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);
}運行截圖：
