Lucene單值編碼壓縮算法源碼解析
引言
本文收集了我在看Lucene源碼中遇到的所有的對單值(int,long,float,double)的壓縮算法,可能一種類型針對不同的場景會有多種不同的壓縮策略,本文會隨著我自己的源碼閱讀不斷持續(xù)更新。
不管是什么類型的數(shù)值,在計算機中存儲都是二進制存儲,而我們說對其進行壓縮或者編碼,其實就是只保留有效信息,什么是有效信息?就是哪些bit位上面是1。所以所有的壓縮編碼方式都是設計一定的策略,只保留有效信息,并且能夠解碼或者解壓縮。
注意:本文源碼基于lucene-core-9.1.0
VInt編碼
編碼原理
int是4個字節(jié),VInt是對int類型的壓縮編碼,VInt中的v指的是variant(可變的),也就是VInt編碼的int的存儲空間的大小是以字節(jié)為單位的變長大小。VInt編碼結果中的每個字節(jié)分為兩部分:
- 第1位:標記位,如果是1,表示后面的字節(jié)也屬于當前value的VInt編碼結果,如果是0,則表示當前value的VInt編碼結果結束。
- 剩下的7位:數(shù)據(jù)位,VInt中所有字節(jié)的低7位合起來就是完成的value的值。
我們來看幾個例子更好理解:
VInt編碼1314
如上圖所示,整型1314原始編碼需要4字節(jié),但是我們可以發(fā)現(xiàn)高位的一連串0其實都是無效信息,其實是不需要存儲的。VInt編碼首先取原始二進制編碼的最低7位,如上圖綠色所示,這部分構成VInt的第一個字節(jié)的最低7位,因為1314除了最低7位,剩下的非全0,所以第一個VInt編碼的字節(jié)的首位的標記位為1,表示VInt編碼后面還有一個字節(jié)參與編碼。VInt編碼的第二個字節(jié)的最低7位就是由原始二進制編碼中紅色的部分表示(可以通過右移7位,獲取最低7位得到),1314剩下的數(shù)據(jù)都是0,則VInt編碼的第2個字節(jié)的第一位標記位為0,表示1314的VInt編碼結束了。所以1314的VInt編碼就是兩個字節(jié)。
VInt編碼10
如上圖所示,對于整型10,正常的的4字節(jié)編碼,前3個字節(jié)都是0,可以做個標記,不用占用真實的空間。
換成VInt編碼,只需要一個字節(jié)。需要注意的是,這個字節(jié)的第一位是標記位。如果標記位是0,則表示當前字節(jié)就是數(shù)值的結束字節(jié)。如果標記位是1,則表示后面有字節(jié)屬于當前數(shù)值。如下圖所示:
VInt編碼-10
如果使用VInt編碼算法對-10進行編碼,結果如下圖所示:
我們會發(fā)現(xiàn),-10的VInt編碼居然要5個字節(jié),因此VInt編碼只對正數(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, 說明flag位是0,當前要讀的值只有一個字節(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(); // 最后一個字節(jié)最多只有4位是有效的 i |= (b & 0x0F) << 28; // 如果最后一個字節(jié)只有低四位有效,則說明格式正確 if ((b & 0xF0) == 0) return i; throw new IOException("Invalid vInt detected (too many bits)"); }
VLong編碼
對long類型的變長編碼原理同VInt,不再贅述。
zigzag編碼
編碼原理
zigzag是一種編碼方式,可以用于int和long,原理一模一樣,下面以int為例子。
我們想一下為什么負數(shù)會阻礙數(shù)據(jù)壓縮呢?我們知道,數(shù)據(jù)壓縮其實就是保留有效信息,在計算機中,數(shù)據(jù)就是0和1,1肯定是有效信息,所以壓縮就是去掉無效的0。
先觀察下正數(shù)和負數(shù)二進制的規(guī)律:
雖然我們舉的例子10和-10只是個例,但是了解負數(shù)補碼的計算方式,就知道,負數(shù)是正數(shù)按位取反再加1。所以正數(shù)的高位是連續(xù)的0,負數(shù)的高位是連續(xù)的1。
因此,可以分兩步來處理,首先要想辦法把這個符號位1處理下,簡單的做法就是把1挪到最后一位。剩下的數(shù)據(jù)位,我們可以把數(shù)據(jù)位取反,數(shù)據(jù)位和符號位異或就可以取反。
zigzag對正數(shù)的編碼,其實就是正數(shù)左移一位。
源碼
編碼
public static int zigZagEncode(int i) { // (i >> 31):處理符號位,把所有的位都設置為符號位,等待和0(數(shù)據(jù)位左移1位空出來的0)做異或,就能保留符號位在最后一位 // (i << 1):處理數(shù)據(jù)位,數(shù)據(jù)為左移1位,把最后一位用來存符號位,其他數(shù)據(jù)為都和符號位做異或編碼 return (i >> 31) ^ (i << 1); }
解碼
public static int zigZagDecode(int i) { // (i >>> 1):還原數(shù)據(jù)位,最后和符號位做異或解碼 // -(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]。
后面兩種根本就沒有做壓縮,第三種情況還額外要多一個字節(jié),不能和第2種情況合并嗎?
不能合并,合并了,屬于情況3的值會和情況1的有沖突,讀取的時候無法識別。
憑什么說,zfloat是對float的壓縮算法?
我覺得還是要分場景,如果大部分數(shù)值都是屬于情況1,那壓縮效果是比較好的,如果大部分的數(shù)值都是屬于情況3,則不僅沒有壓縮,反而膨脹了。
上面說的可能還沒有直接看源碼來的清楚。
源碼編碼
static void writeZFloat(DataOutput out, float f) throws IOException { int intVal = (int) f; final int floatBits = Float.floatToIntBits(f); // 為什么負數(shù)只對-1處理呢?原因是-1+1可以變成0 // 為什么正數(shù)直到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 { // 先讀取第一個字節(jié),用來判斷屬于哪種情況 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:最高位設為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的整數(shù)倍,則可以保留除以1000*60*60*24之后的值來編碼。
- hour:如果timestap的值是1000*60*60的整數(shù)倍,則可以保留除以1000*60*60之后的值來編碼。
- second:如果timestap的值是1000的整數(shù)倍,則可以保留除以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編碼(整數(shù)的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,表示后面還有數(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) { // 按照不同的編碼,乘以相應的倍數(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單值編碼壓縮算法源碼解析的詳細內容,更多關于Lucene單值編碼壓縮算法的資料請關注腳本之家其它相關文章!
相關文章
SpringCloud筆記(Hoxton)Netflix之Ribbon負載均衡示例代碼
這篇文章主要介紹了SpringCloud筆記HoxtonNetflix之Ribbon負載均衡,Ribbon是管理HTTP和TCP服務客戶端的負載均衡器,Ribbon具有一系列帶有名稱的客戶端(Named?Client),對SpringCloud?Ribbon負載均衡相關知識感興趣的朋友一起看看吧2022-06-06java監(jiān)聽器實現(xiàn)在線人數(shù)統(tǒng)計
這篇文章主要為大家詳細介紹了java監(jiān)聽器實現(xiàn)在線人數(shù)統(tǒng)計,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2019-11-11metershpere實現(xiàn)調用自定義jar包中的方法
在MeterSphere接口測試中,面對多層循環(huán)邏輯和邏輯判斷等復雜情況,直接編寫測試用例往往顯得混亂不便,本文介紹了一個簡化這一過程的方法:首先使用IDEA創(chuàng)建Maven工程,編寫所需邏輯并生成jar包;然后在MeterSphere中上傳此jar包2024-10-10用3個實例從原理到實戰(zhàn)講清楚Log4j史詩級漏洞
最近應該很多人都在關注著一個漏洞Apache Log4j 2遠程代碼執(zhí)行,該漏洞一旦被攻擊者利用會造成嚴重危害,這篇文章主要給大家介紹了關于如何用3個實例從原理到實戰(zhàn)講清楚Log4j史詩級漏洞的相關資料,需要的朋友可以參考下2021-12-12