Lucene单值编码压缩算法源码解析
作者:沧叔解码 发布时间:2022-12-30 18:00:39
引言
本文收集了我在看Lucene源码中遇到的所有的对单值(int,long,float,double)的压缩算法,可能一种类型针对不同的场景会有多种不同的压缩策略,本文会随着我自己的源码阅读不断持续更新。
不管是什么类型的数值,在计算机中存储都是二进制存储,而我们说对其进行压缩或者编码,其实就是只保留有效信息,什么是有效信息?就是哪些bit位上面是1。所以所有的压缩编码方式都是设计一定的策略,只保留有效信息,并且能够解码或者解压缩。
注意:本文源码基于lucene-core-9.1.0
VInt编码
编码原理
int是4个字节,VInt是对int类型的压缩编码,VInt中的v指的是variant(可变的),也就是VInt编码的int的存储空间的大小是以字节为单位的变长大小。VInt编码结果中的每个字节分为两部分:
第1位:标记位,如果是1,表示后面的字节也属于当前value的VInt编码结果,如果是0,则表示当前value的VInt编码结果结束。
剩下的7位:数据位,VInt中所有字节的低7位合起来就是完成的value的值。
我们来看几个例子更好理解:
VInt编码1314
如上图所示,整型1314原始编码需要4字节,但是我们可以发现高位的一连串0其实都是无效信息,其实是不需要存储的。VInt编码首先取原始二进制编码的最低7位,如上图绿色所示,这部分构成VInt的第一个字节的最低7位,因为1314除了最低7位,剩下的非全0,所以第一个VInt编码的字节的首位的标记位为1,表示VInt编码后面还有一个字节参与编码。VInt编码的第二个字节的最低7位就是由原始二进制编码中红色的部分表示(可以通过右移7位,获取最低7位得到),1314剩下的数据都是0,则VInt编码的第2个字节的第一位标记位为0,表示1314的VInt编码结束了。所以1314的VInt编码就是两个字节。
VInt编码10
如上图所示,对于整型10,正常的的4字节编码,前3个字节都是0,可以做个标记,不用占用真实的空间。
换成VInt编码,只需要一个字节。需要注意的是,这个字节的第一位是标记位。如果标记位是0,则表示当前字节就是数值的结束字节。如果标记位是1,则表示后面有字节属于当前数值。如下图所示:
VInt编码-10
如果使用VInt编码算法对-10进行编码,结果如下图所示:
我们会发现,-10的VInt编码居然要5个字节,因此VInt编码只对正数有压缩作用。
源码实现
编码
public final void writeVInt(int i) throws IOException {
// 如果i的最低7位置0后i非0
while ((i & ~0x7F) != 0) {
// i & 0x7F:取最低7位
// | 0x80 为flag为置1
writeByte((byte) ((i & 0x7F) | 0x80));
// i 右移7位
i >>>= 7;
}
// 剩下不足7位的
writeByte((byte) i);
}
解码
public int readVInt() throws IOException {
byte b = readByte();
// 如果 b >= 0, 说明flag位是0,当前要读的值只有一个字节。
if (b >= 0) return b;
int i = b & 0x7F;
b = readByte();
i |= (b & 0x7F) << 7;
if (b >= 0) return i;
b = readByte();
i |= (b & 0x7F) << 14;
if (b >= 0) return i;
b = readByte();
i |= (b & 0x7F) << 21;
if (b >= 0) return i;
b = readByte();
// 最后一个字节最多只有4位是有效的
i |= (b & 0x0F) << 28;
// 如果最后一个字节只有低四位有效,则说明格式正确
if ((b & 0xF0) == 0) return i;
throw new IOException("Invalid vInt detected (too many bits)");
}
VLong编码
对long类型的变长编码原理同VInt,不再赘述。
zigzag编码
编码原理
zigzag是一种编码方式,可以用于int和long,原理一模一样,下面以int为例子。
我们想一下为什么负数会阻碍数据压缩呢?我们知道,数据压缩其实就是保留有效信息,在计算机中,数据就是0和1,1肯定是有效信息,所以压缩就是去掉无效的0。
先观察下正数和负数二进制的规律:
虽然我们举的例子10和-10只是个例,但是了解负数补码的计算方式,就知道,负数是正数按位取反再加1。所以正数的高位是连续的0,负数的高位是连续的1。
因此,可以分两步来处理,首先要想办法把这个符号位1处理下,简单的做法就是把1挪到最后一位。剩下的数据位,我们可以把数据位取反,数据位和符号位异或就可以取反。
zigzag对正数的编码,其实就是正数左移一位。
源码
编码
public static int zigZagEncode(int i) {
// (i >> 31):处理符号位,把所有的位都设置为符号位,等待和0(数据位左移1位空出来的0)做异或,就能保留符号位在最后一位
// (i << 1):处理数据位,数据为左移1位,把最后一位用来存符号位,其他数据为都和符号位做异或编码
return (i >> 31) ^ (i << 1);
}
解码
public static int zigZagDecode(int i) {
// (i >>> 1):还原数据位,最后和符号位做异或解码
// -(i & 1):还原符号位,i的最后一位是符号位,该表达式把每一位都设置为符号位
return ((i >>> 1) ^ -(i & 1));
}
ZFloat
编码原理
ZFloat对float的编码分为3种情况来处理:
情况1:如果float的值强转成int类型后的值intVal和float相等,并且intVal的范围在[-1,125]之间,这种情况只用一个byte就可以,将byte的最高位设为1标记这种情况,把intVal的值加1后存储在byte的低7位中。
情况2:排除第一种情况之外,如果float>0,则按IEEE 754的标准直接存储,并没有压缩处理。
情况3:其他情况首先写入一个byte:0xFF标记最后一种情况,然后直接按IEEE 754的标准直接存储,并没有压缩处理。
从上面的说明可能会有一些疑问:
第一种情况中为什么范围就是[-1,125]?
最终存储的时候会加1,范围变成了[0,126],二进制的范围[0000 0000,0111 1110],因为最高位会设置成1标记这种情况,而1111 1111留出来作为情况3的标记,所以范围就是[-1,125]。
后面两种根本就没有做压缩,第三种情况还额外要多一个字节,不能和第2种情况合并吗?
不能合并,合并了,属于情况3的值会和情况1的有冲突,读取的时候无法识别。
凭什么说,zfloat是对float的压缩算法?
我觉得还是要分场景,如果大部分数值都是属于情况1,那压缩效果是比较好的,如果大部分的数值都是属于情况3,则不仅没有压缩,反而膨胀了。
上面说的可能还没有直接看源码来的清楚。
源码编码
static void writeZFloat(DataOutput out, float f) throws IOException {
int intVal = (int) f;
final int floatBits = Float.floatToIntBits(f);
// 为什么负数只对-1处理呢?原因是-1+1可以变成0
// 为什么正数直到125呢,是因为第3个分支,会先写个标记byte:0xFF,所以不能包括126,126+1=127=0xFF会冲突
if (f == intVal && intVal >= -1 && intVal <= 0x7D && floatBits != NEGATIVE_ZERO_FLOAT) {
// 最高位是1表示这种情况
out.writeByte((byte) (0x80 | (1 + intVal)));
} else if ((floatBits >>> 31) == 0) { // 其他大于0的情况
// 为什么不直接writeInt呢?我也不清楚,单独的lucene-core模块没有找到原因。
out.writeByte((byte) (floatBits >> 24));
out.writeShort((short) (floatBits >>> 8));
out.writeByte((byte) floatBits);
} else { // 其他小于0的情况
out.writeByte((byte) 0xFF);
out.writeInt(floatBits);
}
}
解码
static float readZFloat(DataInput in) throws IOException {
// 先读取第一个字节,用来判断属于哪种情况
int b = in.readByte() & 0xFF;
if (b == 0xFF) { // 情况3,后面还有4字节IEEE 754编码的float
return Float.intBitsToFloat(in.readInt());
} else if ((b & 0x80) != 0) { // 情况1
// b & 0x7f:最高位设为0
// -1 是因为编码的时候进行加1了
return (b & 0x7f) - 1;
} else { // 情况2
int bits = b << 24 | ((in.readShort() & 0xFFFF) << 8) | (in.readByte() & 0xFF);
return Float.intBitsToFloat(bits);
}
}
ZDouble
编码原理
double的编码和float的非常像,但是多了一种情况,如果double的值强转成float后精度没有丢失,则直接用float存储。其他情况和float的一模一样,我们就直接看源码吧。
源码编码
static void writeZDouble(DataOutput out, double d) throws IOException {
int intVal = (int) d;
final long doubleBits = Double.doubleToLongBits(d);
// 因为多了一种情况,所以需要多一个标记,因此范围成了 [-1..124]
if (d == intVal && intVal >= -1 && intVal <= 0x7C && doubleBits != NEGATIVE_ZERO_DOUBLE) {
out.writeByte((byte) (0x80 | (intVal + 1)));
return;
} else if (d == (float) d) { // 和zfloat相比,多出来的一种情况,使用标记:0xFE
out.writeByte((byte) 0xFE);
out.writeInt(Float.floatToIntBits((float) d));
} else if ((doubleBits >>> 63) == 0) { // 同zfloat情况2
out.writeByte((byte) (doubleBits >> 56));
out.writeInt((int) (doubleBits >>> 24));
out.writeShort((short) (doubleBits >>> 8));
out.writeByte((byte) (doubleBits));
} else { // 同zfloat情况3
out.writeByte((byte) 0xFF);
out.writeLong(doubleBits);
}
}
解码
static double readZDouble(DataInput in) throws IOException {
int b = in.readByte() & 0xFF;
if (b == 0xFF) {
return Double.longBitsToDouble(in.readLong());
} else if (b == 0xFE) {
return Float.intBitsToFloat(in.readInt());
} else if ((b & 0x80) != 0) {
return (b & 0x7f) - 1;
} else {
long bits =
((long) b) << 56
| ((in.readInt() & 0xFFFFFFFFL) << 24)
| ((in.readShort() & 0xFFFFL) << 8)
| (in.readByte() & 0xFFL);
return Double.longBitsToDouble(bits);
}
}
TLong
编码原理
TLong是对使用long类型存储的毫秒级timestamp的编码算法。TLong的编码有个header记录使用的是哪种编码方式,四种header的格式如下所示:
day:如果timestap的值是1000*60*60*24的整数倍,则可以保留除以1000*60*60*24之后的值来编码。
hour:如果timestap的值是1000*60*60的整数倍,则可以保留除以1000*60*60之后的值来编码。
second:如果timestap的值是1000的整数倍,则可以保留除以1000之后的值来编码。
uncompressed:其他情况就不需要先处理。
header是一个byte,我们的编码方式只有4种,只需要两位就能标记,剩下的6位我们也不能浪费。用其中5位存储经过上述预处理后的值的低5位,如果除了低5位外非零,使用VLong存储剩下的值。而header剩下的1位就是用来表示除了header之外是否还有剩下的值,我们看个例子,下面的例子中是可以整除hour级别的,因此使用的hour的编码方式:
如上面的例子所示,2022-11-08 10:00:00的毫秒级时间戳是1667872800000,它可以整除1000*60*60,所以使用的header是hour并且整除后的值是463298,463298的二进制和zigzag编码(整数的zigzag编码就是左移一位)如上图所示,把zigzag编码的低5位拷贝到header的低5位,zigzag剩下的值不为0,则header中的标记位设置为1。zigzag剩下的值使用VLong编码,因此TLong编码的结果如上图所示。
源码编码
static void writeTLong(DataOutput out, long l) throws IOException {
int header;
if (l % SECOND != 0) { // 无压缩
header = 0;
} else if (l % DAY == 0) { // 按天粒度
header = DAY_ENCODING;
l /= DAY;
} else if (l % HOUR == 0) { // 小时粒度
header = HOUR_ENCODING;
l /= HOUR;
} else { // 秒粒度
header = SECOND_ENCODING;
l /= SECOND;
}
// 先按zigzag编码
final long zigZagL = BitUtil.zigZagEncode(l);
// zigzag编码的最后5位放在head的最后5位
header |= (zigZagL & 0x1F);
final long upperBits = zigZagL >>> 5;
if (upperBits != 0) { // 如果zigzag编码的值去除最后5位后非零,则header的第3位设置为1,表示后面还有数据
header |= 0x20;
}
// 写入header
out.writeByte((byte) header);
if (upperBits != 0) { // zigzag编码的值去除最后5位剩下的value使用VLong的方式编码
out.writeVLong(upperBits);
}
}
解码
static long readTLong(DataInput in) throws IOException {
// 读取header
int header = in.readByte() & 0xFF;
// 取header最后5位
long bits = header & 0x1F;
if ((header & 0x20) != 0) { // 判断是否除了header之外后面还有数据
// in.readVLong():读取VLong编码的剩下数据
// << 5: 左移5位,为header中的低5位留出空间
// bits |=:bits是保存的是完整的数据
bits |= in.readVLong() << 5;
}
// 使用zigzag解码
long l = BitUtil.zigZagDecode(bits);
switch (header & DAY_ENCODING) { // 按照不同的编码,乘以相应的倍数还原时间戳
case SECOND_ENCODING:
l *= SECOND;
break;
case HOUR_ENCODING:
l *= HOUR;
break;
case DAY_ENCODING:
l *= DAY;
break;
case 0:
break;
default:
throw new AssertionError();
}
return l;
}
来源:https://juejin.cn/post/7163560186823573517
猜你喜欢
- 前言我们都知道在java中进行日期格式化使用simpledateformat。通过格式 yyyy-MM-dd 等来进行格式化,但是你知道其中
- 一、ANR说明和原因1.1 简介ANR全称:Application Not Responding,也就是应用程序无响应。1.2 原因Andr
- 主要从以下几方面来介绍一下@Scope注解@Scope注解是什么@Scope注解怎么使用@Scope注解的使用场景1,@Scope注解是什么
- 装饰器模式概述装饰器模式(Decorator Pattern)也称为包装模式(Wrapper Pattern),属于结构型模式。它是指在不改
- 1、未配置之前2、开始配置 2.1 新建一个unauth.html<!DOCTYPE html><html la
- 问题(1)重入锁是什么?(2)ReentrantLock如何实现重入锁?(3)ReentrantLock为什么默认是非公平模式?(4)Ree
- Exception e中e的getMessage()和toString()方法的区别:示例代码1:public class TestInfo
- 本文以实例形式讲述了C#命令模式的实现方法,分享给大家供大家参考。具体实现方法如下:现假设想让遥控器控制电灯的开关、电视机的开关和切换,该如
- ①概念二叉搜索树又称二叉排序树,它或者是一棵空树**,或者是具有以下性质的二叉树:若它的左子树不为空,则左子树上所有节点的值都小于根节点的值
- 1、什么是 生命周期?Maven 强大的原因是有一个十分完善的生命周期,生命周期可以理解为项目构建步骤的集合,它定义了各个构建环节的执行顺序
- Spring spring-context-indexer依赖<dependencies> <d
- 前言为了减少日志频繁打印带来的性能影响,线上环境设置的日志级别一般都相对较高。而当出现生产问题需要排查的时候,可能需要适当降低日志级别(例如
- 以下代码实现了android的免提开启和关闭功能需要添加的权限<uses-permission android:name="
- Maven打包时指定启动类使用Maven打包的时候, 有时候需要指定启动类, 可如下操作!测试项目(结构如下):代码: com.xxx.Ma
- 一、直接插入排序基本思想:将一个记录插入到已排序的有序表中,使插入后的表仍然有序对初始关键字{49 38 65 97 76 13 27 49
- 大部分app打开pdf文件是通过intent调起手机中能打开pdf文件的工具,来查看pdf文件,如果需求是,用户在app内下载好pdf文件后
- log4j MDC实现日志追踪MDC 中包含的可以被同一线程中执行的代码所访问内容。当前线程的子线程会继承其父线程中的 MDC 的内容。记录
- public string check_number(string num_str)
- 1, * 的概念java里的 * 是动态拦截Action调用的对象,它提供了一种机制可以使开发者在一个Action执行的前后执行
- 目录获取程序下面的文件获取临时目录下的文件获取程序下面的文件首先我们创建了实例解决方案:其中调用链是:Main.Shell->FooA