RocksDB存儲引擎

TiDB所使用的RocksDB是LSM類儲存引擎之一。日志結(jié)構(gòu)合并樹（Log Structured Merge Tree, LSM Tree）類存儲引擎的特點是寫入的時候是追加寫入（append only）。無論是INSERT、UPDATE、DELETE操作，都會被轉(zhuǎn)化為追加寫入操作。

基于這種特性，LSM Tree類存儲引擎的寫入速度很快，但是讀取速度慢，且寫放大和讀放大現(xiàn)象比較突出。

RocksDB寫

RocksDB寫入遵循“日志寫先行”的規(guī)則，即先將WAL日志（Write-Ahead Log）落盤，再把數(shù)據(jù)寫入內(nèi)存中的MemTable，以防止宕機(jī)時丟失數(shù)據(jù)。

RocksDB寫可以分為以下幾個步驟：

1. 將WAL日志寫入磁盤（sync_log=True）；
2. 將數(shù)據(jù)追加寫入內(nèi)存中的MemTable。如果是刪除（或修改）數(shù)據(jù)的操作，則在MemTable中寫入一條刪除（或修改）標(biāo)記，而不用去訪問實際的數(shù)據(jù)，從而大大提高寫的速度；
3. 當(dāng)MemTable的大小達(dá)到write_buffer_size的大小（典型值是64KB）時，當(dāng)前的MemTable被轉(zhuǎn)存為內(nèi)存中的一個immutable MemTable。同時，內(nèi)存中會開辟出一塊新的區(qū)域作為新的MemTable，供新的數(shù)據(jù)寫入；
4. 后臺有專門的進(jìn)程將immutable MemTable刷到磁盤。如果immutable MemTable刷盤的速度明顯慢于MemTable寫入的速度，導(dǎo)致等待落盤的immutable MemTable積壓達(dá)到了5個，會產(chǎn)生Write Stall現(xiàn)象，即TiDB會限制寫入MemTable的速度；
5. 當(dāng)數(shù)據(jù)成功落盤后，對應(yīng)的WAL日志就可以被覆蓋寫了（即WAL日志是循環(huán)寫）。

注：如果沒有immutable MemTable，而是直接將MemTable寫入磁盤，落盤的過程中可能會造成寫阻塞。

RocksDB寫入磁盤的數(shù)據(jù)是分level層次保存的SSTable。Level級數(shù)越小，表示處于該level的SSTable越新。同一level的數(shù)據(jù)量超出一定大小后會進(jìn)行合并壓縮，并被轉(zhuǎn)化為下一層級，這一過程稱為Compaction。在Compaction的過程中會對數(shù)據(jù)進(jìn)行去重、排序。

1. immutable MemTable落盤后存儲在Level 0層級的SSTable；
2. 當(dāng)Level 0的SSTable數(shù)目達(dá)到4個時，該層的SSTable開始向Level 1做Compaction，被壓縮合并為Level 1的一個SSTable，并在此過程中對其中所有的Key進(jìn)行排序；
3. 當(dāng)Level 1的所有SSTable中的總數(shù)據(jù)量達(dá)到256M時，該層的SSTable開始向Level 2做Compaction，被壓縮合并為Level 2的一個SSTable，并在此過程中對其中所有的Key進(jìn)行排序；
4. 當(dāng)Level 2的所有SSTable中的總數(shù)據(jù)量達(dá)到2.5GB時，該層的SSTable開始向Level 3做Compaction，被壓縮合并為Level 3的一個SSTable，并在此過程中對其中所有的Key進(jìn)行排序；
5. 當(dāng)Level 3的所有SSTable中的總數(shù)據(jù)量達(dá)到25GB時，該層的SSTable開始向Level 4做Compaction，被壓縮合并為Level 4的一個SSTable，并在此過程中對其中所有的Key進(jìn)行排序；
6. 當(dāng)Level 4的所有SSTable中的總數(shù)據(jù)量達(dá)到250GB時，該層的SSTable開始向Level 5做Compaction。如此類推，不斷向下面的Level推進(jìn)。

RocksDB讀

相對B+樹數(shù)據(jù)結(jié)構(gòu)的存儲引擎來說，RocksDB中的查詢操作會慢一些。

RocksDB的內(nèi)存中有一個叫做Block Cache的內(nèi)存區(qū)域，緩存著最近最常被訪問的數(shù)據(jù)。在讀數(shù)據(jù)時，會先訪問Block Cache，如果在Block Cache中找到了要讀取的數(shù)據(jù)，這種情況就被稱為Block Cache命中。

RocksDB讀可以分為以下幾個步驟：

1. 在Block Cache中查詢要讀取的數(shù)據(jù)；
2. 如果Block Cache未命中，則到MemTable中查詢；
3. 如果在MemTable中沒有讀到數(shù)據(jù)，則到immutable MemTable中查詢；
4. 如果所有immutable MemTable中都沒有讀到數(shù)據(jù)，則到磁盤的Level 0中按SSTable從新到舊的順序查詢；
5. 如果Level 0中沒有讀到數(shù)據(jù)，則到磁盤的Level 1中按SSTable從新到舊的順序查詢；
6. 如此遞歸向下，直到讀到目標(biāo)的Key。由于上層Level的數(shù)據(jù)肯定比下層Level的數(shù)據(jù)新，我們只要讀第一次找到的Key就行。

注：由于從Level 1開始，SSTable中的數(shù)據(jù)是按Key排好序的，我們只需要看一個SSTable中的最小的Key和最大的Key，就可以判斷想要查詢的目標(biāo)Key是否位于該SSTable中。如果目標(biāo)Key位于該SSTable中，就可以通過二分查找法、BloomFilter等算法來查找。

Raft日志同步

每一個Region及其副本構(gòu)成一個Raft Group，其中的leader副本對外提供服務(wù)，可以讀寫。TiKV會將對數(shù)據(jù)的每個變更操作都轉(zhuǎn)化為一條Raft Log，并將Raft日志從leader副本同步到follower副本。

Raft log格式的簡單示例如下：

#Region編號_日志編號,log{操作類型 key=鍵值,value=變更}
4_1,log{PUT key=1,name='Tom'}
4_2,log{PUT key=2,name='Adny'}
4_3,log{PUT key=1,name='Jack'}
...
4_N,log{DEL key=3}

每個TiKV節(jié)點中有兩個RocksDB實例，存儲Raft日志的RocksDB Raft實例和存儲KV鍵值對數(shù)據(jù)的RocksDB KV實例。

Raft日志同步可以分為以下幾個步驟：

1. Propose：TiKV將收到的SQL請求轉(zhuǎn)化為Raft日志；
2. Append：Leader副本將Raft日志持久化到本地的RocksDB Raft中（RocksDB寫）；
3. Replicate：Leader副本將Raft日志發(fā)送給其他TiKV節(jié)點上自己的Follower副本。Follower副本在收到Raft日志后，也要持久化到自己本地的RocksDB Raft中（Append）；
4. Committed：Follower副本在將收到的Raft日志持久化到自己的本地存儲后，會向Leader副本返回一個確認(rèn)信息。當(dāng)超過半數(shù)的副本（包括Leader副本在內(nèi)）都完成Append后，Raft日志同步的狀態(tài)變?yōu)镃ommitted；
5. Apply：Leader副本將Raft日志應(yīng)用到本地的RocksDB KV中（RocksDB寫）。

最后的Apply步驟中，不保證Follower副本也已經(jīng)將Raft日志應(yīng)用到本地的RocksDB KV中。

注：Raft日志同步中的Committed狀態(tài)不代表上層事務(wù)的Commited狀態(tài)，也不等同于應(yīng)用的Committed狀態(tài)。

References
【1】RocksDB原理及應(yīng)用
【2】The Log-Structured Merge-Tree