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

數(shù)據(jù)庫系統(tǒng)經(jīng)過幾十年演進后，分布式數(shù)據(jù)庫在近幾年發(fā)展如火如荼，國內(nèi)外出現(xiàn)了很多分布式數(shù)據(jù)庫創(chuàng)業(yè)公司，為什么分布式數(shù)據(jù)庫開始流行？在計算機歷史上出現(xiàn)過數(shù)百個數(shù)據(jù)庫系統(tǒng)，為什么我們需要分布式數(shù)據(jù)庫？

為何走向分布式數(shù)據(jù)庫

讓我們追溯數(shù)據(jù)庫發(fā)展歷史，看看分布式數(shù)據(jù)庫為何出現(xiàn)。

1960 年代：第一個數(shù)據(jù)庫

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

無論是網(wǎng)狀模型還是層次模型，最開始的數(shù)據(jù)庫都非常難用，沒有很多我們?nèi)缃窳晳T的東西：

沒有表，更沒有 SQL；

數(shù)據(jù)粗暴存儲，不得不通過指針遍歷整個數(shù)據(jù)結(jié)構(gòu)來進行查詢；

邏輯層和物理層并不分離，沒有獨立的模式（schema），要增加屬性，必須重新加載全部的數(shù)據(jù)然后轉(zhuǎn)存；

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

1970 年代：關(guān)系型數(shù)據(jù)庫

到了20世紀70年代，IBM 的研究員 Edgar Frank Codd 看到他周圍的程序員每天花費大量時間處理查詢、改變模式和思考如何存儲數(shù)據(jù)，于是他創(chuàng)造了今天眾所周知的關(guān)系模型。

關(guān)系模型建立之后，IBM 開啟了著名的 System R 進行專項研究，該項目是第一個實現(xiàn) SQL 和事務(wù)的 DBMS。System R 的設(shè)計對后來各類數(shù)據(jù)庫產(chǎn)生了積極的影響。

關(guān)系模型擺脫了查詢和數(shù)據(jù)存儲之間的緊密耦合，查詢獨立于存儲，數(shù)據(jù)庫可以自由地在幕后進行優(yōu)化，程序員無需知道背后的存儲方式，只需要通過 SQL 與數(shù)據(jù)庫進行交互，這對于開發(fā)者非常友好。

1978 年 Oracle 發(fā)布，點燃了商業(yè)數(shù)據(jù)庫的導火線。

20世紀末：走向成熟

接下來的幾十年里，數(shù)據(jù)庫進入成長期，一步步走向成熟。早期的層次模型和網(wǎng)狀模型消失了，關(guān)系型數(shù)據(jù)庫成為主流。SQL 成為數(shù)據(jù)庫標準查詢語言，直到今天我們?nèi)匀辉谑褂谩?/p>

數(shù)據(jù)庫商業(yè)化也越來越完善，同時開始出現(xiàn)如 PostgreSQL 和 MySQL 等開源數(shù)據(jù)庫。由于大型商業(yè)數(shù)據(jù)庫非常昂貴，一些互聯(lián)網(wǎng)企業(yè)開始使用 MySQL 等開源數(shù)據(jù)庫作為替代方案。

2000 年代：NoSQL

21 世紀伊始，互聯(lián)網(wǎng)走向繁榮，突然間許多公司需要支持越來越多的用戶，并且必須 24 * 7 不間斷運行服務(wù)，為此互聯(lián)網(wǎng)公司不得不在多臺計算機上復制（replication）和分片（shard）存儲他們的數(shù)據(jù)。

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

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

不支持跨分片事務(wù)；

重新分片是困難的，會成為數(shù)據(jù)庫管理員的噩夢；

Google 等公司如此分片存儲數(shù)據(jù)庫，目的是不惜一切代價來獲得可擴展性，因為他們需要構(gòu)建越來越大的應(yīng)用，服務(wù)越來越多的用戶。這些事情都是為了追求可擴展性。

為此，這些公司還開發(fā)了 NoSQL，不惜放棄了關(guān)系模型，放棄了事務(wù)，放棄了數(shù)據(jù)一致性保證（有的 NoSQL 只保證最終一致性）。

前文提到，20世紀70年代 Edgar Frank Codd 為了減輕開發(fā)人員心智負擔而設(shè)計了關(guān)系型數(shù)據(jù)庫，而 NoSQL 解決了應(yīng)用程序所需的可擴展性，但又好似退回到了以前，程序員又要面臨 NoSQL 功能不足的問題——也就是 Jim Gray 所說的：“所有的存儲系統(tǒng)最終都會演變成數(shù)據(jù)庫系統(tǒng)?！?/p>

2010 年代：分布式數(shù)據(jù)庫

為什么要構(gòu)建分布式數(shù)據(jù)庫呢？通過歷史發(fā)展分析應(yīng)該相當清楚了，現(xiàn)有的數(shù)據(jù)庫解決方案給開發(fā)者和管理員帶來了過重的負擔。當你開始一個新的大項目，選擇一個單點數(shù)據(jù)庫會犧牲掉未來的可擴展性，選擇一個 NoSQL 又會讓開發(fā)者承受額外的負擔來解決問題，并且可能不支持事務(wù)等優(yōu)秀的功能。

分布式數(shù)據(jù)庫試圖結(jié)合兩者優(yōu)點，構(gòu)建成為兩全其美的系統(tǒng)：既能支持完整的關(guān)系模型，又能提供高可擴展性和可用性。分布式數(shù)據(jù)庫常被稱為 NewSQL 或 Distributed SQL——無論怎么稱呼，都指那些在多臺機器運行的數(shù)據(jù)庫。

這不是說 NoSQL 是完全沒用的，事實上人們在 NoSQL 上構(gòu)建了許多成功的系統(tǒng)，但這要困難得多。Google 的分布式數(shù)據(jù)庫 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.

翻譯過來就是：“我們認為最好讓應(yīng)用程序開發(fā)者來解決因過度使用事務(wù)而導致的性能問題，而不是讓開發(fā)者總是圍繞著缺少事務(wù)編寫代碼?！?/p>

也就是說，事務(wù)是否會造成性能影響的應(yīng)該由業(yè)務(wù)開發(fā)者來考慮，而作為一個數(shù)據(jù)庫必須提供事務(wù)機制，來滿足各種應(yīng)用常見的需求。

Spanner 論文發(fā)表后，開始涌現(xiàn)出許多優(yōu)秀的開源分布式數(shù)據(jù)庫，其中具有代表性的有：CockroachDB、TiDB、YugabyteDB 和最近開源的 OceanBase 等等。

通過回顧數(shù)據(jù)庫歷史進程，我們知道了為什么出現(xiàn)分布式數(shù)據(jù)庫，現(xiàn)在我們要關(guān)注如何實現(xiàn)分布式數(shù)據(jù)庫。

如何實現(xiàn)分布式數(shù)據(jù)庫

分布式數(shù)據(jù)庫我們關(guān)注：

數(shù)據(jù)如何在機器上分布；

數(shù)據(jù)副本如何保持一致性；

如何支持 SQL；

分布式事務(wù)如何實現(xiàn)；

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

數(shù)據(jù)分布

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

如何劃分分片？

如何定位特定的數(shù)據(jù)？

分片主要有兩種方法：哈?；蚍秶?/p>

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

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

例如下圖所示，我們按照關(guān)鍵字劃分為三個范圍：［a 開頭，h 開頭）、［h 開頭，p 開頭）、［p 開頭，無窮）。

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

我們關(guān)心的最后一個問題是，當某個分片的數(shù)據(jù)過大，超過我們所設(shè)的閾值時，如何擴展分片？由于有一個中間層進行轉(zhuǎn)換，這也很容易進行，只需要在現(xiàn)有的范圍中選取某個點，然后將該范圍一分為二，便得到兩個分區(qū)。

如下圖所示，當 p-z 的數(shù)據(jù)量超過閾值，為了避免負載壓力，我們拆分該范圍。

顯然，這里有一個取舍（trade-off），如果范圍閾值設(shè)置得很大，那么在機器之間移動數(shù)據(jù)會很慢，也很難快速恢復某個故障機器的數(shù)據(jù)；但如果范圍閾值設(shè)置得很小，中間轉(zhuǎn)換層可能會增長得非?？?，增加查詢的開銷，同時數(shù)據(jù)也會頻繁拆分。一般范圍閾值選擇 64 MB 到 128 MB，Cockroachdb 使用 64MB 大小，TiDB 默認閾值為 96 MB 大小。

數(shù)據(jù)一致性

一個帶有“分布式”三個字的系統(tǒng)當然需要容忍錯誤，為了避免一臺機器掛掉后數(shù)據(jù)徹底丟失，通常會將數(shù)據(jù)復制到多臺機器上冗余存儲。但分布式系統(tǒng)中請求會丟失、機器會宕機、網(wǎng)絡(luò)會延遲，因此我們需要某種方式知道冗余的副本中哪些數(shù)據(jù)是最新的，

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

保持一致性常常會以性能為代價（以后我們會討論），因此，大部分 NoSQL 只保證最終一致性，并通過一些沖突處理方案來解決數(shù)據(jù)不一致。

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

現(xiàn)有著名的復制數(shù)據(jù)的算法是我們經(jīng)常聽到的 Paxos、Raft、Zab 或 Viewstamped Replication 等算法。其中，Google 花了數(shù)年時間才實現(xiàn)了一個滿足生產(chǎn)需要的 Paxos 算法。而 Raft 是一個后起新秀，是斯坦福大學的博士生 Ongaro Diego 基于 Paxos 設(shè)計的一個更具理解性的共識算法。Raft 誕生后便席卷了分布式共識算法領(lǐng)域，如今你可以在 Github 搜到許許多多的 Raft 開源實現(xiàn)，把他們 clone 到你的應(yīng)用中來實現(xiàn)可靠的數(shù)據(jù)復制吧（千萬別真的這么干！）。

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

簡而言之，Raft 算法只需要超過半數(shù)的節(jié)點寫入成功，即認為本次寫操作成功，并返回結(jié)果給客戶端。發(fā)生故障時，Raft 算法可以重新選舉領(lǐng)導者，只要少于半數(shù)的節(jié)點發(fā)生故障，Raft 就能正常工作。

Raft 算法可以滿足可靠復制數(shù)據(jù)，同時系統(tǒng)能夠容忍不超過半數(shù)的節(jié)點故障。

在分布式數(shù)據(jù)庫中，一個分片使用一個共識組（consensus group）復制數(shù)據(jù)，具體的 Raft 共識組稱為 Raft 組（Raft group），Paxos 共識組稱為 Paxos 組（Paxos group）。

我從 TiDB 官網(wǎng)中找來一張圖，TiDB 將一個分片稱為一個 Region，如圖中有三個 Raft 組，用來復制三個 Region 的數(shù)據(jù)。

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

SQL 表數(shù)據(jù) KV 化存儲

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

Get（key）

Put（key， value）

ConditionalPut（key， value， exp）

Scan（startKey， endKey）

Del（key）

我們討論的是 OLTP 類分布式數(shù)據(jù)庫都是行存。我們以 CockroachDB 舉例，一個表通常包含行和列，可以將一個表轉(zhuǎn)換成如下結(jié)構(gòu)：

/《table》/《index》/《key》/《column》 -》 Value

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

CREATE TABLE test （

id INTEGER PRIMARY KEY，

name VARCHAR，

price FLOAT，

）;

轉(zhuǎn)換成 KV 存儲如圖所示：

當然，這樣的存儲方式會將 float 等類型通通轉(zhuǎn)換為 string 類型。

除此之外，數(shù)據(jù)庫通常會創(chuàng)建一些非主鍵索引，主要分為兩類：

唯一索引

非唯一索引

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

/《table》/《index》/《key》 -》 Value

如圖所示：

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

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

當然，表數(shù)據(jù) KV 化并不只有這種方式，TiDB 則按照如下規(guī)則進行映射：

該方式?jīng)]有將每一列拆開存儲，方法大同小異，詳細內(nèi)容不再展開，參閱《三篇文章了解 TiDB 技術(shù)內(nèi)幕 - 說計算》。

分布式事務(wù)

當我們談?wù)撌聞?wù)時，永遠離不開 ACID。分布式事務(wù)中最難保證的是原子性和隔離性。在分布式系統(tǒng)中，原子性需要原子提交協(xié)議來實現(xiàn)，例如兩階段提交；而隔離性可以通過兩階段鎖或多版本并發(fā)控制（MVCC）來實現(xiàn)不同的隔離級別。

分布式數(shù)據(jù)庫們都實現(xiàn)了 MVCC，Google Spanner 設(shè)計了 TrueTime 來實現(xiàn)，但 TrueTime 并不開源；TiDB 則基于 Google Percolator 來實現(xiàn)。Cockroach 的分布式事務(wù)實現(xiàn)比較復雜，涉及到不少新東西，后面我們會展開來談。

篇幅原因，分布式事務(wù)會作為我們后面討論的重點方向，在此不再展開。

結(jié)語

最終，一個分布式數(shù)據(jù)庫簡要架構(gòu)如下圖所示。

開源造福人類，如今涌現(xiàn)了許多優(yōu)秀的開源分布式數(shù)據(jù)庫，他們都是很好的學習材料，筆者也會在后續(xù)文章中繼續(xù)分享 CockroachDB、TiDB、YugabyteDB 和 OceanBase 的技術(shù)細節(jié)。感謝這些開源者。

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

編輯：jq