數(shù)據(jù)庫(kù)、操作系統(tǒng)和編譯器并稱(chē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ù)。

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

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

?

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

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

為了解決數(shù)據(jù)丟失問(wèn)題，我們可以把數(shù)據(jù)放在非易失存儲(chǔ)介質(zhì)（比如硬盤(pán)）中。改進(jìn)的方案是在磁盤(pán)上創(chuàng)建一個(gè)文件，收到一條數(shù)據(jù)，就在文件中 Append 一行。OK，我們現(xiàn)在有了一個(gè)能持久化存儲(chǔ)數(shù)據(jù)的方案。但是還不夠好，假設(shè)這塊磁盤(pán)出現(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ù)安全問(wèn)題，可以松一口氣了。But，做復(fù)制過(guò)程中是否能保證副本之間的一致性？也就是在保證數(shù)據(jù)不丟的前提下，還要保證數(shù)據(jù)不錯(cuò)。保證數(shù)據(jù)不丟不錯(cuò)只是一項(xiàng)最基本的要求，還有更多令人頭疼的問(wèn)題等待解決：

• 能否支持跨數(shù)據(jù)中心的容災(zāi)？

• 寫(xiě)入速度是否夠快？

• 數(shù)據(jù)保存下來(lái)后，是否方便讀取？

• 保存的數(shù)據(jù)如何修改？如何支持并發(fā)的修改？

• 如何原子地修改多條記錄？

這些問(wèn)題每一項(xiàng)都非常難，但是要做一個(gè)優(yōu)秀的數(shù)據(jù)存儲(chǔ)系統(tǒng)，必須要解決上述的每一個(gè)難題。

為了解決數(shù)據(jù)存儲(chǔ)問(wèn)題，我們開(kāi)發(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ì)問(wèn)了，這里講的存儲(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 中的任何概念，專(zhuān)注于討論如何實(shí)現(xiàn) TiKV 這樣一個(gè)高性能高可靠性的巨大的（分布式的） Map。

?

RocksDB

任何持久化的存儲(chǔ)引擎，數(shù)據(jù)終歸要保存在磁盤(pán)上，TiKV 也不例外。但是 TiKV 沒(méi)有選擇直接向磁盤(pán)上寫(xiě)數(shù)據(jù)，而是把數(shù)據(jù)保存在 RocksDB 中，具體的數(shù)據(jù)落地由 RocksDB 負(fù)責(zé)。這個(gè)選擇的原因是開(kāi)發(fā)一個(gè)單機(jī)存儲(chǔ)引擎工作量很大，特別是要做一個(gè)高性能的單機(jī)引擎，需要做各種細(xì)致的優(yōu)化，而 RocksDB 是一個(gè)非常優(yōu)秀的開(kāi)源的單機(jī)存儲(chǔ)引擎，可以滿(mǎn)足我們對(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ǔ)方案。俗話(huà)說(shuō)，萬(wàn)事開(kāi)頭難，然后中間難，最后結(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ù)制方案是可靠、高效并且能處理副本失效的情況。聽(tīng)上去比較難，但是好在我們有 Raft 協(xié)議。Raft 是一個(gè)一致性算法，它和 Paxos 等價(jià)，但是更加易于理解。這里[https://raft.github.io/raft.pdf]是 Raft 的論文，感興趣的可以看一下。本文只會(huì)對(duì) Raft 做一個(gè)簡(jiǎn)要的介紹，細(xì)節(jié)問(wèn)題可以參考論文。另外提一點(diǎn)，Raft 論文只是一個(gè)基本方案，嚴(yán)格按照論文實(shí)現(xiàn)，性能會(huì)很差，我們對(duì) Raft 協(xié)議的實(shí)現(xiàn)做了大量的優(yōu)化，具體的優(yōu)化細(xì)節(jié)可參考我司首席架構(gòu)師唐劉同學(xué)的這篇文章。

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

1. Leader 選舉

2. 成員變更

3. 日志復(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ǔ)在磁盤(pán)上；通過(guò) Raft，我們可以將數(shù)據(jù)復(fù)制到多臺(tái)機(jī)器上，以防單機(jī)失效。數(shù)據(jù)的寫(xiě)入是通過(guò) Raft 這一層的接口寫(xiě)入，而不是直接寫(xiě) 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è)左閉右開(kāi)區(qū)間來(lái)描述。

注意，這里的 Region 還是和 SQL 中的表沒(méi)什么關(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)上沒(méi)什么數(shù)據(jù)的情況）。同時(shí)為了保證上層客戶(hù)端能夠訪(fǎng)問(wèn)所需要的數(shù)據(jù)，我們的系統(tǒng)中也會(huì)有一個(gè)組件記錄 Region 在節(jié)點(diǎn)上面的分布情況，也就是通過(guò)任意一個(gè) Key 就能查詢(xún)到這個(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。所有的讀和寫(xiě)都是通過(guò) Leader 進(jìn)行，再由 Leader 復(fù)制給 Follower。?

大家理解了 Region 之后，應(yīng)該可以理解下面這張圖：

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

?

MVCC

很多數(shù)據(jù)庫(kù)都會(huì)實(shí)現(xiàn)多版本控制（MVCC），TiKV 也不例外。設(shè)想這樣的場(chǎng)景，兩個(gè) Client 同時(shí)去修改一個(gè) Key 的 Value，如果沒(méi)有 MVCC，就需要對(duì)數(shù)據(jù)上鎖，在分布式場(chǎng)景下，可能會(huì)帶來(lái)性能以及死鎖問(wèn)題。

TiKV 的 MVCC 實(shí)現(xiàn)是通過(guò)在 Key 后面添加 Version 來(lái)實(shí)現(xiàn)，簡(jiǎn)單來(lái)說(shuō)，沒(méi)有 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)用戶(hù)通過(guò)一個(gè) Key + Version 來(lái)獲取 Value 的時(shí)候，可以將 Key 和 Version 構(gòu)造出 MVCC 的 Key，也就是 Key-Version。然后可以直接 Seek(Key-Version)，定位到第一個(gè)大于等于這個(gè) Key-Version 的位置。

這里有一篇更詳細(xì)的文檔，可以進(jìn)一步閱讀。

?

事務(wù)

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

?

其他

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

轉(zhuǎn)載于:https://www.cnblogs.com/williamjie/p/10218764.html

總結(jié)

以上是生活随笔為你收集整理的三篇文章了解 TiDB 技术内幕——说存储的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。