一文读懂DEPART：分布式KV存储系统的副本解耦方案

基于LSM-tree的键值存储系统是NewSQL/NoSQL产物中最常用的底层存储计划，对其停止研究具有重要意义与应用价值。论文针对 散布式键值系统初次提出了副本解耦的思惟，在多副本容错机造下可以实现副本数据的高效办理，从而显著提拔系统性能。而且论文提出的手艺能够应用到Cassandra、TiKV、ScyllaDB等系统中。本次分享将和各人一路讨论基于副本解耦的散布式键值系统的设想实现计划，并切磋将来的推广应用。

1、在大数据时代，数据量呈指数级增长，估计到2025年，全球的数据总量将达175ZB，非构造化和半构造化数据已占据主导地位。对海量非构造化和半构造化数据停止高效存储，KV存储系统供给了很好的处理计划：

● KV存储系统具有灵敏的数据模子，数据暗示为KV对形式，为肆意数据类型，且长度不定；

● KV存储的访存接口十分简单，向外供给Put、Get、Scan等简单的接口停止数据读写；

● KV存储还具备高可扩展性，数据基于Key停止划分和索引，无需维护额外的元数据。

因为KV存储系统具有上述诸多长处，因而被普遍应用在了NewSQL和NoSQL产物中。好比目前常见的KV存储系统：LevelDB、RocksDB、Cassandra、TiKV等。

2、目前支流的耐久化KV存储系统都接纳LSM-tree（log-structured merge tree）架构做为存储引擎，其具有高效的写入效率，但同时存在严峻的读写放大问题。

如图，KV数据起首缓存在内存并停止排序，然后以批量逃加的体例将数据写入磁盘上，构成磁盘上的一个SSTable文件，SSTable文件中的数据是按Key有序的，那种写入体例能够将大量的随机写转换为挨次写，从而充实操纵磁盘挨次写的带宽优势，获得高效的写入效率。

为兼顾读性能，磁盘上的数据被组织成多层形式，且容量逐层递增，而且除第0层以外，其他每层的数据是完全有序的。通过维护如许一个多层有序的架构，LSM-tree能够获得高效的写入和范畴查询性能，而且供给高可扩展性，当需要扩展存储容量时，能够通过简单的增加LSM-tree的层数来实现高效的扩展。

然而，LSM-tree多层的数据组织构造招致查询操做需要逐层搜刮，从第0层起头，曲到找到查询的数据为行，而且写入期间需要施行频繁的Compaction操做，详细Compaction操做需要从LSM-tree中读取相邻两层的数据，然后施行合并排序操做，再将合并后的有效数据写回磁盘。因而，当我们将数据从第0层逐步合并到较高层时，需要将数据频繁的读出而且写回，进而招致严峻的读写放大问题，且严峻消耗磁盘的IO带宽。

3、散布式KV存储系统被普遍应用，以撑持大规模的数据存储。

关于Cassandra、TiKV那一类散布式KV存储系统，起首数据基于Key的一致性哈希或者Key的范畴划分到各个存储节点上，然后每个节点内部利用一个LSM-tree来存储办理所有数据，下图以Cassandra为例做详细的介绍。

如图，KV数据起首基于Key的一致性哈希停止分区，图中有五个物理节点，每个节点有两个虚拟节点，因而整个哈希环被划分红十个范畴段。图中0到100的范畴段被划分红0-10、11-20、21-30等十个范畴段，而且每个范畴段都与顺时针标的目的比来的虚拟节点和相对应的物理节点相联系关系。好比0-10、51-60那两个范畴段被划分到节点0；11-20和61-70那两个范畴段被划分到节点1。

通过上述划分战略，每个节点会包罗多个范畴段，而且节点内部将所有范畴段存储在一个LSM-tree中。

4、为包管数据的高可靠，多副本容错机造被普遍应用在散布式KV存储系统中，即每份数据会复造成多份，而且存储在多个节点上，因而每个节点上的数据可分为主副本和冗余副本。

● 主副本：指通过一致性哈希划分战略划分到节点上的数据；

● 冗余副本：指通过复造战略发送到节点上的冗余数据；

● 同一索引：关于节点上的主副本和冗余副本，现有KV存储系统都接纳同一的多副本办理计划，也就是把主副本和冗余副本同一存储在一个LSM-tree中，如下图。

考虑到LSM-tree架构自己存在严峻的读写放大问题，而同一的索引计划又会极大的增加LSM-tree中存储的数据量，因而会进一步加剧LSM-tree的读写放大问题。

5、通过尝试进一步验证了同一的多副本办理计划会加剧KV系统的读写放大。

如图，在五个节点构成的当地存储集群长进行尝试，客户端起首写入300GB的KV数据，然后从集群中读出30GB的KV数据，KV大小为1KB，那里别离统计了散布式KV系统Cassandra和TiKV在差别副本数量下的读写放大系数，图（a）展现了写放大系数，图（b）展现了读放大系数。

由尝试成果可知，当副本数量越多时，KV存储系统的写放大和读放大越严峻，且放大系数增加的倍数超越副本数量增加的倍数，那里次要原因是上述阐发的同一多副本办理计划，会大大加剧写流程中施行的Compaction数据量，而且也会成倍增加读流程中需要搜刮的数据量。

为处理散布式KV系统中同一多副本办理招致的问题，接下来介绍处理计划。

2.1 设想思惟

次要设想思惟是在存储层对主副本和冗余副本停止解耦，以制止读写过程中主副本和冗余副本之间的彼此干扰。副本解耦后，接纳多个LSM-tree来对解耦的多副本停止独立办理。

如图，当系统设置装备摆设为三副本时，在每个存储节点上利用一个LSM-tree来存储主副本，别的两个LSM-tree来别离存储来自其他两个节点的冗余副本。那种计划的设法及实现都十分简单，但是存在着一些典型的问题。

2.2 mLSM的两个次要限造

● 多个LSM-tree会招致K倍的内存开销，因为每个LSM-tree都需要在内存中维护一个MemTable；

● 多个LSM-tree的解耦计划对Compaction开销的削减长短常有限的，因为每个LSM-tree仍然需要施行频繁的Compaction操做，从而来维护每层数据的完全有序，招致LSM-tree的Compaction开销仍然十分严峻。通过尝试验证，当客户端写200GB数据，接纳三副本时，多个LSM-tree的解耦计划比拟于同一索引计划，也就是原始计划，只削减了21%的Compaction数据量。

综合上述两个阐发能够得出，多个LSM-tree的解耦计划并非更佳选择，需要进一步优化设想。

2.3 设想计划

DEPART，散布式KV存储系统的副本解耦计划

在存储层对主副本和冗余副本停止解耦，然后按照功用需求，对解耦出的主副本和冗余副本停止差别化的办理，如下图。

关于主副本：仍然利用LSM-tree架构来存储，但LSM-tree架构愈加轻量级，从而包管高效的读写和范畴查询性能；

关于冗余副本：设想了一个有序度可调的两层日记架构停止存储，可按照上层应用的性能需求在读写性能之间做权衡。

2.4 计划挑战

a. 挑战一：若何设想副本区分机造

实现主副本和冗余副本的解耦，下图是一个轻量级的副本区分机造。

如图，当一个节点收到KV数据后，接纳和Coordinator不异的步调，起首计算Key的哈希值，然后按照一致性哈希数据散布机造，能够映射得到该KV划分到的节点ID。

若是计算得到的节点ID等于当前节点，那么就申明那个KV数据是通过一致性哈希机造映射到当前节点的，则该KV数据会被识别为主副本，而且存储在LSM-tree傍边，不然那个KV数据就是通过复造战略从其他节点发送过来的冗余数据，则当前节点将其识别为冗余副本，而且存储在两层日记傍边。

该解耦计划仅仅基于简单的哈希计算，因而是低开销的。此外，它在每个存储节点上独立施行，因而不会影响上层的数据散布机造以及一致性协议。

b. 挑战二：若何设想有序度可调的两层日记架构

(1) 关于解耦出的冗余副本，应该若何停止高效的办理，使其满足差别场景下的性能需求？那里设想了一个有序度可调的两层日记架构。

如上图，当节点收到冗余副本后，起首以批量逃加的体例将冗余副本快速写入到全局日记中，构成一个segment文件，那里的segment文件类似于LSM-tree傍边的SSTable文件，从而包管冗余副本能够高效的写入磁盘。

(2) 然后利用一个后台线程，将全局日记中的数据朋分到差别的当地日记中，如下图。

需要留意的是，每个当地日记用来存储一类冗余副本，他们所对应的主副本存储在不异的节点，好比那里当地日记LOGi，就用来存储对应主副本在节点i的那类冗余副本。

如许做的益处是能够实现细粒度的冗余副本办理，关于差别节点发送过来的冗余副本，利用差别的当地日记停止独立办理，从而能够包管高效的冗余副本读写性能，而且当恢复数据时，只需要读取响应的当地日记，制止了扫描所有的冗余副本，也能够进步数据恢复的效率。

(3) 其次，关于当地日记内部的数据办理也需要详细设想。

考虑到按照一致性哈希数据散布战略，每个节点会负责若干范畴段的数据，基于该特征，进一步设想了基于范畴的数据分组机造。

按照定义的范畴段，将当地日记进一步划分红差别的独立组，差别组之间的数据没有堆叠。好比节点2中的当地日记LOG0专门用来存储对应主副本在节点0上的冗余副本，又考虑到节点0中的主副本包罗0-10、51-60等范畴段，因而节点2中的当地日记LOG0被划分为Group 0[0-10]和Group 1[51-60]等若干组。

数据分组能够有效进步数据GC以及恢复性能，因为GC和数据恢复操做只需要读取响应的组即可，制止了扫描整个的当地日记。

(4) 关于每个组内的数据组织停止详细的设想。

每个组会包罗若干个sorted run文件,当朋分全局日记时，每次朋分操做城市在第2层的当地日记的组内产生一个sorted run文件，那些sorted run文件内部的KV数据是完全有序的，但sorted run文件之间的KV数据并未排序。因而，能够通过调整组内sorted run文件的个数来决定两层日记的有序度，从而在读写性能之间做权衡。

好比，当组内的sorted run文件个数越少，则两层日记的有序度越高，那时候读操做需要查抄的sorted run的文件个数也就越少，因而读性能会越好，但需要施行更频繁的合并排序操做，从而招致写性能会越差；反之，两层日记的有序度越低，合并排序开销越少，则写性能会越好，但读操做需要查抄的sorted run文件个数也就越多，招致读性能会越差。

（5）若何设置两层日记的有序度。

考虑到有序度会决定系统的读写性能，因而可按照上层应用的性能需求，来设置差别的有序度。

好比关于读密集型应用，或者系统设置装备摆设为高的读一致性品级，则能够通过削减组内sorted run文件的个数来将两层日记设置为高有序度，以包管好的读性能；不然能够通过增加组内sorted run文件的个数，来将两层日记设置为低有序度，从而包管好的写性能。

c. 挑战三：副本解耦后若何加速数据恢复操做

副本解耦后，通过一种并行的恢复机造，以操纵数据解耦存储的特征来加速数据恢复操做。

如图步调①中，当为节点上的数据构建Merkle tree以检测丧失的数据时，利用两个线程，并行地从LSM-tree的主副本和两层日记的冗余副本中读数据。

当修复多个范畴段的丧失数据时，如图步调③，同样利用两个线程，并行地从LSM-tree的主副本和两层日记的冗余副本中读写数据。

3.1 尝试设置

尝试办事器硬件设置装备摆设

● 在6个节点（5个存储节点，1个客户端节点）构成的当地集群中运行所有尝试， 10 Gb/s以太网交换机；

● 工做负载：利用YCSB 0.15.0来生成工做负载，KV对大小为1KB，生成的工做负载从命Zipf散布 (0.99)；

● 参数：默认接纳三副本，而且将写一致性品级和读一致性品级默认设置为1（WCL=ONE, RCL=ONE）。

3.2 比力

● Cassandra v3.11.4 VS multiple LSM-trees (mLSM) VS DEPART

● DEPART builds on Cassandra v3.11.4

在开源的散布式KV存储系统Cassandra上实现了原型系统DEPART，同时也实现了多个LSM-tree的简单解耦计划。将DEPART与Cassandra、多个LSM-tree的解耦计划别离停止性能比力，以展现系统DEPART的设想优势。

尝试一：基准测试

尝试一别离测试了差别KV系统的写、读、范畴查询和更新操做的吞吐量。

由尝试成果可知，比拟于Cassandra，系统DEPART能够显著提拔所有操做的吞吐量。而关于多个LSM-tree的解耦计划，其能够较好地提拔Cassandra的读性能，但对Cassandra的写性能提拔十分有限。次要原因是多个LSM-tree的解耦计划会招致解耦出的每个LSM-tree仍然需要施行频繁的Compaction操做，以维护每层数据的完全有有序，从而招致总的Compaction开销仍然十分严峻。

尝试二：差别一致性设置装备摆设

尝试评估了差别一致性设置装备摆设下的系统性能。那里关于强一致性品级，考虑了三副本下差别的写一致性品级和读一致性品级设置装备摆设。

由尝试成果可知，与Cassandra比拟。系统DEPART能够在差别一致性设置装备摆设下均能够进步所有操做的吞吐量，而且比拟于多个LSM-tree的解耦计划，DEPART能够有效进步写入和更新操做的吞吐量。

然而，当读一致性品级（RCL）设置装备摆设为大于1时，与Cassandra比拟，DEPART的读性能收益会变小，而且DEPART的读性能还要略差于多个LSM-tree的解耦计划。其次要原因是，在那种读一致性设置装备摆设下，每个读恳求需要胜利拜候至少两个副本，因而必需搜刮两层日记傍边的冗余副本；又因为两层日记中的冗余副本并未完全排序，因而读取两层日记的性能要低于读取完全排序的LSM-tree的主副本。

留意，DEPART的读性能仍然要好于Cassandra，因为副本解耦后，DEPART搜刮的数据量更少，但是DEPART的读性能要差于多个LSM-tree，因为多个LSM-tree连结冗余副本完全有序。

尝试三：数据恢复性能

别离测试当恢复差别数据量时所需要的时间。

与Cassandra比拟，DEPART将恢复时间削减38%-54%，次要原因是并行修复机造能够并行地读写主副本和冗余副本。

尝试四：有序度参数S对系统读写性能的影响

如表格所示，当S的值为1时，两层日记会变成两层LSM-tree，KV数据是完全有序的，因而它能够获得更高的读吞吐量。但因为频繁的合并排序操做，那时候写吞吐量是更低的。

当S的值从1不竭增大时，两层日记的有序度会不竭降低，故合并排序开销逐步减小，因而写性能会不竭增加，而读性能会不竭降低。

因而，能够通过调整S的取值，在读写性能之间做适宜的权衡。

DEPART是一个基于副本解耦的高性能和高可靠的散布式KV存储系统，包罗轻量级副本解耦计划、两层日记架构、有序度可调机造、并行恢复机造等关键模块设想。

更多详细的成果和阐发见论文，源码地址：https://github.com/ustcadsl/depart

KV研究热点总结与瞻望

起首，目前KV范畴的绝大部门工做都集中在优化KV存储引擎上，例如改良LSM-tree架构，以减轻读写放大问题，以及连系新型硬件来从头设想KV存储引擎等等。

但在KV系统的数据容错层，相关研究少少，我们停止了初步摸索，察看到当前同一的多副本办理会极大加剧KV系统的读写放大，因而研究设想了基于副本解耦的多副本差别化办理框架，极大提拔了系统性能。那项工做基于Cassandra开源平台实现，并能够应用在TiKV等一系列基于LSM-tree的散布式KV存储系统中。

关于KV系统将来的研究标的目的，能够连系应用层的需乞降缓存特征来停止特定的KV系统设想。例如，研究设想一种属性感知的内存KV系统，使其在存储构造上可以撑持对数据属性值的高效读写，最末摆设到云存储平台，以高效支持SQL数据库等应用。此外也能够连系上层应用的其他特征和需求来设想针对性的KV存储系统。

详细内容请参阅论文《DEPART: Replica Decoupling for Distributed Key-Value Storage》