vLLM snapshot 使用链式 block hash

vLLM 在实现 Automatic Prefix Caching（自动前缀缓存）与 State Snapshot（状态快照/分叉）时，采用链式 Block Hash（Chained Block Hash）来保证上下文缓存判重的唯一性与高效查找。

在 PagedAttention 机制下，显存被划分为固定大小的 Block（如每块 16 个 Token）。链式 Block Hash 的核心原理是：当前 Block 的 Hash 值，必须由“上一个 Block 的 Hash”与“当前 Block 的 Token 内容”共同决定。

计算递推公式

• 首个 Block (N=0N=0N=0)：

H0=Hash(Tokens0)H_0 = \text{Hash}(\text{Tokens}_0)H0​=Hash(Tokens0​)

• 后续 Block (N≥1N \ge 1N≥1)：

HN=Hash(HN−1,TokensN)H_N = \text{Hash}(H_{N-1}, \text{Tokens}_N)HN​=Hash(HN−1​,TokensN​)

为什么必须采用“链式”设计？

1. 消除上下文碰撞（Context Collision）
   假设两段完全不同的对话，在第 10 个 Block 刚好出现了相同的 16 个常用 Token（例如"\nSystem: OK, I got it.\n"）。

• 如果不加链：仅 Hash 当前 16 个 Token，这两个 Block 的 Hash 完全相同，框架会误认为它们可以共享 KV Cache，导致严重的前缀上下文错乱。
• 如果加链：因为两段对话前 9 个 Block 的H8H_8H8​不同，代入计算后第 10 个 Block 的H9H_9H9​必然不同，从而确保了即便局部 Token 相同，只要前缀历史不同，Hash 就绝对不碰撞。

2. 天然构成隐式前缀树（Radix Tree）
   链式 Hash 的指针依赖关系，在全局 Block 哈希表中自然构建起了一棵前缀树。任何一个历史节点HNH_NHN​都唯一对应了一条从根节点到当前位置的完整 Prompt 路径。

在 Snapshot 与状态恢复中的作用

利用链式 Block Hash，vLLM 可以在多轮对话、树状搜索（Tree Search）或 Speculative Decoding 中实现零拷贝的快照管理：

• 秒级创建快照（Snapshot/Fork）：
  保存当前推理状态时，无需物理拷贝庞大的 KV Cache 矩阵，只需记录当前末尾 Block 的链式 Hash 值HtailH_{\text{tail}}Htail​，并将其路径上所有物理 Block 的引用计数（Ref Count）加 1。
• 快速命中与恢复：
  新请求发起或状态回滚时，框架沿 Token 序列逐 Block 计算链式 Hash，直接在全局 Hash Table 中匹配HiH_iHi​。命中者直接映射物理 Block 页，避开重复计算；一旦出现不同 Token，从分支点分裂（COW，写时复制）分配新 Block 即可。