HotStorage 2019 - Jungle
2022-11-29|2023-10-27
DieInADream
type
status
date
slug
summary
tags
category
icon
password
Property
Oct 27, 2023 09:48 AM
Abstract
- 读性能、写性能、空间放大三者不可兼得（RUM 理论），现有的一些工作致力于改善这三方面，但是对尾延迟的改善不明显，所以本文提出了一个新的方法，即移植 CoW B+Tree 到 LSM 树，以减小更新开销，但又不会牺牲查询性能。除此以外，本文还提供了一种简单实用的方式来在针对 更新优化 和 空间优化 的形式的一种调整机制。测试结果表明可以在保证读性能的情况下减小了更新的开销
Introduction
- LSM 最大的问题就是合并开销大，不只是磁盘 I/O 上的开销还有 CPU 开销。现有的一种优化就是 Tiering，通过在一层上维护了多个 sorted runs 来延迟了合并，因为减少了重写所以减小了更新的开销，但随之带来的坏处就是索引占据的空间开销变大了，因为有重复老旧的数据。此外，查询开销也变大了，因为需要检查更多的 sorted run。
- 为了在不降低查找成本的情况下调节更新成本，本文提出了一种新的 LSM-tree 方法 Jungle，它用 copy-on-write (CoW) B+树 [6,8,9,13,20] 来代替每个 sorted run，该树分别存储键和值。当新的写批键-值对进来时，Jungle 按键对它进行排序，将值追加到 B+ 树文件的末尾，然后追加更新的节点，这些节点只存储键和对它们值的引用。对于我们的目标用例来说，分离键和值是一个重要的促进因素，在目标用例中，值比键大得多。
- 由于多个批 batches 是按时间顺序积累的，所以 Jungle 与 Tiering 中排序运行 Sorted Run 的堆栈有许多相似之处。与现有 Tiering 的最大区别是，CoW B+-树的查找成本不受添加到树中的 batch (即Sorted Run) 数量的影响；对于单个查找，不需要访问多个 Sorted Run。它使 Tiering 更加灵活，从而可以摆脱堆栈中 Sorted Run 个数的限制。
- CoW B+Tree 因为也是追加写的，所以需要周期进行 Compaction 任务来把所有追加的 batches 合并然后写回到整个 B+Tree，且有序。通过调整这个 Compaction 的频率，我们可以很容易对 LSM-Tree 调优，比如 Compaction 发生的不那么频繁，CoW B+Tree 将会积攒更多的 batches，整体的更新开销就会下降，但是后果就是增加了空间开销；如果 Compaction 比较频繁，将会增加更新开销，但是更新开销也只会接近 LSM 树的开销。需要注意的是，查询的开销是不受 Compaction 频率的影响的，实验结果也证实了该结论。
Background
LSM
- 两种合并策略：Leveling 的写放大是 T，Tiering 的写放大很小，因为不重写，但空间放大为 Leveling 的 T 倍
- 现有的 LSM 大多都采用了 BF 优化查询，但是 BF 会误报，所以尾延迟还是会受到层级数和 stack size 的影响
CoW B+Tree
- CoW B+Tree 或者叫 append-only B+Tree 是 B+Tree 的一个变体，通过异地更新的方式来处理写入。
- 如下图 a 所示，更新节点 E，那么修改的新节点 E‘ 就被追加到文件的末尾，而不是覆盖写 E
- 因为现在 节点 E 位置变了，所以修改也需要级联从叶子到根的整个路径，所以该路径上的 C 和 A 也需要更新成 C’ 和 A’
- 因为更新从叶子节点到根节点路径上的所有节点的开销太大了，所以 CoW B+Tree 就是采用批量追加写的方式，可以显著减小写放大。
- 还有一个显著减小写放大的方法是把 value 从叶子节点中解耦出来，把 value 写到 B+Tree 以外的地方，然后在 B+Tree 中维护 Key 和指向 value 的引用（字节偏移）
- 如下图 b 所示，原本已经有一个 WriteBatch 10-50 【Insert {10, A}, {15, B}, {27, C}, {50, D}】，此时修改 15，27，32 【Set {15, E}, {27, F}, {32, G}】；
- 新建一个 WriteBatch，首先写 Value 部分，然后追加写 Key 和 Reference 部分，因为两个 Batch 操作的数据位于同一个节点，那么原有的第一个 Batch 里的 10 和 50 对应的 reference 也会被复制，确保该节点的引用信息是连续的。（保证有序性）
- 一旦 CoW B+树引用的数据的空间使用超过一定的阈值，将会触发一个 Compaction 任务。该任务按照键顺序遍历树，拷贝最新的数据到新的空间，自底向上构建一个新的 B+Tree，然后删除旧的树。
- 如下图 c 所示，在图 b 的基础上，再执行了【Set {15, H}, {50, I} 】，并更新索引
- 此时触发 Compaction，则根据保存的键和引用的顺序，拷贝有效数据，重新构建 B+Tree，回收无效空间
Jungle: Planting LSM-Tree and Copy-On-Write B+-Tree Together
- Jungle 是一个混合的 LSM 树，其中的 sorted run 使用了 CoW B+Tree 来代替。由于 CoW B+树可以按时间顺序包含多个写 Batch，如果所有的写 Batch 都是内部排序的，那么它在 Tiering 中与 sorted run 堆栈共享许多公共特性，因此 Jungle 可以被看作 Tiering 的一个变种。如下图所示，每个 CoW B+Tree 对应了 tiering LSM-Tree 中的一叠 sorted runs。一个 stack 中的每个 sorted run 对应就是一个 CoW B+Tree 中的 write batch
- 使用 CoW B+Tree 的最大优点是读开销低
- 在 Tiering LSM 中读开销大致与 stack 的大小成正比，因为需要检查每个 sorted run，假设每个 run 有 R 条数据，一个 Stack 里有 T 个 run，对应的查询开销是 ，即便有 BF，Stack 的大小直接影响假阳性的可能性。这是为什么 Stack 中 sorted run 的最大个数有限制的原因之一。
- 对于 CoW B+Tree，查询开销只会受到树中所有不同键数量的影响，而跟 WriteBatch 的数量无关，如果一个树中有 T 个不同的 WriteBatch 具有重复的键，且有 R 个唯一的键，那么每层的查找成本将为 ，如果 T 个 WriteBatch 的键都是独一无二的，那么查询开销就是 ，还是会比 小，因为 T 相比于 R 要小得多，因此，它使我们能够拥有灵活的 write batch 数量，同时保持与 leveling 合并几乎相同的查找成本：每级 。 这种方法与 BF 是正交的，我们仍然可以使用它来提高读性能
- 本质是在 Tiering 的基础上建立一个有序索引。CoW 后面追加写入的键和 reference 信息便是有序索引。
- Jungle 有两种合并操作，就地合并和层间合并。下图展示了一个例子
- in-place merge 和 CoW B+Tree 的 Compaction 机制是一样的
- inter-level merge 和 Tiering 合并是一样的
- CoW B+Tree 相比于传统的 Tiering 的优势是很容易获取到独一无二的键的个数，以及他们的空间使用，而不需要任何的 I/O。如果空间使用没达到每一层的阈值，就不需要合并到下一层。这种情况下触发一个 in-place merge，这样受害的 CoW B+-树就被压缩了，而不会影响其他树，如图 4(a) 所示。
- 本质就是多个 WriteBatch 的合并以回收空间，并提升了 value 的有序性
- 如果实际的大小达到了阈值就需要调用层间合并。遍历候选的 CoW B+Tree 然后把新的写 batches 追加到下一层相应的 CoW B+Tree 中，如下图 b 所示。整体的形状就还是保持 Tiering 的形状。
- 图中例子就是 L1 第一个 stack 里的两个 write_batch 发生了合并成为 0-50，但是根据下一层的 write_batch 的范围做了拆分，0-26 和 30-50，写入到 L2 前两个 stack。
- 本质就是 Tiering + Partition
合并频率
- CoW B+树的合并阈值 C 定义为包含陈旧数据的树占用的空间量与实时新数据的大小之比。（空间放大）
- C=3，in-place merge 将触发，也就是当一个 CoW B+ 树及其数据的空间使用大于其活动键值对大小的 3 倍时。就和 Tiering LSM 中，有三个 sorted run 触发就地合并。
- 在达到该阈值之前，如果级别 level 的总大小超过了限制，即比 Leveling 中的限制大 C 倍，则可能发生级别间合并 inter-level merge。
- 在大小方面设置阈值比在 sorted run 数量方面设置阈值更有好处。
- 在 Tiering 中，Sorted Run 严格限制为 T，不管 Sorted Run 的实际大小如何，归并都会发生。如果 stack 中 run 的平均大小小于其限制 S，则合并将比 C = T 的 Jungle 更早发生，因为 Jungle 将在实际的大小限制，即 C·S 时，触发合并。
- 在 Jungle 的视角中，单个写 batch 的大小和树中写 batch 的总数都无关紧要；因此，如果它们的平均大小小于 S，它可以容纳更多的写 batch，如图 5 所示
- 因此，在 Tiering 中调用的合并总数将与 C = T 的 Jungle 中相同，当且仅当所有 sorted run 的大小都均匀为 S 时才会如此。否则，Tiering 执行的合并次数一般比 Jungle 更多，从而增加了整体的写放大。对于倾斜的负载，在 Tiering 和 Jungle 中合并次数的差距将会更大，因为部分冷的 stack 其实是很少被更新的，那么这些 stack 就很可能填充了大量的小的 sorted runs，然后导致写放大增加。
- 更糟糕的是，尽管我们放的是uniform 的随机数据，但实际上排序运行 sorted run 的实际大小分布并不均匀。它受到各种因素的影响，如 level 中的键范围划分、受害者堆栈 victim stack 选择策略或概率问题，如 balls into bins 的模型
- 注意，为了避免此类问题，Tiering 不允许超过 T 个 runs，其原因是由于查找性能：更多的 runs 将使查找成本更高。此外，由于前面提到的小 run 问题，Tiering 也不能将 stack 的大小限制降低到小于 T。
- 假设限定 stack 的大小为 M (run 个数)，其中 M < T，假设在合并前的每个运行 run 的大小都是 S 的理想情况，并且假设级别 l 中的堆栈 stack 的键范围与下一个级别 l + 1 中的 T 个堆栈 stack 重叠，合并将生成 T 个运行 run，每个 run 的大小为 ，所以会造成比以前的 runs 更小 （< S），相应地会让 Tiering 触发合并更频繁。因此，stack 中的 run 个数应该和层间系数一样为 T
- Jungle 中的 CoW B+Tree 的 Compaction 阈值很容易调整，因为很难影响到读性能，所以其实对于该参数的调整的本质是在写性能和空间开销上调优。
- C 更小意味着合并更频繁，空间开销减小，因为 GC 的快
- C 更大意味着合并没那么频繁，写开销就下降了，因为被均摊的更多了
- 设置该阈值也有几个选项：
- 单一的全局 value （本文目前只考虑了该情况）
- 每一层垂直不同的值（每一层的 C 大小不一样）
- 根据工作负载模式和局部性，每个键范围的水平层面不同值（每个 Stack 内大小不同）
开销分析
- 参数解释：
- R 代表每一个 run 包含的最大键个数
- L 代表 LSM 的层级数
- p 代表 BF 的误报率 （m 和 n 代表 BF 的位数和总的键的个数，k 代表哈希函数的个数），n/m=1/10 且 k=3 的时候，p 大约等于 1.7%
- 比较结果：
- Jungle 点查询开销和 Leveling 类似，只是每个 CoW B+Tree 的键个数不同，最多可能 C*R 个键
- 范围查询开销和 Leveling 是一样的，不受到 B+Tree 高度的影响
- 写和空间放大受到 Compaction 阈值 C 的影响，如果 C=T，那么和 Tiering 就类似，除了 ，分别代表了 CoW B+Tree 节点的额外写和空间开销。
- 假设 value 的平均大小为 V 然后键和引用加起来的大小为 K，每个写 batch 包含 R 个键值对，首先写 value，大小为 R*V，然后写 Key，R*K。因此， 都将等于 。
- 但是最差情况下每个 Batch 都是独一无二的键值对，在追加新批次之前，现有 CoW B+-树节点的大小将为 ，我们可能需要为单个批处理追加重写所有这些节点，因此 的值将增加到 ，V=1KB，K=16B，C=10，它们的范围将在 0.016 到 0.16 之间。当键小于值时，这些值通常小于 1
- 随着 C 值的降低，Jungle 的空间成本将接近于 Leveling 的空间成本。然而，写放大仍然比 Leveling 小得多，因为 Jungle 只是向现有的 CoW B+-树追加了一个新的写 Batch，除了就地合并 in-place update。
- 就地合并 in-place update 最有可能发生在最后一层，在那里所有键最终都被确定下来。
- 最后一层的写 Batch 可能包含已经存在的键，因此我们可以在追加 C 写批后触发原地合并。
- 因此，C 主要影响就地合并 in-place merge 的频率。这是 Jungle 的好处之一，因为我们可以保持 C 的值小于 T，这比 Tiering 使用的空间更少，同时保持类似的写放大。
Evaluation
- 在本文中，我们不根据广泛使用的键值存储(如RocksDB[1]) 来衡量整体性能，因为它们包含了许多与 Jungle 在原始 leveling 和 tiering 方案上的改进正交的优化。
空间放大
- 由于空间使用随时间波动，我们测量平均值以及最大值和最小值。Leveling 的空间占用最小，接近原来工作集大小的 1.2 倍。Tiering 的空间放大预期为 11.1，但实际测量值远小于此值，平均为 3.24。发生这种情况有两个原因。
- 首先，合并不能同时发生在所有的堆栈上，因此有些堆栈是满的，而另一些没有。因此平均堆栈大小总是小于最大堆栈大小。理论值是按照最大 stack 大小计算的。
- 其次，正如我们在第 3 节中提到的，堆栈中排序运行 sorted run 的大小在实践中是不均匀的。最终它不能充分利用空间容量，合并操作被触发的频率更高，因此我们观察到 Tiering 显示出比 C=5 更大的写放大。(即因为 run 个数达到阈值被频繁合并)
- 另一方面，即使在相同的合并时间和受害者策略下，Jungle 的空间放大范围也更可预测。这是因为它的压缩阈值基于实际的数据大小比，而不是 CoW B+-树中的写批总数（这仿佛说的是 C 比较小的时候，因为 C=10 的时候空间放大波动很大）
Conclusion
- 本文提出了一种结合 LSM-树和 CoW B+-树的混合 Jungle 方法。Jungle 的主要目标是切断更新成本和查找成本之间的关系，使键值存储的索引更加灵活，便于优化。我们的评估结果表明，通过调整 CoW B+-树的压缩阈值，可以很容易地调整 Jungle 的写和空间放大，并且对查找成本的影响最小。
Discussion Topics
Chances of LSM-tree deformation
- Jungle 展示了打破 LSM 树的限制的可行性，LSM 树的限制被严格限制在查找成本、更新成本和空间成本之间的关系。通过在权衡中消除查找成本，它提供了解决现有设计问题的新机会。例如：
- 尽管与 B+-树相比读性能有所下降，但 LSM 树实现一直保持多层的原因是为了保持相邻级别 T 之间的比率恒定。更少的级别使 T 更大，这导致更高的写放大。
- 在不均匀的工作负载下，LSM 树方法对于采用不同的合并策略进行热/冷分离一直是被动的。延迟热键范围的合并可能增加相同范围的查找成本。
- 我们可以重新思考这些基本原理。
Limitations
- 还有一些潜在的局限性，我们需要进一步研究。
- Range lookup：如果一个 CoW B+-树中有许多小的写 batch，那么访问模式将更加随机，这将导致范围查找的退化。我们相信通过预读，少于 T 个 batch 就可以了。
- Long keys：较长的键使 Bw 和 Bs 的值 value 更大。我们可以使用 CoW B+-tree[2] 的变体来调节这个开销。Forestdb
State-of-the-art approaches
- 在 Dostoevsky[11] 的论文中，Dayan 等人提出了一种不同的方法来设置每个级别的堆栈 stack 的大小限制。由于最后一层对更新成本和空间成本有主要影响，我们可以通过将最后一层的堆栈 stack 大小设置得更小来降低总体成本。他们还提出了一个模型来寻找每个级别的最优堆栈 stack 大小，这与他们之前的论文 Monkey[10] 类似，该论文探索了每个级别的 Bloom 过滤器大小的最佳比例。这些方案与 Jungle 正交，因为在 Jungle 中堆栈 stack 大小限制可以转化为合并阈值 C。我们可以用同样的方法来进一步降低运营成本
- 提出了一种用于分层 Tiering 合并的键范围分区策略——PebblesDB [19]，它将栈键范围边界称为 Guard。Jungle 可以采用它的方法来高效地创建或分割 CoW B+-树，以避免可能导致多余合并的键范围倾斜。
- Utterance