從資料結構比較HBase的3種memstore實作方案

HBase在寫入時會将資料暫存在memstore中，滿足一定條件後再刷到磁盤；

其實作主要有以下要求：

1. 既要快速讀取，還要快速寫入
2. 需要有序，以友善scan
3. 盡可能記憶體友好，減少gc

目前存在以下3種實作方案：

1. DefaultMemstore
2. CompactingMemstore
3. CCSMapMemStore

其核心的差異在于所采用的資料結構不同；

對于一個有序資料集合，通常用數組或連結清單的結構進行存放，二者具有如下特點：

• 連結清單：定位需要周遊，時間複雜度為O(N)，但新增不需要挪動現有元素；

• 數組：通過二分查找定位，時間複雜度為O(logN)，但新增麻煩，需要挪動現有元素；

  對比前述要求可知，連結清單和數組都無法同時滿足1和2；

常見的做法是給連結清單增加額外的索引結構，形成跳表，以空間換時間；

基于連結清單的跳表：給連結清單增加索引節點後，可通過二分查找定位，時間複雜度為O(logN)，并且新增時不需要挪動現有元素，但缺點是增加了很多節點，具體實作時意味着多了很多對象；

這個結構可滿足要求中的1和2，但不滿足3，Jdk中自帶的ConcurrentSkipListMap就是一種實作，簡稱CSLM；

還有一種思路，就是把跳表的所有節點進行合并，存放到數組結構中；

基于數組的跳表：通過記錄元素節點長度和其它節點位置，來展現跳表結構，即不要求資料按實體順序存放，也可通過二分查找，還不需要太多對象；

這個結構可以很好的滿足前述3點要求，那有沒有什麼缺點？由于節點位置都需要自己計算，對比連結清單跳表中的直接指派，實作上要略微複雜一些；

阿裡提供了一個這樣的實作叫CompactedConcurrentSkipListMap，簡稱CCSM，下面是issue中的附圖：

前述3種memstore所采用的資料結構如下圖所示：

DefaultMemstore的實作中，active是可變的資料集，接受目前的寫入操作，而snapshot是flusher線程基于之前的active生成，為不可變的資料集，這兩部分都采用了Jdk自帶的CSLM；

實際上由于snapshot部分不可變，不存在新增元素時需要移動現有元素的問題，是以用數組即可，可以減少跳表結構的額外節點開銷，這就是CompactingMemstore的主要優化思路；

具體實作時active會比較小，大約2M左右，是以額外節點的數量就會比較少，寫滿後會flush成同樣小的segment，然後compact等操作不停的将其轉成數組結構，并合并為少量大的segment；

CCSMapMemStore則是将整個跳表實作替換掉，無論是active還是snapshot，從最大程度上減少了對象的建立，也避免了CompactingMemstore中compact帶來的開銷；

阿裡提供的性能測試結果如下：

參考資料：

https://issues.apache.org/jira/browse/HBASE-14918 https://issues.apache.org/jira/browse/HBASE-20312 https://mp.weixin.qq.com/s/LPhfQmx0lhRayA_KQWD0-g