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：
图 2：
找到第一个锚点（anchor）
刚开始处理时，下标值为 0 的地方为第一个锚点
找到第二个锚点（anchor）
第一个锚点的值为 0，我们最终目的是获得第二个锚点的值，第二个锚点跟第一个锚点之间的数据进行压缩处理。在这个区间的数据，有两个子区间的数据是一样的，那么需要对这两个子区间进行压缩存储。由于注意的是，两个字区间可能有重叠部分。
处理下标值为 0 的数组元素
图 3：
encodeArray[] 数组是经过压缩处理的数组。
取出下标值为 0 以及后面的三个数组元素，4 个字节组成一个 int 类型的数值，对这个数值进行散列，如果发生冲突，说明可能之前散列过相同的值，由于这里是第一个数据，所以不会发生这种情况。
处理下标值为 1 的数组元素
图 4：
同上一步操作，类似滑动窗口的操作，窗口大小为 4 个字节，每一次右移一个字节，然后我们计算下标值 1~下标值 4 的数组元素组成的 int 值，同样进行散列。
处理下标值为 2、3、4 的数组元素
同样的，还是没有发生 hash 冲突。
处理下标值为 5 的数组元素
图 5：
此时发生冲突，由于不同的值可能会有相同的 hash 值，所以这里还要继续判断下标值 03 的数组元素对应的 int 值是否跟下标值 58 的数组元素对应的 int 值是否一样。在这里，的确这两个区间 R1、R2 的数据是一模一样的，那么需要开始进行压缩存储。
找出相同数据的最大区间
目前我们找到了 数组中下标值 03 跟 58 两个相同的区间 R1、R2，接着扩大这两个区间，直到满足两个区间数据相同，且是最大的区间。
图 6：
注意的是，这里两个区间有重叠的区域，即下标值 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：
上图中 原始数据即 anchor 至 matchOff 之间的数据。
找到第三个锚点（anchor）
上面的流程结束后，更新第二个锚点的值为 15。按照同样的逻辑找到第三个锚点。
处理下标值为 15~41 的数组元素
都没有发生 hash 冲突的情况。
处理下标值为 42 的数组元素
图 8：
此时发生冲突，由于不同的值可能会有相同的 hash 值，所以这里还要继续判断下标值 14 的数组元素对应的 int 值是否跟下标值 4245 的数组元素对应的 int 值是否一样。在这里，的确这两个区间 R1、R2 的数据是一模一样的，那么需要开始进行压缩存储。
找出相同数据的最大区间
然后下标值 5 跟下表值 46 的数组元素就不相同了，所以相同数据的最大区间如下图的 R1 跟 R2
图 9：
计算 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：
注意 encodeArray[]数组中下标值为 9 的数组元素，由于 token 值只有高 4 位用来表示原始数据的长度，即最大值为 15，所以 literalLen 的值超出的部分需要额外的一个字节存储，当前 literalLen 的值为 27，所以额外的值为 27 - 15 = 12。
找到第四个锚点（anchor）
上面的流程结束后，更新第三个锚点的值为 46。按照同样的逻辑找到第四个锚点
处理下标值为 46 的数组元素
图 11：
找出相同数据的最大区间
图 12：
计算 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：
注意 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：
结语
本文通过一个例子实现了 LZ4Fast 的压缩过程，由于篇幅原因上文中如何计算 hash 的过程并没有给出，并且没有理解源码中提供的 hash 函数的含义，以及为什么要留最后的 5 个字节单独处理。在随后的博客中，会介绍解压过程。
