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

图3: The structures of XIndex and FINEdex. FINEdex consists of model and data parts.3 THE FINEDEX DESIGN 实现高并发性能的关键是减少数据之间的依赖关系，以及减少线程之间的冲突。基于这些原则，FINEdex处理非共享级别箱中的插入，并同时以两种粒度重新训练模型，包括级别箱再训练和模型再训练。具体来说，level bin是附加在每个训练数据后面的2级排序数组，如图3b所示。这种肥厚的数据结构显著减少了线程冲突的数量，因为不同训练数据背后的关卡箱没有数据依赖性。新数据会按照顺序插入到关卡箱子中，以保持所有数据的排序。同时，现有的训练数据不受新数据的影响，这保证了在插入过程中不会丢失数据。当关卡箱已满时，我们同时以两种粒度重新训练数据，以适应运行时的新数据分布，包括关卡箱再训练和模型再训练。

前者重新训练全级bins以获得小模型，后者合并小模型以提高性能。由于FINEdex中的所有模型都是独立的，所以经过再训练后，旧模型很容易被新模型取代。通过这些设计，FINEdex使用多线程实现了高并发性能。
3.1 Model Part 作者提出了学习探针算法(LPA)来根据数据分布自适应地训练模型，确保所有的模型误差都小于给定的阈值。其思想是在垂直方向上找到宽度为2*max_error的平行四边形，使得没有训练过的数据被放置在平行四边形之外，如图2b中的灰色块所示。因此，作者利用平行四边形的两条垂线相交并平分平行四边形的直线，得到线性回归模型。
3.2 Data Part 无数据丢失。训练过的数据数组没有用于处理插入，以避免图2b中的数据丢失错误。
保持所有数据的排序范围查询。共享增量缓冲区的一个缺点是训练数据数组与增量缓冲区之间的数据重叠，这影响了范围查询的性能。与之不同的是，FINEdex在每个训练数据下处理结构中的插入，而不存在数据重叠，因此在插入过程中保持所有数据的排序。