课程概要
预备课程：
6.S081: Operating System Engineering 6.S081 / Fall 2019
操作系统课本：xv6: a simple, Unix-like teaching operating system
课程地址：6.824 Home Page: Spring 2020
笔记：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系数的增加，会面临一些困难：
- 内部负载不均衡
- 长尾问题，相同的任务在不同机器上面执行的效率不同
- 有些不能并行执行的代码：初始化、交叉执行
- 共享资源的瓶颈：网络
分布式并不是一劳永逸，有些性能其实也并不好解决：
- 个别用户的响应时间比较长（长尾）
- 多个用户希望同时更新同一数据
而上面的问题，并不是通过加机器就能解决。需要更好的设计。
lab4 错误容忍
故障出现的时间永远不确定。这是一个非常常见的问题
1000台机器+大规模的网络–>肯定会出现一些故障
面对这些故障是就需要在应用软件层处理，以达到容错的目的。例如在数据库软件中的主从（主从不是严格意义上的分布式）。
对于分布式软件，我们期望：
- 可用性，尽管出现了部分故障也能继续提供服务
- 可恢复性，故障处理后，不需要额外的处理就能继续工作
服务副本，如果某台服务器出现故障，可以让副本继续提供服务。容错不只是单单的多台服务器即可，应该要保证在不同的区域。假设机房断电，那么该分布式系统就是不成立的。
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任务执行抽象：
- MR调用输入文件的map()任务，产生新的数据集合(k2,v2) —中间数据
- MR根据提供的K2对数据v2进行规整
- 把key和value传递给reduce处理
- 最终根据一系列的(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实践。
参考资料
- 第一课：介绍：Introduction
- 《A Very Brief Introduction to MapReduce》A Very Brief Introduction to MapReduce
- 《MapReduce: Simplified Data Processing on Large Clusters》
- 《Storage Architecture and Challenges》Storage Architecture and Challenges