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

很多人用過(guò)數(shù)據(jù)庫(kù)，但是很少有人實(shí)現(xiàn)過(guò)一個(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é)都看過(guò)這兩個(gè)項(xiàng)目的代碼。但是分布式數(shù)據(jù)庫(kù)方面，好的開源項(xiàng)目并不多。 TiDB 目前獲得了廣泛的關(guān)注，特別是一些技術(shù)愛好者，希望能夠參與這個(gè)項(xiàng)目。由于分布式數(shù)據(jù)庫(kù)自身的復(fù)雜性，很多人并不能很好的理解整個(gè)項(xiàng)目，所以我們希望能通過(guò)一系列文章，自頂向上，由淺入深，講述 TiDB 的一些技術(shù)原理，包括用戶可見的技術(shù)以及大量隱藏在 SQL 界面后用戶不可見的技術(shù)點(diǎn)。

本文為本系列文章第一篇。

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

[[192995]]

數(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ǔ)，或者是通過(guò)硬件或者軟件進(jìn)行存儲(chǔ)復(fù)制。到這里似乎我們已經(jīng)解決了數(shù)據(jù)安全問題，可以松一口氣了。But，做復(fù)制過(guò)程中是否能保證副本之間的一致性?也就是在保證數(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)：

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

2. 這個(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à)，但是更加易于理解。這里[https://raft.github.io/raft.pdf]是 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)化。

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

• Leader 選舉
• 成員變更
• 日志復(fù)制

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

到這里我們總結(jié)一下，通過(guò)單機(jī)的 RocksDB，我們可以將數(shù)據(jù)快速地存儲(chǔ)在磁盤上;通過(guò) Raft，我們可以將數(shù)據(jù)復(fù)制到多臺(tái)機(jī)器上，以防單機(jī)失效。數(shù)據(jù)的寫入是通過(guò) Raft 這一層的接口寫入，而不是直接寫 RocksDB。通過(guò)實(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ù)不超過(guò)一定的大小(這個(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)度過(guò)來(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)上面的分布情況，也就是通過(guò)任意一個(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。Repica 之間是通過(guò) 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。所有的讀和寫都是通過(guò) 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)是通過(guò)在 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é)我們介紹過(guò)的 Key 是有序的排列)，這樣當(dāng)用戶通過(guò)一個(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 【https://research.google.com/pubs/pub36726.html】模型，并且做了大量的優(yōu)化。事務(wù)的細(xì)節(jié)這里不詳述，大家可以參考論文以及我們的其他文章。這里只提一點(diǎn)，TiKV 的事務(wù)采用樂觀鎖，事務(wù)的執(zhí)行過(guò)程中，不會(huì)檢測(cè)寫沖突，只有在提交過(guò)程中，才會(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ò)。

【本文是51CTO專欄機(jī)構(gòu)“PingCAP”的原創(chuàng)文章，轉(zhuǎn)載請(qǐng)聯(lián)系作者本人獲取授權(quán)】

戳這里，看該作者更多好文