RocksDB存儲引擎

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

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

RocksDB寫

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

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

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

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

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

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

RocksDB讀

相對B+樹數據結構的存儲引擎來說，RocksDB中的查詢操作會慢一些。

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

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

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

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

Raft日志同步

每一個Region及其副本構成一個Raft Group，其中的leader副本對外提供服務，可以讀寫。TiKV會將對數據的每個變更操作都轉化為一條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節點中有兩個RocksDB實例，存儲Raft日志的RocksDB Raft實例和存儲KV鍵值對數據的RocksDB KV實例。

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

1. Propose：TiKV將收到的SQL請求轉化為Raft日志；
2. Append：Leader副本將Raft日志持久化到本地的RocksDB Raft中（RocksDB寫）；
3. Replicate：Leader副本將Raft日志發送給其他TiKV節點上自己的Follower副本。Follower副本在收到Raft日志后，也要持久化到自己本地的RocksDB Raft中（Append）；
4. Committed：Follower副本在將收到的Raft日志持久化到自己的本地存儲后，會向Leader副本返回一個確認信息。當超過半數的副本（包括Leader副本在內）都完成Append后，Raft日志同步的狀態變為Committed；
5. Apply：Leader副本將Raft日志應用到本地的RocksDB KV中（RocksDB寫）。

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

注：Raft日志同步中的Committed狀態不代表上層事務的Commited狀態，也不等同于應用的Committed狀態。

References
【1】RocksDB原理及應用
【2】The Log-Structured Merge-Tree