本文从 《LSM-based Storage Techniques: A Survey》 摘取部分图片,来介绍 LSM tree 的相关内容。详细内容请查看论文原文。
in-place update V.S. out-of-place update
- 索引结构通常有两种数据的更新策略:in-place update 和 out-of-place update。
- in-place update:在原数据处覆盖写入,e.g. B+树。该策略读性能较好(只需要读一份数据);随机 IO导致写性能较差;空间碎片导致空间利用率下降。
- out-of-place update:在新的地方写入更新后的数据(原数据不做变更), e.g. LSM tree。与 in-place update 相反,该策略写性能较好(顺序写);同一份数据保存多份导致读性能较差;顺序写减少空间碎片从而提高空间利用率。
LSM-tree 基本原理
- LSM-tree 包含 C0, C1, …, Ck 共 k+1 层, 每一层的数据都是 B+ 树。其中 C0 层维护在内存中,而 C1, …, Ck 层维护在磁盘。
- Write 操作: 每次写入数据都只写入 C0 层。
-
Point Query 操作:每次点查询操作会依次遍历 C0, C1, …, Ck, 返回查询到最新版本的数据。如果遍历完之后都没有查到数据,则该数据不存在。比如, 查询
key = b
的值, 在 C0 层查到 b=2
, 直接返回该值,而不用继续遍历 C1, …, Ck。 -
Range Query 操作:范围查询会并发的在 C0, C1, …, Ck 查找指定范围的数据,然后根据优先级从高到低将每层的查询结果合并为最终的查询结果。 比如,查询结果为
<C0, a=1, b=2>, <C1, b=3, c=3>
, 合并之后的最终结果为 a=1, b=2, c=3
。 - Delete 操作:删除操作写入删除标记数据,由后台进程负责异步删除。
- Merge 操作:C0, C1, …, Ck 每层容量固定,依次按照一定比率递增。当某层 Ci 数据规模达到该层容量上限,后台 Merge 进程 会将该层数据合入 Ci+1 层。
Merge 策略: Leveling Merge Policy V.S. Tiering Merge Policy
注:图中的数字表示 Index 的范围。如 0-100 指 Index 在 0-100 的数据可以保存在该 component。
- Leveling Merge Policy:每一层只包含一个 component。L 层的 component 容量是 L-1 层的 T 倍。当 L 层达到其容量上限,会被合并到 L+1 层。如 Fig.3(a),L0 的数据达到上限,合入到 L1 层。
- Tiering Merge Policy:每一层最多包含 T 个 component。当 L 层达到容量上限,它的 T 个 component 会合并为 L+1 层的一个 component。如果 L 为配置的最大层,则合并后的 component 保持在该层。如 Fig.3(b), T=2, L0 层的数据达到上限,它的 2 个component 合并为了 L1 层的一个新的 component。
Partition Policy: partitioned leveling merge policy V.S. partitioned tiering merge policy
LSM-tree 有两类比较常见的优化策略:布隆过滤器(Bloom Filter)和数据分区(Partitioning)。
- 布隆过滤器(Bloom Filter):可以为每一棵 B+ 树或它的非叶子节点绑定一个布隆过滤器,以提高数据的查询效率。
- 数据分区(Partitioning):可以将每一层的 component 拆分成更小的 partition(记作: SSTable)。数据分区可以提高 merge 的效率;减少merge 过程中对磁盘空间的浪费等。
不同的 merge policy, partioning 的处理方式也有所不同。
partitioned leveling merge policy
- 每一层的数据被 partition 为多个相同大小的 SSTable。
- L0 数据直接从内存 flush 而来,因此不需要进行 partition。
- 读写操作与非 partitioned 的 leveling merge policy 一致。
- Merge 流程: 将 L 层一个 SSTable merge 到 L+1 层,需要将 L+1 层所有和该 SSTable 有重叠 Index 的 SSTable 一起,合并为 L+1 层新的 SSTable。如 Fig.4 Merge 0-30(L1) 到 L2。L2 层与它 Index 有重叠的 SSTable 有 0-15(L2) 和 16-32(L2)。将0-30(L1), 0-15(L2) 和 16-32(L2) 三个 SSTable 一起合并为 L2 层新的 SSTable: 0-10(L2), 11-19(L2) 和 20-32(L2)。
partitioned tiering merge policy: vertical grouping V.S. horizontal grouping
tiering merge policy 将每层的数据分成不同的 Group 进行处理。将重合 Index 的 SSTable 拆分到同一个 Group 的策略称为 vertical grouping policy;将不重合 Index 的 SSTable 拆分到同一个 Group 的策略称为 horizontal grouping policy。
- partitioned tiering with vertical grouping
- 每一层的 SSTable 被拆分为 Index 互相重叠的 Group。
- Merge 操作:Fig.5 中, 0-31(L1), 0-30(L1) 中的 Index 在 0-15(可能) 部分 merge 为 0-13(L2) 所在 Group 的一个 SSTable,即 0-12(L2);其 Index 在 16-34(可能) 部分 merge 到 16-32(L2) 所在 Group 的一个 SSTable,即 17-31(L2)。
- 查询操作: 在该策略下,每一层的查询操作需要查询该层 Index 覆盖的 Group 下的所有 SSTable 的情况。
- 在这种策略下,上一层相同 Group 的 SSTable 需要 Merge 到下一层 Index 重叠的 Group 内,SSTable 大小不再固定。
- partitioned tiering with horizontal grouping
- 每一层大小固定的的 SSTable 被拆分为 Index 互不重叠的 Group。
- 每一层包含一个接受上一层合入进来的新 SSTable 的 Group,称之为 active group。
- Merge 操作: 合并 L 层的某个 SSTable 时, 选择该层所有其他 group 中与其 Index 重叠的 SSTable,合并到 L+1 层 active group 中。 如 Fig.6, 选择该层其他 Group 与 35-70(L1) Index 重叠的 SSTable,即 35-65(L1)。将35-70(L1),35-65(L1) 合并到 L2 层的 active group 中,即 35-52(L2) 和 53-70(L2)。
Reference