如何使用MapReduce解决序列排序问题，输出链式依赖结果

核心思路 #

你这个需求本质是构建节点后继关系的传递闭包，输出每个节点对应的完整后继链，我们可以根据数据规模选择两种实现方式：

• 小规模数据集：直接在Reducer端全量加载后继关系表，遍历拼接即可，实现最简单
• 大规模数据集：采用迭代式MapReduce任务，逐轮拼接延长链，直到没有更长的链生成

小规模场景实现步骤 #

Mapper 逻辑 #

保持你现有的逻辑不变，直接输出解析后的键值对即可，键是前驱节点，值是直接后继节点，示例：

map(key, line):
    pre, next_node = parse(line)
    emit(pre, next_node)

Reducer 逻辑 #

1. 先在Reducer的setup阶段把所有Mapper输出的键值对全部存入哈希表next_map，保存所有直接后继关系
2. 遍历next_map的每个前驱节点，迭代查询后继并拼接，直到没有下一级后继为止
3. 输出最终的<节点, 完整后继链>键值对
   伪代码示例：

reduce():
    next_map = {}
    # 先加载所有后继关系
    for pre, next_node in mapper_outputs:
        next_map[pre] = next_node
    # 遍历每个节点拼接链
    for start_node in next_map.keys():
        current = start_node
        chain = []
        while current in next_map:
            current = next_map[current]
            chain.append(current)
        emit(start_node, " -> ".join(chain))

大规模场景迭代式实现 #

如果数据量太大无法在Reducer内存放下全量next_map，就用多轮迭代的方式处理：

1. 第1轮Mapper输出两类值：原始的<节点, "direct:"+直接后继>，以及链初始值<节点, "chain:"+直接后继>
2. Reducer对同一个key的所有值分类：如果有direct后继，就把所有chain值末尾拼接上这个direct后继，输出新的<链首, 新chain>；如果没有direct后继，就把当前chain作为最终结果输出
3. 重复执行MapReduce任务，直到某一轮没有新的更长的chain生成，就结束迭代

内容的提问来源于stack exchange，提问作者Alex