Accordion:HBase 「呼吸式」內存壓縮算法

　　介紹：

　　現今，HBase 所支持的現代產品對Hbase讀寫性能的期望越來越高。理想情況下，HBase 也希望在保證其可靠的持久存儲的前提下能同時享有內存資料庫的速度。社區的貢獻者在HBase 2.0中引入了一種名為Accordion的新算法，這促使Hbase又朝著其理想的目標邁出了重要的一步。

　　Hbase RegionServer 負責將數據劃分到多個Region中。RegionServer 內部（垂直）的可伸縮性能對於最終用戶體驗以及整個系統的利用率至關重要。Accordion 算法通過更好地利用RAM來進一步提高RegionServer的可擴展性。Accordion 算法可以實現在內存中容納更多的數據，並且降低寫入磁碟的頻率。這正好是多個場景下我們所需要的。首先，HBase的磁碟佔用和寫入放大因此減少；其次，更多數據的讀取和寫入將直接從RAM中獲得，更少的讀取和寫入基於磁碟I/O，換句話說，HBase的性能得到提高。在2.0版本之前，這些不同的指標是不能同時滿足的，並且相互制約。而通過Accordion 算法，它們都同時得到了改善。

　　Accordion 的靈感來自於HBase的LSM樹形設計模式。一個 HBase Region 被存儲為一系列可查找的鍵值對映射。最上面是一個可變內存存儲，稱為MemStore ，接收最新Put進來的數據。其餘的是不變的HDFS文件，稱為HFile 。一旦MemStore寫滿，它將被刷新到磁碟，從而創建一個新的HFile。HBase採用多版本並發控制，也就是說，MemStore將所有修改後的數據存儲為獨立版本。因此，一條數據的多個版本同時駐留在MemStore和HFile層中。當一個讀操作進來，Hbase會優先掃描BlockCache中的Hfile拿取最新的版本數據。為了減少磁碟訪問次數，HFile在後臺異步進行壓縮合併，這個過程將真正清除已刪除的數據，合併小的HFile文件。

　　通過將隨機 application-level I/O轉換為順序磁碟I/O，LSM樹可提供出色的寫入性能。但是，傳統的設計並未嘗試壓縮內存數據。這源於歷史原因：LSM樹設計當時，RAM還是非常緊缺的資源，因此MemStore的容量很小。隨著硬體環境的不斷變化，由RegionServer管理的整個MemStore可能為數千兆字節，這就為Hbase優化留下了大量空間。

　　Accordion 算法重新將LSM原理應用於MemStore，以便當數據仍在RAM中時消除冗餘和其他開銷。這樣做可以減少Flush到HDFS的頻率，從而減少寫入放大和整個磁碟佔用空間。隨著刷新次數的減少，MemStore寫入磁碟的頻率會降低，因此寫入性能會提高。磁碟上的數據較少也意味著對塊緩存的壓力較小，命中率較高，更佳的讀響應。最後，減少磁碟寫入也意味著在後臺發生較少的壓縮，即讀取和寫入周期將縮短。總而言之，內存壓縮算法的效果可以被看作是一個催化劑，使整個系統的運行速度更快。

　　目前Accordion提供了兩個級別的內存壓縮：basic 級別和 eager 級別。前者適用於所有數據更新模式的通用優化，後者對於高數據流的應用程式非常有用，如生產-消費隊列，購物車，共享計數器等。所有這些使用案例都會對rowkey進行頻繁更新，生成多個冗餘版本的數據，這些情況下Accordion算法將發揮其價值。但另一方面，eager 級壓縮優化可能會導致更大的計算開銷（更多內存副本和垃圾收集），這可能會影響數據寫入時的響應時間。如果MemStore開啟了 MemStore-本地分配緩衝區（MSLAB）配置則開銷會很高。所以建議不要將此配置與eager級壓縮結合使用。

　　如何使用

　　內存壓縮可以在全局和列族級別進行配置。支持三種級別配置：none (傳統實現), basic, and eager。

　　默認情況下，所有表都是basic內存壓縮。可以在hbase-site.xml中覆蓋寫這個全局配置，如下所示：

　　性能增益

　　我們通過廣受歡迎的雅虎雲服務基準測試YCSB對HBase進行了廣泛的測試。我們的實驗使用了100-200 GB數據集，並且執行了各種具有代表性的工作負載。結果表明Accordion算法所帶來的性能增益得到的顯著提升。

　　重尾 (Zipf) 分布：第一個實驗會執行一個工作負載，其中rowkey遵循大多數現實生活場景中出現的Zipf分布。在這種情況下，當100％的操作是寫入操作時，Accordion實現寫入放大率降低30％，寫入吞吐量提高20％，GC降低22％。當50％的操作是讀取時，尾部讀取延遲減少12％。

　　均勻分布：第二個實驗的工作量是所有rowkey都均衡分布。在此情況下，在100％寫入的情況下，Accordion的寫入放大率降低25％，寫入吞吐量提高50％，GC降低36％。尾部讀取延遲不受影響（由於沒有本地化，這是預期的）。　　

Accordion如何工作

　　高級設計：

　　Accordion推出了CompactingMemStore，一個內部使用壓縮策略的MemStore實現。與默認的MemStore相比，它將所有數據保存在一個單片數據結構中，Accordion將其作為一連串的segment來管理。最新的segment，稱為active segment（段），是可變的，用來接收Put操作。一旦達到溢出條件（默認情況下，32MB-25％的MemStore大小），active segment 被移動到管道（ in-memory pipeline）中，並置為不可變segment，我們稱之為內存刷新（in-memory flush）。Get 操作通過掃描這些 segment 和 HFiles 拿取數據（後者通過塊緩存進行訪問，與往常訪問HBase一樣）。

　　CompactingMemStore 可能會不時在後臺合併多個不可變段，從而創建更大更精簡的段。因此，管道是「會呼吸的」（擴張和收縮），類似於手風琴波紋管，所以我們也將Accordion 譯為手風琴。

　　當RegionServer決定刷新一個或多個MemStore到磁碟以釋放內存時，它會考慮刷新CompactingMemStore中已經移入管道中的segment到磁碟。基本原理是延長MemStore有效管理內存的生命周期，以減少整體I / O。當刷新發生時，管道中所有的segment 段將被移出合成一個快照， 合併並流式傳輸形成新的HFile。

　　圖1顯示了CompactingMemStore與傳統設計的結構。

　　分段結構：

　　與默認的MemStore類似，CompactingMemStore在單元存儲之上維護一個索引，以允許通過鍵快速搜索。不同的是，MemStore索引被實現為一個Java skiplist（ConcurrentSkipListMap ）， 一種動態但奢侈的數據結構，用於管理大量小對象。CompactingMemStore 則在不可變的 segment 索引之上上實現了高效且節省空間的扁平化布局。這種通用優化可以幫助所有壓縮策略減少RAM開銷，使數據幾乎不存在冗餘。一旦將一個段添加到管道中，CompactingMemStore 就將其索引序列化為一個名為CellArrayMap 的有序數組，該數組可以快速進行二進位搜索。

　　CellArrayMap既支持從Java堆內直接分配單元，也支持MSLAB的自定義分配（堆內或堆外），實現差異通過被索引引用的KeyValue對象抽象出來（圖2）。CellArrayMap本身始終分配在堆內。

　　壓縮算法：

　　內存中壓縮算法在管道中的Segment上維護了一個單一的扁平化索引。這樣的設計節省了存儲空間，尤其是當數據項很小時，可以及時將數據flush至磁碟。單個索引可使搜索操作在單一空間進行，因此縮短了尾部讀取延遲。

　　當一個active segment被刷新到內存時，它將排隊到壓縮管道，並立即觸發一個異步合併調度任務。該調度任務將同時掃描管道中的所有段（類似於磁碟上的壓縮）並將它們的索引合併為一個。basic和eager 壓縮策略之間的差異體現在它們處理單元數據的方式上。basic壓縮不會消除冗餘數據版本以避免物理複製; 它只是重新排列KeyValue對象的引用。eager壓縮則相反，會過濾出冗餘數據。但這是以額外的計算和數據遷移為代價的。例如，在MSLAB存儲器中，倖存的單元被複製到新創建的MSLAB中。當數據高度冗餘時，壓縮開銷的代價就變得有意義了。

　　未來的壓縮可能會在basic壓縮策略和eager壓縮策略之間實現自動選擇。例如，該算法可能會在一段時間內嘗試eager壓縮，並根據所傳遞的值（如：數據被刪除的比例）安排下一次壓縮。這種方法可以減輕系統管理員的先驗決定，並適應不斷變化的訪問模式。

　　結束語

　　本文，我們介紹了Accordion的基本原理，配置，性能增益以及內存壓縮算法的一些細節。如有紕漏之處，還望多多指教。

第三十屆CIO班招生 法國布雷斯特商學院碩士班招生 北達軟EXIN網絡空間與IT安全基礎認證培訓 北達軟EXIN DevOps Professional認證培訓

責編：zhangxuefeng