數據庫爲何又如何走向分佈式？

數據庫領域圖靈獎獲得者 Jim Gray 說過：“所有的存儲系統最終都會演變成數據庫系統。(All storage systems will eventually evolve to be database systems.)”

數據庫系統經過幾十年演進後，分佈式數據庫在近幾年發展如火如荼，國內外出現了很多分佈式數據庫創業公司，爲什麼分佈式數據庫開始流行？在計算機歷史上出現過數百個數據庫系統，爲什麼我們需要分佈式數據庫？

爲何走向分佈式數據庫

讓我們追溯數據庫發展歷史，看看分佈式數據庫爲何出現。

1960 年代：第一個數據庫

1961 年，Charles Bachman 等人設計了第一個計算機數據庫管理系統 (DBMS)，這個網狀模型(Network model) 的數據庫被稱爲 IDS（Integrated Data Store）。隨後不久，IBM 在 1968 年開發了層次模型 (hierarchical model) 的數據庫 IMS（Information Management System）。這兩個數據庫都是實驗性的先行者。

無論是網狀模型還是層次模型，最開始的數據庫都非常難用，沒有很多我們如今習慣的東西：

• 沒有表，更沒有 SQL；

• 數據粗暴存儲，不得不通過指針遍歷整個數據結構來進行查詢；

• 邏輯層和物理層並不分離，沒有獨立的模式 (schema)，要增加屬性，必須重新加載全部的數據然後轉存；

最初的數據庫沒有獨立存儲數據，沒有任何抽象，這導致開發者需要耗費大量精力來使用。

1970 年代：關係型數據庫

到了 20 世紀 70 年代，IBM 的研究員 Edgar Frank Codd 看到他周圍的程序員每天花費大量時間處理查詢、改變模式和思考如何存儲數據，於是他創造了今天衆所周知的關係模型。

關係模型建立之後，IBM 開啓了著名的 System R 進行專項研究，該項目是第一個實現 SQL 和事務的 DBMS。System R 的設計對後來各類數據庫產生了積極的影響。

關係模型擺脫了查詢和數據存儲之間的緊密耦合，查詢獨立於存儲，數據庫可以自由地在幕後進行優化，程序員無需知道背後的存儲方式，只需要通過 SQL 與數據庫進行交互，這對於開發者非常友好。

1978 年 Oracle 發佈，點燃了商業數據庫的導火線。

20 世紀末：走向成熟

接下來的幾十年裏，數據庫進入成長期，一步步走向成熟。早期的層次模型和網狀模型消失了，關係型數據庫成爲主流。SQL 成爲數據庫標準查詢語言，直到今天我們仍然在使用。

數據庫商業化也越來越完善，同時開始出現如 PostgreSQL 和 MySQL 等開源數據庫。由於大型商業數據庫非常昂貴，一些互聯網企業開始使用 MySQL 等開源數據庫作爲替代方案。

2000 年代：NoSQL

21 世紀伊始，互聯網走向繁榮，突然間許多公司需要支持越來越多的用戶，並且必須 24 * 7 不間斷運行服務，爲此互聯網公司不得不在多臺計算機上覆制 (replication) 和分片 (shard) 存儲他們的數據。

分片存儲即將表按照某個關鍵字拆分成多個分片，例如按照年進行拆分，2000 年的數據存儲在第一臺機器上，2001 年的數據存儲在第二臺機器上，以此類推。這通常由數據庫管理員來完成。同時爲了讓應用程序不修改代碼、無感知地讀寫分片數據，必須要將一箇中間件放到這些分片前面，將應用程序原本的 SQL 轉換爲支持分片的 SQL。如下圖所示。

當然，這類方案也有一些缺點，例如：

• 不支持跨分片事務；

• 重新分片是困難的，會成爲數據庫管理員的噩夢；

Google 等公司如此分片存儲數據庫，目的是不惜一切代價來獲得可擴展性，因爲他們需要構建越來越大的應用，服務越來越多的用戶。這些事情都是爲了追求可擴展性。

爲此，這些公司還開發了 NoSQL，不惜放棄了關係模型，放棄了事務，放棄了數據一致性保證（有的 NoSQL 只保證最終一致性）。

前文提到，20 世紀 70 年代 Edgar Frank Codd 爲了減輕開發人員心智負擔而設計了關係型數據庫，而 NoSQL 解決了應用程序所需的可擴展性，但又好似退回到了以前，程序員又要面臨 NoSQL 功能不足的問題——也就是 Jim Gray 所說的：“所有的存儲系統最終都會演變成數據庫系統。”

2010 年代：分佈式數據庫

爲什麼要構建分佈式數據庫呢？通過歷史發展分析應該相當清楚了，現有的數據庫解決方案給開發者和管理員帶來了過重的負擔。當你開始一個新的大項目，選擇一個單點數據庫會犧牲掉未來的可擴展性，選擇一個 NoSQL 又會讓開發者承受額外的負擔來解決問題，並且可能不支持事務等優秀的功能。

分佈式數據庫試圖結合兩者優點，構建成爲兩全其美的系統：既能支持完整的關係模型，又能提供高可擴展性和可用性。分佈式數據庫常被稱爲 NewSQL 或 Distributed SQL——無論怎麼稱呼，都指那些在多臺機器運行的數據庫。

這不是說 NoSQL 是完全沒用的，事實上人們在 NoSQL 上構建了許多成功的系統，但這要困難得多。Google 的分佈式數據庫 Spanner 論文中有一句話：

We believe it is better to have application programmers deal with performance problems due to overuse of transactions as bottlenecks arise, rather than always coding around the lack of transactions.

翻譯過來就是：“我們認爲最好讓應用程序開發者來解決因過度使用事務而導致的性能問題，而不是讓開發者總是圍繞着缺少事務編寫代碼。”

也就是說，事務是否會造成性能影響的應該由業務開發者來考慮，而作爲一個數據庫必須提供事務機制，來滿足各種應用常見的需求。

Spanner 論文發表後，開始湧現出許多優秀的開源分佈式數據庫，其中具有代表性的有：CockroachDB、TiDB、YugabyteDB 和最近開源的 OceanBase 等等。

通過回顧數據庫歷史進程，我們知道了爲什麼出現分佈式數據庫，現在我們要關注如何實現分佈式數據庫。

如何實現分佈式數據庫

分佈式數據庫我們關注：

1. 數據如何在機器上分佈；

2. 數據副本如何保持一致性；

3. 如何支持 SQL；

4. 分佈式事務如何實現；

當然，本文只會簡述分佈式數據庫的簡單原理，許多細節不會涉及，如果你想要深入學習，除了學習源代碼外，可以關注筆者的公衆號和筆者下半年將要出版的書籍。

數據分佈

NewSQL 和 NoSQL 的數據分佈是類似的，他們都認爲所有數據不適合存放在一臺機器上，必須分片存儲。因此需要考慮：

1. 如何劃分分片？

2. 如何定位特定的數據？

分片主要有兩種方法：哈希或範圍。

哈希分片將某個關鍵字通過哈希函數計算得到一個哈希值，根據哈希值來判斷數據應該存儲的位置。這樣做的優點是易於定位數據，只需要運行一下哈希函數就能夠知道數據存儲在哪臺機器；但缺點也十分明顯，由於哈希函數是隨機的，數據將無法支持範圍查詢。

範圍分片指按照某個範圍劃分數據存儲的位置，舉個最簡單的例子，按照首字母從 A-Z 分爲 26 個分區，這樣的分片方式對於範圍查詢非常有用；缺點是通常需要對關鍵字進行查詢才知道數據處於哪個節點，這看起來會造成一些性能損耗，但由於範圍很少會改變，很容易將範圍信息緩存起來。

例如下圖所示，我們按照關鍵字劃分爲三個範圍：[a 開頭，h 開頭)、[h 開頭，p 開頭)、[p 開頭，無窮）。

如下圖所示，這樣進行範圍查詢效率會更高。

我們關心的最後一個問題是，當某個分片的數據過大，超過我們所設的閾值時，如何擴展分片？由於有一箇中間層進行轉換，這也很容易進行，只需要在現有的範圍中選取某個點，然後將該範圍一分爲二，便得到兩個分區。

如下圖所示，當 p-z 的數據量超過閾值，爲了避免負載壓力，我們拆分該範圍。

顯然，這裏有一個取捨 (trade-off)，如果範圍閾值設置得很大，那麼在機器之間移動數據會很慢，也很難快速恢復某個故障機器的數據；但如果範圍閾值設置得很小，中間轉換層可能會增長得非常快，增加查詢的開銷，同時數據也會頻繁拆分。一般範圍閾值選擇 64 MB 到 128 MB，Cockroachdb 使用 64MB 大小，TiDB 默認閾值爲 96 MB 大小。

數據一致性

一個帶有 “分佈式” 三個字的系統當然需要容忍錯誤，爲了避免一臺機器掛掉後數據徹底丟失，通常會將數據複製到多臺機器上冗餘存儲。但分佈式系統中請求會丟失、機器會宕機、網絡會延遲，因此我們需要某種方式知道冗餘的副本中哪些數據是最新的，

最常見的複製數據方式是主從同步（或者直接複製冷備數據），主節點將更新操作同步到從節點。但這樣存在潛在的數據不一致問題，同步更新操作丟失了怎麼辦？從節點恰好寫入失敗了怎麼辦？有時這些錯誤甚至會永久損壞數據，需要數據庫管理員介入。

保持一致性常常會以性能爲代價 (以後我們會討論)，因此，大部分 NoSQL 只保證最終一致性，並通過一些衝突處理方案來解決數據不一致。

很多名詞沒有加以解釋，如果你覺得很多名詞你不瞭解，想要了解更多內容，請關注我的公衆號，或是期待我下半年將出版的新書。

現有著名的複製數據的算法是我們經常聽到的 Paxos、Raft、Zab 或 Viewstamped Replication 等算法。其中，Google 花了數年時間才實現了一個滿足生產需要的 Paxos 算法。而 Raft 是一個後起新秀，是斯坦福大學的博士生 Ongaro Diego 基於 Paxos 設計的一個更具理解性的共識算法。Raft 誕生後便席捲了分佈式共識算法領域，如今你可以在 Github 搜到許許多多的 Raft 開源實現，把他們 clone 到你的應用中來實現可靠的數據複製吧（千萬別真的這麼幹！）。

Raft 未必真的易於使用，但它已經使得編寫具有一致性的系統比以往更容易，具體算法細節不再展開，感興趣的同學請閱讀前文《條分縷析 Raft 共識算法》。

簡而言之，Raft 算法只需要超過半數的節點寫入成功，即認爲本次寫操作成功，並返回結果給客戶端。發生故障時，Raft 算法可以重新選舉領導者，只要少於半數的節點發生故障，Raft 就能正常工作。

Raft 算法可以滿足可靠複製數據，同時系統能夠容忍不超過半數的節點故障。

在分佈式數據庫中，一個分片使用一個共識組 (consensus group) 複製數據，具體的 Raft 共識組稱爲 Raft 組(Raft group)，Paxos 共識組稱爲 Paxos 組(Paxos group)。

我從 TiDB 官網中找來一張圖，TiDB 將一個分片稱爲一個 Region，如圖中有三個 Raft 組，用來複制三個 Region 的數據。

圖片權侵刪

軟件工程沒有銀彈，使用共識算法仍然需要面臨許多生產問題，例如成員變更、範圍分區變更、實現線性一致性等等問題都要去克服。只不過現在我們有了堅實的學術支撐，這樣進行復制是正確的。

SQL 表數據 KV 化存儲

解決了 KV 存儲以後，我們還要想辦法用 KV 結構來存儲表結構。通常，增刪查改可以抽象成如下 5 個 KV 操作（也許可以再多些，但基本就是這些）。

Get(key)
Put(key, value)
ConditionalPut(key, value, exp)
Scan(startKey, endKey)
Del(key)

我們討論的是 OLTP 類分佈式數據庫都是行存。我們以 CockroachDB 舉例，一個表通常包含行和列，可以將一個錶轉換成如下結構：

/<table>/<index>/<key>/<column> -> Value

爲了可讀性使用斜槓來分割字段。/<index>/<key>/ 這部分表示需要每個表必須有一個主鍵。這樣看不大直觀，舉個例子，對於以下建表語句：

CREATE TABLE test (
    id      INTEGER PRIMARY KEY,
    name    VARCHAR,
    price   FLOAT,
);

轉換成 KV 存儲如圖所示：

當然，這樣的存儲方式會將 float 等類型通通轉換爲 string 類型。

除此之外，數據庫通常會創建一些非主鍵索引，主要分爲兩類：

• 唯一索引

• 非唯一索引

唯一索引比較簡單，由於值唯一，我們可以通過如下映射：

/<table>/<index>/<key> -> Value

如圖所示：

非唯一索引和主鍵類似，只不過其值爲空。如圖所示：

上述表數據 KV 化規則已經有些陳舊，CockroachDB 最新的映射規則參閱《Structured data encoding in CockroachDB SQL》。但其中的思想是相似的。

當然，表數據 KV 化並不只有這種方式，TiDB 則按照如下規則進行映射：

該方式沒有將每一列拆開存儲，方法大同小異，詳細內容不再展開，參閱《三篇文章瞭解 TiDB 技術內幕 - 說計算》。

分佈式事務

當我們談論事務時，永遠離不開 ACID。分佈式事務中最難保證的是原子性和隔離性。在分佈式系統中，原子性需要原子提交協議來實現，例如兩階段提交；而隔離性可以通過兩階段鎖或多版本併發控制 (MVCC) 來實現不同的隔離級別。

分佈式數據庫們都實現了 MVCC，Google Spanner 設計了 TrueTime 來實現，但 TrueTime 並不開源；TiDB 則基於 Google Percolator 來實現。Cockroach 的分佈式事務實現比較複雜，涉及到不少新東西，後面我們會展開來談。

篇幅原因，分佈式事務會作爲我們後面討論的重點方向，在此不再展開。

結語

最終，一個分佈式數據庫簡要架構如下圖所示。

開源造福人類，如今湧現了許多優秀的開源分佈式數據庫，他們都是很好的學習材料，筆者也會在後續文章中繼續分享 CockroachDB、TiDB、YugabyteDB 和 OceanBase 的技術細節。感謝這些開源者。

值得一提的是，在數據庫領域獲得圖靈獎的學者不多，一共 Charles Bachman、Edgar Frank Codd、Jim Gray、Michael Stonebraker 四位大師，本文提到了其中前三位。2020 年圖靈獎獲得者 Jeffrey Ullman 雖然在數據庫領域也有所建樹，但他是因爲編程語言領域（“龍書”）而獲獎，而非在數據庫領域獲獎。無論是學術領域還是工業領域，衷心希望分佈式 + 數據庫能加把勁！

相關閱讀

條分縷析 Raft 算法

條分縷析 Raft 算法 (續)：日誌壓縮和性能優化

運行 3000 次都不出錯的 MIT 6.824 Raft 實驗

參考文獻

1. All storage systems will eventually evolve to be database systems. - Jim Gray

2. "The hows and whys of a distributed SQL database" by Alex Robinson

3. 《三篇文章瞭解 TiDB 技術內幕 - 說計算》

4. Corbett J C, Dean J, Epstein M, et al. "Spanner: Google’s globally distributed database." ACM Transactions on Computer Systems (TOCS), 2013, 31(3): 1-22.

5. Peng D, Dabek F. "Large-scale incremental processing using distributed transactions and notifications." 2010.

6. Chandra T D, Griesemer R, Redstone J. "Paxos made live: an engineering perspective."Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing. 2007: 398-407.

7. D. Ongaro and J. Ousterhout. "In search of an understandable consensus algorithm." In USENIX Annual Technical Conference (ATC), pages 305--320, 2014.

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/psB4euZAww1bhiDRZPdDuQ