ClickHouse场景及其原理

ClickHouse场景及其原理

ClickHouse是Yandex公司于2016年开源的一个列式数据库管理系统。Yandex的核心产品是搜索引擎，非常依赖流量和在线广告业务，因此ClickHouse天生就适合用户流量分析。

这里直接从原始数据开始消费，通过Flink清洗任务将数据洗入数据仓库存储，在数据仓库经过作业清洗并在ClickHouse生成用户行为明细，可以称作无模型化明细数据。利用ClickHouse原生的RoaringBitMap函数对参与计算的行为人群交并差集计算。

那么难点和挑战在哪里？主要是 3 个方面：

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

ClickHouse有如下特点：

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

标签建群

如上，可以基于标签进行交并差逻辑计算。

实现要点

1. 根据标签ID的定义，从行为数据仓库中给每个人打标并生成相应的标签编码集，标签编码集通过Array[Array]/[Array]的方式以uid作为主键写入到分布式ClickHouse标签表中。

2. 如多维度标签1234定义为《用户在最近多少天浏览某个页面的次数》
   用户uid=6666在分布式表列为1234标签编码集可能是
   [03_page1_4, 03_page2_4, 03_page3_4, 03_page4_4]
   表示用户6666最近3天浏览page1是4次，用户6666 最近3天浏览page2是4次，用户6666最近3天浏览page3是4次，用户6666最近3天浏览page4是4次，上述映射到二维数组就是
   [ [03 ,page1 ,4], [03 ,page2 ,4], [03 ,page3 ,4], [03 ,page4 ,4]
   标签过滤则使用ck的函数(label_1234, ( ([1] = ‘01’ and [2] = ‘page1’) or ([1] = ‘04’ and [2] = ‘page2’) )

3. 如单维度标签5678定义为《用户感兴趣的商品分类》
   用户uid=6666 标签编码集可能是
   [01, 02, 03, 04]
   表示用户6666感兴趣的分类是01/02/03/04
   标签过滤则使用ck的函数hasAny(array1, array2)

4. 前端通过选择标签并选择其对应的维度，然后进行标签之间的交并差逻辑，并生成对应的规则RuleContent。

5. 后端解析到RuleContent，并通过规则引擎(DFS生成bitmap语句)从元数据表中获取标签元数据(如维度的index和array index的对应关系/标签所在ck分布式表schame和表名等)生成对应的bitmap Sql语句，不同标签之间使用clickhouse之bitmap的交并差获取相应的目标人群。

采用性能最好的稀疏位图索引 RoaringBitmap 来表示一个标签对应的人群包。在这样的情况下，集合的计算可以转换到对应位图的计算例如 A 交上 B 和 C 的并集可以转换为RoaringBitmap的计算。

实现样例

RoaringBitmap

bitmap

Java中BitSet可以用来替代HashSet做数字精确去重，在Redis中也有setbit和getbit直接操作BitMap，其底层实现都是直接翻译成0|1二进制结构，但其存在以下两个很明显的问题

1. BitSet 内部的long[ ]数组(long含有8*8 bit)是基于向量的，即随着Set内存放的最大数字而动态扩展。数组的最大长度计算公式：(maxValue−1)>>6+1 ，也就是说当存储一个较大值进去，就直接可以让内存占用M级别以上，过大的值域将会导致 OOM（比如指定 Long.MAX_VALUE）。
2. 一个BitMap存储40亿个数据为例，基于32位的Unsigned Int，大概消耗232bit=229B=29MB=512MB内存，但当数据稀疏的时候，也需要要开辟这么大的内存空间，就发挥不出其存储效率。

RoaringBitmap32

采用分桶的思想来将稀疏数据存储节约内存，https://www.ics.uci.edu/~goodrich/teach/cs165/notes/BinPacking.pdf

RBM首先会对其划分为16+16，前16位用来存储Container位置编号，后16位用来存具体Container内容。例如数字31，被存储在第31/216=0个位置的Container中。值得注意的是Container是在需要创建的时候才会开辟，而不是直接初始化所有位置的Container。

• RoaringBitmap64是由一系列RoaringBitmap32表示。实现方式有很多种，一种比较通用的做法用map存储，是把前 32 位存成 key，value是后32 所对应的 RoaringBitmap32，RoaringBitmap32 的实现如图中所示。第一层称之为 Chunk（高16位），如果该取值范围内没有数据就不会创建 Chunk。第二层称之为Container（低16位），会依据数据分布进行创建。

• RoaringBitmap32使用两种容器结构：Array Container和Bitmap Container。

  • Array Container存放稀疏的数据，可以用以存储双字节类型的数字，最大支持216/(2×8)=4096个数，空间开销为(2+2×c)B，c为基数，时间开销为O(log(n))。
  • Bitmap Container存放稠密的数据。最大存储16位的的数据也就是65536个数，空间开销固定为8KB(2^16/23/2^10)，时间开销为O(log(1))，若一个Container里面的元素数量小于4096，就使用Array Container；反之就用Bitmap来存储值。
  • RunContainer对连续序列采用RLE编码压缩，例如序列11,12,13,14,15会被压缩为(11,4)，4表示11后面有连续4个数字，极端情况下如果序列都是连续的，那么最终只需要4B，但如果序列是奇数或者偶数列，那不仅不会压缩，甚至还会膨胀两倍。类似ArrayContainer，RunContainer由可变长度的Unsigned Short数组存储RLE压缩后的数据，空间开销与它存储的连续序列数runs有关（简称r），为(2+4×r)B，时间开销为O(log(n))。
  • SharedContainer，在进行RBM之间的拷贝的时候，有时并不需要将一个Container拷贝多份，可以使用SharedContainer来指向实际的Container，这样可以满足多个RBM共享同一个Container存储空间。

  在指定位置编号的新Container上插入一个元素时，默认用ArrayContainer来存储；如果是插入连续序列元素时，例如API自带的addRange方法，会生成RunContainer；如果是一串不规则序列，RBM的Optimaze会根据插入后ArrayContainer和RunContainer的空间占用大小来选择。当插入ArrayContainer的容量超过4096(超出8KB)，RBM自动将其转成BitmapContainer来存储；反之，如果BitmapContainer被删除后的元素个数小于4096，RBM根据Optimaze来决定转为ArrayContainer或者RunContainer。

uid映射递增优化

uid通过特定的编码方式(高32位表示某种含义，低32位表示某种含义)，并非连续递增生成，这样会加大uid的稀疏性。当数据比较稀疏的时候，一个人群包对应的RoaringBitmap64由很多个 RoaringBitmap32组成，每个RoaringBitmap32内部又由很多个array container组成。而对有序数组的交并补计算尽管也比较高效，但是相比于bitmap计算来说还是有明显的差异。这样导致计算性能提升不上去。因此能不能通过编码的方式，对区间内的数据进行编码，让数据更加集中，从而提升计算效率。

希望达到如下效果：

• 编码后同一个区间内的用户相对集中
• 不同区间的用户编码后同样在不同的区间内
• 编码后同一个人群包同一个区间内的用户 id 相对集中
• 通过编码，能够非常好地加速计算，计算速度提升 1~2 个量级
• 编码的过程是在引擎内部实现的，对用户是无感知的。当数据导入的时候，会自动完成编码。

有这几个问题需要解决：

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

组合建群

人群预估

人群画像

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

人群导入

基于ClickHouse构建的一套海量UBA技术解决方案，底层ClickHouse集群的稳定性 、读写性能、资源使用率均会影响上层业务的使用体验。与此同时，海量数据如何导入ClickHouse，以及数据导入过程的稳定性、导入效率、资源消耗在很大程度上决定了ClickHouse集群的整体稳定性和使用效率。所以，一个稳定高效的数据导入方案对于一套UBA解决方案来说是必不可少的。

统计分析

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

ClickHouse应用优化实践

在支持UBA场景各项功能模块的过程中，我们针对ClickHouse的查询，存储等方面做了大量应用优化工作。下面选取其中几个优化点做简单介绍。

查询下推

ClickHouse中的针对分布式表的查询会被改写成对local表的查询并发送到集群各个shard执行，然后将各个shard的中间计算结果收集到查询节点做合并。当中间计算结果很大时，比如countDistinct、 windowFunnel函数等，查询节点的数据收集和数据合并可能成为整个查询的性能瓶颈。

查询下推的思路就是尽量将计算都下推到各个shard执行，查询节点仅收集合并少量的最终计算结果。不过，也不是所有查询都适合做下推优化，满足以下两个条件的查询可以考虑做下推优化：

• 数据已经按照计算需求做好sharding：比如，UBA场景的数据已按user id做好了sharding，所以针对用户的漏斗分析，UV等计算可以下推到各个shard执行。否则，下推后的计算结果是不准确的。
• 计算的中间结果较大：sum，count等计算是无需下推的，因为其中间结果很小，合并计算很简单，下推并不能带来性能提升。

下面，我们以上文中提到的漏斗分析为例，阐述一下如何做查询下推。

上图是用windowFunnel函数实现漏斗分析的一个SQL，如图中“执行步骤”所示，该查询需要从各shard收集大量数据并在查询节点完成计算，会产生大量数据传输和单点计算量。

我们先使用配置distributed_group_by_no_merge做了一版下推优化：

优化SQL-V1将windowFunnel的计算下推到各个shard执行，仅在查询节点对windowFunnel的最终结果做聚合计算。在我们的场景下，该版本较上一版本性能提升了5倍以上。

为了更进一步做查询下推，我们利用cluster + view的函数组合，将聚合查询进一步下推：

优化SQL-V2的性能较优化SQL-V1进一步提升30+%.

Array和Map的跳数索引支持

UBA场景中的事件数据有很多公共属性和私有属性，公共属性被设计为表的固定字段，而私有属性因为各个事件不尽相同，所以采用Array/Map来存储。最初的设计是采用两个数组分别存储属性名和属性值，ClickHouse支持Map结构后，则在后续模块中采用Map来满足类似需求。无论是Array还是Map，最初都不支持创建跳数索引，所以在其他索引字段过滤效果有限的情况下，针对Array和Map的操作可能会成为查询的性能瓶颈。

针对这个问题，我们给Array和Map加上了Bloom filter等跳数索引支持，针对Map仅对其key构建索引。在某些出现频率较低的私有属性过滤场景下，Array/Map的跳数索引可以收获数倍的性能提升。

压缩算法优化

ClickHouse常用的数据压缩方式有三种，分别为LZ4、LZ4HC以及ZSTD。针对不同的数据类型，数据分布方式来使用特定的编码方式可以大大提高数据压缩率，以减少存储成本。

针对UBA场景，我们测试了不同压缩算法的压缩率，写入性能，查询性能。相较默认的LZ4，ZSTD(1)在压缩率上普遍可以节省30%以上的存储空间，查询性能方面未见明显差异，不过写入性能在某些场景下有20%左右的下降。由于UBA场景数据存储压力较大，同时对数据时效性要求不是很高，因此我们最终选择了ZSTD(1)作为主要的压缩方式。