如今，人们对基于HBase的产品的读写速度要求越来越高。理想情况下，人们希望HBase在保证其可靠持久存储的前提下，能够具备读写内存数据的速度。为此，在HBase2.0中引入了Accordion算法。HbaseRegionServer负责将数据划分到多个Region。RegionServer的内部（垂直）可扩展性对于最终用户体验和整体系统利用率至关重要。Accordion算法通过提高RAM的利用率来提高RegionServer的可扩展性。这样可以在内存中存放更多的数据，从而减少磁盘的读取频率（即减少HBase中的磁盘占用和写入方式，增加读写RAM，减少对磁盘的IO访问）.在HBase2.0之前，这些指标不能同时满足，相互制约。在引入Accordion之后，这种情况得到了改善。Accordion算法源自HBase核心架构LSM算法。在HBaseRegion中，数据以key-value的形式映射到可搜索存储中，其中新进来的数据和一些topmost（front）的数据存储在内存（MemStore）中，其余都是不变的HDFS文件。那就是HFile。当MemStore满时，将数据刷入硬盘，生成新的HFile。HBase采用多版本并发控制，MemStore将所有修改的数据存储为独立的版本。MemStore和HFile中都可能存储一条数据的多个版本。读取多版本数据时，根据key从HBase中扫描BlockCache中的HFile，获取最新的版本数据。为了降低磁盘访问频率，HFiles在后台进行合并（即compaction过程，删除多余的cell，创建更大的文件）。LSM通过将随机读取和写入转换为顺序读取和写入来提高写入性能。以前的设计没有使用压缩内存数据。主要原因是在LSM树设计之初，RAM还是非常稀缺的资源，所以MemStore的容量很小。随着硬件的不断提升，整个RegionServer管理的MemStore可能有好几G，这给HBase优化留下了很大的空间。Accordion算法将LSM重新应用到MemStore，以便在数据仍在RAM中时可以删除冗余和其他开销。这样做可以减少刷新到HDFS的频率，从而减少写入放大和磁盘使用。随着flush次数的减少，MemStore写入磁盘的频率也会降低，从而提高HBase的写入性能。磁盘上更少的数据也意味着块缓存的压力更小，从而缩短了读取的响应时间。最终，更少的磁盘写入也意味着后台压缩更少，意味着更少的读写周期。总而言之，内存压缩算法的作用可以看作是让整个系统运行得更快的催化剂。目前Accordion提供两种级别的内存压缩：基本级别和急切级别。前者适合所有数据更新的优化，后者对数据流量大的应用很有用，比如生产-消费队列、购物车、共享柜台等，这些用例都会频繁更新rowkey，产生多个冗余版本的数据，而手风琴算法将在这些情况下发挥其价值。但另一方面，eager-level压缩优化可能会增加计算开销（更多的内存副本和垃圾收集），这可能会影响数据写入的响应时间。如果MemStore使用堆上MemStore-Local分配缓冲区(MSLAB)，这会导致开销增加。因此不建议将此配置与eager-level压缩结合使用。可以在全局和列族级别配置内存压缩的使用方式。目前支持三个级别的配置：none（传统实现）、basic和eager。默认情况下，所有表都是基本的内存压缩。这个配置可以在hbase-site.xml中修改如下：hbase.hregion.compacting.memstore.type/property>也可以在HBaseshell中为每个列族单独配置，如下：create'',{NAME=>'',IN_MEMORY_COMPACTION=>''}性能提升HBase通过使用YCSB（YahooCloudServiceBenchmark）进行了全面测试。实验中，数据集大小为100-200GB，结果表明手风琴算法可以显着提升HBase的性能。重尾（Zipf）分布：在测试负载中国，rowkey服从大多数现实场景中出现的Zipf分布。在这种情况下，Accordion在100%的操作都是写操作的情况下实现了写放大降低30%，写吞吐量提高20%，GC降低22%。当50%的操作是读取时，尾读取延迟减少12%。Uniformdistribution：在第二个测试中，rowkeys是均匀分布的。当100%的操作都是写操作时，Accordion将写放大减少了25%，写吞吐量减少了50%，GC减少了36%。尾部读取延迟不受影响（由于没有本地化）。Accordion的工作原理高级设计：Accordion引入了MemStore的内部压缩（CompactingMemStore）实现。与默认的MemStore相比，Accordion将所有数据保存在一个完整的数据结构中，并以段的形式进行管理。最新的段称为活动段，是可变的，可用于接收Put操作。如果活动段达到溢出条件（默认32MB，MemStore大小的25%），它们将被移动到内存管道，并将其设置为不可变段，我们称这个过程为内存刷新。Get操作通过扫描这些Segment和HFiles来取数据（后面的操作是通过blockcache访问的，就像正常访问HBase一样）。CompactingMemStore可能会不时地在后台合并多个不可变段，形成更大的段。因此，管道是“会呼吸的”（扩张和收缩），类似于手风琴的风箱，所以我们也将Accordion译为手风琴。当RegionServer将一个或多个MemStore刷入磁盘释放内存时，会将CompactingMemStore中已经移入管道的段刷入磁盘。基本原理是延长MemStore的生命周期以有效管理内存以减少整体I/O。当flush发生时，pipeline中的所有segment都会被移除，形成一个snapshot，通过merge和streaming形成一个新的HFile。图1显示了CompactingMemStore的结构和传统的设计。图1.CompactingMemStore和DefaultMemStoreSegment结构：CompactingMemStore与默认的MemStore类似，在单元存储上维护一个索引，这样可以通过key快速查找。两者的区别在于MemStore索引实现是通过Java的skiplist（ConcurrentSkipListMap——一种动态但豪华的数据结构）来管理大量的小对象。CompactingMemStore在不可变段索引之上实现高效且节省空间的平面布局。这种优化可以帮助所有压缩策略减少RAM开销，甚至使数据几乎冗余。当一个Segment添加到管道中时，CompactingMemStore将其索引序列化为一个名为CellArrayMap的有序数组，可以对其进行快速二进制搜索。CellArrayMap支持从Java堆直接分配单元和自定义分配MSLAB（堆内或堆外）。实现差异是通过索引引用的KeyValue对象抽象出来的（图2）。CellArrayMap本身总是分配在堆上。图2.具有平面CellArrayMap索引和MSLAB单元存储的不可变段压缩算法：内存压缩算法在管道中的段上维护单个平面索引。这种设计节省了存储空间，尤其是在数据项较小的情况下，可以及时将数据刷入磁盘。单个索引允许在单个空间中执行搜索，从而减少尾部读取延迟。当一个活动段被刷新到内存中时，它会被排入压缩管道，这会立即触发一个异步合并调度程序。此计划任务将同时扫描管道中的所有段（类似于磁盘上的压缩）并将它们的索引合并为一个。基本压缩策略和急切压缩策略之间的区别在于它们处理单元格数据的方式。基本压缩不会消除冗余数据版本以避免物理复制，它只是重新排列对KeyValue对象的引用。急切压缩则相反，过滤掉冗余数据，但代价是额外的计算和数据迁移。例如，在MSLAB内存中，幸存的单元被复制到新创建的MSLAB中。未来的压缩可能会在basic和eager压缩策略之间实现自动选择。例如，该算法可能会在一段时间内尝试急切压缩，并根据传递的值（例如，要删除的数据的百分比）安排下一次压缩。这种方法减轻了系统管理员的先验决定并适应不断变化的访问模式。
