HBase內存管理之MemStore的實現原理和優化
Java工程中內存管理總是一個繞不過去的知識模塊，無論HBase、Flink還是Spark等，如果使用的JVM堆比較大同時對讀寫延遲等性能有較高要求，一般都會選擇自己管理內存，而且一般都會選擇使用部分堆外內存。
HBase系統中有兩塊大的內存管理模塊，一塊是MemStore ，一塊是BlockCache，這兩塊內存的管理在HBase的版本迭代過程中不斷進行過各種優化，接下來筆者結合自己的理解，將這兩個模塊的內存管理迭代過程通過幾篇文章梳理一遍，相信很多優化方案在各個系統中都有，舉一反三，個人覺得對內核開發有很大的學習意義。本篇文章重點集中介紹MemStore內存管理優化。
基于跳表實現的MemStore基礎模型
實現MemStore模型的數據結構是SkipList(跳表)，跳表可以實現高效的查詢\插入\刪除操作，這些操作的期望復雜度都是O(logN)。另外，因為跳表本質上是由鏈表構成，所以理解和實現都更加簡單。這是很多KV數據庫(Redis、LevelDB等)使用跳表實現有序數據集合的兩個主要原因。跳表數據結構不再贅述，網上有比較多的介紹，可以參考。
JDK原生自帶的跳表實現目前只有ConcurrentSkipListMap(簡稱CSLM，注意：ConcurrentSkipListSet是基于ConcurrentSkipListMap實現的)。ConcurrentSkipListMap是JDK Map的一種實現，所以本質上是一種Map，不過這個Map中的元素是有序的。這個有序的保證就是通過跳表實現的。ConcurrentSkipListMap的結構如下圖所示：
基于ConcurrentSkipListMap這樣的基礎數據結構，按照最簡單的思路來看，如果寫入一個KeyValue到MemStore中，肯定是如下的寫入步驟：
- 在JVM堆中為KeyValue對象申請一塊內存區域。
- 調用ConcurrentSkipListMap的put(K key, V value)方法將這個KeyValue對象作為參數傳入。
圖1 基于跳表實現的最基礎MemStore模型
對吧，這樣的話，實現非常簡單。根據Key查詢可以利用跳表的有序性。但是這樣的內存存儲模型會有很多問題(具體見下節)，本文就基于這個最原始的模型開始優化之旅。
再看圖1這個存儲模型，可以發現MemStore從內存管理上來說主要由兩個部分組成，一個是原生KeyValue的內存管理，見上圖下半部分;一個是ConcurrentSkipListMap的內存管理，見上圖上半部分。接下來筆者分別就這兩個部分的內存管理優化，分成兩個小節進行深入介紹。
MemStore中原生KeyValue對象內存存儲優化
對于HBase這樣基于LSM實現的MemStore來說，上述實現方案每寫入一個KeyValue，在沒有寫入ConcurrentSkipList之前就需要申請一個內存對象，可以想見，對于很多寫入吞吐量幾萬每秒的業務來說，每秒就會有幾萬個內存對象產生，這些對象會在內存中存在很長一段時間，對應的會晉升到老生代，一旦執行了flush操作，老生代的這些對象會被GC回收掉。這樣的內存玩法，會導致JVM的GC壓力非常大。GC壓力主要來源于：這些內存對象一旦晉升到老生代，執行完Major GC后會存在大量的非常小的內存碎片，這些內存碎片會引起頻繁的Full GC，而且每次Full GC的時間會異常的長。
- MemStore引入MemStoreLAB
針對上面的問題，MemStore借鑒TLAB(Thread Local Allocation Buffer)機制，實現了MemStoreLAB，簡稱MSLAB。基于MSLAB實現寫入的核心流程如下：
- 一個KeyValue寫入之后不再單獨為KeyValue申請內存，而是提前申請好一個2M大小的內存區域(Chunk)。
- 將寫入的KeyValue順序復制到申請的Chunk中，一旦Chunk寫滿，再申請下一個Chunk。
- 將KeyValue復制到Chunk中后，生成一個Cell對象(這個Cell對象在源碼中為ByteBufferChunkKeyValue)，這個Cell對象指向Chunk中的KeyValue內存區域。
- 將這個Cell對象作為Key和Value寫入ConcurrentSkipListMap中。
- 原生的KeyValue對象寫入到Chunk之后就沒有再被引用，所以很快就會被Young GC回收掉。
基于MSLAB的MemStore可以表征為下圖：
圖2 基于MSLAB實現的MemStore示意圖
對比圖1和圖2，引入MSLAB之后MemStore實現稍顯復雜，后者引入了兩個長壽內存對象，一個是2M的Chunk對象，一個是指向KV內存區域的Cell對象，這兩種內存對象都會晉升到老生代。這里分別針對這兩個內存對象進行解讀：
- 引入2M大小的Chunk對象之后，數據寫入就不再需要為每個KeyValue申請一個內存對象，這樣可以大大降低內存碎片的產生。
- 那Cell對象不會引起內存碎片?這個筆者查閱了很多資料都沒有找到相關的說明，個人理解是因為Cell相對原生KeyValue來說占用內存小的多，可以一定程度上可以忽略。Cell與KeyValue對象分別占用內存大小如下所示：
ByteBufferChunkKeyValue類(Cell對象)的字段如下：
- protected final ByteBuffer buf;
- protected final int offset;
- protected final int length;
- private long seqId = 0;
對象大小可以表示為對象頭和各個字段的大小總和，其中對象頭占16Byte，Reference類型占8Byte，int類型占4Byte，long類型占8Byte，Cell對象大小可以表示為：
- ClassSize.OBJECT
- + ClassSize.REFERENCE
- + (2 * Bytes.SIZEOF_INT)
- + Bytes.SIZEOF_LONG
- = 16 + 8 + 2 * 4 + 8 = 40 Byte。
原生KeyValue對象大小為：
- ClassSize.OBJECT(16)
- + Key Length(4)
- + Value Length(4)
- + Row Length(2)
- + FAMILY LENGTH(1)
- + TIMESTAMP_TYPE LENGTH(9)
- + length(row) + length(column family)
- + length(column qualifier)
- + length(value)
- =
- 36
- + length(row) + length(column family)
- + length(column qualifier) + length(value)
按照一個KV中length(row) + length(column family) + length(column qualifier) + length(value)總計84Byte算，原生KeyValue對象大小為120Byte，為Cell對象的3倍。
引入MSLAB后一定程度上降低了老生代內存碎片的產生，進而降低了Promotion Failure類型的Full GC產生。那還有沒有進一步的優化空間呢?針對Chunk，還有兩個大的優化思路：
- MemStore引入ChunkPool
MSLAB機制中KeyValue寫入Chunk，如果Chunk寫滿了會在JVM堆內存申請一個新的Chunk。引入ChunkPool后，申請Chunk都從ChunkPool中申請，如果ChunkPool中沒有可用的空閑Chunk，才會從JVM堆內存中申請新Chunk。如果一個MemStore執行flush操作后，這個MemStore對應的所有Chunk都可以被回收，回收后重新進入池子中，以備下次使用。基本原理如圖3、圖4所示：
圖3 基于ChunkPool實現的Chunk管理模型
每個RegionServer會有一個全局的Chunk管理器，負責Chunk的生成、回收等。MemStore申請Chunk對象會發送請求讓Chunk管理器創建新Chunk，Chunk管理器會檢查當前是否有空閑Chunk，如果有空閑Chunk，就會將這個Chunk對象分配給MemStore，否則從JVM堆上重新申請。每個MemStore僅持有Chunk內存區域的引用，如圖3中MemStoreLAB的小格子。
下圖是MemStore執行Flush之后，對應的所有Chunk對象中KV落盤形成HFile，這部分Chunk就可以被Chunk管理器回收到空閑池子。
圖4 MemStore Flush過程中Chunk回收過程
使用ChunkPool的好處是什么呢?因為Chunk可以回收再使用，這就一定程度上降低了Chunk對象申請的頻率，有利于Young GC。
- MemStore Offheap實現
除過ChunkPool之外，HBase 2.x版本針對Chunk對象優化的另一個思路是將Chunk使用的這部分內存堆外化。關于堆外內存的細節內容，筆者將會在下篇文章重點分析，這篇文章只做個簡單介紹。
Chunk堆外化實現比較簡單，在創建新Chunk時根據用戶配置選擇是否使用堆外內存，如果使用堆外內存，就使用JDK提供的ByteBuffer.allocateDirect方法在堆外申請特定大小的內存區域，否則使用ByteBuffer.allocate方法在堆內申請。如果不做配置，默認使用堆內內存，用戶可以設置hbase.regionserver.offheap.global.memstore.size這個值為大于0的值開啟堆外，表示RegionServer中所有MemStore可以使用的堆外內存總大小。
- 原生KeyValue對象內存存儲優化總結
基于原生KeyValue直接寫入ConcurrentSkipListMap方案，HBase在之后的版本中不斷優化，針對原生KeyValue內存管理部分分別采用MemStoreLAB機制、ChunkPool機制以及Chunk Offheap機制三種策略，對GC性能進行持續優化。
第一節我們提到MemStore內存管理分為原生KeyValue內存管理和ConcurrentSkipListMap內存管理兩個部分，第二節重點介紹了HBase針對原生KeyValue內存管理所采用的3種優化方案。接下來第三節首先介紹JDK原生ConcurrentSkipListMap在內存管理方面的主要問題，以及HBase在2.x版本以及3.x版本針對ConcurrentSkipListMap內存管理問題進行優化的兩個方案。
ConcurrentSkipListMap數據結構存在的問題以及優化方案
一個KV在MemStore中的旅程
經過上面知識的鋪墊我們知道，一個KV寫入MemStore會經過如下幾個核心步驟：
- 在Chunk中申請一段與KV相同大小的內存空間將KV拷貝進去。
- 生成一個Cell對象，該對象包含指向Chunk中對應數據塊的指針、offsize以及length。
- 將這個Cell對象分別作為Key和Value插入到CSLM表示的跳表Map中。
有了CSLM這樣的跳表之后，查詢就可以在O(N)時間復雜度內完成。但是，JDK實現的CSLM跳表在內存使用方面有些粗糙，導致內存中產生了大量意義不大的Java對象，這些Java對象的頻繁產生一方面導致內存效率使用比較低，另一方面會引起比較嚴重的Java GC。為什么JDK實現的CSLM跳表會有這樣的問題?接著往下看。
- MemStore ConcurrentSkipListMap數據結構存在的問題
原生ConcurrentSkipListMap邏輯示意圖如下圖所示：
圖5 CSLM示意圖
JDK自帶的CSLM每個節點都是一個對象，其中最底層節點是Node對象，其他上層節點是Index對象。Node對象和Index對象的核心字段可以參考CSLM源碼實現：
其中Node對象由一個key、一個value以及指向下一個Node節點的引用組成。Index對象由一個Node節點引用、向下和向右的引用組成。
根據上述代碼可以知道：
- 每個Node對象有3個引用變量，分別指向Key(Cell對象)、Value(Cell對象)以及Next Node。
- 每個Index對象有3個引用變量，分別指向代表的Node節點，下層Index節點以及右側Index節點。
假設業務寫入50M規模的KV，那寫入到MemStore后，除了正常存儲KV數據占用的Chunk對象外，CSLM占用的對象和內存分別有多少呢?
對象數：50M個Node對象，假如跳表中level N層的Index節點個數是50M/2^(N+2)，那么總共會有50M/4個Index對象。整個CSLM一共有62.5M個對象。
內存占用情況(均認為JVM設置大于32G，未開啟壓縮指針)：
(1)Node對象
- 50M * (ClassSize.OBJECT + ClassSize.REFERENCE + ClassSize.REFERENCE + ClassSize.REFERENCE) ＝50M * (16 + 8 + 8 + 8) = 2000M
(2)Index對象
- 12.5M * (ClassSize.OBJECT + ClassSize.REFERENCE + ClassSize.REFERENCE + ClassSize.REFERENCE) ＝12.5M * (16 + 8 + 8 + 8) = 500M
總內存占用2500M。假設業務寫入的KV為50Byte，那總的數據量為2500M。為了存儲這2500M大小的數據，MemStore又產生了額外的2500M內存。
- CompactingMemStore如何優化這個困境
CompactingMemStore的核心工作原理如圖所示：
圖6 CompactingMemStore核心工作原理示意圖
- 一個Cell寫入到Region后會先寫入MutableSegment中。MutableSegment可以認為就是一個小的MemStore，MutableSegment包含一個MSLAB存儲Chunk，同時包含一個ConcurrentSkipListMap。
- 默認情況下一旦MutableSegment的大小超過2M，就會執行In-memory Flush操作，將MutableSegment變為ImmutableSegment，并重新生成一個新的MutableSegment接收寫入。ImmutableSegment有多個實現類，In-memory Flush生成的ImmutableSegment為CSLMImmutableSegment，可以預見這個ImmutableSegment在數據結構上也是使用CSLM。
- 每次執行完In-memory Flush之后，RegionServer都會啟動一個異步線程執行In-memory Compaction。In-memory Compaction的本質是將CSLMImmutableSegment變為CellArrayImmutableSegment或者CellChunkImmutableSegment，這才是CompactingMemStore最核心的地方。那什么是CellArrayImmutableSegment/CellChunkImmutableSegment呢?為什么要做這樣的轉換?接著往下看。
- In-memory Compaction機制
現在我們需要回過頭來想想這兩個問題：
- 為什么要將一個大的MemStore切分成這么多小的Segment?這么設計的初衷是為In-memory Compaction做準備，只有將MemStore分為MutableSegment和ImmutableSegment，才可能基于ImmutableSegment進行內存優化。
- 如何對ImmutableSegment進行內存優化?答案是將CSLMImmutableSegment變為CellArrayImmutableSegment或者CellChunkImmutableSegment。通過上文的介紹我們知道，CSLM這種數據結構對內存并不友好，因為ImmutableSegment本身已經不再接收任何更新刪除寫入操作，只允許讀操作，這樣的話CSLM就可以轉換為對內存更加友好的Array或者其他的數據結構。這個轉換就是In-memory Compaction。
理清楚上面兩個問題，我們再來看看In-memory Compaction的主要流程。如果參與Compaction的Segment只有一個，我們稱之為Flatten，非常形象，就是將CSLM拉平為Array或者Chunk，示意圖如下圖圖7所示。
圖7 In-Memory Compaction之Flatten示意圖
緊接著就有兩個問題：
- CSLMImmutableSegment是如何拉平成CellArrayImmutableSegment?
- CellArrayImmutableSegment和CellChunkImmutableSegment分別是什么樣的數據結構?
CSLMImmutableSegment拉平成CellArrayImmutableSegment比較容易理解，順序遍歷CSLMImmutableSegment讀取出對應的Cell，順序寫入一個申請好的數組即可。所以直觀上看，CSLMImmutableSegment和CellArrayImmutableSegment相比就是將CSLM變成了一個數組。
那CellArrayImmutableSegment能不能進一步優化呢?是不是可以將Array[Cell]這樣一個在內存中不完全連續的對象轉變成一塊完全連續內容空間的對象，這種優化方式也比較自然，借鑒Chunk思路申請一塊2M的大內存空間，遍歷數組中的Cell對象，將其順序拷貝到這個Chunk(這種Chunk稱為Index Chunk，區別與存儲KV數據的Data Chunk)中，就變成了CellChunkImmutableSegment，將內存由不連續變為連續的一大好處就是變換后連續的內存區域可以在堆外管理，默認情況下In-memory Compaction會直接將CSLMImmutableSegment拉平成CellChunkImmutableSegment。
上述過程是只有一個Segment參與Compaction的流程。如果參與Compaction的Segment個數超過1個，會有兩種Compaction的形式：Merge和Compact。先說Merge，Merge的處理流程和Flatten基本一致，如In-Memory Compaction之Merge示意圖所示，左側兩個Segment進行合并形成右側一個大的CellChunkImmutableSegment，合并過程就是順序遍歷左邊兩個Segment，取出對應的Cell，然后順序寫入右邊CellChunkImmutableSegment中。
圖8 In-Memory Compaction之Merge示意圖
Compaction與Merge的處理流程基本相同，不同的是，Compaction在合并的過程中順序遍歷左邊兩個Segment，讀取對應Cell之后會檢測是否有多個版本的Cell，如果存在超過設置版本數的Cell，就將老版本的Cell刪掉。因為存在原始KV的變更，所以新生成的Data Chunk會進行重建，這是和Merge最大的不同。如In-Memory Compaction之Compaction示意圖所示，右側新生成的CellChunkImmutableSegment的Data Chunk是經過重建過的。
圖9 In-Memory Compaction之Compaction示意圖
CompactingMemStore通過將CSLM數據結構變成Array或者Chunk，優化了CSLM數據結構本身內存利用效率低的問題，提升GC效率。另外，提升內存利用率可以使MemStore中存儲下更多的KV數據，進而減少Flush和Compaction發生的頻率，提升整個HBase集群的性能。
CCSMap又是如何優化CSLM?
CCSMap全稱CompactedConcurrentSkipListMap，是阿里巴巴內部版本為了優化CSLM數據結構內存利用效率低所實現的一個新的數據結構。CCSMap數據結構的基本理念是將原生的ConcurrentSkipListMap進行壓縮，壓縮的直觀效果如下圖所示：
圖10 CCSMap數據結構邏輯示意圖
上圖中上面結構是原生的CSLM數據結構，下面是CCSMap數據結構，很明顯，主要是將Index對象壓縮到了Node對象上，數據寫入/讀取流程和CSLM基本上一致。壓縮后可以抹掉Index對象，但是這樣的優化顯然不是全部。接下來的優化才是重點。
CCSMap數據結構可以認為只有一個Node對象(Index可以理解為Node對象的一個字段)，既然只有一種對象，是否可以借鑒MSLAB的思路將Node對象順序存儲到固定大小的Chunk中，這樣做的好處顯而易見：整個Chunk可以以大塊申請，同時可以在堆外申請。CCSMap就是基于這個思路進行的物理存儲設計，筆者根據相關Jira上給出的資料以及閱讀源代碼畫出來的一個物理存儲示意圖：
圖11 CCSMap數據結構物理實現示意圖
這里有個認知的轉換，在CSLM數據結構下，KV就是KV，但是在CCSMap數據結構下，KV需要包裝成Node對象，Node對象的核心字段如下：
Node對象除了正常的KV Data之外，還有幾個比較重要的字段，meta字段主要存儲level，dataLen存儲數據大小，nextNode存儲當前節點的后繼節點，levelIndex是一個數組，表示這個Node在各個Level上Index指向的Node(NodeId)。這樣一個Node對象就可以完全表征邏輯示意圖中Node節點。
當然在具體實現中如何根據Index存儲的一個long類型的NodeId在CCSMap中找到對應的Node，這里面有個小小的技巧，就是這個long類型的NodeId前4Byte表示ChunkId，后4Byte表示對應Node在指定Chunk上的偏移量，這樣就可以根據NodeId輕松讀取到這個Node對應的內存空間。
根據物理存儲示意圖，KV數據寫入的時候會首先包裝成一個Node對象，包裝的過程主要是生成level字段，然后根據跳表規則不斷查找，確定對應的nextNode和levelIndex[]兩個字段。Node對象封裝好之后就可以順序持久化到Chunk中。
CCSMap相比CSLM可以節省多少對象?多少內存?
- 減少多少對象?CCSMap將ConcurrentSkipListMap和KV對象一起放到Chunk中去了，所以沒有任何對象開銷，這點比原生的CSLM優秀了非常多。
- 減少了多少內存?還是假設業務寫入50M規模的KV，CCSMap中Node對象中long[] levelIndex會占用12.5M * 8Byte = 100M，另外，dataLen占用4Byte，nextNode占用8Byte，meta占用4Byte，總共占用50 * 16Byte = 800M。所以總計占用900M。相比CSLM的2500M，降低了64%。
MemStore內存進化總結
基于上述長篇大論，我們知道MemStore的內存主要分為兩部分，其中一部分是KV存儲本身，一部分是CSLM。文中第二節重點介紹了KV存儲本身的幾個優化思路，包括MSLAB、ChunkPool以及Chunk Offheap等，第三節分別重點介紹了使用CompactingMemStore和CCSMap兩種機制對CSLM數據結構進行優化的原理。其實，優化來優化去，最核心的落腳點還是能不能將對象順序持久化到連續一段內存(Chunk)上，抓住這個最終落腳點非常重要。
最后說點題外話，前一段時間JDK13發布，進一步增強了ZGC特性。ZGC應該是Java歷史上最大的改進之一，這點應該沒有任何疑問，TB級別的堆可以保證GC時間低于10ms，實際場景中128G內存最大GC時間才1.68ms。如果真是這樣的GC性能，可能很多現在我們做的各種內存管理優化在很多年之后都不再是問題。
