Titan 是 pingcap 開源的一個(gè)基于 RocksDB 的 存儲(chǔ)引擎瘪菌，以插件的形式提供下面，通過 key value 分離降低在 compaction 過程中的寫放大枚碗。整個(gè)項(xiàng)目是受 WiscKey 的啟發(fā)舟扎。本文主要討論 Titan 在 RocksDB 基礎(chǔ)之上寫入和查詢機(jī)制粮呢，基于 Titan 代碼版本為 54a20a5@master伍玖。

Titan 架構(gòu)圖

Blob File

與 RocksDB 一樣，Titan 在進(jìn)行數(shù)據(jù)寫入時(shí)依然是先寫入 WAL 日志睛挚，然后寫入到 memtable 中邪蛔。在一定條件下，memtable 是可以支持多線程并發(fā)寫入的扎狱。在 memtable 執(zhí)行 flush 操作過程中侧到，與 RocksDB 不同的是，Titan 會(huì)挑選大小超過 4KB 的 value 通過 BlobFileBuilder 生成 blob file 中以實(shí)現(xiàn) kv 分離淤击。

Blob FIle Layout

blob file 的 layout 如圖所示匠抗，包括定長(zhǎng)的 header、若干 blob record污抬、若干 meta block 和 1 個(gè) meta block index汞贸，以及定長(zhǎng)的 footer。

blob file layout

• header 保存了 magic number 和 version 字段印机，以及一個(gè)目前只在 version 2 才有的 flags 字段矢腻，flags 目前保存的是解壓字典標(biāo)志位；
• record 則是實(shí)際的用戶數(shù)據(jù)射赛，是一個(gè)變長(zhǎng)的結(jié)構(gòu)多柑。blob file 中的 record 在寫入時(shí)按照 key 順序進(jìn)行存儲(chǔ)，以提高順序讀取能力楣责；
• meta block 屬于可選項(xiàng)竣灌，目前只有存儲(chǔ)解壓字典的類型聂沙。相應(yīng)的 meta block index 則存儲(chǔ) meta block 的索引信息；
• footer 中存儲(chǔ) meta index block 的索引信息初嘹。

可以看到及汉，由于 blob file 本身無需直接支持檢索，blob file 中并未存儲(chǔ)訪問 record 的索引信息削樊。blob file 的訪問是通過存儲(chǔ)在 LSM-tree 中的 blob index 來完成豁生，blob index 包括 record 所在的 blob file 文件名、文件偏移量和數(shù)據(jù)大小漫贞。record 中額外存儲(chǔ)了相應(yīng)的 key 信息甸箱，是為了通過 record 中的 key 可以快速查詢到 LSM-tree 中存儲(chǔ)的相應(yīng) blob index，從而便于通過比對(duì) blob index 和 record 的內(nèi)容進(jìn)行 GC 等操作迅脐。

數(shù)據(jù)寫入

BlobFileBuilder

在 flush 過程中芍殖，Titan 進(jìn)行 blob file 的構(gòu)建。flush 是指將 LSM-tree 的 memtable 數(shù)據(jù)刷入到 Level 0 的 SST 文件的過程谴蔑，可以由用戶調(diào)用 DB::Flush() 手動(dòng)觸發(fā)豌骏，也可以由于 WAL 或 memtable 的大小超過閾值觸發(fā)。利用 RocksDB 高度擴(kuò)展性隐锭，Titan 實(shí)現(xiàn)了 rocksdb::TableBuilder 虛基類窃躲，通過重載其工廠函數(shù)實(shí)現(xiàn)自定義 rocksdb::titandb::TitanTableBuilder 的注入。Titan 在 flush 過程中钦睡，選取 value.size() 超過閾值的 value 以 blob record 的形式寫入到 blob file 中蒂窒，該閾值可以通過
TitanCFOptions.min_blob_size 進(jìn)行設(shè)置，默認(rèn)為4096荞怒。同時(shí)洒琢，Titan 會(huì)在 LSM-tree 的對(duì)應(yīng) value 中記錄 record 的訪問 blob index，以實(shí)現(xiàn)對(duì) blob file 中數(shù)據(jù)的查詢褐桌。對(duì)于大小小于閾值的 value衰抑，退化成普通的 RocksDB flush 流程，直接存儲(chǔ) key 和 value荧嵌。

數(shù)據(jù)查詢

數(shù)據(jù)結(jié)構(gòu)

UML類圖

• BlobFileSet 是管理和訪問 blob file 的入口呛踊，通過 BlobStorage 以 column family 為單位進(jìn)行管理；
• BlobStorage 管理一個(gè) column family 對(duì)應(yīng)的 blob 文件啦撮，包括打開的文件的元信息以及打開的 blob file 的文件 BlobFileCache谭网；
• BlobFileCache 通過 file cache 管理打開的 blob file 文件，BlobFileCache 中的 file cache 指針與 BlobFileSet 中的 file cache 指針指向相同的對(duì)象逻族。cache 的 key 是 file number，這是一個(gè)在構(gòu)建 blob file 時(shí)生成的唯一序號(hào)骄崩。cache 的 value 則是用于讀取 blob 文件的 BlobFileReader聘鳞。在查詢 cache 時(shí)薄辅，如果發(fā)現(xiàn) cache 中找不到需要的 key，則構(gòu)建一個(gè)對(duì)應(yīng)文件的 BlobFileReader抠璃；
• BlobFileReader 執(zhí)行實(shí)際的 blob file 讀取操作站楚。在創(chuàng)建 Titan 實(shí)例時(shí)配置 blob cache，可發(fā)揮與 RocksDB 的 block cache 類似的作用搏嗡。cache 的 key 由 blob 文件信息和 handle offset 兩部分編碼而成窿春，后者對(duì)應(yīng) blob record 在文件中存儲(chǔ)的偏移量。

執(zhí)行流程

數(shù)據(jù)查詢的執(zhí)行流程

數(shù)據(jù)讀取先查詢 LSM-tree 中的 key 對(duì)應(yīng)的 value采盒，對(duì)于 blob index 類型的 value旧乞，根據(jù) blob index 的索引信息檢索 blob file 中的 blob record 進(jìn)而得到返回的數(shù)據(jù)；對(duì)于普通的 value磅氨，則可直接返回尺栖。

點(diǎn)查詢

點(diǎn)查詢?cè)诖颂幨侵刚{(diào)用 Get() 接口，一次獲取一個(gè) key 對(duì)應(yīng)的 value 的查詢烦租。 盡管如此延赌，由于 LSM-tree 中只存儲(chǔ)較小的鍵值對(duì)，在同等內(nèi)存容量下的 Titan 可以緩存更多的索引叉橱、布隆過濾器和 block挫以。盡管在 RocksDB 的讀取流程基礎(chǔ)上，Titan 對(duì)于 blob record 額外增加了一次 blob file 的讀取窃祝。但由于更優(yōu)的緩存掐松，Titan 大部分點(diǎn)查詢 和 RocksDB 的查詢一樣，只需要一次 IO锌杀。不僅如此甩栈，由于更低的 LSM-tree 層級(jí)以及更小的數(shù)據(jù) block，Titan 擁有更小的讀放大糕再，點(diǎn)查詢性能相對(duì)于 RocksDB 有顯著提升量没。

范圍查詢

為了提升范圍查詢能力，blob record 按照 key 字典順序進(jìn)行存儲(chǔ)突想。同時(shí)殴蹄，充分利用操作系統(tǒng)的 page cache 機(jī)制，通過 readahead() 系統(tǒng)調(diào)用將文件內(nèi)容提前緩存到操作系統(tǒng)中猾担，避免執(zhí)行實(shí)際操作時(shí)才進(jìn)行 IO 造成較大延時(shí)袭灯。盡管如此，Titan 的范圍查詢性能依然顯著低于 RocksDB绑嘹。需要指出的是稽荧，Wisckey 論文中有提到利用 SSD 的并行特性來優(yōu)化范圍查詢性能，通過線程池并行預(yù)取數(shù)據(jù)到內(nèi)存中工腋，在 value 較大的場(chǎng)景下可以得到近似于 LevelDB 的性能姨丈。

參考文獻(xiàn)

WiscKey: Separating Keys from Values in SSD-Conscious Storage
Titan Overview
RocksDB Wiki