KV Cache 分页与前缀缓存

Paged KV Cache & Prefix Caching

解决 LLM 推理中 KV Cache 内存碎片化和重复计算问题，通过分页管理和内容哈希实现高效缓存复用

子问题

1.KV Cache 内存碎片化

2.前缀重复计算

3.Block 引用计数与生命周期

4.内容哈希冲突处理

5.Decode 阶段 Block 边界跨越时的增量分配时机

6.CUDA Graph 固定张量尺寸与可变 block_table 长度的兼容

7.Preempt 抢占后序列重新入队的缓存失效处理

Signals

维度	nano-vllm
分页策略	固定 256 token Block，deque 空闲池 O(1) 分配
前缀缓存	xxhash 链式哈希内容寻址，碰撞时 token_ids 精确比对
引用计数	Block 级 ref_count，多序列共享，归零即回收
显存分配	warmup 峰值探测后一次性分配 6 维张量池
KV 写入	Triton JIT kernel 按 slot_mapping 并行写入
调度集成	Scheduler 双阶段调度，preempt 抢占释放 Block

1.使用 xxhash 等快速哈希算法做内容寻址

2.Block 粒度对齐到 256 token 以平衡碎片与命中率

3.链式哈希将前一 Block 哈希作为 prefix 参与计算，确保前缀连续性

4.cache_miss 一旦触发即传播到后续所有 Block，避免断裂的部分命中

5.warmup 模型后用峰值显存差值计算可用 Block 数，最大化显存利用