干货｜ClickHouse 在UBA系统中的字典编码优化实践

ClickHouse UBA版本是字节跳动内部在开源版本基础上为 火山引擎 增长分析 （对话框回复数字“10”了解产品详情）专门深度定制优化的版本。本篇文章介绍在字典编码方向上的优化实践。

文 |Jet He 字节跳动数据平台研发工程师，长期致力于OLAP引擎开发优化，在OLAP领域、用户行为在线分析等有丰富的经验。

DataFinder

背景

虽然ClickHouse列存已经有比较好的存储压缩率，但面对海量 数据时，磁盘空间的占用跟常用的Parquet格式相比仍然有不少差距。 特别是对于低基数列时，Parquet的存储空间会更加有优势。

同时， 大多这类数据的事件属性都有低基数的特征，例如事件属性中的城市、性别、品牌等等。 Parquet会自动对低基数列做字典编码，因此会获得更高的存储效率。

同时ClickHouse官方也提供了一种字典编码的解决方案即LowCardinality类型，网上也有一些测试Benchmark数据，效果不错，可以进一步降低存储空间和提升查询、IO性能。

上图是内部LowCardinality的存储结构，写入过程中，会构建一个字典，列数据通过Positions表示，数值是字典中每个Unique值的Index。其他更加详细的介绍可以参考官方文档。

但在内部环境中通过验证测试发现，原始的LowCardinality列存在以下两个致命问题：

1. 在LowCardinality列比较多的情况下(平均300+)，Part Merge耗时严重，在大量实时写入的场景下，Merge速度跟不上写入速度，最终会导致集群不可用；

2. 用户数据中事件属性多种多样，UBA版本通过动态Map列实现用户属性的自由上报，也会导致某些属性基数非常大，不再适合做字典编码，否则会同时导致存储、计算性能下降。

如果以上两个问题得不到解决，那么字典编码功能就无法上线使用。需要一种解决方案，能够做到支持大量的列做字典编码的同时需要保证内部Part的Merge速度，另外就是面对高基数列时需要一个Fall back方案，让高基数列时不再做字典编码，改用原始列存储。原作者在做字典编码技术分享时也提到了针对高基数列时Fall back到原始列的构想，但社区版本中目前没有付诸实现。

DataFinder

解决方案

当统一把事件属性列（Map列）改为LowCardinality列时，发现Part Merge耗时严重，Part数会不断增长，最终会导致集群不可用。通过Profile发现，在LowCardinality列Part Merge时，耗时主要发生在字典构造上，具体如下图灰色部分所示：

即在做Part Merge过程中，首先会通过Primary Key列做排序，然后从每个Part中获取对应的Row写入到一个新的Part中。例如一次从Part1中取3行写入到新Part中，下一次从Part2中取5行写入到新Part中，写入到新Part时，LowCardinality首先做构建新的字典，并生成好倒排索引，形成一个新的LowCardinality列，然后通过Column的Insert接口完成写入。另外在构建字典的过程中，是通过一个HashTable实现，这样在做Merge时这块的性能损耗较大，所以优化的关键点就是在于字典的构建过程。

这里实现了一种先构建字典后做具体Merge的思路，即多个Part的Merge过程中，词典只需要构建一次，然后接下来的Merge只需要将Index直接Append写入到新Part即可。

整个过程可以分为两个过程：

01 -Dictionary Merge

首先进行字典的Merge，在Merge的过程中，先将待Merge的几个Part中的字典部分做Merge，生成一个字典，同时记录下每个Part这个列中Index的变化，这个变化类似一个转换矩阵;

Index Merge过程中将这个转换矩阵逐个Apply到Part中的Index，有时这个转换矩阵为空，例如Unique值很少的列，基本可以保证每个Part的字典基本一样，如果转换矩阵为空这步操作会直接跳过。

02 -Index Merge

Index Merge过程跟之前的Merge过程一致，只不过这里不再做字典构建了，会直接将列中的Index Append 到新列的Index中，如下图所示：

经过这个Merge优化后，LowCardinality的Merge性能有明显提升，在大量写入的场景也能应付自如，写入的Part可以得到及时Merge。

具体的性能优化测试数据如下表所示，Merge速度的是在表写入过程中统计得出，写入大量大概10亿左右：

	Merge优化前	Merge优化后
float64 类型 (distinct 200)
6~7 MiB/sec	37 ~ 45 MiB/sec
string 类型 (distinct 100000)
6 ~ 8 MiB/sec	12 ~ 40.53 MiB/sec
string 类型 (distinct 1M)
~ 25 MiB/sec	~ 28 MiB/sec
string 类型 (distinct 10M)
~ 44.99 MiB/sec	~ 28 MiB/sec

可以看出在基数10万以内时性能提升非常明显，当基数100万+时，性能提升不明显，并且在1000万时还会导致性能回退。 这里也不难理解，因为当基数变大时，Merge过程中转换矩阵会变得很大，转换矩阵的Apply的过程就会变成一个新的瓶颈点。 解决这一问题的只有Fall back方案，即将高基数列自动不做字典编码。

Fall back方案在内部做了很多讨论，也跟原作者讨论了可能的实现方案。

最终通过LowCardinality内部封装的方式实现。如下图所示：

Stream可以理解为文件流，通过Version值标识该列是否是已经是Fall back的列。

内部复用了Index Stream，如果发生了Fall back那么这个Stream里面的值便是原始列的值。Fall back可以发生在实时写入过程中和Part Merge过程中。如果此列发生了Fall back后续的所有Part都将是Fall back的。

Fall back后，一个高基数列的Merge速度和存储性能对比，连续写入1亿条记录的统计：

LowCardinality Column
LowCardinality Fall back Column
Native Column
Merge速度
28M/s ~ 70M/s
125M/s ~ 190M/s
200M/s ~ 210M/s
存储空间
1063M
1013M
1013M

从表中可以看出，Fall back后的列基本跟原始列性能接近，至少保证Merge和存储性能没有退化。 如果不做Fall back，存储空间占用会比原始列还要多，Merge性能无法支撑实时写入。

通过Merge优化和自动Fall back解决了LowCardinality列的两大绊脚石，接下来看下我们在内部一些大应用上的测试验证效果。

DataFinder

性能验证

下面是在内部某些大APP上的验证结果。

磁盘占用

Column number
Rows
Disk size
LowCardinality
Native
6000+
4亿
79G

| 115G

(+45.57%) | | 6000+ | 50亿 | 829G | 1248G

(+50.54%) | | 4000+ | 1.5亿 | 17G | 24G

(+41.18%) | | 100+ | 1.4亿 | 6.5G | 7.7G

(+18.46%) |

数据表是内部某些APP某个时间段的数据。从上表中可以看出，列越多，数据量越大，存储空间下降就会越明显，最高可以节省一半的数据存储空间。在数据量非常的大APP场景下，上线LowCardinality后可以节省大量的存储资源。

针对某个APP，获取其典型的10个业务SQL，做查询性能测试，下面是两个数据表分别查询的对比测试结果：

从上图可以看出，有两个SQL导致查询性能有回退现象，其余SQL都是LowCardinality的表查询性能更优，耗时更短。

10个查询对应的磁盘数据读取量：

可以看出，基本上所有SQL读取的数据量都有明显的减少，对磁盘IO的压力会降低很多。SQL8对应的查询列已经做了Fall back，所以跟原始列读取数据量持平。

下图是查询时对应的内存使用量：

其中除了SQL8发生了Fall back外，其他查询均是LowCardinlity表内存使用量较大。由于LowCardinality列计算过程中，如filter，需要读取的Part字典并将列反解出来，每个Part的字典是独立存在的，这样在计算过程中会多占用些内存。这块也是后续优化的重点。

DataFinder

小结

‍目前ClickHouse UBA版已经全面启用了字典编码列，并且在火山引擎增长分析（DataFinder）服务的多个客户环境中已经上线。

从实践反馈看，我们为客户节省了大量存储资源，同时在大多数场景下查询性能也有提升明显。总体上由于字典位于每个Part中独立存储，查询过程中无法做到在压缩域直接计算，因而会造成个别场景下查询性能不佳，并且内存使用量上会增加。

下一步工作的重点将是优化LowCardinality的计算过程，例如把字典做成Part间共享的，可以减少计算过程中内存占用，进一步扩展复杂场景在可以直接在压缩域做计算。

参考文献

• https://github.com/yandex/clickhouse-presentations/raw/master/meetup19/string\_optimization.pdf
• https://clickhouse.com/docs/en/sql-reference/data-types/lowcardinality/

点击 阅读原文

了解 增长分析

产品介绍

火山引擎增长分析

一站式用户分析与运营平台，为企业提供数字化消费者行为分析洞见，优化数字化触点、用户体验，支撑精细化用户运营，发现业务的关键增长点，提升企业效益。

后台回复数字“10”了解产品

- End -