摘要：設(shè)計(jì)目標(biāo)作為的一個(gè)子項(xiàng)目，首要的設(shè)計(jì)目標(biāo)便是兼容。支持粒度的，并且支持多種，包括和等，目前默認(rèn)使用的是。和的設(shè)計(jì)有很大區(qū)別。未來(lái)的工作優(yōu)化我們通過(guò)測(cè)試發(fā)現(xiàn)，目前使用做范圍

作者：鄭志銓

Titan 是由 PingCAP 研發(fā)的一個(gè)基于 RocksDB 的高性能單機(jī) key-value 存儲(chǔ)引擎，其主要設(shè)計(jì)靈感來(lái)源于 USENIX FAST 2016 上發(fā)表的一篇論文 WiscKey。WiscKey 提出了一種高度基于 SSD 優(yōu)化的設(shè)計(jì)，利用 SSD 高效的隨機(jī)讀寫性能，通過(guò)將 value 分離出 LSM-tree 的方法來(lái)達(dá)到降低寫放大的目的。

我們的基準(zhǔn)測(cè)試結(jié)果顯示，當(dāng) value 較大的時(shí)候，Titan 在寫、更新和點(diǎn)讀等場(chǎng)景下性能都優(yōu)于 RocksDB。但是根據(jù) RUM Conjecture，通常某些方面的提升往往是以犧牲其他方面為代價(jià)而取得的。Titan 便是以犧牲硬盤空間和范圍查詢的性能為代價(jià)，來(lái)取得更高的寫性能。隨著 SSD 價(jià)格的降低，我們認(rèn)為這種取舍的意義會(huì)越來(lái)越明顯。

Titan 作為 TiKV 的一個(gè)子項(xiàng)目，首要的設(shè)計(jì)目標(biāo)便是兼容 RocksDB。因?yàn)?TiKV 使用 RocksDB 作為其底層的存儲(chǔ)引擎，而 TiKV 作為一個(gè)成熟項(xiàng)目已經(jīng)擁有龐大的用戶群體，所以我們需要考慮已有的用戶也可以將已有的基于 RocksDB 的 TiKV 平滑地升級(jí)到基于 Titan 的 TiKV。

因此，我們總結(jié)了四點(diǎn)主要的設(shè)計(jì)目標(biāo)：

支持將 value 從 LSM-tree 中分離出來(lái)多帶帶存儲(chǔ)，以降低寫放大。

已有 RocksDB 實(shí)例可以平滑地升級(jí)到 Titan，這意味著升級(jí)過(guò)程不需要人工干預(yù)，并且不會(huì)影響線上服務(wù)。

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

盡量減少對(duì) RocksDB 的侵入性改動(dòng)，保證 Titan 更加容易升級(jí)到新版本的 RocksDB。

Titan 的基本架構(gòu)如下圖所示：

圖 1：Titan 在 Flush 和 Compaction 的時(shí)候?qū)?value 分離出 LSM-tree，這樣做的好處是寫入流程可以和 RockDB 保持一致，減少對(duì) RocksDB 的侵入性改動(dòng)。

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

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

圖 2：BlobFile 主要由 blob record 、meta block、meta index block 和 footer 組成。其中每個(gè) blob record 用于存放一個(gè) key-value 對(duì)；meta block 支持可擴(kuò)展性，可以用來(lái)存放和 BlobFile 相關(guān)的一些屬性等；meta index block 用于檢索 meta block。

BlobFile 有幾點(diǎn)值得關(guān)注的地方：

BlobFile 中的 key-value 是有序存放的，目的是在實(shí)現(xiàn) Iterator 的時(shí)候可以通過(guò) prefetch 的方式提高順序讀取的性能。

每個(gè) blob record 都保留了 value 對(duì)應(yīng)的 user key 的拷貝，這樣做的目的是在進(jìn)行 GC 的時(shí)候，可以通過(guò)查詢 user key 是否更新來(lái)確定對(duì)應(yīng) value 是否已經(jīng)過(guò)期，但同時(shí)也帶來(lái)了一定的寫放大。

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

TitanTableBuilder 是實(shí)現(xiàn)分離 key-value 的關(guān)鍵。我們知道 RocksDB 支持使用用戶自定義 table builder 創(chuàng)建 SST，這使得我們可以不對(duì) build table 流程做侵入性的改動(dòng)就可以將 value 從 SST 中分離出來(lái)。下面將介紹 TitanTableBuilder 的主要工作流程：

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

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

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

在第一點(diǎn)的基礎(chǔ)上，保留 WAL 可以使 Titan 極大地減少對(duì) RocksDB 的侵入性改動(dòng)，而這也正是我們的設(shè)計(jì)目標(biāo)之一。

Titan 使用 Version 來(lái)代表某個(gè)時(shí)間點(diǎn)所有有效的 BlobFile，這是從 LevelDB 中借鑒過(guò)來(lái)的管理數(shù)據(jù)文件的方法，其核心思想便是 MVCC，好處是在新增或刪除文件的同時(shí)，可以做到并發(fā)讀取數(shù)據(jù)而不需要加鎖。每次新增文件或者刪除文件的時(shí)候，Titan 都會(huì)生成一個(gè)新的 Version ，并且每次讀取數(shù)據(jù)之前都要獲取一個(gè)最新的 Version。

圖 4：新舊 Version 按順序首尾相連組成一個(gè)雙向鏈表，VersionSet 用來(lái)管理所有的 Version，它持有一個(gè) current 指針用來(lái)指向當(dāng)前最新的 Version。

Garbage Collection (GC) 的目的是回收空間，一個(gè)高效的 GC 算法應(yīng)該在權(quán)衡寫放大和空間放大的同時(shí)，用最少的周期來(lái)回收最多的空間。在設(shè)計(jì) GC 的時(shí)候有兩個(gè)主要的問(wèn)題需要考慮：

何時(shí)進(jìn)行 GC

挑選哪些文件進(jìn)行 GC

Titan 使用 RocksDB 提供的兩個(gè)特性來(lái)解決這兩個(gè)問(wèn)題，這兩個(gè)特性分別是 TablePropertiesCollector 和 EventListener 。下面將講解我們是如何通過(guò)這兩個(gè)特性來(lái)輔助 GC 工作的。

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

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

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

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

Titan 會(huì)為每個(gè)有效的 BlobFile 在內(nèi)存中維護(hù)一個(gè) discardable size 變量，每次 Compaction 結(jié)束之后都對(duì)相應(yīng)的 BlobFile 的 discardable size 變量進(jìn)行累加。每次 GC 開始時(shí)就可以通過(guò)挑選 discardable size 最大的 BlobFile 來(lái)作為作為候選的文件。

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

我們使用 go-ycsb 測(cè)試了 TiKV 在 Txn Mode 下分別使用 RocksDB 和 Titan 的性能表現(xiàn)，本節(jié)我會(huì)簡(jiǎn)要說(shuō)明下我們的測(cè)試方法和測(cè)試結(jié)果。由于篇幅的原因，我們只挑選兩個(gè)典型的 value size 做說(shuō)明，更詳細(xì)的測(cè)試分析報(bào)告將會(huì)放在下一篇文章。

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

Memory：128GB（我們通過(guò) Cgroup 限制 TiKV 進(jìn)程使用內(nèi)存不超過(guò) 32GB）

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

數(shù)據(jù)集選定的基本原則是原始數(shù)據(jù)大?。ú凰闵蠈懛糯笠蛩兀┮瓤捎脙?nèi)存大，這樣可以防止所有數(shù)據(jù)被緩存到內(nèi)存中，減少 Cache 所帶來(lái)的影響。這里我們選用的數(shù)據(jù)集大小是 64GB，進(jìn)程的內(nèi)存使用限制是 32GB。

我們主要測(cè)試 5 個(gè)常用的場(chǎng)景：

Data Loading Performance：使用預(yù)先計(jì)算好的 key 數(shù)量和固定的 value 大小，以一定的速度并發(fā)寫入。

Update Performance：由于 Titan 在純寫入場(chǎng)景下不需要 GC（BlobFile 中沒(méi)有可丟棄數(shù)據(jù)），因此我們還需要通過(guò)更新來(lái)測(cè)試 GC 對(duì)性能的影響。

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

Random Key Lookup Performance：這一步主要測(cè)試點(diǎn)查性能，并且點(diǎn)查次數(shù)要遠(yuǎn)遠(yuǎn)大于 key 的數(shù)量。

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

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

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

圖 9 Output Size：Titan 的空間放大相比 RocksDB 略高，這種差距會(huì)隨著 Key 數(shù)量的減少有略微的縮小，這主要是因?yàn)?BlobFile 中需要存儲(chǔ) Key 而造成的寫放大。

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

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

本次測(cè)試我們對(duì)比了兩個(gè)具有代表性的 value size 在 5 種不同場(chǎng)景下的性能差異，更多不同粒度的 value size 的測(cè)試和更詳細(xì)的性能報(bào)告我們會(huì)放在下一篇文章去說(shuō)明，并且我們會(huì)從更多的角度（例如 CPU 和內(nèi)存的使用率等）去分析 Titan 和 RocksDB 的差異。從本次測(cè)試我們可以大致得出結(jié)論，在大 value 的場(chǎng)景下，Titan 會(huì)比 RocksDB 擁有更好的寫、更新和點(diǎn)讀性能。同時(shí)，Titan 的范圍查詢性能和空間放大都遜于 RocksDB 。

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

Merge

SingleDelete

除了 Open 接口以外，其他 API 的參數(shù)和返回值都和 RocksDB 一致。已有的項(xiàng)目只需要很小的改動(dòng)即可以將 RocksDB 實(shí)例平滑地升級(jí)到 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 來(lái)作為絕大多數(shù) API 的返回值，使用者可以通過(guò)它檢查執(zhí)行結(jié)果是否成功，也可以通過(guò)它打印錯(cuò)誤信息：

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 中是默認(rèn)關(guān)閉的，我們通過(guò) TiKV 的配置文件來(lái)決定是否開啟和設(shè)置 Titan，相關(guān)的配置項(xiàng)包括 [rocksdb.titan] 和 [rocksdb.defaultcf.titan]， 開啟 Titan 只需要進(jìn)行如下配置即可：

[rocksdb.titan]
enabled = true

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

我們通過(guò)測(cè)試發(fā)現(xiàn)，目前使用 Titan 做范圍查詢時(shí) IO Util 很低，這也是為什么其性能會(huì)比 RocksDB 差的重要原因之一。因此我們認(rèn)為 Titan 的 Iterator 還存在著巨大的優(yōu)化空間，最簡(jiǎn)單的方法是可以通過(guò)更加激進(jìn)的 prefetch 和并行 prefetch 等手段來(lái)達(dá)到提升 Iterator 性能的目的。

通常來(lái)說(shuō)，GC 的速度太慢會(huì)導(dǎo)致空間放大嚴(yán)重，過(guò)快又會(huì)對(duì)服務(wù)的 QPS 和延時(shí)帶來(lái)影響。目前 Titan 支持自動(dòng) GC，雖然可以通過(guò)減小并發(fā)度和 batch size 來(lái)達(dá)到一定程度限制 GC 速度的目的，但是由于每個(gè) BlobFile 中的 blob record 數(shù)目不定，若 BlobFile 中的 blob record 過(guò)于密集，將其有效的 key 更新回 LSM-tree 時(shí)仍然可能堵塞業(yè)務(wù)的寫請(qǐng)求。為了達(dá)到更加精細(xì)化的控制 GC 速度的目的，后續(xù)我們將使用 Token Bucket 算法限制一段時(shí)間內(nèi) GC 能夠更新的 key 數(shù)量，以降低 GC 對(duì) QPS 和延時(shí)的影響，使服務(wù)更加穩(wěn)定。

另一方面，我們也正在研究自動(dòng)調(diào)節(jié) GC 速度的算法，這樣我們便可以，在服務(wù)高峰期的時(shí)候降低 GC 速度來(lái)提供更高的服務(wù)質(zhì)量；在服務(wù)低峰期的時(shí)候提高 GC 速度來(lái)加快空間的回收。

TiKV 在某些場(chǎng)景下僅需要判斷某個(gè) key 是否存在，而不需要讀取對(duì)應(yīng)的 value。通過(guò)提供一個(gè)這樣的 API 可以極大地提高性能，因?yàn)槲覀円呀?jīng)看到將 value 移出 LSM-tree 之后，LSM-tree 本身會(huì)變的非常小，以至于我們可以將更多地 index、filter 和 DataBlock 存放到內(nèi)存當(dāng)中去，這樣去檢索某個(gè) key 的時(shí)候可以做到只需要少量甚至不需要 IO 。