主题
PagedAttention 设计思想
白板导读
上一节我们花了大量篇幅证明了一个结论：传统 KV Cache 管理方案存在严重的显存浪费问题——87.5% 的预分配空间可能根本用不上。现在，解决方案来了。vLLM 的 PagedAttention 并不是凭空发明的全新概念，而是从计算机科学史上最经典的设计之一——操作系统的虚拟内存分页机制中获得的灵感。这一节将完整地展示这个"跨界借鉴"的过程：先回顾 OS 分页机制的核心思想，然后逐一映射到 LLM 推理场景，最后给出 PagedAttention 的完整设计蓝图。理解了这个映射关系，你就掌握了面试中关于 PagedAttention 的核心答案。
2.1 操作系统虚拟内存：灵感来源
问题的同构性
让我们先看一个有趣的对比：
操作系统面临的问题（1960s）：
进程 A 需要 100MB 内存
进程 B 需要 50MB 内存
进程 C 需要 200MB 内存
物理内存总共 256MB
如果给每个进程分配连续的物理内存：
- 进程 A 占 [0, 100MB)
- 进程 B 占 [100, 150MB)
- 进程 C 放不下！[150, 256MB) 只有 106MB < 200MB ❌
但实际上 A 可能只用了 30MB，B 只用了 10MB
→ 大量空闲内存被"锁死"在已分配区域内 → 无法给 C 使用LLM 推理面临的问题（2020s）：
请求 A 的 KV Cache 需要 2000 tokens
请求 B 的 KV Cache 需要 500 tokens
请求 C 的 KV Cache 需要 3000 tokens
GPU 显存总共能存 8000 tokens 的 KV Cache
如果给每个请求预分配最大序列长度的连续空间 (max=8192):
- 请求 A 预分配 8192 tokens
- 请求 B 预分配 8192 tokens
- 请求 C 无法分配！只剩空位不够 8192 ❌
实际上 A 只用了 2000，B 只用了 500
→ 大量预分配空间被浪费 → 无法容纳更多请求这两个问题结构完全相同：都是固定大小/连续分配导致的资源利用效率低下。操作系统工程师们在 1960 年代就解决了这个问题，他们的方案就是分页（Paging）。
OS 分页机制核心思想
分页机制的精髓可以概括为三步：
第一步：切分 将物理内存划分为固定大小的页框（Page Frame），通常为 4KB：
物理内存 (64KB 示例):
┌──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┬──────────┐
│ Frame 0 │ Frame 1 │ Frame 2 │ Frame 3 │ Frame 4 │ Frame 5 │ Frame 6 │ Frame 7 │
│ 4KB │ 4KB │ 4KB │ 4KB │ 4KB │ 4KB │ 4KB │ 4KB │
└──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┴──────────┘第二步：映射
每个进程拥有自己的逻辑地址空间（虚拟地址），通过页表（Page Table） 映射到离散的物理页框：
进程 A 的地址空间 (需要 12KB = 3 页):
逻辑地址: 页表: 物理内存:
[Page 0] ──────→ Frame 2 ─────────┐
[Page 1] ──────→ Frame 5 │
[Page 2] ──────→ Frame 0 ────────┘
注意：Frame 2、5、0 在物理上不连续！但这完全没问题。
进程 A 根本不需要知道自己的数据在物理内存的哪个位置。第三步：按需分配与回收
- 进程申请内存时，OS 分配空闲的 Page Frame 并更新页表
- 进程释放内存时，OS 回收 Page Frame 供其他进程使用
- 不再需要连续的大块内存！
分页解决碎片化的原理
分页后的内存布局:
Frame 0: [进程A-P0]
Frame 1: [进程C-P0]
Frame 2: [进程A-P1]
Frame 3: [进程B-P0]
Frame 4: [进程C-P1]
Frame 5: [进程A-P2]
Frame 6: [空闲]
Frame 7: [进程C-P2]
外部碎片 = 0！（因为所有 Frame 大小相同，任何空闲 Frame 都能分配）
内部碎片 ≤ (PageSize - 1)，即最多浪费 4095 字节（一页的最后一部分）
对比传统连续分配:
外部碎片：可能有大量无法使用的空洞
内部碎片：可能很大（整个分区未填满）2.2 从 OS 分页到 PagedAttention 的精确映射
现在我们把 OS 的分页思想逐项映射到 vLLM 的 KV Cache 管理场景。
完整映射对照表
| 操作系统概念 | PagedAttention 对应 | 具体含义 |
|---|---|---|
| 物理内存 (Physical Memory) | GPU VRAM（显存） | 存储数据的实际硬件 |
| 页 / 页框 (Page / Frame) | Block（默认 16 tokens） | 固定大小的基本存储单元 |
| 页面大小 (Page Size) | Block Size（token 数） | 每个 Block 存储多少 token 的 KV |
| 进程地址空间 (Process Address Space) | 一个 Sequence（一次请求） | 一个逻辑上的连续实体 |
| 页表 (Page Table) | Block Table | 记录逻辑 Block → 物理 Block 的映射 |
| 缺页中断 (Page Fault) | Block 分配请求 | 新 token 到来时申请新 Block |
| 页面回收 (Page Eviction) | Block 释放 | 序列结束时归还 Block |
| 交换到磁盘 (Swap to Disk) | Swap 到 CPU 内存 | GPU 不够时将 KV Cache 暂存到 CPU RAM |
| 从磁盘换入 (Swap In) | 从 CPU 换回 GPU | 资源充足时恢复 KV Cache |
| 共享页面 (Shared Pages) | Prefix Caching（前缀缓存共享） | 多个请求共享相同的 System Prompt KV |
| 写时复制 (Copy-on-Write) | Copy-on-Write | 共享前缀时不复制，修改时才复制 |
Block 的具体设计
PagedAttention 中最基本的存储单位是 Block。每个 Block 是一个固定的二维张量，用于存储一段连续 token 的 KV Cache：
python
"""
PagedAttention Block 数据结构定义
"""
import torch
from dataclasses import dataclass
@dataclass
class Block:
"""一个 Block：存储固定数量 token 的 KV Cache"""
block_id: int # 全局唯一编号
ref_count: int = 0 # 引用计数（用于 Prefix Sharing 和 GC）
device: str = "cuda:0" # 所在设备
# 实际的 KV 数据 (在 vLLM 内部是 CacheEngine 管理)
# 形状: [num_layers, 2, num_kv_heads, block_size, head_dim]
# num_layers: Transformer 层数
# 2: K 和 V
# num_kv_heads: KV 头数 (GQA 后的数量)
# block_size: 默认 16
# head_dim: 每个头的维度 (如 128)
# 全局配置
BLOCK_SIZE = 16 # 默认值，可通过 --block-size 参数修改
def calc_block_size_bytes(
num_layers: int,
num_kv_heads: int,
head_dim: int,
dtype_bytes: int = 2,
block_size: int = BLOCK_SIZE,
) -> int:
"""
计算单个 Block 的字节大小
公式: block_bytes = layers × 2(KV) × kv_heads × block_size × head_dim × dtype
"""
return (
num_layers
* 2 # K + V
* num_kv_heads
* block_size # 每个存 16 个 token
* head_dim
* dtype_bytes
)
# 以 Llama 3 8B 为例计算
llama_block_bytes = calc_block_size_bytes(
num_layers=32,
num_kv_heads=8,
head_dim=128,
dtype_bytes=2,
block_size=16,
)
print(f"Llama 3 8B 单个 Block 大小: {llama_block_bytes:,} bytes "
f"({llama_block_bytes/1024:.1f} KB)")
# 输出: Llama 3 8B 单个 Block 大小: 131,072 bytes (128.0 KB)
# RTX 4090 (24GB) 能放多少个 Block？
gpu_memory_for_kv_gb = 8 # 假设 8GB 用于 KV Cache
num_blocks = gpu_memory_for_kv_gb * 1024**3 // llama_block_bytes
print(f"RTX 4090 用 8GB 显存可放 {num_blocks:,} 个 Block")
print(f" 这些 Block 可支持的最大 Token 数: {num_blocks * BLOCK_SIZE:,}")
print(f" 如果平均每请求 512 tokens: 最大并发 ≈ {num_blocks * BLOCK_SIZE // 512} 个请求")输出：
Llama 3 8B 单个 Block 大小: 131,072 bytes (128.0 KB)
RTX 4090 用 8GB 显存可放 65,536 个 Block
这些 Block 可支持的最大 Token 数: 1,048,576
如果平均每请求 512 tokens: 最大并发 ≈ 32,768 个请求注意：这是理论最大值。实际并发数还受限于
--max-num-seqs参数和模型 forward pass 本身的计算时间。但即使打折扣，PagedAttention 的并发能力也远超传统方案。
2.3 Block Table 数据结构
每个正在处理的 Sequence（请求）都维护一张 Block Table，记录它的 KV Cache 分别存储在哪些物理 Block 上。
python
"""
Block Table 数据结构与操作演示
"""
from typing import List, Optional
class BlockTable:
"""
Block Table: 一个序列的逻辑 Block → 物理 Block 映射表
例如，一个长度为 50 的序列 (block_size=16):
逻辑 Block 0 (tokens 0-15) → 物理 Block #3
逻辑 Block 1 (tokens 16-31) → 物理 Block #7
逻辑 Block 2 (tokens 32-47) → 物理 Block #12
逻辑 Block 3 (tokens 48-49) → 物理 Block #21 (只用了 2/16 个位置)
"""
def __init__(self, seq_id: int, block_size: int = 16):
self.seq_id = seq_id
self.block_size = block_size
self.mapping: List[int] = [] # mapping[i] = 第 i 个逻辑块的物理 Block ID
@property
def num_logical_blocks(self) -> int:
return len(self.mapping)
@property
def seq_length(self) -> int:
"""当前序列的实际 token 数量（最后一个 Block 可能未满）"""
if not self.mapping:
return 0
return (self.num_logical_blocks - 1) * self.block_size + self._last_block_used
@property
def _last_block_used(self) -> int:
"""最后一个 Block 中已使用的 token 数（需要在运行时追踪）"""
return self.block_size # 简化：假设总是满的（实际由引擎追踪）
def append_block(self, physical_block_id: int):
"""追加一个新的物理 Block 映射"""
self.mapping.append(physical_block_id)
def get_physical_blocks(self) -> List[int]:
"""获取所有已映射的物理 Block ID 列表"""
return list(self.mapping)
# ===== 使用示例 =====
def demo_block_table():
"""演示 Block Table 如何随着序列增长而扩展"""
bt = BlockTable(seq_id="req-001", block_size=16)
print("Block Table 演示:")
print("=" * 55)
print(f"{'步骤':>4} {'操作':>15} {'逻辑块':>8} {'物理块ID':>12} "
f"{'序列长度':>10} {'占用Block数':>10}")
print("-" * 55)
steps = [
("初始", "新请求到达", [], "-", 0, 0),
("1", "处理前 20 tok", [3, 7], "[3, 7]", 20, 2),
("2", "增长到 45 tok", [3, 7, 12, 21], "[3,7,12,21]", 45, 4),
("3", "继续到 100 tok", [3,7,12,21,33,45,58], "[...]", 100, 7),
]
for step, action, mapping, mapping_str, length, count in steps:
if step != "初始":
for bid in mapping[len(bt.mapping):]:
bt.append_block(bid)
print(f"{step:>4} {action:>15} {mapping_str:>8} {count:>10} "
f"{length:>10} {count:>10}")
if __name__ == "__main__":
demo_block_table()输出：
=======================================================
步骤 操作 逻辑块 物理块ID 序列长度 占用Block数
-------------------------------------------------------
0 新请求到达 [] - 0 0
1 处理前 20 tok [3, 7] [3, 7] 20 2
2 增长到 45 tok [3, 7, 12, 21] [3,7,12,21] 45 3
3 继续到 100 tok [...] ... 100 7关键观察
物理 Block 可以不连续：逻辑 Block 0→1→2 对应物理 Block 3→7→12，中间隔了 4、5、6、8、9、10、11 等。这完全不影响正确性——Attention 计算时会根据 Block Table 收集分散的数据。
按需增长：序列开始时只有 0 个 Block，每增加约 16 个 token 就追加一个 Block。不会预先分配。
最后一个 Block 可能不满：100 个 token 占用了 7 个 Block（容量 112），最后一块有 12 个位置空闲——这就是内部碎片，但最多浪费
(block_size - 1)个 token 的空间，非常可控。
2.4 Block Manager（块管理器）
Block Manager 是 PagedAttention 的"内存管理器"，负责 Block Pool 的维护和分配/释放操作。它是整个系统的核心组件之一。
Block Pool 模型
Block Pool (GPU 上的所有可用 Block)
┌──────────────────────────────────────────────────────────────┐
│ │
│ [0][1][2][3][4][5][6][7][8][9][10][11]...[N-2][N-1] │
│ ↑ │
│ └── free_list: [0,1,2,4,6,8,9,10,11,...] │
│ 已分配: [3→Seq-A, 5→Seq-B, 7→Seq-C, ...] │
│ │
│ 总 Block 数 N = gpu_memory_for_kv / single_block_size │
│ │
└──────────────────────────────────────────────────────────────┘BlockManager 核心接口
python
"""
BlockSpaceManager: PagedAttention 的块管理器
简化版实现（vLLM 实际源码更复杂，包含 swap、copy-on-write 等）
"""
from enum import Enum
from typing import List, Dict, Set, Optional, Tuple
class BlockStatus(Enum):
FREE = "free"
ALLOCATED = "allocated"
class BlockAllocator:
"""Block 分配器：管理一个 Block Pool"""
def __init__(self, num_blocks: int, block_size: int = 16):
self.num_blocks = num_blocks
self.block_size = block_size
# 所有 Block 的状态
self.status: List[BlockStatus] = [BlockStatus.FREE] * num_blocks
# 空闲列表（用于快速分配）
self.free_list: Set[int] = set(range(num_blocks))
# 引用计数（用于共享检测和垃圾回收）
self.ref_counts: Dict[int, int] = {i: 0 for i in range(num_blocks)}
@property
def num_free(self) -> int:
return len(self.free_list)
@property
def num_allocated(self) -> int:
return self.num_blocks - self.num_free
def allocate(self, count: int = 1) -> Optional[List[int]]:
"""
从空闲池中分配指定数量的 Block
Returns: 分配的 Block ID 列表，或 None（如果空间不足）
"""
if len(self.free_list) < count:
return None # OOM!
allocated = []
for _ in range(count):
block_id = self.free_list.pop() # 取出一个空闲 Block
self.status[block_id] = BlockStatus.ALLOCATED
self.ref_counts[block_id] = 1
allocated.append(block_id)
return allocated
def free(self, block_ids: List[int]):
"""释放指定的 Block 回空闲池"""
for bid in block_ids:
if self.status[bid] == BlockStatus.ALLOCATED:
self.status[bid] = BlockStatus.FREE
self.free_list.add(bid)
self.ref_counts[bid] = 0
def can_allocate(self, count: int) -> bool:
"""检查是否有足够的空闲 Block"""
return len(self.free_list) >= count
def get_stats(self) -> dict:
"""返回统计信息"""
return {
"total_blocks": self.num_blocks,
"free_blocks": self.num_free,
"allocated_blocks": self.num_allocated,
"utilization_pct": round(
self.num_allocated / self.num_blocks * 100, 1
),
"free_ratio": round(
self.num_free / self.num_blocks * 100, 1
),
}
class BlockSpaceManager:
"""完整的块空间管理器（管理所有 Sequence 的 Block 分配）"""
def __init__(self, block_size: int = 16, num_gpu_blocks: int = 10000,
num_cpu_blocks: int = 2048):
self.block_size = block_size
self.gpu_allocator = BlockAllocator(num_gpu_blocks, block_size)
self.cpu_allocator = BlockAllocator(num_cpu_blocks, block_size)
# 每个 Sequence 的 Block Table
self.block_tables: Dict[str, List[int]] = {}
def allocate_seq(self, seq_id: str, num_tokens: int) -> bool:
"""
为新序列分配 Block
Args:
seq_id: 请求的唯一标识
num_tokens: 初始 token 数
Returns: 是否分配成功
"""
num_blocks_needed = (num_tokens + self.block_size - 1) // self.block_size
blocks = self.gpu_allocator.allocate(num_blocks_needed)
if blocks is None:
return False # GPU 空间不足
self.block_tables[seq_id] = blocks
return True
def grow_seq(self, seq_id: str, new_total_tokens: int) -> bool:
"""序列增长时追加分配 Block"""
current_blocks = len(self.block_tables.get(seq_id, []))
needed_blocks = (new_total_tokens + self.block_size - 1) // self.block_size
additional = needed_blocks - current_blocks
if additional <= 0:
return True # 不需要额外分配
new_blocks = self.gpu_allocator.allocate(additional)
if new_blocks is None:
return False # 无法增长（GPU 满了）
self.block_tables[seq_id].extend(new_blocks)
return True
def free_seq(self, seq_id: str):
"""释放序列的所有 Block"""
if seq_id in self.block_tables:
self.gpu_allocator.free(self.block_tables[seq_id])
del self.block_tables[seq_id]
def get_seq_block_table(self, seq_id: str) -> List[int]:
"""获取序列的 Block Table"""
return self.block_tables.get(seq_id, [])
def snapshot(self) -> dict:
"""生成当前状态的快照"""
return {
"gpu": self.gpu_allocator.get_stats(),
"active_sequences": len(self.block_tables),
"sequences": {
sid: tbl for sid, tbl in self.block_tables.items()
}
}
# ===== 演示 =====
def demo_block_manager():
"""演示 Block Manager 的分配/释放过程"""
mgr = BlockSpaceManager(block_size=16, num_gpu_blocks=100)
operations = [
("分配 Seq-A (20 tok)", "alloc", "seq-a", 20),
("分配 Seq-B (50 tok)", "alloc", "seq-b", 50),
("分配 Seq-C (100 tok)", "alloc", "seq-c", 100),
("Seq-A 增长到 80 tok", "grow", "seq-a", 80),
("释放 Seq-B", "free", "seq-b", None),
("分配 Seq-D (200 tok)", "alloc", "seq-d", 200),
]
print("Block Manager 运行演示")
print("=" * 65)
print(f"{'操作':<25} {'类型':<8} {'结果':<30} {'GPU空闲':>8}")
print("-" * 65)
for desc, op_type, seq_id, tokens in operations:
if op_type == "alloc":
success = mgr.allocate_seq(seq_id, tokens)
result = "✅ 成功" if success else "❌ 失败(OOM)"
elif op_type == "grow":
success = mgr.grow_seq(seq_id, tokens)
result = "✅ 成功" if success else "❌ 失败(无法增长)"
else:
mgr.free_seq(seq_id)
result = "✅ 已释放"
stats = mgr.snapshot()["gpu"]
print(f"{desc:<25} {op_type:<8} {result:<30} {stats['free_blocks']:>8}")
print("\n最终状态:")
snap = mgr.snapshot()
print(f" GPU 利用率: {snap['gpu']['utilization_pct']}%")
print(f" 活跃序列: {snap['active_sequences']}")
for sid, tbl in snap["sequences"].items():
print(f" {sid}: {len(tbl)} Blocks → IDs {tbl}")
if __name__ == "__main__":
demo_block_manager()输出：
Block Manager 运行演示
=================================================================
类型 结果 GPU空闲
-----------------------------------------------------------------
分配 Seq-A (20 tok) alloc ✅ 成功 99
分配 Seq-B (50 tok) alloc ✅ 成功 97
分配 Seq-C (100 tok) alloc ✅ 成功 91
Seq-A 增长到 80 tok grow ✅ 成功 89
释放 Seq-B free ✅ 已释放 93
分配 Seq-D (200 tok) alloc ✅ 成功 81
最终状态:
GPU 利用率: 19.0%
活跃序列: 3
seq-a: 5 Blocks → IDs [0, 1, 2, 3, 4]
seq-c: 7 Blocks → IDs [5, 6, 7, 8, 9, 10, 11]
seq-d: 13 Blocks → IDs [12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]2.5 为什么固定大小 Block 能消除碎片化？
这是 PagedAttention 最精妙的设计选择之一。让我们用一个具体的例子来证明：
场景：4 个请求同时运行，它们的序列长度分别是 23, 67, 15, 41 (block_size=16)
传统方案 (max_seq_len=128, 连续分配):
请求 A (23): ████████████████████░░░░...░░ (预分配 128, 实际用 23, 浪费 82%)
请求 B (67): ██████████████████████████████░░...░░ (预分配 128, 浪费 48%)
请求 C (15): ████████████░░░░░░░...░░ (预分配 128, 浪费 88%)
请求 D (41): █████████████████████████████░░...░░ (预分配 128, 浪费 68%)
总预分配: 512 tokens 空间
实际使用: 146 tokens
浪费: 366 tokens (71.5%)
PagedAttention 方案 (block_size=16):
请求 A (23): [Blk0][Blk1] (2 块, 最后一块用了 7/16)
请求 B (67): [Blk2][Blk3][Blk4][Blk5] (4 块, 最后一块用了 3/16)
请求 C (15): [Blk6] (1 块, 用了 15/16)
请求 D (41): [Blk7][Blk8][Blk9] (3 块, 最后一块用了 9/16)
总分配: 10 块 × 16 = 160 tokens 空间
实际使用: 146 tokens
浪费: 14 tokens (仅来自内部碎片!)
浪费率: 14/160 = 8.75% (vs 传统方案的 71.5%)数学证明：
对于 $n$ 个序列，第 $i$ 个序列的实际长度为 $l_i$，Block 大小为 $b$：
传统方案总浪费： $$W_{traditional} = \sum_{i=1}^{n}(L_{max} - l_i) = n \cdot L_{max} - \sum_{i=1}^{n} l_i$$
PagedAttention 总浪费（仅内部碎片）： $$W_{paged} = \sum_{i=1}^{n}\left(b - 1\right) = n \cdot (b - 1)$$ (最坏情况：每个序列的最后一块都只用了 1 个 token)
效率提升比： $$\frac{W_{traditional}}{W_{paged}} = \frac{n \cdot L_{max} - \sum l_i}{n \cdot (b - 1)}$$
当 $L_{max} \gg b$ 且 $\sum l_i \ll n \cdot L_{max}$ 时（即大多数请求远短于最大限制），这个比值可以达到 数十甚至上百倍。
以我们的例子代入：
- $L_{max}=128$, $b=16$, $n=4$, $\sum l_i=146$
- $W_{trad} = 4×128 - 146 = 366$
- $W_{paged} = 4×15 = 60$
- 效率提升 = 366/60 = 6.1x（减少到原来的 1/6）
要点回顾
| 维度 | 关键要点 |
|---|---|
| 灵感来源 | OS 虚拟内存分页机制（1960s 经典设计），问题结构完全同构 |
| 核心映射 | Physical Memory→VRAM, Page→Block(16tok), Process→Sequence, PageTable→BlockTable |
| Block 设计 | 固定大小（默认 16 tokens/KV），Llama 3 8B 每块 128KB |
| Block Table | 每个序列维护 list[int] 映射逻辑块→物理块，物理块可不连续 |
| Block Manager | 维护 Free Pool + 分配/释放 API + 引用计数 |
| 碎片消除 | 外部碎片=0（固定大小 Block），内部碎片≤(b-1)/avg_len |
| 效率提升 | 相比传统预分配，浪费率从 ~70% 降至 ~10%，提升 6-10x |
| 下一章预告 | PagedAttention 不仅解决了静态内存管理，还实现了 Prefix Caching（前缀共享） 和 Copy-on-Write 两个高级特性 |
一句话总结：PagedAttention 的本质是将操作系统的分页思想迁移到了 GPU KV Cache 管理领域。通过将 KV Cache 切分为固定大小的 Block、用 Block Table 做非连续映射、按需分配和释放，它将显存利用率从传统的 50-65% 提升到了 90-98%。这不是一个小的优化，而是一个架构级的范式转变——它让 vLLM 能够在同样的硬件上服务数倍于传统方案的并发请求数。