Chapter 6 Mass-Storage Structure¶
Overview of Mass Storage Structure
磁盘（Magnetic disks）是计算机系统中最主要的辅助存储（secondary storage），容量大、成本低、断电后数据仍能保留，但访问延迟远高于主存。
硬盘（Hard disk） 是最常见的磁盘形式，有些磁盘为可移动磁盘（removable），磁盘驱动器通过 I/O bus 连接到计算机，例如 USB、SCSI、EIDE、SATA。
盘片旋转速度约为每秒 60 ~ 250 圈，历史上磁盘盘片尺寸从 0.85 inch 到 14 inch 不等，现代常见尺寸包括 3.5 inch、2.5 inch、1.8 inch，单盘容量从 30 GB 到 3 TB 不等且仍在增长。
1 Disk Structure¶
磁盘驱动器对上层暴露为一维的 logical block array，每个 logical block 是最小传输单位。上层通常只关心 block number，不直接管理柱面、磁道和扇区。
LBA 到物理扇区的典型映射
Logical blocks 会顺序映射到磁盘 sectors：
sector 0是最外层 cylinder 的第一条 track 上的第一个 sector- 先沿当前 track 顺序映射
- 再映射同一 cylinder 中剩余 tracks
- 然后从外层 cylinder 逐步走向内层 cylinder
理想情况下，logical address 到 physical address 的转换应很简单，但 bad sectors、spare sectors、firmware remapping 等机制会让真实映射更复杂。
磁盘的基本物理结构包括 platter、track、sector、cylinder、disk arm 和 disk head，同一半径上的所有 tracks 组成一个 cylinder。
为什么 OS 通常使用 LBA？
现代磁盘内部可能有坏块替换、缓存、可变扇区密度和 firmware 调度。OS 直接操作 CHS（Cylinder-Head-Sector）既复杂又不稳定，因此更常把磁盘看成线性的 block device。
寻道定位时间（Positioning time）是把磁头移动到目标 sector 所需的时间，也称随机访问时间（random-access time）：
- 寻道时间（Seek time）：移动 disk arm 到目标 cylinder 的时间。
- 旋转延迟（Rotational latency）：等待目标 sector 转到 disk head 下方的时间。
常见性能指标
- 传输速率（Transfer rate）：数据在 drive 与 computer 之间传输的速率，理论接口速率可到 6 Gb/s，实际有效速率约 1 Gb/s。
- 寻道时间（Seek time）：典型机械硬盘约 3 ms 到 12 ms，台式机硬盘普遍为 9 ms。
-
旋转延迟（Rotational latency）：\(one\ rotation = \frac{60}{RPM}\)，平均旋转延迟约为半圈时间，即
\[ average\ latency = \frac{1}{2} \times \frac{60}{RPM} \]
- 平均访问时间：\(average\ access\ time = average\ seek\ time + average\ latency\)
- 平均 I/O 时间：\(average\ I/O\ time = average\ access\ time + \frac{data\ size}{transfer\ rate} + controller\ overhead\)
2 Disk Scheduling¶
OS 负责高效使用磁盘硬件，对磁盘而言，主要目标是缩短访问耗时（尤其是寻道时间）、提升磁盘带宽。
Disk Bandwidth
磁盘带宽（Disk bandwidth）是单位时间完成的数据传输量：
磁盘调度（Disk scheduling）从挂起的磁盘请求（pending disk requests）里选择下一个要处理的请求。若磁盘空闲，请求可以立即执行；若磁盘忙，OS 或控制器会把请求放入队列。
一个磁盘请求通常包含 I/O 类型、磁盘地址、内存地址以及扇区数量，调度算法只有在队列中有多个请求时才有意义。现代设备常由存储设备和控制器的固件在内部做排序，OS 只提供 LBA 请求。
说明
后续调度算法均以如下 cylinder 请求队列为例，假设 cylinder 范围是 [0, 199]，初始磁头位置为 53。
98, 183, 37, 122, 14, 124, 65, 67
2. 1 FCFS¶
FCFS（First-Come First-Served）按请求到达顺序服务，最简单也最公平。
- 优点：每个请求都有机会被服务，不存在无限延期（indefinite postponement）。
- 缺点：没有优化 seek time，平均响应时间可能很差。
Total head movements?
2. 2 SSTF¶
SSTF（Shortest Seek Time First）每次选择离当前磁头位置最近的请求，类似 CPU 调度中的 SJF，通常能明显减少总寻道时间。
- 优点：平均响应时间缩短，吞吐量提升。
- 缺点：预先计算寻道距离会产生额外开销，存在饥饿风险，响应时间差异大。
Total head movements?
访问顺序为 \(53 \to 65 \to 67 \to 37 \to 14 \to 98 \to 122 \to 124 \to 183\)，磁头移动距离为：
2. 3 SCAN¶
SCAN 又称电梯算法（elevator algorithm），磁头像电梯一样沿一个方向移动，沿途服务请求，到达磁盘一端后再反向移动并继续服务。
- 优点：吞吐量高，响应时间的波动小，平均响应时间表现优良。
- 缺点：磁头刚刚经过的柱面若产生新请求，需要等待很长时间才能被处理。
Total head movements?
访问顺序为 \(53 \to 37 \to 14 \to 0 \to 65 \to 67 \to 98 \to 122 \to 124 \to 183\)，磁头移动距离为：
2. 4 C-SCAN¶
C-SCAN（Circular SCAN）把 cylinders 视为一个循环列表，磁头只在一个方向服务请求；到达末端后快速返回起点，返回途中不服务请求。
C-SCAN 牺牲一部分磁头移动距离，换取更均匀的等待时间。因为所有请求都从同一个方向被扫描，不会出现 SCAN 中两端服务频率不同的问题。
Total head movements?
访问顺序为 \(53 \to 65 \to 67 \to 98 \to 122 \to 124 \to 183 \to 199 \to 0 \to 14 \to 37\)，磁头移动距离为：
2. 4 LOOK and C-LOOK¶
SCAN / C-SCAN 会移动到磁盘端点，即使端点附近没有请求。LOOK 和 C-LOOK 的改进是磁头只移动到当前方向上的最后一个请求位置，然后就反向或跳转。
Total head movements?
LOOK 的访问顺序为 \(53 \to 37 \to 14 \to 65 \to 67 \to 98 \to 122 \to 124 \to 183\)，磁头移动距离为：
C-LOOK 的访问顺序为 \(53 \to 65 \to 67 \to 98 \to 122 \to 124 \to 183 \to 14 \to 37\)，磁头移动距离为：
Selecting Disk-Scheduling Algorithm
磁盘调度算法的性能取决于请求数量、请求分布、磁盘类型和 workload，主要的选择原则如下：
SSTF常作为默认选择，因为简单且效果通常不错LOOK和C-LOOK在 heavy I/O load 下通常表现更好- 调度器应作为可替换模块实现，便于针对设备和 workload 调整
- 文件分配方式和 metadata 布局会影响调度效果
File system 会努力提高 spatial locality，把相关数据和 metadata 尽量放近。若文件系统布局很差，即使调度算法优秀，也可能被迫处理大量远距离 seek。
3 Nonvolatile Memory Devices¶
非易失性存储设备中，形态类似机械磁盘的称为固态硬盘（SSD, Solid-State Disk），其他类型包含 U 盘（USB drive）、替代传统磁盘的内存盘（DRAM disk replacement）、主板贴片式闪存以及主存储器件。
NVM 相比机械硬盘（HDD）可靠性更高、读写速度快，但单位容量成本更高，使用寿命相对有限，需要合理的读写管控
NVM 无机械运动部件，不存在寻道时间与旋转延迟，因此 FCFS 调度算法就可以满足使用需求。
问题
SSD 没有机械定位延迟，但 NAND Flash 不能原地覆盖，必须先擦除再写入。擦除粒度大于写入粒度，并且每个 cell 的可擦写次数有限。
NAND Flash 通常按 page 读写，但按更大的 block 擦除。
由于不能原地覆写，闪存页中会混杂有效数据和无效数据。
SSD 控制器需要维护 闪存转换层（FTL, Flash Translation Layer），把上层 LBA 映射到真实 flash pages，同时执行垃圾回收以释放无效页空间。
当空闲 block 充足时，写入可以很快，当 invalid pages 很多但 free blocks 不够时，controller 必须先搬迁有效数据并擦除 block，写延迟会明显上升。
Flash cell 只能擦除有限次数，SSD 寿命常用 DWPD（Drive Writes Per Day）描述，因此需要均匀地向所有单元写入数据。
Magnetic Tape
磁带（Magnetic tape）是早期的辅助存储设备，如今大多用于数据备份。
| 特性 | 说明 |
|---|---|
| 容量 | 大，课件给出 200 GB ~ 1.5 TB 量级 |
| 随机访问 | 很慢，需要 wind / rewind |
| 顺序传输 | 一旦数据到达 head 下方，传输速率可接近磁盘，如 140 MB/s |
| 数据持久性 | 较好，适合长期备份 |
4 Disk Management¶
4. 1 Formatting and Partitioning¶
物理格式化（Physical formatting） 将磁盘划分为扇区，便于控制器读写，每个扇区通常包含 header、data 和 ECC，数据区通常为 512 字节，容量可自定义。
OS 还需要在磁盘上记录自己的数据结构：
- Partition disk：把磁盘划成若干 cylinder groups / partitions，每个 partition 可视为一个 logical disk
- Logical formatting：在 partition 上创建文件系统
- Reserved sectors：某些 FS 预留 spare sectors 处理 bad blocks
- Clusters：FS 可把多个 blocks 组合成 cluster，提高吞吐
- Boot sector：若 partition 包含 OS image，需要初始化 boot sector
4. 2 Device Names and Partitions¶
Linux 中不同磁盘类型有传统设备命名约定。
| 设备类型 | 典型命名 | 示例 |
|---|---|---|
| IDE | /dev/hda 到 /dev/hdd |
/dev/hda1 表示第一块 IDE 盘的第一个分区 |
| SCSI / SATA / USB storage | /dev/sdX |
/dev/sda1、/dev/sdb1 |
Partition Number
分区编号通常从 1 开始，例如 /dev/sda1。传统 MBR 最多支持 4 个 primary partitions。
若需要更多分区，需要使用 extended partition 和 logical partitions，logical partition 编号通常从 5 开始。
4. 3 Mount, Boot Block and Raw Disk¶
Root partition 包含 OS，其它 partitions 可以放其它 OS、其它 file systems，或作为 raw device 使用。
- boot 时挂载 root partition，其它 partition 可自动挂载或手动挂载。
- mount 时检查 file system consistency，metadata 不正确则尝试修复后再挂载，正确则加入 mount table。
- 挂载成功后，用户才能通过目录树访问该文件系统。
Boot block 可以指向 boot volume 或 boot loader 所在 blocks。Boot loader 至少要知道如何从文件系统中定位、加载并启动 kernel。
有些应用希望自己管理 block，例如数据库系统。它们可能使用 raw disk access，让 OS file system 尽量不参与数据布局、缓存和锁管理。
磁盘可能出现坏块（bad blocks），常见方法是 sector sparing，预留备用扇区，当某 sector 损坏时，由 controller 或 OS 把逻辑地址重映射到备用 sector。
4. 4 Swap-Space Management¶
Swap space 用于在 DRAM 不足时，把整个进程或部分 pages 暂时移动到 secondary storage。
Secondary storage 远慢于 DRAM，因此 swap 性能必须优化，可以有多个 swap spaces 分散单个设备上的 I/O 压力，专用 swap partition 通常比普通文件中的 swap 更直接，使用 swap file 更方便扩容和管理。
Linux 的 swap 数据结构会记录某个 swap slot 是否空闲，以及该 slot 被哪些进程 / 页面映射，用 0 表示未使用，用非零值表示被映射使用的进程数。
5 Disk Attachment¶
5. 1 Host-Attached Storage¶
Host-attached storage 通过 I/O bus 直接连接到主机。
常见接口
- SCSI（Small Computer System Interface）
- 一条 cable 上可接 16 个 devices
- SCSI initiator 发起操作，SCSI target 执行任务，每个目标可包含 8 个逻辑单元
- Linux 常用
/dev/sda表示一块 SCSI 磁盘
- IDE（Integrated Drive Electronics）：Linux 传统上用
/dev/hda表示 IDE disk - Fibre Channel：高速串行总线，可形成交换式光纤网络（switched fabric），拥有 24 位寻址空间，常用于存储区域网络（SAN）
5. 2 Network-Attached Storage¶
NAS（Network-Attached Storage）通过网络提供文件系统访问，而不是通过本地 bus 暴露 block device。
客户端可远程挂载服务器上的文件系统，常用协议包括 NFS、CIFS、iSCSI，一般基于远程过程调用（RPC）实现，大多在 IP 网络中使用 TCP 或 UDP 协议传输，iSCSI 协议则是在 IP 网络中封装传输 SCSI 协议。
5. 3 Storage Area Network¶
SAN（Storage Area Network）是连接 servers 和 storage units 的专用高速网络。
SAN 的数据传输占用带宽高，因此需要独立组网。TCP/IP 协议栈在存储访问场景下效率偏低，而 SAN 采用高速互联技术与高效协议。
多台主机与磁盘阵列可接入同一套 SAN，服务器集群能够共享同一套存储资源，存储资源可动态分配给各主机。
6 RAID Structure¶
单块磁盘便宜但可能失效，且吞吐有限。RAID（Redundant Array of Independent Disks）把多块磁盘组合起来，用冗余提高可靠性，用并行提高吞吐。
RAID 的两个目标
- Reliability：一块磁盘失效时仍能恢复数据
- Speed：把数据分散到多块盘上并行读写，聚合带宽
RAID 可以由 OS 在多块 bus-attached disks 上实现，也可以由硬件 RAID controller 实现，还可以作为独立 RAID array box 提供。
| 技术 | 做法 | 作用 |
|---|---|---|
| Data mirroring | 多块磁盘保存相同数据 | 提高可靠性，写入要写多个副本 |
| Data striping | 数据拆分到多块磁盘 | 提高并行读写带宽 |
| Parity / ECC | 保存可恢复丢失数据的校验信息 | 用较少冗余恢复单盘或多盘失效 |
RAID 技术组合被称为不同 levels，常见等级有 0、1、1+0、5、5+0、6、6+0，RAID 2 基本不用。
6. 1 RAID 0¶
RAID 0 把数据均匀拆分到两块或多块磁盘上，使用固定 strip size，但没有 parity，也没有 redundancy。
RAID 0 只提升性能和容量呈现，不提升可靠性。任一磁盘失效都可能导致整个 RAID 0 上的数据不可用。
6. 2 RAID 1¶
RAID 1 又称 mirroring / shadowing，把同一份数据完整写到两块磁盘。
每次写入必须写到所有 mirror，因此写成本较高，读取时可从 seek time 更短的那块盘读，容量利用率约为 50%。除非多个 mirror 同时失效，否则数据仍可恢复。
6. 3 RAID 2 and RAID 3¶
RAID 2 在 bit-level 做 striping，并使用 Hamming code 做错误校正。Hamming code 由 4 bit data 和 3 bit parity 组成，允许使用 7 个硬盘。
位交叉奇偶校验（bit-interleaved parity）
- 数据条带化分散存储在多块数据盘，单独配备一块专用校验盘，存放全部数据盘的校验信息
- 每次写入操作同步下发所有磁盘，单块磁盘仅存储 1 比特数据
- 运算生成校验比特并保存，用于故障后数据恢复
RAID 3 使用位交叉奇偶校验，数据分散到多块数据盘，另有专用 parity disk 保存所有数据盘的 XOR parity。
示例
若 4 块数据盘保存比特 0 1 1 0，则 parity bit 为：
若其中一位丢失，例如 0 ? 1 0，可用剩余 bits 与 parity bit 再做 XOR 恢复丢失 bit。
Bit-level striping 可提高并行性能，但每次写都要更新 parity，XOR 开销通常由硬件完成；恢复时需要大量 XOR，recovery time 较长。
6. 4 RAID 4, RAID 5 and RAID 6¶
| Level | 做法 | 特点 |
|---|---|---|
| RAID 4 | block-level striping + 专用 parity disk | 小读只访问一块 data disk，但 parity disk 可能成为写瓶颈 |
| RAID 5 | 类似 RAID 4，但 parity 分布到所有 disks | 避免单独 parity disk 热点，是常见折中 |
| RAID 6 | RAID 5 基础上增加第二个 parity block | 可容忍更多磁盘失效，写入和容量成本更高 |
6. 4 RAID and File Systems¶
RAID 可以检测并恢复磁盘失效，但它并不能自动防止所有数据损坏。因此一些文件系统会额外加入 checksum 和自恢复机制，例如 Solaris ZFS。
ZFS 为全部文件系统数据与元数据添加校验和，校验和与对应数据、元数据的指针存放在一处，可检测并修复数据、元数据损坏问题。
ZFS 还使用 storage pools，而不是传统固定 volumes / partitions。
Traditional Storage vs Pooled Storage
传统方式先把磁盘切成 volumes / partitions，再在其上建文件系统。Pooled storage 则把 disks 放入统一 pool，pool 内多个 file systems 可共享空间，并从 pool 中动态分配和释放。