快速建设网站视频教程,工业设计属于什么专业类别,建设公司属于什么企业,wordpress 伪静态 主题失效MIT 6.824 -- Cache Consistency -- 11 引言严峻挑战锁服务缓存一致性问题案例演示优化 原子性问题故障恢复问题log内容故障恢复 小结 课程b站视频地址: MIT 6.824 Distributed Systems Spring 2020 分布式系统
推荐伴读读物:
极客时间 – 大数据经典论文解读DDIA – 数据密集… MIT 6.824 -- Cache Consistency -- 11 引言严峻挑战锁服务缓存一致性问题案例演示优化 原子性问题故障恢复问题log内容故障恢复 小结 课程b站视频地址: MIT 6.824 Distributed Systems Spring 2020 分布式系统
推荐伴读读物:
极客时间 – 大数据经典论文解读DDIA – 数据密集型应用大数据相关论文中译版本
本节预习作业:
Frangipani论文 引言
Frangipani 是一篇关于分布式文件系统的古老论文但是站在目前的角度来看其更符合适用于小型团体的NFS(网络文件系统)实现。
该篇论文所描述的网络文件系统由两部分组成:
每个客户端本地都需要引入一个Frangipani服务该服务负责对上提供类UNIX文件系统接口对下负责与Petal集中式存储服务进行通信与数据传输服务。文件系统的数据结构如: 文件内容Inode目录目录的文件列表inode和块的空闲状态这些数据都存储在一个叫Petal的共享虚拟磁盘服务中。
Petal 会运行在不同的服务器上还会提供分片副本机制来支持高可用和容错性。当Frangipani需要读写文件时它会向正确的Petal服务器发送RPC。整个Petal表现的就像是一个磁盘可以将其看做是共享磁盘所有Frangipani都会与之交互。
出于性能考虑Frangipani会在本地缓存中缓存读取到的文件数据同时采用Write-Back将脏数据异步写回Petal。同时Frangipani服务负责实现文件系统相关的逻辑Petal只是作为简单的共享存储系统存在它不关心文件和目录这些概念以此来实现一个去中心化的设计。
解释一下Frangipani服务负责实现文件系统逻辑的含义:
Frangipani服务通过Write-Back缓存来管理文件数据信息这意味着我们对文件的所有修改操作都是发生在缓存中的比如创建文件时我们会新创建inode初始化内容对应目录列表更新这些修改都只存在于本地缓存中稍后才会被写回Petal中。为了让Frangipani服务可以通过操作内存就完成类似创建文件的事情这意味着我们需要把对文件系统的逻辑和设计在Frangipani服务中也实现一遍。
由于这种去中心化的设计导致大部分CPU运算逻辑都集中在Frangipani服务中这意味着我们可以通过增加更多的用户来获得更多的CPU算力以此来同时运行更多的文件系统操作。因为大部分的文件系统操作只在客户端本地发生所以大部分CPU消耗的都是本地的所以这个系统的天然自带扩展性。 关键点在于此处的本地缓存和异步写回意味着客户端无需频繁与Petal进行交互只需要与本地的Frangipani服务进行交互即可。 在某个时间点瓶颈会在Petal。因为这是一个中心化的存储系统这时你需要增加更多的存储服务器。
所以我们现在有了一个系统它在客户端本地做了大量的缓存并且文件的修改可以在本地缓存完成。这会导致我们面临一些严峻挑战。 严峻挑战
Frangipani的挑战主要来自于三方面:
缓存一致性问题原子性问题崩溃恢复问题
第一个问题假设用户1发起了创建文件请求然后在本地缓存中完成了在dhy目录下创建Main.go文件的任务由于采用Write-Back机制此时修改产生的脏数据并不会立马同步回Petal中。
用户2接着发起文件查询请求他想要获取/dhy目录下的所有文件但是由于用户1的写操作还未同步回Petal所以用户2此时无法看到用户1创建的Main.go文件这就是由于缓存导致的不一致性问题。 另一个问题就是丢失更新问题或者在该场景下还可以成为原子性问题假设用户1尝试在/dhy目录下创建Main1.go文件用户2尝试在/dhy目录下创建Main2.go文件这两个操作看似不冲突但是他们都需要为/dhy目录增加一个新的目录项所以这里的问题是当他们同时操作时系统能识别这些修改了相同目录的操作并得到一些有意义的结果吗
这里的有意义的结果是指A和B最后都要创建成功我们不想只创建一个文件因为第二个文件的创建有可能会覆盖并取代第一个文件。 之所以称当前问题为原子性问题是因为我们期望类似于创建文件删除文件这样的操作表现的就像即时生效一样同时不会与同时发生的其他操作相互干扰。
最后一个问题是假设客户端修改了大量的内容由于Write-Back缓存可能会在本地的缓存中堆积了大量的修改。如果客户端崩溃了但是这时这些修改只有部分同步到了Petal还有部分仍然只存在于本地。同时其他的客户端还在使用文件系统。那么客户端在执行操作的过程中的崩溃最好不要损坏其他人同样会使用的文件系统。
这意味着我们需要的是单个服务器的故障恢复我希望某个客户端的崩溃不会影响其他使用同一个共享系统的客户端。哪怕说这些客户端正在查看我的目录我的文件它们应该看到一些合理的现象。它们可以漏掉我最后几个操作但是它们应该看到一个一致的文件系统而不是一个损坏了的文件系统数据。所以这里我们希望有故障恢复。 锁服务
Frangipani的第一个挑战是缓存一致性。在这里我们想要的是线性一致性和缓存带来的好处。对于线性一致性来说当我查看文件系统中任何内容时我总是能看到最新的数据。对于缓存来说我们想要缓存带来的性能提升。某种程度上我们想要同时拥有这两种特性的优点。
Frangipani的缓存一致性核心是由锁保证的我们之后在原子性和故障恢复中将会再次看到锁。但是现在我们只讨论用锁来保证缓存一致用锁来帮助客户端确定当它们缓存了数据时它们缓存的是最新的数据。
除了Frangipani服务器也就是客户端Petal存储服务器在Frangipani系统中还有第三类服务器锁服务器。尽管你可以通过分片将锁分布到多个服务器上但是我接下来会假设只有一个锁服务器。逻辑上锁服务器是独立的服务器但是实际上我认为它与Petal服务器运行在一起。在锁服务器里面有一个表单就叫做locks。我们假设每一个锁以文件名来命名所以对于每一个文件我们都有一个锁而这个锁可能会被某个客户端所持有。 下面举例说明锁服务器工作流程:
假设文件X最近被客户端1使用了所以客户端1对于文件X持有锁。同时文件Y最近被客户端2使用所以客户端2对于文件Y持有锁。锁服务器会记住每个文件的锁被谁所持有。当然一个文件的锁也有可能不被任何人持有。 在每个客户端会记录跟踪它所持有的锁和锁对应的文件内容。所以在每个客户端中Frangipani模块也会有一个lock表单表单会记录文件名、对应的锁的状态和文件的缓存内容。这里的文件内容可能是大量的数据块也可能是目录的列表。 由于分片都采用分块存储所以这里加锁粒度可以细化到chunk层级。 当一个Frangipani服务器决定要读取文件比如读取目录 /、读取文件X、查看一个inode首先它会向一个锁服务器请求文件对应的锁之后才会向Petal服务器请求文件或者目录的数据。收到数据之后客户端会记住本地有一个文件X的拷贝对应的锁的状态和相应的文件内容。每一个客户端的锁至少有两种模式。客户端可以读或者写相应的文件或者目录的最新数据可以在创建删除重命名文件的过程中如果这样的话我们认为锁在Busy状态。 在客户端完成了一些操作之后比如创建文件或者读取文件它会随着相应的系统调用例如renamewritecreateread释放锁。只要系统调用结束了客户端会在内部释放锁现在客户端不再使用那个文件。但是从锁服务器的角度来看客户端仍然持有锁。客户端内部会标明这时锁是Idle状态它不再使用这个锁。所以这个锁仍然被这个客户端持有但是客户端并不再使用它。这在稍后的介绍中比较重要。 Frangipani这里应用了很多规则这些规则使得Frangipani以一种提供缓存一致性的方式来使用锁并确保没有客户端会使用缓存中的旧数据。这些规则、锁、缓存数据需要配合使用。这里的规则包括
客户端不允许持有缓存的数据除非同时也持有了与数据相关的锁。所以基本上来说不允许在没有锁保护的前提下缓存数据。从操作意义上来说这意味着对于客户端来说在它使用一个数据之前它首先要从锁服务器获取数据的锁。只有当客户端持有锁了客户端才会从Petal读取数据并将数据放在缓存中。 所以这里的顺序是获得锁之后再从Petal读取数据。所以直到获取了锁客户端是不能缓存数据的要想缓存数据客户端必须先持有锁之后才能从Petal读取数据。 如果你在释放锁之前修改了锁保护的数据那你必须将修改了的数据写回到Petal只有在Petal确认收到了数据你才可以释放锁也就是将锁归还给锁服务器。 所以这里的顺序是先向Petal存储系统写数据之后再释放锁。 最后再从客户端本地的lock表单中删除关文件的锁的记录和缓存的数据。 缓存一致性问题
客户端和锁服务器之间的缓存一致协议协议包含了4种不同的消息。本质上你可以认为它们就是一些单向的网络消息。
首先是Request消息从客户端发给锁服务器。Request消息会说hey锁服务器我想获取这个锁。如果从锁服务器的lock表单中发现锁已经被其他人持有了那锁服务器不能立即交出锁。但是一旦锁被释放了锁服务器会回复一个Grant消息给客户端。这里的Request和Grant是异步的。如果你向锁服务器请求锁而另一个客户端现在正持有锁锁服务器需要持有锁的客户端先释放锁因为一个锁不能同时被两个人持有。那我们怎么能让这个客户端获取到锁呢
前面说过如果一个客户端在使用锁并在执行读写操作那么它会将锁标记为Busy。但是通常来说当客户端使用完锁之后不会向锁服务器释放锁。所以如果我创建了一个新文件create函数返回时这些新文件的锁仍然被当前客户端持有。只是说现在锁的状态会变成Idle而不是Busy。但是从锁服务器看来当前客户端仍然持有锁。
这里延迟将锁还给锁服务器的原因是如果当前客户端创建了文件Y。我接下来几乎肯定要将Y用于其他目的或许我向它写一些数据或许会从它读数据。所以如果客户端能持有所有最近用过的文件的锁并不主动归还的话会有非常大的优势。在一个常见的例子中我使用了home目录下的一些文件并且其他客户端没有人查看过这些文件。当前客户端最后会为我的文件持有数百个在Idle状态的锁。但是如果某人查看了我的文件他需要先获取锁而这时我就需要释放锁了。
所以这里的工作方式是如果锁服务器收到了一个加锁的请求它查看自己的lock表单可以发现这个锁现在正被客户端1所持有锁服务器会发送一个Revoke消息给当前持有锁的客户端1。并说现在别人要使用这个文件请释放锁吧。
当客户端收到了一个Revoke请求如果锁时在Idle状态并且缓存的数据脏了客户端会首先将修改过的缓存写回到Petal存储服务器中因为前面的规则要求在释放锁之前要先将数据写入Petal。所以如果锁的状态是Idle首先需要将修改了的缓存数据发回给Petal只有在那个时候客户端才会再向锁服务器发送一条消息说好吧我现在放弃这个锁。所以对于一个Revoke请求的响应是客户端会向锁服务器发送一条Release消息。
如果客户端收到Revoke消息时它还在使用锁比如说正在删除或者重命名文件的过程中直到客户端使用完了锁为止或者说直到它完成了相应的文件系统操作它都不会放弃锁。完成了操作之后客户端中的锁的状态才会从Busy变成Idle之后客户端才能注意到Revoke请求在向Petal写完数据之后最终释放锁。
以上就是Frangipani使用的缓存一致性协议的一个简单版本的描述。这里面没有考虑一个事实那就是锁可以是为写入提供的排他锁Exclusive Lock也可以是为只读提供的共享锁Shared Lock。
就像Petal只是一个块存储服务并不理解文件系统。锁服务器也不理解文件目录还有文件系统它只是维护lock表单表单中记录的是锁的名字和锁的持有者。Frangipani可以理解锁与某个文件相关联。实际上Frangipani在这里使用的是Unix风格的inode号来作为lock表单的key而不是文件的名字。 案例演示
本节以一个案例作为演示来看一下此处缓存一致性协议工作的整个流程。
首先我们有两个客户端和一个锁服务器按照协议如果客户端1想要读取并修改文件Z。在它从Petal读取文件之前它需要先获取对于Z的锁所以它向锁服务器发送Request消息 如果当前没有人持有对文件Z的锁或者锁服务器没听过对于文件Z的锁初始化状态锁服务器会在lock表单中增加一条记录并返回Grant消息给客户端1说你现在持有了对于Z文件的锁 从这个时间点开始客户端1持有了对文件Z的锁并且被授权可以从Petal读取Z的数据。所以这个时间点客户端1会从Petal读取并缓存Z的内容。之后客户端1也可以在本地缓存中修改Z的内容。 过了一会客户端2也想读取文件Z。但是一开始客户端2并没有对于文件Z的锁所以它要做的第一件事情就是向锁服务器发送Request消息请求对于文件Z的锁 但是锁服务器知道不能给客户端2回复Grant消息因为客户端1现在还持有锁。接下来锁服务器会向客户端1发送Revoke消息 而客户端1在向Petal写入修改数据之前不允许释放锁。所以它现在会将任何修改的内容写回给Petal 写入结束之后客户端1才可以向锁服务器发送Release消息 锁服务器必然会有一个表单记录谁在等待文件Z的锁一旦锁的当前持有者释放了锁锁服务器需要通知等待者。所以当锁服务器收到了这条Release消息时锁服务器会更新自己的表单并最终将Grant消息发送给客户端2 这个时候客户端2终于可以从Petal读取文件Z
这就是缓存一致性协议的工作流程它确保了直到所有有可能私底下在缓存中修改了数据的客户端先将数据写回到Petal其他客户端才能读取相应的文件。所以这里的锁机制确保了读文件总是能看到最新写入文件的数据。 优化
在这个缓存一致性的协议中有许多可以优化的地方。比如锁的懒释放:
每个客户端用完了锁之后不是立即向锁服务器释放锁而是将锁的状态标记为Idle就是一种优化
另一个主要的优化是Frangipani有共享的读锁Shared Read Lock和排他的写锁Exclusive Write Lock。如果有大量的客户端需要读取文件但是没有人会修改这个文件它们都可以同时持有对这个文件的读锁。如果某个客户端需要修改这个已经被大量其他客户端缓存的文件时那么它首先需要Revoke所有客户端的读锁这样所有的客户端都会放弃自己对于该文件的缓存只有在那时当前客户端才可以修改文件。因为没有人持有了这个文件的缓存所以就算文件被修改了也没有人会读到旧的数据。
最后再提一下脏数据写回时机客户端每隔30秒会将所有修改了的缓存写回到Petal中。所以如果某个客户端突然崩溃了我或许会丢失过去30秒的数据但是不会丢更多这实际上是模仿Linux或者Unix文件系统的普通工作模式。在一个分布式文件系统中很多操作都是在模仿Unix风格的文件系统这样使用者才不会觉得Frangipani的行为异常因为它基本上与用户在使用的文件系统一样。 原子性问题
当我做了一个复杂的操作比如说创建一个文件这里涉及到标识一个新的inode、初始化一个inodeinode是用来描述文件的一小份数据、为文件分配空间、在目录中为新文件增加一个新的名字这里有很多步骤很多数据都需要更新。我们不想任何人看到任何中间的状态我们希望其他的客户端要么发现文件不存在要么文件完全存在但是我们绝不希望它看到中间状态。所以我们希望多个步骤的操作具备原子性。
为了实现原子性为了让多步骤的操作例如创建文件重命名文件删除文件具备原子性Frangipani在内部实现了一个数据库风格的事务系统并且是以锁为核心。
简单来说Frangipani是这样实现分布式事务的
在完全完成操作之前Frangipani确保其他的客户端看不到当前客户端的修改。首先当前客户端获取所有读写数据的锁在完成操作之前客户端不会释放任何一个锁。并且为了遵循一致性规则将所有修改了的数据写回到Petal之后客户端才会释放所有的锁。
比如我将文件从一个目录移到另一个目录这涉及到修改两个目录的内容我不想让人看到两个目录都没有文件的状态。为了实现这样的结果Frangipani首先会获取执行操作所需要的所有数据的锁之后完成所有的步骤比如完成所有数据的更新并将更新写入到Petal最后释放锁。
因为我们有了锁服务器和缓存一致性协议我们只需要确保我们在整个操作的过程中持有所有的锁我们就可以无成本的获得这里的不可分割原子事务。
所以为了让操作具备原子性Frangipani持有了所有的锁。对于锁来说这里有一件有意思的事情Frangipani使用锁实现了两个几乎相反的目标。对于缓存一致性Frangipani使用锁来确保写操作的结果对于任何读操作都是立即可见的所以对于缓存一致性这里使用锁来确保写操作可以被看见。但是对于原子性来说锁确保了人们在操作完成之前看不到任何写操作因为在所有的写操作完成之前客户端持有所有的锁。 故障恢复问题
我们需要能正确应对这种场景一个客户端持有锁并且在一个复杂操作的过程中崩溃了。比如说一个客户端在创建文件或者删除文件时它首先获取了大量了锁然后会更新大量的数据在其向Petal回写数据的过程中一部分数据写入到了Petal还有一部分还没写入这时客户端崩溃了并且锁也没有释放因为数据回写还没有完成。这是故障恢复需要考虑的有趣的场景。
这里有一些很直接的解决方式但是都存在些许问题:
其中一种处理方法是如果发现客户端崩溃了就释放它所有的锁。假设客户端在创建新文件它已经在Petal里将文件名更新到相应的目录下但是它还没有将描述了文件的inode写入到PetalPetal中的inode可能还是一些垃圾数据这个时候是不能释放崩溃客户端持有的锁因为其他客户端读取这个文件可能读出错误的数据。另一种处理方法是不释放崩溃了的客户端所持有的锁。如果客户端在向Petal写入数据的过程中崩溃了因为它还没有写完所有的数据也就意味着它不能释放所有的锁。所以简单的不释放锁是正确的行为因为这可以将这里的未完成的更新向文件的读取者隐藏起来这样没人会因为看到只更新了一半的数据而感到困惑了。但是另一方面如果任何人想要使用这些文件那么他需要永远等待锁因为我们没有释放这些锁。
第二种方式也不可行因为我们绝对需要释放锁这样其他的客户端才能使用这个系统使用相同的文件和目录。但同时我们也需要处理这种场景崩溃了的客户端只写入了与操作相关的部分数据而不是全部的数据。
Frangipani与其他的系统一样需要通过预写式日志Write-Ahead LogWAL实现故障可恢复的事务Crash Recoverable Transaction。
当一个客户端需要完成涉及到多个数据的复杂操作时在客户端向Petal写入任何数据之前客户端会在Petal中自己的Log列表中追加一个Log条目这个Log条目会描述整个的需要完成的操作。只有当这个描述了完整操作的Log条目安全的存在于Petal之后客户端才会开始向Petal发送数据。所以如果客户端可以向Petal写入哪怕是一个数据那么描述了整个操作、整个更新的Log条目必然已经存在于Petal中。
这是一种非常标准的行为它就是WAL的行为。但是Frangipani在实现WAL时有一些不同的地方。 第一个是在大部分的事务系统中只有一个Log系统中的所有事务都存在于这个Log中。当有故障时如果有多个操作会影响同一份数据我们在这一个Log里就会保存这份数据的所有相关的操作。所以我们知道对于一份数据哪一个操作是最新的。但是Frangipani不是这么保存Log的它对于每个客户端都保存了一份独立的Log。
另一个有关Frangipani的Log系统有意思的事情是客户端的Log存储在Petal而不是本地磁盘中。几乎在所有使用了Log的系统中Log与运行了事务的计算机紧紧关联在一起并且几乎总是保存在本地磁盘中。但是出于优化系统设计的目的Frangipani的客户端将自己的Log保存在作为共享存储的Petal中。每个客户端都拥有自己的半私有的Log但是却存在Petal存储服务器中。这样的话如果客户端崩溃了它的Log可以被其他客户端从Petal中获取到。所以Log存在于Petal中。
这里其实就是每个客户端的独立的Log存放在公共的共享存储中这是一种非常有意思并且反常的设计。 log内容
每个客户端的Log存在于Petal已知的块中并且每个客户端以一种环形的方式使用它在Petal上的Log空间。Log从存储的起始位置开始写当到达结尾时客户端会回到最开始并且重用最开始的Log空间。所以客户端需要能够清除它的Log这样就可以确保在空间被重复利用之前空间上的Log条目不再被需要。
每个Log条目都包含了Log序列号这个序列号是个自增的数字每个客户端按照12345为自己的Log编号这里直接且唯一的原因在论文里也有提到如果客户端崩溃了Frangipani会探测客户端Log的结尾Frangipani会扫描位于Petal的Log直到Log序列号不再增加这个时候Frangipani可以确定最后一个Log必然是拥有最高序列号的Log。所以Log条目带有序列号是因为Frangipani需要检测Log的结尾。
除此之外每个Log条目还有一个用来描述一个特定操作中所涉及到的所有数据修改的数组。数组中的每一个元素会有一个Petal中的块号Block Number一个版本号和写入的数据。类似的数组元素会有多个这样就可以用来描述涉及到修改多份文件系统数据的操作。
这里有一件事情需要注意Log只包含了对于元数据的修改比如说文件系统中的目录、inode、bitmap的分配。Log本身不会包含需要写入文件的数据所以它并不包含用户的数据它只包含了故障之后可以用来恢复文件系统结构的必要信息。例如我在一个目录中创建了一个文件F那会生成一个新的Log条目里面的数组包含了两个修改的描述一个描述了如何初始化新文件的inode另一个描述了在目录中添加的新文件的名字。 这里比较疑惑一点在于: 如果Log只包含了元数据的修改那么在故障恢复的时候文件的内容都丢失了也就是对于创建一个新文件的故障恢复只能得到一个空文件这不太合理。 当然Log是由多个Log条目组成每个条目由块号版本号写入数据三部分组成。
为了能够让操作尽快的完成最初的时候Frangipani客户端的Log只会存在客户端的内存中并尽可能晚的写到Petal中。这是因为向Petal写任何数据包括Log都需要花费较长的时间所以我们要尽可能避免向Petal写入Log条目就像我们要尽可能避免向Petal写入缓存数据一样。
所以这里的完整的过程是。当客户端从锁服务器收到了一个Revoke消息要自己释放某个锁它需要执行好几个步骤。
首先客户端需要将内存中还没有写入到Petal的Log条目写入到Petal中。之后再将被Revoke的Lock所保护的数据写入到Petal。最后向锁服务器发送Release消息。
这里采用这种流程的原因是在第二步我们向Petal写入数据的时候如果我们在中途故障退出了我们需要确认其他组件有足够的信息能完成我们未完成修改。先写入Log将会使我们能够达成这个目标
这些Log记录是对将要做的修改的完整记录。所以我们需要先将完整的Log写入到Petal。之后客户端可以开始向Petal写入其修改了的块数据这个过程中可能会故障也可能不会。如果客户端完成了向Petal写入块数据它就能向锁服务发送Release消息。所以如果我的客户端修改了一些文件之后其他的客户端想要读取这些文件上面的才是一个实际的工作流程。锁服务器要我释放锁我的客户端会先向Petal写入Log之后再向Petal写入脏的块数据最后才向锁服务器发送Release消息。之后其他的客户端才能获取锁并读取相应的数据块。这是没有故障的时候对应的流程。 如果我们收到了一个针对特定文件Z的Revoke消息客户端会将整个Log都写入Petal或许写入完整的Log显得没那么必要在这里可以稍作优化。如果Revoke要撤回的锁对应的文件Z只涉及第一个Log并且客户端中的其他Log并没有修改文件Z那么可以只向Petal写入一个Log剩下的Log之后再写入这样可以节省一些时间。 故障恢复
当客户端需要重命名文件或者创建一个文件时首先它会获得所有需要修改数据的锁之后修改自身的缓存来体现改动。但是后来客户端在向Petal写入数据的过程中故障了。客户端可能在很多个位置发生故障但是由于前面介绍过的工作流程Frangipani总是会先将自身的Log先写入到Petal。这意味着如果发生了故障那么发生故障时可能会有这几种场景
要么客户端正在向Petal写入Log所以这个时候客户端必然还没有向Petal写入任何文件或者目录。要么客户端正在向Petal写入修改的文件所以这个时候客户端必然已经写入了完整的Log。
当持有锁的客户端崩溃了之后发生的第一件事情是锁服务器向客户端发送一个Revoke消息但是锁服务器得不到任何响应之后才会触发故障恢复。如果没有人需要用到崩溃客户端持有的锁那么基本上没有人会注意到客户端崩溃了。假设一个其他的客户端需要崩溃了的客户端所持有的一个锁锁服务器会发出Revoke消息但是锁服务器永远也不会从崩溃了的客户端收到Release消息。
Frangipani出于一些原因对锁使用了租约当租约到期了锁服务器会认定客户端已经崩溃了之后它会初始化恢复过程。实际上锁服务器会通知另一个还活着的客户端说看客户端1看起来崩溃了请读取它的Log重新执行它最近的操作并确保这些操作完成了在你完成之后通知我。在收到这里的通知之后锁服务器才会释放锁。这就是为什么日志存放在Petal是至关重要的因为一个其他的客户端可能会要读取这个客户端在Petal中的日志。
发生故障的场景究竟有哪些呢
第一种场景是客户端1在向Petal写入任何信息之前就故障了。这意味着当客户端2执行恢复查看崩溃了的客户端的Log时发现里面没有任何信息自然也就不会做任何操作。之后客户端2会释放客户端1所持有的锁。客户端1或许在自己的缓存中修改了各种各样的数据但是如果它没有在自己的Log存储区写入任何信息那么它也不可能在Petal中写入任何它修改的块数据。我们会丢失客户端1的最后几个操作但是文件系统会与客户端1开始修改之前保持一致。因为很明显客户端1没能走到向Petal写Log那一步自然也不可能向Petal写入块数据。第二种场景是客户端1向Petal写了部分Log条目。这样的话执行恢复的客户端2会从Log的最开始向后扫描直到Log的序列号不再增加因为这必然是Log结束的位置。 客户端2会检查Log条目的更新内容并向Petal执行Log条目中的更新内容。比如Petal中的特定块需要写入特定的数据这里对应的其实就是客户端1在自己本地缓存中做的一些修改。所以执行恢复的客户端2会检查每个Log条目并重新向Petal执行客户端1的每一条Log。当客户端2执行完客户端1存放在Petal中的Log它会通知锁服务器之后锁服务器会释放客户端1持有的锁。这样的过程会使得Petal更新至故障客户端1在故障前的执行的部分操作。或许不能全部恢复客户端1的操作因为故障客户端可能只向Petal写了部分Log就崩溃了。同时除非在Petal中找到了完整的Log条目否则执行恢复的客户端客户端2是不会执行这条Log条目的所以这里的隐含意思是需要有类似校验和的机制这样执行恢复的客户端就可以知道这个Log条目是完整的而不是只有操作的一部分数据。这一点很重要因为在恢复时必须要在Petal的Log存储区中找到完整的操作。所以对于一个操作的所有步骤都需要打包在一个Log条目的数组里面这样执行恢复的客户端就可以要么全执行操作的所有步骤要么不执行任何有关操作的步骤但是永远不会只执行部分步骤。这就是当在向Petal写入Log时发生了故障的修复过程。 另一个有趣的可能是客户端1在写入Log之后并且在写入块数据的过程中崩溃了。先不考虑一些极其重要的细节执行恢复的客户端2并不知道客户端1在哪个位置崩溃的它只能看到一些Log条目同样的客户端2会以相同的方式重新执行Log。尽管部分修改已经写入了Petal客户端2会重新执行修改。对于部分已经写入的数据相当于在相同的位置写入相同的数据。对于部分未写入的数据相当于更新了Petal中的这部分数据并完成了操作。
上面的描述并没有涵盖所有的场景下面的这个场景会更加复杂一些。如果一个客户端完成了上面流程的步骤12在释放锁的过程中崩溃了进而导致崩溃的客户端不是最后修改特定数据的客户端。具体可以看下面这个例子:
假设我们有一个客户端1它执行了删除文件d/f的操作。之后有另一个客户端2在删除文件之后以相同的名字创建了文件当然这是一个不同的文件。所以之后客户端2创建了同名的文件d/f。在创建完成之后客户端1崩溃了所以我们需要基于客户端1的Log执行恢复这时可能有第三个客户端3来执行恢复的过程。 这里的时序表明客户端1删除了一个文件客户端2创建了一个文件客户端3做了恢复操作。有可能删除操作仍然在客户端1的Log中当客户端1崩溃后客户端3需要读取客户端1的Log并重新执行客户端1的Log中的更新。因为删除文件的Log条目仍然存在于客户端1的Log中如果不做任何额外的事情客户端3会删除这个文件d/f。但是实际上客户端3删除的会是客户端2稍后创建的一个完全不同的文件。
这样的结果是完全错误的因为需要被删除的是客户端1指定的文件而不是客户端2创建的一个相同名字的文件。因为客户端2的创建是在客户端1的删除之后所以我们不能只是不经思考的重新执行客户端1的Log客户端1的Log在我们执行的时候可能已经过时了其他的一些客户端可能已经以其他的方式修改了相同的数据所以我们不能盲目的重新执行Log条目。
Frangipani是这样解决这个问题的通过对每一份存储在Petal文件系统数据增加一个版本号同时将版本号与Log中描述的更新关联起来。在Petal中每一个元数据每一个inode每一个目录下的内容都有一个版本号当客户端需要修改Petal中的元数据时它会向从Petal中读取元数据并查看当前的版本号之后在创建Log条目来描述更新时它会在Log条目中对应的版本号填入元数据已有的版本号加1。
之后如果客户端执行到了写数据到Petal的步骤它也会将新的增加了的版本号写回到Petal。
所以如果一个客户端没有故障并且成功的将数据写回到了Petal。这样元数据的版本号会大于等于Log条目中的版本号。如果有其他的客户端之后修改了同一份元数据版本号会更高。
所以实际上客户端3看到的客户端1的删除操作对应的Log条目会有一个特定的版本号它表明由这个Log条目影响的元数据对应版本号3举例。 客户端2的修改在客户端1崩溃之前所以客户端1必然已经释放了相关数据的锁。客户端2获得了锁它会读取当前的元数据可以发现当前的版本号是3当客户端2写入数据的时候它会将版本号设置为4。 之后当客户端3执行恢复流程时客户端3会重新执行客户端1的Log它会首先检查版本号通过查看Log条目中的版本号并查看Petal中存储的版本号如果Petal中存储的版本号大于等于Log条目中的版本号那么客户端3会忽略Log条目中的修改因为很明显Petal中的数据已经被故障了的客户端所更新甚至可能被后续的其他客户端修改了。所以在恢复的过程中客户端3会选择性的根据版本号执行Log只有Log中的版本号高于Petal中存储的数据的版本时Log才会被执行。
这里有个比较烦人的问题就是客户端3在执行恢复但是其他的客户端还在频繁的读取文件系统持有了一些锁并且在向Petal写数据。客户端3在执行恢复的过程中客户端2是完全不知道的。客户端2可能还持有目录 d的锁而客户端3在扫描故障客户端客户端1的Log时需要读写目录d但是目录d的锁还被客户端2所持有。我们该如何解决这里的问题
一种不可行的方法是让执行恢复的客户端3先获取所有关联数据的锁再重新执行Log。这种方法不可行的一个原因是有可能故障恢复是在一个大范围电力故障之后这样的话谁持有了什么锁的信息都丢失了因此我们也就没有办法使用之前的缓存一致性协议因为哪些数据加锁了哪些数据没有加锁在断电的过程中丢失了。
但是幸运的是执行恢复的客户端可以直接从Petal读取数据而不用关心锁。这里的原因是执行恢复的客户端想要重新执行Log条目并且有可能修改与目录d关联的数据它就是需要读取Petal中目前存放的目录数据。接下来只有两种可能要么故障了的客户端客户端1释放了锁要么没有。如果没有的话那么没有其他人不可以拥有目录的锁执行恢复的客户端可以放心的读取目录数据没有问题。如果释放了锁那么在它释放锁之前它必然将有关目录的数据写回到了Petal。这意味着Petal中存储的版本号至少会和故障客户端的Log条目中的版本号一样大因此之后恢复软件对比Log条目的版本号和Petal中存储的版本号它就可以发现Log条目中的版本号并没有大于存储数据的版本号那么这条Log条目就会被忽略。所以这种情况下执行恢复的客户端可以不持有锁直接读取块数据但是它最终不会更新数据。因为如果锁被释放了那么Petal中存储的数据版本号会足够高表明在客户端故障之前Log条目已经应用到了Petal。所以这里不需要关心锁的问题。 小结
本文主要讨论了以下内容:
Petal是什么缓存一致性分布式事务分布式故障恢复
论文还讨论了一下性能但是过了20年之后的今天很难理解这些性能数据。因为作者在一个与今天非常不同的硬件非常不同的环境测试的性能。笼统来说作者展示的性能数据表明随着越来越多的Frangipani客户端加入到系统中系统并没有明显变慢。即使新加入的客户端在频繁的执行文件系统操作并不会影响现有的客户端。这样的话系统可以提供合理的扩展性因为它可以在不减慢现有客户端的前提下增加更多的客户端。
尽管Frangipani有大量有意思且值得记住的技术但是它对于存储系统的演进并没有什么影响。部分原因是Frangipani的目标环境是一个小的工作组人们坐在桌子上的客户端前共享文件。这样的环境现在还存在与某些地方但是却不是分布式存储的主要应用场景。真正的应用场景是一些大型的数据中心、大型网站、大数据运算在这些场景中文件系统的接口相比数据库接口来说就不是那么有用了。比如在大型网站的环境中人们非常喜欢事务但是人们在非常小的数据下才需要事务这些小的数据也就是你会存储在数据库中的数据而不是你会存储在文件系统中的数据。所以这里的一些技术你可以在一些现代的系统中看到类似的设计但是通常出现在数据库中。
另一个大的场景是为大数据运算存储大的文件例如MapReduce。实际上GFS某种程度上看起来就像是一个文件系统但是实际上是为了MapReduce设计的存储系统。但是不论对于GFS也好还是大数据运算也好Frangipani关注在客户端的本地缓存和缓存一致性反而不是很有用。如果你读取10TB的数据缓存基本上没什么用并且会适得其反。所以随着时间的推移Frangipani在一些场合还是有用的但是并不符合在设计新系统时候的需求。
