OS09 文件系统

文件系统1：I/O性能、文件系统设计

性能的基本概念

• 响应时间/延迟（response time/latency）：执行操作耗时

• 带宽/吞吐量（bandwidth/throughput）：操作被执行的速率，例如op/s、MB/s，Mbps，GFLOP/s

• 一般而言，延迟随系统吞吐量增大而增大

• 延迟的影响因素：
• 软件：例如使用queue来缓存请求
• 硬件控制器延迟
• I/O设备服务时间

• Queuing行为为在利用率增大时使延迟显著增大

对请求与服务建模

• 假设请求平均到来、到来间隔相对固定，处理时间固定，设到来间隔 ，服务时间， 排队延迟
• 服务速率：每秒能执行的操作
• 到达速率；每秒到来的请求
• 利用率：
• 当U<1时，能保持等待队列始终为空，T_Q固定为接近于0；U>1时，队列将越来越长（过载），T_Q线性增长

• 假设请求的到来存在burst，即一段时间内请求集中到来，会造成严重的排队情况，导致延迟增大

• 使用指数分布建模，“无记忆性”

• 分布的衡量指标：平均值，方差，
• 若分布退化为常数，C=1
• 若分布为指数分布“无记忆性”，C=1，无法根据过去预知未来
• 磁盘的响应时间的分布，C=1.5左右

Queuing Theory

• 适用于长期的、稳定的，到达速率=完成速率的情况

• 请求的到来和完成都服从一定的概率分布

• 假设系统平衡、队列长度无限制

• 有以下参数：
• ：请求到来速率
• ：平均服务时间
• ：服务速率
• ：利用率

• 需要计算的参数：
• ：排队时间
• ：队列长度，约为

• 使用柏松过程建模：
• 无记忆性的排队时间（C=1）
• 总排队时间

提升性能

• 提高每部分的速度

• 并行：适用于解耦合的系统，多个独立的总线/控制器并行运行

• overlap：在等待时进行其他有用工作

• 优化性能提升的瓶颈：优化队列调度策略

• queuing吸收了burst、使任务流更平缓

• 磁盘在以下情况下表现最好：
• 大量顺序读写（有大量请求时可以被piggypack，形成一些顺序读写）
• burst可能会增大延迟，也使piggypack成为可能，可以对请求进行重排序和batching

磁盘调度

• FIFO：请求间公平，但容易产生大量随机读写，导致大量的寻道

• SSTF：Shortest Seek Time First：执行在磁盘上最近的（寻道+旋转开销最小的）请求。缺点是容易导致饥饿。

• SCAN：在既定的周游方向上，选择最近的请求。即不断从小到大、从大到小遍历。能够避免饥饿，同时保持SSTF的优点

• C-SCAN：Circular。周游方向限定（例如只顺时针旋转），不回头。比SCAN更公平，对处于中间位置的数据不偏倚。

网络I/O

• 在现代云系统中十分重要

• 提升网络I/O的方法：
• 对分布式应用建立更好的抽象
• 优化内核的TCP/IP栈
• kernel-bypass：将网络栈放在用户空间下，操控网卡时不用陷入内核态。以及RDMA、smartNIC技术

从存储到文件系统

• 三层抽象：
• I/O API：地址空间，支持很长的buffer
• 文件系统：逻辑索引的block，通常为4KB
• 硬件设备：HDD上，一个文件系统block可能对应物理索引的一些扇区；SSD上，通过闪存传输层，对应物理索引的一些块。

• 构建文件系统：OS的一个层，为磁盘及其他块设备的block抽象为文件、目录等。需要提供以下界面：
• 命名：通过名称而非块号对文件进行索引
• 组织：目录中存放文件名；将文件映射到block
• 保护：严格要求访问权限
• 可靠性：在可能的crash发生时保护文件安全

• OS对文件的观点：
• 在syscall界面，文件是字节的集合（UNIX）。OS不关心在磁盘上存放了什么数据结构
• 在OS内部，文件是一些block的集合（block是逻辑上一次传输的基本单元，而扇区是物理上一次传输的基本单元，block大小一定是扇区大小的整数倍，UNIX中是4KB）

• 当用户需要读取某些字节时：操作系统将对应block取出，返回部分字节

• 当用户需要写入某些字节时，OS取出block、在内存中修改一些部分，写回block

• 真实的I/O以block为单位，小于block的读写需要进行翻译和buffer

磁盘管理

• 磁盘上存放有：
• 文件：逻辑上顺序存放的一些块的集合
• 目录：用户可见的从名字到文件的映射

• 磁盘上的一个扇区通过（柱面、盘面、扇区）三元组定位。OS必须处理损坏的扇区

• 逻辑块地址（Logical Block Addressing，LBA）：每个扇区具有一个整数地址，从整数地址到物理三元组的翻译由磁盘控制器完成。

• 文件系统需要：
• 跟踪文件对应的blocks
• 跟踪目录中名字对应的文件
• 跟踪空闲的磁盘block

• 这些数据结构需要在磁盘的一块区域存储

文件系统设计

• 设计的关键要素：
• 磁盘性能：尽可能增多顺序访问，降低寻道开销
• open before r/w：在打开文件时实现权限检查、提前查询文件具体的位置
• 支持文件大小的动态变更
• 将文件组织成目录
• 谨慎的分配/释放磁盘上的block

• 组成部分：
• 文件路径（path）指向目录结构
• 目录结构存放文件号（inumber）指向文件头
• 文件头/inode，维护数据所在的blocks

• 回忆：打开文件描述（OFD）中存放了文件的inumber

• 组成部分：目录、index数据结构、存储blocks、空闲块map
• 文件名通过目录这一数据结构查找到文件号
• 文件号通过index数据结构（inode）查找到存储中的block

• 打开文件实际上是名称解析操作，将文件名解析为文件号，并记录在打开文件描述中；之后的读写通过文件号作为索引完成

目录抽象

• 是特殊的文件，包括从文件名到文件号的键值对

• 使用一些syscall来访问目录：open/creat/readdir/mkdir/rmdir/link/unlink

• 解析一个文件路径时：
• 访问根目录的文件头
• 读入根目录的block（存放了键值对），查找到下级目录的位置
• 访问下级目录的文件头
• ……
• 读入给定文件的文件头

• 当前工作目录CWD

文件系统2:案例分析

案例分析：FAT-File Allocation Table

• 我们已经通过目录这一抽象将文件名翻译成文件号

• 文件在磁盘中按块存储，读写文件的某个部分时，可用文件号+块号+偏移量（FN,<B,x>）表示。注意此时块号是逻辑上的，不一定在磁盘中物理上相邻。例如，file_read 31, <2,x>

• 将文件号+块号+偏移量翻译成磁盘的物理位置，这一过程通过FAT完成。FAT是一个结点数组（表）：
• 可以以文件号作为索引在FAT中找到本文件的第一个结点。这是一个链表头，文件的每个块对应的结点在FAT中以链表形式存储。
• 翻译时，顺着链表依次访问数据结点，直到到达对应块号的结点
• 某一文件对应的链表，各结点在FAT中的位置是乱序的。

• FAT中未使用的部分标记为空闲。需要增加结点时，可以顺序扫描也可以通过维护free-list

• FAT也需要持久性地保存在磁盘中。

• 对磁盘格式化时，需要将扇区置零。同时将FAT的所有结点置为free；快速格式化时，可以仅直接重置FAT。

• FAT中的目录维护从文件名到文件号的映射，是一个顺序表，每个元素有三项数据：文件名、文件号、下一顺位元素地址。翻译时需要进行线性检索。在FAT中，文件属性被记录在目录中，而非与文件直接关联。根目录总是被存储在磁盘的编号为2的块中（不存在0/1）

• 优点：实现简单、轻量级，适合于嵌入式设备等。不存在碎片（允许乱序）

• 缺点：
• 文件号-磁盘位置的翻译，最坏和平均时间开销均为线性。大文件翻译过程耗时长。
• 顺序访问文件中的块，FAT翻译效率高，磁盘读写效率不一定高（文件块在磁盘上可能不连续）
• 随机访问文件中的块，FAT翻译效率也会降低（不断遍历链表）

案例分析：UNIX FILE SYSTEM

• Unix系统中，文件号用于作为索引访问inodes数组。每个inode对应一个文件，并存储其元数据。这里文件属性被记录在文件对应inode中，而非目录中。允许多个文件名（目录条目）指向同一个文件。

• Inode内部：
• 存放文件元数据（用户、组、权限、时间）
• 使用多层次树结构来维护从文件块+偏移量到磁盘块的映射。
• 第一部分：直接指针，至多12个，对于大小不超过48KB的文件足够。按照统计数据，48KB可以覆盖70%左右的文件。
• 第二部分：间接指针，一个。指向一个大小为4KB的中间块，存放1024个指针直接指向文件块，共覆盖4MB磁盘区域
• 第三部分：双重间接指针（Double Indirect Pointer），一个。两级中间块，共覆盖4GB磁盘区域

案例分析：Berkeley FAST FILE SYSTEM

• inode结构与UNIX BSD4.1一致。

• inode集中在外部轨道上。一次读写头剐蹭就可能损坏所有文件的inode；且inode离实际文件位置很远

• 创建文件时不清楚之后的大小，难以分配合适的连续空间

• 将inode分布在更靠近数据的轨道上。通常情况下，同一目录下的文件的inode会被存储在相同的柱面组里。这使得ls操作十分快速。也使得数据块、元数据、freelist在同一个块组中，目录与其中的文件在同一个块组中，交错访问效率更高。

• 新文件块的“首次空闲”分配策略
• 文件扩展时的分配逻辑：首先尝试在位图中连续分配新块。若无法连续分配，则选择块组内新的空闲块范围。
• 空间分布特征：起始部分：可能存在少量小碎片。末尾部分：大段连续空闲块（适合大文件顺序写入）。
• 优势：减少碎片化。大文件获得连续布局，提升读写性能。

• 使用bitmap来实现freelist

• 尝试连续地分配文件

• 保持磁盘有10%的空余用于方便增删查改；块组内预留空间：避免因完全写满导致性能下降或无法扩展文件。

• Skip-Sector Positioning：如果文件各个块在磁道上连续存储，在两次读写间隙处理器可能需要处理前面的块，此时磁盘会继续旋转，导致错过下一个连续的磁盘块。因此SSP将同一个文件的各个扇区交错存储。也可预先一次性读取然后缓存，等待下一次读取

• 对小文件和大文件都十分高效，且局部性较好

• 元数据和数据的局部性较好

• 无需解碎片化

• 对微文件低效（仍需inode和数据块）

• 文件在磁盘上相对连续时，编码比较低效。

• 需要预留空间放置碎片。

硬链接和软链接

硬链接（Hard Links）

• 本质：目录中文件名到文件编号（inode）的映射。

• 创建：
• 文件首次创建时自动生成第一个硬链接。
• 通过 link() 系统调用添加额外硬链接。

• 删除：
• 使用 unlink() 移除链接。
• 文件内容实际删除条件：无剩余硬链接（inode 引用计数归零）。

软链接（Symbolic Links）

• 本质：存储目标文件路径的快捷方式。

• 目录结构对比：
• 普通条目：<文件名, 文件编号>
• 软链接：<文件名, 目标文件名>

• 特性：
• 每次访问时动态解析目标路径（可能失败，如目标被删除）。
• 通过 symlink 系统调用创建。

目录遍历过程

1. 根目录 /
• 内核预配置根目录的 inode 编号（如 2）。
• 从磁盘读取 inode 2，获取其直接/间接块指针。
• 定位根目录数据块（如块 49358），扫描找到 home 的 inode 编号（如 8086）。

2. 目录 /home
• 读取 inode 8086，获取数据块（如 7756）。
• 扫描块内容，找到 pkuos 的 inode 编号（如 732）。

3. 目录 /home/pkuos
• 读取 inode 732，获取数据块（如 12132）。
• 扫描块内容，找到 stuff.txt 的 inode 编号（如 9909）。

4. 文件 /home/pkuos/stuff.txt
• 读取 inode 9909，建立文件描述符以访问其数据块。
• 权限检查：逐级验证路径中每个目录及目标文件的权限。

• 逐层解析路径，通过 inode 定位数据块。

• 每次目录访问需权限验证。

目录的改进

• 目录使用顺序存储时，顺序遍历开销很大

• 使用B树这一数据结构维护目录

案例分析：New Tech File System（NTFS）

• 现代Windows系统默认使用

• 可变长度拓展

• 使用Master File Table维护文件号到磁盘位置的映射。每个条目至多占用1KB。几乎是属性-值的键值对序列，存放元数据和数据。

• MFT的每个条目存放：
• 文件元数据
• （小文件）直接存放文件数据
• （中文件）文件数据拓展表（每个条目包括起始块和大小，指向一块在磁盘中连续的区域）
• （大文件）指向其他MFT条目，其中维护更多的拓展list

• 目录：
• 通过B树实现
• 文件号用户在MFT中标识条目
• MFT条目总是有文件名这一属性：可读名称、文件号、上级目录
• 实现硬链接：条目中存放多个文件名属性

文件系统3:缓冲，可靠性，事务

mmap

• 传统IO需要在用户内存中的缓冲区和磁盘中的文件进行显式的传输
• 这可能在内存中存放同一文件的多份拷贝，增加系统调用，降低性能

• 可以直接将文件映射入一块用户地址空间，当用户程序访问时，将对应文件页调入物理内存，在物理内存中读写，最后将其写回磁盘

• mmap时，对应虚拟地址的页表项被标记为invalid；触发page fault后，handler查询补充页表，获取映射的文件位置，再查询文件系统，从磁盘中调页到物理内存

• 系统调用：void* mmap (void *addr, size_t len, int prot, int flags, int fd, off_t offset);
• addr不为NULL时，指定内核将文件映射到从addr开始的一片连续的虚拟地址；为NULL时，由内核自行决定，并返回首地址。
• 内核自行决定的地址可能在数据段之上、堆之下

• 当多个进程对同一文件调用mmap时，内核可以只在物理内存中存放一个副本，令两个进程的虚拟地址都指向它，从而实现共享。按要求决定是否标记为COW

Buffer Cache（File System Caching）

• 动机：为了满足用户访问文件的需要，内核必须将磁盘中的文件拷贝进物理内存，在用户程序访问结束后，若有修改，将脏页写回磁盘。考虑局部性，可以将磁盘数据缓存在内存中

• Buffer Cache：物理内存也可以用来缓存内核资源，例如目录、频繁使用的磁盘块、空闲位图

• 核心功能：
• 缓存已访问的数据：存储最近读写的磁盘数据，后续相同请求可直接从内存返回。
• 写回延迟（Write-back）：允许对缓存的修改暂时不写回磁盘，提升写入性能。
• 按需加载：仅在应用程序实际请求数据时才从磁盘加载到缓存（被动缓存）。

• 用户进程访问文件的全过程：
• 使用open系统调用向内核传递文件地址；内核通过目录将文件地址翻译为inum，从对应的inode中获得文件在磁盘上的位置，将部分数据拷贝至物理内存
• 使用read系统调用向内核传递文件描述符；内核通过文件描述符表-文件表得到inum号，从inode中提取信息，若对应文件块已经被加载到物理内存中，则再拷贝一份到用户缓冲区即可
• 使用write与read近似，但脏页最后需要被写回磁盘

• 在系统软件中全部实现，不像cache和TLB一样涉及硬件

• 块在“空闲”和“使用中”之间多了过渡态：从磁盘中预加载；正在写回磁盘

• 物理内存块可以用于多种目的：inode、目录、文件、空闲位图

• 当程序exit后，驱逐关联的文件块（脏的写回）

• 替换策略：LRU。可以接受完全LRU策略的开销
• 优点：在总体上表现出色，只要内存足够大以容纳全部工作集
• 缺点：若有些应用程序扫描整个文件系统，许多缓存的数据只被使用一次就会被清除
• 有些OS允许用户指定替换策略，例如“Use Once”

• cache size：OS应该为buffer cache分配多少比例的内存？
• 若分配过多内存，无法运行较多的应用
• 若分配过少内存，无法充分发挥caching性能，许多应用可能运行缓慢
• 解决方案：动态设置buffer cache比例，使得调页&访问文件的比例均衡

File System Prefetching

• Read Ahead Prefetching：提早取出顺序的块
• 既定事实：大部分文件访问都是按顺序的
• 电梯算法（在磁道上来回往复，有限寻找顺路访存请求并执行）可以给并发的应用提供有效的prefetch

• 把握预取的规模：
• 预取太多将请求的延迟暴露给其他应用
• 预取太少将导致寻道和旋转延迟过高（在并发文件请求中）

Delayed Writes

• Buffer cache是一种写回的cache，对其的写被视为延迟写（delayed write）

• write系统调用将用户空间中的数据写入内核中的buffer cache（内存-内存，速度快，可以快速返回）

• read直接从内核的buffer cache中读，因此write的内容可以反映在read中（满足同步性）

• 当buffer cache满时，或者周期性地刷新时，write向buffer cache写入的数据最终被写入磁盘。

• 优点：
• 对文件的写不需要被写回磁盘，而是被缓存在cache中，可以快速完成write系统调用。
• 不强制要求立即写回后，磁盘调度器可以通过电梯算法来灵活地重新安排写操作，避免随机寻道
• 延迟块分配：可以同时给一个文件分配多个块，使它们之间连续
• 许多文件最终并不会被写入磁盘，例如只是作为多进程共享的内存区域。此时buffer cache可以避免不必要的磁盘访问

Buffer Caching和按需调页的区别

• 按需调页：
• 由于要管理的物理页帧数量庞大，只能使用近似LRU算法（时钟算法），以避免陷入内核态。
• 只有当物理内存将满时，才将最近不使用的页换出

• Buffer Caching：
• 可以使用完全LRU算法，因为实在内核层面（软件）对cache进行管理
• 周期性地将脏块写回磁盘，即使其最近被使用过。原因：为可能的crash做好准备，降低数据丢失。（Linux系统每30s写回一次）

• 周期性写回磁盘并没有从根源上避免数据丢失：当系统crash时，cache中仍然可能有未写回的脏块。
• 如果脏块是目录，那么可能导致磁盘空间泄漏（丢失指向文件inode的指针）
• 使得文件系统不一致（inconsistent）
• 文件系统需要恢复机制！！

文件系统需要满足的性质

• 可用性（Availability）：文件系统可以接受并处理请求的概率。
• 使用“9”的个数作为衡量指标。例如99.9%记为“3个9”
• 主要考察可能的失败（failure）概率

• 持久性（Durability）：文件系统在错误发生时恢复数据的能力
• 主要考察对错误的容忍度（鲁棒性）
• 持久性不能推出可用性：在磁盘中的数据是持久的（durable），但当机器crash后可能无法访问

• 可靠性（Reliability）：在规定的条件下，在特定时间内，系统或组件执行其所需功能的能力
• 通常比单一的可用性要求更强：要求系统不仅能“上线（up）”，还要能正确地工作
• 包含可用性、安全性（security）、错误容忍度/持久性
• 必须要求数据能在系统crash、磁盘crash和其他问题中幸存下来

增强持久性

• 磁盘块中包含Reed-Solomon纠错码（ECC，error correcting codes），用于处理磁盘驱动的小瑕疵

• 为了使写操作在短期内能幸免（当crash发生时，不导致不一致性错误）
• 要么放弃延迟写策略，在每次写操作时都直接写入磁盘
• 要么使用特殊的，有后备电源的RAM（称为非易失性RAM，也即Non-valatile RAM， NVRAM），在Buffer Cache机制下存放脏块

• 为了使写操作在长期内能幸免
• 需要复制/冗余（replicate），为数据保留不止一份拷贝
• 重要要素：失败独立性（Independence of Failure）
• 尽可能解耦不同拷贝，将拷贝存放在关联度很低的不同地方

RAID：独立磁盘冗余阵列

• Redundant Array of Independent Disks

• 将多个物理磁盘组合成逻辑单元，以增强可靠性、性能和容量

• 是对数据存储的虚拟化：在多个物理磁盘驱动的基础上，构建一个逻辑磁盘驱动

• RAID1:磁盘映像
• 每块磁盘都具有一块“影子磁盘”，它们执行完全相同的操作
• 适用环境：高IO吞吐量，高可用性要求
• 开销最为昂贵：100%容量开销
• 牺牲写时带宽：一次逻辑写等于两次物理写
• 读操作可以被优化：从任意一块物理磁盘中读即可。可以并行读取
• 错误恢复：一块磁盘crash，更换新磁盘并将影子磁盘中的数据拷贝到其中。可以在系统中维护热备盘（hot spare），当RAID1阵列中某块磁盘故障时，自动替换故障盘，并开始同步数据、恢复冗余状态

• RAID5:分布式校验
• 数据条带化，分块写入不同磁盘。（以此增大带宽）
• 不同磁盘之间的块彼此对齐，所有磁盘的同一位置的磁盘块构成一个条带单元（stripe unit）
• 每个条带单元中有一个校验块，存储单元其他块的异或值。这样当一块磁盘故障时，通过其他磁盘可以恢复该磁盘的信息
• 不同条带单元的校验块均匀分布在不同磁盘上。
• RAID5的缺点：当今磁盘容量越来越大，单个校验块不够。恢复故障磁盘耗时太长，在恢复过程中，其他磁盘可能再次发生故障，导致无法恢复。

• RAID6:双备份，允许阵列中两块磁盘发生故障。需要更复杂的纠删码（Erasure Code），例如奇偶码

• 通用的纠删码：Reed-Solomon code
• m个数据段，生成n-m个数据段（纠错码）
• 可以容忍n-m个故障同时发生

• 地理复制（跨地域多副本存储）通过在不同地理位置存储数据的多个副本，显著提升持久性和可用性。即使整个区域发生故障（如自然灾害、断电或网络攻击），数据仍可从其他位置访问。
• 数据在多个独立故障域（如不同数据中心、云区域或国家）存储副本。
• 读取可用性高：没有纠错码的简单拷贝模式下，读取任意拷贝均可；有纠错码模式下，在n块磁盘中选择m块读取
• 写入可用性较低（权衡点）
• 强一致性 → 必须写入所有副本才算成功（任一副本故障会导致写入失败）。
• 最终一致性 → 允许短暂不一致，但可能冲突（如DynamoDB、Cassandra）。

常见 RAID 级别

关键概念

• 条带化（Striping）：数据分块并行写入多个磁盘（如 RAID 0、5、6）。

• 镜像（Mirroring）：数据完全复制到另一磁盘（如 RAID 1）。

• 校验（Parity）：通过计算校验位实现冗余（如 RAID 5、6），故障后可通过校验恢复数据。

优缺点对比

• RAID 0：速度快，但无冗余，任一磁盘故障导致数据全毁。

• RAID 1：高可靠性，但存储利用率仅 50%。

• RAID 5/6：兼顾性能与冗余，但写入时需计算校验，性能有损耗。

• RAID 10：高性能 + 高容错，但成本高（需至少 4 块盘）。

增强文件系统可靠性

• 若磁盘断电或软件崩溃：
• 一些进行中的操作可能完成
• 一些进行中的操作可能丢失
• 对一个块的覆写可能部分完成

• 使用RAID不一定能处理好这些错误
• 对写入的错误状态缺少保护措施
• 若RAID阵列中的某一硬盘没有被写入，将导致纠删码失效

• 文件系统需要持久性（作为下限）
• 先前存储的数据（在一些恢复步骤后）可以被恢复/取回

• 存储可靠性问题：
• 逻辑上单个文件操作，可能涉及对多个物理磁盘块的更新
• 为了提高性能，我们需要并发操作
• 如何在并发更新多个物理磁盘块时，仍能保持数据一致性？

• 在单个逻辑文件操作引发的一系列关联物理块更新中，崩溃或断电可能导致数据不一致问题

• 两种可靠性方式：
• 谨慎排序并恢复
• 版本化与写时复制

文件系统4:事务&分布式决策

可靠性方式：谨慎排序

• 将文件操作以特定顺序执行，使得对错误鲁棒

• 文件操作，先分配数据块，再写入数据块，再分配inode，再写入inode，再更新空闲位图，再更新目录中文件名到inum的键值对，最后更新目录中的修改时间。

• 从崩溃中恢复时，遍历全盘的数据结构，检查是否存在未完成的操作。若有，根据需要进行清理/继续。该恢复操作与磁盘尺寸成正比。
• 先扫描inode表，如果存在未链接的文件（不在任何目录中），将其删除或移入“失物招领”目录（lost & found dir）
• 将空闲块位图与inode树比较
• 扫描目录，寻找是否有未更新的的更新/访问时间

• 使用FAT和FFS来保护文件系统的数据结构。许多应用级恢复机制（例如Word）

实例：FFS/fsck

可靠性方式：版本化&写时复制

• 修改文件时生成新版本，而非直接覆盖。新版本文件可以复用未修改的块，仅写入变动的部分。如果文件通过树结构组织，仅需要更新一条路径

• 新旧版本通过指针结构关联，原子提交（只有在所有修改完成后，才原子化地修改指针）。

• 崩溃发生时只需要回退到上一有效指针即可

• 性能优化：批量更新（Batching），多个操作打包提交，减少指针切换开销。

• 该方式在网络文件服务器中被使用。NetApp‘s Write Anywhere File Layout（WAFL）；ZFS（在Sun/Oracle系统中）；OpenZFS

实例：ZFS/OpenZFS

• 可变尺寸的块：512B-128KB

• 使用对称树来组织文件，以便在我们制作拷贝时通过树的层级知道文件的大小

• 存储带版本号的指针

• 批量写入：收到写请求时，先缓存一定数量的写，到达一定数量后再打包成一个事务组（Transaction Group，TXG），使用它们创建新版本

• 在每个block group中，空闲的空间以区段树的方式呈现。延迟更新：释放空间时，先记录到日志，暂不更新主区段树；等到block group被激活（TXG提交时），批量处理日志中的空闲空间变更

其他通用的可靠性解决方案

• 使用事务（transaction）来表示原子化的更新
• 将多个相关的更新打包，要求它们原子化。也即：如果在这些更新执行中发生了崩溃，那么系统状态要么是更新全部完成，或者是一个都没有完成
• 现代文件系统使用事务来更新文件系统的数据结构和元数据
• 许多应用实现了自己的事务系统

• 为媒介错误提供备份
• 媒介采用纠错码等备份机制
• 在不同媒介之间备份

• 在更新文件时，先使用一个临时文件记录更改，再重命名（多在应用层面）

事务

• 动机：操作共享数据结构时的关键区（critical zone）；将原子化更新的概念从内存拓展到稳定存储

• 事务是一串原子化的读写操作，将系统从一个一致状态转移到另一个。（consistent state）

• 事务的典型结构：
• 开始事务：获取id
• 进行一系列更新。如果此时发生任何错误，或与任何其他事务发生冲突，则回滚到事务开始前
• 提交事务（commit）

• 实现事务的原子性：一个简单的操作，例如写数据/向数据结构中添加基础元素，是原子化的

基于事务的文件系统

• 通过使用日志（log）达到更高的可靠性
• 所有变更都以事务的形式呈现
• 当事务被写入日志时，即被视为提交
• 此时数据强制写入磁盘以确保可靠性
• 使用NVRAM加速此过程（作为持久化存储，替代磁盘接收日志，避免磁盘IO延迟）
• 即使文件系统未更新完毕，数据仍保存在日志中。

• 日志存储在非易失的NVRAM上

• Log-Structed文件系统：没有主存储，数据始终以日志形式存储，日志不断增加，修改某一事务只是标记为无效而非立刻擦除；日志会逐渐变得杂乱，需要定期整理回收（GC）；因为大部分情况下只追加写入，适合SSD

• Journaling文件系统：日志仅用于故障恢复。

Journaling文件系统

• 不直接修改磁盘上的数据结构；每次写更新都被视为事务记录在日志中（称为journal或intention list）；也在磁盘中备份。

• 一旦更新被记录在磁盘中，可以被安全地应用到文件系统（例如修改inode指针和目录映射）

• 一旦修改已应用到文件系统，立即从日志中删除相关表项

• 一些选项：要将所有数据记录进日志还是仅元数据

• （无日志情况下）创建文件：
• 遍历空闲位图，寻找空闲磁盘块
• 遍历inode表，寻找空闲inode表项
• 寻找目录插入点
• 写入空闲位图（将磁盘块标记为used）
• 写入inode表项，更新指针指向磁盘块
• 写入目录，将文件名指向inode

• （有日志的）创建文件
• 遍历空闲位图，寻找空闲磁盘块
• 遍历inode表，寻找空闲inode表项
• 寻找目录插入点
• [log] 写入空闲位图（将磁盘块标记为used）
• [log] 写入inode表项，更新指针指向磁盘块
• [log] 写入目录，将文件名指向inode
• （log commit）

• 所有对文件系统的访问首先查看日志；最终，将日志中记录的更改实际应用于磁盘，再清除日志

• 故障恢复：从故障中恢复后，首先扫描日志
• 截断半截日志：探测到有start而没有commit的事务时，截断该事务，磁盘保持不变
• 保留完整日志：探测到有完整的带commit的日志后，如常重做即可

• 日志能抵抗故障的原因：通过截断半截、保留完整，所有的事务都是原子化的，要么完全应用到磁盘，要么被截断

• 开销：所有数据都要经历两次写（一次对日志的写，一次对目标文件数据块的写）
• 现代文件系统只记录元数据更新，也就是只在日志中维护对文件系统数据结构的修改，而对文件内容的直接修改（无日志地）直接应用

集中式&分布式系统

• 集中式系统（centralized system）：主要功能在一台物理计算机上完成。客户端-服务器模型。

• 分布式系统（distributed system）：许多物理上彼此隔绝的计算机在同一个任务上工作
• 早期模型：多个服务器协作（称为一个cluster）
• 新模型：peer2peer（p2p）；wide-spread collaboration

• 分布式系统动机：
• 建造更多、更简单的计算机更廉价和容易
• 用户可以对一些部分拥有完全控制权
• collaboration（协作）：用户在网络资源上彼此协作更便捷

• 分布式系统（理论上的）优点：
• 更高可用性：一台机器故障后可以使用另一台
• 更好持续性：将数据存储在不同位置
• 更高安全性

• 实际上的缺陷：
• 可用性差：常常需要每台机器都上线
• 可靠性差：任意一台机器故障都可能导致数据丢失
• 安全性差：系统易于入侵

• 在分布式系统中协调（coordinate）更加困难
• 需要协调对共享状态信息的多重拷贝

• 系统的透明性（transparency）：将复杂性隐藏在简单界面的能力
• 位置透明：隐藏资源具体存储位置
• 迁移透明：资源可以在用户不知情时移动
• 备份透明：隐藏资源存在多少份拷贝
• 并发透明：隐藏实际用户数
• 并行透明：系统可将大任务分割成小任务从而加速
• 错误容忍：系统隐藏可能发生的错误

• 在分布式程序开发时，由于不共享内存，无法通过test&set操作保持同步性。一种抽象：报文的收/发。可能的界面：
• 邮箱（mbox）：暂时容纳报文的区域，由目的地和队列组成
• send（message，mbox）：将报文发送到由mbox标识的远程邮箱
• receive（buffer，mbox）：等待直到mbox接收到报文，将其拷贝到缓冲区并返回，唤醒一个等待线程

分布式决策

• 一致意见（consensus）问题：系统中所有结点都会提出（propose）一个值，部分结点可能故障并停止响应；最终，所有幸存的结点共同决策，从提出值中取一个相同值

• 分布式决策（decision making）：从true和false中选择/从commit和abort中选择

• 决策需要具有持久性：所有作出的决策必须要被记录

• 将军悖论：两座山上的将军商讨进攻时间，但信使可能被截获。我们需要同步性（simultaneity）之外的能力

• 分布式事务：多台机器原子化地决定是否做某事（没有时间约束，但最后一定会发生）

• 两段式提交协议（Two-Phase Commit Protocol，2PC）
• 在每台机器上维护持久性的、稳定的日志，记录提交是否发生。机器从故障中恢复后，首先检查日志并恢复到故障前的状态
• 准备阶段：全局协调者（coordinator）向所有参与者发出Prepare/Request请求，询问是否成功提交。参与者执行事务（但不commit，将执行结果（成功/失败）记录在日志中，并提交结果给协调者。
• 提交阶段：如果任意参与者投给abort，协调者在日志中记录并通知所有参与者abort，参与者将abort记录在日志中；若所有参与者都回应准备好了（Commit），协调者在日志中记录Commit，要求所有结点commit（结点收到commit，正式提交，释放资源，以ACK回应），接收到ACK后，协调者在日志中记录Got Commit

• 由于机器无法收回决策，因此全局状态要么commit，要么abort

• 考虑故障
• 协调者在等待参与者投票时，某个参与者故障：协调者超时，没有接收满N个投票，发送全局abort信号
• 参与者在等待PREPARE请求时，协调者故障：参与者超时并发送abort信号
• 参与者在等待全局投票结果时，协调者故障：参与者必须阻塞，等待协调者恢复并传递全局结果

• 所有结点都使用稳定存储（SSD/NVRAM）来存储当前状态

• 2PC协议并不能解决将军悖论，因为协议要求所有结点最终做出相同的决策，不一定是在同一个时间

• 功能：增强系统容错性。
• 即使有部分成员错误退出也能做出决定；在决策后，决策结果被存放在多地。
• 一方面，如果有成员因错误而关机/中断，重启后可以通过查询其他成员的信息而恢复自身数据；另一方面，如果有成员受到恶意攻击/数据谬误，也可以与其他成员交流以恢复。

• 缺点：worker容易阻塞于等待其他成员。阻塞的成员仍然持有资源（锁或内存中pinned的页）
• 成员B在日志中记录准备好提交，随即向协调者成员A发送yes投票，之后崩溃
• 成员A崩溃
• 成员B重启，检查日志，向A发送请求询问结果。此时B无法决定是否abort。因为A崩溃，所以B持续被阻塞。

文件系统5:现代存储和文件系统

• IO devices: disks with dedup （FAST’08 Dedup）

• IO: end-to-end management（SOSP’13 IOFlow）

• Modern file systems（SOSP’03 GFS）

• RAID and erasure coding（OSDI’16 EC-Cache）

• File systems for distributed applications（SIGCOMM’01 Chord）

IO devices: disks with dedup：使用去冗余打破存储瓶颈

• Deduplication：去冗余。是一种全局压缩技术，将许多文件公有的重复的段移除（只保留一份）
• 区别于局部压缩（如winzip等）是在文件内部寻找重复出现的数据并进行编码。压缩窗口约100KB
• 全局压缩的压缩窗口可以大很多，达到10倍甚至50倍的压缩率

• 大型企业数据存储要求：周期性对数据做备份，全量备份对所有文件备份，周期长；增量备份只对新增文件备份，周期短

• 去冗余过程：
• 指纹技术（fingerprinting）：将数据流分成段，存储在磁盘中的每个段都计算并存储其哈希值。新的段到来时，在已有数据段中查找，若某个段哈希值与新段相同，则说明新段与该段重合。
• 缺陷：假设8KB设为一段，每段哈希值20B，则压缩比8196/20=400，80TB的数据的哈希值仍需要200GB存储，过于庞大。

• 独有的低开销、高速、高压缩率技术：summary vector、stream informed segment layout、locality preserved caching（LPC）

• Summary Vector
• 目标：使用最小的内存，对新段进行哈希值查找
• bloom filter：维护一个很长的bit向量表，和少量哈希函数（3个），插入新数据时，分别计算三个哈希值，将对应位置的bit置为1；查找时，计算三个哈希值，若bit向量中三个位置的值都为1，则可以认为在已有集合中。可能存在假阳性（实际没有在已有集合中，但输出yes）但不会存在假阴性。如果bloom filter输出no，则新数据一定不在已有集合中。
• 使用bloom filter技术，维护一个summary vector存储已有哈希值（指纹）信息（索引数据）
• 因为所有数据段可以共用一个bit向量（summary vector），因此占用内存可以再缩小百倍
• 这样所有数据段的指纹可以存放在磁盘中（不常访问），称为disk index

• Stream Informed Segment Layout
• 类似FFS中block group，在磁盘上增强局部性
• 来自同一个流的数据段，和该流的元数据（例如索引数据）放在同一个container中，读写速度快

• Locality Preserved Caching
• 磁盘中存放有（fingerprint，container ID）键值对，称为index
• 维护一个index cache，缓存其中的一个子集（类似TLB）
• 通过键值对查找container时，直接将container的元数据加载进index cache，方便后面操作

• 总结：新数据到来时，先在index cache中检查新数据指纹是否已在cache中，如有则重复于对应ID的container中的某段；如没有，则进入summary vector中查找，若输出no，则一定是新数据，若输出yes，则可能重复，需要访问disk index查找是否有相同指纹。若认定是新数据，则在插入对应container中，要同时更新disk index、summary vector和index cache

IOFlow: end-to-end management：端到端SLA文件系统

• 背景知识：企业数据中心
• 通用目的应用
• 应用运行在数个虚拟机上
• 在虚拟机直接和虚拟机-存储之间存在分离的网络
• 存储被虚拟化；资源被共享

• 动机：文件系统需要向机器保证可预期的性能表现，例如传输带宽
• 文件系统需要提供端到端的SLA（Service-Level Agreement）
• 保证一定的带宽、吞吐量、优先级

• 局限：虚拟机+网卡+网络层+磁盘共有超过18个抽象层，彼此之间独立配置和操作，难以满足以上需求

• 挑战：存储没有控制平面或强制机制

• 思想：解耦数据平面和控制平面，构建控制平面，在数据平面维护可控的队列，在两个平面之间构建界面和API

• 存储流（storage flow）：指的是一个SLA需要的所有IO请求，可以用四元对（虚拟机，文件操作，文件，共享信息）表示

• IOFlow API：根据四元对决定存储流的优先级

Modern file systems：现代分布式文件系统（GFS）

• 设计背景
• 节点故障频繁发生
• 文件通常非常大（多GB级别）
• 文件主要通过追加写入修改，随机写入极少
• 高吞吐量比低延迟更重要

• 架构特点
• 单Master节点：管理元数据（文件名、块位置、访问控制等），客户端通过Master获取元数据后直接与ChunkServer交互，避免Master成为性能瓶颈。
• 数据分块：文件被划分为固定大小的块（Chunk）（默认64MB），每个块分配全局唯一的64位句柄，并在多个ChunkServer上复制（默认3份）。
• 控制流与数据流分离：客户端与Master交互获取元数据，与ChunkServer直接传输文件数据，提升吞吐量。

• 写入流程
1. 客户端向Master请求目标块的ChunkServer列表。
2. Master选择一个主副本（Primary）并授予租约（Lease），主副本负责协调写入顺序。
3. 客户端将数据推送到所有副本，主副本确认写入顺序后通知其他副本执行。
4. 主副本返回写入结果给客户端。

• 容错与一致性
• Master通过操作日志（Operation Log） 持久化元数据变更，定期生成检查点以加速恢复。
• 若主副本失效，Master会在租约到期后重新指派新的主副本。

• 优势与局限
• 优势：高吞吐、支持大规模数据存储、容错性强。
• 局限：单Master可能成为单点故障（通过Shadow Master缓解），不适合小文件高频读写场景。

RAID and erasure coding：基于纠删码的集群缓存（EC-Cache）

• 问题背景
• 分布式缓存中常见负载不均衡：热点数据访问集中、网络延迟差异、节点故障等。
• 传统**选择性复制（Selective Replication）**通过增加热门数据副本数来平衡负载，但内存开销大且粒度粗（只能整数倍复制）。

• EC-Cache核心思想
• 纠删码技术：将对象拆分为k个数据单元，编码生成r个校验单元，分散存储在集群中。读取时只需任意k个单元即可解码原始数据。
• 示例：k=10，r=1，内存开销仅增加10%，但可实现细粒度负载均衡。
• 额外读取（Δ）：每次读取k+Δ个单元（如Δ=1），选择最先到达的k个解码，避免慢节点影响尾延迟。

• 技术优势
1. 内存开销可控：通过调整k和r实现灵活的内存-性能权衡。
2. 负载均衡：数据单元分散存储，访问压力均匀分布。
3. 降低延迟：并行读取多个单元缩短中位数延迟，Δ机制优化尾部延迟。

• 实际效果
• 负载不均衡减少3倍以上，中位数延迟降低5倍（100MB对象）。
• 适用于大数据场景（如Alluxio），但对小对象效果有限。

File systems for distributed applications：分布式哈希表（Chord）

• 设计目标
• 解决P2P系统中的高效数据定位问题，支持Lookup(key)→IP映射。
• 核心要求：低跳数（O(log N)）、可扩展性（O(log N)状态）、高容错性。

• 关键机制
• 一致性哈希：将节点和数据键映射到环形ID空间（如SHA-1哈希），数据存储在后继节点（ID大于等于键的第一个节点）。
• 指表（Finger Table）：每个节点维护O(log N)个指向其他节点的指针，按指数距离跳跃（如n+2^0, n+2^1, ...），加速查找。
• 动态维护：新节点加入时，通过询问现有节点初始化指表，并接管部分数据键范围；节点失效时，通过后继列表快速恢复。

一致性哈希环

• 环形 ID 空间：将节点和数据键通过哈希函数（如 SHA-1）映射到一个 m 位的整数空间（如 0 ~ 2^160 - 1），形成一个逻辑环。

• 数据存储规则：每个键值对存储在它的后继节点（即环上第一个 ID ≥ 键的节点）。示例：
• 键 K20 的后继是节点 N32（假设环上有 N10, N32, N90）。
• 若节点 N32 离线，K20 会转移到下一个节点 N90。

节点与键的定位

• 问题：如何快速找到某个键的后继节点？

• 朴素方法：每个节点记录其后继节点，顺序查询（O(N) 跳数，效率低）。

• Chord 优化：通过**指表（Finger Table）**加速查询。

指表（Finger Table）

• 物理意义：指表项 i 指向环上距离当前节点 n 约 2^i 的位置的后继节点。

• 示例：
• 节点 N8（m=6）的指表：
• finger[0] = successor(8 + 1) = N14
• finger[1] = successor(8 + 2) = N14
• finger[2] = successor(8 + 4) = N21
• ...
• finger[5] = successor(8 + 32) = N42

指表的作用

• 加速查找：每次查询至少将距离缩短一半，实现 O(log N) 跳数。
查找流程：
1. 当前节点检查键是否落在自身和直接后继之间，若是则返回后继。
2. 否则，从指表找到最大且不超过键的节点，转发请求。
示例：节点 N8 查找 K54：
• finger[5]=N42（因 8+32=40 ≤ 54）
• finger[5]=N42 继续查找，最终找到 K54 的后继 N56。

实际案例

场景：6 位 ID 空间（0~63），现有节点 {N1, N8, N14, N21, N32, N42}，查找 K36。

1. N8 发起查询：
• 检查 K36 ∈ (N8, N14]? → 否。
• 指表中最大不超过 36 的项是 finger[2]=N21（8 + 2^2=12 的后继）。

2. N21 继续查询：
• K36 ∈ (N21, N32]? → 否。
• 指表中 finger[4]=N32（21 + 2^4=37 的后继）。

3. N32 返回结果：
• K36 ∈ (N32, N42] → 后继为 N42。

• 实际应用
• 衍生出分布式键值存储（如Amazon Dynamo）和区块链技术（如比特币）。
• 局限性：假设无恶意节点，需额外机制保障安全性。

总结对比