Lucene 中的 VInt
零 版本
Lucene-Core 版本 8.8.2
一 简介
Lucene 的 Index 设计基本依赖磁盘存储,而倒排索引是依赖大量冗余数据来完成分词搜索的技术,所以 Lucene 在设计的时候用了很多时间换空间的数据压缩技术,以此保障能在最少的磁盘资源来储存最多的数据。VInt 就是其中一个很有意思的结构设计。
二 技术原理
1 概要
Java 中一个普通的 int 占据 4 个 byte。
但是当 int 的值为 -128 ~ 127 的时候,其实只需要一个 byte 就可以放得下了,其它三个 byte 都是无意义的冗余(其它几个 byte 所能代表的区间以此类推),真实能够用满这四个 byte 的情况并不多。VInt 的意思是 variant int,也就是可变的 int。其本质是按需分配,减少这种冗余。
2 byte 指示位
一个正常的 byte 有八个数据有效位,而 VInt 中只有七个,最高位变成了后一个 byte 的指示位。
- 最高位为 1,代表后一个 byte 依然是当前数据
- 最高位为 0,代表后面没有数据了
3 VInt 的副作用
- 对于正数来说,由于只有七个数据位,所以当 int 的值比较大的时候,可能会需要 5 个 byte 才能表述当前的数据(这个问题无法被解决,VInt 也觉得无需解决,因为情况在真实生产中并不多)
- 对于负数来说,最高位为 1,无法被压缩(引入 zigzag 编码)
4 zigzag 编码
使用位移和异或操作将首位的符号位挪到数据的最后一位。
三 Demo假如需要分别序列化 1 / 200 / -1 这三个 int 数,则 VInt 算法的具体步骤为(有效数据标黄):
1 二进制化
- 1 的二进制数为 00000000 00000000 00000000 00000001
- 200 的二进制数为 00000000 00000000 00000000 11001000
- -1 的二进制数为 11111111 11111111 11111111 11111110
2 向前位移一位,后面补 0
- 1 处理后的二进制数为 00000000 00000000 00000000 00000010
- 200 处理后的二进制数为 00000000 00000000 00000001 10010000
- -1 处理后的二进制数为 11111111 11111111 11111111 11111100
3 异或操作
异或操作的本质是不同为 0,相同是 1。
- 对于正数,异或一个 11111111 11111111 11111111 11111111
- 1 的处理表达式为 00000000 00000000 00000000 00000010 ^ 11111111 11111111 11111111 11111111 = 00000000 00000000 00000000 00000010;
- 200 的处理表达式为 00000000 00000000 00000001 10010000 ^ 11111111 11111111 11111111 11111111 = 00000000 00000000 00000001 10010000
- 对于负数,异或一个 00000000 00000000 00000000 00000000
- 【Lucene 中的 VInt】-1 的处理表达式为 11111111 11111111 11111111 11111100 ^ 00000000 00000000 00000000 00000000 = 00000000 00000000 00000000 00000011
4 八位为一个单位处理数字
以八位为一个单位读取数据,当读取到八位之后,将第一位看作是标记位,如果还有其它数据的话,再读取八位。
- 【Lucene 中的 VInt】-1 的处理表达式为 11111111 11111111 11111111 11111100 ^ 00000000 00000000 00000000 00000000 = 00000000 00000000 00000000 00000011
- 对于数字 1 来说
- 序列化过程:
- 先读取七位 0000010,之前都为 0,没有数据,则前面补 0,为 00000010
- 读取过程:
- 读取序列化数据 00000010,第一位是 0,代表只有一个 byte,后面没有其它数据,故数据为 00000010
- 最后一位是 0,代表是正数,与 11111111 异或操作,得到 00000010
- 将数据往后挪一位,前端补 0,最终为 00000001
- 序列化过程:
- 对于数字 200 来说
- 序列化过程:
- 先读取七位 0010000,之前不都为 0,则前面补 1,为 10010000
- 再读取七位 0000011,之前都为 0,则前面补 0,为 00000011
- 组合数据为 10010000 00000011
- 读取过程:
- 读取序列化数据 10010000,第一位是 1,代表不止一个 byte,后面还有其它数据,故数据为 0010000
- 再读取 00000011,第一位是 0,代表没有其它数据来,数据为 0000011
- 组合数据为 00000001 10010000
- 最后一位是 0,代表是正数,与 11111111 11111111 异或操作,得到 00000001 10010000
- 将数据往后挪一位,前端补 0,最终为 00000000 11001000
- 序列化过程:
- 对于数字 -1 来说
- 序列化过程:
- 先读取七位 0000011,之前都为 0,没有数据,则前面补 0,为 00000011
- 读取过程:
- 读取序列化数据 00000011,第一位是 0,代表只有一个 byte,后面没有其它数据,故数据为 00000011
- 最后一位是 1,代表是负数,与 00000000 异或操作,得到 11111100
- 将数据往后挪一位,前端补 1,最终为 11111110
四 源码0 流程
以下源码的调用流程:
- 序列化过程:
- lucene 确认一个 int 值
- 调用 zigZagEncode(...) 将 int 编码成 zint
- 调用 writeVInt(...) 方法将 zint 编码成 vint,并写入到磁盘或者其它内存容器中
- 调用 readVInt() 方法从磁盘或者其它内存容器中读取一个 vint 值,并将其反编码成 zint
- 调用 zigZagDecode(...) 方法将 zint 反编码成 int
1 writeZInt
writeZInt(...) 方法在 org.apache.lucene.store.DataOutput 中:
// 这个方法用于写入一个 zigzag 编码之后的 int 值 public final void writeZInt(int i) throws IOException { // BitUtil.zigZagEncode(i) 用于 zigzag 编码 writeVInt(BitUtil.zigZagEncode(i)); }// 用于写入一个 VInt public final void writeVInt(int i) throws IOException { while ((i & ~0x7F) != 0) { // writeByte(...) 方法用于将 byte 持久化到文件中,暂时无需关注 writeByte((byte)((i & 0x7F) | 0x80)); i >>>= 7; } writeByte((byte)i); }
2 zigZagEncode
zigZagEncode(...) 方法在 org.apache.lucene.util.BitUtil 中:
// i >> 31 对于正数或者 0 来说,会返回全 0 的屏障 // i >> 31 对于负数来说,会返回全 1 的屏障 public static int zigZagEncode(int i) { return (i >> 31) ^ (i << 1); }
3 readZInt
readZInt(...) 方法在 org.apache.lucene.store.DataOutput 中:
public int readZInt() throws IOException { return BitUtil.zigZagDecode(readVInt()); }public int readVInt() throws IOException { // 此处从磁盘读取一个 byte byte b = readByte(); // b >= 0,代表最高位是 0,后续没有值了,以下雷同 if (b >= 0) return b; int i = b & 0x7F; // 继续读取一个 byte b = readByte(); i |= (b & 0x7F) << 7; if (b >= 0) return i; // 继续读取一个 byte b = readByte(); i |= (b & 0x7F) << 14; if (b >= 0) return i; // 继续读取一个 byte b = readByte(); i |= (b & 0x7F) << 21; if (b >= 0) return i; // 继续读取一个 byte,在 VInt 的编码下,最高五个 byte b = readByte(); i |= (b & 0x0F) << 28; if ((b & 0xF0) == 0) return i; throw new IOException("Invalid vInt detected (too many bits)"); }
4 zigZagDecode
zigZagDecode(...) 方法在 org.apache.lucene.util.BitUtil 中:
// decode 的操作和 zigZagEncode(...) 是完全相反的 public static int zigZagDecode(int i) { return ((i >>> 1) ^ -(i & 1)); }
推荐阅读
- xp系统中的wps字体总是含糊不清晰应该怎样办?
- 通过自定义字段中的图像URL更改woocommerce图像
- 寻找两个正序数组中的中位数
- 将标签文章更改为WordPress中的文章
- 更改options-reading.php中的输入”min”属性
- WordPress主题自定义中的类别/图像滑块不显示
- flutter 中的列表的性能优化续集#yyds干货盘点#
- 在第790行的config-woocommerce/config.php中的非对象上调用成员函数get_cart_subtotal()
- 从WordPress中的functions.php调用jQuery
- #yyds干货盘点#认识Golang中的数组类型