Fork me on GitHub

Lucene 源码系列——LZ4

原文地址:https://www.amazingkoala.com.cn/Lucene/yasuocunchu/2019/0226/37.html

LZ4 是一种无损数据压缩算法,着重于压缩和解压的速度,并且应用广泛。在 Hadoop、Linux 内核、文件系统都有应用,而在 Lucene 中,则是使用 LZ4 对倒排表的数据以及词向量(termVector)进行压缩存储。在本篇文章中,介绍 LZ4Fast 的压缩逻辑在 Lucene 中的 Java 实现。

两种实现

Lucene 中提供了两种 LZ4 的算法实现,分别是 LZ4Fast 跟 LZ4High:

LZ4Fast

本文介绍的就是 LZ4Fast,它是原生的 LZ4 算法的实现,性能跟内存开销小于 LZ4High,最多使用 16KB 的内存。

LZ4High

LZ4High 相比较 LZ4Fast,它的压缩速度较慢,并且占用更多的内存(每个线程占用~256KB),但是它提供了更高的压缩比,处理很大的数据时更能体现压缩比的优势。可能会随后的博客中更新:)。

流程简介

压缩过程分为两步

步骤一:计算 hash,找到相同的数据区间
步骤二:将相同的数据区间进行压缩存储

例子

我们通过一个例子,来介绍 LZ4Fast 的压缩的实现:
图 1:
1.png
图 2:
2.png

找到第一个锚点(anchor)

刚开始处理时,下标值为 0 的地方为第一个锚点

找到第二个锚点(anchor)

第一个锚点的值为 0,我们最终目的是获得第二个锚点的值,第二个锚点跟第一个锚点之间的数据进行压缩处理。在这个区间的数据,有两个子区间的数据是一样的,那么需要对这两个子区间进行压缩存储。由于注意的是,两个字区间可能有重叠部分。

处理下标值为 0 的数组元素

图 3:
3.png

encodeArray[] 数组是经过压缩处理的数组。
取出下标值为 0 以及后面的三个数组元素,4 个字节组成一个 int 类型的数值,对这个数值进行散列,如果发生冲突,说明可能之前散列过相同的值,由于这里是第一个数据,所以不会发生这种情况。

处理下标值为 1 的数组元素

图 4:
4.png

同上一步操作,类似滑动窗口的操作,窗口大小为 4 个字节,每一次右移一个字节,然后我们计算下标值 1~下标值 4 的数组元素组成的 int 值,同样进行散列。

处理下标值为 2、3、4 的数组元素

同样的,还是没有发生 hash 冲突。

处理下标值为 5 的数组元素

图 5:
5.png

此时发生冲突,由于不同的值可能会有相同的 hash 值,所以这里还要继续判断下标值 03 的数组元素对应的 int 值是否跟下标值 58 的数组元素对应的 int 值是否一样。在这里,的确这两个区间 R1、R2 的数据是一模一样的,那么需要开始进行压缩存储。

找出相同数据的最大区间

目前我们找到了 数组中下标值 03 跟 58 两个相同的区间 R1、R2,接着扩大这两个区间,直到满足两个区间数据相同,且是最大的区间。
图 6:
6.png

注意的是,这里两个区间有重叠的区域,即下标值 5~9 的区域。

计算 token 值

matchOff:

该值是相同数据区间R2的第一个元素的下标值,即5。

literalLen:

由于直到matchOff位置才开始有相同的数据区间,所以anchor(当前值0)至matchOff的区间的数据需要原封不动的写入到encodeArray[]数组中,而literalLen代表了这段数据的长度。matchOff与anchor的差值就是literalLen,即 literalLen = matchOff- anchor,当前锚点anchor的值Wie0,所以literalLen的值为5。

matchLen:

matchLen描述了两个相同区间R1跟R2相同数据的个数,即 10。

token 值是 literalLen 跟 matchLen 的组合值,利用组合存储

final int token = (Math.min(literalLen, 0x0F) << 4) | Math.min(matchLen - 4, 0x0F);
当前的literalLen跟matchLen-4的值没有大于0x0F,所以token = (5 << 4) | (10 - 4), 即 86,二进制就是0b01010110。后面的处理过程中会有literalLen跟matchLen-4的值大于0x0F的情况。

matchDec:

matchDec是R2跟R1的两个区间第一个元素所在下标值的差值,即 5 - 0 = 5。这个值在解压的时候会作为遍历的一个条件。由于matchDec是个int类型,并且这个值不会大于(1 << 16),所以需要两个字节分别存储低8位跟高8位在解压时,根据matchDec跟matchLen的大小,恢复数据的过程略有不同,后面会介绍。
写入 token 值、anchor 至 matchOff 的数据、matchDec

图 7:
7.png

上图中 原始数据即 anchor 至 matchOff 之间的数据。

找到第三个锚点(anchor)

上面的流程结束后,更新第二个锚点的值为 15。按照同样的逻辑找到第三个锚点。

处理下标值为 15~41 的数组元素

都没有发生 hash 冲突的情况。

处理下标值为 42 的数组元素

图 8:
8.png

此时发生冲突,由于不同的值可能会有相同的 hash 值,所以这里还要继续判断下标值 14 的数组元素对应的 int 值是否跟下标值 4245 的数组元素对应的 int 值是否一样。在这里,的确这两个区间 R1、R2 的数据是一模一样的,那么需要开始进行压缩存储。

找出相同数据的最大区间

然后下标值 5 跟下表值 46 的数组元素就不相同了,所以相同数据的最大区间如下图的 R1 跟 R2
图 9:
9.png

计算 token 值

matchOff:

该值是相同数据区间R2的第一个元素的下标值,即42。

literalLen:

由于直到matchOff位置才开始有相同的数据区间,所以anchor(当前值15)至matchOff的区间的数据需要原封不动的写入到encodeArray[]数组中,而literalLen代表了这段数据的长度。matchOff与anchor的差值就是literalLen,即 literalLen = matchOff- anchor,当前锚点anchor的值为15,所以literalLen的值为27。

matchLen:

matchLen描述了两个相同区间R1跟R2相同数据的个数,即 4。

token 值是 literalLen 跟 matchLen 的组合值,利用组合存储

final int token = (Math.min(literalLen, 0x0F) << 4) | Math.min(matchLen - 4, 0x0F);

当前的literalLen大于0x0F ,所以token = (15 << 4) | (4 - 4), 即 240,二进制就是0b11110000。

matchDec:

matchDec是R2跟R1的两个区间第一个元素所在下标值的差值,即 42 - 1 = 41。这个值在解压的时候会作为遍历的一个条件。由于matchDec是个int类型,并且这个值不会大于(1 << 16),所以需要两个字节分别存储低8位跟高8位在解压时,根据matchDec跟matchLen的大小,恢复数据的过程略有不同,后面会介绍。

写入 token 值、anchor 至 matchOff 的数据、matchDec

图 10:
10.png

注意 encodeArray[]数组中下标值为 9 的数组元素,由于 token 值只有高 4 位用来表示原始数据的长度,即最大值为 15,所以 literalLen 的值超出的部分需要额外的一个字节存储,当前 literalLen 的值为 27,所以额外的值为 27 - 15 = 12。

找到第四个锚点(anchor)

上面的流程结束后,更新第三个锚点的值为 46。按照同样的逻辑找到第四个锚点

处理下标值为 46 的数组元素

图 11:
11.png

找出相同数据的最大区间

图 12:
12.png

计算 token 值

matchOff:

该值是相同数据区间R2的第一个元素的下标值,即46。

literalLen:

由于直到matchOff位置才开始有相同的数据区间,所以anchor(当前值46)至matchOff的区间的数据需要原封不动的写入到encodeArray[]数组中,而literalLen代表了这段数据的长度。matchOff与anchor的差值就是literalLen,即 literalLen = matchOff- anchor,当前锚点anchor的值为46,所以literalLen的值为0。说明不用写原始数据到encodeArray[]数组中

matchLen:

matchLen描述了两个相同区间R1跟R2相同数据的个数,即 22。

token 值是 literalLen 跟 matchLen 的组合值,利用组合存储

final int token = (Math.min(literalLen, 0x0F) << 4) | Math.min(matchLen - 4, 0x0F);

当前的matchLen为22,大于0x0F ,所以token = (0 << 4) | 15, 即 15,二进制就是0b00001111。matchLen多出来的部分需要再用一个字节存储。

matchDec:

matchDec是R2跟R1的两个区间第一个元素所在下标值的差值,即 46 - 15 = 31。这个值在解压的时候会作为遍历的一个条件。由于matchDec是个int类型,并且这个值不会大于(1 << 16),所以需要两个字节分别存储低8位跟高8位在解压时,根据matchDec跟matchLen的大小,恢复数据的过程略有不同,后面会介绍。

图 13:
13.png

注意 encodeArray[]数组中下标值为 42 的数组元素,由于 token 值只有低 4 位用来表示原始数据 matchLen 的长度,即最大值为 15,所以 matchLen 的值超出的部分需要额外的一个字节存储,当前 matchLen 的值为 22,所以额外的值为 22 - 15 - 4 = 3。
另外 literalLen 的值为 0,说明这个区间内的数据已经存储过了。

最后 5 个字节的处理

最后 5 个字节在上面的流程中不会被处理,LZ4Fast 算法会对最后 5 个字节单独处理。上面的流程结束后,更新第三个锚点的值为 68。同样需要存储 token,不过 token 的值的计算方式为

final int token = Math.min(literalLen, 0x0F) << 4;

计算 token 值

还有最后 5 个字节,所以 literalLen 的值为 5,所以 token 的值为 (5 << 4)= 80。

写入 token 值、最后 5 个字节的原始数据

图 14:

至此,array[]数组压缩成 encodeArray[]数组的过程结束。

压缩后的数据结构如下:

图 15:
15.png

结语

本文通过一个例子实现了 LZ4Fast 的压缩过程,由于篇幅原因上文中如何计算 hash 的过程并没有给出,并且没有理解源码中提供的 hash 函数的含义,以及为什么要留最后的 5 个字节单独处理。在随后的博客中,会介绍解压过程。


本文地址:https://www.6aiq.com/article/1586653402909
本文版权归作者和AIQ共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出