Lecture1 - Introduction

参考链接：
nil.csail.mit.edu/6.824/2022/papers/mapreduce.pdf

为什么使用分布式系统

  • 连接分隔开的物理机器（允许用户共享数据）
  • 通过并行来提高容量（capacity）
  • 容错（tolerate faults）
  • 通过隔离实现安全

发展历史

  • 局域网（1980s）：DNS、AFS
  • 数据中心随着大型网站兴起（1990s）：网页搜索、购物
  • 云计算（2000s）
  • ……

挑战

  • 大量并发组件
  • 必须处理部分故障（某台机器宕机）
  • 难于实现性能优势

课程结构

  • 课程
  • 论文
  • labs
    • Mapreduce
    • replication using raft
    • replicated K-V service
    • sharded K-V service

聚焦：基础架构

  • 存储
  • 计算
  • 通信

主题

  • 容错（高可用性-备份、可恢复性-日志/事务）
  • 一致性
  • 性能（吞吐量、延迟）
  • 实现

Mapreduce

Lab1

  • Q1：需要开启一个协程来不断循环监控某个共享变量，同时这个共享变量又会在其他地方修改，该如何处理？

Lecture2 - RPC and Threads

Why Go？

  • 对线程和RPC的支持
  • 好的垃圾回收机制
  • 类型安全
  • 简单易学
  • 编译型语言，运行时开销不大

线程

关心并发的原因：

  • IO并发性
  • 多核并行
  • 方便：定期执行一些后台活动任务

挑战：

  • 竞态条件（两个线程操作同一个资源）
    • 避免共享资源
    • 加锁，让指令变成原子操作
  • 同步
    Channels 或者 condition variables
  • 死锁

Go的解决方案：

  • channels（不共享内存时使用）
  • locks + condition variables（共享内存时使用）

RPC

LEC 3 - GFS

参考链接：
nil.csail.mit.edu/6.824/2022/papers/gfs.pdf
解读Google分布式文件系统GFS（合集）_哔哩哔哩_bilibili

为什么分布式存储实现起来很难？

（层层递进，又互相影响）
高性能 ——> 在许多服务器上共享数据
许多服务器 ——> 持续故障
容错 ——> 主从复制
主从复制 ——> 潜在的不一致性
一致性 ——> 低性能

分布式文件系统 Q&A

单机文件系统 —(A)— 分布式文件系统 —(B)—> GFS

  • A1：文件如何分散存储在多台服务器上？怎样实现动态扩缩容？

    • 分割存储
    • 在 master 单点上增减、调整 chunk 元数据

  • A2：怎么知道哪一个文件存储在哪台机器上？

    • 根据 master 元数据中文件名到 chunk 再到 chunk 位置的映射来定位具体的 chunkserver

  • A3：怎样保证服务器在故障时文件不损坏不丢失？

    • master 的 WAL 和主备、chunk的多副本

  • A4：使用多副本的话，如何保持副本间数据的一致性？

    • 对一个 chunk 所有副本的写入顺序都是一致的。这是由控制流和数据流分离技术来实现的，控制流都是由 primary 发出，副本的写入顺序也是由 primary 到 secondary
    • 使用 chunk 版本号来检测 chunk 副本是否出现过宕机，失效的副本不会再进行写入操作，master 不会再记录这个副本的信息，GC 会自动回收这些副本
    • master 定期检查 chunk 副本的 checksum 来确认其是否正确
    • GFS 推荐应用更多地使用追加来达到更高的一致性

  • B1：怎样支持大文件存储？

    • 采用了更大的 chunk(64MB)，以及配套的一致性策略

  • B2：超多台机器的情况下，自动监控、容错与恢复？

    • master 的主备切换由 chubby 负责，chunk 的租约、副本位置与数量是由 master 负责

  • B3：怎样支持快速的顺序读和追加写？

    • 总体上 GFS 是三写一读的模式，写入采用了流水线技术和数据流与控制流分离技术保证性能
    • 追加写对一致性的保证更简单也更高效，所以写入多采用追加写的形式
    • 读取则所有副本均可读，在就近读取情况下性能会很高

GFS 整体架构


一个 GFS 集群由一个主节点 master 和 多个 chunkserver 组成，集群会被许多 GFS 客户机访问。

GFS 存储设计

chunk 在 chunkserver 中的分布

GFS 的 master 设计

管理元数据结点（master 结点）设计为单点还是多节点？

单中心结点 多中心结点（分布式中心结点）
优点 实现难度低，一致性容易保证 实现难度极高，一致性难以保证，系统可靠性难以验证
缺点 单点可能会成为整个系统的瓶颈 不存在瓶颈，可拓展性极强
方案工作重心 缩减元数据，减少单 master 压力 设计一个分布式的元数据管理功能，验证其可靠性

Google 最终选择了单主节点模式，用来存储整个文件系统的三类元数据：

  1. 所有文件和 chunk 的 namespace 【持久化】
  2. 文件到 chunk 的映射【持久化】
  3. 每个 chunk 的位置【不持久化】（master 启动或者每当有新 chunkserver 加入时会从各个 chunkserver 处收集 chunk 位置）
    master 和 chunkserver 之间会有周期性的心跳检测，用来发送命令和获取状态信息。

GFS 读取文件的简单过程：
文件名 ——> 获取文件对应的所有 chunk 名 ——> 获取所有的 chunk 的位置 ——> 依次到对应的 chunkserver 中读取 chunk

GFS 采取一些措施来确保 master 不会成为系统瓶颈：

  1. GFS 所有数据流都不经过 master，而是直接由 client 和 chunkserver 交互（数据流和控制流分离）
  2. GFS 的 client 会缓存 master 中的元数据，在大部分情况下，都无需访问 master
  3. 为了避免 master 的内存成为系统的瓶颈，GFS 采用了一些手段来节省 master 的内存（增大 chunk 的大小、对元数据进行定制化压缩——元数据小于64bit）

时至今日，大部分分布式系统还是会倾向于选择单个中心节点，因为单点瓶颈不像想象中那么难解决，非中心节点的实现难度也不如想象中那么可控

GFS 高可用设计

数据的高可用和结点的高可用可以看作是一致的

Master 的高可用设计（元数据的高可用设计）

  • master 的三类元数据中， namespace 和文件 chunk 的对应关系必须持久化（因为这些数据只存在 master 中）
  • GFS 有两个 master，正在使用的称为 primary master，还有一个 shadow master 作为备份使用
  • master 正常运行时，对元数据的所有修改，都要先记录日志，后修改真正的内存中的元数据（Operation log / write ahead log， 是整个 GFS 的核心）
  • primary master 会实时向 shadow master 同步 WAL，只有 shadow master 同步日志完成，元数据的修改才算成功

修改过程：
新增的元数据日志写入本地磁盘 ——> 把 WAL 传给 shadow master ——> 得到反馈后正式修改 primary master 元数据

如何实现自动切换？
如果 master 宕机，会通过 Google 的 Chubby 算法（本质上是共识算法）来识别并切换到 shadow master（切换是秒级的）
master 的高可用机制就和 MySQL 的主备机制非常像

chunk 的高可用设计（文件数据的高可用设计）

文件被拆分为一个个 chunk 来存储，每个 chunk 都有三个副本。因此，文件数据的高可用是以 chunk 为维度来保持的。

  • GFS 中，对一个 chunk 的每次写入，必须确保在三个副本中都写入完成，才视为写入完成

  • 一个 chunk 的所有副本都会具有完整的数据

  • 如果一个 chunkserver 宕机，其他两个副本仍然保存着这个 chunk 的数据

  • 如果宕机的这个副本在一段时间后仍然没有恢复，那么 master 就可以在另外一个 chunkserver 中重建一个副本，从而始终把 chunk 的副本数目维持在 3 个（可以设置）

  • GFS 维持每个 chunk 的校验和，读取时可以通过校验和进行校验，如果校验不匹配，chunkserver 会反馈给 master 处理，master 会选择其他副本进行读取，并重建此 chunk 副本

  • 为了减少对 master 的压力，GFS 采用了一种租约（lease）机制，把文件的读写权限下放给某一个 chunk 副本

  • master 可以把租约授权给某个 chunk 副本（primary），在租约生效的一段时间内（60s），对这个 chunk 的写操作直接由这个副本负责

  • 租约的主备只决定控制流走向，不影响数据流

chunk 副本的放置也很关键，GFS 中有三种情况需要 master 发起副本创建：

  • 新建 chunk
  • chunk 副本复制：发现副本所在的 chunkserver 宕机，导致 chunk 副本数小于预期值，新增一个 chunk 副本
  • 负载均衡：master 定期对 chunkserver 进行监控，如果发现某个 chunkserver 的负载过高，则把这个 chunk 副本搬迁到别的 chunkserver 中（创建新的删除旧的）

master 对副本位置的选择策略：

  • 新副本所在的 chunkserver 资源利用率较低
  • 新副本所在的 chunkserver 最近创建的 chunk 副本不多（防止 chunkserver 瞬间增加大量副本成为热点）
  • chunk 的其他副本不能在同一机架（机架/机房级别的高可用）

过期副本检测：

  • 对于每一个 chunk，master 会维护一个 chunk 版本号 来区别该副本是最新的还是过期的
  • 每当 master 为 chunk 授予租约的时候，就会增加它的版本号，然后通知副本进行更新，在一致的状态下 master 的所有副本都会记录这个版本号（如果此时某个副本不可达，则它的版本号不会进行更新）
  • 当 chunkserver 重启或者报告它的 chunk 以及对应的版本号的时候 master 会检测该 chunkserver 是否包含过期副本，master 通过周期性的垃圾回收删除过期副本。

无论是 master 中的还是 chunkserver 中的版本号，都会持久化保存到硬盘中。

GFS 的读写流程

GFS 的写入

  • 写入时要在三个副本都完成写入后才能返回写入结果
  • 采用两个非常先进的技术：
    • 流水线技术
      边接收边发送
    • 数据流与控制流分离技术？
      Client 会把文件数据发往离自己最近的一个副本，无论它是否是 primary（持有租约），这个副本在接收到数据后，立刻向其他副本转发（边接受边转发），这样就控制了数据流的流向，节省了网络传输代价。

GFS 写入流程：
1 & 2、Client 向 Master 询问要写入的 chunk 的租约在那个 chunkserver 上（Primary Replica），以及其他副本（Secondary Replicas）的位置（通常 Client 中就直接有缓存）。如果都没有租约，则 master 选择一个副本授予租约（非显式的）
3、Client 将数据推送到所有副本上，这一步骤会用到流水线技术，就近写入且写入数据流唯一（只是将数据推送到副本 chunkserver 上的一个内部 LRU 缓存上，还没有正式写入）
4、确认所有副本都收到数据后，Client 发送正式写入的请求到 Primary Replica，Primary Replica 接收到这个请求后，会对 Chunk 上的所有操作排序，然后按照这个顺序执行写入（Primary Replica 唯一确定写入顺序，保证副本一致性）
5、Primary Replica 将 Chunk 写入顺序同步给 Secondary Replica（此时，在 Primary Replica 上的写入已经成功）
6、Secondary Replica 将写入结果返回给 Primary Replica
7、Primary Replica 返回写入结果给 Client

  • 所有副本写入成功：Client 确认写入完成
  • 部分 Secondary Replica 写入失败/无响应：Client 认为写入失败，从 3 开始重新执行
    如果一个写入操作涉及到多个 Chunk，Client 会把它们分成多个写入来执行。

GFS 的读取

1、Client 收到读取一个文件请求后，首先查看自身缓存中是否有此文件的元数据信息，如果没有，则请求 Master 获取元数据信息并存储在自身缓存中
2、Client 计算文件偏移量对应的 chunk
3、Client 向离自身最近的 chunkserver 发送请求（如果此时发现 chunkserver 中没有自己所需要的 chunk，说明 Client 缓存失效，重新请求 Master 获取最新的元数据）
4、读取时进行 chunk 校验和的确认，校验和不一致则选择其他副本进行读取
5、Client 返回应用读取结果

GFS 的一致性模型

GFS 对文件系统的分层

GFS是一个松散的一致性检查的模型，通过简单高效的实现，来支持我们的高度分布式计算的应用。

  • consistent：一致的（无论在哪个副本读取，读到结果都一样）
  • defined：已定义的（文件发生了修改操作后，读取是一致的，且 Client 可以看到最新修改的内容，在 consistent 基础上还能与用户最新写入保持一致）
  • inconsistent：不一致的

LEC 4 - Primary-Backup Replication

Failures

Fail-Stop failures：如果发生失败，则停止运行机器

一些通过主备复制无法处理的错误：

  • 逻辑 bug
  • 配置错误
  • 恶意错误

一些通过主备复制可以处理的错误：

  • 地震
  • ……

Challenge

  • 判断 primary 是否真的出现故障（设计机制使得不会同时出现两个 primary，i.e. split-brain）
  • 保持 primary/backup 同步
  • 主机和备份机之间的切换（故障转移，fail over）

两种解决方案

  1. State transfer：每次发送转移的状态（CPU、内存等），一个操作可能会产生很多状态，比如单个操作写入千兆字节的数据，此时发送状态给备份机器的操作代价会很昂贵
  2. replicate state machine（RSM）：每次发送操作给备份机器，备份机器也执行一次该操作

复制操作的级别

  1. 应用程序级别的操作：例如文件追加写、写入等
  2. 机器级别的操作：复制经典的机器操作码，感觉更底层一点？是透明的！

VM-FT：显式的虚拟化

Goals

对客户机来讲，整个主备系统表现得和只有一台机器一样

对于一些常规操作（inr、dec……），在相同的初始状态执行一系列相同的指令后，主机和备机能够保持一致的状态，但是对于一些非确定性操作（non-deterministic operation），则需要一些特殊手段来保证主机和备机执行后仍能保持一致。

非确定性操作：

  • 输入数据包或时钟中断？
  • 多核并发操作 ——> 只使用单核处理器

系统架构

如上图，对于一个需要提供容错保护的 VM（the primary VM），我们运行一个备份 VM （backup VM）在另一台不同的物理服务器上，这台备份虚拟机执行与主虚拟机相同的指令来与主虚拟机保持同步。

主虚拟机与从虚拟机可以共享硬盘，主虚拟机在收到外界输入后同样将这些输入通过日志通道（logging channel）输送给备份虚拟机，主机与备份虚拟机执行相同的操作，但是备份虚拟机的输出会被丢弃，只有主虚拟机的输出会返回给客户端。

LEC 5 - Fault Tolerance: Raft (1)

Raft 是一个用来管理复制日志（replicated log）的共识算法（consensus algorithm）。
共识算法允许一组机器作为一个协调的团队工作，这让这个团队可以在其中一些成员出现故障时幸存下来。

Raft 的诸多新特性：

  • Strong leader：Raft 使用比其他共识算法更强的领导形式
  • Leader election：Raft 使用随机的计时器来选举 leader
  • Membership changes

Raft 的诸多优势：

  • 简单易懂
  • 完全能够满足实际系统的需要
  • 安全属性被形式化的指出和证明
  • 效率与其他算法类似

Lab2

Lab2-A（Leader Election）

tips

  1. time.Duration 可以直接与数字相乘，但是不能与变量相乘
    1
    2
    3
    4
    time.Second * 1      // √
    time.Second * num    // ×
    // 解决方法：
    time.Second * time.Duration(num)
  2. time.Since() 用来判断心跳是否超时
    1
    2
    // 相当于 time.Now().Sub(t)
    time.Since(t) > ELECTIONTIMEOUT

测试结果

Lab2-B（Log）

测试结果

image-20230511212022096

Lab2-C（Persist）

lab2-C 主要是实现 Raft 的持久化功能。如果某台服务器宕机重启，那么之前存储的所有信息将会丢失，所以需要添加持久化功能来使得重启的机器能够快速恢复到重启前的状态。

在 Lab2-C 中，我们需要实现两个方法：

  • persist()：进行持久化

  • readPersist()：读取持久化的状态

每当机器重启后，都会调用 readPersist() 方法来读取持久化的状态

在 Raft 中，需要持久化的信息主要有三个：

  • currentTerm
  • voteFor
  • log

我们需要对上面三个信息进行编码来保存，在读取时只需要对信息解码后赋值给运行中的 Raft 即可。编码会用到 lab 给的包 labgob，labgob 是对 Go 的 gob 封装，在原来的基础上增加了对变量首字母大写的检测，如果首字母不是大写则会报错。

遇到的一些问题：

  1. Lab2C 的 test 中会模拟许多不稳定的网络状态，如 RPC 信息丢失、长时延等，在运行 Unreliable 相关的测试用例时会报错：index commit 不一致。

    翻阅巨长的 log 经过几天痛苦的 debug 之后，找到了问题所在。Leader 在发出带有日志的 AppendEntriesRPC 后，可能这个 AppendEntriesRPC 响应很长时间后才发回来，在它前面已经有 RPC 执行过了并且对日志进行了修改，这个迟到的 RPC 就会覆盖前面 RPC 的操作。

    解决方法：严格按照 Figure2 中的步骤执行，不能偷懒（通过修改 AppendEntries Rule 3 相关的代码解决了该问题）

Lab2-D（Snapshot）

如果 Raft 服务器运行了超级长的时间，那么它所保存的日志就会非常非常大，这会占用很大的内存空间，一个解决方法是添加快照机制，定时对 Raft 拍摄快照，来将 Raft 的状态保存为快照。

服务恢复的两种方式：

  1. Replay log，将所有日志中的命令重新执行一次来重建状态（代价会比较昂贵）
  2. Snapshot