ClickHouse UBA 版本是字节跳动外部在开源版本根底上为火山引擎增长剖析专门深度定制优化的版本。本文介绍在字典编码方向上的优化实际，作者系字节跳动数据平台研发工程师 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 即可。
整个过程能够分为两个过程：
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 亿左右：
能够看出在基数 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 亿条记录的统计：
从表中能够看出，Fall back 后的列根本跟原始列性能靠近，至多保障 Merge 和存储性能没有进化。如果不做 Fall back，存储空间占用会比原始列还要多，Merge 性能无奈撑持实时写入。
通过 Merge 优化和主动 Fall back 解决了 LowCardinality 列的两大绊脚石，接下来看下咱们在外部一些大利用上的测试验证成果。
性能验证
上面是在外部某些大 APP 上的验证后果。
1、磁盘占用
数据表是外部某些 APP 某个时间段的数据。
从上表中能够看出，列越多，数据量越大，存储空间降落就会越显著，最高能够节俭一半的数据存储空间。在数据量十分的大 APP 场景下，上线 LowCardinality 后能够节俭大量的存储资源。
2、针对某个 APP，获取其典型的 10 个业务 SQL，做查问性能测试。
上面是两个数据表别离查问的比照测试后果：
从上图能够看出，有两个 SQL 导致查问性能有回退景象，其余 SQL 都是 LowCardinality 的表查问性能更优，耗时更短。
3、10 个查问对应的磁盘数据读取量：
能够看出，基本上所有 SQL 读取的数据量都有显著的缩小，对磁盘 IO 的压力会升高很多。SQL8 对应的查问列曾经做了 Fall back，所以跟原始列读取数据量持平。
下图是查问时对应的内存使用量：
其中除了 SQL8 产生了 Fall back 外，其余查问均是 LowCardinlity 表内存使用量较大。因为 LowCardinality 列计算过程中，如 filter，须要读取的 Part 字典并将列反解进去，每个 Part 的字典是独立存在的，这样在计算过程中会多占用些内存。这块也是后续优化的重点。
小结
目前 ClickHouse UBA 版曾经全面启用了字典编码列，并且在火山引擎增长剖析（DataFinder）服务的多个客户环境中曾经上线。
从实际反馈看，咱们为客户节俭了大量存储资源，同时在大多数场景下查问性能也有晋升显著。总体上因为字典位于每个 Part 中独立存储，查问过程中无奈做到在压缩域间接计算，因此会造成个别场景下查问性能不佳，并且内存使用量上会减少。
下一步工作的重点将是优化 LowCardinality 的计算过程，例如把字典做成 Part 间共享的，能够缩小计算过程中内存占用，进一步扩大简单场景在能够间接在压缩域做计算。
参考文献
https://github.com/yandex/cli…
https://clickhouse.com/docs/e…
火山引擎增长剖析
一站式用户剖析与经营平台，为企业提供数字化消费者行为剖析洞见，优化数字化触点、用户体验，撑持精细化用户经营，发现业务的要害增长点，晋升企业效益。
欢送关注同名公众号「字节跳动数据平台」