From WiscKey to Bourbon: A Learned Index for Log-Structured Merge Trees

我们介绍了BOURBON，一种利用机器学习提供快速查找的合并(LSM)树。我们基于对LSM设计的仔细分析得出的经验原则来设计和实现。BOURBON使用贪婪的分段线性回归来学习键分布，以最小的计算实现快速查找，并应用成本效益策略来决定何时学习是值得的。通过在合成数据集和真实数据集上的一系列实验，我们表明，与最先进的生产lsm相比，BOURBON通过1.23×-1.78×提高了查找性能。

一研究内容

    本文将学习索引的思想应用到lsm中。一个主要的挑战是，虽然学习索引主要是为只读设置定制的，但LSMs是为写设置优化的。写操作会破坏学习到的索引，因为在现有数据上学习到的模型现在必须更新以适应更改;因此，系统必须反复重新学习数据。然而，我们发现lsm非常适合学习索引。例如，虽然写操作会修改LSM，但树的大多数部分是不可变的;因此，学习一个预测键值对位置的函数只需要一次，只要不可变数据存在就可以使用。然而，随之而来的是许多挑战。例如，键或值的大小不定，使得学习预测位置的函数变得更加困难，过早地进行模型构建可能会导致大量的资源浪费。

BOURBON使用分段线性回归(piecewise linear regression)，这是一种简单但有效的模型，能够以很小的空间开销实现快速训练(即学习)和推理(即查找)。BOURBON采用了文件学习:模型是建立在文件之上的，因为LSM文件一旦创建，就不会在原地修改。BOURBON实现了一个成本-