一、为什么需要 KV Cache?
在大语言模型的自回归生成过程中,模型每次生成一个新 Token,都需要利用此前已经生成的上下文信息。
Transformer 的 Attention 计算需要 Query、Key 和 Value:
其中:
- Query(Q):当前 Token 的查询向量。
- Key(K):历史 Token 的键向量。
- Value(V):历史 Token 的值向量。
- d_k:Key 向量维度。
如果每次生成新 Token 时,都重新计算整个历史序列的 Key 和 Value,就会产生大量重复计算。
KV Cache 就是为了解决这个问题。
1. 不使用 KV Cache 的计算方式
假设模型需要生成三个 Token:
输入:A B C
第 1 次生成:
计算 A、B、C → 生成 D
第 2 次生成:
重新计算 A、B、C、D → 生成 E
第 3 次生成:
重新计算 A、B、C、D、E → 生成 F
随着序列增长,历史 Token 会被反复计算。
2. 使用 KV Cache 的计算方式
使用 KV Cache 后,模型会保存历史 Token 的 Key 和 Value。
输入:A B C
Prefill:
计算 A、B、C
保存 K、V 缓存
第 1 次 Decode:
只计算 D 的 K、V
读取历史缓存
生成 E
第 2 次 Decode:
只计算 E 的 K、V
读取历史缓存
生成 F
历史 Token 的 KV 不需要重复计算。
需要注意:Decode 阶段仍然需要读取历史 KV Cache 参与 Attention,只是避免了重新计算历史 Token 的 K、V。
3. KV Cache 在 Transformer 中的位置
对于包含多个 Transformer Layer 的模型,每一层都需要维护自己的 Key 和 Value。
假设模型有 32 层:
- 第 1 层维护自己的 K、V。
- 第 2 层维护自己的 K、V。
- 依次到第 32 层。
因此,KV Cache 是按照 Layer、Head 和 Token 等维度组织的缓存数据。
二、KV Cache 的数据结构
理解 PagedAttention,首先需要理解 KV Cache 的存储结构。
1. KV Cache 的基本维度
一个典型的 KV Cache 可以抽象为:
其中:
| 参数 | 含义 |
|---|---|
| L | Transformer 层数 |
| 2 | Key 和 Value 两部分 |
| B | 请求批次大小 |
| S | 缓存序列长度 |
| H_{kv} | KV Head 数量 |
| D_h | 每个 Head 的维度 |
实际实现中,KV Cache 的物理布局会受到 Attention Backend、并行策略和硬件实现影响,不一定严格采用上述维度顺序。
2. KV Cache 的存储示意
假设模型有 2 层,每层保存 Key 和 Value:
Transformer
│
├── Layer 0
│ ├── Key Cache
│ └── Value Cache
│
└── Layer 1
├── Key Cache
└── Value Cache
每个 Token 都会在对应层产生自己的 Key 和 Value。
随着生成长度增加,KV Cache 持续增长。
3. KV Cache 与模型权重的区别
| 对比维度 | 模型权重 | KV Cache |
|---|---|---|
| 保存内容 | 模型训练得到的参数 | 历史 Token 的 Key、Value |
| 是否随请求变化 | 通常不变 | 随请求执行动态变化 |
| 是否与上下文长度相关 | 不直接相关 | 高度相关 |
| 是否随并发增加 | 通常不随请求数线性增加 | 通常随并发增加 |
| 生命周期 | 通常随模型实例存在 | 通常随请求或缓存复用生命周期变化 |
| 显存用途 | 保存模型参数 | 保存历史上下文计算结果 |
模型权重决定模型的计算能力,KV Cache 则保存推理过程中已经计算过的历史信息。
三、KV Cache 为什么会占用大量显存?
KV Cache 的显存占用与模型结构、上下文长度、并发请求数量和数据精度直接相关。
1. KV Cache 显存计算公式
单个请求的 KV Cache 理论占用可以表示为:
其中:
- L:模型层数。
- S:缓存 Token 数量。
- H_{kv}:KV Head 数量。
- D_h:Head Dimension。
- P:每个元素的字节数。
- 2:分别表示 Key 和 Value。
如果有多个请求:
这里假设所有请求的缓存长度相同。实际请求长度往往不同,需要逐请求计算或按 Block 分配量估算。
2. 显存估算案例
假设一个模型具有以下参数:
| 参数 | 数值 |
|---|---|
| Transformer 层数 | 32 |
| KV Head 数量 | 8 |
| Head Dimension | 128 |
| 数据精度 | FP16 |
| 单个请求上下文长度 | 8192 |
| 并发请求数量 | 16 |
FP16 每个元素占用 2 Bytes。
单个请求:
约为 1 GiB。
16 个请求:
也就是说,仅 KV Cache 就可能占用约 16 GiB 显存。
这还没有包含模型权重、激活值、CUDA 工作区和运行时开销。
3. GQA、MQA 对 KV Cache 的影响
KV Cache 大小还受到 Attention 架构影响。
| 注意力结构 | KV Head 数量 | 显存特点 |
|---|---|---|
| MHA | 与 Query Head 数量相同 | KV Cache 较大 |
| GQA | 少于 Query Head 数量 | KV Cache 更小 |
| MQA | 通常为 1 | KV Cache 更小 |
例如模型有 32 个 Query Head:
- MHA:32 个 KV Head。
- GQA:8 个 KV Head。
- MQA:1 个 KV Head。
在其他参数完全相同的情况下:
因此,GQA 和 MQA 不仅能够减少 KV Cache 的显存需求,还可以降低 Decode 阶段的 KV 数据读取压力。
四、传统 KV Cache 管理方式的问题
传统连续 KV Cache 管理方式通常要求每个请求的缓存存放在连续的显存区域中。
这种方式实现简单,但在高并发推理场景中存在明显问题。
1. 显存预分配浪费
假设三个请求的最大上下文长度均为 4096 Token:
| 请求 | 最大预留 Token | 实际使用 Token |
|---|---|---|
| A | 4096 | 512 |
| B | 4096 | 2048 |
| C | 4096 | 3000 |
如果按照最大上下文长度预分配,每个请求都需要占用 4096 Token 的缓存空间。
但实际使用量分别只有 512、2048 和 3000。
这会产生大量未使用的缓存空间。
2. 显存碎片问题
假设 GPU 显存中存在多个不同大小的空闲区域:
显存空间:
[请求 A][空闲][请求 B][空闲][请求 C][空闲]
虽然总空闲空间可能足够,但未必存在足够大的连续空间满足新请求的分配需求。
这就是外部显存碎片问题。
需要区分两种浪费:
- 内部碎片:分配的空间大于实际使用量,剩余部分无法被其他请求使用。
- 外部碎片:空闲空间分散,难以满足较大的连续分配请求。
3. 请求长度不确定
大模型的输出长度通常无法提前准确确定。
例如:
- 请求 A 生成 20 Token 后结束。
- 请求 B 生成 200 Token 后结束。
- 请求 C 生成 2000 Token 后结束。
如果按照最大长度预分配,就会产生明显浪费。
如果按照当前长度分配,又需要频繁扩展缓存空间。
传统连续分配方式难以同时兼顾动态扩展、显存利用率和并发能力。
4. 传统管理方式的主要问题
| 问题 | 原因 | 影响 |
|---|---|---|
| 内部碎片 | 预分配空间过大 | 显存利用率下降 |
| 外部碎片 | 连续内存分配限制 | 分配困难 |
| 动态扩展困难 | 请求长度不断变化 | 需要重新分配或复制 |
| 请求间隔离 | 缓存通常独立分配 | 难以共享相同前缀 |
| 并发受限 | 单个请求占用过多空间 | 可运行请求数量减少 |
五、PagedAttention 的核心思想
PagedAttention 是 vLLM 提出的核心技术之一。
它借鉴操作系统虚拟内存分页机制,将 KV Cache 切分为固定大小的 Block。
每个请求不再需要占用一整块连续的显存区域,而是通过 Block Table 记录逻辑位置与物理 Block 之间的映射关系。
1. 从连续存储到分页存储
传统方式:
请求 A:
[Block 0][Block 1][Block 2][Block 3]
请求 B:
[Block 4][Block 5][Block 6][Block 7]
每个请求通常需要连续的缓存区域。
PagedAttention:
请求 A:
逻辑 Block 0 → 物理 Block 3
逻辑 Block 1 → 物理 Block 8
逻辑 Block 2 → 物理 Block 1
请求 B:
逻辑 Block 0 → 物理 Block 5
逻辑 Block 1 → 物理 Block 2
逻辑 Block 2 → 物理 Block 9
物理 Block 可以分布在显存的不同位置。
逻辑上连续的 Token,不需要存放在物理上连续的显存区域。
2. PagedAttention 的核心组件
| 组件 | 作用 |
|---|---|
| KV Cache Block | 存放固定数量 Token 的 K、V 数据 |
| Block Table | 记录逻辑 Block 与物理 Block 的映射 |
| Block Manager | 管理 Block 的分配、释放和引用 |
| Free Block Pool | 保存当前可用的物理 Block |
| Attention Kernel | 根据 Block 映射读取 KV Cache 并计算 Attention |
| Scheduler | 根据请求状态和资源情况安排执行 |
3. 分页机制的整体结构
flowchart TD
A["请求 Token 序列"] --> B["逻辑 Token 位置"]
B --> C["计算逻辑 Block 编号"]
C --> D["查询 Block Table"]
D --> E["获取物理 Block 编号"]
E --> F["计算 Block 内偏移"]
F --> G["定位 KV Cache"]
G --> H["读取 Key 和 Value"]
H --> I["执行 Attention 计算"]
I --> J["生成模型输出"]
K["Block Manager"] --> L["Free Block Pool"]
L --> M["分配物理 Block"]
M --> D
N["请求状态变化"] --> O["更新 Block Table"]
O --> D
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style C fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style D fill:#EAE8FA,stroke:#A49BD5,color:#51477D
style E fill:#EAF3EC,stroke:#83A995,color:#315D49
style F fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style G fill:#EAF3EC,stroke:#83A995,color:#315D49
style H fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style I fill:#EAF3EC,stroke:#83A995,color:#315D49
style J fill:#DCEFE5,stroke:#4F8B70,color:#24563F
style K fill:#EAE8FA,stroke:#A49BD5,color:#51477D
style L fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style M fill:#EAF3EC,stroke:#83A995,color:#315D49
style N fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
style O fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
六、KV Cache Block 的组织方式
理解 PagedAttention,最重要的是理解 Block 的组织结构。
1. Block 的基本定义
一个 Block 是固定容量的 KV Cache 存储单元。
假设:
- 每个 Block 容纳 16 个 Token。
- 每个 Token 在每层保存 Key 和 Value。
- 所有 Transformer Layer 都有对应的缓存数据。
当请求有 35 个 Token 时,需要:
三个 Block 的逻辑组织:
| 逻辑 Block | Token 范围 | 使用数量 |
|---|---|---|
| Block 0 | 0~15 | 16 |
| Block 1 | 16~31 | 16 |
| Block 2 | 32~34 | 3 |
最后一个 Block 还有 13 个 Token 的剩余容量。
这部分属于 Block 内部未使用空间。
2. Block 内部偏移计算
假设 Block Size 为 16,Token 的逻辑位置为 35。
逻辑 Block 编号:
Block 内偏移:
因此:
- 逻辑 Block 编号为 2。
- Block 内偏移为 3。
再通过 Block Table 查询对应物理 Block 编号,最终定位 KV Cache 数据。
一般公式:
3. Block Table 的结构
假设请求 A 使用三个逻辑 Block:
| 逻辑 Block | 物理 Block |
|---|---|
| 0 | 3 |
| 1 | 8 |
| 2 | 1 |
Block Table 可以表示为:
block_table = {
"request_A": [3, 8, 1]
}
这表示请求 A 的逻辑 Block 0、1、2 分别对应物理 Block 3、8、1。
需要注意,这只是帮助理解映射关系的简化 Python 表示。真实 vLLM 内部使用高效的数据结构和 GPU 可访问的索引信息,不是简单依赖 Python 字典完成每次 Token 的显存访问。
4. Block 的物理布局
PagedAttention 的物理缓存布局通常按照模型层、KV 类型、Block、Head 和 Head Dimension 等维度组织。
概念上可以理解为:
KV Cache
│
├── Layer 0
│ ├── Key
│ │ ├── Physical Block 0
│ │ ├── Physical Block 1
│ │ └── Physical Block N
│ │
│ └── Value
│ ├── Physical Block 0
│ ├── Physical Block 1
│ └── Physical Block N
│
├── Layer 1
│ ├── Key
│ └── Value
│
└── Layer N
├── Key
└── Value
具体物理张量布局取决于所使用的 Attention Backend 和模型配置。
七、PagedAttention 的执行原理
PagedAttention 不只是将 KV Cache 分块存储,还需要解决如何高效访问这些分散的缓存数据。
1. 传统 Attention 的缓存访问
假设一个请求有 64 个历史 Token。
传统连续存储方式可以直接访问一段连续的 KV Cache:
Token 0 → Token 1 → Token 2 → ... → Token 63
访问逻辑比较简单。
但连续内存分配会带来动态扩展和显存碎片问题。
2. PagedAttention 的缓存访问
假设 Block Size 为 16:
逻辑 Token:
0~15 → 逻辑 Block 0
16~31 → 逻辑 Block 1
32~47 → 逻辑 Block 2
48~63 → 逻辑 Block 3
物理 Block 可能分布为:
逻辑 Block 0 → 物理 Block 5
逻辑 Block 1 → 物理 Block 2
逻辑 Block 2 → 物理 Block 9
逻辑 Block 3 → 物理 Block 1
Attention Kernel 需要根据 Block Table 找到对应物理缓存。
3. Attention 访问过程
flowchart TD
A["当前 Query"] --> B["读取逻辑 Token 位置"]
B --> C["计算逻辑 Block 编号"]
C --> D["查询 Block Table"]
D --> E["获得物理 Block 地址"]
E --> F["计算 Block 内偏移"]
F --> G["读取历史 Key"]
F --> H["读取历史 Value"]
G --> I["计算 QK 相似度"]
H --> J["参与加权求和"]
I --> K["Softmax"]
K --> L["Attention 输出"]
J --> L
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style C fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style D fill:#EAE8FA,stroke:#A49BD5,color:#51477D
style E fill:#EAF3EC,stroke:#83A995,color:#315D49
style F fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style G fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style H fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style I fill:#EAF3EC,stroke:#83A995,color:#315D49
style J fill:#EAF3EC,stroke:#83A995,color:#315D49
style K fill:#EAE8FA,stroke:#A49BD5,color:#51477D
style L fill:#DCEFE5,stroke:#4F8B70,color:#24563F
4. PagedAttention 改变了什么?
PagedAttention 没有改变 Attention 的核心数学计算。
它改变的是:
- KV Cache 的存储组织。
- 逻辑 Token 到物理 Block 的映射。
- Attention Kernel 对历史 KV 的访问方式。
- 缓存分配和释放的管理方式。
因此,PagedAttention 的价值主要体现在显存管理和高并发推理效率上。
八、Block Manager:缓存分配与释放
Block Manager 是 KV Cache 管理中的关键组件。
它负责维护物理 Block 的使用状态,并根据请求生命周期动态分配和释放缓存。
1. Block Manager 的职责
| 职责 | 具体作用 |
|---|---|
| Block 初始化 | 创建可用物理 Block 池 |
| Block 分配 | 为新请求分配缓存空间 |
| Block 映射 | 建立逻辑 Block 与物理 Block 的关系 |
| Block 扩展 | 请求增长时申请额外 Block |
| Block 释放 | 请求完成时回收缓存 |
| 引用计数 | 管理多个请求共享的 Block |
| 缓存复用 | 支持前缀缓存等复用场景 |
2. 空闲 Block 池
假设系统初始化了 10 个物理 Block:
Free Block Pool:
[0][1][2][3][4][5][6][7][8][9]
请求 A 需要两个 Block:
请求 A:
[0][1]
空闲池变成:
Free Block Pool:
[2][3][4][5][6][7][8][9]
请求 B 需要三个 Block:
请求 B:
[2][3][4]
当请求 A 完成后,Block 0 和 Block 1 可以重新回到空闲池。
3. Block 分配流程
flowchart TD
A["新请求进入"] --> B["计算需要的 Block 数量"]
B --> C["查询 Free Block Pool"]
C --> D{"空闲 Block 是否足够"}
D -->|"是"| E["分配物理 Block"]
D -->|"否"| F["检查可回收缓存"]
F --> G{"是否存在可回收资源"}
G -->|"是"| H["释放或回收 Block"]
G -->|"否"| I["等待或执行抢占策略"]
H --> C
I --> J["等待资源可用"]
J --> C
E --> K["更新 Block Table"]
K --> L["请求继续执行"]
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style C fill:#EAE8FA,stroke:#A49BD5,color:#51477D
style D fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
style E fill:#EAF3EC,stroke:#83A995,color:#315D49
style F fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style G fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
style H fill:#EAF3EC,stroke:#83A995,color:#315D49
style I fill:#F7EAE7,stroke:#C98D7C,color:#754438
style J fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style K fill:#EAE8FA,stroke:#A49BD5,color:#51477D
style L fill:#DCEFE5,stroke:#4F8B70,color:#24563F
4. Block 释放机制
请求结束后,Block Manager 会检查请求占用的 Block。
如果 Block 没有被其他请求引用,就可以释放并重新加入空闲池。
如果 Block 正在被多个请求共享,则不能直接释放,而是需要减少引用计数,直到没有请求再使用它。
这种机制是 Prefix Caching 能够安全复用缓存的重要基础。
九、Prefix Caching:前缀缓存共享
PagedAttention 的分页结构为 KV Cache 共享提供了基础。
Prefix Caching 可以让不同请求复用相同前缀产生的 KV Cache,从而减少重复 Prefill 计算。
1. 为什么需要前缀缓存?
在实际业务中,很多请求会使用固定的系统提示词。
例如:
请求 A:
你是一个专业的 Java 助手。
请解释 JVM 垃圾回收。
请求 B:
你是一个专业的 Java 助手。
请解释 Java 类加载机制。
请求 C:
你是一个专业的 Java 助手。
请解释线程池的工作原理。
三个请求都包含相同的系统提示词。
如果每次都重新计算这段公共前缀,就会浪费 GPU 计算资源。
2. 前缀缓存的复用过程
假设公共前缀已经计算完成,并且对应 KV Cache Block 仍然存在。
后续请求可以通过匹配缓存信息复用这些 Block。
flowchart TD
A["请求 A"] --> C["公共 Token 前缀"]
B["请求 B"] --> C
D["请求 C"] --> C
C --> E["执行前缀 Prefill"]
E --> F["生成 KV Cache Block"]
F --> G["建立缓存索引"]
G --> H["请求 A 复用"]
G --> I["请求 B 复用"]
G --> J["请求 C 复用"]
H --> K["计算 A 的独有内容"]
I --> L["计算 B 的独有内容"]
J --> M["计算 C 的独有内容"]
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style D fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style C fill:#EAE8FA,stroke:#A49BD5,color:#51477D
style E fill:#EAF3EC,stroke:#83A995,color:#315D49
style F fill:#EAF3EC,stroke:#83A995,color:#315D49
style G fill:#EAE8FA,stroke:#A49BD5,color:#51477D
style H fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style I fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style J fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style K fill:#DCEFE5,stroke:#4F8B70,color:#24563F
style L fill:#DCEFE5,stroke:#4F8B70,color:#24563F
style M fill:#DCEFE5,stroke:#4F8B70,color:#24563F
3. 前缀缓存的匹配依据
Prefix Caching 通常基于 Token Block 的内容和相关计算上下文进行匹配,而不是简单地判断两段文本是否相似。
需要考虑:
- Token 序列是否一致。
- 模型是否一致。
- 相关计算配置是否兼容。
- 多模态输入信息是否一致。
- 缓存 Block 是否仍然存在。
- 缓存是否满足当前请求的复用条件。
4. 为什么通常按完整 Block 复用?
分页缓存通常以 Block 为管理单位。
例如 Block Size 为 16:
公共前缀:
Token 0~15:完整 Block
Token 16~31:完整 Block
Token 32~39:未填满 Block
完整 Block 更容易进行缓存匹配和共享。
最后一个未填满的 Block 通常不能像完整 Block 一样直接作为任意新请求的共享前缀使用。具体复用边界取决于实现中的缓存粒度和匹配策略。
5. 引用计数与 Copy-on-Write
多个请求共享相同的物理 Block 时,系统需要跟踪引用关系。
假设:
请求 A ──┐
├── 共享物理 Block 5
请求 B ──┘
如果请求 A 完成,只能减少该 Block 的引用计数,不能直接回收。
如果请求 B 仍然使用该 Block,缓存就必须继续保留。
当共享前缀之后需要写入不同内容时,系统还需要避免直接覆盖共享数据。常见思路是采用 Copy-on-Write,即在需要修改共享内容时分配新的 Block。
十、KV Cache 的动态扩展机制
大模型的生成长度通常是不确定的,因此 KV Cache 必须支持动态增长。
1. 请求开始时分配缓存
假设 Block Size 为 16。
Prompt 有 30 个 Token:
请求开始时需要两个 Block。
2. Decode 阶段扩展
随着 Token 生成:
| 当前 Token 数量 | 需要的 Block 数量 |
|---|---|
| 30 | 2 |
| 31 | 2 |
| 32 | 2 |
| 33 | 3 |
| 48 | 3 |
| 49 | 4 |
当 Token 数量超过当前 Block 的容量时,需要申请新的 Block。
3. 动态扩展流程
flowchart TD
A["请求开始"] --> B["分配初始 Block"]
B --> C["执行 Prefill"]
C --> D["进入 Decode"]
D --> E["生成新 Token"]
E --> F{"当前 Block 是否有剩余容量"}
F -->|"有"| G["写入当前 Block"]
F -->|"无"| H["申请新 Block"]
H --> I{"分配是否成功"}
I -->|"成功"| J["更新 Block Table"]
I -->|"失败"| K["触发资源不足处理"]
K --> L["等待、抢占或重计算"]
L --> H
J --> G
G --> M{"是否达到停止条件"}
M -->|"否"| D
M -->|"是"| N["释放请求缓存"]
style A fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style B fill:#EAF3EC,stroke:#83A995,color:#315D49
style C fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style D fill:#E0F0FE,stroke:#93BCE8,color:#1E4976
style E fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style F fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
style G fill:#EAF3EC,stroke:#83A995,color:#315D49
style H fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style I fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
style J fill:#EAE8FA,stroke:#A49BD5,color:#51477D
style K fill:#F7EAE7,stroke:#C98D7C,color:#754438
style L fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style M fill:#F7F4E8,stroke:#C7B77A,color:#675A2D
style N fill:#DCEFE5,stroke:#4F8B70,color:#24563F