一道有现实意义的代码笔试题

我面试候选人时, 不太喜欢从 leetcode/leetgpu 上找题目. 倒不是觉得算法题没价值, 而是这类题目有题库, 有攻略, 有标准答案; 候选人在上面的表现, 更多反映的是刷题投入度, 而不是工程判断力. 何况它们和岗位日常也确实错位得厉害: 工作里真正难缠的往往是并发、生命周期、时钟这些脏活, 而不是在 30 分钟内默写出一个红黑树.

所以我更习惯的做法是: 从线上/实际项目开发中遇到的问题里挑一个, 把业务背景抽象掉, 拿来当笔试题. 这类题目没法背, 因为它可能上个月才刚在我们的线上环境里发生; 它天然有梯度, 候选人能做到哪一层, 和入职之后能独立承担哪类工作基本对得上; 顺带还有一个好处, 候选人做题的过程, 也是在预览这个岗位每天面对的问题长什么样. 最近我最常用的一道, 就是 release lease 的实现. 它来自我们线上分布式缓存 (Mooncake) 的一次真实迭代, 来龙去脉我在 RL 下 Mooncake Store 演进分析里讲过; 不过这篇文章不要求你了解 Mooncake, 下面会把背景完全抽象掉.

背景: 回收器被 lease 卡死了

想一个很常见的系统设定: 一个缓存节点管理着一大堆内存对象. 读路径是 zero-copy 风格的: 调用方先向节点查询, 拿到对象所在的内存位置, 然后自己直接去读这块内存 (比如通过 RDMA). 也就是说, 从“节点返回位置”到“调用方读完”, 中间隔着一段节点感知不到的时间窗口. 为了保证这段时间里对象不被回收, 节点在返回位置的同时会授予一段 lease: 承诺在 lease 过期之前, 这块内存一定有效. 对象上的 lease 状态非常简单, 就一个时间戳:

# 每个对象一份
atomic<timestamp> lease_timeout          # 初值 0

GrantLease(ttl):                         # 读路径查询时调用
  lease_timeout = max(lease_timeout, now() + ttl)

CanEvict():                              # 回收器调用, 无锁读
  return now() >= lease_timeout

多个并发读者被一个 max 折叠进同一个时间戳, 每对象常数内存, 回收器一次原子 load 就能判断. 这个设计本身没什么毛病. 问题出在参数和负载上. 我们线上 lease TTL 是 30s, 而一次读取毫秒级就结束了, 但它留下的 lease 还要继续挂将近 30s. 在内存特别紧张、必须大量驱逐对象的节点上, 某次线上观测的数据是:

回收器的候选扫描跑了大约 1046 万次, 真正扫出可回收对象的只有 4911 次, 占比 0.047%;
空转原因里, 98.3% 是“对象 lease 还没过期”;
每轮空扫时, 距离最早一个 lease 过期还要等 p50 ≈ 17.0s, p90 ≈ 26.4s, p99 ≈ 28.8s, 而 TTL 本身就是 30s.

翻译一下: 读者们早就读完走人了, 但回收器还在对着一堆“其实已经没人在读”的对象反复空扫. 修复方向也很自然: 读者读完之后主动释放 lease. 麻烦在于, 主动释放和上面这个 max 折叠的设计是冲突的: lease_timeout 里只有一个时间戳, 并发读者被折叠之后, 你根本不知道现在还有几个人持有 lease. 读者 A 读完想释放, 直接把 lease_timeout 清零肯定不行, 因为读者 B 可能还在读. 这就是这道笔试题的全部来源.

题目

在上面的设定下, 为对象增加主动释放 lease 的能力, 实现 GrantLease 和 ReleaseLease 两个函数, 满足:

接口: GrantLease(ttl) -> token, 授予一段 ttl 的 lease, 可以返回一个 token 给调用方, token 内容自定; ReleaseLease(token), 调用方读取结束后 (无论成败) 调用, 带回 grant 时拿到的 token.
语义: 当所有并发持有者都释放之后, 对象要立刻能被回收器看见 (CanEvict() 为真), 不必等 TTL 自然过期.
hint 语义: ReleaseLease 只是性能优化. 调用方可能崩溃, 可能超时, 可能是不认识这个接口的旧版本客户端, 总之可能永远不调用; 这种情况下对象最迟在 TTL 过期后仍然要能被回收. 换句话说, 不允许把主动释放做成正确性的前提.
隔离性: 绝不允许提前终止其他并发持有者的 lease. 只要还有人处在自己的 lease 有效期内且没有释放, CanEvict() 就不能为真.
复杂度: 每对象附加状态 O(1), grant/release 锁内操作 O(1). 不允许为每个持有者单独记一条状态: 对象可能是千万级的, 热点对象可能同时被成百上千个读者持有.
环境: 时间用的是 system_clock, 可能回退; 并且调用方从读取时钟到真正拿到对象锁之间, 可能被阻塞任意久. (P.S. 其实我是想用 steady_clock, 奈何社区 Mooncake 为了支持 snapshot/restore 把所有 steady_clock 换成了 system_clock =。=)
回收器: 仍然通过无锁读一个原子时间戳来判断, 不允许让回收器去抢对象锁.

要求给出状态定义、状态不变量、两个函数的伪代码, 以及边界情况的讨论.

参考实现

先给状态. 相比原来只有一个 lease_timeout, 增加一条水位线和一个计数:

mutex             lease_mutex    # 对象级小锁
timestamp         lease_now      # 水位线, 锁内读写
uint64            lease_cnt      # 当前窗口内尚未 release 的持有者数, 锁内读写
atomic<timestamp> lease_timeout  # 硬判定, 写入都在锁内; 回收器仍然无锁读它

CanEvict() 一行都不用改. 然后是不变量, 这是这套设计的灵魂, 伪代码只是照着不变量抄:

lease_cnt 表示: 恰好有 lease_cnt 个调用者, 持有落在 (lease_now, lease_timeout] 窗口内的 lease, 且尚未调用 ReleaseLease.
lease_now <= lease_timeout; 若两者相等, 则 lease_cnt 一定为 0, 即无人持有 lease.
lease_now 只增不减.

        lease_now (水位线)                                  lease_timeout
──────────────┼──────────────────────────────────────────────────┼──────────→ 时间
  token 落在水位线之下:            当前窗口: lease_cnt 个持有者,
  旧窗口迟到者, release 一律 noop  token 落在 (lease_now, lease_timeout] 内

token 就用 grant 时算出的过期时间戳本身, 即 now + ttl. 注意它不是持有者的身份标识, 两个并发读者完全可能拿到相同的 token; 它唯一的用途是和水位线比大小.

GrantLease(ttl):
  now = clock()                     # 锁外先读时钟
  new_lease = now + ttl             # 这就是返回给调用方的 token
  lock(lease_mutex):
    if new_lease <= lease_now:      # (G1) 出生即过期
      return new_lease
    if now >= lease_timeout:        # (G2) 旧窗口已整体自然过期, 开新窗口
      lease_now = now
      lease_timeout = new_lease
      lease_cnt = 1
      return new_lease
    lease_timeout = max(lease_timeout, new_lease)   # (G3) 续在当前窗口上
    lease_cnt += 1
    return new_lease

逐条分支说:

(G3) 是主干: 窗口还活着, 就把窗口右沿 max 上去, 计数加一. 并发读者仍然像原来一样折叠进同一个窗口, 只是现在多了一个计数, 知道有几个人在里面.

(G2) 是开新窗口: 旧窗口在真实时间上已经整体过期. 注意这时旧窗口里可能还残留着 lease_cnt > 0, 也就是那些拿了 lease 但一直没 release 的调用者 (崩溃了, 或者压根不打算调). 我们不需要等他们: 把水位线直接抬到 now, 他们手里的 token 全都 <= 旧 lease_timeout <= now = 新 lease_now, 也就是全部沉到了水位线之下, 之后他们迟到的 release 会被 (R2) 挡住. 一次赋值就把整个旧窗口的烂账一笔勾销, 这是水位线这个设计最舒服的地方.

(G1) 处理的是一个很阴间的边界: 从锁外读时钟到真正拿到锁之间, 调用方可能被阻塞任意久 (题目条件 6). 如果这段时间超过了 ttl, 别的线程可能已经把 lease_now 推过了 new_lease. 这种 token 绝对不能计入 lease_cnt: 它已经在水位线之下, 对应的 release 会被 (R2) 无视, 计入了就是一笔永远还不上的 +1, 在窗口自然过期被整体重置之前, lease_cnt 再也回不到 0, 主动释放在这个对象上直接失效. 所以这里不碰任何状态, 原样返回一个“出生即过期”的 token 就好: 查询本身不报错, 调用方后续拿着这个 token 准备读数据时, 第一步的过期校验就会失败, 走已有的失败重试路径. 这个分支在 TTL 30s 的线上大概率一辈子都走不到, 但它必须存在; 候选人能不能自己发现它, 区分度很高.

ReleaseLease(token):
  now = clock()
  lock(lease_mutex):
    if now >= lease_timeout:        # (R1) 整个窗口已自然过期, 顺手重置
      lease_now = now
      lease_timeout = now
      lease_cnt = 0
      return
    if token <= lease_now:          # (R2) 水位线之下: 旧窗口迟到者
      return
    assert token <= lease_timeout
    assert lease_cnt > 0
    lease_cnt -= 1
    if lease_cnt == 0:              # (R3) 最后一人离场, 窗口塌缩
      lease_now = max(lease_now, now)
      lease_timeout = lease_now

(R3) 是这道题的目的所在: 最后一个持有者离场时, 把 lease_timeout 拉回到水位线上. 由不变量 2, 这个状态就是“无人持有”, 回收器下一次原子 load 立刻看到 CanEvict() == true, 30s 的等待被压缩成了几毫秒. 这里 lease_now = max(lease_now, now) 的 max 不是防御性编程的装饰: system_clock 可能回退 (题目条件 6), 如果 now 比 lease_now 还小而我们直接赋值, 水位线就倒退了, 不变量 3 被破坏, 已经沉下去的旧 token 会重新浮到水位线之上, (R2) 就挡不住它们了.

(R2) 是水位线的收网动作: token <= lease_now 说明这个调用者所属的窗口早已被 (G2) 或 (R1) 整体废弃, 他的计数贡献当时已经被一并清零, 现在什么都不用做. 顺便可以验证一下不变量 1 为什么能一直成立: 所有把水位线往上推的路径, (G2)(R1)(R3), 恰好也都是把 lease_cnt 清零或重置的路径. “抬水位线”和“废弃旧窗口计数”永远是同一个动作.

(R1) 和 (G2) 对称: 真实时间已经越过窗口右沿, 无论 token 是谁, 直接把状态重置到“无人持有”. 有个细节值得多看一眼: 为什么这里要把 lease_timeout 从一个更小的旧值改写成 now? 因为水位线抬到了 now, 不变量 2 要求 lease_timeout 跟上. 这一笔表面上把 lease_timeout 写大了, 但它复活不了一个已经过期的 lease: 任何读到时间 >= now 的回收器看它照样过期; 就算时钟回退, 让它在个别回收器眼里短暂显得未过期, 那也只是把回收推迟一小会, 是保守方向的误差, 不破坏任何承诺.

最后说下两个 assert, 它们不是摆设, 而是不变量 1 的直接推论: 能走到这里的 token 满足 lease_now < token, 而当前窗口内所有 token 都 <= lease_timeout ((G2) 的赋值与 (G3) 的 max 共同保证), 所以第一条成立; 又因为存在一个水位线之上尚未释放的 token, lease_cnt 必然大于 0. 这两个 assert 在线上等价于免费的一致性自检, 真炸了就说明有人违反了调用协议. 最典型的违反, 就是把同一个 token release 了两次: token 不是身份, 重复扣减会把别人的那份计数也扣掉, 别人还在读的对象就可能被提前回收. 所以 ReleaseLease 必须是 at-most-once, 失败了也不要重试, 反正有 TTL 兜底, 丢一次 release 最多损失一点回收及时性.

后记

随着用 AI vibe coding 的人越来越多, 代码质量成了我最担忧的问题. 就我旁观团队同学 vibe coding 的体感, 下面三类问题反复出现:

真实项目里链路从来不止一条, 而且形态各异. 开发一个新需求时, 本来就该逐条斟酌它和每条存量链路是否适配; 对不适配的组合, 正确做法是主动检测、当场报错“这个配置组合我们不支持”, 而不是静默处理, 最后以精度不对或者预料之外的 crash 的形式浮出水面. 但 AI 几乎从不主动 assert “这条链路/这个配置组合我不支持”, 它只会硬着头皮实现下去, 留下一堆莫名其妙的问题.
随意的 if 分支. 上面参考实现里的每一个 if 都是被不变量逼出来的, 各自有一段能讲清楚的存在理由; 而 vibe coding 出来的 if 往往是反的: 先随手写了分支, 再倒过来找理由, 甚至没有理由. 每多一个 if, 需要论证的状态组合就翻一倍. 就算是让 AI 写代码, 也应该扪心自问一句: 这个 if 真的有必要么? 我真是太讨厌 if 了.
滥用 Python 动态特性. getattr/setattr 满天飞, kwargs 一路透传, 对象结构要跑起来才知道长什么样; 本来 review 时一眼能看出的问题, 全被推迟到线上才暴露. 写代码时, 我一直尽量坚持着“所搜即所得”: 通过 CTRL-F 纯文本搜索就能得到想要的答案. 这也是我超喜欢 Rust 的原因, 没有语法上的隐式结构, 想知道对象在哪里构造? 直接 CTRL-F 搜索相应函数就行; 如果是 C++, 那五花八门的构造姿势就别想了=。=

这也是我越来越倾向用这类题目做笔试的原因: AI 把“写出能跑的代码”变得前所未有地便宜, 但“哪些分支不该存在、哪些组合应该当场拒绝、哪些不变量必须守住”, 这些判断反而越来越贵. 这道题考的, 恰好就是后者.

背景: 回收器被 lease 卡死了

题目

参考实现

后记

CATALOG