【技术贴】揭秘Apache Kylin V2.0新特性：字典编码模块的优化

为了支持高效的OLAP查询，Apache Kylin实现了多种高效的数据压缩和编码方式，其中包括位图编码、定长编码、字典编码等。本文主要是介绍Apache Kylin V2.0的字典编码的相关实现，以及对字典编码模块的一些优化。——谢凡

Apache Kylin V2.0即将发布，新版本将使得Apache Kylin功能更完善，不仅支持雪花模型，还拥有更加全面的SQL语法、实时流式数据接入等等，相信大家也都迫不及待想要使用新版本。
如您有更多问题，可以直接联系谢凡。
谢凡github地址：https://github.com/xiefan46

字典编码的实现

Apache Kylin的字典编码模块主要是通过Trie树（字典树）的方式来实现。使用这种编码的维度，每个segment在构建的时候都会为这个维度所有可能的值创建一个字典，然后使用字典中每个值的编号来编码。使用字典编码的好处是字典编码产生的编码非常紧凑，尤其是在维度值的基数较小且长度较大的情况下十分节约空间。当然，如果维度基数过大，采用字典编码也十分容易造成内存溢出。采用字典编码的方式来压缩数据的方式并非是Apache Kylin首创，而是一种在搜索引擎中的常用技术，Apache Kylin的代码实现中大量借鉴了搜索引擎中的许多技术，从而实现高效的OLAP查询。如果您想详细了解Trie树相关知识，可以参考如下的资料：https://zh.wikipedia.org/wiki/Trie

Apache Kylin对字典编码模块的特殊优化

之前在介绍Trie字典编码的时候我们提到，Trie树在处理超高基数维度时很容易遇到内存溢出的问题。因此我们一般来说建议用户不要将超高基数的维度的列加入到构建Cube时候的维度定义中，但是在实际使用Kylin的过程中，用户却常常因为各种各样的原因（对Cube构建原理不了解、希望查明细数据等）而把超高基数的维度（用户ID,手机号码等）加入到维度的定义中。如果这一列用的还是字典编码，则在构建过程中会占用大量的内存，因此用户会发现在构建字典的一步报出内存不足的错误。在使用比较旧版本的Kylin时，如果遇到此类问题，我们往往建议用户通过去掉超高基数维度列或者用分段构建等方式来解决。不过较新版本的Kylin对字典编码的相关模块进行了优化，可用性得到了比较大的提升。一些主要的优化如下：

2.1 将对象形态的Trie树压缩为更紧凑的数组形态

在对一个维度的所有值构建字典的过程中，程序会在内存中维护一个对象形态的Trie树结构，并且将一列中的值逐个加入到这颗Trie树中，在所有值都被加入到Trie树中以后，Kylin会再次扫描整颗Trie树，搜集统计信息，并且利用这些统计信息将对象形态的Trie树压缩为更为紧凑和节约空间的数组形态。在查询的过程中，Kylin会直接在数组形态的Trie树上进行查询。使用数组形态的Trie树而不是对象形态的Trie树的最大好处就是前者的内存占用相比于后者大大降低，仅为后者的约五分之一到十分之一。当然，数组形态的Trie树也有一些缺点，比如一旦构建完成就无法再插入新的值等。不过，由于Kylin适用的场景往往都是一次预处理然后反复进行查询的OLAP场景，因此这一缺点是可以忍受的。

2.2 采用分段压缩的方式减少峰值内存占用

通过分析Kylin的字典构建过程可以看到，Kylin的字典构建过程中的内存占用情况会呈现出一个“山峰”形状。在所有值被逐个加入到对象形态Trie树中时，内存占用会逐渐上升。随后，随着对象形态Trie树被压缩为数组，内存用量又会骤然下降。在实际使用过程中，当超高基数维度的字典处于构建过程中的内存占用峰值的位置时，很可能会遇到内存不够的问题。因此，优化内存占用的一个思路就是想办法把这一山峰“削平”。新版的字典TrieDictionaryForest就是根据这一思路实现的：其基本思路是利用输入值有序的特点（在构建字典前，一列中的值会被ＭapReduce排序），将一个大的Trie树切分为多棵小的Trie树，并且各棵树之间是保持相对有序的。这样，在字典构建的过程中，不用等到所有值都被加入到字典中以后才对字典进行压缩，而是能逐段地压缩字典，这样，构建过程中的峰值内存占用就被“削平”了。在查询的过程中，程序只需要进行二次的定位，定位到子Trie树，再进行查找，便能实现和旧Trie数一样的效果。优化前后的内存变化对比如下图：

2.3 支持超过2G的字典

旧版的字典无法支持超过2G的数据，原因是定义Java数组长度时用的是int类型所致。新版的字典由于每棵子Trie树都可以拥有一个数组，因此整个字典不会遇到最大大小限制的问题。如果内存足够，用户可以对任意大小的列构建字典。

2.4 多Reducer并行构建字典

字典构建过程由Reducer在本地构建完成：优化前Kylin的字典构建过程是统一交给Kylin的Job Node完成的，这样的实现很容易遇到单点的问题。而优化后，字典的构建会被分散到各个Reducer中，各个Reducer会各自将自己负责的字典构建完成，然后将构建完成后的字典序列化以后写到HDFS中。Job　Node需要做的仅仅是把这些字典读出来，优化后，Job Node的负担被大幅度降低了。同时，多个Reduce可以做到对不同的列并行地构建字典，字典的构建速度能得到很大的提升。另外，由于Reducer仅仅需要将构建完成后的字典写入到HDFS中，而不是像以前一样将一列中的所有值写入到HDFS中，因此磁盘IO也会有很大的优化。