MyRocks: 為facebool 的社交圖譜服務的LSM-tree存儲引擎

文章目錄

概覽
1. UDB 架構
2. UDB 表格式
3. Rocksdb：針對flash存儲優化過的第三方庫

3.1 Rocksdb架構
3.2 為什麼選擇Rocksdb

4. MyRocks / Rocksdb 開發曆程

4.1 設計目标
4.2 性能挑戰

4.2.1 降低CPU的消耗
4.2.2 降低range-scan 的延時消耗
4.2.3 磁盤空間和Compaction 的一些挑戰

4.3 使用 MyRocks 的更多優勢

4.3.1 線上備份和恢複功能
4.3.2 即使有很多二級索引也能提供很好的擴充能力
4.3.3 在替換和插入操作中不需要額外的讀取
4.3.4 擁有更多壓縮的空間

5. 生産環境的資料遷移工具

5.1 MyShadow - shadow 查詢測試
5.2 資料正确性校驗
5.3 實際的遷移過程

6. 性能
7. 總結

概覽

論文位址：MyRocks: LSM-Tree Database Storage Engine Serving Facebook’s Social Graph

個人覺這篇論文優質的地方展現在：

facebook 工程師們解決業務複雜問題的思路。從前期的調研 + 測試 + 開發 + 周邊服務建設都是層層遞進，基本痛點 + 解決痛點的技術方向都在前期調研完成，有效得保證後續工作的價值。
對作為第三方庫的單機引擎(Rocksdb) 整體功能了解得更加透徹（能夠更加靈活得使用 Rocksdb 了），也會明白底層軟體一定是放在一個個有價值的業務中才能展現其底層的價值，就像wiredtiger 接入 mongodb。

當然MyRocks 在facebook中解決的問題就類似 X-DB在polardb 要解決的問題。

Facebook中 UDB(user database)資料庫主要用來存儲最為重要的社交關系資料。由于曆史包袱，當然也不算是包袱，最開始UDB是使用MySQL + innnodb 作為後端存儲。随着資料量的不斷增長，到現在(2020)為止有一些痛點需要克服，這一些痛點主要是由于innodb存儲引擎引入的。

B+ 樹索引引入的空間碎片（記憶體+磁盤，主要是磁盤成本）
壓縮效率低下
每個行事務會額外消耗13B的存儲空間。

後續會詳細介紹innodb 中為什麼會有這三個問題。

綜上問題，Facebook開發者考慮引入LSM-tree 架構的存儲引擎，能夠擁有良好的空間使用率，并且在服務好read/write的同時保持低延時，這樣就很完美。這個時候如果從頭研發一個新架構的成熟存儲引擎，需要花費太多的時間（以年為機關計算）。是以，Rocksdb這個第三方庫進入了他們的視野，隻需要在其上對接一個MySQL的可插拔存儲引擎接口就能在不需要修改MySQL的用戶端協定，SQL層以及複制相關代碼的情況下完成我們的需求。

大體架構：

有了一個能快速解決問題的方向，接下來就是定目标了。官方大佬大手一揮，我們要利用myrocks 減少UDB中50%的servers成本。

ps: 這裡減少50% 并不是空穴來風，理論上如果保持和innodb同能能力的吞吐和延時的情況下，降低50%的存儲成本以及 cpu/記憶體消耗，就能夠達到這個目标。

存儲成本中 LSM-tree本身就能夠降低這樣的寫放大。如果lsm-tree所有層都寫滿，leveled-merge 政策下，寫放大1.11…，而b+tree 的（空間碎片）寫放大則基本在1.5以上。相關資料可以參考Optimizing-Space-Amplification-in-RocksDB。

空間放大，理論上天然就能夠滿足存儲成本的需求，而CPU和記憶體的降低則對myrocks 是一個挑戰。減少50%的伺服器，意味着算力降了一半，這在rocksdb 的compaction/flush 的高CPU消耗中是一個痛點。

是以，開發者們列出了 MyRocks 支援 UDB核心特性開發過程中面臨的挑戰：

CPU/IO/記憶體壓力增加。相當于同樣的資源需面臨之前2x的請求壓力。
rocksdb的順序scan性能比逆序scan性能好，但相比于innodb中的B±tree底層葉子結點的雙向連結清單來說差很多。實際的UDB應用中有很大的需求需要反向scan，這需要對rocksdb的疊代器做一些優化。
在LSM-tree中會有更多的key之間的比較（點讀/scan/compaction），都是對CPU的消耗。
LSM-tree的讀依賴bloom-filter來過濾不存在的key，這會增加記憶體負擔。
scan性能比innodb差很多。
tombstone管理，innodb是in-place-update，是以不回有tombstone。而lsm-tree則會直接追加一條key，如果清理不及時，會造成空間放大以及影響scan性能。
LSM-tree 的 compaction 會消耗I/O資源，進而造成write-stall 以及上層read latency-spike。

這一些挑戰會涉及到 rocksdb 的大量特性開發，但這一些開發相比一個全新的存儲引擎來說也不算什麼了。當然，這一些特性在後續的rocksdb中并不僅僅是為了 MyRocks 的定制，每一個特性都能夠通用到其他的rocksdb使用者中。

除了針對Rocksdb 的核心特性開發之外，還有資料遷移工具的開發（萬級别的伺服器資料的遷移需要非常謹慎）：

生産資料的導入：

MyShandow工具：同步截取使用者請求，并插入到MyRock 所在的伺服器中。
Data correctness 工具：資料校驗工具，會比對 innodb和myrocks 執行個體中索引以及依據索引查找到的資料内容。

舊資料的替換：

MyRocks提供 bulkload 來快速加載舊資料。
每一個Innodb的執行個體替換到MyRocks 執行個體之後即可删除Innodb執行個體，這其實對于 MySQL 這種存儲引擎之間資料是獨立的的資料庫來說很簡答。

Facebook在2017年，基本完成了 UDB 的資料從 Innodb 到 MyRocks 的遷移。實際的收益則是降低了63%的存儲成本，75%的磁盤I/O壓力，二級索引維護的開銷和讀性能的加速讓CPU的消耗略有降低（LSM-tree相比于 b±tree來說很不容易了），進而整體達到了之前50%以上的server縮減。

Facebook 工程師通過這個實踐案例得出了幾個非常有價值的結論：

建立在LSM-tree上的資料庫在經過一些定制化的調優還是非常有價值的。（這個在阿裡的X-DB也有證明），當然這個還是看資料庫的主體應用場景。
記錄了想要替換一個成熟的B±tree存儲引擎所遇到的性能挑戰以及做出的對應的優化。
在不同資料庫/存儲引擎之間的遷移工具還是很常見的，本paper的實踐則比較好得展示了整個遷移過程的思路和方法。

接下來将詳細介紹 MyRocks 是如何解決列出來的這一些痛點以及相關遷移工具的詳細設計細節，這個過程很有趣，更值得學習。

1. UDB 架構

從UDB的架構演進到對底層存儲的各種需求，能夠看到一個很明顯的現象就是存儲成本的縮減是我們基礎軟體的核心，希望用最少的成本盡可能得滿足使用者需求。

UDB是facebook 内部大規模應用的全球分片資料庫服務，其中應用了MySQL的上百種特性。早期的UDB服務是運作在HDD之上，因為HDD性能有限，是以叢集的伺服器負載需要被嚴格得監控，防止達到HDD的性能上限。随着SSD 高性能存儲硬體的普及，在2010年開始，将SSD接入UDB中作為HDD底層存儲的cahce，雖然單台伺服器成本增加了，但是吞吐缺提升了一個量級，單台機器可以存儲的資料量也上升了。

在2013年，UDB 将所有的HDD都替換為了SSD，這個時候問題就凸顯出來了，雖然吞吐不受限制了，但是存儲成本卻快速上升，SSD本身沒有HDD那樣的大資料量的存儲，卻仍然要保證那麼多資料的存儲，這個時候解約存儲成本就是一個首要問題了。針對innodb的壓縮引入了很多其他的問題：

壓縮資料。MySQL的innodb是支援資料壓縮的，但是也隻有50%的壓縮率，這對UDB來說并不是一個滿意的結果。

存儲引擎帶來的問題：

空間使用率太低。通過對innodb存儲引擎的深入研究，發現了innodb的b-tree 索引碎片會造成磁盤25-30% 的空間被浪費掉（完全碎片的空間，無法繼續存儲）。他們也嘗試通過碎片整理進行優化，但是收效甚微。原因是 UDB接受的資料存儲基本都是不固定大小的随機寫，這種workload下本身B-tree會産生很多索引碎片，而進行碎片整理的過程必然要對管理磁盤塊的指針進行移動，這回額外得消耗系統CPU/SSD壽命，間接降低了系統的性能。
壓縮率不高。Innodb預設的管理磁盤的資料塊大小是16KB，為了保證壓縮後的頁面可以單獨更新，這裡将壓縮後可以生成的塊大小預定義為了1K, 2K, 4K, 或者 8K。如果設定的key_block_size 是8K， 16KB的資料經過壓縮後為5KB，但也隻能占用8K的存儲空間，這樣有也就隻有50%的壓縮率。而設定更小的key_block_size則會産生更多的B-tree的分裂，進而消耗更多的CPU。在Innodb中對于經常更新的表使用的是8kb的key_block_size，而不經常更新的則使用4kb，是以整體的壓縮率其實并不高。

Innodb過高的寫放大造成的寫性能問題。

a. Innodb的B-tree 髒（更新）資料頁最終會被回寫到磁盤中，而在大量的随機寫入場景下這樣的回寫會很頻繁。再加上key_block_size的配置，對于一個資料表的單行幾個位元組的修改也會造成8K的回寫。

b. Innodb還有double-write 機制，防止異常當機之後的資料丢失問題。

上面說的幾個關于innodb的問題并不是很好優化且優化效果甚微，是以UDB開發者們急切得需要一個高空間使用率、低寫放大的資料庫實作。最終發現LSM- tree 架構能夠很好得解決這兩個問題。而且 LSM-tree 因為其分層架構，對于帶有緩存的存儲系統來說天然具有優勢。

盡管LMS-tree 的這一些潛在優勢很有吸引力，且能解決B-tree的痛點，但仍然會有以下兩個難題：

當時并沒有一個在生産環境且閃存裝置上被驗證過的LSM-tree 資料庫。
UDB 仍然需要提供大量的讀吞吐。原因是UDB 表中都有主鍵，是以插入key的時候需要執行主鍵限制的檢查并更新或者删除之前的行，這個時候需要讀到之前的行資料，而在大量更新的場景下就會産生大量的讀。但LSM-tree 在read-heavy場景以及flash-storage下不一定擁有良好的性能。

2. UDB 表格式

UDB 存儲社交資料的表主要有兩種格式（類似圖的點和邊）：

對象
對象關聯資料。

每個對象和關系都有定義其特征的類型（fbtype 和 assoc_type）。 fbtype 或 assoc_type 确定存儲對象或關聯的實體表。

公共對象表稱為 fbobj_info，它用來存儲公共對象。key可以用fbtype + fbid 表示，value則是對象本身以序列化格式存儲在“資料”列中，其格式取決于每個 fbtype。
而關聯表存儲對象之間的關系。例如，assoc_comments 表存儲對 Facebook 活動（例如文章）的評論關聯資料，key 可以用：id+accoc_type表示。關聯表用二級索引 id1_type 優化range scan 性能。因為擷取與 id (id1) 關聯的 ids (id2) 清單是 Facebook 上的常見邏輯，例如擷取喜歡某個文章的人的辨別符清單。

從shcema 的角度來看，對于對象表的通路方式類似于k/v存儲，而非關系型存儲。且在社交圖譜中的操作中，一個事務往往會修改相同id1的對象表和關聯表。是以，實際的存儲中這兩張表也會存放在同一個資料庫執行個體。

3. Rocksdb：針對flash存儲優化過的第三方庫

Rocksdb 是在2012年基于LevelDB 做出來的單機存儲引擎，主要在flash-ssd這樣的儲存設備上做了很多優化。它當時也是為了解決其他資料庫在使用閃存裝置過程中的存儲性能問題而推出的，且在UDB調研的時候已經應用在了facebook 内部ZippyDB,Laser, Dragon等資料庫之中。Rocksdb 在開始研發的時候對業界的主流資料結構做了大量的調研，最後選擇了 LSM-tree ，隻有這個資料結構在擁有足夠低的寫放大的同時讀性能也能得到很好的平衡。

3.1 Rocksdb架構

寫路徑

a. 先寫WAL

b. 追加寫記憶體的一個buffer元件 Memtable，傳回使用者完成寫請求。

c. Memtable達到門檻值，Flush到SST(sorted string tables)。每一個SST都會按照順序來存儲資料，這一些資料會被分割為多個data blocks。每個sst還有一個index block, 其中儲存了每一個datablock的第一個key，用作二分查找對應的data-block。多個ssts會被組織成一個個Level，每個level中都有一批 sst（類似上圖）。

d. 為了讓每一個level的大小不回超過限制，同時清理過期的key，會從Ln中選擇出一些ssts 與 Ln+1 中有重疊的sst進行合并，将新的sst 寫入到Ln+1中。
讀路徑

a. 先讀所有的memtable

b. 讀每一個sst内部的bloomfilter, 用來過濾目前sst不存在的key的查找。

c. 所有的L0 的ssts，每個sst都會讀一次（二分查找）

d. 所有Ln的ssts，整層進行二分查找

3.2 為什麼選擇Rocksdb

正如前面說到的，UDB使用MySQL存儲引擎過程中遇到的兩個主要痛點：磁盤空間使用率，寫放大。而這兩個問題在 LSM-tree 的架構中都能得到很好的解決。

對于寫放大來說：LSM-tree 是Append-only 架構，這不同于 B-tree 的inplace-update，能夠天然解決空間使用率問題。再說一下寫放大，Innodb 中更新一行的幾個位元組都要寫入8K，對于 LSM-tree 來說，每次寫入磁盤都會batch累計一批資料，除了每個sst的最後一次寫入之外不會存在很小的流量寫入。
再來看空間使用率問題：

前面說過B-tree 因為索引碎片問題，會導緻20-30% 的空間被浪費，完全無法使用。Rocksdb out-of-place update 并不會有這樣的問題，唯一要擔心的是tombstone的删除并不及時（Compaciton删除）。但在經過調優之後，這個tombstone對空間消耗的影響能夠降到10%以内。
再來看壓縮，Innodb 16KB壓縮為5KB，但是還得寫入8KB，也就是壓縮率為50%。而對于 rocksdb 來說壓縮5KB 就寫入5KB。
最後再來對比一下單行事務的大小。對于 Innodb 來說，一個單行的事務操作需要額外增加 6B 的trasaction-id + 7B 的復原指針。而對于 Rocksdb 來說，單行事務中每一個 key 僅僅會儲存一個7B 的seq-number，而且這個seq-number 在key 處于最後一層的時候會被置為0，0對于壓縮來說非常友好。

綜上來看，Rocksdb 能夠很好得解決 Innodb 的空間使用率和寫放大問題。那Facebook 的工程師終于決定基于 rocksdb 來開發一個 MyRocks 存儲引擎作為MySQL 的插件引擎。在MySQL5.6 版本中，已經實作了MyRocks，而且通過 TPC-C 的benchmark 進行壓測，性能表現良好。

4. MyRocks / Rocksdb 開發曆程

這一節我們能夠學習到開發一個複雜大型項目的一些方法論。重構和遷移一個大型資料庫的資料是一個大工程，是以開始工作之前他們先制定了一些目标，雖然高效得實作這一些功能，但相應實作的可靠性、隐私、安全性和簡單性也都非常重要。

4.1 設計目标

保留一些應用已經存在的特性和操作。

比如實作MyRocks 的過程中，讓MySQL 不用變更Client接口和SQL 層的協定對接就能直接使用 MyRocks 是最好不過。這樣一些MySQL 的工具：instance-monitering, backup, failover 都能夠直接使用了。
縮短項目完成周期。

這個項目并不是說需要花費幾年的時間來完成一個非常棒的資料庫，并再花費幾年時間完成遷移工具的開發。因為UDB 的資料量還在不斷增長，想要讓UDB 的痛點得到解決，這種工程量并不是可取的。他們是通過如下兩種方式縮短MyRocks 的上線周期的：

a. UDB 的表格式是固定的，是以在調研/分析 MyRocks 的設計的同時會優先将 MyRocks 的表格式/索引格式設計出來，因為這一些格式是底層實作，一旦固定下來，後續基本不太可能變化。

b. 在開發MyRocks 的過程中，還在用開源的LinkBench 收集 UDB on Innodb 上的使用者 workload ,這一些 workload 後續會被用來對每一個 MyRocks 完成的特性進行針對性壓測，進而降低後續的測試成本。
設定清晰的性能目标。

MyRocks 需要提升性能的同時不希望犧牲一緻性。是以在替換 innodb 這件事情上有兩個目标。

a. 降低資料庫的空間使用率 50% 以上

b. 降低空間使用率的同時并不會增加CPU/ IO 的消耗。

在這兩個清晰的目标驅動下，我們能夠知道接下來所面臨的困難。想要節省50% 的磁盤空間，意味着單個MySQL 執行個體将要面對之前兩倍的資料壓力。雖然MyRocks 能夠使用更少的CPU 和 IO 來處理寫入，但也會是以引入更多的讀。
設計選擇。

a. 為了Rocksdb 滿足 MyRocks 的特性，會增加一些額外的特性到開源社群中，而這一些特性也能夠應用在其他類似的資料庫中。

b. 叢集索引結構的設計。UDB 本身使用了 Innodb 的聚集索引結構，由于所有的列都存在，可以通過一次read 就能讀到主鍵。MyRocks 的設計中也采用這樣的聚集索引結構。二級索引會包含一個主鍵列用來索引主鍵key，但并不會包含row id。

4.2 性能挑戰

MyRocks 的開發過程中對讀性能做了幾點的優化進而能夠和 Innodb 的性能接近，同時針對大量 tombstone 能夠降低scan性能和消耗很多空間的問題做了一些優化，接下來将會詳細讨論這一些優化點。

4.2.1 降低CPU的消耗

Mem-comparable keys

在LSM-tree 中的讀取會有比 Innodb 讀取中更多的 key 比較操作。在Range-scan下，Innodb 中我們還需要一次二分查找就能找到起始key，而在LSM-tree 中需要為每一個有序部分進行二分查找（所有mmetable/ imm, L0的所有sst，L1-Ln的每一層），并且使用一個最小堆來進行排序。這個起始key的查找在 LSM-tree 中就會多幾次 key的比較。而在接下來的讀取過程中，Innodb 隻需要順序讀下去，LSM-tree 卻需要在最小堆至少一次和舊版本key的比較，保證傳回的是最新的key。

針對這種比較場景，MyRocks 實作了 bytewise-comparable Comparator 來讓MyRocks 中的key比較的時候使用位元組序的方式（CPU 位運算效率還是很高的，計算單元中的大量的門電路都是比較機器碼的）。
Reverse key Comparator

方向掃描則是在資料庫使用單機存儲引擎中出現的需求，單機引擎沒辦法在分布式場景支援MVCC，是以一般上層分布式資料庫會為每一個寫入到引擎的key都會增加一個時間戳，來支援多版本。很多時候需要按照key的更新時間降序掃描key，這個時候一般情況就需要通過第二種方式來進行掃描。這個問題在 MyRocks 接入 UDB 的實作過程中就是一個痛點，UDB 會有固定的場景需要按照更新時間降序擷取好友關系。

關于key的反向比較器的實作也就是針對Rocksdb 疊代器中Prev 性能問題的規避方式。通過實作一個反向比較器，可以讓key的存儲按照原本相反的排序方式存儲在SST中，這樣原本應該Prev掃描的結果就可以直接轉化為Next 的高效掃描了。

更多的 Rocksdb 這裡的細節和測試可以參考:

Rocksdb iterator 的 Forward-scan 和 Reverse-scan 的性能差異
Faster Approximate Size to Scan Calculation

更高效得預估 key-range 之間的資料庫的大小。這個需求來自于 MySQL 優化器根據使用者SQL 生成執行計劃的時候需要預先知道這個操作會消耗多長時間。比如 MySQL 拿到一個查詢請求，它會拿到一個這個範圍的最小key和最大key傳給存儲引擎，MyRocks 此時要預估掃描的成本并傳回給MySQL。

這裡 Rocksdb 的實作是通過确認最小key 和最大key 所處block 之間的距離（包括memtable/imm的大小）。這個過程需要掃描計算每一個Rocksdb 元件的累積大小，會有較高的CPU開銷。這裡主要通過兩方面進行優化：

a. 強制要求給出特定的索引。這就能完全跳過計算最大key和最小key 之間的距離了。因為社交關系圖譜查詢是高度統一的（查找好友關系），是以多個SQL查詢中增加這個提示能夠減少大部分的類似計算的開銷。

b. Rocksdb 的實作計算兩個key-range 之間資料大小的算法優化。通過首先預估兩個key 之間完整的 SST 的大小，如果确定它們并不會顯著改變結果的預期，則跳過剩餘部分 SSTs 的掃描。比如發現一個SST 的key-range 全部在整個key之間，則直接加上這個SST 的大小，如果在SST key-range 的end key 在start key之前，則跳過這個key，隻有有 sst 的key-range 落在兩個key之間才會進一步計算SST内部的重疊部分。

實作代碼如下：

4.2.2 降低range-scan 的延時消耗

Prefix-Bloom filter

在UDB資料庫中，會有大量的 range-scan 産生，這對 LSM-tree 來說是一個不小的挑戰。

在傳統的B-tree 中，Range query 會從一個葉子節點開始，通過雙向連結清單向前或者向後讀幾個leaf page就可以了。對于LSM-tree 來說則有兩部分：Seek 和 Next 操作。其中Seek操作耗時較多，很多時候需要從SST 中讀取一個data block, 而且即使這個 key 不在這個data block 也會被讀出來。這個過程會消耗更多的I/O 和解壓縮的CPU。

為了降低這種情況下的Scan耗時，Rocksdb 實作了 prefix bloomfilter 能夠跳過任何不包括start key的datablock的讀取，當然隻需要消耗部分存儲空間。
Reducing Tombstone on Deletes and Updates

在Rocksdb 中 Compaction 是一個影響讀寫性能的主要因素。其中最大的痛點是如何處理大量删除産生的 tombstone，這一些 tombstone 的增加會嚴重影響scan性能。而在UDB 的更新場景中，意味着針對一個 old key 的删除和 new key的寫入（同一個user-key 的不同value）。如果UDB中針對 MyRocks 的index key有非常頻繁的update，那接下來針對包含這個index-key 的range-scan 會掃描它所有的 tombstone（UDB 會有非常頻繁的針對二級索引的range-scan ），而這一些tombstone隻有被compaction到最後一層才會清理。

因為以上tombstone 造成的問題，Rocksdb 開發出了 SingleDelete 特性。與傳統的Delete 類型相比，SingleDelete 在删除 Old-key類型為Put 的操作時能夠直接清理掉，無需等待compaciton到Lmax。

這個特性僅适用與一個 user-key的一次Put，如果針對一個user-key有多次Put，比如Put(key=1, value=1), Put(key=1, value=2) 接下來調用SingDelete(key=1)，這種情況下(key=1,value=1)還會能夠被讀到，這是一個資料不一緻的情況。在MyRocks 中，這種情況不會出現，因為 MyRocks 能夠保證針對二級索引的更新僅僅會有一次Put，不允許針對同一個二級索引更新多次。

針對SingleDelete 的這個問題的測試可以使用如下測試代碼:

rocksdb::WriteOptions wopts;
string value;
wopts.sync = true;

// 第一個SST 檔案，包含一個Put
db->Put(wopts, "key1", "value1" );
db->Flush(rocksdb::FlushOptions());

// 第二個SST 檔案，包含一個Put + SingleDelete
db->Put(wopts, "key1", "value2" );
db->SingleDelete(wopts, "key1");
db->Flush(rocksdb::FlushOptions());

// 保證前兩個檔案能夠被 compaction 到
db->CompactRange(rocksdb::CompactRangeOptions(), nullptr, nullptr);

// 還是能夠讀到
db->Get(rocksdb::ReadOptions(), "key1", &value);
cout << "key1's value after singledelete :" << value << endl;

Trigger Compaction based on Tombstone

當UDB 删除大量的行時，一些sst 可能會被大量的tombstone填充，這一些tomestone 會嚴重影響scan性能

Rocksdb 通過 TableCollection 實作了一個Deletion Triggered Compaction (DTC)，當發現sst 中 tombstone 過多且超過一定的門檻值，則直接針對目前sst 觸發新的compaction。

關于DTC 的實作細節和性能測試可以參考Rocksdb和Lethe 對Delete問題的優化

下圖是LinkBench 在大量tombstone 下用未優化過的Rocksdb 和 DTC / SingleDelete 的對比測試，可以發現DTC+SingleDelete 能夠有效解決tombstone 過多對使用者性能的影響。

4.2.3 磁盤空間和Compaction 的一些挑戰

降低記憶體使用。

為了提升讀性能，會為每一個SST生成一個bloom filter，這一些bloom filter在正常讀時候都會被加載到記憶體中。為了降低他們對記憶體的消耗，Rocksdb 擴充了Bloomfilter ，允許Bloom filter在LSM-tree 的最後一層不建立bloom filter。如果我們将層的增大比例調整為10，那90%的資料都會被存放在最後一層，這樣能夠減少90%的bloom filter的建立，進而減少90%的記憶體消耗。對于之前層的Bloom filter來說，則仍然有效。當然，這會讓最後一層不存在的key的過濾失效，而這裡則選擇了犧牲CPU 來保證記憶體的權衡。
減少因為Compaction造成的SSD降速

MyRocks 依賴SSD 内部的 Trim Command 來降低SSD内部的寫放大，進而達到提升SSD吞吐性能的目的。但是我們會發現SSD的性能在 Trim指令的時候會有一段下跌。而這個情況在 Rocksdb的Compaction 過程中更為頻繁，compaction 完成之後會将舊檔案批量删除，這個時候會有大量的Trime 指令，進而造成SSD 的性能下降。

為了減緩這個問題，Rocksdb 實作了RateLimiter 來降低Compaction/Flush 針對SSD的寫入速度，保證了底層IO的穩定。同時在非全雙工的SSD主要下，能夠有效降低寫入的增加對上層業務讀的Latency 的影響。
實體移除過期資料

這個功能很有意思。在UDB的社交圖譜資料中，之前提到對象的辨別fbid 是單調遞增的，而對象表内的對象的修改會随着時間的推移逐漸減少。尤其是當一個對象被删除了，那基本不會有針對這個對象的更新操作了。後續的插入/更新/删除操作基本都隻針對這個新的對象了，這個時候之前舊的對象操作資料可能會大機率集中在一個sst檔案中，而這個sst檔案因為不會和其他的sst檔案有重疊，基本不會被compaction排程到，落到最後一層，進而無法被删除掉。

為了解決上面的問題， Rocksdb開發了period compaction功能，就是設定一個period時間，會在這個時間内檢查每個SSD檔案的年齡，如果年齡超過了period設定的時間，那會直接讓這個SST 參與Compaction，直到最後一層，從被有效清理掉。

參數設定可以通過:
options.periodic_compaction_seconds 進行設定(僅在Level Compaction政策中生效)。
Bullk loading

造成Rocksdb LSM- tree write-stall 最主要的原因是短時間大量的寫入。像線上的schema 變更，線上資料導入都會産生大量的寫入。而Innodb 到 MyRocks 遷移工具則是線上資料導入場景，會産生大量的寫入，如果還是按照MyRocks 的資料寫入接口的話會有大量的額外寫入（memetable->flush->多層Compaciton），如何保證這個操作不會影響正常的寫入請求（不産生write-stall），Rocksdb 設計了Bulk loading。

這個特性在Rocksdb 外部通過sst_file_writer API 接口遇險建立好SST，新的SST通過Ingest接口直接插入到 LSM-tree 的Lmax中，并同步更新Rocksdb 的Manifest。這個過程會bypass memtable, L0->Lmax-1 的compaction。

如下是 Innodb / MyRocks 讀寫接口/ MyRocks Bulkload 下的性能對比：

關于更多Bulkload 的實作細節，可以參考Rocksdb 通過ingestfile 來支援高效的離線資料導入

4.3 使用 MyRocks 的更多優勢

4.3.1 線上備份和恢複功能

MyRocks 實作了邏輯備份功能和 ReadOnly Snapshot Read來解決一緻性讀問題。在Innodb 中一緻性讀是通過Undo log實作的，UNDO LOG 是通過連結清單實作的，在建立事務快照之後需要保留針對這個事務的所有更改，友善後續的事務復原，而在同一行頻繁更新多次，這會造成read snapshot 顯著變慢，周遊UNDO LOG 進行重放。而對于MyRocks來說，會為每一行維護一個版本。

恢複資料的時候MyRocks 提供了Bulkload特性，性能顯著高于Rocksdb。

資料備份功能的實作是實體複制一個副本的執行個體。這個過程是在Rocksdb 打一個checkpoint ,并且會将所有的SSTs和WAL files 發送到一個備份的地方。

4.3.2 即使有很多二級索引也能提供很好的擴充能力

MyRocks 中在操作二級索引的時候不會産生随機讀IO。這個相比于Innodb的in-place update來說确實是很有優勢。在MyRocks中 insert操作就是Rocksdb的Put，update操作對應Rocksdb的 SingleDelete + Put，delete 二級索引對應 Rocksdb 的 SingleDelete。可以看到這個過程不會産生額外的讀請求，而在Innodb中則需要額外的Get/GetForUpdate 操作。在上面的Bullkload 優勢的測試中也能夠看到MyRocksd 在這個場景下本身性能也比 Innodb有優勢。

4.3.3 在替換和插入操作中不需要額外的讀取

大體和前面的提到的優勢類似。在MySQL 的 REPLACE 文法中需要插入或者覆寫一個新行，Innodb 需要讀一下新插入行的主鍵，确認這個主鍵所在的行是否存在，如果存在，那先删除舊行，再插入新行；如果不存在，則直接插入新行。這個操作對于 MyRocks 來說隻需要一次 rocksdb 的Put 就可以。

4.3.4 擁有更多壓縮的空間

MyRocks 的 Rocksdb 本身資料是分層存儲，如果每一層都被填充滿，那90% 的資料會落在最後一層。這樣可以在不同的層使用不同的壓縮算法，大多數情況我們讀請求是落在靠近上層的資料中，這樣可以針對L0 + L1 使用更高效的壓縮/解壓縮算法 LZ4，在最後一層的壓縮算法可以算則 Zstandard 算法。

5. 生産環境的資料遷移工具

以上功能facebook 工程師在一年半左右的時間完成了開發和功能正确的測試。接下來就開始從Innodb的執行個體進行資料遷移到 MyRocks 執行個體。畢竟 MyRocks 還沒有在生産環境跑過，這個時候為了防止軟體内部的一些cornor case 的異常問題，遷移之前将 MyRocks 的執行個體的複制機制禁止掉了，也就是僅僅從 Innodb 執行個體中拉取資料到 MyRocks執行個體，且讀流量不會切到 MyRocks 執行個體上，這樣能夠保證即使拉取資料到 MyRocks 之上出現core 或者資料一緻性問題時不會影響生産環境的正常服務。這個時候，針對 MyRocks 的各種異常測試以及自動化工具都能安全放心的跑起來了。

先從導出 Innodb 的表，通過 MyRocks 的bulkload 功能導入到 MyRocks執行個體。因為 Innodb 具有聚集索引，從它的執行個體中導出的資料已經是按照主鍵排過序的，這個時候就可以直接 bulkload 到 MyRocks中。對于每一個副本集，可以按照每小時 200-300G的速度遷移到 MyRocks 執行個體中。接下來詳細看看具體的資料遷移工具實作和資料一緻性校驗工具的實作。

5.1 MyShadow - shadow 查詢測試

這個工具出現的目的是為了讓上限之前的 MyRocks 執行個體能夠在生産環境的 workload下得到足夠多的穩定性和性能測試，包括确認 CPU 和 IO 使用率是否在和Innodb的對比預期之内以及一些預期之外的奔潰異常回歸測試是否能夠保證資料的可靠性。

MyShadow 實作架構如下：

在facebook的生産環境中，維護了一個 MySQL Audit 插件，能夠捕獲生産環境的workload并記錄在内部的日志服務中。MyShadow 支援從日志服務中将這一些捕獲的生産環境的請求重放到目标 MyRocks 執行個體，進而能夠在 MyRocks 上線之前就得到生産環境 workload 的測試情況。

這裡 MyShadow 的實作應該是使用 Rocksdb 的 trace_replay 功能

5.2 資料正确性校驗

使用一個新的資料庫線上替換原有的資料庫，在資料正确性方面是一個非常大的挑戰。以Innodb 的資料作為參考（原本生産環境的資料，正确性沒有問題），通過工具将其中的資料和寫入到 MyRocks 中的資料進行對比來确認 MyRocks 中資料的正确性。

這個正确性校驗工具主要有三種模式：Single, Pair 和 Select。

Single 模式主要用來檢查處于同一張表的 Primary keys 和 Secondary keys 的一緻性，具體是驗證是通過檢查所處表内的行數和重疊列的校驗和是否相同來确認的。這個過程能夠發現一些 MyRocks 或 Rocksdb 内部的一些bug。比如 Rocksdb compaction的bug，沒有正确處理Delete 類似的key，導緻索引不一緻。
Pari 模式對整個表進行掃描，通過read snapshot 擷取表内某一個狀态下的 Innodb 執行個體和 MyRocks 執行個體之間的 row counts和校驗和。這個模式能夠發現在Single mode下未發現的問題
Select 模式。這個模式有點類似 pair 模式，但并不是掃描整張表。而是對MyShadow 捕獲的 workload 執行 select 語句，并比較語句的結果在 Innodb 執行個體和 MyRocks 執行個體之間的差異，如果不同則表示資料不一緻。

關于資料校驗過程的步驟可以參考如下圖：

其中：Primary instance1 是 innodb執行個體，Replice instance2,3 是 MyRocks執行個體

5.3 實際的遷移過程

在通過了 MyShadow 的測試和資料正确性的測試之後，接下來就要将MyRocks 執行個體正式移植到生産環境了。

遷移過程分為三個階段（如下圖），持續了整整一年。

第一步（上圖中的第二步）當時每一個 MySQL 副本集中有 6個 MySQL 執行個體（1primary, 5replicas）。這個時候将兩個副本中的執行個體切換為 MyRocks。 MyRocks 執行個體會從 Innodb的 Primary 執行個體複制資料。讀請求主要是落在副本執行個體上，是以這個配置下跑幾個月能夠再次确認 MyRocks 時能夠扛住讀流量。
第二步（上圖中的第三步），這一步開始之前經過了很長時間的測試。因為這一步需要将 Primary instance 切換為 MyRocks，這讓facebook 的工程師們有點慌。因為切換之後所有的寫入都會經過 Primary，事關資料一緻性的核心。在覺得解決了 “所有” 的問題之後，這一步開始了。将 Primary 執行個體切換為了 MyRocks，保留三個innodb 的副本執行個體。切換之後他們監控了整個應用所有的異常行為，發現，，，都正常（嚴謹中的嚴謹）。這之後又跑了大概幾個月的時間，沒有什麼問題之後終于能夠确認所有的執行個體都能夠切換到 MyRocks 了。
第三步替換所有的執行個體為 MyRocks。整個UDB中有成千上萬個 MySQL 副本集，後續的遷移就是時間上的花費了。但還有一些副本集中儲存有 Innodb 執行個體，來持續進行 Innodb 和 MyRocks 的對比測試。

6. 性能

直接貼一張表來看看

最初的目标是解約 50% 的伺服器，這裡可以看到切換到MyRocks 之後空間成本下降了 63%，而且能夠提供更有優勢的CPU使用率和更低的寫放大（寫放大降低了4倍），在以百PB為量級的資料庫中，這樣的優化效果可以說是非常成功了。

7. 總結

強無敵的PE(production engineer)，是MySQL和Rocksdb 的核心開發者，對現有項目有非常深入的底層了解，同時也對 Innodb 和 Rocksdb 的特性有足夠的了解，能夠在較短得時間内分析清楚問題并在實踐中能快速排查解決遷移到生産環境遇到的問題。這才保證項目的高效性和成功性。
對底層硬體存儲和作業系統的運作機制有足夠的了解也很重要
完整高效的自動化遷移工具能夠讓最終的效率事半功倍。
完善的監控體系能夠讓問題排查高效且有迹可循。
工具的相容性，像MyShandow 和 data correctness tool 就相容 Innodb 和 MyRocks，這樣友善兩者的性能對比。
用好Rocksdb 不容易，這玩意參數太多了。。。。。。一些結合workload 的最優參數的摸索估計還需要不少時間(也被吐槽了，，，不可否認的是引擎的靈活性非常重要，能夠适用更多的可優化的場景)。