vLLM APC 六问：从 block hash 到 free/evict

上一篇我把 vLLM Automatic Prefix Caching，简称 APC，放回了 prefill、decode、PagedAttention 和 Scheduler 的大图里。

这篇只追六个源码问题：

1. block hash 怎么构造？
2. 最长前缀命中怎么找？
3. 命中的 block 怎么 touch 并挂进 request？
4. 新 block 怎么分配？
5. free 和 evict 为什么不是一回事？
6. 哪些请求为什么必须跳过 APC？

这六个问题串起来，才是 vLLM 作为推理系统的味道：它不是简单地“查一个缓存”，而是在调度器、KV block 管理、引用计数、hash namespace、spec decode、pooling 输出之间维护一套可复用但不能乱复用的内部状态。

源码版本是 vLLM commit 752a3a504485790a2e8491cacbb35c137339ad34。主线文件是：

• vllm/v1/request.py
• vllm/v1/core/kv_cache_utils.py
• vllm/v1/core/kv_cache_manager.py
• vllm/v1/core/kv_cache_coordinator.py
• vllm/v1/core/single_type_kv_cache_manager.py
• vllm/v1/core/block_pool.py
• vllm/sampling_params.py
• vllm/pooling_params.py

先给一张脑内流程图：

Request.update_block_hashes()
  -> hash_block_tokens(parent_hash, block_token_ids, extra_keys)
  -> KVCacheManager.get_computed_blocks()
  -> KVCacheCoordinator.find_longest_cache_hit()
  -> FullAttentionManager.find_longest_cache_hit()
  -> BlockPool.get_cached_block()
  -> KVCacheManager.allocate_slots()
  -> KVCacheCoordinator.allocate_new_computed_blocks()
  -> SingleTypeKVCacheManager.add_local_computed_blocks()
  -> BlockPool.touch()
  -> SingleTypeKVCacheManager.allocate_new_blocks()
  -> BlockPool.get_new_blocks()
  -> KVCacheCoordinator.cache_blocks()
  -> BlockPool.cache_full_blocks()
  -> BlockPool.free_blocks() / BlockPool._maybe_evict_cached_block()

如果你只记一句话：

APC 的本质是：用链式 block hash 找到一段连续、完整、可复用的 KV block 前缀，
把这段前缀转成 request 的已计算进度，并用引用计数保护住对应物理 block。

1. block hash 怎么构造

APC 的 key 不是原始 prompt 字符串，而是 token 化之后的 full block。

入口在 Request.update_block_hashes()。这个方法本身很短：如果 request 上有 _block_hasher，就把新出现的完整 block 转成 hash，追加到 request.block_hashes。真正的构造逻辑在 hash_block_tokens()：

BlockHash(
  hash_function((
    parent_block_hash,
    tuple(curr_block_token_ids),
    extra_keys,
  ))
)

这里有三个关键字段。

第一，curr_block_token_ids。

vLLM 比较的是 tokenizer 之后的 token id，不是你肉眼看到的字符串。chat template、special tokens、多模态 placeholder、不同 tokenizer 版本，都可能让“看起来一样”的文本变成不一样的 token 序列。APC 必须站在模型真正吃进去的 token 视角，而不是站在 API 文本视角。

第二，parent_block_hash。

这是最容易被忽略的点。block hash 不是每个 block 独立算：

h0 = H(NONE, [A, B, C, D], extra0)
h1 = H(h0,   [E, F, G, H], extra1)
h2 = H(h1,   [I, J, K, L], extra2)

为什么要带 parent？因为 Transformer 里某个 block 的 KV 不是只由这个 block 自己决定。[E, F, G, H] 出现在 A B C D 后面，和出现在 X Y Z W 后面，attention 能看的历史不同，算出来的 K/V 也不是同一个语义状态。

所以 vLLM 用链式 hash 把“当前位置之前的所有上下文”压进当前 block 的 key。这样一来，两个请求必须从第一块开始连续相同，后面的 block 才可能继续命中。

第三，extra_keys。

generate_block_hash_extra_keys() 会把这些东西并入 hash key：

LoRA 信息
多模态输入的 hash
cache_salt
prompt embeddings 相关 key

这解决的是“token id 一样但内部状态不应该共享”的问题。比如同一串 token 在不同 LoRA adapter 下，模型权重变了，KV 不能复用；同一段文本配了不同图片 embedding，KV 也不能复用。

cache_salt 的细节尤其值得单独拎出来。源码只在 start_token_idx == 0 时把 salt 加入第一块的 extra_keys，但因为后续 block hash 都带 parent hash，所以 salt 会沿着整条 hash 链传播。

salt 不同:
  h0 不同
  -> h1 的 parent 不同
  -> h2 的 parent 不同
  -> 整条前缀链都不会互相命中

这不是说 APC 不能复用，而是说复用必须发生在同一个 hash namespace 内。同一个 tenant、同一个安全域、同一个共享系统提示词场景，可以用同一个 salt 复用；不同租户或安全域，用不同 salt 隔离。风险不是“缓存把别人回答吐出来”，而是攻击者通过请求延迟推断某个前缀是否曾出现过。salt 隔离的是这种命中侧信道。

2. 最长前缀命中怎么找

调度器真正查 APC，是通过 KVCacheManager.get_computed_blocks(request)。

这个函数第一段先判断是否允许读 prefix cache：

if not self.enable_caching or request.skip_reading_prefix_cache:
    return empty, 0

然后它设置：

max_cache_hit_length = request.num_tokens - 1

这行很有推理系统味道：即使整个 prompt 都在 cache 里，也不能把全部 token 都直接跳过。为了得到下一 token 的 logits，最后一个 token 仍然需要重新进入本次计算。当前实现还要求 num_computed_tokens 按 block size 对齐，所以“留最后一个 token 重算”有时会导致重算整个最后 block。源码注释也说这未来还有优化空间。

真正找最长命中的实现，在 full attention 场景下是 FullAttentionManager.find_longest_cache_hit()。逻辑可以翻译成：

max_num_blocks = max_length // block_size

for block_hash in block_hashes[:max_num_blocks]:
    cached_blocks = block_pool.get_cached_block(block_hash, kv_cache_group_ids)
    if cached_blocks:
        append to computed_blocks
    else:
        break

if drop_eagle_block:
    pop last matched block

while returned length is not alignment_tokens-aligned:
    pop last matched block

所以它找的是“最长连续前缀”，不是“所有相同 block 的集合”。

举个例子：

block_hashes: [h0, h1, h2, h3]
cache 状态:    hit hit miss hit
返回结果:      h0, h1

h3 即使在 cache 表里，也不能拿来用。因为链式 hash 已经表达了前缀依赖，只要中间断了，后面的“命中”就不能作为这个 request 的连续历史。

BlockPool.get_cached_block() 还有一个多 KV cache group 的约束：它会给每个 kv_cache_group_id 拼出 block_hash_with_group_id，任何一个 group miss，都返回 None。这说明 APC 命中不是一个单表命中，而是要满足当前注意力结构需要的所有 KV cache group 都有可用 block。

这就是为什么 vLLM 的 APC 命中要走 coordinator 和 manager，而不是一个全局 dict[prompt_hash]。不同 attention 类型、sliding window、EAGLE/MTP、hybrid KV cache group，都可能改变“这段 cache 能不能作为当前请求的已计算前缀”。

3. 命中 block 怎么 touch 并挂进 request

get_computed_blocks() 只是“查到”。查到之后，block 还没有变成当前 request 的 block table。

真正挂进去发生在 KVCacheManager.allocate_slots()：

if new_computed_blocks exists or num_external_computed_tokens > 0:
    coordinator.allocate_new_computed_blocks(...)

new_blocks = coordinator.allocate_new_blocks(...)

顺序很重要：先处理已经命中的 computed blocks，再给剩下 token 分配新 block。

KVCacheCoordinator.allocate_new_computed_blocks() 又分两阶段：

1. 先让每个 manager add_local_computed_blocks()
2. 再让每个 manager allocate_external_computed_blocks()

源码注释解释了为什么要这么做：多 KV cache group 下，如果某个 group 先去为 external computed tokens 分配新 block，get_new_blocks() 可能会从 free queue 里拿走一个“另一个 group 还没 touch 的 cache-hit block”，从而把本来应该命中的 block evict 掉。先统一 touch 本地命中块，可以把它们从 eviction candidate 里救出来。

SingleTypeKVCacheManager.add_local_computed_blocks() 做了三件具体的事。

第一，拿到当前 request 的 block 列表：

req_blocks = self.req_to_blocks[request_id]
assert len(req_blocks) == 0

源码假设这只发生在首次分配。运行中的 request 如果已经被追踪过，coordinator 会短路，不重复把命中块挂进去。

第二，处理被 attention 机制跳过的 block。

比如 sliding window 里，有些老 block 对当前注意力不可达。源码会用 null block padding：

req_blocks.extend([self._null_block] * num_skipped_blocks)

这样 block table 的逻辑位置还在，但不可达位置不占真实 KV block。

第三，touch 并追加命中块：

self.block_pool.touch(new_computed_blocks)
req_blocks.extend(new_computed_blocks)
self.num_cached_block[request_id] = len(req_blocks)

touch() 是保护命中 block 的关键动作。它的源码语义是：

for block in blocks:
    if block.ref_cnt == 0 and not block.is_null:
        free_block_queue.remove(block)
    block.ref_cnt += 1

一个 cached block 可能已经没有 request 引用了，所以 ref_cnt == 0，但它的 hash metadata 还在，因此还留在 prefix cache 里。这个状态很微妙：

它可以被新请求 APC 命中；
但它也在 free queue 里，是可被重新分配、从而被 evict 的候选。

所以命中之后必须 touch。touch 的含义不是“更新时间戳”这么简单，而是：

把这个 block 从 free queue 拿出来，
把 ref_cnt 加一，
让它正式成为当前 request 的已引用物理 KV block。

最后那行 num_cached_block[request_id] = len(req_blocks) 也很关键。它告诉后面的 cache_blocks()：这些命中块本来就是 cache 里的，不要再尝试重复注册 hash。

4. 新 block 怎么分配

命中前缀只是减少了要算的 token，不代表 request 不需要新 block。剩下的新 token、lookahead token、外部 KV connector 回填的 token，都还要有 slot。

这部分集中在 KVCacheManager.allocate_slots()。它的源码 docstring 画了一张布局图，可以概括为：

| comp | new_comp | ext_comp | new | lookahead |

comp      = request 之前已经算过的 token
new_comp  = 本轮 APC 命中的本地 prefix cache token
ext_comp  = KV connector 认为已经在外部算好的 token
new       = 本轮要真正计算的 token
lookahead = speculative decoding 预留 token

这个函数先算：

num_local_computed_tokens =
  request.num_computed_tokens + num_new_computed_tokens

total_computed_tokens =
  min(num_local_computed_tokens + num_external_computed_tokens, max_model_len)

然后它先 remove_skipped_blocks()，把 attention 已经不可能再访问的 block 释放掉。源码注释明确说，这一步要放在分配新 block 之前，这样可以减少真正需要 evict 的 cached block。

之后通过 KVCacheCoordinator.get_num_blocks_to_allocate() 问所有 single-type manager：

为了让这个 request 至少拥有 num_tokens_need_slot 个 token slot，
扣掉已经挂上的命中 block 后，还需要新分配多少物理 block？

如果 free block 不够，allocate_slots() 返回 None，调度器这轮就不能调度这个 request。

如果够，才进入真正分配：

coordinator.allocate_new_computed_blocks(...)
new_blocks = coordinator.allocate_new_blocks(...)

KVCacheCoordinator.allocate_new_blocks() 只是分发到各个 manager；普通 full attention 场景看 SingleTypeKVCacheManager.allocate_new_blocks() 就够了：

req_blocks = self.req_to_blocks[request_id]
num_required_blocks = cdiv(num_tokens, self.block_size)
num_new_blocks = num_required_blocks - len(req_blocks)

if num_new_blocks <= 0:
    return []

new_blocks = self.block_pool.get_new_blocks(num_new_blocks)
req_blocks.extend(new_blocks)
self.new_block_ids.extend(...)

这里有一个非常重要的 subtraction：

num_new_blocks = required_blocks - len(req_blocks)

len(req_blocks) 里面已经包含了前面 add_local_computed_blocks 挂进去的命中 block。也就是说，APC 命中的 block 不是“额外奖励”，而是直接占据 request 的逻辑 block table 位置，新分配只补缺口。

BlockPool.get_new_blocks() 负责从 free queue 里拿物理 block：

ret = free_block_queue.popleft_n(num_blocks)

for block in ret:
    if enable_caching:
        _maybe_evict_cached_block(block)
    assert block.ref_cnt == 0
    block.ref_cnt += 1

这里再次体现 free 和 evict 的区别：从 free queue 拿到的 block 可能还带着旧的 block_hash，说明它之前作为 prefix cache 仍然可命中。现在它要被分配给新 token 了，旧内容马上会被覆盖，所以必须 _maybe_evict_cached_block(block)，把旧 hash 映射清掉。

最后，allocate_slots() 会调用 coordinator.cache_blocks(request, num_tokens_to_cache)。这里也有一个 spec decode 相关细节：

num_tokens_to_cache =
  min(total_computed_tokens + num_new_tokens, request.num_tokens)

源码注释说得很直白：draft tokens 可能会被 reject，所以只能 cache finalized tokens。vLLM 不是“只要有 KV 就立刻进 APC”，它必须保证写入 prefix cache 的 token 已经是请求真实序列的一部分。

5. free 和 evict 为什么不是一回事

这是读 APC 最容易混的地方。

在 vLLM 里，free 和 evict 不是同义词：

free:
  这个 block 当前没有 request 引用了，可以回到 free queue。

evict:
  这个 block 的旧 hash metadata 被移除，未来不能再通过 prefix cache 命中它。

BlockPool.free_blocks() 做的是引用计数和 free queue：

for block in ordered_blocks:
    block.ref_cnt -= 1
    if block.ref_cnt == 0 and not block.is_null:
        if block.block_hash is None:
            blocks_without_hash.append(block)
        else:
            blocks_with_hash.append(block)

free_block_queue.prepend_n(blocks_without_hash)
free_block_queue.append_n(blocks_with_hash)

popleft_n() 从 free list 头部拿 block；prepend_n() 放到头部；append_n() 放到尾部。结合源码注释，含义就是：

没有 hash 的 free block 不可能被 APC 命中，优先拿去复用；
带 hash 的 free block 仍然可能服务未来相同前缀，尽量晚一点被复用。

所以一个 block 可以处于这种状态：

ref_cnt == 0
block_hash != None
在 free queue 里

这看起来像“空闲”，但它还不是“废掉”。它是一个可回收的 prefix cache entry：如果新请求在它被重新分配前命中它，touch() 会把它从 free queue 移除，ref_cnt += 1，它又变回 live block。

真正的 evict 在 _maybe_evict_cached_block()：

evicted_hashes = _remove_cached_block_hashes(block)
if not evicted_hashes:
    return False

_emit_block_removed_events(evicted_hashes)
return True

它清的是 hash metadata 和 cache 事件，不是简单地把 block 放回 free queue。

get_new_blocks() 里会在物理块被重新分配时触发 _maybe_evict_cached_block()。这时必须 evict，因为同一个物理 block 接下来会装新的 token KV，旧 hash 如果还留在表里，就会把未来请求指向错误内容。

源码还有一个显式接口 BlockPool.evict_blocks(block_ids)，它的 docstring 更能说明二者区别：即使 ref_cnt > 0 的 block，也可以只从 prefix cache hash table 里 evict，而不会从 block pool 里 free 掉。也就是说：

free 管所有权：有没有 request 正在引用这个物理 block。
evict 管可发现性：还能不能通过 block hash 从 APC 查到这个 block。

这组状态才是 APC 的内存管理核心。

6. 哪些请求为什么必须跳过 APC

“跳过 APC”在源码里更准确地说，是跳过 prefix cache read。

KVCacheManager.get_computed_blocks() 只看两个条件：

not self.enable_caching
request.skip_reading_prefix_cache

request.skip_reading_prefix_cache 来自 Request.get_skip_reading_prefix_cache()：

如果 sampling_params.skip_reading_prefix_cache 显式设置了，用它；
否则如果 pooling_params.skip_reading_prefix_cache 显式设置了，用它；
否则 False。

那哪些地方会默认把它设成 True？

第一类是 prompt_logprobs。

SamplingParams.__post_init__() 里有这段逻辑：

if self.skip_reading_prefix_cache is None:
    self.skip_reading_prefix_cache = self.prompt_logprobs is not None

原因在注释里：如果读 prefix cache，prompt logprobs 的输出可能少于 n_prompt_tokens。

这很好理解。APC 的目的就是跳过一段已经算过的 prefill。但 prompt logprobs 要的是 prompt 内 token 的概率信息。你把前面 token 的 prefill 跳过了，本请求这次就没有为那些 token 重新产生对应 logits，自然无法完整返回每个 prompt token 的 logprob。

所以需要 prompt logprobs 的请求必须跳过 cache read，完整跑 prefill。

第二类是 token 级 pooling 任务。

PoolingParams._merge_default_parameters() 里：

if self.skip_reading_prefix_cache is None:
    if self.task in ["token_embed", "token_classify"]:
        self.skip_reading_prefix_cache = True
    else:
        self.skip_reading_prefix_cache = False

原因和 prompt logprobs 类似。token_embed、token_classify 这类任务要的是 token 级输出。如果 prefix cache 让前面一段 token 不经过本次计算，本请求就可能拿不到和 n_prompt_tokens 对齐的完整 token 输出。

第三类是调用方显式要求。

比如一些路径会把 bypass_prefix_cache 映射到 skip_reading_prefix_cache。这不是默认性能策略，而是调用方对正确性、隔离、调试或外部 KV 流程的显式选择。

还要注意一个容易误解的点：

skip_reading_prefix_cache 只表示本请求不从 APC 读命中，
不等于这个请求一定不往 APC 写。

allocate_slots() 后面的 cache_blocks() 仍然由 enable_caching 和 delay_cache_blocks 控制。一个需要 prompt logprobs 的请求可能不能复用旧 cache，但它完整 prefill 后产生的 finalized full blocks，仍然可以被后续普通生成请求复用。

另一些情况不是“跳过”，而是“自然 miss”：

不同 cache_salt
不同 LoRA
不同多模态输入
不同 prompt embeddings
不同 chat template/tokenization 结果

这些会通过 extra_keys 或 token ids 改变 block hash。系统没有跳过查表，只是 key 不同，所以不会命中。

把六个动作连起来

现在可以把 APC 的一次命中生命周期串成完整状态机：

请求进入:
  token ids 形成 full block
  Request.update_block_hashes() 生成链式 block hash

调度前:
  KVCacheManager.get_computed_blocks()
  如果允许读 cache，就按 block_hashes 找最长连续命中
  最多命中到 prompt_length - 1，给最后 token 留 logits 计算

命中后:
  allocate_slots() 先处理 computed blocks
  add_local_computed_blocks() 把命中块挂进 req_to_blocks
  BlockPool.touch() 把 ref_cnt 从 0/已有引用继续加一
  如果 block 原本在 free queue，把它移除，避免被分配走

补缺口:
  根据 request 需要的 token slot 计算还差多少 block
  BlockPool.get_new_blocks() 从 free queue 拿新物理块
  如果拿到的 block 还带旧 hash，先 evict 旧 cache metadata
  req_to_blocks 追加新 block

计算后:
  finalized full blocks 通过 cache_blocks() 注册进 prefix cache
  draft / unverified token 不进入 APC

请求结束或 block 不再需要:
  free_blocks() 降 ref_cnt
  ref_cnt 为 0 的 block 回到 free queue
  带 hash 的 free block 仍可被未来请求 APC 命中
  直到物理块被重新分配或显式 evict，hash metadata 才会被移除

这就是为什么 APC 不是“一个缓存功能”，而是一套推理系统内部协议：

hash 负责正确性边界；
longest prefix hit 负责把可复用 KV 转成连续进度；
touch/ref_cnt 负责并发请求下的生命周期；
free queue 负责内存再利用；
evict 负责清理过期 hash；
skip_reading_prefix_cache 负责那些必须完整产出 prompt/token 级结果的请求。

如果你把这套状态机吃透，再看 vLLM 的 KV connector、P/D 分离、spec decode、sliding window、hybrid attention，就不会只看到一堆 if/else。你会看到它们都在回答同一个问题：

当前 request 的哪些 token 已经有可信 KV？
这些 KV 在哪些物理 block 里？
谁正在引用它们？
哪些 block 只是空闲但还值得保留？
哪些 block 的旧身份必须被清掉？

这就是 vLLM 作为推理系统最核心的味道：把模型计算，变成可调度、可复用、可回收、可隔离的 block 生命周期。