인스턴스를 여러 개 띄우면 트래픽 분산은 자연스럽게 해결된다 — 적어도 웹 서버 세계에서는 그렇다. HTTP 요청은 어느 인스턴스로 가든 같은 결과를 낸다. 상태가 없으니 라우터는 부하만 보면 된다.
LLM 서빙에서는 이 전제가 깨진다. 인스턴스마다 KV 캐시가 다르게 쌓여 있다. 동일한 시스템 프롬프트로 들어온 요청이라도, 그 프롬프트의 KV 캐시가 없는 인스턴스에 도착하면 prefill을 처음부터 재실행해야 한다. 2048 토큰짜리 RAG 컨텍스트라면 수백 밀리초가 날아간다. 라우팅 결정이 곧 연산 비용 결정이다.
KV 캐시는 로컬 상태다
웹 애플리케이션의 세션 정보는 Redis 같은 외부 저장소에 두면 어느 인스턴스로 라우팅해도 접근할 수 있다. KV 캐시는 그게 안 된다. GPU HBM에 올라가 있는 tensor 형태이고, 크기가 수 GB에 달한다. 인스턴스 A에서 만들어진 캐시를 인스턴스 B로 옮기려면 GPU 간 고속 네트워크(NVLink, RoCE)를 통한 대용량 전송이 필요하고, 그 자체로 상당한 지연이 발생한다.
결국 각 인스턴스는 자신이 처리한 요청들의 KV 캐시만 보유한다. 특정 prefix의 캐시는 특정 인스턴스에 귀속된다. 라우터가 이 사실을 모르면, 캐시를 보유한 인스턴스 대신 엉뚱한 인스턴스에 요청을 보낸다.
Round-Robin 기준으로 인스턴스가 N개라면, 동일 prefix 요청이 캐시를 가진 인스턴스에 도달할 확률은 1/N이다. 인스턴스를 4개로 늘리면 캐시 히트율이 이론상 25%까지 떨어진다. 서빙 규모를 키울수록 캐시 효과가 사라지는 구조다.
Round-Robin과 LOR가 실제로 얼마나 나쁜가
llm-d 프로젝트가 8 pod(16 H100 GPU) 환경에서 cache-aware routing과 round-robin을 직접 비교한 결과, TTFT가 57배 차이 났다. 같은 하드웨어에서 처리량은 2배. Llama 3.1 70B 기준 4× AMD MI300X 환경에서는 output tokens/sec가 3배, TTFT가 절반 수준으로 내려갔다. DigitalOcean의 측정에서는 cache-aware routing이 random routing 대비 처리량을 108% 높였다.
Least-Outstanding-Requests(LOR)는 round-robin보다 정교하지만 LLM 트래픽에서는 기대만큼 동작하지 않는다. LOR은 현재 처리 중인 요청 수를 기준으로 인스턴스를 고른다. LLM 요청의 길이 편차가 극단적이라는 게 문제다. 짧은 요청 10개를 처리하는 인스턴스와 긴 요청 1개를 처리하는 인스턴스는 대기 수가 같지만 실제 부하는 전혀 다르다. LOR이 부하를 잘못 추정하는 경우가 빈번하고, 캐시 지역성을 전혀 고려하지 않는다는 점에서 round-robin과 근본적으로 같은 문제를 안고 있다.
2000 토큰짜리 시스템 프롬프트가 있고 시간당 1000건 요청이 들어오는 서비스라면, 캐시를 놓칠 때마다 2000 토큰 prefill이 발생한다. TrueFoundry의 분석으로는 이 조건에서 naive 라우팅이 시간당 200만 토큰의 중복 prefill을 발생시킨다.
Prefix-Aware Routing: prefix를 라우팅 키로
해결책은 요청의 prefix를 라우팅 결정에 포함하는 것이다. 동일 prefix를 공유하는 요청을 항상 같은 인스턴스로 보내면, 그 인스턴스의 캐시가 재사용된다.
구현 방식으로 두 가지가 주로 쓰인다.
첫 번째는 prefix hash sticky다. 요청의 공유 prefix를 해싱해 인스턴스에 매핑한다. consistent hashing과 유사하다. 구현이 단순하고 오버헤드가 낮지만, 실제로 그 인스턴스에 캐시가 있는지는 확인하지 않는다. 인스턴스가 재시작되거나 캐시가 eviction되면 hit이 없는 상태에서도 같은 인스턴스로 계속 라우팅한다.
두 번째는 radix tree 기반 cache-aware routing으로, SGLang Router가 채택한 방식이다. 라우터가 각 인스턴스별 prefix tree를 별도로 유지한다. 새 요청이 들어오면 모든 인스턴스의 tree에서 prefix 매칭 길이를 비교한다. 매칭 길이가 임계값을 넘는 인스턴스가 있으면 그쪽으로 보내고, 없으면 부하가 가장 낮은 인스턴스를 선택한다. 시스템 전체가 불균형한 상태라면 가장 작은 tree를 가진 인스턴스(캐시가 가장 적게 쌓인 인스턴스)를 우선해 균형을 잡는다. vLLM production-stack도 유사한 방식의 prefix-aware routing을 공식 지원한다.
2-인스턴스 H100/Llama-3.1-8B 환경에서 session-aware 라우팅은 96.26%의 캐시 히트율을 기록했고, round-robin과 least-loaded는 92.693.0% 수준이었다. 격차가 34%p로 작아 보이지만 이 수치는 인스턴스가 2개인 경우다. 인스턴스가 8개라면 round-robin의 히트율은 이론상 12.5%까지 떨어지는 반면 prefix-aware routing은 거의 100%에 가깝게 유지된다. 플릿 규모가 커질수록 격차는 기하급수적으로 벌어진다.
Sticky Routing이 만드는 핫 prefix 문제
Prefix-aware routing이 잘 동작하는 조건은 prefix 분포가 어느 정도 고르다는 전제다. 실제 프로덕션 트래픽은 그렇지 않다.
가장 흔한 케이스는 동일 시스템 프롬프트를 쓰는 수백 개의 병렬 요청이다. RAG 파이프라인이라면 retrieval된 문서가 prefix에 포함되기도 한다. 전체 요청의 70%가 동일 prefix를 공유하는 상황이라면, sticky routing은 그 70%를 단일 인스턴스로 몰아넣는다. 그 인스턴스의 GPU 메모리와 처리 대기열이 포화되는 동안 나머지 인스턴스는 한가하다. prefix-aware routing이 load balancing 문제를 만들어내는 역설이다.
이 상황을 다루는 현실적인 방법은 hybrid overflow다. 기본적으로 prefix-sticky로 라우팅하되, 대상 인스턴스의 부하가 임계값(대기 요청 수, 메모리 사용률 등)을 넘으면 sticky를 포기하고 다른 인스턴스로 보낸다. overflow된 요청은 캐시 미스가 발생하지만, 인스턴스 포화로 인한 큐잉 지연보다는 prefill 비용이 싼 경우가 많다. 시스템 프롬프트 길이가 짧다면 prefill 비용도 낮아 overflow 허용 임계값을 낮게 잡아도 된다. 반대로 4096 토큰 이상의 긴 컨텍스트라면 overflow 비용이 상당하므로 임계값을 높이거나 핫 prefix를 여러 인스턴스에 미리 워밍업하는 방식을 고려해야 한다.
Llumnix (OSDI '24)는 인스턴스 간 요청 마이그레이션과 KV 캐시 인식 부하 분산을 결합해 이 문제를 다른 방식으로 접근한다. 단순 round-robin 대비 mean TTFT를 최대 6.4배, P99 TTFT를 최대 12.1배 개선했고, KV 캐시 인식 스케줄러를 쓰면 queue-size 기반 단순 부하 분산 대비 mean TTFT가 4.6배 추가로 개선된다.
P/D 분리 환경에서의 추가 복잡성
DistServe처럼 prefill 인스턴스와 decode 인스턴스를 물리적으로 분리한 아키텍처에서는 라우팅이 두 단계로 나뉜다. prefill을 어느 인스턴스에서 실행할지, decode를 어느 인스턴스에서 실행할지를 각각 결정해야 하고, prefill이 끝난 KV 캐시를 decode 인스턴스로 전송하는 비용이 추가된다. DistServe는 decode 인스턴스가 prefill 인스턴스에서 KV 캐시를 pull하는 방식을 채택한다.
이 구조에서는 prefix-sticky routing으로 prefill 인스턴스를 고정해도, decode 인스턴스 선택과 KV 전송 경로를 별도로 제어해야 한다. 단순한 prefix hash sticky routing 하나로 전체를 커버하기 어렵고, 라우팅 로직의 복잡도가 한 층 더 올라간다.
언제 어떤 전략을 쓸 것인가
| 라우팅 전략 | 캐시 히트율 | 부하 균형도 | 구현 복잡도 | 적합한 상황 |
|---|---|---|---|---|
| Round-Robin | 1/N (인스턴스 증가 시 급락) | 높음 | 낮음 | prefix 공유가 거의 없는 트래픽 |
| LOR | 1/N (동일) | 중간 | 낮음 | 요청 길이 편차가 극히 작을 때 |
| Prefix-Hash Sticky | 높음 | 낮음 (핫 prefix 시 심각) | 낮음 | prefix 분포 균일, 인스턴스 수 소규모 |
| Hybrid (임계값 overflow) | 높음 (핫 prefix 시 부분 저하) | 중간 | 중간 | 핫 prefix가 존재하는 실제 트래픽 |
| Radix Tree Cache-Aware | 높음 (지속) | 중간 | 높음 | 대규모 다중 인스턴스, 분포 불균일 |
prefix 공유율이 낮은 트래픽 — 사용자마다 완전히 다른 컨텍스트가 들어오는 서비스 — 이라면 round-robin이나 LOR이 낫다. Sticky routing으로 얻는 캐시 이득이 없으면서 부하 분산 품질만 떨어진다.
prefix 공유율이 30%를 넘고 인스턴스가 4개 이상이라면 cache-aware routing을 적용하는 게 맞다. 비용 차이가 수십 배까지 벌어지는 상황에서 단순성을 이유로 round-robin을 유지하는 건 합리적이지 않다. 핫 prefix가 예상된다면 pure sticky 대신 임계값 기반 hybrid를 선택해야 한다. 임계값 설정이 까다롭지만, 단일 인스턴스 과부하로 전체 처리량이 망가지는 것보다는 훨씬 낫다.
인스턴스를 더 띄울수록 문제가 쉬워지는 게 웹 서버 세계의 상식이다. LLM 서빙에서는 반대다. 인스턴스가 늘어날수록 캐시 분산이 심해지고, 라우터가 캐시 상태를 얼마나 아느냐가 처리량 차이를 결정한다.