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中修正，如下所示：

也可在HBase shell中为每个列族启动独自性能，如下所示：

性能提高

经过应用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紧缩，并依据所传递的值（如：数据被删除的比例）布置下一次性紧缩。这种方法可以减轻系统治理员的先验选择，并顺应不时变动的访问形式。