索引压缩算法New PForDelta简介以及使用SIMD技术的优化-阿里云开发者社区

开发者社区> alizhen> 正文

索引压缩算法New PForDelta简介以及使用SIMD技术的优化

简介: New PForDelta算法介绍 倒排索引的数据包括docid, term frequency, term position等,往往会占用很大的磁盘空间,需要进行压缩。压缩算法需要考虑两点:压缩效果和解压缩效率。
+关注继续查看

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压缩后的数据如下图所示:

11

图中第一个位置的“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后的数据如下图所示:

22

可以比较与普通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技术后解压效率有不错的提升,这将在后面介绍的测试效果中体现出来。

33

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

44

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

测试效果

测试1

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

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

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

横坐标:表示用不同framebit压缩的数据(例如5表示此数据用framebit=5的方式压缩了)

纵坐标:表示解压速率,单位MB/s

55

测试2

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

其它指标不变

66

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

结语

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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
《JavaScript启示录》——1.5 使用new操作符实例化构造函数
构造函数从根本上说是用于创建预配置对象的饼干模具模板。以String()为例,这个函数在与new操作符[new String('foo') ]一起使用时会创建基于String()模板的字符串实例。让我们来看一个示例。
1292 0
图像算法的工程优化技术
图像算法的工程优化技术 当一个很酷的图像算法实现之后,我们希望集成到软件中去,这时将会遇到最大的拦路虎:性能。 可以想像一下,如果美图秀秀做一个美颜效果要转圈圈转个30秒,还会有多少人用呢。 学术界喜欢推出复杂度更低的算法,去解决性能问题,而在实际工程应用中,对代码的优化和硬件的良好运用效果来得更快更显著,这里就对不改动算法,纯工程方面做性能优化的技术作一个简介。
1295 0
使用 Date 和 SimpleDateFormat 类表示时间
使用 Date 和 SimpleDateFormat 类表示时间 在程序开发中,经常需要处理日期和时间的相关数据,此时我们可以使用 java.util 包中的 Date 类。这个类最主要的作用就是获取当前时间,我们来看下 Date 类的使用: 使用 Date ...
930 0
神经架构优化(NAO):新的神经架构搜索(NAS)算法
如果你是一名深度学习实践者,你可能发现自己经常会遇到同一个关键问题:我应该为现在的任务选择哪种神经网络架构?
521 0
粒子群优化算法(PSO)之基于离散化的特征选择(FS)(一)
欢迎大家关注我们的网站和系列教程:http://www.tensorflownews.com/,学习更多的机器学习、深度学习的知识! 作者:Geppetto 在机器学习中,离散化(Discretization)和特征选择(Feature Selection,FS)是预处理数据的重要技术,提高了算法在高维数据上的性能。
1132 0
使用Verilog实现FPGA偶数/奇数分频电路设计并使用modelsim仿真
本人地大14级师兄,如果有学弟学妹搜到这个评论一个呗! 一、设计要求 编写VerilogHDL程序,实现如下功能: 输入时钟信号和复位/信号,实现4分频/5分频,占空比为1:1.   二、设计思路 1.偶数分频 假设为N分频,计数到N/2-1时,时钟翻转、计数清零,如此循环就可以得到N(偶)分频   2.奇数分频(占空比为50%) (1)假设为N分频,取一个进行上升沿触发的模N计数,触发时钟翻转后,经过(N-1)/2再次进行翻转,得到一个占空比非50%奇数N频时钟。
1680 0
+关注
4
文章
0
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
文娱运维技术
立即下载
《SaaS模式云原生数据仓库应用场景实践》
立即下载
《看见新力量:二》电子书
立即下载