05 · BlockManager：分页 KV Cache
先建立直觉：为什么 KV 不必连续摆放？
如果一个请求的 token 在逻辑上连续，它的 KV Cache 是否也必须占一整段连续 GPU 显存？
先观看这段动画。它把“连续预留为何浪费”“11 个 token 怎样变成三张逻辑页”“物理 block 可以离散”“追加时何时需要新页”以及“共享 prefix 何时释放”串成同一条因果链。
观看时只抓住一个结论：block_table 保存的是“逻辑页顺序 → 物理 block id”的映射；它让 token 的访问顺序保持连续，而不要求物理 KV 地址连续。固定大小页与页表映射正是 PagedAttention 内存管理思想的关键。1
一个请求怎样拿到页
设 block_size = 4。长度为 11 的请求需要 ceil(11 / 4) = 3 个逻辑 block：前两页各放 4 个 token，最后一页放 3 个 token，并留下 1 个空位。这个空位是内部碎片；它没有消失，但代价被限制在最后一页，而不是为每条请求预留最大长度的一整段连续显存。
分配时，BlockManager 从 free_block_ids 取可用物理 id，写入 Sequence 的 block_table，同时把这些 id 视为已用。物理 id 可以是 [7, 2, 14] 这样离散的序列；Attention 路径只要依据 table 取页，逻辑 token 的历史顺序不会丢失。
| 你看到的对象 | 它回答的问题 | 不应混淆为 |
|---|---|---|
block_size | 一张逻辑页最多容纳几个 token？ | 请求的总长度上限 |
seq.block_table | 第 0、1、2 张逻辑页分别在哪个物理 block？ | 一段连续显存地址 |
free_block_ids | 现在还能分配哪些物理页？ | 某个 Sequence 已经拥有的页 |
| 最后一页空位 | 固定页带来的内部碎片有多少？ | 外部碎片或请求失败 |
追加第 5 个 token 时，发生了两件不同的事
对一个长度为 4、block_size = 4 的请求，已有逻辑页已经填满。第 5 个 token 并不是立即“写进缓存”；系统先需要确认它会跨入一张新逻辑页。
can_append()是检查：若追加会跨页，它需要确认空闲队列中仍有可分配 block。may_append()是动作：条件满足后，真正取一个物理 id，并将它追加到block_table。
这两个函数刻意分开，正是为了让调度器能先判断资源是否满足，再改变共享的内存状态。阅读边界条件时，要同时观察 len(seq)、block_size 与“新 token 是已经追加还是尚未追加”。
共享 prefix 为什么不能直接释放
Prefix Cache 可以让多个 Sequence 的 table 指向同一个完整 prefix block。这里的共享不是复制整页 KV，而是多个引用指向同一物理页；因此 block 的 ref_count 必须记录还有多少 Sequence 在使用它。第一个请求结束时，计数从 2 变为 1，物理页仍不能回收；最后一个引用离开后，计数变为 0，id 才能回到 free_block_ids。
这让“分配”“追加”“释放”成为一条完整资源生命周期：
free_block_ids → allocate → seq.block_table → can_append / may_append → ref_count = 0 → deallocate → free_block_ids代码锚点：去哪里验证这条链路
下面是概念化阅读路径，不等同于上游源码的逐行转录。先追一个字段，再看它被谁检查、何时改变，最后回到实验解释状态。
| 阅读锚点 | 先问的问题 | 实验里的可观察结果 |
|---|---|---|
seq.block_table | 某张逻辑页写入了哪个物理 id？ | A 的离散页 id 与逻辑页顺序同时出现。 |
can_append() | 追加前是否有足够的空闲物理页？ | B 填满一页后，先显示检查结果。 |
may_append() | 检查通过后，哪一个 id 被真正加入 table？ | B 从 4 变 5 token，table 多出一个 id。 |
deallocate() 与 ref_count | 何时能把物理页放回 free queue？ | 释放请求后，已用页下降、空闲队列恢复。 |
动手验证：预测 → 运行 → 解释
不要先点击“分配”。先把 token 长度换算成逻辑页，再用实验中的 block table 验证。如果预测错误，重点不是记住答案，而是指出究竟把“逻辑页、物理页、空位、检查和分配”的哪两个概念混在了一起。
| 步骤 | 你要做什么 | 你应该观察什么 |
|---|---|---|
| 1. 预测 | 装载默认任务：block_size=4、A=11 token。先选择 A 需要的 block 数、最后一页空位数；再判断 B 从完整一页追加 1 token 时是否需要新页。 | 使用 ceil(长度 / block_size) 预测页数；区分“逻辑连续”与“物理 id 连续”。 |
| 2. 运行 | 依次分配 A、分配填满页的 B、追加 B 的第 5 个 token。随后分别释放 A 与 B。 | A 的 block_table 为离散 id；B 追加前先检查空闲页，追加后才增加 table 项；释放会改变 free queue。 |
| 3. 解释 | 点击“核对我的预测”，再用一句话说明 B 为什么不能复用原页。 | 用“跨入新逻辑页、can_append()、may_append()、block_table”解释，而不是只说“因为页满了”。 |
当 `block_size=4`、请求长度从 4 增加到 5 时，为什么需要先检查空闲 block？
完成默认对比任务后，把 block_size 改成 8，重新预测 A=11 时的 block 数和最后一页空位；比较两次结果，并解释内部碎片为何变化。
下一节：Prefix Cache