【6.824 笔记】LEC 1: Introduction

参考笔记链接:

http://nil.csail.mit.edu/6.824/2020/notes/l01.txt

https://mit-public-courses-cn-translatio.gitbook.io/mit6-824/lecture-01-introduction

分布式系统 Intro

什么是分布式系统?

  • 多个相互协作的计算机
  • 大型网站的存储,MapReduce,peer-to-peer共享,等等
  • 很多重要的基础设施都是分布式的

人们为什么要建立分布式系统?

  • 通过并行性增加容量
  • 通过副本机制 replication 来容忍故障
  • 将计算放在与外部实体相近的地方
  • 通过隔离来实现安全

遇到的问题:

  • 许多并发的部分,复杂的相互作用
  • 必须应对部分故障
  • 要释放机器的全部潜在性能很困难

课程 Intro

课程主页

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

课程人员

罗伯特-莫里斯,讲师
阿尼什-阿塔尔耶,助教
Aakriti Shroff, TA
Favyen Bastani, TA
Tossaporn Saengja,助教

实验 Lab

  1. Lab 1: MapReduce
  2. Lab 2: replication for fault-tolerance using Raft
  3. Lab 3: fault-tolerant key/value store
  4. Lab 4: sharded key/value store

主要内容

这是一门关于应用程序基础设施的课程。

  • 存储
  • 通信
  • 计算

最大的目标是:隐藏分布的复杂性的抽象概念。
在我们的搜索中,有几个主题会反复出现。

主题:实现
RPC,线程,并发控制。
实验室…

主题:性能
目标:可扩展的吞吐量
Nx个服务器 -> Nx个通过并行CPU、磁盘、网络的总吞吐量。
[图示:用户、应用服务器、存储服务器] 。
因此,处理更多的负载只需要购买更多的计算机。
而不是由昂贵的程序员重新设计。
当你可以在没有太多互动的情况下进行分工时,就很有效。
随着N的增长,扩展变得更加困难。
负载不平衡,散兵游勇,最慢的N次方延迟。
不可并行化的代码:初始化、交互。
共享资源的瓶颈,例如网络。
有些性能问题不容易通过扩展来解决
例如,单个用户请求的快速响应时间。
例如,所有用户都想更新相同的数据
通常需要更好的设计,而不仅仅是更多的计算机
实验4

主题:容错
1000台服务器,大网络------总是有一些故障
我们希望向应用隐藏这些故障。
我们通常希望。
可用性 – 尽管有故障,应用程序仍能取得进展
可恢复性 – 当故障被修复时,应用程序将重新恢复活力
大的想法:复制的服务器。
如果一个服务器崩溃了,可以用另一个(或几个)进行。
实验1、2和3

主题:一致性
通用的基础设施需要明确的行为。
例如,“Get(k)产生最近一次Put(k,v)的值”。
实现良好的行为是很难的!
"副本 "服务器很难保持一致。
客户端可能会在多步骤更新的中途崩溃。
服务器可能会崩溃,例如,在执行后但在回复前。
网络分区可能使活着的服务器看起来像死了;有 "大脑分裂 "的风险。
一致性和性能是敌人。
强大的一致性需要沟通。
例如,Get()必须检查最近的Put()。
许多设计只提供弱一致性,以获得速度。
例如,Get()并不*产生最新的Put()!
这对应用程序的程序员来说是很痛苦的,但可能是一个很好的权衡。
在一致性/性能范围内,有许多设计点是可能的。

案例研究。MapReduce

让我们把MapReduce(MR)作为一个案例来讨论吧
很好地说明了6.824的主要议题
具有巨大的影响力
实验1的重点

MapReduce概述
背景:对多TB级数据集进行多小时的计算
例如,建立搜索索引,或排序,或分析网络结构
只适用于1000台计算机
应用不是由分布式系统专家编写的
总体目标:让非专业的程序员也能轻松使用
程序员只需定义Map和Reduce函数
通常是相当简单的顺序代码
MR负责处理并隐藏了分布式的所有方面!

MapReduce工作的抽象视图

image-20221015200508232输入被(已经)分割成M个文件
MR为每个输入文件调用Map(),产生一组k2,v2的
的 "中间 "数据
每次调用Map()都是一个 “任务”
MR收集给定k2的所有中间v2。
并将每个键+值传递给一个Reduce调用
最终输出是来自Reduce()的对的集合。

例子:字数统计
输入是数以千计的文本文件
Map(k, v)
将v分割成单词
对于每个词w
发出(w, “1”)
减少(k, v)
emit(len(v))

MapReduce的扩展性很好。
N个 "工作者 "计算机可以获得Nx的吞吐量。
Maps()可以并行运行,因为它们不相互影响。
Reduce()也一样。
所以你可以通过购买更多的计算机来获得更多的吞吐量。

MapReduce隐藏了很多细节。
向服务器发送应用程序代码
跟踪哪些任务已经完成
将数据从Maps转移到Reduce
平衡服务器上的负载
从故障中恢复

然而,MapReduce限制了应用程序可以做什么。
没有交互或状态(除了通过中间输出)。
没有迭代,没有多阶段的管道。
没有实时或流式处理。

输入和输出都存储在GFS集群文件系统上。
MR需要巨大的并行输入和输出的吞吐量。
GFS将文件分割到许多服务器上,以64MB为一个块。
以并行方式映射读取
以并行方式减少写入
GFS还将每个文件复制到2或3个服务器上
拥有GFS是MapReduce的一大胜利。

什么可能会限制性能?
我们关心这个问题,因为这是需要优化的。
CPU、内存、磁盘、网络?
在2004年,作者受到了网络容量的限制。
MR在网络上发送什么?
地图从GFS读取输入。
Reduces读取Map的输出。
可以和输入一样大,例如,用于排序。
Reduces写输出文件到GFS。
[图示:服务器,网络交换机的树形]
在MR的全对全洗牌中,一半的流量要经过根交换机。
论文的根交换机:100到200千兆比特/秒,总共有
1800台机器,所以55兆比特/秒/台。
55是很小的,例如,比磁盘或内存速度小得多。
今天:相对于CPU/磁盘,网络和根交换机要快得多。

一些细节(论文的图1)。
一个主站,把任务交给工人并记住进度。
主站将地图任务交给工人,直到所有的地图完成。
地图将输出(中间数据)写到本地磁盘上
地图将输出按哈希值分割到每个Reduce任务的一个文件中。
2.在所有地图完成后,主站将Reduce任务分配给工人
每个Reduce任务从(所有)Map工作者那里获取其中间输出。
每个Reduce任务在GFS上写一个单独的输出文件

MR如何尽量减少网络使用?
主站尝试在存储其输入的GFS服务器上运行每个Map任务。
所有的计算机都同时运行GFS和MR任务
因此,输入数据是从本地磁盘(通过GFS)读取的,而不是通过网络。
中间数据只经过一次网络。
地图工作者写到本地磁盘。
Reduce工作者直接从Map工作者那里读取,而不是通过GFS。
中间数据被分割成持有许多键的文件。
R比键的数量小得多。
大的网络传输更有效率。

MR如何获得良好的负载平衡?
如果N-1个服务器必须等待1个慢速服务器完成,那么就会造成浪费和缓慢。
但有些任务很可能比其他任务花的时间更长。
解决方案:任务比工人多得多。
主人把新任务交给完成先前任务的工人。
因此,没有一个任务大到可以支配完成时间(希望如此)。
因此,快的服务器比慢的服务器做更多的任务,完成的时间也差不多。

容错性如何?
也就是说,如果一个工作者在MR任务中崩溃了怎么办?
我们想对应用程序的程序员完全隐藏故障。
MR是否必须从头开始重新运行整个工作?
为什么不呢?
MR只重新运行失败的Map()s和Reduce()s。
假设MR将一个Map运行了两次,一个Reduce看到了第一次运行的输出。
另一个Reduce看到了第二次运行的输出?
正确性要求重新执行时产生完全相同的输出。
所以Map和Reduce必须是纯确定性的函数。
它们只允许看它们的参数。
没有状态,没有文件I/O,没有交互,没有外部通信。
如果你想允许非功能性的Map或Reduce呢?
工作者失败将需要重新执行整个工作。
或者你需要创建同步的全局检查点。

工作者崩溃恢复的细节。

  • 地图工作者崩溃了。
    主站注意到工作器不再响应 ping
    主站知道它在该工作者上运行了哪些地图任务
    这些任务的中间输出现在已经丢失,必须重新创建
    主站告诉其他 Worker 运行这些任务
    如果Reduces已经获取了中间数据,则可以省略重新运行。
  • Reduce工作者崩溃了。
    完成的任务是好的 – 存储在GFS中,有副本。
    主程序在其他worker上重新启动worker的未完成任务。

其他故障/问题。

  • 如果主站给了两个工作者相同的Map()任务怎么办?
    也许master会错误地认为一个worker死了。
    它将只告诉Reduce工作者其中一个。
  • 如果主站给了两个worker同样的Reduce()任务呢?
    他们都会试图在GFS上写下同一个输出文件!
    GFS的原子重命名可以防止混合;一个完整的文件将是可见的。
  • 如果一个工作器非常慢 – "散兵游勇 "怎么办?
    也许是由于软弱的硬件。
    主站启动最后几个任务的第二个副本。
  • 如果一个工作者由于硬件或软件损坏而计算出不正确的输出,怎么办?
    太糟糕了! MR假设 "故障停止 "的CPU和软件。
  • 如果主程序崩溃了怎么办?

目前的状况?
影响力巨大(Hadoop, Spark, &c)。
可能在谷歌已经不使用了。
被Flume/FlumeJava取代(见Chambers等人的论文)。
GFS被Colossus(没有好的描述)和BigTable取代。

结论
MapReduce单枪匹马地使大集群计算流行起来。

  • 不是最有效或最灵活的。
  • 扩展性好。
  • 易于编程 – 失败和数据移动被隐藏。
    这些在实践中都是很好的权衡。
    我们将在课程后期看到一些更高级的继承者。
    祝你在实验室里玩得开心!