minikv 重构项目 · 任务 8 / 8

m08:先测量,再改关键路径

对应第 18 章(代码应该一目了然)、第 20 章(为性能而设计)

背景与对应章节

一次纯内存的 GET 要 1.2 微秒。时间花在哪了?你的第一个猜测对吗?

minikv 的 GET 路径看上去没什么复杂的:切分命令、查哈希表、把值加上引号返回。但 make bench 说一次命中要 1.2 µs 左右——对一次哈希查找来说太多了。同一条路径上还有几处读起来"不对劲"的代码:返回 std::pair 的查询、两个 bool 参数的格式化函数、一个会偷偷改统计的 exists()。

这个任务把第 18 章和第 20 章放在一起练:让代码一目了然和让关键路径变快往往是同一件事,但前提是你先量出时间真正花在哪。做之前请读 第 18 章 · 代码应该一目了然(尤其 18.2 节关于通用容器和违背预期的代码)和 第 20 章 · 为性能而设计(20.2 先测量、20.3 围绕关键路径设计、20.4 的完整例子)。

你要找的问题

分两部分。先读代码,找出"读的人第一眼会猜错"的地方:

位置读的时候问自己
Store::get()、Database::get()调用处写 r.first、r.second,不看声明你知道哪个是什么吗?这次调用一共拷贝了几次值?
Server::bulk() 的所有调用bulk(x, true, true) 和 bulk(x, false, false) 分别做了什么?后者有必要存在吗?
Store::exists()一个叫 exists 的函数会修改什么?执行 SET a 1、GET a、STATS,看 keyspace_hits 是几。
Server::handleGet()一次 GET 查了几次哈希表?
src/stats.h每条命令都会用字符串名字去 std::map 里找计数器。如果有人把名字拼错,会发生什么?

然后是性能。在读完代码、动手测量之前,先把你的猜测写下来:GET 命中的 1.2 µs 里,下面几项各占多少?按从大到小排个序。

先跑基准、复现统计的问题:

cd project/minikv
make bench
make && printf 'SET a 1\nGET a\nSTATS\n' | ./minikv /tmp/m08-demo.log; rm -f /tmp/m08-demo.log

任务与约束

  1. 先测量。把 GET 命中路径拆成几段,分别计时,得到一张"每段多少纳秒"的表,再和你的猜测对照。
  2. 改掉不明显的代码:pair 返回值、bool 参数、exists() 的副作用。改完后每次 GET 只记一次命中或未命中。
  3. 围绕关键路径重新设计 GET:先想清楚"一次 GET 最少必须做什么",再让代码尽量接近它。
  4. 每改一处就重新测一次。没有可测量收益、也没让代码更简单的改动,撤回。
  5. 在笔记里记下改前改后的 make bench 数字(多跑几次取中位数)。

约束:

自查清单

提示

提示 1:没有 perf 怎么测

WSL 和很多容器里没有 perf。最朴素的办法往往就够用:把项目复制到临时目录,写一个小程序,用 std::chrono::steady_clock 把每一段单独跑 100 万次计时(多跑几轮取最好或中位数)。要调用私有成员,可以在这个一次性的测量程序里先 #define private public 再 include 头文件——它只是测量脚手架,不要进代码库。也可以反过来做:在副本里临时把某一段换成最简单的实现,看总时间掉了多少。

提示 2:微基准也会骗人

单独测"查哈希表"可能只有 100 ns 左右,放进完整路径里却贵得多。原因是缓存:10 万个键加上值,数据量超过了 L3,随机查找要沿着"桶 → 节点 → 值"连续跳几次内存。单独循环查找时,CPU 能把相邻几次查找的内存访问重叠起来,所以看起来便宜。所以最后一定要用完整路径(make bench)验证,各段加起来对不上总时间时,别急着下结论。

提示 3:理想的 GET 长什么样

第 20.3 节的做法是先想象"最少需要做什么":找到键、找不到就回 (nil)、找到就把值加上引号拼进回复里——一次查找、零次拷贝、一次分配。把它和现在的代码逐行对比,多出来的每一步都要有理由。格式化那一步,大多数值根本不含需要转义的字符,常见情况能不能一次 append 整段?

参考答案与讨论

先自己测、自己改、测试全绿,再打开下面的内容。你的数字一定和这里不同(机器不同),要比的是相对变化和你找到的瓶颈是不是同一个。

打开参考答案

测量:时间到底去哪了

在基线的副本里单独计时关键路径的每一段(每段 100 万次,5 轮取最好):

环节ns / 次
完整的 Server::handle("GET key:N")1130
切分命令 + 转大写 + 查处理函数表70
db_.exists(key):一次查找 + 一次字符串名字的计数132
db_.get(key):查找 + optional 拷贝 + pair 拷贝311
 其中只查不拷(Index::find)87
 Stats::add("keyspace_hits") 一次11
bulk(value, true, true):ostringstream 逐字符输出 100 字节665
 同样的转义,手写拼接(不调用 isprint)77
Database::get() 与 Store::get() 对比(透传层开销)311 vs 318

一半以上的时间在格式化回复上,比最可疑的"两次查找、两次拷贝"加起来还多。透传层在 -O2 下被内联,测不出任何开销:它们是 m03 的设计问题,不是性能问题,所以 m08 不动它们。

改动,以及每一步的收益

std::string Server::handleGet() {
    ...
        if (!db_.exists(key)) return "(nil)";   // lookup #1, counts a hit
        auto r = db_.get(key);                  // lookup #2, counts again
        return bulk(r.second, true, true);      // what do true, true mean?
    ...
}

std::pair<bool, std::string> Store::get(const std::string& key) const {
    std::optional<std::string> v = index_.get(key);       // copy #1
    stats_.add(v ? "keyspace_hits" : "keyspace_misses");
    if (!v) return {false, ""};
    return {true, *v};                                      // copy #2
}
std::string Server::handleGet() {
    ...
        const std::string* value = db_.find(key);
        return value ? quoted(*value) : "(nil)";
    ...
}

// Returns a pointer to the value stored under `key`, or nullptr if there
// is none. The pointer is valid only until the next write to this Store
// (set, del, incr, append, compact); copy the value to keep it longer.
// Each call counts as one keyspace hit or miss in STATS.
const std::string* Store::find(const std::string& key) const;

// Whether `key` has a value. Unlike find(), not counted in STATS.
bool Store::exists(const std::string& key) const;
// Formats s for a reply.
std::string Server::bulk(const std::string& s, bool quote, bool escape) const {
    std::ostringstream out;
    if (quote) out << '"';
    for (char c : s) {
        unsigned char u = static_cast<unsigned char>(c);
        if (escape && (c == '"' || c == '\\')) {
            out << '\\' << c;
        } else if (escape && !std::isprint(u)) {
            out << "\\x" << std::hex << std::setw(2) ...;
        } else {
            out << c;
        }
    }
    ...
}
return bulk(db_.stats(), false, false);   // just a copy, in disguise
// True for bytes that cannot appear as-is inside a quoted reply. Printable
// ASCII is 0x20..0x7E; we test the range directly instead of calling
// std::isprint() per byte, which showed up in the GET benchmark.
bool needsEscape(unsigned char c);

// Appends `s` to `out` as a double-quoted reply string ... Runs of bytes
// that need no escaping (normally the whole value) are copied in one go.
void appendQuoted(std::string& out, const std::string& s);
std::string quoted(const std::string& s);

return db_.stats();

另外,Stats 从 std::map<std::string, uint64_t> 换成了 4 个普通字段的结构体:拼错名字从"运行时悄悄多出一个空计数器"变成编译错误。

逐步测量的结果(make bench,绑定同一个 CPU 核,与基线交替运行):

  • 只改格式化:1216 → 约 540 ns。手写版本一开始逐字符调 std::isprint() 再 out += c,单独测要 230 ns;改成直接判断字节范围、不需要转义的整段一次 append,降到约 75 ns(都含一次内存分配)。
  • 再改一次查找、去掉拷贝、普通字段计数器:约 535 → 约 490 ns,大约 8%,和噪声同一量级。按第 20.2 节,这样的改动本该撤回;我们保留,是因为它们同时修掉了第 18 章的问题,代码更简单了。这一点要老实说:它们是为了可读性,不是为了速度。

结果

机器:AMD Ryzen 7 8745H(16 个逻辑核),WSL2(Linux 6.6),g++ 14.2,-O2。基线和 m08 各跑 5 次、交替进行,取中位数;测量时机器上还有别的编译任务,单次波动约 ±5%。你的数字会不同。

ns / 命令基线m08变化
GET(命中)1216503快 2.4 倍
GET(未命中)305314无变化:未命中本来就不格式化值
SET32423307无变化:主要是 write(2) 和摊下来的压缩

剩下的约 490 ns 主要是哈希表的访存:数据超过 L3,每次随机查找要连跳几次内存。再往下就是第 20.3 节说的根本性改动(换成开放寻址、把短值内联进表里),要多写一大块代码。我们停在这里,理由来自另一次测量:用管道给 ./minikv 喂 100 万条 GET,每条从约 1.77 µs 降到约 1.07 µs,而后者里大约 0.6 µs 是 getline 和 cout。终端 I/O 已经和命令本身一样贵了,继续压 GET 的收益越来越小。

代价与取舍

返回 const std::string* 省掉了拷贝,但调用者必须知道"下一次写之后它可能失效"。这正是第 18 章说的需要用注释补偿的不明显之处,所以写进了接口注释。替代方案各有代价:std::optional<std::string> 安全但每次多一次拷贝;std::string_view 有同样的生命周期问题,还表达不了"不存在";withValue(key, callback) 最安全,但调用处最别扭。对一个单线程、只有一个调用者的接口,指针 + 注释是合理的折中。

把计数挪到 handleGet(),find() 就成了纯查询;但"命中率"的定义会散到命令层。参考答案留在 find() 里并写进注释。副作用本身不是罪过,出人意料的副作用才是:叫 exists 的函数改统计会让人猜错,叫 find 且注释写明会计数的函数不会。

第 20.1 节说浅层的多次调用有开销。这在跨模块、虚函数、跨进程时是真的;但在这里,-O2 把透传层内联掉了,测不出差别。如果你在 m08 里顺手删掉 Database 层并把提速归功于它,那就是没有测量支撑的结论。

行为变化(测试未改动,全部通过)

  • STATS 的 keyspace_hits/keyspace_misses 每次 GET 只记一次,EXISTS 不再计入。
  • STATS 总是输出全部 4 个计数器(值为 0 也输出),顺序不变。

审稿人仍会指出的问题

  • Database::find() 仍是纯透传,exists() 和 find() 两个查询接口并存:见 m03。
  • 命令切分、toUpper 拷贝、std::map 处理函数表还有几十纳秒可省,但 m05 会重写这部分。
  • SET 的成本几乎全在每条命令一次 write(2) 上。根本办法是批量提交(group commit),但它改变持久性语义,得先想清楚。

完整的讨论(包括测量方法)在 solutions/m08/DISCUSSION.md。对照自己的改动:

cd project            # 仓库里 minikv/ 和 solutions/ 所在的目录
make -C minikv clean && make -C solutions/m08 clean
diff -ru minikv solutions/m08
make -C solutions/m08 test bench