ClickHouse UBA版本是字节跳动内部在开源版本基础上为火山引擎增长分析（对话框回复数字“10”了解产品详情）专门深度定制优化的版本。本篇文章介绍在字典编码方向上的优化实践。
文 |Jet He 字节跳动数据平台研发工程师，长期致力于OLAP引擎开发优化，在OLAP领域、用户行为在线分析等有丰富的经验。
虽然ClickHouse列存已经有比较好的存储压缩率，但面对海量数据时，磁盘空间的占用跟常用的Parquet格式相比仍然有不少差距。特别是对于低基数列时，Parquet的存储空间会更加有优势。同时，大多这类数据的事件属性都有低基数的特征，例如事件属性中的城市、性别、品牌等等。Parquet会自动对低基数列做字典编码，因此会获得更高的存储效率。
同时ClickHouse官方也提供了一种字典编码的解决方案即LowCardinality类型，网上也有一些测试Benchmark数据，效果不错，可以进一步降低存储空间和提升查询、IO性能。上图是内部LowCardinality的存储结构，写入过程中，会构建一个字典，列数据通过Positions表示，数值是字典中每个Unique值的Index。其他更加详细的介绍可以参考官方文档。但在内部环境中通过验证测试发现，原始的LowCardinality列存在以下两个致命问题：- 在LowCardinality列比较多的情况下(平均300+)，Part Merge耗时严重，在大量实时写入的场景下，Merge速度跟不上写入速度，最终会导致集群不可用；
- 用户数据中事件属性多种多样，UBA版本通过动态Map列实现用户属性的自由上报，也会导致某些属性基数非常大，不再适合做字典编码，否则会同时导致存储、计算性能下降。
如果以上两个问题得不到解决，那么字典编码功能就无法上线使用。需要一种解决方案，能够做到支持大量的列做字典编码的同时需要保证内部Part的Merge速度，另外就是面对高基数列时需要一个Fall back方案，让高基数列时不再做字典编码，改用原始列存储。原作者在做字典编码技术分享时也提到了针对高基数列时Fall back到原始列的构想，但社区版本中目前没有付诸实现。首先来看针对LowCardinality列Part Merge的优化方案。
这里先介绍下ClickHouse的Part Merge过程。ClickHouse的数据组织是以Part形式存在的，每个Part对应磁盘的一个数据目录，每次写入都会生成一个Part，Part目录下包含各个列的数据文件。因此每次写入的时候最好是大批量的写入，才能有较好的写入吞吐。
ClickHouse有常驻Worker线程不断的做Part的Merge，将小Part不断地Merge成大Part，从而提升查询性能。如果Part不能及时Merge会造成严重的性能问题，更有甚者还会造成Inodes耗尽。
当统一把事件属性列（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即可。
首先进行字典的Merge，在Merge的过程中，先将待Merge的几个Part中的字典部分做Merge，生成一个字典，同时记录下每个Part这个列中Index的变化，这个变化类似一个转换矩阵;
Index Merge过程中将这个转换矩阵逐个Apply到Part中的Index，有时这个转换矩阵为空，例如Unique值很少的列，基本可以保证每个Part的字典基本一样，如果转换矩阵为空这步操作会直接跳过。
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列的两大绊脚石，接下来看下我们在内部一些大应用上的测试验证效果。磁盘占用
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的表查询性能更优，耗时更短。可以看出，基本上所有SQL读取的数据量都有明显的减少，对磁盘IO的压力会降低很多。SQL8对应的查询列已经做了Fall back，所以跟原始列读取数据量持平。其中除了SQL8发生了Fall back外，其他查询均是LowCardinlity表内存使用量较大。由于LowCardinality列计算过程中，如filter，需要读取的Part字典并将列反解出来，每个Part的字典是独立存在的，这样在计算过程中会多占用些内存。这块也是后续优化的重点。目前ClickHouse UBA版已经全面启用了字典编码列，并且在火山引擎增长分析（DataFinder）服务的多个客户环境中已经上线。从实践反馈看，我们为客户节省了大量存储资源，同时在大多数场景下查询性能也有提升明显。总体上由于字典位于每个Part中独立存储，查询过程中无法做到在压缩域直接计算，因而会造成个别场景下查询性能不佳，并且内存使用量上会增加。下一步工作的重点将是优化LowCardinality的计算过程，例如把字典做成Part间共享的，可以减少计算过程中内存占用，进一步扩展复杂场景在可以直接在压缩域做计算。产品介绍
火山引擎增长分析
一站式用户分析与运营平台，为企业提供数字化消费者行为分析洞见，优化数字化触点、用户体验，支撑精细化用户运营，发现业务的关键增长点，提升企业效益。
后台回复数字“10”了解产品