Bitmap、RoaringBitmap原理分析
作者:京東科技 曹留界
在人羣本地化實踐中我們介紹了人羣ID中所有的pin的偏移量可以通過Bitmap存儲,而Bitmap所佔用的空間大小隻與偏移量的最大值有關係。假如現在要向Bitmap內存入兩個pin對應的偏移量,一個偏移量為1,另一個偏移量為100w,那麼Bitmap存儲直接需要100w bit的空間嗎?數據部將偏移量存入Bitmap時,又如何解決數據稀疏問題呢?本文將為大家解答這個問題。
一、BitMap
Bitmap的基本思想就是用一個bit位來標記某個元素對應的Value,而Key即是該元素。由於採用了Bit為單位來存儲數據,因此可以大大節省存儲空間。
如果想將數字2存入位圖中,則只需要將位圖數組中下標為2的數組值置為1。
但是,如果現在要存儲兩個人羣ID對應的偏移量,一個偏移量為1,另一個偏移量為100w,如果將這兩個值直接放到位圖數組中,那麼位圖數組所需要的空間就是100wbit,會產生大量的空間浪費。那麼有什麼方法可以避免空間浪費嗎?答案就是RoaringBitMap!
二、RoaringBitMap
RoaringBitMap是一種高效壓縮位圖,簡稱RBM。RBM的概念於2016年由S. Chambi、D. Lemire、O. Kaser等人在論文《Better bitmap performance with Roaring bitmaps》 《Consistently faster and smaller compressed bitmaps with Roaring》中提出。下面我們結合java中的實現對其進行介紹。
2.1 實現思路
RBM主要將32位的整型(int)分為高16位和低16位(兩個short),其中高16位對應的數字使用16位整型有序數組存儲,低16位根據不同的情況選擇三種不同的container來存儲,這三種container分別為:
•Array Container
底層數據結構為short類型的數組,直接將數字低16位的值存儲到該數組中。short類型的數組始終保持有序,方便使用二分查找,且不會存儲重複數值。因為這種Container存儲數據沒有任何壓縮,因此只適合存儲少量數據。其內部數組容量是動態變化的,當容量不夠時會進行擴容,最大容量為4096。由於數組是有序的,存儲和查詢時都可以通過二分查找快速定位其在數組中的位置。
ArrayContainer佔用的空間大小與存儲的數據量為線性關係,每個short為2字節,因此存儲了N個數據的ArrayContainer佔用空間大致為2N字節。存儲一個數據佔用2字節,存儲4096個數據佔用8kb。
•Bitmap Container
底層實現為位圖。這種Container使用long[]存儲位圖數據。我們知道,每個Container處理16位整形的數據,也就是0~65535,因此根據位圖的原理,需要65536個比特來存儲數據,每個比特位用1來表示有,0來表示無。每個long有64位,因此需要1024個long來提供65536個比特。
因此,每個BitmapContainer在構建時就會初始化長度為1024的long[]。這就意味着,不管一個BitmapContainer中只存儲了1個數據還是存儲了65536個數據,佔用的空間都是同樣的8kb。
•Run Container
RunContainer中的Run指的是行程長度壓縮算法(Run Length Encoding),對連續數據有比較好的壓縮效果。
它的原理是,對於連續出現的數字,只記錄初始數字和後續數量。即:
•對於數列11
,它會壓縮為11,0
;
•對於數列11,12,13,14,15
,它會壓縮為11,4
;
•對於數列11,12,13,14,15,21,22
,它會壓縮為11,4,21,1
;
源碼中的short[] valueslength中存儲的就是壓縮後的數據。
這種壓縮算法的性能和數據的連續性(緊湊性)關係極為密切,對於連續的100個short,它能從200字節壓縮為4字節,但對於完全不連續的100個short,編碼完之後反而會從200字節變為400字節。
如果要分析RunContainer的容量,我們可以做下面兩種極端的假設:
最好情況,即只存在一個數據或只存在一串連續數字,那麼只會存儲2個short,佔用4字節
最壞情況,0~65535的範圍內填充所有的奇數位(或所有偶數位),需要存儲65536個short,128kb
也就RBM在存入一個32位的整形數字時,會先按照該數字的高16位進行分桶,以確定該數字要存入到哪個桶中。確定好分桶位置後,再將該數字對應的低16位放入到當前桶所對應的container中。
舉個栗子
以十進制數字131122為例,現在我們要將該數字放入到RBM中。第一步,先將該數字轉換為16進制,131122對應的十六進制為0x00020032;其中,高十六位對應0x0002,首先我們找到0x0002所在的桶,再將131122的低16位存入到對應的container中,131122的低16位轉換為10進制就是50,沒有超過ArrayContainer的容量4096,所以將低16位直接放入到對應的ArrayContainer中。
如果要插入的數字低16位超過了4096,RBM會將ArrayContainer轉換為BitMapContainer。反之,如果數據在刪除之後,數組中的最大數據小於4096,RBM會將BitMapContainer轉換回ArrayContainer。
RBM處理的是32位的數字,如果我們想處理Long類型的數字怎麼辦呢?這個時候可以使用Roaring64NavigableMap。Roaring64NavigableMap也是使用拆分模式,將一個long類型數據,拆分為高32位與低32位,高32位代表索引,低32位存儲到對應RoaringBitmap中,其內部是一個TreeMap類型的結構,會按照signed或者unsigned進行排序,key代表高32位,value代表對應的RoaringBitmap。
三、空間佔用對比
1、連續數據
分別向位圖中插入1w、10w、100w、1000w條連續數據,並且對比BitMap和RoaringBitMap佔用空間的大小。比較結果如下表所示:
10w數據佔用空間 | 100w數據佔用空間 | 1000w數據佔用空間 | |
---|---|---|---|
BitMap | 97.7KB | 976.6KB | 9.5MB |
RoaringBitMap | 16KB | 128KB | 1.2MB |
@Test
public void testSizeOfBitMap() {
//對比佔用空間大小 - 10w元素
RoaringBitmap roaringBitmap3 = new RoaringBitmap();
byte[] bits2 = new byte[100000];
for (int i = 0; i < 100000; i++) {
roaringBitmap3.add(i);
bits2[i] = (byte) i;
}
System.out.println("10w數據 roaringbitmap byte size:"+ roaringBitmap3.getSizeInBytes());
System.out.println("10w數據 位圖數組 byte size:"+bits2.length);
RoaringBitmap roaringBitmap4 = new RoaringBitmap();
byte[] bits3 = new byte[1000000];
for (int i = 0; i < 1000000; i++) {
roaringBitmap4.add(i);
bits3[i] = (byte) i;
}
System.out.println("100w數據 roaringbitmap byte size:"+ roaringBitmap4.getSizeInBytes());
System.out.println("100w數據 位圖數組 byte size:"+bits3.length);
RoaringBitmap roaringBitmap5 = new RoaringBitmap();
byte[] bits4 = new byte[10000000];
for (int i = 0; i < 10000000; i++) {
roaringBitmap5.add(i);
bits4[i] = (byte) i;
}
System.out.println("1000w數據 roaringbitmap byte size:"+ roaringBitmap5.getSizeInBytes());
System.out.println("1000w數據 位圖數組 byte size:"+bits4.length);
}
運行截圖:
2、稀疏數據
我們知道,位圖所佔用空間大小隻和位圖中索引的最大值有關係,現在我們向位圖中插入1和999w兩個偏移量位的元素,再次對比BitMap和RoaringBitMap所佔用空間大小。
佔用空間 | |
---|---|
BitMap | 9.5MB |
RoaringBitMap | 24Byte |
@Test
public void testSize() {
RoaringBitmap roaringBitmap5 = new RoaringBitmap();
byte[] bits4 = new byte[10000000];
for (int i = 0; i < 10000000; i++) {
if (i == 1 || i == 9999999) {
roaringBitmap5.add(i);
bits4[i] = (byte) i;
}
}
System.out.println("兩個稀疏數據 roaringbitmap byte size:"+ roaringBitmap5.getSizeInBytes());
System.out.println("兩個稀疏數據 位圖數組 byte size:"+bits4.length);
}
運行截圖:
- 應用健康度隱患刨析解決系列之數據庫時區設置
- 對於Vue3和Ts的心得和思考
- 一文詳解擴散模型:DDPM
- zookeeper的Leader選舉源碼解析
- 一文帶你搞懂如何優化慢SQL
- 京東金融Android瘦身探索與實踐
- 微前端框架single-spa子應用加載解析
- cookie時效無限延長方案
- 聊聊前端性能指標那些事兒
- Spring竟然可以創建“重複”名稱的bean?—一次項目中存在多個bean名稱重複問題的排查
- 京東金融Android瘦身探索與實踐
- Spring源碼核心剖析
- 深入淺出RPC服務 | 不同層的網絡協議
- 安全測試之探索windows遊戲掃雷
- 關於數據庫分庫分表的一點想法
- 對於Vue3和Ts的心得和思考
- Bitmap、RoaringBitmap原理分析
- 京東小程序CI工具實踐
- 測試用例設計指南
- 當你對 redis 説你中意的女孩是 Mia