Lecture1: 概述
分布式系统工程
什么是分布式系统？
- 多个共同处理任务的计算机
- 大型网站的存储、MapReduce,P2P共享网络等
- 很多重要的基础设施都是分布式的
为什么需要分布式系统
- 物理上使用单独1的实体来组织
- 通过隔离来确保安全
- 通过重复来容忍错误
- 通过并行CPU、内存、次盘、网络来使得产量倍增
缺点
- 复杂:很多并行的部分
- 必须处理局部错误
- 实现理论上的性能潜力是非常tricky的
为什么上这门课
- 有趣-挑战性的问题，很棒的解决方案
- 应用在现实系统中，分布式系统就是被大型网站兴起所驱动发展的
- 活跃的研究领域-很多进步和很多未能解决的问题
- 训练动手能力-你将要在实验中构建严格的系统
主旨
- 这是一门关于基础架构的课程，但是被很多应用所使用，有关隐藏在分布式应用背后的抽象
- 三种抽象
- 存储
- 通信
- 计算
- 三层架构
- 用户
- app服务
- 存储服务
很多方法都来源与冗余
主题：实现
- RPC
- 线程
- 并行控制
主题：性能
- 理想结果：水平扩展
- 我需要更多的服务器，来得到更多的cpu,硬盘，内存，网络，因此处理负载问题只需要买更多的机器
- 问题：随着规模增长，保持线性效果变得更难
- 各个单机负载不均衡
- 无法并行的代码：初始代码，相互影响的代码
- 共享资源成为瓶颈：网络
- 很多性能问题无法通过增加机器来解决
- 如单个用户请求的延迟
- 这需要更多的程序员优秀的代码而不是更多的计算机
主题：容错
- 1000多台服务器，复杂的网络，他的部分总是会发生故障，我们想要隐藏这些应用内部的故障
- 我们需要
- 高可用：尽管发生故障也能运行
- 耐用：app错误修复后能够重新运行
- 解决方法
- 冗余服务器
- 如果一个服务挂了，客户可以使用其他服务器运行他们
主题：一致性
- 通用目的的基础架构需要定义良好的行为
- 例如get(k)生成最近的put(k,v)放进去的值
- 得到良好行为是很困难的
- 冗余的服务器是很难保证一致性的
- 客户可能在多步骤更新的时候崩溃了
- 服务器肯呢个在一个尴尬的时候崩溃了，比如在执行但是复制以前
- 网络使得活着的服务器看着像挂了，脑分裂问题
- 一致性是性能的敌人
- 一致性需要通信，例如取得最新的put()操作
- 强一致性的系统是效率地下的
- 好性能通常通过弱的一致性实现
- 在这一维度，有很多想法提出
案例研究：mapreduce
让我们聊聊MR,它是课程一个重要的主题，也是lab1的主题
概述
内容
- 在很多t数据集上的很多小时的计算
- 例子：网络爬虫图结构的分析
- 使用了1000多电脑
- 通常不是由分布式系统专家所发展
- 分布式可能是痛苦的，如：错误的处理
- 总体目标：
- 不需要特殊的程序员就能切分数据到几个服务器上处理，并且有可观的效率表现
- 程序员定义Map和Reduce函数，序列化的代码，一般是很简单的
- MR将代码运行在1000个服务器上，拥有大量的输入但是却隐藏了分布式的细节
MR的抽象
- 输入被拆分为M个文件
- map生成k-v对，reduce来处理计算
Input1 -> Map -> a,1 b,1 c,1Input2 -> Map -> b,1Input3 -> Map -> a,1 c,1| | || | -> Reduce -> c,2| -----> Reduce -> b,2---------> Reduce -> a,2
MR调用Map()函数给每个Input文件，产生k2,v2键值对的实时数据
每个Map()调用是一个任务
MR 产生所有给定k2的实时结果，并且将结果传入到reduce 调用，最终的结果<k3,v3>从reduce产生，存储在输出文件中
流程：
MapReduce API --map(k1, v1) -> list(k2, v2)reduce(k2, list(v2) -> list(k2, v3)
例子：单词统计
输入是文本文件
map(k,v)，将文件且分，每个文件得到一个map(k,v)，汇总reduce，得到整个文件的map(k,v)
mapreduce隐藏了很多痛苦的细节
- 起初存储/读取在服务器上
- 追踪哪个任务完成了
- 数据移动
- 错误恢复
MapReduce扩展性很好
- N个机器得到了N倍提升
- 假设M R是大于等于N的
- map可以并行处理i，因为他们互补干扰
- reduce也可以
- 唯一需要影响不能并行的操作是map 和reduce之间的shuffle
- 你可以通过购买电脑得到更好的算力，而不是给每个应用特殊目的的有效的并行加速
- 计算机比程序员便宜
什么导致了性能的限制呢？
- 我们关心可以优化的部分cpu 网络 磁盘 内存
- 2004年，作者的主要限制是跨域的网络带宽
- 因为所有shuffle操作依赖网络
- 当时的核心交换机 100-200 g/s
- 1800机器，因此55g/s
- 这个效率低于内存和磁盘的利用速度
- 因此他们关心的是优化数据移动操作
- 如今数据中心的网络更快了
更多细节
- 主：给工作者任务，记住及时输出在那
- M Map任务 R reduce任务
- 输出存储在GFS上，每个map input文件复制三次
- 所有的计算机运行GFS和MR任务
- 输入任务比worker更多
- master给每个worker一个map任务
- map任务将他们的keyhash到r 分快，在本地硬盘
- 问题：有什么好的数据结构来完成这个任务
- 在map完成前不要进行reduce调用
- master告诉reducers 从 map worker处得到实时数据
- reduce worker写入最后的输出到gfs
MR对于慢的网络有什么设计细节
- map input 读GFS分片在本地硬盘，而不是网络
- 相互影响的数据只用网络传输一次
- map worker写入局部硬盘，而不是GFS
- 实时数据将分割进拥有很多key的文件中
如何做到负载均衡？
- 对于水平扩展至关重要。出现很多服务器等待一个慢服务器的情况
- 但是很多任务u就是比其他的长
- 解决：tasks比worker更多
- master将新任务给那些完成之前任务的worker
- 不要有太大的以至于影响整个大的任务的任务
- 这样更好的服务器做更多的工作，确保异构的分布式结构也能做到负载均衡
如何做到容错
- 例如，其中的节点执行mr时候崩溃了怎么办
- 容错是程序编写的最重要的部分
- mr 运行 只允许map和reduce失败
- MR需要他们是一个纯函数，不能产生很多的副作用
- MR 不能保持calls的状态
- 他们不能读写文件除了 mr需要的input/output
- 他们没有潜在的任务之间的通信
- 这些就是为了保证m r再次执行得到的是和上一次一样的结果
- 这也就是mr区别于其他并行编程范式的根本原因
- 他对于mr的简洁也是重要的
错误回复的细节
- map worker 崩溃
- master 发现worker不再对ping响应
- 崩溃的worker的map实时结果也就丢失了
- 但是这个结果肯呢个是每个reduce任务所需要的
- master 再次启动并加速这个任务在其他GFS分片上
- 一些reduce可能已经读到了错误的worker的运算结果
- 这里我们基于函数式的不可逆转的map
- master不需要重新运行map如果reduce已经取得了所有的交互数据
- reduce崩溃也会导致强制重新执行map操作
- reduce worker崩溃
- 已经处理的数据是ok的，已经存在了GFS中，GFS可以保证存有备份
- master让其他worke完成没有做的任务
- reduce woker在写入output中间崩溃
- GFS 已经原子的命名了以前的结果，因此master再运行一次mr任务也是安全的
其他失败问题
- master已经给两个worker同样的map任务？可能master错误的认为其中一个已经死了
- 他只会让reduce worker得到其中一个的数据
- master已经给两个worker同样的reduce任务？
- 他们会都给GFS写入同样的数据
- GFS的原子命名会修正他，只有一个重复的数据保留
- 如果单个worker非常慢怎么办，落伍者
- 可能因为硬件故障
- master会再开一个任务的副本执行
- 如果一个worker得到错误的结果，由于错误的h/w s/w，
- 无法解决，mr假设cpu和software错误会停止
- 如果master crash怎么办
- 从check-out恢复，或者放弃任务
那些任务mr不能表现良好？
- 不是每个任务适合map shuffle reduce模式
- 小数据，overhead是过高的，例如网站后端
- 大数据的小更新，例如给一些文档增加一个索引
- 不可预测的读(map reduce都无法选择input)
- 多次shuffles 如page-rank(能使用多次mr实现，但是i效率差)
- 更灵活的系统是可以的，但是更复杂的模型是不可以的
一个真实的网站公司会怎样使用MR?
- catbook 一个为cat社交的一个社交网络，需要
- 购买一个搜索引擎，使得人们可以找到cat
- 分析不同猫的受欢迎程度来决定广告价值
- 找到狗并把他们剔除出去
MR都能完成这三个任务
-
构建倒序索引
-
index: map(profile text) -> (word, cat_id)reduce(word, list(cat_id) -> list(word, list(cat_id)) -
计算访问数
-
map(web logs) -> (cat_id, "1")reduce(cat_id, list("1")) -> list(cat_id, count) -
过滤文件
map(profile image) -> img analysis -> (cat_id, "dog!")reduce(cat_id, list("dog!")) -> list(cat_id)
结论
- MR 实现了分布式计算
- 不是最有效最灵活的
- 水平扩展性好
- 编程容易-隐藏了其中的分布式细节，实践的好的权衡
- 在后续会找到他更优秀的继承者