摘要
基于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数据量，并且也会成倍增加读流程中需要搜索的数据量。
