MIT6.824学习笔记
MIT 6.824 分布式系统课程笔记，记录 MapReduce、实验与分布式编程中的问题。
MIT6.824学习笔记 distribution course go的协程可以通过注解的方法式选定特定的协程进行任务发布
6.5840 Schedule: Spring 2023 (mit.edu)
00 introduces
1
2
3
4
5
6
7
8
9
10
Labs:
goal: deeper understanding of some important ideas
goal: experience with distributed programming
first lab is due a week from Friday
one per week after that for a while
Lab 1: distributed big-data framework (like MapReduce)
Lab 2: fault tolerance using replication (Raft)
Lab 3: a simple fault-tolerant database
Lab 4: scalable database performance via sharding
01 MapReduce论文阅读
rfeet.qrk (mit.edu)
词汇
commodity machine：是指那些广泛可用、成本相对较低、没有特定定制的计算机硬件。这些机器往往是标准化的，可以从多家供应商那里购买，而不是特制或专为某种特定应用而设计。
crawled document: 爬虫文档信息
conspire to：共同导致
obscure : 掩盖
messy detail: 混乱的细节
conduit: 管道
resilient: 弹性的、有复原力的
The issues of how to parallelize the computation, distribute the data, and handle
failures conspire to obscure the original simple computation with large amounts of complex code to deal with
these issues.
programming model
map function : take input pair and produces a set of intermediate key/value pairs. not repetition
reduce function : accept an intermediate key I and a set of values for that key. It merges together these values to form a possibly smaller set of values.
a group of clusters, one master to assign the rest workers the map/reduce task.
master(role): assign the worker， pass the locations of map workers to reduce workers.
map worker(role) : parses key/value pair out of the input data, and call the map function defined by user.
reduce worker(role): use rpc to read data from map workers, group all the same key by sorting, call the reduce function defined by user.
fault tolerance
woker failure: matser ping worker periodically.
any tasks running in failed workers are reset back to their initial idle state.
completed map task should be re-executed becaue their output is stored on the local disk.
but competely tasks do not need to be re-executed.
master failure
write periodic checkpoint of the master data structure.
aborts the mapReduce computation if the master fails.
02 lab1
[MIT 6.824 - MapReduce: Simplified Data Processing on Large Clusters
Übung macht den Meister (frederick-s.github.io)](https://frederick-s.github.io/2022/02/13/mit-6.824-map-reduce/)
[MIT 6.824 分布式系统
Lab 1：MapReduce - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/260752052)
路径介绍
src/mrapps: 所有课程使用的map/reduce函数，其中wc.go是lab1使用的函数
src/mr: 是lab1 要填写的coordinator与worker的逻辑
串行的实现在mrsequential.go
而我们所需要做的分布式实现在mr
问题
worker 一直向coordinator请求吗，什么时候终止？
每次worker该获得多少任务?
一旦work获得map任务还能不能获得reduce任务?
输出文件是如何reduce合并为一整个文件的？
当所有任务都被完成后，就终止。
每次worker获得一项任务的map阶段或者reduce阶段。
我们可以设计成整个集群只有map在运行或者只有reduce在运行，这样就不用考虑map与reduce的平衡问题；如果让map和reduce 同时存在（某些场景下，可能需要固定某些节点只执行reduce、为了不让这些节点空闲就很有必要让map与reduce数量平衡），那么可以使得map结束后，立马将其filename对应的task加入队列。
将所属的map中间态输出文件，读取并执行reduce函数，输出out文件，最后测试程序会自行合并这些数据。
03 GFS google file system
[MIT 6.824 - The Google File System
Übung macht den Meister (frederick-s.github.io)](https://frederick-s.github.io/2022/04/19/mit-6.824-gfs/)
Google File System 论文详析 - 知乎 (zhihu.com)
GFS是一个分布式文件系统
一个 GFS 集群由一个主节点（master）和多个 chunkserver 组成，并被多个客户端（client）访问。不管是主节点还是 chunkserver 或客户端，都运行在廉价的 Linux 机器上。可以简单的将 chunkserver 和客户端运行在同一台机器上，如果系统资源允许或者能够容忍客户端代码潜在的不可靠性的话。
每个文件在存入 GFS 时会被切分为固定大小的块（chunk），每个 chunk 在创建时会被主节点分配一个全局不可变的64位 chunk handle。chunkserver 将 chunk 保存在本地文件系统中，每个 chunk 对应着本地的一个 Linux 文件，客户端通过指定 chunk handle 和文件偏移范围来读取或者写入 chunk。为了保证可靠性，每个 chunk 会复制到多台 chunkserver 上。GFS 默认为每个 chunk 生成3份副本，不过用户也可以为某些命名空间下的文件指定不同的副本数量。
主节点保存了全部的系统元数据，包括文件命名空间、访问控制信息、每个文件和对应 chunk 的映射、每个 chunk 所在的位置等。同时主节点还负责 chunk 的租约管理、不再使用的 chunk 的垃圾回收、chunkserver 间的 chunk 迁移等。主节点也会定期的向 chunkserver 发送心跳用于向 chunkserver 发送指令和收集 chunkserver 当前的状态。
GFS 的客户端代码会集成到用户应用程序中，它负责实现文件系统 API 以及和主节点、 chunkserver 通信来读取或写入文件。GFS 客户端通过主节点获取文件的元数据信息，然而文件的读取和写入都只和 chunkserver 通信，从而减少了主节点的负担。
不管是 GFS 客户端还是 chunkserver 都不会缓存文件数据。客户端缓存收益不大是因为 Google 大部分的应用程序是对大文件的流式读取或者文件内容过大无法被缓存。不考虑缓存简化了客户端和整个系统的实现，因为引入缓存就要考虑缓存一致性问题。不过客户端会缓存文件的元数据信息，例如某个 chunk 的位置信息。chunkserver 不缓存是因为 chunk 是作为 Linux 文件保存在本地文件系统中，操作系统本身已经提供了一层文件访问缓存，没有必要再加一层。
基本读操作
C send file, chunk index
return chunk handle, chunk server list, chunk locations
chunk cache list
c read from closet server
server check the version, if ok -> send data
why check version? to avoid stale data
写
GFS 支持的文件数据修改数据包括两种：
指定偏移值的数据写入（Write）以及数据追加（Record Append）
client send junk handle to master (talk to the master where to write)
master pick out one as primary +and others as secondary+ increment version number to send back to client
client send writing signal to primary replica
primary replica send the sync signal to secondary replica 1 and secondary replica 2, if the primary admitted the modification.
GFS 的一致性模型是相对松散的，这就要求上层应用在使用 GFS 时能够适应 GFS 所提供的一致性语义。简单来讲，上层应用可以通过两种方式来做到这一点：更多使用追加操作而不是覆写操作；写入包含校验信息的数据。
数据写入
当写入时，指定的数据会被直接写入到客户端指定的偏移位置中，覆盖原有的数据。GFS 并未为该操作提供太多的一致性保证：如果不同的客户端并发地写入同一块文件区域，操作完成后这块区域的数据可能由各次写入的数据碎片所组成，即进入不确定的状态。
数据追加
与写入操作不同，GFS 确保即便是在并发时，数据追加操作也是原子且 at least once（至少一次）的。操作完成后，GFS 会把实际写入的偏移值返回给客户端，该偏移值即代表包含所写入数据的确定的文件区域的起始位置。由于数据追加操作是 at least once 的，GFS 有可能会在文件中写入填充（padding）或是重复数据，但出现的概率不高。
客户端有可能读入重复的数据，此时只能由上层应用通过鉴别记录的唯一 ID 等信息来过滤重复数据了。
为了在读取数据时避免读入填充数据或是损坏的数据，数据在写入前往往会放入一些如校验和等元信息以用于验证其可用性，如此一来 GFS 的客户端 library 便可以在读取时自动跳过填充和损坏的数据。
删除文件
首先，当用户删除某个文件时，GFS 不会从 Namespace 中直接移除该文件的记录，而是将该文件重命名为另一个隐藏的名称，并带上删除时的时间戳。在 Master 周期扫描 Namespace 时，它会发现那些已被“删除”较长时间，如三天，的文件，这时候 Master 才会真正地将其从 Namespace 中移除。在文件被彻底从 Namespace 删除前，客户端仍然可以利用这个重命名后的隐藏名称读取该文件，甚至再次将其重命名以撤销删除操作。
Master 在元数据中有维持文件与 Chunk 之间的映射关系：当 Namespace 中的文件被移除后，对应 Chunk 的引用计数便自动减 1。同样是在 Master 周期扫描元数据的过程中，Master 会发现引用计数已为 0 的 Chunk，此时 Master 便会从自己的内存中移除与这些 Chunk 有关的元数据。在 Chunk Server 和 Master 进行的周期心跳通信中，Chunk Server 会汇报自己所持有的 Chunk Replica，此时 Master 便会告知 Chunk Server 哪些 Chunk 已不存在于元数据中，Chunk Server 则可自行移除对应的 Replica。
一致性 Consistency
文件的数据修改则相对复杂。在讲述接下来的内容前，首先我们先明确，在文件的某一部分被修改后，它可能进入以下三种状态的其中之一：
客户端读取不同的 Replica 时可能会读取到不同的内容，那这部分文件是不一致的（Inconsistent）
所有客户端无论读取哪个 Replica 都会读取到相同的内容，那这部分文件就是一致的（Consistent）
所有客户端都能看到上一次修改的所有完整内容，且这部分文件是一致的，那么我们说这部分文件是确定的（Defined）
在修改后，一个文件的当前状态将取决于此次修改的类型以及修改是否成功。具体来说：
如果一次写入操作成功且没有与其他并发的写入操作发生重叠，那这部分的文件是确定的（同时也是一致的）
如果有若干个写入操作并发地执行成功，那么这部分文件会是一致的但会是不确定的：在这种情况下，客户端所能看到的数据通常不能直接体现出其中的任何一次修改
失败的写入操作会让文件进入不一致的状态
chunk大小
对于一个小文件来说，它可能只有几个甚至是一个 chunk，如果这个文件被访问的频率较大，它就有可能成为热点数据，保存了对应的 chunk 的 chunkserver 就要承受更大的流量。不过在 Google 的实际应用场景中，热点数据并没有成为一个大问题，因为大部分的系统面向的是大文件的流式读取，流量能较平均的分发到各个 chunkserver。
Google 确实有遇到过一个热点数据问题，有个批处理系统会先将一个可执行文件写入到 GFS 中，这个可执行文件的大小只有一个 chunk，然后所有客户端会同时读取这个可执行文件并执行，这就造成了几台 chunkserver 同时承接了大量的请求。Google 通过两个方面来解决这个问题，第一针对这个文件设置一个较大的副本数量，让更多的 chunkserver 来分散流量，即水平扩展；第二交替启动批处理系统的客户端，避免同一时间的大量请求。另一种长期的解决方案是在这种场景下允许客户端从其他已读取完毕的客户端那读取文件。
chunk handle ：每一个操作记录 读写类型，version number, chunk server locations
元数据
GFS 集群的元数据主要包括以下三类信息：
文件与 Chunk 的 Namespace
文件与 Chunk 之间的映射关系
每个 Chunk Replica 所在的位置
所有的元数据都保存在主节点的内存中，前两种元数据被修改时还会以日志的形式保存在本地日志文件中，并备份到其他服务器上。通过日志文件的方式使得主节点能够轻松的修改元数据，并且在主节点崩溃重启后能恢复数据，当然极端情况下主节点有可能没有保存最新的元数据到日志文件中就崩溃了，这里后文会有说明主节点会在持久化完成后才返回结果给客户端，所以客户端不会看到未持久化的元数据。
数据结构
主节点也能够轻易的每隔一段时间遍历所有的元数据，这个主要有三个目的，第一是扫描不再需要的 chunk 进行垃圾回收；第二如果某个 chunkserver 失联了，能将其保存的 chunk 备份到其他 chunkserver 上；第三将某些流量失衡或者本地磁盘空间不够的 chunkserver 下的 chunk 转移到其他 chunkserver 下。
if client store the version cache for a long time, it is possible that its version number is stale, oldder than the other replicas. because if the version number checking test is passed, the chunk handle is permitted.
04 The Design of a Practical System for Fault-Tolerant Virtual Machines
https://zhuanlan.zhihu.com/p/523109983
abstract
实现了一个企业级的系统，它通过复制 ”对primary虚拟机操作“ 到secondary虚拟机来提供 fault-tolerant功能。
而这个操作对于应用的性能削减不到10%，此外 primary和secondary的交互带宽也不会超过20Mbit/s，低带宽要求意味两个虚拟机之间的距离可以很远。
这个系统会自动存储冗余错误恢复恢复时所需的额外信息。
这个篇文章主要介绍FT基本设计、可选方案、一堆实现细节，以及对比实验结果。
conclusion
利用在backup上面做terministic replay， 实现fault-tolerant。
FT模型基本信息
所有主VM接收到的输入都会通过名为logging channel的网络连接，被发送到备份VM上。对于几个工作负载而言，主要的输入途径是网络和磁盘。为了保证备份VM和主VM使用相同的方式执行非确定性操作，下面2.1节讨论的额外的信息也需要发送。结果备份VM总是执行和主VM一致的操作。然而，备份VM的输出会被管理程序扔掉，因此只有主VM产生实际输出，并被返回给客户端。和2.2节中描述的一样，为了确保主VM失败后没有数据丢失，主备VM遵循一个具体的协议，包括备份VM明确的确认信息。
针对在VMare vSphere平台上的x86虚拟机，VMware确定性地重放恰好提供了这个功能。确定性重放记录了 VM 的输入以及与 VM执行相关的所有可能的不确定性的日志条目流，这些条目会被写入日志文件。在读取日志文件中的条目后，VM 操作会被精确地重放。 对于非确定性操作，为了允许操作以相同的状态变化和输出再现，需要记录足够的信息。 对于非确定性事件，例如定时器或 IO 完成中断，事件发生的确切指令也会被记录下来。