LSM 樹廣泛用于數(shù)據(jù)存儲，例如 RocksDB、Apache AsterixDB、Bigtable、HBase、LevelDB、Apache Accumulo、SQLite4、Tarantool、WiredTiger、Apache Cassandra、InfluxDB和ScyllaDB等。

在這篇文章中，我們將深入探討 Log Structured Merge Tree ，又名 LSM 樹：許多高度可擴(kuò)展的 NoSQL 分布式鍵值類型數(shù)據(jù)庫（如 Amazon 的 DynamoDB、Cassandra 和 ScyllaDB）的數(shù)據(jù)結(jié)構(gòu)。

眾所周知，這些數(shù)據(jù)庫在設(shè)計(jì)上支持的寫入速率遠(yuǎn)遠(yuǎn)超過傳統(tǒng)關(guān)系數(shù)據(jù)庫所能提供的。
These databases by design are known to support write rates far more than what traditional relational databases can offer.

我們將看到 LSM 樹如何使他們能夠?qū)崿F(xiàn)他們聲稱的寫入速度，以及它們?nèi)绾未龠M(jìn)讀取。
We'll see how LSM Tree enables them to allow the write speeds that they claim, as well as how they facilitate reads.

什么是 LSM 樹？

典型的數(shù)據(jù)庫管理系統(tǒng)（簡稱 DBMS）由多個(gè)組件組成，每個(gè)組件負(fù)責(zé)處理數(shù)據(jù)存儲、檢索和管理的不同方面。
A typical Database Management System (DBMS in short) consists of multiple components, each responsible for handling different aspects of data storage, retrieval and management.

一個(gè)這樣的組件是存儲引擎，它負(fù)責(zé)提供可靠的接口，以便從底層存儲設(shè)備高效地讀取和寫入數(shù)據(jù)。
One such component is the storage engine which is responsible for providing a reliable interface for reading and writing data efficiently from/to the underlying storage device.

它是實(shí)現(xiàn)數(shù)據(jù)庫四大要求中的兩個(gè)的組件，即 ACID 屬性：A tomicity 和D耐用性。
It's the component that implements the two among the four big asks of databases ie, the ACID properties: A tomicity and D urability

除此之外，存儲引擎的性能在選擇數(shù)據(jù)庫時(shí)也很重要，因?yàn)樗亲罱咏谑褂玫拇鎯υO(shè)備的組件。
In addition to that, the performance of a storage engine matters a lot in the choice of a database as it's the component that's closest to the storage device in use.

實(shí)現(xiàn)存儲引擎的兩種流行的數(shù)據(jù)結(jié)構(gòu)是 B+ 樹和 LSM 樹。
Two popular data structures for implementing storage engines are B+ Trees and LSM Trees.

幾乎所有 NoSQL 數(shù)據(jù)庫都使用 LSM Tree 的變體作為其底層存儲引擎，因?yàn)樗试S它們實(shí)現(xiàn)快速的寫入吞吐量和對主鍵的快速查找。
Almost all NoSQL databases use a variant of LSM Tree as their underlying storage engine, because it allows them to achieve fast write throughput and fast lookups on the primary key.

LSM 樹也越來越受歡迎，因?yàn)榇鎯υO(shè)備的物理設(shè)計(jì)從旋轉(zhuǎn)磁盤到 NAND 閃存 SSD 和最近的 NVDIMM，如英特爾傲騰。傳統(tǒng)的存儲引擎（基于 B+ 樹）是為旋轉(zhuǎn)磁盤設(shè)計(jì)的，寫入速度很慢，并且只提供基于塊的尋址。然而，今天的應(yīng)用程序是寫入密集型的，并且會生成大量數(shù)據(jù)。因此，需要重新考慮 DBMS 中現(xiàn)有存儲引擎的設(shè)計(jì)。英特爾傲騰和其他 NVM 等新存儲設(shè)備提供字節(jié)尋址能力并且比 SSD 更快。這導(dǎo)致了諸如Nova之類的探索，它是一個(gè)用于持久內(nèi)存的日志結(jié)構(gòu)文件系統(tǒng)。

LSM Trees are also gaining popularity as storage devices advance in their physical design from spinning disks to NAND flash SSDs and recently NVDIMMs such as Intel Optane. Traditional storage engines (based on B+ Trees) are designed for spinning disks, are slow in writes and offer only block based addressing. Today's applications, however, are write intensive and generate high volumes of data. As a result, there's a need to rethink the design of existing storage engines in DBMSs. New storage devices such as Intel Optane and other NVMs offer byte addressibility and are faster than SSDs. This has led to explorations such as Nova which is a log structured file system for persistant memory.

除此之外，學(xué)習(xí) LSM 樹是進(jìn)入復(fù)雜的數(shù)據(jù)庫存儲引擎內(nèi)部世界的最快方法。它們在設(shè)計(jì)上比基于 B+ 樹的存儲引擎非常簡單。因此，如果您對 NoSQL 數(shù)據(jù)庫如何存儲數(shù)據(jù)感興趣，或者正在嘗試實(shí)現(xiàn)存儲引擎，請繼續(xù)閱讀！

In addition to that, learning about LSM Trees is the fastest way to get into the complicated world of database storage engine internals. They are very simple in design than B+ Tree based storage engines. So if you're someone interested in how NoSQL databases store your data, or are trying to implement a storage engine, continue reading!

B tree 與 B+ tree

B-Tree： B-Tree 被稱為自平衡樹，因?yàn)樗墓?jié)點(diǎn)在中序遍歷中排序。在 B-tree 中，一個(gè)節(jié)點(diǎn)可以有兩個(gè)以上的子節(jié)點(diǎn)。B-tree 的高度為 logM N（其中“M”是樹的順序，N 是節(jié)點(diǎn)數(shù)）。每次更新都會自動(dòng)調(diào)整高度。在 B-tree 中，數(shù)據(jù)按特定順序排序，最小值在左側(cè)，最大值在右側(cè)。在 B-tree 中插入數(shù)據(jù)或鍵比二叉樹更復(fù)雜。B-Tree必須滿足一些條件：

• B樹的所有葉子節(jié)點(diǎn)必須在同一層級。
• 在 B 樹的葉子節(jié)點(diǎn)之上，不應(yīng)該有空的子樹。
• B-樹的高度應(yīng)該盡可能低。

B+ 樹，通過僅在樹的葉節(jié)點(diǎn)處存儲數(shù)據(jù)指針，消除了 B-樹用于索引的缺點(diǎn)。因此，B+樹的葉子節(jié)點(diǎn)的結(jié)構(gòu)與B樹的內(nèi)部節(jié)點(diǎn)的結(jié)構(gòu)有很大的不同。這里可以注意到，由于數(shù)據(jù)指針只存在于葉節(jié)點(diǎn)，葉節(jié)點(diǎn)必須將所有的鍵值連同它們對應(yīng)的指向磁盤文件塊的數(shù)據(jù)指針一起存儲，以訪問它們。此外，葉節(jié)點(diǎn)被鏈接以提供對記錄的有序訪問。因此，葉節(jié)點(diǎn)形成索引的第一級，內(nèi)部節(jié)點(diǎn)形成多級索引的其他級別。葉節(jié)點(diǎn)的一些鍵值也出現(xiàn)在內(nèi)部節(jié)點(diǎn)中，只是作為一種媒介來控制記錄的搜索。

讓我們看看B-tree和B+樹的區(qū)別：

LSM tree 問題場景

傳統(tǒng)關(guān)系型數(shù)據(jù)庫使用b+ tree或一些變體作為存儲結(jié)構(gòu)，能高效進(jìn)行查找。
但保存在磁盤中時(shí)它也有一個(gè)明顯的缺陷，那就是邏輯上相離很近但物理卻可能相隔很遠(yuǎn)，這就可能造成大量的磁盤隨機(jī)讀寫。

隨機(jī)讀寫比順序讀寫慢很多，為了提升IO性能，我們需要一種能將隨機(jī)操作變?yōu)轫樞虿僮鞯臋C(jī)制，于是便有了LSM樹。LSM樹能讓我們進(jìn)行順序?qū)懘疟P，從而大幅提升寫操作，作為代價(jià)的是犧牲了一些讀性能。

關(guān)于磁盤IO

磁盤讀寫時(shí)涉及到磁盤上數(shù)據(jù)查找，地址一般由柱面號、盤面號和塊號三者構(gòu)成。也就是說移動(dòng)臂先根據(jù)柱面號移動(dòng)到指定柱面，然后根據(jù)盤面號確定盤面的磁道，最后根據(jù)塊號將指定的磁道段移動(dòng)到磁頭下，便可開始讀寫。

整個(gè)過程主要有三部分時(shí)間消耗，查找時(shí)間(seek time) +等待時(shí)間(latency time)+傳輸時(shí)間(transmission time) 。分別表示定位柱面的耗時(shí)、將塊號指定磁道段移到磁頭的耗時(shí)、將數(shù)據(jù)傳到內(nèi)存的耗時(shí)。整個(gè)磁盤IO最耗時(shí)的地方在查找時(shí)間，所以減少查找時(shí)間能大幅提升性能。

關(guān)于磁盤IO這一部分，其實(shí)要區(qū)別看待。如果采用的是ssd，那么對于任意地址而言，其實(shí)尋址時(shí)間可以認(rèn)為是固定的，它與最傳統(tǒng)的chs以及l(fā)ba尋址方式不一樣。如果是ssd的話，隨機(jī)讀寫和順序讀寫，開銷差距大嗎？

性能比較-機(jī)械硬盤

機(jī)械硬盤在順序讀寫場景下有相當(dāng)出色的性能表現(xiàn)，但一遇到隨機(jī)讀寫性能則直線下降。
順序讀是隨機(jī)讀性能的400倍以上。順序讀能達(dá)到84MB/S。
順序?qū)懯请S機(jī)讀性能的100倍以上。順序?qū)懶阅苣苓_(dá)到79M/S。

原因：是因?yàn)闄C(jī)械硬盤采用傳統(tǒng)的磁頭探針結(jié)構(gòu)，隨機(jī)讀寫時(shí)需要頻繁尋道，也就需要磁頭和探針頻繁的轉(zhuǎn)動(dòng)，而機(jī)械結(jié)構(gòu)的磁頭和探針的位置調(diào)整是十分費(fèi)時(shí)的，這就嚴(yán)重影響到硬盤的尋址速度，進(jìn)而影響到隨機(jī)寫入速度。

性能比較-固態(tài)硬盤

順序讀：220.7MB/s。隨機(jī)讀：24.654MB/s。
順序?qū)懀?7.2MB/s。隨機(jī)寫：68.910MB/s。

總結(jié)：對于固態(tài)硬盤，順序讀的速度仍然能達(dá)到隨機(jī)讀的10倍左右。但是隨機(jī)寫還是順序?qū)?，差別不大。

LSM tree 特性

LSM樹的核心特點(diǎn)是利用 “順序?qū)憽?來提高寫性能。

LSM數(shù)據(jù)存儲分為內(nèi)存和文件兩部分。這樣的設(shè)計(jì)，是通過犧牲小部分讀性能換來高性能寫。LSM樹的核心就是放棄部分讀能力，換取寫入的最大化能力，放棄磁盤讀性能來換取寫的順序性。極端的說，基于LSM樹實(shí)現(xiàn)的HBase的寫性能比Mysql高了一個(gè)數(shù)量級，讀性能低了一個(gè)數(shù)量級。

LSM樹由Patrick O'Neil等人在論文《The Log-Structured Merge Tree》：https://www.cs.umb.edu/~poneil/lsmtree.pdf , 提出，它實(shí)際上不是一棵樹，而是2個(gè)或者多個(gè)樹或類似樹的結(jié)構(gòu)（注意這點(diǎn)）的集合。下圖示出最簡單的有2個(gè)結(jié)構(gòu)的LSM樹。

在LSM樹中，最低一級也是最小的C0樹位于內(nèi)存里，而更高級的C1、C2...樹都位于磁盤里。數(shù)據(jù)會先寫入內(nèi)存中的C0樹，當(dāng)它的大小達(dá)到一定閾值之后，C0樹中的全部或部分?jǐn)?shù)據(jù)就會刷入磁盤中的C1樹，如下圖所示。

由于內(nèi)存的讀寫速率都比外存要快非常多，因此數(shù)據(jù)寫入C0樹的效率很高。并且數(shù)據(jù)從內(nèi)存刷入磁盤時(shí)是預(yù)排序的，也就是說，LSM樹將原本的隨機(jī)寫操作轉(zhuǎn)化成了順序?qū)懖僮?，寫性能大幅提升。不過，它的tradeoff就是犧牲了一部分讀性能，因?yàn)樽x取時(shí)需要將內(nèi)存中的數(shù)據(jù)和磁盤中的數(shù)據(jù)合并?？傮w上來講這種tradeoff還是值得的，因?yàn)椋?/p>

可以先讀取內(nèi)存中C0樹的緩存數(shù)據(jù)。內(nèi)存的效率很高，并且根據(jù)局部性原理，最近寫入的數(shù)據(jù)命中率也高。
寫入數(shù)據(jù)未刷到磁盤時(shí)不會占用磁盤的I/O，不會與讀取競爭。讀取操作就能取得更長的磁盤時(shí)間，變相地彌補(bǔ)了讀性能差距。

在實(shí)際應(yīng)用中，為了防止內(nèi)存因斷電等原因丟失數(shù)據(jù)，寫入內(nèi)存的數(shù)據(jù)同時(shí)會順序在磁盤上寫日志，類似于我們常見的預(yù)寫日志（WAL），這就是LSM這個(gè)詞中Log一詞的來歷。另外，如果有多級樹的話，低級的樹在達(dá)到大小閾值后也會在磁盤中進(jìn)行合并，如下圖所示。

RocksDB 的架構(gòu)圖：

LSM樹有以下三個(gè)重要組成部分：

1) MemTable

MemTable是在內(nèi)存中的數(shù)據(jù)結(jié)構(gòu)，用于保存最近更新的數(shù)據(jù)，會按照Key有序地組織這些數(shù)據(jù)，LSM樹對于具體如何組織有序地組織數(shù)據(jù)并沒有明確的數(shù)據(jù)結(jié)構(gòu)定義，例如Hbase使跳躍表來保證內(nèi)存中key的有序。

因?yàn)閿?shù)據(jù)暫時(shí)保存在內(nèi)存中，內(nèi)存并不是可靠存儲，如果斷電會丟失數(shù)據(jù)，因此通常會通過WAL(Write-ahead logging，預(yù)寫式日志)的方式來保證數(shù)據(jù)的可靠性。

2) Immutable MemTable

當(dāng) MemTable達(dá)到一定大小后，會轉(zhuǎn)化成Immutable MemTable。Immutable MemTable是將轉(zhuǎn)MemTable變?yōu)镾STable的一種中間狀態(tài)。寫操作由新的MemTable處理，在轉(zhuǎn)存過程中不阻塞數(shù)據(jù)更新操作。

3) SSTable (Sorted String Table，排序字符串表)

Sorted Strings Table (borrowed from google) is a file of key/value string pairs, sorted by keys.
"An SSTable provides a persistent,ordered immutable map from keys to values, where both keys and values are arbitrary byte strings. Operations are provided to look up the value associated with a specified key, and to iterate over all key/value pairs in a specified key range. Internally, each SSTable contains a sequence of blocks (typically each block is 64KB in size, but this is configurable). A block index (stored at the end of the SSTable) is used to locate blocks; the index is loaded into memory when the SSTable is opened. A lookup can be performed with a single disk seek: we first find the appropriate block by performing a binary search in the in-memory index, and then reading the appropriate block from disk. Optionally, an SSTable can be completely mapped into memory, which allows us to perform lookups and scans without touching disk."
SSTable (directly mapped to GFS) is key-value based immutable storage. It stores chunks of data, each is of 64KB.

SSTable Definitions:

Index of the keys: key and starting location
Chunk is a storage unit in GFS, replica management are by chunk

有序鍵值對集合，是LSM樹組在磁盤中的數(shù)據(jù)結(jié)構(gòu)。為了加快SSTable的讀取，可以通過建立key的索引以及布隆過濾器來加快key的查找。

https://www.mauriciopoppe.com/notes/computer-science/data-structures/memtable-sstable/

Memtable

In-memory data structure that holds data before it’s flushed into an SStable, the implementation may use a RB Tree, a skiplist, a HashLinkList

SSTable

An immutable data structure that stores a large number of key:value pairs sorted by key

Advantages over simple hash indexes

• Merging SSTables is similar to doing a merge sort
• To find if a key exists we don’t need an index of all the keys in memory, instead we can keep an index for every few kilobytes and then perform a scan (sparse index)
• range queries can be compressed before writing to disk, the sparse index would only need to find the starting position of the compressed segment

References

• https://github.com/facebook/rocksdb/wiki/MemTable
• https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/

這里需要關(guān)注一個(gè)重點(diǎn)，LSM樹(Log-Structured-Merge-Tree)正如它的名字一樣，LSM樹會將所有的數(shù)據(jù)插入、修改、刪除等操作記錄(注意是操作記錄)保存在內(nèi)存之中，當(dāng)此類操作達(dá)到一定的數(shù)據(jù)量后，再批量地順序?qū)懭氲酱疟P當(dāng)中。這與B+樹不同，B+樹數(shù)據(jù)的更新會直接在原數(shù)據(jù)所在處修改對應(yīng)的值，但是LSM數(shù)的數(shù)據(jù)更新是日志式的，當(dāng)一條數(shù)據(jù)更新是直接append一條更新記錄完成的。這樣設(shè)計(jì)的目的就是為了順序?qū)懀粩嗟貙mmutable MemTable flush到持久化存儲即可，而不用去修改之前的SSTable中的key，保證了順序?qū)憽?/p>

因此當(dāng)MemTable達(dá)到一定大小flush到持久化存儲變成SSTable后，在不同的SSTable中，可能存在相同Key的記錄，當(dāng)然最新的那條記錄才是準(zhǔn)確的。這樣設(shè)計(jì)的雖然大大提高了寫性能，但同時(shí)也會帶來一些問題：

1）冗余存儲，對于某個(gè)key，實(shí)際上除了最新的那條記錄外，其他的記錄都是冗余無用的，但是仍然占用了存儲空間。因此需要進(jìn)行Compact操作(合并多個(gè)SSTable)來清除冗余的記錄。
2）讀取時(shí)需要從最新的倒著查詢，直到找到某個(gè)key的記錄。最壞情況需要查詢完所有的SSTable，這里可以通過前面提到的索引/布隆過濾器來優(yōu)化查找速度。

SSTable 數(shù)據(jù)模型

SSTable 中的數(shù)據(jù)按主鍵排序后存放在連續(xù)的數(shù)據(jù)塊(Block)中，塊之間也有序。接著，存放數(shù)據(jù)塊索引，由每個(gè) Block 最后一行的主鍵組成，由于數(shù)據(jù)查詢中的Block定位。接著，存放布隆過濾器和表格的 Schema 信息。最后，存放固定大小的 Trailer 以及 Trailer 的偏移位置。

查找 SSTable 時(shí)，首先從子表的索引信息中讀取 SSTable Trailer 的偏移位置，接著獲取 Trailer 信息。根據(jù) Trailer 中記錄的信息，可以獲取塊索引的大小和偏移，從而將整個(gè)塊索引加載到內(nèi)存中。根據(jù)塊索引記錄的每個(gè) Block 的最后一行的主鍵，可以通過二分查找定位到查找的 Block。最后將 Block 加載到內(nèi)存中，通過二分查找 Block 中記錄的行索引查找到具體某一行。本質(zhì)上看，SSTable 是一個(gè)兩級索引結(jié)構(gòu)：塊索引以及行索引；而整個(gè) ChunkServer 是一個(gè)三級索引結(jié)構(gòu)：子表索引、塊索引以及行索引。

SSTable 分為兩種格式：稀疏格式和稠密格式。對于稀疏格式，某些列可能存在，也可能不存在，因此，每一行只存儲包含實(shí)際值的列，每一列存儲的內(nèi)容為：<列ID，列值>(<Column ID, Column Value>); 而稠密格式中每一行都需要存儲所有列，每一列只需要存儲列值，不需要存儲列 ID，這是因?yàn)榱?ID 可以從表格 Schema 中獲取。

SSTable 文件的內(nèi)容分為 5 個(gè)部分，F(xiàn)ooter、IndexBlock、MetaIndexBlock、FilterBlock 和 DataBlock。其中存儲了鍵值對內(nèi)容的就是 DataBlock，存儲了布隆過濾器二進(jìn)制數(shù)據(jù)的是 FilterBlock，DataBlock 有多個(gè)，F(xiàn)ilterBlock 也可以有多個(gè)，但是通常最多只有 1 個(gè)，之所以設(shè)計(jì)成多個(gè)是考慮到擴(kuò)展性，也許未來會支持其它類型的過濾器。另外 3 個(gè)部分為管理塊，其中 IndexBlock 記錄了 DataBlock 相關(guān)的元信息，MetaIndexBlock 記錄了過濾器相關(guān)的元信息，而 Footer 則指出 IndexBlock 和 MetaIndexBlock 在文件中的偏移量信息，它是元信息的元信息，它位于 sstable 文件的尾部。下面我們至頂向下挨個(gè)分析每個(gè)結(jié)構(gòu)

Footer 結(jié)構(gòu)

它的占用空間很小只有 48 字節(jié)，內(nèi)部只存了幾個(gè)字段。下面我們用偽代碼來描述一下它的結(jié)構(gòu)

// 定義了數(shù)據(jù)塊的位置和大小
struct BlockHandler {
  varint offset;
  varint size;
}

struct Footer {
  BlockHandler metaIndexHandler;  // MetaIndexBlock的文件偏移量和長度
  BlockHandler indexHandler; // IndexBlock的文件偏移量和長度
  byte[n] padding;  // 內(nèi)存墊片
  int32 magicHighBits;  // 魔數(shù)后32位
  int32 magicLowBits; // 魔數(shù)前32位
}
復(fù)制代碼

Footer 結(jié)構(gòu)的中間部分增加了內(nèi)存墊片，其作用就是將 Footer 的空間撐到 48 字節(jié)。結(jié)構(gòu)的尾部還有一個(gè) 64位的魔術(shù)數(shù)字 0xdb4775248b80fb57，如果文件尾部的 8 字節(jié)不是這個(gè)數(shù)字說明文件已經(jīng)損壞。這個(gè)魔術(shù)數(shù)字的來源很有意思，它是下面返回的字符串的前64bit。

$ echo http://code.google.com/p/leveldb/ | sha1sum
db4775248b80fb57d0ce0768d85bcee39c230b61
復(fù)制代碼

IndexBlock 和 MetaIndexBlock 都只有唯一的一個(gè)，所以分別使用一個(gè) BlockHandler 結(jié)構(gòu)來存儲偏移量和長度。

Block 結(jié)構(gòu)

除了 Footer 之外，其它部分都是 Block 結(jié)構(gòu)，在名稱上也都是以 Block 結(jié)尾。所謂的 Block 結(jié)構(gòu)是指除了內(nèi)部的有效數(shù)據(jù)外，還會有額外的壓縮類型字段和校驗(yàn)碼字段。

struct Block {
  byte[] data;
  int8 compressType;
  int32 crcValue;
}

每一個(gè) Block 尾部都會有壓縮類型和循環(huán)冗余校驗(yàn)碼（crcValue），這會要占去 5 字節(jié)。如果是壓縮類型，塊內(nèi)的數(shù)據(jù) data 會被壓縮。校驗(yàn)碼會針對壓縮和的數(shù)據(jù)和壓縮類型字段一起計(jì)算循環(huán)冗余校驗(yàn)和。壓縮算法默認(rèn)是 snappy ，校驗(yàn)算法是 crc32。

crcValue = crc32(data, compressType)

在下面介紹的所有 Block 結(jié)構(gòu)中，我們不再提及壓縮和校驗(yàn)碼。

DataBlock 結(jié)構(gòu)

DataBlock 的大小默認(rèn)是 4K 字節(jié)（壓縮前），里面存儲了一系列鍵值對。前面提到 sst 文件里面的 Key 是有序的，這意味著相鄰的 Key 會有很大的概率有共同的前綴部分。正是考慮到這一點(diǎn)，DataBlock 在結(jié)構(gòu)上做了優(yōu)化，這個(gè)優(yōu)化可以顯著減少存儲空間。

Key = sharedKey + unsharedKey

Key 會劃分為兩個(gè)部分，一個(gè)是 sharedKey，一個(gè)是 unsharedKey。前者表示相對基準(zhǔn) Key 的共同前綴內(nèi)容，后者表示相對基準(zhǔn) Key 的不同后綴部分。

比如基準(zhǔn) Key 是 helloworld，那么 hellouniverse 這個(gè) Key 相對于基準(zhǔn) Key 來說，它的 sharedKey 就是 hello，unsharedKey 就是 universe。

DataBlock 中存儲的是連續(xù)的一系列鍵值對，它會每隔若干個(gè) Key 設(shè)置一個(gè)基準(zhǔn) Key?；鶞?zhǔn) Key 的特點(diǎn)就是它的 sharedKey 部分是空串。基準(zhǔn) Key 的位置，也就是它在塊中的偏移量我們稱之為「重啟點(diǎn)」RestartPoint，在 DataBlock 中會記錄所有「重啟點(diǎn)」位置。第一個(gè)「重啟點(diǎn)」的位置是零，也就是 DataBlock 中的第一個(gè) Key。

struct Entry {
  varint sharedKeyLength;
  varint unsharedKeyLength;
  varint valueLength;
  byte[] unsharedKeyContent;
  byte[] valueContent;
}

struct DataBlock {
  Entry[] entries;
  int32 [] restartPointOffsets;
  int32 restartPointCount;
}

DataBlock 中基準(zhǔn) Key 是默認(rèn)每隔 16 個(gè) Key 設(shè)置一個(gè)。從節(jié)省空間的角度來說，這并不是一個(gè)智能的策略。比如連續(xù) 26 個(gè) Key 僅僅是最后一個(gè)字母不同，DataBlock 卻每隔 16 個(gè) Key 強(qiáng)制「重啟」，這明顯不是最優(yōu)的。這同時(shí)也意味著 sharedKey 是空串的 Key 未必就是基準(zhǔn) Key。

一個(gè) DataBlock 的默認(rèn)大小只有 4K 字節(jié)，所以里面包含的鍵值對數(shù)量通常只有幾十個(gè)。如果單個(gè)鍵值對的內(nèi)容太大一個(gè) DataBlock 裝不下咋整？

這里就必須糾正一下，DataBlock 的大小是 4K 字節(jié)，并不是說它的嚴(yán)格大小，而是在追加完最后一條記錄之后發(fā)現(xiàn)超出了 4K 字節(jié)，這時(shí)就會再開啟一個(gè) DataBlock。這意味著一個(gè) DataBlock 可以大于 4K 字節(jié)，如果 value 值非常大，那么相應(yīng)的 DataBlock 也會非常大。DataBlock 并不會將同一個(gè) Value 值分塊存儲。

FilterBlock 結(jié)構(gòu)

如果沒有開啟布隆過濾器，F(xiàn)ilterBlock 這個(gè)塊就是不存在的。FilterBlock 在一個(gè) SSTable 文件中可以存在多個(gè)，每個(gè)塊存放一個(gè)過濾器數(shù)據(jù)。不過就目前 LevelDB 的實(shí)現(xiàn)來說它最多只能有一個(gè)過濾器，那就是布隆過濾器。

布隆過濾器用于加快 SSTable 磁盤文件的 Key 定位效率。如果沒有布隆過濾器，它需要對 SSTable 進(jìn)行二分查找，Key 如果不在里面，就需要進(jìn)行多次 IO 讀才能確定，查完了才發(fā)現(xiàn)原來是一場空。布隆過濾器的作用就是避免在 Key 不存在的時(shí)候浪費(fèi) IO 操作。通過查詢布隆過濾器可以一次性知道 Key 有沒有可能在里面。

單個(gè)布隆過濾器中存放的是一個(gè)定長的位圖數(shù)組，該位圖數(shù)組中存放了若干個(gè) Key 的指紋信息。這若干個(gè) Key 來源于 DataBlock 中連續(xù)的一個(gè)范圍。FilterBlock 塊中存在多個(gè)連續(xù)的布隆過濾器位圖數(shù)組，每個(gè)數(shù)組負(fù)責(zé)指紋化 SSTable 中的一部分?jǐn)?shù)據(jù)。

struct FilterEntry {
  byte[] rawbits;
}

struct FilterBlock {
  FilterEntry[n] filterEntries;
  int32[n] filterEntryOffsets;
  int32 offsetArrayOffset;
  int8 baseLg;  // 分割系數(shù)
}

其中 baseLg 默認(rèn) 11，表示每隔 2K 字節(jié)（2<<11）的 DataBlock 數(shù)據(jù)（壓縮后），就開啟一個(gè)布隆過濾器來容納這一段數(shù)據(jù)中 Key 值的指紋。如果某個(gè) Value 值過大，以至于超出了 2K 字節(jié)，那么相應(yīng)的布隆過濾器里面就只有 1 個(gè) Key 值的指紋。每個(gè) Key 對應(yīng)的指紋空間在打開數(shù)據(jù)庫時(shí)指定。

// 每個(gè) Key 占用 10bit 存放指紋信息
options.SetFilterPolicy(levigo.NewBloomFilter(10))

這里的 2K 字節(jié)的間隔是嚴(yán)格的間隔，這樣才可以通過 DataBlock 的偏移量和大小來快速定位到相應(yīng)的布隆過濾器的位置 FilterOffset，再進(jìn)一步獲得相應(yīng)的布隆過濾器位圖數(shù)據(jù)。

至于為什么 LevelDB 的布隆過濾器數(shù)據(jù)不是整個(gè)塊而是分成一段一段的，這個(gè)原因筆者也沒有完全整明白。期待有讀者可以提供思路。

MetaIndexBlock 結(jié)構(gòu)

MetaIndexBlock 存儲了前面一系列 FilterBlock 的元信息，它在結(jié)構(gòu)上和 DataBlock 是一樣的，只不過里面 Entry 存儲的 Key 是帶固定前綴的過濾器名稱，Value 是對應(yīng)的 FilterBlock 在文件中的偏移量和長度。

key = "filter." + filterName
// value 定義了數(shù)據(jù)塊的位置和大小
struct BlockHandler {
  varint offset;
  varint size;
}

就目前的 LevelDB，這里面最多只有一個(gè) Entry，那么它的結(jié)構(gòu)非常簡單，如下圖所示

IndexBlock 結(jié)構(gòu)

它和 MetaIndexBlock 結(jié)構(gòu)一樣，也存儲了一系列鍵值對，每一個(gè)鍵值對存儲的是 DataBlock 的元信息，SSTable 中有幾個(gè) DataBlock，IndexBlock 中就有幾個(gè)鍵值對。鍵值對的 Key 是對應(yīng) DataBlock 內(nèi)部最大的 Key，Value 是 DataBlock 的偏移量和長度。不考慮 Key 之間的前綴共享，不考慮「重啟點(diǎn)」，它的結(jié)構(gòu)如下圖所示

SSTable in Apache Cassandra

SSTable 的組件：
在 Cassandra 中，SSTable 具有多個(gè)組件，這些組件存儲在多個(gè)文件中，如下所示。

LSM樹的Compact策略

從上面可以看出，Compact操作是十分關(guān)鍵的操作，否則SSTable數(shù)量會不斷膨脹。在Compact策略上，主要介紹兩種基本策略：size-tiered和leveled。

不過在介紹這兩種策略之前，先介紹三個(gè)比較重要的概念，事實(shí)上不同的策略就是圍繞這三個(gè)概念之間做出權(quán)衡和取舍。

1）讀放大:讀取數(shù)據(jù)時(shí)實(shí)際讀取的數(shù)據(jù)量大于真正的數(shù)據(jù)量。例如在LSM樹中需要先在MemTable查看當(dāng)前key是否存在，不存在繼續(xù)從SSTable中尋找。
2）寫放大:寫入數(shù)據(jù)時(shí)實(shí)際寫入的數(shù)據(jù)量大于真正的數(shù)據(jù)量。例如在LSM樹中寫入時(shí)可能觸發(fā)Compact操作，導(dǎo)致實(shí)際寫入的數(shù)據(jù)量遠(yuǎn)大于該key的數(shù)據(jù)量。
3）空間放大:數(shù)據(jù)實(shí)際占用的磁盤空間比數(shù)據(jù)的真正大小更多。上面提到的冗余存儲，對于一個(gè)key來說，只有最新的那條記錄是有效的，而之前的記錄都是可以被清理回收的。

下面先粗略看看RocksDB的讀寫流程，其實(shí)與HBase是很像的。

RocksDB讀寫簡介

直接上圖說明。

RocksDB的寫緩存（即LSM樹的最低一級）名為memtable，對應(yīng)HBase的MemStore；讀緩存名為block cache，對應(yīng)HBase的同名組件。

執(zhí)行寫操作時(shí)，先同時(shí)寫memtable與預(yù)寫日志W(wǎng)AL。memtable寫滿后會自動(dòng)轉(zhuǎn)換成不可變的（immutable）memtable，并flush到磁盤，形成L0級sstable文件。sstable即有序字符串表（sorted string table），其內(nèi)部存儲的數(shù)據(jù)是按key來排序的，后文將其簡稱為SST。

執(zhí)行讀操作時(shí)，會首先讀取內(nèi)存中的數(shù)據(jù)（根據(jù)局部性原理，剛寫入的數(shù)據(jù)很有可能被馬上讀?。碼ctive memtable→immutable memtable→block cache。如果內(nèi)存無法命中，就會遍歷L0層sstable來查找。如果仍未命中，就通過二分查找法在L1層及以上的sstable來定位對應(yīng)的key。

隨著sstable的不斷寫入，系統(tǒng)打開的文件就會越來越多，并且對于同一個(gè)key積累的數(shù)據(jù)改變（更新、刪除）操作也就越多。由于sstable是不可變的，為了減少文件數(shù)并及時(shí)清理無效數(shù)據(jù)，就要進(jìn)行compaction操作，將多個(gè)key區(qū)間有重合的sstable進(jìn)行合并。本文暫無法給出"compaction"這個(gè)詞的翻譯，個(gè)人認(rèn)為把它翻譯成“壓縮”（compression？）或者“合并”（merge？）都是片面的。

通過上面的簡介，我們會更加認(rèn)識到，LSM樹是一種以讀性能作為trade-off換取寫性能的結(jié)構(gòu)，并且RocksDB中的flush和compaction操作正是LSM思想的核心。下面來介紹LSM-based存儲中通用的兩種compaction策略，即size-tiered compaction和leveled compaction。

通用compaction策略

size-tiered compaction與空間放大

size-tiered compaction的思路非常直接：每層允許的SST文件最大數(shù)量都有個(gè)相同的閾值，隨著memtable不斷flush成SST，某層的SST數(shù)達(dá)到閾值時(shí)，就把該層所有SST全部合并成一個(gè)大的新SST，并放到較高一層去。下圖是閾值為4的示例。

size-tiered compaction的優(yōu)點(diǎn)是簡單且易于實(shí)現(xiàn)，并且SST數(shù)目少，定位到文件的速度快。當(dāng)然，單個(gè)SST的大小有可能會很大，較高的層級出現(xiàn)數(shù)百GB甚至TB級別的SST文件都是常見的。它的缺點(diǎn)是空間放大比較嚴(yán)重，下面詳細(xì)說說。

所謂空間放大（space amplification），就是指存儲引擎中的數(shù)據(jù)實(shí)際占用的磁盤空間比數(shù)據(jù)的真正大小偏多的情況。例如，數(shù)據(jù)的真正大小是10MB，但實(shí)際存儲時(shí)耗掉了25MB空間，那么空間放大因子（space amplification factor）就是2.5。

為什么會出現(xiàn)空間放大呢？很顯然，LSM-based存儲引擎中數(shù)據(jù)的增刪改都不是in-place的，而是需要等待compaction執(zhí)行到對應(yīng)的key才算完。也就是說，一個(gè)key可能會同時(shí)對應(yīng)多個(gè)value（刪除標(biāo)記算作特殊的value），而只有一個(gè)value是真正有效的，其余那些就算做空間放大。另外，在compaction過程中，原始數(shù)據(jù)在執(zhí)行完成之前是不能刪除的（防止出現(xiàn)意外無法恢復(fù)），所以同一份被compaction的數(shù)據(jù)最多可能膨脹成原來的兩倍，這也算作空間放大的范疇。

下面用Cassandra的size-tiered compaction策略舉兩個(gè)例子，以方便理解。每層SST個(gè)數(shù)的閾值仍然采用默認(rèn)值4。

• 以約3MB/s的速度持續(xù)插入新數(shù)據(jù)（保證unique key），時(shí)間與磁盤占用的曲線圖如下。

圖中清晰可見有不少毛刺，這就是compaction過程造成的空間放大。注意在2000s~2500s之間還有一個(gè)很高的尖峰，原數(shù)據(jù)量為6GB，但在一瞬間增長到了12GB，說明Cassandra在做大SST之間的compaction，大SST的缺陷就顯現(xiàn)出來了。盡管這只是暫時(shí)的，但是也要求我們必須預(yù)留出很多不必要的空閑空間，增加成本。

• 重復(fù)寫入一個(gè)400萬條數(shù)據(jù)的集合（約1.2GB大，保證unique key），共重復(fù)寫入15次來模擬數(shù)據(jù)更新，時(shí)間與磁盤占用的曲線圖如下。

這種情況更厲害，最高會占用多達(dá)9.3GB磁盤空間，放大因子為7.75。雖然中途也會觸發(fā)compaction，但是最低只能壓縮到3.5GB左右，仍然有近3倍的放大。這是因?yàn)橹貜?fù)key過多，就算每層compaction過后消除了本層的空間放大，但key重復(fù)的數(shù)據(jù)仍然存在于較低層中，始終有冗余。只有手動(dòng)觸發(fā)了full compaction（即圖中2500秒過后的最后一小段），才能完全消除空間放大，但我們也知道full compaction是極耗費(fèi)性能的。

接下來介紹leveled compaction，看看它是否能解決size-tiered compaction的空間放大問題。

leveled compaction與寫放大

leveled compaction的思路是：對于L1層及以上的數(shù)據(jù)，將size-tiered compaction中原本的大SST拆開，成為多個(gè)key互不相交的小SST的序列，這樣的序列叫做“run”。L0層是從memtable flush過來的新SST，該層各個(gè)SST的key是可以相交的，并且其數(shù)量閾值單獨(dú)控制（如4）。從L1層開始，每層都包含恰好一個(gè)run，并且run內(nèi)包含的數(shù)據(jù)量閾值呈指數(shù)增長。

下圖是假設(shè)從L1層開始，每個(gè)小SST的大小都相同（在實(shí)際操作中不會強(qiáng)制要求這點(diǎn)），且數(shù)據(jù)量閾值按10倍增長的示例。即L1最多可以有10個(gè)SST，L2最多可以有100個(gè)，以此類推。

隨著SST不斷寫入，L1的數(shù)據(jù)量會超過閾值。這時(shí)就會選擇L1中的至少一個(gè)SST，將其數(shù)據(jù)合并到L2層與其key有交集的那些文件中，并從L1刪除這些數(shù)據(jù)。仍然以上圖為例，一個(gè)L1層SST的key區(qū)間大致能夠?qū)?yīng)到10個(gè)L2層的SST，所以一次compaction會影響到11個(gè)文件。該次compaction完成后，L2的數(shù)據(jù)量又有可能超過閾值，進(jìn)而觸發(fā)L2到L3的compaction，如此往復(fù)，就可以完成Ln層到Ln+1層的compaction了。

可見，leveled compaction與size-tiered compaction相比，每次做compaction時(shí)不必再選取一層內(nèi)所有的數(shù)據(jù)，并且每層中SST的key區(qū)間都是不相交的，重復(fù)key減少了，所以很大程度上緩解了空間放大的問題。重復(fù)一遍上一節(jié)做的兩個(gè)實(shí)驗(yàn)，曲線圖分別如下。

持續(xù)寫入實(shí)驗(yàn)，尖峰消失了。

持續(xù)更新實(shí)驗(yàn)，磁盤占用量的峰值大幅降低，從原來的9.3GB縮減到了不到4GB。

但是魚與熊掌不可兼得，空間放大并不是唯一掣肘的因素。仍然以size-tiered compaction的第一個(gè)實(shí)驗(yàn)為例，寫入的總數(shù)據(jù)量約為9GB大，但是查看磁盤的實(shí)際寫入量，會發(fā)現(xiàn)寫入了50個(gè)G的數(shù)據(jù)。這就叫寫放大（write amplification）問題。

寫放大又是怎么產(chǎn)生的呢？下面的圖能夠說明。

可見，這是由compaction的本質(zhì)決定的：同一份數(shù)據(jù)會不斷地隨著compaction過程向更高的層級重復(fù)寫入，有多少層就會寫多少次。但是，我們的leveled compaction的寫放大要嚴(yán)重得多，同等條件下實(shí)際寫入量會達(dá)到110GB，是size-tiered compaction的兩倍有余。這是因?yàn)長n層SST在合并到Ln+1層時(shí)是一對多的，故重復(fù)寫入的次數(shù)會更多。在極端情況下，我們甚至可以觀測到數(shù)十倍的寫放大。

寫放大會帶來兩個(gè)風(fēng)險(xiǎn)：一是更多的磁盤帶寬耗費(fèi)在了無意義的寫操作上，會影響讀操作的效率；二是對于閃存存儲（SSD），會造成存儲介質(zhì)的壽命更快消耗，因?yàn)殚W存顆粒的擦寫次數(shù)是有限制的。在實(shí)際使用時(shí)，必須權(quán)衡好空間放大、寫放大、讀放大三者的優(yōu)先級。

RocksDB的混合compaction策略

由于上述兩種compaction策略都有各自的優(yōu)缺點(diǎn)，所以RocksDB在L1層及以上采用leveled compaction，而在L0層采用size-tiered compaction。下面分別來看看。

leveled compaction

當(dāng)L0層的文件數(shù)目達(dá)到level0_file_num_compaction_trigger閾值時(shí)，就會觸發(fā)L0層SST合并到L1。

L1層及以后的compaction過程完全符合前文所述的leveled compaction邏輯，如下圖所示，很容易理解。

多個(gè)compaction過程是可以并行進(jìn)行的，如下圖所示。最大并行數(shù)由max_background_compactions參數(shù)來指定。

前面說過，leveled compaction策略中每一層的數(shù)據(jù)量是有閾值的，那么在RocksDB中這個(gè)閾值該如何確定呢？需要分兩種情況來討論。

• 參數(shù)level_compaction_dynamic_level_bytes為false
  這種情況下，L1層的大小閾值直接由參數(shù)max_bytes_for_level_base決定，單位是字節(jié)。各層的大小閾值會滿足如下的遞推關(guān)系：

target_size(Lk+1) = target_size(Lk) * max_bytes_for_level_multiplier * max_bytes_for_level_multiplier_additional[k]

其中，max_bytes_for_level_multiplier是固定的倍數(shù)因子，max_bytes_for_level_multiplier_additional[k]是第k層對應(yīng)的可變倍數(shù)因子。舉個(gè)例子，假設(shè)max_bytes_for_level_base = 314572800，max_bytes_for_level_multiplier = 10，所有max_bytes_for_level_multiplier_additional[k]都為1，那么就會形成如下圖所示的各層閾值。

可見，這與上文講leveled compaction時(shí)的示例是一個(gè)意思。

• 參數(shù)level_compaction_dynamic_level_bytes為true
  這種情況比較特殊。最高一層的大小不設(shè)閾值限制，亦即target_size(Ln)就是Ln層的實(shí)際大小，而更低層的大小閾值會滿足如下的倒推關(guān)系：

target_size(Lk-1) = target_size(Lk) / max_bytes_for_level_multiplier

可見，max_bytes_for_level_multiplier的作用從乘法因子變成了除法因子。特別地，如果出現(xiàn)了target_size(Lk) < max_bytes_for_level_base / max_bytes_for_level_multiplier的情況，那么這一層及比它低的層就都不會再存儲任何數(shù)據(jù)。

舉個(gè)例子，假設(shè)現(xiàn)在有7層（包括L0），L6層已經(jīng)存儲了276GB的數(shù)據(jù)，并且max_bytes_for_level_base = 1073741824，max_bytes_for_level_multiplier = 10，那么就會形成如下圖所示的各層閾值，亦即L5~L1的閾值分別是27.6GB、2.76GB、0.276GB、0、0。

可見，有90%的數(shù)據(jù)都落在了最高一層，9%的數(shù)據(jù)落在了次高一層。由于每個(gè)run包含的key都是不重復(fù)的，所以這種情況比上一種更能減少空間放大。

universal compaction

universal compaction是RocksDB中size-tiered compaction的別名，專門用于L0層的compaction，因?yàn)長0層的SST的key區(qū)間是幾乎肯定有重合的。

前文已經(jīng)說過，當(dāng)L0層的文件數(shù)目達(dá)到level0_file_num_compaction_trigger閾值時(shí)，就會觸發(fā)L0層SST合并到L1。universal compaction還會檢查以下條件。

• 空間放大比例
  假設(shè)L0層現(xiàn)有的SST文件為(R1, R1, R2, ..., Rn)，其中R1是最新寫入的SST，Rn是較舊的SST。所謂空間放大比例，就是指R1~Rn-1文件的總大小除以Rn的大小，如果這個(gè)比值比max_size_amplification_percent / 100要大，那么就會將L0層所有SST做compaction。

• 相鄰文件大小比例
  有一個(gè)參數(shù)size_ratio用于控制相鄰文件大小比例的閾值。如果size(R2) / size(R1)的比值小于1 + size_ratio / 100，就表示R1和R2兩個(gè)SST可以做compaction。接下來繼續(xù)檢查size(R3) / size(R1 + R2)是否小于1 + size_ratio / 100，若仍滿足，就將R3也加入待compaction的SST里來。如此往復(fù)，直到不再滿足上述比例條件為止。

當(dāng)然，如果上述兩個(gè)條件都沒能觸發(fā)compaction，該策略就會線性地從R1開始合并，直到L0層的文件數(shù)目小于level0_file_num_compaction_trigger閾值。

重新審視 B+ tree 與 LSM tree

作為最廣泛使用的索引數(shù)據(jù)結(jié)構(gòu)之一，B ⁺ -tree [3] 為當(dāng)今幾乎所有的關(guān)系數(shù)據(jù)庫管理系統(tǒng) (RDBM) 提供支持。最近，日志結(jié)構(gòu)合并樹（LSM-tree）[5] 作為 B ⁺ -tree的競爭者引起了極大的興趣，因?yàn)樗臄?shù)據(jù)結(jié)構(gòu)可以實(shí)現(xiàn)更好的存儲空間使用效率和更低的寫入放大。由于這兩個(gè)廣為人知的優(yōu)勢，LSM-trees 已被許多 NoSQL 產(chǎn)品（例如，Google 的 BigTable、Cassandra 和 RocksDB）采用。我們研究了 LSM-tree 相對于 B ⁺ -tree的這兩個(gè)優(yōu)勢是否仍然存在于具有內(nèi)置透明壓縮的新存儲硬件的存在下。

透明壓縮

基于硬件的數(shù)據(jù)壓縮能力在現(xiàn)代存儲設(shè)備和基礎(chǔ)設(shè)施上變得越來越廣泛，例如，具有內(nèi)置透明壓縮功能的商用固態(tài)驅(qū)動(dòng)器 (SSD) 正在興起 [8]，大多數(shù)全閃存陣列 (AFA) [2 , 4, 6] 透明地壓縮他們的數(shù)據(jù)，并且云供應(yīng)商已經(jīng)開始將基于硬件的壓縮能力集成到他們的存儲基礎(chǔ)設(shè)施中（例如，Microsoft Corsia [1]）。圖 1 展示了內(nèi)置透明壓縮的 SSD：其控制器芯片對 I/O 路徑上的每個(gè) 4KB LBA（邏輯塊地址）塊進(jìn)行壓縮或解壓縮，這對于正常訪問 SSD 的主機(jī)是透明的塊設(shè)備通過標(biāo)準(zhǔn)接口（例如，NVMe）。

為了讓主機(jī)實(shí)現(xiàn)存儲內(nèi)透明壓縮的好處，此類 SSD 可能會暴露比其內(nèi)部物理存儲容量大得多的稀疏 LBA 空間。此外，由于可以高度壓縮重復(fù)的數(shù)據(jù)模式（例如，全零或全一），主機(jī)可以在每個(gè) 4KB LBA 塊中存儲稀疏數(shù)據(jù)內(nèi)容（即任意數(shù)量的有效數(shù)據(jù)），而不會浪費(fèi)物理存儲空間，如圖 2 所示。因此，當(dāng)使用內(nèi)置透明壓縮的 SSD 時(shí)，我們可以在不犧牲真實(shí)物理存儲成本的情況下采用稀疏的磁盤數(shù)據(jù)結(jié)構(gòu)，這為數(shù)據(jù)管理系統(tǒng)創(chuàng)造了新的設(shè)計(jì)空間范圍 [ 9]。

B+ 樹與 LSM 樹：存儲成本

^{我們首先研究 B +} -tree 和 LSM-tree的存儲成本比較。B ⁺ -tree 以頁為單位管理其數(shù)據(jù)存儲。為了降低數(shù)據(jù)存儲成本，B ⁺ -tree 可以應(yīng)用塊壓縮算法（例如，lz4、zlib 和 ZSTD）來壓縮每個(gè)存儲頁面（例如，MySQL 和 MongoDB/WiredTiger 中的頁面壓縮功能）。除了明顯的 CPU 開銷外，B ⁺ -tree 頁面壓縮還會因?yàn)?4KB-alignment 約束而遭受壓縮比損失，這可以解釋如下： 存儲設(shè)備以 4 KB LBA 塊為單位服務(wù) I/O 請求。結(jié)果，每個(gè) B ⁺-樹頁面（無論壓縮或未壓縮）必須完全占據(jù)存儲設(shè)備上的一個(gè)或多個(gè) 4 KB LBA 塊。當(dāng) B ⁺ -tree 應(yīng)用頁面壓縮時(shí)，4KB 對齊約束可能會導(dǎo)致明顯的存儲空間浪費(fèi)。這可以在圖3中進(jìn)一步說明：假設(shè)一個(gè)16KB的B ⁺ -tree頁面被壓縮到5KB，壓縮后的頁面必須占用存儲設(shè)備上的兩個(gè)LBA塊（即8KB），浪費(fèi)了3KB的存儲空間。因此，由于 4 KB-alignment 約束帶來的 CPU 開銷和存儲空間浪費(fèi)，B ⁺ -tree 頁面壓縮在生產(chǎn)環(huán)境中并沒有被廣泛使用。同時(shí)，在隨機(jī)寫入的工作負(fù)載下，B ⁺ -tree 頁面往往只有 50%～80% 滿 [3]。因此，B ⁺-tree 通常具有較低的存儲空間使用效率。

與 B ⁺ -tree 相比，LSM-tree 具有更高的存儲空間使用效率，可以解釋如下： 一個(gè) LSM-tree 由多個(gè)不可變的 SSTable 文件組成，每個(gè)文件包含多個(gè)塊（典型塊大小為 4 KB ）。由于是不可變的，所有塊都可以 100% 填滿（即，完全填滿用戶數(shù)據(jù)）。在應(yīng)用壓縮以降低存儲成本時(shí)，LSM-tree 單獨(dú)壓縮每個(gè)塊并將壓縮塊緊密地打包在 SSTable 文件中（即，壓縮塊不受 4 KB 對齊約束）。出于演示的目的，我們使用 RocksDB 和 WiredTiger 作為 LSM-tree 和 B ⁺ -tree 的代表，并在 150 GB 數(shù)據(jù)集上運(yùn)行具有 128 字節(jié)記錄大小的隨機(jī)只寫工作負(fù)載。對于 WiredTiger，我們設(shè)置它的 B⁺ - 樹葉頁面大小為 8 KB。結(jié)果顯示，RocksDB 和 WiredTiger 分別在存儲設(shè)備上占用了 218GB 和 280GB。它清楚地展示了 LSM-tree 更好的存儲空間使用效率。

然而，當(dāng)在內(nèi)置透明壓縮的存儲硬件上運(yùn)行時(shí)，LSM-tree 與 B ⁺ -tree 的存儲成本優(yōu)勢將大大減弱。如圖 4 所示，只要 B ⁺ - 樹頁面用全零等高度可壓縮的內(nèi)容填充未使用的空間，存儲內(nèi)透明壓縮將消除不太緊湊的 B ⁺ -樹頁面數(shù)據(jù)結(jié)構(gòu)的存儲成本損失. 此外，in-storage 透明壓縮不受 4 KB-alignment 約束，即所有壓縮數(shù)據(jù)塊都緊密打包在 NAND 閃存中，如圖 4 所示。因此，in-storage 透明壓縮無縫地緩解了存儲B ⁺的使用效率缺點(diǎn)^{-tree，縮小了 B +} -tree 和 LSM-tree之間的存儲成本差距。例如，我們在與上述配置相同的內(nèi)置透明壓縮 [8] 的 SSD 上運(yùn)行 RocksDB 和 WiredTiger，結(jié)果表明，存儲內(nèi)透明壓縮可以將 RocksDB 的存儲成本從 218 GB 降低到 129 GB ，并將WiredTiger的存儲成本從280GB降低到104GB。SSD 可以在 WiredTiger 上實(shí)現(xiàn)更高的壓縮比，因?yàn)槠洳惶o湊的 B ⁺樹頁面數(shù)據(jù)結(jié)構(gòu)導(dǎo)致更高的數(shù)據(jù)壓縮率。RocksDB 具有較高的壓縮后存儲成本主要是因?yàn)槠涔逃械目臻g放大。結(jié)果表明，存儲內(nèi)透明壓縮有效縮小了 B ^{+之間的存儲成本差距}-tree 和 LSM-tree。

B+ 樹 vs. LSM-tree：寫放大

在寫入放大方面比較 B ⁺ -tree 和 LSM-tree 更加復(fù)雜，并且很大程度上取決于運(yùn)行時(shí)工作負(fù)載的特征。當(dāng) (i) B ⁺ -tree 具有非常大的高速緩存內(nèi)存（例如，足以容納大部分或整個(gè)數(shù)據(jù)集）并使用非常大的重做日志文件時(shí)，B ⁺ -tree的寫入放大率可能比 LSM-tree 低得多，或 (ii) 平均記錄大小很大（例如，512 B 及以上）。這解釋了為什么 LSM-tree 通常被用于針對平均記錄大小相對較小的內(nèi)存數(shù)據(jù)集大得多的系統(tǒng)。

我們感興趣的是，在那些對 LSM-tree 友好的工作負(fù)載（即，記錄大小大于內(nèi)存的數(shù)據(jù)集）下，存儲內(nèi)透明壓縮是否有助于縮小 B ⁺ -tree 與 LSM-tree 的寫入放大差距。 在這種情況下，B ⁺ -tree 的寫放大主要是由臟頁刷新引起的寫放大。例如，如果一個(gè) B ⁺ -tree 在一個(gè) 8 KB 頁內(nèi)修改了一條 32 B 的記錄，然后將該臟頁從內(nèi)存刷新到存儲，則寫入放大將為 8 KB/32 B=256。即使存儲硬件可以將頁面壓縮為 4:1（因此將寫入放大減少到 64），它仍然比 LSM-tree 的典型寫入放大（例如~20）大得多。因此，關(guān)閉 B⁺ -tree 與 LSM-tree 寫入放大差距，必須修改B ⁺ -tree 實(shí)現(xiàn)以更好地利用存儲內(nèi)透明壓縮。我們在下面提出一個(gè)解決方案。

這是由一個(gè)簡單的觀察引起的：對于 B ⁺ -樹頁面，讓 Δ 表示其內(nèi)存中圖像和存儲圖像之間的差異。如果差異顯著小于頁面大小，我們可以通過記錄頁面修改Δ來大大減少寫入放大，而不是將整個(gè)內(nèi)存頁面映像寫入存儲設(shè)備。不幸的是，當(dāng)一個(gè) B ⁺-tree 在沒有內(nèi)置透明壓縮的普通存儲設(shè)備上運(yùn)行，由于顯著的操作開銷，這種方法不實(shí)用：給定 4 KB 塊 IO 接口，我們必須將來自不同頁面的多個(gè) Δ 合并為一個(gè) 4 KB LBA 塊，以便實(shí)現(xiàn)寫放大減少。為了提高增益，我們應(yīng)該對每個(gè)頁面多次應(yīng)用頁面修改日志記錄，然后再重置此過程以構(gòu)建最新的存儲頁面圖像。因此，與同一頁面相關(guān)聯(lián)的多個(gè)Δ將分布在存儲設(shè)備上的多個(gè) 4 KB 塊上，但這會增加數(shù)據(jù)管理的復(fù)雜性和頁面讀取延遲。結(jié)果，這個(gè)簡單的設(shè)計(jì)理念并沒有被現(xiàn)實(shí)世界的B ^+使用公開文獻(xiàn)中報(bào)告的樹實(shí)現(xiàn)。

首次內(nèi)置透明壓縮的存儲硬件使上述簡單的想法切實(shí)可行。通過應(yīng)用這種存儲硬件支持的稀疏數(shù)據(jù)結(jié)構(gòu)，我們不再需要將來自不同頁面的多個(gè) Δ 合并到同一個(gè) 4 KB LBA 塊中。如圖 5 所示，每個(gè) B ⁺ -tree 頁面關(guān)聯(lián)一個(gè)專用的 4 KB LBA 塊作為其修改日志空間來存儲自己的 Δ，稱為本地化頁面修改日志。4KB I/O接口下，實(shí)現(xiàn)對每頁建議的頁面修改日志，B ⁺-tree 將 D = [Δ,O]（其中 O 表示全零向量，|D| 為 4 KB）寫入與頁面關(guān)聯(lián)的 4 KB 修改日志塊。在存儲設(shè)備內(nèi)部，D 中的所有零都將被壓縮掉，僅物理存儲 Δ 的壓縮版本。與傳統(tǒng)做法相比，這顯然導(dǎo)致寫入放大要低得多，傳統(tǒng)做法是，無論頁面中有多少字節(jié)真正改變，每個(gè)臟頁都完全寫入存儲。^{通過為每個(gè) B +}樹頁面專用一個(gè) 4 KB 修改日志空間，我們不會產(chǎn)生額外的 B ⁺樹存儲管理復(fù)雜性。當(dāng)然，這種設(shè)計(jì)方法會受到較長的頁面加載延遲的影響，幸運(yùn)的是，這并不重要，原因有兩個(gè)：（i）一個(gè) B ⁺-tree 只需要額外讀取一個(gè)與 LBA 空間中的頁面相鄰的 4 KB LBA 塊。因此，B ⁺ -tree 只向存儲設(shè)備發(fā)出單個(gè)讀取請求。(ii) 與從存儲設(shè)備獲取數(shù)據(jù)相比，從 Δ 構(gòu)建更新的內(nèi)存頁面所需的時(shí)間要少得多。

定量結(jié)果

出于演示目的，我們實(shí)現(xiàn)了一個(gè) B ⁺樹，它結(jié)合了上述用于減少寫入放大的方法。生成的實(shí)現(xiàn)稱為 B ^-樹。為了比較，RocksDB 和 WiredTiger 被用作 LSM-tree 和 normal B ^+的代表-樹。在所有實(shí)驗(yàn)中，每條記錄都是通過將其一半內(nèi)容填充為全零而另一半內(nèi)容填充為隨機(jī)字節(jié)來生成的，以模擬運(yùn)行時(shí)數(shù)據(jù)內(nèi)容的可壓縮性。圖 6 顯示了在 500 GB 數(shù)據(jù)集下測量的寫入放大，其中所有情況都使用 15 GB 緩存。在每個(gè)實(shí)驗(yàn)中，我們使用 1、2、4、8 或 16 個(gè)客戶端線程來覆蓋各種運(yùn)行時(shí)工作負(fù)載并發(fā)。與 RocksDB 相比，WiredTiger 的寫入放大要大得多，而 B ^-- tree 基本上可以關(guān)閉 B ⁺-tree 與 LSM-tree 寫入放大差距。例如，在32B記錄大小和4個(gè)客戶端線程的情況下，RocksDB的寫放大為38，而WiredTiger的寫放大分別為8 KB頁面大小下268和16 KB頁面大小下530，為7.1比 RocksDB 大 x 和 13.9 倍。相比之下，B ^- tree 的寫入放大在 8 KB 頁面大小下為 28（僅為 RocksDB 寫入放大的 73.7%），在 1 6KB 頁面大小下為 36（與 RocksDB 幾乎相同）。

我們進(jìn)一步比較了 LBA 空間上的邏輯存儲使用量（即存儲內(nèi)壓縮之前）和閃存的物理使用量（即存儲內(nèi)壓縮之后）的總存儲使用量。使用相同的 500 GB 數(shù)據(jù)集，RocksDB、WiredTiger 和 B ^- tree 的邏輯存儲使用量分別為 728 GB、934 GB 和 1,548 GB。^{入庫壓縮后，RocksDB、WiredTiger、B -} tree的物理閃存使用量分別為431GB、347GB、452GB 。^{由于 LSM-tree 的數(shù)據(jù)結(jié)構(gòu)比 B +} -tree更緊湊，因此 RocksDB 的邏輯存儲使用量比其他兩種更小。由于 B ^--tree 為每一頁分配一個(gè) 4KB 的塊，以實(shí)現(xiàn)本地化的修改日志，其邏輯存儲使用量遠(yuǎn)大于 WiredTiger。WiredTiger 消耗的物理閃存容量比 RocksDB（因?yàn)?LSM-tree 的空間放大）和 B ^- tree（因?yàn)轫撁嫘薷娜罩居涗浺鸬拇鎯﹂_銷）要少。由于頁面修改日志造成的存儲空間開銷，B ^- tree 的物理存儲使用量比 RocksDB 略大。例如，RocksDB 的物理存儲使用量為 431 GB，而 B ^-- tree 的物理存儲使用量為 452 GB，僅比 RocksDB 大 5% 左右。

最后，圖 7 顯示了在三種不同工作負(fù)載下測量的速度性能：
(a) 隨機(jī)點(diǎn)讀取，(b) 隨機(jī)范圍掃描，和 (c) 隨機(jī)點(diǎn)寫入。

如圖 7(a) 所示，普通的 B ⁺ -tree（即 WiredTiger）具有最好的點(diǎn)讀 TPS（每秒事務(wù)數(shù)）性能，而 RocksDB 和 B ^-- tree 實(shí)現(xiàn)了幾乎相同的隨機(jī)點(diǎn)讀 TPS 性能。比如在16個(gè)客戶端線程下，WiredTiger可以達(dá)到71K TPS，而RocksDB qnd B ^-- tree可以達(dá)到57K TPS，比WiredTiger低19.7%左右。

圖 7（b）顯示了運(yùn)行隨機(jī)范圍掃描查詢時(shí)測量的 TPS，其中每次范圍掃描覆蓋 100 個(gè)連續(xù)記錄。與隨機(jī)點(diǎn)讀取的情況相比，WiredTiger 和 B ^--tree 在范圍掃描吞吐量性能方面的差異明顯較小。這是因?yàn)?B ^- tree 的兩個(gè)開銷（即，獲取額外的 4KB 和內(nèi)存中的頁面重建）可以在每次范圍掃描覆蓋的記錄中分?jǐn)?。相比之下，RocksDB 的范圍掃描吞吐量性能明顯低于其他兩個(gè)，因?yàn)榉秶鷴呙枵{(diào)用 LSM-tree 中所有級別的讀取，導(dǎo)致高讀取放大。

圖 7（c）顯示了隨機(jī)點(diǎn)寫入工作負(fù)載下的性能。^{B +} -tree 和 LSM-tree的隨機(jī)寫入速度性能從根本上受到寫入放大的限制。因此，通過顯著降低寫放大，B ^- -樹可以實(shí)現(xiàn)更高的寫入速度性能。如圖 7(C) 所示，B ^-- tree 的寫入吞吐量比 RocksDB 高 19% ，比 WiredTiger 高約 2.1 倍。 我們的 FAST'22 論文 [7] 提供了更全面的實(shí)驗(yàn)結(jié)果。

結(jié)論

Modern storage hardware with built-in transparent compression allows data management systems to employ sparse on-disk data structure without sacrificing the true physical data storage cost. This opens a new but largely unexplored spectrum of opportunities to innovate data management software design. As one small step towards exploring this design spectrum, we showed that B+-tree could nicely leverage such modern storage hardware to close the gap with its recent contender LSM-trees in terms of storage cost and write amplification. This work suggests that the arrival of such modern storage hardware warrants a revisit on the role and comparison of B+-tree and LSM-tree in future data management systems.

具有內(nèi)置透明壓縮的現(xiàn)代存儲硬件允許數(shù)據(jù)管理系統(tǒng)采用稀疏的磁盤數(shù)據(jù)結(jié)構(gòu)，而不會犧牲真正的物理數(shù)據(jù)存儲成本。這為創(chuàng)新數(shù)據(jù)管理軟件設(shè)計(jì)開辟了一個(gè)新的但很大程度上尚未探索的機(jī)會范圍。作為探索這一設(shè)計(jì)范圍的一小步，我們展示了 B ⁺樹可以很好地利用這種現(xiàn)代存儲硬件來縮小與最近的競爭者 LSM 樹在存儲成本和寫入放大方面的差距。這項(xiàng)工作表明，這種現(xiàn)代存儲硬件的出現(xiàn)需要重新審視 B ⁺ -tree 和 LSM-tree 在未來數(shù)據(jù)管理系統(tǒng)中的作用和比較。

References:

[1] D. Chiou, E. Chung, and S. Carrie. (Cloud) Acceleration at Microsoft. Tutorial at Hot Chips, 2019

[2] Dell EMC PowerMax. https://delltechnologies.com/

[3] G. Graefe and H. Kuno. Modern B-tree techniques. In IEEE International Conference on Data Engineering, 2011

[4] HPE Nimble Storage. https://www.hpe.com/

[5] P. O’Neil, E. Cheng, D. Gawlick, and E. O’Neil. The log-structured merge-tree (LSM-tree). Acta Informatica, 1996

[6] Pure Storage FlashBlade. https://purestorage.com/

[7] Y. Qiao, X. Chen, N. Zheng, J. Li, Y. Liu, and T. Zhang. Closing the B-tree vs. LSM-tree Write Amplification Gap on Modern Storage Hardware with Built-in Transparent Compression. In USENIX Conference on File and Storage Technologies (FAST), 2022

[8] ScaleFlux Computational Storage. http://scaleflux.com

[9] N. Zheng, X. Chen, J. Li, Q. Wu, Y. Liu, Y. Peng, F. Sun, H. Zhong, and T. Zhang. Re-think data management software design upon the arrival of storage hardware with built-in transparent compression. In USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage), 2020