프리픽스 캐싱

프리픽스 캐싱 (Prefix Caching)

같은 프롬프트 앞부분을 여러 요청이 공유할 때, 그 공통 부분의 KV 캐시를 다시 계산하지 않고 재사용하면 추론이 훨씬 빨라져요. vLLM의 프리픽스 캐싱(prefix caching)이 바로 이 일을 해주는 기능이에요. 특히 대화 히스토리나 시스템 프롬프트처럼 자주 반복되는 앞부분이 있는 워크로드에서 효과가 커요.

이 문서에서는 vLLM V1에서 프리픽스 캐싱이 어떤 데이터 구조 위에서 동작하는지, 주요 KV 캐시 연산(할당·추가·해제·축출)의 흐름, 그리고 한 요청이 처음부터 끝까지 어떻게 캐시를 타는지 차례로 살펴볼게요.

기본 아이디어

프리픽스 캐싱의 핵심은 KV 캐시를 블록 단위로 관리하고, 각 블록에 해시를 붙여 두는 거예요. 프롬프트 토큰들이 같은 해시를 만들면 같은 블록으로 판정하고 재사용하죠. 이때 프롬프트를 해싱하는 방식은 여러 가지가 있는데, 단순 해시(finite hash)는 블록 안의 모든 토큰 조합마다 해시가 달라져 중간만 공유된 프롬프트에서 캐시 적중률이 떨어져요. 그래서 vLLM은 해시 체인(hash chain) 방식을 써요. 즉 현재 블록의 해시가 이전 블록 해시에 의존하도록 해서, 첫 블록부터 순서대로 일치하면 이후 블록까지 자연스럽게 재사용할 수 있게 해요.

이미지 입력과 해시 — 이미지 같은 멀티모달 입력이 있으면 자리표시자(placeholder) 토큰과 실제 이미지를 구분해야 해요. 이 문제를 해결하기 위해 프런트엔드 이미지 프로세서가 만든 이미지 해시를 "extra hash"로 인코딩해요. 예를 들어 블록 크기가 16이고 프롬프트에 41개의 자리표시자 토큰이 있다면, 각 블록은 자기 토큰 ID들과 함께 같은 이미지 해시를 extra hash로 갖게 돼요. 이렇게 해서 같은 이미지를 쓴 프롬프트만 캐시를 공유할 수 있어요.

보안을 위한 캐시 격리 — 공유 환경에서 프라이버시를 지키기 위해, vLLM은 요청 단위로 선택적인 salt를 넣어 프리픽스 캐시 재사용을 격리할 수 있어요. 요청에 cache_salt를 포함하면 이 값이 첫 블록의 해시에 섞여 들어가서, 같은 salt를 쓴 요청끼리만 캐시 블록을 재사용할 수 있어요. 이렇게 하면 응답 지연 차이로 캐시된 내용을 유추하는 타이밍 공격을 막을 수 있으면서도 성능 손실은 없어요.

{
  "messages": [
    {"role": "system", "content": "You are a helpful assistant."},
    {"role": "user", "content": "Here is a document with details about the world series: ..."},
    {"role": "user", "content": "Who won the world series in 2020?"}
  ],
  "cache_salt": "your-cache-salt"
}

이렇게 하면 캐시 공유는 명시적으로 같은 salt에 합의한 사용자들 사이로 제한돼요. 같은 신뢰 그룹 안에서는 캐시를 재사용하고, 그 밖의 사용자와는 격리되죠.

데이터 구조

V1의 프리픽스 캐싱은 KV 캐시 매니저에서 구현돼요. 기본 구성 요소는 "Block" 데이터 클래스(단순화 버전)예요.

class KVCacheBlock:
    # The block ID (immutable)
    block_id: int
    # The block hash (will be assigned when the block is full,
    # and will be reset when the block is evicted).
    block_hash: BlockHash
    # The number of requests using this block now.
    ref_cnt: int

    # The pointers to form a doubly linked list for the free queue.
    prev_free_block: "KVCacheBlock | None" = None
    next_free_block: "KVCacheBlock | None" = None

설계상 두 가지를 짚을게요.

1. KV 캐시 매니저를 초기화할 때 모든 KVCacheBlock을 미리 블록 풀(block pool)로 할당해요. 이렇게 하면 파이썬 객체 생성 오버헤드를 피하고, 모든 블록을 항상 쉽게 추적할 수 있어요.
2. KVCacheBlock에 이중 연결 리스트 포인터를 직접 넣어서 자유 큐(free queue)를 바로 만들 수 있어요. 여기서 두 가지 이점이 생겨요. 첫째, 리스트 중간의 요소를 꼬리로 옮기는 걸 O(1)로 할 수 있어요. 둘째, 요소를 감싸는 또 다른 파이썬 큐(예: deque)를 도입하지 않아도 돼요.

그래서 KV 캐시 매니저가 초기화되면 다음 구성 요소들이 생겨요.

• Block Pool — KVCacheBlock 목록
• Free Block Queue — 헤드·테일 블록 포인터만 저장
• Cache blocks — 해시 키 → 블록 ID 매핑
• Request blocks — 요청 ID → 할당된 블록 ID 매핑

연산

블록 할당

새 요청 — 스케줄러가 새 요청에 KV 캐시 블록을 할당하는 흐름:

1. 스케줄러는 kv_cache_manager.get_computed_blocks()를 호출해 이미 계산된 블록 시퀀스를 얻어요. 요청의 프롬프트 토큰을 해싱해서 캐시 블록을 조회하는 방식이에요.
2. 스케줄러는 kv_cache_manager.allocate_slots()를 호출하는데, 내부적으로:
   1. 새로 필요한 블록 수를 계산하고, 충분한 블록이 없으면 반환
   2. 계산된 블록을 "터치(touch)" — 계산된 블록의 참조 횟수를 1 늘리고, 그 블록이 다른 요청에 안 쓰이면 자유 큐에서 제거. 이렇게 하면 계산된 블록이 축출되지 않아요.
   3. 자유 큐 헤드에서 새 블록을 pop해 할당. 헤드가 캐시된 블록이면, 그 블록을 "축출"해서 다른 요청이 더 이상 재사용하지 못하게 해요.
   4. 할당된 블록이 이미 토큰으로 가득 차 있으면 즉시 캐시 블록에 추가해 같은 배치 안의 다른 요청도 재사용할 수 있게 해요.

실행 중 요청 — 스케줄러가 실행 중 요청에 블록을 할당하는 흐름:

1. kv_cache_manager.allocate_slots() 호출:
   1. 새로 필요한 블록 수 계산, 부족하면 반환
   2. 자유 큐 헤드에서 새 블록 pop. 헤드가 캐시된 블록이면 축출해 다른 요청이 못 쓰게 함
   3. 기존 블록과 새 블록의 슬롯에 토큰 ID 추가. 블록이 가득 차면 캐시 블록에 추가해 캐시

중복 블록 — 블록 크기가 4이고 프롬프트 ABCDEF + 디코딩 길이 3인 요청(Request 1)을 보낸다고 해볼게요.

Prompt: [A, B, C, D, E, F]
Output: [G, H, I]

Time 0:
  Tokens: [A, B, C, D, E, F, G]
  Block Table: [0 (ABCD), 1 (EFG)]
  Cache Blocks: 0
Time 1:
  Tokens: [A, B, C, D, E, F, G, H]
  Block Table: [0 (ABCD), 1 (EFGH)]
  Cache Blocks: 0, 1
Time 2:
  Tokens: [A, B, C, D, E, F, G, H, I]
  Block Table: [0 (ABCD), 1 (EFGH), 2 (I)]
  Cache Blocks: 0, 1

이제 블록 0과 1이 캐시됐어요. 같은 요청을 greedy 샘플링으로 다시 보내면(Request 2) Request 1과 정확히 같은 출력을 낼 거예요.

Prompt: [A, B, C, D, E, F]
Output: [G, H, I]

Time 0:
  Tokens: [A, B, C, D, E, F, G]
  Block Table: [0 (ABCD), 3 (EFG)]
  Cache Blocks: 0, 1
Time 1:
  Tokens: [A, B, C, D, E, F, G, H]
  Block Table: [0 (ABCD), 3 (EFGH)]
  Cache Blocks: 0, 1, 3

보시다시피 블록 3은 새로 가득 찬 블록이라 캐시되는데, 사실 블록 1과 똑같아요. 즉 같은 블록을 두 번 캐시한 셈이죠. V0에서는 블록 3이 중복임을 감지하면 블록 3을 풀고 Request 2가 블록 1을 쓰게 해서 블록 테이블이 Time 1에서 [0, 1]이 됐어요. 그런데 V1의 블록 테이블은 append-only라서 블록 테이블을 [0, 3]에서 [0, 1]로 바꿀 수 없어요. 그래서 해시 키 E-H에 대해 중복 블록이 남게 되는데, 이 중복은 요청이 해제될 때 정리돼요.

해제 (Free)

요청이 끝나면, 그 블록을 아무도 안 쓰고 있다면(참조 횟수 0) 모든 블록을 해제해요. 예를 들어 요청 1과 그에 연결된 블록 2, 3, 4, 8을 해제하면 해제된 블록이 자유 큐 꼬리에 역순으로 추가돼요. 이유는 요청의 마지막 블록일수록 더 많은 토큰을 해싱해서 다른 요청이 재사용할 가능성이 낮기 때문에, 먼저 축출되어야 하기 때문이에요.

축출 (LRU)

자유 큐의 헤드 블록(가장 오래 사용되지 않은, least-recently-used 블록)이 캐시된 상태라면, 그 블록이 다른 요청에 쓰이지 않도록 축출해야 해요. 구체적으로:

1. 자유 큐 헤드에서 블록을 pop (축출할 LRU 블록)
2. 캐시 블록에서 블록 ID 제거
3. 블록 해시 제거

예시

블록 크기가 4(블록당 4토큰 캐시)이고 KV 캐시 매니저에 총 10개 블록이 있다고 가정할게요.

Time 1: 캐시가 비어 있고 새 요청이 들어옴. 4개 블록을 할당해요. 그중 3개는 이미 가득 차서 캐시됐고, 네 번째 블록은 4개 중 3개만 차 있는 부분 블록이에요.

Time 2: Request 0이 블록 3을 가득 채우고 디코딩을 계속하려고 새 블록을 요청. 블록 3을 캐시하고 블록 4를 할당해요.

Time 3: Request 1이 14개 프롬프트 토큰으로 들어오는데, 처음 10개 토큰은 Request 0과 같음. 캐시에 적중하는 건 처음 2개 블록(8토큰)뿐이에요. 왜냐하면 세 번째 블록은 4개 중 2개만 일치하기 때문이에요.

Time 4: Request 0이 끝나고 해제됨. 블록 2, 3, 4가 역순으로 자유 큐에 추가돼요(블록 2, 3은 여전히 캐시돼 있어요). 블록 0, 1은 Request 1이 쓰고 있어서 자유 큐에 추가되지 않아요.

Time 5: Request 1이 끝나고 해제됨.

Time 6: Request 2가 29개 프롬프트 토큰으로 들어오는데, 처음 12개는 Request 0과 같음. 자유 큐 순서가 7 - 8 - 9 - 4 - 3 - 2 - 6 - 5 - 1 - 0이었더라도, 캐시 적중 블록(0, 1, 2)은 할당 전에 터치되어 큐에서 제거돼요. 그래서 자유 큐는 7 - 8 - 9 - 4 - 3 - 6 - 5가 되고, 할당된 블록은 0(캐시), 1(캐시), 2(캐시), 7, 8, 9, 4, 3(축출)이 돼요.

이렇게 프리픽스 캐싱은 블록 해시와 자유 큐를 조합해, 공통된 프롬프트 앞부분을 반복 사용하는 워크로드에서 계산을 크게 줄이는 구조예요.

더 알아보기 (Learn more)

• vLLM 공식 문서: Prefix Caching
• 기능 사용 가이드: 자동 접두사 캐싱 (Automatic Prefix Caching)