本文章主要记录一下我做 CMU 15-445 Project #0 Copy-on-Write Trie (2023 Fall) 以及 HyperLogLog (2024 Fall) 的经历。

去年本就该完成的 CMU 15-445，但是去年 Homework #1 SQL 和 Project #0 都花费了较多时间。 后来去实习了，就搁置了这门课。

去年年底还做了 CSAPP 的 lab0 和 lab1，其中 lab1 简直难度爆炸 🤯 以至于我只做了 5 题就停止了。 lab2 bomb 更是看不懂一点。 我的 CSAPP 仓库 在这里。

相比之下，今年的 Homework #1 SQL 就只有 5 题，关系结构也很简单，两小时就能做完。

自从上次做完 CS144 之后，接近一年没写 C++ 了，Project #0 就当复健了。 每年 Project #0 的题目都挺有意思的，这次也是抱着好奇心做的。

Last but certainly not least, 向这门课表达开源的敬意，在本文章以及后续的 CMU 15-445 系列文章中，我不会公开任何解法。

调试配置

工具链依旧用的是我最喜欢的 llvm+clang+clangd。 IDE 是 vscode，插件 codelldb 和 clangd。

settings.json 配置：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

{
  "clangd.path": "clangd-18",
  // https://github.com/microsoft/vscode-cmake-tools/issues/139
  "cmake.debugConfig": {
    "type": "lldb",
    "request": "launch",
    "program": "${command:cmake.launchTargetPath}",
    "args": [],
    "cwd": "${workspaceFolder}"
  }
}

然后在 Cmake 插件栏选择 Configure 配置编译器和编译模式，测试的时候选择对应的 build / debug target 即可。

不过有个问题，断点时，有的项目如 HyperLogLog 可以正常查看 STL 容器，但是有的项目如 Buffer Pool Manager 就没法正常查看。 看 cmake 里写的 compile option 似乎也是通用的，可能是配置问题或者 codelldb 插件问题。

看不到容器内容的时候调试起来就很痛苦，但是没法解决这个问题，只能搁置了。 感觉有可能是某个模板没有编译进去…只能说 C++ 模板就这样了。 记录一下可能相关的 issue: 1

Copy-On-Write Trie

去年写的了，当时也没记什么笔记，下面是根据代码提交回忆的。

首先是编译问题，需要跳转到 third_party/backward-cpp/backward.hpp 将 move 改为 std::move。 不过这个问题只在 2023 的项目里出现，在 2024 里没有这个问题。

项目要求实现一个 Copy-on-Write (CoW) 前缀树。 它的基本原理就是在写入时将需要修改的节点复制一份，并且不影响原来节点的使用，来实现高效并发的数据结构。 这个方法在操作系统、ZFS 等地方比较常用。

具体来讲。

Put 时，首先会创建新的根节点，并依次创建新节点到需要更新的节点。

Remove 时，搜索到需要删除的节点，进行删除，然后依次向上回溯，判断每个途径节点是否为空并且没有其他子节点，进行删除。

修改后再将旧的根节点替换为新的根节点，这一步是原子的，所以很安全。

最后再实现一些锁和 sql string function 就完成了。

讲义里可能讲的有点玄乎，但实际做起来很简单，这里就不过多讲解了。

HyperLogLog

HyperLogLog (HLL) 是一个基于概率模型的数据基数估计算法，常用于网站唯一访客量计算等场景。Redis 就有对它的支持。

在百亿级别的访问量下，哈希表的维护会引发内存不足、效率低等问题。 HLL 则不直接储存哈希值，而是通过命中概率来反向估计基数，只需要消耗十几个 KB 的内存。

HLL 的原理就不赘述了，这里就说说我的理解。 举个例子来说，抛 1 次骰子，它为 1 的概率是 1/6，但是抛 6 次，它出现 1 的期望概率就是 100%。 那么反向就可以推导出，我们看到一个骰子点数为 1，那么它很有可能被抛了 6 次，就算不是 6 次，也会在其上下波动。 而抛出次数越多，那么概率估计就无限接近于正确值。 HLL 做的就是这么一件事，它保存的不是每次抛骰子的点数，而是记录某个点数出现了多少次。 只不过它是基于实际场景的哈希分布进行设计的。

该项目的任务就是实现两种 HyperLogLog 模型，两个都比较简单，下面只讲讲我遇到的一些麻烦。

Task #1

Task #1 实现一个普通的基于 leftmost 的 HLL。

这里我写好了后断点才发现 bitset 是以小端序读取数据的，导致重写。 此外还有 -1 * ulong 导致溢出的问题，需要注意一下。

不清楚它这里使用 bitset 的意义何在。 leftmost 是从左计算，但是用 bitset 转小端序后又变成逆序…看起来就很别扭。

另外，前导零计算其实在 c++20 里面实现了 std::countl_zero，不过课程用的是 c++17.

Task #2

Task #2 实现一个基于 rightmost 和 dense 结构的 HLL。

这一题就略难点。

主要是有些细节没有讲清楚，比如：

1. ComputeCardinality 怎么运用 overflow 的值。
2. dense 和 overflow 设置的规则是什么（比如说非 0 才设置，或者 max 规则）

那么没办法，只能去看测试用例。

通过观察 PrestoCase2 这个测试用例可以推理出 dense / overflow 似乎都是无条件覆盖的。 并且基数值特别大，可以推理出在计算 sum 时需要把 overflow 和 dense 进行拼接。 ComputeCardinality 到这里就完成了。

再观察 PrestoCase1 测试用例可以发现，obj.AddElem(-1); 的前后基数没有变。 断点调试一下，就可以推理出一个比较完整的 overflow / dense 的设置规则：

1. dense 不为空，设置 dense
2. overflow 不为空，同时设置 overflow 和 dense

…这下彻底拥抱 TDD 了 🤣

提交

Project #0 本身比较简单，但是写了接近两天，有点烦，不过能 AC 至少我不会被 asked to withdraw from the course…😪

最后在提交的时候发现了 clang-tidy 的问题，照常理来说 vscode clangd 应该是自动对整个项目运行 clang-tidy 的。

项目没有提供自定义 clang-tidy binary path 选项，那我们就先跑一下它提供的 make check-clang-tidy-p0，报错 Unable to run clang-tidy.，这个在预期之内，因为我们用的是 clang-tidy-18。

根据报错提示去到 CMakeFiles/check-clang-tidy-p0.dir/build.make:76 改一下 binary 为自定义安装的 clang-tidy-18 再跑一下就可以发现问题：

1
2
3
4

/home/iyume/workspace/CMU-15-445/.clang-tidy:65:1: error: unknown key 'AnalyzeTemporaryDtors'
AnalyzeTemporaryDtors: true
^~~~~~~~~~~~~~~~~~~~~
Error parsing /home/iyume/workspace/CMU-15-445/.clang-tidy: Invalid argument

把 .clang-tidy 中 AnalyzeTemporaryDtors: true 这一行删掉就能使用 clang-tidy-18 了。 直接跑会有配置项报错，不过还是可以跑起来的。所以估计是 vscode clangd 插件没有对这个情况做判断，直接挂了。