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

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

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

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

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

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

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

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

沒(méi)有表，更沒(méi)有 SQL；

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

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

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

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

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

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

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

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

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

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

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

2000 年代：NoSQL

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如何支持 SQL；

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

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

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

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

如何劃分分片？

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

分片主要有兩種方法：哈?；蚍秶?。

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

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

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

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

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

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

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

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

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

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

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

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

現(xiàn)有著名的復(fù)制數(shù)據(jù)的算法是我們經(jīng)常聽(tī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è)更具理解性的共識(shí)算法。Raft 誕生后便席卷了分布式共識(shí)算法領(lǐng)域，如今你可以在 Github 搜到許許多多的 Raft 開(kāi)源實(shí)現(xiàn)，把他們 clone 到你的應(yīng)用中來(lái)實(shí)現(xiàn)可靠的數(shù)據(jù)復(fù)制吧（千萬(wàn)別真的這么干?。?/p>

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

簡(jiǎn)而言之，Raft 算法只需要超過(guò)半數(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)能夠容忍不超過(guò)半數(shù)的節(jié)點(diǎn)故障。

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

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

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

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

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

Get（key）

Put（key， value）

ConditionalPut（key， value， exp）

Scan（startKey， endKey）

Del（key）

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

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

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

CREATE TABLE test （

id INTEGER PRIMARY KEY，

name VARCHAR，

price FLOAT，

）;

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

當(dāng)然，這樣的存儲(chǔ)方式會(huì)將 float 等類型通通轉(zhuǎn)換為 string 類型。

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

唯一索引

非唯一索引

唯一索引比較簡(jiǎn)單，由于值唯一，我們可以通過(guò)如下映射：

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

如圖所示：

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

上述表數(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)]有將每一列拆開(kāi)存儲(chǔ)，方法大同小異，詳細(xì)內(nèi)容不再展開(kāi)，參閱《三篇文章了解 TiDB 技術(shù)內(nèi)幕 - 說(shuō)計(jì)算》。

分布式事務(wù)

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

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

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

結(jié)語(yǔ)

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

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

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

編輯：jq