业务背景

众所周知，广告是很多互联网公司的主要收入，对于字节跳动来说也是如此。那么，在字节跳动广告的 DMP&CDP 业务，乃至所有广告业务中，有哪些场景在使用 ClickHouse 呢？是在线服务还是离线统计的呢？应该说都有。

可以从三个场景来讲：人群预估、人群画像和统计分析。

人群预估 主要是根据一定的圈选条件，确认命中的用户数目。在广告精准投放过程中，广告主需要知道当前选定的人群组合中大概会有多少人，用于辅助判断投放情况进而确定投放预算。因为是在线业务，一般要求计算的时间不能超过 5 秒。

人群画像 主要是对广告投放的用户群进行画像分析，也是在线的，同样对时间有一定的要求，因为是偏分析的场景，一般不能超过 20 秒，否则用户的体验就非常差了。

统计分析 的使用场景比较多，在线、离线都有，包括一些搜索词统计分析，广告、投放收入数据的分析等等，应用的方面很多。

我今天主要分享的是人群预估，因为这是一个比较大的难点。而对于统计分析来说本身就是 ClickHouse 的强项。

就如我之前说的，人群预估就是根据一定的圈选条件，确认命中的用户数目。比如下图中我们可以看到，在投放广告的时候，可以根据地域、性别、年龄、兴趣、首次激活时间等条件进行圈选。其本质就是集合的快速交并补计算。

举一个简单的例子，假设一个望远镜厂商想通过投放广告吸引用户购买。那么假设他想投给在北京的喜欢户外或者爬山的人。本质上来说，我们就是通过集合运算，把喜欢户外和喜欢爬山的人群求并集，然后与北京的人群求交集，也就是北京的喜欢户外或者爬山的人。

这个结果就是我们想要投广告对应的的人群，而我们的目标就是能够快速地求这个人群对应的用户数。

因此，我们假设平台的全量用户是 8 人，分别是从 uid1 到 uid8。其中北京共有 5 人，分别是 uid 1 到 uid5，对应集合 A；喜欢户外的是 uid1 和 4，对应集合 B；喜欢爬山的是 uid 1、3、5、6，对应集合 C。那么，我们想要投放广告的人数是 A 交上 B 和 C 的并集，uid 1、3、4、5 共 4 人。

听起来就是集合运算，并不复杂。那么难点和挑战在哪里？主要是 3 个方面：

人群包数据量多，基数大。平台的用户数上亿，仅抖音的 DAU 就好几亿，抖音、头条对应的人群包在亿级别。整体的人群基数大，对应的标签也非常多。
计算复杂（单次计算可能包含几百上千个人群包），从之前的图我们可以看出，广告主可以设定一个非常复杂的圈选条件。
查询时长要求短（小于 5 s），其实如果页面上等待时间超过 1s，是有明显感知。如果超过 5 s，那么广告主的体验确实会非常不好。

除了这个之外，人群权限计算的人群包还需要与其他数据 join 进行分析，这就意味着说我们不仅仅只出一个数，还有比较复杂的计算。我们的计算引擎必须要有一定的分析能力，能够进行复杂的分析计算。

在使用 ClickHouse 之前我们也尝试了不少已有的系统，如 Druid、ES、Spark，甚至业务方还自研过一个系统。其中 Druid、ES、Spark 均不能很好的满足时间期望。自研的系统因为我们可以高度的定制化，性能上能够上来，但缺乏一定的灵活性。

因此，通过对比我们选择了 ClickHouse。原因主要有两个方面

第一是快，特别适用于大宽表的场景，这个是其他引擎所不能比拟的。
第二是架构简单，我们可以很好地做很多定制化的开发，甚至去修改整个执行逻辑，这个我后面会提到，我们其实对于 ClickHouse 有比较大的改动。

技术方案 V1

那么首先是我们的第一版技术方案，这个技术方案的背景是，业务提出来希望能够尽快上线，时间比较紧。

我们采用明细存储的方式，表有 2 列，分别是 tag_id 和 uid。每一个 tag_id 表示一个人群包，uid 是对应的用户 id。那么如果是一个比较大的人群包，可能需要用上亿行来表示。我们对 tag_id 建立了主键，因此可以快速的找出对应的用户 id 集合。集合的交集操作会转化为 in，并集为 or，补集为 not in 表示。

我们看一个具体的例子。如果我们要求 A 交上 B 和 C 的并集。那么对应的 sql 就是如此。其中，交集是采用 in 子查询的方式。并集直接用 or 表示。其中，SELECT distinct uid FROM tag_uid_map WHERE (tag_id = B) OR (tag_id = C) 用来表示 B | C。SELECT count distinct(uid) FROM tag_uid_map WHERE tag_id = A 表示集合 A，uid IN 表示求交集计算。

A&(B|C)
SELECT count distinct(uid)
FROM tag_uid_map
WHERE tag_id = A
AND uid IN (
SELECT distinct uid
FROM tag_uid_map
WHERE (tag_id = B) OR (tag_id = C)
)

在这种情况下，我们想要快速的求出 sql 的结果，采用了 2 个优化方向：

因为 clickhouse 是分布式数据库，我们希望尽可能并行计算，减少节点之间数据传输，把计算下推下去，减少汇聚节点的计算压力。
因为最后要获取去重后的用户数，看看如何能够快速计算 count distinct。上一次分享也有人问字节是否在 count distinct 做过一些优化？我们也做了一些优化和尝试。

我们继续看之前的场景， A 交上 B 和 C 的并集。我们有没有办法能够划分不同的区间进行并行计算呢？答案当然是有的。

如果我们把用户 id 按照奇数偶数分为 2 个区间，可以保证一个用户只会在一个区间内，因为用户的 id 要么是奇数要么是偶数，且区间之间用户 id 不重复。那么 A B C 也同样划分为奇偶两个区间。在这样的基础上，可以在区间内单独的计算子集合的结果最后对区间计算结果进行汇总。A 交上 B 和 C 的并集就等于 A_奇数集合交上 B_奇数集合和 C_奇数集合的并集并上 A_偶数集合交上 B_偶数集合和 C_偶数集合的并集的结果。对于人群预估来说，我们更关心集合的数目。A 交上 B 和 C 的并集所对应用户的个数可以转化为，A_奇数集合交上 B_奇数集合和 C_奇数集合的并集所对应用户的个数加上 A_偶数集合交上 B_偶数集合和 C_偶数集合的并集的用户数。因此，通过把用户 id 划分到不同的集合，我们可以在每个集合上并行计算。最后只需要把每个集合的用户数做一次累加就可以，我们的计算方式就是这样的。

以 A 交 B 为例：

我们在数据导入的时候按照用户 id 划分为 4 个区间，分别导入到 4 台不同的机器，保证每台机器上的用户不重复。这样在每一台机器计算完结果后，直接把结果进行汇总。同时，在人群预估的场景下，我们返回的是子区间 count distinct 结果，而不是对应的聚合函数中间状态。这样可以大大减少输的数据量。同时，最后只需要做一次累加，不需要把聚合函数中间状态进行 merge 后求去重后结果。实际场景的话我们划分的区间数可能要比机器数要多，这样才可能并行导入。

因此，在 clickhouse 上的改动主要是两个：

导入的时候按照 uid 分片，实际中肯定不是按照奇偶来划分了
扩充了 sql 语法，并行计算，修改了引擎的执行逻辑。支持 count distinct 中间结果不做 merge 直接进行累加

第二个优化是快速计算 count distinct，这里我们做过几个方向的尝试，比较通用的思路有两个：

优化 hash 函数，能够快速求出 hash 结果。
通过一些近似函数的方式，在允许一定的误差的情况下快速求出结算结果，比如 UniqHLL12/UniqCombined 等

其他还有一些思路偏探索，主要是精确算法下优化 hash 表的结构，减少 hash 冲突。

随着上面的一系列优化后，第一版本的方案上线了。

优点是基本能满足需求，大部分的查询都小于 5 s。
缺点是当表达式非常复杂，特别是存在很多的交集和补集的时候，由于交集和补集需要用子查询来实现，SQL 会非常长，对用户很不友好，且不利于分析。
其次，当人群包非常大且表达式复杂的时候查询容易超时。因为 in 和 not in 的操作是比较花费 cpu 资源的。

随着数据量的不断增长 ClickHouse 在当前存储引擎的支持下也难以保证查询时间,而且这些大查询还会影响其他查询，因此我们觉得有必要做新一版的开发。

技术方案 V2

下面介绍一下我们的第二版方案。这个方案做了很多的优化，我们也已经对核心的技术方案申请了专利。

我们认为，可以使用位图来进行计算，因为位图是一种逻辑上非常巧妙的描叙集合的方法。根据用户 id 的特性，我们准备采用性能最好的稀疏位图索引 RoaringBitmap 来表示一个标签对应的人群包。在这样的情况下，集合的计算可以转换到对应位图的计算。

例如 A 交上 B 和 C 的并集可以转换为 RoaringBitmap 的计算

ClickHouse 其实有引入 RoaringBitmap，但是是 32 位的 bitmap。而我们的用户规模用 32 位表示并不够，因此我们给 ClickHouse 引入了 Bitmap64 类型和一系列的相关计算函数。

我们第二版本的表结构长这样，还是 2 列，但不需要明细存储。一列 tag_id 用来表示标签，另外用类型为 Bitmap64 的 uids 列表示标签所对应的用户 id。

相比于第一个方案，tag_id 只需要存 1 个，会节省空间。另外，uids 用 RoaringBitmap 存储也会比原来的存储要节省不少空间。而集合的交并补也对应了 bitmap 的交并补计算。

如果我们要求 A 交上 B 和 C 的并集。对应的 sql 相比第一版本就要简单很多了。看右边，基本上从表达式就能对计算的内容一目了然，非常直观。相比于使用第一版本的建表和查询方式，使用 bitmap 有如下优势：

空间节省，没有冗余数据，RoaringBitmap 存储高效
计算高效
Sql 直观，无需子查询，且具有更好的拓展性。

光是用 RoaringBitmap 其实是不够的，我们花了 1-2 个礼拜快速做了一个 demo 出来，发现效果并不理想，与第一版本的差距不大。我们在这个基础上做了很多的优化，目标就是让整体计算尽可能得快，可以分为以下几个方面：

和第一版本的想法一样，尽可能的并行计算，减少数据传输
在数据层面进行优化
计算的优化
读取的优化
通过 cache 减少计算的数据量

首先是并行计算，相比于之前用子查询来表示交集和补集，采用 RoaringBitmap 来实现交集和补集要简单很多，这样使得我们的计算可以更加充分的并行，到线程粒度。这样，一方面我们可以更好的利用上多核的计算资源。另一方面，可以更好的控制查询使用的资源，避免一些大查询占用过多资源。如上图所示，我们把全量数据分成很多份，每台机器的每一个线程处理其中一部分的数据，得出对应的计算结果。最后将各线程直接合并。

这个与 ClickHouse 默认的处理机制是不一样的，Clickhouse 在多线程读取的时候，读取的数据并不是固定的，哪个线程处理完了就去读新的数据，当处理速度跟不上的话也会降低线程数目。如果要实现每个线程固定读对应的数据，并在读取完成后完成计算，就需要修改整个读取和处理模型。

这个是我们的读取和处理模型，可以看到，数据在导入的时候被分成了若干份，每一份 uid 都是独立的。我们通过建立 input stream 去读取对应的数据，stream 的数量和数据分成的数量相等，并保证一个同一份数据只会进入一个 Stream。ParallelBitMapProcessor 构造一个线程池，从队列里面一次取 Stream 进行数据读取，当一个线程完全读完一个 Stream 之后，才会调用下一个 stream。

ClickHouse 整体的结构如上图所示，黑色的是原来 ClickHouse 的读取和执行流程，红色的是我们新增的，可以看到，基本上整个读取和执行流程都发生了变化，改动还是比较大的。

在整个并行后我们发现效果并不是非常理想，相比于第一版本的提升并不明显，通过对 RoaringBitmap 底层原理的深入研究和对数据的分析，我们发现，原因是因为区间内的用户 id 过于离散。

离散的原因有 2 点：

uid 的生成并不是连续的。
由于数据按照一定规则均匀划分到不同的区间内，那么就会导致子区间内的数据比原始空间更加离线。

那么为什么离散的情况下会导致计算效果并不理想，大家可能有疑问，RoaringBitmap 不就是用来存储稀疏的数据的吗？

原因跟 RoaringBitmap64 的实现有关，RoaringBitmap64 是由一系列 RoaringBitmap32 表示。实现方式有很多种，一种比较通用的做法用 map 存储，是把前 32 位存成 key，value 是后 32 所对应的 RoaringBitmap32，RoaringBitmap32 的实现如图中所示。

第一层称之为 Chunk（高 16 位），如果该取值范围内没有数据就不会创建 Chunk。

第二层称之为 Container（低 16 位），会依据数据分布进行创建。

RoaringBitmap32 使用两种容器结构：Array Container 和 Bitmap Container。Array Container 存放稀疏的数据，Bitmap Container 存放稠密的数据。若一个 Container 里面的元素数量小于 4096，就使用 Array Container；反之，就用 Bitmap 来存储值。

当数据比较稀疏的时候，我们发现一个人群包对应的 RoaringBitmap64 由很多个 RoaringBitmap32 组成，每个 RoaringBitmap32 内部又由很多个 array container 组成。而对有序数组的交并补计算尽管也比较高效，但是相比于 bitmap 计算来说还是有明显的差异。这样导致计算性能提升不上去。因此我们就在想，能不能通过编码的方式，对区间内的数据进行编码，让数据更加集中，从而提升计算效率。事实上我们也是这么做的，我们实现了一种高效的编码，希望达到如下效果：

编码后同一个区间内的用户相对集中
不同区间的用户编码后同样在不同的区间内
编码后同一个人群包同一个区间内的用户 id 相对集中

通过编码，能够非常好地加速计算，计算速度提升 1~2 个量级

当然，编码的过程是在引擎内部实现的，对用户是无感知的。当数据导入的时候，会自动完成编码。

这块其实有一个比较大的工程量，有这几个问题需要解决：

编码相当于是一个额外的工作量，会对导入有一定影响。同时，如果要导出 uid，需要增加额外的解码过程。如何减少编、解码带来的额外的代价。
原来为了能够尽快导入数据，我们是采用并行导入的方式。增加了额外的编码环节是否会导致导入必须要串行来完成，并行导入如果都在写字典是否会导致数据产生冲突
主备之间如何高效同步字典，避免字典的同步不及时导致数据无法解码。有一些一致性的问题要处理。
字典如何高效管理、备份，避免丢失。

除了数据通过编码优化分布性外，我们还从工程的角度对计算进行了优化。主要有下面 3 点：

通过一些指令集计算和汇编指令对计算进行加速，在我们实际测试中发现这个能够大大加快计算速度。
另外，我们 bitmap 的计算能够尽可能在原地完成，减少数据拷贝。举个例子，求 A 与 C 的并集，我们可以直接在 A 上面进行计算，得到结果。当我们的计算表达式包含多个 A 的时候且 A 在左侧的时候，这样就失效了。因此，需要我们处理的时候需要对整个表达式进行处理和判断，看看哪些计算可以在原地完成。当然，更进一步的话，在这个 Case 中我们通过移动位置（A 和 C 交换位置）也是可以做到原地计算的。
是我们在对比第一第二版本的时候发现，bitmap 在交集和补集的性能上相比原来的子查询有非常明显的提升，但是在大量的并集的情况下与原来的相比提升不够明显。这个一方面说明 clickhouse 的性能还是非常优越的，另一方面也给我们带来了挑战。最后我们发现可以把 RoaringBitmap32 的 Fast Union 的思想移植到 RoaringBiamap64 上，通过 lazy 计算的方式，提高大量并集的计算性能。

当然，以上说的其实是我们在工程实践的一些大的有明显效果的优化点，其实小的优化点还有很多，工程上要做的事情很多。

除了计算以外，读取的优化也很重要。大家都知道 clickhouse 是列存数据库，对于每一列的数据又是分块存储的，默认是每 8192 行为一块。分块存储的好处是能够更好的做压缩，减小数据存储。对于一些基本类型来说效果很好。但是对于 bitmap 类型来说本身值的类型就非常大，8192 行组成的块大小非常大，如果我只是读取其中的一个 bitmap，会有很大的读放大，会非常影响性能。

另外，由于 clickhouse 是一个在主键上的稀疏索引，并不能精确地定位某一个块中是否包含对应的数据。这个对于普通类型也是没有问题的，因为有的时候建立精确索引并且查找索引的代价还不如直接暴力扫原始数据。但是对于 bitmap 来说我们是希望能够精确到定位到数据的。

因此我们做了这几个优化：

调整块的大小，把默认的 8192 行改成了 128，这个是我们实际测试中在我们场景的最佳实践。如果数据太细，那么会导致 mark 文件过大，读取索引定位数据的时间变长。
定期合并历史数据，因为我们有的标签是一个增量数据，我们希望通过一些合并减少数据读取
通过二级索引的方式能够更好的精确定位，尽量减少读取不需要的数据

最后一个优化点也是很多系统都必备的，那就是 cache。因为用户读取的数据和计算的结果通常具有 2 8 原则，即经常读取的都是一小部分数据。因此，我们通过 cache 可以加速第二、第三次读取时间。实际上我们做了三层的 cache：

读取层面的 cache，对于同一个标签，通过 cache 第二次可以直接命中内存
中间计算结果的 cache，还是举之前望远镜例子，广告主除了想看到北京的喜欢户外或者爬山的人的一共有多少人。还想看到这些人在头条、抖音等各端上分别多少人。如果我们是依次计算每个结果，这里面就有重复计算的过程。因此我们目前的做法是提供一个 udf multiCount，可以让用户复用中间的计算结果。比如我们想计算，A&B&C&D&E&F，A&B&C&D&E&F&G，A&B&C&D&E&F&H，这里有重复的部分。可以用这样的函数一次性计算出结果。multiCount 函数里 _1 来表示第一个表达式的计算结果，函数的结果返回一个数组，分别是每个表达式的计算结果。通过这种方式，一个是避免了重复结果的反复计算，另一个也减少了整体的 qps。当然，这样的方法还是有一定的局限性，后面讲未来的展望时我会提到我们想做的更通用性一些。
对结果的 cache，结果 cache 只需要记录一个 string 用来表示计算的表达式和一个 uint64 表示结果，代价非常小。那么可以用很小的空间存储大量的计算结果。当然前提是确实出现不少名字缓存的情况。

做了这么多，都是为了降低查询的时间，减少导入和查询的资源，那么到底效果怎么样呢？可以说还是非常突出的。从空间上来说，采用 RoaringBitmap 可以减少 tag_id 列的冗余存储，同时 uid 采用压缩存储，因此整的空间存储降低为原来的 1/3，因为数据量降低了，因此导入也变快了，导入时长也缩短为原来的 1/3，同时，在查询性能上收益非常明显，avg/pct99/max 下降明显，消除绝大多数 5 s 以上的大查询，可以说达到了开发的预期。最后，在资源上效果也很不错，CPU 使用下降明显，内存使用上 PageCache 节省 100 G+ 以上。

查询时长

这个图是上线后的效果图，可以看到，原来确实是经常有一些大的查询，有些时间久的甚至超过了 20 s。上线后如右边的红框所示，很少看到超过 5 s 的查询了，绝大部分查询非常稳定。这个其实还是我们没有上中间结算结果 cache 时候的效果图，当我们通过 multiCount 缓存中间结果后，直接把 qps 下降了 4 倍以上。

当然，要在更多的场景用上来，我们其实还要做不少工作的。比如，为了支持一些更复杂的查询我们还开发了其他一系列计算的 udf，比如结果不返回 count 而是 array 用来做投放。

同时，为了支持与其他表 join，我们还支持了 in bitmap 语法，能够让 bitmap 表与其他表进行 join，join 的时候，因为做了编码，因此需要支持字典的复用（其他表使用相同的字典进行编码）等等。

未来展望

可以说，第二版本达到了我们的预期，也在线上取得了比较大的成果，业务方的反馈也很不错。可能在很长一段时间内都能满足业务需要。随着数据量的不断增长，将来又有哪些方面可以做一些持续的优化呢？我对未来的展望简单做了一些总结:

我们主要想从这三个方面进行迭代：

从计算层面和数据层面进行更多的优化，读取的数据更少，更精准的找到真正要读取的数据。减少甚至尽可能消除读放大。计算上能够想更多的招，包括利用一些新硬件减少计算的时间
从 cache 层面能够做的更加智能化。通过解析表达式，从子表达式的粒度看看是否能够把一些公共子项缓存起来，这样 cache 才会更通用。当然，这可能要引入一些机器学习的算法。
扩充表达式的表现能力，能够在更过的场景得到应用。大家可以看到，目前我们在计算的时候是使用一个 uint64 来表示一个对应的标签，如果表示一个多维的标签，我们内部有一些做法，但是还不是很通用，业务方用起来也有点费劲，我们希望能够更好的支持标签的表达。同时，更多的场景也需要一些更多的 udf 开发，我们会逐步支持各个场景的需求。

最后，此次分享主要介绍了 ClickHouse 在字节广告的应用场景，主要是人群预估、人群画像和统计分析这几个方面。其次，就人群预估这个场景介绍了我们的实现方案和优化的思路，以及未来的迭代计划。

以上就是本次分享的全部内容，谢谢。

作者介绍：

董一峰，字节跳动 ClickHouse 研发工程师

本文转载自公众号字节跳动技术团队（ID：toutiaotechblog）。

原文链接：

ClickHouse 在字节广告 DMP& CDP 的应用

创作场景

ClickHouse 在字节广告 DMP& CDP 的应用