写点什么

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

用户头像
ApacheDoris
关注
发布于: 2021 年 03 月 24 日

感谢 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 


发布于: 2021 年 03 月 24 日阅读数: 24
用户头像

ApacheDoris

关注

还未添加个人签名 2021.03.17 加入

Doris(原百度Palo https://cloud.baidu.com/product/palo.html )是一款基于大规模并行处理技术的分布式 SQL 数据仓库,由百度在2017年开源,2018年进入 Apache 孵化器

评论

发布
暂无评论
【遇见Doris】Doris基于Hive表的全局字典设计与实现