本文選自“字節跳動基礎架構實踐”系列文章。

“字節跳動基礎架構實踐”系列文章是由字節跳動基礎架構部門各技術團隊及專家傾力打造的技術乾貨內容，和大家分享團隊在基礎架構發展和演進過程中的實踐經驗與教訓，與各位技術同學一起交流成長。

RocksDB 是世界上最被廣泛使用的存儲引擎之一，字節跳動內部大量的數據庫產品（如圖數據庫、NewSQL 等）都構建在 RocksDB 之上，對存儲引擎的研發投入將會持續加大，為更多業務賦能。

本文將介紹字節跳動對 RocksDB 存儲引擎的幾方面改進，其中參考了大量社區貢獻的經驗，也有部分獨創的技術，希望能為大家帶來更多的優化思路。

1. 背景

RocksDB 作為最著名的 LSM 類存儲引擎之一，在字節跳動內部佔據非常重要的位置，大量的數據庫、存儲系統都在基於 RocksDB 進行構建或改進，但 LSM 系列眾所周知的一些問題同樣困擾著字節跳動的業務，包括性能問題、成本問題、功能問題等等。

本文首先嚐試梳理和介紹我們對 RocksDB 在五個方面的改進（在內部存儲引擎 TerarkDB 的基礎上開發），希望能給社區帶來一些參考價值，也歡迎對存儲引擎感興趣的技術專家加入我們一起為字節跳動構建更強大的底層支撐。

2. RocksDB 的不足

• 讀寫放大嚴重
• 應對突發流量的時候削峰能力不足
• 壓縮率有限
• 索引效率較低
• 等等

3. 我們的改進

3.1 LazyBuffer

RocksDB 之前的某個版本引入了 PinnableSlice 作為數據在引擎內的傳輸載體，它的主要作用是可以減少數據複製，即當用戶所要查找的數據在 BlockCache 中的時候，只返回其引用。

但是 PinnableSlice 在一些場景下無法發揮價值，比如用戶的某個操作需要觸碰 大量不需要的 Value 時（如 Value 有很多版本或者有大量的 tombstone），PinnableSlice 依然會對這些無用的 Value 產生 I/O 操作，這部分開銷是完全可以避免的。

我們為此構建了 LazyBuffer 替換 PinnableSlice，當用戶獲得 Value 的時候，並不真正進行磁盤 I/O，只有用戶真正需要取值的時候才進行真正的 fetch 操作進行 I/O。

Lazy Buffer 是對 PinnableSlice 的增強，從減少數據複製更進一步減少不必要的 IO，對於大量的掃描、SeekRandom 等場景有很大好處。

3.2 Lazy Compaction

自從 LSM 推廣開來，針對 LSM Compaction 的各種策略優化層出不窮，其中主流的 Compaction 策略有以下幾種：

• Leveled Compaction全部層級都按照標準的從上到下進行層級合併讀寫放大都比較嚴重，但是空間放大較低在這篇論文（Towards Accurate and Fast Evaluation of Multi-Stage Log-Structured Designs）中有詳細的闡述
• Tiered Compaction即 RocksDB 中的 Universal Compaction空間放大和讀放大嚴重，但是寫放大最小在這篇論文（Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores via Adaptive Removal of Superfluous Merging）有詳細的闡述
• Tiered+Leveled Compaction即 RocksDB 中的 Level Compaction是一個混合的 Compaction 策略，空間放大比 Tiered Compaction 更低，寫放大也比 Leveled 低
• Leveled-N Compaction比 Leveled Compaction 寫放大更低，讀放大更高一次合併 N - 1 層到第 N 層

從上面的分類我們可以看到，主流的 Compaction 策略主要 在不同的合併時機之間進行權衡和選擇，字節跳動在這裡使用了稍微改進一點的方式。

首先，我們要理解如果能夠允許 SST 可以不必保持強有序，那麼就可以讓我們收集到更多的統計信息後再真正執行外排序（Compaction），但缺點是會增加一定程度的讀放大，對讀延遲會有影響，那麼有沒有辦法讓增加的讀放大可控，甚至幾乎不增加讀放大呢？

我們嘗試構建了一種新的 SST 數據結構（Adaptive Map，簡稱 aMap），區別於 RocksDB 默認的結構，aMap 是一個邏輯上的虛擬 SST，如下圖所示：

aMap 結構示意圖

圖中 SST 1、SST 2、SST 3 是三個物理上的 SST 文件，當需要對他們進行合併的時候，我們先構建虛擬遮罩，對上層暴露邏輯上的合併好的 SST（邏輯上是一個大 SST），同時記錄和標記其中的覆蓋度、Key Space 等統計信息。

它的主要功能有：

• 大的 Compaction 策略上，繼承了 RocksDB 的 Level Compaction（Universal Compaction 也可以支持，看場景需要，默認是 Level Compaction）
• 當需要進行 Compaction 的時候，會首選構建 Adaptive Map，將候選的幾個 SST 構成一個邏輯上的新 SST（如上圖所示）
• Adaptive Map 中會切分出多個不同的重疊段，R1、R2、R3、R4、R5，這些重疊段的重疊度會被追蹤記錄
• 後臺的 GC 線程會優先選擇那些重疊度更好的層進行 GC，通過這種手段，我們可以讓 GC 更有效率，即寫放大遠低於默認的情況

讀寫放大和原版 RocksDB 對比，理論分析上是有優勢的：

複雜度分析對比（讀放大和寫放大）

3.3 KV 分離

在論文 *WiscKey: Separating Keys from Values in SSD-conscious Storage* 介紹了一種 KV 分離的 SST 設計，它的主要方式是構建一個 Value Log 文件不斷的在上面追加 Value 數據，同時原始的 SST 中 Value 只記錄數據真實存在的位置即可。

KV 分離的基本原理

其實 KV 分離的思路比較直接和簡單，把符合閾值的 value 從直接存儲在 SST 中，改為存儲文件指針，降低 Compaction、Seek 等操作的開銷。

RocksDB 社區有一個 KV 分離的 BlobDB 功能，但是目前功能還不完善，還有大量的工作需要繼續做，這裡就暫不做對比。另一個 TitanDB 是一個實現上相對完整的 KV 分離存儲引擎（以 RocksDB 插件的形式構建），我們在這裡對他們進行一個簡單的對比：

綜合來看，在和社區的對比中，我們實現 KV 分離的大體思路是類似的，但由於我們有 Adaptive Map 的存在，可以對真正的 GC 操作進行延遲到負載較低的時候進行，對於應對突發流量尖峰會有相當不錯的效果。

但 KV 分離也帶來了一些損失，最重要的就是對於範圍查詢造成了損害，後續可以通過邏輯層進行 Prefetch 來降低這部分的損耗。

3.4 多種索引支持

對於原生的 RocksDB，其 SST 格式大致如下圖所示：

<code>[data block 1]
[data block 2]
...
[data block N]
[meta block 1: filter block]          (see section: "filter" Meta Block)
[meta block 2: index block]
[meta block 3: compression dictionary block]  (see section: "compression dictionary" Meta Block)
[meta block 4: range deletion block]      (see section: "range deletion" Meta Block)
[meta block 5: stats block]          (see section: "properties" Meta Block)
...
[meta block K: future extended block]  (we may add more meta blocks in the future)
[metaindex block]
[Footer]                (fixed size; starts at file_size - sizeof(Footer))/<code>

其中，index block 和 filter block 幫助用戶快速定位目標 key 所在的 block。RocksDB 默認的 index 並沒有考慮不同數據類型之間的差異，無法根據不同數據類型選擇壓縮效率和查詢效率最高的索引結構，針對這個問題，我們構建了一種自適應的索引選擇和構建機制。

• 對於輸入的數據，我們會對其進行分段式探測，確定最高效的索引算法
• 對於這批數據進行單獨索引並把索引放在 index block 中的

目前已經支持的額外索引算法有：

• 壓縮 Trie 索引，針對字符串類型進行通用壓縮
• 非降序整數索引，通過 bitmap 構建高度壓縮的索引
• ......

通過多種索引結構的支持，為以後的長期優化提供了更多可能，甚至在 SST 中內嵌 B+ 樹索引 data block 等等，更加靈活、模塊化的結構讓引擎的適應能力更強，面對不同的存儲介質、訪問模式可以有更佳的綜合表現。

3.5 極致壓縮

對於數據庫應用來說，除了追求高性能外，成本控制也是一個很重要的話題，其中成本控制的重要一環就是數據壓縮，對於 LSM 結構來說，默認是通過 block 進行壓縮的，壓縮率和塊的尺寸強相關。

在這裡為了解決塊尺寸和壓縮率的 tradeoff 問題，我們構建了一系列的壓縮算法，其中最常用的是可以按記錄抽取數據的全局壓縮，其基本思路其實並不複雜，通過對 LZ 系列的改進，使用高效的手段保留每一個 Record 的 Offset 即可，而 Offset 表有很多種方法進行壓縮存儲（顯然它是遞增的非連續整數序列），利用 pfordelta 等方法進行優化變通存儲不難辦到。

全局壓縮算法的概要流程

其大致流程是：

• 先對數據進行掃描採樣構建數據字典所以默認情況下需要對 Compaction SST 進行改造以提供兩遍掃描的能力
• 根據數據字典，對原數據進行滑動窗口壓縮
• 最後再進行一輪可選的熵壓縮（Entropy Compression）熵壓縮業內主流的包括 ANS 和高階 Huffman 等等，可以根據實際數據分佈探測選擇
• 在壓縮過程中，將會保存每條原始數據的 offset 信息構成偏移表

偏移表的構建和保存

偏移表採用常見的類 pfordelta 算法壓縮保存即可，需要注意的是因為偏移表會被頻繁訪問，這裡的適宜有一階差分表和二階差分表，根據實際情況選擇即可。

索引後續可以直接映射到這裡具體的 record offset 中來，方便後續的直接按記錄尋址。

3.6 新硬件支持

對目前流行的新硬件（如持久化內存、FPGA、QAT 等），我們同樣進行了適配和優化，比如在在設備有 QAT 硬件的時候，我們在主機 CPU 負載較高時，選擇放棄一部分 CPU 壓縮 offload 到 QAT 中進行壓縮，再比如我們將一部分數據放在持久化內存上實現真正的 Record 級別數據訪問（我們採用的並非常見的塊級別的索引結構，而是直接按記錄索引）等等。

這裡我們以 QAT 壓縮為例來說明：

• 我們知道隨著 PCIe NVMe SSD 的大範圍普及，磁盤的帶寬和 IOPS 大幅度提升
• 磁盤帶寬的提升進而將系統瓶頸轉移到了 CPUCPU 要做的工作包括數據排序（SST 需要維護有序性）、CRC 校驗、數據壓縮、查詢比對等等
• 我們初步目前的計劃是把數據壓縮和 CRC 校驗卸載到專門的 QAT 硬件中進行加速目前 QAT 硬件的性價比較高，甚至部分主板還自帶
• QAT 本身能支持的壓縮算法有限，主要以 zlib 的 deflate 為主
• 當我們卸載了數據壓縮和 CRC 校驗後，就可以分配更多的 CPU 進行 SST 的 GC 和 Compaction，儘快將 SST 形態調整到最佳

目前 QAT 的使用還在測試階段，還沒有正式上線，下一步計劃對 FPGA 的應用進行深度的調研。

4. 對比測試

我們使用 RocksDB 的 bench 工具進行了一些簡單的測試，對比了 RocksDB、TitanDB 和 TerarkDB 的區別和差異，需要注意是，該工具使用的是隨機生成的數據，對於 TerarkDB 的壓縮算法不是很友好，所以壓縮率差距並不大。

這次改進，我們重點關注的是 KV 分離的表現，所以只對比較大的 Value 進行 benchmark 確認其改進效果：

• 測試環境：原始測試數據集大小為 256 GB，內存 128 GBCPU : 48 CoreRAM : 128 GBDisk : Intel NVMe 3.4T測試程序為 db_benchLinux version 4.14GCC Version 6.3.0
• 測試內容：fillrandom：多線程隨機寫入, 存在重複 keyreadseq：多線程順序 Scanreadrandom：多線程隨機 Getseekrandom：多線程隨機 Seek

Value size = 4KB

Value size = 32KB

5. 後續

字節跳動在單機引擎上的投入會持續加大，同時也會考慮為各類特定業務構建針對性的專用引擎，其目標是在單機內為上層業務提供更強大的性能，更靈活的功能和更可靠的服務。

為了實現這些目標，後續我們還需要做的有很多，包括卸載單機引擎的 CPU 到集群上進行分佈式 Compaction、引入 SPDK 相關的技術提升 IO 效率、引入 AI Tuning 針對不同負載做更靈活的 I/O 策略、引入新硬件（如持久化內存和 FPGA）等等。

為了實現字節跳動存儲引擎的多樣性和走向業界前沿，我們迫切的希望有志者能夠加入我們一起做新的探索，我們也希望未來在主流的期刊上、開源社區中能夠看到字節跳動的活躍身影，為技術社區貢獻自己的力量。

6. 參考文獻

1. WiscKey: Separating Keys from Values in SSD-conscious Storage
2. Bitcask A Log-Structured Hash Table for Fast Key/Value Data
3. LSM-trie: An LSM-tree-based Ultra-Large Key-Value Store for Small Data
4. Towards Accurate and Fast Evaluation of Multi-Stage Log-Structured Designs

更多分享

字節跳動基礎架構團隊

字節跳動基礎架構團隊是支撐字節跳動旗下包括抖音、今日頭條、西瓜視頻、火山小視頻在內的多款億級規模用戶產品平穩運行的重要團隊，為字節跳動及旗下業務的快速穩定發展提供了保證和推動力。

公司內，基礎架構團隊主要負責字節跳動私有云建設，管理數以萬計服務器規模的集群，負責數萬臺計算/存儲混合部署和在線/離線混合部署，支持若干 EB 海量數據的穩定存儲。

文化上，團隊積極擁抱開源和創新的軟硬件架構。我們長期招聘基礎架構方向的同學，具體可參見 job.bytedance.com ，感興趣可以聯繫郵箱 [email protected] 。

閱讀更多 字節跳動技術團隊 的文章

關鍵字: 數據結構 技術 存儲