一、引言

在進(jìn)行大數(shù)據(jù)開(kāi)發(fā)時(shí)，我們可以使用布隆過(guò)濾器和Redis中的HyperLogLog來(lái)進(jìn)行大數(shù)據(jù)的判重和數(shù)量統(tǒng)計(jì)，雖然這兩種方法節(jié)省內(nèi)存空間并且效率很高，但是也存在一些誤差。如果需要100%準(zhǔn)確的話，我們可以使用BitMap來(lái)存儲(chǔ)數(shù)據(jù)。

BitMap 位圖索引數(shù)據(jù)結(jié)構(gòu)被廣泛地應(yīng)用于數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)搜索中，但是對(duì)于存儲(chǔ)較為分散的數(shù)據(jù)時(shí)，BitMap會(huì)占用比較大的內(nèi)存空間，因此我們更偏向于使用 Roaring BitMap稀疏位圖索引進(jìn)行存儲(chǔ)。同時(shí)，Roaring BitMap廣泛應(yīng)用于數(shù)據(jù)庫(kù)存儲(chǔ)和大數(shù)據(jù)引擎中，例如Hive，Spark，Doris，Kylin等。

下文將分別介紹 BitMap 和 Roaring BitMap 的原理及其相關(guān)應(yīng)用。

二、BitMap原理

BitMap的基本思想就是用bit位來(lái)標(biāo)記某個(gè)元素對(duì)應(yīng)的value，而key就是這個(gè)元素。

例如，在下圖中，是一個(gè)字節(jié)代表的8位，下標(biāo)為1,2,4,6的bit位的值為1，則該字節(jié)表示{1,2,4,6}這幾個(gè)數(shù)。

在Java中，1個(gè)int占用4個(gè)字節(jié)，如果用int來(lái)存儲(chǔ)這四個(gè)數(shù)字的話，那么將需要4 * 4 = 16字節(jié)。

BitMap可以用于快速排序，查找，及去重等操作。優(yōu)點(diǎn)是占用內(nèi)存少（相較于數(shù)組）和運(yùn)算效率高，但是缺點(diǎn)也非常明顯，無(wú)法存儲(chǔ)重復(fù)的數(shù)據(jù)，并且在存儲(chǔ)較為稀疏的數(shù)據(jù)時(shí)，浪費(fèi)存儲(chǔ)空間較多。

三、Roaring BitMap 原理

3.1 存儲(chǔ)方式

為了解決BitMap存儲(chǔ)較為稀疏數(shù)據(jù)時(shí)，浪費(fèi)存儲(chǔ)空間較多的問(wèn)題，我們引入了稀疏位圖索引Roaring BitMap。Roaring BitMap 有較高的計(jì)算性能及壓縮效率。下面簡(jiǎn)單介紹一下Roaring BitMap的基本原理。

Roaring BitMap處理int型整數(shù)，將32位的int型整數(shù)分為高16位和低16位分別進(jìn)行處理，高16位作為索引分片，而低16位用于存儲(chǔ)實(shí)際數(shù)據(jù)。其中每個(gè)索引對(duì)應(yīng)一個(gè)數(shù)據(jù)桶（bucket），那么一共可以包含2^16 = 65536個(gè)數(shù)據(jù)塊。每個(gè)數(shù)據(jù)桶使用container容器來(lái)存儲(chǔ)低16位的部分，每個(gè)數(shù)據(jù)桶最多存儲(chǔ)2^16 = 65536個(gè)數(shù)據(jù)。

如上圖所示，高16位作為索引查找具體的數(shù)據(jù)塊，當(dāng)前索引值為0，低16位作為value進(jìn)行存儲(chǔ)。

Roaring BitMap在進(jìn)行數(shù)據(jù)存儲(chǔ)時(shí)，會(huì)先根據(jù)高16位找到對(duì)應(yīng)的索引key（二分查找），低16位作為key對(duì)應(yīng)的value，先通過(guò)key檢查對(duì)應(yīng)的container容器，如果發(fā)現(xiàn)container不存在的話，就先創(chuàng)建一個(gè)key和對(duì)應(yīng)的container，否則直接將低16位存儲(chǔ)到對(duì)應(yīng)的container中。

Roaring BitMap的精妙之處在于使用不同類型的container，接下來(lái)將對(duì)其進(jìn)行介紹。

3.2 container類型

1.ArrayContainer

顧名思義，ArrayContainer直接采用數(shù)組來(lái)存儲(chǔ)低16位數(shù)據(jù)，沒(méi)有采用任何數(shù)據(jù)壓縮算法，適合存儲(chǔ)比較稀疏的數(shù)據(jù)，在Java中，使用short數(shù)組來(lái)存儲(chǔ)，并且占用的內(nèi)存空間大小和數(shù)據(jù)量成線性關(guān)系。由于short為2字節(jié)，因此n個(gè)數(shù)據(jù)為2n字節(jié)。ArrayContainer采用二分查找定位有序數(shù)組中的元素，因此時(shí)間復(fù)雜度為O(logN)。ArrayContainer的最大數(shù)據(jù)量為4096, 4096 * 2b = 8kb。

2.BitMapContainer

BitMapContainer采用BitMap的原理，就是一個(gè)沒(méi)有經(jīng)過(guò)壓縮處理的普通BitMap，適合存儲(chǔ)比較稠密的數(shù)據(jù)，在Java中使用Long數(shù)組存儲(chǔ)低16位數(shù)據(jù)，每一個(gè)bit位表示一個(gè)數(shù)字。由于每個(gè)container需要存儲(chǔ)2^16 = 65536個(gè)數(shù)據(jù)，如果通過(guò)BitMap進(jìn)行存儲(chǔ)的話，需要使用2^16個(gè)bit進(jìn)行存儲(chǔ)，即8kb的數(shù)據(jù)空間。

可以從下圖中看出ArrayContainer和BitMapContainer的內(nèi)存空間使用關(guān)系，當(dāng)數(shù)據(jù)量小于4096時(shí)，使用ArrayContainer比較合適，當(dāng)數(shù)據(jù)量大于等于4096時(shí)，使用BitMapContainer更佳。

因?yàn)锽itMap直接使用位運(yùn)算，所以BitMapContainer的時(shí)間復(fù)雜度為O(1)。

3.RunContainer

RunContainer采用Run-Length Encoding 行程長(zhǎng)度編碼進(jìn)行壓縮，適合存儲(chǔ)大量連續(xù)數(shù)據(jù)。Java中使用short數(shù)組進(jìn)行存儲(chǔ)。連續(xù)bit位程度越高的話越節(jié)省存儲(chǔ)空間，最佳場(chǎng)景下（65536個(gè)數(shù)據(jù)全為1）只需要存儲(chǔ)4字節(jié)。最差場(chǎng)景為所有數(shù)據(jù)都不連續(xù)，所有存儲(chǔ)數(shù)據(jù)位置為奇數(shù)或者偶數(shù)，這種場(chǎng)景需要存儲(chǔ)128kb。由于采用二分查找算法定位元素，因此時(shí)間復(fù)雜度為O(logN)。

行程長(zhǎng)度編碼即的原理是對(duì)連續(xù)出現(xiàn)的數(shù)字進(jìn)行壓縮，只記錄初始數(shù)字和后續(xù)連續(xù)數(shù)量。

例如：[1,2,3,4,5,8,9,10]使用編碼后的數(shù)據(jù)為[1,4,8,2]。

Java 里可以使用runOptinize()方法來(lái)對(duì)比RunContainer和其他兩個(gè)Container存儲(chǔ)空間大小，如果使用RunContainer存儲(chǔ)空間更佳則會(huì)進(jìn)行轉(zhuǎn)化。

根據(jù)上面三個(gè)Container類型我們可以得知如何進(jìn)行選擇：

1. Container默認(rèn)使用ArrayContainer，當(dāng)元素?cái)?shù)量超過(guò)4096時(shí)，會(huì)由ArrayContainer轉(zhuǎn)換BitMapContainer。
2. 當(dāng)元素?cái)?shù)量小于等于4096時(shí)，BitMapContainer會(huì)逆向轉(zhuǎn)換回ArrayContainer。
3.  正常增刪元素不會(huì)使Container直接變成RunContainer，而需要用戶進(jìn)行優(yōu)化方法調(diào)用才會(huì)轉(zhuǎn)換為最節(jié)省空間的Container。

3.3 Roaring BitMap 相關(guān)源碼

介紹完Roaring BitMap的三種container類型以后，讓我們了解一下，Roaring BitMap的相關(guān)源碼。這里介紹一下Java中增加元素的源碼實(shí)現(xiàn)。

public void add(final int x) {
    final short hb = Util.highbits(x);
    final int i = highLowContainer.getIndex(hb);
    if (i >= 0) {
      highLowContainer.setContainerAtIndex(i,
          highLowContainer.getContainerAtIndex(i).add(Util.lowbits(x)));
    } else {
      final ArrayContainer newac = new ArrayContainer();
      highLowContainer.insertNewKeyValueAt(-i - 1, hb, newac.add(Util.lowbits(x)));
    }
  }

Roaring BitMap首先獲取添加元素的高16位，然后再調(diào)用getIndex獲取高16位對(duì)應(yīng)的索引，如果索引大于0，表示已經(jīng)創(chuàng)建該索引對(duì)應(yīng)的container，故直接添加相應(yīng)的元素低16位即可；否則的話，說(shuō)明該索引對(duì)應(yīng)的container還沒(méi)有被創(chuàng)建，先創(chuàng)建對(duì)應(yīng)的ArrayContainer，再進(jìn)行元素添加。值得一提的是，在getIndex方法中，使用了二分查找來(lái)獲取索引值，所以時(shí)間復(fù)雜度為O(logn)。

// 包含一個(gè)二分查找
protected int getIndex(short x) {
  // 在二分查找之前，我們先對(duì)常見(jiàn)情況優(yōu)化。
  if ((size == 0) || (keys[size - 1] == x)) {
    return size - 1;
  }
  // 沒(méi)有碰到常見(jiàn)情況，我們只能遍歷這個(gè)列表。
  return this.binarySearch(0, size, x);
}

對(duì)于元素添加，三種Container提供了不同的實(shí)現(xiàn)方式，下面將分別介紹。

1. ArrayContainer

if (cardinality == 0 || (cardinality > 0
          && toIntUnsigned(x) > toIntUnsigned(content[cardinality - 1]))) {
    if (cardinality >= DEFAULT_MAX_SIZE) {
      return toBitMapContainer().add(x);
    }
    if (cardinality >= this.content.length) {
      increaseCapacity();
    }
    content[cardinality++] = x;
  } else {
    int loc = Util.unsignedBinarySearch(content, 0, cardinality, x);
    if (loc < 0) {
      // 當(dāng)標(biāo)簽中元素?cái)?shù)量等于默認(rèn)最大值時(shí)，把ArrayContainer轉(zhuǎn)換為BitMapContainer
      if (cardinality >= DEFAULT_MAX_SIZE) {
        return toBitMapContainer().add(x);
      }
      if (cardinality >= this.content.length) {
        increaseCapacity();
      }
      System.arraycopy(content, -loc - 1, content, -loc, cardinality + loc + 1);
      content[-loc - 1] = x;
      ++cardinality;
    }
  }
  return this;
}

ArrayContainer把添加元素分成兩種場(chǎng)景，一種走二分查找，另外一種不走二分查找。

第一種場(chǎng)景：不走二分查找。

當(dāng)基數(shù)為0或者值大于container中的最大值，可以直接添加，因?yàn)閏ontent數(shù)組是有序的，最后一個(gè)是最大值。

當(dāng)基數(shù)大于等于默認(rèn)最大值4096時(shí)，ArrayContainer將轉(zhuǎn)換為BitMapContainer。如果基數(shù)大于content的數(shù)組長(zhǎng)度的話，需要將content進(jìn)行擴(kuò)容。最后進(jìn)行賦值即可。

第二種場(chǎng)景：走二分查找。

先通過(guò)二分查找找到對(duì)應(yīng)的插入位置，如果返回loc大于等于0，說(shuō)明存在，直接返回即可，如果小于0才進(jìn)行后續(xù)插入。后續(xù)操作同上，當(dāng)基數(shù)大于等于默認(rèn)最大值4096時(shí)，ArrayContainer將轉(zhuǎn)換為BitMapContainer。如果基數(shù)大于content的數(shù)組長(zhǎng)度的話，需要將content進(jìn)行擴(kuò)容。最后通過(guò)拷貝數(shù)組將元素插入到content數(shù)組中。

2. BitMapContainer

public Container add(final short i) {
  final int x = Util.toIntUnsigned(i);
  final long previous = BitMap[x / 64];
  long newval = previous | (1L << x);   BitMap[x / 64] = newval;
  if (USE_BRANCHLESS) {
    cardinality += (previous ^ newval) >>> x;
  } else if (previous != newval) {
    ++cardinality;
  }
  return this;
}

BitMap數(shù)組為BitMapContainer的存儲(chǔ)容器存放數(shù)據(jù)的內(nèi)容，數(shù)據(jù)類型為long，在這里我們只需要找到x在BitMap中的位置，并且把相應(yīng)的bit位置1即可。x/64就是找到對(duì)應(yīng)long的舊值，1L<<x 就是把對(duì)應(yīng)的bit位置為1，再跟舊值進(jìn)行或操作，就可以得到新值，再將這個(gè)新值存回到bitmap數(shù)組即可。<="" span="">

3. RunContainer

public Container add(short k) {
   
  int index = unsignedInterleavedBinarySearch(valueslength, 0, nbrruns, k);
  if (index >= 0) {
    return this;// already there
  }
  index = -index - 2;
  if (index >= 0) {
    int offset = toIntUnsigned(k) - toIntUnsigned(getValue(index));
    int le = toIntUnsigned(getLength(index));
    if (offset <= le) {
      return this;
    }
    if (offset == le + 1) {
      // we may need to fuse
      if (index + 1 < nbrruns) {
        if (toIntUnsigned(getValue(index + 1)) == toIntUnsigned(k) + 1) {
          // indeed fusion is needed
          setLength(index,
              (short) (getValue(index + 1) + getLength(index + 1) - getValue(index)));
          recoverRoomAtIndex(index + 1);
          return this;
        }
      }
      incrementLength(index);
      return this;
    }
    if (index + 1 < nbrruns) {
      // we may need to fuse
      if (toIntUnsigned(getValue(index + 1)) == toIntUnsigned(k) + 1) {
        // indeed fusion is needed
        setValue(index + 1, k);
        setLength(index + 1, (short) (getLength(index + 1) + 1));
        return this;
      }
    }
  }
  if (index == -1) {
    // we may need to extend the first run
    if (0 < nbrruns) {
      if (getValue(0) == k + 1) {
        incrementLength(0);
        decrementValue(0);
        return this;
      }
    }
  }
  makeRoomAtIndex(index + 1);
  setValue(index + 1, k);
  setLength(index + 1, (short) 0);
  return this;
}

RunContainer中的兩個(gè)數(shù)據(jù)結(jié)構(gòu)，nbrruns表示有多少段行程，數(shù)據(jù)類型為int，valueslength數(shù)組表示所有的行程，數(shù)據(jù)類型為short。

1. 首先，使用二分查找+順序查找在valueslength數(shù)組中查找元素k的插入位置index。如果查找到的index結(jié)果大于等于0那就說(shuō)明k是某個(gè)行程起始值，已經(jīng)存在，直接返回。
2. -index-2是為了指向前一個(gè)行程起始值的索引。
3. 接下來(lái)是一些偏移量和索引值的判斷，主要是為了確認(rèn)k是否落在上一個(gè)行程里，或者外面，如果落在上一個(gè)行程里，則直接返回，否則需要新建一個(gè)行程或者就近與一個(gè)行程混合并且將行程長(zhǎng)度加1。

3.4 BitMap 和 Roaring BitMap 存儲(chǔ)情況對(duì)比

public static void count(Integer inputSize) {         RoaringBitMap BitMap = new RoaringBitMap();         BitMap.add(0L, inputSize);
 
        //獲取BitMap個(gè)數(shù)
        int cardinality = BitMap.getCardinality();
 
        //獲取BitMap壓縮大小
        int compressSizeIntBytes = BitMap.getSizeInBytes();
 
        //刪除壓縮（移除行程編碼，將container退化為BitMapContainer 或 ArrayContainer）         BitMap.removeRunCompression();
 
        //獲取BitMap不壓縮大小
        int uncompressSizeIntBytes = BitMap.getSizeInBytes();
 
        System.out.println("Roaring BitMap個(gè)數(shù)：" + cardinality);
        System.out.println("最好情況，BitMap壓縮大?。? + compressSizeIntBytes / 1024 + "KB");
        System.out.println("最壞情況，BitMap不壓縮大?。? + uncompressSizeIntBytes / 1024 / 1024 + "MB");
 
        BitSet bitSet = new BitSet();
        for (int i = 0; i < inputSize; i++) {
            bitSet.set(i);
        }
        //獲取BitMap大小
        int size = bitSet.size();
 
        System.out.println("BitMap個(gè)數(shù)：" + bitSet.length());
        System.out.println("BitMap大?。? + size / 8 / 1024 / 1024 + "MB");
    }

上述代碼使用了Java內(nèi)置的BitMap(BitSet) 和 Roaring BitMap進(jìn)行存儲(chǔ)大小對(duì)比，輸出結(jié)果如下所示。

• Roaring BitMap個(gè)數(shù)：1000000000
• 最好情況，BitMap壓縮大?。?49KB
• 最壞情況，BitMap不壓縮大?。?19MB
• Roaring BitMap個(gè)數(shù)：1000000000
• BitMap大?。?28MB

可以發(fā)現(xiàn)，Roaring BitMap的壓縮性能效果非常好，同等情況下，是BitMap占用內(nèi)存的近一千分之一。在退化成BitMapContainer/arrayContainer之后也仍然比使用基本的BitMap存儲(chǔ)效果好一些。

四、Roaring BitMap 使用

4.1 Java 中相關(guān) API 使用

在Java中，Roaring BitMap提供了交并補(bǔ)差集等操作，如下代碼所示，列舉了Java中roaing BitMap的相關(guān)API使用方式。

//添加單個(gè)數(shù)字
public void add(final int x)


//添加范圍數(shù)字
public void add(final long rangeStart, final long rangeEnd)


//移除數(shù)字
public void remove(final int x)


//遍歷RBM
public void forEach(IntConsumer ic)


//檢測(cè)是否包含
public boolean contains(final int x)


//獲取基數(shù)
public int getCardinality()


//位與，取兩個(gè)RBM的交集，當(dāng)前RBM會(huì)被修改
public void and(final RoaringBitMap x2)


//同上，但是會(huì)返回一個(gè)新的RBM，不會(huì)修改原始的RBM，線程安全
public static RoaringBitMap and(final RoaringBitMap x1, final RoaringBitMap x2)


//位或，取兩個(gè)RBM的并集，當(dāng)前RBM會(huì)被修改
public void or(final RoaringBitMap x2)


//同上，但是會(huì)返回一個(gè)新的RBM，不會(huì)修改原始的RBM，線程安全
public static RoaringBitMap or(final RoaringBitMap x1, final RoaringBitMap x2)


//異或，取兩個(gè)RBM的對(duì)稱差，當(dāng)前RBM會(huì)被修改
public void xor(final RoaringBitMap x2)


//同上，但是會(huì)返回一個(gè)新的RBM，不會(huì)修改原始的RBM，線程安全
public static RoaringBitMap xor(final RoaringBitMap x1, final RoaringBitMap x2)


//取原始值和x2的差集，當(dāng)前RBM會(huì)被修改
public void andNot(final RoaringBitMap x2)


//同上，但是會(huì)返回一個(gè)新的RBM，不會(huì)修改原始的RBM，線程安全
public static RoaringBitMap andNot(final RoaringBitMap x1, final RoaringBitMap x2)


//序列化
public void serialize(DataOutput out) throws IOException
public void serialize(ByteBuffer buffer)


//反序列化
public void deserialize(DataInput in) throws IOException
public void deserialize(ByteBuffer bbf) throws IOException

對(duì)于序列化來(lái)說(shuō)，Roaring BitMap官方定義了一套序列化規(guī)則，用來(lái)保證不同語(yǔ)言實(shí)現(xiàn)的兼容性。

Java中可以使用serialize方法進(jìn)行序列化，deserialize方法進(jìn)行反序列化。

4.2 業(yè)務(wù)實(shí)際場(chǎng)景應(yīng)用

Roaring BitMap可以用來(lái)構(gòu)建大數(shù)據(jù)標(biāo)簽，針對(duì)類型特征來(lái)創(chuàng)建對(duì)應(yīng)的標(biāo)簽。

在我們的業(yè)務(wù)場(chǎng)景中，有很多需要基于人群標(biāo)簽進(jìn)行交并補(bǔ)集運(yùn)算的場(chǎng)景，下面以一個(gè)場(chǎng)景為例，我們需要計(jì)算每天某個(gè)設(shè)備接口 在設(shè)備標(biāo)簽A上的查詢成功率，因?yàn)樵O(shè)備標(biāo)簽A中的設(shè)備不是所有都活躍在網(wǎng)的，所以我們需要將設(shè)備標(biāo)簽A與每日日活人群標(biāo)簽取交集，得到的交集大小才能用作成功率計(jì)算的分母，另外拿查詢成功的標(biāo)簽人群做分子來(lái)進(jìn)行計(jì)算即可，查詢時(shí)長(zhǎng)耗時(shí)為1s。

假如沒(méi)有使用標(biāo)簽保存集合之前，我們需要在hive表中查詢出同時(shí)滿足當(dāng)天在網(wǎng)的活躍用戶和設(shè)備A的用戶數(shù)量，查詢時(shí)長(zhǎng)耗時(shí)在幾分鐘以上。兩種方式相比之下，使用Roaring BitMap查詢的效率更高。

五、總結(jié)

本文結(jié)合個(gè)人理解梳理了BitMap及Roaring BitMap的原理及使用，分別主要介紹了Roaring BitMap的存儲(chǔ)方式及三種container類型及Java中Roaring BitMap相關(guān)API使用，如有不足和優(yōu)化建議，也歡迎大家批評(píng)指正。

參考資料：

• Chambi S , Lemire D , Kaser O , et al.
  Better BitMap performance with Roaring 
  BitMaps[J]. Software—practice & Experience, 2016, 46(5):709-719.
• https://RoaringBitMap.org/
• https://github.com/RoaringBitMap/RoaringFormatSpec