我先交代一下标题里“sl”到底指什么。在项目文档里不同人会把 sl 写作 sequence length序列长度或者 sliding window滑动窗口有些场景下它俩根本就是同一个问题数据不断在尾部追加同时旧数据从头部被淘汰整个工作集像一列火车一样往前平移。无论是 C 后端处理滑动窗口日志还是大模型推理里管理 KV cache只要碰到底层存储的“尾部写、头部丢”模式缓存命中率就成了那个决定系统最终吞吐的关键指标。这篇文章想把这些看似不相关的东西串起来先从 std::deque 的分块实现讲起把它的块表结构、迭代器设计和与 vector 的缓存差异讲清楚再切入 vLLM 的 PagedAttention、滑动窗口注意力循环回收和自动前缀缓存说明 GPU 上的 KV cache 管理其实就是在用更粗的“缓存行”做同一件事。适合两类人看一类是正在做 C 服务性能优化、想搞明白 deque 到底快在哪慢在哪的工程师另一类是刚接触 LLM 推理服务部署、想知道 vLLM 这些优化到底改了什么的人。下面进正题。1. 滑动窗口类负载最容易把缓存命中率击穿的场景1.1 尾部写入、头部淘汰这到底是什么负载先说我踩过的一道坎。有一个日志滚动模块需要把最近 5 分钟的访问事件放在内存里按时间顺序展示老事件过期就移除。我当时图省事直接用 std::vector发现数据量一上来就频繁卡顿换成链表后顺序遍历又慢得离谱最后换 deque 才压住了延迟。后来才明白这类“尾部追加 头部淘汰”的滚动窗口负载对容器的要求其实非常特殊单次操作基本只碰头部和尾部中间数据只是被“路过”而不是被“改写”。如果用 vector瓶颈在于容量到达上限时要整体重新分配把一整段内存搬到新地址旧缓存行、TLB 全部作废移动一次数组代价巨大如果换成链表虽然增删头尾是 O(1)但每个节点独立分配在堆上地址彼此分散顺序访问时预取器基本失效每个节点都可能成为一次 cache miss。deque 的分块思路正好卡在中间内部划分成多个固定大小的连续块块与块之间用映射关系串起来。尾部追加到块内的空位就是普通写入块满了才新申请一块头部淘汰到只剩空块时就把整块还给分配器。这样既避免了大段复制又保留了块内的空间局部性。你可能会问既然中间数据很少访问为什么 deque 不干脆做成“头尾两个独立缓冲区”因为现实里的滑动窗口往往还伴随偶尔的中间查询比如按索引回看某个历史事件、统计区间的聚合结果。如果头尾完全分离这些操作就没法用统一索引表达。所以 deque 的“块 映射”结构其实是一种很务实的折中它在头尾操作、顺序访问、随机访问三者之间找到了一个平衡点虽然每个单项都不是理论最优但组合场景下最不拉胯。1.2 从延迟数字理解cache miss 是怎么吃掉你的吞吐这里先补个背景。现代 CPU 的缓存结构是 L1/L2/L3/内存这样的金字塔L1 缓存命中大概 4 个周期L2 大概 12 个周期L3 大概 40 个周期真正掉到内存里面要 200 到 400 个周期。如果一颗 4GHz 的 CPU 每次访问数据都要 miss一次访问就是几十纳秒而一个内存热点函数一秒要访问几千万次最终差距就是毫秒级。所以在热路径上“一次内存访问”和“一次 L1 命中”之间可以差两个数量级这往往比算法的常数项优化更值得关注。缓存命中率能决定系统吞吐本质是因为两个局部性时间局部性和空间局部性。时间局部性指同一个数据被反复访问空间局部性指访问了一个地址它附近的地址很快也会被访问。CPU 一次从内存拿数据不是拿一个字节而是拿一整条 cache linex86 通常是 64 字节到缓存里。如果你的数据结构把要用的数据挤在少数几条 cache line 里那一次内存访问能喂饱后面很多次计算反之如果数据分散在好多条 cache line 里每条 line 只用到一点有效带宽就大幅下降。deque 的设计就是在帮 CPU 维持空间局部性但它能给到什么程度完全取决于分块大小和遍历模式。这就要说到 std::deque 的具体内存布局了下面拆开看。2. 拆开 std::deque 的内存布局块、映射表、迭代器2.1 中央映射表 固定大小块deque 到底怎么存std::deque 的标准要求很有意思两端插入是摊还常数时间中间插入是线性时间随机访问是常数时间。这个组合决定实现必须是分块结构。几乎所有标准库实现都会维护两样东西一个中央映射表以及一系列固定大小的数据块。中央映射表本质是一个指针数组数组的每一项指向一块连续内存这块连续内存就是真正存放元素的地方。你往头部插入时映射表从数组的中间位置向前扩展往尾部插入时则从中间位置向后扩展所以中央映射表本身也必须预留两头增长的空间。在 libstdcGCC 的标准库里块大小的判定逻辑我一直觉得值得背下来默认每个块的字节数是 512但还要看元素类型占多大。如果一个元素比 512 字节还大那一个块就只能放一个元素如果元素是 8 字节的 int64那一个块就是 64 个元素。MSVC 的标准库实现则完全不是这个策略它让每个块最多容纳 16 字节/元素大小 个元素本质上是把块做得非常小。这也是为什么同一段代码在 Linux 上跑得飞快换到 Windows 上可能直接慢一半的经典原因。我之前给一个跨平台服务做性能回归发现同一套容器代码在 MSVC 和 GCC 下的吞吐差了将近一倍最终定位到的就是块大小差异。顺便提一下迭代器的内部结构。deque 的迭代器不是裸指针它至少要记录四个字段当前元素指针 cur、当前块起始 first、当前块末尾 last、当前块在中央映射表中的位置 node。实现大致长这样template typename _Tp, typename _Ref, typename _Ptr struct _Deque_iterator { _Tp* _M_cur; // 当前元素 _Tp* _M_first; // 当前块起点 _Tp* _M_last; // 当前块终点 _Map_pointer _M_node; // 中央映射表条目 ... };每次 或 -- 都要先检查 cur 是否到了 first 或 last 边界到了边界就得跳到相邻块并把 first/last 同步成新块的边界。这个边界判断引入了一个分支但它 pattern 很规整顺序遍历时分支预测基本能命中可一旦随机访问情况就完全不一样了。2.2 随机访问、二分查找这些“伪连续”场景是重灾区实操里最容易出事的不是头尾插入而是“你以为它是连续数组”的操作模式。deque 确实支持 operator[]它也是常数时间但是这个常数时间前面有一个不小的常数先查中央映射表拿到块指针再在块内做偏移。如果映射表本身又不在缓存里那一次 operator[] 可能比 vector 的裸指针多出几十个周期的开销。更麻烦的是在 deque 上做二分查找或者按索引稀疏访问会不断在块与块之间跳来跳去缓存命中率会显著低于 vector。我自己写一个按时间索引的事件缓存时最初用 deque 保存 index后来在 1000 万条数据上做二分查找性能比 vector 慢了大概 3 倍。定位之后直接把容器切回 vector利用它内存连续的特性配合 lower_bound延迟直接回到预期水平。所以我的结论是如果某个结构的主要场景是按下标随机读就应该用 vector哪怕它牺牲了头尾插入的常数性因为你的热路径根本不是头尾操作。deque 真正的主场是“只动头尾、中间遍历稳定”的队列型负载、滑动窗口、任务调度等这些场景它才是最优解。还有一个容易被忽略的坑是元素大小。deque 的块内元素数量取决于“块字节数 / 元素大小”如果你的结构体变大块内的元素数量就变少遍历时需要跨越的块数量就变多。一旦元素大小超过 512 字节libstdc 的 deque 等价于每块一个元素空间局部性直接退化成链表水平。遇到这种结构体最好改成存指针或者索引否则你会看到 deque 遍历慢得毫无道理。2.3 微基准数据把 vector、libstdc deque、MSVC deque 摆一起比我在一台 4.8GHz 的 x86 机器上用 100 万个 int64 元素做了两组基准一组是整体顺序遍历累加一组是随机按下标读 100 万次。为避免编译器优化结果用 volatile 累加随机索引用固定随机种子。测试结果如下容器实现顺序遍历GB/s随机访问GB/sstd::vector约 28约 1.9libstdc deque512 字节块约 22约 1.2MSVC deque小碎块约 11约 0.8顺序遍历里 vector 最快因为一次 load 连续读取整个数组预取器可以按 64 字节 cache line 的节奏把后面的数据提前拉到 L2基本是内存带宽的天花板。libstdc deque 每个块 512 字节块内连续、块间地址不连续但每次只跳 512 字节现代预取器基本能跟上所以损失不大大概 20% 左右。MSVC deque 的块太小遍历时没走几步就跨一次 node预取流频繁被打断损失直接超过 50%这个差异往往比换算法还明显。随机访问场景大家都 missvector 略好因为地址连续、TLB 覆盖更完整deque 每次都要多查一次映射表速度比 vector 慢 30% 到 60%MSVC 的映射表条目更碎更分散所以最慢。这里有个很实际的启发如果你线上跑的是 MSVC而且热路径是顺序遍历我强烈建议你用内存对齐的环缓冲替代 deque或者直接用 vector 加头尾指针模拟窗口。我那个日志滚动模块后来就是靠这个改动把 p99 从 3.8ms 拉到 1.1ms 的没有改任何业务逻辑。3. 从 deque 到 KV cachevLLM 是怎么优化大模型缓存命中率的3.1 LLM 推理里那个“增长的滑动窗口”现在把镜头拉高到 LLM 推理服务。部署一个 7B 模型做对话输入一段 prompt模型逐个 token 生成回复。这个过程中有一份非常关键的中间数据叫 KV cache也就是把每个历史 token 对应的 Key 矩阵和 Value 矩阵缓存下来避免后续生成时重复计算前面的注意力。KV cache 的大小跟序列长度sequence length也就是标题里的 sl近似线性关系具体算一下你会很震撼。以常见 7B 模型粗算假设 32 层 transformer、隐藏维度 4096、KV 使用 FP162 字节。每个 token 的 KV 缓存大小大约是每 token KV 字节 层数 × 2K 和 V 两个矩阵× 隐藏维度 × 每个元素字节 32 × 2 × 4096 × 2 524,288 字节。也就是说每个 token 要吃掉 512KB 显存。一条长度 4096 的序列KV cache 就是 2GB 显存。4096 个 token 的 KV 就能吃掉四分之一张 80GB A100而且每处理一个新 token 都要往尾部写一份新的 KV。如果不做块化管理随便来几个并发长上下文的请求显存立刻就爆。这里就出现了一个和 deque 滑动窗口很像的问题当序列越来越长旧 token 可能已经不在当前注意力窗口内了但新 token 还在不断往尾巴上追加。系统必须决定哪些 KV 块继续留在显存里哪些可以被淘汰或者复用。在原生 PyTorch 的朴素实现里通常给每个序列预分配一块连续张量长度不够再重新分配。每个 token 生成都要搬动整块内存内存碎片化严重显存利用率极低很多小请求会因为“显存不够”被拒绝实际上显存里全是无法合并的碎片。3.2 PagedAttention把 KV cache 做成一张“显存版映射表”vLLM 的核心思路是借鉴操作系统内存分页把 KV cache 拆成固定大小的块每个块里存若干个 token 的 key/value再用一个 block table 记录“逻辑块 - 物理块”的映射。这个 block table 简直就是 std::deque 中央映射表的显存版逻辑上你有一个长长的序列看起来完整且连续物理上它是一批或分散或连续的显存块靠映射表把它们串起来。这样拆有两个直接好处和 deque 选型的理由完全一样。一是按需分配尾部扩长一点就只分配一个块不再整段搬移也不会因为预留太长导致浪费。二是不再碎片化物理块的粒度固定显存管理器可以像页表一样高效回收和重用块。另外一个在 LLM 场景独有的好处是共享前缀如果两个请求享有一部分重复的 prompt 前缀PagedAttention 可以让它们直接共用同一段物理 KV 块新序列只需要在 block table 里追加新的映射条目。这就像多个 deque 迭代器同时指向同一个块大家只读不写就行了。这套“分块 映射表”的做法本质上是在 GPU 显存的尺度上复刻了 CPU 缓存的多级管理思路KV cache 是“内存”GPU 的 L2 和计算单元里的高速缓冲区是“缓存”而 block table 决定了哪些块能落在缓存里、哪些块需要被驱逐。你优化 std::deque 时纠结的是 cache line到了 vLLM 这里纠结的是 block table 和显存命中率差别只是尺度从 64 字节放大到了几百 KB 到几 MB 的块。3.3 滑动窗口注意力的“循环块回收”真正让我觉得 vLLM 和 deque 是同一件事的是它对滑动窗口注意力sliding window attention的处理。某些模型最早代表性的有 Mistral 7B的注意力范围不是全局的它只让每个 token 看到前面 W 个 token 的 KV。在这种情况下很早之前的 KV 块已经完全没用了如果再占着显存就是浪费。vLLM 对这类模型做了循环缓冲去管理窗口块当一个块里的 token 全部落在窗口之外这个块的物理显存会被立刻回收进块分配器后续新 token 追加时可以直接复用。逻辑上你看到的是一个“尾部在写、头部在丢”的 deque/环形队列物理上它由一块块显存拼成由分配器按 FIFO 的次序循环利用。你可以直接把它理解成“GPU 版的 deque块是缓存行block table 是中央映射表滑动窗口就是双端弹出”。这里有个容易踩的坑如果你的模型配置了 sliding window而你的服务端推理框架还是按“完整上下文”去预留显存甚至做了前缀 KV 复用那么窗口外的块并不会被及时释放导致显存长期虚高批处理大小被无谓压低。排查办法很简单先看推理框架暴露的 GPU KV cache usage 指标再对照模型配置里的 window_size 参数如果窗口外还有块被长期占用多半是框架没有正确触发循环复用或者你自行改了 attention 后没有同步刷新 window 元信息。3.4 序列长度越大前缀命中率越值钱最后回到“sl 越长越要优化缓存命中率”的直觉。因为 KV cache 和序列长度线性增长对在线服务来说处理长序列时最贵的不是计算本身而是“把该准备的 KV 算出来再存进去”。如果多个用户的请求带有相同前缀这是很多 RAG 场景的常态知识库段落、系统提示词、工具说明都是固定开头那么前缀的 KV 计算结果完全可以复用省下的就是前缀长度对应的那串计算和显存带宽。vLLM 的自动前缀缓存正是干这件事的它给每个物理块加一个基于内容的哈希记录这个块对应的 prompt 前缀的 KV 结果新请求进来时先按前缀逐块找缓存命中的块直接进 block table。命中率在这个体系里是可以从指标上直接看到的vLLM 会暴露 prefix cache hit rate 之类的指标。实操里我观察到把公共的系统提示词固定放在 prompt 最前面比放在中间或末尾能明显提升命中率因为前缀匹配是按块从左到右进行的前面能连上后面的块才能继续连。还要注意块大小和前缀长度的配合。如果公共前缀只有 10 个 token而每块能存 16 个 token那它覆盖不满一个块永远不可能在块粒度上命中。要想吃满前缀缓存公共前缀至少要和若干完整块对齐。这个特性和 deque 的“块内连续、块间映射”是一模一样的块的粒度决定了你能复用的最小单位粒度越大命中粒度越粗缓存浪费也越多。4. 常见问题与排查技巧实录4.1 C 侧高频翻车点跨块造成的假性“顺序访问”我把这一类问题归纳为“看起来在顺序读实际上每次都在跨块”。最常见的现场是你用 deque 存了一个结构体然后写了一个 for 循环从 begin() 遍历到 end()你以为这是连续的实际上你只是把“块内连续、块间跳跃”的模式均匀地喂给了 CPU。如果块内结构体大小又恰好是 3 个 int 加一个指针20 字节缓存行利用率会很差一个 64 字节 cache line 里可能只有两三个对象被用上遍历起来每一行都有浪费。排查方法分三步。第一步先用硬件计数器数一下 cache-miss 和 cache-referencesperf stat 里如果 miss 比例超过 30% 就要怀疑数据布局问题。第二步确认热点函数里有没有明显的间接寻址deque 迭代器在汇编层面通常表现为频繁的边界判断和指针跳转。第三步做一个对照实验把同一个 deque 换成 vector或者换成固定容量 ring buffer跑同一组 benchmark看吞吐差异。如果替换后提升超过 30%就说明瓶颈确实在容器布局而不是算法本身。4.2 服务端 LLM 推理的“缓存命中率低”从哪来如果你部署了 vLLM 并把前缀缓存打开了却发现命中率指标一直很低先别急着调大批处理参数按顺序排查五个点第一prompt 前缀是否真的对齐。很多框架做前缀匹配是基于 token id 级别的如果同一条 prompt 因为换行、空白、编码差异导致 token 序列不一致前面那段一个都匹配不上。直接用 tokenizer 打印前 50 个 token id 对比一下最保险。第二块大小和前缀长度的关系。公共前缀必须完整覆盖若干个块才能在块粒度上命中。如果公共前缀只有 10 个 token而每块能存 16 个 token命中率自然上不去。这时候要么把公共 prompt 加长到块大小的整数倍要么调整块大小让粒度更细。第三是否被滑动窗口打断。如果模型是 sliding window attention且窗口长度不长旧前缀的 KV 块早就被循环回收了自然没有命中可言。这种情况优化命中率没有意义还不如直接省计算量。第四多进程和多副本之间是否共享缓存。vLLM 的 prefix cache 是进程级的请求如果被负载均衡散到多个副本命中率天生会被稀释。想让缓存收益最大化最好让相同前缀的请求尽量路由到同一副本。第五是否真的打开了开关。一些版本里自动前缀缓存默认关闭要用 enable_prefix_caching 参数或对应环境变量打开。很多“优化了半天命中率没涨”的案例最后发现都是开关没开。4.3 一张自查表直接对着定位我把两类问题整理成一张表遇到性能异常的时候对着查定位现象最可能原因推荐处理deque 遍历慢到接近链表MSVC 小碎块 / 结构体过大换成 vector 或自定义定长环队列deque 随机访问极慢映射表和数据块分散TLB 压力大改用 vector或对常访问区间做拷贝缓存vLLM 前缀缓存命中率 10%prompt 前缀 token 不一致固定头部模板用 tokenizer 验 idvLLM 块分配持续增长但命中率低sliding window 未正确复用循环块检查 window_size 与框架循环回收日志GPU 显存占用高且碎片明显KV cache 按固定大块预分配开启 paged attention / 调整块大小最后再分享一个只在实际部署里踩出来的经验不管你是调 C 的 deque 还是调 vLLM 的缓存参数都要先明确你的“热数据粒度”到底是什么。对 deque 来说热粒度是 cache line 和块对 KV cache 来说热粒度是一个逻辑 token 的 key/value但实际复用粒度是块。粒度定了再去看块大小、映射方式、回收策略就不会在错误的尺度上做无用优化。我见过太多人拼命调算法复杂度结果一个错误的容器布局就让整条链路的缓存命中率腰斩换对容器之后性能立刻翻倍。数据结构的内存布局这件事在 CPU 上重要在 GPU 上更重要值得你在动手优化前先花几分钟把底层模型想清楚。
从std::deque到vLLM：滑动窗口下的缓存命中率优化
我先交代一下标题里“sl”到底指什么。在项目文档里不同人会把 sl 写作 sequence length序列长度或者 sliding window滑动窗口有些场景下它俩根本就是同一个问题数据不断在尾部追加同时旧数据从头部被淘汰整个工作集像一列火车一样往前平移。无论是 C 后端处理滑动窗口日志还是大模型推理里管理 KV cache只要碰到底层存储的“尾部写、头部丢”模式缓存命中率就成了那个决定系统最终吞吐的关键指标。这篇文章想把这些看似不相关的东西串起来先从 std::deque 的分块实现讲起把它的块表结构、迭代器设计和与 vector 的缓存差异讲清楚再切入 vLLM 的 PagedAttention、滑动窗口注意力循环回收和自动前缀缓存说明 GPU 上的 KV cache 管理其实就是在用更粗的“缓存行”做同一件事。适合两类人看一类是正在做 C 服务性能优化、想搞明白 deque 到底快在哪慢在哪的工程师另一类是刚接触 LLM 推理服务部署、想知道 vLLM 这些优化到底改了什么的人。下面进正题。1. 滑动窗口类负载最容易把缓存命中率击穿的场景1.1 尾部写入、头部淘汰这到底是什么负载先说我踩过的一道坎。有一个日志滚动模块需要把最近 5 分钟的访问事件放在内存里按时间顺序展示老事件过期就移除。我当时图省事直接用 std::vector发现数据量一上来就频繁卡顿换成链表后顺序遍历又慢得离谱最后换 deque 才压住了延迟。后来才明白这类“尾部追加 头部淘汰”的滚动窗口负载对容器的要求其实非常特殊单次操作基本只碰头部和尾部中间数据只是被“路过”而不是被“改写”。如果用 vector瓶颈在于容量到达上限时要整体重新分配把一整段内存搬到新地址旧缓存行、TLB 全部作废移动一次数组代价巨大如果换成链表虽然增删头尾是 O(1)但每个节点独立分配在堆上地址彼此分散顺序访问时预取器基本失效每个节点都可能成为一次 cache miss。deque 的分块思路正好卡在中间内部划分成多个固定大小的连续块块与块之间用映射关系串起来。尾部追加到块内的空位就是普通写入块满了才新申请一块头部淘汰到只剩空块时就把整块还给分配器。这样既避免了大段复制又保留了块内的空间局部性。你可能会问既然中间数据很少访问为什么 deque 不干脆做成“头尾两个独立缓冲区”因为现实里的滑动窗口往往还伴随偶尔的中间查询比如按索引回看某个历史事件、统计区间的聚合结果。如果头尾完全分离这些操作就没法用统一索引表达。所以 deque 的“块 映射”结构其实是一种很务实的折中它在头尾操作、顺序访问、随机访问三者之间找到了一个平衡点虽然每个单项都不是理论最优但组合场景下最不拉胯。1.2 从延迟数字理解cache miss 是怎么吃掉你的吞吐这里先补个背景。现代 CPU 的缓存结构是 L1/L2/L3/内存这样的金字塔L1 缓存命中大概 4 个周期L2 大概 12 个周期L3 大概 40 个周期真正掉到内存里面要 200 到 400 个周期。如果一颗 4GHz 的 CPU 每次访问数据都要 miss一次访问就是几十纳秒而一个内存热点函数一秒要访问几千万次最终差距就是毫秒级。所以在热路径上“一次内存访问”和“一次 L1 命中”之间可以差两个数量级这往往比算法的常数项优化更值得关注。缓存命中率能决定系统吞吐本质是因为两个局部性时间局部性和空间局部性。时间局部性指同一个数据被反复访问空间局部性指访问了一个地址它附近的地址很快也会被访问。CPU 一次从内存拿数据不是拿一个字节而是拿一整条 cache linex86 通常是 64 字节到缓存里。如果你的数据结构把要用的数据挤在少数几条 cache line 里那一次内存访问能喂饱后面很多次计算反之如果数据分散在好多条 cache line 里每条 line 只用到一点有效带宽就大幅下降。deque 的设计就是在帮 CPU 维持空间局部性但它能给到什么程度完全取决于分块大小和遍历模式。这就要说到 std::deque 的具体内存布局了下面拆开看。2. 拆开 std::deque 的内存布局块、映射表、迭代器2.1 中央映射表 固定大小块deque 到底怎么存std::deque 的标准要求很有意思两端插入是摊还常数时间中间插入是线性时间随机访问是常数时间。这个组合决定实现必须是分块结构。几乎所有标准库实现都会维护两样东西一个中央映射表以及一系列固定大小的数据块。中央映射表本质是一个指针数组数组的每一项指向一块连续内存这块连续内存就是真正存放元素的地方。你往头部插入时映射表从数组的中间位置向前扩展往尾部插入时则从中间位置向后扩展所以中央映射表本身也必须预留两头增长的空间。在 libstdcGCC 的标准库里块大小的判定逻辑我一直觉得值得背下来默认每个块的字节数是 512但还要看元素类型占多大。如果一个元素比 512 字节还大那一个块就只能放一个元素如果元素是 8 字节的 int64那一个块就是 64 个元素。MSVC 的标准库实现则完全不是这个策略它让每个块最多容纳 16 字节/元素大小 个元素本质上是把块做得非常小。这也是为什么同一段代码在 Linux 上跑得飞快换到 Windows 上可能直接慢一半的经典原因。我之前给一个跨平台服务做性能回归发现同一套容器代码在 MSVC 和 GCC 下的吞吐差了将近一倍最终定位到的就是块大小差异。顺便提一下迭代器的内部结构。deque 的迭代器不是裸指针它至少要记录四个字段当前元素指针 cur、当前块起始 first、当前块末尾 last、当前块在中央映射表中的位置 node。实现大致长这样template typename _Tp, typename _Ref, typename _Ptr struct _Deque_iterator { _Tp* _M_cur; // 当前元素 _Tp* _M_first; // 当前块起点 _Tp* _M_last; // 当前块终点 _Map_pointer _M_node; // 中央映射表条目 ... };每次 或 -- 都要先检查 cur 是否到了 first 或 last 边界到了边界就得跳到相邻块并把 first/last 同步成新块的边界。这个边界判断引入了一个分支但它 pattern 很规整顺序遍历时分支预测基本能命中可一旦随机访问情况就完全不一样了。2.2 随机访问、二分查找这些“伪连续”场景是重灾区实操里最容易出事的不是头尾插入而是“你以为它是连续数组”的操作模式。deque 确实支持 operator[]它也是常数时间但是这个常数时间前面有一个不小的常数先查中央映射表拿到块指针再在块内做偏移。如果映射表本身又不在缓存里那一次 operator[] 可能比 vector 的裸指针多出几十个周期的开销。更麻烦的是在 deque 上做二分查找或者按索引稀疏访问会不断在块与块之间跳来跳去缓存命中率会显著低于 vector。我自己写一个按时间索引的事件缓存时最初用 deque 保存 index后来在 1000 万条数据上做二分查找性能比 vector 慢了大概 3 倍。定位之后直接把容器切回 vector利用它内存连续的特性配合 lower_bound延迟直接回到预期水平。所以我的结论是如果某个结构的主要场景是按下标随机读就应该用 vector哪怕它牺牲了头尾插入的常数性因为你的热路径根本不是头尾操作。deque 真正的主场是“只动头尾、中间遍历稳定”的队列型负载、滑动窗口、任务调度等这些场景它才是最优解。还有一个容易被忽略的坑是元素大小。deque 的块内元素数量取决于“块字节数 / 元素大小”如果你的结构体变大块内的元素数量就变少遍历时需要跨越的块数量就变多。一旦元素大小超过 512 字节libstdc 的 deque 等价于每块一个元素空间局部性直接退化成链表水平。遇到这种结构体最好改成存指针或者索引否则你会看到 deque 遍历慢得毫无道理。2.3 微基准数据把 vector、libstdc deque、MSVC deque 摆一起比我在一台 4.8GHz 的 x86 机器上用 100 万个 int64 元素做了两组基准一组是整体顺序遍历累加一组是随机按下标读 100 万次。为避免编译器优化结果用 volatile 累加随机索引用固定随机种子。测试结果如下容器实现顺序遍历GB/s随机访问GB/sstd::vector约 28约 1.9libstdc deque512 字节块约 22约 1.2MSVC deque小碎块约 11约 0.8顺序遍历里 vector 最快因为一次 load 连续读取整个数组预取器可以按 64 字节 cache line 的节奏把后面的数据提前拉到 L2基本是内存带宽的天花板。libstdc deque 每个块 512 字节块内连续、块间地址不连续但每次只跳 512 字节现代预取器基本能跟上所以损失不大大概 20% 左右。MSVC deque 的块太小遍历时没走几步就跨一次 node预取流频繁被打断损失直接超过 50%这个差异往往比换算法还明显。随机访问场景大家都 missvector 略好因为地址连续、TLB 覆盖更完整deque 每次都要多查一次映射表速度比 vector 慢 30% 到 60%MSVC 的映射表条目更碎更分散所以最慢。这里有个很实际的启发如果你线上跑的是 MSVC而且热路径是顺序遍历我强烈建议你用内存对齐的环缓冲替代 deque或者直接用 vector 加头尾指针模拟窗口。我那个日志滚动模块后来就是靠这个改动把 p99 从 3.8ms 拉到 1.1ms 的没有改任何业务逻辑。3. 从 deque 到 KV cachevLLM 是怎么优化大模型缓存命中率的3.1 LLM 推理里那个“增长的滑动窗口”现在把镜头拉高到 LLM 推理服务。部署一个 7B 模型做对话输入一段 prompt模型逐个 token 生成回复。这个过程中有一份非常关键的中间数据叫 KV cache也就是把每个历史 token 对应的 Key 矩阵和 Value 矩阵缓存下来避免后续生成时重复计算前面的注意力。KV cache 的大小跟序列长度sequence length也就是标题里的 sl近似线性关系具体算一下你会很震撼。以常见 7B 模型粗算假设 32 层 transformer、隐藏维度 4096、KV 使用 FP162 字节。每个 token 的 KV 缓存大小大约是每 token KV 字节 层数 × 2K 和 V 两个矩阵× 隐藏维度 × 每个元素字节 32 × 2 × 4096 × 2 524,288 字节。也就是说每个 token 要吃掉 512KB 显存。一条长度 4096 的序列KV cache 就是 2GB 显存。4096 个 token 的 KV 就能吃掉四分之一张 80GB A100而且每处理一个新 token 都要往尾部写一份新的 KV。如果不做块化管理随便来几个并发长上下文的请求显存立刻就爆。这里就出现了一个和 deque 滑动窗口很像的问题当序列越来越长旧 token 可能已经不在当前注意力窗口内了但新 token 还在不断往尾巴上追加。系统必须决定哪些 KV 块继续留在显存里哪些可以被淘汰或者复用。在原生 PyTorch 的朴素实现里通常给每个序列预分配一块连续张量长度不够再重新分配。每个 token 生成都要搬动整块内存内存碎片化严重显存利用率极低很多小请求会因为“显存不够”被拒绝实际上显存里全是无法合并的碎片。3.2 PagedAttention把 KV cache 做成一张“显存版映射表”vLLM 的核心思路是借鉴操作系统内存分页把 KV cache 拆成固定大小的块每个块里存若干个 token 的 key/value再用一个 block table 记录“逻辑块 - 物理块”的映射。这个 block table 简直就是 std::deque 中央映射表的显存版逻辑上你有一个长长的序列看起来完整且连续物理上它是一批或分散或连续的显存块靠映射表把它们串起来。这样拆有两个直接好处和 deque 选型的理由完全一样。一是按需分配尾部扩长一点就只分配一个块不再整段搬移也不会因为预留太长导致浪费。二是不再碎片化物理块的粒度固定显存管理器可以像页表一样高效回收和重用块。另外一个在 LLM 场景独有的好处是共享前缀如果两个请求享有一部分重复的 prompt 前缀PagedAttention 可以让它们直接共用同一段物理 KV 块新序列只需要在 block table 里追加新的映射条目。这就像多个 deque 迭代器同时指向同一个块大家只读不写就行了。这套“分块 映射表”的做法本质上是在 GPU 显存的尺度上复刻了 CPU 缓存的多级管理思路KV cache 是“内存”GPU 的 L2 和计算单元里的高速缓冲区是“缓存”而 block table 决定了哪些块能落在缓存里、哪些块需要被驱逐。你优化 std::deque 时纠结的是 cache line到了 vLLM 这里纠结的是 block table 和显存命中率差别只是尺度从 64 字节放大到了几百 KB 到几 MB 的块。3.3 滑动窗口注意力的“循环块回收”真正让我觉得 vLLM 和 deque 是同一件事的是它对滑动窗口注意力sliding window attention的处理。某些模型最早代表性的有 Mistral 7B的注意力范围不是全局的它只让每个 token 看到前面 W 个 token 的 KV。在这种情况下很早之前的 KV 块已经完全没用了如果再占着显存就是浪费。vLLM 对这类模型做了循环缓冲去管理窗口块当一个块里的 token 全部落在窗口之外这个块的物理显存会被立刻回收进块分配器后续新 token 追加时可以直接复用。逻辑上你看到的是一个“尾部在写、头部在丢”的 deque/环形队列物理上它由一块块显存拼成由分配器按 FIFO 的次序循环利用。你可以直接把它理解成“GPU 版的 deque块是缓存行block table 是中央映射表滑动窗口就是双端弹出”。这里有个容易踩的坑如果你的模型配置了 sliding window而你的服务端推理框架还是按“完整上下文”去预留显存甚至做了前缀 KV 复用那么窗口外的块并不会被及时释放导致显存长期虚高批处理大小被无谓压低。排查办法很简单先看推理框架暴露的 GPU KV cache usage 指标再对照模型配置里的 window_size 参数如果窗口外还有块被长期占用多半是框架没有正确触发循环复用或者你自行改了 attention 后没有同步刷新 window 元信息。3.4 序列长度越大前缀命中率越值钱最后回到“sl 越长越要优化缓存命中率”的直觉。因为 KV cache 和序列长度线性增长对在线服务来说处理长序列时最贵的不是计算本身而是“把该准备的 KV 算出来再存进去”。如果多个用户的请求带有相同前缀这是很多 RAG 场景的常态知识库段落、系统提示词、工具说明都是固定开头那么前缀的 KV 计算结果完全可以复用省下的就是前缀长度对应的那串计算和显存带宽。vLLM 的自动前缀缓存正是干这件事的它给每个物理块加一个基于内容的哈希记录这个块对应的 prompt 前缀的 KV 结果新请求进来时先按前缀逐块找缓存命中的块直接进 block table。命中率在这个体系里是可以从指标上直接看到的vLLM 会暴露 prefix cache hit rate 之类的指标。实操里我观察到把公共的系统提示词固定放在 prompt 最前面比放在中间或末尾能明显提升命中率因为前缀匹配是按块从左到右进行的前面能连上后面的块才能继续连。还要注意块大小和前缀长度的配合。如果公共前缀只有 10 个 token而每块能存 16 个 token那它覆盖不满一个块永远不可能在块粒度上命中。要想吃满前缀缓存公共前缀至少要和若干完整块对齐。这个特性和 deque 的“块内连续、块间映射”是一模一样的块的粒度决定了你能复用的最小单位粒度越大命中粒度越粗缓存浪费也越多。4. 常见问题与排查技巧实录4.1 C 侧高频翻车点跨块造成的假性“顺序访问”我把这一类问题归纳为“看起来在顺序读实际上每次都在跨块”。最常见的现场是你用 deque 存了一个结构体然后写了一个 for 循环从 begin() 遍历到 end()你以为这是连续的实际上你只是把“块内连续、块间跳跃”的模式均匀地喂给了 CPU。如果块内结构体大小又恰好是 3 个 int 加一个指针20 字节缓存行利用率会很差一个 64 字节 cache line 里可能只有两三个对象被用上遍历起来每一行都有浪费。排查方法分三步。第一步先用硬件计数器数一下 cache-miss 和 cache-referencesperf stat 里如果 miss 比例超过 30% 就要怀疑数据布局问题。第二步确认热点函数里有没有明显的间接寻址deque 迭代器在汇编层面通常表现为频繁的边界判断和指针跳转。第三步做一个对照实验把同一个 deque 换成 vector或者换成固定容量 ring buffer跑同一组 benchmark看吞吐差异。如果替换后提升超过 30%就说明瓶颈确实在容器布局而不是算法本身。4.2 服务端 LLM 推理的“缓存命中率低”从哪来如果你部署了 vLLM 并把前缀缓存打开了却发现命中率指标一直很低先别急着调大批处理参数按顺序排查五个点第一prompt 前缀是否真的对齐。很多框架做前缀匹配是基于 token id 级别的如果同一条 prompt 因为换行、空白、编码差异导致 token 序列不一致前面那段一个都匹配不上。直接用 tokenizer 打印前 50 个 token id 对比一下最保险。第二块大小和前缀长度的关系。公共前缀必须完整覆盖若干个块才能在块粒度上命中。如果公共前缀只有 10 个 token而每块能存 16 个 token命中率自然上不去。这时候要么把公共 prompt 加长到块大小的整数倍要么调整块大小让粒度更细。第三是否被滑动窗口打断。如果模型是 sliding window attention且窗口长度不长旧前缀的 KV 块早就被循环回收了自然没有命中可言。这种情况优化命中率没有意义还不如直接省计算量。第四多进程和多副本之间是否共享缓存。vLLM 的 prefix cache 是进程级的请求如果被负载均衡散到多个副本命中率天生会被稀释。想让缓存收益最大化最好让相同前缀的请求尽量路由到同一副本。第五是否真的打开了开关。一些版本里自动前缀缓存默认关闭要用 enable_prefix_caching 参数或对应环境变量打开。很多“优化了半天命中率没涨”的案例最后发现都是开关没开。4.3 一张自查表直接对着定位我把两类问题整理成一张表遇到性能异常的时候对着查定位现象最可能原因推荐处理deque 遍历慢到接近链表MSVC 小碎块 / 结构体过大换成 vector 或自定义定长环队列deque 随机访问极慢映射表和数据块分散TLB 压力大改用 vector或对常访问区间做拷贝缓存vLLM 前缀缓存命中率 10%prompt 前缀 token 不一致固定头部模板用 tokenizer 验 idvLLM 块分配持续增长但命中率低sliding window 未正确复用循环块检查 window_size 与框架循环回收日志GPU 显存占用高且碎片明显KV cache 按固定大块预分配开启 paged attention / 调整块大小最后再分享一个只在实际部署里踩出来的经验不管你是调 C 的 deque 还是调 vLLM 的缓存参数都要先明确你的“热数据粒度”到底是什么。对 deque 来说热粒度是 cache line 和块对 KV cache 来说热粒度是一个逻辑 token 的 key/value但实际复用粒度是块。粒度定了再去看块大小、映射方式、回收策略就不会在错误的尺度上做无用优化。我见过太多人拼命调算法复杂度结果一个错误的容器布局就让整条链路的缓存命中率腰斩换对容器之后性能立刻翻倍。数据结构的内存布局这件事在 CPU 上重要在 GPU 上更重要值得你在动手优化前先花几分钟把底层模型想清楚。
背后的工程美学)
