实现可靠的磁盘

持久数据的 “持久”

如果我们的数据 “就地消失”

  • 通讯软件无法使用
  • 支付软件无法使用

没有 “一个” 绝对可靠的存储设备

临时失效

  • Kernel panic (bug); 断电

部分失效

  • ECC 纠错失败; fail slow

永久失效

  • 小概率事件：硬盘物理损坏 (大量重复 = 必然发生)
  • 极小概率事件：战争爆发/三体人进攻地球/世界毁灭

RAID: 存储设备的虚拟化

性能和可靠性，我们能不能全都要呢？

一个 “反向” 的虚拟化

  • 类比：进程/虚存/文件把 “一个设备” 虚拟成多份

RAID: Design Space

RAID (虚拟化) = 虚拟块号到 (磁盘, 块号) 的 “映射”

  • 虚拟磁盘块可以存储在任何物理磁盘上
    • 物理磁盘读写可以并行；存储>1>1份即可实现容错

RAID-0：更大的容量、更快的速度

  • 读速度 x 2；写速度 x 2
  • Quiz: 交错排列还是一分为二?

RAID-1：镜像 (容错)

  • 保持两块盘完全一样
  • 读速度 x 2；写速度保持一致

容错的代价

浪费了一块盘的容量……

  • 如果我们有 100 块盘
  • 但假设不会有两块盘同时 fail-stop？

能不能只用 1-bit 的冗余，恢复出一个丢失的 bit？

  • x=a⊕b⊕cx=a⊕b⊕c
    • a=x⊕b⊕ca=x⊕b⊕c
    • b=a⊕x⊕cb=a⊕x⊕c
    • c=a⊕b⊕xc=a⊕b⊕x
  • 100 块盘里，99 块盘都是数据！
    • Caveat: random write 性能

RAID-5: Rotating Parity

使 Parity 均匀分布在各个磁盘

c29-1-1.webp

RAID: 讨论

更快、更可靠、近乎免费的大容量磁盘

  • 从此再无 “高可靠性磁盘”
    • 现在我们只需要RAID

c29-1-2.webp

RAID: 自身的可靠性

磁盘 Fail-stop

  • 软件可以感知
  • 自动启用备盘并复制数据
    • 期间性能下降

RAID 物理磁盘不能完美同步

  • 断电 → 数据不一致
  • 如何解决？

计算机系统的又一个黄金时代

“三驾马车” 开启 “大数据” 时代

c29-1-3.webp

这是一个分布式的RAID

数据中心存储：一个 “分布式的 RAID”

Everything is Virtual

c29-1-4.webp

  • 阿里云 Elastic Block Storage (EBS, FAST’24 🏅)
    • 现在理解为什么云厂商能躺着挣 💰 了
    • 算上 3X replica，amplification 还<1<1

数据中心存储的挑战

Data corruption

Fail-slow

c29-1-5.webp

  • Firmware bug; device error; wear-out; configuration; environment; … 磁盘上的 “性能问题”

实现可靠的文件系统

崩溃一致性 (Crash Consistency)

Crash Consistency: Move the file system from one consistent state (e.g., before the file got appended to) to another atomically (e.g., after the inode, bitmap, and new data block have been written to disk).

c29-2-1.webp

(你们平时编程时假设不会发生的事，操作系统都要给你兜底)

Recap: 文件系统的实现

磁盘上的数据结构

c29-2-2.webp

  • 为吞吐量优化
    • 配合 “按块读写”，而不是 “Random Access”
  • 数据结构更关注局部性
    • 临近的信息紧凑地排列在一起

实现崩溃一致性

磁盘：提供的接口

  • bwrite
  • bread
    • 并不提供多块读写 “all or nothing” 的支持
    • 甚至为了性能，没有顺序保证
      • bwrite 可能被乱序
  • bflush 等待已写入的数据落盘
    • 即便是 vSSD，也没有实现 crash consistency

File System Checking (FSCK)

根据磁盘上已有的信息，恢复出 “最可能” 的数据结构

c29-2-3.webp

  • SQCK: A declarative file system checker (OSDI’08)
  • 然而 (FAST’18): “widely used file systems (EXT4, XFS, BtrFS, and F2FS) may leave the file system in an uncorrectable state if the repair procedure is interrupted unexpectedly”

实现崩溃一致性

我们需要一个更可靠的方法

  • 只要磁盘不坏，断电就不会有数据损坏

难实现的根本原因

  • 存储设备不提供多次写入的原子性
    • bwrite(inode)
    • bwrite(d-bitmap)
    • bwrite(data)

重新理解 “数据结构”

视角 1: 存储实际数据结构 (链表、二叉树、……)

  • 文件系统的 “直观” 表示
  • crash unsafe

视角 2: Append-only 记录所有历史操作

  • “重做” 所有操作得到数据结构的当前状态
  • 容易实现崩溃一致性

Jouraling = 1 + 2

  • 先用 append-only 记录日志，等待落盘，再更新数据结构

实现 Atomic Append

用 bread, bwrite 和 bflush 实现 append()

c29-2-4.webp

  1. 定位到 journal 的末尾 (bread)
  2. bwrite TXBegin 和所有数据结构操作
  3. bflush 等待数据落盘
  4. bwrite TXEnd
  5. bflush 等待数据落盘
  6. 将数据结构操作写入实际数据结构区域
  7. 等待数据落盘后，删除 (标记) 日志

Journaling: 优化

现在磁盘需要写入双份的数据

  • 批处理 (xv6; jbd)
    • 多次系统调用的 Tx 合并成一个，减少 log 的大小
    • jbd: 定期 write back
  • Checksum (ext4)
    • 不再标记 TxBegin/TxEnd
    • 直接标记 Tx 的长度和 checksum
  • Metadata journaling (ext4 default)
    • 数据占磁盘写入的绝大部分
      • 只对 inode 和 bitmap 做 journaling 可以提高性能
    • 保证文件系统的目录结构是一致的；但数据可能丢失

Metadata Journaling

从应用视角来看，文件系统的行为可能很怪异

更为一劳永逸的方案：TxOS

  • xbegin/xend/xabort 系统调用实现跨 syscall 的 “all-or-nothing”
    • 应用场景：数据更新、软件更新、check-use……

存储系统支撑了当今的互联网工业——每个 SSD 都是 “套娃” 的计算机系统；它们又组成了大规模存储网络，构成了我们今天的数字世界。实现低成本、高性能、高可靠的存储并不是一个十分简单的问题，这也是计算机产业让我们感到激动的原因。