MIT 6.824分布式课程讲稿翻译 - Lec 1

Posted on | In

MIT 6.824是一门非常经典的分布式系统课程, 通过对经典的Google三大论文的阅读体会, 尝试几个工程量比较大且颇有挑战的Lab, 最终实现一个分布式KV存储系统, 能够让学习者对分布式系统这个方向有入门性的了解.

由于这门课程只给出了类似思维导图的Notes, 并不是完整讲稿, 因此翻译时有些上下文不通顺的地方, 暂时按个人理解来翻译, 并在括号内注明原文. 如果有些部分还是难理解的话建议参考原文.

原文地址: 6.824 2017 Lecture 1: Introduction

导论

什么是分布式系统?

  • 多个主机协同工作
  • 大型数据库, P2P文件共享, MapReduce, DNS等等
  • 大部分关键的基础架构都是分布式的!

为什么需要分布式?

  • 用于连接物理上相互分离的实体
  • 通过隔离(isolation)保证安全性
  • 通过冗余备份实现容错(fault tolerance)
  • 通过并行的CPU/内存/磁盘/网络硬件提升吞吐量(throughput)

然而带来的问题包括:

  • 复杂性(complex): 有多个并发的部分
  • 需要处理局部故障(partial failure)的情况
  • 难以实现的性能潜力(performance potential)

为什么要上这门课?

  • 有趣: 困难的问题, 有力的解决方案
  • 被运用在真实系统中: 由大型Web网站的发展(the rise of big Web sites)趋势导致
  • 活跃的研究领域(active research area): 许多成果以及更多等待解决的问题
  • 动手实践: 你将会在这门课的实验中构建不同的系统

课程结构

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

课程相关人员

Robert Morris, 讲师
Frans Kaashoek, 讲师
Lara Araujo, 助教
Anish Athalye, 助教
Srivatsa Bhat, 助教
Daniel Ziegler, 助教

课程组成

授课

  • 重要思想
  • 论文讨论
  • 实验

阅读

主要是阅读研究论文(部分是旧的, 部分新的). 这些论文都阐述了一些关键的思想或是重要的细节, 后续课程重点也会围绕这些论文.
请在课前完成阅读! 每个论文都有一个简单的问题让你回答, 请务必将阅读时遇到的问题和答案在课前晚上10点之前发给我们.

两次考试

课上的期中考试, 考试周的期末考试

实验

  • 实验目标:
    • 加深对某些重要技术的理解
    • 锻炼编写分布式程序(distributed programming)的能力
    • 第一个实验期限设在从周五开始的一周之内
    • 后续一段时间每周会有一个新实验
  • 实验内容:
    • 实验一: MapReduce
    • 实验二: 使用Raft实现冗余容错(replication for fault-tolerance using Raft)
    • 实验三: 容错的KV存储(fault-tolerant key/value store)
    • 实验四: 数据分片的KV存储(sharded key/value store)

期末项目(可选)

你也可以选择做一个期末项目, 2~3个人组队, 用于代替实验四, 请自选题目并告知我们.

实验的成绩取决于你的程序通过了多少个我们规定的测试项, 因此你能够清楚地知道自己做得怎么样.
如果只是有时通过有时通不过, 我们检查运行的时候也会有可能无法通过.

实验项目的调试可能会很费时, 因此建议大家尽早开始, 平时也可以来助教办公室或者在Piazza上提问

主要论题

这是一门关于应用底层基础架构的课程, 需要去考虑如何抽象以便对应用层隐藏分布式系统的复杂性, 主要包括三类抽象:

  • 存储(Storage)
  • 通信(Communication)
  • 计算(Computation)

下面的这些论题后续可能会经常提到:

论题: 实现(Implementation)

包括RPC, 线程, 并发控制(concurrency control)

论题: 性能(Performance)

目标: 可伸缩的吞吐量(scalable throughput)
通过并行的CPU, 磁盘, 网络, 使N倍的服务器增长带来N倍总吞吐量的提升. 这样提升负载只需要购置更多的服务器.

然而随着N的增大, 扩容将越来越困难:

  • 负载的不均衡, straggler问题;
  • 非并行化的代码(如初始化, 交互相关的代码)
  • 共享资源(如网络)带来的瓶颈

论题: 容错(Fault Tolerance)

成千上万的服务器, 复杂的网络架构, 总会导致某些地方出错, 我们希望把这些错误对应用层隐藏起来.
一般希望达到的是:

  • 可用性(Availability): 在出错时应用仍然能访问数据
  • 持久性(Durability): 错误被修复之后, 应用的数据能够恢复重用

一个重要思想: 使用冗余的服务器(replicated servers). 当一台服务器宕机, 客户端可以接着使用其他的服务器.

论题: 一致性(Consistency)

通常意义上, 基础架构需要提供定义良好的行为(well-defined behavior). 例如”Get(k)返回最近一次的Put(k, v)”.
但是一个足够好的实现是很困难的:

  • 备机难以与主机保持一致
  • 在包含多个步骤的更新过程中(multi-step update)客户端可能会宕机
  • 服务器可能会在奇怪的时候宕机, 例如执行完任务(Task)和发送回复之间(after executing but before replying)
  • 网络环境可能会使服务器看上去宕机, 导致”脑裂”

一致性与性能往往是相互对立的:

  • 一致性要求通信, 比如获取最近一次的Put().
  • 强一致性(Strong consistency)往往会降低系统性能.
  • 高性能的系统通常会要求应用是弱一致性(weak consistency)的.
  • 在这个问题上人们已经尝试了许多不同的设计方式(design points).

案例研究: MapReduce

使用场景

数TB的数据集需要数小时的计算工作时, 例如在数千台服务器上进行爬取网页的拓扑图结构分析, 且缺少一些分布式系统专家来开发, 使得分布式将带来极大的困难.

主要目标

要让普通的开发者也能轻松地分割数据, 分别在多个服务器上以较高的效率处理
开发者只需要定义Map和Reduce函数, 编写普通的的串行代码(sequential code), 降低分布式编程的难度.
MapReduce能够在数千台机器上运行这些函数, 处理大量的输入数据, 并将分布式的细节隐藏起来.

MapReduce抽象图

输入被分割成$M$个文件. 

Input1 -> Map -> a,1 b,1 c,1
Input2 -> Map ->     b,1
Input3 -> Map -> a,1     c,1
                  |   |   |
                      |   -> Reduce -> c,2
                      -----> Reduce -> b,2

MapReduce通过对每个输入文件调用Map(), 输出中间数据(intermidiate data)—键值对<k2, v2>的集合. 每个Map()调用称为一个Task
之后MapReduce对给定的每个k2, 统计其所有的中间数据并传给Reduce函数
最终从Reduce输出的是键值对<k2, v3>的集合, 存储在$R$个输出文件中

示例: 统计字数(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隐藏了许多繁琐的细节

  • 在服务器上启动程序(starting s/w on servers)
  • 跟踪哪些Task被完成(tracking which tasks are done)
  • 数据迁移(data movement)
  • 错误恢复(recovering from failures)

MapReduce能够方便地扩容

  • $N$台服务器能够得到$N$倍的吞吐量增长
  • 假设$ M, R >= N$(例如大量的输入文件和Key值)
  • 由于Map()函数相互无交集, 可以并行运行
  • Reduce()同理
    因此你能够通过更多的服务器得到更大的吞吐量, 而不是去针对每个应用进行特定的并行化, 计算机比程序员便宜得多!

什么因素可能会限制性能?

性能使我们需要优化的点, 所以要多加考虑
CPU? 内存? 磁盘? 网络?
2004年时(MapReduce论文的)作者们被跨分区网络带宽所限制. 要知道在Map->Reduce的过程中, 所有数据都要走网络.
论文当时使用的根路由器速度在100~200Gb/s, 1800台机器, 因此每台机器平均使用55Mb/s, 速度非常慢, 比硬盘和RAM慢得多. 因此他们要考虑的是如何最小化网络上的数据传输(当然今天的数据中心要快得多).

更多细节

  • Master: 向worker分发Task. 要记住这里中间输出的是$M$个Map Task, $R$个Reduce Task.
  • 输入存放在GFS中, 每个Map输入文件存3份用于备份
  • Task数远大于worker数
  • master每次给一个worker分配一个Task, 完成后再分配下一个
  • Map worker将(Map和Reduce)中间的Key值哈希映射成$R$份到本地磁盘上
  • 等所有Map调用执行完毕后才开始执行Reduce调用
  • master会让Reducer从Map worker获取已分片的中间数据
  • Reduce worker将最终的输出数据写入GFS(每个Reduce task输出一个文件)

这些细节设计如何提升在慢速网络环境中的效率

  • Map的输入时从本地磁盘上的GFS备份(GFS replica)读入, 而不是通过网络读入的.
  • 中间数据(Intermediate data)只在网络上传输一次, Map worker写入到本地磁盘而非GFS中
  • 中间数据被划分成若干个包含许多Key的文件, 在大型网络(Big network)中传输效率更快

如何较好地实现负载均衡

这对于扩展非常关键——因为N-1个服务器等待1个服务器完成是严重影响效率的
但某些Task可能会比其他的花费更长的时间.
解决方案: 使Task的数量远比worker多, 这样的好处是:

  • Master就能把新的任务分派给那些完成了先前任务的Worker.
  • Task不会太大, 以至于占据了Worker的所有时间
  • 快的服务器比慢的服务器可以做更多的工作, 保证它们大约在同一时刻结束工作.

关于容错(Fault Tolerance)

容错就是说如果一台服务器在执行一个MR(MapReduce)任务的过程中宕机了怎么办?
故障的隐藏在编程中是一个很值得研究的话题(huge part of programming)
为什么不把整个任务重新开始?
MapReduce仅在Map()或Reduce()失败时才重新执行. 因此MR需要这两个函数都是纯函数(Pure function), 也就是说:

  • 每次调用都是无状态的
  • 除了MR输入输出文件之外, 不会读写其他文件
  • Task与Task之间没有隐藏的数据交互
    这样才能保证重新执行一定能得到同样的输出.
    需要提供纯函数是MR相对于其他并行编程模式的一个主要限制, 但这正是保证MR简洁性的关键.

Worker宕机恢复的细节

Map Worker宕机后:

  • Master发现Worker不再响应Ping包
  • 宕机的Worker会缺少相应的中间文件(丢失的中间文件可能会被每个Reduce Task需要).
  • Master重新执行, 向输入文件在GFS上的其他副本(服务器)分发任务.
  • 某些Reduce Worker可能已经读了故障的Map Worker输出的中间数据, 这里需要取决于Map()函数的功能和定义. 如果Reduce已经读取了所有中间数据那么Master不需要重新执行Map(), 接着Reduce Worker会宕机从而使得失败的Map()强制重新执行.

Reduce Worker宕机后:

  • 那些已经完成的Task是OK的, 输出和冗余备份都已经写入保存到GFS中了.
  • 对于没有完成的Task, Master会在其他Worker重启这些Task.

Reduce Worker正在输出结果中途宕机:

  • GFS有原子性的重命名操作(atomic rename)来保证输出只有全部完成, 输出文件才可见. 因此Master在其他地方重新执行这个Reduce Task是安全的.

其他错误/问题

  • 如果Master给两个Worker分配了同一个Map Task?
    可能是Master认为其中一个Worker已经挂了. 它会只把一个Worker告诉后续的Reduce Worker.
  • 如果Master给两个Worker分配了同一个Reduce Task?
    他们会试图在GFS上写入同一个输出文件!
    但GFS提供的原子性的重命名操作
  • 如果一个Worker非常慢 - 是一个”掉队者(straggler)”?
    可能是因为薄弱的硬件条件.
    Master会拷贝最后剩下的少数Task到其他Worker上执行
  • 如果一个Worker由于软件或硬件原因计算出错误的输出?
    太糟糕了! MapReduce假设CPU和软件都是”遇错即停”的
  • 如果Master宕机了?

什么样的应用不适合用MapReduce运行?

不是每个应用都适合这种Map/Shuffle/Reduce的模式:

  • 数据很少的, 因为传输时间会很长. 例如不是网站的后端(not web site back-end)
  • 对大量数据进行少量更新, 例如将一些文档添加到一个大的索引中
  • 不可预期的读操作(因为Map和Reduce都不能自己选择输入)
  • 多次重组(Shuffle), 例如page-rank(可以用MapReduce但不是很高效)
  • 很多灵活的系统都可以用MR, 但是模型会很复杂

总结

MapReduce使得大规模集群计算变得流行起来.

  • 不是最高效或最灵活的
  • 便于扩展
  • 易于编程—隐藏了失败处理和数据转移

这些都是在实践中很好的取舍(trade-offs)
我们会在后续课程中还会看到更多比MapReduce高级的框架模型.
祝实验愉快!