WeOLAP 亞秒級實時數倉 —— BitBooster 10倍查詢優化實踐

推薦系統對“個性化體驗”的強烈訴求，推動了“亞秒級”分析系統的誕生。

微信大資料平台基于ClickHouse核心打造了WeOLAP亞秒級查詢引擎，支援互動分析，實時計算、推薦效果分析等業務場景，本文介紹系列性能優化之Bitbooster

一、背景

為實作秒級互動分析響應訴求，在人群預估(廣告)、 留存分析中 Join 常會被 Bitmap 運算替代，可取得數倍性能提升的效果；但在實踐過程中，我們發現 ClickHouse 的 Bitmap 運算在諸多情況下有性能退化，長尾效應嚴重。

BitBooster 是我們為 Bitmap 查詢所新增的一系列優化機制的統稱，且在持續疊代中。本文将介紹如何通過 BitBooster加速 Bitmap 查詢，讓相關分析提速10X！

1.1 效果先行：

上線前：單分組 Bitmap64 合并，耗時超過100s

上線後：擁有實時接入性能，單分組 Bitmap64 合并耗時僅 0.3s，性能提升 300X+

注：上述 Case 為 Bitmap uint64 場景，效果特别突出

1.2 業務場景

• 人群預估：廣告投放篩選，确認命中的使用者數目，用于輔助判斷投放情況，預估預算
• 行為分析：諸如留存分析，差異分析等
• 實驗分析：推薦系統模型上線前需要做A/B實驗做假設檢驗，驗證模型效果
• 紅點投放：營運活動，評估影響面

上述場景通常是線上業務，強互動式分析，一般要求計算的時間不能超過秒級。以人群預估場景為例，可以根據使用者各類屬性等條件進行圈選，其本質就是集合的快速交并補計算；

曆史演進：

主要經曆 Hadoop/ClickHouse 明細分析 -> ClickHouse Roaringbitmap (10X提速) -> BitBooster (10X+提速，自研核心特性)

1.3 原生 Bitmap 慢在哪？

“RoaringBitmap 從性能，空間使用率各個方面非常優秀，以及在諸多成熟開源軟體(spark,druid,kylin) 中廣泛使用”

ClickHouse 源碼核心中的Bitmap 底層使用的是 RoaringBitmap ，這是一種為存儲優化，高度壓縮的 Bitmap 資料結構。實際上，ClickHouse 使用的 Roaring Bitmap 一點也不算慢；發表在 SIGMOD ‘17 上的論文 《An Experimental Study of Bitmap Compression vs. Inverted List Compression》曾對諸多 Bitmap 壓縮算法進行過比較，RoaringBitmap 幾乎是一騎絕塵：

以至于作者總結說：

“Use Roaring for bitmap compression whenever possible. Do not use other bitmap compression methods”

我們要說明的是，慢和快是相對的，一次 20s+ 的查詢對于使用 Spark/Hadoop 作為 OLAP 引擎進行資料分析的時代或許是快的，但是當我們以 ClickHouse 為底座實作了 TP90 查詢<3s 時，這樣長的耗時就慢得可惡了。

為了優化 ClickHouse 的 Bitmap 運算，我們分析了 ClickHouse Bitmap 的實作細節以及一些 ClickHouse 計算引擎的執行過程，總結了影響 ClickHouse Bitmap 運算性能的幾個關鍵點：

1. 資料傾斜場景無法充分利用CPU資源：ClickHouse 的并發執行模型在大多數場景中都有非常好的性能表現，但是對于 Bitmap 相關查詢，許多生産環境中的查詢都可能出現由于部分 Bitmap 過大而引發的資料傾斜問題。
2. 讀取并行度不夠：ClickHouse 由于内在讀取機制的限制，對 Bitmap 的讀取尚有許多可優化的空間，比如對大 Bitmap 提高讀取并行度，優化記憶體拷貝等。
3. 存儲布局過于稀疏：對于 Bitmap64，由于存在兩層索引結構，實際上是以高 48（32+16）bits 作為索引 key。對線上資料來說，通常都會導緻資料離散程度非常高，Container 個數極多，而 Container 内部存儲的元素又非常少。這種布局上的稀疏性，嚴重拖累了各類運算的性能。在千萬元素這個量級上，如果說 Bitmap32 尚處于「可用」狀态，那麼 Bitmap64 則是幾乎無法使用。
4. 未開啟指令優化，Bitmap 運算沒有向量化執行。ClickHouse 能在 OLAP 領域異軍突起的一大原因對向量化執行引擎進行了優秀的工程實作。RoaringBitmap 大量用到一些 bitset 運算操作，非常有利于進行向量化執行。RoaringBitmap 庫本身也支援一些指令優化選項，需要在 ClickHouse 編譯過程中進行指定才能發掘 RoaringBitmap 相關運算的性能潛力。
5. 叢集資源未充分利用：ClickHouse 在單機性能上極為強悍，但是以叢集模式提供服務時，如果不在資料分布上進行優化，就無法充分利用叢集各個節點的計算性能。

二、關鍵技術

2.1 單機計算優化

ClickHouse 通過 DAG計算圖 + 線程池 來并行化SQL執行，線程池中的線程通過遊曆 DAG 計算圖，執行任何處于可執行狀态的節點。通過按批處理的方式，周遊計算圖帶來的開銷可以被有效降低。同時，由于算子均為線程安全，DAG圖上各個可執行節點均可被并行處理。

這一并發執行模型在大多數場景中都能工作得非常好，但亦并非完美，在查詢 Bitmap 的場景中還有不少優化改進的地方。ClickHouse 的 DAG計算圖本身其實蘊含了一系列的執行流水（ClickHouse 中也确實是通過組合連接配接多個 Pipe 來建構計算圖的），而計算圖中的單個節點同一時刻隻能被一個線程所執行，也就是說 ClickHouse 可以有DAG計算圖節點間的并行，但沒有DAG計算圖節點内的并行。這意味着如果某個 Pipe 比較「慢」的話，整個SQL的執行時間都會被這些 Straggler 所拖累。

然而，在大多數查詢場景中并不會遇到這一問題，因為 ClickHouse 預設在資料讀取時通過按行數劃分的方式，将資料切割為了行數接近的 Block，并以這些 Block 為單元進行處理——這意味着每個 Pipe 上的資料行數是較為接近的，是以不會出現因為資料傾斜而出現Straggler 的情形。但是 Bitmap 是 ClickHouse 資料結構中的另類，兩個 Bitmap 可能因為存儲的元素個數不同而有着相當明顯的計算量差異，是以對于Bitmap類型來說，即使兩批資料的行數相同，其代表的計算工作量也完全不同。在這種情況下，就會出現資料傾斜現象——某個 Pipe 的工作量顯著高于别的 Pipe 進而拖慢了整個查詢。

為了解決這一問題，我們在核心中增加了一個優化機制，針對 Bitmap 相關 SQL 的DAG計算圖，允許在滿足一定條件的情況下，額外添加一個 Repartition 階段，來重新平衡各個 Pipe 之間的工作量：

通過這樣的優化，在 Repartition 前後，各個 Pipe 保持獨立，但是在 Repartition 階段則變為多對多的關系。使得讀取階段的單個 Pipe 中的資料，可以根據資料量重新劃分後，分發到其他所有空閑的 Pipe 中。

我們在中測試發現，這一優化對于存在資料傾斜的場景，能帶來 10%- 20% 左右的性能提升：

--查詢 S1：
CREATE TABLE test.bm_64
(
`ds` Date,
`bm` AggregateFunction(groupBitmap, UInt64),
`id` String
)
ENGINE = MergeTree
PARTITION BY ds
ORDER BY id;


insert into test.bm_64 select '2022-06-10', groupBitmapState(rand64()), 'rand' from numbers(10000000); X 1
insert into test.bm_64 select '2022-06-11', groupBitmapState(rand64()), 'rand' from numbers(10000000); X 1
insert into test.bm_64 select '2022-06-12', groupBitmapState(rand64()), 'rand' from numbers(10000000); X 7


optimize table test.bm_64;
-----------------------------
SELECT ds, bitmapCardinality(bm) FROM test.bm_64 WHERE id = 'rand' ORDER BY ds ASC
SETTINGS force_repartition_after_reading_from_merge_tree = 1;


┌─────────ds─┬─bitmapCardinality(bm)─┐
│ 2022-06-10 │              10000000 │
│ 2022-06-11 │              10000000 │
│ 2022-06-12 │              10000000 │
│ 2022-06-12 │              10000000 │
│ 2022-06-12 │              10000000 │
│ 2022-06-12 │              10000000 │
│ 2022-06-12 │              10000000 │
│ 2022-06-12 │              10000000 │
│ 2022-06-12 │              10000000 │
└────────────┴───────────────────────┘
9 rows in set. Elapsed: 83.593 sec.
-----------------------------
SELECT ds, bitmapCardinality(bm) FROM test.bm_64 WHERE id = 'rand' ORDER BY ds ASC


┌─────────ds─┬─bitmapCardinality(bm)─┐
│ 2022-06-10 │              10000000 │
│ 2022-06-11 │              10000000 │
│ 2022-06-12 │              10000000 │
│ 2022-06-12 │              10000000 │
│ 2022-06-12 │              10000000 │
│ 2022-06-12 │              10000000 │
│ 2022-06-12 │              10000000 │
│ 2022-06-12 │              10000000 │
│ 2022-06-12 │              10000000 │
└────────────┴───────────────────────┘
9 rows in set. Elapsed: 108.241 sec.           

2.2 讀取優化

從我們最終的測試效果結果來看，單機計算優化的效果是比較有限的，僅在部分嚴重資料傾斜的場景中有比較大的提升，大部分場景沒有實作比較大的性能提升（比如對查詢 S1 大約僅10%～20%）。這反過來促使我們思考，是否主要的瓶頸并不在 Bitmap 函數的計算上。

我們使用社群的 ClickHouse SQL Profile 工具 ClickHouse-FlameGraph 對查詢 S1 進行了 Profile。為了更清晰地弄清楚瓶頸所在，我們對 ClickHouse-FlameGraph 進行了一些改進優化，使得最後的 Profile 結果可以具體到單個線程：

查詢 S1 線程粒度 Profile 結果

從上圖中可以看到，在三個執行線程中，有兩個線程大部分時間都處于等待狀态，另外一個線程大部分耗時都用在讀取 Bitmap 上。

這一現象與 ClickHouse 核心的讀取機制有關，ClickHouse 采用的是 Mark （稀疏索引中的一個條目） 級的讀取負載均衡政策，在生成具體的計算圖時，先計算總的需要讀取的Mark數，然後将所有 Mark 均衡配置設定給讀取線程池中的每個線程。

通常每個 Mark 對應的讀取行數都是固定的，它實際上是由 index_granularity 确定，預設值為 8192。ClickHouse 的讀取線程池也實作了 「工作竊取(Work-Stealing)算法」，空閑的讀取線程會通過工作竊取的方式幫助其他線程讀取。這裡的限制在于，最小的工作任務單元為一個 Mark，是以預設情況下單個線程需要負擔至少 8192 行的讀取，在這一範圍内沒有任何讀取的并行化機制。對于那些存儲的 Bitmap 基數動辄百萬/千萬的表來說，如果一個線程每次都要負責讀取 8192 個Bitmap，這個限制就成了一個比較大的問題。

一種解決辦法是把 index_granularity 設定的低一點，但是這樣會導緻索引密度變高；我們發現如果主鍵列較多，或者表本身比較大的情況下去調整 index_granularity 會顯著增加 ClickHouse 的記憶體負擔。

我們的解決方案是對反序列過程進行優化，為 Bitmap 類型的反序列化增加異步接口，使得對元素個數較多的 Bitmap，可以委托給其他線程執行，達到并行反序列化的效果。從下圖可以看出，優化後各個線程的等待時間占比明顯減少:

查詢 S1 讀取優化後，線程粒度 Profile 結果

此外，我們還對 RoaringBitmap 以及 ClickHouse Bitmap 相關的代碼進行了一些優化，修改了代碼中一些不合理的地方，盡可能地減少了記憶體拷貝，這部分改動帶來的提升也比較明顯。

将以上這些優化效果結合起來，最終我們可以在 S1 這樣的查詢上實作 4X 的性能提升：

2.3 布局優化

盡管通過前文的計算和讀取優化，我們将查詢 S1 的單機耗時從 108s 降低到了 26s，達到了4倍的性能提升，但是對比 Bitmap32，這樣的表現仍舊差強人意。對于約 1000w 元素的 Bitmap32，同樣執行 S1 中的查詢，在無任何優化情況下，查詢耗時不到 0.4s（圖中的Bitmap 通過 rand32() 函數生成，存在的碰撞，因而資料量略少于1000w）:

如果啟用前文的優化，則僅需 0.18s:

要了解這種巨大的性能落差從何而來，需要深入了解 RoaringBitmap 的存儲結構：

RoaringBitmap 32

對于 32 位類型的元素存儲，RoaringBitmap 在存儲時使用一個數組作為索引結構，以元素的高 16 bits 作為 key，低16 bits 作為 Value 存入 Container 中。根據 Container 中資料的規模和連續性，在Container 内部會選擇 Range（Run Container）、Bitset、Array 中最合适的類型作為實際的底層容器。如果需要存儲的元素在高 16 位的分布較為離散，那麼單個 Container 中的元素個數就會比較稀少，Container 會選擇 Array 而非 Bitset/Range 作為存儲容器，引起 Bitmap 各類運算速率的降低。

對于 64 位類型的元素，RoaringBitmap 選擇在 Bitmap32 的基礎上建構 Bitmap64。具體來說，Bitmap64 使用了 TreeMap 作為索引結構，索引的 key 是元素的高 32 bits，value 則是 RoaringBitmap32，元素的低 32 bits 會直接存放到這個 RoaringBitmap32 中。

RoaringBitmap64 結構

對于 RoaringBitmap64，由于存在兩層索引結構，實際上是以高 48（32+16）bits 作為索引 key。這對線上資料來說，通常都會導緻資料離散程度非常高，Container 個數極多，而 container 内部存儲的元素個數非常稀少。

這種稀疏布局帶來的一個顯著影響就是 RoaringBitmap 不僅不能有效壓縮資料，反而在存儲上的開銷大幅增長：

1000w 随機元素 Bitmap32 vs Bitmap64 存儲對比

由于 RoaringBitmap 的大多數運算操作都需要周遊内部的 Container，緊湊布局可以提高周遊操作的效率。而如果内部布局稀疏，就有可能嚴重拖累了各類 Bitmap 運算的性能。内部布局是否緊湊，在 Bitmap32 上會引起數倍的性能差别，而在 Bitmap64 上則可能有兩個數量級的差異。

在生産環境中，業務資料生成的 Bitmap 很難天然形成緊湊的布局。這就導緻在千萬元素這個量級上，Bitmap32 尚處于「可用」狀态，而 Bitmap64 則是幾乎無法使用。實際上，我們通過測試發現，1000w個随機元素構成的 Bitmap64（稀疏布局），與1000w個連續元素構成的 Bitmap64（緊密布局），即使在最簡單的 bitmapCardinality 計算上，兩者也存在明顯的性能差别：

CREATE TABLE test.bm_64
(
`ds` Date,
`bm` AggregateFunction(groupBitmap, UInt64),
`id` String
)
ENGINE = Memory;


insert into test.bm_64 select '2022-06-10', groupBitmapState(toUInt64(number)), 'seq' from numbers(10000000);
insert into test.bm_64 select '2022-06-10', groupBitmapState(rand64()), 'rand' from numbers(10000000);
-------------------------------------
:) select bitmapCardinality(bm) from test.bm_64 where id = 'seq';


Query id: e155afae-59e4-4cac-91be-bff3bd06afe1


┌─bitmapCardinality(bm)─┐
│              10000000 │
└───────────────────────┘


1 rows in set. Elapsed: 0.055 sec.
-------------------------------------
:) select bitmapCardinality(bm) from test.bm_64 where id = 'rand';


Query id: 511c2e67-f562-417d-875f-d9b15ad72f3f


┌─bitmapCardinality(bm)─┐
│              10000000 │
└───────────────────────┘


1 rows in set. Elapsed: 8.361 sec.           

在此處給出的測試 SQL 中，使用了 Memory 表引擎，以避免 Bitmap64 的讀取影響最終的耗時結果。我們在讀取優化中已經看到，對于内部稀疏的 Bitmap64 對象，讀取過程中的序列化、反序列化開銷大得驚人，可能比計算本身還要耗時。

為了解決 Bitmap 存儲布局稀疏的問題。我們首先想到的是編碼，通過将存儲的元素連續編碼為順序序列，我們可以得到一個内部布局非常緊密的 Bitmap：

編碼映射

編碼映射方案本身并不新奇，比如 Kylin 使用全局字典編碼來實作精确去重；ClickHouse 的低基數類型使用 Part 級别字典來壓縮字元串資料存儲，同時加速 Compare 操作；還有一些外部編碼/全局順序ID生成服務都是編碼映射的案例。

不過，在為 ClickHouse 設計一個生産環境可用的編碼映射方案時，必須要考慮解決以下問題：

• ClickHouse 的寫入是并發執行的，如何保證并發場景下不同批次寫入資料的編碼一緻性？
• 對于線上場景需要支援實時編碼，整體耗時必須可控，避免造成寫入反壓。
• 能否支援shard級/全局字典？字典資訊在不同副本間如何同步？
• 對于已有的曆史 Bitmap，在缺乏明細表的情況下如何進行編碼？
• 編碼後的 Bitmap 包含的元素内容和編碼前不同，使用者如何在 ClickHouse 查詢和使用已有的編碼映射關系，如何滿足使用者點查 、提包的需求？
• 編碼映射關系如何持久化，存儲在哪？

從這些問題出發，我們認為這種編碼最合适的實作方式，是與 ClickHouse 的現有字典功能結合，一方面可以友善已經熟悉 ClickHouse 字典功能的同學上手，另一方面也盡可能地将複雜性限制在 ClickHouse 内部。基于此，我們在 ClickHouse 核心中新增一種可編碼字典,命名它為 EncodedDictionary：

EncodedDictionary 支援所有 ClickHouse 内置的字典函數，其使用上和通常的字典别無二緻。同時我們還增加了一個轉碼函數 bitmapDictEncode，借助它可以很友善的把一個未編碼的 Bitmap 轉換為一個編碼過的緊湊的 Bitmap:

select bitmapDictEncode(bm, 'default.dict_test', 0) from ( select groupBitmapState(rand64())as bm from numbers(10000000))           

編碼後的 Bitmap64，在查詢和讀取性能上都有很大的提升：

值得一提的是，編碼在 Bitmap 的存儲開銷上也帶來了顯著的收益，Bitmap64 在編碼後存儲占用與同規模的 Bitmap32 一緻。同時我們也發現對于 Bitmap32，在使用字典編碼後能節約 30%+ 的存儲空間。

2.4 指令集優化

為何需要指令集優化？我們看以下程式如何通過指令集加速：

[程式] bitmapAndCardinality：兩個 Bitmap 求交集後的基數大小

int c= 0;




for (int k = 0; k<1024;++k){

  // count：計算 64-bit word 中有多少個1位，循環周遊多次

  c+= count(A[k] & B[k])

}
           

count 函數的一個常見實作如下圖左，疊代式計算效率很低；

開啟指令集優化後，可以通過一條指令 popcnt (下圖右) 替代原來的疊代式計算，加速執行:

此外RBM 中大量用到BitSet 操作，它對向量化執行非常親和,諸如邏輯ORs,ANDs,ANDNOT,XORs 都能被 SIMD 指令集加速

RBM官方公布的資料集測試中，AVX2的向量化相對于标量執行模式會有3.5X倍提升；AVX-512理論有5X提升。

AVX2的硬體支援已經很成熟普遍，程式中修改特定調用指令集，編譯期間指定指令集，這種基礎和通用性能優化方法，對多數查詢都有效。ClickHouse 中可以在編譯時加上選項開啟指令集優化：

-DENABLE_AVX2=1
-DENABLE_AVX2_FOR_SPEC_OP=1           

2.5 多機并行&彈性伸縮

借鑒傳統資料庫存儲的分片思想，我們可以先将資料根據特定分組規則進行sharding，然後再對 Bitmap 編碼，并設定 Group；計算分布在不同節點上，一方面提升多機并行度，減小中間結果傳輸；另一方面，分組相同的(Group) Bitmap 可直接本地做 colocation Join，不涉及跨節點的 Bitmap 運算。

借助 WeOLAP 團隊和騰訊雲聯合研發的“存算分離”架構，可以實作在計算成為瓶頸時，查詢高峰期叢集将 Bitmap 彈性分布在更多的計算節點上，低峰期降低計算節點數目，以達到成本和性能的最優解。

三、效果展示

3.1 編碼速率

實時寫入編碼：線上叢集的實時寫入一般以一百萬為一批進行，我們測試了百萬行寫入編碼的耗時。由于 EncodedDictionary 的内置緩存可以對于已編碼的資料進行加速，是以我們會分别測試空字典冷啟動和字典預熱後兩種情況的耗時。從測試結果看，在冷啟動的場景下約有額外 1.8s 不到的開銷，在字典預熱後，額外耗時不到 20ms:

100萬行資料實時編碼寫入性能，基本持平（機關秒）

Bitmap to Bitmap 編碼：

對于我們在核心中新增的 Bitmap to Bitmap 的編碼函數 bitmapDictEncode，我們分别在字典冷啟動/預熱、是否啟用單機計算和讀取優化等條件下測試了其性能。

測試資料集：

• 30 Bitmap64:基數分布: 1000w * 5 + 100w * 7 + 10w * 9 + 1w * 9
• 30 Bitmap32:基數分布: 1000w * 5 + 100w * 7 + 10w * 9 + 1w * 9

Bitmap to Bitmap 編碼性能（機關秒）

3.2 計算性能

測試資料集（同上），以下均為單機計算性能：

測試資料集上 Bitmap64 運算性能（機關秒）

測試資料集上 Bitmap32 運算性能（機關秒）

3.3 線上資料效果

某業務場景--文章分析

均為 Bitmap64，單 Group 約 2千個Bitmap，單機計算加速效果如下:

某實驗平台場景-留存分析

均為 Bitmap32，7 天資料約 4 百萬個 Bitmap，14 天資料約 9 百萬個Bitmap，單機計算加速效果如下：

單節點計算優化效果

四、總結

資料庫的計算優化很多時候是一個精細活，對 ClickHouse 這種單機性能出類拔萃的工程傑作則更是如此，需要不斷的 Profile、 Code Review 和 Demo 驗證，在 N 次無效甚至退化的改動後，才終于榨取到幾個百分點的提升，然而帶給資料庫工作者最多快樂的并不是最終提升了多少性能，而是在終于弄清問題後的「Eureka 時刻」。

微信早期使用Bitmap 32 在大多數分析場景中的運算性能瓶頸并不明顯。随着業務的發展，開始需要在 FeedId，DocId 等 UInt64 類型資料上使用 Bitmap 的需求，Bitmap64 嚴重的性能退化和 ClickHouse快如閃電的處理速度反差巨大，這促使我們開始探索如何對 Bitmap 查詢進行優化提速。

在初期優化工作中，受到了社群同行們技術文章的諸多啟發，不過由于業務場景和瓶頸點的差異，在技術選型和落地方案上還是有比較大的不同；我們正着手把這項功能合并到 Clickhouse 社群中，回饋社群；目前WeOLAP團隊累計為ClickHouse社群貢獻PR 100+，推動騰訊成為國内社群貢獻第一梯隊廠商。

引用：

1. Roaring Bitmaps: Implementation of an Optimized Software Library
2. Roaring Bitmaps: Implementation of an Optimized Software Library
3. Roaring Bitmaps publications
4. http://roaringbitmap.org/publications/
5. ClickHouse 在位元組廣告 DMP&CDP 的應用
6. https://cloud.tencent.com/developer/news/680214
7. GitHub - Slach/clickhouse-flamegraph
8. https://github.com/Slach/clickhouse-flamegraph

作者:微信大資料團隊

來源:微信公衆号:微信背景團隊

出處:https://mp.weixin.qq.com/s/tJQoNRZ5UDJ_IASZLlhB4Q