AI007. Prefix Cache 调度器

解题思路

考点定位

LLM 推理服务的 Prefix Cache 槽位选择模拟。算法只有「逐槽位比公共前缀」，考的是三级并列规则和状态更新的先后顺序——典型的「规则密集型」机考题。

每个请求怎么选槽位

对当前请求，逐个槽位计算它的缓存序列与请求序列的最长公共前缀长度（从头逐 token 比到第一个不同处）。选槽位按三级优先：

1. 公共前缀更长者优先； 2. 前缀一样长，当前负载更小者优先； 3. 仍并列，编号更小者优先。

实现上用一个三元组作比较键：(-prefixLen, load, id) 取最小，一次遍历完成，不需要排序。

选完之后的状态更新

两个动作，顺序和数值都别想当然：

• 负载增加的是未命中数：len(请求) − prefixLen，不是整个请求长度，也不是前缀长度。命中的部分复用缓存，只有没命中的 token 产生新计算量。
• 缓存序列整体替换为本次请求的序列（不是拼接、不是保留原值）。下一个请求面对的是更新后的槽位。

输出的槽位编号从 1 开始，内部若用 0 基下标记得 +1。

实现步骤

best = None
for i, (load, seq) in enumerate(slots):
    p = 0
    while p < len(seq) and p < len(req) and seq[p] == req[p]:
        p += 1
    key = (-p, load, i)
    if best is None or key < best[0]:
        best = (key, i, p)
_, sid, p = best
slots[sid][0] += len(req) - p    # 负载加未命中数
slots[sid][1] = req              # 缓存整体替换

复杂度

时间 O(S·Q·L)，L 为序列最长长度；空间 O(S·L)。规模内直接双层循环即可。

易错点清单

• 三级并列的顺序写乱（先比负载再比前缀）。
• 负载加成了请求全长或前缀长。
• 忘记替换缓存序列，后续请求全部错位。
• 槽位编号 0 基 1 基混淆。
• 公共前缀为 0 也是合法选择（谁都不匹配时按负载与编号裁）。

样例走查

样例 1：三个槽位 (load=3, 缓存 1 2 3)、(load=1, 缓存 1 2 4)、(load=0, 缓存 9)，两个请求。

请求 1 2 5：三个槽位的公共前缀分别是 2、2、0。前缀并列在槽 1 和槽 2 之间，比负载：3 对 1，选负载小的槽 2，输出 2 2。更新：负载 1 + (3−2) = 2，缓存替换为 1 2 5。

请求 9 8：槽 1、2 前缀 0，槽 3 前缀 1（9 命中后缓存耗尽），选槽 3，输出 3 1。第一问的更新如果忘了做，第二问面对的槽位状态就全是错的——状态题错一步废全局。

面试里怎么讲它

Prefix Cache 是 LLM 推理工程的真实机制，面试口径：多个请求共享相同的前缀（系统提示词、few-shot 模板）时，前缀部分的 KV 已经算过，命中缓存就只为未命中的后缀付出计算——这道题里「负载加未命中数」正是这笔账的抽象。追问「为什么并列时选负载小的槽位」：这是最朴素的负载均衡，避免热门前缀把单一槽位打爆。把一道模拟题讲成「我理解 vLLM 这类推理框架为什么做 prefix caching」，是这题在面试里的正确打开方式。