FINEdex: A Fine-grained Learned Index Scheme for Scalable and Co(2)

1 INTRODUCTION 数据存储和访问性能对于内存系统很重要，但是数据的爆炸性增长加剧了这一问题。在过去的几十年里，现有的索引结构，如B 树、哈希映射和Bloom过滤器，通常支持内存系统以内存效率高的方式处理数据处理任务。
一般来说，基于树的结构对范围查询的所有数据进行排序，其目的是识别给定范围内的项目。许多系统(如NoSQL系统)构造基于树的结构来提供高效的数据存储和访问。尽管将所有数据和元数据完全保存在主存中可以避免昂贵的磁盘I/O操作，但一旦索引结构太大，无法放入有限大小的内存中，就会加剧高空间开销。事实上，在最先进的内存系统中，索引(例如基于树的结构)消耗了大约55%的总内存。
为了提高B 树的性能和降低内存开销，采用了强大的硬件来提高B 树的性能，包括缓存、SIMD和gpu。同时，一些压缩方案利用前缀/后缀截断、字典压缩和键归一化技术来节省空间。为了减少B 树的内存开销，还提出了近似结构。

然而，以上所有方案都是针对通用数据结构设计的，并且主要关注索引结构本身，而忽略了内存系统中数据分布的模式。Kraska等人认为，精确的数据分布可以有效地优化索引结构。例如，线性回归函数足以存储和访问一组连续的整数键(例如，从1到100M的键)，这在查找性能和内存开销方面比传统的B 树有显著的优势。数据分布的模式对于内存系统提供高性能变得非常重要。然而，在现实世界的应用程序和系统中(例如，处理智能设备的数据，Facebook和LMDB的pb级存储系统)，一些模式极其复杂，甚至无法通过已知的模式来表示。因此，我们考虑使用机器学习(ML)方法来学习显示数据分布模式的模型，称为学习索引。
学习到的索引为内存系统的索引开辟了一个新的研究主题:索引可以被视为ML模型。作者使用具有成本效益的计算来加速传统的比较，从而提高访问速度并节省内存空间。此外，为了有效地利用多核处理器的优势，作者进行了并发操作以提供高性能。本文上下文中的并发性被解释为使用多线程执行索引操作(例如，读取和写入数据)。然而，由于以下挑战，要在并发内存系统中有效地利用学习到的索引并非易事。