LLM 推理服务线上最大的浪费：静态 batching。一个 batch 里 8 个请求，序列长度从 12 到 2048——短的 12 个 token 2ms 就算完了，然后等长的那条跑完。190ms 算力闲置，GPU/NPU 空转。Continuous Batching 的解法：不等——哪个请求算完了，立刻把它的位置让给新请求。batch 永不满，永不空转。

静态 batching 的吞吐 = avg_seq_len / max_seq_len × peak_throughput。2048 max, 512 avg → 利用率 25%。Continuous Batching → 利用率 85-95%。

核心机制：Request Slot 的抢占与填充

Continuous Batching 把 “batch” 的概念从静态槽位变成动态 slot 池。每个 slot 绑定一个正在运行的请求。请求完成后 slot 释放，调度器从等待队列拉下一个请求填入。

# cann-recipes-infer/continuous_batching/scheduler.py

from dataclasses import dataclass
from typing import List, Optional

@dataclass
class Request:
    id: int
    prompt: List[int]          # 输入的 token 序列
    max_new_tokens: int        # 最大生成 token 数
    temperature: float = 1.0
    generated: List[int] = None  # 已生成的 token
    state: str = 'pending'      # pending/running/done

@dataclass
class Slot:
    """一个 batch 位置——持续占有的 GPU 资源"""
    index: int                # 在 batch 中的索引 (0..max_batch-1)
    request: Optional[Request] = None
    kv_cache_offset: int = 0  # KV Cache 分页的起始地址
    kv_cache_pages: int = 0  # 已占据的 page 数
    is_running: bool = False

class ContinuousBatchingScheduler:
    def __init__(self, max_batch_size=64, max_seq_len=4096,
                 page_size=16, kv_cache_total_pages=4096):
        self.max_batch = max_batch_size
        self.max_seq_len = max_seq_len
        self.page_size = page_size    # 每个 page 存 16 个 token 的 KV cache
        self.total_pages = kv_cache_total_pages

        self.slots = [Slot(i) for i in range(max_batch_size)]
        self.free_pages = list(range(kv_cache_total_pages))  # 空闲页栈
        self.waiting_queue = []      # 等待队列 [(priority, request)]

    def schedule(self, new_requests: List[Request]) -> List[int]:
        """返回需要运行的 slot 索引列表"""
        # 步骤 1：新请求入队
        for req in new_requests:
            self.waiting_queue.append((0, req))  # priority=0（FIFO）

        # 步骤 2：释放已完成的 slot
        for slot in self.slots:
            if slot.request and slot.request.state == 'done':
                self._free_slot(slot)

        # 步骤 3：填充空闲 slot
        free_slots = [s for s in self.slots if not s.is_running]
        for slot in free_slots:
            if not self.waiting_queue:
                break

            _, req = self.waiting_queue.pop(0)

            # 分配 KV cache 页
            needed_pages = (len(req.prompt) + req.max_new_tokens + self.page_size - 1) // self.page_size
            if len(self.free_pages) < needed_pages:
                # 不够 page → 请求继续等待
                self.waiting_queue.insert(0, (0, req))
                continue

            slot.request = req
            slot.kv_cache_offset = self.free_pages[0] * self.page_size * self.kv_dim * 2
            slot.kv_cache_pages = needed_pages
            slot.is_running = True
            req.state = 'running'

            # 分配 page
            pages = self.free_pages[:needed_pages]
            del self.free_pages[:needed_pages]
            slot.allocated_pages = pages

        # 步骤 4：返回活跃 slot
        return [s.index for s in self.slots if s.is_running]

    def _free_slot(self, slot: Slot):
        """释放 slot 的所有资源"""
        self.free_pages.extend(slot.allocated_pages)
        slot.request = None
        slot.is_running = False
        slot.allocated_pages = []

KV Cache 的分页管理

PagedAttention 的 KV 缓存不是连续分配——是按页分配的，物理地址不连续。好处：碎片化少（一个请求的 2048 个 token KV cache 可以分配在 128 个不连续的 16-page 块中）、重用率更高（前缀相同的请求共享物理 page）。

# cann-recipes-infer/continuous_batching/kv_cache.py

class PagedKVCache:
    """分页管理的 KV Cache，每个 page 存储 page_size 个 token 的 K/V"""

    def __init__(self, num_layers, num_heads, head_dim,
                 total_pages, page_size, dtype):
        self.num_layers = num_layers
        self.num_heads = num_heads
        self.head_dim = head_dim
        self.page_size = page_size

        # 物理存储：[num_layers, 2, total_pages, page_size, num_heads, head_dim]
        # 2 = [K_cache, V_cache]
        self.cache = torch.empty(
            num_layers, 2, total_pages, page_size,
            num_heads, head_dim, dtype=dtype, device='npu'
        )

        # Page 表：逻辑 page → 物理 page（支持不连续映射）
        self.page_table = {}  # request_id → [physical_page_ids]

    def write_kv(self, layer_id, request_id, token_pos, k, v):
        """写入一个 token 的 K/V 到分页缓存"""
        pages = self.page_table[request_id]
        page_idx = token_pos // self.page_size    # 逻辑 page 号
        offset = token_pos % self.page_size        # page 内偏移
        phys_page = pages[page_idx]

        self.cache[layer_id, 0, phys_page, offset] = k  # K
        self.cache[layer_id, 1, phys_page, offset] = v  # V

    def read_kv(self, layer_id, request_id, start, end):
        """读取 [start, end) 范围的 K/V（可能跨页）"""
        pages = self.page_table[request_id]
        k_chunks, v_chunks = [], []

        pos = start
        while pos < end:
            page_idx = pos // self.page_size
            offset = pos % self.page_size
            chunk_end = min(end, (page_idx + 1) * self.page_size)

            phys_page = pages[page_idx]
            k_chunks.append(
                self.cache[layer_id, 0, phys_page, offset:chunk_end - pos + offset]
            )
            v_chunks.append(
                self.cache[layer_id, 1, phys_page, offset:chunk_end - pos + offset]
            )

            pos = chunk_end

        return torch.cat(k_chunks, dim=0), torch.cat(v_chunks, dim=0)

    def allocate_pages(self, request_id, num_pages):
        """为请求分配页"""
        pages = allocator.allocate(num_pages)
        self.page_table[request_id] = pages
        return pages

    def free_pages(self, request_id):
        """释放请求占用的页"""
        pages = self.page_table.pop(request_id)
        allocator.free(pages)

Attention 计算：混合 Prefill 和 Decode

Continuous Batching 的核心难点：batch 中混合了 prefill 和 decode 请求。Prefill 请求一次处理所有 prompt token（计算量大），decode 请求每次只处理 1 个 token（很小但频繁）。

# cann-recipes-infer/attention/mixed_attention.py

def mixed_prefill_decode_attention(
    Q, K, V,                  # [total_tokens, num_heads, head_dim]
    request_sizes,            # [num_requests]: 每个请求的 token 数
    request_states,           # ['prefill', 'decode', ...]
    kv_cache: PagedKVCache,
    softmax_scale: float
):
    """
    混合 prefill/decode 的 attention 计算
    Q 的形状：prefill 请求贡献 seq_len 个 query，decode 请求贡献 1 个 query
    total_tokens = sum(prefill_seq_lens) + num_decode_requests
    """
    # 步骤 1：分离 prefill 和 decode 请求
    prefill_indices = [i for i, s in enumerate(request_states) if s == 'prefill']
    decode_indices = [i for i, s in enumerate(request_states) if s == 'decode']

    # 步骤 2：Prefill attention——FlashAttention 处理长序列
    if prefill_indices:
        prefill_Q_sections = []
        prefill_KV_sections = []
        token_offset = 0

        for i in prefill_indices:
            n_tokens = request_sizes[i]
            # 每个 prefill 请求独立做 attention（不能混合不同请求的 KV）
            prefill_Q = Q[token_offset:token_offset + n_tokens]
            prefill_K = K[token_offset:token_offset + n_tokens]
            prefill_V = V[token_offset:token_offset + n_tokens]

            # FlashAttention：O(N²×D) 计算，O(N×D) 内存
            output = flash_attention(prefill_Q, prefill_K, prefill_V,
                                     softmax_scale=softmax_scale)

            prefill_Q_sections.append(output)
            token_offset += n_tokens

        prefill_outputs = torch.cat(prefill_Q_sections, dim=0)
    else:
        prefill_outputs = None

    # 步骤 3：Decode attention——PagedAttention 处理单 token
    if decode_indices:
        decode_outputs = []
        token_offset = sum(request_sizes[i] for i in prefill_indices)

        for i in decode_indices:
            # 每个 decode 请求只处理一个 query
            q = Q[token_offset:token_offset + 1]  # [1, num_heads, head_dim]

            # 从分页 KV cache 读取全部历史 KV
            k, v = kv_cache.read_kv(
                request_id=i, start=0, end=request_sizes[i]
            )

            # PagedAttention：O(N×D) 计算（N=历史长度, 只乘一次）
            output = paged_attention(q, k, v, softmax_scale=softmax_scale)
            decode_outputs.append(output)
            token_offset += 1

        decode_outputs = torch.cat(decode_outputs, dim=0)
    else:
        decode_outputs = None

    # 合并输出
    if prefill_outputs is not None and decode_outputs is not None:
        return torch.cat([prefill_outputs, decode_outputs], dim=0)
    return prefill_outputs or decode_outputs

Prefill 和 decode 分开处理的原因：prefill 用 FlashAttention（块内计算，吞吐优化），decode 用 PagedAttention（逐 token 加载历史 KV，延迟优化）。两个 kernel 不能混用——混合只会拖慢两者。

性能对比

LLaMA-7B on 8× Ascend 910 NPU，请求 Poisson arrival (λ=50 req/s)，mean seq=512

| 策略 | 吞吐 (req/s) | TPOT (ms) | 显存利用率 | 平均 batch 大小 |
|------|-------------|----------|-----------|----------------|
| 静态 batching, bs=8  | 12.3  | 1,420 | 25%  | 8.0 |
| 静态 batching, bs=32 | 38.7  | 3,210 | 48%  | 32.0 |
| 静态 batching, bs=64 | 44.2  | 4,890 | 31%  | 64.0 |
| Continuous Batching  | 482   | 187   | 88%  | 53.2 (动态) |

吞吐差异：44.2 vs 482 → 10.9×
延迟差异：4,890ms vs 187ms → 26×

为什么静态 bs=64 只有 31% 显存利用率？因为转化为实际活跃 token 时只有 ¾ 是 prefill/decoding token（剩余是 padding）。Continuous Batching 没有 padding。

踩坑一：Prefix Caching 与 Page Sharing 的竞态

两个请求共享相同的 system prompt（“You are a helpful assistant…”）。PagedAttention 可以让它们共享同一个 KV cache page——前缀一样，不需要各自存。

# ❌ 两个请求各自分配 KV cache page（浪费）
req1 = allocate_pages(prompt="You are a helpful assistant..." + "Task A")
req2 = allocate_pages(prompt="You are a helpful assistant..." + "Task B")
# "You are a helpful assistant..." = 7 tokens → 2 pages
# 分配了 4 pages → 浪费 2 pages（前缀 7 tokens 存了两遍）

# ✅ Prefix Caching：共享前缀的 KV cache
prefix_hash = hash("You are a helpful assistant...")
if prefix_hash in prefix_cache:
    shared_pages = prefix_cache[prefix_hash]  # 复用！
    req1_pages = shared_pages + alloc.allocate(needed_for_task_A)
    req2_pages = shared_pages + alloc.allocate(needed_for_task_B)
    # 前缀的 2 pages 被两个请求共享 → 省 2 pages
else:
    shared_pages = alloc.allocate(needed_for_prefix)
    prefix_cache[prefix_hash] = shared_pages

# 关键：前缀 page 的引用计数
# 释放 req1 时不能释放共享 page（req2 还在用）
# 必须 refcnt ≥ 1 才能释放

踩坑二：Prefill 长请求占满 batch → Decode 饥饿

Pre-PreFill 阶段：一个请求的 prompt 有 4096 个 token → FlashAttention 在 8 张 NPU 上跑 4 秒。4 秒内没有 decode 请求被服务→decode 饥饿。TPOT（Time Per Output Token）因为这个 4 秒的 prefill 从 187ms 涨到 4,187ms。

# ❌ 一个长 prefill 占满所有 slot
slot[0]: prefill(4096 tokens) → 4 seconds
slot[1..63]: 空 → decode 请求无法进入（等 prefill 完成分配 KV pages）

# ✅ Prefill 分块（Chunked Prefill）：长 prompt 切成多段
# 每段 512 tokens，中间插入 decode 请求的 service window

def chunked_prefill(request, chunk_size=512):
    prompt = request.prompt
    total_chunks = (len(prompt) + chunk_size - 1) // chunk_size

    for chunk_id in range(total_chunks):
        chunk_start = chunk_id * chunk_size
        chunk_end = min(chunk_start + chunk_size, len(prompt))
        chunk = prompt[chunk_start:chunk_end]

        # 做一部分 prefill（0.5ms）
        output = flash_attention_chunk(Q[chunk_start:chunk_end], ...)

        # 让出算力给 decode 请求（1ms 的 decode window）
        if chunk_id < total_chunks - 1:
            yield_to_decode_requests(timeout_ms=1.0)

        # 积累 KV cache 并继续
        kv_cache.write(request_id, chunk_start, chunk_end, K, V)

实测：Chunked Prefill 把 TPOT 从 4,187ms 降回 204ms（decode 每 0.5ms prefill 后得到 1ms 的服务窗口）。总吞吐从 482 降到 468 req/s（-3%），但 TPOT 降 20×——用户体验的提升远超 3% 吞吐损失。

踩坑三：KV Cache 页碎片化导致 OOM

64 个请求 × 512 pages/request = 32768 pages。分配和释放随机，高度碎片化——free_pages 列表是碎片分布的，分配 128 个 page 可能找不到连续块（即使总空闲 pages > 128）。

# ❌ 碎片化：128 个 page 散落在 2000 个空闲位置中
# 需要 128 pages → 实际有 2000 free pages → 但连续不足 → OOM

# ✅ 碎片压缩：定期 compact page 表
def compact_page_table(page_table, active_requests):
    """把所有活跃 page 移到连续区域"""
    # 收集所有活跃 page
    active_pages = set()
    for req_id in active_requests:
        active_pages.update(page_table[req_id])

    # 构建新的连续映射
    new_mapping = {}
    new_idx = 0

    for old_page in sorted(active_pages):
        new_mapping[old_page] = new_idx
        kv_cache[new_idx] = kv_cache[old_page]  # 搬数据
        new_idx += 1

    # 更新 page 表
    for req_id in active_requests:
        page_table[req_id] = [new_mapping[p] for p in page_table[req_id]]

    free_pages = list(range(new_idx, total_pages))
    return free_pages, page_table

Compaction 的代价：手动搬 32768 个 page → 32768 × (page_size × num_heads × head_dim × 2 × 2 bytes) = 对于 LLaMA-7B (d=4096, heads=32, head_dim=128): 32768 × 16 × 32 × 128 × 2 × 2 = 8.5GB 数据迁移 → 在 NPU 的 HBM 内部拷贝约 10ms。每个 1000 step 做一次 compact → 额外的 0.001% 时间 → 可忽略。

Continuous Batching 颠覆了 LLM 推理服务的调度范式——不再让短序列等长序列。核心：动态 slot 池 + PagedAttention 分页 KV cache + Prefix Caching 共享前缀 + Chunked Prefill 避免 decode 饥饿。在 8× Ascend 910 NPU 上达到 482 req/s（vs 静态 batching 44.2 req/s = 10.9× 提升），TPOT 从 4890ms 降到 187ms（26× 改善）。三个关键点：Prefix Caching 的引用计数管理（共享 page 不能单独释放）、Chunked Prefill 的长 prompt 分段策略（每 512 token 让出 1ms decode 窗口）、KV Cache 的碎片压缩（定期 compact page 表防 OOM）。