背景

搜索引擎中，倒排索引是用于实现高效检索的一个核心数据结构。大数据集的倒排索引同样很大，因此产生了倒排索引压缩技术，降低读取索引时的磁盘I/O时间，以及在内存、CPU缓存之间进行数据传输的时间。

倒排索引压缩方面的研究已有接近50年的历史，目前仍然在持续更新，每年都有新算法提出。随着计算机硬件的发展，现在的搜索系统倾向于让索引数据常驻内存，因此索引压缩技术的关注点也在变化，从早期的专注于优化压缩率提升磁盘I/O效率，变为更重视解码效率和查询性能。

在58当前的搜索场景下，索引热数据通常都常驻内存，有可能出现服务器上内存使用比例大幅超过CPU使用比例，因此索引压缩的主要效果在于降低内存占用，平衡资源利用率，避免内存成为资源瓶颈。

本文将简单介绍在面向内存的场景下适用的一些压缩算法，并结合58搜索的场景，重点介绍其中一种算法的原理、实现和优化方法。

倒排索引压缩算法概览

给定一个文档集，其倒排索引表示的是文档集中的每个词到其所出现的文档的集合的映射。为了便于处理，索引中会为每个文档分配一个从0递增的id，因此倒排索引一般包含一个词典，其中每个词对应一个升序排列的文档id数组，我们称其为倒排链（posting list）。这些倒排链一般会占倒排索引的大部分空间，因此倒排索引压缩技术所要解决的问题，可以抽象为如何对有序整数序列进行压缩。

除了优化压缩率以外，压缩技术还要保证压缩后的索引数据能够被高效检索。检索的形式通常为多个词的与、或、非等逻辑关系查询，具体到倒排索引这一层，则表现为多个倒排链之间的交集、并集、差集运算。在58搜索场景下，最常见的是交集运算。在交集运算中，倒排链需要支持的基本操作，是给定一个文档id，查找它在这个倒排链中的位置。

基于上一节所述的场景，我们调研了业界多种压缩算法，下面将介绍其中一些典型算法，例如常见的PForDelta[1]及其衍生的算法如NewPFD[2]，OptPFD[3]等，然后是较新的一些算法，如获得SIGIR会议2014年最佳论文的PEF（Partitioned Elias-Fano）[4]，以及2017年提出的MILC[5]。

PForDelta

PForDelta算法是2005年提出的算法，压缩方法主要包括分块、差分编码和异常值处理。

它的基本思想是把倒排链分为多个块（chunk），例如每128个id分为一个块，然后对块进行压缩。

为了压缩块内每个元素的空间，可以利用id升序排列的特性，只存相邻id的差值（即delta）。例如原始chunk为{10023, 10102, 10123, 10192, 10197, 10212}，则每个id需要 14 bit。如果只存储差值，那么除了第一个id以外，其余元素可存储为{79, 21, 69, 5, 15}，每个元素只需要 7 bit。

由于块内差值都用固定位宽存储，且id分布一般不均匀，一旦出现少量非常大的差值，会导致块内所有差值的位宽都增大。对于这类异常值，PForDelta进行了单独存储，使得其余较小的值可以用较少的位宽存储。

在PForDelta之后提出的NewPFD和OptPFD在异常值存储等方面进行了优化，提高了压缩率。

差分编码方式决定了PForDelta的解码效率较低，解码块中的一个元素，需要遍历它前面的所有元素进行累加，此外还有对异常值的额外处理。经过实测，基于PForDelta压缩的倒排的集合运算耗时比未压缩版本高了大约一倍。

PEF: Partitioned Elias-Fano

PEF算法是一种压缩率和查询性能两方面表现都比较好的算法，根据其实验结果，压缩率和交集运算效率都优于OptPFD。

它是基于1974年出现的Elias-Fano编码做出的改进。EF编码将每个元素分为高位和低位，根据高位把元素划分到不同的桶中，然后把每个桶的元素个数以 unary code 的形式存储在一起，接着把所有元素的低位按顺序存储。在EF编码的chunk中查找一个key时，先从unary code中定位到它所在的桶（使用位运算技巧可以达到O(1)时间复杂度），然后在桶内线性查找，根据低位确定是哪个元素。

EF编码的空间使用率与PForDelta等成熟编码相当，随机访问和查找性能也好，只是不能充分利用倒排链的局部聚集性。PEF提出了两种分块算法优化了这一点，显著地提高了压缩率。论文作者提供了此算法的开源实现 (https://github.com/ot/partitioned_elias_fano)，同时也有slide可供参考[7]。

经过我们实测，PEF的查询耗时比未压缩索引高了约36%，同时倒排链空间能降低大约65%。

MILC: Inverted List Compression in Memory

MILC是一种注重查询性能的压缩算法。它的结构类似于PForDelta，也会将倒排表进行分块，但每个块内并未使用差分编码，而使用了offset-based编码，因此能在解码时提供很好的随机访问效率。它提高压缩率的主要手段在于分块算法和二级分块的设计。

在论文给出的实验结果中，它的解码效率与未压缩的倒排表几乎相同，压缩率优于PForDelta，略弱于PEF。下一节将展开介绍它的具体原理。

58有很多种搜索业务，对查询响应时间的要求不尽相同，例如58主站搜索性能要求较高，我们希望压缩后的索引，其查询性能不低于压缩前的索引，因此需要选择解码效率高的压缩算法，为此可以接受较差的压缩率，因此MILC是比较合适的选择。而对于一部分流量较低或延迟不敏感的搜索应用，我们选择使用压缩率和解码效率较均衡的压缩算法，例如PEF。

MILC算法原理

MILC的基本存储结构与PForDelta等类似，先分块后编码，但分块和编码方式有所不同。

每一块的块首元素存入元数据块中（Metadata block），而块中的剩余元素以自身减去块首元素值所得差值的形式存储于数据块（Data block）中，每个差值以相同位宽存储。MILC将这种编码方式称为offset-based编码。

例如对于倒排表 L = {120, 200, 270, 420, 820, 860, 1060, 1160, 1220, 1340, 1800, 1980, 2160, 2400}，按每个数据块4个元素的方式分块，并把编码后的数据存储在32位整数数组中，将得到图1所示的结果。

分块后，块内位宽的计算方式：假设块首元素为β，数据块大小为m，其中元素序列为{a0, …, am-1}，则差值位宽基于最大差值即 am-1 来计算，需要 b = ?log(am-1 - β + 1)? 个bit。

数据块中的元素个数以及差值位宽信息也需要存储在元数据块中。

以上介绍了基本的编码方法，接下来介绍解码方法。对于交集运算，倒排表需要支持的基本操作是对于给定的一个doc id，在表中查找其位置。

假设要查找的值为e，查找步骤为：

1，在跳表（即元数据块）中进行二分查找，定位 e 所在的数据块。

2，在数据块中以（e - β）作为key进行二分查找。查找过程中需要通过若干位运算从数组中解码差值。

例如解码图1中的第一个差值，假设数组为A，由于位宽是10，解码方式为A[0] & 0x03FF；第四个差值横跨A[0]和A[1]，解码方式为(A[0]>>30) | ((A[1] & 0x00FF) << 2)。

步骤2体现了MILC与PForDelta的明显差异。PForDelta解码时必须从前向后遍历目标元素之前的每一个差值，逐个累加后才能完成解码，而MILC中解码任意差值时不依赖于前面的差值，所以MILC能够支持块内的随机访问，从而可以使用二分查找算法。但其缺点是，相较于PForDelta的delta-based编码（使用相邻元素之间的差值），这样计算出的差值会比较大，占用更多位宽。

为了进一步优化压缩率，MILC引入了动态分块和二级分块。

由于倒排表中元素值分布不均，定长分块可能导致某些块内差值较大。通过动态分块方法，可以将数值较接近的元素尽可能分到一个块中，让差值变小。

例如图2，如果按固定128元素的分块方式，block 0位宽为?log(600 - 4 + 1)?=10，block 1位宽为?log(900 - 605 + 1)?=9，整体所需空间为10*128+9*128=2432 bit。

改为动态分块之后，block 0位宽为?log(120 - 4 + 1)?=7，block 1位宽为?log(900 - 500 + 1)?=9，整体所需空间为7*108+9*148=2088 bit [5]。

设计动态分块算法时需要在块数与位宽之间权衡。块越小，差值位宽越小，但块数也会越多，跳表也会随之线性增大。论文中证明了如果跳表里面每项元数据的大小为?，则每个块的元素个数最多为2?，高于这个值空间效率会降低。MILC的元数据大小为80bit，因此在动态分块时，块最大为160。

MILC基于动态规划思想给出了分块算法，使用一个辅助数组记录倒排表每个位置上的当前最优分块策略，遍历每个doc id，对每个doc id计算160种分块代价并择优记忆，遍历完成后回溯一遍即得到最优分块方式，时间复杂度O(n)。

二级分块：对已经分好的块中的差值序列还可以再次划分，整体结构与第一级分块类似，也分为跳表和数据块，在细节上会进行简化，这里不再详述。

以上就是MILC的核心编码方法。除此之外，论文中还讨论了针对CPU Cache和SIMD指令的一些优化思路，有兴趣的读者可以进一步阅读原文。

MILC算法实践与优化

在58搜索应用该算法的初期，首先实现的是MILC算法的一个简化版，支持动态分块，不支持二级分块。在随后的的性能测试中，发现查询性能与未压缩倒排表相比有较大差距。

由于性能不符合预期，二级分块功能并未继续实现，以免进一步增加解码代价。我们转而在简化版基础上进行查询性能优化。

通过性能分析可发现，块内元素的解码是较为耗时的操作，相比于未压缩版本只需一个指令即可读取doc id，压缩版本需要使用多个位运算指令（位移，按位与等）来解码。通过算法分析还发现，跳表查找的算法也有优化空间。下面介绍一下具体的优化方式。

首先是对块内解码的优化：块内差值改为使用8、16或32bit整数来存储，这不仅避免了位运算解码的代价，也为应用SIMD指令集提供了可能性。

块内元素的查找，原编码方式只适合使用二分查找，现在可以使用SIMD指令进行向量化线性查找，虽然线性查找的平均时间复杂度不如二分查找，但块中元素个数通常很少，并且使用几个SIMD指令就可以一次性比较多个元素，比如8bit差值的块，使用SSE4指令集可以一次性比较16个元素，所以线性查找平均效率会比二分查找更高。

其次是对跳表查找算法的优化。论文中跳表查找使用了二分查找算法。考虑到在两个倒排表进行交集运算的过程中，二分查找的结果较大概率会落在查找区间靠前的位置，因此使用Galloping Search[6]效率会更高。

Galloping Search从区间起点以指数级增长的步长逐步向后探测，当探测到大于等于search key的元素时，以此为区间终点，进行二分查找。对于search key靠近区间前部的情况，探测次数加上二分查找次数之和，比在完整区间中作二分查找的次数会少很多。

经过以上优化后，交集运算的查询平均耗时甚至比未压缩版本降了几个百分点，压缩率则难免比原版MILC算法差一些。

需注意的是，以上优化仅对交集运算有效。对于纯并集运算，必须遍历倒排表的每一个元素，计算效率必然低于未压缩版本。在58常见的搜索场景下，绝大部分查询为交集运算，因此最终整体的查询效率与未压缩版本持平。

该算法最终应用在58主站搜索后，在不改变查询性能的前提下，减少了大约35%的倒排链数据。

总结

综上，本文介绍了近年来的几种典型倒排索引压缩方案，根据需求场景的不同，这些压缩方案在压缩率和解码效率上的取舍也不一样。然后具体介绍了MILC算法，以及我们针对58搜索的高查询性能场景所进行的优化，使其查询性能与未压缩索引对齐。

除了本文所述的方案以外，倒排还有许多其他的存储形式，例如各种形式的bitmap。而索引压缩也不限于倒排链的压缩，还包括倒排term词典的压缩、正排索引的压缩等，希望以后可以继续探讨。

参考：

[1] M. Zukowski, S. Heman, N. Nes, and P. Boncz. Super-scalar ram-cpu cache compression. In ICDE, 2006.

[2] J. Zhang, X. Long, and T. Suel. Performance of compressed inverted list caching in search engines. In WWW, pages 387–396, 2008.

[3] H. Yan, S. Ding, and T. Suel. Inverted index compression and query processing with optimized document ordering. In WWW, pages 401–410, 2009.

[4] G. Ottaviano and R. Venturini. Partitioned elias-fano indexes. In SIGIR, pages 273–282, 2014.

[5] J. Wang, C. Lin, et al. MILC: Inverted List Compression in Memory.

[6] https://en.wikipedia.org/wiki/Exponential_search

[7] http://www.di.unipi.it/~ottavian/files/partitioned_elias_fano_sigir14.pptx

欢迎大家关注“58架构师”微信公众号，定期分享云计算、AI、区块链、大数据、搜索、推荐、存储、中间件、移动、前端、运维等方面的前沿技术和实践经验。