CSE_lecture26:GPUs and MapReduce

The distributed (and parallel) programming on a single device & MapReduce

from single device to a distributed computing

单芯片的性能增长已经非常有限，因此引入分布式计算，使用很多张卡。但分布式计算在编程时需要考虑更多情况，因此使用分布式计算框架，让算法工程师不用自行考虑分布式计算的细节问题

对于数据中心，为了统计网站访问量，需要记录巨大的log，现在的任务是找到其中最热的网页推荐给用户。对于单机系统，使用单线程的命令行指令即可找到；而对于海量的log entry只能使用分布式，使用RPC分区并将计算分发给多台设备。难点在于：怎么高效地传输海量数据，怎么在带宽受限时高效地回收RPC，怎么应对设备出错，以及根据设备状态合理实现分区平衡

因此要解决的问题有：

• 在节点间高效传数据
• 节点协调同步
• 容错
• 使用locality减少数据传输
• 充分利用资源，即平衡快慢设备

MapReduce: simplified data processing on large clusters

MapReduce是一种distributed batch processing system，使用函数式编程，其并行度很高：

Map(function, set of values)
Reduce(function, set of values)

Map将function作用于set的每个value，Reduce使用function将所有value结合在一起：

(map #'length' (() (a) (a b) (a b c))) -> (0 1 2 3)
(reduce #'+' (1 2 3 4 5)) -> 15

只要用户将操作分为Map和Reduce（其中Reduce可以使用Map后的数据），底层就可以优化前面提到的问题：

• 在节点间高效传数据：根据数据被用于Map还是Reduce来进行优化，如将Map放在GFS节点上，Reduce放在Map机房
• 节点协调同步：Reducer在Mapper后调度
• 容错：函数是无状态的，重做即可
• 使用locality减少数据传输：根据数据的位置，将Map和Reduce放在同一机器
• 充分利用资源，即平衡快慢设备：将慢机器上的Map任务分配给快机器即可，但Reduce对并行不友好

google的MapReduce进一步优化，Map的结果为kv对，此时Reduce根据key来进行分区，从而实现Reduce的并行

有了MapReduce后，用户只需要考虑算法即可

如对于word count，MapReduce可以这样设计：

Map (input) # a shard of file
for each word w in input
    EmitIntermediate (w, "1");

Reduce (String key, Iterator values)
    int result = 0;
    for each v in values
        result += ParseInt (v);
    emit (AsString (result));

MapReduce的执行流为：

• Map Worker:
  • Map: 数据分片为shard后调用Map函数，生成键值对
  • Partition: 调用分区函数，根据key将数据分配给不同的Reducer，实现负载均衡
• Reduce Worker:
  • Sort: 对键排序，从而将同一个键的值聚合在一起
  • Reduce: 对相同键对应的值进行聚合操作，得到最终结果

• step1: 对文件分片为shard，从而分配给不同的Map Reducer，在GFS场景下为64MB，适配chunk size，降低RPC通信次数，并保证并行度
• step2: 在集群上分配出一个master和多个workers，即remote fork
• step3: 将shard发送给Map Worker，并调用Map函数，生成的键值对暂存在内存中
• step4: 生成IF(intermediate files)，分为多个partition，这是根据分区函数划分的
• step5: Reducer Worker根据分区从Map Worker中获取数据。为了防止数据过多使Reducer Worker内存溢出，需要进行排序，只需要将同一个key的值都拿过来，不需要一次性拿走所有的key
• step6: Reducer Worker进行聚合并直接输出结果

MapReduce需要进行容错，不需要用户进行log标记（类似于transaction)，并提供GFS，其可以抽象成不会挂的文件系统：

• Worker failure: 类似于raft使用log将会导致性能很差，因此直接进行重做(re-execution)即可，因为Map和Reduce是无状态的，且不会被用户感知
• Master failure: 重做不是一个好的策略，因为时间开销过大。使用高的checkpoint记录中间状态即可
• bad records: 可能因为用户提供的Map或Reduce本身出错，当反复挂时，直接跳过

locality用于减少网络访问，需要将计算放在离存储更近的地方。而google的计算节点也是GFS chunkserver，而Reducer在Mapper的数据获取可以通过整形规划来进行优化

对于负载均衡，由于任务可以重做，因此采取first win即可