P06 · BlockManager：paged KV + 前缀缓存
PagedAttention 的内存管理层：引用计数、哈希链前缀匹配、LRU 可驱逐池、原子分配。
mine/p06_block_manager.py
验收 ./check.sh p06
提示 A-17 · 参考解 C-17 solutions/p06_block_manager.py
题面速览
- 在系统中的位置：KV cache 被切成固定大小的物理 block（例如 16 个 token）。每个序列有一张 block table：逻辑块 i → 物理块号。attention kernel 用
slot = table[pos // bs] * bs + pos % bs找到 token 的 K/V。 - 前缀缓存：同一个 system prompt、同一张图的多轮对话，前缀 KV 完全相同。满的 block 用哈希链标识：
h_i = hash((h_{i-1}, tuple(block_i 的 token)))（链式哈希保证“相同内容但前缀不同”的块不会误命中）。分配时从头逐块匹配，命中就共享物理块（引用计数 +1）。
prompt: [0..9]（bs=4） → 块 [0,1,2,3] [4,5,6,7] [8,9,_,_]
可匹配块数 = (len - 1) // bs = 2 # 至少留 1 个 token 要算（否则拿不到下一个 token 的 logits）
num_cached_tokens = 命中块数 × bs
- 释放与驱逐：free 时逆序减引用；归零的块：有哈希 → 进 LRU 可驱逐池（仍能被命中复用）；无哈希 → 回空闲表。需要新块时优先空闲表，其次驱逐 LRU 最旧的（同时删除它的哈希登记）。
num_free_blocks = 空闲 + 可驱逐。 - 原子性：allocate / append 因 block 不足失败时必须不改变任何状态（先检查后修改）。命中可驱逐池里的块也会占用“可用”名额。
- append 填满一个块：decode 让最后一个块变满时也要计算哈希并登记，后续请求可以命中模型生成的内容（多轮对话）。
验收要点：slot 映射 · append 跨 block 边界 · OutOfBlocks 原子性 · free 全部归还 · 前缀共享与引用计数 · free 后缓存仍可命中、最后一个 token 永不命中 · 驱逐后不再命中 · append 填满的 block 也进入缓存。
直觉与类比
物理 block = 一间四人间（block_size=4 张床），num_blocks = 酒店一共几间房。一个序列 = 一个旅行团，前台给它一张房卡清单（block table）：第 1 批住 2 号房、第 2 批住 7 号房……房间号不需要连号——这正是 paged 的意义。slot(seq, pos) 就是“第 pos 号客人睡哪张床”：房号 × 每间床数 + 床位号。
读者还书后，书先放在还书推车上：① 别的读者正好要这本书，可以直接从推车上拿走（命中一个 ref==0 的块，“复活”它）；② 推车满了，馆员从最早放上来的那一端拿走一本，抹掉内容改装成别的书（LRU 驱逐）。抹掉的那一刻必须把目录卡片（hash → block）也撕掉，否则下一个读者按目录拿到封面对、内容全错的书——KV 错乱，模型不报错，只会悄悄说胡话。
如果块的标签只写“本块装了 [7, 8]”，两个前缀完全不同的序列会误认为能共享它。可 KV 的值依赖从句首到这里的全部上下文。所以标签写成“上一块的标签 + 本块内容”，只有整条前缀都一样的序列才会算出同一个 h_i。
框架视角 · 三个操作 · 一张账本 · 不变量
| 操作 | 读（只读，不能有副作用） | 写（顺序很重要） | 可能 raise 的位置 |
|---|---|---|---|
| allocate | ① 满块的哈希链（只给 len//bs 个满块算）② 在前 (len-1)//bs 块内从头连续查 hash→block，第一次 miss 就停 ③ 容量：需要新块数 ≤ num_free_blocks − 命中块中 ref==0 的个数 | ④ 命中块：ref==0 的先移出可驱逐池 → ref+1 ⑤ 其余块：取新块（空闲优先，否则驱逐最旧 + 删哈希登记）⑥ 满块登记哈希 ⑦ 保存 table / tokens / 哈希链 / 命中数 | 只在 ③（以及 ⑤ 的兜底）；必须在任何写之前 |
| append_slot | pos = len(tokens[seq])；pos // bs == len(table) 吗（要不要新块） |
① 先取新块（唯一会 raise 的事）② 再 append token ③ 若 (pos+1) % bs == 0：这块刚满 → 用链尾当父哈希，算新哈希、入链、登记 |
只在 ①；顺序反了会留下“多了一个 token”的脏状态 |
| free | 该序列的 block table | 逆序遍历：ref−1；归零时有哈希 → 进可驱逐池（最新一端），否则 → 空闲表；最后删掉该序列的四份记录 | 不会 raise |
| 不变量 | 违反时的症状 |
|---|---|
I1 num_free_blocks == len(空闲表) + len(可驱逐池)，二者不相交，块都满足 ref == 0 |
同一个块被分配给两个序列，内容互相覆盖 |
I2 b ∈ 可驱逐池 ⟺ ref[b] == 0 且 block_hash[b] is not None |
命中后忘了移出池子 → 正在用的块被当候补驱逐 |
I3 hash_to_block[h] == b ⟹ block_hash[b] == h |
驱逐后没删映射 → 旧前缀“命中”一块已被覆盖的块 |
I4 ref[b] == 包含 b 的 block table 个数；全部 free 后 num_free_blocks == num_blocks |
block 泄漏：跑一会儿就 OutOfBlocks |
I5 num_cached_tokens(seq) % bs == 0 且 < len(token_ids) |
全部命中时模型没有 token 可 forward，采不出下一个 token |
易错点
- 给半满的最后一块也算哈希：之后更长的 prompt 会命中只装了部分 token 的块。只有满块才有身份。
- 可匹配上限写成
len // bs：prompt 恰为 bs 整数倍且全命中时 num_cached_tokens == len，违反 I5。 - 哈希链起点不一致：allocate 用 None 当 h_{-1}、append_slot 用别的哨兵 → decode 填满的块永远不会被 allocate 命中。
- 驱逐时无条件
del hash_to_block[h]：同一哈希被两个块算出（内容相同）、映射指向另一个块时，会删掉别人的有效映射。 - free 用正序：尾部块（最不通用）变成“最新”从而最晚被驱逐，共享度最高的首块反而先死。
can_allocate与 allocate 的检查混为一谈：前者粗（不看命中，偏保守），后者必须精确。- 命中 ref==0 的块时没移出可驱逐池；append 先 append token 再取块。
逐步图：前缀共享 + 引用计数 + 可驱逐池（例 2）
块0=[1,2]、块1=[3,4] 是满块，登记 h0、h1；块2=[5] 不满，不登记。num_cached_tokens("a") = 0。
ref：11100000
可匹配 (5-1)//2 = 2 块，两块都命中（ref+1）；块 3 是新块。num_cached_tokens("b") = 4，num_free_blocks = 4。
ref：22110000
逆序：块2 ref→0 无哈希 → 空闲表；块1、块0 ref→1。num_free_blocks = 5。
ref：11010000
逆序：块3 → 空闲表；块1、块0 ref→0 有哈希 → 可驱逐池 [1, 0]（块1 先入池 = 最旧）。num_free_blocks = 8（空闲 6 + 可驱逐 2）。
ref：00000000（绿色 = 在可驱逐池里）
只有 (4-1)//2 = 1 块可匹配！块0 从可驱逐池“复活”；可驱逐池剩 [1]。num_cached_tokens("c") = 2。
第二块 [3,4] 明明在缓存里，但“至少留 1 个 token 要算”的规则不允许命中，于是分配了新块 4。
三级提示
L1I/O 示例与关键问题I/O 示例 + 关键问题 + 细节（轻度剧透）
例 1：不开前缀缓存（block_size=4, num_blocks=6，空闲表 FIFO）：
bm.allocate("x", [11, 12, 13, 14, 15, 16]) # -> [0, 1] ceil(6/4)=2 块
bm.num_free_blocks # -> 4 空闲表 [2, 3, 4, 5]
bm.slot("x", 5) # -> 5 = table[5//4]*4 + 5%4 = 1*4 + 1
bm.append_slot("x", 17) # -> 6 pos=6，块 1 还有空位
bm.append_slot("x", 18) # -> 7 pos=7，块 1 填满
bm.append_slot("x", 19) # -> 8 pos=8，需要第 3 块 -> table [0, 1, 2]
bm.num_free_blocks # -> 3
bm.free("x") # 逆序归还 2, 1, 0 -> 空闲表 [3, 4, 5, 2, 1, 0]
bm.allocate("y", [1, 2, 3]) # -> [3]
例 2：见逐步图。
例 3：命中可驱逐块也会占用名额——原子性陷阱（block_size=2, num_blocks=3）：
bm.allocate("a", [1, 2, 3, 4, 5]); bm.free("a")
# 空闲表 [2]，可驱逐池 [1, 0]，num_free_blocks = 3
bm.allocate("b", [1, 2, 3, 4, 5, 6, 7]) # 需要 4 块；命中块0、块1（都在可驱逐池里）
# -> raise OutOfBlocks
bm.num_free_blocks # -> 3，空闲表 [2]，可驱逐池 [1, 0]（完全没变）
bm.allocate("b", [1, 2, 3, 4, 5, 6]) # -> [0, 1, 2]，num_cached_tokens = 4，num_free_blocks -> 0
第一次：需要新块 4−2=2 个，但“可用”的 3 块里有 2 块正是被命中的那两块，真正能当新块的只有 1 块，所以必须失败，且失败前不能动任何状态。
关键问题
- prompt 10 个 token、bs=4：需要几块？哪几块是满块、会得到哈希？半满的块会不会进前缀缓存？
- prompt 恰好 8 个 token、bs=4，两块都已在缓存里。允许命中几块？num_cached_tokens 是多少？全部命中的话模型这一步能产出什么？
- 两个块内容都是 [7, 8]，一个前面是 [1, 2]、一个前面是 [5, 6]。哈希应该相同吗？
- 命中的块可能 ref>0，也可能 ref==0。两种情况 allocate 时分别做什么？哪一种会让“可用块数”变少？
- 从可驱逐池拿一个块装新内容时，除了移出池子，还必须清理哪两处记录？
- append_slot 新 token 的 pos 是多少？什么条件下拿新块？拿块失败时哪些状态已被你改掉了？
- free 时为什么逆序遍历？
细节
- 哈希链起点选一个固定哨兵（如 None）当 h_{-1}；allocate 和 append_slot 必须同一套规则。
- 从头连续匹配——第一次 miss 就停。
can_allocate(num_tokens)只是ceil(num_tokens/bs) <= num_free_blocks的粗检查。- enable_prefix_cache=False：不登记任何哈希，free 后的块全部回空闲表，num_cached_tokens 恒为 0。
- 同内容多副本：哈希表里一个哈希只指向一个物理块；登记时若已存在保留旧的。驱逐时只有映射正指向这一块才删除。
L2思路与常见坑思路拆分与常见坑（中度剧透）
| 结构 | 用途 |
|---|---|
free: deque[int] |
无哈希的空闲块，popleft 取、append 还 |
ref: list[int] |
每个物理块的引用计数 |
block_hash: list[int|None] |
每个物理块当前登记的哈希（None = 不在缓存里） |
hash_to_block: dict[int,int] |
命中查找 |
evictable: OrderedDict[int,None] |
ref==0 但仍有哈希的块，插入顺序 = LRU 顺序 |
tables / tokens / hashes / cached: dict[seq_id, ...] |
每个序列的 block table、全部 token、哈希链、命中 token 数 |
- allocate = 先算、再查、最后改。容量检查公式：
新块数 = 总块数 − 命中数；真正可用 = num_free_blocks − 命中块中 ref==0 的个数。只写新块数 <= num_free_blocks时例 3 会“通过检查”，然后在取第 2 个新块时才 raise——此时命中块的 ref 已经加过了，状态被破坏。 - 取块 helper
_take_block()：空闲表非空就 popleft；否则从可驱逐池弹出最旧的，删除它的哈希登记（两处），否则 raise；最后 ref 设为 1。allocate 和 append_slot 都用它。 - append_slot 顺序：
pos = len(tokens[seq])；若pos // bs == len(table)先取新块；再 append token；若(pos + 1) % bs == 0用链尾当父节点算新哈希、追加进链并登记。最后返回slot(seq, pos)。 - free：逆序，ref−=1；归零看 block_hash：有 → 可驱逐池最新端，无 → 空闲表。删掉该序列的四份记录。
L3详解：答案与驱逐追踪详解：答案、逐步追踪、骨架提示（重度剧透）
关键问题答案
- 3 块；满块是第 0、1 块（token 0..7），各有哈希；第 2 块只有 2 个 token，不进缓存。
- 只能命中 (8-1)//4 = 1 块，num_cached_tokens = 4。全命中的话没有任何 token 要 forward，拿不到最后位置的 logits，采样不出下一个 token。
- 不同。链式哈希把前缀编码进去，防止“块内容相同但前缀不同”的块被误命中。
- ref>0：只需 ref+1。ref==0：先从可驱逐池删掉再 ref=1；它原本算在 num_free_blocks 里，命中后不再可用，让“可用于新块的数量”减 1。
block_hash[b]置 None，以及hash_to_block中指向 b 的映射。不清理：之后同前缀请求会“命中”被覆盖的块，KV 错乱。- pos = 当前 token 数；条件
pos // bs == len(table)；拿块是第一步，失败时什么都还没改。 - 逆序时最后一块最先进入可驱逐池，成为“最旧”，最先被驱逐；越靠前的前缀块（更可能被共享）越晚被驱逐。
追踪：append 填满的块进入缓存，随后被驱逐（block_size=2, num_blocks=3）：
| 操作 | 返回 | 空闲表 | 可驱逐池 (旧→新) | 说明 |
|---|---|---|---|---|
| allocate("a",[7,8,9]) | [0, 1] | [2] | [] | 块0=[7,8] 满，登记 h0；块1=[9] 不满 |
| append_slot("a",10) | 3 | [2] | [] | pos=3 → 块1 offset 1；块1 刚满，用父哈希 h0 算 h1 并登记 |
| free("a") | [2] | [1, 0] | 逆序：块1 先入池（最旧） | |
| allocate("b",[7,8,9,10,11]) | [0, 1, 2] | [] | [] | 可匹配 2 块，全中，num_cached_tokens=4 |
| free("b") | [2] | [1, 0] | 块2=[11] 无哈希 → 空闲表 | |
| allocate("z",[50..55]) | [2, 1, 0] | [] | [] | 先用空闲块 2，再驱逐 1、0，并删除 h1、h0 的登记 |
| free("z"); allocate("b2",[7,8,9,10,11]) | ?? | num_cached_tokens = ??（h0 还在吗？） |
最后一行
返回 3 个新块、num_cached_tokens = 0——h0、h1 在驱逐时已被删除。
自检：例 1~3 逐行跑一遍；再构造“同一块被两个序列共享、先 free 一个、再 free 另一个”，确认第一次 free 后 num_free_blocks 只增加了非共享的块。
面试官追问 & 对照源码
- 多模态 prompt 的 block hash 必须包含什么？
- 多个 stage 共卡时，每个 stage 的 num_blocks 怎么定？
对照源码：vllm/v1/core/kv_cache_manager.py · vllm/v1/core/block_pool.py