CSE_lab2攻略

lab2: Distributed FileSystem

在lab1中，我们已经实现了基本的inode filesystem，并能够操作directory；而在lab2中，我们需要实现一个分布式的文件系统，该系统分为以下三部分，它们通过rpc进行通信：

  • filesystem client: 文件系统服务器，向metadata server发送请求获取元数据，再向各个data server发送请求修改具体的block
  • metadata server: 只有一台，用于存放元数据
  • data server: 有很多台，存放具体的block

在lab2中有两种文件类型：regular file和directory，其中regular file被拆成一个或多个块，存放在不同的data server上；而directory block则放在metadata server上

lab2需要运行三种测试，这需要进入docker环境，在chfs目录下启动docker：

1
docker start -a -i chfs

进入docker环境后，在build目录下输入以下指令来编译代码：

1
2
3
cmake ..
make -j
make build-tests -j

对于单元测试，执行以下指令：

1
make test -j

对于压力测试，执行以下指令，该测试执行速度很慢：

1
make run_concurrent_stress_test

如遇失败，使用以下指令清理残留的中间状态，防止下一次测试又失败：

1
make clean-fs

而集成测试比较麻烦，需要额外设置环境，在scripts/lab2目录下执行：

1
2
3
4
5
6
# pull cse-lab2-base image
docker pull registry.cn-shenzhen.aliyuncs.com/cse-lab/cse-lab2-base
# rename the image
docker tag registry.cn-shenzhen.aliyuncs.com/cse-lab/cse-lab2-base cse-lab2-base
# set up the environment
docker compose up

这时终端会停在某一页面，这反而说明docker compose成功，新建一个终端并执行以下命令：

1
docker exec -it lab2-fs_client-1 bash

进入docker容器后，在scripts/lab2目录下执行以下指令，如果遇到权限问题，使用chmod +x ...赋予相应文件执行权限：

1
./integration_test.sh

注意运行集成测试后，无论成功与否，都需要清理容器：

1
docker rm -f lab2-fs_client-1 lab2-data-1 lab2-meta-1

三个测试都通过后即可提交

接下来提供lab2的攻略，在lab2中，阅读头文件，使用lab1已经实现的api尤为关键。注意：本攻略未实现选做部分，即part 3

part 1: distributed filesystem

part 1A: data server

data server的操作都是以单个block为单元的，这是因为每个文件的所有block都分散在不同的data server上。因此，在这一部分，我们也只需要操作单个block即可。注意：在这一部分我们还暂时不实现版本号

阅读dataserver.h可知，我们可以使用lab1就已经实现的block_allocator_，而BlockAllocator类有成员bm，从而保证我们可以使用已经实现的块分配和块读写

首先是read_data，与BlockManager不同，这次我们不是一次读取一整个块，而是只读取其中的一部分。因此我们使用bm将整个块读取出来，再返回我们需要的那一部分

1
2
3
4
5
6
7
8
9
10
11
auto DataServer::read_data(block_id_t block_id, usize offset, usize len,
                           version_t version) -> std::vector<u8> {
  // TODO: Implement this function.
  CHFS_ASSERT(offset + len <= block_allocator_->bm->block_size(),
              "Invalid offset or length");
  std::vector<u8> buffer(block_allocator_->bm->block_size());
  auto res = block_allocator_->bm->read_block(block_id, buffer.data());
  CHFS_ASSERT(res.is_ok(), "Failed to read block");

  return std::vector<u8>(buffer.begin() + offset, buffer.begin() + offset + len);
}

而write_data相对更简单，因为在bm中已经实现了write_partial_block了，直接调用即可

1
2
3
4
5
6
7
8
9
10
auto DataServer::write_data(block_id_t block_id, usize offset,
                            std::vector<u8> &buffer) -> bool {
  // TODO: Implement this function.
  auto res = block_allocator_->bm->write_partial_block(block_id, buffer.data(), offset, buffer.size());
  if (res.is_ok()) {
    return true;
  }

  return false;
}

最后alloc_block和free_block直接调用block_allocator_的对应api即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
auto DataServer::alloc_block() -> std::pair<block_id_t, version_t> {
  // TODO: Implement this function.
  auto res = block_allocator_->allocate();
  if (res.is_ok()) {
    block_id_t block_id = res.unwrap();
    version = 0 // 仅占位
    return {block_id, version + 1};
  }

  return {};
}

auto DataServer::free_block(block_id_t block_id) -> bool {
  // TODO: Implement this function.
  auto res = block_allocator_->deallocate(block_id);
  if (res.is_ok()) {
    return true;
  }

  return false;
}

基于lab1实现这一部分很轻松，现在我们可以通过以下单元测试：

  • DataServerTest.ReadAndWrite

注意DataServerTest.AllocateAndDelete暂时通过不了，因为该测试涉及到了版本号的判断

part 1B: metadata server

这一部分要求我们实现metadata server，因此先要搞清楚metadata server的架构：

1
| Boot block | Super block | Inode Table | Inode Bitmap | Free block Bitmap | Directory blocks |

这里不必太在乎inode table与inode分离的问题，实际上metadata server的块架构与lab1的inode层架构是一致的，唯一的区别就是metadata server的data block只存放inode和directory，不会存放regular file

在lab1中经常传参InodeType，但我们并没有根据这个参数作分类讨论，现在需要用到这个了：

1
2
3
4
5
enum class InodeType : u32 {
  Unknown = 0,
  FILE = 1,
  Directory = 2,
};

可以注意到分为了FILE和Directory两种类型，其中FILE就是lab2需要额外讨论的regular file

我们先说directory，directory直接放在metadata server上，因此其inode和我们在lab1实现的并没有区别，还是多个direct block和一个indirect block，而它们存放的block id自然也是metadata server上的block id：

1
| type | FileAttr | Direct block id | Indirect block id |

而regular file与我们在lab1中的实现有很大区别，由于regular file的各个块被分散在多台data server上，因此我们不仅要维护block id，还要维护mac id和version，即using BlockInfo = std::tuple<block_id_t, mac_id_t, version_t>，其架构如下：

1
| type | FileAttr | BlockInfo(block id & mac id & version) |

这里需要再注意一下FileAttr，在lab1中框架代码已经帮我们实现了inode参数的处理，但由于现在我们需要额外实现regular file的处理函数，需要额外操作FileAttr了，至于如何操作，复用data_op.cc中read_file和write_file的框架代码即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class FileAttr {
  friend class Inode;

public:
  u64 atime = 0;
  u64 mtime = 0;
  u64 ctime = 0;
  u64 size = 0;

  auto set_mtime(u64 t) { mtime = t; }

  auto set_all_time(u64 t) {
    atime = t;
    mtime = t;
    ctime = t;
  }

} __attribute__((packed));

分析完metadata server的架构后，我们可以实现相应的代码了

首先，在正式实现metadata_server.cc中的函数之前，我们先在FileOperation类中添加以下函数，用于处理regular file的逻辑。因为MetadataServer类的函数基本都是靠调用成员std::shared_ptr<FileOperation> operation_来处理逻辑的：

1
2
3
4
5
6
auto add_block_mapping(inode_id_t id, block_id_t bid, mac_id_t mac_id, version_t version)
      -> ChfsNullResult;
auto remove_block_mapping(inode_id_t id, block_id_t bid)
      -> ChfsNullResult;
auto get_block_mapping(inode_id_t id)
      -> ChfsResult<std::vector<std::tuple<block_id_t, mac_id_t, version_t>>>;

这是因为regular file的inode与lab1实现的区别就是block id的存放逻辑，即block mapping，这需要我们在Inode类进行添加：

1
2
3
4
// 用于metadata server中的directory和regular file两种类型的inode
// 使用type进行区分
[[maybe_unused]] block_id_t blocks[0];
[[maybe_unused]] std::tuple<block_id_t, mac_id_t, version_t> blocks_map[0];

其中blocks原来就有，给directory使用即可；我们添加的是blocks_map，用于regular file（maybe_unused其实就是在暗示）

注意到我们分配的数组大小为0，这是一种柔性数组写法，当Inode buffer空间开的足够大时，我们就可以通过指针来访问数组而不越界，但缺点在于blocks和blocks_map的起始地址一样，因此建议不要为block_id, mac_id, version各开一个数组，否则会出现覆写问题

这里我们认为blocks_map数组的实际大小就是block_num，因此blocks_map不应当出现空洞才对，从而保证添加新的block时，直接追加即可，同时节约了空间，防止无限遍历（真正读写文件时并不用担心出现空洞的问题，因为不会突然释放中间的block）

现在我们回到data_op.cc中来实现这三个处理blocks_map的函数。首先是add_block_mapping，步骤为：

  • 读取inode信息，参考write_file的框架代码即可
  • 找到第一个空闲的位置，这里其实可以简化为在末尾追加即可（代码有历史残留），同时我们需要修改inner_attr中的size，这是我们判断block_num的重要依据
  • 处理一下inner_attr，写回inode所在的block，同样参考write_file即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
auto FileOperation::add_block_mapping(inode_id_t id, block_id_t bid, mac_id_t mac_id, version_t version) -> ChfsNullResult {
  // 1. 读取inode信息
  const auto block_size = this->block_manager_->block_size();
  std::vector<u8> inode(block_size);
  auto inode_p = reinterpret_cast<Inode *>(inode.data());
  auto inode_res = this->inode_manager_->read_inode(id, inode);
  if (inode_res.is_err()) {
    return ChfsNullResult(inode_res.unwrap_error());
  }
  // 注意需要判断类型
  if (inode_p->get_type() != InodeType::FILE) {
    return ChfsNullResult(ErrorType::INVALID_ARG);
  }
  // 2. 找到第一个空闲的位置，添加映射
  usize file_sz = inode_p->get_size();
  usize block_num = calculate_block_sz(file_sz, block_size);
  // 防止溢出
  if (block_num >= inode_p->max_file_sz_supported() / block_size) {
    return ChfsNullResult(ErrorType::OUT_OF_RESOURCE);
  }
  // 由于remove直接将block位置设为无效，因此这里直接找到第一个无效的位置，而不是追加到末尾（写错了懒得改了）
  usize i = 0;
  for(; i < block_num; ++i) {
    if (std::get<0>(inode_p->blocks_map[i]) == KInvalidBlockID) {
      // 找到空闲位置，添加映射
      inode_p->blocks_map[i] = std::make_tuple(bid, mac_id, version);
      break;
    }
  }
  if (i == block_num) {
    // 没有找到空闲位置，添加到末尾
    inode_p->blocks_map[block_num] = std::make_tuple(bid, mac_id, version);
  }
  inode_p->inner_attr.size += block_size;
  inode_p->inner_attr.mtime = time(0);
  // 3. 写回inode信息
  inode_p->inner_attr.set_all_time(time(0));
  auto write_res =
      this->block_manager_->write_block(inode_res.unwrap(), inode.data());
  if (write_res.is_err()) {
    return ChfsNullResult(write_res.unwrap_error());
  }
  return KNullOk;
}

而remove_block_mapping步骤类似，遍历blocks_map，找到block_id对应的条目并将其设置为KInvalidBlockID即可，但为了避免空洞问题，需要将其后面的条目前移一格，从而覆写该条目（其实还需要将遍历完后末尾的条目设置为KInvalidBlockID，但由于block_num限制了范围，保证了我们不会读取到末尾，后续add时覆写即可）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
auto FileOperation::remove_block_mapping(inode_id_t id, block_id_t bid) -> ChfsNullResult {
  // 1. 读取inode信息
  const auto block_size = this->block_manager_->block_size();
  std::vector<u8> inode(block_size);
  auto inode_p = reinterpret_cast<Inode *>(inode.data());
  auto inode_res = this->inode_manager_->read_inode(id, inode);
  if (inode_res.is_err()) {
    return ChfsNullResult(inode_res.unwrap_error());
  }
  // 注意需要判断类型
  if (inode_p->get_type() != InodeType::FILE) {
    return ChfsNullResult(ErrorType::INVALID_ARG);
  }
  // 2. 找到需要移除的block
  bool found = false;
  usize file_sz = inode_p->get_size();
  usize block_num = calculate_block_sz(file_sz, block_size);
  for (usize i = 0; i < block_num; ++i) {
    if (found){
      // 向前移动一格，覆盖被删除的block，防止inode size与数组长度不匹配，同时避免空洞
      inode_p->blocks_map[i - 1] = inode_p->blocks_map[i];
      continue;
    }

    if (std::get<0>(inode_p->blocks_map[i]) == bid) {
      // 找到后移除映射
      inode_p->blocks_map[i] = std::make_tuple(KInvalidBlockID, 0, 0);
      inode_p->inner_attr.size = (inode_p->inner_attr.size > block_size) ? (inode_p->inner_attr.size - block_size) : 0;
      inode_p->inner_attr.mtime = time(0);
      found = true;
    }
  }
  if (!found) {
    return ChfsNullResult(ErrorType::INVALID_ARG);
  }
  // 3. 写回inode信息
  inode_p->inner_attr.set_all_time(time(0));
  auto write_res =
      this->block_manager_->write_block(inode_res.unwrap(), inode.data());
  if (write_res.is_err()) {
    return ChfsNullResult(write_res.unwrap_error());
  }
  return KNullOk;

}

最后get_block_mapping省略写回inode步骤即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
auto FileOperation::get_block_mapping(inode_id_t id) -> ChfsResult<std::vector<std::tuple<block_id_t, mac_id_t, version_t>>> {
  // 1. 读取inode信息
  const auto block_size = this->block_manager_->block_size();
  std::vector<u8> inode(block_size);
  auto inode_p = reinterpret_cast<Inode *>(inode.data());
  auto inode_res = this->inode_manager_->read_inode(id, inode);
  if (inode_res.is_err()) {
    return ChfsResult<std::vector<std::tuple<block_id_t, mac_id_t, version_t>>>(inode_res.unwrap_error());
  }
  // 注意需要判断类型
  if (inode_p->get_type() != InodeType::FILE) {
    return ChfsResult<std::vector<std::tuple<block_id_t, mac_id_t, version_t>>>(ErrorType::INVALID_ARG);
  }
  // 2. 依次将映射压入到vector中
  std::vector<std::tuple<block_id_t, mac_id_t, version_t>> mappings;
  usize file_sz = inode_p->get_size();
  usize block_num = calculate_block_sz(file_sz, block_size);
  for (usize i = 0; i < block_num; ++i) {
    if (std::get<0>(inode_p->blocks_map[i]) != KInvalidBlockID) {
      mappings.emplace_back(std::get<0>(inode_p->blocks_map[i]),
                            std::get<1>(inode_p->blocks_map[i]),
                            std::get<2>(inode_p->blocks_map[i]));
    }
  }
  return ChfsResult<std::vector<std::tuple<block_id_t, mac_id_t, version_t>>>(std::move(mappings));

}

现在我们终于分析并实现完regular file中的blocks_map逻辑，可以实现metadata_server.cc中的函数了。这里面的大部分函数都直接调用operation_中的对应api即可

首先是mknode，需要我们创建一个inode，给了parent，因此调用lab1实现的operation_->mk_helper即可：

1
2
3
4
5
6
7
8
9
10
11
auto MetadataServer::mknode(u8 type, inode_id_t parent, const std::string &name)
    -> inode_id_t {
  // TODO: Implement this function.
  // 等效于调用 operation_ 的 mk_helper 方法
  auto res = operation_->mk_helper(parent, name.c_str(), static_cast<InodeType>(type));
  if (res.is_ok()) {
    return res.unwrap();
  }

  return 0;
}

关于unlink，在directory中删除文件，调用operation_->unlink即可：

1
2
3
4
5
6
7
8
9
10
11
auto MetadataServer::unlink(inode_id_t parent, const std::string &name)
    -> bool {
  // TODO: Implement this function.
  // 等效于调用 operation_ 的 unlink 方法
  auto res = operation_->unlink(parent, name.c_str());
  if (res.is_ok()) {
    return true;
  }

  return false;
}

关于lookup函数，调用operation_->lookup即可：

1
2
3
4
5
6
7
8
9
10
11
auto MetadataServer::lookup(inode_id_t parent, const std::string &name)
    -> inode_id_t {
  // TODO: Implement this function.
  // 等效于调用 operation_ 的 lookup 方法
  auto res = operation_->lookup(parent, name.c_str());
  if (res.is_ok()) {
    return res.unwrap();
  }

  return 0;
}

而allocate_block是用于regular file的，步骤为：

  • 使用metadata_server.h中的RandomNumberGenerator generator来随机选择一个data server（注释其实已经告诉你了）
  • 在data server中调用alloc_block函数，这需要用到rpc，在RpcClient中提供了call函数来帮助实现，从而得到block_id和version
  • 调用operation_->add_block_mapping来将这个新的block压入inode中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
auto MetadataServer::allocate_block(inode_id_t id) -> BlockInfo {
  // TODO: Implement this function.
  // 向data server请求分配新块
  // 随机选择一个data server
  u32 mac_id = generator.rand(1, num_data_servers);
  auto client_it = clients_[mac_id];
  // 使用rpc调用data server的alloc_block方法
  auto rpc_res = client_it->call("alloc_block");
  if(!rpc_res.is_ok()) {
    return {};
  }
  auto [block_id, version] = rpc_res.unwrap()->as<std::pair<block_id_t, version_t>>();
  // 在inode中更新这个block的信息
  auto inode_res = operation_->add_block_mapping(id, block_id, mac_id, version);
  if(!inode_res.is_ok()) {
    return {};
  }
  return std::make_tuple(block_id, mac_id, version);
}

而free_block已经提供了machine_id，依次调用client_it->call("free_block", block_id)和operation_->remove_block_mapping即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
auto MetadataServer::free_block(inode_id_t id, block_id_t block_id,
                                mac_id_t machine_id) -> bool {
  // TODO: Implement this function.
  std::lock_guard<std::mutex> lock(block_mutex);
  // 找到对应的data server移除block
  auto client_it = clients_[machine_id];
  auto rpc_res = client_it->call("free_block", block_id);
  if (!rpc_res.is_ok()) {
    return false;
  }
  // 在inode中移除这个block的信息
  auto inode_res = operation_->remove_block_mapping(id, block_id);
  if (inode_res.is_ok()) {
    return true;
  }
  return false;
}

关于readdir，使用directory_op.h中提供的read_directory帮助函数即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
auto MetadataServer::readdir(inode_id_t node)
    -> std::vector<std::pair<std::string, inode_id_t>> {
  // TODO: Implement this function.
  // 使用directory_op的read_directory方法
  std::list<DirectoryEntry> entries;
  auto res = read_directory(operation_.get(), node, entries);
  if (res.is_err()) return {};
  std::vector<std::pair<std::string, inode_id_t>> result;
  for (const auto &entry : entries) {
    result.emplace_back(entry.name, entry.id);
  }

  return result;
}

关于get_block_map，调用operation_->get_block_mapping即可：

1
2
3
4
5
6
7
8
9
10
auto MetadataServer::get_block_map(inode_id_t id) -> std::vector<BlockInfo> {
  // TODO: Implement this function.
  // 等效于调用 operation_ 的 get_block_mapping方法
  auto res = operation_->get_block_mapping(id);
  if (res.is_ok()) {
    return res.unwrap();
  }

  return {};
}

最后get_type_attr调用operation_->get_type_attr即可，这个函数不是我们自己实现的，注意两者返回的类型不一致，需要类型转换一下：

1
2
3
4
5
6
7
8
9
10
11
12
auto MetadataServer::get_type_attr(inode_id_t id)
    -> std::tuple<u64, u64, u64, u64, u8> {
  // TODO: Implement this function.
  auto res = operation_->get_type_attr(id);
  if (res.is_ok()) {
    auto [type, attr] = res.unwrap();
    return std::make_tuple(attr.size, attr.atime, attr.mtime, attr.ctime,
                           static_cast<u8>(type));
  }

  return {};
}

现在，我们可以通过以下单元测试：

  • MetadataServerTest.CreateDirThenLookup
  • MetadataServerTest.WriteAnEmptyFile
  • MetadataServerTest.CheckPersist
  • MetadataServerTest.CheckReadDir
  • MetadataServerTest.CheckUnlink

part 1C: filesystem client

part 1C.1: client implement

现在我们来实现client，大部分时间，它都是直接访问metadata server的；而读写文件时，client先在metadata server上拿到blocks_map，再根据mac_id访问各个data server拿到需要的block

在实现前需要注意的是，client都是通过rpc来访问数据的，因此错误处理其实处理的是rpc调用成功与否；而无论是metadata server还是data server，其函数返回值基本都没有被ChfsResult包装过，而是使用特殊值返回的方法来返回错误，因此需要根据这些特殊值来进行错误处理（这里的错误处理用于metadata并发导致的错误，而block并发引发的version不一致返回空值即可，以迎合测试集）

首先是mknode，直接rpc到metadata server的mknode函数即可，错误处理为返回值为0（由lab1可知，这里的inode id是logic id，因此不可能是0）：

1
2
3
4
5
6
7
8
9
10
11
12
13
auto ChfsClient::mknode(FileType type, inode_id_t parent,
                        const std::string &name) -> ChfsResult<inode_id_t> {
  // TODO: Implement this function.
  auto rpc_res = metadata_server_->call("mknode", static_cast<u8>(type), parent, name);
  if (rpc_res.is_ok()) {
    inode_id_t new_inode = rpc_res.unwrap()->as<inode_id_t>();
    if (new_inode == 0) {
      return ChfsResult<inode_id_t>(ErrorType::AlreadyExist);
    }
    return ChfsResult<inode_id_t>(new_inode);
  }
  return ChfsResult<inode_id_t>(rpc_res.unwrap_error());
}

关于unlink，直接rpc到metadata server上调用unlink函数即可，错误处理为返回值为false

1
2
3
4
5
6
7
8
9
10
11
12
auto ChfsClient::unlink(inode_id_t parent, std::string const &name)
    -> ChfsNullResult {
  // TODO: Implement this function.
  auto rpc_res = metadata_server_->call("unlink", parent, name);
  if (rpc_res.is_err()) {
    return ChfsNullResult(rpc_res.unwrap_error());
  }
  if (!rpc_res.unwrap()->as<bool>()) {
    return ChfsNullResult(ErrorType::NotExist);
  }
  return KNullOk;
}

关于lookup，通过rpc调用metadata server的lookup即可，错误处理为返回值为0，即inode id错误：

1
2
3
4
5
6
7
8
9
10
11
12
13
auto ChfsClient::lookup(inode_id_t parent, const std::string &name)
    -> ChfsResult<inode_id_t> {
  // TODO: Implement this function.
  auto rpc_res = metadata_server_->call("lookup", parent, name);
  if (rpc_res.is_ok()) {
    inode_id_t inode = rpc_res.unwrap()->as<inode_id_t>();
    if (inode == 0) {
      return ChfsResult<inode_id_t>(ErrorType::NotExist);
    }
    return ChfsResult<inode_id_t>(inode);
  }
  return ChfsResult<inode_id_t>(rpc_res.unwrap_error());
}

关于readdir，通过rpc调用metadata server的readdir即可，考虑到directory确实可能为空，不必错误处理

1
2
3
4
5
6
7
8
9
10
11
auto ChfsClient::readdir(inode_id_t id)
    -> ChfsResult<std::vector<std::pair<std::string, inode_id_t>>> {
  // TODO: Implement this function.
  auto rpc_res = metadata_server_->call("readdir", id);
  if (rpc_res.is_ok()) {
    auto entries = rpc_res.unwrap()->as<std::vector<std::pair<std::string, inode_id_t>>>();
    return ChfsResult<std::vector<std::pair<std::string, inode_id_t>>>(entries);
  }
  return ChfsResult<std::vector<std::pair<std::string, inode_id_t>>>(
      rpc_res.unwrap_error());
}

关于get_type_attr，通过rpc调用metadata server的get_type_attr即可，错误处理为tuple返回为空，因为正常情况下不可能为空，注意两者返回类型也不一致，需要类型转换：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
auto ChfsClient::get_type_attr(inode_id_t id)
    -> ChfsResult<std::pair<InodeType, FileAttr>> {
  // TODO: Implement this function.
  auto rpc_res = metadata_server_->call("get_type_attr", id);
  if (rpc_res.is_ok()) {
    auto type_attr = rpc_res.unwrap()->as<std::tuple<u64, u64, u64, u64, u8>>();
    if (type_attr == std::tuple<u64, u64, u64, u64, u8>{}) {
      return ChfsResult<std::pair<InodeType, FileAttr>>(ErrorType::NotExist);
    }
    InodeType type = static_cast<InodeType>(std::get<4>(type_attr));
    FileAttr attr;
    attr.size = std::get<0>(type_attr);
    attr.atime = std::get<1>(type_attr);
    attr.mtime = std::get<2>(type_attr);
    attr.ctime = std::get<3>(type_attr);
    return ChfsResult<std::pair<InodeType, FileAttr>>(std::make_pair(type, attr));
  }
  return ChfsResult<std::pair<InodeType, FileAttr>>(rpc_res.unwrap_error());
}

而read_file比较复杂，因为涉及到了data server的直接访问，步骤如下：

  • rpc调用metadata server的get_block_map函数，错误时返回为空，但不必错误处理，因为为空时不会进入到后面的遍历循环
  • 维护remain和cur_offset，分别判断剩余读取大小和当前块的偏移量，遍历时根据它们决定是否读取当前块，并用它们计算本次读取内容的长度
  • 遍历blocks_map，rpc到mac_id对应的data server，并调用read_data函数，这里错误处理相当于高耦合了version和client，因此反而不管最好
  • 返回result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
auto ChfsClient::read_file(inode_id_t id, usize offset, usize size)
    -> ChfsResult<std::vector<u8>> {
  // TODO: Implement this function.
  auto rpc_res = metadata_server_->call("get_block_map", id);
  if (!rpc_res.is_ok()) {
    return ChfsResult<std::vector<u8>>(ErrorType::NotExist);
  }
  auto block_map = rpc_res.unwrap()->as<std::vector<std::tuple<block_id_t, mac_id_t, version_t>>>();
  std::vector<u8> result;
  usize remain = size;
  usize cur_offset = offset;
  for (auto &[block_id, mac_id, version] : block_map) {
    if (remain == 0) break;
    if (cur_offset >= DiskBlockSize){
      cur_offset -= DiskBlockSize;
      continue;
    }
    auto cli = data_servers_[mac_id];
    usize to_read = std::min(remain, DiskBlockSize - cur_offset);
    auto data_res = cli->call("read_data", block_id, cur_offset, to_read, version);
    if(!data_res.is_ok()) {
      return ChfsResult<std::vector<u8>>(ErrorType::BadResponse);
    }
    auto data = data_res.unwrap()->as<std::vector<u8>>();
    result.insert(result.end(), data.begin(), data.end());
    remain -= to_read;
    cur_offset = 0;
  }
  return ChfsResult<std::vector<u8>>(result);
}

而write_file的步骤为：

  • rpc调用metadata server的get_block_map函数，错误时返回为空，但不必错误处理，因为为空时不会进入到后面的遍历循环
  • 维护remain和cur_offset，分别判断剩余写入大小和当前块的偏移量，遍历时根据它们决定是否写入，并用它们计算本次读取内容的长度；同时将blocks_map维护成一个队列
  • 进入循环时先判断是否需要分配一个新的block，rpc调用metadata server的allocate_block函数（注意rpc的名字映射为alloc_block，这是唯一的不同名），分配失败时返回值为空，需要错误处理，成功则入队
  • blocks_map出队并rpc调用data server的write_data函数（这里也该错误处理，但写漏了）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
auto ChfsClient::write_file(inode_id_t id, usize offset, std::vector<u8> data)
    -> ChfsNullResult {
  // TODO: Implement this function.
  auto rpc_res = metadata_server_->call("get_block_map", id);
  if (!rpc_res.is_ok()) {
    return ChfsNullResult(rpc_res.unwrap_error());
  }
  auto block_map = rpc_res.unwrap()->as<std::vector<std::tuple<block_id_t, mac_id_t, version_t>>>();
  usize remain = data.size();
  usize cur_offset = offset;
  usize data_pos = 0;
  while(remain > 0){
    // 先判断是否需要分配一个新的块
    if (block_map.empty()){
      auto new_block_res = metadata_server_->call("alloc_block", id);
      if (!new_block_res.is_ok()) {
        return ChfsNullResult(new_block_res.unwrap_error());
      }
      if (new_block_res.unwrap()->as<std::tuple<block_id_t, mac_id_t, version_t>>() == std::tuple<block_id_t, mac_id_t, version_t>{}) {
        return ChfsNullResult(ErrorType::OUT_OF_RESOURCE);
      }
      auto [new_block_id, mac_id, version] = new_block_res.unwrap()->as<std::tuple<block_id_t, mac_id_t, version_t>>();
      block_map.push_back(std::make_tuple(new_block_id, mac_id, version));
    }
    // 出队
    auto &[block_id, mac_id, version] = block_map.front();
    block_map.erase(block_map.begin());
    if (cur_offset >= DiskBlockSize){
      cur_offset -= DiskBlockSize;
      continue;
    }
    auto cli = data_servers_[mac_id];
    usize to_write = std::min(remain, DiskBlockSize - cur_offset);
    std::vector<u8> write_data(data.begin() + data_pos, data.begin() + data_pos + to_write);
    auto write_res = cli->call("write_data", block_id, cur_offset, write_data);
    if (!write_res.is_ok()) {
      return ChfsNullResult(write_res.unwrap_error());
    }
    remain -= to_write;
    data_pos += to_write;
    cur_offset = 0;
  }
  return KNullOk;
}

最后free_file_block通过rpc调用metadata server上的free_block函数，根据返回值是否为false来进行错误处理

1
2
3
4
5
6
7
8
9
10
11
12
auto ChfsClient::free_file_block(inode_id_t id, block_id_t block_id,
                                 mac_id_t mac_id) -> ChfsNullResult {
  // TODO: Implement this function.
  auto rpc_res = metadata_server_->call("free_block", id, block_id, mac_id);
  if (rpc_res.is_err()) {
    return ChfsNullResult(rpc_res.unwrap_error());
  }
  if (!rpc_res.unwrap()->as<bool>()) {
    return ChfsNullResult(ErrorType::INVALID);
  }
  return KNullOk;
}
part 1C.2: version implement

为了保证block操作的before-or-after原子性，需要为每个block引入version，这些version被存放在data server的开头，架构如下：

1
| version blocks | free block bitmap | file data blocks |

这里我们回到BlockAllocator的构造函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 *  Creates a new block allocator with a block manager and a bitmap block id.
 *
 * @param bm the block manager
 * @param bitmap_block_id the block id of the bitmap
 * @param will_initialize whether to initialize the bitmap
 *
 * # Note!!!!
 * We assume that the blocks before the `bitmap_block_id` is reserved,
 * so they cannot be allocated.
 */
BlockAllocator(std::shared_ptr<BlockManager> bm, usize bitmap_block_id,
               bool will_initialize = true);

可以注意到这里指定了bitmap_block_id前的块不能被分配出去，正好可以用来存放version block，我们只需要计算version block num，并在未initialized的情况下清空这一部分即可。因此DataServer::initialize修改如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 使用最前面不会被分配出去的块来实现version blocks
constexpr usize version_block_cnt = (KDefaultBlockCnt * sizeof(version_t) + DiskBlockSize - 1) / DiskBlockSize;

auto bm = std::shared_ptr<BlockManager>(
    new BlockManager(data_path, KDefaultBlockCnt));
if (is_initialized) {
  block_allocator_ =
      std::make_shared<BlockAllocator>(bm, version_block_cnt, false);
} else {
  // We need to reserve some blocks for storing the version of each block
  // 这里需要初始化一下version blocks
  std::vector<u8> zero_block_data(bm->block_size(), 0);
  for (usize i = 0; i < version_block_cnt; ++i) {
    auto write_res =
        bm->write_block(i, zero_block_data.data());
    CHFS_ASSERT(write_res.is_ok(), "Failed to initialize version blocks");
  }
  block_allocator_ = std::shared_ptr<BlockAllocator>(
      new BlockAllocator(bm, version_block_cnt, true));
}

version在每次分配和释放块时，都加一；而在read block时，如果不匹配，返回空值（这是为了迎合测试集）

因此在DataServer::read_data添加以下代码：

1
2
3
4
5
6
// 检查版本号是否匹配
version_t current_version = get_block_version(block_id);
if (current_version != version) {
    // 版本不匹配，拒绝访问
    return {};
}

在alloc_block和free_block添加以下代码：

1
2
3
// 更新版本号
version_t version = get_block_version(block_id);
set_block_version(block_id, version + 1);

注意alloc_block要返回更新之后的版本号即可

现在我们需要额外自行实现get_block_version和set_block_version函数，计算好version block id和offset，然后进行对应block的操作即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
auto DataServer::get_block_version(block_id_t block_id) -> version_t {
  usize block_size = block_allocator_->bm->block_size();
  usize versions_per_block = block_size / sizeof(version_t);
  usize version_block_index = block_id / versions_per_block;
  usize offset_in_block = (block_id % versions_per_block) * sizeof(version_t);
  std::vector<u8> buffer(block_size);
  auto res = block_allocator_->bm->read_block(version_block_index, buffer.data());
  CHFS_ASSERT(res.is_ok(), "Failed to read version block");
  version_t version;
  memcpy(&version, buffer.data() + offset_in_block, sizeof(version_t));
  return version;
}

auto DataServer::set_block_version(block_id_t block_id, version_t version) -> void {
  usize block_size = block_allocator_->bm->block_size();
  usize versions_per_block = block_size / sizeof(version_t);
  usize version_block_index = block_id / versions_per_block;
  usize offset_in_block = (block_id % versions_per_block) * sizeof(version_t);
  std::vector<u8> buffer(block_size);
  auto res = block_allocator_->bm->read_block(version_block_index, buffer.data());
  CHFS_ASSERT(res.is_ok(), "Failed to read version block");
  memcpy(buffer.data() + offset_in_block, &version, sizeof(version_t));
  auto write_res = block_allocator_->bm->write_block(version_block_index, buffer.data());
  CHFS_ASSERT(write_res.is_ok(), "Failed to write version block");
}

现在，我们可以通过以下测试：

  • DataServerTest.AllocateAndDelete
  • DistributedClientTest.WriteAndThenRead
  • MetadataServerTest.ReadWhenBlockIsInvalid

part 2: support concurrency

之前我们通过version解决了block分配与释放导致的原子性问题，现在，我们还需要保证metadata的原子性。我们只需要给metadata_server.cc的以下函数上锁即可，因为它们并不是只读操作：

  • mknode
  • unlink
  • allocate_block
  • free_block

在它们开头添加std::lock_guard<std::mutex> lock(metadata_mutex);即可

现在可以通过以下单元测试了：

  • DistributedClientTest.CreateConcurrent
  • DistributedClientTest.ReCreateWhenDelete
  • MetadataServerTest.CheckInvariant1
  • MetadataServerTest.CheckInvariant2
  • MetadataServerTest.CheckInvariant3
  • MetadataServerTest.CheckInvariant4

最后运行一下压力测试和集成测试即可

总结一下这个lab，由于part 3变为选做部分，难度下降了很多，注意chfs的耦合度较高即可

计算机学习 > se专业课 > cse > lab
#se #cse
CSE_lab2攻略
http://example.com/2025/10/25/CSE-lab2攻略/
作者
jietiDdd
发布于
2025年10月25日
许可协议