vLLM과 SGLang의 Prefix Caching 구현은 무엇이 다른가: Hash vs Radix Tree의 트레이드오프

Prefix Caching의 히트율이 이론보다 낮게 나오는 이유를 운영 관점에서 설명하는 글은 많다. 제거 정책, 요청 분포, 버킷 충돌 같은 원인들이다. 그런데 히트율의 천장 자체를 결정하는 건 더 아래 층위에 있다 — 캐시 키를 어떻게 만들고, 자료구조가 부분 매칭을 허용하는가 아닌가가 같은 워크로드에서도 다른 히트율로 이어진다. vLLM과 SGLang이 선택한 구현이 다르고, 그 차이가 실제 서빙에서 드러나는 조건도 다르다.

캐시 키는 어떻게 만들어지는가

vLLM의 Automatic Prefix Caching(APC)은 토큰 시퀀스를 블록 단위로 잘라 각 블록에 해시를 계산한다. 기본 블록 크기는 16토큰이다. 해시는 체인 방식으로 계산한다 — 현재 블록의 해시 입력에 이전 블록의 해시값이 포함되기 때문에, 블록 위치가 달라지면 같은 토큰이라도 다른 해시가 나온다.

# vllm/v1/core/kv_cache_utils.py
def hash_block_tokens(
    hash_function: Callable[[Any], bytes],
    parent_block_hash: BlockHash | None,
    curr_block_token_ids: Sequence[int],
    extra_keys: tuple[Any, ...] | None = None,
) -> BlockHash:
    if not parent_block_hash:
        parent_block_hash = NONE_HASH
    curr_block_token_ids_tuple = tuple(curr_block_token_ids)
    return BlockHash(
        hash_function((parent_block_hash, curr_block_token_ids_tuple, extra_keys))
    )

extra_keys에는 LoRA ID, 멀티모달 입력 해시, cache_salt(멀티테넌시 격리용)가 들어간다. v0.11부터 기본 해시 함수는 SHA-256이며, 계산 비용은 약 100~200 ns/토큰 수준이다. 50k 토큰 기준 약 6 ms를 소모한다.

여기서 생기는 근본적인 제약이 있다. vLLM은 블록이 완전히 채워진 경우에만 캐시에 올린다. 부분 블록(partial block)은 캐시 대상이 아니다.

부분 매칭이 불가능한 이유

블록 크기 16토큰, 시스템 프롬프트가 17토큰인 경우를 생각해보자. 첫 번째 블록(토큰 1~16)은 캐시에 올라간다. 두 번째 블록에는 토큰 17 하나만 채워져 있다. 이 블록은 완전하지 않아 캐시에 올라가지 않는다. 다음 요청이 같은 시스템 프롬프트를 공유하더라도 첫 블록 16토큰만 재사용되고, 17번째 토큰은 매번 재계산한다.

접두사 길이가 블록 크기의 배수와 맞지 않을 때 손실되는 토큰 수는 prefix_len % block_size다. 49토큰이면 48토큰이 캐시되고 1토큰이 버려진다. 33토큰이면 32토큰이 캐시되고 1토큰이 버려진다. 이 숫자는 작아 보이지만, 많은 요청이 동일한 공유 구간 끝부분을 매번 재계산한다는 뜻이다.

문제가 실질적으로 커지는 건 다양한 길이의 few-shot 예시가 섞이는 워크로드다. few-shot 한 벌이 37토큰이면, 공유 접두사가 블록 경계와 어긋난 상태에서 해시 매칭은 매번 경계를 놓친다. 이론적으로는 37토큰을 공유할 수 있는데 실제로는 32토큰(2블록×16)만 매칭된다. 히트율이 이론보다 낮게 나오는 구조적 원인 중 하나가 바로 이것이다.

Radix Tree가 무엇을 다르게 푸는가

SGLang의 Radix Attention은 KV 캐시를 Radix Tree(압축 트리)에 저장한다. 트리의 각 노드는 토큰 시퀀스의 공통 접두사를 엣지로 표현한다. 새 요청이 들어오면 match_prefix가 루트에서 시작해 토큰을 하나씩 비교하며 내려가다가 불일치 지점에서 멈춘다. 공통 구간까지의 KV 캐시를 재사용하고, 나머지 토큰만 새로 계산한다.

부분 불일치가 생기면 _split_node가 실행된다. 기존 노드와 새 요청이 중간에서 갈라지는 경우, 공통 구간을 새 중간 노드로 만들고 나머지를 각각 자식 노드로 붙인다.

# sglang/python/sglang/srt/mem_cache/radix_cache.py
def _split_node(self, key, child, split_len):
    new_node = TreeNode(priority=child.priority)
    new_node.key = child.key[:split_len]
    new_node.value = child.value[:split_len].clone()
    child.key = child.key[split_len:]
    child.value = child.value[split_len:].clone()
    # new_node가 child의 부모로 삽입됨

위 49토큰 예시에서 Radix Tree는 49토큰을 그대로 트리 경로에 저장하고, 다음 요청에서 49토큰 전부를 매칭한다. 블록 경계가 공유 구간을 자르지 않는다.

조회 복잡도는 공유 접두사 길이를 L, 페이지 크기를 p라 할 때 O(L/p)다. 불일치 지점을 찾을 때 내부적으로 지수 탐색 후 이진 탐색을 적용해 비교 횟수를 줄인다. 삽입도 O(L/p), 삭제(LRU eviction)는 리프에서 올라오며 부모를 정리하기 때문에 O(depth)다.

다중 템플릿이 섞인 워크로드에서 Radix Tree의 강점이 두드러진다. 시스템 프롬프트 A-B-C를 공유하는 요청 집합과 A-B-D를 공유하는 요청 집합이 있을 때, 트리는 A-B 구간 하나를 공유 노드로 두고 C, D를 각각 자식 분기로 관리한다. 해시 맵은 이 공유 구조를 표현하지 못한다.

vLLM의 진화: 무엇이 바뀌고 무엇이 남았는가

vLLM v1 아키텍처에서도 기본 캐시 단위는 블록이다. KVCacheBlock은 block_id, ref_cnt, _block_hash로 구성되고, 블록 풀을 시작 시 사전 할당해 런타임 Python 객체 생성을 제거했다. free block queue는 이중 연결 리스트로 O(1) 조작이 가능하다.

# vllm/v1/core/kv_cache_utils.py
@dataclass(slots=True)
class KVCacheBlock:
    block_id: int
    ref_cnt: int = 0
    _block_hash: BlockHashWithGroupId | None = None
    _block_hash_num_tokens: int | None = None
    prev_free_block: "KVCacheBlock | None" = None
    next_free_block: "KVCacheBlock | None" = None

블록 단위 체인 해시 구조는 v1에서도 유지된다. 블록이 완전히 채워져야만 캐시에 올라가는 제약도 그대로다. 접두사 길이가 블록 경계와 맞지 않는 워크로드에서의 구조적 히트율 손실은 여전히 존재한다.

enable-prefix-caching 플래그 하나로 APC를 켤 수 있어 운영 편의성은 높다.

vllm serve <model> --enable-prefix-caching

활성화 후 vLLM이 노출하는 Prometheus 지표에서 gpu_cache_usage_perc와 prefix cache hit rate 관련 메트릭으로 실제 캐시 효율을 모니터링할 수 있다. SGLang은 sglang:cache_hit_rate를 직접 노출한다.

워크로드별 비교

SGLang 논문(arXiv:2312.07104)에서 Radix Attention은 시스템 프롬프트 공유 비율이 높은 합성 워크로드 기준으로 최대 6.4x 처리량 향상, 3.7x 레이턴시 감소를 보고했다. 공유 비율이 낮아질수록 격차는 좁아진다.

시스템 프롬프트가 블록 크기의 배수로 맞아떨어지는 경우라면 Hash 기반도 Radix와 동일한 히트율을 낼 수 있다. vLLM APC를 쓰면서 히트율을 올리고 싶다면, 시스템 프롬프트 길이를 16의 배수(또는 설정한 블록 크기의 배수)로 맞추는 것만으로도 의미 있는 차이가 생긴다. 자료구조를 바꾸기 전에 이 정렬부터 확인하는 게 맞다.

Radix Tree의 비용

트리 구조는 관리 복잡도가 높다. LRU 제거 시 리프 노드부터 올라오면서 단일 자식만 남은 부모 노드를 병합해야 하고, 동시 요청이 많은 환경에서 트리 삽입·분기·제거에 글로벌 락이 걸리면 이 비용이 레이턴시 꼬리에 나타난다. SGLang은 lock_ref > 0인 노드를 eviction에서 제외해 현재 요청이 사용 중인 KV 캐시를 보호하지만, 제거 가능한 노드가 줄어드는 부작용이 있다.

메모리 측면에서는, 요청 다양성이 높은 워크로드에서 트리 노드 수가 수천 개로 불어날 수 있다. 노드 하나가 토큰 키 텐서, KV 인덱스 텐서, 메타데이터(접근 시각, hit_count, lock_ref 등)를 보유하기 때문에 CPU 메모리 오버헤드가 누적된다. 요청 1만 건을 처리했을 때 노드당 메타데이터만 수십 바이트라고 해도 전체로는 수 MB 단위가 된다.

요청 다양성이 낮고 시스템 프롬프트가 하나로 고정된 배포 환경에서는 Hash 기반이 오버헤드 없이 동일한 히트율을 낸다. 반면 접두사 공유 패턴이 복잡하고, 시스템 프롬프트 템플릿이 여러 종류이고, 멀티턴 대화가 많은 워크로드에서는 임의 길이 부분 매칭이 가능한 Radix Tree가 히트율 상한 자체를 끌어올린다.