之前已經參加過幾次QCon峰會，不過今年QCon 2014 上海峰會對我來說比較特別，不再只是一名聽眾，而是第一次登臺演講。感覺的確不太一樣，一來是身份從聽眾變成了講師，二來是因為成了講師，讓我接觸到更多的業內朋友，也遇到了更多的提問、咨詢。會后已經有一段時間了，還有朋友提出想了解更多的技術知識。看來會上行云流水的半個小時，未能把一個技術點講述明白，我想還是總結一下，讓技術圈朋友們對Bitmap這個技術點加深點理解。

　　一、背景

　　a) 歷史的困惑

　　每個技術點背后都有一系列業務的故事，透過我這次講的Bitmap，我們可以看到歷史上始終困擾營銷領域的一個核心問題。著名廣告大師約翰•沃納梅克提出：我知道我的廣告費有一半浪費了，但遺憾的是，我不知道是哪一半被浪費了 (注：翰•沃納梅克，始創第一家百貨商店“沃納梅克氏”，被認為是百貨商店之父；同時也是第一個投放現代廣告的商人)。為什么會出現這樣的浪費呢？我個人覺得還是對營銷所面向的人群理解不透徹導致的。因此，營銷領域一直期待技術系統能夠提供一種能力，可以高速、靈活的、從海量用戶中，找出最合適的那一部分。

　　b) 時代的曙光

　　需求的背后，是技術的不斷進步。最近幾年，信息技術的突飛猛進，給解決問題帶來了一線曙光。大數據處理技術和系統，已經滲透到當今每一個行業和業務職能領域，成為重要的生產因素。人們對于海量數據的挖掘和運用，預示著新一波生產率增長和消費者盈余浪潮的到來。使用各種各樣新型的技術武器（Hadoop、Spark、Storm等等開源工具），我們近乎完美的捕捉到這個時代的浪潮：將人群的屬性分析、行為分析、甚至是心理分析深入到相當精深的地步。

　　c) 業務驅動力

　　業務需求對技術的要求是永無止境的。我們需要更好的工具：

1. 更快速的分析，一次任務就需要個把小時，甚至需要一天，數據的產出，無法支持我們業務的快速調整。
2. 更靈活的分析工具，應該比Oracle或者IBM的BI系統更好，我們需要有多維交叉的計算能力，而不只是簡單的幾種統計數字。
3. 更輕量級的系統，動輒幾十臺服務器組成的Hadoop集群，我們真是無法負擔啊，成本太高昂了。

　　二、現有技術分析

　　a) 硬幣的兩面

　　我們最初非常仰仗Hadoop，不過后來發現Hadoop不是銀彈，核心的問題不是Hadoop出了錯，而是我們對Hadoop的本質理解稍顯片面。Hadoop是一種高吞吐量系統，其設計和實現中采用了小操作合并，基于操作日志的更新等提高吞吐量的技術。硬幣的兩面在使用過程中逐步顯現：高吞吐量和低延遲是兩個矛盾的目標。既然要低延遲，上Storm，上Redis。在2011年，我們在Hadoop的批處理的基礎上，為我們的統計平臺增加了實時計算能力。下面這張圖，大約反映了一種典型的架構系統：如何使用兩種流派的計算系統解決計算問題。

　　看似完美的解決了高吞吐量和低延遲的矛盾，但是，核心業務問題沒有得到解決：業務人員需要在海量數據中，使用多維交叉的方式，不斷計算手里的數據。批量處理還是需要幾個小時，甚至一天才能出一批數據。流式處理只能算當前的數據，歷史數據無法回朔。

　　b) 白天鵝：傳統技術的缺陷

　　看待硬幣的兩面是一種視角，這也許是一種平庸的視角。如果不看硬幣，把硬幣當做金屬，尋找、發現、創造一種新的鑄造硬幣的方法，又是另外一種視角。2012年，我們跳出了傳統的視角（例如Hadoop、或者Storm的改造），重新觀察我們的問題。經過分析，我們得到一個結論：我們需要做的，是創造第三種計算方式，而不是繼續在兩種計算方式中挖潛。

　　如果我們把傳統系統看作白天鵝，并把高速的、靈活的多維交叉分析當作飛行的目標，我們應該看看白天鵝為什么飛得累，飛得慢？

　　第一個技術障礙是高I/O開銷，包括磁盤I/O和網絡I/O兩種主要開銷。傳統的數據存儲都是以行的方式存儲在磁盤文件中，而傳統的文件系統又都是為大文件連續讀寫做優化的。假如我們要做多維交叉分析，我們分析一下系統的運作過程：

1. 根據查詢需求，定位到數據在某些文件。
2. 從文件系統中提取文件。這里產生了磁盤開銷。
3. 如果是分布式系統（例如普遍使用Hadoop），這里產生了高昂的網絡傳輸開銷。
4. 然后需要按行的方式，從文件中提取數據。這里會碰到一個非常隱蔽的問題，每行數據中會有大量的信息對本次查詢無任何意義（可能造成非常巨大且不幸的浪費）。

　　第二個技術障礙是計算相對低效。傳統計算中，把大量的CPU和內存放到了數據裝載，數據過濾等等（上面的浪費就是例子）。

　　新一代的計算體系的設計重點是降低整體IO，并盡量讓計算資源用在真正有價值的點上。

　　c) 從白天鵝到黑天鵝

　　我們用了三種法寶克服上面的缺陷，以提高整體計算效率：

1. 預處理：盡量降低低效的文件讀取在整個計算過程中的比重。
2. 壓縮：使用高壓縮比的壓縮算法將需要計算的數據壓縮到最小（同時不影響計算精度）。
3. 內存計算：將計算需要的全量數據全部一次性裝載入內存，這樣可以最大程度的將CPU的計算能力用于業務計算。

　　那么到底是哪只黑天鵝將以上的優點集于一身內？它就是Bitmap。

　　三、Bitmap的秘密

　　a) Bitmap如何做到多維交叉計算的？

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

　　Bitmap可以理解為通過一個bit數組來存儲特定數據的一種數據結構；由于bit是數據的最小單位，所以這種數據結構往往是非常節省存儲空間。比如一個公司有8個員工，現在需要記錄公司的考勤記錄，傳統的方案是記錄下每天正常考勤的員工的ID列表，比如2012-01-01:[1,2,3,4,5,6,7,8]。假如員工ID采用byte數據類型，則保存每天的考勤記錄需要N個byte，其中N是當天考勤的總人數。另一種方案則是構造一個8bit（01110011）的數組，將這8個員工跟員工號分別映射到這8個位置，如果當天正常考勤了，則將對應的這個位置置為1，否則置為0；這樣可以每天采用恒定的1個byte即可保存當天的考勤記錄。

　　綜上所述，Bitmap節省大量的存儲空間，因此可以被一次性加載到內存中。再看其結構的另一個更重要的特點，它也顯現出巨大威力：就是很方便通過位的運算（AND/OR/XOR/NOT），高效的對多個Bitmap數據進行處理，這點很重要，它直接的支持了多維交叉計算能力。比如上邊的考勤的例子里，如果想知道哪個員工最近兩天都沒來，只要將昨天的Bitmap和今天的Bitmap做一個按位的“OR”計算，然后檢查那些位置是0，就可以得到最近兩天都沒來的員工的數據了，比如：

　　再比如，我們想知道哪些男員工沒來？我們可以在此結果上再“And”上一個Bitmap就能得到結果。

　　b) Bitmap如何做到高速運算的？

　　回憶一下前面，浪費的有兩個部分：其一是存儲空間的浪費，Bitmap比文件強多了，但是仍然有浪費的嫌疑。它需要保存到外部存儲（數據庫或者文件），計算時需要從外部存儲加載到內存，因此存儲的Bitmap越大，需要的外部存儲空間就越大；并且計算時I/O的消耗會更大，加載Bitmap的時間也越長。其二是計算資源的浪費，計算時要加載到內存，越大的Bitmap消耗的內存越多；位數越多，計算時消耗的cpu時間也越多。

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

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

　　RLE編碼很簡單，比較適合有很多連續字符的數據，比如以下邊的Bitmap為例：

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

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

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

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

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

　　c) Bitmap在大數據計算上的能力？

　　我們用一個TalkingData Analytics中用戶留存的例子來看Bitmap如何做到用戶回訪的統計。比如想知道某個應用，昨天新增的用戶中，有多少人今天又開啟了應用（次日留存）。使用過Hive的工程師，不難理解下面語句的含義：

　　同時，我們使用Bitmap技術后，同樣實現上述的計算，對比測試顯示出效率的差異是巨大的：

　　d) 引入Bitmap技術后，分析系統可能的處理流程大體是什么樣的？

1. 數據收集系統收集設備上傳數據，然后分發給實時處理系統和批量處理系統；
2. 實時系統采用自有計數器程序，或者基于Storm之類中間件的計數器程序，計算各類簡單計數器，然后批量（比如30s或者1min）更新到Redis或者HBase之類的存儲；前端供應計數器類數據的服務通過訪問后臺計算器程序或者是計數器存儲來給報表系統提供服務；
3. 批量系統對該批的數據按用戶進行去重生成/修改某天/某個應用的活躍用戶Bitmap，同時可以根據需要，將機型、地域、操作系統等等各種數據提煉成屬性Bitmap，備用。
4. 報表中針對分析需要，提取各種Bitmap（用戶、屬性……Bitmap），高效的利用CPU/內存，通過組合And/Or/Not等基礎計算，最終完成多維交叉計算功能，反饋客戶結果。

　　四、黑天鵝的未來

　　TalkingData提供給客戶大數據下高速的多維交叉計算能力，還只是一個開始。在大數據時代，技術的發展必將推動業務的進化。TalkingData的未來在于提供客戶更快速、更便捷、更靈活的數據服務。黑天鵝也遇到了更多的問題，需要逐一解決。

　　a) 內存映射文件

　　比如即便用了優化的壓縮技術，Bitmap從文件中遷移到內存中的速度相對來說還是短板。例如系統構建初期，我們曾經把Bitmap存儲在Mysql中，感覺還不錯，不過隨著數據量的增加，隨機讀的問題越來越嚴重：大約一次查詢中，90%的時間全部被Mysql占去（某些開銷是挺浪費的，例如Mysql一次SQL的執行計劃，怎么都需要1ms左右）。下一步，我們計劃采用“內存映射文件”技術來解決這個問題。

　　內存映射文件與虛擬內存有些類似，通過內存映射文件可以保留一個地址空間的區域，同時將物理存儲器提交給此區域，只是內存文件映射的物理存儲器來自一個已經存在于磁盤上的文件，而非系統的頁文件，而且在對該文件進行操作之前必須首先對文件進行映射，就如同將整個文件從磁盤加載到內存。

　　由此可以看出，使用內存映射文件處理存儲于磁盤上的文件時，將不必再對文件執行I/O操作，這意味著在對文件進行處理時將不必再為文件申請并分配緩存，所有的文件緩存操作均由系統直接管理，由于取消了將文件數據加載到內存、數據從內存到文件的回寫以及釋放內存塊等步驟，使得內存映射文件在處理大數據量的文件時能起到相當重要的作用。

　　b) 分布式Bitmap計算

　　可以預見到的第二個Bitmap計算的難題是：我們有可能遇到“需要非常巨大的計算能力才能解決的問題”。舉個簡單的例子，假如一個客戶想看幾年的數據指標，那么有可能需要提取出成千上萬個，甚至幾十萬個Bitmap，放到內存中進行計算，這是相當恐怖的要求。

　　TalkingData第一代Bitmap計算引擎，雖然利用了諸如“Fork-join”技術最大程度的利用CPU/內存，但是遇到上面的計算要求，肯定還是力不從心。第二代Bitmap計算引擎，采用分布式計算：把一個需要非常巨大的計算能力才能解決的問題分成許多小的部分，然后把這些部分分配給許多計算機進行處理，最后把這些計算結果綜合起來得到最終的結果。

　　請大家注意一下Bitmap天生的特性，其實一個Bitmap代表了一個集合，同時它支持的計算中，就是集合計算中的“And/OR/Not”。大家可以在這個wiki上復習一下“集合代數”的知識。

　　http://zh.wikipedia.org/wiki/%E9%9B%86%E5%90%88%E4%BB%A3%E6%95%B0

　　這里面有一些給分布式Bitmap計算提供了理論基礎，下面這張圖表達的是分配律：

　　假如我們有三個集合，分別是A（去過美國的游客），B（去過中國的游客），C（使用IOS設備的游客）。現在業務人員要求找出，既去過美國，又去過中國，同時又使用IOS設備的游客。最直接的計算是：（A∩B）∪C，但是假如我們在分布式系統的視角下，我們可以分拆后的計算是：（A∪C）∩（B∪C），可以在兩臺計算節點上分別計算，再匯總到中心節點獲得最后結果。基于這些集合代數計算的原理，我們可以把復雜的多維交叉分析，分解成很多小單元計算，分配到不同的服務器上計算，再做匯總計算得到結果。

　　原理簡單，但是執行起來還是有很多困難的，比如數據傾斜、分拆計算優化、在高并發下解決負載均衡……任重道遠！

　　總結

　　當我最近閱讀30年前的Paper的時候，我發現科學領域的寬廣和深度。大約在30年前，天體物理學家利用基數計算（Bitmap就是一種基數計算）來解釋恒星數據，除此以外，還有時間序列分析和頻譜分析。我們今天研究某個產品在時間上的規律，還有一個人群使用產品的頻率特征，不就是這些計算科學在商業世界的再實踐嗎？

　　從歷史觀的角度來看，這些計算科學很早就已經存在，而現代多數程序員由于需要學習各種各樣的IDE、語言，忽視了這些基礎算法的學習和實踐，要持續、有效地發展個人和團隊，后者恰恰更重要。Bitmap技術不但讓我們支持了業務的發展，也證明了我們走在一條正確的路上：透過現象看本質，從基礎的算法出發，吸收各種技術流派的思想，創造屬于自己的技術，反饋和服務于技術社區。這就是TalkingData的技術底蘊。