引言

數(shù)據(jù)庫(kù)、操作系統(tǒng)和編譯器并稱為三大系統(tǒng)，可以說(shuō)是整個(gè)計(jì)算機(jī)軟件的基石。其中數(shù)據(jù)庫(kù)更靠近應(yīng)用層，是很多業(yè)務(wù)的支撐。這一領(lǐng)域經(jīng)過了幾十年的發(fā)展，不斷的有新的進(jìn)展。

很多人用過數(shù)據(jù)庫(kù)，但是很少有人實(shí)現(xiàn)過一個(gè)數(shù)據(jù)庫(kù)，特別是實(shí)現(xiàn)一個(gè)分布式數(shù)據(jù)庫(kù)。了解數(shù)據(jù)庫(kù)的實(shí)現(xiàn)原理和細(xì)節(jié)，一方面可以提高個(gè)人技術(shù)，對(duì)構(gòu)建其他系統(tǒng)有幫助，另一方面也有利于用好數(shù)據(jù)庫(kù)。

研究一門技術(shù)最好的方法是研究其中一個(gè)開源項(xiàng)目，數(shù)據(jù)庫(kù)也不例外。單機(jī)數(shù)據(jù)庫(kù)領(lǐng)域有很多很好的開源項(xiàng)目，其中 MySQL 和 PostgreSQL 是其中知名度最高的兩個(gè)，不少同學(xué)都看過這兩個(gè)項(xiàng)目的代碼。但是分布式數(shù)據(jù)庫(kù)方面，好的開源項(xiàng)目并不多。 TiDB 目前獲得了廣泛的關(guān)注，特別是一些技術(shù)愛好者，希望能夠參與這個(gè)項(xiàng)目。由于分布式數(shù)據(jù)庫(kù)自身的復(fù)雜性，很多人并不能很好的理解整個(gè)項(xiàng)目，所以我希望能寫一些文章，自頂向上，由淺入深，講述 TiDB 的一些技術(shù)原理，包括用戶可見的技術(shù)以及大量隱藏在 SQL 界面后用戶不可見的技術(shù)點(diǎn)。

保存數(shù)據(jù)

[[277076]]

數(shù)據(jù)庫(kù)最根本的功能是能把數(shù)據(jù)存下來(lái)，所以我們從這里開始。

保存數(shù)據(jù)的方法很多，最簡(jiǎn)單的方法是直接在內(nèi)存中建一個(gè)數(shù)據(jù)結(jié)構(gòu)，保存用戶發(fā)來(lái)的數(shù)據(jù)。比如用一個(gè)數(shù)組，每當(dāng)收到一條數(shù)據(jù)就向數(shù)組中追加一條記錄。這個(gè)方案十分簡(jiǎn)單，能滿足最基本，并且性能肯定會(huì)很好，但是除此之外卻是漏洞百出，其中最大的問題是數(shù)據(jù)完全在內(nèi)存中，一旦停機(jī)或者是服務(wù)重啟，數(shù)據(jù)就會(huì)永久丟失。

為了解決數(shù)據(jù)丟失問題，我們可以把數(shù)據(jù)放在非易失存儲(chǔ)介質(zhì)(比如硬盤)中。改進(jìn)的方案是在磁盤上創(chuàng)建一個(gè)文件，收到一條數(shù)據(jù)，就在文件中 Append 一行。OK，我們現(xiàn)在有了一個(gè)能持久化存儲(chǔ)數(shù)據(jù)的方案。但是還不夠好，假設(shè)這塊磁盤出現(xiàn)了壞道呢?我們可以做 RAID (Redundant Array of Independent Disks)，提供單機(jī)冗余存儲(chǔ)。如果整臺(tái)機(jī)器都掛了呢?比如出現(xiàn)了火災(zāi)，RAID 也保不住這些數(shù)據(jù)。我們還可以將存儲(chǔ)改用網(wǎng)絡(luò)存儲(chǔ)，或者是通過硬件或者軟件進(jìn)行存儲(chǔ)復(fù)制。到這里似乎我們已經(jīng)解決了數(shù)據(jù)安全問題，可以松一口氣了。But，做復(fù)制過程中是否能保證副本之間的一致性?也就是在保證數(shù)據(jù)不丟的前提下，還要保證數(shù)據(jù)不錯(cuò)。保證數(shù)據(jù)不丟不錯(cuò)只是一項(xiàng)最基本的要求，還有更多令人頭疼的問題等待解決：

• 能否支持跨數(shù)據(jù)中心的容災(zāi)?
• 寫入速度是否夠快?
• 數(shù)據(jù)保存下來(lái)后，是否方便讀取?
• 保存的數(shù)據(jù)如何修改?如何支持并發(fā)的修改?
• 如何原子地修改多條記錄?

這些問題每一項(xiàng)都非常難，但是要做一個(gè)優(yōu)秀的數(shù)據(jù)存儲(chǔ)系統(tǒng)，必須要解決上述的每一個(gè)難題。 為了解決數(shù)據(jù)存儲(chǔ)問題，我們開發(fā)了 TiKV 這個(gè)項(xiàng)目。接下來(lái)我向大家介紹一下 TiKV 的一些設(shè)計(jì)思想和基本概念。

Key-Value

作為保存數(shù)據(jù)的系統(tǒng)，首先要決定的是數(shù)據(jù)的存儲(chǔ)模型，也就是數(shù)據(jù)以什么樣的形式保存下來(lái)。TiKV 的選擇是 Key-Value 模型，并且提供有序遍歷方法。簡(jiǎn)單來(lái)講，可以將 TiKV 看做一個(gè)巨大的 Map，其中 Key 和 Value 都是原始的 Byte 數(shù)組，在這個(gè) Map 中，Key 按照 Byte 數(shù)組總的原始二進(jìn)制比特位比較順序排列。 大家這里需要對(duì) TiKV 記住兩點(diǎn)：

這是一個(gè)巨大的 Map，也就是存儲(chǔ)的是 Key-Value pair

這個(gè) Map 中的 Key-Value pair 按照 Key 的二進(jìn)制順序有序，也就是我們可以 Seek 到某一個(gè) Key 的位置，然后不斷的調(diào)用 Next 方法以遞增的順序獲取比這個(gè) Key 大的 Key-Value

講了這么多，有人可能會(huì)問了，這里講的存儲(chǔ)模型和 SQL 中表是什么關(guān)系?在這里有一件重要的事情要說(shuō)四遍：

這里的存儲(chǔ)模型和 SQL 中的 Table 無(wú)關(guān)! 這里的存儲(chǔ)模型和 SQL 中的 Table 無(wú)關(guān)! 這里的存儲(chǔ)模型和 SQL 中的 Table 無(wú)關(guān)! 這里的存儲(chǔ)模型和 SQL 中的 Table 無(wú)關(guān)!

現(xiàn)在讓我們忘記 SQL 中的任何概念，專注于討論如何實(shí)現(xiàn) TiKV 這樣一個(gè)高性能高可靠性的巨大的(分布式的) Map。

RocksDB

任何持久化的存儲(chǔ)引擎，數(shù)據(jù)終歸要保存在磁盤上，TiKV 也不例外。但是 TiKV 沒有選擇直接向磁盤上寫數(shù)據(jù)，而是把數(shù)據(jù)保存在 RocksDB 中，具體的數(shù)據(jù)落地由 RocksDB 負(fù)責(zé)。這個(gè)選擇的原因是開發(fā)一個(gè)單機(jī)存儲(chǔ)引擎工作量很大，特別是要做一個(gè)高性能的單機(jī)引擎，需要做各種細(xì)致的優(yōu)化，而 RocksDB 是一個(gè)非常優(yōu)秀的開源的單機(jī)存儲(chǔ)引擎，可以滿足我們對(duì)單機(jī)引擎的各種要求，而且還有 Facebook 的團(tuán)隊(duì)在做持續(xù)的優(yōu)化，這樣我們只投入很少的精力，就能享受到一個(gè)十分強(qiáng)大且在不斷進(jìn)步的單機(jī)引擎。當(dāng)然，我們也為 RocksDB 貢獻(xiàn)了一些代碼，希望這個(gè)項(xiàng)目能越做越好。這里可以簡(jiǎn)單的認(rèn)為 RocksDB 是一個(gè)單機(jī)的 Key-Value Map。

Raft

好了，萬(wàn)里長(zhǎng)征第一步已經(jīng)邁出去了，我們已經(jīng)為數(shù)據(jù)找到一個(gè)高效可靠的本地存儲(chǔ)方案。俗話說(shuō)，萬(wàn)事開頭難，然后中間難，最后結(jié)尾難。接下來(lái)我們面臨一件更難的事情：如何保證單機(jī)失效的情況下，數(shù)據(jù)不丟失，不出錯(cuò)?簡(jiǎn)單來(lái)說(shuō)，我們需要想辦法把數(shù)據(jù)復(fù)制到多臺(tái)機(jī)器上，這樣一臺(tái)機(jī)器掛了，我們還有其他的機(jī)器上的副本;復(fù)雜來(lái)說(shuō)，我們還需要這個(gè)復(fù)制方案是可靠、高效并且能處理副本失效的情況。聽上去比較難，但是好在我們有 Raft 協(xié)議。Raft 是一個(gè)一致性算法，它和 Paxos 等價(jià)，但是更加易于理解。Raft 的論文，感興趣的可以看一下。本文只會(huì)對(duì) Raft 做一個(gè)簡(jiǎn)要的介紹，細(xì)節(jié)問題可以參考論文。另外提一點(diǎn)，Raft 論文只是一個(gè)基本方案，嚴(yán)格按照論文實(shí)現(xiàn)，性能會(huì)很差，我們對(duì) Raft 協(xié)議的實(shí)現(xiàn)做了大量的優(yōu)化，具體的優(yōu)化細(xì)節(jié)可參考我司首席架構(gòu)師 tangliu 同學(xué)的《TiKV 源碼解析系列 - Raft 的優(yōu)化》這篇文章。

Raft 是一個(gè)一致性協(xié)議，提供幾個(gè)重要的功能：

1. Leader 選舉
2. 成員變更
3. 日志復(fù)制

TiKV 利用 Raft 來(lái)做數(shù)據(jù)復(fù)制，每個(gè)數(shù)據(jù)變更都會(huì)落地為一條 Raft 日志，通過 Raft 的日志復(fù)制功能，將數(shù)據(jù)安全可靠地同步到 Group 的多數(shù)節(jié)點(diǎn)中。

到這里我們總結(jié)一下，通過單機(jī)的 RocksDB，我們可以將數(shù)據(jù)快速地存儲(chǔ)在磁盤上;通過 Raft，我們可以將數(shù)據(jù)復(fù)制到多臺(tái)機(jī)器上，以防單機(jī)失效。數(shù)據(jù)的寫入是通過 Raft 這一層的接口寫入，而不是直接寫 RocksDB。通過實(shí)現(xiàn) Raft，我們擁有了一個(gè)分布式的 KV，現(xiàn)在再也不用擔(dān)心某臺(tái)機(jī)器掛掉了。

Region

講到這里，我們可以提到一個(gè) 非常重要的概念：Region。這個(gè)概念是理解后續(xù)一系列機(jī)制的基礎(chǔ)，請(qǐng)仔細(xì)閱讀這一節(jié)。

前面提到，我們將 TiKV 看做一個(gè)巨大的有序的 KV Map，那么為了實(shí)現(xiàn)存儲(chǔ)的水平擴(kuò)展，我們需要將數(shù)據(jù)分散在多臺(tái)機(jī)器上。這里提到的數(shù)據(jù)分散在多臺(tái)機(jī)器上和 Raft 的數(shù)據(jù)復(fù)制不是一個(gè)概念，在這一節(jié)我們先忘記 Raft，假設(shè)所有的數(shù)據(jù)都只有一個(gè)副本，這樣更容易理解。

對(duì)于一個(gè) KV 系統(tǒng)，將數(shù)據(jù)分散在多臺(tái)機(jī)器上有兩種比較典型的方案：一種是按照 Key 做 Hash，根據(jù) Hash 值選擇對(duì)應(yīng)的存儲(chǔ)節(jié)點(diǎn);另一種是分 Range，某一段連續(xù)的 Key 都保存在一個(gè)存儲(chǔ)節(jié)點(diǎn)上。TiKV 選擇了第二種方式，將整個(gè) Key-Value 空間分成很多段，每一段是一系列連續(xù)的 Key，我們將每一段叫做一個(gè) Region，并且我們會(huì)盡量保持每個(gè) Region 中保存的數(shù)據(jù)不超過一定的大小(這個(gè)大小可以配置，目前默認(rèn)是 64mb)。每一個(gè) Region 都可以用 StartKey 到 EndKey 這樣一個(gè)左閉右開區(qū)間來(lái)描述。

注意，這里的 Region 還是和 SQL 中的表沒什么關(guān)系! 請(qǐng)各位繼續(xù)忘記 SQL，只談 KV。 將數(shù)據(jù)劃分成 Region 后，我們將會(huì)做 兩件重要的事情：

• 以 Region 為單位，將數(shù)據(jù)分散在集群中所有的節(jié)點(diǎn)上，并且盡量保證每個(gè)節(jié)點(diǎn)上服務(wù)的 Region 數(shù)量差不多
• 以 Region 為單位做 Raft 的復(fù)制和成員管理

這兩點(diǎn)非常重要，我們一點(diǎn)一點(diǎn)來(lái)說(shuō)。

先看第一點(diǎn)，數(shù)據(jù)按照 Key 切分成很多 Region，每個(gè) Region 的數(shù)據(jù)只會(huì)保存在一個(gè)節(jié)點(diǎn)上面。我們的系統(tǒng)會(huì)有一個(gè)組件來(lái)負(fù)責(zé)將 Region 盡可能均勻的散布在集群中所有的節(jié)點(diǎn)上，這樣一方面實(shí)現(xiàn)了存儲(chǔ)容量的水平擴(kuò)展(增加新的結(jié)點(diǎn)后，會(huì)自動(dòng)將其他節(jié)點(diǎn)上的 Region 調(diào)度過來(lái))，另一方面也實(shí)現(xiàn)了負(fù)載均衡(不會(huì)出現(xiàn)某個(gè)節(jié)點(diǎn)有很多數(shù)據(jù)，其他節(jié)點(diǎn)上沒什么數(shù)據(jù)的情況)。同時(shí)為了保證上層客戶端能夠訪問所需要的數(shù)據(jù)，我們的系統(tǒng)中也會(huì)有一個(gè)組件記錄 Region 在節(jié)點(diǎn)上面的分布情況，也就是通過任意一個(gè) Key 就能查詢到這個(gè) Key 在哪個(gè) Region 中，以及這個(gè) Region 目前在哪個(gè)節(jié)點(diǎn)上。至于是哪個(gè)組件負(fù)責(zé)這兩項(xiàng)工作，會(huì)在后續(xù)介紹。

對(duì)于第二點(diǎn)，TiKV 是以 Region 為單位做數(shù)據(jù)的復(fù)制，也就是一個(gè) Region 的數(shù)據(jù)會(huì)保存多個(gè)副本，我們將每一個(gè)副本叫做一個(gè) Replica。Replica 之間是通過 Raft 來(lái)保持?jǐn)?shù)據(jù)的一致(終于提到了 Raft)，一個(gè) Region 的多個(gè) Replica 會(huì)保存在不同的節(jié)點(diǎn)上，構(gòu)成一個(gè) Raft Group。其中一個(gè) Replica 會(huì)作為這個(gè) Group 的 Leader，其他的 Replica 作為 Follower。所有的讀和寫都是通過 Leader 進(jìn)行，再由 Leader 復(fù)制給 Follower。 大家理解了 Region 之后，應(yīng)該可以理解下面這張圖：

我們以 Region 為單位做數(shù)據(jù)的分散和復(fù)制，就有了一個(gè)分布式的具備一定容災(zāi)能力的 KeyValue 系統(tǒng)，不用再擔(dān)心數(shù)據(jù)存不下，或者是磁盤故障丟失數(shù)據(jù)的問題。這已經(jīng)很 Cool，但是還不夠完美，我們需要更多的功能。

MVCC

很多數(shù)據(jù)庫(kù)都會(huì)實(shí)現(xiàn)多版本控制(MVCC)，TiKV 也不例外。設(shè)想這樣的場(chǎng)景，兩個(gè) Client 同時(shí)去修改一個(gè) Key 的 Value，如果沒有 MVCC，就需要對(duì)數(shù)據(jù)上鎖，在分布式場(chǎng)景下，可能會(huì)帶來(lái)性能以及死鎖問題。 TiKV 的 MVCC 實(shí)現(xiàn)是通過在 Key 后面添加 Version 來(lái)實(shí)現(xiàn)，簡(jiǎn)單來(lái)說(shuō)，沒有 MVCC 之前，可以把 TiKV 看做這樣的：

Key1 -> Value 
    Key2 -> Value 
    …… 
    KeyN -> Value 

有了 MVCC 之后，TiKV 的 Key 排列是這樣的：

Key1-Version3 -> Value 
    Key1-Version2 -> Value 
    Key1-Version1 -> Value 
    …… 
    Key2-Version4 -> Value 
    Key2-Version3 -> Value 
    Key2-Version2 -> Value 
    Key2-Version1 -> Value 
    …… 
    KeyN-Version2 -> Value 
    KeyN-Version1 -> Value 
    …… 

注意，對(duì)于同一個(gè) Key 的多個(gè)版本，我們把版本號(hào)較大的放在前面，版本號(hào)小的放在后面(回憶一下 Key-Value 一節(jié)我們介紹過的 Key 是有序的排列)，這樣當(dāng)用戶通過一個(gè) Key + Version 來(lái)獲取 Value 的時(shí)候，可以將 Key 和 Version 構(gòu)造出 MVCC 的 Key，也就是 Key-Version。然后可以直接 Seek(Key-Version)，定位到第一個(gè)大于等于這個(gè) Key-Version 的位置。

事務(wù)

TiKV 的事務(wù)采用的是 Percolator 模型，并且做了大量的優(yōu)化。事務(wù)的細(xì)節(jié)這里不詳述，大家可以參考論文以及我們的其他文章。這里只提一點(diǎn)，TiKV 的事務(wù)采用樂觀鎖，事務(wù)的執(zhí)行過程中，不會(huì)檢測(cè)寫寫沖突，只有在提交過程中，才會(huì)做沖突檢測(cè)，沖突的雙方中比較早完成提交的會(huì)寫入成功，另一方會(huì)嘗試重新執(zhí)行整個(gè)事務(wù)。當(dāng)業(yè)務(wù)的寫入沖突不嚴(yán)重的情況下，這種模型性能會(huì)很好，比如隨機(jī)更新表中某一行的數(shù)據(jù)，并且表很大。但是如果業(yè)務(wù)的寫入沖突嚴(yán)重，性能就會(huì)很差，舉一個(gè)極端的例子，就是計(jì)數(shù)器，多個(gè)客戶端同時(shí)修改少量行，導(dǎo)致沖突嚴(yán)重的，造成大量的無(wú)效重試。

其他

到這里，我們已經(jīng)了解了 TiKV 的基本概念和一些細(xì)節(jié)，理解了這個(gè)分布式帶事務(wù)的 KV 引擎的分層結(jié)構(gòu)以及如何實(shí)現(xiàn)多副本容錯(cuò)。下一節(jié)會(huì)介紹如何在 KV 的存儲(chǔ)模型之上，構(gòu)建 SQL 層。