Tebis: Index Shipping for Efficient Replication in LSM Key-Value(6)

在Send-Index方法中，当空间被填满时，主区域就CPU和设备I/O执行和的合并过程。然后，主region将得到的索引发送到备份region。这种方法(a)减少了每个备份设备读取和的I/O流量，(b)避免了内存排序，(c) 的内存。备份区域不需要在内存中保存一个。通过在内存中对KV对排序，来分摊与合并期间的I/O开销。对于到的合并，备份区域不需要读取和。相反，它们接收并重写主索引。如果在备份区域中省略，那么对于每个区域一个副本，的内存开销将减少2倍，对于两个副本，将减少3倍。
发送索引方法的一个后果是增加了网络流量。本质上，Send-Index通过网络发送重组后的索引。增加的流量使用网络吞吐量而不是设备读I/O。此外，与归并排序和读I/O相比，RDMA通信所需的CPU也有所减少。

在Tebis中，主要的设备结构是值日志和层次的B 树索引。Tebis将值日志和B 树索引都存储为一个固定段的列表。与日志段类似，每个段为2 MB，起始设备偏移量分段对齐。重写时，Tebis用新的段号替换主设备的高阶位。
区域的索引(图3)由叶子节点和索引节点组成。对于每个KV对，叶节点(图3底部)包含一个key前缀，用于减少对值日志的I/O操作，以及一个设备偏移量，指向值日志中KV对的设备位置。索引节点存储可变大小的pivot键和指向其后续节点(索引节点或叶节点)的设备位置的指针。备份需要重写叶子节点和索引节点中KV对的设备偏移量(图3中的虚线箭头)。
备份跟踪两个段的映射:日志映射和索引映射。日志映射在日志的刷新操作期间更新。索引映射在Send-Index方法中动态更新，仅在到合并期间有效。在合并过程中，主进程自底向上、从左到右构建索引。因此，主服务器可以在构建新索引时逐段递增地发送新索引。