skip to content

Search

大三上 CSE 的 Lab 解题记录

19 min read Updated:

记录我完成计算机系统工程（CSE）的 Lab 的思路和遇到的 bug。

# cse
# chfs
Not in series

Lab 1: Basic Filesystem

Preparation

代码拉下来先看了看git log，发现今年只改了 Lab 文档，代码还是两年前的

一开始编译测试的时候就给我没整明白了，我是用 VSCode 进入到容器内进行开发，按照助教的提示执行

mkdir build
cd build
cmake ..
make build-tests -j
make test -j

理论上应该通过BasicTest测试，结果在执行倒数第二句的时候直接报错buffer overflow detected，问 Gemini 得到的答案是：

根据你提供的报错信息，这不是你代码的问题，也不是 fmt 或 gtest 库本身的问题。问题的核心在于你系统中的构建工具链 (build toolchain) 出了问题。 … 总结一下：首选方案是更新你的系统和开发工具包（特别是 binutils）。这有超过 90% 的概率能解决你遇到的这个问题。

于是我很担心又是 Mac 运行 Ubuntu 容器时导致的问题，好在我先试了别的方法——不用 VSCode 的终端，在自己的终端里进入到容器内执行命令，结果居然编译成功了，这 bug 也是真离谱。

Part 1: Block Layer

The block layer implements a block device which provides APIs to allocate/deallocate blocks, read/write data from/to the blocks.

Part 1A: Block Manager

这部分要实现四个函数：write_block、write_partial_block、zero_block、read_block，我调用了memcpy和memset来实现。

Part 1B: Block Allocator

分配指定id的块时，需要在bitmap中将对应比特位置成 1。逻辑不是很难，就是需要在 bit、byte、block 的大小之间不停换算比较麻烦。

Part 2: Inode Layer

The inode layer manages the blocks provided by the block layer in the form of inode. This layer provides APIs to allocate/deallocate inodes, read/write data from/to these inodes. The superblock is also in this layer, which records some critical information of the filesystem.

Part 2A: Inode and Inode Manager

这个 Lab 的 Inode Manager 布局和课上讲的有点区别，一方面是用一个位图标记某个 Inode 的使用状态，并动态分配存放 Inode 的 block；另一方面是一个 Inode 占用一个完整的 block。

allocate_inode

新建一个inode和一个buffer，把inode的数据 flush 到buffer里后，用bm把buffer里的数据写进 block 里；计算出inode_id后用set_table方法写进 Inode Table；最后返回inode_id。

set_table

先找到要写入的bid在 Inode Table 中所在的块和偏移量，然后用bm写入数据。

get

就是把set_table做的事情反过来读出来。

free_inode

先用set_table把inode_id处置为KInvalidBlockID，再把位图中的对应位置成 0。

Part 3: Filesystem Layer

The filesystem layer provides some basic filesystem APIs, including file operation APIs and directory operation APIs.

Part 3A: Create

先用block_allocator_给inode分配一个 block，拿到block_id后再用inode_manager_分配一个inode。

这里有个东西让我挺困惑的，TODO 里提示要在此处用block_manager_把inode的数据写入对应的 block，那我还把type传入allocate_inode不就没意义了吗，而且先前已经在这个函数里实现了在对应的 block 里写inode的数据。

Part 3B: Read and Write

write_file

这个需要特别处理的点就是 indirect block 的分配、释放和写入，其它的都是调用一些前两层的 API 就行。

read_file

逻辑本身也不复杂，有一个地方值得注意的是，std::vector的reserve()方法只是预留了一定大小的空间，但其真正的 size 并没有变化，因此不能直接操作内存，但是用push_back()、emplace_back()、insert()等方法就没问题。

Part 3C: Operations on Directory Entries

parse_directory

用一些标准库里的字符串操作。

read_directory

读出对应inode中的数据后再调用parse_directory即可。

append_to_directory

直接在字符串后面追加即可。

rm_from_directory

一个遍历每个 entry，若某个 entry 的文件名为要删除的，就不把它加入到返回的字符串中。

在集成测试的时候报错了，看 log 发现报错是调用substr(1)的时候越界了（因为我一开始的做法是给每个不删除的 entry 前面加上/之后追加到res里），意识到有可能删掉某个文件后目录为空了。

Part 3D: Combine Directory and File Together

lookup

先调用上一步实现的read_directory，然后遍历列表寻找对应名字的 entry，返回其inode_id。

mk_helper

还是先read_directory，看看是否已有同名目录或文件，然后调用alloc_inode分配并获得inode_id，最后再调用write_file更新父目录的信息。

unlink

和mk_helper做相反的操作，先找到对应名称的文件，删除后再更新父目录的信息。

Lab 2: Distributed FileSystem

Preparation

Lab 2 是基于 Lab 1 的，需要先拉取代码后合并lab1分支。

Part 1: Distributed Filesystem

Part 1A: Data Server

需要实现的四个函数和 Lab 1 中的基本一致，就是多了一个version_t，但在这个环节中还无需实现，用一个假的tmp_global_version占位即可，在分配和释放块时对其 +1（如果在分配块时直接返回一个固定值，没法通过测试）。

Part 1B: Metadata Server

mknode、unlink、lookup都直接调用FileOperation中对应的操作即可。

get_block_map

先读取该 inode 的信息，由于BlockInfo中的三元组存的block_id_t、mac_id_t、version_t分别是 64 位、32 位、32 位，所以 inode 中的inode_id_t blocks[]数组中每两个对应一个BlockInfo，用reinterpret_cast转换一下。

allocate_block、free_block

分配和释放 block 的操作需要使用 RPC 调用，完成后还要更新对应的 inode。由于原本的Inode类的定义里没有更新inner_attr的方法，于是新增了这个方法：

auto set_size(u64 sz) {
  inner_attr.size = sz;
  inner_attr.set_all_time(time(0));
}

readdir

直接使用read_directory方法，需要转换成返回值对应的数据结构。

get_type_attr

根据 id 拿到 inode 后，读取对应信息返回即可。

测试时遇到了两个问题，一个是MetadataServerTest.CreateDirThenLookup总能在首次测试的时候通过，而再次测试就寄了，GPT-5-Codex 说是测试前没有删除旧数据，但问助教说他那边没有这个问题，找了好久也没解决，遂摆；另一个是MetadataServerTest.CheckUnlink没法通过，让 GPT-5-Codex 帮我 debug，发现 Lab 1 里实现free_inode后修改位图并没有写回磁盘。

Part 1C: Filesystem Client

mknode、unlink、lookup、read_dir、get_type_attr均可直接使用 RPC 调用。

read_file

先读取文件属性决定实际可读字节数，再获取块映射。利用dispatch_request计算需要访问的首块/尾块及偏移区间，逐块向数据服务器发送read_data，将返回内容按顺序拼接成结果向量。

write_file

根据写入结束位置计算所需块数，不足则循环调用alloc_block补齐映射；随后同样借助dispatch_request拆分写入窗口，将每段数据打包后调用write_data。写入过程中跟踪已写字节数，避免越界或重复覆盖。

free_file_bloc

通过 RPC 调用元数据服务器的free_block，在元数据侧完成映射删除并释放数据块。

增加版本号数据块以避免竞态条件

直接让 GPT-5-Codex 给我大动工了，具体而言，在 dataserver 上的前(total_blocks + versions_per_block_ - 1) / versions_per_block_个块存放版本信息，针对块的各种操作都要同时更新版本信息。AI 还为这个版本控制功能加上了锁。

Part 2: Support Concurrency

在MetadataServer类中加入成员mutable std::mutex metadata_mu_，然后在其中所有可能出现多线程并发问题的操作中先执行：

std::lock_guard<std::mutex> lk(metadata_mu_);

一开始DistributedClientTest.ReCreateWhenDelete测试还没法通过，又是 GPT-5-Codex 发挥神力在ChfsClient::mknode的实现中加了一句给解决了：

if (inode == 0) {
  return ChfsResult<inode_id_t>(ErrorType::INVALID);
}

Part 3: Recover after Crash

这部分不计入总成绩，我直接偷懒让 GPT-5-Codex 给写了hhh

**整体思路概览**  
为了满足 Part 3 “元数据操作可崩溃后恢复”的要求，我把工作拆成三层：最底层的块管理器负责提供日志所需的额外空间与写入捕获；中间层的 `CommitLog` 负责 redo 日志的编码、落盘、恢复与 checkpoint；最上层的 `MetadataServer` 在执行 `mknode`/`unlink` 时启动捕获、生成日志、再调用原有的元数据逻辑，从而把两个操作包装成“先记录日志、后真正写磁盘”的 WAL（write-ahead logging）流程。
 
---
 
**1. BlockManager：为日志和捕获做硬件准备**  
- 在 `BlockManager` 的日志构造函数中我把总块数分成“真实数据块 + 1024 个保留日志块”，以 `log_start_block_` 记录日志区起点。这样日志与元数据共享同一个文件，并且日志区的写入一样会经历“可能失败”的模拟逻辑。  
- 新增 `begin_capture()` / `finish_capture()`：一旦捕获开启，所有对普通数据块的写操作都会把写入内容临时复制到内存里的 `captured_blocks_` 中，方便稍后生成 redo 日志。  
- 新增 `consume_failure_flag()`：底层一旦触发“每三次失败一次”的模拟，除了返回 `ErrorType::INVALID` 外，还会通过原子布尔记录下来，方便上层知道“刚才有磁盘错误，必须让事务回滚并走 recover”。  
 
这一步是 Part 3A 的基础：没有日志区域和块捕获，就无法构造 redo 日志，也无法得知物理写入是否失败。
 
---
 
**2. CommitLog：实现 redo 日志的写入、提交、恢复与 checkpoint**  
`CommitLog` 是整个 Part3 的核心，关键点如下：
 
- **日志格式**：每条记录占用两个块：先写数据块，再写元数据块（包含 magic、事务号、目标块号、日志状态 PREPARED/COMMITTED 等）。只要读到一个 COMMITTED 记录，就可以用数据块内容直接覆写目标块实现 redo。  
- **append_log() / commit_log()**：  
  1. `begin_capture` 收集到哪些元数据块被修改之后，`append_log` 会把这些块依次写入日志。写数据块、`sync`、写元数据块、`sync`，保证“日志先落盘”。  
  2. 如果任何一次写日志失败（可能模拟的磁盘错误），就停止追加并复位尾指针，让当前事务返回失败。  
  3. `commit_log` 只是把对应元数据块的状态改成 COMMITTED，并在启用 checkpoint 时触发 `checkpoint()`。  
- **recover()**：重启后顺序扫描日志区域；只要看到 magic 正确且状态为 COMMITTED，就用日志里的数据块重放到目标块，然后把日志块清零，以免重复恢复。  
- **checkpoint()**：遍历所有事务记录，把状态为 COMMITTED 的日志数据写回真正的元数据块，随后清掉日志块、更新状态为 APPLIED，并维持一个 `sequence_` 用于决定哪些日志仍需保留。`kMaxLogSize` 超过 128 会主动触发 checkpoint。  
 
通过这些步骤，实现了标准的 redo-only WAL：日志先写、崩溃后根据日志重放、周期性把已提交的日志刷新回数据区并删除。
 
---
 
**3. MetadataServer：把 WAL 包进元数据操作**  
负责在真正修改 inode/目录前后插入日志逻辑：
 
- 在 `mknode`/`unlink` 加锁后，若启用日志就调用 `begin_capture()`；执行原有的 `mk_helper` / `unlink`；随后 `finish_capture()` 拿到所有被改动的块，传给 `CommitLog::append_log()`；最后 `commit_log()` 并视情况 `checkpoint()`。  
- 一旦底层写日志失败（包括模拟磁盘故障），`BlockManager::consume_failure_flag()` 会告诉上层，于是操作返回失败（`mknode` 返回 0、`unlink` 返回 false），同时日志已经部分写入，下一次恢复即可再试。  
- 成功路径下，原来的元数据逻辑不变，只是多了“先写日志”与“失败检测”这两个守门员。
 
如此一来，两个元数据操作就具备了“崩溃后一旦恢复就能重得一致状态”的特性：要么返回失败并靠恢复修补，要么返回成功且日志最终在 checkpoint 中消除。
 
---
 
**4. 关键设计权衡**  
- 日志结构选择“两个块一组”的 redo 方式简单直观，恢复时不用解析复杂操作，只需复制块数据。  
- 事务 ID 只用于区分多个操作的日志条目，`sequence_` 保存追加顺序帮助 checkpoint 清理。  
- 所有写日志的地方都谨慎处理错误，避免 `abort()` 把测试直接中止；这是为了正确模拟“磁盘可能失败，但系统继续运行、等待恢复”的场景。  
 
---
 
**5. 验证路径**  
实现完成后，可以开启日志的元数据服务器运行 `CommitLogTest.*`。特别是 `CheckRecoverFromFailure`：它会模拟磁盘失败导致 `mknode` 返回 0，但 `recover()` 之后目录里仍存在新建的条目，证明 redo 生效；而 `CheckCheckpointFunctional` 会大量创建/删除目录，验证 checkpoint 能清掉日志且恢复后状态正确。
 
---
 
总体来说，这套方案严格遵循文档中的要求：日志只关注元数据操作（mknode/unlink），使用 redo logging 与 checkpoint 保证“all-or-nothing”；并且对每一步都加入中文注释和错误处理，让实现更清晰可靠。

Lab 3: Raft

Preparation

Raft 是一种用于复制日志的共识算法。这个 Lab 要我们参照 Raft 论文来实现一个这样的服务器集群。

开始之前，我尝试了 Claude Opus 4.5 和 Gemini 3 Pro 来解决这个 Lab，最终只拿下了 Part 1 和 Part 2 的一部分，不愧是号称 CSE 最难的 Lab（

我观看了这个视频以了解 Raft。

Part 1: Leader Election

文档中提供了建议的实现步骤：

  1. RequestVoteArgs结构体需要四个字段：候选者 term、候选者 ID、候选者最后一条日志 ID、候选者最后一条日志 term；RequestVoteReply结构体需要两个字段：当前 term（应该是投票者的）、投的是赞成票还是反对票。
  2. 实现RaftNode::request_vote。如果候选者 term 较小，则直接投反对票；如果候选者 term 较大，则更新自己的 term，并将身份转为追随者。如果候选者最后一条日志 term 较大，投赞成票；如果候选者最后一条日志 term 一样，但最后一条日志 ID 较大，也投赞成票；否则投反对票。
  3. 实现RaftNode::handle_request_vote_reply。先检查收到的回复，如果回复的 term 较大，则更新自己的 term，并把身份转为追随者，直接 return。然后判断自己的身份是不是候选者，如果不是，直接 return。最后再判断是否收到了赞成票，我的做法是用一个 bool 数组存储 target 的选票（避免重复收到同一个 node 的赞成票），统计数组中 true 的个数，过半则转为领导者。
  4. to be continued…