written by 普队

New PForDelta算法介绍

倒排索引的数据包括docid, term frequency, term position等，往往会占用很大的磁盘空间，需要进行压缩。压缩算法需要考虑两点：压缩效果和解压缩效率。一般来说，提升解压缩效率，减少用户查询的响应时间更加重要。PForDelta算法以及它的改进版本New PForDelta算法在拥有不错压缩率的情况下解压缩性能也十分优秀。

PForDelta算法

算法的第一步是要进行Delta Encoding操作，对于一组按照顺序从小到大排列的数据，不需要保存每个元素的值，只需要保存相邻元素的差值即可。例如存储docid时就需要这么做，而对于不是递增排列的TF和TP，则没有这个操作，此时仅被称为PFor算法。

完成Delta Encoding后得到的数据会被拆分成多个block，每个block存储固定个数的数据（例如128个），算法会分别对每个block独立的压缩和解压。这样做除了可以利用数据的局部性特征，对不同部分采用不同的压缩策略外，还可以在解压缩时只选择解压部分block，不需要针对整个文件，例如查询某一term的position时只解压其所在block。

PForDelta算法的基础思想是对于一个block，认为其中大部分数据只需要较小的空间就可以存储下来，而剩下的部分被当做异常数据处理。一般通过设定一个值framebit，使得超过90%的数据都可以直接由framebit位存储下来，称为正常部分，剩下的小于10%的数据单独存储，称为异常部分。

比如一组数据如下：10, 34, 69, 77, 126, 137, 150, 179, 278, 279, ……..，在Delta Encoding后得到数据10, 24, 35, 8, 49, 11, 13, 29, 99, 1, …….，设定framebit = 5，那么小于32的数据都可以直接存下，大于等于32的有35, 49, 99需要单独存储。使用PForDelta压缩后的数据如下图所示：

图中第一个位置的“2”表示与第一个异常值的位置是2，往后数间隔2个可以找到第一个异常值的位置，可以通过异常部分知道这个异常值是35，然后根据这个位置的“1”又可以往后数间隔1个找到下一个异常值的位置，这个异常值是49，以此类推可以继续找下去。异常部分的存储是倒序的，这样做是为了在解压缩的时候更方便的把异常值填进去。

解压的过程就是先把正常部分每5位提取出来，然后按前面所说将异常值的位置找出来并且根据异常部分填入异常值。

除了存储数据外，整个数据还需要一个头信息，用于记录framebit的取值以及压缩后的长度等。

PForDelta算法会存在一个问题：异常数据的间隔可能超过framebit位能存储的最大值，例如framebit=5时异常值的间隔超过了31。一个可行的解决方法是将某些原来不是异常值的数据当成异常值处理，从而减小异常值的间隔，但是这样也造成了不必要的浪费。

New PForDelta算法

针对上面提到的问题，改进后的PForDelta算法的思路是：以128个数据为block大小时，异常值的间隔不会很大，可以把它们单独拿出来存储，而原来存储这些间隔大小的位置就用来存储异常值的低位，异常值的高位则和间隔一起存储在异常部分。

继续以上面Delta Encoding后的数据为例：10, 24, 35, 8, 49, 11, 13, 29, 99, 1, …….，设定framebit = 5。使用New PForDelta后的数据如下图所示：

可以比较与普通PForDelta的不同：正常部分开头存储的第一个异常值的位置没有了；圆圈内原来存储的是异常值的间隔，现在变成了35, 49, 99二进制形式下的低5位；异常部分存储的是第一个异常值35的位置“2”以及它除去低5位后的高位，异常值49与上一个异常值的间隔“1”以及它的高位，异常值99与上一个异常值的间隔“3”以及它的高位等等。

解压缩时首先将前面每5个bit存储的数据解压出来，然后处理异常部分：读到“2”，于是将“0000001”拼接到第2个位置“00011”之前得到35；读到“1”，将”00000001”拼接到第4个位置”10001”之前得到49；读到”3”，将“0000003”拼接到第8个位置”00011”之前得到99。（假设下标从0开始）

异常部分每个值的大小一般不会很大，可以用别的压缩算法继续压缩，例如indexlib中采用了s9算法（这里只是简单介绍一下）：对每一个4字节32bit，选定一个提前规定的9种bit_length中的一种，例如选为7，且它对应的code_num为4，意思是接下来的4个数据都能用7bit的方式存储在这4个字节中，应当保证bit_length选的尽量小使得可以存储尽量多的数据。预先取定的9种bit_length保证它乘上对应的code_num不超过28，这样留下4bit的空间用于存储采用了第几种bit_length。

New PForDelta算法的优势与实现

算法的性能好坏与它的实现密切相关，原因是它的设计原则要求它CPU流水线友好，从而达到压缩率好的情况下解压效率也很优秀的目标。

因此实现时需要做到：对每个framebit分别实现函数；采用循环展开的优化方法；减少或避免分支结构出现。这些策略都是为了尽量保证流水线的通畅性。

使用SIMD技术

SIMD全称Single Instruction Multiple Data，单指令多数据流，通俗的说是指这样的指令集：收集多个操作数，将它们放入128位、256位甚至更多位的寄存器中（这个过程的访存操作也是并行的），同时（并行）对它们执行相同的操作。索引压缩算法看重压缩率和解压效率，New PForDelta算法解压时的指令序列契合SIMD技术对多个操作数执行相同操作的理念，因此可以使用SIMD技术来优化它。

New PForDelta算法解压时分为正常部分和异常部分的解压。异常部分需要将异常数据的高位依据间隔补到正常部分解压出来的数组中，不能使用SIMD指令，而正常部分只是将一系列按相同的framebit位存储的数据顺序提取到数组中，完全可以使用SIMD指令，因此我们只针对正常部分进行优化，优化的指令集是128位的sse4指令集（在编译时使用avx2编译选项，线上机器也支持avx2）。

来看一个简单的例子：framebit取8，解压时原来的实现方法是将一个int（4字节）中每8位用位运算取出分到数组中，解压16个数据则需要对4个int执行上述操作，采用sse4指令后只需将128位并行存入寄存器，然后并行的将它们分到数组的16个单元中。可以发现优化后的指令条数相比原来少了很多，但是流水线的流畅性就没有原来那么好了。另外，对于不规则的framebit（意思是有很多数据存储时横跨两个字节或者两个int），sse4指令需要添加一些额外的操作，超过原来解压方法所付出的代价。但是总体上来说，指令数目的减少弥补了流水线的问题，使用SIMD技术后解压效率有不错的提升，这将在后面介绍的测试效果中体现出来。

上图为原来解压的操作顺序，其中每个int的低位在左边。

上图为优化后解压的操作顺序，相同的标号代表并行执行。

测试效果

测试1

测试数据：没有异常值的随机数据

测试机器：CPU版本为v4的线上机器

蓝色和橙色：对应原始解压方法和新型解压方法

横坐标：表示用不同framebit压缩的数据（例如5表示此数据用framebit=5的方式压缩了）

纵坐标：表示解压速率，单位MB/s

测试2

测试数据：有接近10%异常值的随机数据

其它指标不变

可以发现，平均情况下解压速率提升了10%左右。framebit=6的异常是由于原先特别针对此情况采用了复杂的SIMD技术优化（汇编代码形式），framebit=15的异常原因主要是此种情况下sse指令特别复杂（每15位填充需要32个数据才能填满整int，因此需要很多额外的指令处理数据）。提升效果没有预想中的明显，可见New PForDelta算法流水线友好的设计初衷得到了体现。

结语

本文只讨论单纯使用SIMD技术对New PForDelta算法的提升作用，另一个优化思路是从索引结构上进行考虑，包括PForDelta和New PForDelta在不同场景下的对比、异常部分的压缩策略（例如是否采用s9）等。另外，压缩率和解压效率的平衡也是一个重要的课题。