멀티 인스턴스 LLM 서빙 환경에서 라우팅은 더 이상 "어느 서버로 보낼까"의 문제가 아니다. 어느 인스턴스로 요청을 보내느냐가 TTFT와 캐시 히트율을 동시에 결정한다. 문제는 이 두 목표가 근본적으로 긴장 관계에 있다는 것이다—부하를 균등하게 분산하는 라우터와 KV 캐시를 최대한 재사용하는 라우터는 같은 결정을 내리지 않는다. 요청을 보내는 시점에 출력 길이를 알 수 없기 때문에, 한 라우터가 두 목표를 동시에 최적화하는 것은 불가능하다.
이 글은 그 긴장을 어떤 전략으로, 어떤 조건에서 다루는지 구체적으로 살핀다.
왜 LLM 라우팅은 HTTP 로드밸런서와 다른가
일반적인 L4/L7 로드밸런서는 요청을 stateless하게 분산한다. 각 요청의 처리 비용이 대체로 균일하고, 어느 서버가 처리하든 결과가 같다고 가정한다. LLM 요청은 이 가정이 세 군데에서 깨진다.
첫째로 prefill과 decode의 비용이 비대칭이다. prefill은 입력 토큰 전체를 한 번에 계산하는 compute-bound 단계고, decode는 토큰을 하나씩 생성하는 memory-bandwidth-bound 단계다. 입력이 8,000 토큰인 요청과 100 토큰인 요청의 처리 비용 차이는 수십 배에 달한다. 라우터가 이를 모르면 긴 prefill 요청이 한 인스턴스에 몰리는 순간 큐가 폭발한다.
둘째로 출력 길이를 사전에 모른다. HTTP 응답 크기는 서버가 미리 알지만, LLM은 EOS 토큰이 나오기 전까지 길이가 확정되지 않는다. Least-Connections 기반 로드밸런서가 "요청 수가 적은 인스턴스"로 보내도, 그 인스턴스가 출력 2,000 토큰짜리 요청을 10개 처리 중이라면 실제 부하는 다르다.
셋째로 KV 캐시 상태가 인스턴스마다 다르다. LLM 엔진은 앞서 처리한 요청의 attention KV 쌍을 캐시에 보관한다. 동일한 prefix로 시작하는 다음 요청이 같은 인스턴스에 들어오면 prefill 연산을 건너뛸 수 있다. Moreh의 실측에서 Qwen3-32B 모델(8,000 토큰 시스템 프롬프트 + 1,000 토큰 사용자 입력)을 8개 AMD MI250 파드에서 돌렸을 때, 랜덤 라우팅의 P50 TTFT는 4,464ms였고 prefix-aware 라우팅으로 전환하자 217ms로 줄었다. 20배 차이다.
이 셋이 합쳐지면 stateless 로드밸런서가 내린 "균등한" 결정이 실제로는 최악의 결정이 된다.
라우팅 전략 4종 해부
Round-Robin / Random
가장 단순하다. 인스턴스 상태를 전혀 참조하지 않고 순환 또는 랜덤으로 분산한다. 구현 비용이 없고 핫스팟도 없다.
문제는 캐시다. 동일한 시스템 프롬프트로 들어오는 요청들이 8개 인스턴스에 고르게 퍼지면, 각 인스턴스는 동일한 prefix를 반복 계산한다. Ranvier의 실측에서 8-GPU 구성의 Round-Robin 캐시 히트율은 12.5%였다—8분의 1의 확률로 우연히 같은 인스턴스에 도달하는 수준이다. 같은 워크로드에서 prefix-aware 라우팅의 히트율은 97.5%였다.
처리량도 벌어진다. 동일한 8-GPU 구성에서 Round-Robin은 36.3 req/s, prefix-aware는 44.4 req/s였다(22.3% 차이). P99 TTFT는 6,800ms vs 1,000ms다.
prefix 재사용이 없는 다양한 one-off 요청 트래픽이라면 Round-Robin은 합리적이다. 시스템 프롬프트가 고정된 API 서빙, 챗봇, 코드 에이전트처럼 공유 prefix가 있는 워크로드에서는 쓰지 않는 게 낫다.
Least-Outstanding-Requests (LOR)
현재 처리 중인 요청 수가 가장 적은 인스턴스로 보낸다. Round-Robin보다 부하 균형은 낫지만, 캐시 상태를 모른다는 점은 같다. 출력 길이 불확실성 때문에 "요청 수가 적다"가 "부하가 적다"를 보장하지 않는다. Least-Connections류 전략이 LLM 서빙에서 쓸 만한 시나리오는 한정적이다—prefix 재사용이 거의 없고 요청 길이 편차가 낮은 경우.
Prefix-Hash 라우팅 (세션 고정)
요청의 prefix(또는 세션 ID)를 해싱해서 항상 같은 인스턴스로 보낸다. 캐시 히트율은 극대화된다. 문제는 핫스팟이다.
특정 시스템 프롬프트로 수렴하는 트래픽이 있을 때, 그 prefix의 해시값을 받는 인스턴스 하나가 전체 트래픽 중 불균형한 비율을 처리하게 된다. 나머지 인스턴스는 유휴 상태다. 인스턴스 수가 늘어날수록 이 불균형은 심화된다—인스턴스가 4대일 때는 핫 인스턴스가 25% 이상의 트래픽을 받지만, 16대로 늘어나면 나머지 15대가 절반 이상 논다.
구체적으로 보면, DualMap 논문의 분석에서 순수 prefix-affinity 라우팅은 tail latency가 급격히 상승한다—핫 인스턴스의 큐가 차면서 p99가 폭발한다. 고부하 QPS에서 prefix-only 라우팅은 약 55%의 요청만 정상 처리했고, load-awareness를 결합하면 100%로 회복됐다.
핫스팟을 완화하는 방법이 없는 건 아니다. partial replication—인기 prefix의 KV 캐시를 여러 인스턴스에 복제—은 히트율을 유지하면서 트래픽을 나눌 수 있다. 단, 복제 비용과 메모리 낭비가 생긴다. adaptive prefix hash—prefix가 핫해지면 해시 key를 더 세분화해 여러 인스턴스로 분산—도 같은 방향의 해결책이다. Ray Serve의 prefix-aware 라우팅이 이 접근을 쓴다: 큐 길이 차이가 임계값(imbalanced_threshold)을 넘으면 캐시 우선에서 부하 균형으로 자동 전환한다.
KV-Aware 라우팅
각 인스턴스의 KV 캐시 상태와 현재 부하를 실시간으로 수집해 라우팅 결정을 내린다. 이론적으로는 두 목표를 절충하는 최선의 전략이다.
vLLM Router는 Consistent Hashing으로 이 방향을 구현한다—세션 ID나 routing key 기반으로 cache-sticky하게 보내되, 인스턴스 부하 정보를 함께 참조한다. SGLang의 cache_aware 정책은 radix tree로 prefix 매칭을 계산하고 load balancing(shortest queue)으로 fallback한다.
# dstack gateway 설정 예시 (SGLang)
router:
type: sglang
policy: cache_aware # random | round_robin | cache_aware | power_of_two
# vLLM Router 정책 예시
# Consistent Hashing: routing_key(session_id, user_id) → sticky worker
# Power of Two (PoT): 두 인스턴스를 랜덤 샘플링 → 가벼운 쪽 선택
# Round Robin / Random: stateless fallback
그러나 KV-Aware 라우팅의 실제 비용은 인스턴스 상태를 얼마나 자주, 얼마나 정확하게 수집하느냐에 달려 있다.
KV-Aware 라우팅의 실제 구현 비용: Staleness 문제
라우터가 각 인스턴스의 KV 캐시 점유율, 큐 길이, 현재 처리 중인 요청 수를 알려면 폴링이 필요하다. SGLang router는 기본적으로 health check를 30초 간격으로 실행하고, 실제 부하 메타데이터는 더 짧은 주기로 갱신된다. 문제는 이 간격 사이에 캐시 상태가 바뀐다는 것이다.
폴링 주기가 길수록 라우터의 결정은 현실과 멀어진다. 라우터가 "인스턴스 A에 이 prefix의 KV 캐시가 있다"고 판단했을 때, 그 캐시가 이미 evict됐거나 다른 요청으로 덮였다면 라우팅 결정은 틀렸다. 고부하 상황에서는 캐시 eviction 속도가 빨라지기 때문에 staleness의 영향이 커진다.
이 문제를 vLLM Router와 SGLang은 다르게 접근한다. vLLM Router는 prefix/decode 분리(P/D disaggregation) 아키텍처를 명시적으로 지원하면서, ZMQ 기반 discovery와 NIXL/NCCL 백엔드로 인스턴스 상태를 더 빠르게 동기화한다. vLLM의 P/D disaggregation 기반 라우터는 Llama 3.1 8B 8+8 파드 구성에서 K8s native 대비 100% 높은 throughput과 1,200ms 낮은 TTFT를 기록했다.
SGLang은 cache_aware 정책이 staleness를 감지하면 자동으로 shortest-queue fallback으로 전환하는 방식을 쓴다. 완벽하진 않지만 stale 정보로 계속 잘못된 결정을 내리는 것보다 낫다.
staleness가 임계 수준을 넘으면 KV-Aware 라우터는 Round-Robin보다 나쁠 수 있다. Round-Robin은 적어도 결정이 틀릴 이유가 없다—정보가 없는 게 잘못된 정보보다 나은 경우다.
요청 분포가 전략을 뒤집는 지점
공유 prefix 비율이 낮은 트래픽(0~20%)에서는 어떤 라우팅 전략도 캐시 히트율에서 차이를 만들지 못한다. Round-Robin이나 LOR이 충분하다.
prefix 공유 비율이 50% 이상이 되면 전략별 결과가 뚜렷하게 갈린다. Ranvier 실측 기준으로 50% 토큰 공유 환경에서 prefix-aware 라우팅의 히트율은 91%였고, Round-Robin은 ~11%에 머물렀다. TTFT 차이는 캐시 히트(18ms)와 캐시 미스(500ms) 간 28배 gap으로 직결된다.
90% 공유 비율에서는 prefix-aware의 히트율이 97~98%까지 올라간다. 동시에 핫스팟 문제도 심해진다—거의 모든 요청이 소수의 prefix 해시값으로 수렴하기 때문에 특정 인스턴스가 포화된다.
인스턴스 수가 늘어날수록 Prefix-Hash의 핫스팟은 심화되지만, 동시에 KV-Aware의 staleness 비용도 늘어난다—수집해야 할 인스턴스 메타데이터가 많아지고 폴링 오버헤드가 증가한다. 인스턴스 수가 적을 때(2~4대)는 Prefix-Hash가 단순하고 효과적이다. 16대 이상으로 규모가 커지면 load-aware fallback 없는 순수 prefix-hash는 위험하다.
아래 표는 인스턴스 4대 구성에서 세 시나리오별 전략별 특성을 정리한 것이다.
| 시나리오 | Round-Robin | Prefix-Hash | KV-Aware |
|---|---|---|---|
| prefix 공유 0% (다양한 쿼리) | 캐시 히트 ~12%, 부하 균등 | 캐시 히트 ~12%, 부하 균등 | 캐시 히트 ~12%, 폴링 오버헤드 발생 |
| prefix 공유 50% | 캐시 히트 ~11%, TTFT 불리 | 캐시 히트 ~91%, 핫스팟 리스크 | 캐시 히트 60~80%(staleness 의존), 부하 절충 |
| prefix 공유 90% | 캐시 히트 ~12%, TTFT 최악 | 캐시 히트 ~97%, 핫스팟 심각 | 캐시 히트 75~90%, 부하 절충, staleness 리스크 |
핫스팟: 인기 prefix가 한 인스턴스를 죽이는 구조
chatbot API에서 상위 1개 시스템 프롬프트가 전체 트래픽의 60%를 차지하는 상황을 생각해보자. Prefix-Hash 라우팅에서 이 프롬프트는 단일 인스턴스로 수렴한다. 그 인스턴스는 KV 캐시와 요청 큐가 빠르게 차오르고, GPU 메모리가 한계에 달하면 OOM이 발생하거나 eviction이 폭발적으로 일어나 히트율이 역설적으로 떨어진다. 나머지 인스턴스는 한가하다.
이 구조에서 p99 TTFT 스파이크는 핫 인스턴스 큐 대기 시간에서 온다. 핫스팟 인스턴스가 처리 중인 동안 새 요청이 계속 들어오면 큐잉 지연이 캐시 히트로 얻는 latency 절감을 상쇄한다.
완화 전략으로는 두 가지가 현실적이다. 첫째는 load threshold fallback—Ray Serve가 채택한 방식으로, 인스턴스 간 큐 차이가 임계값을 넘으면 캐시 우선을 포기하고 부하 분산으로 전환한다. 둘째는 partial KV cache replication—인기 prefix의 KV 캐시를 여러 인스턴스에 복제해 트래픽을 나눈다. 메모리 비용이 들지만, 핫스팟 OOM보다 낫다.
언제 어떤 전략을 선택하는가
라우팅 전략 선택에 필요한 변수는 세 가지다: prefix 재사용률, 인스턴스 수, 지연 SLO.
| 조건 | 권장 전략 |
|---|---|
| prefix 재사용률 낮음 (0~20%) + 인스턴스 소수 | Round-Robin 또는 LOR |
| prefix 재사용률 높음 (50%+) + 인스턴스 소수 (2~4대) | Prefix-Hash (threshold fallback 설정 권장) |
| prefix 재사용률 높음 + 인스턴스 다수 (8대+) | KV-Aware (cache_aware + load fallback) |
| 지연 SLO 엄격 + prefix 재사용률 높음 | KV-Aware + 짧은 폴링 주기 + fallback |
| prefix 재사용률 불명확 | LOR로 시작, 히트율 모니터링 후 전환 |
"기본값으로 Round-Robin을 쓰면 안 되는 조건"은 명확하다: 시스템 프롬프트 공유율이 30%를 넘고, TTFT SLO가 있고, 인스턴스가 2대 이상인 환경이다. 이 세 조건이 겹치면 Round-Robin의 캐시 미스 비용이 부하 균형의 이점을 넘어선다.
반대로 KV-Aware를 무조건 선택하는 것도 틀렸다. 폴링 주기가 충분히 짧지 않으면—고부하에서 인스턴스 캐시 상태가 100ms 단위로 바뀌는데 500ms 간격으로 수집하면—라우터가 보유한 정보의 절반 이상이 이미 stale하다. 그 상황에서 KV-Aware는 Round-Robin보다 나쁜 결정을 내릴 수 있다.
세 변수를 먼저 측정하지 않으면 전략 선택은 추측이다. 실제 트래픽에서 prefix 재사용률을 측정하고(vLLM의 cache_hit_rate 메트릭, SGLang의 radix tree hit 통계), 그 숫자를 기준으로 전략을 고르는 순서가 맞다.