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

降低高并发的数据依赖性。FINEdex通过肥化数据结构减轻了数据依赖，即每个训练数据都有自己的小型缓冲区来处理修改，而不是与数万个训练数据共享一个大缓冲区。此外，我们在运行时通过fne粒度再训练将缓冲区绑定到较小的大小，以保持低数据依赖性。这样的设计显著地减少了线程冲突，提高了并发性能，这在我们的实验评估中得到了证明。
作者提出了训练数据下的水平箱结构来处理这些修改。关卡箱的结构是一个经过修改的两级b树，如图3b所示。水平块表示根容器，垂直块表示子容器。当两级储存器未满时，将像b -树一样插入新数据，不同的是数据按优先级插入到前一个子储存器中。完整级别的容器不会增长到更高级别，以避免基于树的结构中的高度数据依赖。相反，我们建议使用两种粒度的细粒度再训练来容纳更多的数据。
具体来说，图3b显示了关卡箱是如何处理插入的。一开始，为了节省空间，只在训练过的数据下放置一个箱子，根据需要构造其他箱子。例如，我们构造两个子bin，当根bin已满时插入16。随着插入的数据增多，数据会优先插入到上一个子bin中，以提高空间利用率。此外，为了插入20，我们将现有数据向前移动到第一个子bin以保持所有数据的排序。在本例中，我们最多移动(n 1)个数据，其中n是子bin的长度。当前一个子bin已满时，数据像两层b树一样被插入，在最坏的情况下最多移动(m n/2)个数据，其中m和n分别表示根bin和子bin中的槽数。

3.3 Concurrent Retraining3.3.1 Level-Bin Retraining. 重新训练模型需要重新训练训练过的数据数组和关卡箱中的所有覆盖数据。因此，即使只有一个训练数据的level bin是满的，重新训练整个模型也是昂贵的。为了解决这个问题，我们基于完整箱子的数据重新训练一个新模型，而训练过的数据数组和级别箱子中的其他数据不被重新训练。新模型附加在相应的训练数据下，在新模型下创建新的级别箱来处理插入，如图4所示。level -bin再训练可以获得较高的并发性能，因为为了数据一致性，只锁定满level bin，而不涉及其他数据。此外，执行level-bin再训练是具有成本效益的(例如，在我们的实验中为27μs)，因为满level bin包含不超过n * m个数据，其中m和n分别代表根和子bin中的槽数。
3.3.2 Model Retraining. 如图4所示，FINEdex通过对不同模型(即大模型和覆盖的小模型，包括较小的模型)训练后的数据数组进行模型再训练。根据3.2节的设计原则，在覆盖的训练数据数组上训练新模型，这些数据数组不受新数据的修改。再训练过程在后台执行，以隐藏并发系统中的延迟。在重新训练过程中，关卡箱不会受到影响，并且可以在不阻塞整个系统的情况下并发地处理就地修改。我们直接在新训练的数据数组下附加关卡箱子的指针。在重新训练新模型后，FINEdex使用RCUbarrier来确保所有线程都能访问新模型。RCU-barrier是一种并发系统的同步机制，它允许所有读取器访问共享内存中的新数据结构，而不是旧数据结构。由于新模型和旧模型都指向相同的级别容器，并且重新训练期间的修改在级别容器中就地处理，因此在模型重新训练期间的任何并发修改都不会丢失。