S07 · Page the KV Cache — 把连续上下文映射到分页内存

序列在逻辑上连续，存储它的物理块不必连续。

01连续分配为什么难以管理

请求的最终输出长度通常未知。预留一大段连续 KV 会浪费空间，增长时重新分配又需要复制。分页把 cache 分成固定大小的块，每条请求只保存逻辑块到物理块的映射。序列增长时补一个块即可，完成后回收各块；尾块仍可能有内部浪费，因此块大小也存在取舍。

s07_paged_kv.py

# Framework pseudocode for block-table responsibilities.
def resolve_position(request, token_position):
    logical = token_position // block_size
    offset = token_position % block_size
    return request.block_table[logical], offset

required = ceil_div(computed_positions + planned_tokens, block_size)
new_blocks = pool.reserve(max(0, required - len(request.block_table)))
request.block_table.extend(new_blocks)
# Reservation does not mean these positions were computed.

for block in finished_request.block_table:
    pool.release_reference(block)
# Reclaim storage only after the final reference is released.

02地址翻译必须贯穿读写两端

token 位置除以 block size 得到逻辑块号，余数给出块内偏移，再查 block table 得到物理地址。写入新 K/V 和读取历史 K/V 都必须遵守同一个映射。分配失败时不能先增加长度，也不能重复释放共享块。真正的分页注意力还要让算子直接理解块表，而非每步重新拼出连续张量。

03区分块管理和模型缓存布局

DeepInfer 的 block_manager.hpp 负责空闲块、引用计数和分配约束；设备侧 CacheEngine 决定具体张量布局。V4 的缓存还涉及模型专用格式和状态，不能用普通 GQA 的 K/V 数组推断其字节数。本课片段仅解释地址翻译，没有实现上游分页算子、并发锁或完整缓存生命周期。

TRY IT YOURSELF

动手想一想

设 block size 为 4，某请求 block table 为 [7,2,9]。计算第 0、5、10 个 token 的物理地址，再说明第 12 个 token 到来时需要做什么。