數(shù)據(jù)庫領(lǐng)域圖靈獎(jiǎ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)過幾十年演進(jìn)后，分布式數(shù)據(jù)庫在近幾年發(fā)展如火如荼，國內(nèi)外出現(xiàn)了很多分布式數(shù)據(jù)庫創(chuàng)業(yè)公司，為什么分布式數(shù)據(jù)庫開始流行？在計(jì)算機(jī)歷史上出現(xiàn)過數(shù)百個(gè)數(shù)據(jù)庫系統(tǒng)，為什么我們需要分布式數(shù)據(jù)庫？

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

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

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

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

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

沒有表，更沒有 SQL；

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

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

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

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

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

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

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

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

20世紀(jì)末：走向成熟

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

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

2000 年代：NoSQL

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

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

當(dāng)然，這類方案也有一些缺點(diǎn)，例如：

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

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

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

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

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

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

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

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

這不是說 NoSQL 是完全沒用的，事實(shí)上人們在 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.

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

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

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

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

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

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

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

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

如何支持 SQL；

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

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

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

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

如何劃分分片？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Get（key）

Put（key， value）

ConditionalPut（key， value， exp）

Scan（startKey， endKey）

Del（key）

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

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

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

CREATE TABLE test （

id INTEGER PRIMARY KEY，

name VARCHAR，

price FLOAT，

）;

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

當(dāng)然，這樣的存儲方式會將 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》。但其中的思想是相似的。

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

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

分布式事務(wù)

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

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

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

結(jié)語

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

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

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

編輯：jq