a) Bitmap如何做到多維交叉計(jì)算的？
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)的方案是記錄下每天正成乓螅考勤的員工的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（01110011）的數(shù)組勒极，將這8個(gè)員工跟員工號(hào)分別映射到這8個(gè)位置是掰，如果當(dāng)天正常考勤了辱匿，則將對應(yīng)的這個(gè)位置置為1键痛，否則置為0；這樣可以每天采用恒定的1個(gè)byte即可保存當(dāng)天的考勤記錄匾七。
綜上所述絮短，Bitmap節(jié)省大量的存儲(chǔ)空間，因此可以被一次性加載到內(nèi)存中昨忆。再看其結(jié)構(gòu)的另一個(gè)更重要的特點(diǎn)戚丸，它也顯現(xiàn)出巨大威力：就是很方便通過位的運(yùn)算（AND/OR/XOR/NOT），高效的對多個(gè)Bitmap數(shù)據(jù)進(jìn)行處理，這點(diǎn)很重要限府，它直接的支持了多維交叉計(jì)算能力夺颤。比如上邊的考勤的例子里，如果想知道哪個(gè)員工最近兩天都沒來胁勺，只要將昨天的Bitmap和今天的Bitmap做一個(gè)按位的“OR”計(jì)算世澜，然后檢查那些位置是0，就可以得到最近兩天都沒來的員工的數(shù)據(jù)了署穗，比如：
再比如寥裂，我們想知道哪些男員工沒來？我們可以在此結(jié)果上再“And”上一個(gè)Bitmap就能得到結(jié)果案疲。
b) Bitmap如何做到高速運(yùn)算的封恰？
回憶一下前面，浪費(fèi)的有兩個(gè)部分：其一是存儲(chǔ)空間的浪費(fèi)褐啡，Bitmap比文件強(qiáng)多了诺舔，但是仍然有浪費(fèi)的嫌疑。它需要保存到外部存儲(chǔ)（數(shù)據(jù)庫或者文件）备畦，計(jì)算時(shí)需要從外部存儲(chǔ)加載到內(nèi)存低飒，因此存儲(chǔ)的Bitmap越大，需要的外部存儲(chǔ)空間就越大懂盐；并且計(jì)算時(shí)I/O的消耗會(huì)更大褥赊，加載Bitmap的時(shí)間也越長。其二是計(jì)算資源的浪費(fèi)莉恼，計(jì)算時(shí)要加載到內(nèi)存拌喉，越大的Bitmap消耗的內(nèi)存越多；位數(shù)越多俐银，計(jì)算時(shí)消耗的cpu時(shí)間也越多司光。
對于第一種浪費(fèi)，最直覺的方案就是可以引入一些文件壓縮技術(shù)悉患，比如gzip/lzo之類的，對存儲(chǔ)的Bitmap文件進(jìn)行壓縮榆俺，在加載Bitmap的時(shí)候再進(jìn)行解壓售躁，這樣可以很好的解決存儲(chǔ)空間的浪費(fèi)，以及加載時(shí)I/O的消耗茴晋；代價(jià)則是壓縮/解壓縮都需要消耗更多的CPU/內(nèi)存資源陪捷；并且文件壓縮技術(shù)對第二種浪費(fèi)也無能為力。因此只有系統(tǒng)有足夠多空閑的CPU資源而I/O成為瓶頸的情況下诺擅，可以考慮引入文件壓縮技術(shù)市袖。
那么有沒有一些技術(shù)可以同時(shí)解決這兩種浪費(fèi)呢？好消息是有，那就是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個(gè)仗扬，接下來是2個(gè)1症概，11個(gè)0早芭，1個(gè)1，2個(gè)0逼友，3個(gè)1精肃，最后是11個(gè)0（當(dāng)然此處只是對RLE的基本原理解釋帜乞，實(shí)際應(yīng)用中的編碼并不完全是這樣的）黎烈。
可以預(yù)見照棋，對于一個(gè)很大的Bitmap，如果里邊的數(shù)據(jù)分布很稀疏（說明有很多大片連續(xù)的0）溶锭，采用RLE編碼后符隙，占用的空間會(huì)比原始的Bitmap小很多霹疫。
同時(shí)引入一些對齊的技術(shù)丽蝎，可以讓采用RLE編碼的Bitmap不需要進(jìn)行解壓縮，就可以直接進(jìn)行AND/OR/XOR等各類計(jì)算红省；因此采用這類壓縮技術(shù)的Bitmap类腮，加載到內(nèi)存后還是以壓縮的方式存在蚜枢，從而可以保證計(jì)算時(shí)候的低內(nèi)存消耗；而采用word（計(jì)算機(jī)的字長需频，64位系統(tǒng)就是64bit）對齊等技術(shù)又保證了對CPU資源的高效利用昭殉。因此采用這類壓縮技術(shù)的Bitmap藐守，保持了Bitmap數(shù)據(jù)結(jié)構(gòu)最重要的一個(gè)特性卢厂，就是高效的針對每個(gè)bit的邏輯運(yùn)算。
常見的壓縮技術(shù)包括BBC（有專利保護(hù)）,
WAH（http://code.google.com/p/compressedbitset/）
和EWAH(http://code.google.com/p/javaewah/)任内。在Apache Hive里邊使用了EWAH死嗦。
c) Bitmap在大數(shù)據(jù)計(jì)算上的能力越除？
我們用一個(gè)TalkingData Analytics中用戶留存的例子來看Bitmap如何做到用戶回訪的統(tǒng)計(jì)外盯。比如想知道某個(gè)應(yīng)用门怪，昨天新增的用戶中锅纺，有多少人今天又開啟了應(yīng)用（次日留存）。使用過Hive的工程師护锤，不難理解下面語句的含義：
同時(shí)烙懦，我們使用Bitmap技術(shù)后氯析，同樣實(shí)現(xiàn)上述的計(jì)算莺褒，對比測試顯示出效率的差異是巨大的：
d) 引入Bitmap技術(shù)后你辣，分析系統(tǒng)可能的處理流程大體是什么樣的陨舱？
數(shù)據(jù)收集系統(tǒng)收集設(shè)備上傳數(shù)據(jù)，然后分發(fā)給實(shí)時(shí)處理系統(tǒng)和批量處理系統(tǒng)表悬；
實(shí)時(shí)系統(tǒng)采用自有計(jì)數(shù)器程序签孔，或者基于Storm之類中間件的計(jì)數(shù)器程序饥追，計(jì)算各類簡單計(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ù)纬黎；
批量系統(tǒng)對該批的數(shù)據(jù)按用戶進(jìn)行去重生成/修改某天/某個(gè)應(yīng)用的活躍用戶Bitmap本今，同時(shí)可以根據(jù)需要，將機(jī)型孕索、地域躏碳、操作系統(tǒng)等等各種數(shù)據(jù)提煉成屬性Bitmap菇绵，備用脸甘。
報(bào)表中針對分析需要丹诀，提取各種Bitmap（用戶铆遭、屬性……Bitmap），高效的利用CPU/內(nèi)存碗脊，通過組合And/Or/Not等基礎(chǔ)計(jì)算衙伶，最終完成多維交叉計(jì)算功能矢劲，反饋客戶結(jié)果芬沉。
