Refix Caching 詳解：實(shí)現(xiàn) KV Cache 的跨請(qǐng)求高效復(fù)用
Prefix Caching 原理的講解視頻可以在這里觀看：https://www.bilibili.com/video/BV1jgTRzSEjS
本文是 vLLM 系列文章的第 3 篇，介紹 vLLM 中 Prefix Caching 的實(shí)現(xiàn)原理。
1 什么是 Prefix Caching
前綴緩存（Prefix Caching）是一種大語言模型推理優(yōu)化技術(shù)，它的核心思想是緩存歷史對(duì)話中的 KV Cache，以便后續(xù)請(qǐng)求能直接重用這些中間結(jié)果。這樣可以顯著降低首 token 延遲，提升整體推理效率。Prefix Caching 尤其適用于多輪對(duì)話、長(zhǎng)文檔問答等高前綴復(fù)用場(chǎng)景。
Prefix Caching 在大語言模型推理中的應(yīng)用場(chǎng)景主要包括以下幾類：
圖片
- Few-shot learning（少樣本學(xué)習(xí)）：多個(gè)請(qǐng)求都包含相同的 few-shot 示例部分，只是最后的問題不同。Prefix Caching 可以將這些 few-shot 示例的 KV Cache 復(fù)用，避免每次都重新計(jì)算相同的示例內(nèi)容。
- Self-consistency（自洽性）：對(duì)于同一個(gè)問題，先采樣多個(gè)不同的推理路徑（重復(fù)請(qǐng)求多次），然后選擇最一致的答案。這些請(qǐng)求都共享相同的前綴（問題部分），Prefix Caching 可以讓每次 decode 時(shí)都直接復(fù)用問題部分的緩存，只計(jì)算不同的答案部分。
- Multi-turn chat（多輪對(duì)話）：多輪對(duì)話中，每一輪的對(duì)話都基于之前的聊天歷史。Prefix Caching 允許每一輪都復(fù)用之前聊天歷史的KV緩存，只對(duì)新增的問答部分進(jìn)行計(jì)算。
- Tree-of-thought（思維樹）：復(fù)雜推理任務(wù)中，一個(gè)問題會(huì)被分解成多個(gè)分支，每個(gè)分支下又有進(jìn)一步的分支。每個(gè)分支都共享前面的搜索歷史作為前綴。Prefix Caching 可以讓所有分支共享公共的歷史部分緩存，只對(duì)各自獨(dú)立的分支內(nèi)容做增量計(jì)算。
Prefix Caching 只會(huì)減少處理查詢（prefill 階段）的時(shí)間，而不會(huì)減少生成新 token（decode 階段）的時(shí)間。
2 PagedAttention 和 Prefix Caching 的關(guān)系
- PagedAttention 主要解決 KV Cache 如何在 GPU 顯存中“按需分配”，通過分頁機(jī)制讓 KV Cache 可以非連續(xù)存儲(chǔ)和動(dòng)態(tài)擴(kuò)容，極大緩解內(nèi)存碎片化問題，實(shí)現(xiàn)高效的內(nèi)存管理。
- Prefix Caching 則專注于“避免重復(fù)算”，即當(dāng)多個(gè)請(qǐng)求有相同的 prompt 前綴時(shí)，只需計(jì)算一次并緩存其 KV，后續(xù)請(qǐng)求直接復(fù)用，顯著降低首 token 時(shí)延，尤其適合多輪對(duì)話和長(zhǎng) system prompt 場(chǎng)景。
維度 | PagedAttention | Prefix Caching |
關(guān)注點(diǎn) | 高效管理 KV Cache 的內(nèi)存分配與碎片化 | 復(fù)用請(qǐng)求間公共前綴的 KV Cache，減少重復(fù)計(jì)算 |
作用階段 | 整個(gè)推理過程，包括 prefill 和 decode 階段 | prefill 階段（推理開始前處理 prompt） |
是否涉及跨請(qǐng)求 | 主要用于單個(gè)請(qǐng)求內(nèi)部的緩存管理 | 針對(duì)不同請(qǐng)求間的共享前綴 |
技術(shù)原理 | 受操作系統(tǒng)虛擬內(nèi)存分頁啟發(fā)，將 KV Cache 分塊（block）動(dòng)態(tài)分配和管理 | 通過哈希、基數(shù)樹等結(jié)構(gòu)檢測(cè)和緩存相同前綴的 KV，跨請(qǐng)求復(fù)用 |
主要作用 | 解決 KV Cache 占用大、內(nèi)存碎片嚴(yán)重、動(dòng)態(tài)擴(kuò)展難等問題，提升顯存利用率和吞吐量 | 避免對(duì)相同前綴重復(fù)計(jì)算，顯著降低首 token 延遲，提升多輪對(duì)話等場(chǎng)景效率 |
典型應(yīng)用 | 任何高并發(fā)、長(zhǎng)序列推理場(chǎng)景 | 長(zhǎng) system prompt、few-shot、對(duì)話歷史復(fù)用、多輪對(duì)話等 |
3 RadixAttention
論文 SGLang: Efficient Execution of Structured Language Model Programs 中提出通過 RadixAttention 來實(shí)現(xiàn)Prefix Caching。
圖片
上圖展示了采用 LRU 淘汰策略的 RadixAttention 操作示例，描繪了 Radix Tree（基數(shù)樹）在不同請(qǐng)求作用下的動(dòng)態(tài)演化過程。這些請(qǐng)求包括兩個(gè)對(duì)話會(huì)話、一批 few-shot 學(xué)習(xí)查詢，以及一次自洽性采樣（self-consistency sampling）。樹的每條邊標(biāo)注了一個(gè)子字符串或一段 token 序列，節(jié)點(diǎn)則通過顏色編碼以區(qū)分不同狀態(tài)：
- 綠色表示新添加的節(jié)點(diǎn)，
- 藍(lán)色表示當(dāng)前時(shí)間點(diǎn)訪問到的緩存節(jié)點(diǎn)，
- 紅色表示已經(jīng)被淘汰的節(jié)點(diǎn)。
具體步驟如下：
- 步驟(1)：Radix Tree 初始為空。
- 步驟(2)：服務(wù)器接收到用戶消息
"Hello"，并生成 LLM 回復(fù)"Hi"。系統(tǒng)提示"You are a helpful assistant"、用戶消息"Hello!"和模型回復(fù)"Hi!"被整合為一條邊，并連接到一個(gè)新節(jié)點(diǎn)。 - 步驟(3)：新的 prompt 到達(dá)，服務(wù)器在樹中找到了該 prompt 的前綴（即第一輪對(duì)話），并重用其 KV cache。新的對(duì)話輪次作為新節(jié)點(diǎn)追加進(jìn)樹中。
- 步驟(4)：開啟新的對(duì)話會(huì)話。為了讓兩個(gè)會(huì)話共享系統(tǒng)提示，“b” 節(jié)點(diǎn)被拆分成兩個(gè)節(jié)點(diǎn)。
- 步驟(5)：第二個(gè)會(huì)話繼續(xù)，但由于內(nèi)存限制，第 (4) 步中的 “c” 節(jié)點(diǎn)被淘汰。新的輪次被追加在 “d” 節(jié)點(diǎn)之后。
- 步驟(6)：服務(wù)器收到一個(gè) few-shot learning 查詢，將其插入樹中。由于該查詢和現(xiàn)有節(jié)點(diǎn)沒有公共前綴，根節(jié)點(diǎn)被拆分。
- 步驟(7)：服務(wù)器收到一批新的 few-shot learning 查詢。它們共享相同的 few-shot 示例，因此將 (6) 中的 “e” 節(jié)點(diǎn)拆分以實(shí)現(xiàn)共享。
- 步驟(8)：服務(wù)器收到來自第一個(gè)對(duì)話會(huì)話的新消息。由于使用 LRU 策略，第二個(gè)對(duì)話的所有節(jié)點(diǎn)（如 “g” 和 “h”）被淘汰。
- 步驟(9)：服務(wù)器收到一個(gè)請(qǐng)求，要求對(duì) (8) 中 “j” 節(jié)點(diǎn)的問題進(jìn)行更多回答采樣，可能是用于自洽性采樣（self-consistency sampling）。為了騰出空間，第 (8) 步中的 “i”、 “k”、 “l(fā)” 節(jié)點(diǎn)被淘汰。
4 vLLM 中的 Prefix Caching
最初，vLLM 支持手動(dòng)前綴緩存，用戶需通過 prefix_pos 參數(shù)顯式指定前綴邊界位置。
PR：https://github.com/vllm-project/vllm/pull/1669
從 v0.4.0 版本開始，vLLM 引入了自動(dòng)前綴緩存（Automatic Prefix Caching），無需手動(dòng)指定即可自動(dòng)識(shí)別并復(fù)用共享前綴。
PR：https://github.com/vllm-project/vllm/pull/2762
4.1 在 vLLM 中啟用 Prefix Caching
4.1.1 環(huán)境準(zhǔn)備
執(zhí)行以下命令安裝 vLLM。
# 安裝 uv，管理 python 虛擬環(huán)境
curl -LsSf https://astral.sh/uv/install.sh | shsource$HOME/.local/bin/env# 安裝 GPU Driverwget https://cn.download.nvidia.com/tesla/565.57.01/NVIDIA-Linux-x86_64-565.57.01.runsh NVIDIA-Linux-x86_64-565.57.01.run --silent# 安裝 CUDA Toolkit（如 nvcc、include、lib64）sudo apt updatesudo apt install -y nvidia-cuda-toolkit# 創(chuàng)建 python 虛擬環(huán)境uv venv vllm-demo --python 3.12 --seedsource vllm-demo/bin/activate# 安裝 vLLMuv pip install vllm4.1.2 離線推理（Offline Inference）
在 vLLM 中設(shè)置 enable_prefix_caching=True 可以啟用 Automatic Prefix Caching。下面這段代碼展示了 vLLM 的 Automatic Prefix Caching 功能：第一次生成關(guān)于 "John Doe 年齡" 的回答時(shí)，需要完整構(gòu)建 KV Cache；而第二次詢問 "Zack Blue 年齡"，由于兩次問題共享相同的長(zhǎng)表格前綴，vLLM 會(huì)自動(dòng)復(fù)用已有緩存，從而顯著減少重復(fù)計(jì)算，加速生成過程。
import time
from vllm import LLM, SamplingParamsLONG_PROMPT = ( "You are a helpful assistant in recognizes the content of tables in markdown format. Here is a table as follows.\n# Table\n" + """
| ID | Name | Age | Occupation | Country | Email | Phone Number | Address ||-----|---------------|-----|---------------|---------------|------------------------|----------------|------------------------------|| 1 | John Doe | 29 | Engineer | USA | john.doe@example.com | 555-1234 | 123 Elm St, Springfield, IL || 2 | Jane Smith | 34 | Doctor | Canada | jane.smith@example.com | 555-5678 | 456 Oak St, Toronto, ON || 3 | Alice Johnson | 27 | Teacher | UK | alice.j@example.com | 555-8765 | 789 Pine St, London, UK || 4 | Bob Brown | 45 | Artist | Australia | bob.b@example.com | 555-4321 | 321 Maple St, Sydney, NSW || 5 | Carol White | 31 | Scientist | New Zealand | carol.w@example.com | 555-6789 | 654 Birch St, Wellington, NZ || 6 | Dave Green | 28 | Lawyer | Ireland | dave.g@example.com | 555-3456 | 987 Cedar St, Dublin, IE || 7 | Emma Black | 40 | Musician | USA | emma.b@example.com | 555-1111 | 246 Ash St, New York, NY || 8 | Frank Blue | 37 | Chef | Canada | frank.b@example.com | 555-2222 | 135 Spruce St, Vancouver, BC || 9 | Grace Yellow | 50 | Engineer | UK | grace.y@example.com | 555-3333 | 864 Fir St, Manchester, UK || 10 | Henry Violet | 32 | Artist | Australia | henry.v@example.com | 555-4444 | 753 Willow St, Melbourne, VIC|| 11 | Irene Orange | 26 | Scientist | New Zealand | irene.o@example.com | 555-5555 | 912 Poplar St, Auckland, NZ || 12 | Jack Indigo | 38 | Teacher | Ireland | jack.i@example.com | 555-6666 | 159 Elm St, Cork, IE || 13 | Karen Red | 41 | Lawyer | USA | karen.r@example.com | 555-7777 | 357 Cedar St, Boston, MA || 14 | Leo Brown | 30 | Chef | Canada | leo.b@example.com | 555-8888 | 246 Oak St, Calgary, AB || 15 | Mia Green | 33 | Musician | UK | mia.g@example.com | 555-9999 | 975 Pine St, Edinburgh, UK || 16 | Noah Yellow | 29 | Doctor | Australia | noah.y@example.com | 555-0000 | 864 Birch St, Brisbane, QLD || 17 | Olivia Blue | 35 | Engineer | New Zealand | olivia.b@example.com | 555-1212 | 753 Maple St, Hamilton, NZ || 18 | Peter Black | 42 | Artist | Ireland | peter.b@example.com | 555-3434 | 912 Fir St, Limerick, IE || 19 | Quinn White | 28 | Scientist | USA | quinn.w@example.com | 555-5656 | 159 Willow St, Seattle, WA || 20 | Rachel Red | 31 | Teacher | Canada | rachel.r@example.com | 555-7878 | 357 Poplar St, Ottawa, ON || 21 | Steve Green | 44 | Lawyer | UK | steve.g@example.com | 555-9090 | 753 Elm St, Birmingham, UK || 22 | Tina Blue | 36 | Musician | Australia | tina.b@example.com | 555-1213 | 864 Cedar St, Perth, WA || 23 | Umar Black | 39 | Chef | New Zealand | umar.b@example.com | 555-3435 | 975 Spruce St, Christchurch, NZ|| 24 | Victor Yellow | 43 | Engineer | Ireland | victor.y@example.com | 555-5657 | 246 Willow St, Galway, IE || 25 | Wendy Orange | 27 | Artist | USA | wendy.o@example.com | 555-7879 | 135 Elm St, Denver, CO || 26 | Xavier Green | 34 | Scientist | Canada | xavier.g@example.com | 555-9091 | 357 Oak St, Montreal, QC || 27 | Yara Red | 41 | Teacher | UK | yara.r@example.com | 555-1214 | 975 Pine St, Leeds, UK || 28 | Zack Blue | 30 | Lawyer | Australia | zack.b@example.com | 555-3436 | 135 Birch St, Adelaide, SA || 29 | Amy White | 33 | Musician | New Zealand | amy.w@example.com | 555-5658 | 159 Maple St, Wellington, NZ || 30 | Ben Black | 38 | Chef | Ireland | ben.b@example.com | 555-7870 | 246 Fir St, Waterford, IE |
""")defget_generation_time(llm, sampling_params, prompts): # time the generation start_time = time.time() output = llm.generate(prompts, sampling_params=sampling_params) end_time = time.time() # print the output and generation time print("-" * 30) print(f"Output: {output[0].outputs[0].text}") print(f"Generation time: {end_time - start_time} seconds.") print("-" * 30)defmain(): # set enable_prefix_caching=True to enable APC llm = LLM(model="deepseek-ai/deepseek-llm-7b-chat", enable_prefix_caching=True) sampling_params = SamplingParams(temperature=0, max_tokens=100) # Querying the age of John Doe get_generation_time( llm, sampling_params, LONG_PROMPT + "Question: what is the age of John Doe? Your answer: The age of John Doe is ", ) # Querying the age of Zack Blue # This query will be faster since vllm avoids computing the KV cache of LONG_PROMPT again. get_generation_time( llm, sampling_params, LONG_PROMPT + "Question: what is the age of Zack Blue? Your answer: The age of Zack Blue is ", )if __name__ == "__main__": main()通過對(duì)比兩次生成時(shí)間，發(fā)現(xiàn)第二次生成時(shí)間顯著縮短，可以直觀感受到 Automatic Prefix Caching 帶來的性能提升。
------------------------------
Output: 29.
Generation time: 0.46364879608154297 seconds.
------------------------------
Adding requests: 100%|███████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 1/1 [00:00<00:00, 180.41it/s]
Processed prompts: 100%|█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████| 1/1 [00:00<00:00, 7.95it/s, est. speed input: 13891.30 toks/s, output: 31.84 toks/s]
------------------------------
Output: 30.
Generation time: 0.13191604614257812 seconds.
------------------------------4.1.3 在線推理（Online Serving）
在 GPU 后端中，v1 版本 的 vLLM 默認(rèn)啟用 Prefix Caching（v0 默認(rèn)禁用），可以通過 --no-enable-prefix-caching 參數(shù)禁用 Prefix Caching。執(zhí)行以下命令啟動(dòng) vLLM 服務(wù)提供在線推理：
vllm serve deepseek-ai/deepseek-llm-7b-chat然后使用以下 Python 代碼請(qǐng)求在線推理服務(wù)，使用和前面離線推理相同的 prompt。
import time
import requestsLONG_PROMPT = ( "You are a helpful assistant in recognizes the content of tables in markdown format. Here is a table as follows.\n# Table\n" + """
| ID | Name | Age | Occupation | Country | Email | Phone Number | Address ||-----|---------------|-----|---------------|---------------|------------------------|----------------|------------------------------|| 1 | John Doe | 29 | Engineer | USA | john.doe@example.com | 555-1234 | 123 Elm St, Springfield, IL || 2 | Jane Smith | 34 | Doctor | Canada | jane.smith@example.com | 555-5678 | 456 Oak St, Toronto, ON || 3 | Alice Johnson | 27 | Teacher | UK | alice.j@example.com | 555-8765 | 789 Pine St, London, UK || 4 | Bob Brown | 45 | Artist | Australia | bob.b@example.com | 555-4321 | 321 Maple St, Sydney, NSW || 5 | Carol White | 31 | Scientist | New Zealand | carol.w@example.com | 555-6789 | 654 Birch St, Wellington, NZ || 6 | Dave Green | 28 | Lawyer | Ireland | dave.g@example.com | 555-3456 | 987 Cedar St, Dublin, IE || 7 | Emma Black | 40 | Musician | USA | emma.b@example.com | 555-1111 | 246 Ash St, New York, NY || 8 | Frank Blue | 37 | Chef | Canada | frank.b@example.com | 555-2222 | 135 Spruce St, Vancouver, BC || 9 | Grace Yellow | 50 | Engineer | UK | grace.y@example.com | 555-3333 | 864 Fir St, Manchester, UK || 10 | Henry Violet | 32 | Artist | Australia | henry.v@example.com | 555-4444 | 753 Willow St, Melbourne, VIC|| 11 | Irene Orange | 26 | Scientist | New Zealand | irene.o@example.com | 555-5555 | 912 Poplar St, Auckland, NZ || 12 | Jack Indigo | 38 | Teacher | Ireland | jack.i@example.com | 555-6666 | 159 Elm St, Cork, IE || 13 | Karen Red | 41 | Lawyer | USA | karen.r@example.com | 555-7777 | 357 Cedar St, Boston, MA || 14 | Leo Brown | 30 | Chef | Canada | leo.b@example.com | 555-8888 | 246 Oak St, Calgary, AB || 15 | Mia Green | 33 | Musician | UK | mia.g@example.com | 555-9999 | 975 Pine St, Edinburgh, UK || 16 | Noah Yellow | 29 | Doctor | Australia | noah.y@example.com | 555-0000 | 864 Birch St, Brisbane, QLD || 17 | Olivia Blue | 35 | Engineer | New Zealand | olivia.b@example.com | 555-1212 | 753 Maple St, Hamilton, NZ || 18 | Peter Black | 42 | Artist | Ireland | peter.b@example.com | 555-3434 | 912 Fir St, Limerick, IE || 19 | Quinn White | 28 | Scientist | USA | quinn.w@example.com | 555-5656 | 159 Willow St, Seattle, WA || 20 | Rachel Red | 31 | Teacher | Canada | rachel.r@example.com | 555-7878 | 357 Poplar St, Ottawa, ON || 21 | Steve Green | 44 | Lawyer | UK | steve.g@example.com | 555-9090 | 753 Elm St, Birmingham, UK || 22 | Tina Blue | 36 | Musician | Australia | tina.b@example.com | 555-1213 | 864 Cedar St, Perth, WA || 23 | Umar Black | 39 | Chef | New Zealand | umar.b@example.com | 555-3435 | 975 Spruce St, Christchurch, NZ|| 24 | Victor Yellow | 43 | Engineer | Ireland | victor.y@example.com | 555-5657 | 246 Willow St, Galway, IE || 25 | Wendy Orange | 27 | Artist | USA | wendy.o@example.com | 555-7879 | 135 Elm St, Denver, CO || 26 | Xavier Green | 34 | Scientist | Canada | xavier.g@example.com | 555-9091 | 357 Oak St, Montreal, QC || 27 | Yara Red | 41 | Teacher | UK | yara.r@example.com | 555-1214 | 975 Pine St, Leeds, UK || 28 | Zack Blue | 30 | Lawyer | Australia | zack.b@example.com | 555-3436 | 135 Birch St, Adelaide, SA || 29 | Amy White | 33 | Musician | New Zealand | amy.w@example.com | 555-5658 | 159 Maple St, Wellington, NZ || 30 | Ben Black | 38 | Chef | Ireland | ben.b@example.com | 555-7870 | 246 Fir St, Waterford, IE |
""")defget_generation_time(prompt): url = "http://localhost:8000/v1/completions" headers = {"Content-Type": "application/json"} payload = { "model": "deepseek-ai/deepseek-llm-7b-chat", "prompt": prompt } start_time = time.time() response = requests.post(url, jsnotallow=payload, headers=headers) end_time = time.time() print("-" * 30) if response.status_code == 200: result = response.json() output_text = result["choices"][0]["text"] print(f"Output: {output_text.strip()}") print(f"Generation time: {end_time - start_time} seconds.") else: print(f"? Error {response.status_code}: {response.text}") print("-" * 30)defmain(): get_generation_time( LONG_PROMPT + "Question: what is the age of John Doe? Your answer: The age of John Doe is " ) get_generation_time( LONG_PROMPT + "Question: what is the age of Zack Blue? Your answer: The age of Zack Blue is " )if __name__ == "__main__": main()輸出結(jié)果如下：
Output: 29.
Generation time: 0.4827253818511963 seconds.
------------------------------
------------------------------
Output: 30.
Generation time: 0.1334974765777588 seconds.
------------------------------4.2 實(shí)現(xiàn)原理
vLLM 選擇了基于哈希的方法來實(shí)現(xiàn) Prefix Caching。具體來說，vLLM 根據(jù)每個(gè) KV block 內(nèi)的 token 和該 block 之前前綴中的 token 來計(jì)算該 block 的哈希值：
Block 1 Block 2 Block 3
[A gentle breeze stirred] [the leaves as children] [laughed in the distance]
Block 1: |<--- block tokens ---->|
Block 2: |<------- prefix ------>| |<--- block tokens --->|
Block 3: |<------------------ prefix -------------------->| |<--- block tokens ---->|在上面的示例中，第一個(gè) block 的 KV Cache 可以通過 token “A gentle breeze stirred” 唯一標(biāo)識(shí)。第三個(gè) block 則可以通過 block 內(nèi)的 token “l(fā)aughed in the distance” 以及前綴 token “A gentle breeze stirred the leaves as children” 唯一標(biāo)識(shí)。
此前，vLLM 中的每個(gè)序列都維護(hù)著一個(gè)從邏輯 KV block 到物理 KV block 的映射。為了實(shí)現(xiàn) KV block 的自動(dòng)緩存，vLLM 還將邏輯 KV block 映射到它們的哈希值，并維護(hù)一個(gè)全局哈希表用于管理所有物理 KV block。這樣一來，所有具有相同哈希值的 KV block（例如不同請(qǐng)求之間共享的前綴 block）都可以映射到同一個(gè)物理 block，從而共享內(nèi)存空間。這種設(shè)計(jì)實(shí)現(xiàn)了自動(dòng)的前綴緩存，無需在 KV block 之間維護(hù)樹狀結(jié)構(gòu)。
4.2.1 Block 的哈希值計(jì)算
在 vllm v1 中，一個(gè) block 的哈希值由 3 個(gè)因素決定：
- parent_block_hash：父 block 的哈希值。
- cur_block_token_ids：該 block 中維護(hù)的 token ids。
- extra_keys：用于確保該 block 唯一性的其他信息，例如 LoRA ID、多模態(tài)輸入的哈希值，以及在多租戶環(huán)境下用于隔離緩存的 cache salt 等。
BlockHashType(
hash((parent_block_hash, curr_block_token_ids_tuple, extra_keys)),
curr_block_token_ids_tuple,
extra_keys
)4.2.2 數(shù)據(jù)結(jié)構(gòu)
在 vLLM 中實(shí)現(xiàn) Prefix Caching 的數(shù)據(jù)結(jié)構(gòu)如下圖所示：
圖片
- Block Pool：管理所有 KV Cache block，提供分配、釋放和緩存 block 的方法。Block Pool 包含所有的
KVCacheBlock，以及用于管理空閑塊的FreeKVCacheBlockQueue，同時(shí)還通過 Cache blocks (cached_block_hash_to_block)（Dict[BlockHashType, Dict[block_id, KVCacheBlock]）維護(hù)哈希值與緩存 block 之間的映射關(guān)系。
classBlockPool:
def__init__(self, num_gpu_blocks: int, enable_caching: bool): # All kv-cache blocks. self.blocks: list[KVCacheBlock] = [ KVCacheBlock(idx) for idx in range(num_gpu_blocks) ] # Free block queue that constructs and manipulates a doubly linked # list of free blocks (including eviction candidates when caching is # enabled). self.free_block_queue = FreeKVCacheBlockQueue(self.blocks) # {block_hash: {block ID: block}}. A cached block is # a full block with a block hash that can be used for prefix caching. # The cached block may be used by running requests or in the # free_block_queue that could potentially be evicted. # NOTE: We currently don't de-duplicate the blocks in the cache, # meaning that if a block becomes full and is cached, we don't check # if there is already an identical block in the cache. This is because # we want to make sure the allocated block IDs won't change so that # block tables are append-only. self.cached_block_hash_to_block: dict[BlockHashType, dict[ int, KVCacheBlock]] = defaultdict(dict)- Free Block Queue（free_block_queue 屬性，F(xiàn)reeKVCacheBlockQueue 實(shí)例）：是一個(gè)由
KVCacheBlock組成的雙向鏈表結(jié)構(gòu)，用于維護(hù)所有空閑的 KV Cache block。 隊(duì)列本身僅維護(hù)head和tail指針，每個(gè) block 通過其 prev_free_block 和 next_free_block 字段鏈接。該結(jié)構(gòu)支持以 O(1) 時(shí)間復(fù)雜度添加、刪除或移動(dòng)任意位置的 block，便于高效實(shí)現(xiàn) LRU 淘汰策略和資源調(diào)度。
classFreeKVCacheBlockQueue:
def__init__(self, blocks: list[KVCacheBlock]) -> None:
self.num_free_blocks = len(blocks)
# Initialize the doubly linked list of free blocks.
self.free_list_head: Optional[KVCacheBlock] = blocks[0]
self.free_list_tail: Optional[KVCacheBlock] = blocks[-1]當(dāng)一個(gè) block 被分配后再釋放時(shí)，會(huì)根據(jù)以下淘汰順序重新添加到隊(duì)列中（越靠前緩存越先被淘汰）：
- 最近最少使用（LRU）的 block 排在最前；
- 如果多個(gè) block 的最后訪問時(shí)間相同（例如由同一個(gè)請(qǐng)求分配）， 那么**哈希 token 數(shù)更多的 block **排在更前?！肮oken數(shù)更多”在 vLLM 的中指的是在 block 鏈中位置更靠后的 block。在一個(gè)序列中：第一個(gè)塊的哈希只依賴于其自身的 token，第二個(gè)塊的哈希依賴于第一個(gè)塊的哈希和自身的 token，第三個(gè)塊的哈希依賴于第二個(gè)塊的哈希和自身的 token，以此類推。因此序列末尾的塊通常包含特定于當(dāng)前請(qǐng)求的內(nèi)容，復(fù)用價(jià)值較低 序列開頭的塊（如系統(tǒng)提示）更可能在不同請(qǐng)求間共享。
- Request blocks 以及 Block Pool 都維護(hù)在 KVCacheManager 類中。
a.req_to_blocks：Dict[req_id: List[KVCacheBlock]]，記錄一個(gè)請(qǐng)求下所有的 block。
b.req_to_block_hashes：Dict[req_id, List[BlockHashType]]，記錄一個(gè)請(qǐng)求下所有的 block 的 hash 值。由于只有滿塊才可以被計(jì)算 hash 值，因此相同請(qǐng)求下，可能存在 len(List[BlockHashType]) < len(List[KVCacheBlock]) 的情況。
classKVCacheManager:
def__init__(
self,
kv_cache_config: KVCacheConfig,
max_model_len: int,
enable_caching: bool = True,
caching_hash_algo: str = "builtin",
num_preallocate_tokens: int = 64,
log_stats: bool = False,
) -> None: self.block_pool = BlockPool(self.num_gpu_blocks, enable_caching) # Mapping from request ID to blocks to track the blocks allocated # for each request, so that we can free the blocks when the request # is finished. self.req_to_blocks: defaultdict[str, list[KVCacheBlock]] = defaultdict(list) # Mapping from request ID to kv block hashes. # This is to avoid recomputing the block hashes for each call of # `get_computed_blocks` or `allocate_slots`. self.req_to_block_hashes: defaultdict[ str, list[BlockHashType]] = defaultdict(list) # {req_id: The number of cached blocks for this given request} # This is used to track the number of cached blocks for each request. # This is only used to track the RUNNING requests, we do not track the # data for reempted ones. self.num_cached_block: dict[str, int] = {}4.2.3 操作
4.2.3.1 分配 Block
調(diào)度器為新請(qǐng)求分配 KV Cache block 的流程如下：
- 調(diào)用
kv_cache_manager.get_computed_blocks()： 根據(jù)請(qǐng)求的 prompt tokens 進(jìn)行哈希，并在緩存中查找對(duì)應(yīng)的 Cache Blocks，獲取已計(jì)算的 block 序列。 - 調(diào)用
kv_cache_manager.allocate_slots()：執(zhí)行以下步驟：
計(jì)算當(dāng)前請(qǐng)求需要分配的新 block 數(shù)量；若可用 block 數(shù)不足，則直接返回；
“觸碰（touch）”已命中的緩存 block：即增加其引用計(jì)數(shù)，并將其從 Free Block Queue 中移除（如果當(dāng)前沒有其他請(qǐng)求在用），這樣做是為了防止這些緩存 block 被淘汰。
通過彈出 Free Block Queue 的隊(duì)頭來分配新 block；如果該 block 是緩存 block，則同時(shí)會(huì)驅(qū)逐該 block，其他請(qǐng)求將無法再復(fù)用此 block。
如果新分配的 block 已經(jīng)被 token 填滿，則立即將其添加到 Cache Blocks 中，以便在同一批次中的其他請(qǐng)求可以復(fù)用。
調(diào)度器為運(yùn)行中的請(qǐng)求分配 KV Cache block 的流程如下：
調(diào)用 kv_cache_manager.allocate_slots()：執(zhí)行以下步驟：
- 計(jì)算當(dāng)前需要分配的新 block 數(shù)量；若可用 block 不足，則返回；
- 同樣從 Free Block Queue 的隊(duì)頭彈出 block；如果彈出的 block 是緩存 block，則同時(shí)驅(qū)逐該 block，避免其他請(qǐng)求再復(fù)用；
- 將 token ID 寫入已有 block 和新分配的 block 中的空槽位。如果某個(gè) block 被填滿，則將其添加到 Cache Blocks 中以進(jìn)行緩存。
4.2.3.2 釋放 Block
當(dāng)一個(gè)請(qǐng)求結(jié)束時(shí)，如果其占用的 block 沒有被其他請(qǐng)求使用（引用計(jì)數(shù)為 0），則釋放這些 block。 在本例中，釋放了請(qǐng)求 1 以及其關(guān)聯(lián)的 block 2、3、4 和 8?？梢钥吹?，釋放的 blocks 會(huì)按照逆序添加到 Free Block Queue 的尾部。這是因?yàn)檎?qǐng)求的最后一個(gè) block 通常哈希了更多的 token，更具請(qǐng)求特異性，不太可能被其他請(qǐng)求復(fù)用，因此應(yīng)當(dāng)優(yōu)先被淘汰。
圖片
4.2.3.3 驅(qū)逐（LRU）
當(dāng) Free Block Queue 的隊(duì)頭 block（即最近最少使用的 block）仍處于緩存狀態(tài)時(shí)，必須將其驅(qū)逐，以防止被其他請(qǐng)求繼續(xù)使用。 具體的驅(qū)逐過程包括以下步驟：
- 從 Free Block Queue 的隊(duì)頭彈出該 block，即要被驅(qū)逐的 LRU block；
- 從 Cache Blocks 中移除該 block 的 ID；
- 從 KVCacheBlock 移除該 block 對(duì)應(yīng)的哈希值。
4.3 示例
在本示例中，假設(shè)每個(gè) block 的大小為 4（即每個(gè) block 可緩存 4 個(gè) token），整個(gè) KV Cache Manager 中共有 10 個(gè) block。
時(shí)刻 1：緩存為空，一個(gè)新請(qǐng)求 Request 0（ABCD|EFGH|IJKL|MNO） 到來。分配了 4 個(gè) block，其中 3 個(gè)已填滿并被緩存，第 4 個(gè) block 部分填充，僅包含 3 個(gè) token。所有 prompt tokens 都被調(diào)度。
圖片
Block 的哈希值不是只基于自己的 token，而是包含了完整的前綴路徑信息。例如，ID=2 的 hash 是 “A-L”，表示這是一個(gè)對(duì) token
A到L的 prefix 路徑（前綴+當(dāng)前塊）的唯一哈希標(biāo)識(shí)。
時(shí)刻 3：Request 0 經(jīng)過 2 次推理過程（1 次 prefill + 1 次 decode），達(dá)到下面這個(gè)狀態(tài)。Request 0 將 block 3 填滿，并請(qǐng)求一個(gè)新 block 以繼續(xù) decode。此時(shí)將 block 3 緩存，并分配 block 4。
圖片
時(shí)刻 4：新的請(qǐng)求 Request 1（ABCD|EFGH|IJkl|mn） 帶著 14 個(gè) prompt token 到來，其中前 10 個(gè) token 與 Request 0 相同?？梢钥吹剑挥星皟蓚€(gè) block（共 8 個(gè) token）命中緩存，因?yàn)榈?3 個(gè) block 僅匹配了其 4 個(gè) token 中的前 2 個(gè)。Request 1 使用的 block 5 已經(jīng)被 token 填滿，因此被緩存。
圖片
時(shí)刻 5：Request 0 已完成并被釋放。Block 2、3 和 4 按照逆序被添加到空閑隊(duì)列中（但 Block 2 和 3 仍處于緩存狀態(tài)）。Block 0 和 1 未被加入空閑隊(duì)列，因?yàn)樗鼈內(nèi)员?Request 1 使用。
圖片
時(shí)刻 6：Request 1 推理完畢，同樣需要釋放掉相關(guān)資源。（原圖有誤，用紅筆做了修正）
圖片
時(shí)刻 7：Request 2（ABCD | EFGH | IJKL | 0-3 | 4-7 | 8-11 | 12-15 | 16） 帶著 29 個(gè) prompt token 到來，其中前 12 個(gè) token 與 Request 0 完全相同。此時(shí)，前 3 個(gè) block（block 0 ~ block 2）可以命中緩存，因此在正式分配新 block 之前，會(huì)先被 touch 并從 Free Block Queue 中移除。隊(duì)列順序從原本的 7 - 8 - 9 - 4 - 3 - 2 - 6 - 5 - 1 - 0 更新為 7 - 8 - 9 - 4 - 3 - 6 - 5。剩余 5 個(gè)所需 block 將從 Free Block Queue 頭部依次分配，因此獲取了 block 7、8、9、4 和 3。由于 block 3 仍處于緩存狀態(tài)（哈希值 A–P），因此需要將其從緩存中驅(qū)逐。
這個(gè)例子可以幫助我們更好體會(huì)到不立刻驅(qū)逐 block、以及逆序 append block 的好處。
圖片
4.4 幾個(gè)注意點(diǎn)
4.4.1 只緩存完整的 block
在 vLLM 中只緩存完整的 block，假如一個(gè) block 沒有被 token 完全填滿，那么這個(gè) block 就不會(huì)被緩存。
# 假設(shè) block_size = 4
# 請(qǐng)求的 token 序列如下：
tokens = ["A", "B", "C", "D", "E", "F", "G"]
# vLLM 會(huì)將 tokens 分成 KV blocks，每個(gè) block 包含 4 個(gè) token
# Block 0: ["A", "B", "C", "D"] ? — 完整的 block，滿足 4 個(gè) token，會(huì)被緩存
# Block 1: ["E", "F", "G"] ? — 只包含 3 個(gè) token，未填滿，不會(huì)被緩存4.4.2 哈希沖突
哈希鍵結(jié)構(gòu)并不能 100% 避免沖突。從理論上講，不同的前綴 token 仍然有可能產(chǎn)生相同的哈希值。為了在多租戶環(huán)境中避免哈希沖突，建議使用 SHA256 作為哈希函數(shù)，而不是默認(rèn)的內(nèi)置哈希。自 vLLM v0.8.3 起已支持 SHA256，可通過 --prefix-caching-hash-algo 命令行參數(shù)啟用。但請(qǐng)注意，這會(huì)帶來一定的性能開銷：大約每個(gè) token 增加 100–200 ns（對(duì)于 5 萬個(gè) token，大約增加 6 ms）。
4.4.3 前綴相同才能復(fù)用緩存
只有前綴相同的部分才能復(fù)用緩存，中間某一段相同是無法復(fù)用的。
假設(shè)對(duì)于 req1:
ABCD | EFGH
假設(shè)對(duì)于 req2:
DCAB | EFGH雖然兩者在 EFGH 部分的 token 內(nèi)容完全一致，但 req2 不能復(fù)用 req1 的 EFGH block。 這是因?yàn)?Transformer 的每一層都具有前向依賴性——每個(gè) token 的表示不僅依賴它自身，還受到前面所有 token 的影響。因此，只要前綴不同，即使中間的 token 完全相同，其 KV 緩存結(jié)果也會(huì)不同，無法共享。
5 Prefix Cache Aware Routing
Prefix Caching 雖然能有效減少單個(gè)實(shí)例內(nèi)部的 KV Cache 重復(fù)計(jì)算，但在多副本部署場(chǎng)景下，僅靠單實(shí)例的緩存復(fù)用遠(yuǎn)遠(yuǎn)不夠。即使多個(gè)請(qǐng)求具有相同前綴，仍可能被隨機(jī)分配到不同實(shí)例，導(dǎo)致每個(gè)實(shí)例都重復(fù)計(jì)算并緩存相同前綴。Prefix Cache Aware Routing 則是為了解決這個(gè)問題，它能根據(jù)請(qǐng)求前綴的匹配情況，智能地將請(qǐng)求路由到已有緩存的 worker，從而在集群層面實(shí)現(xiàn)更高效的 KV Cache 利用率。
目前，已經(jīng)有不少項(xiàng)目實(shí)現(xiàn)了 Prefix Cache Aware Routing，例如：
- vLLM Production Stack 支持通過 LMCache 實(shí)現(xiàn) Prefix Cache Aware Routing。另外 vLLM Production Stack 還有一個(gè)提案 RFC: prefix-cache-aware routing 中，其中實(shí)現(xiàn)了兩種策略：基于 HashTrie 的匹配和基于 SimHash 的一致性哈希。其中，HashTrie 的方案在緩存命中率上表現(xiàn)更優(yōu)。
- SGLang 則采用了一種基于請(qǐng)求歷史構(gòu)建 Radix Tree（基數(shù)樹）的緩存感知路由策略。
- AIBrix 實(shí)現(xiàn)了一個(gè)分布式前綴緩存池，并對(duì) vLLM 進(jìn)行了定制化修改以支持從該緩存池加載緩存。在請(qǐng)求路由階段，它的 Prefix Router 能最大化模型服務(wù)器上的前綴緩存命中率。目前支持兩種策略：一種是類似 vLLM 的哈希匹配，另一種是類似 SGLang 的 Radix Tree 匹配。
- KubeAI 使用了一種帶有負(fù)載邊界的一致性哈希算法（CHWBL），它會(huì)對(duì)請(qǐng)求前綴（可配置長(zhǎng)度）進(jìn)行哈希，但可能因此犧牲一部分精度。當(dāng)服務(wù)器負(fù)載過高時(shí)，它還會(huì)觸發(fā) "overflow" 策略將請(qǐng)求溢出到其他節(jié)點(diǎn)。
- Gateway API Inference Extension EPP（End-point Picker） 通過模擬模型服務(wù)器的緩存淘汰策略（如 LRU）構(gòu)建一張所有后端服務(wù)器的近似前綴緩存索引表，用于指導(dǎo)后續(xù)請(qǐng)求的智能路由。關(guān)于 Gateway API Inference Extension 的詳細(xì)解釋可以參考：為 Kubernetes 提供智能的 LLM 推理路由：Gateway API Inference Extension 深度解析。
下圖展示了 Gateway API Inference Extension 的 Prefix Cache Aware Routing 的工作流程。
SGLang v0.4 為 LLM 推理引擎引入了具備緩存感知（cache-aware）能力的負(fù)載均衡器。該負(fù)載均衡器能預(yù)測(cè)各個(gè) worker 的 prefix KV cache 命中率，并自動(dòng)選擇匹配率最高的 worker。測(cè)試顯示其吞吐量最高提升 1.9 倍，緩存命中率改善達(dá) 3.8 倍，且工作節(jié)點(diǎn)越多優(yōu)勢(shì)越顯著。下圖展示了緩存感知負(fù)載均衡器與傳統(tǒng)輪詢負(fù)載均衡器在數(shù)據(jù)并行中的差異。緩存感知負(fù)載均衡器會(huì)維護(hù)一個(gè)與 worker 實(shí)際基數(shù)樹近似的基數(shù)樹。該樹會(huì)進(jìn)行惰性更新，幾乎沒有任何開銷。
圖片
SGLang Router 的主要特性包括：
- 多節(jié)點(diǎn)支持：支持在多臺(tái)機(jī)器上部署 worker，單個(gè) Router 可連接分布式的多個(gè) worker，便于水平擴(kuò)展，同時(shí)在分布式環(huán)境中保持對(duì)緩存命中的感知能力。
- 感知緩存的路由機(jī)制：將請(qǐng)求優(yōu)先發(fā)送到緩存命中率更高的 worker，并結(jié)合負(fù)載均衡策略避免負(fù)載不均。
- 免通信設(shè)計(jì)：worker 之間無需同步緩存狀態(tài)，Router 通過跟蹤請(qǐng)求歷史來近似推斷各個(gè) worker 的緩存狀態(tài)，而不是直接查詢 worker 的實(shí)際緩存信息。
- 高性能實(shí)現(xiàn)：使用純 Rust 編寫，支持高并發(fā)，開銷極低，性能相比基于 Python 的方案提升達(dá) 2 倍。
- 獨(dú)立包形式發(fā)布：以
sglang-router包發(fā)布，提供 Python 接口，并配有 CLI 工具，方便用戶快速上手使用。
SGLang Router 在分布式系統(tǒng)層面優(yōu)化多 worker 環(huán)境中的緩存利用率，而核心的 prefix caching 則專注于單個(gè) worker 內(nèi)的計(jì)算重用。
使用方式如下，先安裝 sglang 和 sglang-router 包。
uv venv sglang-demo --python 3.12 --seed
source sglang-demo/bin/activate
uv pip install sglang[all]
uv pip install sglang-router可以使用 sglang_router.launch_server 一起啟動(dòng) SGLang Router 和多個(gè) worker。--dp-size 表示你要啟動(dòng)多少個(gè)獨(dú)立的 worker 來進(jìn)行數(shù)據(jù)并行（data parallel）。這里啟動(dòng)了 2 個(gè) worker，因此你的服務(wù)器上需要 2 個(gè) GPU。
python -m sglang_router.launch_server \
--model-path deepseek-ai/DeepSeek-R1-Distill-Qwen-1.5B \
--dp-size 2 --host 0.0.0.0如果是在多個(gè)節(jié)點(diǎn)上啟動(dòng) worker，然后在主節(jié)點(diǎn)上啟用 SGLang Router，可以使用 sglang_router.launch_router。
# 先分別啟動(dòng)幾個(gè) worker
# 在第一個(gè)窗口執(zhí)行
python -m sglang.launch_server --model-path deepseek-ai/DeepSeek-R1-Distill-Qwen-1.5B --host 0.0.0.0 --port 30001 --base-gpu-id 0
# 在第二個(gè)窗口執(zhí)行
python -m sglang.launch_server --model-path deepseek-ai/DeepSeek-R1-Distill-Qwen-1.5B --host 0.0.0.0 --port 30002 --base-gpu-id 1
# 啟動(dòng) SGLang Router
# 在第三個(gè)窗口執(zhí)行
python -m sglang_router.launch_router \
--worker-urls http://localhost:30001 http://localhost:30002再開啟一個(gè)窗口發(fā)送請(qǐng)求到 SGLang Router，反復(fù)發(fā)送多次請(qǐng)求：
curl -X POST http://localhost:30000/generate \
-H "Content-Type: application/json" \
-d '{"text": "What is the capital of France?"}'可以看到請(qǐng)求始終落到其中一個(gè) worker 上。（只會(huì)在一個(gè) worker 的日志中看到請(qǐng)求信息）
[2025-06-08 21:06:35] Prefill batch. #new-seq: 1, #new-token: 7, #cached-token: 1, token usage: 0.00, #running-req: 0, #queue-req: 0
2025-06-08 21:06:35,733 - INFO - flashinfer.jit: Loading JIT ops: cascade
2025-06-08 21:06:35,741 - INFO - flashinfer.jit: Finished loading JIT ops: cascade
[2025-06-08 21:06:36] Decode batch. #running-req: 1, #token: 41, token usage: 0.00, cuda graph: True, gen throughput (token/s): 0.88, #queue-req: 0
[2025-06-08 21:06:36] Decode batch. #running-req: 1, #token: 81, token usage: 0.00, cuda graph: True, gen throughput (token/s): 122.53, #queue-req: 0
[2025-06-08 21:06:36] Decode batch. #running-req: 1, #token: 121, token usage: 0.00, cuda graph: True, gen throughput (token/s): 121.24, #queue-req: 0
[2025-06-08 21:06:36] INFO: 127.0.0.1:50554 - "POST /generate HTTP/1.1" 200 OK
[2025-06-08 21:06:38] Prefill batch. #new-seq: 1, #new-token: 1, #cached-token: 7, token usage: 0.00, #running-req: 0, #queue-req: 0
[2025-06-08 21:06:39] Decode batch. #running-req: 1, #token: 33, token usage: 0.00, cuda graph: True, gen throughput (token/s): 16.84, #queue-req: 0
[2025-06-08 21:06:39] Decode batch. #running-req: 1, #token: 73, token usage: 0.00, cuda graph: True, gen throughput (token/s): 122.95, #queue-req: 0
[2025-06-08 21:06:39] Decode batch. #running-req: 1, #token: 113, token usage: 0.00, cuda graph: True, gen throughput (token/s): 122.47, #queue-req: 0
[2025-06-08 21:06:39] INFO: 127.0.0.1:50554 - "POST /generate HTTP/1.1" 200 OK
[2025-06-08 21:06:41] Prefill batch. #new-seq: 1, #new-token: 1, #cached-token: 7, token usage: 0.00, #running-req: 0, #queue-req: 0
[2025-06-08 21:06:41] Decode batch. #running-req: 1, #token: 25, token usage: 0.00, cuda graph: True, gen throughput (token/s): 21.48, #queue-req: 0
[2025-06-08 21:06:41] INFO: 127.0.0.1:50554 - "POST /generate HTTP/1.1" 200 OK在 SGLang Router 的日志上也可以看出，請(qǐng)求被轉(zhuǎn)發(fā)給了 worker 1。
[Router (Rust)] 2025-06-08 21:06:08 - INFO - ?? Initializing router on 127.0.0.1:30000
[Router (Rust)] 2025-06-08 21:06:08 - INFO - ?? Initializing workers on ["http://localhost:30001", "http://localhost:30002"][Router (Rust)] 2025-06-08 21:06:08 - INFO - ?? Policy Config: CacheAwareConfig { cache_threshold: 0.5, balance_abs_threshold: 32, balance_rel_threshold: 1.0001, eviction_interval_secs: 60, max_tree_size: 16777216, timeout_secs: 300, interval_secs: 10 }[Router (Rust)] 2025-06-08 21:06:08 - INFO - ?? Max payload size: 4 MB[Router (Rust)] 2025-06-08 21:06:08 - INFO - All workers are healthy[Router (Rust)] 2025-06-08 21:06:08 - INFO - ? Serving router on 127.0.0.1:30000[Router (Rust)] 2025-06-08 21:06:08 - INFO - ? Serving workers on ["http://localhost:30001", "http://localhost:30002"][Router (Rust)] 2025-06-08 21:06:08 - INFO - starting 32 workers[Router (Rust)] 2025-06-08 21:06:08 - INFO - Actix runtime found; starting in Actix runtime[Router (Rust)] 2025-06-08 21:06:08 - INFO - starting service: "actix-web-service-127.0.0.1:30000", workers: 32, listening on: 127.0.0.1:30000[Router (Rust)] 2025-06-08 21:07:08 - INFO - Before eviction - Used size per tenant:[Router (Rust)] 2025-06-08 21:07:08 - INFO - Tenant: http://localhost:30001, Size: 0[Router (Rust)] 2025-06-08 21:07:08 - INFO - Tenant: http://localhost:30002, Size: 0[Router (Rust)] 2025-06-08 21:07:08 - INFO - After eviction - Used size per tenant:[Router (Rust)] 2025-06-08 21:07:08 - INFO - Tenant: http://localhost:30001, Size: 0[Router (Rust)] 2025-06-08 21:07:08 - INFO - Tenant: http://localhost:30002, Size: 0[Router (Rust)] 2025-06-08 21:07:08 - INFO - Processed Queue: {"http://localhost:30002": 0, "http://localhost:30001": 3}[Router (Rust)] 2025-06-08 21:07:08 - INFO - Running Queue: {"http://localhost:30002": 0, "http://localhost:30001": 0}6 總結(jié)
Prefix Caching 通過緩存并復(fù)用多個(gè)請(qǐng)求中相同前綴的 KV Cache，有效降低了大語言模型推理中的首 token 延遲和計(jì)算成本。與 PagedAttention 關(guān)注內(nèi)存管理不同，Prefix Caching 專注于跨請(qǐng)求的計(jì)算復(fù)用，特別適用于多輪對(duì)話、few-shot 學(xué)習(xí)等場(chǎng)景。實(shí)現(xiàn)方式上，SGLang 采用基數(shù)樹（RadixAttention）方案，而 vLLM 則使用基于哈希的方法。在分布式部署環(huán)境中，Prefix Cache Aware Routing 進(jìn)一步優(yōu)化了集群級(jí)別的緩存利用率，通過智能路由將請(qǐng)求發(fā)送到緩存命中率更高的節(jié)點(diǎn)。
7 附錄
7.1 Few-shot learning
Few-shot learning 就是通過在 prompt 中給模型少量任務(wù)示例，讓模型在沒有專門微調(diào)的情況下，理解并完成新任務(wù)。
圖片
7.2 Self-consistency
Self-consistency 的概念來源于論文 Self-Consistency Improves Chain of Thought Reasoning in Language Models。
該方法基于這樣的假設(shè)：在復(fù)雜推理任務(wù)中，從問題到唯一正確答案通常存在多種不同的推理路徑。
其核心方案是用 self-consistency 解碼策略替代傳統(tǒng)的貪婪解碼。具體做法是：對(duì)語言模型進(jìn)行多次采樣，生成多條不同的推理路徑（即重復(fù)請(qǐng)求多次），然后根據(jù)這些路徑的最終答案進(jìn)行投票，選出最一致的答案作為最終輸出。
Self-consistency 策略認(rèn)為復(fù)雜推理任務(wù)往往可以通過多條路徑獲得正確解，因此通過抽樣生成一個(gè)多樣化的推理路徑集合，并選取一致性最高的結(jié)果，有效降低了貪婪解碼帶來的隨機(jī)性。
Self-consistency 的核心流程如下：
- Step 1：使用思維鏈（Chain-of-Thought）提示，引導(dǎo)模型進(jìn)行逐步推理；
- Step 2：對(duì)語言模型進(jìn)行多次采樣，生成多個(gè)推理路徑；
- Step 3：對(duì)不同路徑的最終答案進(jìn)行投票，選擇一致性最高的答案輸出。
圖片
7.3 Chain of Thought
Chain of Thought (CoT) 是一種增強(qiáng)語言模型推理能力的技術(shù)，特別適用于需要多步推理的問題。通過在模型的提示中加入一系列的中間推理步驟，可以幫助模型進(jìn)行復(fù)雜的推理任務(wù)，從而避免單純的“直接回答”模式。CoT 使得模型能夠理解并生成推理過程，而不是直接給出答案，從而提高其在復(fù)雜問題上的表現(xiàn)。
CoT 有兩種應(yīng)用模式：
Few-Shot CoT
在 Few-Shot CoT 中，開發(fā)者給出一兩個(gè)示例，在示例中明確展示如何進(jìn)行思維鏈的推理。通過這些示例，模型能夠?qū)W習(xí)如何通過逐步推理得出結(jié)論。
示例：
假設(shè)用戶詢問：“我想為朋友的生日挑選一束花?！?
步驟1：理解問題，確定用戶的需求。
步驟2：列出可能適合生日的花種。
步驟3：根據(jù)花的象征意義、花朵的顏色和花期，篩選出推薦的花種。這種逐步思考的過程可以讓模型根據(jù)需求生成符合用戶期望的推薦。
Zero-Shot CoT
在 Zero-Shot CoT 中，開發(fā)者直接告訴模型進(jìn)行逐步推理。例如，通過提示“讓我們一步步地思考”，模型就能自動(dòng)產(chǎn)生更清晰、合理的推理步驟，而不需要提前給出示例。
示例：
假設(shè)用戶詢問：“我想為我的女朋友購買一些花，她喜歡粉色和紫色的花。”
通過簡(jiǎn)單的提示：“讓我們一步步思考”
模型就能給出以下推理過程：
步驟1：理解需求（粉色和紫色的花）。
步驟2：列舉適合的花種（例如粉色的玫瑰、紫色的蘭花等）。
步驟3：結(jié)合花的象征意義和花卉的實(shí)際情況（如價(jià)格、季節(jié)性等），給出推薦。7.4 Tree of Thought
Tree of Thought (ToT) 進(jìn)一步擴(kuò)展了 CoT 的理念，特別適用于需要多步驟推理的復(fù)雜任務(wù)。與 CoT 不同，ToT 框架不僅要求生成思維鏈，而是生成多個(gè)思維路徑，并通過“思維樹”進(jìn)行探索。每個(gè)思維步驟都具有多個(gè)備選方案，模型會(huì)在這些方案中搜索最優(yōu)解。
示例：
假設(shè)用戶詢問：“我想為我的妻子買一束鮮花，但我不確定選擇哪種。她喜歡淡雅的顏色和花香?！?在 ToT 框架下，模型會(huì)按照以下步驟進(jìn)行思考：
思維步驟1：理解需求（淡雅的顏色和花香）。
思維步驟2：列出候選花種：百合、玫瑰、紫羅蘭、桔梗、康乃馨。
思維步驟3：評(píng)估每種花是否符合要求（花香、顏色、花期等）。
思維步驟4：通過多條思維路徑篩選出最優(yōu)選擇（如百合、紫羅蘭等）。
最終推薦：基于推理過程給出具體建議，例如：“考慮到您妻子喜歡淡雅的顏色和花香，我建議選擇百合或紫羅蘭，它們既符合顏色要求又有花香?！?/code>CoT 與 ToT 的區(qū)別與聯(lián)系
- CoT：專注于引導(dǎo)模型逐步推理，強(qiáng)調(diào)思考的過程，可以通過單一路徑進(jìn)行推理并得出答案。
- ToT：在 CoT 的基礎(chǔ)上，加入了多條推理路徑的選擇，使得模型能夠在多條思維路徑中搜索最優(yōu)解。ToT 更適合處理復(fù)雜問題，尤其是需要多個(gè)選擇和深度探索的場(chǎng)景。
7.5 前綴樹（Trie）和 基數(shù)樹（Radix Tree）
基數(shù)樹（Radix Tree）和前綴樹（Trie）的區(qū)別主要在于結(jié)構(gòu)的緊湊性和節(jié)點(diǎn)的表示方式：
- 前綴樹（Trie） 是一種按字符逐層拆分的樹結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)只存儲(chǔ)一個(gè)字符，路徑上的字符連接起來表示字符串。它的層級(jí)深度通常等于字符串的長(zhǎng)度，節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)較多（比如 26 個(gè)英文字母），空間利用率較低，但查找操作簡(jiǎn)單直觀。Trie 這個(gè)術(shù)語來自于 retrieval。根據(jù)詞源學(xué)，trie 的發(fā)明者 Edward Fredkin 把它讀作
/?tri?/，不過，大部分人把它讀作/?tra?/。
圖片
- 基數(shù)樹（Radix Tree） 也稱為壓縮前綴樹，是對(duì) Trie 的空間優(yōu)化。它將 Trie 中只有一個(gè)子節(jié)點(diǎn)的路徑節(jié)點(diǎn)合并成一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)上存儲(chǔ)的是一段字符序列（而非單個(gè)字符），從而減少樹的深度和節(jié)點(diǎn)數(shù)量，提高空間利用率。基數(shù)樹的邊可以表示多個(gè)字符，查找時(shí)按塊比較，適合處理長(zhǎng)字符串和有長(zhǎng)公共前綴的集合。
圖片
因此，基數(shù)樹可以看作是前綴樹的一種壓縮和優(yōu)化版本，兼具 Trie 的前綴查找特性和更高的空間效率。
8 參考資料
- 圖解Vllm V1系列5：調(diào)度器策略（Scheduler）：https://zhuanlan.zhihu.com/p/1908153627639551302
- LLM Load Balancing at Scale: Consistent Hashing with Bounded Loads：https://www.kubeai.org/blog/2025/02/26/llm-load-balancing-at-scale-chwbl/
- SGLang Router for Data Parallelism：https://docs.sglang.ai/router/router.html
- SGLang v0.4: Zero-Overhead Batch Scheduler, Cache-Aware Load Balancer, Faster Structured Outputs：https://lmsys.org/blog/2024-12-04-sglang-v0-4/
- vLLM的prefix cache為何零開銷：https://zhuanlan.zhihu.com/p/1896927732027335111
- Fast and Expressive LLM Inference with RadixAttention and SGLang：https://lmsys.org/blog/2024-01-17-sglang/
- EP05-vLLM源碼講解直播筆記-Prefix Caching：https://kevincheung2259.github.io/2025/04/16/vLLM-EP05/
- [Prefill優(yōu)化][萬字]??原理&圖解vLLM Automatic Prefix Cache(RadixAttention): 首Token時(shí)延優(yōu)化：https://zhuanlan.zhihu.com/p/693556044
- 圖解Vllm V1系列6：KVCacheManager與PrefixCaching：https://mp.weixin.qq.com/s/Ta7jh-2g7lAEiFOjcSJHVw
- 圖解大模型計(jì)算加速系列：vLLM源碼解析3，Prefix Caching：https://mp.weixin.qq.com/s/bAY4OGqQlEeBaITIwxQEuw
- Prefix Cache Aware Proposal：https://github.com/kubernetes-sigs/gateway-api-inference-extension/issues/498
- AIBrix v0.3.0 發(fā)布：KVCache 多級(jí)卸載、前綴緩存、公平路由與基準(zhǔn)測(cè)試工具：https://mp.weixin.qq.com/s/1__uUX7xMoQ6q7HFXrP2Bw
- 大模型推理加速與KV Cache（五）：Prefix Caching：https://zhuanlan.zhihu.com/p/739669365
- CoT系列-Self-Consistency(year 2022.Mar, Google)：https://zhuanlan.zhihu.com/p/609739922
- PR [Experimental] Prefix Caching Support：https://github.com/vllm-project/vllm/pull/1669
- PR Add Automatic Prefix Caching：https://github.com/vllm-project/vllm/pull/2762
- SgLang代碼細(xì)讀-3.Cache：https://www.cnblogs.com/sunstrikes/p/18891538
