摘要:在大数据与云计算时代，数据访问速度是衡量大规模存储系统性能的一个重要指标.因此，如何设计一种轻量、高效的数据索引结构，从而满足系统高吞吐率、低内存占用的需求，是当前数据库领域的研究热点之一.Kraska等人提出使用机器学习模型代替传统的B树索引，并在真实数据集上取得了不错的效果，但其提出的模型假设工作负载是静态的、只读的，对于索引更新问题没有提出很好的解决办法.提出了基于中间层的可扩展的学习索引模型Dabble，用来解决索引更新引发的模型重训练问题.首先，Dabble模型利用K-Means聚类算法将数据集划分为K个区域，并训练K个神经网络分别学习不同区域的数据分布.在模型训练阶段，创新性地把数据的访问热点信息融入到神经网络中，从而提高模型对热点数据的预测精度.在数据插入时，借鉴了LSM树延迟更新的思想，提高了数据写入速度.在索引更新阶段，提出一种基于中间层的机制将模型解耦，从而缓解由于数据插入带来的模型更新问题.分别在Lognormal数据集以及Weblogs数据集上进行实验验证，结果表明，与当前先进的方法相比，Dabble模型在查询以及索引更新方面都取得了非常好的效果.



Abstract:In the era of big data and cloud computing, efficient data access is an important metric to measure the performance of a large-scale storage system. Therefore, design a lightweight and efficient index structure, which can meet the system's demand for high throughput and low memory footprint, is one of the research hotspots in the current database field. Recently, Kraska, et al proposed to use the machine learning models instead of traditional B-tree indexes, and remarkable results are achieved on real data sets. However, the proposed model assumes that the workload is static and read-only, failing to handle the index update problem. This study proposes Dabble, a middle layer based scalable learning index model, which is used to mitigate the index update problem. Dabble first uses K-means algorithm to divide the data set into K regions, and trains K neural networks to learn the data distribution of different regions. During the training phase, it innovatively integrates the data access patterns into the neural network, which can improve the prediction accuracy of the model for hotspot data. For data insertion, it borrows the idea of LSM tree, i.e., delay update mechanism, which greatly improved the data writing speed. In the index update phase, a middle layer based mechanism is proposed for model decoupling, thus easing the problem of index updating cost. Dabble model is evaluated on two datasets, the Lognormal distribution dataset and the real-world Weblogs dataset. The experiment results demonstrate the effectiveness and efficiency of the proposed model compared with the state-of-the-art methods.



PDF全文下载地址:

http://jos.org.cn/jos/article/pdf/5910