【遇见 Doris】Doris 基于 Hive 表的全局字典设计与实现

感谢 7 月 25 日来参加 Doris 与 Dolphin Scheduler 合作举办的线上 Meetup 的小伙伴们，现在为大家带来 Meetup 的内容。

本次 Meetup 请到了来自百度、奇安信、美团点评和易观的技术大牛带来技术分享。了解更多详情请关注 Doris 官方公众号。嘉宾分享回顾会陆续放出，公众号后台回复“0725”立即 get 回放录像及嘉宾 PPT。

本次为大家带来的是第二期内容回顾：《Doris 基于 Hive 表的全局字典设计与实现》，第一期在这儿。

本期主讲人： 

王博

  美团点评

  数据开发工程师

为什么需要全局字典

什么是全局字典

全局字典的技术实现

总结与未来规划 

为什么需要全局字典

我们在业务上需要 OLAP 引擎能够⽀持精确去重的预计算，但这个需求本身是不是合理的呢？

目前线上数据分析会有一些与⾦钱相关的计算，比如某一个业务方要计算他们个人的销售业绩、以及一些广告的点击率等，这些能够转化为金钱的计算需求是要求精确去重的，近似去重是⽐较难以容忍的。

目前 Doris 的 BITMAP 列已经⽀持了对于整型的精确去重计算，但是现实的场景是业务会有更多的数据类型需要精确去重，比如 String，这些非整型的数据类型是无法直接存入 BITMAP 的。

什么是全局字典

那么基于以上的问题我们需要引入一个新的数据结构——全局字典，其实就是一个比较大的 MAP。

MAP 的 KEY 列保存了原始值，VALUE 列保存了编码后的整型值。这样的话，即使我们有一个字段是 String 类型的，如果能将 String 字段值转成一个整型值，再把原始值的 String 类型的值和转换后的整型值都存入这个 MAP，那么在导入数据时就可以读取这个 MAP，先将原始值替换为整型值，再将整型值导入到 Doris 的 BITMAP 列中，最终实现对 String 类型的精确去重查询。

其实就是设计一个中间的映射数据结构去实现对原始值的转化，再把转化后的值存入 Doris，这样就能实现对任意数据类型进行精确去重。

2. 全局字典的构建与使用流程

当然，只有一个 MAP 的数据结构是不够的，它需要一个完整的使用流程。

简单来说，首先是更新，这个更新就是对全局字典数据结构进行更新。第二步是读取，在编码的阶段，也就是已经有了字典之后，需要读这个字典的数据，然后根据映射把原始值转成编码值，核心的步骤就是一个构建和编码的流程。这两个流程是比较容易形成性能瓶颈点的，这里后面会具体说到。

3. 业界目前主要有两种全局字典的实现

第一个是基于 Trie 树的全局字典，第二种是基于 Hive 表的全局字典。今天我们主要讲的就是基于 Hive 表的全局字典。

全局字典的技术实现

1. 基于 Trie 树的全局字典

这个方案主要是 Kylin 引擎支持，在美团内部有大规模的落地经验，大部分业务都用的这套方案。这套方案在内部使用的优点缺点也是很明确的了。

（1）Trie 树的基本设计

Trie 树就是基于前缀匹配的树。每次插入的时候都会进行一次前缀的匹配，如果前缀能匹配上，多出来的部分会做一个大小的比较。如果新插入的值大于已经存在的值，就插入到右侧，否则插入到左侧，会做一个排序和比较的过程。如果前缀都不匹配的话，会生成一个新的节点。

根据 Trie 树的特性我们可以得出一个结论——Trie 结构在数据写入的时候就已经完成了去重和排序的工作（其实我们主要利用它去重的特点）。在读取数据时，数据在 Trie 树中的位置就是对应的编码值。也就是说，当数据写入完成时就达到了我们的预期——去重以及对数据的编码。

（2）对 Trie 树进行分片

在实际的线上环境中有一个 Trie 树是不够的，因为通常 Trie 树非常大，小的可能几十 MB 上百 MB，大的几十 GB 上百 GB 都有，所以一定要做树的分裂操作。

一个树经过分裂会分成多个分片，这样做的好处是不用一次把数据全加载到内存中，可以通过对分片文件进行缓存从而提高访问效率。但是目前的方案容易在缓存中出现一个性能的瓶颈。具体实现时，一个子树就是一个分片，每一个分片都是位于 HDFS 的一个文件。

（3）Trie 树总结与分析

优点是资源比较节约，写入一个树的过程目前是一个单节点的构建，而编码阶段只需要做一次 MAPREDUCE 操作就可以完成字典的读取和对原始值的编码，相对来说资源比较节约而且在大部分场景下性能表现良好。

但是我们经过内部使用，也发现了一些局限性。

主要问题是在缓存上，上面提到了要对 Trie 树进行分片，但是在两种情况下分片缓存的命中率会下降：

• 字典非常大。我们有些业务去重字段基数很高，所以字典很大，达到几十 GB 上百 GB 的情况，分片会非常非常多。虽然字典是排过序的，但是输入的数据可能是比较离散的。比如你有 10 个分片，输入 10 行数据，你要对这 10 行数据做一个编码，最差的情况是你要访问 10 次 HDFS，比较好的情况是 10 行数据可以在一个分片中查到，生产环境中不能对用户的输入值做出最优的假设，事实上当字典基数很高时，最差的情况往往容易发生。

• 有多列高基数去重列。比如当你对一张表进行编码的时候，因为单节点的内存是有限的，每列都需要加载不同的字典，会导致字典不停地读入读出，因为内存不足最终也会导致缓存的命中率下降。这种下降带来的影响是字典整体的构建流程耗时变长。

第二个局限性是目前字典是单个 Reducer 构建的，写入 HDFS 时一半数据位于本节点，一半数据分散在其他节点。而在我们使用过程中观察到 HDFS 不会把网络带宽作为一个查询路由，你的查询有可能打在单个节点上从而把 HDFS 的单节点网络带宽打满。此外，单节点的构建效率也比较低。

2. 基于 Hive 表的全局字典

基于 SparkSQL+Hive 表构建字典这套方案的优点是可以解决 Trie 树的瓶颈场景。

这套方案其实非常简单，它只需要三张表，第一张表是字典表也就是 MAP，KEY 列保存了去重列的原始值，VALUE 列保存了去重字段编码后的值，该列为整型。第二张表是用户输入表，就是用户那张原始的 Hive 表。还有一张是去重表，保存了每次输入的值去重后的集合。

（1）构建流程：抽取去重值

如上图所示，右上是一个原始表，保存了两列数据，我们期望对这张表进行的操作是，把 name 列替换成一个编码后的列。第一步是要把去重值抽出来，用 insert 和 group by 写一个 SQL，将需要去重的值保存到一张 grpby_table。

（2）构建流程：构建全局字典

第二步要做一个全局字典的构建，这步其实就是写入字典的过程。

看右侧，我们期望的结果是对上面这个需要去重的值的 grpby_table 的 name 列生成一个对应的 VALUE，也就是进行编码。

步骤 #1 是获取本次导入的新增的去重值，用去重值表 left join 字典表，通过 where 条件可以把新增的值抽出来，因为我们只需要对每次新增的去重值做一个编码。

步骤 #2 是使用 row_number 函数对新增的去重值做一个编码，现在我们已经拿到了这样一个集合。

步骤 #3 是和字典表做一个 union，将增量值和历史值合在一起，结果就是右侧下方的表。

（3）构建流程：对原始值进行编码

有了字典之后我们就可以进行编码操作了，这个编码是对原始值做编码。

右上方左边的表是原始表（Hive 表），右边是我们对 name 列编码后的字典，这样我们只需要用原始表的 name 列和字典表的 dict_key（name）列做一个 join 就能得到右下所示的表。这就完成了对原始表进行编码的操作。

这里要关注一个问题，当去重列数据倾斜时容易出现性能瓶颈（后文会具体说明解决方案）。

（4）性能瓶颈分析：字典构建阶段

因为我们目前使用 SparkSQL 的窗口函数（row_number）对去重值做解码，此函数的瓶颈在于它是单机执行的，而非分布式的。可用内存有限，单次输入亿级别的行数时容易内存溢出。

这个问题是比较容易解决的：每次拿到去重值之后先进行一个统计计算，如果行数超过一亿行就做一个切分。

（5）性能瓶颈分析：编码阶段

第二个瓶颈相对来说不是很容易解决，当去重列发生数据倾斜的时候，要么跑不完要么耗时非常长。

第一种优化方法是使用 MAP JOIN，但 MAP JOIN 也是有性能上限的。

第二种优化方法是，如果倾斜列空值较多那么就只对非空值进行编码，先把原始值进行切分，把非空的抽出来之后就一定不会倾斜了。

还有一种非常极端的情况，如果数值特别大无法使用 MAP JOIN 而且倾斜的值不是空值的，那么就对原始表，维表和字典表都加一个随机的前缀（这个问题其实就转化为如何解决 Spark 数据倾斜的问题）。这种方法的弊端是，添加了随机前缀意味着原始值和字典值都进行了膨胀。

总结与未来规划

1. 两种方案对比分析

对比两种方案，有两个基本的维度：字典构建和对原始值进行编码。

在字典构建上，基于 Hive 的方案因为是使用 SparkSQL 和窗口函数实现的，这种方法并行度很高，性能会很好；而 Trie 树是基于单节点构建的，相对来说吞吐量会低一点，会慢一点。

在编码上，基于 Hive 的方法一次 Shuffle 完成一列的编码，如果有多列 Bitmap 列的话，就需要多次 Shuffle 这时资源开销会大一些；而 Trie 树是不需要 Shuffle 的。

基于 Hive 的方法相对有更大的弹性，除了极端的数据倾斜的情况，Hive 这个方案是几乎没有什么瓶颈，是很占优势的；但是 Trie 树的方案它的瓶颈不在资源上，这也是我们线上落地的时候比较重要的痛点，它会在特定情况在缓存上出现瓶颈，这点是加资源也无法解决的问题。

2. 美团为什么选择了基于 Hive 表的方案？

最终我们设计 Doris 的字典方案时选择了 Hive 表方案是因为考虑到：

（1） Hive 表方案除了个别数据倾斜情况下整个方案没有什么明显的瓶颈，未来可以考虑从 Spark 引擎层的角度解决极端的数据倾斜问题。

（2）Hive 表方案可以解决 Trie 树的短板问题。

（3） 这个方案实现起来比较简单可以很快落地。

（4） 弹性比较好，在资源足够的情况下可以达到非常高的吞吐，很高的并行度。

3. 未来规划

目前在美团内部，基于 Hive 表的方案已经成为 Hive2Doirs 流程的默认方案，已经跑了大概 2 个月了。未来计划需要有更多的业务接入，可能会面临更复杂的考验，我们也期待对这套方案做持续的改进。

未来优化的方向是：

（1）考虑从 Spark 的层面解决数据倾斜的问题，比如引入 SparkAQE 特性（当 Join 时发现单个节点处理数据量过大时，会把数据做一个分发，引入多个节点去处理倾斜的数据，这样就可能会解决数据倾斜的问题），未来如果引入这一特性，整套 SparkSQL+Hive 做字典的方案将会没有明显的瓶颈。

（2）使用 Trie 树与 Hive 表融合的方案，这个方向是一个很理想的设计，但是改造成本会非常高。在大部分情况下使用 Trie 树做字典的编码，在基数高字典大的情况下就把 Trie 树转成 Hive 表然后使用 Join 完成编码。不过这套方案的改造成本比较高，比如写入时 Trie 树支持分布式构建，读取时需要能转成 SparkRDD 再转成 Hive 表。

欢迎扫码关注：

Apache Doris(incubating)官方公众号

相关链接：

Apache Doris 官方网站：

http://doris.incubator.apache.org

Apache Doris Github：

https://github.com/apache/incubator-doris

Apache Doris 开发者邮件组：

dev@doris.apache.org