使用RoaringBitmap的方案的可以適用于如下場(chǎng)景。

• 標(biāo)簽數(shù)量多：需要對(duì)多張大表進(jìn)行關(guān)聯(lián)運(yùn)算，可以使用BITMAP_AND替換JOIN運(yùn)算，可以降低內(nèi)存消耗，Bitmap插件庫(kù)使用SIMD指令優(yōu)化可以將CPU使用率提升1~2個(gè)數(shù)量級(jí)。

• 數(shù)據(jù)規(guī)模大且需去重運(yùn)算：如數(shù)十億數(shù)據(jù)需要去重，Bitmap結(jié)構(gòu)天然去重，避免精確UV計(jì)算和內(nèi)存的開銷。

在介紹Bitmap計(jì)算方案之前，我們需要區(qū)分畫像系統(tǒng)中常用的兩類標(biāo)簽數(shù)據(jù)，針對(duì)這兩類數(shù)據(jù)的計(jì)算模式大相徑庭，我們需要依據(jù)數(shù)據(jù)模型和運(yùn)算模式將合理的部分轉(zhuǎn)化為Bitmap格式存儲(chǔ)。

• 屬性標(biāo)簽：主要描述用戶的屬性情況，例如用戶性別、所在省份、已婚狀態(tài)等，數(shù)據(jù)相對(duì)穩(wěn)定，通常進(jìn)行精準(zhǔn)條件過濾。這類數(shù)據(jù)進(jìn)行Bitmap壓縮比會(huì)很高，且Bitmap適合對(duì)應(yīng)的運(yùn)算。

• 行為標(biāo)簽：主要描述用戶行為特征，描述用戶在某個(gè)時(shí)間做了一件什么事，比如用戶店鋪瀏覽購(gòu)買行為、用戶登錄活躍行為等，數(shù)據(jù)變更頻率高，通常需要進(jìn)行范圍掃描，聚合過濾。這類數(shù)據(jù)不適合進(jìn)行Bitmap壓縮，壓縮比會(huì)很差，運(yùn)算模式不適合Bitmap直接運(yùn)算。

屬性標(biāo)簽處理場(chǎng)景通常是描述用戶的屬性情況，數(shù)據(jù)相對(duì)穩(wěn)定，通常進(jìn)行精準(zhǔn)條件過濾，通過Bitmap能實(shí)現(xiàn)高效的壓縮和運(yùn)算。

• 方案介紹

  假設(shè)現(xiàn)有的DMP（Data Management Platform）系統(tǒng)中存在兩張屬性標(biāo)簽表，如下圖所示。dws_userbase表描述用戶基礎(chǔ)屬性，dws_usercate_prefer表描述用戶偏好。

  典型的人群人數(shù)預(yù)估的場(chǎng)景比如計(jì)算[province = 北京] & [cate_prefer = 時(shí)裝] 的人數(shù)，通常可以關(guān)聯(lián)、過濾、去重最終獲得人數(shù)。但在數(shù)據(jù)規(guī)模較大的場(chǎng)景，關(guān)聯(lián)、去重運(yùn)算會(huì)帶來嚴(yán)重的性能負(fù)擔(dān)。

  Bitmap優(yōu)化方案通過預(yù)構(gòu)建標(biāo)簽的Bitmap表來減少即席運(yùn)算的成本，比如將兩張表中的列拆開分別構(gòu)建Bitmap表如下圖所示，通過兩表中對(duì)應(yīng)Bitmap的與運(yùn)算計(jì)算出人數(shù)。rb_dws_userbase_province表描述省份和uid的Bitmap關(guān)系，rb_dws_usercate_prefer_cprefer描述類目和uid的Bitmap關(guān)系。

  但是按列拆分的方案也存在一定的問題，當(dāng)多列之間存在層級(jí)的組織關(guān)系時(shí)，上述的拆分和運(yùn)算方式可能會(huì)導(dǎo)致計(jì)算錯(cuò)誤的情況，如下圖所示。在描述店鋪用戶新客、老客、潛客信息的dws_shop_cust表中，按照列拆分成描述店鋪名稱的Bitmap表rb_dws_shop_cust_shop_id，描述客戶類型的Bitmap表rb_dws_shop_cust_cust_type。當(dāng)計(jì)算[shop_id = A] & [cust_type = 新客] 的人群集合，會(huì)得到[1]的uid集合，然而在真實(shí)的表中這條數(shù)據(jù)不存在。產(chǎn)生這種錯(cuò)誤的原因是cust_type、shop_id兩個(gè)字段存在一定的關(guān)聯(lián)性，在數(shù)倉(cāng)模型中cust_type是shop_id維度的指標(biāo)數(shù)據(jù)，脫離統(tǒng)計(jì)維度單獨(dú)使用指標(biāo)是錯(cuò)誤的。因此可以將維度shop_id和指標(biāo)cust_type組合值作為構(gòu)建Bitmap的單元，生成rb_dws_shop_cust_sid_ctype表來避免這類錯(cuò)誤。

  根據(jù)以上方案介紹，需要將uid壓縮存儲(chǔ)進(jìn)Bitmap，通過Bitmap與或非運(yùn)算實(shí)現(xiàn)標(biāo)簽的對(duì)應(yīng)運(yùn)算。

• 方案實(shí)踐

  • 用戶信息編碼處理

    用戶標(biāo)識(shí)可能是字符類型的，由于Bitmap只能保存整數(shù)信息，因此需要先將uid進(jìn)行整數(shù)編碼進(jìn)Hologres中，可以通過插入包含自增序列Serial（Beta）的表完成字符ID的編碼。

    -- 創(chuàng)建字典表
    CREATE TABLE dws_uid_dict (
        encode_uid bigserial,
          uid text primary key
    );
    
    -- 錄入標(biāo)簽表中的uid
    INSERT INTO dws_uid_dict(uid)
    SELECT uid
    FROM dws_userbase ON conflict DO NOTHING;

    對(duì)用戶標(biāo)識(shí)進(jìn)行編碼不僅可以方便存儲(chǔ)進(jìn)Bitmap，還可以使ID信息保持連續(xù)性。如下圖所示bitmap2由于存儲(chǔ)的ID數(shù)據(jù)稀疏，存儲(chǔ)效率相比bitmap1低很多，因此對(duì)ID編碼處理，也會(huì)降低存儲(chǔ)成本，提升運(yùn)算效率。

    對(duì)于數(shù)值類型，如果較為稀疏也可以考慮編碼，但是進(jìn)行編碼有利有弊，例如在廣告DMP系統(tǒng)中除了需要高性能的畫像能力，也需要實(shí)時(shí)輸出人群明細(xì)的能力；而一旦需要輸出人群明細(xì)，就需要Join用戶ID表進(jìn)行還原，這一部分的性能開銷，也應(yīng)當(dāng)納入技術(shù)選型的考慮因素中。因此您可以依據(jù)使用場(chǎng)景權(quán)衡選擇，是否進(jìn)行編碼建議如下。

    • 字符ID：建議編碼。

    • 整數(shù)ID且需要頻繁還原原始值：建議不編碼。

    • 整數(shù)ID且不需要還原原始值：建議編碼。

  • Bitmap 加工和查詢

    依據(jù)上述方案按列拆分的思路，將dws_userbase表與dws_shop_cust表進(jìn)行拆分，按照分別為省份、性別的列Bitmap拆分為一個(gè)表，但是性別只有男、女兩個(gè)選項(xiàng)，壓縮出來的Bitmap只能分布于集群中的兩個(gè)節(jié)點(diǎn)，計(jì)算存儲(chǔ)都很不平均，集群的資源并不能充分利用。因此有必要將Bitmap拆分成多段，并將它們打散到集群中來提升并發(fā)執(zhí)行的能力，假設(shè)將Bitmap打散成65536段，SQL命令如下。

    -- dws_userbase 結(jié)構(gòu)見寬表方案
    BEGIN;
    CREATE TABLE dws_shop_cust
    (
      uid text not null primary key,
      shop_id text,
        cust_type text
    );
    call set_table_property('dws_shop_cust', 'distribution_key', 'uid');
    END;
    
    -- 創(chuàng)建bitmap插件
    CREATE EXTENSION roaringbitmap;
    
    BEGIN;
    CREATE TABLE rb_dws_userbase_province (
        province text,
      bucket int,
        bitmap roaringbitmap
    );
    call set_table_property('rb_dws_userbase_province', 'distribution_key', 'bucket');
    END;
    
    BEGIN;
    CREATE TABLE rb_dws_shop_cust_sid_ctype (
        shop_id text,
      cust_type text,
      bucket int,
        bitmap roaringbitmap
    );
    call set_table_property('rb_dws_shop_cust_sid_ctype', 'distribution_key', 'bucket');
    END;
    
    -- 寫入bitmap表
    INSERT INTO rb_dws_userbase_province
    SELECT province,
           encode_uid / 65536 as "bucket",
           rb_build_agg(b.encode_uid) AS bitmap
    FROM dws_userbase a join dws_uid_dict b on a.uid = b.uid
    GROUP BY province, "bucket";
    
    INSERT INTO rb_dws_shop_cust_sid_ctype
    SELECT shop_id,
           cust_type,
           encode_uid / 65536 AS "bucket",
           rb_build_agg(b.encode_uid) AS bitmap
    FROM dws_shop_cust a
    JOIN dws_uid_dict b ON a.uid = b.uid
    GROUP BY shop_id, cust_type, "bucket";

    當(dāng)進(jìn)行[shop_id = A] & [cust_type = 新客] & [province = 北京]的客群人數(shù)預(yù)估時(shí)，按照標(biāo)簽的與或非邏輯組織對(duì)應(yīng)的Bitmap關(guān)系運(yùn)算，即可完成對(duì)應(yīng)的查詢，SQL命令如下。

    SELECT SUM(RB_CARDINALITY(rb_and(ub.bitmap, uc.bitmap)))
    FROM
      (SELECT rb_or_agg(bitmap) AS bitmap,
              bucket
       FROM rb_dws_userbase_province
       WHERE province = '北京'
       GROUP BY bucket) ub
    JOIN
      (SELECT rb_or_agg(bitmap) AS bitmap,
              bucket
       FROM rb_dws_shop_cust_sid_ctype
       WHERE shop_id = 'A'
         AND cust_type = '新客'
       GROUP BY bucket) uc ON ub.bucket = uc.bucket;

當(dāng)我們計(jì)算[province=北京] & [shop_id=A且7天未購(gòu)買]的用戶時(shí)，SQL命令如下所示。

-- 原始行為表
BEGIN;
CREATE TABLE dws_usershop_behavior
(
  uid int not null,
  shop_id text not null,
  pv_cnt int,
  trd_cnt int,
  ds integer not null
);
call set_table_property('dws_usershop_behavior', 'distribution_key', 'uid');
COMMIT;

-- 編碼行為表
BEGIN;
CREATE TABLE dws_usershop_behavior_bucket
(
  encode_uid int not null,
  shop_id text not null,
  pv_cnt int,
  trd_cnt int,
  ds int not null,
  bucket int
);
CALL set_table_property('dws_usershop_behavior_bucket', 'orientation', 'column');
call set_table_property('dws_usershop_behavior_bucket', 'distribution_key', 'bucket');
CALL set_table_property('dws_usershop_behavior_bucket', 'clustering_key', 'shop_id,encode_uid');
COMMIT;

-- 寫入分桶的事實(shí)數(shù)據(jù)
INSERT INTO dws_usershop_behavior_bucket
SELECT *,
             encode_uid,
       shop_id,
       pv_cnt,
       trd_cnt,
       encode_uid / 65536
FROM dws_usershop_behavior a JOIN dws_uid_dict b
on a.uid = b.uid;

-- 事實(shí)數(shù)據(jù)和屬性數(shù)據(jù)聯(lián)合運(yùn)算
SELECT sum(rb_cardinality(bitmap)) AS cnt
FROM
  (SELECT rb_and(ub.bitmap, us.bitmap) AS bitmap,
          ub.bucket
   FROM
     (SELECT rb_or_agg(bitmap) AS bitmap,
             bucket
      FROM rb_dws_userbase_province
      WHERE province = '北京'
      GROUP BY bucket) AS ub
   JOIN
     (SELECT rb_build_agg(uid) AS bitmap,
             bucket
      FROM
        (SELECT uid,
                bucket
         FROM dws_usershop_behavior_bucket
         WHERE shop_id = 'A' AND ds > to_char(current_date-7, 'YYYYMMdd')::int
         GROUP BY uid,
                  bucket HAVING sum(trd_cnt) = 0) tmp
      GROUP BY bucket) us ON ub.bucket = us.bucket) r

為了避免Bitmap數(shù)據(jù)計(jì)算對(duì)生產(chǎn)業(yè)務(wù)的影響，可以選擇在離線完成Bitmap數(shù)據(jù)的加工，通過Hologres外部表能力從MaxCompute或者Hive中直接加載數(shù)據(jù)。離線處理Bitmap的過程與在線流程思路類似，也可以通過編碼、聚合方式產(chǎn)生數(shù)據(jù)，在MaxCompute中離線構(gòu)建Bitmap數(shù)據(jù)示例如下。

-- 選擇project
USE bitmap_demo; 

-- 創(chuàng)建原始表
CREATE TABLE mc_dws_uid_dict (
encode_uid bigint,
bucket bigint,
uid string
);

CREATE TABLE mc_dws_userbase
(
  uid string,
  province string,
  gender string,
  marriaged string
);

-- 對(duì)新增的UID進(jìn)行編碼
-- 計(jì)算新增編碼uid
WITH uids_to_encode AS
  (SELECT DISTINCT(ub.uid),
          CAST(ub.uid / 65336 AS BIGINT) AS bucket
   FROM mc_dws_userbase ub
   LEFT JOIN mc_dws_uid_dict d ON ub.uid = d.uid
   WHERE d.uid IS NULL),
-- 計(jì)算每個(gè)分桶中待編碼的uid數(shù)量，通過sum窗口累加出bucket編碼的起始值
uids_bucket_encode_offset AS
  (SELECT bucket,
          sum(cnt) over (ORDER BY bucket ASC) - cnt AS bucket_offset
   FROM
     (SELECT count(1) AS cnt,
             bucket
      FROM uids_to_encode
      GROUP BY bucket) x),
-- 計(jì)算已使用編碼值最大值
dict_used_id_offset AS
  (SELECT max(encode_uid) AS used_id_offset FROM mc_dws_uid_dict)
-- 新增用戶的編碼 = 已使用編碼值最大值 + Bucket編碼起始值 + RowNumber序號(hào)
INSERT INTO mc_dws_uid_dict
SELECT
       COALESCE((SELECT used_id_offset FROM dict_used_id_offset),0) + bucket_offset + rn,
       bucket,
       uid
FROM
  (SELECT row_number() OVER (partition BY ub.bucket ORDER BY ub.uid) AS rn,
          ub.bucket,
          bo.bucket_offset,
          uid
   FROM uids_to_encode ub
   JOIN uids_bucket_encode_offset bo ON ub.bucket = bo.bucket) j


-- 創(chuàng)建bitmap相關(guān)函數(shù)
add jar function_jar_dir/mc-bitmap-functions.jar as mc_bitmap_func.jar -f;
create function mc_rb_cardinality as com.alibaba.hologres.RbCardinalityUDF using mc_bitmap_func.jar;
create function mc_rb_build_agg as com.alibaba.hologres.RbBuildAggUDAF using mc_bitmap_func.jar;

-- 創(chuàng)建bitmap表并寫入
CREATE TABLE mc_rb_dws_userbase_province
(
  province string,
  bucket int,
  bitmap string
);
INSERT INTO mc_rb_dws_userbase_province
SELECT province,
       b.bucket_num,
       mc_rb_build_agg(b.encode_uid) AS bitmap
FROM mc_dws_userbase a join mc_dws_uid_dict b on a.uid = b.uid
GROUP BY province, b.bucket_num;

在Hologres中執(zhí)行以下命令。

-- 創(chuàng)建MaxCompute外部表
CREATE TABLE mc_rb_dws_userbase_province (
    province text,
  bucket int,
    bitmap text
) server odps_server options(project_name 'bitmap_demo', table_name 'mc_rb_dws_userbase_province');
-- 將外表中bitmap數(shù)據(jù)寫到Hologres中
INSERT INTO rb_dws_userbase_province
SELECT province,
       bucket::INT,
       roaringbitmap_text(bitmap, FALSE)
FROM mc_rb_dws_userbase_province;

通過上述步驟，可以將數(shù)據(jù)加載至Hologres，然后按照標(biāo)簽圈選條件，組合Bitmap運(yùn)算加速查詢。

• MaxCompute中計(jì)算Bitmap數(shù)據(jù)可使用mc-bitmap。

• 離線加工使用Bitmap方案更多信息請(qǐng)參見離線UV計(jì)算

在實(shí)時(shí)計(jì)算場(chǎng)景中，可以使用Flink和Hologres組合的方式，基于RoaringBitmap實(shí)時(shí)對(duì)用戶標(biāo)簽去重，主要思路如下。

1. 將用戶ID字典表作為維表，利用Hologres的Insert on Conflict機(jī)制處理新增編碼，在Flink中進(jìn)行維表Join。

2. 將Join結(jié)果流按照標(biāo)簽維度進(jìn)行RoaringBitmap聚合。

3. 輸出的Bitmap結(jié)果寫入Hologres對(duì)應(yīng)的Bitmap表中。