RocksDB 在 Facebook 規模下運行八年的實戰報告：最佳化目標如何從寫入放大轉到空間放大，再轉到 CPU。
RocksDB 是 Facebook 在 2012 年從 LevelDB 分支出來的嵌入式 LSM-tree 鍵值函式庫，如今支撐公司內超過 30 個應用、合計數百 PB 的生產資料。這篇論文提出的不是新演算法，而是一份八年份的現場報告，回答的是「到底哪個資源真的會痛」：團隊一開始為了省 flash 抹除次數而全力壓低寫入放大，後來從整個機隊的量測發現真正的瓶頸是磁碟空間，於是做出 Dynamic Leveled Compaction 把空間額外開銷壓在 13% 上下；要到很後面 CPU 與 DRAM 才被排進來，而且理由不是 SSD 跑贏了軟體，而是 CPU 與記憶體相對 flash 變貴了。因為每個分片配一個 RocksDB 實例，一台主機上會同時跑數十甚至數百個實例，逼出了跨實例的資源控制器、執行緒池、可切換的 WAL 模式與檔案刪除限速；而每月一次、逐台上線又可逐台回滾的發版節奏，則逼出了磁碟格式必須同時向後與向前相容。生產環境也證明只有 block checksum 遠遠不夠：以 RocksDB 這一層為源頭的資料損毀，大約每 100PB 每三個月就發生一次，而且其中 40% 在被發現之前就已經傳到其他複本，於是完整性檢查往上延伸進 MemTable 與 block cache，往下延伸成交給儲存層驗證的 handoff checksum。論文最後老實承認，自己當年三個信念是錯的：可設定性愈多對使用者愈好、RocksDB 可以無視 CPU 的 bit flip、以及遇到任何 I/O 錯誤就直接停擺是可以接受的。
在 RocksDB 之前，伺服器上想做本機持久化儲存的應用，不是嵌入 LevelDB、BerkeleyDB 這類函式庫，就是把資料丟給遠端儲存服務。flash SSD 的普及讓後者變得沒有吸引力：一顆能提供數十萬 IOPS 的裝置，把瓶頸從儲存裝置推到了網路，於是把資料放在本機 flash、把引擎直接嵌進應用行程，成了自然的架構選擇。但 LevelDB 當初只為一種相當單純的工作負載而寫：只有一種 compaction 策略、參數選項直接寫死在程式碼裡，對於一台主機上同時跑幾十個實例更是完全沒有答案。同一時期（約 2011 年）社群的共識，以 SILT 這類研究為代表，是「寫入放大」才是該壓的數字，因為 flash 的 program/erase 次數有限，而像 InnoDB 這種 B-tree 引擎為了改動不到 100 bytes 的內容，就得重寫整個 4KB 到 16KB 的頁面。RocksDB 正是從這個共識出發的，而這篇論文有很大一部分，就是在講他們如何發現：對 Facebook 大多數機隊而言，那並不是第一順位的正確目標。
RocksDB 從第一天就押注在 Log-Structured Merge tree 上，理由是 flash 的讀寫效能不對稱、抹除次數又有限。寫入先被記憶體吸收，再轉成大塊的循序檔案寫出，引擎因此永遠不會像 B-tree 那樣發出小筆、隨機、就地覆寫的頁面寫入，而那正是 InnoDB 寫入放大的來源。同樣的版面配置也很省空間：SSTable 一次寫成、塞得滿滿的而且不可變，沒有 B-tree 那種頁面內部碎裂，這種不碎裂的佈局，正是後來團隊能乾淨俐落地把目標轉向空間的前提。作者說他們一再重問 LSM-tree 是否仍然合適，答案一再是肯定的：SSD 的價格還沒便宜到讓大多數場景值得用 CPU 或 DRAM 去換 flash 用量。
RocksDB 不在讀取、寫入、空間這個三角上替使用者選定一個點，而是直接把 compaction 演算法本身開放成設定。Leveled Compaction 承襲並改良自 LevelDB，各層容量呈指數成長、每層只有一個 sorted run，所以讀取大致每層只碰一個檔案、空間額外開銷也小，但寫入放大通常落在 10 到 30 之間。Tiered Compaction（在 RocksDB 裡叫 Universal，做法近似 Cassandra 與 HBase）採取懶惰合併，把寫入放大壓到 4 到 10，代價是每次讀取要掃過更多 sorted run。FIFO Compaction 則是資料庫一超過容量上限就直接丟掉最舊的檔案，對資料庫來說荒謬，但對「本來就允許掉資料」的 SSD 快取剛剛好。因為可調的是演算法而不只是參數，同一套函式庫才能同時服務寫入密集的日誌、均衡的資料庫與快取三種場景。
全文的主線是：值得最佳化的資源改變了兩次，而每一次改變都是被機隊量測推動的，不是被理論推動的。第一個是寫入放大，跟隨社群保護抹除次數的共識，而 leveled compaction 在這點上完勝 B-tree，在 MySQL 上跑 LinkBench 時每筆交易發出的寫入量只有 InnoDB 的 5%。接著量測顯示 IOPS 與 flash 壽命其實大多閒置，真正卡住的是磁碟空間，於是空間放大成為目標，Dynamic Leveled Compaction 也因此誕生。要等到空間這邊容易摘的果實都摘完了，CPU 與 DRAM 才進場；而且作者明確反對「SSD 已經快到軟體追不上」這種流行說法，他們的理由是經濟性的：CPU 與記憶體相對 SSD 變貴了，所以降低 CPU 開銷是一根降低成本、換取更划算硬體配置的槓桿，而不是拿來救吞吐量。
傳統 leveled compaction 給每一層一個靜態的容量目標，結果是：幾乎所有資料都住的最後一層，實際大小可能遠低於設定值，而上面幾層卻塞滿了等著被合併下去的死資料。Dynamic Leveled Compaction 把算式反過來：先量測最後一層的實際大小，再由它推導出其他每一層的目標，於是整棵樹永遠是對著真實資料維持預期的指數比例，而不是對著一個設定常數。效果是資料庫中屬於已刪除、已覆寫的那部分被壓得更緊，而且更關鍵的是它會保持穩定，不會隨資料庫成長而漂移。在隨機寫入的 benchmark 中，它把空間額外開銷穩在 13% 左右，而 LevelDB 式的 leveled 會漂到 25% 以上；論文並指出 leveled 最壞情況可高達 90%，dynamic leveling 則始終穩定。
因為分片是負載平衡與複製的單位，而且複製時必須整份原子搬移，所以分片大小必然有上限；一台主機於是跑數十到數百個 RocksDB 實例，而不是一個大實例。這讓原本是本機調校的問題變成全域問題：write buffer 與 block cache 的記憶體、compaction 執行緒、compaction 的 I/O 頻寬、總磁碟用量與檔案刪除速率，都必須同時做「每實例」與「每主機」的上限管理，甚至可能要細到每個 I/O 裝置。RocksDB 的做法是把資源控制器做成明確的 C++ 物件，由應用建立後傳給多個 DB 物件，讓數個實例共用同一份預算；同時支援優先順序，讓最需要某資源的實例拿得到。當實例分散在不同行程時問題更難，因為每個行程只看得到自己的局部資訊，論文也只能給兩種都不完美的策略：要嘛每個實例都配置得保守一點、放棄壓榨主機資源，要嘛讓實例之間互相交換用量資訊再各自調整。
從 LevelDB 繼承來的 block checksum，只能證明「檔案系統還回來的東西，跟當初交下去的一樣」，檔案 I/O 層以上的一切完全沒有保護。生產數據顯示這件事很重要：以 RocksDB 為源頭的損毀大約每 100PB 每三個月出現一次，而且有 40% 在被察覺之前就已經複製出去了；到那個時候，丟掉壞複本已經沒用，因為可能根本沒有正確的複本可用。RocksDB 因此疊了四層檢查：隨著紀錄一路穿過 MemTable 與 block cache 的 per-key-value checksum、每次讀取都驗的 block checksum、記在中繼資料裡、只要 SSTable 被複製去建複本或備份就重驗的整檔 checksum，以及往下交給儲存層、在寫入當下就驗證的 handoff checksum。背後的原則就是經典的 end-to-end 論證逐層套用：每一層都要盡早抓出自己這層的錯誤，因為損毀傳得愈遠，代價愈大。
RocksDB 內部本來就用 56 位元的 sequence number 區分同一個 key 的不同版本，但應用無法指定它、無法要求一個「事先沒登記過的過去時點」的快照，也無法讓不同實例的 sequence number 互相對應，所以跨分片的一致性讀取基本上做不到。應用的變通做法不外乎兩種：把時間戳編進 key 裡，這會毀掉 point lookup，因為完整的 key 已經無法事先得知；或編進 value 裡，這會讓同一個 key 的亂序寫入與讀取舊版本都變貴。論文提出的解法，是把時間戳升格成掛在鍵值對上的一等公民欄位，由應用決定內容、但由 RocksDB 理解其語意。因為使用者的 key 保持完整，Bloom filter 依然對 key 有效、point lookup 可以取代 iterator，而且每個 SSTable 可以在屬性中記錄自己涵蓋的時間戳範圍，讓只可能含有過期版本的檔案在被打開之前就被排除。
一筆寫入會同時進入記憶體中的 MemTable（以 skiplist 實作，維持有序並提供 O(log n) 的插入與搜尋）以及磁碟上的 write-ahead log。當 MemTable 達到設定大小，引擎會把該 MemTable 與 WAL 一起改為不可變、配置一組新的給後續寫入、把凍結的 MemTable flush 成磁碟上的 Sorted String Table 檔案，然後丟棄凍結的 MemTable 與其對應的 WAL。每個 SSTable 內部依序存放資料、切成大小一致的 block，另有一個索引 block、每個資料 block 一筆索引項，因此檔案內的查找就是一次二分搜尋。WAL 並非必要，這點很重要，因為 RocksDB 上層的分散式系統通常自己就有複製日誌（例如 Paxos log），不需要第二份。
剛 flush 出來的 SSTable 落在 Level-0，該層的檔案之間 key 範圍可以重疊，因為每個檔案本身就是一個完整的 sorted run。Level-0 以上的每一層都只含一個 sorted run，被切分到多個檔案上，所以在這些層裡，一個 key 至多只會出現在一個檔案中。各層被指派指數成長的容量目標；當第 L 層超出目標時，RocksDB 會挑出它的一些 SSTable，與第 L+1 層中 key 範圍重疊的 SSTable 合併，過程中順手丟掉被刪除與被覆寫的版本，並把輸出寫成利於讀取與省空間的形式。compaction 的 I/O 全是整檔的大量循序讀寫、而且可以平行化，這正是它適合 SSD 的原因；在 dynamic leveling 之下，各層的容量目標本身也不再固定，而是由實際觀測到的最後一層大小重新推算。
一次 Get 會先搜尋所有 MemTable，接著因為範圍重疊而必須掃過所有 Level-0 的 SSTable，然後逐層往上，直到找到 key 或確認最後一層也沒有為止。在每一層內，先用索引 block 做二分搜尋定位候選 block，而每個 SSTable 各自的 Bloom filter 會在任何資料 block 被讀出之前，先排除掉絕大多數不可能含有該 key 的檔案。在 RocksDB 5.9 上量到的效果是：leveled 有 Bloom filter 時每次 Get 約 0.99 次 I/O、沒有時 1.7 次；tiered 沒有 filter 時要 3.39 次，因為有 12 個 sorted run 要走訪。掃描是弱點：iterator 必須在每一層都定位一次，而且完全無法利用 Bloom filter，這就是為什麼 FIFO 的每次 iterator seek 要 967 次 I/O，而 leveled 只要 1.84 次。
既然上層的複製系統往往已經自己做了持久化日誌，RocksDB 就提供三種 WAL 行為：每次操作都同步寫、緩衝寫（由低優先權的背景執行緒定期刷到磁碟，因此不影響前景延遲），以及完全不寫 WAL。另一個實務陷阱是檔案刪除：在 XFS 開啟 realtime discard 這類感知 flash 的檔案系統上，刪檔會發出 TRIM，而 TRIM 會讓 SSD 韌體更新位址對映、把這個變更寫進 flash 中的 FTL 日誌，並可能觸發內部垃圾回收與大量資料搬移。由於一次 compaction 就會同時刪掉好幾個輸入檔案，這一波 TRIM 就表現為前景 I/O 的延遲尖峰。RocksDB 因此替檔案刪除加上限速，讓檔案逐步移除而非同時移除，既保留 TRIM 對壽命與效能的好處，又避開延遲尖峰。
應用會為每種資源建立一個或多個資源控制器物件（C++ 物件），把同一個物件傳進多個 DB 物件，讓這些實例共用同一份預算；另外還有每實例的控制器，限制單一實例的胃口，並以優先順序決定爭搶時誰勝出。論文點名的受控資源包括 write buffer 與 block cache 的記憶體、compaction 的 I/O 頻寬、compaction 執行緒、總磁碟用量與檔案刪除速率，並指出這些上限可能得依每個 I/O 裝置分別維護。第二條血淚守則是：絕不要隨手開一堆不受池管理又長命的執行緒。執行緒太多會造成過度的 context switch、I/O 尖峰，並讓除錯變得極度困難，所以任何可能睡眠或等待條件的工作，都該交給大小與資源用量可封頂的執行緒池。跨行程的協調則仍未解決，因為單一行程只看得到自己那個分片的局部資訊。
block checksum 覆蓋每個 SSTable block 與每個 WAL fragment，在資料產生時生成，且因為範圍小而在每次讀取時都驗證，於是任何在檔案系統或更底層被弄壞的資料，都能在送到客戶端之前被攔下。file checksum 在 2020 年加入，覆蓋整個 SSTable，記錄在資料庫中繼資料的檔案項目裡，只要檔案為了建立複本或備份而被搬運就重新驗證，因此能抓到搬運路徑本身造成的損毀。handoff checksum 則是對「即將寫出的資料」先算好、隨資料一起往下傳，由下層在寫入當下驗證；本機檔案系統很少提供這種寫入 API，Oracle ASM 這類專門的堆疊有，而遠端儲存服務則可以把它接到自己內部的 ECC 上，RocksDB 還能用 checksum 合併技巧，從既有的 WAL fragment checksum 便宜地算出 handoff 值。per-key-value checksum 在論文寫作時仍在實作中，它隨每筆紀錄穿過 MemTable 與 block cache，並在 flush 與 compaction 時查驗，補上檔案 I/O 層之上的缺口。
內部每一筆客戶端寫入都會遞增一個 56 位元的 sequence number，因此同一個 key 的多個版本可以並存於 LSM-tree 中、靠這個號碼區分，而 compaction 就是最終回收「沒有人看得到的版本」的機制。應用可以取得一個 Snapshot，之後 RocksDB 保證當下存在的所有鍵值對都會保留到快照被明確釋放為止；但快照必須事先取得、沒有 API 可以指定過去的時點，而且作用範圍只限單一實例，所以跨分片之間沒有任何東西在協調版本。使用者自訂時間戳這個擴充，是把應用選定的時間戳當成掛在鍵值對上的中繼資料，而不是串接進 key、也不是塞進 value。因為使用者的 key 保持完整，可以用帶 Bloom filter 的 point lookup 取代 iterator，而 SSTable 的屬性也能記下它涵蓋的時間戳範圍，讓只可能含有過期值的檔案在這次讀取中直接被排除。
「分散式系統在單一節點上把位元組放在哪裡」這個問題，RocksDB 成了預設答案。MySQL 有了 MyRocks，論文中 UDB 空間腰斬的成績就是它的招牌；Facebook 的 ZippyDB、LogDevice、Dragon 與 Rockset 都建在它之上；CockroachDB、TiDB 的 TiKV、MongoDB 與 Rocksandra 把它當成可插拔的儲存引擎；而 Apache Flink、Kafka Stream 與 Samza 都以它作為本機狀態後端，這也是為什麼今天大多數串流處理的 checkpoint 底下坐著一棵 LSM-tree。這篇論文整理出的 compaction 詞彙——leveled 對 tiered 對 FIFO，再加上動態層級容量——成了後續 LSM 研究爭論時共用的框架，而 RocksDB 本身則是 PebblesDB、SlimDB、Monkey、WiscKey 及其後繼者用來對照的基準線。也不是所有人都留在原版：CockroachDB 用 Pebble 取代了 RocksDB，那是一套以 Go 寫成、保留檔案格式與大部分設計、但刻意甩掉本文所抱怨的設定面的引擎；Speedb 則直接把 RocksDB 分支出去——兩者都是「設定過度膨脹」這個侷限在公開場合上演的結果。失效處理那一節則已經沉澱為業界標準做法：任何會把檔案在複本之間搬運的引擎，如今都被期待要有逐筆紀錄與整檔的 checksum。影響最深的一點是，「多數 SSD 部署卡住的是空間，不是 IOPS 也不是 flash 壽命」這個實測結論，扭轉了一個花了十年在壓低寫入放大的研究社群的方向，也讓工業界的經驗報告在 FAST 與 OSDI 這種場合取得了一等公民的地位。
“We describe how and why RocksDB's resource optimization target migrated from write amplification, to space amplification, to CPU utilization.”
“Second, we find that any server with a high-end CPU has more than enough compute power to saturate one high-end SSD. RocksDB has never had an issue making full use of SSD performance in our environment.”
“Based on our measurements, corruptions are introduced at the RocksDB level roughly once every three months for each 100PB of data. Worse, in 40% of those cases, the corruption had already propagated to other replicas.”