概述

Frangipani 是一个网络文件系统。其系统中存在多个工作站运行着 Frangipani 服务和一个叫做 Petal 的共享虚拟磁盘服务。

Frangipani 除了基本的缓存外，还实现了 Write-Back 缓存（其修改文件/文件夹的操作是在本地缓存进行，需要同步才与 Petal 进行同步）。因此其操作是在工作站进行的，Petal 只负责写入读取文件。

挑战

因为使用了缓存，因此我们要确保一致性。即缓存一致性问题，使缓存的数据与实际数据保持一致。

主要问题有：

  • 在一个工作站进行的操作，其他工作站可以看得到。
  • 因为使用了 Write-Back ，在同步过程中出现故障，导致只有一部分数据同步到了 Petal。应该怎样处理？

锁服务

1，概述

Frangipani 的缓存一致性核心由锁保证的。

在 Frangipani 存在锁服务器（简称 LS），其 LS 存储着 locks 表，其记录了文件被哪个工作站持有。

工作站（简称 WS ）中也有一个 locks 表记录自己持有的锁和锁对应的文件内容。但是在 WS 中的锁，分为两种类状态：

  • Busy状态：WS 在修改文件的过程中。
  • Idle状态：修改已经结束，可以释放锁。在 WS 视角中，是释放锁的。在 LC 视角中，该 WS 仍然持有锁。

锁规则：

  • WS 在持有锁时才允许缓存数据。
  • 若修改了数据，将其同步到 Petal 后才允许释放锁。然后将 WS 缓存的记录删除。

2，缓存一致性

WS 与 LS 之间的缓存一致性协议包含以下单向消息：

  • Request 消息：WS 跟 LS 申请锁。
    • 若已被持有，放入队列中，发送 Revoke 消息给持有锁的 WS。
    • 若未持有，立即回复 Grand 消息给 WS。
  • Grand 消息：LS 回复 WS，允许获取锁
  • Revoke 消息：LS 发送给 WS，WS 判断锁的状态：
    • 若锁在 Idle 状态，将数据同步至 Petal，然后发送 Release 消息。
    • 若锁在 Busy 状态，等待其转换未 Idle 状态，然后执行上述操作。
  • Release 消息：WS 发送至 LS 中，表示放弃对应的锁。

以上仅仅介绍以排他锁（写锁）的操作，可以更改分为读锁和写锁，获取更高的效率。

因为在文件被其他 WS 获取后才真正释放锁，因此在未被其他 WS 使用前，可以增加修改操作的效率。

WS 可以每隔一段时间同步数据，避免发生崩溃时造成的所有数据的丢失。

因此对于缓存一致性，其写操作对任何读操作都是可见的。

3，原子性

因为在获取锁时才可以操作文件，确保了在操作完成前看不到任何写操作，因此是原子性的。

Frangipani Log

为了避免在同步至 Petal 中出现崩溃，导致数据错误，Petal 使用预写式日志（Write-Ahead Log，WAL）处理。

WS 的条目不仅保存在 WS 中，也要保存在 Petal 中的。WS 以环形的结构使用在 Petal 上的 Log 空间。

Log 条目的结构为：

  • 一个递增的序列号
  • 需要更改的数据，和对应的 Petal 的块号（Block Number）和版本号

Log 只包含元数据的修改，例如目录、inode、bitmap的分配。不包含需要写入文件的数据。

具体流程：

  • WS 收到来着 LS 的 Revoke 信息。
  • 同步前，WS 会在 Petal 自己的 Log 列表中追加 Log 条目。
  • Petal 存储完整的 Log 条目后，开始发送数据。
  • WS 回复 Release 消息。

若发送数据中途崩溃，Petal 可以按照 Log 条目执行。

其在发送 Log 条目时，可以只发送对应的锁的条目。

故障恢复

1，概述

LS 给 WS 发送 Revoke 消息，WS 需要在租约内回复信息（锁存在租约）。若租约过期了， LS 可以认为 WS 已经崩溃。

LS 认为 WS 崩溃时，会通知其他的 WS，去读取它的 Log，重新执行 Log 内的操作。执行完成后才释放锁。

2，场景

WS1 在向 Petal 写入任何信息之前故障了

WS2 在查看 Log 时，发现没有任何信息。不会做任何操作。

WS1 在故障前写入了部分 Log 条目

WS2 执行部分 Log 条目的操作。因此为了避免意外情况的发生，一个操作的所有步骤都需要在一个 Log 条目中。

WS1 在故障前写入了完整的 Log 条目，但是在写入数据过程中崩溃了

WS2 重新执行其所有 Log 条目操作。

在 WS 重演 Log 条目操作的过程中，Log 条目中的版本号大于文件的版本号才会执行。若不正确表示其文件被一个后面获取锁的 WS 更改过了。