Lucene系列(二)int的变长存储与zigzag编码
前言
lucene代码量还是比较多的, 在没有看的很明白的情况下, 先写一写新学到的工具类的一些操作吧~也是收获很多.
在lucene写入索引文件时, 为了节省空间,经常会对数据进行一些压缩, 这篇文章介绍一种对int, long类型有用的压缩方式. 即变长存储.
它在lucene中的应用十分广泛, 有事没事就用一下,因此为了熟练的理解代码, 我们还是来一探究竟吧~
在lucene8.7.0版本的代码中, 它没有单独定义成类, 可能是因为是一个小的功能点吧~
对变长数据的写入实现在org.apache.lucene.store.DataOutput#writeVInt中, 对变长数据的读取实现在org.apache.lucene.store.DataInput#readVInt.
定义
什么叫做变长存储? 我们以writeVInt为例,看看注释:
Writes an int in a variable-length format. Writes between one and five bytes. Smaller values take fewer bytes. Negative numbers are supported, but should be avoided. VByte is a variable-length format for positive integers is defined where the high-order bit of each byte indicates whether more bytes remain to be read. The low-order seven bits are appended as increasingly more significant bits in the resulting integer value. Thus values from zero to 127 may be stored in a single byte, values from 128 to 16,383 may be stored in two bytes, and so on.
简单翻译一下:
以可变长度格式写入一个整数. 写入1-5个字节. 越小的值占用的字节越少. 支持负数但是尽量别用. VByte是正整数的变长格式, 每个byte的高位用来标识是否还有更多的字节需要读取. 低位的7个bit位代表实际的数据. 将逐渐读取到的低位附加作为越来越高的高位,就可以拿到原来的整数.
0~127只需要一个字节, 128~16383需要两个字节, 以此类推.
从这里看到,变长整数存储的压缩率,是和数字大小有关系的,数字越小,压缩率越高, 如果全是最大的int, 反而需要更多的字节来存储.
实现
我们实现一个简单的工具类, 能实现上述的变长存储(lucene代码copy出来),之外提供一些辅助我们看源码的方法.
public class VariableInt {
/**
* transfer int to byte[] use variable format
*/
public static byte[] writeVInt(int i) {
int bytesRequired = bytesRequired(i);
byte[] res = new byte[bytesRequired];
int idx =0;
while ((i & ~0x7F) != 0) {
res[idx++] = ((byte) ((i & 0x7F) | 0x80));
i >>>= 7;
}
res[idx] = (byte) i;
return res;
}
/**
* transfer byte[] to int use variable format
*/
public static int readVInt(byte [] vs) throws IOException {
int idx = 0;
byte b = vs[idx++];
// 大于0,说明第一位为0,说明后续没有数据需要读取
if (b >= 0) return b;
int i = b & 0x7F;
b = vs[idx++];
i |= (b & 0x7F) << 7;
if (b >= 0) return i;
b = vs[idx++];
i |= (b & 0x7F) << 14;
if (b >= 0) return i;
b = vs[idx++];
i |= (b & 0x7F) << 21;
if (b >= 0) return i;
b = vs[idx];
// Warning: the next ands use 0x0F / 0xF0 - beware copy/paste errors:
i |= (b & 0x0F) << 28;
if ((b & 0xF0) == 0) return i;
throw new IOException("Invalid vInt detected (too many bits)");
}
/**
* compute int need bytes.
*/
public static int bytesRequired(int i) {
if (i < 0) throw new RuntimeException("I Don't Like Negative.");
if ((i >>> 7) == 0) return 1;
if ((i >>> 14) == 0) return 2;
if ((i >>> 21) == 0) return 3;
if ((i >>> 28) == 0) return 4;
return 5;
}
}除了读取写入意外, 提供了一个计算int数字需要几个byte来存储的方法.在我们debug源码时,可以帮助我们分析写入的索引文件.
VariableLong的代码就不贴了.和Variable基本相同,只是变长的长度从1-5变成了1-9而已.
zigzag编码
在Lucene实现的DataOutPut中, 我们可以看到writeZint(int i)方法,经过了解,它使用zigzag编码+变长存储来存储一个整数.
什么是zigzag编码?
首先我们回顾一下计算机编码:
- 原码：最高位为符号位，剩余位表示绝对值；
- 反码：除符号位外，对原码剩余位依次取反；
- 补码：对于正数，补码为其自身；对于负数，除符号位外对原码剩余位依次取反然后+1。
为了方便及其他问题,计算机使用补码来存储整数.
那么我们的变长整数就有一个问题. 他对于负数很不友好.
- 1这个int整数, 本身存储使用4个字节, 通过上文的变长编码,使用一个字节即可.
- -1这个int整数,他的补码为:
11111111111111111111111111111111, 也就是说全部是1. 你这时候用变长编码来存储, 需要5个字节, 压缩的目的达不到了.反而多占了空间.
那么基于一个共识: 小整数用的多,因此需要变长编码. 小的负整数也不少,变长编码会压缩率不高甚至反向压缩.
因此诞生了zigzag编码, 它可以有效的处理负数. 它的底层逻辑是: 按绝对值升序排列，将整数hash成递增的32位bit流，其hash函数为h(n) = (n ??1) ^ (n?? 31),
hash函数的作用如图所示:
设想一下这个hash函数做了什么?
对于小的负整数而言:
- 左移1位可以消去符号位，低位补0
- 有符号右移31位将符号位移动到最低位，负数高位补1，正数高位补0
- 按位异或 对于正数来说，最低位符号位为0，其他位不变 对于负数，最低位符号位为1，其他位按位取反
那么-1的表示变成了00000000000000000000000000000001, 比较小, 适合使用变长编码了. 1的表示变成了00000000000000000000000000000010, 虽然增大了一点,但是仍然很小,也适合使用变长编码了.
总结一下:
zigzag编码解决了使用变长编码时小的负整数压缩率太低的问题, 它基于一个共识,就是我们使用的小整数(包括正整数和负整数) 是比较多的. 因此将负整数映射到正整数这边来操作.
对应表是:
整数 | zigzag |
|---|---|
0 | 0 |
-1 | 1 |
1 | 2 |
-2 | 3 |
2 | 4 |
-3 | 5 |
3 | 6 |
zigzag实现
这个zigzag的实现比较简单, 在上面已经实现了变长编码的基础上. 只需要实现一个简单的hash函数就好了.
/**
* transfer int to byte[] use zig-zag-variable format
*/
public static byte[] writeZInt(int i) {
// zigzag 编码
i = (i >> 31) ^ (i << 1);
return writeVInt(i);
}
/**
* transfer byte[] to int use zig-zag-variable format
*/
public static int readZInt(byte[] vs) throws IOException {
int i = readVInt(vs);
return ((i >>> 1) ^ -(i & 1));
}完美.
总结
本文简单介绍了.
- 使用变长编码来对整数进行压缩,对于小正整数能取得不错的压缩率.
- 使用zigzag编码对整数进行编码,可以解决掉变长编码对于小负整数压缩率低的难点.
因此, 当你确认你的待压缩数字, 都是比较小的正负整数, 就使用zigzag+变长编码来进行压缩吧, 压缩率25~50%还是可以做到的.
很多需要序列化的开源程序, 都是用zigzag+变长编码来进行整数的压缩, 比如google的protobuf, apache的avro项目, apache的lucene项目, 都在一些场景使用了这套连招, 快快使用吧~.
完。