本文根據58同城何良均老師在DataFunTalk數據主題技術沙龍活動“大數據從底層處理到數據驅動業務”中分享的《Bit Map在大數據精準營銷中的應用》編輯整理而成，在未改變原意的基礎上稍作修改。
今天分享主題分為四個方面，第一個是項目背景，第二個依據項目需求的技術選型，接著就是項目架構，最後講一下項目實現過程中的一些細節。
我們的數據主要有兩種，一種是用戶賬號數據，數據量有十億，這些數據包括很多類型，比如uid，用戶設備號等。還有就是用戶標籤數據，也達到千萬級，包含數據用的社會屬性，比如性別、年齡段等，也包括用戶的興趣愛好以及最近的上網行為標籤，其實這類數據就是用戶畫像。這類數據就對應相應的產品線，如精準營銷中有個“易獲客”項目，這個項目背景就是客戶在頁面通過用戶標籤快速精準匹配用戶群體，然後通過短信、電話進行營銷。當時有兩種部署方式，一種是公司部署一套，客戶通過外網訪問；另外一種就是有些客戶對數據安全性比較高，我們會把服務部署到客戶，客戶就在頁面選擇一些標籤，點擊查詢返回滿足要求用戶信息。
技術選型依據數據特點，數據量大但也不是特別大，有千萬級標籤+十億級用戶；依據項目需求，需要很多維度，用戶標籤分佈於幾百上千個維度，沒有度量概念，度量和維度都是olap中的概念。除了數據之外還有產品要求，需要在線應用，性能要求較高，必須做到毫秒級響應；數據量不斷增長，必須做到底層數據存儲和計算可擴展性以應對數據量的增加；同時希望產品不屬於用戶方，再出現問題時能夠很容易恢復，需要代碼可控。
基於這些需求，對開源技術進行相關調研，像Kylin/Druid都是多維分析常見的工具，但是我們並沒有使用。這兩個框架都會做一些數據預計算/聚合，都能做到亞秒級查詢，像Kylin底層是基於HBase可擴展性很強，Druid本身就是一個分佈式系統，兩個框架都是開源。但是我們選用Bit，因為依據數據需求簡單而且Bit只有維度沒有度量，還有就是維度個數多，查詢是基於用戶uid，查詢明細數據。在查詢明細中Druid有兩個問題，如果將uid和維度存儲Kylin和Druid，對維度的基數有限制，會構建維度字典，光一個uid就有4G，因此在幾百上千維度查詢效率會降低；還有一個就是uid用戶量大，Kylin和Druid會將uid和其他維度進行組合會出現很多情況，會額外增加數據量，因此這種請款也不適合用Kylin，還有就是Kylin會對維度構建索引，uid索引會很大，查詢效率也是很低。基於這些要求還有其他一些技術需求，最終方案是使用HBASE+BitMap的自研框架，HBASE主要做數據存儲，將HBASE做處理器做並行計算，BitMap構建索引。
HBASE是由一個active和region master作為服務主節點，有Hfile子節點和多個region server，底層是HDFS層，每一個region server管理很多region，每一個region會根據數據量會有很多Store file，這幾者是依靠客戶端協調。接著說一下HBASE表分區，HBASE表裡面很為很多region，我們一般會設置每個region的最大值達到最大值自動分裂。而每一個region會有管理範圍，分區是用region server管理。
HBASE有很多特點，第一個就是海量存儲，其底層是基於HDFS，是橫向存儲，可以加很多節點，支持PB級數據存儲；按列存儲，將樹屬性相似的放到列組裡面，壓縮比比較高；第三個就是極易擴展，分為存儲和計算，都是分佈式存儲和計算；然後高併發，單機讀寫性能在2w+；第五個就是稀疏，當列中屬性為空，不佔用存儲空間。
前面講存儲是HBASE，計算是HBASE協處理器，HBASE協處理器分為兩種，一種是Endpoint，一種是region server。與數據中存儲過程和觸發器類似，項目用的是Endpoint，類似於數據庫中的存儲過程。上圖左右兩邊目的相同都是統計表的行數，不用協處理器會直接在命令行中count相關表，從每一個region裡面掃描最後得到結果，這種方式耗時很大，由於串行計算，同時會將數據從服務端加載到客戶端。Endpoint會以並行方式實現，會將客戶端請求發送到所有region上，每個region分擔數據量，最後將數據返回協處理器客戶端，然後彙總聚合，這樣運行速度快很多。速度快一個是並行計算，另一個是將計算的數據移動到服務端，這樣數據穩定性高，直接從本地加載數據計算也會減少開銷，協處理器返回客戶端是數據的數量。
可能你們會對BitMap瞭解很少，其應用場景比較單一，但是在某些方面效果比較好。BitMap底層實現是一個位數組，位數組的value取值只能是0或1，因為是數組，數組下標是整數範圍內的取值，最大為2147483647。上圖中長度為10的BitMap，通過BitMap的api進行相關設置，會將對應的下標設置為1，如圖中6、3、5、7的下標都設為1。BitMap可以進行布爾計算，可以求交集和求並集，其取值是0或1（或者是或否，出現與不出現），節省存儲空間。BitMap的應用一個是數據排序，排序要求數據不能重複。第二個就是Bloom filter，是對應於一組hashmap對應一個BitMap，是犧牲一定錯誤率來釋放存儲空間，如在HBASE的索引和爬蟲URL判重。但是重點是作為索引，其實它在數據庫、搜索引擎和OLAP應用很多。
舉一個例子說明下，如上圖是一個數據表有四列，下面是一個簡單查詢，查詢有性別和婚姻狀況兩個維度，性別有兩個取值，婚姻狀況有三個取值，BitMap首先會在維度裡面構建BitMap，第一步如何構建性別的BitMap，對於性別這個列，位圖索引形成兩個向量，男向量為10100...，向量的每一位表示該行是否是男，如果是則位1，否為0，同理，女向量位01011。第二部構建婚姻狀況的BitMap，婚姻狀況這一列，位圖索引生成三個向量，已婚為11000...，未婚為00100...，離婚為00010...。這樣就構建完需要查詢的BitMap，首先將性別為男的標籤拿出來，然後將婚姻狀況為未婚的標籤拿出來求交，這樣就定為下標為2，就查出滿足需要的結果。
BitMap有很多實現方式，構建框架也有很多。最後我們選用Roaring Bitmap，選擇的原因在於：我們存儲的是整數，將下標標籤取值設為1，該框架將整數i的高16位會被用於構造塊，存儲到keys中，低16位則被看做value，存儲到Container[] values中的某個Container中，兩個數組通過下標對應。BitMap是分快實現的，有三個特點就是分塊存儲、壓縮、計算，這樣在BitMap使用時可以按塊解壓節省內存空間。但是在計算時必須全部解壓。Roaring Bitmap在開源框架裡應用很多，如olap中有kylin、Druid、piont等，搜索引擎方面有Lucene、slor、Elasticserach等，還有spark、hive、tez等。也有很多實現語言，比如Java、C、C++、Python等。
前面介紹了項目背景、技術選型，接下來介紹下基於HBASE和BitMap實現的項目框架構建。上圖是項目整體架構，因為是用戶從頁面構建標籤，因此從上到下分為幾個模塊。可視化層，給用戶提供頁面，選擇標籤，然後接口層傳入標籤，提供API服務，將選擇標籤傳入路由層，構建索引服務，在索引服務中會判斷是存客營銷還是新客營銷，頁面標籤是求交還是求並；然後索引服務將標籤部署於服務器的region server上，在存儲計算層，通過協處理器存儲查詢。通過標籤和startkey構建rowkey，然後查詢數據，在BitMap中進行求交、求並的操作，最後將結果返回給索引服務，索引服務將結果返回前端頁面，用戶拿到的是匹配到的uid。存儲計算層還好，主要發費在數據準備階段，需要考慮很多東西。數據量大（十億級標籤）並不能直接構建BitMap，需要做這些用戶標籤做MR生成倒排、uid分桶、gid轉id，通過bulkload生成BitMap索引，然後傳入region server裡面，提供相關服務。
數據準備層完成uid轉連續整數id，根據最大id分桶，標籤分桶生成Bit Map索引，並序列化後生成HFile，Bulkload Bit Map索引。存儲計算層完成Hbase：存儲索引數據，Hbase cop：分佈式計算，Roaring Bitmap ：索引，布爾計算，求交求並。路由層實現計算請求參數：新客營銷、存客營銷，將請求通過cop路由到Region Server。接口層完成使用netty構建http服務，接受前端查詢請求並解析接口層。可視化層完成標籤選擇，查詢客群，下載客群。
接下來講一下第四部分實現細節，講幾個關鍵重點：id分區，分區構建BitMap索引，coprocessor實現。用戶有十億，並不是直接將數據構建BitMap，會對id進行分區，依據分區構建BitMap。將uid進行轉義成id，為連續整數，因為BitMap裡面是整數。原始表有很多維度，每個維度有很多標籤，通過標籤求交求並篩選出需要的結果。
Id分區有兩個問題，一個是為什麼id要分區，第二個是如何進行id分區。首先說第一個，BitMap是依據標籤查詢的，id不分區，下標很長，十億標籤有100M，不能很好結合hbase協處理器的並行計算能力，查詢效率很低；每個標籤構建的bitmap索引長度達到10億級，存儲開銷大；id不分區，如果id超過了整數最大範圍，無法構建bitmap索引。
接下來說一下如何進行id分區，id分區用到協處理器，結合hbase表分區實現。如10億id，分成200個區，每個區包含500萬個id，和hbase表region startkey/endkey進行對應。如和region裡面的rowkey，0-500萬相當於第一個分區，region分區是和hbase分區結合在一起，因此每個region只包含500萬個賬號。同時我們指定rowkey範圍，不需要hbase表進行分裂，將進行關聯hbase表region設置成分區不可分裂，在建表的時候預先建好分區。下面是項目中建立表分區代碼事例，將十億數據分為200個分區：create 'index', {METHOD => 'table_att', METADATA=> {'SPLIT_POLICY' => 'org.apache.hadoop.hbase.regionserver.Disabled Region Split Policy'}},{NAME=>'d',COMPRESSION => 'SNAPPY'}, SPLITS => [‘0005000000’, ‘0010000000’, ‘0015000000’, ‘0020000000’, ‘0025000000’,‘0030000000’, ... ,‘09950000000' , '10000000000']。
建好表後就是如何構建索引，每一個分區對應500萬的數據，通過roam構建BitMap時，會輸出rowkey和value。將每一個region裡面的標籤設為key，標籤會對應BitMap，region有範圍只會生成相應的BitMap。如第一個region，startkey為0，構建的標籤為200萬，對應的下標是500萬，region對應的是500萬，存儲的是500萬-1000萬的id，存儲時會減去相應範圍，因此長度還是固定的。
BitMap有幾個特點：每個分區包含部分id，每個分區包含所有標籤，Rowkey：startkey_tag，Value：Bit Map索引，Bit Map下標範圍[0,500萬)。在後續分區可能id很大，但是會startkey和id set設置一定偏移量，保證id取值範圍永遠是0-500萬，避免id過大超出整數取值範圍，避免用戶量過大超出BitMap索引。如在region3裡面構建BitMap的例子，startkey是1500萬，每一個標籤對應一個索引。
建完索引，接著就是協處理器實現——coprocessor實現，這個其實比較關鍵，扮演著並行計算的角色。如從很多標籤篩選用戶，裡面可能有很多求交求並關係。協處理器會從客戶端通過索引服務解析求交求並的關係，傳給region server，傳給協處理器的服務端，傳入的參數並未發生變化。在region server會自動更新邏輯，會返回匹配到的id。Cop-client會組織標籤之間的計算關係，即求交求並關係；將標籤關係發送給Cop-server，比如查詢select id from table where Dim1=tag1_3 and (Dim3=tag3_1 or Dim3=tag3_2 or Dim3=tag3_3 or …) and … and (Dim..n= tagn_1 or Dim..n=tagn_2 or …) ;用戶選擇相應維度，返回標籤，協處理器客戶端會將標籤重新組織，變成相關關係tag1_3 and (tag3_1 or tag3_2 or tag3_3 or …) and … and (tagn_1 or tagn_2 or …)，發給協處理器服務端。
上圖是協處理器服務端完成的任務，首先拿到客戶端返回的參數，主要是標籤，第一步通過標籤+startkey，構建rowkey，根據rowkey在當前region查詢BitMap，然後依據標籤間關係，對BitMap求交求並計算；最後返回一個BitMap和startkey返回給協處理器客戶端。
客戶端拿到服務端返回的startkey和BitMap，可能有很多組，因此獲取所有Region執行Cop後返回的startkey和Bit Map，然後在客戶端返回匹配到的id，將所有region返回的結果聚合返回給用戶。上圖是region3的例子，返回startkey加上BitMap取值為1的下標，就得到查詢到的id。
——END
閱讀更多 datafuntalk 的文章
