關(guān)于Bitmap

在大數(shù)據(jù)時代，想要不斷提升基于海量數(shù)據(jù)獲取的決策、洞察發(fā)現(xiàn)和流程優(yōu)化等能力，就需要不停思考，如何在利用有限的資源實現(xiàn)高效穩(wěn)定地產(chǎn)出可信且豐富的數(shù)據(jù)，從而提高賦能下游產(chǎn)品的效率以及效果。在貨拉拉數(shù)倉構(gòu)建過程中，我們不斷探索各種方式來實現(xiàn)降本提效。例如在一些場景下，利用Bitmap去提升下游的數(shù)據(jù)使用體驗，并達成我們想要的降本提效的目的。

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

首先從Bitmap開始說起，這里采用經(jīng)典的WWH結(jié)構(gòu)，讓不熟悉的小伙伴能夠快速了解掌握。

What

BitMap，即位圖，是比較常見的數(shù)據(jù)結(jié)構(gòu)，簡單來說就是按位存儲，主要為了解決在去重場景里面大數(shù)據(jù)量存儲的問題。本質(zhì)其實就是哈希表的一種應(yīng)用實現(xiàn)，使用每個位來表示某個數(shù)字。

舉個例子

假設(shè)有個1，3，5，7的數(shù)字集合，如果常規(guī)的存儲方法，要用4個Int的空間。其中一個Int就是32位的空間。3個就是4*32Bit，相當(dāng)于16個字節(jié)。

如果用Bitmap存儲呢，只用8Bit（1個字節(jié)）就夠了。bitmap通過使用每一bit位代表一個數(shù)，位號就是數(shù)值，1標(biāo)識有，0標(biāo)識無。如下所示：

BitMap的簡單實現(xiàn)

對于 BitMap 這種經(jīng)典的數(shù)據(jù)結(jié)構(gòu)，在 Java 語言里面，其實已經(jīng)有對應(yīng)實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)類 java.util.BitSet 了，而 BitSet 的底層原理，其實就是用 long 類型的數(shù)組來存儲元素，因為使用的是long類型的數(shù)組，而 1 long = 64 bit，所以數(shù)據(jù)大小會是64的整數(shù)倍。這樣看可能很難理解，下面參考bitmap源碼寫了一個例子，并寫上了詳細(xì)的備注，方便理解

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

下面就來簡單玩一玩這個自制的BitMap，先嘗試插入一個3，并清理掉它，看看底層二進制結(jié)構(gòu)是怎樣變化的

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);
}

輸出結(jié)果如下：

再通過數(shù)組，插入多個元素看看效果

public static void main(String[] args) {
    // 數(shù)組試驗
    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);
}

輸出結(jié)果如下：

BitSet源碼理解

前面簡單了解了一下BitMap，下面就通過源碼來看看java是如何實現(xiàn)BitSet的。

備注信息

打開源碼，首先映入眼簾的是下面這一段長長的備注，簡單翻譯一下，便于英語不好的小伙伴理解

源碼備注翻譯如下

• 這個類實現(xiàn)了一個根據(jù)需要增長的位向量。位集的每個組件都有一個布爾值。BitSet的位由非負(fù)整數(shù)索引?？梢詸z查、設(shè)置或清除單個索引位。一個位集可用于通過邏輯AND、邏輯inclusive OR和邏輯exclusive OR操作修改另一個位集的內(nèi)容。
• 默認(rèn)情況下，集合中的所有位最初的值都為false。
• 每個BitSet都有一個當(dāng)前大小，即BitSet當(dāng)前使用的空間位數(shù)。請注意，大小與BitSet的實現(xiàn)有關(guān)，因此它可能會隨著實現(xiàn)而改變。BitSet的長度與BitSet的邏輯長度有關(guān)，并且與實現(xiàn)無關(guān)。
• 除非另有說明，否則將null參數(shù)傳遞給位集中的任何方法都將導(dǎo)致NullPointerException。
• 如果沒有外部同步，BitSet對于多線程使用是不安全的。

核心片段理解

首先可以看到源碼中，最核心的屬性信息。在BitSet 中使用的是long[] 作為底層存儲的數(shù)據(jù)結(jié)構(gòu)，并通過一個 int 類型的變量，來記錄當(dāng)前已經(jīng)使用數(shù)組元素的個數(shù)。

這種類型的屬性結(jié)構(gòu)很常見，比如StringBuilder、StringBuffer底層是一個char[] 作為存儲，一個int 變量用來計數(shù)，相似的還有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;

再往下看，是一個很重要的方法，是用來獲取某個數(shù)在數(shù)組中的下標(biāo)，采用的算法是將這個數(shù)右移6位，這是因為 bitIndex >> 6 = bitIndex / (2^6) = bitIndex /64，而long就是64個字節(jié)

 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;
}

接著比較有意思的就是它的空參構(gòu)造器，BITS_PER_WORD默認(rèn)是1<<6 也就是64，根據(jù)上面方法原理，wordIndex(64-1)+1 = 1 ，所以最終初始化的是長度為1的數(shù)組

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];
}

最后看到這個很經(jīng)典也很重要的方法，由于底層是數(shù)組，在初始化的時候，并不知道將來會需要存儲多大的數(shù)據(jù)，所以對于這一類底層核心實現(xiàn)結(jié)構(gòu)是數(shù)組的實體類，通常會使用動態(tài)擴容的方法，具體實現(xiàn)細(xì)節(jié)也都大同小異，這里實現(xiàn)的動態(tài)擴容是原本的兩倍，和Vector類似。

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

至于其他的源碼細(xì)節(jié)，因為篇幅有限，就暫且不表，感興趣的可以自行閱讀～

Why

BitMap的特點

根據(jù)bitmap的實現(xiàn)原理，其實可以總結(jié)出使用bitmap的幾個主要原因：

• 針對海量數(shù)據(jù)的存儲，可以極大的節(jié)約存儲成本！當(dāng)需要存儲一些很大，且無序，不重復(fù)的整數(shù)集合，那使用Bitmap的存儲成本是非常低的。
• 因為其天然去重的屬性，對于需要去重存儲的數(shù)據(jù)很友好！因為bitmap每個值都只對應(yīng)唯一的一個位置，不能存儲兩個值，所以Bitmap結(jié)構(gòu)天然適合做去重操作。
• 同樣因為其下標(biāo)的存在，可以快速定位數(shù)據(jù)！比如想判斷數(shù)字 99999是否存在于該bitmap中，若是使用傳統(tǒng)的集合型存儲，那就要逐個遍歷每個元素進行判斷，時間復(fù)雜度為O(N)。而由于采用Bitmap存儲，只要查看對應(yīng)的下標(biāo)數(shù)的值是0還是1即可，時間復(fù)雜度為O(1)。所以使用bitmap可以非常方便快速的查詢某個數(shù)據(jù)是否在bitmap中。
• 還有因為其類集合的特性，對于一些集合的交并集等操作也可以支持！比如想查詢[1,2,3]與[3,4,5] 兩個集合的交集，用傳統(tǒng)方式取交集就要兩層循環(huán)遍歷。而Bitmap實現(xiàn)的底層原理，就是把01110000和00011100進行與操作就行了。而計算機做與、或、非、異或等等操作是非?？斓?。

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

• 只能存儲正整數(shù)而不能是其他的類型；
• 不適合存儲稀疏的集合，簡單理解，一個集合存放了兩個數(shù)[1,99999999]，那用bitmap存儲的話就很不劃算，這也與它本來節(jié)約存儲的優(yōu)點也背離了；
• 不適用于存儲重復(fù)的數(shù)據(jù)。

BitMap的優(yōu)化

既然bitmap的優(yōu)點如此突出，那應(yīng)該如何去優(yōu)化它存在的一些局限呢？

• 針對存儲非正整數(shù)的類型，如字符串類型的，可以考慮將字符串類型的數(shù)據(jù)利用類似hash的方法，映射成整數(shù)的形式來使用bitmap，但是這個方法會有hash沖突的問題，解決這個可以優(yōu)化hash方法，采用多重hash來解決，但是根據(jù)經(jīng)驗，這個效果都不太好，通常的做法就是針對字符串建立映射表的方式。
• 針對bitmap的優(yōu)化最核心的還是對于其存儲成本的優(yōu)化，畢竟大數(shù)據(jù)領(lǐng)域里面，大多數(shù)時候數(shù)據(jù)都是稀疏數(shù)據(jù)，而我們又經(jīng)常需要使用到bitmap的特長，比如去重等屬性，所以存在一些進一步的優(yōu)化，比較知名的有WAH、EWAH、RoaringBitmap等，其中性能最好并且應(yīng)用最為廣泛的當(dāng)屬RoaringBitmap

RoaringBitmap的核心原理

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

如下圖所示

RoaringBitmap的做法就是將131138 原本32bit的存儲結(jié)構(gòu)，拆分成連兩個16bit的結(jié)構(gòu)，而拆分出的兩個16bit分別存儲了131138除65536的商2以及余數(shù)66。

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

通過商來作為key劃分不同的Container，就類似劃分不同的桶，key就是標(biāo)識數(shù)據(jù)應(yīng)該存在哪個桶，container用來存對應(yīng)數(shù)據(jù)的低16位的數(shù)字。比如 1000和60666 除以65536后的結(jié)果分別是(0,1000)和(0,60666)，所以這兩個數(shù)據(jù)存儲到RoaringBitmap中，就會都放到key位0那個container中，container中就是1000和60666。

由于container中存放的數(shù)字是0~65536的一些數(shù)據(jù)，可能稀疏可能稠密，所以RoaringBitmap依據(jù)不同的場景，提供了 3 種不同的 Container，分別是 ArrayContainer 、 BitmapContainer 、RunContainer。

關(guān)于三個Container的存儲原理如下：

• ArrayContainer 存儲的方式就是 shot類型的數(shù)組， 每個數(shù)字占16bit 也就是2Byte，當(dāng)id 數(shù)達到4096個時，占用4096x2 = 8196byte 也就是8kb，而id數(shù)最大是65536，占用 65536x2 =131072 byte 也就是128kb。
• BitmapContainer存儲的方式就是bitmap類型，bitmap的位數(shù)為 65536，能存儲0~65535個數(shù)字，占用 65536/8/1024=8kb，也就是bitmap container占用空間恒定為8kb。
• RunContainer存儲的必須是連續(xù)的數(shù)字，比如存儲1，2，3...100w，RunContainer就只會存儲[1,100w]也就是開頭和結(jié)尾的一個數(shù)字，其壓縮效率取決于連續(xù)的數(shù)字有多長。

關(guān)于ArrayContainer和BitmapContainer的選擇：

如圖所示，可以看到ArrayContainer 更適合存放稀疏的數(shù)據(jù)，BitmapContainer 適合存放稠密的數(shù)據(jù)。在RoaringBitmap中，若一個 Container 里面的元素數(shù)量小于 4096，會使用 ArrayContainer 來存儲。當(dāng) Array Container 超過最大容量 4096 時，會轉(zhuǎn)換為 BitmapContainer，這樣能夠最大化的優(yōu)化存儲。

how

bitmap就像一柄雙刃劍，用的好可以幫助我們破除瓶頸，解決痛點。用的不好不僅會丟失它所有的優(yōu)點，還要搭上過多的存儲，甚至?xí)适У糇钪匾臏?zhǔn)確性，所以要針對不同業(yè)務(wù)場景靈活使用我們的武器，才能事半功倍！

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

BitMap在用戶分群的應(yīng)用

假設(shè)有用戶的標(biāo)簽寬表，對應(yīng)字段及值如下

如果想根據(jù)標(biāo)簽劃分人群，比如：1001城市 + 下單。

傳統(tǒng)解決方案

通常是對列值進行遍歷篩選，如果優(yōu)化也就是列上建立索引，但是當(dāng)這張表有很多標(biāo)簽列時，如果要索引生效并不是每列有索引就行，要每種查詢組合建一個索引才能生效，索引數(shù)量相當(dāng)于標(biāo)簽列排列組合的個數(shù)，當(dāng)標(biāo)簽列有1、2 k 的時候，這基本就是不可能的。通常的做法是在數(shù)倉提前將熱點的組合聚合過濾成新字段，或者只對熱點組合加索引，但這樣都很不靈活。

使用BitMap的方案

通過采用bitmap的辦法，按字段重組成Bitmap。

把數(shù)據(jù)調(diào)整成這樣的結(jié)構(gòu)，再進行條件組合,那就簡單了。比如: 1001城市 + 下單 = Bitmap[00000110] & Bitmap[00001010]= 1 ，這個計算速度相比寬表條件篩選是快很多的，如果數(shù)據(jù)是比較稠密的，bitmap可以極大的節(jié)省底層存儲，如果數(shù)據(jù)比較稀疏，可以采用RoaringBitmap來優(yōu)化。

BitMap在A/B實驗平臺業(yè)務(wù)的應(yīng)用

在支持貨拉拉A/B實驗平臺業(yè)務(wù)的場景中，會有一個實驗對應(yīng)很多司機的情況，因為要在數(shù)倉處理成明細(xì)寬表，來支持OLAP引擎的使用，隨著維度的增多，數(shù)據(jù)發(fā)散的情況變得很嚴(yán)重，數(shù)倉及OLAP的存儲與計算資源都消耗巨大。為了解決這個痛點，在架構(gòu)組同事建議下，引入了BitMap，將組裝好的司機id數(shù)組轉(zhuǎn)換成RoaringBitmap格式，再傳入到OLAP引擎里面使用。

在數(shù)倉應(yīng)用層，由于引入了BitMap，重構(gòu)了原本的數(shù)據(jù)表結(jié)構(gòu)及鏈路，并優(yōu)化了數(shù)倉的分層。不僅讓整個鏈路耗時縮短了2個多小時，還節(jié)省了后續(xù)往OLAP引擎導(dǎo)數(shù)的時間，再算上數(shù)倉層的計算與存儲資源的節(jié)省，很完美的實現(xiàn)了降本增效！而在OLAP引擎層，由架構(gòu)組的同事通過二次開發(fā)，支持了Bitmap的使用，也取得了很不錯的效果。

具體的落地與應(yīng)用則在下篇文章給大家詳細(xì)分享。

結(jié)語

本文首先通過對于BitMap的簡單實現(xiàn)以及對于Java中BitSet源碼的分析，提升讀者對于其底層原理的理解，然后分析了BitMap的特點，并針對其存儲優(yōu)化的方案，講解了RoaringBitmap技術(shù)的原理，最后列舉了對于BitMap的常見使用場景。希望大家讀后都能有所收獲。

更多關(guān)于貨拉拉BitMap大數(shù)據(jù)的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論