征服OS的第三座大山-持久化

type

status

date

slug

summary

I/O设备概述

总线层次结构

越快的总线就越短, 连接的设备越少, 反之越长的总线连接的设备越多, 速度越慢(可以类比存储器层次结构).

标准设备模型

💡

不是具体设备, 可以视作I/O设备的通用接口模型.

内部实现被封装, 接口暴露给上层系统, 遵循交互协议.

操作系统访问I/O设备的方式: 使用明确的I/O专用指令(一般为特权指令)/内存映射, 将I/O设备寄存器编入本机地址空间, 使用通用的内存存取指令读写.

标准协议(轮询)

轮询过程中一直占用CPU, 比较低效.

中断机制

💡

在等待时找点别的事做, CPU就能将更多的时间用来计算了.

进程向设备发出请求之后让进程睡眠, 切换执行其他任务. 当设备完成请求后抛出硬件中断, 调用对应的中断处理程序结束请求并唤醒睡眠的进程. 这种机制允许计算与等待I/O并行进行, 提高了CPU利用率.

特例: 对于高速I/O设备, 往往轮询只需要等待很短的时间, 然而若使用中断则需要频繁进行上下文切换, 摊销效率很低, 代价反而更高. 由于设备速度未知, 可以考虑混合策略, 先尝试轮询一小段时间, 若设备没有就绪再进行中断(类比两阶段锁, 先轮询后休眠).

直接内存访问 DMA

💡

将I/O控制的主要逻辑移交出去, CPU就能将更多的时间用来计算了.

DMA控制器/引擎: 系统中的一个特殊设备, 处理内存和设备之间的数据传递, 不需要CPU介入(地位类似于专门处理I/O的一个协处理器). CPU通知DMA控制器数据位置, 数据量和数据传送目标, 就可以转而处理其他请求. DMA控制器完成任务之后再中断通知CPU.

设备纳入操作系统

每个设备都有专用接口, 使用驱动程序将其纳入通用的操作系统.

设备驱动程序封装与设备交互的细节, 对上层提供相对统一的接口. 上层只管发出请求, 将其分发到对应的设备驱动程序, 由它来完成底层操作.

缺陷: 通用的接口可能不能覆盖某些特殊功能, 这样接口就会成为功能种类的瓶颈.

驱动程序的代码在内核中的占比越来越大, 而且是内核崩溃的主要贡献者.

设备接口实例:

配套交互协议:

等待驱动就绪: 读取状态寄存器(0x1F7)直到驱动 READY 而非忙碌.

向命令寄存器写入参数: 写入扇区数, 待访问扇区对应的逻辑块地址(LBA), 并将驱动编号(master=0x00, slave=0x10, 因为 IDE 允许接入两个硬盘)写入命令寄存器(0x1F2-0x1F6).

开启 I/O: 发送读写命令到命令寄存器. 向命令寄存器(0x1F7)中写入 READ-WRITE 命令.

数据传送(针对写请求): 等待直到驱动状态为 READY 和 DRQ(驱动请求数据), 向数据端口写入数据.

中断处理: 在最简单的情况下, 每个扇区的数据传送结束后都会触发一次中断处理程序. 较复杂的方式支持批处理, 全部数据传送结束后才会触发一次中断处理.

错误处理: 在每次操作之后读取状态寄存器. 如果 ERROR 位被置位, 可以读取错误寄存器来获取详细信息.

示例驱动程序:

磁盘(硬件内容, 可以略读或跳过)

对外接口

磁盘对外接口在逻辑层面上表现为操作系统可以识别和访问的抽象设备, 其主要形式包括:

块设备(Block Device): 磁盘在操作系统中通常作为块设备出现, 数据以固定大小的块(如512字节或4KB)进行读写. 块设备支持随机访问, 允许操作系统直接寻址任意块. 所以可以将具有n个扇区的磁盘视为一个扇区数组, 从0~n-1编址. 磁盘保证对单个扇区的写入是原子的(要么完成更新, 要么完全没更新);

文件系统接口: 在用户层面, 磁盘通过挂载文件系统呈现为目录结构, 用户通过文件路径进行访问. 常见文件系统有FAT32、NTFS、ext4等. 文件系统负责将逻辑文件映射到磁盘物理块;

逻辑卷管理(LVM)接口: 操作系统可以通过逻辑卷管理器将多个物理磁盘抽象为逻辑卷, 实现磁盘的灵活分区、扩展与快照功能, 提升管理灵活性;

虚拟磁盘接口: 在虚拟化环境中, 磁盘可能表现为虚拟磁盘(如VDI、VMDK文件), 由虚拟机管理程序映射到物理磁盘资源, 提供隔离的存储空间.

这些逻辑接口屏蔽了底层硬件细节, 为上层应用和操作系统提供统一、抽象且高效的磁盘访问方式.

基本内部结构

磁盘由以下几个主要部分组成:

盘片(Platter): 圆形磁性材料的薄盘, 是数据存储的载体, 通常由多个盘片堆叠组成.

磁头(Head): 用于读写数据, 通常每个盘面对应一个磁头.

磁臂(Actuator Arm): 带动磁头在盘面上移动以定位到特定磁道.

主轴(Spindle): 驱动盘片高速旋转, 常见转速有5400 RPM、7200 RPM、10000 RPM等.

磁道(Track): 盘面上的同心圆区域, 用于组织数据. 在扇区线密度相同的情况下, 外圈周长更大, 包含的扇区更多. 考虑到移动磁头需要时间, 为了让磁头移动之后能继续访问下一个连续扇区(而非等待一周旋转), 磁道之间常常采取磁道偏斜设计, 即将相邻号的扇区错开一些, 使得磁头就位之后刚好续上下一个连续扇区;

扇区(Sector): 磁道上最小的数据单元, 常为512字节.

柱面(Cylinder): 多个盘片上相同编号的磁道集合, 形成柱状结构.

磁道缓冲区(Track Buffer): 现代磁盘驱动器中自带的少量缓存(通常为8MB或16MB), 用于保存单条磁道上的所有扇区(方便响应对同一磁道上多个扇区内容的多次访问).

延迟计算

磁盘访问延迟通常由以下几个部分组成:

单磁道旋转延迟

这是磁头到达目标扇区所需等待的时间, 平均为旋转一圈所需时间的一半:

平均旋转延迟 = 0.5 ×(60 ÷ 转速)(单位: 秒)

例如, 对于7200 RPM磁盘:

平均旋转延迟 = 0.5 ×(60 ÷ 7200) ≈ 4.17 毫秒

多磁道寻道时间

这是磁臂从当前位置移动到目标磁道所需的时间, 通常分为:

最小寻道时间: 磁头已在目标磁道上, 为0.

平均寻道时间: 通常由厂商提供, 或通过经验模型估算.

最大寻道时间: 从最外层磁道到最内层磁道, 取决于磁盘物理结构.

经验模型:

T_seek = α + β × n

其中, n 为跨越的磁道数, α 和 β 为常数.

传输时间

这是将数据从磁盘传输到内存的时间, 计算公式如下:

传输时间 = 数据大小 ÷ 传输速率

例如, 传输4KB数据, 速率为100 MB/s, 则:

传输时间 = 4KB ÷ 100MB/s ≈ 0.04 毫秒

磁盘调度

磁盘调度算法用于决定多个I/O请求的服务顺序, 以优化平均响应时间或吞吐量.

较早的系统中磁盘调度交由操作系统全权负责, 而现代磁盘内部就具有复杂的内部调度程序, 可以精确控制所有硬件细节(如磁头的位置等), 故现代磁盘的调度方式往往是由操作系统选出几个它认为最好的请求, 将其全部发送到磁盘, 再让磁盘的内部调度程序决定具体调度方式.

现代调度系统还会进行I/O合并, 将多个连续单块的读取合并成一个多块请求.

有时候等待一段时间再将请求发送到磁盘, 会得到更好的结果(可能会有新的更合适的请求到达).

💡

最短寻道时间优先(SSTF)

选择距离当前磁头位置最近的请求进行处理.

优点: 减少平均寻道时间.

缺点: 可能导致远端请求长时间得不到响应(饥饿问题).

电梯(SCAN/C-SCAN)

SCAN(电梯算法): 磁头朝一个方向移动时处理沿途的请求, 到达最末端后反向.

C-SCAN(循环电梯): 只在一个方向处理请求, 到达末端后快速返回起始端, 不处理请求.

优点: 相对公平, 减少饥饿现象.

SCAN适合负载均匀, C-SCAN适合高请求密度场景.

最短定位时间优先(SPTF)

选择预计完成时间最短的请求处理, 考虑寻道时间和旋转延迟的综合.

优点: 在高精度延迟控制场景下更优.

缺点: 计算复杂度较高, 依赖较详细的硬件特性模型.

该调度策略理论最优, 但实践中实现较少, 多用于模拟或高端系统.

廉价冗余磁盘阵列 RAID(硬件内容, 可以略读或跳过)

对外接口

💡

对于上层的文件系统, RAID看起来像是一个很大的、(我们希望是)快速的、并且(希望是)可靠的磁盘. 就像单个磁盘一样, 它将自己展现为线性的块数组, 每个块都可以由文件系统(或其他客户端)读取或写入.

RAID(Redundant Array of Independent Disks)对外以单一逻辑磁盘的形式呈现, 操作系统将其视为一个标准的块设备, 进行统一的读写操作. RAID控制器或软件RAID系统负责将这些操作映射到多个物理磁盘. 其对外接口特性包括:

逻辑块设备接口: RAID隐藏了底层多个磁盘的存在, 提供一致的逻辑块地址空间.

透明性: 上层应用和文件系统无需了解数据如何分布在多个磁盘上, 读写操作由RAID系统自动调度.

热插拔支持: 在支持热备份的RAID级别中, 对外接口可支持磁盘热插拔, 提高系统可用性.

性能与冗余增强: 在不同RAID级别下, 对外表现为更高的吞吐量(如RAID 0)或更高的容错能力(如RAID 1/5).

基本内部结构

RAID的内部结构依赖于其级别, 但通常包含以下组件:

多个物理磁盘: 通过硬件或软件组合而成.

条带化(Striping): 将数据划分为多个条带(Stripe), 分布在不同磁盘上, 提高并行读写性能.

冗余机制: 某些级别(如RAID 1、RAID 5)引入数据副本或奇偶校验位, 实现容错能力.

RAID控制器:

硬件RAID控制器: 独立处理RAID逻辑, 减轻CPU负担, 提供更高性能.
软件RAID: 由操作系统管理, 成本低, 适用于普通服务器或桌面环境.

缓存与写策略: 部分RAID控制器带有缓存, 可配置写回或直写策略, 影响性能和可靠性.

当文件系统向RAID发出逻辑I/O请求时, RAID内部计算要访问的磁盘(或多个磁盘)以完成请求, 然后发出一个或多个物理I/O来执行此操作. 这些物理I/O的确切性质取决于RAID的级别.

RAID系统通常构建为单独的硬件盒, 并通过标准连接(例如SCSI或SATA)接入主机. 然而RAID内部相当复杂. 它包含一个微控制器, 运行固件指导RAID的操作. 它还包含易失性存储器DRAM, 用于在读取和写入时缓冲数据块. 在某些情况下, 还包含非易失性存储器, 用于安全地缓冲写入(可能对崩溃恢复有用). 它甚至可能包含专用的逻辑电路, 用于执行奇偶校验计算(在某些RAID级别中非常有用, 下面会提到). 在高层面上, RAID是一个非常专业的计算机系统: 它拥有自己的处理器, 内存和磁盘. 然而它不运行应用程序, 而是运行专门用于操作RAID的软件.

故障模型

RAID的设计目标之一是应对磁盘故障, 其常见故障模型包括:

磁盘单点故障: 部分RAID级别可容忍一个或多个磁盘失效(如RAID 1、5), 系统仍能正常工作.

双盘失效: 标准RAID 5无法容忍两个磁盘同时失效, 需使用RAID 6等更高级别.

控制器或缓存故障: 硬件RAID控制器损坏可能导致整个阵列不可用, 应配备备份控制器或冗余设计.

数据不一致或写入中断: 在断电或系统崩溃情况下, 未完成的写操作可能导致冗余信息不一致(写孔问题).

RAID 0: 条带化

💡

要性能不要安全, 无冗余设计.

结构: 将数据按条带划分, 交错写入多个磁盘. 单个块的大小可以任意设置, 较大的块定位成本低但是并行性差, 较小的块反之, 需要权衡.

优点:

所有磁盘可以并行读写, 拥有极高的读写性能, 适用于高带宽应用.
无冗余开销, 磁盘空间完全可用.

缺点:

无容错能力, 任一磁盘损坏都会导致整体数据丢失.

适用场景: 对性能要求高且数据可重建的场合(如视频编辑、临时数据处理).

RAID 1: 镜像

💡

要安全不要性能, 直接存储两份相同数据.

可以与RAID 0组成RAID 01或RAID 10, 增加一些并行性来提高性能.

结构: 每份数据在两个或多个磁盘上保持完全一致的副本.

优点:

具备完整的容错能力, 任何一个磁盘损坏数据仍然可用.
读性能提升, 可从多个磁盘并发读取.

缺点:

存储效率低, 磁盘利用率为50%(双盘镜像).

适用场景: 对数据安全性要求极高的系统, 如数据库、金融系统.

RAID 4: 奇偶校验

💡

保守地提供冗余, 比RAID 0安全, 比RAID 1存储效率高.

结构:

数据条带化分布在多个磁盘上.
单独设置一个磁盘存放所有奇偶校验信息.

优点:

支持容忍单个磁盘故障, 具有容错能力.
相较RAID 1节省空间, 效率更高.

缺点:

奇偶校验磁盘成为性能瓶颈, 每次写操作都需更新该磁盘.

适用场景: 对写入压力不高的中等容错场景.

RAID 5: 旋转奇偶校验

💡

将RAID 4中的奇偶校验条带打散, 在不降低安全性的前提下随机写入性能明显提高(不受到奇偶校验盘的瓶颈限制), 随机读取性能小幅提高, 没有小写入问题, 各盘均衡.

RAID 5基本上与RAID 4相同, 在少数情况下更好, 几乎完全取代了市场上的RAID 4.

结构:

类似RAID 4, 但奇偶校验信息分散在各个磁盘中, 按条带轮转分布.

优点:

容忍单盘故障.
无奇偶校验磁盘瓶颈, 读写性能均衡.
存储利用率较高(N块磁盘中有 N-1 块可用于数据).

缺点:

写操作涉及读取旧数据和校验信息, 写性能低于RAID 0.
无法容忍双盘故障.

适用场景: 适合读多写少的通用服务器、存储系统.

总结

文件和目录API

文件

文件就是一个线性字节数组, 每个字节都可以读写.

文件的低级名称: inode号(每个文件都有一个inode号与其关联, 可能多个文件关联到同一inode).

文件系统不了解文件的结构(编码方式)/内容, 只负责保管和存取.

文件系统API

创建文件

返回一个文件描述符fd(进程私有), 作为访问该文件的一个句柄(即引用/线索/指针, whatever).

💡

“句柄”到底是哪个神金想出来的名词?

使用open()打开的文件获得的fd从0开始连续递增计数. 一般进程创建时会将0初始化为stdin, 1初始化为stdout, 2初始化为stderr. 也就是说首个获得的fd一般为3.

读写文件

💡

小工具: strace(Linux), dtruss(macOS), truss(Unix), 跟踪程序使用的系统调用.

改变读写位置:

读写行为隐式地改变文件指针位置, 而lseek()是显式地改变文件指针位置.

write()操作可能被缓冲(OS决定按批写入, 摊销) → 可以fsync(int fd)调用强行立即写入(除了立即写入该文件本身可能还需要立即写入对该文件所在目录的修改).

文件重命名

可以用于实现某些原子更新行为, 例如:

文件元数据

储存元数据的结构如下:

每个文件通常将该类型信息保存在其inode中, 可以使用stat程序(使用stat和fstat系统调用)查看.

删除文件

创建目录

目录本身的信息由文件系统自动维护, 无法直接被更新, 只能通过在目录中新建/删除/修改文件和目录等内容间接更新.

空目录有两个条目: .(自己)和..(父目录).

参数mode指示rwx权限(如0777).

读取目录

目录条目的数据结构:

目录本身就相当于元素类型为dirent的列表.

目录本身只记录少量信息. 若想获取目录下各文件的详细信息(如使用ls -l), 则需要对该目录下的每个文件再各执行一遍stat().

删除目录

硬链接

硬链接: 将人类可读文件名关联到inode.

创建文件的流程: 新建一个inode结构来追踪几乎所有关于该文件的信息, 然后使用link()系统调用建立硬链接将人类可读的名称关联到该inode, 并将该链接放入目录. 多个人类可读名可以通过硬链接关联到同一inode(文件本体).

因此删除文件就要调用unlink(), 删除人类可读名称和inode号之间的硬链接. 当链接到某一inode的人类可读名称数量为0时即可释放该inode对应的数据块(可作他用, 不一定擦除, 留下恢复空间), 因为没有了链接/指针就说明不会再从上层被引用.

stat程序/系统调用同样可以查看一个inode的引用计数.

硬链接的局限:

inode只在单一而非跨文件系统内唯一, 故不在同一文件系统内的文件和inode不能建立硬链接;

不能创建目录的硬链接, 因为可能导致目录树中出现环.

符号链接

又称软链接, 将人类可读文件名关联到链接指向文件的路径名, 是独立于文件和目录之外的第三种类型的文件系统成分.

💡

软链接文件的内容就是其指向的文件的路径名. 链接到的路径名越长则软链接文件越大.

当软链接指向的文件路径被删除, 就会产生空指针/野指针等悬空引用问题.

创建和挂载文件系统

完整目录树的构建: 先分别制作不同的文件系统模块, 再将其挂载到目录树的相应位置.

mkfs工具: 使用指定的存储设备(如磁盘分区)创建指定类型的空文件系统.

mount程序/系统调用: 以现有目录作为目标挂载点, 将新的文件系统粘贴到目录树的指定节点上, 即可在统一的文件系统树中通过唯一路径访问该节点. 挂载之后挂载点的路径就是该文件系统的根目录路径.

运行mount程序即可查看系统当前挂载的内容和位置.

文件系统实现

💡

文件系统是纯软件, 不会使用专门的硬件支持, 具有很强灵活性.

理解某个具体文件系统的两个角度: 数据结构(数据和元数据的组织方式, 如数组/树结构) + 访问方法(如何将进程发出的调用映射到文件系统的结构上, 即调用对应系统的哪些结构和行为).

极简文件系统 VSFS

数据区域

将磁盘分为个固定大小4KB的块的集合, 地址从到. 大部分块用于存储用户数据, 少部分保留给文件系统自身, 用于记录元数据(如inode).

inode

💡

inode记录了诸如文件类型, 文件大小, 文件所有者, 访问权限, 访问和修改时间, 文件包含数据块的位置等元数据信息.

全名index node,(用inode号在inode数组中)索引(的)节点, 每个inode用inode号隐式引用, 给定一个inode号就可以根据inode表起始地址和inode大小计算目标inode的地址.

在元数据区域分配一些块, 用于存放inode数组. 该区域称为inode表. inode数组的大小决定了文件系统中文件的最大数量(要容纳更多文件需要扩大inode表).

💡

文件系统如何维护inode到数据块的映射?

直接指针: 在inode中维护若干个指针, 每个指向一个数据块. 缺陷: 能维护的指针数量有限 → 文件大小有上限, 对大文件支持不佳.

二级索引: 在inode中维护若干个直接指针和一个间接指针, 间接指针指向一个专门用于存放直接指针的数据块(可以形象理解为”直接指针库”). 所有的直接指针都指向一个数据块.

多级索引: 指针库中继续存放指向其他指针库的间接指针, 即可通过树结构构建指数级增长的数据块映射. 大部分文件很小, 所以多级索引的树结构为不平衡树.

链表结构: 维护一个文件分配表, 维护某数据块的直接指针 → 下一个数据块的直接指针的映射关系, 从而可以顺序查找一个文件的所有数据块. 缺陷是随机访问效率较低.

位图

需要一个结构来记录inode表和数据块的分配情况(哪些空闲/哪些占用) → 在元数据区域分配空间用于存放inode位图和数据块位图(bitmap), 用二进制序列的各位标记对应的inode/数据块是否被占用(空闲为0, 占用为1).

为文件分配数据块时, 以分配连续的数据块为佳(顺序存取效率高).

超级块

最后还需要在元数据区域加上一个超级块(super block), 用于存储描述该文件系统自身的信息, 例如文件系统中inode和数据块的个数, inode表的开始位置等, 还可能包含一些用于标识文件系统类型的幻数, 地位相当于该文件系统的使用说明/导航(不然上层不知道文件系统中各区域的划分).

文件系统挂载时将超级块调入内存, 其他部分留在磁盘中.

目录组织

目录只包含一个Pair<文件名, inode号>二元组的列表.

删除文件 → 可以将目录条目的inum设置为0(保留, 标记未用)以备重用.

文件系统通常将目录视为特殊类型的文件, 一个目录分配一个inode, 其中”类型”字段设置为”dir”. inode(使用直接或间接指针)指向的数据块中存储上述二元组列表.

除了简单列表之外还可以使用其他更高级的数据结构来存储目录条目(如B-树).

💡

“活动inode”: 从磁盘被载入内存中的inode

读取

总过程: 根据完整路径名(上层)找到对应的inode(底层).

打开文件: 遍历路径名, 通过父目录的inode号索引到父目录的内容, 再从父目录的内容条目中找到子目录或目录中文件的inode号, 递归查找(起点: 根目录使用约定的周知inode号, Unix中一般为2, 找到目标文件的inode后将其读入内存(令其成为活动inode);

进行权限检查, 若检查通过则在进程私有的打开文件表中为该文件添加一个条目, 分配一个文件描述符fd并返回给用户, fd即为该文件在用户打开文件表中的索引(还会在系统的全局打开文件表和系统的全局活动inode表中各添加一个条目);

💡

全局打开文件表中, 可以为不同的进程维护不同的记录, 如为多个进程独立维护文件读写偏移等.

发出read()系统调用, 设置文件偏移量并开始读取, 从用户打开文件表索引到系统打开文件表, 再索引到活动inode表, 查阅(内存中的活跃)inode以获取每个块的位置, 从磁盘中读取块, 更新inode的相关字段, 文件偏移量实时更新;

结束访问, 释放fd(即用户打开文件表项), 将系统打开文件表的对应表项的f_count减去1, 若减到0(即没有进程打开该inode)则释放该表项, 将活动inode的修改后的内容写回磁盘, 释放活动inode.

💡

普遍顺序: 查inode → 读数据块 → 更新inode.

读取时不会访问分配结构(即位图), 因为已经检查到inode指向的数据块, 默认它已经存在.

调用open()打开文件时的I/O量与路径长度正相关(递归深度成正比).

对于读取大文件的情况, 可能需要遍历很多(间接)指针库, 开销会更大.

写入

用与读取同样的方式找到目标文件, 发出write()调用, 用完后关闭文件.

区别: write可能涉及新数据块的分配. 对已存在的文件进行写入操作首先要决定将哪个块分配给文件, 然后再将数据写入某个块, 同时需要更新inode位图和数据位图和inode等结构. 故每次写入文件至少会导致5个I/O: 读取数据位图, 更新数据位图(分配新块), 读取inode, 更新inode(增加指针), 将数据写入数据块.

若要创建一个新文件, 首先要分配一个inode, 还要在直接包含该文件的目录数据中添加该文件的条目. 故需要进行以下I/O: 读取inode位图, 写入inode位图, 初始化inode, 读取目录inode, 更新目录inode, 写入目录数据(甚至还可能需要为目录分配更多的数据块).

单次操作的开销太大, 需要使用缓存和缓冲机制来摊销.

缓存和缓冲

读取和写入文件开销很大, 会导致频繁的I/O从而产生性能问题. 大多数文件系统会使用系统内存来缓存重要的(频繁更新的)块, 从而减少磁盘I/O的次数. 使用cache替换策略决定哪些块留在内存中.

早期的文件系统从内存中划分出固定比例的空间用于缓存块, 然而纯静态划分可能导致浪费. 相比之下现代系统更多采用动态划分方法, 即将虚拟内存页面和文件系统页面集成到统一页面缓存中, 即将两种页面同等对待, 拥有更强灵活性. 只要缓存命中就不需要磁盘I/O, 从而减少读取流量.

通过使用写回机制, 在数据页面被替换的时候再将修改写回磁盘, 可能可以减少写入的次数, 并且批处理和I/O调度可以摊销, 提高性能.

大多数现代文件系统都将写入在内存中缓冲5~30s, 但是会带来其他问题(若系统在缓冲时崩溃则会丢失所有更新). 所以这是性能和可靠性之间的折中. 某些对数据丢失敏感的程序会主动调用fsync()来强制立即完成更新, 甚至干脆直接越过文件系统, 使用原始的磁盘接口.

SPOOLing系统

💡

缓冲在内存中短期存储任务, 而SPOOLing系统在磁盘中持久存储, 调度慢速外设.

“伪脱机批处理”

SPOOLing系统(Simultaneous Peripheral Operations On-Line)是一种操作系统技术, 用于协调计算机与外部设备(如打印机、磁带驱动器等)之间的输入/输出操作, 以提高资源的使用效率.

结构:

“井”: 用作缓冲的存储区域, 调节供求之间的矛盾, 消除人工干预带来的损失

“预输入程序”: 操作系统将一批作业从输入设备上预先输入到磁盘的输入缓冲区中暂时保存(“预输入”), 此后由作业调度程序调度作业执行, 作业使用数据时不必再启动输入设备, 只要从磁盘的输入缓冲区中读入

“缓输出程序”: 作业执行中不必直接启动输出设备, 只要将作业的输出数据暂时保存到磁盘的输出缓冲区, 当作业执行完毕后, 由操作系统组织信息成批输出

“井管理程序”

核心概念:

缓冲处理: 数据不是直接发送到外设, 而是先存储在磁盘等中间介质中.

异步操作: 输入/输出设备可以与CPU并行工作, 提高系统并发能力.

排队机制: 多个作业的I/O请求被排队, 按照一定策略有序处理.

举例: 打印任务SPOOLing

用户提交打印任务.

任务被保存到SPOOL目录(一个磁盘区域).

打印机空闲时, 系统将任务一个个送去打印.

优点:

提高CPU和外设的使用效率

支持多任务同时进行

避免I/O操作对程序执行的阻塞

注意事项:

SPOOLing适用于速度慢、资源共享的设备(如打印机)

它与缓冲不同: 缓冲是短期内存存储, 而SPOOLing是长期/批量存储

常见应用场景:

打印任务调度

批处理系统的输入输出

数据备份任务

总结: SPOOLing是一种通过磁盘中转来调度慢速外设I/O操作的系统机制, 使CPU与外设能够高效协同运行.

快速文件系统FFS

💡

把磁盘当做磁盘, 让文件系统的实现具有”磁盘意识”, 令其结构和分配策略与磁盘特性相适应.

旧文件系统的局部性问题

旧Unix文件系统:

优点: 简单, 支持文件系统提供的基本抽象;

问题: 性能很差, 且随时间推移越来越差.

问题根源: Unix文件系统将磁盘当成RAM(随机存取)来处理, 数据遍布各处, 没有考虑到磁盘的定位成本(如寻道时间). 而且空闲空间没有得到精心管理, 最终会散布在磁盘的各处. 再分配给新文件时会将逻辑连续的文件在物理上存储在磁盘的各处.

💡

在磁盘上来回访问逻辑上连续的文件, 完全没有利用局部性, 大大地降低了性能.

磁盘只有在连续读取时才能获得峰值性能.

其他问题: 块太小, 虽然内部碎片少, 但是块定位开销更频繁.

FFS: 柱面组

将磁盘划分为若干个柱面组, 每个柱面组包含若干个块(所以柱面组也可以称作”块组”). 每个柱面组内都分配超级块+位图+数据区域的结构, 都可以分配文件和目录(即组就像一个子文件系统).

↓

优点: 访问同一个组中的多个文件时不会出现长时间的磁盘寻道.

每个组都带有超级块, 以便在部分组故障时文件系统仍然能正常挂载.

文件和目录的分配策略

💡

咒语: 相关的东西放一起, 无关的东西分开放.

决定什么是相关的数据, 并将其放在同一个块组内; 不相关的东西放在不同的块组中.

放置推断方法:

对目录: 找到被分配目录的数量较少(希望跨组平衡目录)且包含大量自由inode(希望随后能分配一堆文件)的块组.

对文件: 首先确保将文件的inode与其数据块分配到相同的块组中(防止inode与数据块之间的长时间寻道), 并将同一目录下的所有文件与该目录放在同一个块组中(不同目录下的文件则可能相互远离).

例外: 对大文件, 若按照一般文件分配, 则一个大文件很容易填满整个块组, 会影响其他相关文件进入该块组, 破坏文件存储的局部性, 不符合需要. 因此对于大文件, FFS将一定数量的数据块分配到第一个块组, 将下一个大块(间接指针指向的部分)放在另一个块组中, 递归进行, 从而跨组平衡大文件, 给每组都留下空间. 缺陷是跨块组访问同一文件的大块会损失性能, 但这是大文件和小文件之间的权衡. FFS采取的具体策略: 基于inode本身的结构, 12个直接指针指向的数据块与inode放在同一块组中, 其余每个间接块(指针库)及其指向的所有块(数据块/下一级指针库)都放在不同的组中. 这种策略下除了开头的12个块, 文件的每个块都放在单独的组中.

其他设计

引入子块(比标准块小的块)以支持小文件, 减少内部碎片. 小文件增大到一定程度后复制到一个完整的标准块, 并释放子块以备将来使用. 然而频繁复制效率低下, 所以常常通过缓冲来避免使用子块(除非必需否则不用);

针对性能优化磁盘布局, 不用连续扇区分布, 而是间隔分布扇区, 用于适应连续请求与旋转之间的时间差(即下一个请求到达时还能赶上下一个连续扇区, 若连续分布扇区则会错过, 多转一圈). FFS会根据磁盘的性能参数决定布局时应该跳过多少块安排下一个扇区;

现代磁盘优化: 将整个磁道读取到内部磁盘缓存(磁道缓冲区)中, 连续访问时不需要连续读取扇区, 而是直接读缓冲区即可;

FFS引入长文件名, 符号链接和原子rename操作.

文件系统检查程序FSCK

💡

“如何在出现断电或系统崩溃的情况下更新持久数据结构?” ——崩溃一致性问题

简而言之, 一致性类似于原子性, 希望磁盘上的结构在且仅在一致性状态之间原子地转移, 不存在中间状态. 然而, 磁盘一次只能处理一个写入任务, 多个更新只能串行进行, 而更新之间可能会发生崩溃或断电. 这就是我们要解决的崩溃一致性问题.

“不怕在写入开始之前或完成之后发生崩溃, 就怕在完成了部分步骤但还有剩余部分未完成时崩溃, 让文件系统处于中间态. ”

💡

可能的不一致:

分配了新inode, 但还没有更新位图和数据块: 不一致, 位图显示无效而inode显示已分配;

更新了位图, 但还没有分配新的inode和数据块: 不一致, 可能导致内存泄漏(错误分配的不会释放);

写入了新数据, 但还没有更新位图和inode: 没有影响, 只是写了点垃圾数据;

分配了新inode并写入了数据块, 但还没有更新位图: 不一致, 需要处理;

分配了新inode并更新了位图, 但还没有写入数据块: 元数据自洽, 但是按照inode指示会找到垃圾数据;

更新了位图并写入了数据块, 但还没有分配新inode: 不一致, 可能导致内存泄漏.

较老的文件系统采用文件系统检查程序fsck.

fsck:(在文件系统挂载完成之前)全盘扫描, 查找文件系统中元数据的不一致并修复(无法解决所有问题, 因为无法检查数据块的语义).

检查对象:

超级块: fsck首先检查超级块是否合理, 主要是进行健全性检查, 例如确保文件系统大小大于分配的块数. 通常, 这些健全性检查的目的是找到一个可疑的(冲突的)超级块. 在这种情况下, 系统(或管理员)可以决定使用超级块的备用副本;

空闲块: 接下来, fsck扫描inode、间接块、双重间接块等, 以了解当前在文件系统中分配的块, 生成正确版本的分配位图. 因此, 如果位图和inode之间存在不一致, 则最终信任inode内的信息并修正位图. 对所有inode执行相同类型的检查, 确保所有(看起来像)已分配的inode都在inode位图中有标记;

inode状态: 检查每个inode是否存在损坏或其他问题. 例如, fsck 确保每个分配的inode的类型字段均有效(即常规文件、目录、符号链接等). 如果inode字段存在问题且不易修复, 则认为该inode可疑, 将其清除并更新inode位图;

inode链接: fsck还会验证每个已分配的inode的链接数. fsck从根目录开始扫描整个目录树, 并为文件系统中的每个文件和目录构建各自的链接计数. 如果新计算的计数与inode中找到的计数不匹配, 则采取纠正措施, 通常是修复inode中的计数. 如果发现已分配但没有被任何目录引用的inode, 则将其移动到lost+found目录.

重复: fsck还检查重复指针, 即两个不同的inode引用同一个块的情况. 如果其中某个inode明显错误则可能会被清除. 或者, 可以复制指向的块, 从而根据需要让每个inode指向相同数据的不同副本.

坏块: 在扫描所有指针列表时, 还会检查坏块指针. 如果指针指向明显超出其有效范围的某个地址(例如指向大于其所在分区大小的块), 则认为该指针有问题. 在这种情况下, fsck不能做任何太聪明的事情, 只是从inode或间接块中删除该指针.

目录检查: fsck不了解用户文件的内容, 但是了解目录数据的格式(因为目录包含由文件系统本身创建的特定格式的元数据, 而非任意数据). 因此fsck对每个目录的内容执行额外的完整性检查, 确保“.” 和“..”条目在最前面, 且目录条目中引用的每个inode都已分配, 且整个层次结构中没有目录被引用超过一次.

需要充分的底层文件系统知识才能构建有效的fsck程序.

fsck程序的根本问题: 全盘扫描太慢了! 杀鸡用牛刀的策略性价比太低, 有效但太浪费.

预写日志

概述

从数据库管理系统中借鉴. 预写日志又称为日志.

基本思路: 写入结构之前先在另外一个周知的地址处登记, 描述将要做的写入事务(即为”预写”过程). 所有登记的题目组成”预写日志”. 如此一来如果在写入期间发生崩溃就可以通过查询日志来完整得知预期的写入行为, 并根据该信息来恢复, 不必扫描整个磁盘.

💡

预写日志在更新期间增加了一些工作量, 从而大大减少了恢复期间需要的工作量.

示例:

每个group中都包含该块组的位图, inode和数据块.

物理日志结构

在写入更新之前填写日志:

对每个事务写5个块: TxB(Transaction Begin, 事务开始), I[v2](要写入的新inode信息), B[v2](要写入的新位图信息), Db(要写入的新数据信息), TxE(Transaction End, 事务结束).

TxB中包含描述本次更新的元数据, 包括如I[v2], B[v2], Db等部分的目标地址和事务标识符(TID)等. TxE中同样包含TID.

这种将要更新的具体内容(I, B, Db)直接放在日志中的日志叫做物理日志.

还有一种不存储具体内容的逻辑日志, 更节省空间.

一旦事务安全地登记在日志中就可以开始写入/覆盖文件系统的结构了, 这个过程叫做”加检查点(checkpointing)”, 即遍历日志一项一项完成任务, 将I[v2], B[v2]和Db写入对应的磁盘位置.

💡

什么破烂翻译...

元数据日志

对物理日志而言, 实现原子更新的代价沉重: 同样的数据在日志中和目标位置写了两次, 写入流量起码加了一倍. 在顺序写入时带宽只能达到峰值带宽的50%. 此外, 日志和写入目标位置之间相隔较远, 还会导致可观的寻道时间.

为了减少写入流量, 引入元数据日志: 不存储数据块Db, 其余部分与物理日志相同.

将Db改为直接写入文件系统, 不再在日志条目中存储副本.

💡

Q: 没有了Db副本, 可能导致什么问题?

A: 崩溃时若尚未完成写入Db, 则恢复时只能恢复inode和位图, 然而此时对应数据块为垃圾数据 → 垃圾数据进入文件.

应对策略: 强制规定写入顺序, 先将Db写入目标地址, 再写入日志条目(TxB, I[v2], B[v2])并提交日志(写入TxE), 加检查点写入I[v2]和B[v2].

💡

其实只要在提交日志(即写入TxE)之前完成写入Db即可, 可以于写入日志条目的任务并行调度.

这样一来, 只要日志被完整更新, 就可以认定数据已经成功写入, 保证不会引入垃圾数据. 如果日志没有完整更新, 则多一块”无主”的垃圾数据(没有元数据指定其归属)也无伤大雅.

💡

补充: 强制写入顺序的机制支持 → 禁用写缓冲/写入屏障(保证屏障前的事务先于屏障后的事务完成)

惯用法: 先写入被指对象, 再写入指针, 保证指针永远不会指向垃圾.

目录比较特殊, 其数据由文件系统维护, 被认为是元数据, 会放在元数据日志中(反正占空间小).

日志自身的原子写入

这样一旦日志写成功就能保证事务可以完成/恢复. 然而考察写入日志的行为本身, 却仍有问题: 如何保证日志的安全写入?

故障示例:

对单条记录而言, 为了提高效率, 写入5个部分的请求一并发出并接受I/O调度(而非先后串行发出), 可能以任意顺序执行. 如果像图示一样对数据块Db的写入调度到最后进行, 恰好在最后又发生崩溃或断电, 则对Db的登记就为垃圾数据, 然而文件系统无法检查Db的语义, 最终会将其判断为一个合法记录, 因为其余部分都是完好的. 所以最终后果是对磁盘写入垃圾数据. 如果将垃圾数据写入了关键区域(如超级块)那就坏事了.

解决方案: 分两步发出写入日志条目的事务.

首先同时发出将前4个部分写入日志的请求(日志写入):

当这4个部分写完之后再发出写入TxE块的请求, 完成日志条目更新(日志提交, commit):

这样就确保了日志的原子更新.

💡

日志原子更新的底层其实是磁盘的原子性保证——任何512字节(一个扇区大小)的写入都是原子的, 不会出现写入一半的情况. 因此为确保TxE的原子写入, 就令其大小恰好为512字节.

宏观上日志被实现为一个循环队列, 头部有一个存储了队首和队尾指针的日志超级块, 用于循环使用日志并防止日志被填满.

所以完成写入日志条目/加检查点的操作时也要实时维护日志超级块中的队列指针.

使用日志进行恢复

对不同崩溃节点:

如果在日志写入期间崩溃(导致日志都没写全), 就直接抛弃该更新;

事务已经完整登记到日志, 在根据日志写入更新期间发生崩溃, 则按顺序重放(replay)事务, 试着再写一遍. 这种策略称为重做日志(redo logging).

最坏的情况就是对未完成就被打断的事务重写一遍. 崩溃是意外事故, 无需担心恢复时的几次冗余写入影响性能.

以上使用日志的协议可能会带来大量的磁盘流量(需要维护日志的更新), 故一些文件系统(如Linux ext3)会通过缓冲成批写入日志来摊销, 代价是更新间隔变长会导致崩溃时丢失的更新变多.

块复用问题

当涉及删除操作时, 原本分配的数据块可能被释放并重用, 这样在元数据日志中可能会产生重用问题, 例如:

示例流程: 创建foo目录 → 删除foo目录 → 创建foobar文件(inode[1000]被释放并复用). 若在更新foobar期间发生崩溃, 则恢复时重新扫描日志, 创建foo目录的任务重放时会错误覆盖foobar文件的内容, 并且无法恢复(元数据日志中没有存放foobar的数据内容).

解决方案:

禁止复用: 永远不复用块, 直到该块从日志中绝迹;

撤销记录: 将删除行为作为一条”撤销记录”写入日志, 重放之前先扫描日志检查, 从而对有撤销记录的块特判, 不进行重放.

其他方案

软更新: 对文件系统的所有写入行为排序(例如先写指向的数据块再写指向它的inode, 保证inode永远不会指向垃圾), 但是构建顺序规则需要复杂的文件系统知识;

写时复制: 永远不会覆写文件或目录, 只选择磁盘上从未使用的位置存放更新, 完成大量更新后翻转文件系统的根结构以纳入指向方才更新的地址的指针;

反向指针: 在每个数据块中加上反向指针, 指向其所属的inode, 与inode中的正向指针形成双重验证, 获得惰性崩溃一致性;

乐观崩溃一致性: 尽可能多地向磁盘发出写入, 使用事务校验和等技术检测不一致, 可以将性能提高一个数量级, 但是需要特殊的磁盘接口才能实现.

日志结构文件系统LFS

概述

设计出发点:

内存大小不断增长, 可以缓存更多数据, 从而读取行为多数时候可以从缓存中直接获取数据, 磁盘流量中写入流量的占比日益增大, 因此文件系统的性能越来越依赖于写入性能;

随机I/O与顺序I/O的速率差距不断扩大, 因为寻道时间和旋转延迟下降较慢, 而传输带宽迅速增大, 因此若能以顺序方式访问磁盘则可以获得极大的性能优势;

当时的文件系统在许多常见工作负载(如创建新文件)下表现不佳, 需要多次写入多个结构, 而且写入之间存在很多短寻道和旋转延迟;

对RAID支持不好.

因此, 理想的文件系统应该专注于提升写入性能, 充分利用磁盘的顺序带宽, 在常见工作负载下表现良好, 对RAID支持良好.

LFS(Log-structured File System, 日志结构文件系统)的核心思想: 写入磁盘时先将(包括元数据在内的)所有更新在内存段中缓冲, 缓冲段满时发起一次向磁盘的长时顺序写入, 传输到磁盘的未使用部分. LFS永远不会覆写现有数据, 始终将数据段写入空闲位置. 段很大, 可以有效地使用磁盘, 令其性能接近于峰值带宽.

💡

顺序读取是不现实的(读取行为完全可能随机分布在磁盘的各处), 然而写入行为完全可以是顺序的(选一块顺序的地址写入即可).

顺序写入设计

将数据块及其inode一同放在一处, 避免跨区域写入导致寻道和旋转:

但是单单将数据块和inode放在一处不足以保证高效写入. 若连续写入先后间隔到达, 则可能因为时间差错过目标扇区而导致频繁的旋转延迟. 故若要获得良好性能, 必须使用写入缓冲, 攒够一大批连续写入事务之后大量(同时)向磁盘驱动器发出(或发出一次大写入).

LFS一次性写入的大块更新称为段(重名, 不是虚拟内存中的段). 只要段足够大就能有效摊销.

连续写入之后的磁盘布局:

查找inode

💡

老式文件系统中所有的inode以数组形式存放在固定位置, 只要得知目标inode在inode表中的偏移量即可;

FFS将磁盘切分为块组, 每个块组有自己的inode表, 故需要额外知道每个块组的大小和起始地址, 以及目标inode在其块组inode表中的偏移量.

LFS的inode则分散在整个磁盘上(紧随在每个数据块后面), 且因不会覆盖使用过的块故最新版本的inode位置会不断移动.

解决方案: inode映射, 在inode号和inode之间维护一个间接层imap: inode号 → inode地址(此处的imap可以理解为inode表, 用inode号索引到对应inode的地址). 每次写入inode时都会在imap中登记新增或更新.

imap本身也需要持久化到磁盘, 才能在断电后也忠实地维护每个inode的地址(不然断电就废了). 因此引入了一个问题: imap应该放在磁盘的何处?

若放在周知的固定地址: 固然简单有效, 但是在该地址与写入目标地址之间横跳会导致寻道开销;

实际采用的策略: 将imap追加到紧随最新一次写入之后的位置. 因此, 当写入新数据块时, LFS实际上将新数据块本身, 其inode和最新版本的完整imap一同写入磁盘.

💡

有了imap不愁找不到inode了, 可是imap又到哪里去找呢? 这样递归下去建立索引层是没有尽头的, 一定需要一个周知的地址来存放线索的末端.

LFS在磁盘上划分一个固定的区域, 称作”检查点区域(ckeckpoint region, CR)”, 包含指向最新的imap的指针, 通过读取CR中的该指针即可找到imap, 进而找到inode, 最终找到数据块或元数据. 检查点区域仅定期更新, 不会导致频繁的寻道开销. 示例中CR放在0地址处(Q: 即超级块中?)

读取文件

流程: 检查CR找到imap → 将整个imap加载到内存(在此之后直接读内存中的imap即可), 查询imap找到inode → 根据inode中的直接指针/间接指针找到数据块并读取.

直到写任务出现才出现脏数据, 到时候再将(脏的)CR, imap, inode和数据块写回磁盘.

目录数据

LFS的目录结构与传统Unix系统基本相同, 目录的数据本质上是元数据(Pair<文件名, inode号>).

目录也采取顺序写入机制. 以下示例为在某个目录dir中创建文件foo:

先写了文件, 再写了目录, 最终追加上更新后的imap.

访问文件foo的流程: 查CR找到imap → 将整个imap加载到内存, 查询imap找到目录dir的inode → 根据目录inode中的条目获取foo的inode号 → 查询imap找到foo的inode → 根据foo的inode中的直接/间接指针找到目标数据块.

💡

递归更新问题:

对于任何不会重用块(即原地更新)的文件系统, 当更新inode时都会使inode在磁盘上的存储位置发生变化. 如果这一变化会导致目录数据的更新, 则会引发目录的父目录的更新, 一直递归到根目录.

LFS通过引入imap巧妙地解决了这一问题, 当inode的地址改变时只需要修改imap这一中间层, 不涉及对包含它的目录的修改, 因此不会引发递归更新.

垃圾收集

由于不会进行原地更新, 所以当任意新版本数据在新块上完成写入之后, 旧版本的数据都称为垃圾, 需要回收(否则很快就会将磁盘空间用尽).

示例1:

示例2:

D0没有修改, 追加了一个数据块D1并修改了inode→原来的inode变为垃圾, 仍然指向D0但是从imap中除名, 不会再被访问.

LFS只保留文件的最新版本, 因此它必须在后台定期查找数据块/inode等结构的垃圾版本并及时清理, 使其再次空闲, 可以在后续写入时被重用.

问题: 若LFS清理程序在运行时简单释放单个垃圾块, 则会在内存中留下大量不连续碎片, 不利于为顺序写入分配连续大块, 会极大降低性能.

解决方案: LFS让清理程序按段(即先前大段写入使用的大小相同的内存块)工作, 为后续顺序写入清理出大块连续空间.

工作流程: 定期读入许多旧的(部分使用的)段, 判定该段中各块的死活, 将存活的块打包复制(妥善安置)到一个新的段, 然后将该段全部释放.

💡

Q: 如何判定块的死活?

A: LFS在每个段的头部维护一个”段摘要块(segment summary block)”, 记录该段中每个数据块的inode号及其在所属文件中的偏移量. 根据这些信息可以直接确定块的死活.

判定流程: 查段摘要块找到要判定的块的inode号 → 查imap找到该数据块的inode → 查inode检查指针字段, 检查指针是否指向该数据块(实际上是正向指针和反向指针对质). 如果一致则存活, 不一致则为垃圾.

在实际实现时LFS做了更多设计, 方便判定块的死活, 例如为文件inode在imap中的记录和所属段的段摘要块中分别维护一个版本号. 当文件被截断或删除时版本号++, 并在imap和新的所属段中登记. 要判定某个块是否存活时只需要检查所属段的段摘要块中的版本号是否与imap中的匹配即可, 匹配则存活, 否则为垃圾.

清理策略:

何时清理: 固定周期性清理/空闲时间清理/磁盘已满时清理/...;

清理哪些块: 一种可能方法(分离冷热段): 常发生覆盖的段(热段)少清理(因为刚清理并转移了活块就可能又产生新的垃圾), 不常发生覆盖的段(冷段)多清理(垃圾就是垃圾, 存活就是存活).

崩溃恢复和日志

💡

如果系统在LFS写入磁盘期间发生崩溃, 会导致什么后果?

正常工作时LFS会将所有写入任务缓冲一段时间后一次性顺序写入. LFS使用日志组织这些写入行为, 定期更新检查点区域CR, 在这些操作期间随时有可能发生崩溃.

为确保CR的原子更新, LFS在磁盘的两端维护了两个CR并交替写入. 更新CR时使用了一个保险的协议: 先写入一个带时间戳的CR头, 再写入CR的主体, 最后写出一个同样带有时间戳CR的末尾(可以类比预写日志中的TxB和TxE, 通过头尾封装来确保中间安全), 若在CR更新期间发生崩溃则头尾的时间戳会不一致, 从而暴露错误, 最终丢弃.

对于确保顺序写入的原子性, 由于LFS更新CR的间隔较长, 所以当系统崩溃重启后得到的CR很有可能是旧版本, 可以用于恢复数据(旧数据不会被覆盖), 但是在该版本到崩溃期间的更改将会丢失. 为了改进丢失问题, LFS借鉴数据库中的前滚技术, 根据当前的CR(大概率是旧版本), 找到(大概率是旧版本的)数据日志的末端, 从该处开始读取下一个段并查看其中是否包含有效更新. 若有则据其进行恢复.