lucene源代码学习之LZ4压缩算法在lucene中应用

怼烎@ 2022-01-15 15:17 799阅读 0赞

LZ4算法又称为Realtime Compression Algorithm，在操作系统(linux/freeBSD)、文件系统(OpenZFS)、大数据(Hadoop)、搜索引擎(Lucene/solr)、数据库(Hbase)……都可以看到它的身影，可以说是一个非常通用的算法。LZ4最突出的地方在于它的压缩/解压速度。

![wKiom1PXOEqwcBhjAAEvAEaL\_6Q857.jpg][wKiom1PXOEqwcBhjAAEvAEaL_6Q857.jpg]

# 基础知识 #

理解Lucene中LZ4算法的实现，需要有以下两点基础知识：

1、理解Lucene里面的packedInts.

关于PacedInts，可以参考http://sbp810050504.blog.51cto.com/2799422/1531624

2、理解素数乘法Hash

在LZ4中，用到了魔数2654435761L，这个数是2到2^32间黄金分割的素数，

2654435761 / 4294967296 = 0.618033987

2654435761L用 signed int表示就是\-1640531535.

所以LZ4的Hash函数如下：

![wKioL1PXOW\_SDdKkAABuUUOek4E194.jpg][wKioL1PXOW_SDdKkAABuUUOek4E194.jpg]

关于LZ4的Hash函数，这个方法我不太理解，贴出来，如果有了解朋友，希望不吝赐教。org.apache.lucene.codecs.compressing.LZ4.HashTable

![wKioL1PXOXrAyJBbAAJX9k\_UJhM527.jpg][wKioL1PXOXrAyJBbAAJX9k_UJhM527.jpg]

# LZ4核心 #

LZ4算法的格式很简单：

![wKioL1PXOYigGGu7AADdwq3aUy0282.jpg][]

Token用来控制上图中LiteralLength和MatchLength的部分。一个Token的8个字节被分为两个部分，高4位表示Literal Length(原文长度)，我们知道4bits最大只能存15，如果长度等于15，那么就需要用到Literal length(optional)部分了。同理，低4位表示Math Length(匹配长度)，如果匹配长度等于15，则会用到Math length (optional) 。Literals表示原文。Offset表示文本处理过程中匹配部分相对当前位置的偏移。

LZ4算法还有一些特定的规则：

1、被压缩文本的最后5个byte只能用原文表示。

2、最后一次匹配的开始位置到文本末尾不能少于12个byte。

3、如果被压缩文本的长度小于13个byte,那么用原文表示会更节省空间。

# 编码过程 #

下面以一个样例来解释Lucene中LZ4

假如我们把符串aaaaabaaaaacaaaaa用LZ4来压缩。压缩的代码如下：

![wKioL1PXOZuz8Px8AAMQ5mZQqtQ943.jpg][]

整个压缩过程中，核心的代码在LZ4.java中：

![wKiom1PXOJKCgP8bAAEWrdf9Rd0583.jpg][]

方法名中的参数解释如下：压缩bytes\[off:off+len\]到out中，最多会使用16KB的内存<这句没有理解>。Hash表ht不是线程安全的，但是可以安全地重用。

压缩的过程如下：

![wKioL1PXOdKh10tsAAE3RqKUJwI823.jpg][]

1、读取4个字节，表示成一个int

(**final****int** v = *readInt*(bytes, off);)

2、用Hash表得到其Hash值。

(**final****int** h = *hash*(v, hashLog);)

3、记录上次映射到此Hash值在bytes数组中的位置

(ref = base + (**int**) hashTable.get(h);)

4、把当前的Hash值及此值在bytes数组中的位置记录到Hash表中

(hashTable.set(h, off - base);)

5、如果hash的位置发生了冲突，并且匹配成功，那么就表示找到一个可压缩的数据段了，而且这个匹配最小有4个字节(int=4bytes)；否则窗口向前移动一个字节，回到第1步。

由于匹配是4个字节大小的窗口，所以如果匹配成功，那么就扩展当前匹配的成果。其代码在：LZ4.java的第241行：

// compute match length

**final****int**matchLen = *MIN\_MATCH* \+ *commonBytes*(bytes, ref + *MIN\_MATCH*, off + *MIN\_MATCH*, limit);

我们关注这个commonBytes函数：

![wKiom1PXOMfj8jqtAADGq2FKWbs019.jpg][]

跟踪一下就会发现其实就是在匹配的基础上往后探路，找到最大匹配。

如果找到了可压缩片断,则按照上图的格式进行编码:

![wKioL1PXOe\_hy2gxAABfqOhntak539.jpg][wKioL1PXOe_hy2gxAABfqOhntak539.jpg]

重复这一过程,直到最后把文本末尾的片断进行编码:

![wKioL1PXOg6zDMghAACiczlCa3Y704.jpg][]

# 解码过程 #

压缩的结果是 \[ 16, 97, 1, 0, 16, 98, 5, 0, 112, 97, 99, 97, 97, 97, 97, 97\] 这个编码包含三个部分:\[ 16, 97, 1, 0\] \[ 16, 98, 5, 0\] \[ 112, 97, 99, 97, 97, 97, 97, 97\] 我们来根据编码的规则,一一解析。即解码的过程.

解析第一部分的内容:

Token=16; Literals=\[97\]; offset=\[1,0\]

Token其实是一个byte分成两部分:前4bit表示LiteralLength,后4bit表示MatchLength.既然如此,我们把Token拆开: LiteralLength= token>>>4 = 1; MatchLength= token&0x0F =0由于是按4-bytes来匹配的，所以MatchLength需要加4，即MatchLength=4 由于literalLength=1<15 ,所以接下的Field是<Literals> ；即dest=\[97\]

接下来，读取到<offset> Field；这个Field是两个byte按Little-Endian格式存储的一个short类型。其值为offset=(offset\[0\] & 0xFF) | ((offset\[1\]& 0xFF)<<8)=1。既然是offset，那么肯定需要一个相对的位置。这个相对的位置就是current position，而不是0，这一点需要记住。所以offset=0是无效的。Offset = 1的意思就是current position-1,推而广之real position = current position &\#8211;offset . 这样的话解码所需的基本要素就齐了，那怎么解码呢？

通过LiteralLength和Literal把Literal写入到byte数组中,如下:

Depressed=\[97\], current position=1 real position = current position &\#8211; offset = 0. matchLength=4

这里出现了一个矛盾：Offset=1, matchLength=4, Offset<matchLength这说明Literal有重叠现象。怎么做呢？

![wKioL1PXOjDBk8vtAAFUvc4tNO0921.jpg][]

这段代码说得非常清楚：在解码的过程中，会有两个可能，一种是上面的例子\----有重叠；一种是没有重叠。有重叠的话就“na&iuml;ve incremental copy”。从字面上不好解释清楚，看代码，多用几个例子，比如“abababababababa”跟踪一下，就能体会到什么是“naive incremental copy”。没有重叠的话就直接调用System.arraycopy()方法，把前面的内容复制过去就OK了。

经过上面的步骤，depressed=\[97,97,97,97,97\],接下来解码第二部分的内容：\[ 16, 98, 5, 0\]

Token=16; Literals=\[98\]; offset=\[1,0\]即LiteralLength=1, MatchLength=0+4=4. Offset=5

Offset > LiteralLength,直接调用System.arraycopy()方法。

得到depressed=\[97, 97,97,97,97,98,97,97,97,97,98\]，看到这里，我们会发现出问题了，原数据是“aaaaabaaaaa”,到这里变成了“aaaaabaaaab”了。其实这里是没有问题的，我们看depressed的下标位置就能够明白了。

接下来处理最后的部分：\[ 112, 97, 99, 97, 97, 97, 97, 97\]

Token=112;读取出LiteralLength= token>>>4 =7，即literals=\[97, 99, 97, 97, 97, 97, 97\] 然后把Literals 复制到depressed数组中，得到最终的结果：

epressed=\[97, 97,97,97,97,98,97,97,97,97, 97, 99, 97, 97, 97, 97, 97\]。这样解码就完毕了。

LZ4的匹配算法在Lucene是用Hash来匹配。当然我们还可以选择其它的数据结构和算法，比如Morphing Match Chain,BinarySearch Tree,Hash Chain,2D Hash Table等等。由于LZ4算法已经到了数据压缩的领域了，已经偏离了Lucene的核心，暂时就浅尝辄止到这里了。

参考博客：

[http://fastcompression.blogspot.com/p/lz4.html<][http_fastcompression.blogspot.com_p_lz4.html]可能需要×××>

转载于:https://blog.51cto.com/sbp810050504/1532152

[wKiom1PXOEqwcBhjAAEvAEaL_6Q857.jpg]: /images/20220115/a77845021d83432a9a397f1fbd5c4537.png
[wKioL1PXOW_SDdKkAABuUUOek4E194.jpg]: /images/20220115/0f3a284d3de8475ab657d42477e8aa81.png
[wKioL1PXOXrAyJBbAAJX9k_UJhM527.jpg]: /images/20220115/396b6d486cdc4198bc10936955a96b5d.png
[wKioL1PXOYigGGu7AADdwq3aUy0282.jpg]: /images/20220115/2773a41cc04b48498ff0b65b7f0445af.png
[wKioL1PXOZuz8Px8AAMQ5mZQqtQ943.jpg]: /images/20220115/2ba14c591d8a43c28c2df980172790a6.png
[wKiom1PXOJKCgP8bAAEWrdf9Rd0583.jpg]: /images/20220115/afe2de244fa14ec9b809609d6cf2d95f.png
[wKioL1PXOdKh10tsAAE3RqKUJwI823.jpg]: /images/20220115/854bf6c14eaf4a4b9ee18f9eaf8b95d4.png
[wKiom1PXOMfj8jqtAADGq2FKWbs019.jpg]: /images/20220115/07d7d17f71f94cf189c7676611da3002.png
[wKioL1PXOe_hy2gxAABfqOhntak539.jpg]: /images/20220115/7a1580efff034b33bf16f5c7a63ef2b2.png
[wKioL1PXOg6zDMghAACiczlCa3Y704.jpg]: /images/20220115/97d8132b11184f92baa5f2f861bd30cb.png
[wKioL1PXOjDBk8vtAAFUvc4tNO0921.jpg]: /images/20220115/c2ba089642d14c1ab8b378d4654fa6e6.png
[http_fastcompression.blogspot.com_p_lz4.html]: http://fastcompression.blogspot.com/p/lz4.html%3C