6.824-lecture-1

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,1
  Input2 -> Map ->     b,1
  Input3 -> 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 实现了分布式计算
• 不是最有效最灵活的
• 水平扩展性好
• 编程容易-隐藏了其中的分布式细节，实践的好的权衡
• 在后续会找到他更优秀的继承者