江苏龙网

  1. 主页 > 生活百科 > >

百万并发场景中倒排索引与位图计算的实践( 二 )

索引


文章插图
复杂度分析
通过上面的例子我们可以看到，在时间复杂度方面查找候选规则集时，进行一轮 || 运算，一轮 & 运算；在查找最优规则时进行一轮 & 运算，所以整体复杂度是 3n≈n 。
在空间复杂度方面，相比原来的行式存储，倒排索引的存储方式，每列都需要存储行 ID，相当于多了 *(n-1)Posting List 存储空间，当然这是粗略计算，因为实际上行 ID 的存储最终转换为位图存储，在空间上有非常大的压缩空间 。
工程问题 - 压缩位图
如果倒排索引位图非常稀疏，系统会存在非常大的空间浪费 。我们举一个极端 case，若千万规则库中命中的行 ID 是第 1000 万位，按照传统方式 BitSet 进行存储，需要消耗 1.2MB 空间，在内存中占用存在严重浪费，有没有压缩优化方案，在 RoaringBitMap 压缩位图方案中我们找到，相同场景在压缩位图方式下仅占 144bytes；即使在 1000 万的位图空间，我们随机存储 1 万个值，两者比也是在 31K vs 2MB，近 100 倍的差距，总的来说 RoaringBitMap 压缩率非常大 。
RoaringBitMap 本质上是将大块的 bitmap 拆分成各个小块，其中每个小块在需要存储数据的时候才会存在，所以当进行交集或并集运算的时候，RoaringBitMap 只需要去计算存在的块而不需要像 bitmap 那样对整个大块进行计算，既做到了压缩的存储又做到计算性能的提升 。
以下图 821697800 为例，对应的 16 进制数为 30FA1D08， 其中高 16 位为 30FA，低 16 位为 1D08 。先用二分查找从一级索引（即 Container Array）中找到数值为 30FA 的容器，该容器是一个 Bitmap 容器，然后在该容器查找低 16 位的数值 1D08，即十进制下 7432，在 Bitmap 中找到相应的位置，将其置为 1 即可 。

百万并发场景中倒排索引与位图计算的实践

文章插图
适用场景分析
回顾上面的设计方案我们可以看到，这种方式仅适用于 PostingList 简单如行 ID 的形式，如果是复杂对象就不适合用位图来存储 。另外仅适用于等值查询，不适用于 like、in 的范围查询，为什么有这种局限性？因为这种方式依赖于搜索条件的空间，在方案中我们将值的条件作为搜索的 Key，值的条件空间希望尽可能是一个有限的、方便穷举的、小的空间 。而范围查询导致这个空间变成难以穷举、近乎无限扩张的、所以不适用 。
其他优化方式
除了使用位运算的方式对倒排索引加速，考虑到 Posting List 的有序性，还有其他的方式比如使用跳表、Hash 表等方式，以 ES 中采用的跳表为例，进行 & 运算实际就是在查找两个有序 Posting List 公共部分，以相互二分查找的形式，将时间复杂度控制在 log (n) 的级别 。
具体参见《工业界如何利用跳表、哈希表、位图进行倒排索引加速？》：https://time.geekbang.org/column/article/221292?utm_source=related_read&utm_medium=article&utm_term=related_read
百万并发场景中倒排索引与位图计算的实践

文章插图




推荐阅读


上一篇：愿意的反义词是什么标准答案?愿意隆重忘记的反义词?

下一篇：什么是瞬态集群？解读火山引擎EMR Stateless 的创新理念以及应用