谈谈分布式计算中的join

Join操作是数据处理中必不可少的一部分,传统关系型数据库经历多年对高效率join的研究和技术沉淀,已经非常成熟。然而在分布式环境下,数据存在不同程度的异构并缺乏索引等机制,使得传统的join优化技术难以应用。更重要的join是一个全局操作,一台物理机器需要大量网络IO获取join计算需要的记录,而网络却正是分布式计算最为珍贵的资源。以上种种原因导致分布式join与传统关系型join有着较大的差别(当然这仅仅是目前的状况,分布式计算也在不断借鉴关系型数据库的经验)。

分布式计算中的join大部分基于MapReduce计算模型,根据join操作实现的阶段可以分为reduce join和map join两大类,其余都是在该基础上进行优化。

Reduce Join

Reduce join是更为通用和常见的join模式,相对地,计算效率会比较一般,毕竟泛化能力和效率总是鱼和熊掌的关系。

Reduce join的核心思想是通过shuffle将具有相同join key的记录拉取到同一个reducer,map端只通过partitioner起到一个分类的作用,其他计算都在reduce端完成。不同于一般的MapReduce只有一个输入数据集,reduce join以两个表作为输入。Map端需要分别将数据转换为(joinKey,record)的形式输出,为了在reduce端区分两个表的记录,最好可以在record中加入一个标识字段,这个字段可以在分类完成之后丢弃。

下面以连接tbl_user(user_id, user_name)和tbl_tel(user_id, tel)两个表为例:

Reduce Join

Reduce join的瓶颈在于需要shuffle传输所有的记录,在数据集很大的情况下这个消耗无疑是巨大的。

Map Join

Map join将join操作本地化,效率更高。但适用场景没有reduce join广,要满足两个条件:随机访问一个数据集,同时可以遍历另外一个数据集。

常见的案例是join一个大表和一个小表,可以直接将小表广播到所有map端,并以哈希表方式加载到内存。在map端即可完成所有的操作,所以是map-only作业,避免了shuffle阶段,大大提高了效率。

Map Join

使用Map Join要注意的一点衡量广播小表的代价是否值得。在标准情况下,一个map处理一个block的数据,通常是64M或128M。但是如果小表有1G那么大,为了处理64M或128M的数据加载1G额外数据,可能得不偿失。

HBase Map Join

为了随机访问小表,普通的map join的策略是广播小表并加载到map端内存,但在有时广播的成本太高,而且当两个表都是大表时普通map join就有心无力了。那么有没有别的方式呢?答案当然是有,比较好的方案就是将其中一个表存储到HBase中,HBase表的row key自然就是join key了。

HBase Map Join

这样相当于为map端提供了统一的随机访问服务,而不要每个map端单独建立一个哈希表。

Hive Bucket Map Join

当数据可以提前确定join key时,Hive的bucket map join就可以派上用场了。Join的难点就在于对应key的数据是散乱分布的,要从多个的节点获取,那么如果一开始存储的时候就将两个表的数据按join key分片进行存储,map端的key对应的数据只需要从其他某个或少量几个节点批量获取,效率不就高多了?

Hive基于这个想法,在建表的时候支持通过指定clustered by (col_name,xxx ) into number_buckets buckets 关键字进行哈希分区。当两个表的join key都是clustered by的字段时,就可以通过设置参数

hive.optimize.bucketmapjoin = true

来命令hive执行bucket map join了。

这种方式其实本质上和普通的map join是一样的,只不过Hive利用了元数据优化了数据的存储分布,使得每个map的数据都是属于同一个join key,并使得拉数据变为批量操作,减少了网络IO。

参考文献

1.NickDimiduck, Amandeep Khurana. HBase实战[M]. 谢磊, 译. 北京: 人民邮电出版社, 2013.
2.张俊林. 大数据日知录: 架构与算法[M]. 北京: 电子工业出版社, 2014.
3.Hive join详解, cnblogs.
4.Edward Capriolo, Dean Warmpler, Jason Ruberglen. Hive编程指南[M]. 曹坤, 译. 北京: 人民邮电出版社, 2013.

本文是原创文章,转载请注明:时间与精神的小屋 - 谈谈分布式计算中的join