返回学习路线

文件在哪里，掉电后又能相信哪一份 ​

一份逻辑文件可以保持连续字节地址，数据却分散在多个区间、多个日志段乃至多块成员盘。这个任务要求沿每层映射找到真实位置，再在部分写入和故障下复算恢复结果。所有快照独立重置，教学块均为256字节；文件逻辑块、设备逻辑块与成员盘内块分别编号。

入口与最终交付 ​

先确认旧文件块映射与分配理路文件块映射与空间分配File block mapping · Direct and indirect blocks · 文件块位图分配由文件字节偏移经过inode直接和间接指针找到设备块，并把数据、大小、指针和空闲位图的共同恢复义务列全。和设备完成与持久化理路设备I/O、DMA与完成边界Device I/O and DMA · Polling interrupt DMA给设备请求建立提交、数据搬运、命令完成和稳定存储四个边界，核验描述符所有权、DMA地址与缓冲生命周期。的接口。区间分支读Extent映射理路Extent文件区间映射Extent mapping · 文件extent · 文件区段映射用逻辑起点、长度和物理起点描述文件中的连续区域，逐步计算字节寻址、孔洞、覆盖拆分与合并条件，区分表示更新与持久发布。与空闲区间管理理路文件系统空闲区间管理Free-space extent management · 空闲区间双索引 · First fit and best fit ranges把设备空闲块组织成最大连续区间，维护地址和长度两种索引，执行首次适配、最佳适配与左右合并，并用双向反例区分策略。；追加分支读日志结构布局理路日志结构文件系统的追加布局Log-structured file system · LFS inode map · 日志结构文件系统把数据、inode与inode映射追加到新位置，通过固定检查点找到当前文件版本，并在可复算持久切点中区分追加布局、提交与旧空间回收。与段清理理路日志段清理与写放大LFS segment cleaning · 段清理 · Cleaning write amplification按当前映射判定日志段中的活块，先复制并持久发布新地址再回收旧段，逐项核算净释放空间、数据写放大和含读取的清理成本。；设备分支读条带和镜像理路磁盘条带与镜像的布局和故障集合RAID striping and mirroring · RAID 0 and RAID 10 · 条带与镜像从逻辑块号算出条带成员与盘内位置，比较四盘条带和成对镜像的容量，枚举哪些双盘故障可恢复，并单独说明部分持久写与重建读错。与校验更新与写洞理路RAID校验更新与写洞RAID parity write hole · RAID 5 parity update · 校验阵列写洞通过四盘异或校验计算擦除重建和更新I/O，枚举数据与校验的持久组合，展示部分写入如何破坏未改块，并界定日志与部分校验保护的能力。。

最终交付一份记录，包含：新旧extent表、双索引分配日志、LFS持久切点表、清理空间/I/O账、镜像失效集合、写洞四格表。每部分再给出一项会让现有证明失效的模型变化，以及需要补上的接口。

任务一：从字节偏移走到设备地址 ​

DISK-32有32块，文件长11块，extent为 $(0,3,8)$、$(5,4,20)$。计算文件字节1553和1025的读取位置。随后用新物理块12、13替换文件块6、7，列出规范化的新表以及仍然为洞的逻辑块。

核对。 1553是逻辑块6偏移17，映射到设备块21偏移17，即设备字节5393。1025是逻辑块4偏移1，位于洞中读零。新表为 $(0,3,8),(5,1,20),(6,2,12),(8,1,23)$；洞仍是3、4、9、10。旧21、22在新映射安全发布和旧引用退出前不能复用。

迁移。 把新物理起点改为21，三片可以重新合成 $(5,4,20)$；只改写逻辑块6时，逻辑块7必须继续映射到22。分别说明为什么需要逻辑连续与物理连续两项合并条件。

任务二：14块空闲不能决定未来请求成败 ​

空闲区间为 $[1,9)$、$[12,18)$，块0保留，其余块已分配。首次适配按地址挑第一个可放下的区间；最佳适配按长度、地址排序。都从左端切出请求，失败不改变任何状态。

分别重置执行请求串5、7和5、3、6，列出每次交付地址、地址索引、长度索引。再把 $[1,9)$ 交付成A长2、B长3、C长3，按A、C、B次序释放，检查最后一次是否同时合并两侧。

核对。 5、7时首次适配得到 $[1,6)$ 后失败，最佳适配得到 $[12,17)$ 再得到 $[1,8)$。5、3、6时首次适配恰好用完两段；最佳适配得到 $[12,17)$、$[1,4)$ 后，余下长度1与5，最后失败。释放实验最终恢复原两段，长度键为 $(8,1),(6,12)$，按长度排序时6在8之前。

迁移。 若请求新增8块对齐条件，$r\le max(b-a)$ 不再足以保证成功。例如仅有 $[3,11)$，长度8，但其中没有一个起点为8倍数的完整8块范围。写出新条件应当先求区间内第一个合格对齐起点，再检查右端。

任务三：追加之后，恢复入口选了哪一版 ​

初态检查点0→imap4→inode3，inode指向数据 [1,2]，文件长512字节。覆盖第二块时追加新数据8、新inode9=[1,8]、新imap10=F→9，最后将检查点改指10。检查点单块写原子，flush可靠，单写者，无快照。

列出新记录未全持久、新记录flush完成、检查点写入未确认、检查点flush成功这四阶段。说明何时可确认持久成功，并追踪新版本字节300。

核对。 前两阶段恢复旧第二块2。第三阶段可以恢复完整旧或完整新版本；第四阶段必须恢复新块8。字节300从块8偏移44读。确认只能在检查点flush成功之后。提前发布根时，8、9、10的8种持久子集中只有全体持久这一种能支撑完整新链。

迁移。 若改为追加第三块，新inode应为 [1,2,8]，旧块2仍活。若每30秒才更新检查点，却更早确认用户持久写，需要说明新增的有效尾部识别及roll-forward协议；不能直接援用本题的检查点恢复证明。

任务四：同一分母，三种成本账 ​

一个8数据槽的段，只有槽1的A:1和槽7的E:0仍被当前映射引用，其余均已被新地址取代或删除。准备两块目标空间，搬移活块，持久发布新地址，再回收旧段，随后写入净释放空间数量的新用户块。

按整段读取，列出读取、搬移写、新用户写，以及净空闲增加。所有数字仅计等大数据块；摘要、inode、imap、检查点、空闲索引与flush均排除。

核对。 读8、搬2、回收8、净增6，再写6新用户块。以6新用户块为共同分母，数据写放大 $(2+6)/6=4/3$，总数据I/O比 $(8+2+6)/6=8/3$；只计清理阶段则 $10/6=5/3$。先搬移需要2块活动空间，净增6不能代替这个启动条件。

迁移。 六槽活时，启动要6块，净增2，写放大4，总I/O比8。若快照还引用当前根已经放弃的一槽，该槽不能按当前表丢弃；请重新计算活块数量，而不是继续代入旧 $u=1/4$。

任务五：四盘不是一种固定的恢复能力 ​

四盘各8块，chunk长2。RAID0在四盘间轮流分chunk；RAID10组成镜像对(0,1)、(2,3)，在两对间条带。计算逻辑块13的位置和两种容量，枚举镜像的六种双盘失效。

核对。 RAID0：D2盘内3，容量32逻辑块。RAID10：D0和D1盘内7，容量16。失败集合{0,1}与{2,3}不可完整恢复，另外四个双盘集合都可。结论假设初始副本一致、失效成员已知、幸存读数正确，不是对部分持久写或静默损坏的保证。

迁移。 D0失败后，D1在重建时有一个块明确读错，那个逻辑块没有可用副本。说明为什么另一个镜像对不能提供恢复值，以及“4种可恢复/6种集合”为什么不是无条件的现实概率。

任务六：恢复公式算出了谁的错误 ​

四盘一行三个数据块加校验，块首字节为 3C,A5,5A,C3，其余字节全0。只改D0首字节为 0F，新校验应为 F0。分别列出D0旧/新与D3校验旧/新的四种持久组合，然后假设D1已知失效。

核对。 旧/旧与新/新重建出原Y=A5；新/旧与旧/新都重建出 96。D1从未被本次请求修改，因此不能用“此次写未确认，可以丢失”解释其旧数据被损坏。构造日志保护时，先声明日志和成员在恢复时是否可读，再给出日志提交、成员更新、flush与清日志顺序。

迁移。 完整条带写免去旧数据读取，却仍可能只持久一部分成员。解释为什么4次写没有因此变成一次原子事务。若一次成员擦除又遇到另一幸存块静默错误，也不能继续套用一处擦除的正确性保证。

运行复算与核验范围 ​

下载标准库复算脚本。在普通Python 3模式运行即可输出JSON，不访问任何磁盘设备、不改变系统设置；-O会明确拒绝，因为它会删除证明用断言。

脚本对9216个extent覆盖情形用逐块映射作oracle，对49152个空闲区间选择情形用独立位图扫描核对；另做6000次混合分配/释放并检查双索引与所有权。它枚举LFS安全持久切点及提前发布的反例、256种清理活块集合、四盘全部16种失效集合，遍历4位数据的单擦除和更新公式，并检查正文十六进制写洞表。

这些检查证明的是所声明模型中的地址、状态和算术一致性。它们没有测试真实磁盘固件、实际文件系统的原子单位、并发性能或真实掉电行为。完成任务时，把每一份结论连同所需故障与持久假设一起交付，才能把小模型正确迁移到更大的系统。