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

01 什么是BitMap？

此BitMap不是指圖片存儲(chǔ)格式里的位圖。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

顯然，這兩種映射到選擇影響到以下幾點(diǎn)：

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

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

優(yōu)點(diǎn)：

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

缺點(diǎn)：

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

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

優(yōu)點(diǎn)：

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

缺點(diǎn)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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