返回专栏
· 23 分钟阅读

PagedAttention 与 KV Cache 管理


一、为什么需要 KV Cache?

在大语言模型的自回归生成过程中,模型每次生成一个新 Token,都需要利用此前已经生成的上下文信息。

Transformer 的 Attention 计算需要 Query、Key 和 Value:

Attention(Q,K,V)=Softmax\left(\frac{QK^T}{\sqrt{d_k}}\right)V

其中:

  • 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 可以抽象为:

KVCache \in \mathbb{R}^{L\times 2\times B\times S\times H_{kv}\times D_h}

其中:

参数 含义
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 理论占用可以表示为:

M_{KV}= 2\times L\times S\times H_{kv}\times D_h\times P

其中:

  • L:模型层数。
  • S:缓存 Token 数量。
  • H_{kv}:KV Head 数量。
  • D_h:Head Dimension。
  • P:每个元素的字节数。
  • 2:分别表示 Key 和 Value。

如果有多个请求:

M_{KV,total}= 2\times L\times B\times S\times H_{kv}\times D_h\times P

这里假设所有请求的缓存长度相同。实际请求长度往往不同,需要逐请求计算或按 Block 分配量估算。

2. 显存估算案例

假设一个模型具有以下参数:

参数 数值
Transformer 层数 32
KV Head 数量 8
Head Dimension 128
数据精度 FP16
单个请求上下文长度 8192
并发请求数量 16

FP16 每个元素占用 2 Bytes。

单个请求:

M_{KV}= 2\times32\times8192\times8\times128\times2
=1,073,741,824\ Bytes

约为 1 GiB。

16 个请求:

M_{KV,total}=16\times1GiB=16GiB

也就是说,仅 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。

在其他参数完全相同的情况下:

M_{GQA}=\frac{8}{32}M_{MHA}
M_{MQA}=\frac{1}{32}M_{MHA}

因此,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 时,需要:

N_{\text{blocks}}= \left\lceil\frac{35}{16}\right\rceil =3

三个 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 编号:

BlockIndex=\left\lfloor\frac{35}{16}\right\rfloor=2

Block 内偏移:

Offset=35\bmod16=3

因此:

  • 逻辑 Block 编号为 2。
  • Block 内偏移为 3。

再通过 Block Table 查询对应物理 Block 编号,最终定位 KV Cache 数据。

一般公式:

LogicalBlockIndex= \left\lfloor\frac{Position}{BlockSize}\right\rfloor
BlockOffset=Position\bmod BlockSize
PhysicalBlock= BlockTable[LogicalBlockIndex]

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:

N_{\text{blocks}}= \left\lceil\frac{30}{16}\right\rceil=2

请求开始时需要两个 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