摘要：設計目標作為的一個子項目，首要的設計目標便是兼容。支持粒度的，并且支持多種，包括和等，目前默認使用的是。和的設計有很大區別。未來的工作優化我們通過測試發現，目前使用做范圍

作者：鄭志銓

Titan 是由 PingCAP 研發的一個基于 RocksDB 的高性能單機 key-value 存儲引擎，其主要設計靈感來源于 USENIX FAST 2016 上發表的一篇論文 WiscKey。WiscKey 提出了一種高度基于 SSD 優化的設計，利用 SSD 高效的隨機讀寫性能，通過將 value 分離出 LSM-tree 的方法來達到降低寫放大的目的。

我們的基準測試結果顯示，當 value 較大的時候，Titan 在寫、更新和點讀等場景下性能都優于 RocksDB。但是根據 RUM Conjecture，通常某些方面的提升往往是以犧牲其他方面為代價而取得的。Titan 便是以犧牲硬盤空間和范圍查詢的性能為代價，來取得更高的寫性能。隨著 SSD 價格的降低，我們認為這種取舍的意義會越來越明顯。

Titan 作為 TiKV 的一個子項目，首要的設計目標便是兼容 RocksDB。因為 TiKV 使用 RocksDB 作為其底層的存儲引擎，而 TiKV 作為一個成熟項目已經擁有龐大的用戶群體，所以我們需要考慮已有的用戶也可以將已有的基于 RocksDB 的 TiKV 平滑地升級到基于 Titan 的 TiKV。

因此，我們總結了四點主要的設計目標：

支持將 value 從 LSM-tree 中分離出來多帶帶存儲，以降低寫放大。

已有 RocksDB 實例可以平滑地升級到 Titan，這意味著升級過程不需要人工干預，并且不會影響線上服務。

100% 兼容目前 TiKV 所使用的所有 RocksDB 的特性。

盡量減少對 RocksDB 的侵入性改動，保證 Titan 更加容易升級到新版本的 RocksDB。

Titan 的基本架構如下圖所示：

圖 1：Titan 在 Flush 和 Compaction 的時候將 value 分離出 LSM-tree，這樣做的好處是寫入流程可以和 RockDB 保持一致，減少對 RocksDB 的侵入性改動。

Titan 的核心組件主要包括：BlobFile、TitanTableBuilder、Version 和 GC，下面將逐一進行介紹。

BlobFile 是用來存放從 LSM-tree 中分離出來的 value 的文件，其格式如下圖所示：

圖 2：BlobFile 主要由 blob record 、meta block、meta index block 和 footer 組成。其中每個 blob record 用于存放一個 key-value 對；meta block 支持可擴展性，可以用來存放和 BlobFile 相關的一些屬性等；meta index block 用于檢索 meta block。

BlobFile 有幾點值得關注的地方：

BlobFile 中的 key-value 是有序存放的，目的是在實現 Iterator 的時候可以通過 prefetch 的方式提高順序讀取的性能。

每個 blob record 都保留了 value 對應的 user key 的拷貝，這樣做的目的是在進行 GC 的時候，可以通過查詢 user key 是否更新來確定對應 value 是否已經過期，但同時也帶來了一定的寫放大。

BlobFile 支持 blob record 粒度的 compression，并且支持多種 compression algorithm，包括 Snappy、LZ4 和 Zstd 等，目前 Titan 默認使用的 compression algorithm 是 LZ4 。

TitanTableBuilder 是實現分離 key-value 的關鍵。我們知道 RocksDB 支持使用用戶自定義 table builder 創建 SST，這使得我們可以不對 build table 流程做侵入性的改動就可以將 value 從 SST 中分離出來。下面將介紹 TitanTableBuilder 的主要工作流程：

圖 3：TitanTableBuilder 通過判斷 value size 的大小來決定是否將 value 分離到 BlobFile 中去。如果 value size 大于等于 min_blob_size 則將 value 分離到 BlobFile ，并生成 index 寫入 SST；如果 value size 小于 min_blob_size 則將 value 直接寫入 SST。

Titan 和 Badger 的設計有很大區別。Badger 直接將 WAL 改造成 VLog，這樣做的好處是減少一次 Flush 的開銷。而 Titan 不這么設計的主要原因有兩個：

假設 LSM-tree 的 max level 是 5，放大因子為 10，則 LSM-tree 總的寫放大大概為 1 + 1 + 10 + 10 + 10 + 10，其中 Flush 的寫放大是 1，其比值是 42 : 1，因此 Flush 的寫放大相比于整個 LSM-tree 的寫放大可以忽略不計。

在第一點的基礎上，保留 WAL 可以使 Titan 極大地減少對 RocksDB 的侵入性改動，而這也正是我們的設計目標之一。

Titan 使用 Version 來代表某個時間點所有有效的 BlobFile，這是從 LevelDB 中借鑒過來的管理數據文件的方法，其核心思想便是 MVCC，好處是在新增或刪除文件的同時，可以做到并發讀取數據而不需要加鎖。每次新增文件或者刪除文件的時候，Titan 都會生成一個新的 Version ，并且每次讀取數據之前都要獲取一個最新的 Version。

圖 4：新舊 Version 按順序首尾相連組成一個雙向鏈表，VersionSet 用來管理所有的 Version，它持有一個 current 指針用來指向當前最新的 Version。

Garbage Collection (GC) 的目的是回收空間，一個高效的 GC 算法應該在權衡寫放大和空間放大的同時，用最少的周期來回收最多的空間。在設計 GC 的時候有兩個主要的問題需要考慮：

何時進行 GC

挑選哪些文件進行 GC

Titan 使用 RocksDB 提供的兩個特性來解決這兩個問題，這兩個特性分別是 TablePropertiesCollector 和 EventListener 。下面將講解我們是如何通過這兩個特性來輔助 GC 工作的。

RocksDB 允許我們使用自定義的 TablePropertiesCollector 來搜集 SST 上的 properties 并寫入到對應文件中去。Titan 通過一個自定義的 TablePropertiesCollector —— BlobFileSizeCollector 來搜集每個 SST 中有多少數據是存放在哪些 BlobFile 上的，我們將它收集到的 properties 命名為 BlobFileSizeProperties，它的工作流程和數據格式如下圖所示：

圖 5：左邊 SST 中 Index 的格式為：第一列代表 BlobFile 的文件 ID，第二列代表 blob record 在 BlobFile 中的 offset，第三列代表 blob record 的 size。右邊 BlobFileSizeProperties 中的每一行代表一個 BlobFile 以及 SST 中有多少數據保存在這個 BlobFile 中，第一列代表 BlobFile 的文件 ID，第二列代表數據大小。

我們知道 RocksDB 是通過 Compaction 來丟棄舊版本數據以回收空間的，因此每次 Compaction 完成后 Titan 中的某些 BlobFile 中便可能有部分或全部數據過期。因此我們便可以通過監聽 Compaction 事件來觸發 GC，通過搜集比對 Compaction 中輸入輸出 SST 的 BlobFileSizeProperties 來決定挑選哪些 BlobFile 進行 GC。其流程大概如下圖所示：

圖 6：inputs 代表參與 Compaction 的所有 SST 的 BlobFileSizeProperties，outputs 代表 Compaction 生成的所有 SST 的 BlobFileSizeProperties，discardable size 是通過計算 inputs 和 outputs 得出的每個 BlobFile 被丟棄的數據大小，第一列代表 BlobFile 的文件 ID，第二列代表被丟棄的數據大小。

Titan 會為每個有效的 BlobFile 在內存中維護一個 discardable size 變量，每次 Compaction 結束之后都對相應的 BlobFile 的 discardable size 變量進行累加。每次 GC 開始時就可以通過挑選 discardable size 最大的 BlobFile 來作為作為候選的文件。

每次進行 GC 前我們都會挑選一系列 BlobFile 作為候選文件，挑選的方法如上一節所述。為了減小寫放大，我們可以容忍一定的空間放大，所以我們只有在 BlobFile 可丟棄的數據達到一定比例之后才會對其進行 GC。我們使用 Sample 算法來獲取每個候選文件中可丟棄數據的大致比例。Sample 算法的主要邏輯是隨機取 BlobFile 中的一段數據 A，計其大小為 a，然后遍歷 A 中的 key，累加過期的 key 所在的 blob record 的 size 計為 d，最后計算得出 d 占 a 比值 為 r，如果 r >= discardable_ratio 則對該 BlobFile 進行 GC，否則不對其進行 GC。上一節我們已經知道每個 BlobFile 都會在內存中維護一個 discardable size，如果這個 discardable size 占整個 BlobFile 數據大小的比值已經大于或等于 discardable_ratio 則不需要對其進行 Sample。

我們使用 go-ycsb 測試了 TiKV 在 Txn Mode 下分別使用 RocksDB 和 Titan 的性能表現，本節我會簡要說明下我們的測試方法和測試結果。由于篇幅的原因，我們只挑選兩個典型的 value size 做說明，更詳細的測試分析報告將會放在下一篇文章。

CPU：Intel(R) Xeon(R) CPU E5-2630 v4 @ 2.20GHz（40個核心）

Memory：128GB（我們通過 Cgroup 限制 TiKV 進程使用內存不超過 32GB）

Disk：SATA SSD 1.5TB（fio 測試：4KB block size 混合隨機讀寫情況下讀寫 IOPS 分別為 43.8K 和 18.7K）

數據集選定的基本原則是原始數據大小（不算上寫放大因素）要比可用內存大，這樣可以防止所有數據被緩存到內存中，減少 Cache 所帶來的影響。這里我們選用的數據集大小是 64GB，進程的內存使用限制是 32GB。

我們主要測試 5 個常用的場景：

Data Loading Performance：使用預先計算好的 key 數量和固定的 value 大小，以一定的速度并發寫入。

Update Performance：由于 Titan 在純寫入場景下不需要 GC（BlobFile 中沒有可丟棄數據），因此我們還需要通過更新來測試 GC 對性能的影響。

Output Size：這一步我們會測量更新場景完成后引擎所占用的硬盤空間大小，以此反映 GC 的空間回收效果。

Random Key Lookup Performance：這一步主要測試點查性能，并且點查次數要遠遠大于 key 的數量。

Sorted Range Iteration Performance：這一步主要測試范圍查詢的性能，每次查詢 2 million 個相連的 key。

圖 7 Data Loading Performance：Titan 在寫場景中的性能要比 RocksDB 高 70% 以上，并且隨著 value size 的變大，這種性能的差異會更加明顯。值得注意的是，數據在寫入 KV Engine 之前會先寫入 Raft Log，因此 Titan 的性能提升會被攤薄，實際上裸測 RocksDB 和 Titan 的話這種性能差異會更大。

圖 8 Update Performance：Titan 在更新場景中的性能要比 RocksDB 高 180% 以上，這主要得益于 Titan 優秀的讀性能和良好的 GC 算法。

圖 9 Output Size：Titan 的空間放大相比 RocksDB 略高，這種差距會隨著 Key 數量的減少有略微的縮小，這主要是因為 BlobFile 中需要存儲 Key 而造成的寫放大。

圖 10 Random Key Lookup： Titan 擁有比 RocksDB 更卓越的點讀性能，這主要得益與將 value 分離出 LSM-tree 的設計使得 LSM-tree 變得更小，因此 Titan 在使用同樣的內存量時可以將更多的 index 、filter 和 DataBlock 緩存到 Block Cache 中去。這使得點讀操作在大多數情況下僅需要一次 IO 即可（主要是用于從 BlobFile 中讀取數據）。

圖 11 Sorted Range Iteration：Titan 的范圍查詢性能目前和 RocksDB 相比還是有一定的差距，這也是我們未來優化的一個重要方向。

本次測試我們對比了兩個具有代表性的 value size 在 5 種不同場景下的性能差異，更多不同粒度的 value size 的測試和更詳細的性能報告我們會放在下一篇文章去說明，并且我們會從更多的角度（例如 CPU 和內存的使用率等）去分析 Titan 和 RocksDB 的差異。從本次測試我們可以大致得出結論，在大 value 的場景下，Titan 會比 RocksDB 擁有更好的寫、更新和點讀性能。同時，Titan 的范圍查詢性能和空間放大都遜于 RocksDB 。

一開始我們便將兼容 RocksDB 作為設計 Titan 的首要目標，因此我們保留了絕大部分 RocksDB 的 API。目前僅有兩個 API 是我們明確不支持的：

Merge

SingleDelete

除了 Open 接口以外，其他 API 的參數和返回值都和 RocksDB 一致。已有的項目只需要很小的改動即可以將 RocksDB 實例平滑地升級到 Titan。值得注意的是 Titan 并不支持回退回 RocksDB。

#include 
#include "rocksdb/utilities/titandb/db.h"

// Open DB
rocksdb::titandb::TitanDB* db;
rocksdb::titandb::TitanOptions options;
options.create_if_missing = true;
rocksdb::Status status =
  rocksdb::titandb::TitanDB::Open(options, "/tmp/testdb", &db);
assert(status.ok());
...

或

#include 
#include "rocksdb/utilities/titandb/db.h"

// open DB with two column families
rocksdb::titandb::TitanDB* db;
std::vector column_families;
// have to open default column family
column_families.push_back(rocksdb::titandb::TitanCFDescriptor(
    kDefaultColumnFamilyName, rocksdb::titandb::TitanCFOptions()));
// open the new one, too
column_families.push_back(rocksdb::titandb::TitanCFDescriptor(
    "new_cf", rocksdb::titandb::TitanCFOptions()));
std::vector handles;
s = rocksdb::titandb::TitanDB::Open(rocksdb::titandb::TitanDBOptions(), kDBPath,
                                    column_families, &handles, &db);
assert(s.ok());

和 RocksDB 一樣，Titan 使用 rocksdb::Status 來作為絕大多數 API 的返回值，使用者可以通過它檢查執行結果是否成功，也可以通過它打印錯誤信息：

rocksdb::Status s = ...;
if (!s.ok()) cerr << s.ToString() << endl;

std::string value;
rocksdb::Status s = db->Get(rocksdb::ReadOptions(), key1, &value);
if (s.ok()) s = db->Put(rocksdb::WriteOptions(), key2, value);
if (s.ok()) s = db->Delete(rocksdb::WriteOptions(), key1);

目前 Titan 在 TiKV 中是默認關閉的，我們通過 TiKV 的配置文件來決定是否開啟和設置 Titan，相關的配置項包括 [rocksdb.titan] 和 [rocksdb.defaultcf.titan]， 開啟 Titan 只需要進行如下配置即可：

[rocksdb.titan]
enabled = true

注意一旦開啟 Titan 就不能回退回 RocksDB 了。

我們通過測試發現，目前使用 Titan 做范圍查詢時 IO Util 很低，這也是為什么其性能會比 RocksDB 差的重要原因之一。因此我們認為 Titan 的 Iterator 還存在著巨大的優化空間，最簡單的方法是可以通過更加激進的 prefetch 和并行 prefetch 等手段來達到提升 Iterator 性能的目的。

通常來說，GC 的速度太慢會導致空間放大嚴重，過快又會對服務的 QPS 和延時帶來影響。目前 Titan 支持自動 GC，雖然可以通過減小并發度和 batch size 來達到一定程度限制 GC 速度的目的，但是由于每個 BlobFile 中的 blob record 數目不定，若 BlobFile 中的 blob record 過于密集，將其有效的 key 更新回 LSM-tree 時仍然可能堵塞業務的寫請求。為了達到更加精細化的控制 GC 速度的目的，后續我們將使用 Token Bucket 算法限制一段時間內 GC 能夠更新的 key 數量，以降低 GC 對 QPS 和延時的影響，使服務更加穩定。

另一方面，我們也正在研究自動調節 GC 速度的算法，這樣我們便可以，在服務高峰期的時候降低 GC 速度來提供更高的服務質量；在服務低峰期的時候提高 GC 速度來加快空間的回收。

TiKV 在某些場景下僅需要判斷某個 key 是否存在，而不需要讀取對應的 value。通過提供一個這樣的 API 可以極大地提高性能，因為我們已經看到將 value 移出 LSM-tree 之后，LSM-tree 本身會變的非常小，以至于我們可以將更多地 index、filter 和 DataBlock 存放到內存當中去，這樣去檢索某個 key 的時候可以做到只需要少量甚至不需要 IO 。