[Day 26] Batch Processing (3-2) - MapReduce Map-Side Joins

续 Day 25

Map-Side Joins

昨天讲的 join 是在 reducer 端完成，所以也称为 reduce-side joins，这个 join 方法的优点就是你不用对输入资料做出任何假设，你只要知道关键资料就好了，而缺点就是所有的排序、复制到 reducer 和 reducer 合并所有输入的操作都是昂贵的，端看你分配的硬体资源有多少，资料可能在 MapReduce 的阶段中多次写入到硬碟里。

换个方向说，如果你能对输入资料做出某些假设，它是有可能让 join 变快速，称之为 map-side join，这个方法使用缩减的 MapReduce Job，意味者 map-side join 未使用 reducer 和排序，每一个 mapper 就只读取输入资料，然後输出，搞定！

Broadcast hash joins

执行 map-side join 的最简单方法适用於大量数据集 join 小量数据集，精确一点的说，小量数据集需要小到能在每个 mapper 的记忆体中存一份。

一样举昨天图 10-2 分析 user 活动事件的例子，将 user 的生日 join 到活动事件。

若 User 资料库小到能存进记忆体中，当 mapper 启动时，mapper 就能把 User 资料库存成 hash table，尔後 mapper 开始扫描 user 活动事件时，就能快速从 hash table 查找 user 的生日年份了。

这简单但有效的算法称之为 broadcast hash join，广播 (broadcast) 代表每个 mapper 皆有小量数据集，hash 代表使用 hash table；此 join 在 Pig (叫做 replicated join) 和 Hive (叫做 MapJoin) 皆有支援。

Partitioned hash joins

如果 map-site join 所有用到的输入资料都是用一样的方法做 分区 (parition) 的话，你就能更进一步的缩小载入记忆体中的数据集大小，一样用上图 10-2 的例子，你可以安排所有的活动事件和 user 资料库皆以 user ID 的个位数数字做分区，所以 mapper 3 就会载入所有 ID 尾数为 3 的资料，然後完成 join。

Partitioned hash joins 在 Hive 也被称为 bucketed map joins 。

Map-side merge joins

另一个 map-side join 的变体是，不只所有输入资料分区策略相同，还是以相同 key 排序过的资料。

在这个状况下，小量数据集能否存进记忆体就不重要了，因为 mapper 也能执行相同的合并操作（这通常由 reducer 完成），渐进的读取 join 2 边的资料，然後完成 join。

若 map-side merge join 可以作业，它的输入十之八九是由其他 MapReduce Job 的输出产生，虽然大多情况下会像昨天那样，由 reduce-side 搞定 join，然而，若该资料集可能会被其他的 join 用到，就很值得先做好分区 & 排好序，然後使用 map-side merge join 完成 join 作业。

Join 小结

在优化 join 策略时，不只是要知道编码或资料夹命名为何，更重要的是要了解分散式档案系统里相关数据集的物理布局，知道档案怎麽储存，用什麽 key 当做分区策略等等。

了解这些过後，才能帮助你选择一个适合的 join 策略。