I5Medium★ LLM Serving 必考 · vLLM 核心Part I · 推理生成、解码与量化

PagedAttention 物理块分配与虚拟块表映射

⚡闪卡盲测➔

模拟虚拟块到离散物理 KV 块的按需分页分配、释放与内部碎片上限控制,打破连续显存预留浪费。

⏱️ 时间复杂度: O(新增 Token / block_size)
💾 空间复杂度: O(SeqCount * MaxBlocksPerSeq) 块表映射开销,内部碎片 < block_size / 序列
🎯 免登录实战自测闭环(先做再看答案)
按「机制回忆 → 关键行填空 → 边界反例 → 追问与错题记录」顺序自测,进度自动保存在本地。
Step 1 · 机制口述与数值稳定性自检
Step 2 · 核心代码关键行补全
class PagedKVCacheAllocator:
"""PagedAttention fixed-size physical KV block allocator with virtual-to-physical mapping."""
def __init__(self, num_blocks: int, block_size: int):
self.block_size = block_size
self.free_blocks =
self.block_tables = {} # seq_id -> list of physical block ids
self.seq_lens = {} # seq_id -> active token count
def allocate_tokens(self, seq_id: str, num_new_tokens: int) -> list:
cur_len = self.seq_lens.get(seq_id, 0)
table = self.block_tables.setdefault(seq_id, [])
new_total = cur_len + num_new_tokens
needed_blocks =
while len(table) < needed_blocks:
if not self.free_blocks:
raise MemoryError("Out of physical KV cache blocks")
table.append(self.free_blocks.pop())
self.seq_lens[seq_id] = new_total
return list(table)
def free_sequence(self, seq_id: str) -> None:
table = self.block_tables.pop(seq_id, [])
self.seq_lens.pop(seq_id, None)
# Return physical blocks to free pool
self.free_blocks.extend(reversed(table))
def internal_waste_tokens(self) -> int:
waste = 0
for seq_id, table in self.block_tables.items():
waste += len(table) * self.block_size - self.seq_lens[seq_id]
return waste
Step 3 · 反例与边界断言核对
Step 4 · 面试追问盲答与错题记录
Q1: Beam Search 或并行采样(n > 1)场景下,PagedAttention 如何零拷贝共享前缀 KV?
下一题: Continuous Batching 连续批处理调度器 →
💡

实战一句话记忆口诀

逻辑连续切定长,物理离散按需挂,内部碎片不超一页,外部碎片彻底消

📐 核心数学公式与机理推导

PhysicalAddr(t)=BlockTable[⌊t/B⌋]⋅B+(t mod B)\text{PhysicalAddr}(t) = \mathrm{BlockTable}\left[\lfloor t / B \rfloor\right] \cdot B + (t \bmod B)
### 虚拟分页地址映射与碎片收敛
传统自回归引擎为每条请求按 max_model_len 预先申请连续显存,导致大量未生成的空槽位长期闲置(内部碎片),且不同长度请求释放后造成物理断裂(外部碎片)。
PagedAttention 将逻辑 KV 序列切分为固定大小 BB(如 B=16B=16 tokens)的逻辑块,按需从物理空闲池分配离散物理块:
- 逻辑索引 tt 所属逻辑块号为 ⌊t/B⌋\lfloor t / B \rfloor,块内偏移为 t mod Bt \bmod B;
- 物理空间不必连续,因此完全消除外部碎片;
- 内部碎片最坏情况下只存在于每条序列的最后 1 个块中,严格小于 BB 个 Token。

🔄 张量维度与形状流转说明

seq_id + num_new_tokens -> 计算 needed_blocks = ceil(total / B) -> 按需从 free_blocks 弹出物理块 -> 写入 block_table[seq_id]

🛡️ 数值稳定性自检与边界要点

  • 空闲块不足时必须回滚已弹出的部分块或预先检查总块数差值,避免 OOM 异常时出现物理块泄漏
  • 当多条请求共享系统前缀时,可在物理块上维护引用计数(RefCount > 1),仅在写入分叉时触发 Copy-on-Write

💻 完整参考代码实现

class PagedKVCacheAllocator:
    """PagedAttention fixed-size physical KV block allocator with virtual-to-physical mapping."""
    def __init__(self, num_blocks: int, block_size: int):
        self.block_size = block_size
        self.free_blocks = list(range(num_blocks - 1, -1, -1))
        self.block_tables = {}  # seq_id -> list of physical block ids
        self.seq_lens = {}      # seq_id -> active token count

    def allocate_tokens(self, seq_id: str, num_new_tokens: int) -> list:
        cur_len = self.seq_lens.get(seq_id, 0)
        table = self.block_tables.setdefault(seq_id, [])
        new_total = cur_len + num_new_tokens
        needed_blocks = (new_total + self.block_size - 1) // self.block_size
        while len(table) < needed_blocks:
            if not self.free_blocks:
                raise MemoryError("Out of physical KV cache blocks")
            table.append(self.free_blocks.pop())
        self.seq_lens[seq_id] = new_total
        return list(table)

    def free_sequence(self, seq_id: str) -> None:
        table = self.block_tables.pop(seq_id, [])
        self.seq_lens.pop(seq_id, None)
        # Return physical blocks to free pool
        self.free_blocks.extend(reversed(table))

    def internal_waste_tokens(self) -> int:
        waste = 0
        for seq_id, table in self.block_tables.items():
            waste += len(table) * self.block_size - self.seq_lens[seq_id]
        return waste

🧪 本地测试与正确性断言

可直接复制到本地 Python / Jupyter 验证:

alloc = PagedKVCacheAllocator(num_blocks=6, block_size=4)
t1 = alloc.allocate_tokens("req1", 5)  # needs ceil(5/4) = 2 blocks
t2 = alloc.allocate_tokens("req2", 4)  # needs 1 block
assert len(t1) == 2 and len(t2) == 1
assert len(alloc.free_blocks) == 3
# Internal waste bounded strictly by < block_size per sequence
assert alloc.internal_waste_tokens() == 3
alloc.free_sequence("req1")
assert len(alloc.free_blocks) == 5
print("✓ PagedAttention block allocator assertion passed")

🎯 核心工程追问与标准应答

Q1:Beam Search 或并行采样(n > 1)场景下,PagedAttention 如何零拷贝共享前缀 KV?
不同分支的逻辑块表在分叉之前直接指向同一组物理块,并将这些物理块的引用计数 ref_count 设为分支数。生成到各自不同的分叉块且出现末尾未满块局部写入时,才只复制最后一个共享块(Copy-on-Write)并把旧块引用计数减 1。
⚡
想检验本题的肌肉记忆?进入 3 阶闪卡主动回忆盲测
隐藏答案遮罩,自测:审题锚点 ➔ 数理公式机理 ➔ 工业标杆代码与连环追问。3 分钟攻破认知盲区!
🎯 立即在闪卡中盲测此题➔
← 上一题: Beam Search 束搜索(束宽更新与长度惩罚)返回 Part I 与全部 105 题下一题: Continuous Batching 连续批处理调度器 →