从数据结构比较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