MIT-6.824 (6)

MIT-6.824 分布式系统学习笔记（6）

参考资料：

Lecture 11 Cache Consistency: Frangipani

初探

Frangipani论文讨论：
- 缓存一致性（Cache Coherence）：缓存中有数据，新的请求修改了实际数据但是此时没有考虑缓存中的数据，此时需要一些额外的工作，保证缓存和实际数据保持一致
- 分布式事务（Distributed Transaction）
- 分布式故障恢复（Distributed Crash Recovery）
Frangipani是一个网络文件系统（NFS，Network File System），与已有的应用程序一起工作
- 工作站运行一个Frangipani服务，应用程序执行文件系统调用时，系统内核中的Frangipani模块实现了文件系统
- 文件系统的数据结构——文件内容、inode、目录、目录的文件列表、inode和块的空闲状态——存储在共享虚拟磁盘服务中（称为Petal）
  - Petal运行在一些不同的服务器上，而非上述的工作站
  - Petal会复制数据，使得即使一个Petal服务器故障也能取回数据
  - Frangipani读写文件时向Petal服务器发送RPC，此时Petal是一个被所有Frangipani使用、基于网络的共享磁盘
论文期望使用Frangipani来支持使用共享的基础设施，如果一个用户编辑了一个文件，其他用户可以读到刚刚编辑的文件（听起看来像是腾讯共享文档一样）
- 虽然数据存储在共享磁盘中，但本地（工作站，或者Frangipani服务器）仍有一些缓存，以提高性能
- Frangipani支持Write-Back缓存：修改、创建、删除一个文件时，会先只更新在本地缓存，这些修改要过一会才写回到Petal——文件系统的逻辑需要存在于每个工作站的Frangipani模块，而Petal只是一个存储系统，因此这是一个去中心化的设计
综上，有一个系统，在工作站里有大量的缓存，文件的修改在本地缓存完成

Frangipani的挑战

两个挑战：缓存，去中心化架构使得大量逻辑放在客户端
缓存一致性挑战：
- 工作站上的一些修改需要被其他工作站看到
- 例如工作站W1在本地缓存中创建一个文件/A，工作站W2的用户要获取/目录下的文件列表时，需要看到新创建的文件A——这种一致性称为缓存一致性（Cache Coherence）
- 如果我缓存了一个数据，而其他人在他的缓存中修改了这个数据，我的缓存需要自动的应用相关修改
原子性挑战：两个工作站可能在同一时间修改同一目录，因此期望类似于创建、删除的操作能即时生效，不会与相同时间其他工作站的操作相互干扰，即，具有原子性（Atomicity）
单个服务器的故障恢复：一个工作站的崩溃不会影响其他使用同一个共享系统的工作站，即使这些工作站正在查看崩溃工作站的文件或目录

Frangipani的锁服务

线性一致性使用户总能看到最新数据，而缓存能带来性能的提升
Frangipani的缓存一致性核心由锁保证，用锁来使工作站相信，当它们缓存了数据时，它们缓存的是最新的数据
锁服务器：
- Frangipani系统中有三种服务器：Frangipani服务器（工作站）、Petal存储服务器、锁服务器
- 逻辑上锁服务器是独立的服务器，实际上它与Petal服务器一起运行
- 锁服务器有一个locks表单，锁以文件名来命名，每个文件（以及对应的锁）可能会被某个工作站持有——Frangipani的锁要么允许一个写入者持有，要么允许多个读取者持有
- 锁服务器会记住每个文件的锁被谁持有
工作站的Frangipani模块也有一个lock表单，记录文件名、对应的锁的状态和文件的缓存内容
- 当一个Frangipani服务器决定要读取文件，它会向一个锁服务器请求文件对应的锁，之后才会向Petal服务器请求文件或者目录的数据
- 收到数据之后，工作站会记住，本地有一个文件X的拷贝，对应的锁的状态，和相应的文件内容
- 在工作站完成创建、读取等操作时，会随着相应的系统调用（如write，create，read）释放锁（在做操作期间，锁的状态是Busy）
- 但从锁服务器的角度来看，工作站仍然持有锁，即使工作站内部会标明此时锁是Idle状态，不再使用这个锁
Frangipani应用了很多的规则，使得没有工作站会使用缓存中的旧数据——规则、锁、缓存数据需要配合使用，实现缓存一致性
- 工作站不允许持有缓存的数据，除非同时也持有了与数据相关的锁——意味着一个工作站使用一个数据之前，首先要从锁服务器获取数据的锁，持有锁后才从Petal读取数据
- 如果在释放锁之前修改了锁保护的数据，必须将修改了的数据写回到Petal，而只有Petal确认收到了数据，才可以释放锁
- 释放锁之后再从工作站的lock表单中，删除文件的锁的记录和缓存的数据

缓存一致性

缓存一致性挑战
工作站和锁服务器之间的缓存一致协议包含4种不同的消息（可以认为是单向的网络消息）
- Request消息：从工作站发给锁服务器，申请锁
- Grant消息：锁服务器的lock表单显示锁已经被其他人持有，此时锁服务器不能交出锁，而一旦锁被释放，锁服务器回复Grant消息给工作站
- Revoke消息：如前所述，当工作站使用完锁不会立刻向锁服务器释放锁，因此如果锁服务器收到Request消息，发现Request的锁被另一个工作站持有，锁服务器会发送一个Revoke消息给当前持有锁的工作站，请求其释放锁
- Release消息：
  - 工作站收到Revoke请求、锁在Idle状态、缓存数据被修改，会先将缓存写回Petal存储服务器，再发送Release消息
  - 工作站收到Revoke请求时如果还在使用锁，则会先忽略Revoke请求，状态转为Idle后再注意到Revoke请求
锁可以是为写入提供的排他锁（Exclusive Lock），也可以是为只读提供的共享锁（Shared Lock）
Frangipani可以理解锁与某个文件相关联——Frangipani使用Unix风格的inode号，作为lock表单的key
优化：
- 每个工作站用完锁之后，不立即向锁服务器释放锁，先锁的状态标记为Idle
- Frangipani有共享的读锁（Shared Read Lock）和排他的写锁（Exclusive Write Lock）——大量的工作站读取文件时，同时持有对这个文件的读锁。如果某个工作站需要修改这个文件，它需要Revoke所有工作站的读锁

原子性

原子性挑战
其他的工作站要么发现文件不存在，要么文件完全存在——多个步骤的操作要具备原子性
Frangipani在内部实现了一个数据库风格、以锁为核心的分布式事务系统
- 工作站要获取所有需要读写的数据的锁，将所有修改的数据写回Petal之后，工作站才释放所有的锁
- 有了锁服务器和缓存一致性协议，只需要确保在整个操作的过程中持有所有的锁，就可以实现不可分割原子事务

Fangipani Log

故障恢复挑战：一个工作站持有锁，向Petal回写数据时一部分数据写入Petal，一部分还没写入，此时工作站崩溃并且锁没有释放
Frangipani需要通过预写式日志（Write-Ahead Log，WAL，见10.2）实现故障可恢复的事务（Crash Recoverable Transaction）——一个工作站向Petal写入数据前，会在Petal中自己的Log列表中追加一个Log条目，描述整个需要完成的操作，之后才向Petal发送数据
Frangipani在实现WAL时，有一些不同的地方：
- 大部分的事务系统中只有一个Log，系统的所有事务都保存在这个Log。但Frangipani对每个工作站都保存了一份独立的Log
- 几乎在所有使用了Log的系统中，Log与运行了事务的计算机紧紧关联在一起，但工作站的Log存储在Petal，而不是本地磁盘，如果工作站崩溃，其他工作站可以从Petal中获取它的Log
Log条目的内容：每个工作站以一种环形的方式使用它在Petal上的Log空间——Log从存储的起始位置开始写，到达结尾时，工作站会重用最开始的Log空间
- 每个Log条目包含Log序列号（自增）。如果工作站崩溃，Frangipani会扫描位于Petal的Log直到Log结尾，因为最后一个Log必然是拥有最高序列号的Log
- 每个Log条目有一个描述一个特定操作涉及到的所有数据修改的数组，数组每一个元素有一个Petal中的块号（Block Number）、一个版本号、写入的数据。之所以是数组，因为如此可以描述涉及修改多份数据的操作
- Log只包含对元数据的修改（如文件系统的目录、inode、bitmap的分配），不包含需要写入文件的数据——只包含了故障之后，可以用来恢复文件系统结构的必要信息
最初，工作站的Log只保存在工作站的内存中，尽可能晚地写到Petal，因为向Petal写数据需要花费较长时间
完整的过程（工作站收到Revoke消息，要释放某个锁）：
- 工作站将内存中还没有写入到Petal的Log条目写入Petal
- 将被Revoke的Lock保护的数据，写入到Petal
- 向锁服务器发送Release消息

故障恢复

场景：工作站需要重命名文件或创建一个文件，获得锁，修改自身的缓存，向Petal写入数据时故障
- 要么工作站正在向Petal写入Log
- 要么工作站正在向Petal写入修改的文件
当持有锁的工作站崩溃后，锁服务器向工作站发送的Revoke消息得不到响应，然后触发故障恢复——没有人需要用到崩溃工作站持有的锁，则没有人会注意到工作站崩溃
Frangipani对锁使用租约，租约到期锁服务器会认定工作站已经崩溃，会初始化恢复过程：会通知另一个活着的工作站，让它读取崩溃工作站的Log，重新执行它最近的操作并确保这些操作完成，完成之后通知锁服务器，最后锁服务器释放锁
第一种故障中，除非在Petal中找到完整的Log条目，否则执行恢复的工作站是不会执行这条Log条目

第二种故障中，尽管部分修改已经写入了Petal，执行恢复的工作站会重新执行所有修改

第三种故障：在释放锁的过程中崩溃，进而导致崩溃的工作站不是最后修改特定数据的工作站，例如一个工作站WS1执行了删除文件的操作，另一个工作站WS2，以相同的名字创建了文件，在创建完成之后，工作站WS1崩溃，此时按以上逻辑需要基于WS1的Log执行恢复（WS3来执行）
- 此时按上述故障恢复，WS3会删除WS2创建的一个完全不同的文件，因此不能盲目地重新执行Log条目
- Frangipani对每一份存储在Petal文件系统数据（每一个元数据，每一个inode，每一个目录下的内容）增加一个版本号，将版本号与Log描述的更新关联起来
  - 工作站修改Petal中的元数据时，向从Petal中读取元数据并查看当前的版本号，创建Log条目来描述更新时，它会将当前版本号+1，填入在Log条目中的版本号，将新的增加了的版本号写回Petal
  - 因此，元数据的版本号会大于等于Log条目的版本号，如果其他的工作站之后修改同一份元数据，版本号会更高
- WS3重新执行WS1的Log时，首先检查Log条目中的版本号和Petal存储的版本号，如果Petal存储的版本号大于等于Log条目中的版本号，WS3会忽略Log条目的修改

Lecture 12 Distributed Transaction

初探

分布式事务由两部分组成：并发控制（Concurrency Control）、原子提交（Atomic Commit）
一些操作会要求从多个服务器上修改或者读取数据
通常将并发控制和原子提交放在一起，当做事务
数据库在存在并发和设备崩溃的前提下，仍然处理事务得到正确结果。正确性的定义为：ACID
- Atomic：原子性
- Consistent：一致性
- Isolated：隔离性，两个同时运行的事务，在事务结束前，不能看到彼此的中间状态，只能看到完成的事务结果。通常来说，隔离性（Isolated）意味着可序列化（Serializable）——并行执行一些事务得到的结果，与按照某种串行的顺序来执行这些事务，可以得到相同的结果
- Durable：持久化的，在客户端提交事务并从数据库得到确认时，在数据库中的修改是持久化的
并发控制（Concurrency Control）是实现可序列化的主要工具，通过与其他尝试使用相同数据的并发事务进行隔离，可以实现可序列化
原子提交（Atomic Commit）帮助处理下述场景：事务T1在执行过程中修改了X的值，此时事务涉及的一台服务器出现错误。此时需要能从这种场景恢复

并发控制

两种策略：悲观并发控制和乐观并发控制
- 悲观并发控制（Pessimistic Concurrency Control）
  - 在事务使用任何数据之前，需要获得数据的锁
  - 如果有锁冲突，如其他事务持有锁，会造成延时等待——为正确性牺牲性能
- 乐观并发控制（Optimistic Concurrency Control）
  - 不用担心其他的事务是否正在读写你要使用的数据，直接继续执行读写操作
  - 在事务最后的时候，再检查是否存在冲突，如果有则必须Abort当前事务，并重试
  - 完全避免了锁带来的性能损耗
本章只讨论了悲观并发控制——锁是两阶段锁（Two-Phase Locking）
- 当事务使用一些数据记录时，在执行任何数据的读写之前先获取锁
- 事务必须持有任何已经获得的锁，直到事务提交或者Abort，不允许在事务的中间过程释放锁
- 第一个阶段获取锁，第二个阶段在事务结束前一直持有锁
- 非常容易产生死锁：例如有两个事务，T1读取记录X，之后再读取记录Y，T2读取记录Y，之后再读取记录X。如果同时运行则存在死锁
  - 策略：使用判断循环、超时等方式，判断是否产生死锁，如果是，则数据库Abort其中一个事务，撤回它所有的操作，如同这个事务从来没有发生
以上使用两阶段锁的并发控制，在一个单主机的数据库中是这样，在一个分布式数据库也是这样

两阶段提交（Two-Phase Commit）

在一个分布式环境中，数据分割在多台机器上，如何构建数据库或存储系统以支持事务——如何构建分布式事务（Distributed Transaction），同时确保出现错误时，数据库仍然具有可序列化和某种程度的原子性（原子性指事务的每一个部分都执行，或者任何一个部分都不执行）
需要执行的任务以某种方式分包给多个服务器，每个服务器完成任务的不同部分
- 一个计算机会用来管理事务，称为事务协调者（Transaction Coordinator）
- 事务协调者以某种形式运行事务的代码（Put、Get、Add），向持有不同数据的其他计算机发送消息，其他计算机再执行事务的不同部分，称为参与者（Participants）
- 事务协调者向服务器S1发消息，对X加1，向服务器S2发消息，对Y减1。之后有更多消息来确认，要么两个服务器都执行了操作，要么两个服务器都没有执行操作。以上是两阶段提交的实现框架
需要知道消息对应的是哪个事务，为此持有数据的服务器会维护一个锁的表单，用来记录锁被哪个事务所持有，并且对于事务有事务ID（Transaction ID）
一个简单的过程：事务协调者（TC），持有数据的两个不同的服务器作为参与者（A，B），一个外部的客户端C
- C向TC发请求，运行一个事务，等待回复
- TC运行整个事务，向A，B发送Put和Get，读取X，Y的数值，对X加1等。因此在事务的最开始，TC向参与者A发送Get请求并得到回复，之后再向参与者B发送一个Put请求并得到回复
- TC完成了事务并想要提交事务，此时释放所有的锁，让事务的结果对于外部可见，向客户端回复
- 在开始执行事务时，TC需要确保所有的事务参与者能够完成它们在事务中的那部分工作，为此TC向所有的参与者发送Prepare消息，等待每个参与者的Yes/No投票
- A或者B收到Prepare消息时，它们知道事务要执行但是还没执行的内容，查看自身的状态并判断能否完成相应工作，向TC回复Yes或者No
  - 如果所有的参与者都回复Yes，事务可以提交，不会发生错误，TC会给每一个参与者发出一个Commit消息，事务参与者回复ACK
  - 如果任何一个参与者回复了No，TC不会发送commit消息，而是发送一轮Abort消息给所有的参与者，撤回这个事务
- 事务Commit之后:
  - TC向客户端发送代表事务输出的内容，表明事务结束并且被持久化保存
  - TC释放锁（不论Commit还是Abort）

故障恢复

事务参与者故障
- 参与者B回复TC的Prepare消息之前崩溃：
  - TC角度看，B没有回复Yes，TC不能Commit
  - B角度看，B被授权可以单方面的Abort事务，因为B知道自己不能发送Yes
- B在回复Yes给Prepare消息后崩溃：
  - 要确保B在故障恢复之后，仍然能完成分包给它的那一部分工作，因此故障重启时，B不能丢失对于事务的状态记录
  - B回复Prepare之前，当前事务的中间状态、要做的修改、事务持有的锁必须在磁盘上持久化存储（以Log的形式在磁盘上存储）——B回复前，首先将相应的Log写入磁盘
  - 它重启恢复时，查看自己的Log可以发现之前正在一个事务的中间，而通过读取Log就知道如何完成它在事务中的那部分工作
- B在收到Commit之后崩溃：完成了修改，数据持久化存储在磁盘上，无需任何处理。而TC没有收到ACK，TC会再次发送Commit消息时，此时B会完全忘记已经在磁盘上持久化存储的事务的信息，因此B会直接ACK这条消息
TC故障
- TC在发送Commit消息之前崩溃：无所谓，没有一个参与者会Commit事务，直接Abort这个事务
- TC发送完一个或者多个Commit消息之后崩溃：
  - TC发送任何Commit消息前，先将事务的信息（结果和事务ID）写入到自己的Log，并持久化存储
  - 恢复时，查看Log可以发现哪些事务执行了一半，哪些事务已经Commit了，哪些事务已经Abort了。对于执行了一半的事务，TC向所有的参与者重发Commit/Abort消息
如果消息在网络传输的时候丢失了：
- TC发送Prepare消息，没有收到所有的Yes/No消息：
  - 选择一：TC重新发送一轮Prepare消息（费时，可能有个参与者永久关机了）
  - 选择二：TC单方面的Abort事务，并发送一轮Abort消息，此时如果一个崩溃的参与者重启并询问被Abort的事务，TC会发现没有该事务的记录，因此会恢复Abort消息
- 参与者等待Prepare消息超时：可以决定Abort事务
- 假设B收到了Prepare消息，并回复了Yes，但参与者没有收到Commit消息：
  - 这段等待commit的时间里，B一直持有事务涉及到数据的锁
  - 不能单方面Abort事务或Commit事务，并释放锁，必须等待TC上线——称为Block，在特定的故障中，会很容易的陷入到一个需要等待很长时间的场景