An Introduction to Be-trees and Write Optimization 学习笔记

An Introduction to Be-trees and Write Optimization 学习笔记

paper链接 ：An Introduction to Be-trees and Write Optimization

文章目录

• Be-trees and Write Optimization 学习笔记

  ---

  • 背景介绍：本节将介绍Be-trees及其在编写优化中的核心作用。

    • 插入操作与删除操作：
      • 插入过程分析：详细探讨如何高效地进行数据插入。
      • 性能优化关键点：分析提升系统性能的关键因素。
      • 删除过程分析：深入讨论数据删除时的注意事项和技术细节。
    • 优化策略探讨：提出多种优化策略以进一步提升系统效率。
    • 3 查询操作
    • • 3.1 查询过程

  • 3.2 buffer组织

    • 4 性能分析
    • • 4.1 模型假设

  • 4.2 复杂度分析

  • 4.3 缓存机制

• 5 节点大小参数B对其系统性能表现有何影响

  • 参数ε的变化如何影响系统的运行效率
  • 整份文档将为您提供一份详尽的使用说明
    • 在此部分中我们将深入探讨如何实现核心功能
      • 我们将介绍一种高效的事务提交机制
    • 同时我们还将为您呈现一套完整的辅助索引管理方案

1 背景

Be-Tree结构如下：

在B-Tree及其变体Bε-Tree中，在这些数据结构中，在内部节点中则包含或持有枢轴键以及子指针字段，在叶节点中则包含有序排列的键值对集合，在这种组织下确保快速查询效率与较低的空间占用

问：叶子节点多大？键值对怎么在叶子节点中存储？一个叶子多个键值对？

大小为B的叶子包含B个键值对，下面称之为items

与传统Bε-Tree相比，在Bε-Tree中，内部节点不仅为缓冲区分配了一定的空间量级，在此过程中还会进行相应的优化配置以提升整体性能表现

疑问句：本文中的B-Tree是否是B+Tree？因为感觉上所有的k-v都储存在叶子节点中，并且中间节点仅负责索引作用。

---

2 插入和删除操作

2.1 插入过程

插入操作被编码为插入消息insert messages

寻址到特定key，然后把insert messages添加到根节点 的buffer中

一旦某个节点的buffer被填满时，则会将满足条件的一批消息发送给该节点的一个子节点

通常选取具有最多未决消息pending messages的孩子

**快速响应：**这样可以尽快把pending message刷到节点里面去

**分摊IO成本：**这样也可以下刷的时候保证每次写数据量不会太少，数据太少就变成随机小写了

每条message最终都会传递到适当的叶子节点，并将新的k-v添加到叶子

叶节点变得太满时分裂（同B树）

当内部节点拥有的子节点数量超出规定上限时会触发分裂操作（类似于B树），存储在缓冲区的消息将被分配至两个新的子节点中

2.2 性能关键

批量从根节点向下刷数据，新消息存储在根节点附近，避免全盘查找

仅当buffer满时（积累足够message）才向下刷，分摊IO成本

对小的 、随机的 插入有很好的优化效果

2.3 删除过程

该删除操作以形式化的方式编码为'tombstone-style message'的形式。
当'tombstone-style message'到达叶子节点时，则需要同时删除对应的目标对象及其携带的'tombstone-style message'。
在目标对象及其所有相关联的子节点仍未到达叶子节点之前，在线存储层中它们都会持续存在。
该删除操作类比于插入操作，在信息传递机制上具有相似性。

2.4 优化

避免大量消息全部流入一个叶子节点

直接将所有消息以及该叶子的所有其他未决消息刷新到叶子

启发式的方法（TokuDB和BetrFS）

---

3 查询操作

3.1 查询过程

包括两部分：

从根到叶子的查询（同B-Tree）

从根到叶子路径上节点的缓冲区中查询对应消息

要在查询结果返回前应用相关消息

对于键k的搜索，在叶子节点中定位到记录(k, v)，同时内部节点缓存区包含已过期（memento）消息，则此搜索结果返回NOT FOUND。
注意：在这种情况下，请确保此搜索无需更新叶子节点。
最终地，在已过期消息被移动至叶子节点之前进行此操作可能会导致错误。（？不是要在查询结果返回前应用相关消息吗）

范围查询与点查询相仿，在操作过程中需要检查并整合整个key范围内的相关信息。

3.2 buffer组织

1. 为了实现快速查找和插入操作, 通常采用平衡二叉搜索树结构来存储 buffer 数据, 其中一种典型实现方式是使用红黑树算法。
2. 缓冲区内的消息按照其 key 值进行排序后, 紧随其后的是带有时间戳的信息条目。这些时间戳的作用是确保所有消息能够按照正确的顺序被处理。

此外，在使用过程中会发现以下操作均较为高效：将消息插入到缓冲区中，并在其中进行查找；同时还可以实现刷新至另一个缓冲区域，并且这些操作均完成得非常迅速。

---

4 性能分析

4.1 模型假设

对比B-Tree和Bε-Tree，有以下假设：

1. 假设所有键值对具有相同的规模
2. 假设每个节点能够存储B个键值对
3. 假计N为计算机系统中整个树结构包含的键值对数量
4. 假设计算机系统中的每个节点只需通过一次I/O操作访问相关的数据

4.2 复杂度分析

对比B-Tree和Bε-Tree的渐进复杂度：

使得插入操作所需的时间减少至原来的εB^{(1-ε)}倍。
单点查询的计算复杂度保持不变；然而，在实际应用中由于树的高度增加到原来的\frac{1}{\varepsilon}倍，则会导致IO操作次数在\varepsilon=\frac{1}{2}时增加至原先的两倍。
范围查询所需的总开销等于第一个键对应的单点查询时间加上对所有剩余键进行扫描的成本（大致等于键的数量k除以每个块的大小B）。

4.3 缓存机制

通常位于靠近根部位置的节点往往会保留在RAM内存中，并通过LRU（Least Recently Used）替换策略来管理这些数据块。这意味着在实际应用中进行搜索所需的操作次数通常会少于O(logBN)次IO操作的数量。特别地，在所有非叶子节点均未被缓存的情况下，则仅需一次IO操作即可完成所需的查找过程。

---

5 节点大小B对性能的影响

1. B-Tree采用了较小的节点（几十到几百KB）以确保插入和删除操作的高效性, 但这种设计导致范围查询性能较弱。
2. Bε-Tree在较大的节点规模下（几百KB到几MB）仍具备较高的插入、删除和范围查询效率。
3. Bε-Tree的树高变为原始高度的1/ε倍, 其前提条件是各节点尺寸保持一致; 而采用较大尺寸后可缩短树高后半段。

---

6 参数ε对性能的影响

ε增加 ，枢轴键和子指针占比增大，缓冲区减小，增加查询性能 （极端为B树）

当ε值降低时

当ε设定为1/2时，查询性能接近于B树的表现。同时，在插入方面具有更低的成本（即每条记录的插入成本为√B分之一）。允许选择较大的节点大小。

实际需要支持可变长度的key这一需求下,B和ε这两个参数均为不确定值。在TokuDB和BetrFS中，默认节点大小设置为4MB,而其分支因子范围通常设置在4至16之间。这意味着每次刷新操作至少能够处理256KB的数据块。

---

7 使用指南

关键点：写性能比读性能高几个数量级。

7.1 引入upsert

避免read-modify-write的模式

一种类型的消息通过使用一个回调函数来编码并更新，并在无需预先知道键值的情况下发送。
这种消息能够对任何异步修改进行编码这些修改基于键旧值以及与其相关的某些辅助数据。
墓碑消息是其特例的一种。
此外(upsert)还可以用于增加计数器更新文件访问时间在取款后更新用户的账户余额以及其他多种操作。

upsert总结：

1. 其实是查询+插入的组合操作，可以理解为“更新”。

upsert(k,(f,Δ)) = v←query(k) + insert(k,f(v,Δ))

当upsert消息刷到叶子节点时，f(v,Δ)将代替旧值v。

当执行一个upsert操作时，在尚未到达叶子节点的情况下，请确保在收到查询结果前将其应用至特定的key字段。

在树结构中同一节点可能出现多个upsert消息（表示多次修改行为），系统需要对从根节点延伸至叶子节点路径上的所有这些upsert消息进行汇总，并按照时间戳顺序对它们进行整合处理。

7.2 引入secondary indices

利用插入性能来提升查询性能

• 该系统支持二级指针（或称二级键），能够存储并管理多个指针（或键），并在需要时根据查询类型自动选择相应的指针（或键）进行检索。
  • B-Tree管理大量指针会产生很高的成本（即高昂的操作开销）。对于大多数场景而言，在每一列上都建立一个独立的指针空间并不是一种经济可行的方法。
  • Bε-Tree由于其插入操作比查询操作耗时少得多，在绝大多数情况下都可以高效地处理所有的潜在查询需求。

设计辅助索引的三个规则：

对所有用于查询的列建立索引

举个例子来说吧，在包含三个字段(k₁, k₂, k₃)的数据表中，
当根据不同的字段（如k₁或k₂）执行查询操作时，
则必须维护相应的两个Bε-Tree结构。

保证每个索引都能直接查询到全部信息(k1,k2,k3)

例如应用程序采用键 k2 进行 k3 值查询，则按 k2 排序的索引此处每个条目均存储相应的 k3 值。
通常而言，在大多数情况下这些辅助索引仅提供主键信息。例如，在尝试通过键 k2 寻找 k3 值时会得到 k1，并基于此在主表中检索对应的 k3 值。

应使应用程序尽可能执行范围查询

一个按k2排序

保证每个索引都能直接查询到全部信息(k1,k2,k3)

例如应用程序使用键K2查找K3值则按K2排序的索引应为每个条目存储相应的K3值
许多辅助索引主要返回主索引的键比如使用键K2查找K3值会返回K1然后根据K1在主索引中寻找K3但是Bε-Tree并不是这样
例如应用程序使用键K2查找K3值则按K2排序的索引应为每个条目存储相应的K3信息
许多辅助索引用一种方法来获取所需数据比如通过指定某个特定的关键字如通过指定某个特定的关键字如通过指定某个特定的关键字如通过指定某个特定的关键字如通过指定某个特定的关键字如通过指定某个特定的关键字如通过指定某个特定的关键字如通过指定某个特定的关键关键字如通过指定某个特定的关键字如通过指定某个特定的关键字

应使应用程序尽可能执行范围查询

例如应用程序需寻找满足a ≤ k1 ≤ b以及k2符合特定谓词条件的所有记录，则应构建一个二级索引：该索引按k1值排序，并仅包含那些k2值符合特定谓词条件的记录。