作者：京東科技 曹留界

在人群本地化實踐中我們介紹了人群ID中所有的pin的偏移量可以通過Bitmap存儲，而Bitmap所占用的空間大小只與偏移量的最大值有關系。假如現(xiàn)在要向Bitmap內(nèi)存入兩個pin對應的偏移量，一個偏移量為1，另一個偏移量為100w，那么Bitmap存儲直接需要100w bit的空間嗎？數(shù)據(jù)部將偏移量存入Bitmap時，又如何解決數(shù)據(jù)稀疏問題呢？本文將為大家解答這個問題。

一、BitMap

Bitmap的基本思想就是用一個bit位來標記某個元素對應的Value，而Key即是該元素。由于采用了Bit為單位來存儲數(shù)據(jù)，因此可以大大節(jié)省存儲空間。

如果想將數(shù)字2存入位圖中，則只需要將位圖數(shù)組中下標為2的數(shù)組值置為1。

但是，如果現(xiàn)在要存儲兩個人群ID對應的偏移量，一個偏移量為1，另一個偏移量為100w，如果將這兩個值直接放到位圖數(shù)組中，那么位圖數(shù)組所需要的空間就是100wbit，會產(chǎn)生大量的空間浪費。那么有什么方法可以避免空間浪費嗎？答案就是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》中提出。下面我們結(jié)合java中的實現(xiàn)對其進行介紹。

2.1 實現(xiàn)思路

RBM主要將32位的整型（int）分為高16位和低16位（兩個short），其中高16位對應的數(shù)字使用16位整型有序數(shù)組存儲，低16位根據(jù)不同的情況選擇三種不同的container來存儲，這三種container分別為：

?Array Container

底層數(shù)據(jù)結(jié)構(gòu)為short類型的數(shù)組，直接將數(shù)字低16位的值存儲到該數(shù)組中。short類型的數(shù)組始終保持有序，方便使用二分查找，且不會存儲重復數(shù)值。因為這種Container存儲數(shù)據(jù)沒有任何壓縮，因此只適合存儲少量數(shù)據(jù)。其內(nèi)部數(shù)組容量是動態(tài)變化的，當容量不夠時會進行擴容，最大容量為4096。由于數(shù)組是有序的，存儲和查詢時都可以通過二分查找快速定位其在數(shù)組中的位置。

ArrayContainer占用的空間大小與存儲的數(shù)據(jù)量為線性關系，每個short為2字節(jié)，因此存儲了N個數(shù)據(jù)的ArrayContainer占用空間大致為2N字節(jié)。存儲一個數(shù)據(jù)占用2字節(jié)，存儲4096個數(shù)據(jù)占用8kb。

?Bitmap Container

底層實現(xiàn)為位圖。這種Container使用long[]存儲位圖數(shù)據(jù)。我們知道，每個Container處理16位整形的數(shù)據(jù)，也就是0~65535，因此根據(jù)位圖的原理，需要65536個比特來存儲數(shù)據(jù)，每個比特位用1來表示有，0來表示無。每個long有64位，因此需要1024個long來提供65536個比特。

因此，每個BitmapContainer在構(gòu)建時就會初始化長度為1024的long[]。這就意味著，不管一個BitmapContainer中只存儲了1個數(shù)據(jù)還是存儲了65536個數(shù)據(jù)，占用的空間都是同樣的8kb。

?Run Container

RunContainer中的Run指的是行程長度壓縮算法(Run Length Encoding)，對連續(xù)數(shù)據(jù)有比較好的壓縮效果。

它的原理是，對于連續(xù)出現(xiàn)的數(shù)字，只記錄初始數(shù)字和后續(xù)數(shù)量。即：

?對于數(shù)列11，它會壓縮為11,0；

?對于數(shù)列11,12,13,14,15，它會壓縮為11,4；

?對于數(shù)列11,12,13,14,15,21,22，它會壓縮為11,4,21,1；

源碼中的short[] valueslength中存儲的就是壓縮后的數(shù)據(jù)。

這種壓縮算法的性能和數(shù)據(jù)的連續(xù)性（緊湊性）關系極為密切，對于連續(xù)的100個short，它能從200字節(jié)壓縮為4字節(jié)，但對于完全不連續(xù)的100個short，編碼完之后反而會從200字節(jié)變?yōu)?00字節(jié)。

如果要分析RunContainer的容量，我們可以做下面兩種極端的假設：

最好情況，即只存在一個數(shù)據(jù)或只存在一串連續(xù)數(shù)字，那么只會存儲2個short，占用4字節(jié)

最壞情況，0~65535的范圍內(nèi)填充所有的奇數(shù)位（或所有偶數(shù)位），需要存儲65536個short，128kb

也就RBM在存入一個32位的整形數(shù)字時，會先按照該數(shù)字的高16位進行分桶，以確定該數(shù)字要存入到哪個桶中。確定好分桶位置后，再將該數(shù)字對應的低16位放入到當前桶所對應的container中。

舉個栗子

以十進制數(shù)字131122為例，現(xiàn)在我們要將該數(shù)字放入到RBM中。第一步，先將該數(shù)字轉(zhuǎn)換為16進制，131122對應的十六進制為0x00020032；其中，高十六位對應0x0002，首先我們找到0x0002所在的桶，再將131122的低16位存入到對應的container中，131122的低16位轉(zhuǎn)換為10進制就是50，沒有超過ArrayContainer的容量4096，所以將低16位直接放入到對應的ArrayContainer中。

如果要插入的數(shù)字低16位超過了4096，RBM會將ArrayContainer轉(zhuǎn)換為BitMapContainer。反之，如果數(shù)據(jù)在刪除之后，數(shù)組中的最大數(shù)據(jù)小于4096，RBM會將BitMapContainer轉(zhuǎn)換回ArrayContainer。

RBM處理的是32位的數(shù)字，如果我們想處理Long類型的數(shù)字怎么辦呢？這個時候可以使用Roaring64NavigableMap。Roaring64NavigableMap也是使用拆分模式，將一個long類型數(shù)據(jù)，拆分為高32位與低32位，高32位代表索引，低32位存儲到對應RoaringBitmap中，其內(nèi)部是一個TreeMap類型的結(jié)構(gòu)，會按照signed或者unsigned進行排序，key代表高32位，value代表對應的RoaringBitmap。

三、空間占用對比

1、連續(xù)數(shù)據(jù)

分別向位圖中插入1w、10w、100w、1000w條連續(xù)數(shù)據(jù)，并且對比BitMap和RoaringBitMap占用空間的大小。比較結(jié)果如下表所示：

@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數(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);
    }

運行截圖：

2、稀疏數(shù)據(jù)

我們知道，位圖所占用空間大小只和位圖中索引的最大值有關系，現(xiàn)在我們向位圖中插入1和999w兩個偏移量位的元素，再次對比BitMap和RoaringBitMap所占用空間大小。

@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("兩個稀疏數(shù)據(jù) roaringbitmap byte size:"+ roaringBitmap5.getSizeInBytes());
        System.out.println("兩個稀疏數(shù)據(jù) 位圖數(shù)組 byte size:"+bits4.length);
    }

運行截圖：