作者：京東科技 曹留界
在人群本地化實(shí)踐中我們介紹了人群ID中所有的pin的偏移量可以通過(guò)Bitmap存儲(chǔ)，而B(niǎo)itmap所占用的空間大小只與偏移量的最大值有關(guān)系。假如現(xiàn)在要向Bitmap內(nèi)存入兩個(gè)pin對(duì)應(yīng)的偏移量，一個(gè)偏移量為1，另一個(gè)偏移量為100w，那么Bitmap存儲(chǔ)直接需要100w bit的空間嗎？數(shù)據(jù)部將偏移量存入Bitmap時(shí)，又如何解決數(shù)據(jù)稀疏問(wèn)題呢？本文將為大家解答這個(gè)問(wèn)題。
一、BitMap
Bitmap的基本思想就是用一個(gè)bit位來(lái)標(biāo)記某個(gè)元素對(duì)應(yīng)的Value，而Key即是該元素。由于采用了Bit為單位來(lái)存儲(chǔ)數(shù)據(jù)，因此可以大大節(jié)省存儲(chǔ)空間。
如果想將數(shù)字2存入位圖中，則只需要將位圖數(shù)組中下標(biāo)為2的數(shù)組值置為1。
但是，如果現(xiàn)在要存儲(chǔ)兩個(gè)人群ID對(duì)應(yīng)的偏移量，一個(gè)偏移量為1，另一個(gè)偏移量為100w，如果將這兩個(gè)值直接放到位圖數(shù)組中，那么位圖數(shù)組所需要的空間就是100wbit，會(huì)產(chǎn)生大量的空間浪費(fèi)。那么有什么方法可以避免空間浪費(fèi)嗎？答案就是RoaringBitMap！
二、RoaringBitMap
RoaringBitMap是一種高效壓縮位圖，簡(jiǎn)稱(chēng)RBM。RBM的概念于2016年由S. Chambi、D. Lemire、O. Kaser等人在論文《Better bitmap performance with Roaring bitmaps》 《Consistently faster and smaller compressed bitmaps with Roaring》中提出。下面我們結(jié)合JAVA中的實(shí)現(xiàn)對(duì)其進(jìn)行介紹。
2.1 實(shí)現(xiàn)思路
RBM主要將32位的整型（int）分為高16位和低16位（兩個(gè)short），其中高16位對(duì)應(yīng)的數(shù)字使用16位整型有序數(shù)組存儲(chǔ)，低16位根據(jù)不同的情況選擇三種不同的container來(lái)存儲(chǔ)，這三種container分別為：
•Array Container
底層數(shù)據(jù)結(jié)構(gòu)為short類(lèi)型的數(shù)組，直接將數(shù)字低16位的值存儲(chǔ)到該數(shù)組中。short類(lèi)型的數(shù)組始終保持有序，方便使用二分查找，且不會(huì)存儲(chǔ)重復(fù)數(shù)值。因?yàn)檫@種Container存儲(chǔ)數(shù)據(jù)沒(méi)有任何壓縮，因此只適合存儲(chǔ)少量數(shù)據(jù)。其內(nèi)部數(shù)組容量是動(dòng)態(tài)變化的，當(dāng)容量不夠時(shí)會(huì)進(jìn)行擴(kuò)容，最大容量為4096。由于數(shù)組是有序的，存儲(chǔ)和查詢(xún)時(shí)都可以通過(guò)二分查找快速定位其在數(shù)組中的位置。
ArrayContainer占用的空間大小與存儲(chǔ)的數(shù)據(jù)量為線性關(guān)系，每個(gè)short為2字節(jié)，因此存儲(chǔ)了N個(gè)數(shù)據(jù)的ArrayContainer占用空間大致為2N字節(jié)。存儲(chǔ)一個(gè)數(shù)據(jù)占用2字節(jié)，存儲(chǔ)4096個(gè)數(shù)據(jù)占用8kb。
•Bitmap Container
底層實(shí)現(xiàn)為位圖。這種Container使用long[]存儲(chǔ)位圖數(shù)據(jù)。我們知道，每個(gè)Container處理16位整形的數(shù)據(jù)，也就是0~65535，因此根據(jù)位圖的原理，需要65536個(gè)比特來(lái)存儲(chǔ)數(shù)據(jù)，每個(gè)比特位用1來(lái)表示有，0來(lái)表示無(wú)。每個(gè)long有64位，因此需要1024個(gè)long來(lái)提供65536個(gè)比特。
因此，每個(gè)BitmapContainer在構(gòu)建時(shí)就會(huì)初始化長(zhǎng)度為1024的long[]。這就意味著，不管一個(gè)BitmapContainer中只存儲(chǔ)了1個(gè)數(shù)據(jù)還是存儲(chǔ)了65536個(gè)數(shù)據(jù)，占用的空間都是同樣的8kb。
•Run Container
RunContainer中的Run指的是行程長(zhǎng)度壓縮算法(Run Length Encoding)，對(duì)連續(xù)數(shù)據(jù)有比較好的壓縮效果。
它的原理是，對(duì)于連續(xù)出現(xiàn)的數(shù)字，只記錄初始數(shù)字和后續(xù)數(shù)量。即：
•對(duì)于數(shù)列11，它會(huì)壓縮為11,0；
•對(duì)于數(shù)列11,12,13,14,15，它會(huì)壓縮為11,4；
•對(duì)于數(shù)列11,12,13,14,15,21,22，它會(huì)壓縮為11,4,21,1；
源碼中的short[] valueslength中存儲(chǔ)的就是壓縮后的數(shù)據(jù)。
這種壓縮算法的性能和數(shù)據(jù)的連續(xù)性（緊湊性）關(guān)系極為密切，對(duì)于連續(xù)的100個(gè)short，它能從200字節(jié)壓縮為4字節(jié)，但對(duì)于完全不連續(xù)的100個(gè)short，編碼完之后反而會(huì)從200字節(jié)變?yōu)?00字節(jié)。
如果要分析RunContainer的容量，我們可以做下面兩種極端的假設(shè)：
最好情況，即只存在一個(gè)數(shù)據(jù)或只存在一串連續(xù)數(shù)字，那么只會(huì)存儲(chǔ)2個(gè)short，占用4字節(jié)
最壞情況，0~65535的范圍內(nèi)填充所有的奇數(shù)位（或所有偶數(shù)位），需要存儲(chǔ)65536個(gè)short，128kb
也就RBM在存入一個(gè)32位的整形數(shù)字時(shí)，會(huì)先按照該數(shù)字的高16位進(jìn)行分桶，以確定該數(shù)字要存入到哪個(gè)桶中。確定好分桶位置后，再將該數(shù)字對(duì)應(yīng)的低16位放入到當(dāng)前桶所對(duì)應(yīng)的container中。
舉個(gè)栗子
以十進(jìn)制數(shù)字131122為例，現(xiàn)在我們要將該數(shù)字放入到RBM中。第一步，先將該數(shù)字轉(zhuǎn)換為16進(jìn)制，131122對(duì)應(yīng)的十六進(jìn)制為0x00020032；其中，高十六位對(duì)應(yīng)0x0002，首先我們找到0x0002所在的桶，再將131122的低16位存入到對(duì)應(yīng)的container中，131122的低16位轉(zhuǎn)換為10進(jìn)制就是50，沒(méi)有超過(guò)ArrayContainer的容量4096，所以將低16位直接放入到對(duì)應(yīng)的ArrayContainer中。
如果要插入的數(shù)字低16位超過(guò)了4096，RBM會(huì)將ArrayContainer轉(zhuǎn)換為BitMapContainer。反之，如果數(shù)據(jù)在刪除之后，數(shù)組中的最大數(shù)據(jù)小于4096，RBM會(huì)將BitMapContainer轉(zhuǎn)換回ArrayContainer。
RBM處理的是32位的數(shù)字，如果我們想處理Long類(lèi)型的數(shù)字怎么辦呢？這個(gè)時(shí)候可以使用Roaring64NavigableMap。Roaring64NavigableMap也是使用拆分模式，將一個(gè)long類(lèi)型數(shù)據(jù)，拆分為高32位與低32位，高32位代表索引，低32位存儲(chǔ)到對(duì)應(yīng)RoaringBitmap中，其內(nèi)部是一個(gè)TreeMap類(lèi)型的結(jié)構(gòu)，會(huì)按照signed或者unsigned進(jìn)行排序，key代表高32位，value代表對(duì)應(yīng)的RoaringBitmap。
三、空間占用對(duì)比
1、連續(xù)數(shù)據(jù)
分別向位圖中插入1w、10w、100w、1000w條連續(xù)數(shù)據(jù)，并且對(duì)比BitMap和RoaringBitMap占用空間的大小。比較結(jié)果如下表所示：
10w數(shù)據(jù)占用空間 100w數(shù)據(jù)占用空間 1000w數(shù)據(jù)占用空間 BitMap 97.7KB 976.6KB 9.5MB RoaringBitMap 16KB 128KB 1.2MB @Test
public void testSizeOfBitMap() {
//對(duì)比占用空間大小 - 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數(shù)據(jù) roaringbitmap byte size:"+ roaringBitmap3.getSizeInBytes());
System.out.println("10w數(shù)據(jù) 位圖數(shù)組 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數(shù)據(jù) roaringbitmap byte size:"+ roaringBitmap4.getSizeInBytes());
System.out.println("100w數(shù)據(jù) 位圖數(shù)組 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數(shù)據(jù) roaringbitmap byte size:"+ roaringBitmap5.getSizeInBytes());
System.out.println("1000w數(shù)據(jù) 位圖數(shù)組 byte size:"+bits4.length);
}
運(yùn)行截圖：
2、稀疏數(shù)據(jù)
我們知道，位圖所占用空間大小只和位圖中索引的最大值有關(guān)系，現(xiàn)在我們向位圖中插入1和999w兩個(gè)偏移量位的元素，再次對(duì)比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("兩個(gè)稀疏數(shù)據(jù) roaringbitmap byte size:"+ roaringBitmap5.getSizeInBytes());
System.out.println("兩個(gè)稀疏數(shù)據(jù) 位圖數(shù)組 byte size:"+bits4.length);
}
運(yùn)行截圖：
