抖音、快手數(shù)億級量級的APP，日活、月活、留存、漏斗分析、多維分析等是如何做到秒級響應(yīng)的呢 ？這其中就是BitMap技術(shù)。本文作者從多個角度對BitMap展開了分析說明，希望通過此文能夠加深你對BitMap技術(shù)的認識。

01 什么是BitMap？

此BitMap不是指圖片存儲格式里的位圖。

Bit即比特，是目前計算機系統(tǒng)里邊數(shù)據(jù)的最小單位，8個bit即為一個Byte。一個bit的值，或者是0，或者是1；也就是說一個bit能存儲的最多信息是2.

BitMap可以理解為通過一個bit數(shù)組來存儲特定數(shù)據(jù)的一種數(shù)據(jù)結(jié)構(gòu)；由于bit是數(shù)據(jù)的最小單位，所以這種數(shù)據(jù)結(jié)構(gòu)往往是非常節(jié)省存儲空間。

比如一個公司有8個員工；現(xiàn)在需要記錄公司的考勤記錄；傳統(tǒng)的方案是記錄下每天正常考勤的員工的ID列表，比如2012-01-01:[1,2,3,4,5,6,7,8];假如員工ID采用byte數(shù)據(jù)類型，則保存每天的考勤記錄需要N個byte，其中N是當(dāng)天考勤的總?cè)藬?shù)。另一種方案則是構(gòu)造一個8bit（即1byte）的數(shù)組，將這8個員工跟員工號分別映射到這8個位置，如果當(dāng)天正常考勤了，則將對應(yīng)的這個位置置為1，否則置為0；這樣可以每天采用恒定的1個byte即可保存當(dāng)天的考勤記錄。

除了節(jié)省存儲空間，BitMap結(jié)構(gòu)的另一個更重要的特點，就是很方便通過位的運算（AND,OR,XOR,NOT），高效的對多個BitMap數(shù)據(jù)進行處理。比如上邊的考勤的例子里，如果想知道那個員工最近兩天都沒來，只要將昨天的BitMap和今天的BitMap做一個按位的OR計算，然后檢查那些位置是0，就可以得到最近兩天都沒來的員工的數(shù)據(jù)了，比如：

BitMap在有的文檔里也稱為：bit array， bitset或者bitstring。關(guān)于BitMap技術(shù)的詳細信息，可以參考http://en.wikipedia.org/wiki/Bit_array

Java SDK里邊有提供BitMap的實現(xiàn)：java.util.BitSet

02 BitMap在統(tǒng)計系統(tǒng)里邊能做什么？

例子 1：針對獨立用戶的統(tǒng)計。比如想知道某個應(yīng)用，每天有多少個獨立用戶使用了該應(yīng)用？可以根據(jù)該應(yīng)用的用戶訪問日志，每天生成一個BitMap；每個用戶對應(yīng)BitMap里的一個位置，如果當(dāng)天訪問了，該位置就置為1，否則為0。這樣要知道當(dāng)天這個應(yīng)用的總獨立用戶數(shù)，只需要看看那天的BitMap里邊有多少個1。

對于10M（1000萬）用戶的應(yīng)用，每天需要的BitMap大小為10M/8=1.25MB，即只需要1.25兆字節(jié)。在采用一些壓縮技術(shù)的基礎(chǔ)上，可以進一步縮減需要的存儲量，一般情況下可能只需要大約100-200KB的存儲即可。

例子2：用戶回訪的統(tǒng)計。比如想知道某個應(yīng)用，昨天使用過的用戶中，有多少今天也使用了？可以在例子1（每天保存一個獨立活躍用戶的BitMap）的基礎(chǔ)上，將昨天的BitMap和今天的BitMap進行AND操作，然后數(shù)一下生成的BitMap里有多少個1即可。

03 怎么將用戶映射到BitMap里邊的某個位置？

使用BitMap的時候，都需要將原始數(shù)據(jù)（比如用戶）映射到BitMap里的位置；這種映射一般可以采用外部數(shù)據(jù)（比如在數(shù)據(jù)庫里保存用戶到BitMap位置的映射），或者采用固定的規(guī)則（比如計算用戶名的hash code）。

采用第一種方法時，通常是在數(shù)據(jù)庫里邊給用戶分配一個數(shù)值型的用戶ID，而用戶ID的生成規(guī)則采用自增量的方式來產(chǎn)生；這樣比如有100個用戶，則其用戶ID為1，2，3，…，98，99，100；用戶ID為1的用戶映射到BitMap里的第1個位置，用戶ID為2的用戶映射到BitMap里的第2個位置…（問題：如果自增量的初始值不是0，而是比如10000，會產(chǎn)生什么影響？）

采用自增量的另外一個好處是，系統(tǒng)用戶數(shù)少的時候，BitMap需要的位數(shù)也少；當(dāng)用戶量增長時，BitMap的位數(shù)跟著增長即可；而且如果記住每天的總用戶數(shù)，BitMap里邊還可以直接表明每天的新增用戶是哪些（注意：此處對于我們的分析系統(tǒng)不一定適用）

采用第二種方法時，最常使用的規(guī)則是計算用戶的hash（比如Object.hashCode,或者MD5）;但由于hash生成的數(shù)字分布很寬（比如java里邊Object的hashCode會返回一個int，所以其分布是-2³¹?– 2³¹-1），但需要的BitMap的位數(shù)往往不用那么大，這樣就需要再做一個hashcode到BitMap里位置的映射（一般是取余數(shù)），這就要求必須預(yù)先知道BitMap的大小，且這個大小一般要求保持不變。

比如要求將用戶映射到一個1024位的BitMap：用戶A的hashcode是101，101除1024取余數(shù)是101，所以用戶A就對應(yīng)BitMap的第101位；而用戶B的hashcode是1234567，1234567除1024取余數(shù)是647，用戶B就對應(yīng)BitMap的第647位。

第二種方法由于采用固定的規(guī)則來計算映射，而不需要去做外部數(shù)據(jù)查詢，因此映射這部分的開銷會較第一種方法低很多。但第二種方法也有兩個缺點，其一是如果預(yù)期總用戶量會增長到1百萬，即使目前系統(tǒng)只有1000個用戶，也需要一個1百萬位的BitMap，這樣會造成很大的存儲和計算資源的浪費；其二是hashcode有沖突的問題（即有可能用戶C和用戶D計算出來的hashcode是一樣的）；

而hashcode到BitMap里位置的映射也會造成更多的沖突（比如用戶E和用戶F的hashcode分別是12345678和12377422，但除1024取余后都是334）。這些沖突的存在，導(dǎo)致了數(shù)據(jù)可信度的下降，比如BitMap里的第334位為0，則可以知道用戶E和F都不在；但如果第334位為1，則并不知道用戶E或者用戶F是不是在。

采用第二種方法的BitMap，有一個更廣為人知的名字，即Bloom Filter (http://en.wikipedia.org/wiki/Bloom_filter)。 Bloom Filter經(jīng)常用于文本分析中來記錄某個詞是否已經(jīng)出現(xiàn)；或者垃圾郵件過濾中來檢查郵件地址是否在已知的垃圾郵件地址列表里。

04 分析系統(tǒng)里，同一個用戶在不同的應(yīng)用里邊，是映射到同一個位置，還是不同位置？

在我們的分析系統(tǒng)里邊，一個用戶/設(shè)備會同時使用多個應(yīng)用；但主要的分析，都是基于某個應(yīng)用來做，這種情況下就涉及到幾個問題：

1. 是在全局給用戶分配統(tǒng)一的ID，還是在每個應(yīng)用里邊，對同一個用戶會分配不同的ID？
2. 也就是說，某個應(yīng)用的BitMap，是根據(jù)所有應(yīng)用的總用戶數(shù)，還是這個應(yīng)用自己的總用戶數(shù)，來確定其BitMap的大??？

比如所有應(yīng)用總共有1億用戶，應(yīng)用APP1有1百萬用戶，應(yīng)用APP2有50萬用戶，用戶USER1同時使用APP1和APP2，那么以上的問題也就是：

1. 核心問題是：用戶USER1是始終映射到位置12345，還是在APP1里映射到123，而在APP2里映射到234？
2. 由此引申的是：要記錄APP1的活躍用戶，是要維護一個1億位的BitMap，還是維護一個1百萬位的BitMap？

顯然，這兩種映射到選擇影響到以下幾點：

1. 需要的BitMap的大小
2. 需要維護的用戶到用戶ID映射表的大小
3. 方便針對同一個應(yīng)用的分析，還是方便針對用戶的跨應(yīng)用的分析？

采用全局用戶ID的方案分別由下邊的優(yōu)缺點：

優(yōu)點：

1. 用戶到ID的映射表較小，容量可控
2. 用戶的ID全局一致，便于跨應(yīng)用來分析用戶行為

缺點：

1. 每個應(yīng)用都需要很大的BitMap，造成BitMap空間的浪費；不過這個可以通過BitMap的壓縮技術(shù)來改善
2. BitMap里邊不能很直觀的反應(yīng)：應(yīng)用的總用戶數(shù)和哪些用戶是當(dāng)天的新增用戶，從而計算用戶回訪/保持需要額外的計算

采用在應(yīng)用級別分配ID的方案則有如下的優(yōu)缺點：

優(yōu)點：

1. BitMap空間的浪費少（不過引入壓縮技術(shù)后優(yōu)勢應(yīng)該不明顯）
2. 要是應(yīng)用每天都有新增用戶，從BitMap的大小，基本就可以知道應(yīng)用的總用戶數(shù)
3. BitMap里邊直觀的包含了每天的新增用戶信息，便于做用戶回訪/保持分析。

缺點：

1. 需要維護更大的用戶到ID的映射表；由于這個表在處理中有很大的查詢量，有可能對該表的查詢成為性能瓶頸
2. 很難滿足跨應(yīng)用的分析，比如計算兩個應(yīng)用的重合用戶

由此可見，采用什么樣的映射方案可以獲得最大性能/最方便的實現(xiàn)，跟要做什么樣的分析直接相關(guān)。

拿計算用戶回訪為例，需要計算APP1昨天新增的用戶，今天有多少人繼續(xù)使用了APP1？

對于使用全局用戶ID的方案，需要通過數(shù)據(jù)庫，查詢出APP1昨天新增的用戶是哪些，他們的用戶ID是多少，由此構(gòu)造一個昨天新增用戶的BitMap；然后將該BitMap和今天的活躍用戶的BitMap進行一個AND操作，就可以知道其中哪些用戶今天繼續(xù)使用了APP1；然后做一個計數(shù)就可以得出人數(shù)。

而對于使用應(yīng)用級別用戶ID的方案，假如前天APP1的用戶總數(shù)是1000，昨天是2000，那么就知道昨天新增的用戶在BitMap里邊是位置1000-2000；那么要計算今天的回訪，只需要加載今天的BitMap，看看1000-2000這個位置范圍內(nèi)有多少個1就可以了。

05 如果要記錄用戶的多維信息，能否用BitMap實現(xiàn)？

統(tǒng)計系統(tǒng)中經(jīng)常需要對用戶進行多維分析；這些維度信息通常分為兩類，一類是比較靜態(tài)的，比如用戶的性別，用戶使用的手機類型；另一類則更動態(tài)，比如用戶當(dāng)前使用的應(yīng)用版本，本次的聯(lián)網(wǎng)方式，當(dāng)天的位置，當(dāng)天的第一次啟動時段，等等。當(dāng)然靜態(tài)和動態(tài)也不是絕對的，更多還是取決于數(shù)據(jù)使用者對這些數(shù)據(jù)動態(tài)變化的精確程度的容忍度。

對于相對靜態(tài)的維度信息，往往不需要在BitMap里保存，而可以在需要使用的時候，通過對主數(shù)據(jù)進行查詢動態(tài)生成；即使在較大數(shù)據(jù)量下，這類簡單查詢的性能一般還是可控的。

例如要計算：昨天新增用戶，且在今天繼續(xù)使用的用戶里邊，三大運營商各占多少？可以對用戶表做全表掃描，讀取用戶ID和運營商字段，根據(jù)運營商的不同，生成3個BitMap分別對應(yīng)三個運營商的客戶；然后將這3個BitMap和計算好的回訪的BitMap進行AND，即可知道回訪用戶中運營商的分布情況了。

這種方案中有對用戶表的全表掃描，估計很多人會想到另一個方案，就是對計算好的回訪用戶BitMap進行掃描，然后根據(jù)回訪用戶的用戶ID去查詢其對應(yīng)的運營商信息，這樣可以規(guī)避全表掃描；但實際中這兩種方案該如何取舍卻并不容易；因為全表掃描雖然需要訪問的數(shù)據(jù)量很大，但可以保證是順序的讀?。?/p>

而通過用戶ID去查詢器運營商，則不一定是順序的讀?。ǜ@個數(shù)據(jù)庫表的設(shè)計相關(guān)；因此要采用此方案，或者是回訪的用戶量較小，或者此處的查詢要保證是對數(shù)據(jù)庫文件的順序讀?。?；如果有大量的隨機訪問，反而性能有可能更差。因此選擇什么方案還是需要具體分析。

對于某些動態(tài)數(shù)據(jù)，可能確實需要通過BitMap記錄更多的數(shù)據(jù)（一般都是枚舉類型的，也就是在幾個可能的值中取一個），而不只是boolean型的true/false；這種情況下就需要用多個BitMap來表達了。

最簡單的方案就是針對每個可能的取值，采用單獨的BitMap來存儲；比如說應(yīng)用有1.1, 1.2和2.0三個版本，而用戶可能在不同的版本之間切換；如果要記錄用戶每天使用的版本，則可以維護3個BitMap。第一個BitMap保存使用1.1版本的用戶信息，第二個保存使用1.2版本的,第三個保存使用2.0版本的。

另一種方法是采用多個BitMap聯(lián)合來表達；比如還是上邊的例子，可以只適用2個BitMap即可：使用1.1版本的用戶，在第一個BitMap里為0，但在第二個BitMap里邊為1；使用1.2版本的用戶，在第一個BitMap里為1，但在第二個BitMap里為0；而是要2.0版本的，則在第一個BitMap里為1，在第二個BitMap里也為1。也就是說，將3個版本分別編碼為01，10，11；然后用兩個Bitmap來分別保存第一位和第二位。

這種方法比前一種會更節(jié)省，但同樣也會帶來計算上會更復(fù)雜一些。

06 如果系統(tǒng)總用戶有一千萬，但今天只有100個用戶活躍，是否還需要花費1.25MB的空間來保存這個BitMap？

利用BitMap來保存系統(tǒng)的活躍用戶，一般的情形都是系統(tǒng)的總用戶數(shù)會很多，比如是千萬甚至億級別的；但大部分應(yīng)用的日活躍用戶則只是十萬或者萬級別甚至更少；這必然引出一個問題，就是用一億位的BitMap，來保存1萬的活躍用戶信息，豈不是有很多空間都被浪費了？

進一步分析下，浪費的有兩個部分：其一是存儲空間的浪費，BitMap需要保存到外部存儲（數(shù)據(jù)庫或者文件），計算時需要從外部存儲加載到內(nèi)存，因此存儲的BitMap越大，需要的外部存儲空間就越大；并且計算時IO的消耗會更大，加載BitMap的時間也越長。其二是計算資源的浪費，計算時要加載到內(nèi)存，越大的BitMap消耗的內(nèi)存越多；位數(shù)越多，計算時消耗的cpu時間也越多。

對于第一種浪費，最直覺的方案就是可以引入一些文件壓縮技術(shù)，比如gzip/lzo之類的，對存儲的BitMap文件進行壓縮，在加載BitMap的時候再進行解壓，這樣可以很好的解決存儲空間的浪費，以及加載時IO的消耗；代價則是壓縮/解壓縮都需要消耗更多的cpu/內(nèi)存資源；并且文件壓縮技術(shù)對第二種浪費也無能為力。因此只有系統(tǒng)有足夠多空閑的cpu資源而IO成為瓶頸的情況下，可以考慮引入文件壓縮技術(shù)。

那么有沒有一些技術(shù)可以同時解決這兩種浪費呢？好消息是有，那就是BitMap壓縮技術(shù)；而常見的壓縮技術(shù)都是基于RLE（Run Length Encoding，詳見http://en.wikipedia.org/wiki/Run-length encoding）。

RLE編碼很簡單，比較適合有很多連續(xù)字符的數(shù)據(jù)，比如以下邊的BitMap為例：

可以編碼為0,8,2,11,1,2,3,11

其意思是:第一位為0，連續(xù)有8個，接下來是2個1，11個0，1個1，2個0，3個1，最后是11個0。（當(dāng)然此處只是對RLE的基本原理解釋，實際應(yīng)用中的編碼并不完全是這樣的）

可以預(yù)見，對于一個很大的BitMap，如果里邊的數(shù)據(jù)分布很稀疏（說明有很多大片連續(xù)的0），采用RLE編碼后，占用的空間會比原始的BitMap小很多。

同時引入一些對齊的技術(shù)，可以讓采用RLE編碼的BitMap不需要進行解壓縮，就可以直接進行AND/OR/XOR等各類計算；因此采用這類壓縮技術(shù)的BitMap，加載到內(nèi)存后還是以壓縮的方式存在，從而可以保證計算時候的低內(nèi)存消耗；而采用word(計算機的字長，64位系統(tǒng)就是64bit)對齊等技術(shù)又保證了對cpu資源的高效利用。因此采用這類壓縮技術(shù)的BitMap，保持了BitMap數(shù)據(jù)結(jié)構(gòu)最重要的一個特性，就是高效的針對每個bit的邏輯運算。

常見的壓縮技術(shù)包括BBC(有專利保護), WAH（http://code.google.com/p/compressedbitset/）和EWAH(http://code.google.com/p/javaewah/)。在Apache Hive里邊使用了EWAH。

07 引入BitMap技術(shù)后，分析系統(tǒng)可能的處理流程大體是什么樣的？

1. 數(shù)據(jù)收集系統(tǒng)收集手機上傳數(shù)據(jù)，然后分發(fā)給實時處理系統(tǒng)和批量處理系統(tǒng)；
2. 實時系統(tǒng)采用自有計數(shù)器程序，或者基于Storm之類中間件的計數(shù)器程序，計算各類簡單計數(shù)器，然后批量（比如30s或者1min）更新到Redis或者HBase之類的存儲；前端供應(yīng)計數(shù)器類數(shù)據(jù)的服務(wù)通過訪問后臺計算器程序或者是計數(shù)器存儲來給報表系統(tǒng)提供服務(wù)；
3. 批量系統(tǒng)對該批的init事件按用戶進行去重，然后將整理出來的新用戶數(shù)據(jù)批量更新到主數(shù)據(jù)庫；
4. 批量系統(tǒng)對該批的init/launch/continue之類的信息綜合按(用戶+應(yīng)用)去重，并按用戶排序(optional，看具體情況)，然后和主數(shù)據(jù)庫join得到用戶ID，然后按時間、應(yīng)用和用戶ID排序，批量插入用戶活躍行為日志數(shù)據(jù)庫(基于RDBMS或者HBase)，并生成/修改 某天/某個應(yīng)用的活躍用戶BitMap，然后批量更新獨立活躍用戶總數(shù)之類的指標。
5. 報表中針對獨立用戶的比較分析需要即時計算；對計算結(jié)果可以考慮引入有超時控制的cache。

08 EWAH只支持append，如何回避這個限制？

WAH以及EWAH都只支持append；也就是說，初始化BitMap的時候，只支持從低位到高位的順序設(shè)置；比如設(shè)置位置100為1后，就不能再設(shè)置低于100的位置的數(shù)據(jù)了，這對我們的處理，特別是更新歷史數(shù)據(jù)，或造成影響。

由于只支持append，所以要求批處理準備數(shù)據(jù)的時候，需要對用戶ID進行從低到高的排序，這樣保證了初始化BitMap時調(diào)用set(position)操作也是從低到高，從而規(guī)避了不支持append的缺陷。

對于更新歷史數(shù)據(jù)的問題，在可以通過下邊的方法解決：只針對本批數(shù)據(jù)生成活躍用戶的BitMap，然后和歷史保存的Bitmap進行OR，然后保存新的BitMap即可。

本文由 @高增強 原創(chuàng)發(fā)布于人人都是產(chǎn)品經(jīng)理。未經(jīng)許可，禁止轉(zhuǎn)載

題圖來自Unsplash，基于CC0協(xié)議