共计 5249 个字符，预计需要花费 14 分钟才能阅读完成。
本文系北京理工大学科研助理牛颂登所著，本篇也是 OceanBase 学术系列稿件第 10 篇。欢送拜访 OceanBase 官网获取更多信息：https://www.oceanbase.com/
「牛颂登：北京理工大学科研助理，硕士期间在电子科技大学网络空间平安研究院从事聚类和强化学习相干算法钻研，在利用聚类钻研个性化在线学习和强化学习的处分函数设计方向获得了肯定成绩，目前钻研方向为机器学习和数据库相结合的畛域。」
明天分享的论文是 ”Breaking Down Memory Walls in LSM-based Storage Systems. PVLDB, 14(3): 241-254, 2020. doi: 10.5555/3430915.3442425 ”
心愿浏览完本文，你能够对基于 LSM-tree 存储系统的内存治理有新的播种，当然也能够有不同认识，欢送在底部留言探讨。
明天为大家带来的这篇论文是加州大学的陈罗博士 2020 年发表于 PVLDB 的一篇论文：次要内容是其提出了一种动静的基于 LSM-tree 的存储系统的内存治理构造，以及依据工作负载动静调节写内存和缓冲区缓存内存调配的调优器，并在 AsterixDB 上别离以不同工作负载模式对单 LSM-tree 和多 LSM-tree 下的内存治理和内存调优器进行了性能测试。
自适应的内存治理构造
LSM-tree 被广泛应用于古代 NoSQL 零碎中，如 LevelDB、RocksDB、Cassandra、HBase、X-Engine、AsterixDB 等。与传统的就地更新构造不同，LSM-tree 采纳了非就地更新设计：首先在内存中缓冲所有写入，它们随后被刷新到磁盘，以造成不可变的磁盘组件；磁盘组件被定期合并，以进步查问性能和回收废除记录所占用的空间。与所有的页面都在共享缓冲池中治理的就地更新零碎相比，LSM-tree 引入了额定的内存墙，这些内存墙是指各个内存区域之间妨碍无效内存共享的阻碍。
图 1 基于 LSM-tree 的存储引擎构造
以图 1 为例，总内存被划分为存储内存组件的写内存和存储不可变页面的磁盘缓冲区缓存。在这样的一个构造中存在三道内存墙，首先是为内存组件被调配固定的大小，例如 RocksDB 为每个内存组件设置了大小为 64MB 的限度，而 AsterixDB 规定最大可写的数据集个数为 N 个（N 默认是 8），也就是说每个沉闷的数据集只能失去 1/N 的总的写内存。这样做的益处是比拟不便，而且肯定水平上能保障鲁棒性[1]，但因为固定或者平均分配不是最优的调配办法，因而可能对系统的性能有负面的影响。
图 2 论文提出的自适应的内存治理构造
为了突破这三道内存墙，本文提出了一种自适应的内存治理构造，与前一种的不同体现在：
- 首先，不为每个内存组件设置大小限度，而是所有内存组件都是通过共享的内存池来治理的；
- 其次，依据不同的工作负载动静地将写内存的组件（即 SSTable 文件）进行刷盘操作，当 LSM-tree 没有足够的内存来存储传入的写操作时，将从池申请更多的页面，而当总体写内存应用过高时，将抉择 LSM-tree 将其内存组件刷新到磁盘；
- 最初，论文提出的内存调优器能够自适应地调节写内存和缓冲区缓存的内存调配。
正是通过这样的构造无效地突破了后面的三道内存墙。
写内存治理
一、分区内存组件
应用新的内存治理构造，内存组件能够变得十分大，因为它的大小不受限制。现有的 LSM-tree 实现应用跳表或者 B+ 树来治理内存组件，并始终将内存组件齐全刷新到磁盘。然而，这缩小了内存的应用，起因有两个：
首先，因为 B+ 树的页面大概有 2/3 是满的，所以在应用时可更新的 B+ 树存在外部碎片；
其次，思考一个很大的 memtable 对象被刷新到磁盘之后，内存释放出来，新的 memtable 在前一段时间内内存利用率都很低，这升高了随着时间推移的均匀内存利用率。
图 3 分区内存组件的 LSM-tree 构造
为了最大限度地利用内存，论文针对单个 LSM-tree 的内存组件提出应用内存分区的 LSM-tree 来治理写内存，即写内存也采纳分层的形式。 如图 3 所示，能够分为 M0，M1 和 M2 三层，在 M0 处有一个流动的 SSTable 用于存储传入的写操作。当 M1 存满时，它的一个 SSTable 将应用内存合并到下一个层 M1。在抉择合并的 SST 时，论文应用了一种贪心抉择策略，通过最小化在 M1 层重叠的 SSTable 的大小与所选的在 M0 处的 SSTable 的大小之间的比值来抉择 SSTable 进行合并。
M2 层的内存 SSTable 最终被刷新到磁盘。对于内存组件存满所触发的刷新，M2 的 SSTable 将以循环形式刷新到磁盘。对于由事务日志长度过长所触发的刷新，应用最小日志序列号 (Log Sequence Number，LSN) 的 SSTable 将被刷新到磁盘。
这样的构造进步了内存利用率并升高了写入放大。首先，LSM-tree 比 B+ 树取得了更高的空间利用率；其次，因为所提的构造是范畴分区的，它能够应用局部刷新，一次刷新一个内存 SSTable，从而使写内存始终保持满的状态。
二、多 LSM-tree 内存治理
在治理多个 LSM-tree 时，一个根本问题是如何将写内存调配给这些 LSM-tree。因为写内存是按需分配的，所以这个问题变成了如何抉择要刷盘的 LSM-tree。对于日志触发的刷新，应该刷新 LSN 最小的 LSM-tree 以执行日志截断；对于内存触发的刷新，现有的 LSM-tree 实现 (如 RocksDB 和 HBase) 抉择应用最大的内存组件刷新 LSM-tree。直观的感觉是，刷新这个 LSM-tree 能够回收最多的写内存，这些内存能够用于后续的写操作。然而，此策略可能不适宜分区内存组件，因为因为局部 SSTable 刷新，刷新任何 LSM-tree 都将回收雷同数量的写内存。
一种可选的办法是最小日志序列号策略，即每次抉择最旧的 LSN 进行刷盘操作。这样做，LSM-tree 的刷新速率会与它的写入速率大抵反比，而且比拟热的 LSM-tree 会比拟冷的 LSM-tree 更频繁地刷新。此外，当刷新是以日志触发型的刷新主导时，这样的策略还有助于日志截断。
论文提出了一种最优的刷盘策略，当给定 K 个 LSM-tree 的时候，写内存的调配能够被定义为一个最小化写老本的优化问题，即通过最小化第 i 个 LSM-tree 的写速率与每个条目大小的比值，乘上每个条目标写老本，这样一个式子来实现最优的写内存调配，如下式①所示。
其中 ai 为第 i 个 LSM-tree 的内存调配比，ri 为第 i 个 LSM-tree 的写速率，Ci 是每个条目标写 I/O 老本。而 Ci 能够通过首次写入日志时的老本和每次合并时产生的老本之和计算，如下式 ②：
其中 ei 为条目大小，P 为磁盘页面大小，T 为合并策略的大小比，|Li | 为第 i 层的大小，Mw 为总的写内存大小。将②式带入①式，再由拉格朗日乘数法可得下方③式：
即第 i 个 LSM-tree 的最优内存调配比等于它的写速率占所有 LSM-tree 的写速率的比值。也就是说，调配给 LSM-tree 的写内存应该与它的写速率成正比，较热的 LSM-tree 相比于较冷的 LSM-tree 会取得更多的写内存。
三、内存治理计划评估
论文首先对提出的分区内存组件办法和最优刷盘策略进行了评估试验，采纳的测试平台是 AsterixDB，基线别离是基于动态 B+ 树和动静 B+ 树的内存治理办法。动态的 B+ 树内存治理办法下，分为 AsterixDB 默认设置的沉闷数据集个数为 8 的 B+ 树动态默认基线和每个试验下不同的沉闷数据集个数 B+ 树动态调节基线。动静 B+ 树内存治理办法是指不为每个内存组件设置大小限度。刷新策略别离采纳了最大内存、最小日志序列号的刷新策略和论文提的最优刷新策略，并在 YCSB 的不同读写比率的工作负载模式进行了试验。
图 4 单 LSM-tree 的内存组件试验评估后果
图 4 为在单个 LSM-tree 的内存治理比照试验，能够看到针对不同的工作负载，尤其是写入沉重的工作负载 (图 4 b) 下，因为分区内存组件办法更无效地利用写内存，对系统的性能晋升最大。
图 5 多 LSM-tree 内存组件试验评估后果
图 5 为在多个 LSM-Tree 的比照试验下，最小日志序列号策略和最优刷新策略通过在 LSM – 树之间更好地调配写内存，晋升了零碎整体的吞吐量。
内存调优器
一、调优办法
内存调优器的指标是在写内存和缓冲区缓存之间找到最优的内存调配，以最小化每个操作的 I/O 老本，这反过来又能够最大限度地进步零碎效率和总体吞吐量。假如总可用内存为 M，为了便于探讨，假如写内存大小为 x，这意味着缓冲区缓存大小为 M-x。设写内存为 x 时，write(x) 和 read(x) 是每次操作的写老本和读老本。调优指标是最小化每个操作的加权 I/O 老本，失去以下公式④：
这里的两个加权参数 ω 和 γ 容许用户针对不同的用例调整调优指标。例如，在机械硬盘上，因为 LSM-tree 次要应用程序 I/ O 进行写操作，ω 能够设置得更小；而在固态硬盘上，因为 SSD 的写操作通常比读操作老本更大，ω 能够设置得更大些。因为最佳的内存调配依赖于所处的工作负载，因而论文中采纳了在线调优办法来执行间断调优。通过对 cost(x) 进行求导得出了 write(x) 和 read(x) 的导数，并通过实时的统计影响 write(x) 和 read(x) 导数的一些量，来调节动静地内存的调配。
二、理论中的 I/O 老本
内存调优器的最优性取决于 cost(x) 的形态。为了确保内存调优器总是找到全局最小值，cost'(x) 应该最多有一个根。直观上，当调配的写内存的大小比拟小的时候，会有大量的合并操作，合并老本会比拟大，总的 I/O cost 也会比拟大；而当调配的写内存大小十分大的时候，合并老本会相应减小，然而会减少缓存未命中（buffer cache miss），读的老本会减少，总的 I/O 老本也会减少。因而，一个最优的 x 应该均衡读和写的老本。
图 6 操作的 I / O 老本受写内存的大小影响
论文通过试验发现许多理论工作负载的 cost(x) 通常容许内存调优器找到全局最小值。图 7 描述了试验中 YCSB 写沉重工作负载（其中写和读的比重别离占 50%）和 TPC-C 工作负载的 I/O 老本。这些操作散布在 10 个 LSM-tree 中，每个 LSM-tree 有 1000 万条记录，遵循 80-20 热点散布。对于 TPC-C，比例因子设置为 2000。能够看到，对于这两种工作负载，总 I/O 老本都有一个全局最小值。论文还通过扭转总的内存大小和读写比率来评估其余配置，并发现总的 I/O 老本总是具备雷同的总体形态。
图 7 不同写内存大小下的 I / O 老本
三、性能评估
在所有试验中，初始写内存大小设置为 64MB，模仿缓存大小设置为 128MB。LSM-tree 有 1 亿条记录，总容量为 110GB。为了评估内存调优器的准确性，在 TPC-C 上进行了一组试验，以比拟调优后的性能和最佳性能。这里应用 TPC-C，因为它比 YCSB 示意更简单、更理论的工作负载。比例系数设定为 2000。因为对于用到的 SSD 写入的老本是读取的两倍，在试验中，设置写权值 ω 为 2，读权值 γ 为 1，以均衡这两个老本。
为了找到最优内存调配（称为 opt），应用穷尽搜寻来评估不同的内存调配，增量为 128MB。为了显示内存调优器的有效性，试验蕴含了两个额定的基线。第一个基线（称为 64M）总是将写内存设置为 64MB，这是内存调优器的终点；第二个基线（称为 50%）在缓冲区缓存和写内存之间平均分配总的内存估算。总内存估算从 4GB 改为 20GB，每个试验运行 1 小时。图 8 显示了每个操作的加权 I/O 老本和不同内存调配的事务吞吐量。
图 8 TPC- C 上的内存调优器性能评估
应用穷举搜寻，论文发现最小化加权 I/O 老本也能够最大化事务吞吐量。主动调优的 I/O 老本和吞吐量（tuned）十分靠近于通过穷举搜寻找到的最优值，这表明了内存调优器的有效性。此外，内存调优器的性能显著优于两个基于启发式的基线。调配较小的写内存能够使读开销最小化，但会导致更高的写开销。相比之下，调配一个大的写内存能够使写开销最小化，然而读开销会减少很多。因而，这两种调配也不能最大化总体事务吞吐量。
结语
本论文提出能够促成自适应内存治理的 LSM 内存治理构造，通过分区内存组件构造和新的刷盘策略，以更好地利用写入内存；为了突破写内存和缓冲区缓存之间的内存墙，引入了内存调优器，它能够依据工作负载模式间断地调优内存调配。试验证实，通过这些技术一起反对自适应内存治理，以最大限度地升高了基于 LSM 的存储系统的 I/O 老本。
参考文献：
[1] Taewoo Kim, Alexander Behm, Michael Blow, et al. 2020. Robust and efficient memory management in Apache AsterixDB. Software: Practice and Experience 50, 7 (2020), 1114–1151.
欢送拜访 OceanBase 官网获取更多信息：https://www.oceanbase.com/
