Accordion :一种HBase内存压缩算法

现如今，人们对基于HBase的产品的读写速度要求越来越高。在理想情况下，人们希望HBase 可以在保证其可靠的持久存储的前提下能并拥有内存数据读写的速度。为此，在HBase2.0中引入Accordion算法。

Hbase RegionServer 负责将数据划分到多个Region中。RegionServer 内部(垂直)的可伸缩性能对于最终用户体验以及整个系统的利用率至关重要。Accordion 算法通过提高对RAM利用来提升RegionServer扩展性。这样就使得内存中可以存放更多数据，从而降低了对磁盘的读取频率(即降低了HBase中磁盘占用和写入方法，更多的读写RAM，降低了对于磁盘的IO访问)。在HBase2.0之前，这些指标是不能同时满足的，并且相互限制，在引入Accordion之后，这一状况得到了改善。

Accordion算法来源于HBase核心架构LSM算法。在HBase Region 中，数据是按照key-value形式映射为可查找的存放，其中put进来的新数据以及一些topmost(靠前)数据存放在内存中(MemStore)，其余的为不变的HDFS文件，即HFile。当MemStore写满时，数据被flush到硬盘里，生成新的HFile文件。HBase采用多版本并发控制，MemStore将所有修改后的数据存储为独立版本。一条数据的多个版本可能同时存储在MemStore和HFile中。当读取一条多版本数据时，根据key从HBase扫描BlockCache中的HFile获取最新的版本数据。为了降低对磁盘的访问频率，HFiles在后台合并(即压缩过程，删除多余的cells，创建更大的文件)。

LSM通过将随机读写转换为顺序读写，从而提高了写入性能。之前的设计并未采用压缩内存数据，主要原因是在LSM树设计当初，RAM还是非常紧缺的资源，因此MemStore的容量很小。随着硬件不断提升，RegionServer管理的整个MemStore可能为数千兆字节，这就为HBase优化留下了大量空间。

Accordion算法重新将LSM应用于MemStore，以便当数据仍在RAM中时可以消除冗余和其他开销。这样做可以减少flush到HDFS的频率，从而降低了写入放大和磁盘占用。 随着flush次数的减少，MemStore写入磁盘的频率会降低，进而提高HBase写入性能。磁盘上的数据较少也意味着对块缓存的压力较小，提高了读取的响应时间。最终，减少对磁盘写入也意味着在后台压缩次数降低，即读取和写入周期将缩短。总而言之，内存压缩算法的效果可以被看作是一个催化剂，它使整个系统的运行速度更快。

目前Accordion提供了两个级别的内存压缩：basic 级别和 eager 级别。前者适用于所有数据更新的优化，后者对于高数据流的应用非常有用，如生产-消费队列，购物车，共享计数器等。所有这些使用案例都会对rowkey进行频繁更新，生成多个冗余版本的数据，这些情况下Accordion算法将发挥其价值。但另一方面，eager 级压缩优化可能会增加计算开销(更多内存副本和垃圾收集)，这可能会影响数据写入的响应时间。如果MemStore使用堆内MemStore-本地分配缓冲区(MSLAB)，这会导致开销增大。所以建议不要将此配置与eager级压缩结合使用。

如何使用

内存压缩可以在全局和列族级别配置。目前支持三种级别配置：none(传统实现)，basic和eager。默认情况下，所有表都是basic内存压缩。此配置可以在hbase-site.xml中修改，如下所示：

 

 

性能提高

通过利用YCSB(Yahoo Cloud Service Benchmark)对HBase进行了全面测试。试验中采用数据集大小为100-200 GB，结果表明Accordion算法对于HBase性能有显著的提升。

Heavy-tailed (Zipf)分布：在测试负载中国，rowkey遵循大多数现实生活场景中出现的Zipf分布。在这种情况下，当100%的操作是写入操作时，Accordion实现写入放大率降低30%，写入吞吐量提高20%，GC降低22%。当50%的操作是读取时，tail读取延迟降低12%。

均匀分布：第二个测试中rowkey都均衡分布。当100%的操作是写入操作时，Accordion的写入放大率降低25%，写入吞吐量提高50%，GC降低36%。tail读取延迟不受影响(由于没有本地化)。

Accordion如何工作

High Level设计：

Accordion引入了MemStore的内部压缩(CompactingMemStore)实现方法。与默认的MemStore相比，Accordion将所有数据保存在一个整的数据结构中用segment来管理。最新的segment，称为active segment，是可变的，可用来接收Put操作，若active segment达到overflow条件(默认情况下32MB，MemStore的25%大小)，它们将会被移到in-memory pipeline 中，并设为不可变segment，我们称这一过程为in-memory flush。Get操作通过扫描这些 segment和HFiles 取数据(后者操作通过块缓存进行访问，与平常访问HBase一样)。

CompactingMemStore 可能会不时在后台合并多个不可变segment，从而形成更大的segment。因此，pipeline是“会呼吸的”(扩张和收缩)，类似于手风琴波纹管，所以我们也将Accordion 译为手风琴。

当RegionServer 刷入一个或多个MemStore到磁盘释放内存时，它会刷入 CompactingMemStore中已经移入pipeline中的segment到磁盘。基本原理是延长MemStore有效管理内存的生命周期，以减少整体I/O。当flush发生时，pipeline中所有的segment 段将被移出合成一个快照， 通过合并和流式传输形成新的HFile。图1展示了CompactingMemStore与传统设计的结构。

 

 

图1. CompactingMemStore与DefaultMemStore

Segment结构：

与默认的MemStore类似，CompactingMemStore在单元存储之上维护一个索引，这样可以通过key快速搜索。两者不同的是，MemStore索引实现是通过Java skiplist (ConcurrentSkipListMap--一种动态但奢侈的数据结构)管理大量小对象。CompactingMemStore 则在不可变的segment 索引之上实现了高效且节省空间的扁平化布局。这种优化可以帮助所有压缩策略减少RAM开销，甚至可以使数据几乎不存在冗余。当将一个Segment加入pipeline中，CompactingMemStore 就将其索引序列化为一个名为CellArrayMap 的有序数组，该数组可以快速进行二进制搜索。

CellArrayMap既支持从Java堆内直接分配单元，也支持MSLAB的自定义分配(堆内或堆外)，实现差异通过被索引引用的KeyValue对象抽象出来(图2)。CellArrayMap本身始终分配在堆内。

 

 

图2.具有扁平CellArrayMap索引和MSLAB单元存储的不可变Segment

压缩算法：

内存中压缩算法在pipeline中的Segment上维护了一个单一的扁平化索引。这样的设计节省了存储空间，尤其是当数据项很小时，可以及时将数据刷入磁盘。单个索引可使搜索操作在单一空间进行，因此缩短了tail读取延迟。

当一个active segment被刷新到内存时，它将排列到压缩pipeline中，并会立即触发一个异步合并调度任务。该调度任务将同时扫描pipeline中的所有Segment(类似于磁盘上的压缩)并将它们的索引合并为一个。basic和eager 压缩策略之间的差异体现在它们处理单元数据的方式上。basic压缩不会消除冗余数据版本以避免物理复制，它只是重新排列KeyValue对象的引用。eager压缩则相反，它会过滤出冗余数据，但这是以额外的计算和数据迁移为代价的。例如，在MSLAB存储器中，surviving 单元被复制到新创建的MSLAB中。

未来的压缩可能会在basic压缩策略和eager压缩策略之间实现自动选择。例如，该算法可能会在一段时间内尝试eager压缩，并根据所传递的值(如：数据被删除的比例)安排下一次压缩。这种方法可以减轻系统管理员的先验决定，并适应不断变化的访问模式。