Lucene單值編碼壓縮算法源碼解析
引言
本文收集了我在看Lucene源碼中遇到的所有的對(duì)單值(int,long,float,double)的壓縮算法,可能一種類型針對(duì)不同的場(chǎng)景會(huì)有多種不同的壓縮策略,本文會(huì)隨著我自己的源碼閱讀不斷持續(xù)更新。
不管是什么類型的數(shù)值,在計(jì)算機(jī)中存儲(chǔ)都是二進(jìn)制存儲(chǔ),而我們說(shuō)對(duì)其進(jìn)行壓縮或者編碼,其實(shí)就是只保留有效信息,什么是有效信息?就是哪些bit位上面是1。所以所有的壓縮編碼方式都是設(shè)計(jì)一定的策略,只保留有效信息,并且能夠解碼或者解壓縮。
注意:本文源碼基于lucene-core-9.1.0
VInt編碼
編碼原理
int是4個(gè)字節(jié),VInt是對(duì)int類型的壓縮編碼,VInt中的v指的是variant(可變的),也就是VInt編碼的int的存儲(chǔ)空間的大小是以字節(jié)為單位的變長(zhǎng)大小。VInt編碼結(jié)果中的每個(gè)字節(jié)分為兩部分:
- 第1位:標(biāo)記位,如果是1,表示后面的字節(jié)也屬于當(dāng)前value的VInt編碼結(jié)果,如果是0,則表示當(dāng)前value的VInt編碼結(jié)果結(jié)束。
- 剩下的7位:數(shù)據(jù)位,VInt中所有字節(jié)的低7位合起來(lái)就是完成的value的值。
我們來(lái)看幾個(gè)例子更好理解:
VInt編碼1314

如上圖所示,整型1314原始編碼需要4字節(jié),但是我們可以發(fā)現(xiàn)高位的一連串0其實(shí)都是無(wú)效信息,其實(shí)是不需要存儲(chǔ)的。VInt編碼首先取原始二進(jìn)制編碼的最低7位,如上圖綠色所示,這部分構(gòu)成VInt的第一個(gè)字節(jié)的最低7位,因?yàn)?314除了最低7位,剩下的非全0,所以第一個(gè)VInt編碼的字節(jié)的首位的標(biāo)記位為1,表示VInt編碼后面還有一個(gè)字節(jié)參與編碼。VInt編碼的第二個(gè)字節(jié)的最低7位就是由原始二進(jìn)制編碼中紅色的部分表示(可以通過(guò)右移7位,獲取最低7位得到),1314剩下的數(shù)據(jù)都是0,則VInt編碼的第2個(gè)字節(jié)的第一位標(biāo)記位為0,表示1314的VInt編碼結(jié)束了。所以1314的VInt編碼就是兩個(gè)字節(jié)。
VInt編碼10

如上圖所示,對(duì)于整型10,正常的的4字節(jié)編碼,前3個(gè)字節(jié)都是0,可以做個(gè)標(biāo)記,不用占用真實(shí)的空間。
換成VInt編碼,只需要一個(gè)字節(jié)。需要注意的是,這個(gè)字節(jié)的第一位是標(biāo)記位。如果標(biāo)記位是0,則表示當(dāng)前字節(jié)就是數(shù)值的結(jié)束字節(jié)。如果標(biāo)記位是1,則表示后面有字節(jié)屬于當(dāng)前數(shù)值。如下圖所示:
VInt編碼-10
如果使用VInt編碼算法對(duì)-10進(jìn)行編碼,結(jié)果如下圖所示:

我們會(huì)發(fā)現(xiàn),-10的VInt編碼居然要5個(gè)字節(jié),因此VInt編碼只對(duì)正數(shù)有壓縮作用。
源碼實(shí)現(xiàn)
編碼
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, 說(shuō)明flag位是0,當(dāng)前要讀的值只有一個(gè)字節(jié)。
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();
// 最后一個(gè)字節(jié)最多只有4位是有效的
i |= (b & 0x0F) << 28;
// 如果最后一個(gè)字節(jié)只有低四位有效,則說(shuō)明格式正確
if ((b & 0xF0) == 0) return i;
throw new IOException("Invalid vInt detected (too many bits)");
}
VLong編碼
對(duì)long類型的變長(zhǎng)編碼原理同VInt,不再贅述。
zigzag編碼
編碼原理
zigzag是一種編碼方式,可以用于int和long,原理一模一樣,下面以int為例子。
我們想一下為什么負(fù)數(shù)會(huì)阻礙數(shù)據(jù)壓縮呢?我們知道,數(shù)據(jù)壓縮其實(shí)就是保留有效信息,在計(jì)算機(jī)中,數(shù)據(jù)就是0和1,1肯定是有效信息,所以壓縮就是去掉無(wú)效的0。
先觀察下正數(shù)和負(fù)數(shù)二進(jìn)制的規(guī)律:

雖然我們舉的例子10和-10只是個(gè)例,但是了解負(fù)數(shù)補(bǔ)碼的計(jì)算方式,就知道,負(fù)數(shù)是正數(shù)按位取反再加1。所以正數(shù)的高位是連續(xù)的0,負(fù)數(shù)的高位是連續(xù)的1。
因此,可以分兩步來(lái)處理,首先要想辦法把這個(gè)符號(hào)位1處理下,簡(jiǎn)單的做法就是把1挪到最后一位。剩下的數(shù)據(jù)位,我們可以把數(shù)據(jù)位取反,數(shù)據(jù)位和符號(hào)位異或就可以取反。

zigzag對(duì)正數(shù)的編碼,其實(shí)就是正數(shù)左移一位。
源碼
編碼
public static int zigZagEncode(int i) {
// (i >> 31):處理符號(hào)位,把所有的位都設(shè)置為符號(hào)位,等待和0(數(shù)據(jù)位左移1位空出來(lái)的0)做異或,就能保留符號(hào)位在最后一位
// (i << 1):處理數(shù)據(jù)位,數(shù)據(jù)為左移1位,把最后一位用來(lái)存符號(hào)位,其他數(shù)據(jù)為都和符號(hào)位做異或編碼
return (i >> 31) ^ (i << 1);
}
解碼
public static int zigZagDecode(int i) {
// (i >>> 1):還原數(shù)據(jù)位,最后和符號(hào)位做異或解碼
// -(i & 1):還原符號(hào)位,i的最后一位是符號(hào)位,該表達(dá)式把每一位都設(shè)置為符號(hào)位
return ((i >>> 1) ^ -(i & 1));
}
ZFloat
編碼原理
ZFloat對(duì)float的編碼分為3種情況來(lái)處理:
- 情況1:如果float的值強(qiáng)轉(zhuǎn)成int類型后的值intVal和float相等,并且intVal的范圍在[-1,125]之間,這種情況只用一個(gè)byte就可以,將byte的最高位設(shè)為1標(biāo)記這種情況,把intVal的值加1后存儲(chǔ)在byte的低7位中。
- 情況2:排除第一種情況之外,如果float>0,則按IEEE 754的標(biāo)準(zhǔn)直接存儲(chǔ),并沒(méi)有壓縮處理。
- 情況3:其他情況首先寫入一個(gè)byte:0xFF標(biāo)記最后一種情況,然后直接按IEEE 754的標(biāo)準(zhǔn)直接存儲(chǔ),并沒(méi)有壓縮處理。
從上面的說(shuō)明可能會(huì)有一些疑問(wèn):
第一種情況中為什么范圍就是[-1,125]?
最終存儲(chǔ)的時(shí)候會(huì)加1,范圍變成了[0,126],二進(jìn)制的范圍[0000 0000,0111 1110],因?yàn)樽罡呶粫?huì)設(shè)置成1標(biāo)記這種情況,而1111 1111留出來(lái)作為情況3的標(biāo)記,所以范圍就是[-1,125]。
后面兩種根本就沒(méi)有做壓縮,第三種情況還額外要多一個(gè)字節(jié),不能和第2種情況合并嗎?
不能合并,合并了,屬于情況3的值會(huì)和情況1的有沖突,讀取的時(shí)候無(wú)法識(shí)別。
憑什么說(shuō),zfloat是對(duì)float的壓縮算法?
我覺(jué)得還是要分場(chǎng)景,如果大部分?jǐn)?shù)值都是屬于情況1,那壓縮效果是比較好的,如果大部分的數(shù)值都是屬于情況3,則不僅沒(méi)有壓縮,反而膨脹了。
上面說(shuō)的可能還沒(méi)有直接看源碼來(lái)的清楚。
源碼編碼
static void writeZFloat(DataOutput out, float f) throws IOException {
int intVal = (int) f;
final int floatBits = Float.floatToIntBits(f);
// 為什么負(fù)數(shù)只對(duì)-1處理呢?原因是-1+1可以變成0
// 為什么正數(shù)直到125呢,是因?yàn)榈?個(gè)分支,會(huì)先寫個(gè)標(biāo)記byte:0xFF,所以不能包括126,126+1=127=0xFF會(huì)沖突
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呢?我也不清楚,單獨(dú)的lucene-core模塊沒(méi)有找到原因。
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 {
// 先讀取第一個(gè)字節(jié),用來(lái)判斷屬于哪種情況
int b = in.readByte() & 0xFF;
if (b == 0xFF) { // 情況3,后面還有4字節(jié)IEEE 754編碼的float
return Float.intBitsToFloat(in.readInt());
} else if ((b & 0x80) != 0) { // 情況1
// b & 0x7f:最高位設(shè)為0
// -1 是因?yàn)榫幋a的時(shí)候進(jìn)行加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的值強(qiáng)轉(zhuǎn)成float后精度沒(méi)有丟失,則直接用float存儲(chǔ)。其他情況和float的一模一樣,我們就直接看源碼吧。
源碼編碼
static void writeZDouble(DataOutput out, double d) throws IOException {
int intVal = (int) d;
final long doubleBits = Double.doubleToLongBits(d);
// 因?yàn)槎嗔艘环N情況,所以需要多一個(gè)標(biāo)記,因此范圍成了 [-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相比,多出來(lái)的一種情況,使用標(biāo)記: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是對(duì)使用long類型存儲(chǔ)的毫秒級(jí)timestamp的編碼算法。TLong的編碼有個(gè)header記錄使用的是哪種編碼方式,四種header的格式如下所示:

- day:如果timestap的值是1000*60*60*24的整數(shù)倍,則可以保留除以1000*60*60*24之后的值來(lái)編碼。
- hour:如果timestap的值是1000*60*60的整數(shù)倍,則可以保留除以1000*60*60之后的值來(lái)編碼。
- second:如果timestap的值是1000的整數(shù)倍,則可以保留除以1000之后的值來(lái)編碼。
- uncompressed:其他情況就不需要先處理。
header是一個(gè)byte,我們的編碼方式只有4種,只需要兩位就能標(biāo)記,剩下的6位我們也不能浪費(fèi)。用其中5位存儲(chǔ)經(jīng)過(guò)上述預(yù)處理后的值的低5位,如果除了低5位外非零,使用VLong存儲(chǔ)剩下的值。而header剩下的1位就是用來(lái)表示除了header之外是否還有剩下的值,我們看個(gè)例子,下面的例子中是可以整除hour級(jí)別的,因此使用的hour的編碼方式:

如上面的例子所示,2022-11-08 10:00:00的毫秒級(jí)時(shí)間戳是1667872800000,它可以整除1000*60*60,所以使用的header是hour并且整除后的值是463298,463298的二進(jìn)制和zigzag編碼(整數(shù)的zigzag編碼就是左移一位)如上圖所示,把zigzag編碼的低5位拷貝到header的低5位,zigzag剩下的值不為0,則header中的標(biāo)記位設(shè)置為1。zigzag剩下的值使用VLong編碼,因此TLong編碼的結(jié)果如上圖所示。
源碼編碼
static void writeTLong(DataOutput out, long l) throws IOException {
int header;
if (l % SECOND != 0) { // 無(wú)壓縮
header = 0;
} else if (l % DAY == 0) { // 按天粒度
header = DAY_ENCODING;
l /= DAY;
} else if (l % HOUR == 0) { // 小時(shí)粒度
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位設(shè)置為1,表示后面還有數(shù)據(jù)
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之外后面還有數(shù)據(jù)
// in.readVLong():讀取VLong編碼的剩下數(shù)據(jù)
// << 5: 左移5位,為header中的低5位留出空間
// bits |=:bits是保存的是完整的數(shù)據(jù)
bits |= in.readVLong() << 5;
}
// 使用zigzag解碼
long l = BitUtil.zigZagDecode(bits);
switch (header & DAY_ENCODING) { // 按照不同的編碼,乘以相應(yīng)的倍數(shù)還原時(shí)間戳
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;
}以上就是Lucene單值編碼壓縮算法源碼解析的詳細(xì)內(nèi)容,更多關(guān)于Lucene單值編碼壓縮算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
深入探討Java 中的 Object 類詳解(一切類的根基)
本文詳細(xì)介紹了Java中的Object類,作為所有類的根類,其重要性不言而喻,文章涵蓋了Object類的主要方法,如toString()、equals()、hashCode()等,本文深入探討 Object 類的作用、常用方法以及如何在實(shí)際開發(fā)中利用這些方法,感興趣的朋友一起看看吧2025-01-01
SpringBoot主鍵ID傳到前端后精度丟失的問(wèn)題解決
這篇文章主要通過(guò)示例為大家詳細(xì)介紹一些SpringBoot如何解決雪花算法主鍵ID傳到前端后精度丟失問(wèn)題,文中的示例代碼講解詳細(xì),需要的可以參考一下2022-05-05
一個(gè)例子帶你看懂Java中synchronized關(guān)鍵字到底怎么用
synchronized是Java里的一個(gè)關(guān)鍵字,起到的一個(gè)效果是"監(jiān)視器鎖",它的功能就是保證操作的原子性,同時(shí)禁止指令重排序和保證內(nèi)存的可見性,下面這篇文章主要給大家介紹了關(guān)于如何通過(guò)一個(gè)例子帶你看懂Java中synchronized關(guān)鍵字到底怎么用的相關(guān)資料,需要的朋友可以參考下2022-10-10
jdk17+springboot使用webservice的踩坑實(shí)戰(zhàn)記錄
這篇文章主要給大家介紹了關(guān)于jdk17+springboot使用webservice踩坑的相關(guān)資料,網(wǎng)上很多教程是基于jdk8的,所以很多在17上面跑不起來(lái),折騰兩天,直接給答案,需要的朋友可以參考下2024-01-01
超詳細(xì)講解Java秒殺項(xiàng)目登陸模塊的實(shí)現(xiàn)
這是一個(gè)主要使用java開發(fā)的秒殺系統(tǒng),項(xiàng)目比較大,所以本篇只實(shí)現(xiàn)了登陸模塊,代碼非常詳盡,感興趣的朋友快來(lái)看看2022-03-03
Spring MVC---數(shù)據(jù)綁定和表單標(biāo)簽詳解
本篇文章主要介紹了Spring MVC---數(shù)據(jù)綁定和表單標(biāo)簽詳解,具有一定的參考價(jià)值,有興趣的可以了解一下。2017-01-01

