知识卡片
排序合并连接:把相关数据放在一起的核心思想
内容
批处理场景下的连接(如把用户活动日志和用户档案库按用户ID关联)不能像在线查询那样逐条对远程数据库发起随机请求——那样吞吐量会被网络往返时间拖死,还会让批处理变得非确定,因为远程数据被查询的那一刻可能已经变了。更好的做法是让连接两侧的数据集都进同一个分布式文件系统,各自用Mapper提取出连接键(如用户ID),框架按键分区并排序后,具有相同键的记录会天然落到同一个Reducer调用里彼此相邻,这种做法称为排序合并连接:Mapper负责把数据变成方便排序的形式,Reducer负责处理已排序数据(配合二次排序,可以让Reducer总是先看到某类记录再看到另一类,比如先看到用户档案再看到活动事件)。这套架构可以理解为”Mapper向Reducer发消息”:一个键值对里的键,起的作用就像消息该送去哪个地址,即使这个键只是任意字符串。这种设计的深层价值在于把”从正确机器上取到数据”这个网络通信层面的问题,和”取到数据后如何处理”这个应用逻辑彻底剥离开,使Reducer可以是单线程、低内存开销、不操心部分故障的简单代码。
参考来源
- 位置:《数据密集型应用系统设计》第十章《批处理》"示例:用户活动事件分析""排序合并连接""把相关数据放在一起"(源文件:_epub-src/ch10_split_001.html)
- 结论依据:原文说明为每条记录发起远程查询会因网络往返拖慢吞吐量并引入非确定性,给出让两侧数据都在分布式文件系统中经Mapper提取键、按键排序后在Reducer合并的排序合并连接方案,并将键的作用类比为消息地址,直接支撑本卡片结论。
- 原始内容:为待处理的每条记录发起随机访问的网络请求实在是太慢了……当一个Mapper发出一个键值对时,这个键的作用就像值应该传递到的目标地址……这种简单有效的算法被称为排序合并连接。