来给博客除草了：Learned Indexes for a Google

1. 引言

这是一篇业界发表在 2020的Wip论文《规模的基于磁盘的数据库的学习索引》。自从学习索引祖师爷Tim @MIT在 2018发表了第一篇 index的工作之后，有关学习索引的paper呈现 trend。目前，较多的工作focus在in-的层面，直到最近才出现一些工作，研究将学习索引从内存拓展到更远的存储（NVM、SSD、RDMA等）。在内存外学习索引的研究工作中，LSM-tree存储结构是一个令人的方向。得益于LSM-tree的设计哲学，LSM-tree中的组件是read-only的，这种读写特性与学习索引相当契合（学习索引最初也是为了优化读性能而生，原始学习索引并不支持写插入、写更新）。LSM-tree是三驾马车之一——的原型，是研发的分布式海量数据存储系统。将学习索引和进行结合，提升了的读性能。

2. 问题

作者介绍了目前中使用索引的现状：

问题：

作者认为， index天生的存储优势（ index space）有助于缓解cache压力，减少index从外存fetch的次数（尤其有利于减少tail ），从而减少存储资源的占用，提升的吞吐量。

祖师爷最早提出的内存学习索引并不适用于。为此，作者们训练了一种将key映射到中对应的data block的学习索引结构。

3. 背景

LSM-tree LSM-tree是一种非常经典、流行的键值存储结构，具有极其高效的写入效率，和较高的读取效率。其介绍参见：

是PB级别的分布式存储系统，支持低延迟、高吞吐。的结构原型为LSM-tree，谷歌大牛Jeff Dean在十年前将LSM-tree/的实现开源为。

是LSM-tree持久化存储的组件。存储众多键值对，按key进行排序。为了支持对数据集进行有效的操作，将数据分割成data block，并保留索引，说明哪些键位于哪些数据块中。读取时可以使用索引，来找到一个key所在的数据块。

索引被存储在index block中。索引条目包含了每一数据块的位置和大小。利用这些信息，数据块可以被有效地加载到内存中。索引块被keep in ，这意味着读取，特别是连续读取，可以通过查询索引块来完成，并且只对请求的数据进行磁盘读取。

索引是在构建的同时创建的。在构建过程中，一旦一个数据块被填满，该数据块的代表性item（通常会是该数据块的首个item或者最后一个item）就被添加到索引中。之后，该数据块连同其索引被持久化到文件。

随着大小的增加，索引块的大小也会增加。为了提高索引效率，使用两级索引，包括一个0级索引和一个1级索引。0级索引跨越多个索引块，并且总是驻留在内存中，指向1级索引块。第1级索引是一个1级索引块的序列，它指向数据块。当1级索引块所指向的数据块被访问时，一级索引块被加载到内存中。

4. Index for Disk-based

设计 原本的索引，能够确定所给key存储在哪个data block中。而学习索引根据key预测到其存储的。作者认为，预测到具体的对没用，因为即便预测到了，还是要把这个所在的data block加载到内存。因此，作者设计的学习索引。将key映射到data block这个粒度。

但即便是预测到data block，作者认为预测错误的代价大，因为要重新读取周围的data block，这将带来更大的开销（存疑：不可以增加元信息来辅助判断么？）

于是，本文学习索引任务表示为：

训练学习索引f(*)，接受key作为输入，以key所在的data block 作为输出。作者在此用了一个trick：在构建的过程中动态确定学习索引预测的误差值e，以确保能够落在f(k)预测的data block内。因此，这就确保了后续访问时，学习索引总是能给出确切的key所在的data block。

训练 上文提到，学习索引最后预测到的是data block ，但是现在的情况是压根不知道哪个key对应哪个data block 。

因此，换一种方式，先将key映射到字节偏移量。引入下面的记号：

因此，f(k)预测出byte 之后，就可以得到其存储的data block 为：

（存疑：除以平均block size就能得到准确的block 了么？这里应该有更多的说明或论证）

在预测到block 之后，通过取B[block ]，可得到数据在磁盘上存储的位置，进一步将data block读取进内存中。这里B是作者预先处理好的磁盘位置数组。

模型 LR模型（线性回归）。

5. 实验

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img--41)()]

6. 相关工作