MIT6.5840分布式系统课程笔记
分布式系统工程
分布式系统是一组合作提供服务的计算机
主要是基础设施服务，存储、通信、计算
例如云存储、云计算、点对点共享
为什么要构建
并行处理：提高计算速度、吞吐量、有可靠和容错机制、可扩展性强
冗余：通过数据复制提高可靠性
隔离：提高安全性
难点
并发
相互作用
部分节点的失效
性能问题
各实验
实验 1：分布式大数据框架（如MapReduce）
实验 2：使用复制的容错 (Raft)
实验 3：一个简单的容错数据库
实验 4：通过分片扩展数据库性能
一个大目标
对上层应用程序隐藏分发的复杂性
权衡
容错性：尽管出现故障，服务仍然继续。数据冗余。
一致性
性能：可扩展的吞吐量。负载尽量均衡。
上述三点需要权衡，因为通信是慢且不可拓展。提供弱一致性以提高速度。
实施
RPC、线程、并发控制
MapReduce
对多TB数据集进行长时间计算
对开发人员友好，而不仅限于分布式专家使用
程序员只需定义Map和Reduce函数
其他细节被MR管理和隐藏
论文：[MapReduce: Simplified Data Processing on Large Clusters](rfeet.qrk (mit.edu))
过程
输入已经被分割为多个文件
每个文件作为任务，通过Map()生成中间数据
将中间数据传递给Reduce()产生最终输出
细节
- Map()和reduce()可以有多次交叉
- 同一阶段的Map()和Reduce()们并行执行，它们之间没有交互。允许多个交叉的阶段(如MRMRRMMR)。
- 由于并行计算，计算机数目与吞吐量成正比
- MR对于上层应用，隐藏了
- 将程序员编写的代码发送到服务器
- 跟踪任务进度
- 将中间数据乱序传递
- 负载均衡
- 处理失败恢复
- 限制较多，且无交互、无状态、无迭代、无实时或流处理
- 输入和输出存储在GFS集群上，GFS将文件进行了分割，并进行了数据冗余
- 性能限制：
- 早年的带宽限制
- 流量大头在于中间输出传递给Reduce和写入GFS
- 减少使用网络的措施
- 在存储了任务的服务器上直接进行Map，如一个服务器同时运行Map()和GFS存储，Map就可以直接读本地文件了
- Map()结果写入本地，Reduce()直接读取该Map()服务器的本地文件，不走GFS
- 增加中间文件的大小，进行少次大文件传输而非多次小文件传输
- 负载均衡方案：让较快的服务器完成更多的任务，多次分发给他
- 函数保证：Map()和Reduce()必须是纯函数，无状态、无文件IO、无交互、无外部通信
- 崩溃恢复的细节：
- Map
- worker节点不响应心跳
- coordinator知道该worker运行了什么Map任务，并让另一个worker做这个Map
- 如果Reduce已经拿到所有数据，那就不用重做这个Map了
- Reduce
- 已经完成的任务保存进GFS了，不用管
- 没完成的给另一个worker执行
- Map
- 其他错误
- 任务被多次分发：对于多个Map任务，只告诉Reduce一个Mapper；对于多个Reduce任务，GFS保证只有一个中间文件可见
- 一台机子很慢：将部分任务给worker完成
目前
对后世影响大
很少被使用
GFS
大型、快速、统一、容错的存储系统
给多个应用共享
针对批量大数据
具体实现
多个client、多个chunkserver、一个coordinator
文件被分割为64MB的chunk，分布在多个chunkserver上
- coordinator保存了两组映射：filename -> 一组chunkhandle、chunkhandle -> 一组chunkserver
client从coordinator获取目标文件的chunk信息，然后使用直接访问相关chunkserver(多个client会有并行读写，性能高)
chunk被冗余存储，同时写入时也会修改所有备份数据，当然只读其中一个
- 冗余方案(避免了多个client不同顺序的备份写入导致的数据不一致)：对于每个chunk，确定主备server，只写入主server，然后同步到备server
- 写入时涉及租约机制，保证只有一个主server，防止脑裂。每个chunk都有一个租约
允许client重试追加，因此会出现重复数据。可以在写入数据中添加校验和与ID来支持读操作的过滤去重
一致性支持
三种状态
defined：无并发的写入，所有客户端看到的都相同且正确
consistent：并发的写入，客户端看到的相同，但不一定正确。因为大写入被分解为多个小写入，并发交错写入会有问题
inconsistent：各个客户端看到的不相同。这种情况GFS会返回“写入错误”给client
结点宕机处理
- client宕机：写入操作对于主节点，告知或没告知
- chunkserver(包括主备节点)宕机：coordinator定期发心跳，更新缓存的映射信息，可能还需要复制副本数据到新分配的备节点上
- 备节点宕机：主节点重试，或者主节点返回错误让client重试(其实这次大概率也写入失败)
- 主节点宕机：等待租约到期，再分配一个新的主节点
- coordinator宕机(备份coordinator发的心跳没有回应)：将临界状态(映射)写入磁盘。重启恢复；或将更新操作发给备份coordinator
coordinator会进行版本记录，防止访问过时chunk
一些概括
全局集群文件系统，一个通用基础设施
将路由与存储分离
分片、并行吞吐
使用大文件(chunk)减少开销
主备机制，保证了写入的顺序。
租约避免脑裂
coordinator可能是瓶颈，它的存储空间和算力有限（Colossus行），同时对于coordinator的故障处理较差
不适合大量小文件场景（BigTable行）
一致性松散
主备复制
论文：The design of a practical system for fault-tolerant virtual machines (mit.edu)
为什么需要
通过复制实现高可用
避免硬件、设备问题导致的服务不可用
但是无助于操作员的操作失误和软件错误
怎么实现
- 主要方法：
- 快照复制：将快照发送到备份结点。但是快照很大，网络传输较慢。
- 状态机复制：对于相同启动状态的两个状态机，在相同的顺序执行相同的确定性操作，能到达相同的终态。所以只需复制追加的操作。
- 主要讨论的问题：
- 什么是状态
- 主节点是否要等待备份
- 备份结点如何知晓要进行接管
- 主副结点切换是否出现异常
- 结点切换如何加速并保证正确
- 副本级别：
- 应用程序：将高级的逻辑操作发送到备份结点
- 机器级别：转发机器事件(中断、网络数据包)(VMware实现了)
VMware案例
- 状态机复制：主从结点最初以相同的内存、寄存器、软件(OS等)开始，且运行的指令在主从节点上相同
- 但是如读取当前时间、网络数据包和磁盘读取等需要特殊处理。备份必须看到相同的时间和同样的顺序，并且要能产生同样的结果。
- 使用网络共享磁盘模拟本地磁盘
- 备份必须之后一个日志条目
- 允许重试，TCP会忽略重复的序列号，同时共享磁盘也会hash到同一位置
论文：
[In Search of an Understandable Consensus Algorithm(Extended Version)](In Search of an Understandable Consensus Algorithm (mit.edu))
raft论文中文翻译 In Search of an Understandable Consensus Algorithm(Extended Version)_西西弗的小蚂蚁的博客-CSDN博客](https://blog.csdn.net/zj_18706809267/article/details/125044750))
分区问题
计算机无法区分“宕机”与“网络损坏”，因为其表现形式都是无响应
会导致脑裂
需要一个决定切换服务器的自动化方案
投票机制允许一半一下的节点宕机(尽量保持服务器数量为奇数)
一个底层使用了raft的kv服务
一条命令的执行与集群一致：
client向leader的kv层发送PUT/GET命令
kv层调用Start(command)来调用raft
leader的raft添加命令到日志
leader向follower们发送AppendEntries RPC
follower们添加命令到日志
如果leader发现绝大多数人添加成功，就提交日志(执行命令)，并让follower们执行该条相同日志
提交后向client返回响应
日志
日志保存了状态机状态
保证了命令的执行顺序
方便leader查看follower是否一致
在内存中保存，方便重发，同时支持“未提交”到“提交”状态的转变
可以持久化以保存leader状态
集群中日志可能会不同，但最终会收敛到相互一致
只执行大多数节点都添加的，稳定的日志
Raft细节
- 单领导者：保证命令执行的顺序
- 使用任期作为逻辑时钟，并限制唯一leader，防止脑裂
- 各follower节点在一个随机时间内未收到leader发来的心跳，就会变为candidate开始选举
- 通过“大多数”、“同一个任期只能投一次票”，保证一个任期最多一个leader
- 心跳抑制新的选举
- 随机的选举超时时间防止多个节点同时开始选举
- 心跳间隔必须小于选举超时时间
论文：
[In Search of an Understandable Consensus Algorithm(Extended Version)](In Search of an Understandable Consensus Algorithm (mit.edu))
raft论文中文翻译 In Search of an Understandable Consensus Algorithm(Extended Version)_西西弗的小蚂蚁的博客-CSDN博客](https://blog.csdn.net/zj_18706809267/article/details/125044750))
处理日志不一致
Raft保证当选的leader拥有所有已提交的日志，防止出现“承诺client成功，但无日志”的情况
- 已提交：即使故障也不会丢失的操作；系统知道已提交
Raft让follower只能从leader上获取日志，client只与leader交流，保证执行命令的有序
leader发出的心跳带有leader持有日志的信息，故follower可以拿来判断自身日志是否最新，同时返回结果告诉leader自己的日志是否最新。leader维护了对每个节点的日志情况(有效长度)，并根据这个决定下一次心跳要发给对应节点的日志条目。
日志每个条目除了指令还有任期，相同命令、不同任期的条目最终会被覆盖掉(follower删除与leader不同的日志尾部)，以保证follower日志与leader一致()
只能是日志最新的结点成为leader，不能是最长的，因为最长的不一定是最新的，最新的日志可能已经被提交，若最长的成为leader，则会忽视掉最新日志。
加速日志的回滚(先让follower的前缀与leader一致)：follower在心跳响应中放入第一个冲突的日志信息
持久化
崩溃并重启，需要持久化：
1. 已持有的日志：如果这个节点有最新日志，允许他重启后，集群内的新leader获得最新日志 1. 当前任期：避免同意被取代的结点发来的投票请求 1. votedFor：避免出现宕机前投了票、宕机后又投了票leader保存的一些集群内所有节点的日志信息不需要持久化，因为会慢慢收敛，重回正常
- 运行很久的系统，慢慢收敛恢复数据太慢，可以使用快照+一点尾部日志的恢复
使用快照来日志压缩
- 定期将已提交的日志保存为磁盘上的快照，然后丢弃这些已持久化的日志
- 使用了快照会导致日志索引不再从0开始，恢复数据需要改变策略
- 不使用心跳而是一个新的RPC来让follower读取快照
读操作
新leader可能没有执行最新的put操作(老leader执行了)，所以不能马上响应client的PUT操作
- 还是要通过收敛(GET操作加入日志、发送RPC使数据一致化)直到知晓自己的最新PUT已提交
一种方法：租约，规定一个结点是否有权响应只读请求(不一定是当前leader，也可以是老的、租约还未过期的leader)
不过实践中某些时候人们能忍受看到老数据(这种场景就不用出各种方案，并且性能会更高)
重传
- 保证幂等性
- client为请求设置ID和顺序号
- 同一个请求，重发时请求ID不变
- 顺序号防止乱序执行
- kv服务维护ID去重表
- 崩溃恢复如果使用了快照，快照也要包含这个去重表
- 采取某些措施减少去重表大小，如当前已连续的顺序号前的请求全部拒绝
论文：
- [The Go Programming Language and Environment](The Go Programming Language and Environment | May 2022 | Communications of the ACM)
Go做的事
依赖导入
- 需要显式导入包
- 避免导入依赖相关的所有依赖(如导入A包，但A中函数Func的参数是与B包相关的内容，如果还需导入B包，那一次导入会导入大量依赖)
- 使用大小写区分公开和私有，减少语法重量
类型
- 提供引用、字符串、数组、hash表和切片(无自带的Set等数据结构)
- 不支持隐式类型转换
并发
方便程序员管理的线程：goroutine
- 底层使用多路复用
- 提供阻塞IO
提供channel以便goroutine的通信和同步
也提供了mutex、cond、atomic等较低层的并发控制类型
提供了竞态检测工具 -race
安全
解决了部分C和C++的问题，减少了因程序员失误导致的系统问题
提供unsafe包编写底层系统
自带一套加密库
完整性
自带一套开发需要的核心部分(如加密包、网络包)等，但也不滥竽充数，防止出现选择障碍
集成了一套编译、测试等的工具包
一致性
- 性能一致
- 不会出现“缓慢启动”的情况，程序在各生命周期的性能一致
- 完全并发的GC，开销较小
- 在不同系统架构下效果一致
- 不同时间点下一致，官方承诺新版本会向后兼容
辅助工具
大量的工具、插件
库
- 作为适合分布式计算的语言，无中央服务器，通过URL获取远程存储库中托管的包
- 也可以发布静态文件包，以支持实现私有服务
帖子：[Testing Distributed Systems for Linearizability](Testing Distributed Systems for Linearizability (anishathalye.com))
一致性模型
产生了很多模型
- 线性化
- 最终一致性
- 因果一致性
- 分叉一致性
- 可串行化
- 顺序一致性
因为需要在 性能/便利性/可靠性上做权衡
线性化模型
强一致性
需要串行组件
可用性差
最终一致性模型
更受欢迎
性能更好、更大的容错空间
可能读到旧数据，不利于系统安全(权限、支付)
一致性差
权衡
可用性和一致性不能两者兼得
链复制技术
一系列服务器组成链表(保证有序、线性化写入)
头结点接收写请求，并按配置的顺序(有序)，依次向后发送更新请求并进行响应的更新
- 当前写入时，首先将数据缓存，然后将写入请求发给下一个节点(不会像P/R模型一样primary结点负载大)，并等待下一个节点返回ACK
- 下一个节点返回ACK后，才将缓存中的数据持久化到本地，然后给上一个结点返回ACK
- 在等待ACK期间，结点不进行其他操作(线性化)
- 在写入头结点后立刻返回给client写成功响应(高吞吐)
尾结点接收读请求(该结点负载大)(同一时间获得同一数据，强一致)，将尾结点上的数据和请求结果返回给客户端
易知后面结点的数据一定是前面数据的前缀
结点宕机情况
- 写操作
- 头结点：写操作直接失败，客户端报错
- 中间结点和尾结点：反正已经返回客户端成功了。恢复后比较本地存储和前一个结点的数据，并恢复数据。
- 读操作：
- 尾结点：读操作直接失败
- 写操作
可用：
- 多个结点进行数据冗余，
- 额外的配置和监听服务器，监听集群内各节点状态，在节点宕机时分配备份节点。
容忍最多N-1个结点失败
CRAQ
允许任何节点处理读请求，并继续保持强一致
双向链表
不能处理脑裂问题
TODO
事务是数据库中的老生常谈了
ACID
- Atomic
- Consistent
- Isolated
- Durable
分布式事务 = 原子提交 + 并发控制
- 并发控制
- 悲观锁：访问前加锁
- 乐观锁：不加锁，用变量进行记录
- 如果并发小，乐观锁性能好，否则悲观锁
- 并发控制
两段锁协议（2PL）：用于单机事务中的一致性与隔离性
写操作时加锁
所有的解锁操作必须在加锁操作之后(即分为两个阶段)
可能产生死锁
是一种
两阶段提交(2PC)：用于分布式事务
- 将事务分为准备阶段和提交阶段
- 准备阶段：事务管理器给每个参与者发送Prepare消息，每个参与者在本地执行事务，并写Undo、Redo日志
- 提交阶段：如果事务管理器收到了失败或超时消息，就给每个参与者发回滚消息，否则发提交消息。参与者根据发来的消息执行操作，然后释放事务中使用的锁资源。
- 可用性差，因为加锁会阻止其他事务，同时也有无限期阻塞的可能。必须所有服务器都活着才有效
- 将事务分为准备阶段和提交阶段
论文：[Spanner: Google’s Globally-Distributed Database](spanner.pdf (mit.edu))
Spanner
使用Paxos作为分布式一致性协议
非阻塞的读，且只读事务不使用锁机制
会随着时间推移，自动对数据进行重新分片，以平衡各节点负载
支持通用事务
在使用了时间戳的情况下，支持跨越全球的一致性的读操作
- 时间戳分配给数据，更像一个多版本数据库
- 时间戳反应了事务的执行顺序
- 使用了具有原子时钟和GPS的TrueTime API来决定时间戳标记。
结构
并发控制
论文：[No compromises: distributed transactions with consistency, availability, and performance](farm-2015.pdf (mit.edu))
乐观并发控制(OCC)
论文：[Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Servic](atc22-dynamodb.pdf (mit.edu))
论文较新，解读较少，这里放译文：[译文]Amazon DynamoDB - A Scalable, Predicably Performant, and Fully Managed NoSQL Database Service - 知乎 (zhihu.com)
Resilient Distributed Datasets: A Fault-Tolerant Abstraction for In-Memory Cluster Computing
RDD
- RDD：弹性分布式数据集，是一种分布式内存（集群上的内存存储）的抽象，即支持数据重用、容错、并行
- 是只读、分局记录的集合
- 只能通过稳定的物理存储或者其他RDD的数据集来创建
- 用户可以控制哪些RDD被缓存、哪些被分区
Spark
Spark是一种RDD系统，提供了Scala接口(简洁、高效)
Spark中RDD都是对象，可以操作
Spark中RDD默认存储到RAM，RAM不够时部分写到磁盘上
Spark使用lineage进行容错恢复，只需重新计算丢失节点，不需要回滚全部
Spark可以利用数据局部性，提高性能
RDD适用于：
对数据集中的所有元素使用同一操作的批量应用。在这种情况中，RDD可通过lineage高效记住每个转换，并且无需大量数据即可恢复丢失分区。
RDD不适用于：
在共享状态下的异步细粒度的更新，比如web存储系统，或增量式web爬虫，这些更适合于用传统的日志更新，或是数据检查点。MR的局限性
- 需要准备好批量处理的大量数据
- 所有数据处理的方式相同
- 不适用于交互性的
比起MR，提高了表现力和性能，可以描述数据流图，操作内存比操作磁盘更快
论文：Scaling Memcache at Facebook
构建缓存层的最佳实践
大部分业务都是读多写少，缓存层能保护DB
缓存策略
- 读时，先从缓存获取数据，获取失败则将数据从DB加入缓存
- 写时，先更新DB，再将缓存中数据删除
- 不一定必须用分布式事务保证一致性(性能要求)
业务增加时，也需要缓存层横向扩容，通过一致性hash建立memcache集群
读取多个数据，且数据有依赖关系时，会产生一个DAG
对于可能会从一个memcache上读多次的情况，在业务层减少读取次数，一次读出
因为读对错误的容忍性较高，使用UDP通信(此外还在拥塞控制上进行了处理，动态找到窗口大小)
通过对数据发放租约id，避免读到并使用过期数据
防止缓存穿透
- 控制lease的发放速率，并让请求拿过期数据或重试
- 如果容忍过期数据，可以缓存过期数据
- 对各个缓存按访问频率分类，即热数据、冷数据这样的
- 一个缓存节点建立多个备份结点，写效率换读效率
可以使用DB的日志，实现最终一致性
在不同地域建立数据中心和缓存服务
论文：Zanzibar: Google’s Consistent, Global Authorization System
Zanzibar
一个谷歌内部的分布式的鉴权应用
结合了Spanner进行全球存储
为谷歌的众多服务提供了鉴权服务，蒋授权逻辑提取到公共服务中，统一用户模型
Zanzibar是内部系统，服务的对象都是谷歌的服务，信任它们的代码
权限模型：
- ACL：对每个存储对象，增删查改每个操作都设置一个可供修改的条目
Zanzibar部署在全球
Zanzibar不是线性化设计
利用 Spanner 的线性化和即时快照读取
利用特定的安全要求来允许使用过去的快照
用时间戳标记缓存数据而不是试图保持最新
容错全部交给Spanner
。。。。。。。。。。。。。。。。。。。。。。。。TODO
论文：Practical Byzantine Fault Tolerance
PBFT
一种状态机副本复制算法，允许(N-1)/3个节点出错
PBFT算法的过程如下:
- 客户端向主节点发送请求操作消息, 主节点接收到请求操作消息并校验正确后, 保存该消息, 并依据该请求操作消息生成预准备消息, 广播给各备份节点.
- 各备份节点接收到预准备消息并校验正确后, 保存该消息, 并以该预准备消息为依据, 生成准备消息广播给主节点和其他备份节点.
- 各存储副本的节点接收到准备消息并校验正确后, 保存该消息, 并以该准备消息为依据, 生成提交消息给客户端、主节点和其他备份节点.
- 各存储副本的节点接收到 (2n + 1)/3 个提交消息并校验正确后, 则执行来自客户端的请求操作消息里的操作.
- 客户端接收到 (n + 2)/3 个提交消息, 验证正确并接受后, 便认为该消息已被副本节点集群所承认与执行. 这里的客户端接受 (n + 2)/3 个提交消息而不是 (2n + 1)/3 个的原因在于失效的节点数量不超过 (n − 1)/3, 因此 (n − 1)/3 + 1 个一致响应必定能够保证结果是正确的.
论文：Bitcoin: A Peer-to-Peer Electronic Cash System
比特币
一个开放/无权限的系统，服务器数量都未知(很难投票)
提出l了一种解决双花问题的P2P网络：该网络把 交易(transactions) 哈希结果记录到一个基于 PoW共识机制 不断增长的链上，用来给交易打上时间戳形成一条不可篡改的记录
P2P的电子货币可以在无第三方金融机构的情况下进行在线支付
数字签名技术可以用于防止双花(double-spending)
最长链会作为已发生事件的载体，同时其自身也代表了最强大的CPU算力池
只要大部分算力由节点控制而不是合作用于攻击网络，他们将始终创造比攻击者更长的链（也就是攻击该网络需要拿下 >50% 的算力）
消息会尽可能广播。
节点可以随时加入和离开网络。
签名机制如下
在没有可信第三方的情况下，交易需要被广播（transactions must be publicly announced），同时还需要一个可以让参与者对他们接受到的信息达成一致历史顺序的系统
每个Timestamp包含了对上一个Timestamp的hash，如此循环形成链。时间戳服务器通过对要加时间戳的项目区块进行hash并且广播hash值来工作
POW：工作量证明包括检测hash结果中的某个值，例如：SHA-256算法 hash值以一些0 bit开头，就是计算结果满足前缀有多少个0才满足PoW机制，平均所需工作量是0的位数的指数倍，工作量证明难度由根据每小时区块产生的平均值确定。如果它们生成得太快，则难度会增加。
论文：Ethereum White Paper (2014)
智能合约
- 一种带有内置完整成熟的图灵完备编程语言的区块链，可用于创建“合同”，该合同可用于编码任意状态转换函数，从而允许用户创建上述任何系统，以及我们尚未想到的许多其他功能，只需通过几行代码编写逻辑即可。
内容
- 标题: MIT6.5840分布式系统课程笔记
- 作者: urlyy
- 创建于 : 2023-08-16 21:06:01
- 更新于 : 2024-12-06 00:17:51
- 链接: https://urlyy.github.io/2023/08/16/MIT6-5840分布式系统课程笔记/
- 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。