Structure
- 直到
fsync前文件不保证写入nonvolatile存储 - 原数据在syscall返回时保证写入到nonvolatile(optional)
- 文件last-access时间不保证准确，避免每次读取访问metadata write
所有Frangipani Server写入相同的Petal Disk，redo log在Petal Disk隔离的区域存储。当Frangipani Server crash的时候，其他的Server可以recover。
lock service提供了多读单写锁。
Pros:
- 支持透明的Server添加、删除、failover recovery
- 系统运行时创建backup
Cons:
- Logging发生两次，一次在Frangipani，一次在Petal
- Frangipani无法利用磁盘位置信息(因为Petal没有只是虚拟磁盘)
- Frangipani锁整个文件系统而不是某个block
Disk Layout
Petal的虚拟磁盘有$2^{64}$寻址空间。使用了64KB的块大小。
- 第一个区域保存了configuration
- 第二个区域保存了logs，分成了256个区域
- 第三个区域用来存储allocation bitmap
- 第四个区域保存inodes，每个inode 512 bytes
- 第三个区域保存了小data block，每个4KB，每个文件的最初64KB保存在这个区域，如果超过了64KB，其余的保存在large block
- 剩余的区域保存了large block，每个large block需要1 TB的空间保存寻址空间
Logging and Recovery
使用write-ahead redo logging for metadata，user data没有log。
每一个Frangipani server有着自己的log。
当Server需要进行元数据更新时，先在内存中创建record，log record周期性写入Petal。只有log写入到Petal后才会对metadata进行操作。
log使用循环buffer，回收最旧的25%的log用来存储新的。
如果Frangipani crash，系统最终会发现crash并启动recovery demon。demon隐式的拥有了crash的server的log与locks。demon找到log的开始与结尾，重新排序，redo。之后释放所有的锁与清空log。只要Petal不损坏，Frangipani可以承受任意数量的server failures。
Frangipani使用了以下来处理单个文件多个log的情况：
- write lock只有在将dirty data写入到Petal后才可以改变所有者。（无论是lock holder还是recover demon）
- Frangipani只redo从拥有lock之后的操作。为了保证locking protocol的序列化不被改变。每一个metadata block有着版本号，每次执行操作版本号+1同时记录在log中。只有block的版本号早于log的才会执行recover。（为了避免replay的情况：因为redo的时候只能看到一个server的log）
- 在同一时间只有一个recovery demon
只有metadata有log，user data没有，所以在用户的视角file system在failure之后失去了一致性。（磁盘文件系统的journal一般也是这样，log只记录metadata的改变，可以使用fsync等）
Frangipani在lock被revoke的时候才会讲本地的log与cache写回（如果写入log之前crash，log也会丢失，不过只会丢失这一次的写入，不会影响整个文件系统）。
Synchronization and Cache Coherence
多个Frangipani server修改相同的disk，需要谨慎处理同步问题。
Frangipani使用multiple-reader/single-writer锁。当lock service检测到冲突的锁请求，现有的holder被要求释放或者降级。
read lock允许server从disk中读取文件并且缓存，当释放锁时，需要invalid缓存。
write lock允许server read或者write并且缓存。只有获得write lock时，缓存中的内容才可以于disk中不同。所以当一个server被要求释放或者降级时，需要将dirty data写回。如果降级为read lock可以保留缓存内容。
Coherence Protocol:
- request (WS -> LS)
- grant (LS -> WS)
- revoke (LS -> WS)
- release (WS -> LS)
locks保证了读取时可以看到最后的写
虽然可以直接将cache传输到requester，但是为了简便没有这样设计。因为Frangipani之间互相不会通讯，只会与Petal和lock service通讯；同时当server crash时，只需要处理对应server的log即可。
bitmap划分成为了segment，每一个segment可以单独上lock。未分配的data block或者inode通过对应的bitmap的lock来保护。每一个文件、目录、符号连接都是一个segment，每一个lock保护inode与其对应的文件。
Atomicity
有些操作需要原子性的更新多个被不同lock覆盖的磁盘结构（如创建文件需要修改inode，目录，data），为了避免死锁使用两阶段。首先server决定自身需要获得什么锁，其次将需要获得的锁按照inode地址排序，按顺序获取。server检查第一阶段是否有对象数据改变（我的理解是比如有对目录的操作，目录的锁被其他的server释放后会有目录文件的改变，所以需要重新获得一边所有的锁），如果有，则释放锁并重新执行第一阶段。
user在执行操作前获取全部的lock，获得全部的lock后才会执行操作。
当完成后释放lock。
Lock Service
提供multiple-reader/single-writer锁。锁是sticky的，一个client会持续保持锁直到冲突。
lock service使用租约，当client获取lock时，同时也获取了一个lease。每个lease有过期时间，client需要在过期前renew，否则client处于crash。
Conclusion
Frangipani将server放到了user一侧来执行，减少了系统瓶颈。
Frangipani的lock做了两件事：
- Cache Coherence
- Atomic Transaction
Ideas to remember
complex clients sharing simple storage – maybe scalable
cache coherence
distributed transactions
distributed crash recovery
interactions among the above