分布式系统
-
分布式系统是什么?
-
多台协作的计算机
-
存储大型网站,MapReduce,p2p 共享网络等很多关键的基础设施是分布式的
-
-
建设分布式系统的原因
-
通过并行增加容量
-
通过复制实现错误容忍(容错)
-
使计算在物理上靠近外部实体
-
通过隔离实现安全
-
-
但是很多并发部分,复杂的交互,必须处理局部错误,难以实现性能潜力
-
很多性能问题并不能简单通过扩展实现
快速响应单一用户请求
所有用户想更新相同的数据
这些通常需要更好的设计而不仅仅是更多的服务器
-
MapReduce
MapReduce 任务抽象
[图 mapreduce.png
MapReduce 过程
input is (already) split into M files
Input1 -> Map -> a,1 b,1
Input2 -> Map -> b,1
Input3 -> Map -> a,1 c,1
| | |
| | -> Reduce -> c,1
| -----> Reduce -> b,2
---------> Reduce -> a,2
MR calls Map() for each input file, produces set of k2,v2
"intermediate" data
each Map() call is a "task"
MR gathers all intermediate v2's for a given k2,
and passes each key + values to a Reduce call
final output is set of <k2,v3> pairs from Reduce()s
Example: word count
input is thousands of text files
Map(k, v)
split v into words
for each word w
emit(w, "1")
Reduce(k, v)
emit(len(v))
MapReduce scales well:
N "worker" computers get you Nx throughput.
Maps()s can run in parallel, since they don't interact.
Same for Reduce()s.
So you can get more throughput by buying more computers.</pre>
MapReduce 隐藏了很多细节:
-
发送应用代码到服务器
-
追踪哪个任务已经完成
-
将数据从 Map 移动到 Reduce
-
在服务器之间进行平衡加载调整
-
恢复失败任务
MapReduce 限制了应用能做的
-
没有交互或者状态(除了通过中间输出)
-
没有迭代,没有多阶段管道
-
没有做到实时数据或者流数据处理
输入和输出存储在 GFS 集群文件系统中,MR 需要巨大的并行输入和输出吞吐量
-
GFS 需要把大型文件分割到多个服务器上,分成 64 MB 的文件块
-
Map 并行读取
-
Reduce 并行写入
-
GFS 也把每个文件复制到2-3个服务器上,GFS 对 MapReduce 来说是巨大的胜利
限制性能的是什么?
CPU ? 内存 ? 硬盘 ? 网络带宽 ?
在 2004 年他们认为是被网络带宽限制
对于排序来说,Map 从 GFS 读取文件,Reduce 读取 Map 的输出可能和 输入一样大,Reduce 再把文件写入 GFS
在 MR 的 all -to -all shuffle过程中,一半以上的流量通过根交换机
论文中的根交换机:100-200 GB/s,一共1800台服务器,也就是 55MB/s,55 Mb 很小,远低于磁盘或内存速度
今天,网络和根交换机相对于CPU /磁盘快得多
论文中图 1 的详情
一个主节点,将任务分配给 worker 节点并且记住任务进度
-
主节点分给 worker节点 Map 任务直到所有的 Map 任务完成,Map 节点把输出(中间结果数据)到本地磁盘上,Map 分割输出,通过 hash分成每一个 Reduce 任务
-
等所有 Map 完成后,主节点分发 Reduce 任务
每一个 Reduce 从 Map worker 节点拉取 中间输出数据到 Reduce节点
每个 Reduce 任务写入一个单独的输出文件到 GFS上
MR 如何 减小网络带宽使用
-
Master节点尝试在GFS上面运行它的每个Map任务存储它的输入
-
所有的计算机都运行 GFS 和 MR worker
-
输入从本地磁盘读取而不是通过网络
-
-
中间结果数据只在网络中传输一次
-
Map 节点写入本地磁盘
-
Reduce worker节点直接从Map 节点读取,而不是通过磁盘
-
中间结果数据拆分为包含很多 key 的文件
-
Reduce 远小于 key 的数量
-
大的网络带宽会更有效
MR 如何获取良好的负载均衡
如果 N -1 个服务器必须等待 1个比较慢的服务器完成任务是比较浪费的,但是一些任务耗时肯呢个远大于其他的
解决方法: 任务数比worker节点数要更多
-
Master 节点 将新任务分发给完成之前任务的节点
-
因此,希望没有一项任务会大到它可以主导完成时间
-
因此,速度较快的服务器要比速度较慢的服务器执行更多任务,并同时完成。
容错是什么
worker 节点在执行 MR 任务时候崩溃怎么办?
我们想要完全的向应用开发程序员隐藏错误,MR 需要重新运行整个任务吗,为何?
MR 只需要运行 失败的 Map 和 Reduce 任务
假设 MR 运行两次 Map,一个 Reduce 会看到第一次的 Map 输出结果,
另一个 Reduce 会看到第二次的运行结果
正确性要求重新执行才能产生完全相同的输出,因此 Map 和 Reduce 必须是纯粹的确定性函数,他们只被允许看到他们的参数,没有状态,没有文件 I/O,没有交互,没有额外的通信。
如果 想要允许非函数性的 Map 和 Reduce 怎么办
worker 节点失败需要整个任务重新执行,或者你需要创建全局的同步检查点
worker 节点崩溃恢复详情
-
Map worker节点崩溃
-
master 节点注意到 worker节点不再响应 ping
-
master 知道 哪一个 worker 节点上运行的 Map 任务
-
那些中间结果数据现在已经丢失,必须重新创建
-
master 告诉其他节点来运行那些失败的任务
-
如果 Reduce 已经获取到中间结果数据的话,可以忽略重新运行
-
-
Reduce 节点崩溃
-
任务完成就可以,存储在GFS中,同时有多个副本
-
master 在其他worker 节点上重启那些 worker 节点没有完成的任务
-
-
其他失败问题
-
如果 master 给两个 worker 节点相同的 Map() 任务怎么办
-
可能 master 错误的认为 一个 worker已经 死掉了,它会告诉 Reduce 节点只有一个 Map 任务
-
如果 master 给两个 worker 节点相同的 Reduce() 任务怎么办
- 他们都会尝试写入输出文件到 GFS。GFS 原子命名可防止混淆,一个完成的文件将会可见
-
如果一个 worker 节点非常慢怎么办 ?
-
可能是由于不可靠的硬件设备
-
master 启动最近几项任务的副本
-
-
woker 节点因为某种原因,计算出不正确的输出,MR 会认为停止故障的 CPU和软件
-
master 节点宕机怎么办
-
-
当前状态
-
影响巨大 (hadoop, spark)
-
可能在 Google 已经不再使用
-
被 Flume / FlumeJava 所替代 (see paper by Chambers et al)
-
GFS 被 Colossus 和 BigTable 替代
总结
MapReduce 使得大集群计算变得流行
不是最高效的或者最稳定的
扩展性良好
编程简单,失败错误和数据移动被隐藏掉了
这些都是在实践中很好的权衡
-
网友评论