Jeff Dean的Learned Index为数据库索引带来了哪些启发2

本文继续讨论Recursive Model Index(RM-Index)索引更新涉及的相关问题,以及Learned Index对Hash索引以及Bloom Filter索引如何进行改造来降低索引占用空间。

RM-Index索引的更新

上篇文章中关于RM-Index的设计以及与B-Tree索引的对比测试结果,主要针对只读场景的内存型数据库系统,也可以应用于更新频率较低的数据仓库系统中,对于Bigtable而言,每一个SSTable都是当内存中的数据积累了一定量之后才生成的,也可应用RM-Index的思路来优化现有的B-Tree索引。

数据更新包括两种情形:

  • appends 在现有数据集合的尾端进行appends
  • inserts 在现有数据集合的中间进行inserts

通常,对于inserts场景,新的数据应该基本遵循已有的数据分布特点的,因此,原来的模型不需要重新进行训练。而对于appends场景,如果现有模型对Key的趋势能够做很好的预测,现有模型也不需要进行重新训练。在现实应用中,会存在两方面的挑战:

  • 如果Model阶段的预测越精确,往往意味着该模型对于新数据的分布预测会更差,这里存在一些矛盾
  • 如果分布发生了变化,是否能够及时的侦测到?或者,当分布发生变化时,性能是否会出现急剧的恶化?

还有另外一种思路来实现数据的更新:将新的数据放在一个delta-index中,所有的新数据都暂存在内存buffer中,当达到一定的阈值触发Merge操作时,对模型进行重新训练,而这个训练的过程完全可以借助于TPU/GPU进行加速。

Hash索引(Point Index)

对于Hash索引而言,基于Key的查询,在性能上已经是极致了,因此,Learned Index已经难以进行突破。但现有的Hash索引存在一个显著的问题:基于通用数据分布设计的Hash Function,难免会带来明显的键冲突问题,当两个键冲突以后,通常基于一个linked-list或secondary probing来处理重复的记录,无论哪种方式,都会导致在存储空间占用上带来一些浪费。例如,Google的dense-hashmap,有额外的78%的冗余开销,而sparse-hashmap虽然仅有4个bits的额外开销,但在性能上却降低了3~7倍。

Learned Index期望对数据的分布进行学习以后,能够提供一种更佳的模型(即寻找一种更佳的Hash Function),尽可能的降低键冲突:

HashMapVsLearnedHashMap

如下是利用Learned Index优化后的Hash索引与传统Hash索引的对比测试结果:

ModelVsHashIndex

从结果来看:在空间开销上,均有不同程度的节省,有的场景节省高达78%,但在查询性能上,有一定程度的削弱。空间占用与查询性能之间需要做一些取舍。

Bloom Filter索引(Existence Index)

Bloom Filter索引常被用来快速判断一个Key是否存在于一个大集合中。如下图所示:

BloomFilter

图中的Bloom Filter使用了3个Hash函数{h1,h2, h3},写入一条新数据key1时,通过这3个Hash函数对key1进行计算,得到3个Hash值{p11,p12, p13},然后,在一个所有位初始值为0的大的byte数组中,将{p11, p12,p13}对应的位分别设置为1。同样的,当来了一条新数据key2以后,如果得到的Hash值分别为{p21,p22,p23},也将数组中的{p21,p22,p23}对应的位设置为1。

当判断一个Key是否存在于这一个集合中时,也是先利用3个Hash函数对Key值计算得到3个Hash值,而后判断这3个Hash值所对应的位是否为1,如果都为1,则可断定Key值是可能存在的。为何说是”可能存在”而不是”确定存在”呢?原因在于,Hash值存在一定概率的键值冲突,因此,这3个位有可能是被别的Key的Hash值改为1的。这就是Bloom Filter所谓的“误判”。但当Bloom Filter判定一个元素不存在时,该结果却是确定可信的。

:Bloom Filter的Hash函数数目与底层的byte数组的大小,与误判率的值有关,这里不详细展开

与前面提及的问题类似:传统的Bloom Filter的实现,并不会参考实际的数据分布特点,更不会考虑有效Key无效Key之间的区别

利用Bloom Filter索引判断一个Key值存在与否(或者说判断一个Key是否为有效Key),也可以理解为一个二值分类问题。因此,可以基于如下模型训练神经网络:

D = {(xi, yi = 1)|xi ∈ K} ∪ {(xi, yi = 0)|xi ∈ U}.

其中,K为有效Key的集合,U为无效Key的集合。

神经网络模型可以采用CNN(卷积神经网络)或RNN(循环神经网络),因为它们更擅长处理字符串。

Learned Index对传统Bloom Filter的改造思路在于,即考虑了有效Key的分布,又考虑了无效Key的分布,而训练的过程可借助于TPU/GPU进行加速。从最终的效果来看,在Bloom Filter占用空间上均有显著的降低

既然可以将Bloom Filter要做的事情理解为一个二值分类问题,那基于Learned Index的改进思路,没有必要完全参考现有Bloom Filter的所有特性,利用Learned Index还可以做更多有价值的事情,例如,判断一个网站是否是钓鱼网站,其它的特性,如将WHOIS数据或IP信息纳入到模型中,可以更好的改善结果的准确率,降低Bloom Filter数据大小。

总结

Learned Index并不是意图去替代现有的索引,而是对现有索引机制的一些补充:它提供了一种更优的构建索引的思路,但目前为止,该思路主要还是针对Read-Only的OLAP查询任务而设计的,对于存在大量实时写负载的场景,还需要做更多的探索。Learned Index与传统索引的对比,好比RDBMS中的CBO与RBO,未来一定会让数据库的索引更加智能和高效。

References

[1] The Case for Learned Index Structures

推荐阅读:

Jeff Dean的Learned Index为数据库索引带来了哪些启发1

本文源自:NoSQL漫谈(nosqlnotes.com)
除非特别注明,本站文章均为原创,转载请注明出处和链接。

One comment

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注