KV-Cache是一种加速推理的技术, KV-Cache就是将Attention 中的KV缓存下来，通过空间换时间的方式来加速计算Attention。

通过上图的展示可以很容易理解：通过将每次计算的K和V缓存下来，之后新的序列进来时只需要从KV Cache中读取之前的KV值即可，就不需要再去重复计算之前的KV了。

原理非常简单，但llama.cpp的实现源代码却是难以理解的，先看看KV-cache数据结构：

从代码注释可以看出这是一个循环存储的buffer（ring buffer），其中的数据说明如下：

1. has_shift: 表示cell中的位置是否做了偏移操作，而偏移量为cell[i].delta。

2. do_defrag: 表示是否需要执行碎片整理操作。

3. do_copy: 表示是否需要执行复制操作。

4. recurrent:表示是否为循环状态模型，应用于mamba模型。

5. head: 表示需要进行计算的KV头位置，如上图中橙色的格子位置，实际值是cell中有数据的单元数。

6. size:表示缓存的大小，即可以存储的键值对的数量。

7. used:表示已使用的cell单元格数量，即至少有一个sequence id（也是slot id）的单元格。

8. n: 表示cell中位置值非负且具有相应sequence id的单元格个数，即有效cell的个数。

9. type_k 和 type_v: 分别表示键（key）和值（value）的数据类型。

10. cells: 用于存储缓存中的每个单元格的状态。

11. k_l:表示每层的键（key）。

12. v_l:表示每层的值（value）。

13. ctxs: 内存管理数据。

14. bufs: buffer数组。

其中的“ llama_kv_cell”结构体主要是应用于记录token位置的变化，其数据说明如下：

pos: 表示token位置。

delta: 表示当前的pos值与原来的pos值出现偏移时的偏移量。

src: 应用于循环状态模型中复制状态。

seq_id: 表示当前位置的token是属于哪个sequence id,即task id或slot id。

KV-cache相关操作都是在cells中进行，如：

rm: 在指定位置范围内移除sequence id；

add: 在指定位置范围内添加sequence id；

cp: 在指定位置范围内插入sequence id；

clear: 清空cells中的数据，把所有cell单元的pos值置为-1，并去除所有sequence id。

KV-cache初始化过程（llama_kv_cache_init）：

步骤1：设置基本参数，如head、size、used、type_k、type_v等。

步骤2：清空cells数组，并重置cells数据大小为kv_size。

步骤3：计算每种buffer所涉及的decode层数量，buffer会有这些类型：GPU、SYCL（一种计算框架）、VULKAN（一种图像计算框架）、HBM（高内存带宽）、普通CPU，但ggml定义的backend只有三种类型：CPU、GPU、GPU_SPLIT。

步骤4：为每一种buffer分配一个ggml context(ggml 内存管理对象)。

步骤5：为decode每一层建立第一个为空的KV张量。

步骤6：为每一种buffer分配一个buffer。