Uploaded image for project: 'HBase'
  1. HBase
  2. HBASE-20312

CCSMap: A faster, GC-friendly, less memory Concurrent Map for memstore



    • New Feature
    • Status: Patch Available
    • Major
    • Resolution: Unresolved
    • None
    • 3.0.0-beta-2
    • regionserver
    • None
    • TODO


      Now hbase use ConcurrentSkipListMap as memstore's data structure.
      Although MemSLAB reduces memory fragment brought by key-value pairs.
      Hundred of millions key-value pairs still make young generation garbage-collection(gc) stop time long.


      These are 2 gc problems of ConcurrentSkipListMap:

      1. HBase needs 3 objects to store one key-value on expectation. One Index(skiplist's average node height is 1), one Node, and one KeyValue. Too many objects are created for memstore.

      2. Recent inserted KeyValue and its map structure(Index, Node) are assigned on young generation.The card table (for CMS gc algorithm) or RSet(for G1 gc algorithm) will change frequently on high writing throughput, which makes YGC slow.


      We devleoped a new skip-list map called CompactdConcurrentSkipListMap(CCSMap for short),
      which provides similary features like ConcurrentSkipListMap but get rid of Objects for every key-value pairs.

      CCSMap's memory structure is like this picture:


      One CCSMap consists of a certain number of Chunks. One Chunk consists of a certain number of nodes. One node is corresspding one element. This element's all information and its key-value is encoded on a continuous memory segment without any objects.

      1. all insert,update,delete operations is lock-free on CCSMap.
      2. Consume less memory, it brings 40% memory saving for 50Byte key-value.
      3. Faster on small key-value because of better cacheline usage. 20~30% better read/write troughput than ConcurrentSkipListMap for 50Byte key-value.

      CCSMap do not support recyle space when deleting element. But it doesn't matter for hbase because of region flush.

      CCSMap has been running on Alibaba's hbase clusters over 17 months, it cuts down YGC time significantly. here are 2 graph of before and after.





        1. 1.1.2-ccsmap-number.png
          142 kB
          Chance Li
        2. ccsmap-branch-1.1.patch
          241 kB
          Xiang Wang
        3. HBASE-20312-1.3.2.patch
          291 kB
          Andrew Kyle Purtell
        4. HBASE-20312-master.v1.patch
          414 kB
          Chance Li
        5. HBASE-20312-master.v2.patch
          414 kB
          Chance Li
        6. HBASE-20312-master.v3.patch
          413 kB
          Chance Li
        7. HBASE-20312-master.v4.patch
          416 kB
          Chance Li
        8. HBASE-20312-master.v5.patch
          417 kB
          Chance Li
        9. HBASE-20312-master.v6.patch
          417 kB
          Chance Li
        10. HBASE-20312-master.v7.patch
          416 kB
          Chance Li
        11. HBASE-20312-master.v8.patch
          420 kB
          Chance Li
        12. HBASE-20312-master.v9.patch
          420 kB
          Chance Li
        13. hits.png
          63 kB
          Michael Stack
        14. jira1.png
          61 kB
          Xiang Wang
        15. jira2.png
          32 kB
          Xiang Wang
        16. jira3.png
          24 kB
          Xiang Wang
        17. off-heap-test-put-master.png
          243 kB
          Chance Li
        18. on-heap-test-put-master.png
          233 kB
          Chance Li

        Issue Links



              heliangjun Liangjun He
              junnoye Xiang Wang
              0 Vote for this issue
              46 Start watching this issue