二、设计
为解决分布式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文件的个数，来将两层日志设置为低有序度，从而保证好的写性能。
