SpanDB: A Fast, Cost-Effective LSM-tree Based KV Store on Hybrid Storage 主要探討了當(dāng)前新的 NVMe SSD 等快速設(shè)備情況下，基于 LSM-tree 的 KV 存儲(chǔ)（以 RocksDB 為例）的性能優(yōu)化問(wèn)題。

背景

最新的 SATA Revision 3.4 理論帶寬上限為 6Gbps，目前的 NVMe SSD 順序讀性能可以輕松超過(guò) 2GBps。隨著 SSD 技術(shù)的發(fā)展，現(xiàn)有的基于慢速磁盤(pán)設(shè)備的存儲(chǔ)引擎設(shè)計(jì)需進(jìn)行相應(yīng)的改進(jìn)。
在慢速設(shè)備的時(shí)代，我們通常使用多線程技術(shù)，采用遠(yuǎn)多于 CPU 核心數(shù)的線程數(shù)量，盡可能避免慢速設(shè)備造成的較長(zhǎng)時(shí)間的等待。進(jìn)入 NVMe SSD 時(shí)代，在 SPDK 技術(shù)加持下，線程間的同步可能比 IO 本身更耗時(shí)。在這種情形下，傳統(tǒng)的多線程 IO 技術(shù)在 IO 吞吐量、延遲和 CPU 資源利用上都不具備優(yōu)勢(shì)。

ext4 VS SPDK

上圖是 Intel Optane P4800X 分別通過(guò) ext4 和 SPDK 進(jìn)行讀寫(xiě)的對(duì)比測(cè)試，RR、SR、SW 分別代表隨機(jī)讀、順序讀和順序?qū)??？梢钥吹?，在大批量的順序讀場(chǎng)景下，兩者性能相當(dāng)。其余場(chǎng)景 SPDK 性能，尤其是寫(xiě)性能均顯著優(yōu)異于 ext4。

Intel P4610 (N) VS Intel Optane (O)

上圖是對(duì) SATA SSD 和 NVMe SSD P4800X 的對(duì)比 4KB 順序?qū)懭霚y(cè)試，N 代表 I SATA SSD Intel P4610，O 代表 NVMe SSD Intel Optane P4800X，1-N 代表 1 個(gè)線程寫(xiě)入 Intel P4610，CR=2 代表每個(gè)線程發(fā)起 2 個(gè)寫(xiě)請(qǐng)求?？梢钥吹?，NVMe SSD 可以提供更高的并發(fā)能力，多線程下的表現(xiàn)更好。實(shí)際上，即便是 NVMe SSD，超過(guò) 3 個(gè)寫(xiě)入線程并不會(huì)帶來(lái) IOPS 的提升。

架構(gòu)概覽

在現(xiàn)有的 LSM-tree 存儲(chǔ)引擎的基礎(chǔ)之上，針對(duì) NVMe SSD 的特性做了以下幾點(diǎn)優(yōu)化：

• 層次化的存儲(chǔ)結(jié)構(gòu)， NVMe SSD 作為 SD(Speed Disk)，SATA SSD 作為 CD(Capacity Disk)。
• 基于 SPDK 技術(shù)，結(jié)合 polling IO 模式的異步 IO 請(qǐng)求處理，實(shí)現(xiàn)對(duì) SD 高效讀寫(xiě)。
• 并行 WAL 寫(xiě)入。
• WAL 和頂部 level 數(shù)據(jù)存儲(chǔ)在 SD。并根據(jù) SD-CD 負(fù)載情況，動(dòng)態(tài)分布 level 數(shù)據(jù)。

異步請(qǐng)求處理

Asynchronous Request Processing Workflow

如圖所示，在一臺(tái)具有 n 個(gè) CPU 核心的機(jī)器上。基于每個(gè)線程占用一個(gè) CPU 核心的原則，用戶將客戶端線程數(shù)配置為 N_client，內(nèi)部線程數(shù)為 n - N_cllient。內(nèi)部線程被劃分為 logger 和 worker 兩種角色，一個(gè)名叫 head-server thread 的管理線程會(huì)根據(jù)寫(xiě)入強(qiáng)度動(dòng)態(tài)調(diào)整不同角色的內(nèi)部線程數(shù)量。
為實(shí)現(xiàn)異步請(qǐng)求處理，在 RocksDB 已有的 flush 隊(duì)列 Q_flush 和 compact 隊(duì)列 Q_compact 基礎(chǔ)上，SpanDB 引入了1個(gè)讀取隊(duì)列 Q_read 和3個(gè)用于寫(xiě)入的隊(duì)列 Q_ProLog、Q_Log 和 Q_EpiLog。

讀請(qǐng)求

client 線程會(huì)首先嘗試進(jìn)行 memtable 讀取，如命中則可直接獲取返回結(jié)果。如未命中，則將讀取請(qǐng)求放入到 Q_read 中，隨后通過(guò)獲取請(qǐng)求狀態(tài)接口獲取結(jié)果。worker 線程會(huì)隨后讀取并執(zhí)行 Q_read 中的讀請(qǐng)求，并設(shè)置讀取結(jié)果。

寫(xiě)請(qǐng)求

client 線程直接將寫(xiě)請(qǐng)求壓入 Q_ProLog 隊(duì)列，隨后通過(guò)獲取請(qǐng)求狀態(tài)接口獲取結(jié)果。worker 線程讀取 Q_ProLog 寫(xiě)入請(qǐng)求，序列化得到 WAL entry 并壓入到 Q_log。Q_ProLog 隊(duì)列和 Q_Log 隊(duì)列是設(shè)計(jì)用于實(shí)現(xiàn) batched logging。logger 線程會(huì)一次性讀取 Q_log 隊(duì)列中所有的請(qǐng)求，執(zhí)行 group logging，并將寫(xiě)入請(qǐng)求壓入到 Q_EpiLog 隊(duì)列。worker 線程會(huì)從 Q_EpiLog 線程讀取請(qǐng)求，執(zhí)行最終的 memtable 更新操作。

負(fù)載調(diào)度

為減少線程調(diào)度的上下文切換造成的不必要資源占用。SpanDB 默認(rèn)啟動(dòng) 1 個(gè) logger，根據(jù)寫(xiě)入負(fù)載在 1 - 3 個(gè) logger 間浮動(dòng)?；谇芭_(tái)任務(wù)優(yōu)先的原則，根據(jù)寫(xiě)入隊(duì)列的請(qǐng)求響應(yīng)時(shí)間，SpanDB 也會(huì)控制相應(yīng)隊(duì)列的容量上限實(shí)現(xiàn)動(dòng)態(tài)負(fù)載均衡。

基于 SPDK 的快速日志寫(xiě)入

SpanDB 的 WAL 寫(xiě)入依然采用了 group logging 機(jī)制。若干個(gè) logger 線程從 Q_Log 獲取能夠讀取的所有請(qǐng)求，并發(fā)地執(zhí)行寫(xiě)入。
SpanDB 在 SD 的 WAL area 預(yù)先分配若干個(gè)邏輯 page，每個(gè) page 有一個(gè)唯一的 LPN (Log Page Number)。其中一個(gè) page 作為 metadata page。
若干個(gè)連續(xù)的 page 組成一個(gè) log page group，每個(gè) group 對(duì)應(yīng)一個(gè) memtable，容量足夠容納一個(gè) memtable 的 WAL。當(dāng) memtable flush 完成后，log group 將會(huì)被回收重用。meta data page 記錄每個(gè) log page group 的起始 LPN。
SpanDB 配置了多個(gè) logger 并發(fā)寫(xiě)入，每個(gè) logger 有單獨(dú)的 WAL data buffer。為實(shí)現(xiàn)并行寫(xiě)入，每個(gè) logger 通過(guò)原子操作分配得到下一個(gè)寫(xiě)入位置。當(dāng) memtable 寫(xiě)滿時(shí)，meta data page 會(huì)記錄其對(duì)應(yīng)的 log page group 結(jié)束 LPN。

Speed Disk 承擔(dān) LSM-tree 部分 level 負(fù)載

SpanDB 將頂部的部分 level 數(shù)據(jù)遷移到 SD 中，充分利用 SD 的硬件性能。

數(shù)據(jù)組織

為減少對(duì) RocksDB 代碼的侵入，在 SPDK I/O 的基礎(chǔ)上，SpanDB 實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的文件系統(tǒng) TopFS。由于 LSM-tree level 的 append only 屬性，文件系統(tǒng)的管理也類(lèi)似于 WAL，由一個(gè) metadata page 和若干個(gè) data page 組成，metadata page 通過(guò) hash table 記錄每個(gè)文件的起始 LPN。

WAL 寫(xiě)優(yōu)先

對(duì)于 KV 存儲(chǔ)引擎，特別是 OLTP 場(chǎng)景，寫(xiě)入延遲對(duì)用戶較為敏感。為了實(shí)現(xiàn) WAL 優(yōu)先寫(xiě)入，SpanDB 采取了3個(gè)措施：

1. 專(zhuān)門(mén)的 logger 請(qǐng)求隊(duì)列
2. 將 flush/compaction 默認(rèn)請(qǐng)求大小從 1MB 減小為 64KB
3. 限制 flush/compaction 的 worker 數(shù)量

SPDK Cache

SPDK bypass kernel 的特點(diǎn)讓 SPDK 無(wú)法使用系統(tǒng)的 page cache，無(wú)法充分利用局部性原理。在 TopFS 之上，SpanDB 實(shí)現(xiàn)了一個(gè)自有的 cache。在SpanDB 初始化時(shí)，會(huì)在 hugepage 中申請(qǐng)一大片內(nèi)存用作 cache。一個(gè) hash table 用于管理 cache entry，key 是 SST 文件名，value 是該文件包括的 block 對(duì)應(yīng)的 cache entry。

動(dòng)態(tài) level 布局

head-server thread 監(jiān)控 SD 的帶寬使用情況，基于預(yù)設(shè)閾值調(diào)整 SST 文件的分配。由于頂部的 SST 文件在不停 merge，也為了避免 SD 和 CD 間數(shù)據(jù)遷移，SpanDB 調(diào)整的是新創(chuàng)建 SST 文件的位置。因此，相同 level 的文件可能會(huì)分布在不同的設(shè)備之上。

性能測(cè)試結(jié)果

硬件參數(shù)表

YCSB 測(cè)試結(jié)果

RocksDB VS SpanDB on YCSB

1. 基于文件系統(tǒng)的順序 log 寫(xiě)入不能充分發(fā)揮高端 SSD 的性能
2. 除 read intensive 場(chǎng)景外，SpanDB 在不同的硬件組合下均可大幅度提升 IO 吞吐量和降低延遲
3. 高端硬件在 SpanDB 上的收益更大

LinkBench 測(cè)試結(jié)果

SpanDB 相較于 RocksDB 也能顯著改善性能，特別是高端硬件能獲得更大的性能收益。