虽然大型语言模型（LLM）的性能表现足够惊艳，但每次接收用户请求时都需要耗费大量显存和计算资源，一旦请求数量超出预期，就极有可能面临ChatGPT刚发布时的宕机、排队、高延迟等窘境。
想要打造一个高吞吐量的LLM服务，就需要模型在一个批次内处理尽可能多的请求，不过现有的系统大多在每次处理请求时申请大量的key-value（KV）缓存，如果管理效率不高，大量内存都会在碎片和冗余复制中被浪费掉，限制了BATch size的增长。
最近，来自加州大学伯克利分校、斯坦福大学、加州大学圣迭戈分校的研究人员基于操作系统中经典的虚拟内存和分页技术，提出了一个新的注意力算法PagedAttention，并打造了一个LLM服务系统vLLM
论文链接：https://aRxiv.oRg/pdf/2309.06180.pdf
开源链接：https://Github.coM/vllM-Project/vllM
vLLM在KV缓存上实现了几乎零浪费，并且可以在「请求内部」和「请求之间」灵活共享KV高速缓存，进一步减少了内存的使用量。
评估结果表明，vLLM可以将常用的LLM吞吐量提高了2-4倍，延迟水平上与最先进的系统（如FAsteRTRansfoRMeR和ORca）相当，并且在更长序列、更大模型和更复杂的解码算法时，提升更明显。
为了解决注意力机制的内存管理问题，研究人员开发了一种全新的注意力算法PagedAttention，并构建了一个LLM服务引擎vLLM，采用集中式调度器来协调分布式GPU工作线程的执行。
1. 算法
受操作系统中分页（paging）算法启发，PagedAttention将序列中KV缓存划分为KV块，其中每个块包含固定数量Tokens的键（K）和值（V）向量，从而将注意力计算转换为块级运算：
在注意力计算期间，PagedAttention内核分别识别和获取不同的KV块，比如下面的例子中，键和值向量分布在三个块上，并且三个块在物理内存上是不连续的，然后将查询向量与块中的键向量相乘得到部分注意力得分，再乘以块中的值向量得到最终注意力输出。
这种设计使得KV块存储在非连续物理内存中，从而让vLLM中的分页内存管理更加灵活。
2. KV缓存管理器
操作系统会将内存划分为多个固定大小的页，并将用户程序的逻辑页映射到物理页，连续的逻辑页可以对应于非连续的物理内存页，所以用户在访问内存时看起来就像连续的一样。
此外，物理内存空间不需要提前完全预留，使操作系统能够根据需求动态分配物理页。
通过PageAttention划分出的KV块，vLLM利用虚拟内存机制将KV缓存表示为一系列逻辑KV块，并在生成新Token及KV缓存时，从左到右进行填充；最后一个KV块的未填充位置预留给后续生成操作。
KV块管理器还负责维护块表（block table），即每个请求的逻辑和物理KV块之间的映射。
将逻辑和物理KV块分离使得vLLM能够动态地增长KV高速缓存存储器，而无需预先将其保留给所有位置，消除了现有系统中的大多数内存浪费。
3. 解码
从下面的例子中可以看出vLLM如何在单个输入序列的解码过程中执行PagedAttention并管理内存。
① 与操作系统的虚拟内存一样，vLLM最初不需要为最大可能生成的序列长度保留内存，只保留必要的KV块，以容纳在即时计算期间生成的KV缓存。
提示词中包含7个Tokens，所以vLLM将前两个逻辑KV块（0和1）映射到2个物理KV块（7和1）；在预填充（pRefill）步骤中，vLLM使用自注意算法生成提示和首个输出Token的KV缓存；然后将前4个Token的KV缓存存储在逻辑块0中，后面3个Token存储在逻辑块1中；剩余的slot被保留用于后续自回归生成。
② 在首个自回归解码步骤中，vLLM在物理块7和1上使用PagedAttention算法生成新Token
由于最后一个逻辑块中仍有一个slot可用，所以将新生成的KV缓存存储在该slot，更新块表的#filled记录。
③ 在第二次解码步骤中，当最后一个逻辑块已满时，vLLM将新生成的KV缓存存储在新的逻辑块中，为其分配一个新的物理块（物理块3），并映射存储在块表中。
在LLM的计算过程中，vLLM使用PagedAttention内核访问以前以逻辑KV块形式存储的KV缓存，并将新生成的KV缓存保存到物理KV块中。
在一个KV块（块大小>1）中存储多个Token使PagedAttention内核能够跨更多位置并行处理KV缓存，从而提高硬件利用率并减少延迟，但较大的块大小也会增加内存碎片。
