业务背景
众所周知，广告是很多互联网公司的主要收入，对于字节跳动来说也是如此。那么，在字节跳动广告的 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 个方面：
除了这个之外，人群权限计算的人群包还需要与其他数据 join 进行分析，这就意味着说我们不仅仅只出一个数，还有比较复杂的计算。我们的计算引擎必须要有一定的分析能力，能够进行复杂的分析计算。
在使用 ClickHouse 之前我们也尝试了不少已有的系统，如 Druid、ES、Spark，甚至业务方还自研过一个系统。其中 Druid、ES、Spark 均不能很好的满足时间期望。自研的系统因为我们可以高度的定制化，性能上能够上来，但缺乏一定的灵活性。
因此，通过对比我们选择了 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 表示求交集计算。
SELECT count distinct(uid)FROM tag_uid_mapWHERE tag_id = ASELECT distinct uidFROM tag_uid_mapWHERE (tag_id = B) OR (tag_id = C)在这种情况下，我们想要快速的求出 sql 的结果，采用了 2 个优化方向：
我们继续看之前的场景， 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 上的改动主要是两个：
第二个优化是快速计算 count distinct，这里我们做过几个方向的尝试，比较通用的思路有两个：
其他还有一些思路偏探索，主要是精确算法下优化 hash 表的结构，减少 hash 冲突。
随着上面的一系列优化后，第一版本的方案上线了。
随着数据量的不断增长 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 其实是不够的，我们花了 1-2 个礼拜快速做了一个 demo 出来，发现效果并不理想，与第一版本的差距不大。我们在这个基础上做了很多的优化，目标就是让整体计算尽可能得快，可以分为以下几个方面：
首先是并行计算，相比于之前用子查询来表示交集和补集，采用 RoaringBitmap 来实现交集和补集要简单很多，这样使得我们的计算可以更加充分的并行，到线程粒度。这样，一方面我们可以更好的利用上多核的计算资源。另一方面，可以更好的控制查询使用的资源，避免一些大查询占用过多资源。如上图所示，我们把全量数据分成很多份，每台机器的每一个线程处理其中一部分的数据，得出对应的计算结果。最后将各线程直接合并。
这个与 ClickHouse 默认的处理机制是不一样的，Clickhouse 在多线程读取的时候，读取的数据并不是固定的，哪个线程处理完了就去读新的数据，当处理速度跟不上的话也会降低线程数目。如果要实现每个线程固定读对应的数据，并在读取完成后完成计算，就需要修改整个读取和处理模型。
这个是我们的读取和处理模型，可以看到，数据在导入的时候被分成了若干份，每一份 uid 都是独立的。我们通过建立 input stream 去读取对应的数据，stream 的数量和数据分成的数量相等，并保证一个同一份数据只会进入一个 Stream。ParallelBitMapProcessor 构造一个线程池，从队列里面一次取 Stream 进行数据读取，当一个线程完全读完一个 Stream 之后，才会调用下一个 stream。
ClickHouse 整体的结构如上图所示，黑色的是原来 ClickHouse 的读取和执行流程，红色的是我们新增的，可以看到，基本上整个读取和执行流程都发生了变化，改动还是比较大的。
在整个并行后我们发现效果并不是非常理想，相比于第一版本的提升并不明显，通过对 RoaringBitmap 底层原理的深入研究和对数据的分析，我们发现，原因是因为区间内的用户 id 过于离散。
离散的原因有 2 点：
那么为什么离散的情况下会导致计算效果并不理想，大家可能有疑问，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 计算来说还是有明显的差异。这样导致计算性能提升不上去。因此我们就在想，能不能通过编码的方式，对区间内的数据进行编码，让数据更加集中，从而提升计算效率。事实上我们也是这么做的，我们实现了一种高效的编码，希望达到如下效果：
通过编码，能够非常好地加速计算，计算速度提升个量级
当然，编码的过程是在引擎内部实现的，对用户是无感知的。当数据导入的时候，会自动完成编码。
这块其实有一个比较大的工程量，有这几个问题需要解决：
除了数据通过编码优化分布性外，我们还从工程的角度对计算进行了优化。主要有下面 3 点：
当然，以上说的其实是我们在工程实践的一些大的有明显效果的优化点，其实小的优化点还有很多，工程上要做的事情很多。
除了计算以外，读取的优化也很重要。大家都知道 clickhouse 是列存数据库，对于每一列的数据又是分块存储的，默认是每 8192 行为一块。分块存储的好处是能够更好的做压缩，减小数据存储。对于一些基本类型来说效果很好。但是对于 bitmap 类型来说本身值的类型就非常大，8192 行组成的块大小非常大，如果我只是读取其中的一个 bitmap，会有很大的读放大，会非常影响性能。
另外，由于 clickhouse 是一个在主键上的稀疏索引，并不能精确地定位某一个块中是否包含对应的数据。这个对于普通类型也是没有问题的，因为有的时候建立精确索引并且查找索引的代价还不如直接暴力扫原始数据。但是对于 bitmap 来说我们是希望能够精确到定位到数据的。
因此我们做了这几个优化：
最后一个优化点也是很多系统都必备的，那就是 cache。因为用户读取的数据和计算的结果通常具有 2 8 原则，即经常读取的都是一小部分数据。因此，我们通过 cache 可以加速第二、第三次读取时间。实际上我们做了三层的 cache：
做了这么多，都是为了降低查询的时间，减少导入和查询的资源，那么到底效果怎么样呢？可以说还是非常突出的。从空间上来说，采用 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 的时候，因为做了编码，因此需要支持字典的复用（其他表使用相同的字典进行编码）等等。
未来展望
可以说，第二版本达到了我们的预期，也在线上取得了比较大的成果，业务方的反馈也很不错。可能在很长一段时间内都能满足业务需要。随着数据量的不断增长，将来又有哪些方面可以做一些持续的优化呢？我对未来的展望简单做了一些总结:
我们主要想从这三个方面进行迭代：
最后，此次分享主要介绍了 ClickHouse 在字节广告的应用场景，主要是人群预估、人群画像和统计分析这几个方面。其次，就人群预估这个场景介绍了我们的实现方案和优化的思路，以及未来的迭代计划。
以上就是本次分享的全部内容，谢谢。
作者介绍 ：
董一峰，字节跳动 ClickHouse 研发工程师
原文链接 ：
ClickHouse 在字节广告 DMP& CDP 的应用
