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 运算性能的几个关键点：
数据倾斜场景无法充分利用CPU资源：ClickHouse 的并发执行模型在大多数场景中都有非常好的性能表现，但是对于 Bitmap 相关查询，许多生产环境中的查询都可能出现由于部分 Bitmap 过大而引发的数据倾斜问题。
读取并行度不够：ClickHouse 由于内在读取机制的限制，对 Bitmap 的读取尚有许多可优化的空间，比如对大 Bitmap 提高读取并行度，优化内存拷贝等。
存储布局过于稀疏：对于 Bitmap64，由于存在两层索引结构，实际上是以高 48（32+16）bits 作为索引 key。对线上数据来说，通常都会导致数据离散程度非常高，Container 个数极多，而 Container 内部存储的元素又非常少。这种布局上的稀疏性，严重拖累了各类运算的性能。在千万元素这个量级上，如果说 Bitmap32 尚处于「可用」状态，那么 Bitmap64 则是几乎无法使用。
未开启指令优化，Bitmap 运算没有向量化执行。ClickHouse 能在 OLAP 领域异军突起的一大原因对向量化执行引擎进行了优秀的工程实现。RoaringBitmap 大量用到一些 bitset 运算操作，非常有利于进行向量化执行。RoaringBitmap 库本身也支持一些指令优化选项，需要在 ClickHouse 编译过程中进行指定才能发掘 RoaringBitmap 相关运算的性能潜力。
集群资源未充分利用：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 = MergeTreePARTITION BY dsORDER BY id;insert into test.bm_64 select '2022-06-10', groupBitmapState(rand64()), 'rand' from numbers(10000000); X 1insert into test.bm_64 select '2022-06-11', groupBitmapState(rand64()), 'rand' from numbers(10000000); X 1insert into test.bm_64 select '2022-06-12', groupBitmapState(rand64()), 'rand' from numbers(10000000); X 7optimize table test.bm_64;-----------------------------SELECT ds, bitmapCardinality(bm) FROM test.bm_64 WHERE id = 'rand' ORDER BY ds ASCSETTINGS 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+，推动腾讯成为国内社区贡献第一梯队厂商。
引用：
Roaring Bitmaps: Implementation of an Optimized Software Library Roaring Bitmaps: Implementation of an Optimized Software Library Roaring Bitmaps publications http://roaringbitmap.org/publications/ ClickHouse 在字节广告 DMP&CDP 的应用 https://cloud.tencent.com/developer/news/680214 GitHub - Slach/clickhouse-flamegraph https://github.com/Slach/clickhouse-flamegraph