貨拉拉巨量資料對BitMap的探索實踐詳解

關於Bitmap

在巨量資料時代，想要不斷提升基於海量資料獲取的決策、洞察發現和流程優化等能力，就需要不停思考，如何在利用有限的資源實現高效穩定地產出可信且豐富的資料，從而提高賦能下游產品的效率以及效果。在貨拉拉數倉構建過程中，我們不斷探索各種方式來實現降本提效。例如在一些場景下，利用Bitmap去提升下游的資料使用體驗，並達成我們想要的降本提效的目的。

為了更好的展示Bitmap在貨拉拉實踐應用中的探索與實踐，我們分了兩篇文章來介紹，本文主要介紹Bitmap的實現原理與應用優化，以及在一些常見業務場景中的實踐應用，讓大家在面對相應場景的時候，能夠有一個區別於傳統的解決方案的新思路。下一篇文章則是重點介紹Bitmap在貨拉拉中的具體落地，以及使用時遇到的一些痛點和對應解決方案。

首先從Bitmap開始說起，這裡採用經典的WWH結構，讓不熟悉的小夥伴能夠快速瞭解掌握。

What

BitMap，即點陣圖，是比較常見的資料結構，簡單來說就是按位元儲存，主要為了解決在去重場景裡面巨量資料量儲存的問題。本質其實就是雜湊表的一種應用實現，使用每個位來表示某個數位。

舉個例子

假設有個1，3，5，7的數位集合，如果常規的儲存方法，要用4個Int的空間。其中一個Int就是32位元的空間。3個就是4*32Bit，相當於16個位元組。

如果用Bitmap儲存呢，只用8Bit（1個位元組）就夠了。bitmap通過使用每一bit位代表一個數，位號就是數值，1標識有，0標識無。如下所示：

BitMap的簡單實現

對於 BitMap 這種經典的資料結構，在 Java 語言裡面，其實已經有對應實現的資料結構類 java.util.BitSet 了，而 BitSet 的底層原理，其實就是用 long 型別的陣列來儲存元素，因為使用的是long型別的陣列，而 1 long = 64 bit，所以資料大小會是64的整數倍。這樣看可能很難理解，下面參考bitmap原始碼寫了一個例子，並寫上了詳細的備註，方便理解

import java.util.Arrays;
public class BitMap {
    // 用 byte 陣列儲存資料
    private byte[] bits;
    // 指定 bitMap的長度
    private int bitSize;
    // bitmap構造器
    public BitMap(int bitSize) {
        this.bitSize = (bitSize >> 3) + 1;
        //1byte 能儲存8個資料，那麼要儲存 bitSize的長度需要多少個bit呢，bitSize/8+1,右移3位相當於除以8
        bits = new byte[(bitSize >> 3) + 1];
    }
    // 在bitmap中插入數位
    public void add(int num) {
        // num/8得到byte[]的index
        int arrayIndex = num >> 3;
        // num%8得到在byte[index]的位置
        int position = num & 0x07;
        //將1左移position後，那個位置自然就是1，然後和以前的資料做|，這樣，那個位置就替換成1了。
        bits[arrayIndex] |= 1 << position;
    }
    // 判斷bitmap中是否包含某數位
    public boolean contain(int num) {
        // num/8得到byte[]的index
        int arrayIndex = num >> 3;
        // num%8得到在byte[index]的位置
        int position = num & 0x07;
        //將1左移position後，那個位置自然就是1，然後和以前的資料做&，判斷是否為0即可
        return (bits[arrayIndex] & (1 << position)) != 0;
    }
    // 清除bitmap中的某個數位
    public void clear(int num) {
        // num/8得到byte[]的index
        int arrayIndex = num >> 3;
        // num%8得到在byte[index]的位置
        int position = num & 0x07;
        //將1左移position後，那個位置自然就是1，然後對取反，再與當前值做&，即可清除當前的位置了.
        bits[arrayIndex] &= ~(1 << position);
    }
    // 列印底層bit儲存
    public static void printBit(BitMap bitMap) {
        int index=bitMap.bitSize & 0x07;
        for (int j = 0; j < index; j++) {
            System.out.print("byte["+j+"] 的底層儲存：");
            byte num = bitMap.bits[j];
            for (int i = 7; i >= 0; i--) {
                System.out.print((num & (1 << i)) == 0 ? "0" : "1");
            }
            System.out.println();
        }
    }
    // 輸出陣列元素，也可以使用Arrays的toString方法
    private static void printArray(int[] arr) {
        System.out.print("陣列元素：");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
}

下面就來簡單玩一玩這個自制的BitMap，先嚐試插入一個3，並清理掉它，看看底層二進位制結構是怎樣變化的

public static void main(String[] args) {
    // 簡單試驗
    BitMap bitmap = new BitMap(3);
    bitmap.add(3);
    System.out.println("插入3成功");
    boolean isexsit = bitmap.contain(3);
    System.out.println("3是否存在:" + isexsit);
    printBit(bitmap);
    bitmap.clear(3);
    isexsit = bitmap.contain(3);
    System.out.println("3是否存在:" + isexsit);
    printBit(bitmap);
}

輸出結果如下：

再通過陣列，插入多個元素看看效果

public static void main(String[] args) {
    // 陣列試驗
    int[] arr = {8,3,3,4,9};
    printArray(arr);
    int size = Arrays.stream(arr).max().getAsInt();
    BitMap b = new BitMap(size);
    for (int i = 0; i < arr.length; i++) {
        b.add(arr[i]);
    }
    printBit(b);
}

輸出結果如下：

BitSet原始碼理解

前面簡單瞭解了一下BitMap，下面就通過原始碼來看看java是如何實現BitSet的。

備註資訊

開啟原始碼，首先映入眼簾的是下面這一段長長的備註，簡單翻譯一下，便於英語不好的小夥伴理解

原始碼備註翻譯如下

• 這個類實現了一個根據需要增長的位向量。位集的每個元件都有一個布林值。BitSet的位由非負整數索引。可以檢查、設定或清除單個索引位。一個位集可用於通過邏輯AND、邏輯inclusive OR和邏輯exclusive OR操作修改另一個位集的內容。
• 預設情況下，集合中的所有位最初的值都為false。
• 每個BitSet都有一個當前大小，即BitSet當前使用的空間位數。請注意，大小與BitSet的實現有關，因此它可能會隨著實現而改變。BitSet的長度與BitSet的邏輯長度有關，並且與實現無關。
• 除非另有說明，否則將null引數傳遞給位集中的任何方法都將導致NullPointerException。
• 如果沒有外部同步，BitSet對於多執行緒使用是不安全的。

核心片段理解

首先可以看到原始碼中，最核心的屬性資訊。在BitSet 中使用的是long[] 作為底層儲存的資料結構，並通過一個 int 型別的變數，來記錄當前已經使用陣列元素的個數。

這種型別的屬性結構很常見，比如StringBuilder、StringBuffer底層是一個char[] 作為儲存，一個int 變數用來計數，相似的還有ArrayList，Vector等

/**
 * The internal field corresponding to the serialField "bits".
 */
 private long[] words; 
/**
 * The number of words in the logical size of this BitSet.
 */
 private transient int wordsInUse = 0;

再往下看，是一個很重要的方法，是用來獲取某個數在陣列中的下標，採用的演演算法是將這個數右移6位，這是因為 bitIndex >> 6 = bitIndex / (2^6) = bitIndex /64，而long就是64個位元組

 private final static int ADDRESS_BITS_PER_WORD = 6;
 /**
 * Given a bit index, return word index containing it.
 */
private static int wordIndex(int bitIndex) {
    return bitIndex >> ADDRESS_BITS_PER_WORD;
}

接著比較有意思的就是它的空參構造器，BITS_PER_WORD預設是1<<6 也就是64，根據上面方法原理，wordIndex(64-1)+1 = 1 ，所以最終初始化的是長度為1的陣列

private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
/**
 * Creates a new bit set. All bits are initially {  @code false}.
 */
public BitSet() {
    initWords(BITS_PER_WORD);
    sizeIsSticky = false;
}
private void initWords(int nbits) {
    words = new long[wordIndex(nbits-1) + 1];
}

最後看到這個很經典也很重要的方法，由於底層是陣列，在初始化的時候，並不知道將來會需要儲存多大的資料，所以對於這一類底層核心實現結構是陣列的實體類，通常會使用動態擴容的方法，具體實現細節也都大同小異，這裡實現的動態擴容是原本的兩倍，和Vector類似。

/**
 * Ensures that the BitSet can hold enough words.
 *  @param wordsRequired the minimum acceptable number of words.
 */
private void ensureCapacity(int wordsRequired) {
    // 如果陣列的長度小於所需要的就要進行擴容
    if (words.length < wordsRequired) {
        // Allocate larger of doubled size or required size
        // 擴容最終的大小，最小為原來的兩倍
        int request = Math.max(2 * words.length, wordsRequired);
        // 建立新的陣列，容量為request，然後將原本的陣列拷貝到新的陣列中
        words = Arrays.copyOf(words, request);
        // 並設定陣列大小不固定
        sizeIsSticky = false;
    }
}

至於其他的原始碼細節，因為篇幅有限，就暫且不表，感興趣的可以自行閱讀～

Why

BitMap的特點

根據bitmap的實現原理，其實可以總結出使用bitmap的幾個主要原因：

• 針對海量資料的儲存，可以極大的節約儲存成本！當需要儲存一些很大，且無序，不重複的整數集合，那使用Bitmap的儲存成本是非常低的。
• 因為其天然去重的屬性，對於需要去重儲存的資料很友好！因為bitmap每個值都只對應唯一的一個位置，不能儲存兩個值，所以Bitmap結構天然適合做去重操作。
• 同樣因為其下標的存在，可以快速定位資料！比如想判斷數位 99999是否存在於該bitmap中，若是使用傳統的集合型儲存，那就要逐個遍歷每個元素進行判斷，時間複雜度為O(N)。而由於採用Bitmap儲存，只要檢視對應的下標數的值是0還是1即可，時間複雜度為O(1)。所以使用bitmap可以非常方便快速的查詢某個資料是否在bitmap中。
• 還有因為其類集合的特性，對於一些集合的交併集等操作也可以支援！比如想查詢[1,2,3]與[3,4,5] 兩個集合的交集，用傳統方式取交集就要兩層迴圈遍歷。而Bitmap實現的底層原理，就是把01110000和00011100進行與操作就行了。而計算機做與、或、非、互斥或等等操作是非常快的。

雖然bitmap有諸多好處，但是正所謂人無完人，它也存在很多缺陷。

• 只能儲存正整數而不能是其他的型別；
• 不適合儲存稀疏的集合，簡單理解，一個集合存放了兩個數[1,99999999]，那用bitmap儲存的話就很不划算，這也與它本來節約儲存的優點也背離了；
• 不適用於儲存重複的資料。

BitMap的優化

既然bitmap的優點如此突出，那應該如何去優化它存在的一些侷限呢？

• 針對儲存非正整數的型別，如字串型別的，可以考慮將字串型別的資料利用類似hash的方法，對映成整數的形式來使用bitmap，但是這個方法會有hash衝突的問題，解決這個可以優化hash方法，採用多重hash來解決，但是根據經驗，這個效果都不太好，通常的做法就是針對字串建立對映表的方式。
• 針對bitmap的優化最核心的還是對於其儲存成本的優化，畢竟巨量資料領域裡面，大多數時候資料都是稀疏資料，而我們又經常需要使用到bitmap的特長，比如去重等屬性，所以存在一些進一步的優化，比較知名的有WAH、EWAH、RoaringBitmap等，其中效能最好並且應用最為廣泛的當屬RoaringBitmap

RoaringBitmap的核心原理

為了快速把這個原理說清楚，這裡就不繼續擼原始碼了，有興趣的小夥伴可以自行搜尋相關原始碼閱讀，下面簡單闡述一下它的核心原理：1個Int 型別相當於有32 bit 也就相當於2^32=2^16 x 2^16，這意味著任意一個Int 型別可以拆分成兩個16bit的來儲存，每一個拆出來的都不會大於2^16， 2^16就是65536，而Int的正整數實際最大值為 2147483647。而RoaringBitmap的壓縮首先做的就是用原本的數去除65536，結果表示成(商，餘數)，其中商和餘數是都不會超過65536。

如下圖所示

RoaringBitmap的做法就是將131138 原本32bit的儲存結構，拆分成連兩個16bit的結構，而拆分出的兩個16bit分別儲存了131138除65536的商2以及餘數66。

在RoaringBitmap中，把商所處的16bit 被稱為高16位元，除數所處的16bit 被稱為低16位元。並用key和Container去儲存的這些拆分出來的資料，其中key是short[] ，存放的就是商，因為bitmap的特性，商和餘數不會存在完全相同的情況。

通過商來作為key劃分不同的Container，就類似劃分不同的桶，key就是標識資料應該存在哪個桶，container用來存對應資料的低16位元的數位。比如 1000和60666 除以65536後的結果分別是(0,1000)和(0,60666)，所以這兩個資料儲存到RoaringBitmap中，就會都放到key位0那個container中，container中就是1000和60666。

由於container中存放的數位是0~65536的一些資料，可能稀疏可能稠密，所以RoaringBitmap依據不同的場景，提供了 3 種不同的 Container，分別是 ArrayContainer 、 BitmapContainer 、RunContainer。

關於三個Container的儲存原理如下：

• ArrayContainer 儲存的方式就是 shot型別的陣列， 每個數位佔16bit 也就是2Byte，當id 數達到4096個時，佔用4096x2 = 8196byte 也就是8kb，而id數最大是65536，佔用 65536x2 =131072 byte 也就是128kb。
• BitmapContainer儲存的方式就是bitmap型別，bitmap的位數為 65536，能儲存0~65535個數位，佔用 65536/8/1024=8kb，也就是bitmap container佔用空間恆定為8kb。
• RunContainer儲存的必須是連續的數位，比如儲存1，2，3...100w，RunContainer就只會儲存[1,100w]也就是開頭和結尾的一個數位，其壓縮效率取決於連續的數位有多長。

關於ArrayContainer和BitmapContainer的選擇：

如圖所示，可以看到ArrayContainer 更適合存放稀疏的資料，BitmapContainer 適合存放稠密的資料。在RoaringBitmap中，若一個 Container 裡面的元素數量小於 4096，會使用 ArrayContainer 來儲存。當 Array Container 超過最大容量 4096 時，會轉換為 BitmapContainer，這樣能夠最大化的優化儲存。

how

bitmap就像一柄雙刃劍，用的好可以幫助我們破除瓶頸，解決痛點。用的不好不僅會丟失它所有的優點，還要搭上過多的儲存，甚至會喪失掉最重要的準確性，所以要針對不同業務場景靈活使用我們的武器，才能事半功倍！

下面舉例bitmap的一些使用場景，來看看實際開發中，到底怎麼正確使用bitmap：

BitMap在使用者分群的應用

假設有使用者的標籤寬表，對應欄位及值如下

如果想根據標籤劃分人群，比如：1001城市 + 下單。

傳統解決方案

通常是對列值進行遍歷篩選，如果優化也就是列上建立索引，但是當這張表有很多標籤列時，如果要索引生效並不是每列有索引就行，要每種查詢組合建一個索引才能生效，索引數量相當於標籤列排列組合的個數，當標籤列有1、2 k 的時候，這基本就是不可能的。通常的做法是在數倉提前將熱點的組合聚合過濾成新欄位，或者只對熱點組合加索引，但這樣都很不靈活。

使用BitMap的方案

通過採用bitmap的辦法，按欄位重組成Bitmap。

把資料調整成這樣的結構，再進行條件組合,那就簡單了。比如: 1001城市 + 下單 = Bitmap[00000110] & Bitmap[00001010]= 1 ，這個計算速度相比寬表條件篩選是快很多的，如果資料是比較稠密的，bitmap可以極大的節省底層儲存，如果資料比較稀疏，可以採用RoaringBitmap來優化。

BitMap在A/B實驗平臺業務的應用

在支援貨拉拉A/B實驗平臺業務的場景中，會有一個實驗對應很多司機的情況，因為要在數倉處理成明細寬表，來支援OLAP引擎的使用，隨著維度的增多，資料發散的情況變得很嚴重，數倉及OLAP的儲存與計算資源都消耗巨大。為了解決這個痛點，在架構組同事建議下，引入了BitMap，將組裝好的司機id陣列轉換成RoaringBitmap格式，再傳入到OLAP引擎裡面使用。

在數倉應用層，由於引入了BitMap，重構了原本的資料表結構及鏈路，並優化了數倉的分層。不僅讓整個鏈路耗時縮短了2個多小時，還節省了後續往OLAP引擎導數的時間，再算上數倉層的計算與儲存資源的節省，很完美的實現了降本增效！而在OLAP引擎層，由架構組的同事通過二次開發，支援了Bitmap的使用，也取得了很不錯的效果。

具體的落地與應用則在下篇文章給大家詳細分享。

結語

本文首先通過對於BitMap的簡單實現以及對於Java中BitSet原始碼的分析，提升讀者對於其底層原理的理解，然後分析了BitMap的特點，並針對其儲存優化的方案，講解了RoaringBitmap技術的原理，最後列舉了對於BitMap的常見使用場景。希望大家讀後都能有所收穫。

更多關於貨拉拉BitMap巨量資料的資料請關注it145.com其它相關文章！