elasticsearch之Roaring Bitmaps的结构

1. 投递集合说明:

如果你是刚刚接触搜索引擎，你可能会感到奇怪，构建搜索引擎中存储块的一个很重要的原因是搜索引擎能够有效地压缩和快速解码有序的数字集合。 为什么这个很有用？你可能知道elasticsearch的分片，是基于lucene的索引基础上的，将数据分割成一个个小片段(segment)进行存储的， 然后有规律地将这些小片段进行合并。在每个片段里面，每个文档都会有一个从0到2的31次方减1之间的唯一标识。这种结构像是数组的下标一样： 它存储在任何地方，而且足以标识一个条目。文档有序地存储在片段中，而且doc ID就是文档在存储片段中的索引。所以存储片段中的第一篇文档 的doc ID为0，第二篇为1。直到最后一篇文档，它的doc ID和这个存储片段中所有文档的数量减一是一样的。

为什么这些doc ID很有用呢？倒排索引需要把文档列表中的term映射成terms,也就是传入的集合，并且我们刚刚讨论的这些doc IDs 能完美胜任工作，因为它们能被有效压缩。

2. Frame Of Reference

为了能够让计算插入和关联更有效率，我们要求这些传入的集合是有序的。这个讨论中一个很不错的副作用就是传入的集合可以通过delta编码压缩。

举个例子，如果你的传入集合是[73,300,302,343,372],对应的deltas集合就是[73,227,2,30,11,29]。这里需要提到的一个很有意义的事情 就是所有的deltas都是在0到255之间的，所以你一个值只需要一个字节。这就是lucene使用的科技，用来编码你硬盘上的倒排索引：传入的集合被切 分256个doc IDs的数据块中，然后每个数据块都被分离开使用delta编码和位组装压缩:lucene计算每个数据块存储编码过的deltas时所需要的最大的 位数数值。这种编码技术就是很有名的发表在文献中的 Frame Of Reference (FOR)，并且已经在lucene 4.1上面使用。

这里有一个关于3个数据块的例子（实际使用中是256个)

相同的抽象也被用在搜索的时候：查询和过滤返回了包含了它们匹配的文档集合的有序的迭代器。在使用term查询和过滤的场景，实现很简单，我们只需要 返回从倒排索引中取出投递集合的一个迭代器。其他的查询都更加复杂。举个例子，一个分离termA OR termB的操作，我们需要动态的合并termA和termB 的投递集合。但是最后，它仍然使用这个相同的抽象。

3. Roaring bitmaps

这将引导我们进入第二个，也就是lucene所依赖的编码有序整数集合的地方：过滤器缓存。过滤器缓存是一个很有名的能提升一些经常被用到的过滤器的执行速度 的技术。这是一个简单的缓存，它映射了匹配到的doc IDs的集合对应的（过滤器，存储片段）之间的关系对。但是对于倒排索引来说，这个关联就有所不同了：

• 因为我们仅仅缓存常用的过滤器，压缩率和倒排索引所需要的匹配文档中所有可能的term的需求并不匹配。
• 无论如何，我们需要缓存过滤器来保证比重新执行一次过滤器速度更快一些，所以使用一种好的数据结构很重要。
• 缓存过滤器被存放在内存中，投递集合被典型地存放在磁盘中。

出于这些原因，倒排索引和缓存过滤器并不需要使用相同的编码技术。

所以这里我们应该使用的是什么呢？很清楚也很重要的一点就是让有些东西变得更快：如果你的缓存过滤器比重新执行一次filter查询更慢，这就有点本末倒置了， 因为它既占用了内存又把查询变得更慢了。一个编码越复杂，它就越有可能会拖慢编码和解码，因为这将增加cpu的使用，所以让我们来看看我们能用来编码有序数字集 合的简单选择：

1. 选项一：整型数组

可能也是最简单的选项：把doc IDs存储在数组中。这将使得迭带变得很简单，但是压缩变得很差。这种编码技术一个实体需要4个字节，这将使得稠密的过滤器 (数据比较集中，结果集比较大的)变得非常消耗内存。如果你有一个包括100M文档的存储片段，而且有一个匹配大部分文档的过滤器，缓存这个片段上一个单一的过滤器 需要大概400MB的内存。可见，我们还是需要一个对内存利用更有效的选项来解决稠密结果集的问题。

2. 选项二: bitmap

稠密结果集中的整数集是能在bitmaps中使用的一个很好的案例。一个bitmap就是一个每个实体都只占用一个bit(位)的数组，所以它们只可能有两个值：0或者1。为了 知道一个docID是否包含在bitmap中，你需要去读取bitmap中索引的docID的值。0表示这个集合不包括这个docID，1则表示这个集合包括这个docID。迭代要求去统计 连续0的个数，这实际上是比较快的，因为cpu有专门处理这个操作的指令。如果我们与上面的选项一进行比较，在稠密结果集上的内存使用变得好上很多，因为我们现在只需要 100M 的bits也就是大概12.5MB。但是现在我们有另一个问题，在稀疏结果集上，每次匹配结果我们选项一需要4个字节，但是现在却都需要12.5MB的内存，不管实际匹配 的结果集有多大，都需要这些。

很长一段时间以来，lucene都在使用这样一种bitmaps来在内存中缓存过滤器。在lucene 5开始，我们切换到了Daniel Lemire的roaring bitmaps。可以查看Lucene- 5983(https://issues.apache.org/jira/browse/LUCENE-5983)查看更多的背景信息。

3. 选项三：roaring bitmaps

Roaring bitmaps 的目标是更好地利用好上面的两个选项。开始的时候我们把投递集合按16位的最大值(65536)来切分成数据块。这也就意味着，第一个数据块可以被0到65535之间的 数值编码，第二个数据块编码范围是65536到131071。然后在每个数据块，我们使用16位最小值(16 lowest bits)来进行独立编码：如果它有少于4096个值，就会使用数组，否则的话就使用bitmap。 这个阶段需要注意的很重要的一点是按照上面说的在数组编码中我们之前一个值需要4个字节，这里数组一个值只需要2个字节的存储空间，因为数据块ID(block ID) 隐示地给了我们 16个字节的最高位。

为什么选择4096做为一个临界值呢，仅仅是因为当数据块中的文档数超过这个值之后，bitmap将比数组的内存使用率更高:

这就是让roaring bitmaps变得很有趣的原因：它是基于两个比较快的编码技术，它拥有完全不同的压缩特点并且根据内存利用率动态地决定使用哪个编码技术。

Roaring bit maps拥护很多特点，但是在lucene的上下文中只有两个特点让我们感兴趣：

• 迭代所有匹配的文档。这种的典型的使用场景是你通过cached filter使用constant_score查询。
• skipping:能够从大于或等于某一个整数的位置前进到集合中包含的第一个doc ID。这一点的典型应用是你将一个过滤器插入一个查询中。

4. 压缩

让我们来比较几种DocIdSet的实现来说明为什么我们决定使用roaring bitmaps来处理过滤器缓存。这里是几种我们拿来比较的实现:

• int[] array: 见选项一 ,实现见(https://gist.github.com/jpountz/6c3e7ff25c57a2ca7d52)
• bitmap: 见选项二,实现见lucene的BitDocIdSet以FixedBitSet为基础的
• roaring bitmap: 见上面的选项三，参考lucene的RoaringDocIdSet
• for: 一个以磁盘为基础的投递集合，是lucene在索引的过程中产生的，benchmark时存在于OS的cache中

benchmark的代码在 https://code.google.com/a/apache-extras.org/p/luceneutil/source/browse/src/main/DocIdSetBenchmark.java，有兴趣的可以 去github上找找。

在所有我们呈现出来的图表中，我们先使用bitmap作为参考实现因为它已经被lucene使用了很多年了。y轴使用以2为底的对数：值为0表示它和bitmap速度一样快，1表是快两倍。x 轴使用以10为底的对数，代表稠密的doc id集合。举个例子，-2表示10的-2次方也就是1%的文档被包含在集合中。

迭带性能：

这里我们测量了迭代性能，本质上是关于你把一个filter包装在constant-score query中的性能。数组实现战胜了其他的实现by a factor of 2。更有意思的是bitmap在稀 疏结果集中比其他实现都要慢，这就意味着你不能把它使用在cache filters场景下，因为它需要先从磁盘上读取，这样一来速度会更慢。

Skip performance

这次我们测试skipping，应用于你将一个filter插入到一个查询中。插入的数字就是我们在文档中迭带时需要跳过的（不管有没有匹配）。普遍说来，当插入一个 匹配将近1/N的全部文档的查询时会引起跳过N个文档的情况。

你或者疑惑，不同的实现是怎么有效地做到这个的，下面就是答案：

• “for" encodes skip lists on disk
• bitmaps rely on finding the first bit which is set
• roaring bitmaps are naturally indexed, we first go to the block that contains the target doc ID, and then either perform a binary search if documents are stored in an array or use the same approach as the bitmap otherwise
• the int[] array performs an exponential search

尽管bitmap在稀疏结果集中仍然比其他实现要慢，但是它在稠密结果集中要比其他实现要快。其他实现与bitmap之间的性能对比就是当稠密度增加时，roaring bitmaps拥有最优雅的性能下降。

你或许疑惑为什么在这么高的稠密度上，能观察到roaring bitmaps很微小的跳跃。那是因为roaring bitmap这种实现在数据变得稠密时改变了编码方式：它不保存已经存在于集合中的doc IDs 只保存不存在的。这就使得跳跃变慢了，但是对内存使用是有效的并且对于你拥有几个格式为"all except X"的filter caching时非常有用。

Memory footprint

cached filter使用越少的内存，我们就能缓存更多的filter。这里我们可以看到在大多数情况下roaring bitmap都比int[] array和bitmap表现的要好。唯一的例外是在非常稀疏的情况下(少于0.05%的文档包含在集合中时),这时内存 超出了每个数据块使得roaring bitmaps比简单的数据效率稍微低一些。

int[] array 在稠密数据集中时比roaring bitmaps和bitmap需要大概32倍还要多的内存。

在这次的benchmark中，我们使用的是统一的分布的文档格式。这种格式不会影响int[]和bitmap编码，但是它实际上是对roaring bitmaps的最坏的案例，所以我们可以期望它能够在实际的数据中表现的更好。

备注：“for”没有在这个benchmark中出现是因为它全部是走磁盘的，没有用到过内存。

Build time

一个很重要的因素在filter caching中需要考虑的就是构建这个缓存实体时需要花费的时间。roaring bitmaps被或许是最快的一种实现(当稠密度在0.01%到1%之间时)，或者比较接近最快的实现 （int[] array 中当稠密度<0.01%，和bitmap中当稠密度>1%)

Conclusion

没有一种实现是能持续的比所有其它实现好的。一些实现不合格是因为它们在某些特定场景下表现得很差：

• bitmaps 在稀疏集合中表现很差，这点同时表现在多种性能和内存利用率上
• int[] array 比较快，但是在稠密数据集中会疯狂占用大量内存

尽管roaring bitmaps不是最快的实现，但并不失为一种好的选择。

在对比中另外一个重要的疑问就是尽管从倒排索引中投递集合是保存在磁盘而不是内存中的，它仍然很快。在nextDoc benchmark（在某种程度上这也是一种进步）中展示的是它们甚至与内存实现比也很有竞争力。 这就意味着，filter cache想要提高效率的话只应该在很慢的filter中使用，并且不应该在很快的filters中出现，比如说term filters中。

最后，lucene现在常常给所有的filters使用相同的实现。未来我们应该把它变得更有效，例如，根据需要缓存的doc id集的密度使用不同的实现。