6.824 2016 第1课:介绍

6.824: 分布式系统工程

什么是分布式系统 ?

• 多台机器共同协作
• 如DNS域名解析, P2P文件分享, 大的数据库(big databases), MapReduce, &c
• 很多关键基础设施是分布式的!

为什么需要分布式 ?

• 为了连接物理上相互分离的实体
• 为了通过隔离(isolation)实现安全性
• 为了通过复制(replication)实现容错
• 为了使CPUs/mem/disk/net可以实现扩容

然而

• 复杂性: 多个并发的部分
• 必须处理部分失败的情况
• 难以实现的性能潜力

为什么选这门课?

• 兴趣 -- 难题, 非显而易见的解决方案(non-obvious solutions)
• 被实际系统使用 -- 被大网站的崛起而驱动大网站的崛起
• 活跃的研究领域 -- 快速进步的领域 和 有大量问题没有解决的领域
• 动手做 -- 你讲通过实现建立多个系统

课程结构

• http://pdos.csail.mit.edu/6.824

Course staff(课程工作人员):

• Robert Morris, lecturer
• Frans Kaashoek, lecturer
• Steven Allen, TA
• Stephanie Wang, TA
• Jon Gjengset, TA
• Daniel Ziegler, TA

课程组成:

• 课程
• 阅读
• 两个考试
• 实验
• 项目

课程涉及大的想法，阅读和实验

阅读: 研究论文作为案例研究

• 请课前阅读研究论文，否则你会觉得上课内容很无聊，而且你无法不费力地学会， 每篇论文都有为你准备的小问题，请务必给我们发送你阅读论文的时候存在的疑问， 晚上十点前给我们发送问题和答案。

• 实验目标

  • 深入理解一些重要的技术
  • 掌握分布式编程的经验
  • 第一个实验的时间安排是从周五起的一周时间

• 实验安排

  • Lab 1: MapReduce
  • Lab 2: replication for fault-tolerance
  • Lab 3: fault-tolerant key/value store

  • Lab 4: sharded key/value store

    最后的项目，我们将会分成2到3组完成，你可以设想一个项目，然后和我们一起将他搞明白，或者你也可以做我们默认指定的项目。 实验的成绩基于你通过了多少测试案例，我们会给你测验，然后你就可以知道自己是否很小心的完成，如果它通常通过,但有时失败了,它有可能会失败,当我们运行它。

• 实验代码审查 查看其它人的解决方案，发送反馈给我们，可能自己能学到其它方法。

主题

• 这是一门关于会被应用程序抵用的基础设施的课程，它会对应用程序隐藏分布式系统的复杂性而进行抽象，包括下面的三个抽象：

  • 存储(Storage)
  • 通讯(Communication)

  • 计算(Computation)

    两个主题将反复出现。

主题：实现(implementation)

• RPC, threads, concurrency control.

主题： 性能(performance)

• 理想：可伸缩的吞吐量。

    通过购买更多的机器处理更高的负载。
  

• 扩展变得越来越困难:

    负载均衡，straggler问题。
    "Small" non-parallelizable parts。
    隐藏共享资源等，还有网络问题。
  

主题：容错(fault tolerance)

• 上千的服务器，复杂的网络 ————> 总会有东西出错 我们需要对应用程序隐藏这些错误。 我们经常希望：

    可用性: 即使出错我也希望可以使用我们的文件。
    耐用性：当故障修复之后，我的数据可以恢复。
  

  重要理念:复制服务器。

    如果一个服务器故障了，客户们可以使用其他的服务器。
  

主题：一致性(consistency)

• 通用的基础设施需求定义良好的行为。 例如： Get(k) 获取到的值应该是最近的 Put(k,v)设置的。
• 实现良好的行为是很困难的!
  • 客户提交的并发操作。
  • 服务器崩溃在尴尬的时刻。
  • 网络可能会使存活的服务器看起来跟挂了一样;存在“脑裂的风险“
• 一致性和性能不能兼得
  • 一致性需要沟通,如获取最新的Put()。
  • 带有严格同步语义的系统往往是缓慢的。
  • 快速系统通常使应用程序应对复杂(“放松”)的行为。
  • People have pursued many design points in this spectrum.

案例学习： MapReduce

• 让我们将MR作为一个案例进行讨论。 MR是课程6.284主题的一个很好的例子，也是实验1的主要关注点。

• MapReduce概要

  • 背景: 几个小时处理完TB基本的数据集 例如：实验分析爬行网页的结构，通常不是由分布式系统开发的爱好者开发的这就会非常痛苦，如如何处理错误。
  • 总体目标: 非专业程序员可以轻松的在合理的效率下解决的巨大的数据处理问题。程序员定义Map函数和Reduce函数、顺序代码一般都比较简单。 MR在成千的机器上面运行处理大量的数据输入，隐藏全部分布式的细节。

• MapReduce的抽象试图 输入会被分配到不同的分片(splits) Input Map -> a,1 b,1 c,1 Input Map -> b,1 Input Map -> a,1 c,1

                |   |   |
                    |   -> Reduce -> c,2
                    -----> Reduce -> b,2
  

  MR调用在每个分片上调用Map()函数，产生中间数据集k2，v2，然后MR将会收集相同k2的值v2，然后将v2分别传输给Reduce函数， 最后的输出是数据集

• 例子: word count 输入时成千上万的文件文件

    Map(k, v)
        split v into words
        for each word w
            emit(w, "1")
        Reduce(k, v)
            emit(len(v))
  

• 这个模式很容易编程，隐藏了很多让人痛苦的细节

  • 并发: 顺序执行相同的结果
  • starting s/w on servers ???
  • 数据移动
  • 失败

• 这个模型容易扩展 Nx台计算机可以同时执行nx个Map函数和Reduce函数,Map函数不需要相互等待或者共享数据，完全可以并行的执行。 在一定程度上，你可以通过购买更多的计算机来获取更大的吞吐量。而不是每个应用程序专用的高效并行。电脑是比程序员更便宜!

• 哪些为成为现在性能的限制因素？

  • 我们关心的就是我们需要优化的。CPU?内存？硬盘？网络？他们一般将会被网络限制，网络的全内容量通常远小于主机网络链接速度。一般情况下 很难建立一个比单机快1000倍的网络，所以他们关心尽量减少运动的数据在网络上。

• 容错呢?

  比如：如果服务器在执行MR工作时崩溃怎么办？隐藏这个错误非常困难，为什么不重新执行这个工作呢？

  MR重新执行失败的Map函数和Reduce函数,他们是纯函数——他们不会改变数据输入、不会保持状态、不共享内存、不存在map和map，或者reduce和reduce之间的联系，

  所以重新执行也会产生相同的输出。纯函数的这个需求是MR相对于其他并行编程方案的主要限制，然后也是因为这个需求使得MR非常简单。

• 更多细节： master：给workers分配工作，记得中间输出的位置。 NaN. 输入分割，输入存储在GFS，每个分片拷贝三份，全部电脑运行GFS和MR workers，输入的分片远远多于worker的数量， NaN. master在每台机器上面执行Map任务，当原来的任务完成之后map会处理新的任务，worker将输出按key散列映射输出到R分区保存在本地磁盘上， NaN. 当全部没有Map执行的时候Reduce将会执行。master告诉Reducers去获取Map workers产生的中间数据分区，Reduce worker讲最终的结果 NaN. 输出到GFS。

• 有哪些详细的设计帮助提示网络性能？

  • Map的输入来自本地的硬盘而非网络。
  • 中间数据只在网络上面传输一次，保存本地硬盘，而不是GFS.
  • 中间数据通过key被划分到多个文件，”大网络传输“更加有效。

• 它们是怎么很好的处理负载均衡？

  • 扩展的关键 -- otherwise Nx servers -> no gain. ?? 不同的大小，不同的内容和不同的服务器硬件配置导致处理分片或者分区的时间不是一致的。 +　解决方案: 分片的数据要多余ｗorker. Master不断的讲分片分配给那些已经完成之前任务的worker的进行处理。所以没有分片是巨大的，分片的大小只 影响完成的时间，同时速度更快的服务器将会处理更多的工作， 最后一起完成。

• MR怎么应对worker崩溃？

  • Map Worker崩溃：
    • master重新执行，基于GFS的其他副本的数据输入传播任务，即使worker已经完成，因为master依然需要硬盘上的数据。 有些Reduce　workers也许在读取中间数据的时候就已经失败，我们依赖于功能和确定性的Map函数。
  • ｍaster怎么知道work崩溃？(pings)
  • 如果Reduces已经获取全部的中间数据，那么master不需要重启Map函数；如果Reduce崩溃那么必须等待Ｍap再次运行。
  • Reduce worker在输出结果前崩溃,master必须在其他worker上面重新开始该任务。
  • Reduce worker在输出结果的过程中崩溃，GFS会自动重命名输出，然后使其保持不可见直到Reduce完成，所以master在其他地方再次运行Reduce worker将会是安全的。

• 其他错误和问题：

  • 假如master意外的开启两个Ｍap　worker处理同一个输入会怎么样？ 它只会告诉Reduce worker其中的一个。
  • 假如两个Reduce worker　处理中间数据的同一个分区会怎么样？ 它们都会将同一份数据写到GFS上面，GFS的原子重命名操作会触发，先完成的获胜将结果写到GFS.
  • 假如一个ｗorker非常慢怎么办——　一个掉队者？ 产生原因可能是非常糟糕的硬件设施。 master会对这些最后的任务创建第二份拷贝任务执行。
  • 假如一个worker因为软件或者硬件的问题导致计算结果错误怎么办？ 太糟糕了！MR假设是建立在"fail-stop"的cpu和软件之上。
  • 假如master崩溃怎么办？

• 关于那些MapReduce不能很好执行的应用？

  • 并不是所以工作都适合map/shuffle/reduce这种模式
  • 小的数据，因为管理成本太高,如非网站后端
  • 大数据中的小更新，比如添加一些文件到大的索引
  • 不可预知的读(Map 和 Reduce都不能选择输入)
  • Multiple shuffles, e.g. page-rank (can use multiple MR but not very efficient)
  • 多数灵活的系统允许MR，但是使用非常复杂的r模型

• 总结

  • Conclusion MapReduce single-handedly made big cluster computation popular.
    • Not the most efficient or flexible.
    • Scales well.
    • Easy to program -- failures and data movement are hidden. These were good trade-offs in practice. We'll see some more advanced successors later in the course.