1.業務背景

DMP（數據管理平臺）為廣告部門提供B站用戶數據的管理。主要功能包括用戶標簽收集存儲，標簽市場建設，人群包圈選，人群畫像分析，人群/特征定向幾大功能模塊。

其中人群包圈選和人群畫像分析是兩大核心功能。對設計，性能，擴展性，可維護性都有比較高的要求。也是本文中要討論的ClickHouse技術的應用場景。在實踐中，我們利用ClickHouse的bitmap相關功能，實現了人群包的實時預估和計算，也實現了人群包畫像的分鐘級計算。

下面先簡單介紹下人群包圈選和人群畫像兩個功能。

 1.1 人群圈選

所謂人群圈選，就是由用戶根據標簽指定一系列規則，然后通過這個規則把滿足條件的人群圈選出來。假設我們用戶有“性別”，“年齡”，“地域”三個維度的標簽，那么圈選規則就可以是“性別男，年齡>30，北京地區”。該系統需要根據圈選規則實時輸出滿足條件的人數和人群包。

圖片

如上圖所示，用戶使用了性別，年齡，地域三個標簽取了交集，在下方實時顯示了對應的覆蓋人數。

這里的技術難點在于

• 用戶的圈選的規則非常靈活，可能涉及數十種標簽或人群包的交并運算，并且要求實時顯示計算結果。商業DMP中現有大約數百種標簽，hive表中原始數據量PB級，如果采用直接查hive表的方式，顯然是無法滿足性能要求的。
• 人群包數量多，目前日新增數百個人群包，加上需要刷新的舊人群包，每天需要計算上萬個人群包。

因此基于以上需求，需要設計一種高效靈活，可擴展的人群圈選手段。

 1.2 人群畫像

用戶打好人群包之后，可以對人群包中的用戶特征分析，如查看用戶的年齡，性別，地域分布，興趣愛好，up主關注，互動等等。例如下圖所示：

圖片

圖片

圖片

計算用戶畫像的基本原理是需要用人群包中的用戶id與每一個需要洞察的標簽值所對應的用戶id取交集，求出交集的人數后，計算該標簽值在人群包中的百分比或TGI。例如：標簽值"男"占比XX%, 標簽值"女"占比XX% 。人群畫像的技術難點有：

• 人群包人數多，從數萬到億。
• 計算量大，目前畫像包含數十個維度，每日按人群包X維度計算百分比和tgi排名，涉及數億次bitmap交并運算。

最早的DMP使用離線hive sql進行畫像計算，平均一個包畫像要等待2個小時，引入ClickHouse Bitmap技術后，畫像時間降到了分鐘級。

2.基于bitmap的人群圈選

2.1 bitmap基本原理及其在

人群圈選中的應用

bitmap是一種數據結構，可以用來表示一系列正整數的集合。底層是一系列連續的二進制bit位，每個bit位有一個索引序號，依次用1,2,3,4,5...自然數編號。每個bit位有兩種狀態，0或1。如果bit位為0表示這一位對應的索引序號的數字不在集合里，相反，如果bit位為1，表示對應的索引序號的數字在集合中。例如bitmap內容是01101,其中第2，3，5位（從左到右）是1，則該bitmap代表整數集合{2,3,5}。

B站用戶id是一個64位正整數，從1開始編號，無限增加。根據前面的描述，可以用bitmap來代表一系列id的集合。也就是說每個人群包的id集合都可以用一個bitmap來表示。

我們可以在邏輯上給每個標簽值創建一個bitmap，表示所有具有該標簽屬性的人群。這樣人群包的圈選就等價于多個標簽bitmap的交并差運算。以前面提到的規則”性別男，年齡>30，北京地區”為例，人群圈選過程如下：

圖片

如圖所示，系統預先分別給男，>30歲，北京地區建立三個bitmap索引，如果相應索引位的id在集合中，則把對應位置的bit位設置為1。根據人群圈選規則，對三個bitmap進行AND位運算，得到最終bitmap結果，也就是最終的人群包中包含{2,5,7,9}四個id。

以上就是基于bitmap圈選人群包的基本原理，在具體應用中，還解決了很多工程上的問題，例如：

• 支持可擴展的，任意維度的標簽圈選。目前支持標簽數量>300種，總數據量>1PB
• 打通離線數倉與ClickHouse之間的數據流，實現數倉到ClickHouse和ClickHouse到數倉的雙向數據格式轉換和傳輸，以及標簽元數據管理機制。
• 一個包含億級別的bitmap大小有數百MB，如果只存儲在單個bitmap中會導致計算效率下降，因此需要對bitmap的存儲方式進行優化。
• 開發相比原始ClickHouse sql更易于使用的DSL，通過DSL提高系統的易用性，擴展性和執行效率。

 2.2 實踐中遇到的bitmap相關問題

在具體實踐中，我們發現bitmap可以很好的解決離散標簽值的計算，對于億級的人群計算通常可以在5秒內完成。可以滿足大多數人群計算需求。但是仍然存在一些明顯的問題。

id不連續導致的性能問題

ClickHouse中使用Roaring Bitmap存儲bitmap數據，而在Roaring Bitmap內部，數據存儲在不同類型的container中，不同類型的container具有不同的空間成本和計算時間復雜度。Roaring Bitmap內的數據存儲為哪種類型的container是由數據特性決定的，其中一個重要特性就是數據的連續性。分布稀疏的數據連續性低，在Roaring Bitmap中消耗的空間成本和計算時間復雜度都會更高（有關Roaring Bitmap的內部存儲結構及其對計算存儲性能的影響在此不做詳細論述，有興趣的讀者可參見文章基于改進字典的大數據多維分析加速實踐中的第4章節）。

B站用戶的id是整型數據，我們在實踐中發現，id的分布非常稀疏，連續性低，這就造成bitmap體積膨脹，無法達到最佳性能，尤其是在計算畫像時，需要對數百萬的bitmap進行交并運算，bitmap體積過大，對磁盤IO和CPU都有很大的壓力。因此如何采用合適的方法讓bitmap中的id盡量連續分布，是我們的一個主要優化方向。

對于非離散標簽圈選支持受限

DMP的標簽中大部分都是離散標簽查詢，每個標簽值對應一個bitmap。所謂離散標簽值是指枚舉類的標簽值，例如性別，年齡，地域，關注的up主都屬于此類。對于這種標簽，每個標簽值對應的id聚合成bitmap后寫入ClickHouse是比較自然的選擇，ClickHouse對此類標簽的交并查詢支持也很好。

但是在業務需求中，還存在一些非離散的指標查詢，例如：“找出最近一個月某個廣告單元曝光次數大于N次的人”，“找出最近一個月某稿件播放時長大于N分鐘的人”。這些查詢的特點是需要在一定時間范圍內對某個實體的相關指標進行聚合，以廣告曝光次數為例，對應的hive sql大概如下所示：

SELECT
id
FROM (SELECT id, unit_id FROM ad_event_table WHERE
event='show' -- 曝光
AND unit_id IN (11111, 22222) -- 單元id列表
AND log_date >= '${yyyyMMdd, -360d}' -- 近一年
GROUP BY unit_id, id -- 按id + unit_id聚合
HAVING COUNT(1) > N -- 找出每個單元曝光次數大于N次的id ) t0
GROUP BY id -- 所有單元曝光次數>N的id進行去重

如果直接執行一個這樣一個hive sql，涉及的廣告曝光底表近一年的數據可能有數百G之多，至少要幾分鐘才會獲得結果，顯然是無法滿足dmp人數實時預估的要求的。

如果把一年的明細數據導入ClickHouse，在ClickHouse中做類似的查詢并把id實時聚合成bitmap，同樣面臨數據量大，無法滿足秒級人數預估的要求。作為一個折中的辦法，DMP中對于類似的查詢規定了一系列固定的時間窗口，如近30天，60天，90天，180天等等，事先通過離線任務按照固定的時間窗口對每個指標進行預聚合，把每個固定時間窗口內滿足某個指標的人事先聚合成bitmap寫入ClickHouse，用戶圈人的時候只能對固定的幾個時間窗口內的指標進行圈選。還是以上面單元近一年曝光為例，ClickHouse中的查詢如下：

SELECT groupBitmapOr(uid_index) AS `uid_index` -- id bitmap
FROM tag_index_table
WHERE (tag_name='ad_show') -- 廣告曝光
AND (log_date='${yyyyMMdd}') -- 每天更新全量數據
AND (tag_value IN ('360D-11111','360D-22222')) -- 事先聚合好360天的單元曝光，把范圍查詢變成幾個固定時間區間的點查
AND (metric>=N) -- 曝光指標 > N

上述查詢是把采用預聚合的方法把標簽值(單元id)+時間(天數)+指標值(metric)進行聚合，可以把范圍查詢近似成點查，滿足實時計算的需求，通常也可以在秒級返回結果。但是這種方案仍然有以下問題：

• 預聚合數據量大，多個時間窗口存在數據冗余，某些標簽要處理每天都要處理近一年的數據，有數百G到TB級，并且30，60，90等不同時間窗口存在重疊，有數據冗余。
• 標簽值x指標值造成標簽數據膨脹。指標值(metric)為非離散數據, 如曝光次數，播放時長，指標值可能在0到數千之間分布，假設某個廣告單元有1000個指標值，那僅這一個廣告單元就會有1000個bitmap（每個bitmap對應一個指標值），這就造成表中的數據行數很多，索引變大，增加了內存和緩存的開銷。
• 圈選方式不靈活。預處理的時間窗口只能處理一些典型的查詢，還有很多客戶就是要求實時圈選任意日期范圍內的指標，對于這部分需求ClickHouse無法滿足，只能采用spark離線計算。系統就分成了ClickHouse實時計算和spark離線計算兩個部分，增加了系統的復雜度和開發成本。

基于以上原因，我們也需要尋找一種更高效，更靈活的非離散指標標簽圈選方案。

3.ClickHouse字典服務

ClickHouse字典服務是B站ClickHouse團隊針對多個需要在ClickHouse中用Roaring Bitmap做交并補計算的場景而設計開發的一套字典映射服務。關于ClickHouse字典服務的架構及實現，本文不做詳細介紹，感興趣的讀者可參見文章基于改進字典的大數據多維分析加速實踐中的4.3章節，本文下一章節主要闡述該服務在DMP場景下的應用姿勢及效果。

4.ClickHouse字典服務在DMP中的應用

4.1 應用姿勢

首先，使用ClickHouse字典服務對于DMP場景有以下兩個好處：

• 字典服務的id是按順序分配的，可以讓id集中到更小的空間里，對于bitmap來說，id越集中，所生成的bitmap體積越小，運算效率越高。
• 標簽圈選不再局限于整數類型的id，通過字典服務把任意字符串映射成一個整數，比如設備號，buvid等等，為將來的產品功能擴充提供了更大的可能性。

加入字典服務后，整個數據流程如下：

圖片

如圖所示，在原始的id明細表調用字典服務做一次id映射，然后把映射后的id聚合成bitmap。具體還做了以下優化：

• 為了提高效率，減少線上壓力，字典服務每天導出一張離線hive表，業務方先關聯hive表獲取映射id，如果離線hive表中不存在，則通過RPC實時調用字典服務。字典初始化之后，離線表的映射率通常在90%以上，可以極大的減少線上服務的實時壓力。
• 優化了ClickHouse中不同shard中id的分片算法，每個id是一個64位整數，給定N個分片，則取個id的高48位（17~64位）對N取模，模數相同的id屬于通一個bitmap分片。之所以采用這種方法分片，是考慮到ClickHouse bitmap存儲的特點，讓低16位連續的id盡量處于同一個分片中，因為bitmap中連續的bit位越多，可以采用壓縮算法減少體積，提高計算效率。經過測試，在同等條件下，這種優化的分片方式比id直接對分片數N取模，要節省30%的存儲，計算速度快一倍以上。

 4.2 優化效果

引入ClickHouse字典服務后，我們在存儲成本、寫入性能、查詢性能等方面均取得了顯著收益，具體如下文所述。

存儲成本收益

存儲空間上，對于千萬到上億級別的bitmap，體積減少了約4.5倍，對于萬級別的小bitmap減少約1.4倍，平均減少3倍左右。bitmap越大，收益越大。

整體存儲空間收益如下圖所示：

圖片

查詢性能收益

對于查詢延遲較高的人群畫像計算，引入ClickHouse字典服務后查詢性能大幅提升，end2end查詢延遲由之前的20分鐘提升到3分鐘，提升了6.7倍。

從ClickHouse引擎側觀察，DMP場景整體查詢P50，P90延遲優化效果如下圖所示：

圖片

寫入性能收益

在寫入方面，p90寫入延遲降低了2x+，p50寫入延遲降低了1.5x。

整體寫入P50，P90延遲優化效果如下圖所示：

圖片

5  BSI原理簡介及其在ClickHouse中的功能實現

5.1 BSI原理簡介

BSI(Bit-slice index)的數據結構由一組bitmap組成，其中每個bitmap用于表示二進制整型metric在對應比特位上取值為1的實體id集合。

下圖展示了將5個實體id及其對應的整型metric value轉換成BSI表示形式后的效果：

圖片

從上圖的轉換中，我們可以總結出BSI數據結構的以下特征：

• BSI的slice個數由最大整型值的二進制位數決定
• 每個slice都是一個bitmap
• 每個slice對應一個比特位：slice_i 存儲第i個比特位上取值為1的metric value對應的所有實體id的集合

如上文所述，bitmap適用于離散值標簽的人群圈選計算場景，而BSI則更適合針對連續值指標的人群圈選計算場景。除此之外，BSI也適合用于人群圈選完成之后的人群效果指標分析場景（比如，計算某個指定人群包的平均曝光次數）。

5.2 BSI在ClickHouse中的功能實現

BSI數據類型

在ClickHouse中，我們將BSI封裝成一個新的數據類型，用戶可以根據自己的需求定義BSI類型字段并配合ClickHouse中的aggregating mergetree引擎建表，建表示例如下：

CREATE TABLE test.bsi
(
    `log_date` Date,
    ...
    `ck_bucket` UInt32,
    `bsi_agg` AggregateFunction(bsi_merge_agg, BSI)
)
ENGINE = AggregatingMergeTree
PARTITION BY log_date
ORDER BY ck_bucket
TTL ...

具體實現上，BSI本質上就是Bitmap Array，所以我們并沒有重新實現一個獨立的數據類型，而是基于ClickHouse內部的自定義數據類型注冊機制，將Bitmap Array類型注冊為一個新的BSI數據類型。

除了各個比特位對應的slice bitmaps之外，BSI類型數據中還存儲了一個existence bitmap（EBM），用于表示所有metric取值非空(not null)的實體id集合。EBM可用于加速某些BSI計算，并且對于某些BSI functions而言EBM是必需的。

BSI Functions

我們在ClickHouse中實現了許多BSI Functions，包括:

• 用于從明細數據構建BSI的bsi_build
• 用于對單個BSI進行過濾，求和等操作的bsi_filter, bsi_sum, bsi_range, bsi_lt, bsi_gt, bsi_topk, etc
• 用于對BSI數據列做聚合的bsi_add_agg, bsi_merge_agg, etc

關于各個BSI Function的功能細節這里不做詳細闡述，有興趣的讀者可參見引用[2]。

由于BSI Functions的底層實現上依賴于Roaring Bitmap的交并補計算，所以對組成BSI的Roaring Bitmap做ClickHouse字典服務映射也能夠大幅提升BSI Functions的計算性能。

6.BSI+字典服務方案在DMP場景的落地及效果

6.1 落地姿勢

針對DMP場景下連續值指標圈選困難的問題，我們基于連續值指標的明細數據構建出連續值指標的BSI數據，然后導入到ClickHouse中通過BSI Functions即可對連續值指標進行任意時間范圍內的圈選，解決了原來只能預聚合固定時間窗口的查詢限制。

下圖是寫入與查詢BSI數據的整體流程：

圖片

BSI數據寫入

我們的明細數據存儲在離線數倉Hive表中，利用Spark程序將Hive上的明細數據轉換成BSI（bitmap array）結構后寫入到ClickHouse表中。其中，Spark數據同步程序會調用生成BSI數據的UDAF將明細數據組裝成為BSI，同時會調用ClickHouse字典服務進行字典映射轉換，從而降低BSI的存儲成本和查詢延遲。

以上文提及的廣告曝光查詢為例，使用BSI后，數倉開發在進行數據處理時不再需要按照標簽值(單元id)+時間(時間窗口天數)+指標值(metric)進行聚合，每天只需要處理當天的增量日志即可，把當天增量的單元曝光聚合成一個BSI即可。

BSI數據查詢

上述BSI寫入ClickHouse后，業務方就可以通過bsi相關的函數在ClickHouse中實時查詢，以廣告曝光為例，一個典型的表結構和查詢語句如下所示：

CREATE TABLE tag_bitmap_bsi
(
    `tag_name` String,
    `tag_value` String,
    `log_date` Date,
    `sp_bucket` UInt32,
    `sk_bucket` UInt32,
    `ck_bucket` UInt32,
    `bsi_agg` AggregateFunction(bsi_merge_agg, BSI)
)
ENGINE = ReplicatedAggregatingMergeTree(...)
PARTITION BY (toYYYYMMDD(log_date), tag_name)
ORDER BY (sp_bucket, tag_value, ck_bucket)
TTL ...
    
 
SELECT groupBitmapOr(bsi_ge(bsi_agg, N)) AS `uid_index` -- 180天內曝光次數>N次的id組成的bitmap
FROM
(
   SELECT bsi_add_agg(bsi_agg) AS `bsi_agg`
   FROM
   (
      SELECT tag_value, bsi_merge_aggMerge(bsi_agg) AS `bsi_agg` -- 一天之內的指標合并（去重）
      FROM
        tag_bitmap_index_mapped_bsi
      WHERE (tag_name = 'ad_show') AND (log_date > '${yyyyMMdd}' - INTERVAL 180 DAY -- 近180天 ) AND (tag_value IN ('11111', '22222'))
              GROUP BY tag_value, log_date
   )
   GROUP BY
   tag_value -- 最終累加出180天內所有的指標
)

6.2 落地過程遇到的問題及其解決方案

在將BSI落地到，我們遇到了以下問題：

• 在Spark數據同步程序中生成的單個BSI過大，導致spark中的一個row對象過大，在Kryo Serializer做序列化的過程中出現buffer overflow的問題。
• 寫入到ClickHouse各個分片的BSI里的bitmap數據分布稀疏，影響BSI查詢性能。
• 寫入到ClickHouse單個分片的BSI的基數過大（即包含的實體id過多），導致單分片BSI的查詢性能較低。
• ClickHouse中由于分批寫入導致存儲的BSI個數過大，影響BSI的查詢性能。

為了解決上述問題，我們做了以下設計與優化：

圖片

• 在Spark數據同步程序中對明細數據做分桶處理，以避免單條BSI記錄過大導致Kryo Serializer的buffer overflow問題。
• 在Spark數據同步程序中引入ClickHouse字典服務，對分布稀疏的實體id做字典映射，提高BSI內數據的連續性，從而提升BSI查詢性能。
• 使用實體id的高48位做sharding，讓實體id高48位相同的數據都寫入到相同的ClickHouse分片中，降低單個分片中BSI的基數，同時進一步提高BSI內數據的連續性，從而提升BSI查詢性能。
• 使用AggregatingMergeTree作為表引擎，分批寫入的小BSI數據異步聚合成更大的BSI數據，減少ClickHouse中的BSI記錄個數，從而提升BSI查詢性能。

6.3 落地效果與收益

產品功能增強

引入BSI后，DMP在產品功能上得到以下增強與優化：

• 實現了任意日期的指標人群圈選，不再局限于幾個固定的時間窗口，擴展了業務的應用場景。
• 去除了部分通過spark sql離線計算流程，把所有人群包相關的計算統一到ClickHouse里，簡化了系統設計。
• 對于廣告曝光，稿件播放這種數據量大標簽時間范圍從30天提升到一年，提升了產品的能力。

整體場景查詢性能

圖片

受益于BSI和字典服務對查詢性能和存儲成本的優化，生產業務在使用BSI+字典服務的方案后，將之前30天~90天的時間范圍圈選擴大到了一年，目前整體的p50查詢延遲可以保證在500ms左右，p90查詢延遲可以保證在5s左右。

存儲成本收益

相較于通過預聚合不同時間范圍的bitmap數據來支持任意日期范圍的人群圈選，BSI+字典服務的方案在存儲成本上具有顯著優勢，以下是一個支持5天內任意日期范圍圈選場景下，預聚合bitmap方案和BSI方案的存儲成本對比：

可以看到，BSI+字典服務的方案與預聚合Bitmap方案的存儲比約為1:21。

查詢性能收益

相較于原Bitmap方案，BSI+字典服務的方案在查詢性能方面也有明顯優勢。下圖為一個90天范圍內圈選場景，原Bitmap方案和BSI方案的查詢延遲對比：

圖片

7.總結與展望

本文重點介紹了DMP場景的業務需求及實踐過程中遇到的問題，并詳細闡述了我們如何利用ClickHouse字典服務和BSI技術優化增強DMP產品功能，提升整體查詢性能，降低資源成本。

目前BSI+字典服務方案已經在B站商業化DMP場景完成落地上線，未來我們將重點在以下方向完善增強我們的產品功能：

• 工程化BSI+字典服務方案的數據接入流程，為用戶提供更為便利的接入體驗，讓BSI+字典服務方案賦能更多商業化業務場景。
• 探索BSI+字典服務的實時鏈路建設，在低成本低查詢延遲的前提下，為用戶提供更高的end2end數據時效性。
• 得益于字典對人群圈選性能的提升，商業化業務正在嘗試擴展人群圈選的業務范圍，例如投放端定向人數預估，預計24年Q4可以落地。
• 商業化DMP中嘗試BSI的更多應用場景，例如用于多維度廣告相關指標人群的畫像分析。

引用

• BSI Introduction From Hologres（https://www.alibabacloud.com/help/en/hologres/use-cases/profile-analysis-bsi-optimization-beta）
• BSI Function Introduction From Hologres（https://www.alibabacloud.com/help/en/hologres/user-guide/bsi-functions）