一文科普 RocksDB 工作原理

導語

近幾年,RocksDB 的採用率急速上升,儼然成爲內嵌型鍵值存儲(以下簡稱 kv 存儲)的不二之選。

目前,RocksDB 在 Meta、Microsoft、Netflix 和 Uber 等公司的生產環境上運行。在 Meta,RocksDB 作爲 MySQL 部署的存儲引擎,爲分佈式圖數據庫(TAO)提供支持存儲服務。

大型科技公司並非 RocksDB 的僅有用戶,像是 CockroachDB、Yugabyte、PingCAP 和 Rockset 等多個初創企業都構建在 RocksDB 基礎之上。

我在 Datadog 工作了 4 年時間,在生產環境中構建和運行了一系列基於 RocksDB 的服務。本文將就 RocksDB 的工作原理進行概要式講解。

RocksDB 是什麼

RocksDB 是一種可持久化的、內嵌型 kv 存儲。它是爲了存儲大量的 key 及其對應 value 設計出來的數據庫。可以基於這種簡單 kv 數據模型來構建倒排索引、文檔數據庫、SQL 數據庫、緩存系統和消息代理等複雜系統。

RocksDB 是 2012 年從 Google 的 LevelDB fork 出來的分支,並針對跑在 SSD 上的服務器進行了優化。目前,RocksDB 由 Meta 開發和維護。

RocksDB 使用 C++ 編寫而成,因此除了支持 C 和 C++ 之外,還能通過 С binding 的形式嵌入到使用其他語言編寫的應用中,例如 Rust、Go 或 Java。

如果你之前用過 SQLite,你肯定知道什麼是內嵌式數據庫。在數據庫領域,特別是在 RocksDB 的上下文中,“內嵌” 意味着:

如有必要,需依賴於應用層來實現上述功能。

RocksDB 以 kv 對集合的形式存儲數據, key 和 value 是任意長度的字節數組(byte array),因此都是沒有類型的。RocksDB 提供了很少的幾個用於修改 kv 集合的函數底層接口:

通過點查來獲取 key 所關聯的 value:

通過迭代器可以進行範圍掃描——找到特定的 key,並按順序訪問該 key 後續的鍵值對:

Log-structured merge-tree

RocksDB 的核心數據結構被稱爲日誌結構合併樹 (LSM-Tree)。它是一種樹形的數據結構,由多個層級組成,每層的數據按 key 有序。LSM-Tree 主要設計用來應對寫入密集型工作負載,並於 1996 年在同名論文 The Log-Structured Merge-Tree (LSM-Tree) 被大家所知。

LSM-Tree 的最高層保存在內存中,包含最近寫入的數據。其他較低層級的數據存儲在磁盤上,層數編號從 0 到 N 。第 0 層 L0 存儲從內存移動到磁盤上的數據,第 1 層及以下層級則存儲更老的數據。通常某層的下個層級在數據量上會比該層大一個數量級,當某層數據量變得過大時,會合併到下一層。

注:雖然本文主要討論 RocksDB,但涉及 LSM-Tree 的概念適用於大多數底層採用此技術實現的數據庫(例如 Bigtable、HBase、Cassandra、ScyllaDB、LevelDB 和 MongoDB WiredTiger)

爲了更好地理解 LSM-Tree 的工作原理,下面我們將着重剖析它的寫 / 讀路徑。

寫路徑

MemTable

LSM-Tree 的頂層被稱爲 MemTable。MemTable 是一個內存緩衝區,在鍵值對寫入磁盤之前,Memtable 會緩存住這些鍵值對。所有插入和更新操作都會過 MemTable。當然也包括刪除操作:不過,在 RocksDB 中,並不會直接原地修改鍵值對,而是通過插入墓碑記錄(tombstone )來進行標記刪除。

MemTable 具有可配置的字節數限制。當一個 MemTable 變滿時,就會切到一個新的 MemTable,同時原 MemTable 變爲不可修改狀態。

注:MemTable 的默認大小爲 64 MB。

現在,我們往數據庫寫入點 key 看看:

db.put("chipmunk""1")
db.put("cat""2")
db.put("raccoon""3")
db.put("dog""4")

MemTable:內存中的一個有序查找表

如上圖所示,MemTable 中的鍵值對是按 key 有序排列的。儘管 chipmunk 是最先插入的,但由於 MemTable 是按 key 有序的,因此 chipmunk 排在 cat 之後。這種排序對於範圍掃描是必須的,此外,稍後我會詳細介紹,它也會讓某些操作更加高效。

預寫日誌

無論是在進程意外崩潰退出還是計劃內重啓時,其內存中的數據都會丟失。爲了防止數據丟失,保證數據的持久化,除了 MemTable 之外,RocksDB 會將所有更新寫入到磁盤上的預寫日誌(WAL,Write-ahead log)中。這樣,在重啓後,數據庫可以回放日誌,進而恢復 MemTable 的原始狀態。

WAL 是一個只允許追加的文件,包含一組更改記錄序列。每個記錄包含鍵值對、記錄類型(Put / Merge / Delete)和校驗和(checksum)。與 MemTable 不同,在 WAL 中,記錄不按 key 有序,而是按照請求到來的順序被追加到 WAL 中。

WAL:爲了應對宕機的寫前日誌

Flush

RocksDB 使用一個專門的後臺線程定期地把不可變的 MemTable 從內存持久化到磁盤。一旦刷盤(flush)完成,不可變的 MemTable 和相應的 WAL 就會被丟棄。RocksDB 開始寫入新的 WAL、MemTable。每次刷盤都會在 L0 層上產生一個新的 SST 文件。該文件一旦寫入磁盤後,就不再會修改。

RocksDB 的 MemTable 的默認基於跳錶實現。該數據結構是一個具有額外採樣層的鏈表,從而允許快速、有序地查詢和插入數據。有序性使得 MemTable 刷盤時更高效,因爲可以直接按順序迭代鍵值對順序寫入磁盤。將隨機寫變爲順序寫是 LSM-Tree 的核心設計之一

Flush:將不可變內存表刷到磁盤的過程

注:RocksDB 高度可配,因此你可以給 MemTable 配置其他的實現方案,RocksDB 中大部分組件都是如此。在其他的一些基於 LSM 實現的數據庫中,使用自平衡二叉搜索樹來實現 MemTable 並不鮮見

SST

SST 文件包括從 MemTable 刷盤而來的鍵值對,並且使用一種對查詢友好的數據格式來存儲。SST 是 Static Sorted Table 的縮寫(其他數據庫中也稱爲 Sorted String Table)。它是一種基於塊( block) 的文件格式,會將數據切成固定大小的塊(默認爲 4KB)進行存儲。RocksDB 支持各種壓縮 SST 文件的壓縮算法,例如 Zlib、BZ2、Snappy、LZ4 或 ZSTD 算法。與 WAL 的記錄類似,每個數據塊中都包含用於檢測數據是否損壞的校驗和。每次從磁盤讀取數據時,RocksDB 都會使用這些校驗和進行校驗。

SST 文件由幾個部分組成:首先是數據部分,包含一系列有序的鍵值對。key 的有序性可以讓我們對 其進行增量編碼,也即,對於相鄰的 key ,我們可以只存其差值而非整個 key。

儘管 SST 中的 kv 對是有序的,我們也並非總能進行二分查找,尤其是數據塊在壓縮過後,會使得查找很低效。RocksDB 使用索引來優化查詢,存儲在緊鄰數據塊之後的索引塊。Index 會把每個 block 數據中最後一個 key 映射到它在磁盤上的對應偏移量。同樣地,index 中的 key 也是有序的,因此我們可以通過二分搜索快速找到某個 key。

SST: 帶有索引的外存查找文件

例如,我們在查找 lynx,索引會告訴我們這個鍵值對可能在 block 2,因爲按照字典序,lynxchipmunk 之後,但在 raccoon 之前。

但其實 SST 文件中並沒有 lynx,但我們仍然需要從磁盤加載 block 以進行搜索。RocksDB 支持啓用布隆過濾器,一種具有高效空間利用率的概率性數據結構,可以用來檢測某個元素是否在集合中。布隆過濾器保存在 SST 文件中過濾器部分,以便能夠快速確定某個 key 不在 SST 中(從而省去摸硬盤上的數據塊的開銷)。

此外,SST 還有其他幾個不太有趣的部分,比如元數據部分。

Compaction

到現在爲止,一個功能完備的鍵值存儲引擎講完了。但如果這樣直接上生產環境,會有一些問題:空間放大(space amplifications)和讀放大(read amplifications)。空間放大是存儲數據所用實際空間與邏輯上數據大小的比值。假設一個數據庫需要 2 MB 磁盤空間來存儲邏輯上的 1 MB 大小的鍵值對是,那麼它的空間放大率是 2。類似地,讀放大用來衡量用戶執行一次邏輯上的讀操作,系統內所需進行的實際 IO 次數。作爲一個小練習,你可以嘗試推演下什麼是寫放大。

現在,讓我們向數據庫添加更多 key 並刪除當中的一些 key:

db.delete("chipmunk")
db.put("cat""5")
db.put("raccoon""6")
db.put("zebra""7")
// Flush triggers
db.delete("raccoon")
db.put("cat""8")
db.put("zebra""9")
db.put("duck""10")

隨着我們的不斷寫入,MemTable 不斷被刷到磁盤,L0 上的 SST 文件數量也在增長:

RocksDB 引入了壓實( Compaction )機制,可以降低空間放大和讀放大,但代價是更高的寫放大。Compaction 會將某層的 SST 文件同下一層的 SST 文件合併,並在這個過程中丟棄已刪除和被覆蓋的無效 key。Compaction 會在後臺專用的線程池中運行,從而保證了 RocksDB 可以在做 Compaction 時能夠正常處理用戶的讀寫請求。

Leveled Compaction 是 RocksDB 中的默認 Compaction 策略。使用 Leveled Compaction,L0 層中的不同 SST 文件鍵範圍會重疊。L1 層及以下層會被組織爲包含多個 SST 文件的序列,並保證同層級內的所有 SST 在鍵範圍上沒有交疊,且 SST 文件之間有序。Compaction 時,會選擇性地將某層的 SST 文件與下一層的 key 範圍有重疊 SST 文件進行合併。

舉例來說,如下圖所示,在 L0 到 L1 層進行 Compaction 時,如果 L0 上的輸入文件覆蓋整個鍵範圍,此時就需要對所有 L0 和 L1 層的文件進行 Compaction。

而像是下面的這種 L1 和 L2 層的 Compaction,L1 層的輸入文件只與 L2 層的兩個 SST 文件重疊,因此,只需要對部分文件進行 Compaction 即可。

當 L0 層上的 SST 文件數量達到一定閾值(默認爲 4)時,將觸發 Compaction。對於 L1 層及以下層級,當整個層級的 SST 文件總大小超過配置的目標大小時,會觸發 Compaction 。當這種情況發生時,可能會觸發 L1 到 L2 層的 Compaction。從而,從 L0 到 L1 層的 Compaction 可能會引發一直到最底層級聯 Compaction。在 Compaction 完成之後,RocksDB 會更新元數據並從磁盤中刪除 已經被 Compcated 過的文件。

注:RocksDB 提供了不同 Compaction 策略來在空間、讀放大和寫放大之間進行權衡

看到這裏,你還記得上文提過 SST 文件中的 key 是有序的嗎?有序性允許使用 K 路歸併算法逐步合併多個 SST 文件。K 路歸併是兩路歸併的泛化版本,其工作方式類似於歸併排序的歸併階段。

讀路徑

使用持久化在磁盤上不可變的 SST 文件,讀路徑要比寫路徑簡單很多。要找尋某個 key,只需自頂而下遍歷 LSM—Tree。從 MemTable 開始,下探到 L0,然後繼續向更低層級查找,直到找到該 key 或者檢查完所有 SST 文件爲止。

以下是查找步驟:

  1. 檢索 MemTable。

  2. 檢索不可變 MemTables。

  3. 搜索最近 flush 過的 L0 層中的所有 SST 文件。

  4. 對於 L1 層及以下層級,首先找到可能包含該 key 的單個 SST 文件,然後在文件內進行搜索。

搜索 SST 文件涉及:

  1. (可選)探測布隆過濾器。

  2. 查找 index 來找到可能包含這個 key 的 block 所在位置。

  3. 讀取 block 文件並嘗試在其中找到 key。

這就是全部所需步驟了!看看這個 LSM-Tree:

!https://-website-cn.oss-cn-hangzhou.aliyuncs.com/-blog/how-rocksdb-works/rocksdb-lookup.png

根據待查找的 key 的具體情況,查找過程可能在上面任意步驟提前終止。例如,在搜索 MemTable 後,key “cat” 或 “chipmunk” 的查找工作會立即結束。查找 “raccoon” 則需要搜索 L1 爲止,而查找根本不存在的 “manul” 則需要搜索整個樹。

Merge

RocksDB 還提供了一個同時涉及讀路徑和寫路徑的功能:合併(merge)操作。假設,你在數據庫中存了一個整數列表,偶爾需要擴展該列表。爲了修改列表,你需要從數據庫中讀取其現有值,在內存中更新該列表,最後把更新後的值寫回數據庫。

上面整個操作序列被稱爲 “Read-Modify-Write” 循環:

db = open_db(path)

// 讀取 Read
old_val = db.get(key) // RocksDB stores keys and values as byte arrays. We need to deserialize the value to turn it into a list.
old_list = deserialize_list(old_val) // old_list: [1, 2, 3]

// 修改 Modify
new_list = old_list.extend([4, 5, 6]) // new_list: [1, 2, 3, 4, 5, 6]
new_val = serialize_list(new_list)

// 寫回 Write
db.put(key, new_val)

db.get(key) // deserialized value: [1, 2, 3, 4, 5, 6]

上面這種方式能達到目的,但存在一些缺陷:

除了 Put 和 Delete 寫操作之外,RocksDB 還支持第三種寫操作 MergeMerge 操作需要提供 Merge Operator——一個用戶定義函數,負責將增量更新組合成單個值:

funcmerge_operator(existing_val, updates) {
        combined_list = deserialize_list(existing_val)
        for op in updates {
                combined_list.extend(op)
        }
        return serialize_list(combined_list)
}

db = open_db(path, {merge_operator: merge_operator})
// key's value is [1, 2, 3]

list_update = serialize_list([4, 5, 6])
db.merge(key, list_update)

db.get(key) // deserialized value: [1, 2, 3, 4, 5, 6]

上面的 merge_operator 將傳遞給 Merge 調用的增量更新組合成一個單一值。當調用 Merge 時,RocksDB 僅將增量更新插入到 MemTable 和 WAL 中。之後,在 flush 和 compaction 時,RocksDB 調用 merge_operator() ,在條件允許時,將若干更新合併成單個更新或者單個值。在用戶調用 Get 或掃描讀取數據時,如果發現任何待 merge 的更新,也會調用 merge_operator 向用戶返回一個經過 merge 而得到的值。

Merge 非常適合於需要持續對已有值進行少量更新的寫入密集型場景。那麼,代價是什麼?讀將變得更加昂貴——讀時的合併值沒有寫回。對該 key 的查詢需要一遍又一遍地執行相同的合併過程,直到觸發 flush 和 compaction 爲止。與 RocksDB 其他部分一樣,我們可以通過限制 MemTable 中 merge 對象的數量、降低 L0 中 SST 文件數量來優化讀行爲。

挑戰

如果你的應用對性能非常敏感,那麼使用 RocksDB 面臨的最大挑戰是需要針對特定工作負載來進行配置調優。RocksDB 提供了非常多的可配置項,但對其進行合理調整通常需要理解數據庫內部原理並深入研究 RocksDB 源代碼:

“不幸的是,對 RocksDB 進行配置調優並不容易。即使作爲 RocksDB 開發人員的我們,也不能完全理解每個配置更改的所造成的影響。如果你想針對你的工作負載充分調優,我們建議你進行實驗和基準測試,並時刻注意三個放大因素。”

-- RocksDB  官方調優指南

總結

從零開始寫一個生產級別的 kv 存儲是非困難的:

RocksDB 解決了上述兩個問題,從而讓你可以專注於上層業務邏輯實現。這也使得 RocksDB 成爲構建數據庫的優秀模塊。

本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源https://mp.weixin.qq.com/s/aTmQt-UkTPHqehTd6sb3DA