MIT 6.824 Distributed Systems 学习笔记

Schenk

NotesPaper Reading

更新于：2022年5月6日

字数：18k字

时长：63分钟

次浏览

Paper Reading

MapReduce

一个编程模型，用于大规模并行计算，以及采用re-execution进行容错处理

$Map$：输入键值对，输出一系列中间键值对，并将相同的中间键排在一起传递到 $Reduce$ 函数
$Reduce$：输入中间键 $I$ 以及其对应的一系列中间值，对其进行合并，最后输出

实现

Master数据结构

Master存储：

每个map和reduce任务的状态（idle, in-progress, completed）
各个worker的标识
每个已完成的map任务的R个中间文件的位置和大小

容错

Worker Failure
Master Failure
Semantics in the Presence of Failures

本地优化

输入文件被划分为64MB的块，每个块会冗余存放在多个机器上
Master会将map任务尽可能分配到一个保存了对应副本的机器或其周围的机器上

任务粒度

M和R应该远大于worker机器的数量

备份任务

为了解决单点效率瓶颈，在MapReduce任务快完成时，master将剩余in-progress机器仍在执行的任务作为备份任务分配给其他机器

改进

Partitioning Function（如何分配R个输出文件）
Ordering Guarantees
Combiner Function（对重复的中间结果合并）
Input and Output Types（自定义类型）
Side-effects
Skipping Bad Records（用户程序对特定的数据可能有bug）
Local Execution（方便Debug）
Status Information（日志）
Counters

Google File System

Overview

假设

系统组件经常故障，因此需要持续监控，错误检测，容错处理，自动恢复
存储大量文件，有几百万100MB或以上的文件，多GB的文件很常见，需要高效管理，小文件不需要优化
存在两种读：大规模连续读和小规模随机读
有很多大规模连续写（添加内容），也需要支持小规模随机写但不要求其性能
高效处理多用户同时向同一个文件添加内容，保证原子性并减少开销
高持续带宽比低延迟更重要

架构

单个Master：必须最小化其参与的读和写，防止成为瓶颈
chunk大小：选择较大的64MB
- 优势：
  1. 减少client与master的交互
  2. client更有可能在同一个chunk上进行大量操作，减少网络开销
  3. 减少master上存储的metadata
- 劣势：若很多client访问同一个文件，则这个chunk会成为hot spot
Metadata：存放在master的内存中（前两个还会记录在operation log中进行持久化存储）
- 文件和chunk的命名空间
- 文件到chunk的映射
- 各个chunk副本的位置（通过启动时的轮询和之后的心跳消息获取）
一致性模型：保证文件命名空间的改变是原子性的

系统交互

尽可能减少master的参与

Leases

为了保证各副本的一致性改变，master通过将chunk lease给其中一个副本使其成为primary，然后primary选择一个改变的顺序，并同步给其他副本

数据流

原子性record append

快照snapshot

Master操作

命名空间管理和读写锁
副本放置
- 最大化可靠性和可用性
- 最大化网络带宽利用率
chunk的create、re-replicate、rebalance
垃圾回收机制：周期性扫描
过期副本探测：master维护chunk版本号

容错和诊断

高可用性
- 快速恢复
- Chunk复制
- Master复制
数据完整性：chunk分为64KB的块，每个块对应32bit的checksum
诊断工具：诊断log记录重要的事件和所有RPC请求/回复

Fault-tolerant virtual machines

基本FT设计

确定性重播实现

写入log文件

挑战：
- 正确捕获所有输入和对确定执行必要的非确定因素
- 正确将输入和非确定因素应用到备份VM上
- 不造成性能损失

FT协议

**输出要求：**若备份VM接替了故障的主VM，则备份VM将继续与主VM完全一致地向外界输出
**输出规则：**在备份VM收到并确认与生成输出的操作相关的log之前，主VM不能向外部世界输出

检测和响应故障

FT的实际实现

启动和重启FT VM

关键是以相同状态启动备份VM的机制：FT VMotion

管理Logging Channel

其他重要实现

FT VM上的操作
Disk IO的实现
Network IO的实现

Course Notes

FT VM

复制状态机

复制状态机基于这个事实：我们想复制的大部分的服务或者计算机软件都有一些确定的内部操作，不确定的部分是外部的输入
如果有两台计算机，如果它们从相同的状态开始，并且它们以相同的顺序，在相同的时间，看到了相同的输入，那么它们会一直互为副本，并且一直保持一致
VMware FT论文讨论的都是复制状态机，并且只涉及了单核CPU
在多核的机器中，两个核交互处理指令的行为是不确定的，所以就算Primary和Backup执行相同的指令，在多核的机器中，它们也不一定产生相同的结果
如果我们要创建一个新的副本，我们别无选择，只能使用状态转移，因为新的副本需要有完整状态的拷贝。所以创建一个新的副本代价会很高

非确定性事件

客户端输入：

当我们说输入的时候，我们实际上是指接收到了一个网络数据包
- 数据包中的数据
- 提示数据包送达了的中断
对于Primary和Backup，中断最好要在相同的时间，相同的位置触发，否则执行过程就是不一样的，进而会导致它们的状态产生偏差。所以，我们不仅关心网络数据包的内容，还关心中断的时间

怪异指令：

随机数生成器
获取当前时间的指令，在不同时间调用会得到不同的结果
获取计算机的唯一ID

多CPU并发：

当服务运行在多CPU上时，指令在不同的CPU上会交织在一起运行，进而产生的指令顺序是不可预期的

输出控制

Primary和Backup虚机都会生成回复报文，之后通过模拟的网卡送出，但是只有Primary虚机才会真正的将回复送出，而Backup虚机只是将回复简单的丢弃掉
控制输出规则：直到Backup虚机确认收到了相应的Log条目，Primary虚机不允许生成任何输出
Primary会等到Backup已经有了最新的数据，才会将回复返回给客户端。这几乎是所有的复制方案中对于性能产生伤害的地方，在某个时间点，Primary必须要停下来等待Backup

Test-and-Set服务

Primary和Backup都在运行，但是它们之间的网络出现了问题，同时它们各自又能够与一些客户端通信，这样会产生Split Brain问题
Test-and-Set服务会在内存中保留一些标志位，当你向它发送一个Test-and-Set请求，它会设置标志位，并且返回旧的值，Primary和Backup都需要获取Test-and-Set标志位，类似锁
为了能够上线，Primary和Backup或许会同时发送一个Test-and-Set请求给Test-and-Set服务。当第一个请求送达时，Test-and-Set服务会说，这个标志位之前是0，现在是1。第二个请求送达时，Test-and-Set服务会说，标志位已经是1了，你不允许成为Primary

Raft

Majority Vote

在任何时候为了完成任何操作，你必须凑够过半的服务器来批准相应的操作
如果系统有 $2F+1$ 个服务器，那么系统最多可以接受 $F$ 个服务器出现故障，仍然可以正常工作

Raft初探

Raft会以库（Library）的形式存在于服务中：如果有一个基于Raft的多副本服务，那么每个服务的副本将会由两部分组成：应用程序代码和Raft库

日志

Log是Leader用来对操作排序的一种手段，Log是一些按照数字编号的槽位（类似一个数组），槽位的数字表示了Leader选择的顺序
在一个Follower收到了操作，但是还没有执行操作时，需要将这个操作存放在某处，直到收到了Leader发送的新的commit号才执行，对于Raft的Follower来说，Log是用来存放临时操作的地方
Leader需要在它的Log中记录操作，因为这些操作可能需要重传给Follower，即使对那些已经commit的请求，为了能够向丢失了相应操作的副本重传，也需要存储在Leader的Log中
可以帮助重启的服务器恢复状态，每个Raft节点都需要将Log写入到它的磁盘中，这样它故障重启之后，Log还能保留
**注：**从Log上无法直接观察出某一条日志是否已经commit

应用层接口

在Raft集群中，每一个副本上，这两层之间主要有两个接口

第一个接口是key-value层用来转发客户端请求的接口。如果客户端发送一个请求给key-value层，key-value层会将这个请求转发给Raft层，并说：请将这个请求存放在Log中的某处。这个接口实际上是个函数调用，称之为Start函数。这个函数只接收一个参数，就是客户端请求。key-value层说：我接到了这个请求，请把它存在Log中，并在committed之后告诉我

另一个接口是，随着时间的推移，Raft层会通知key-value层：你刚刚在Start函数中传给我的请求已经commit了。这个向上的接口以go channel中的一条消息的形式存在。Raft层会发出这个消息，key-value层要读取这个消息。所以这里有个叫做applyCh的channel，通过它你可以发送ApplyMsg消息

key-value层需要知道从applyCh中读取的消息，对应之前调用的哪个Start函数，所以Start函数需要返回这个请求将会存放在Log中的位置（index）以及当前的任期号（term number）和一些其它我们现在还不太关心的内容

在ApplyMsg中，将会包含请求（command）和对应的Log位置（index）。所有的副本都会收到这个ApplyMsg消息，它们都知道自己应该执行这个请求，弄清楚这个请求的具体含义，并将它应用在本地的状态中。所有的副本节点还会拿到Log的位置信息（index），但是这个位置信息只在Leader有用，因为Leader需要知道ApplyMsg中的请求究竟对应哪个客户端请求（进而响应客户端请求）

Leader选举

Raft生命周期中可能会有不同的Leader，它使用任期号（term number）来区分不同的Leader
Followers（非Leader副本节点）不需要知道Leader的ID，它们只需要知道当前的任期号
每个Raft节点都有一个选举定时器（Election Timer），如果在这个定时器时间耗尽之前，当前节点没有收到任何当前Leader的消息，这个节点会认为Leader已经下线，并开始一次选举，当前服务器会增加任期号（term number），因为它想成为一个新的Leader
之后，当前服务器会发出请求投票（RequestVote）RPC，这个消息会发给所有的Raft节点
如果有一场新的选举，有可能之前的Leader仍然在运行，并认为自己还是Leader。我们也需要关心，在不知道有新的选举时，旧的Leader会有什么样的行为？
确保每个任期最多只有一个Leader：为了能够当选，Raft要求一个候选人从过半服务器中获得认可投票。每个Raft节点，只会在一个任期内投出一个认可选票
如果你赢得了选举，你需要立刻发送一条AppendEntries消息给其他所有的服务器。除非是当前任期的Leader，没人可以发出AppendEntries消息

选举定时器

任何一条AppendEntries消息都会重置所有Raft节点的选举定时器：每一次一个节点重置自己的选举定时器时，都需要重新选择一个随机的超时时间
Raft不能完全避免分割选票（Split Vote），但是可以使得这个场景出现的概率大大降低。Raft通过为选举定时器随机的选择超时时间来达到这一点
选举定时器的超时时间需要至少大于Leader的心跳间隔，实际上由于网络可能丢包，这里你或许希望将下限设置为多个心跳间隔
超时时间的上限：
- 最大超时时间影响了系统能多快从故障中恢复，这里的上限越大，系统的恢复时间也就越长
- 不同节点的选举定时器的超时时间差必须要足够长，使得第一个开始选举的节点能够完成一轮选举：至少需要大于发送一条RPC所需要的往返（Round-Trip）时间

日志恢复

Leader使用一种备份机制来探测Followers的Log中，第一个与Leader的Log相同的位置
在获得位置之后，Leader会给Follower发送从这个位置开始的，剩余的全部Log

选举约束

为了保证系统的正确性，并非任意节点都可以成为Leader
在处理别节点发来的RequestVote RPC时，需要做一些检查才能投出赞成票：
- 候选人最后一条Log条目的任期号大于本地最后一条Log条目的任期号
- 或者，候选人最后一条Log条目的任期号等于本地最后一条Log条目的任期号，且候选人的Log记录长度大于等于本地Log记录的长度

快速恢复

让Follower返回足够的信息给Leader，这样Leader可以以任期（Term）为单位来回退，而不用每次只回退一条Log条目
- XTerm：Follower中与Leader冲突的Log对应的任期号。Leader会在prevLogTerm中带上本地Log记录中，前一条Log的任期号。如果Follower在对应位置的任期号不匹配，它会拒绝Leader的AppendEntries消息，并将自己的任期号放在XTerm中。如果Follower在对应位置没有Log，那么这里会返回 -1
- XIndex：Follower中，对应任期号为XTerm的第一条Log条目的槽位号
- XLen：如果Follower在对应位置没有Log，那么XTerm会返回-1，XLen表示空白的Log槽位数
case1：
1
2
S1: 4 5 5
S2: 4 6 6 6
- Follower（S1）会返回XTerm=5，XIndex=2。Leader（S2）发现自己没有任期5的日志，它会将自己本地记录的，S1的nextIndex设置到XIndex，也就是S1中，任期5的第一条Log对应的槽位号。所以，如果Leader完全没有XTerm的任何Log，那么它应该回退到XIndex对应的位置（这样，Leader发出的下一条AppendEntries就可以一次覆盖S1中所有XTerm对应的Log）
case2：
1
2
S1: 4 4 4
S2: 4 6 6 6
- Follower（S1）会返回XTerm=4，XIndex=1。Leader（S2）发现自己其实有任期4的日志，它会将自己本地记录的S1的nextIndex设置到本地在XTerm位置的Log条目后面，也就是槽位2。下一次Leader发出下一条AppendEntries时，就可以一次覆盖S1中槽位2和槽位3对应的Log
case3：
1
2
S1: 4
S2: 4 6 6 6
- Follower（S1）会返回XTerm=-1，XLen=2。这表示S1中日志太短了，以至于在冲突的位置没有Log条目，Leader应该回退到Follower最后一条Log条目的下一条，也就是槽位2，并从这开始发送AppendEntries消息。槽位2可以从XLen中的数值计算得到

持久化

Log需要被持久化存储的原因是，这是唯一记录了应用程序状态的地方
currentTerm和votedFor都是用来确保每个任期只有最多一个Leader
- 如果一个服务器收到了一个RequestVote请求，并且为服务器1投票了，之后它故障。如果它没有存储它为哪个服务器投过票，当它故障重启之后，收到了来自服务器2的同一个任期的另一个RequestVote请求，那么它还是会投票给服务器2，因为它发现自己的votedFor是空的
- 存储currentTerm是为了防止任期回退
安全的做法是每次你添加一个Log条目，更新currentTerm或者更新votedFor。可以通过一些批量操作来提升性能。例如，只在服务器回复一个RPC或者发送一个RPC时，服务器才进行持久化存储
如果Leader收到了一个客户端请求，在发送AppendEntries RPC给Followers之前，必须要先持久化存储在本地；在回复AppendEntries 消息之前，Followers也需要持久化存储这些Log条目到本地
服务器重启时，commitIndex、lastApplied、nextIndex、matchIndex可以被丢弃，因为Leader可以通过检查自己的Log和发送给Followers的AppendEntries的结果，来发现哪些内容已经commit了

日志快照

快照背后的思想是，要求应用程序将其状态的拷贝作为一种特殊的Log条目存储下来
- 对于大多数的应用程序来说，应用程序的状态远小于Log的大小（如KV数据库）
如果Raft要求应用程序做一个快照，Raft会从Log中选取一个与快照对应的点，然后要求应用程序在那个点的位置做一个快照，然后我们可以安全的将那个点之前的Log丢弃；我们还需要为快照标注Log的槽位号
- 只要Raft持久化存储了快照，快照对应的Log槽位号，以及Log槽位号之后的所有Log，那么快照对应槽位号之前的这部分Log可以被丢弃
重启的时候，必须让Raft有方法知道磁盘中最近的快照和Log的组合，并将快照传递给应用程序。所以应用程序不仅需要有能力能生成一个快照，它还需要能够吸纳一个之前创建的快照，并通过它稳定的重建自己的内存
如果Leader发现有任何一个Follower的Log落后于Leader要做快照的点，Leader可以丢弃Follower需要的Log，但需要某种机制让AppendEntries能处理某些Follower Log的结尾到Leader Log开始之间丢失的这一段Log，即InstallSnapshot RPC
- 当Leader回退到了自己Log的起点，将不能再回退。这时，Leader会将自己的快照发给Follower，之后立即通过AppendEntries将后面的Log发给Follower

线性一致

一个服务是线性一致的，那么它表现的就像只有一个服务器，并且服务器没有故障，这个服务器每次执行一个客户端请求，并且没什么奇怪的事情发生
- 如果执行历史整体可以按照一个顺序排列，且排列顺序与客户端请求的实际时间相符合，那么它是线性一致的
- 一个线性一致的执行历史中的操作是非并发的，也就是时间上不重合的客户端请求与实际执行时间匹配
确定执行顺序：
- 如果一个操作在另一个操作开始前就结束了，那么这个操作必须在执行历史中出现在另一个操作前面
- 执行历史中，读操作，必须在相应的key的写操作之后
对于读请求，线性一致系统只能返回最近一次完成的写请求写入的值

Client交互

源自Raft作者博士论文Ch6

寻找Leader

Client发送请求到随机节点，节点有两种处理方式：
1. 节点可能通过Leader的AppendEntries RPC知道了LeaderId，从而可以将此信息传递给client；
2. 节点作为代理，将请求转发给Leader。
Raft必须防止过期的Leadership信息
- Leader：某个节点处于Leader的状态，但不是当前整个集群的Leader，若client将请求发送给此节点，将永远得不到回复，因为该节点不能得到大部分节点的同意。解决方案： 若Leader没有收到集群中大部分节点的心跳回复，则会自动退位，使得client能请求其他节点
- Follower：当Follower开启一轮选举或任期改变时，不能回复client的请求，防止几个节点相互redirect
- Client：若client与节点失去连接，需要随机请求另一个节点

实现线性一致

Raft中，复制状态机可能会apply一条命令多次，为了实现线性一致，不能允许重复执行
节点保存client操作的结果，当client重发相同请求时，直接回复结果而不执行请求
给与每个client一个唯一标识，client为每条命令分配一个唯一序号
每个节点的状态机为每个client维护一个session，来跟踪client的最新命令序号以及响应的回复
当节点收到同一个client相同序号的命令时，直接回复session中的结果
在并发环境下，节点维护的session应该包含多个序号-回复pair，client在每个请求中包含其还未收到回复的最小的序号，节点根据此来丢弃更小的序号-回复pair
由于存储空间有限，在client session越来越多之后，节点必须丢弃一些client session
- 所有节点必须对丢弃的session达成共识，因此session丢弃必须是确定性的，可选方案：
  - 设置session数量上限，根据LRU (Least Recently Used) 策略丢弃session
  - 基于时间共识来丢弃session
- 处理在session过期后仍不断发送请求的client，可选方案：
  - 为该client重新分配一个新的session，但这有命令重复执行的风险（在该client上一个session中可能已经执行过该命令）
  - 节点区分新client和session过期的client：新client发送RegisterClient RPC来请求一个session，若节点收到的命令请求中包含过期的session，则返回error

更高效地执行只读请求

只读请求可以直接进行而不记录log (防止对磁盘的同步写) ，但是需要一些额外处理，否则可能回复过时数据
1. 若Leader还没将自己任期的log条目标记为committed，则等待标记完成。由于Leader刚上任时不知道自己的哪些log已经commit了，所以他需要在自己任期开始时往自己的log中添加一条空的 no-op 条目，当该条目commit之后，Leader的 commitIndex 至少和其他节点一样大；
2. Leader保存一个本地变量 readIndex 来记录当前的 commitIndex ，这将被用作是请求操作的状态的最低版本
3. Leader需要确保自己没有被更新的Leader取代，为此他发起一轮新的心跳消息，并等待大部分节点的确认，若得到大部分的确认，则Leader知道此时的 readIndex 是所有节点中最大的 commitIndex
4. Leader等待其状态机执行到至少 readIndex ，至此所有操作都是线性一致的
5. 最后，Leader直接查询状态机来获得client只读请求的结果，而不需要记录log
进一步优化：Leader可以积累一定数量的只读请求，然后通过一轮心跳消息来同时执行
进进一步优化：Follower也可以处理只读请求，首先向Leader发送请求来获取 readIndex ，然后Leader执行1-3步并回复Follower，最后Follower执行4-5步

Zookeeper

提高读性能

加入的服务器越多，读性能越高

Zookeeper并不要求返回最新的写入数据，即放弃线性一致性
从而client可以从Follower读取数据

一致保证

写请求线性一致
client请求会根据指定顺序执行，即FIFO client顺序
- 写请求一定会满足，因为写请求必须满足线性一致
- 读请求会发送到非Leader的副本，但是需要满足副本根据client读的顺序执行，即使是从不同的副本读也要满足顺序
  - 每个Log条目都会被Leader打上zxid的标签，这些标签就是Log对应的条目号
  - 任何时候一个副本回复一个客户端的读请求，首先这个读请求是在Log的某个特定点执行的，其次回复里面会带上zxid，对应的就是Log中执行点的前一条Log条目号
  - 客户端会记住最高的zxid，当客户端发出一个请求到一个相同或者不同的副本时，它会在它的请求中带上这个最高的zxid
  - 其他的副本就知道，应该至少在Log中这个点或者之后执行这个读请求
- 写请求和读请求并发时，读请求需要等到Leader执行完写操作后才能执行
  - 如果一个客户端写了一份数据，例如向Leader发送了一个写请求，之后立即读同一份数据，并将读请求发送给了某一个副本，那么客户端需要看到自己刚刚写入的值

同步操作

Zookeeper有一个操作类型是sync，它本质上就是一个写请求

因为读请求必须至少要看到同一个客户端前一个写请求对应的状态
所以，如果我发送了一个sync请求之后，又发送了一个读请求
Zookeeper必须要向我返回至少是我发送的sync请求对应的状态

这是一个代价很高的操作，因为我们现在将一个廉价的读操作转换成了一个耗费Leader时间的sync操作

Ready文件 znode

Zookeeper以文件目录的形式管理数据，所以每一个数据点也可以认为是一个file

假设有另外一个分布式系统，这个分布式有一个Master节点，而Master节点在Zookeeper中维护了一个配置，这个配置对应了一些file（也就是znode）

Master节点对配置的更新需要是原子性的：

假设Master做了一系列写请求来更新配置，那么我们的分布式系统中的Master会以这种顺序执行写请求
假设有一些Ready file，如果Ready file存在，那么允许读这个配置；如果Ready file不存在，那么说明配置正在更新过程中，我们不应该读取配置
如果Master要更新配置，那么第一件事情是删除Ready file
之后它会更新各个保存了配置的Zookeeper file（也就是znode）
当所有组成配置的file都更新完成之后，Master会再次创建Ready file

Worker节点对配置的读取

如果客户端看见了Ready file，那么副本接下来执行的读请求，会在Ready file重新创建的位置之后执行
Zookeeper可以保证这些读请求看到之前对于配置的全部更新

防止客户端读到不同版本的配置文件（Master更新配置，删除Ready file，客户端同时读到了一个Worker没来得及删除的Ready file，并读取了部分znode，然后等Master更新完，Worker重新创建Ready file后，客户端再读完剩下的znode）：

客户端会发送exists请求来查询Ready file是否存在，并建立一个针对这个Ready file的watch
如果Ready file有任何变更，例如被删除了，或者它之前不存在然后被创建了，副本会给客户端发送一个通知
当Ready file有变化时，副本会确保，合适的时机返回对于Ready file变化的通知
如果客户端向某个副本watch了某个Ready file，之后又发送了一些读请求，当这个副本执行了一些会触发watch通知的请求，那么Zookeeper可以确保副本将watch对应的通知，先发给客户端，再处理触发watch通知请求（也就是删除Ready file的请求），在Log中位置之后才执行的读请求
换句话说，客户端在完成读所有的配置之前，如果对配置有了新的更改，Zookeeper可以保证客户端在收到删除Ready file的通知之前，看到的都是配置更新前的数据（即，客户端读取配置读了一半，如果收到了Ready file删除的通知，就可以放弃这次读，再重试读）

Zookeeper作用

Zookeeper的数据都存在内存，因此只适合于存储配置信息

它可以是一个VMware FT所需要的Test-and-Set服务的实现
用它来发布其他服务器使用的配置信息。例如，向某些Worker节点发布当前Master的IP地址
选举Master，当一个旧的Master节点故障时，我们需要让所有的节点都认可同一个新的Master节点
- 用Zookeeper来保存Master的状态，新的Master从Zookeeper读取状态，从而保证其状态是up-to-date的
类似MapReduce的系统：
- Worker节点可以通过在Zookeeper中创建小文件来注册自己
- Master节点通过向Zookeeper写入具体的工作，之后Worker节点从Zookeeper中一个一个的取出工作、执行，完成之后再删除工作

Zookeeper API

Zookeeper的API某种程度上来说像是一个文件系统：它有一个层级化的目录结构，有一个根目录（root），之后每个应用程序有自己的子目录。比如说应用程序1将自己的文件保存在APP1目录下，应用程序2将自己的文件保存在APP2目录下，这些目录又可以包含文件和其他的目录

Zookeeper被设计成要被许多可能完全不相关的服务共享使用，所以我们需要一个命名系统来区分不同服务的信息，这样这些信息才不会弄混

这里的文件和目录都被称为znodes，Zookeeper中包含了3种类型的znode

Regular znodes：这种znode一旦创建，就永久存在，除非你删除了它
Ephemeral znodes：如果Zookeeper认为创建它的客户端挂了，它会删除这种类型的znodes
- Ephemeral znodes与客户端会话绑定在一起，所以客户端需要时不时的发送心跳给Zookeeper，告诉Zookeeper自己还活着，这样Zookeeper才不会删除客户端对应的Ephemeral znode
Sequential znodes：当你想要以特定的名字创建一个文件，Zookeeper实际上创建的文件名是你指定的文件名再加上一个数字。当有多个客户端同时创建Sequential文件时，Zookeeper会确保这里的数字不重合，同时也会确保这里的数字总是递增的

Zookeeper以RPC的方式暴露以下API：

CREATE(PATH，DATA，FLAG)：入参分别是文件的全路径名PATH，数据DATA，和表明znode类型的FLAG
- 如果我向Zookeeper请求创建一个文件，如果我得到了yes的返回，那么说明这个文件之前不存在，我是第一个创建这个文件的客户端
- 如果我得到了no或者一个错误的返回，那么说明这个文件之前已经存在了
DELETE(PATH，VERSION)：入参分别是文件的全路径名PATH，和版本号VERSION
- 每一个znode都有一个表示当前版本号的version，当znode有更新时，version也会随之增加
- 对于delete和一些其他的update操作，可以增加一个version参数，表明当且仅当znode的当前版本号与传入的version相同，才执行操作
EXIST(PATH，WATCH)：入参分别是文件的全路径名PATH，和一个有趣的额外参数WATCH
- 通过指定watch，你可以监听对应文件的变化，Zookeeper可以确保如果文件有任何变更，例如创建，删除，修改，都会通知到客户端
- 判断文件是否存在和watch文件的变化，在Zookeeper内是原子操作
  - 所以，当调用exist并传入watch为true时，不可能在Zookeeper实际判断文件是否存在和建立watch通道之间，插入任何的创建文件的操作，这对于正确性来说非常重要
GETDATA(PATH，WATCH)：入参分别是文件的全路径名PATH，和WATCH标志位
- 这里的watch监听的是文件的内容的变化
SETDATA(PATH，DATA，VERSION)：入参分别是文件的全路径名PATH，数据DATA，和版本号VERSION
- Zookeeper当且仅当文件的版本号与传入的version一致时，才会更新文件
LIST(PATH)：入参是目录的路径名，返回的是路径下的所有文件

使用Zookeeper实现计数器

假设我们在Zookeeper中有一个文件，我们想要在那个文件存储一个统计数字，例如，统计客户端的请求次数

需要保证获取计数值和增加计数值的操作的原子性

WHILE TRUE:
    X, V = GETDATA("F")
    IF SETDATA("f", X + 1, V):
        BREAK

第3行的意思是，只有当实际真实的版本号等于V的时候，才更新数据

使用Zookeeper实现非扩展锁

获得锁：

WHILE TRUE:
    IF CREATE("f", data, ephemeral=TRUE): RETURN
    IF EXIST("f", watch=TRUE):
        WAIT

在代码的第2行，是尝试创建锁文件，如果锁文件创建成功了，表明我们获得了锁，直接RETURN
如果锁文件创建失败了，那表明锁已经被别人占住了，所以我们需要等待锁释放。最终锁会以删除文件的形式释放，所以我们这里通过EXIST函数加上watch=TRUE，来监测文件的删除
在代码的第4行，等待文件删除对应的watch通知。收到通知之后，再回到循环的最开始，从代码的第2行开始执行

如果有1000个客户端同时要获得锁文件，为1000个客户端分发锁所需要的时间是 $O(n^2)$ （羊群效应）

因为每一次锁文件的释放，所有剩下的客户端都会收到WATCH的通知，并且回到循环的开始，再次尝试创建锁文件。所以CREATE对应的RPC总数与1000的平方成正比

使用Zookeeper实现可扩展锁

避免羊群效应，使得，即使有1000个客户端在等待锁释放，当锁释放时，另一个客户端获得锁的复杂度是 $O(1)$ 而不是 $O(n)$

CREATE("f", data, sequential=TRUE, ephemeral=TRUE)
WHILE TRUE:
    LIST("f*")
    IF NO LOWER #FILE: RETURN
    IF EXIST(NEXT LOWER #FILE, watch=TRUE):
        WAIT

第1行调用CREATE，并指定sequential=TRUE，我们创建了一个Sequential文件，如果这是以“f”开头的第27个Sequential文件，这里实际会创建类似以“f27”为名字的文件
- 通过CREATE获得一个全局唯一序列号
- Zookeeper生成的序号必然是递增的
第3行，通过LIST列出了所有以“f”开头的文件，也就是所有的Sequential文件
第4行，如果现存的Sequential文件的序列号都不小于我们在代码第1行得到的序列号，那么表明我们在并发竞争中赢了，我们获得了锁
- 当存在更低序列号的Sequential文件时，我们要做的是等待拥有更低序列号的客户端释放锁
- 在这个方案中，释放锁的方式是删除文件。所以接下来，我们需要做的是等待序列号更低的锁文件删除，之后我们才能获得锁
第5行，我们调用EXIST，并设置WATCH，等待比自己序列号更小的下一个锁文件删除
- 如果等到了，回到LIST开始执行，之所以要重新LIST，是因为比自己低的序号的客户端可能是释放锁才删除文件，也可能是挂了所以删除文件，例如，序号27等待26号释放锁，但如果26号客户端挂了，则需要等待25号释放锁，从而必须重新LIST

Zookeeper中的锁不是原子性的，适合用于Soft Lock的场景，如运行MapReduce Job时，你可以用这样的锁来确保一个Task同时只被一个Work节点执行。例如，对于Task 37，执行它的Worker需要先获得相应的锁，再执行Task，并将Task标记成执行完成，之后释放锁。MapReduce本身可以容忍Worker节点崩溃，所以如果一个Worker节点获得了锁，然后执行了一半崩溃了，之后锁会被释放，下一个获得锁的Worker会发现任务并没有完成，并重新执行任务

CRAQ

CRAQ是对于一个叫链复制（Chain Replication）的旧方案的改进，它在任意副本上执行读请求的前提下，还可以保证线性一致性

链复制

Chain Replication是这样一种方案，你有多个副本，你想确保它们都看到相同顺序的写请求（这样副本的状态才能保持一致）

在Chain Replication中，有一些服务器按照链排列，第一个服务器称为HEAD，最后一个被称为TAIL
当客户端想要发送一个写请求，写请求总是发送给HEAD
- HEAD根据写请求更新本地数据，我们假设现在是一个支持PUT/GET的key-value数据库，所有的服务器本地数据都从A开始
- 当HEAD收到了写请求，将本地数据更新成了B，之后会再将写请求通过链向下一个服务器传递
- 下一个服务器执行完写请求之后，再将写请求向下一个服务器传递，以此类推，所有的服务器都可以看到写请求
- 当写请求到达TAIL时，TAIL将回复发送给客户端，表明写请求已经完成了
对于读请求，如果一个客户端想要读数据，它将读请求发往TAIL
- TAIL直接根据自己的当前状态来回复读请求

故障恢复

如果HEAD出现故障，作为最接近的服务器，下一个节点可以接手成为新的HEAD，并不需要做任何其他的操作。对于还在处理中的请求，可以分为两种情况：

对于任何已经发送到了第二个节点的写请求，不会因为HEAD故障而停止转发，它会持续转发直到commit
如果HEAD在转发这个写请求之前就故障了，那么这个写请求必然没有commit，写请求必然没能送到TAIL，对于这些请求不必做任何事情。或许客户端会重发这个写请求，但是这并不是我们需要担心的问题

如果TAIL出现故障，TAIL的前一个节点可以接手成为新的TAIL。所有TAIL知道的信息，TAIL的前一个节点必然都知道

中间节点出现故障会稍微复杂一点，但是基本上来说，需要做的就是将故障节点从链中移除。或许有一些写请求被故障节点接收了，但是还没有被故障节点之后的节点接收，所以，当我们将其从链中移除时，故障节点的前一个节点或许需要重发最近的一些写请求给它的新后继节点

配置管理器

Chain Replication并不能抵御网络分区，也不能抵御脑裂。因此需要一个外部的权威（External Authority）来决定那些节点是活的，并确保所有参与者都认可由哪些节点组成一条链，这个外部的权威通常称为Configuration Manager

Configuration Manager的工作就是监测节点存活性，一旦Configuration Manager认为一个节点挂了，它会生成并送出一个新的配置，在这个新的配置中，描述了链的新的定义，包含了链中所有的节点，HEAD和TAIL，所有节点都会遵从新的配置内容

Configuration Manager通常会基于Raft或者Paxos，在CRAQ的场景下，它会基于Zookeeper

对于一个数据中心，首先有一个基于Raft或者Paxos的Configuration Manager，它是容错的，也不会受脑裂的影响
之后，通过一系列的配置更新通知，Configuration Manager将数据中心内的服务器分成多个链
- Configuration Manager通告给所有参与者整个链的信息，所以所有的客户端都知道HEAD在哪，TAIL在哪，所有的服务器也知道自己在链中的前一个节点和后一个节点是什么

Aurora

故障可恢复事务

通常来说，事务是通过对涉及到的每一份数据加锁来实现：

对于一个简单的数据库模型，数据库运行在单个服务器上，并且使用本地硬盘
在硬盘上存储了数据的记录，有一些data page用来存放数据库的数据，其中一个存放了X的记录，另一个存放了Y的记录。每一个data page通常会存储大量的记录，而X和Y的记录是page中的一些bit位
在硬盘中，除了有数据之外，还有一个预写式日志（Write-Ahead Log，简称为WAL）
在服务器内部，有数据库软件，通常数据库会对最近从磁盘读取的page有缓存
当你在执行一个事务内的各个操作时，例如执行 X=X+10 的操作时，数据库会从硬盘中读取持有X的记录，给数据加10
但是在事务提交之前，数据的修改还只在本地的缓存中，并没有写入到硬盘
为了让数据库在故障恢复之后，还能够提供同样的数据，在允许数据库软件修改硬盘中真实的data page之前，数据库软件需要先在WAL中添加Log条目来描述事务
- 假设，X的初始值是500，Y的初始值是750
- 在提交并写入硬盘的data page之前，数据库通常需要写入至少3条Log记录：
  - 第一条表明，作为事务的一部分，我要修改X，它的旧数据是500，我要将它改成510
  - 第二条表明，我要修改Y，它的旧数据是750，我要将它改成740
  - 第三条记录是一个Commit日志，表明事务的结束
- 记录旧数据是为了对于一个非常长的事务，在事务结束之前，数据库可以提前将更新了的page写入硬盘；之后如果在事务提交之前故障了，恢复的软件可以发现，事务并没有完成，然后根据WAL中的日志撤回之前的操作
如果数据库成功的将事务对应的操作和commit日志写入到磁盘中，数据库可以回复给客户端说，事务已经提交了，接下来有两种情况：
- 如果数据库没有崩溃，那么在它的cache中，X，Y对应的数值分别是510和740。最终数据库会将cache中的数值写入到磁盘对应的位置。所以数据库写磁盘是一个lazy操作，它会对更新进行累积，每一次写磁盘可能包含了很多个更新操作
- 如果数据库在将cache中的数值写入到磁盘之前就崩溃了，这样磁盘中的page仍然是旧的数值。当数据库重启时，恢复软件会扫描WAL日志，发现对应事务的Log，并发现事务的commit记录，那么恢复软件会将新的数值写入到磁盘中。这被称为redo，它会重新执行事务中的写操作

Aurora 初探

在替代EBS的位置，有6个数据的副本，位于3个AZ，每个AZ有2个副本。所以现在有了超级容错性，并且每个写请求都需要以某种方式发送给这6个副本，这里通过网络传递的数据只有Log条目
这里的存储系统不再是通用（General-Purpose）存储，这是一个可以理解MySQL Log条目的存储系统
Aurora并不需要6个副本都确认了写入才能继续执行操作，只要Quorum形成了，也就是任意4个副本确认写入了，数据库就可以继续执行操作

Aurora存储服务器的容错目标

对于写操作，当只有一个AZ彻底挂了之后，写操作不受影响
对于读操作，当一个AZ和一个其他AZ的服务器挂了之后，读操作不受影响
- AZ的下线时间可能很长，比如说数据中心被水淹了。人们可能需要几天甚至几周的时间来修复洪水造成的故障，在AZ下线的这段时间，我们只能依赖其他AZ的服务器。如果其他AZ中的一个服务器挂了，我们不想让整个系统都瘫痪。所以当一个AZ彻底下线了之后，对于读操作，Aurora还能容忍一个额外服务器的故障，并且仍然可以返回正确的数据
Aurora期望能够容忍暂时的慢副本
如果一个服务器看起来永久故障了，我们期望能够尽可能快的根据剩下的副本，生成一个新的副本

Quorum 复制机制

通常来说，Quorum系统就是简单的读写系统，支持Put/Get操作

假设有N个副本。为了能够执行写请求，必须要确保写操作被W个副本确认，W小于N。所以你需要将写请求发送到这W个副本。如果要执行读请求，那么至少需要从R个副本得到所读取的信息。这里的W对应的数字称为Write Quorum，R对应的数字称为Read Quorum。Quorum系统要求，任意你要发送写请求的W个服务器，必须与任意接收读请求的R个服务器有重叠。这意味着，R加上W必须大于N（至少满足R + W = N + 1 ），这样任意W个服务器至少与任意R个服务器有一个重合

可以轻易的剔除暂时故障、失联或者慢的服务器
可以调整读写的性能

Aurora读写存储服务器

Aurora中的写请求并不是像一个经典的Quorum系统一样直接更新数据。对于Aurora来说，它的写请求从来不会覆盖任何数据，它的写请求只会在当前Log中追加条目（Append Entries）。所以，Aurora使用Quorum只是在数据库执行事务并发出新的Log记录时，确保Log记录至少出现在4个存储服务器上，之后才能提交事务

但是存储服务器内存最终存储的还是数据库服务器磁盘中的page。在存储服务器的内存中，会有自身磁盘中page的cache，例如page1（P1），page2（P2），这些page其实就是数据库服务器对应磁盘的page

当一个新的写请求到达时，这个写请求只是一个Log条目，Log条目中的内容需要应用到相关的page中。但是我们不必立即执行这个更新，可以等到数据库服务器或者恢复软件想要查看那个page时才执行
对于每一个page，如果它最近被一个Log条目修改过，那么存储服务器会在内存中缓存一个旧版本的page和一系列来自于数据库服务器有关修改这个page的Log条目，所以对于一个新的Log条目，它会立即被追加到影响到的page的Log列表中（这里的Log列表从上次page更新过之后开始）
如果之后数据库服务器将自身缓存的page删除了，过了一会又需要为一个新的事务读取这个page，它会发出一个读请求到存储服务器，并要求存储服务器返回当前最新的page数据。这个时候，存储服务器才会将Log条目中的新数据更新到page，并将page写入到自己的磁盘中，之后再将更新了的page返回给数据库服务器，同时存储服务器在自身cache中会删除page对应的Log列表，并更新cache中的page

数据分片

为了能支持超过10TB数据的大型数据库。Amazon的做法是将数据库的数据，分割存储到多组存储服务器上，每一组都是6个副本，称为一个PG（Protection Group），分割出来的每一份数据是10GB

当Aurora需要发送一个Log条目时，它会查看Log所修改的数据，并找到存储了这个数据的PG，并把Log条目只发送给这个PG对应的6个存储服务器。所以，每个PG只存储了部分data page和所有与这些data page关联的Log条目

如果其中一个存储服务器挂了，我们期望尽可能快的用一个新的副本替代它。而一个存储服务器可能会存储10TB数据，也就是数百个PG，若它挂了，需要恢复整个服务器的数据，通过网络传输10TB消耗的时间太长了，因此需要一个更高效的恢复方案

Aurora实际使用的策略是，对于一个特定的存储服务器，它存储了许多Protection Group对应的10GB的数据块。对于Protection Group A，它的其他副本是5个服务器
或许这个存储服务器还为Protection Group B保存了数据，但是B的其他副本存在于与A没有交集的其他5个服务器中
这种模式下，如果一个存储服务器挂了，假设上面有100个数据块，现在的替换策略是：找到100个不同的存储服务器，其中的每一个会被分配一个数据块，也就是说这100个存储服务器，每一个都会加入到一个新的Protection Group中（相当于每一个存储服务器只需要负责恢复10GB的数据，并且可以并行恢复）

Frangipani

Frangipani 挑战

假设工作站W1创建了一个文件 /A。最初，这个文件只会在本地缓存中创建。首先，Frangipani需要从Petal获得 / 目录下的内容，之后当创建文件时，工作站只是修改缓存的拷贝，并不会将修改立即返回给Petal。直接的问题是：假设工作站W2上的用户想要获取 / 目录下的文件列表，我们希望这个用户可以看到新创建的文件。这称为缓存一致性问题（Cache Coherence）
因为所有的文件和目录都是共享的，非常容易会有两个工作站在同一个时间修改同一个目录，我们期望看到的是两个工作站的修改都可以生效，且互不干扰。这称为原子性（Atomicity）
假设我的工作站修改了大量的内容，由于Write-Back缓存，可能会在本地的缓存中堆积了大量的修改。如果我的工作站崩溃了，但是这时这些修改只有部分同步到了Petal，还有部分仍然只存在于本地。同时，其他的工作站还在使用文件系统。那么，我的工作站在执行操作的过程中的崩溃，最好不要损坏其他人同样会使用的文件系统。因此我们需要的是单个服务器的故障恢复

锁服务器

Frangipani的缓存一致性核心是由锁保证的，用锁来帮助工作站确定当它们缓存了数据时，它们缓存的是最新的数据

在锁服务器里面，有一个表单，就叫做locks。我们假设每一个锁以文件名来命名，所以对于每一个文件，我们都有一个锁，而这个锁，可能会被某个工作站所持有

在每个工作站，会记录跟踪它所持有的锁，和锁对应的文件内容。所以在每个工作站中，Frangipani模块也会有一个lock表单，表单会记录文件名、对应的锁的状态和文件的缓存内容

当一个Frangipani服务器决定要读取文件，首先它会向一个锁服务器请求文件对应的锁，之后才会向Petal服务器请求文件或者目录的数据
收到数据之后，工作站会记住，本地有一个文件X的拷贝，对应的锁的状态，和相应的文件内容
在工作站完成了一些操作之后，比如创建文件，或者读取文件，它会随着相应的系统调用（例如rename，write，create，read）释放锁（在做操作期间，锁的状态是Busy）
但是从锁服务器的角度来看，工作站仍然持有锁。工作站内部会标明，这是锁时Idle状态，它不再使用这个锁

Frangipani对锁应用了很多的规则：

工作站不允许持有缓存的数据，除非同时也持有了与数据相关的锁
如果你在释放锁之前，修改了锁保护的数据，那你必须将修改了的数据写回到Petal，只有在Petal确认收到了数据，你才可以释放锁
最后才能从工作站的lock表单中删除关文件的锁的记录和缓存的数据

缓存一致性

工作站和锁服务器之间的缓存一致协议协议包含了4种不同的消息：

Request消息：从工作站发给锁服务器。Request消息会说：hey锁服务器，我想获取这个锁
Grant消息：一旦工作站Request的锁被释放了，锁服务器会回复一个Grant消息给工作站
Revoke消息：通常来说，当工作站使用完锁之后，不会向锁服务器释放锁。如果锁服务器收到了一个加锁的请求，它查看自己的lock表单可以发现，这个锁现在正被工作站WS1所持有，锁服务器会发送一个Revoke消息给当前持有锁的工作站WS1，并说：现在别人要使用这个文件，请释放锁吧
Release消息：当一个工作站收到了一个Revoke请求，如果锁时在Idle状态，并且缓存的数据脏了，工作站会首先将修改过的缓存写回到Petal存储服务器中，然后发送一条Release消息来释放锁
- 如果工作站收到Revoke消息时，它还在使用锁，直到它完成了相应的文件系统操作，它都不会放弃锁；完成了操作之后，工作站中的锁的状态才会从Busy变成Idle，之后工作站才能注意到Revoke请求，在向Petal写完数据之后最终释放锁

一个主要的优化是，Frangipani有共享的读锁（Shared Read Lock）和排他的写锁（Exclusive Write Lock）

原子性

为了实现原子性，Frangipani在内部实现了一个数据库风格的事务系统，并且是以锁为核心。同时，这是一个分布式事务系统

Frangipani是这样实现分布式事务的：在我完全完成操作之前，Frangipani确保其他的工作站看不到我的修改

首先我的工作站需要获取所有我需要读写数据的锁，在完成操作之前，我的工作站不会释放任何一个锁
将所有修改了的数据写回到Petal之后，我的工作站才会释放所有的锁

Frangipani Log

需要能正确应对这种场景：一个工作站持有锁，并且在一个复杂操作的过程中崩溃了。比如说一个工作站在创建文件，或者删除文件时，它首先获取了大量了锁，然后会更新大量的数据，在其向Petal回写数据的过程中，一部分数据写入到了Petal，还有一部分还没写入，这时工作站崩溃了，并且锁也没有释放

Frangipani与其他的系统一样，需要通过预写式日志（Write-Ahead Log，WAL）实现故障可恢复的事务（Crash Recoverable Transaction）

当一个工作站需要完成涉及到多个数据的复杂操作时，在工作站向Petal写入任何数据之前，工作站会在Petal中自己的Log列表中追加一个Log条目，这个Log条目会描述整个的需要完成的操作
只有当这个描述了完整操作的Log条目安全的存在于Petal之后，工作站才会开始向Petal发送数据

Frangipani在实现WAL时，有一些不同的地方：

在大部分的事务系统中，只有一个Log，系统中的所有事务都存在于这个Log中；但是Frangipani不是这么保存Log的，它对于每个工作站都保存了一份独立的Log
几乎在所有使用了Log的系统中，Log与运行了事务的计算机紧紧关联在一起，并且几乎总是保存在本地磁盘中；但是Frangipani工作站的Log存储在Petal，而不是本地磁盘中，这样的话如果工作站崩溃了，它的Log可以被其他工作站从Petal中获取到

我们需要大概知道Log条目的内容是什么：

每个Log条目都包含了Log序列号，这个序列号是个自增的数字。因为如果工作站崩溃了，Frangipani需要根据序列号探测工作站Log的结尾
每个Log条目还有一个用来描述一个特定操作中所涉及到的所有数据修改的数组
- 数组中的每一个元素会有一个Petal中的块号（Block Number），一个版本号和写入的数据
Log只包含了对于元数据的修改，不会包含需要写入文件的数据，所以它并不包含用户的数据

所以写入Petal的完整过程是：当工作站从锁服务器收到了一个Revoke消息，要自己释放某个锁，它需要执行：

首先，工作站需要将内存中还没有写入到Petal的Log条目写入到Petal中
之后，再将被Revoke的Lock所保护的数据写入到Petal
最后，向锁服务器发送Release消息

故障恢复

这里的场景是，当工作站需要重命名文件或者创建一个文件时，首先它会获得所有需要修改数据的锁，之后修改自身的缓存来体现改动。但是后来工作站在向Petal写入数据的过程中故障了。发生故障时可能会有这几种场景：

要么工作站正在向Petal写入Log，所以这个时候工作站必然还没有向Petal写入任何文件或者目录
要么工作站正在向Petal写入修改的文件，所以这个时候工作站必然已经写入了完整的Log

当持有锁的工作站崩溃了之后，发生的第一件事情是锁服务器向工作站发送一个Revoke消息，但是锁服务器得不到任何响应，之后才会触发故障恢复。Frangipani出于一些原因对锁使用了租约，当租约到期了，锁服务器会认定工作站已经崩溃了，之后它会初始化恢复过程

锁服务器会通知另一个还活着的工作站说：看，工作站1看起来崩溃了，请读取它的Log，重新执行它最近的操作并确保这些操作完成了，在你完成之后通知我，在收到这里的通知之后，锁服务器才会释放锁

Frangipani对每一份存储在Petal文件系统数据增加一个版本号，同时将版本号与Log中描述的更新关联起来。当工作站需要修改Petal中的元数据时，它会向从Petal中读取元数据，并查看当前的版本号，之后在创建Log条目来描述更新时，它会在Log条目中对应的版本号填入元数据已有的版本号加1

之后，如果工作站执行到了写数据到Petal的步骤，它也会将新的增加了的版本号写回到Petal。所以，如果一个工作站没有故障，并且成功的将数据写回到了Petal。这样元数据的版本号会大于等于Log条目中的版本号。如果有其他的工作站之后修改了同一份元数据，版本号会更高

分布式事务

分布式事务主要有两部分组成。第一个是并发控制（Concurrency Control）第二个是原子提交（Atomic Commit）

并发控制

在并发控制中，主要有两种策略

悲观并发控制（Pessimistic Concurrency Control）：在悲观系统中，如果有锁冲突，比如其他事务持有了锁，就会造成延时等待。所以这里需要为正确性而牺牲性能
乐观并发控制（Optimistic Concurrency Control）：你不用担心其他的事务是否正在读写你要使用的数据，你直接继续执行你的读写操作，通常来说这些执行会在一些临时区域，只有在事务最后的时候，你再检查是不是有一些其他的事务干扰了你
- 如果没有这样的其他事务，那么你的事务就完成了，并且你也不需要承受锁带来的性能损耗
- 如果有一些其他的事务在同一时间修改了你关心的数据，并造成了冲突，那么你必须要Abort当前事务，并重试

讨论悲观并发控制，这里涉及到的基本上就是锁机制。这里的锁是两阶段锁（Two-Phase Locking）：

当事务需要使用一些数据记录时，第一个规则是在使用任何数据之前，在执行任何数据的读写之前，先获取锁
第二个对于事务的规则是，事务必须持有任何已经获得的锁，直到事务提交或者Abort，你不允许在事务的中间过程释放锁

这就是两阶段锁的两个阶段，第一个阶段获取锁，第二个阶段是在事务结束前一直持有锁

缺点是非常容易产生死锁，实际上事务有各种各样的策略，包括了判断循环，超时来判断它们是不是陷入到这样一个场景中。如果是的话，数据库会Abort其中一个事务，撤回它所有的操作，并表现的像这个事务从来没有发生一样

两阶段提交

原子性是指，事务的每一个部分都执行，或者任何一个部分都不执行。两阶段提交（Two-Phase Commit）是一种解决方案

实际上是数据被分割在不同的服务器上，所以相应的任务也被分包在不同的服务器上。假设有一个计算机会用来管理事务，它被称为事务协调者（Transaction Coordinator），事务协调者以某种形式运行事务的代码，例如Put/Get/Add，它向持有了不同数据的其他计算机发送消息，其他计算机再执行事务的不同部分

在一个完整的系统中，或许会有很多不同的并发运行事务，也会有许多个事务协调者在执行它们各自的事务。在这个架构里的各个组成部分，都需要知道消息对应的是哪个事务，所以对于事务，需要有事务ID（Transaction ID），简称为TID

除了TC之外，其他的服务器执行部分的事务，这些服务器被称为参与者（Participants）

我们将Two-Phase Commit简称为2PC。参与者有：事务协调者（TC），我们假设只有两个参与者（A，B），两个参与者就是持有数据的两个不同的服务器

在事务的最开始，TC会向参与者A发送Get请求并得到回复，之后再向参与者B发送一个Put请求并得到回复
之后，当TC到达了事务的结束并想要提交事务，这样才能：
- 释放所有的锁
- 使得事务的结果对于外部是可见的
- 再向客户端回复
在开始执行事务时，TC需要确保，所有的事务参与者能够完成它们在事务中的那部分工作，TC为了确保这一点，会向所有的参与者发送Prepare消息
当A或者B收到了Prepare消息，它们就知道事务要执行但是还没执行的内容，它们会查看自身的状态并决定它们实际上能不能完成事务，并回复Yes/No
- TC会等待来自于每一个参与者的这些Yes/No投票。如果所有的参与者都回复Yes，那么事务可以提交，不会发生错误；之后TC会发出一个Commit消息，给每一个事务的参与者；之后，事务参与者通常会回复ACK说，我们知道了要commit
- 如果任何一个参与者回复了No，表明自己不能完成这个事务，那么事务协调者不会发送commit消息，它会发送一轮Abort消息给所有的参与者说，请撤回这个事务
在事务Commit之后，会发生两件事情
- 事务协调者会向客户端发送代表了事务输出的内容，表明事务结束了，事务没有被Abort并且被持久化保存起来了
- 为了遵守两阶段锁规则，事务参与者会释放锁（这里不论Commit还是Abort都会释放锁）
  - 每个事务参与者在参与事务时，会对任何涉及到的数据加锁

故障恢复

事务参与者故障

参与者B可能在回复事务协调者的Prepare消息之前的崩溃了：如果B发现自己不可能发送Yes，比如说在发送Yes之前自己就故障了，那么B被授权可以单方面的Abort事务
B也可能在回复了Yes给事务协调者的Prepare消息之后崩溃的：在B故障的时候，不知道事务是否能Commit，因为它还没有收到Commit消息。但是B还是需要做好Commit的准备。这意味着，在故障重启的时候，B不能丢失对于事务的状态记录
- 在B回复Prepare之前，它必须确保记住当前事务的中间状态，记住所有要做的修改，记住事务持有的所有的锁，这些信息必须在磁盘上持久化存储
- 之后如果B在发送完Yes之后崩溃了，当它重启恢复时，通过查看自己的Log，它可以发现自己正在一个事务的中间，并且对一个事务的Prepare消息回复了Yes
B可能在收到Commit之后崩溃了：但是这样的话，B就完成了修改，并将数据持久化存储在磁盘上了。这样的话，故障重启就不需要做任何事情，因为事务已经完成
- 因为没有收到ACK，事务协调者会再次发送Commit消息。当B重启之后，收到了Commit消息时，它可能已经将Log中的修改写入到自己的持久化存储中、释放了锁、并删除了有关事务的Log。因此对于一个它不知道事务的Commit消息，B会简单的ACK这条消息

事务协调者故障

如果事务的任何一个参与者可能已经提交了，或者事务协调者可能已经回复给客户端了，那么我们不能忽略事务。例如如果事务协调者已经向A发送了Commit消息，但是还没来得及向B发送Commit消息就崩溃了，那么事务协调者必须在重启的时候准备好向B重发Commit消息，以确保两个参与者都知道事务已经提交了

如果事务协调者在发送Commit消息之前就崩溃了，那就无所谓了，因为没有一个参与者会Commit事务，它可以直接Abort事务
如果事务协调者在发送完一个或者多个Commit消息之后崩溃，那么就不允许它忘记相关的事务
- 在崩溃的时间点，也就是事务协调者决定要Commit而不是Abort事务，并且在发送任何Commit消息之前，它必须先将事务的信息写入到自己的Log，并存放在例如磁盘的持久化存储中
- 事务协调者在收到所有对于Prepare消息的Yes/No投票后，会将结果和事务ID写入存在磁盘中的Log，之后才会开始发送Commit消息
- 作为恢复流程的一部分，对于执行了一半的事务，事务协调者会向所有的参与者重发Commit消息或者Abort消息，以防在崩溃前没有向参与者发送这些消息

在事务协调者没有收到Yes/No回复一段时间之后，它可以单方面的Abort事务。因为它知道它没有得到完整的Yes/No消息，当然它也不可能发送Commit消息

类似的，如果参与者等待Prepare消息超时了，那意味着它必然还没有回复Yes消息，进而意味着事务协调者必然还没有发送Commit消息。所以如果一个参与者在这个位置因为等待Prepare消息而超时，那么它也可以决定Abort事务

假设B收到了Prepare消息，并回复了Yes，这个时候参与者没有收到Commit消息，它接下来怎么也等不到Commit消息。这段时间里，B一直持有事务涉及到数据的锁，这意味着，其他事务可能也在等待这些锁的释放。但是这时候我们不能单方面Abort事务或Commit事务，并释放锁，必须等待事务协调者上线

因为B对Prepare消息回复了Yes，这意味着事务协调者可能收到了来自于所有参与者的Yes，并且可能已经向部分参与者发送Commit消息
这意味着A可能已经看到了Commit消息，Commit事务，持久化存储事务的结果并释放锁

发布于：2022年4月28日

distributed system

在任意位置运行Python脚本

在Ubuntu上任意位置运行某一个python脚本的方法：首先在python文件开头加上： 1#!/usr/bin/env python3 说明该文件是python3脚本为方便起见，...

论文阅读-Oblivious Database相关

不经意数据库相关研究抵抗inference attack 关键是隐藏访问模式：隐藏访问内容+访问时间/访问次数/访问顺序等 ObliDB:star2: Proceedings of th...