网站开发需要人员,抖音代运营商家谈判话术,做网站用什么主题,展厅设计图效果图大全(2021) 26 [持久化] 持久数据的可靠性#xff1a;RAID和journaling
南京大学操作系统课蒋炎岩老师网络课程笔记。 视频#xff1a;https://www.bilibili.com/video/BV1HN41197Ko?p26 讲义#xff1a;http://jyywiki.cn/OS/2021/slides/16.slides#/ 背景
回顾
文件系统 …(2021) 26 [持久化] 持久数据的可靠性RAID和journaling
南京大学操作系统课蒋炎岩老师网络课程笔记。 视频https://www.bilibili.com/video/BV1HN41197Ko?p26 讲义http://jyywiki.cn/OS/2021/slides/16.slides#/ 背景
回顾
文件系统 把设备抽象成目录树
mount - 文件系统管理mkdir, rmkdir, link, symlink, unlink… - 目录管理open, mmap, read, write, lseek… - 文件管理 使用链表、索引、……实现
如何实现高可靠、高性能
本次课的内容和目标
RAIDRedundant Array of Inexpensive Disks把多块磁盘虚拟化成一块性能更好、更可靠的磁盘。崩溃一致性如何在硬件可能崩溃的情况下保证文件系统数据结构的一致性。
RAIDRedundant Array of Inexpensive Disks
RAIDRedundant Array of Idependent / Inexpensive Disks
持久数据的可靠性
任何物理存储介质都有失效的可能你依然希望在存储设备失效的时候能保持数据的完整。
极小概率事件战争爆发/三体人进攻地球/世界毁灭小概率事件硬盘损坏。但是当小概率时间大量重复那就是必然发生。但我们还是希望系统能照常运转。
增加持久数据可靠性的方法
备胎鸡蛋不能放在一个篮子里
教务处物理备份 期末考试后会提交所有批阅的试卷、成绩表、成绩分布假设教务系统崩溃 v.s. 教务处崩溃是独立事件 两个极小概率事件同时发生那就认倒霉吧 服务器数据备份 所有数据同时写入两块磁盘每日或每周备份 crontab (time-based job scheduler)
RAID: 存储设备的虚拟化
RAID (虚拟化) 虚拟磁盘块到物理磁盘块的 “映射”。
Redundant Array of Inexpensive (Independent) Disks (RAID)
把多个 (不可靠的) 磁盘虚拟成一块非常可靠的虚拟磁盘
类比我们见过的虚拟化
进程把一个 CPU 分时虚拟成多个虚拟 CPU虚存把一份内存通过 MMU 虚拟成多个地址空间文件把一个存储设备虚拟成多个虚拟磁盘
RAID 的虚拟化是 “反向” 的
(一个 → 多个) vs. (多个 → 一个)
RAID 所针对的 Fault Model: Fail-Stop
磁盘可能在某个时刻忽然彻底无法访问 (数据好像完全消失)。如机械故障、芯片故障等磁盘好像就 “忽然消失” 了。假设磁盘能报告这个问题 (如何报告)
你还敢用这个硬盘做 {教务系统, 支付宝, 银行, …} 吗总有一天一定有磁盘会坏掉的坏事件一旦发生就有数据会丢失永远不丢失数据似乎是不可能的。我们还能构造可靠的 (单机) 存储系统吗
RAID - 想法
假设我愿意在系统里多接入一块硬盘用于容灾。通过设备驱动程序抽象成 “一个磁盘” VVV 例如1TB实际由 A,BA, BA,B 两块 1TB 的物理磁盘组成镜像
readb(VVV, blk)可以从 A 或 B 中的任意一个读取。writeb(VVV, blk)将同样的数据写入 A, B 的同一位置。
假设内存带宽远高于磁盘带宽那我们这样的做法
1X write (浪费了 1/2 的总带宽)2X sequential read (tricky)2X random read (使用了 100% 的总带宽)抵抗任意一块盘的损坏
实际上这种做法就是RAID-1。写的时候写入两块实际的盘用于容灾读的时候可以同时从两块盘读增加带宽。即我们可以用多块盘来组成一块更快、更可靠的虚拟磁盘。
RAID - 0
RAID-0: 把多块盘 “交替拼接”
性能分析
RAID-0: 把多块盘 “交替拼接”
V0→A0,V1→B0,V2i→Ai,V2i1→BiV_0→A_0, V_1→B_0, V_{2i}→A_i, V_{2i1}→B_iV0→A0,V1→B0,V2i→Ai,V2i1→Bi完美扩展的高性能虚拟磁盘100% 顺序/随机读写总带宽但完全不能容错
对比RAID-1 (镜像)
V0→(A,B)V0→(A,B)V0→(A,B)读带宽100%容忍一块盘 fail
RAID - 4
RAID: 允许 “多对多” 的映射 (一组映射称为 “条带”, stripe)。(V0,V1)→(A,B,C,D)(V_0,V_1)→(A,B,C,D)(V0,V1)→(A,B,C,D)其中ABV0,CDV1ABV_0, CDV_1ABV0,CDV1。
另一种可能的方式(V0,V1,V2)→(A,B,C,D)(V_0,V_1,V_2)→(A,B,C,D)(V0,V1,V2)→(A,B,C,D)。“三块映射到四块”。
不妨假设所有的条带 Vi,A,B,C,DV_i,A,B,C,DVi,A,B,C,D 的每个块都只有 1-bit。
问题如何用 4 个 bit 存储 3-bit 信息使得 4 个 bit 中的任何一个丢失都能恢复出存储的 3-bit 的信息
异或奇偶校验
对于 bits a1,a2,…,ana_1,a_2,…,a_na1,a2,…,an
存储时an1a1⊕a2⊕…⊕ana_{n1}a_1⊕a_2⊕…⊕a_nan1a1⊕a2⊕…⊕an移项得 a1⊕a2⊕…⊕an⊕an10a_1⊕a_2⊕…⊕a_n⊕a_{n1}0a1⊕a2⊕…⊕an⊕an10。任何一个 bit 丢失 (对应A,B,C,DA,B,C,DA,B,C,D 中某块硬盘不能启动)可以根据 aia1⊕a2⊕…⊕ai−1⊕ai1⋯⊕ana_ia_1⊕a_2⊕…⊕a_{i-1}⊕a_{i1}\dots⊕a_naia1⊕a2⊕…⊕ai−1⊕ai1⋯⊕an来计算出丢失的位。
举个例子如下图 我们共有四块盘A、B、C、PA、B、C、PA、B、C、P其中A、B、CA、B、CA、B、C存储数据PPP盘做奇偶校验。我们假设一开始数据盘存储的数据为(A,B,C)n(0,1,0)(A,B,C)_n(0,1,0)(A,B,C)n(0,1,0)(A,B,C)m(1,0,1)(A,B,C)_m(1,0,1)(A,B,C)m(1,0,1)。则由此我们可以根据 PnAn⊕Bn⊕CnP_nA_n⊕B_n⊕C_nPnAn⊕Bn⊕Cn算出Pn1P_n1Pn1Pm0P_m0Pm0。这时我们假设 AAA盘不幸挂掉了我们就可以根据B、C、PB、C、PB、C、P盘恢复出AAA盘的数据AnPn⊕Bn⊕CnA_nP_n⊕B_n⊕C_nAnPn⊕Bn⊕Cn从而计算出An0A_n0An0Am1A_m1Am1。
RAID-4: Parity Disk专门留一块磁盘作为奇偶校验盘。
(V0,V1,V2)→(A,B,C,P)(V0,V1,V2)→(A,B,C,P)(V0,V1,V2)→(A,B,C,P) AV0,BV1,CV2AV_0, BV_1, CV_2AV0,BV1,CV2PV0⊕V1⊕V2PV_0⊕V_1⊕V_2PV0⊕V1⊕V2 (奇偶校验)
性能分析
sequential/random read: 3x (75% 总带宽)sequential write: 3x (75% 总带宽)random write (tricky) DV0⊕V1⊕V2DV_0⊕V_1⊕V_2DV0⊕V1⊕V2写入任意V0,V1,V2V_0,V_1,V_2V0,V1,V2都需要更新DDD更新 V0V_0V0 需要 readb({A,PA,PA,P}), writeb({A,PA,PA,P})。奇偶校验盘成为了写瓶颈: 0.5x。
RAID - 5Rotating Parity
RAID - 5交错排列 parity block 性能分析
交错排列 parity block让每一块盘都有均等的机会存储 parity sequential read/write: 3x (75% 总带宽) random read (tricky)(read 足够大所有磁盘都可以提供数据) 4x (100% 总带宽) random write (tricky)DV0⊕V1⊕V2DV_0⊕V_1⊕V_2DV0⊕V1⊕V2; 写入任意 V0,V1,V2 都需要更新 D0 奇偶校验依然严重拖慢了随机写入但至少 n 块盘可以获得 n/4 的随机写性能 (能够 scale)
RAID - 更多地讨论
更快、更可靠、近乎免费的大容量磁盘已经成为今天服务器的标准配置。
RAID 的可靠性
RAID 系统发生断电例子RAID-1 镜像盘出现不一致的数据检测到磁盘坏自动重组
崩溃一致性
另一种 Fault Model
我们的硬件的可靠性可以由RAID做到一定程度的保证而我们的文件系统是在磁盘驱动上做的虚拟化是一棵目录树它的可靠性我们需要单独分析。
磁盘并没有故障但操作系统内核可能 crash系统可能断电。在内存中读写时我们不会考虑到一致性的问题。因为内存掉电数据全部丢失我们回来重新跑程序就是了。但是在磁盘读写时由于我们的磁盘时持久化的存储设备就会涉及到崩溃一致性的问题。比如以ext2文件系统为例即使只是向文件的末尾append一个字节的数据也涉及到bitmap、inode和实际data三部分的写入那假如在我们刚刚写完bitmap时系统断电了后面两部分都没有写完我们这时的文件系统还是正确的吗有点像我们并发程序设计中的原子性即崩溃的时候写磁盘的原子性被打破了。
崩溃一致性 (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). 导致崩溃一致性的原因就如同我们上面介绍的那样源自于原子性的丧失
RAID: write(V0V_0V0) → write(AAA), write(BBB)ext2 (文件追加写入一块): write(inode); write(bitmap); write(data); 但是存储设备的多次写入没有原子性保证 有些磁盘在设计时甚至为了性能没有顺序保证(类似我们之前讲的 并发编程从入门到放弃)
原子性丧失后果
考虑追加写入一个数据块磁盘上数据结构的更新包括我们之前说过的b(bit), i, d三个部分的写 我们接下来分别分析只写了三个部分中的某一部分时的后果
{b} - dead block如果只写了bitmap而inodes和data blocks都没有写的话就相当于一块block被标记为了已用虽然实际上时还没有写过的可用的block但是再也不能被用到了成为了一块dead block。有点类似于malloc了当时没有free的内存泄漏。磁盘泄漏{i} - dangling pointe 如果只写了inode但是没写bitmap和data blocks的话问题就大了。试想这样一种情况某个高权限的人写入了自己的私密信息如密码等到某个文件但在这个写入过程中断电了只写了inode但是没写bitmap和data blocks。那这一块就会被认为是还未写的如果有人试图分配这块block就可以获得它的读写权限可能会访问到上述私密信息。如果被别有用心之人构造大量的workload来获取大量的磁盘上写了 i 但是没写 b 和 d 的块的读写权限后果不堪设想相当于本磁盘的数据安全性已经得不到保证。{d} - random writes (没有一致性问题){b,i} - incorrect data{i,d} - dangling pointer{b,d} - dead block
崩溃恢复FSCKFile System Checking
大家可能会有印象早年间的Windows XP系统在不正常关机之后会在再次开机蓝屏时问你要不要检测磁盘如果要检测就会是一个很漫长的等待时间这就是在做FSCKFile System Checking。
根据磁盘上已有的信息恢复出 “最可能” 的数据结构
检查 inode 标记的数据块是否 bitmap 都标记为 “1”检查 inode 数据是否 “看起来合法”否则删除检查是否存在 dangling link没有链接的 inode 被移到 lostfound 目录中lostfound目录大家应该都在Linux系统中见到过就在完成FSCK检测时创建的
刚才的哪些情况可以由 fsck 修复
{b,i} - incorrect data{i,d} - dangling pointer{b,d} - dead block
FSCK的难题
到底谁是对的
在发生不一致时“到底什么是对的”在发生不一致时可能会有多种情况导致现有的情况那么到底应该按哪一种来恢复呢
如果 fsck 的时候发生崩溃
fsck 也是程序fsck 也要访问文件系统。如果 fsck 时发生崩溃由于 fsck 完成的工作比一般的磁盘读写更加危险文件系统可能进入彻底无法恢复的状态
因此fsck 更多用于磁盘发生部分损坏时的数据抢救。
针对 crash我们需要更可靠的方法我们需要一个更可靠的方法文件系统不一致的根本原因是存储设备无法提供多次写入的原子性
崩溃恢复journaling
日志 (Journaling)
能否在磁盘 API 上实现可靠的 multi-write 原子性
readb (读一块), writeb (写一块), sync (等待所有过去的写入落盘)
数据结构的两种实现方法
我们前面说到要将文件系统理解为磁盘上的数据结构。
存储实际数据结构这是我们学习数据结构时常见的表示形式 文件系统的 “直观” 表示crash unsafe append-only 记录所有历史操作这种形式不常见听起来也很离谱但是在维护崩溃一致性时却有关键作用 “重做” 所有操作得到数据结构的当前状态容易实现崩溃一致性
append-only 的数据结构也是实现分布式系统的关键技术。
实现 Atomic Append 定位到 journal 的末尾 (使用 readb) 在 journal 末尾 append TXBegin并记录所有操作 记录文件系统操作 v.s. 记录磁盘块操作 sync等待数据落盘 append TXEnd sync等待 TXEnd 落盘 sync 返回后持久化完成 (“committed”)
实现 Crash Consistency
小孩子才做选择我文件系统全都要 — 两种数据结构的便是形式都维持
主要维护文件系统的结构但预留一定的 journal 区域journal commit 后可以将 journal 中的操作直接应用到文件系统上 (checkpoint)。
redo logging (write-ahead logging): journal 记录 “做什么” 先写 journal再写文件系统崩溃恢复时重做 journal 中的操作 undo logging: 记录如何 “撤销” 操作 (即块中的数值) 先写文件系统再写 journal崩溃恢复时撤销文件系统中的
Journaling: 优化
现在为了做journaling磁盘需要写入双份的数据性能会大幅下降我们需要再性能和可靠性之间做一个trade-off。下面是集中常见的文件系统的实现方式
批处理 (xv6; jbd) 多次系统调用的 Tx 合并成一个减少 log 的大小jbd: 定期 write back Checksum (ext4) 不再标记 TxBegin/TxEnd直接标记 Tx 的长度和 checksum Metadata journaling (ext4 default) 数据占磁盘写入的绝大部分只对 inode 和 bitmap 这些关键信息做 journaling 可以提高性能保证文件系统的目录结构是一致的但数据可能丢失
为应用程序提供 Multi-Write 的一致性
在未来可能会有TxOS 提供三个新的系统调用
xbegin, xend, xabort实现多个系统调用的原子性 应用场景数据更新、软件更新、check-use…… D. E. Porter, et al. Operating systems transactions. In Proc. of SOSP, 2009.
总结
本次课内容与目标
持久数据的可靠性
fail-stop: RAID随机损坏fsck崩溃journaling
Takeaway messages
把磁盘理解成 “数据结构”
