用内嵌双向链表管理空闲 KV 块
缓存块命中后可能需要从队列中间移除,双向链表让这一步保持常数时间。
相关概念
工程问题#
空闲块仍可能保存可复用 KV;再次命中时,要立即将它从可回收队列摘下。
实际实现#
KVCacheBlock 直接保存前后指针。FreeKVCacheBlockQueue 维护头尾,块池预分配元数据,并以引用计数区分在用块。
处理流程#
- 先保护命中块:若空闲先摘除,随后增加引用
- 再从队首取得新分配所需的块
- 请求结束后减少引用计数
- 零引用块按回收次序加入队尾
源码片段#
固定版本 · 原文摘录vllm/v1/core/kv_cache_utils.pyv0.8.5 · V1 · L214–L230
214 if block.prev_free_block is not None:215 # Link the previous block to the next block.216 block.prev_free_block.next_free_block = block.next_free_block217 if block.next_free_block is not None:218 # Link the next block to the previous block.219 block.next_free_block.prev_free_block = block.prev_free_block220221 if block == self.free_list_head:222 # Update the head if the block is the head.223 self.free_list_head = block.next_free_block224 if block == self.free_list_tail:225 # Update the tail if the block is the tail.226 self.free_list_tail = block.prev_free_block227228 # Remove the block from the linked list.229 block.prev_free_block = block.next_free_block = None230 self.num_free_blocks -= 1FreeKVCacheBlockQueue.remove
已知块对象后,直接修改前驱、后继和队列头尾,再清空该块链接并更新计数;没有按队列长度遍历,体现 O(1) 摘除。上层先通过 BlockPool.touch 保护缓存命中块,再申请新块;本片段本身不增加引用计数,也不承担并发同步。
PYTHONApache-2.0
收益与取舍#
工程分析带来的收益
- 已知节点的摘除与追加为 O(1)
- 链表操作无需新建包装对象
付出的代价
- 每块需要两个链表指针
- 引用计数、哈希映射和队列成员身份必须一致
可比较的选择
普通 deque头尾操作直接,但删除任意已知块仍需定位;内嵌链表可直接改指针。
版本与适用范围#
此版本空闲队列按 LRU 意图回收;同一请求释放时反转块顺序,优先回收更靠后的前缀块。不是所有 GPU 内存的通用分配器。
参考来源#
源码、官方文档与原始论文相关实现与比较#
4 个相关案例伙伴分配器把空闲物理页组织为不同 order 的连续块,并用空闲链表管理同阶块。
附源码片段 · 内存管理
limit_req 把漏桶计算、红黑树查状态与队列回收组合起来,按配置的 key 管理请求速率。
附源码片段 · 通信与流量
QEMU 的 QEMUTimerList 用有序单链表维护定时器,链表头就是下一到期项。
附源码片段 · 调度与资源分配
用压缩前缀树组织 token 序列,让多轮对话和分支生成共享已有 KV。
附源码片段 · 缓存与复用