15

MIT 6.824 分布式系统课程第一课：介绍笔记 - Jeffery的博客 | Jeffery Blog

 4 years ago
source link: https://blog.microdba.com/%E5%88%86%E5%B8%83%E5%BC%8F%E7%B3%BB%E7%BB%9F/2020/02/26/mit-6.824-lecture-1-introduce/?
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

MIT 6.824 分布式系统课程第一课：介绍笔记

课程概要

预备课程：

6.S081: Operating System Engineering 6.S081 / Fall 2019

操作系统课本：xv6: a simple, Unix-like teaching operating system

课程地址：6.824 Home Page: Spring 2020

笔记：Introduction

视频：Lecture 1: Introduction

parallelism：性能

fault tolerance：错误容忍

physical :

security/ isolate：机器之间隔离

分布式系统的复杂在于机器多之后，在不同的网络环境下会出现意想不到的故障。除此以外，机器也会出现故障。

分布式挑战：并发、分区错误、性能

课程组成：讲座、论文、考试、实验、最后项目

讲座：思考、论文讨论、实验

论文：阅读经典论文、研究新问题、创新、实现细节。

每篇论文都有提问、在上课前都应该阅读，并且回答一些相关的问题。

四个实验：

Lab 1: MapReduce

Lab 2: replication for fault-tolerance using Raft Raft实现

Lab 3: fault-tolerant key/value store 可容错的K/V存储

Lab 4: sharded key/value store 共享kv存储

课程关注的方向：存储、通信、计算

话题1: 实现，RPC、多线程、并发控制

话题2：性能，通过伸缩机器能达到性能的提升，譬如nServer—>nThroughput。CPU、磁盘、网络。伸缩不只是指一点，例如：web server—db。不能只是单单的伸缩web server。db也需要伸缩

分布式系统的目标：当遇到负载问题时，只需要通过加机器就可以解决。而不是通过程序员重新设计开发一套新的。

在系统中，伸缩随着N系数的增加，会面临一些困难：

  1. 内部负载不均衡
  2. 长尾问题，相同的任务在不同机器上面执行的效率不同
  3. 有些不能并行执行的代码：初始化、交叉执行
  4. 共享资源的瓶颈：网络

分布式并不是一劳永逸，有些性能其实也并不好解决：

  1. 个别用户的响应时间比较长（长尾）
  2. 多个用户希望同时更新同一数据

而上面的问题，并不是通过加机器就能解决。需要更好的设计。

lab4 错误容忍

故障出现的时间永远不确定。这是一个非常常见的问题

1000台机器+大规模的网络–>肯定会出现一些故障

面对这些故障是就需要在应用软件层处理，以达到容错的目的。例如在数据库软件中的主从（主从不是严格意义上的分布式）。

对于分布式软件，我们期望：

  1. 可用性，尽管出现了部分故障也能继续提供服务
  2. 可恢复性，故障处理后，不需要额外的处理就能继续工作

服务副本，如果某台服务器出现故障，可以让副本继续提供服务。容错不只是单单的多台服务器即可，应该要保证在不同的区域。假设机房断电，那么该分布式系统就是不成立的。

Lab 1、2、3 关注一致性

通用的基础结构需要定义明确的行为。客户端先进行put(k,v)操作更新数据，然后通过Get(k)读取数据。此时应保证所有的Get(k)结果都是v。

让所有的行为都一致，是一件困难的事情。因为分布式系统中，你的数据是存在副本的（容错），并且存在于cache、disk。

  • 副本很难保证一致性，如果要保证一致性，需要牺牲吞吐性。
  • 客户端可能在多过程更新的过程中出现失败。
  • 服务器可能在执行请求后发送响应之前时崩溃。
  • 网络分区可能会导致以为服务下线了，其实还在工作，俗称“脑分裂”。

一致性和性能是相对称的。强一致性需要额外的通信。譬如get()需要检查最新的put()操作（分布式不是单点）。

现有的大多数分布式系统采用弱一致性来保证任务处理速度。譬如：get()时，不需要再检查或等待put()。虽然不够严谨，但是也算是一种权衡。

一致性和性能是目前设计分布式系统讨论比较多的地方。

案例学习：MapReduce

MapReduce可以说是开启了分布式系统在工业界的普遍应用。

MapReduce的诞生是为了解决希望在短时间内分析和处理几TB级别的数据。譬如：构建索引、排序、分析爬虫回来文档的Web结构

目标：即使是非分布式专家也能很轻松的写分布式程序。工程师只需要定义Map和reduce即可.Map 和reduce的执行由分布式框架处理。

MapReduce任务执行抽象：

img
  1. MR调用输入文件的map()任务，产生新的数据集合(k2,v2) —中间数据
  2. MR根据提供的K2对数据v2进行规整
  3. 把key和value传递给reduce处理
  4. 最终根据一系列的(k2,v2)集合生成最终结果

例如：单词计数

针对单词计数任务的处理过程：输入—切割文件—生成map任务—提取（shuffle）—reduce计算—生成结果

MapReduce的伸缩性非常好，N台worker可以带来N倍的速度

Map和Reduce的运行是并行的，不需要交叉执行。

因此可以通过购买机器来提高性能

MapReduce中还有一些额外的细节：

  • 发送应用代码到服务器
  • 监控任务处理的进度
  • 把map产生的数据发给reduce
  • 服务器之间的负债均衡
  • 长尾任务处理
  • MapReduce对任务有限制
  • 不能交互执行，没有状态
  • 没有多级迭代，没有多级pipeline。而是一个mapReduce到另外一个MapReduce
  • 不能进行实时流处理（现在已经有了，spark）
  • 输入和输出文件是存储在GFS上的
  • MP需要巨大的输入和输出吞吐
  • GFS会把文件以64MB的chunk拆分到不同的服务器
  • Maps的读是并行
  • Reduces的写是并行
  • GFS 的文件副本会存储在2～3个服务器中
  • GFS是MapReduce成功的一大关键

2004年作者在论文中提到，影响性能的因素不是CPU、硬盘、内存。而是网络。Map()任务需要从GFS中读取输入文件，Reduce需要从Map读取产生的结果。发送reduce的结果文件到GFS。读和输出在排序任务时，所需带宽都比较大。值得注意的是，我们的MP机器大部分都是共享一台交换机的。而交换机本身是有限制的。

论文中提到，根交换机的吞吐是100~200GB/sec。而整个集群有1800台机器。每台机器只有55MB/sec。55MB/sec可比内存或硬盘的速度慢多了。(现在交换机升级了)

一些其他的细节：

  • 所有的任务处理进度都存储在一台master上。并且此台机器需要负责任务分派
  • Map操作产生的文件立即写本地文件
  • Map需要把按hash生成的多个文件合并为一个发给reduce
  • 当所有的map任务完成后，再由master分配执行reduce任务。并且每个reduce是单独写GFS的。
  • MR如何最大化的减少对网络的使用
  • 所有的worker都运行有GFS和MR worker
  • Master会尝试在存储输入文件的GFS上执行MR任务
  • 因此，输入是从本地磁盘（通过GFS）读取的，而不是通过网络读取的。
  • 中间数据仅通过网络传输一次
  • Map直接写本地磁盘，Reduce直接从Map的worker读取文件，而不是通过GFS
  • 中间文件会根据hash分为多个
  • R比键的数量少
  • 大型网络的传输效率更高
  • MR是如何获取良好的负载均衡的
  • 如果N-1台服务器需要等待最后一台完成任务，是一种巨大的浪费。
  • 某些任务花费的时间会比其他的任务执行时间要长

解决方案：把任务切分的比worker多

master在发送新任务时，先发送给哪些之前先执行任务的机器。同一时间，执行速度快的worker要比执行速度慢的woker执行的任务要多。

MapReduce如何处理容错？

  • 如果某个worker在执行MR任务时崩溃了。（面向应用开发程序员我们应该隐藏这个细节）

  • MR是否需要必须从开头执行整个任务？为什么不需要？

    MR只需要运行失败的map和reduce任务。假设map任务执行了两次，一个reduce任务执行看到了第一次执行map任务的结果，另外一个reduce任务看到的是第二个。那么这种情况需要重新执行整个过程。除此之外，可以把map和reduce设计成为一个纯确定性函数。参数决定结果

  • 没有状态，没有文件I/O，没有交叉、没有额外的通讯。假设此时你需要容忍非纯确定的函数怎么办？

    当某个worker失败时，解决方式要不是通过全部重新执行。或者是回到某个系统的快照（你可能需要增加这部分的逻辑）。

Worker故障恢复细节：

Map worker故障

  • master注意到worker不再响应。
  • master因为保存了所有该worker执行的任务编号，把任务发给其他worker执行。之前的中间文件丢失了，需要重建
  • 如果Reduce读取了从之前崩溃的worker的中间数据，则可以丢弃重新运行.

Reduce worker故障

  • 已经执行完成的任务可以保留，因为文件存储在GFS，存在副本
  • Master重启未完成的任务在其他worker执行

其他问题思考：

  • 如果master给两个worker发送了相同的Map任务怎么办？master认为其中一个，此时master只会告诉reduce worker只存在一个
  • 如果master给两个 reduce work发送了相同的任务怎么办？他们会尝试写相同的文件到GFS。GFS是rename是原子性的，可以保证只会存在一个输出结果文件
  • 如果有一台worker执行任务非常慢，怎么办？master应在其他机器执行发送到该机器的其他任务。
  • 如果因为计算机硬件导致计算结果错误怎么办？
  • 如果master挂了怎么办？

Mapreduce产生的影响，催化Hadoop和spark诞生。

Google已经不再使用mapreduce框架了，使用Flume / FlumeJava作为替代

GFS被Colossus和BigTable慢慢的取代了

总结

MapReduce让分布式处理变得流行。

它不是最有效和最灵活的系统。

扩展性非常好。

面向应用开发程序员友好，把数据转移和故障隐藏了起来。

里面包含了很多trade-off实践。

参考资料


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK