DualMap: 분산 LLM 서빙에서 캐시 어피니티와 부하 분산을 동시에 해결하는 이중 해시링 라우팅 (ICLR 2026)

요약

분산 LLM 서빙 클러스터에서 요청 라우터는 두 가지 상충하는 목표를 동시에 달성해야 한다.

• 캐시 어피니티(cache affinity): 같은 프롬프트 프리픽스를 가진 요청을 동일 인스턴스로 보내 KV 캐시를 재사용한다. 재사용이 일어나면 수십만 토큰 어텐션 계산을 메모리 읽기로 대체해 TTFT와 GPU 사용률을 동시에 줄인다.
• 부하 분산(load balancing): 요청을 인스턴스에 고르게 분배해 핫스팟을 방지한다.

기존 스케줄러들은 단일 해시 공간 안에서 두 목표를 동시에 최적화하는 방법이 없었다. 인기 프리픽스 요청을 항상 동일 인스턴스로 모으면 핫스팟이 생기고, 라운드로빈으로 고르게 뿌리면 KV 재사용이 사라진다.

2026년 5월 ICLR 2026에서 발표된 DualMap (arXiv:2602.06502)은 고전 부하 분산 이론인 "power of two choices"를 KV 캐시 어피니티 라우팅에 적용해 두 목표를 함께 달성한다. vLLM 엔진 통합 실험에서 기존 최신 방법 대비 유효 요청 처리 용량 2.25배 향상이 확인되었다.

문제: 캐시 어피니티와 부하 분산은 왜 충돌하는가

KV 캐시 재사용의 전제 조건

SGLang RadixAttention, vLLM 자동 prefix caching처럼 서빙 시스템이 KV 캐시를 저장해 두더라도, 같은 프리픽스를 가진 두 요청이 서로 다른 인스턴스에 도달하면 캐시 히트가 일어나지 않는다. 인스턴스 A에 캐시된 KV를 인스턴스 B가 직접 참조하지는 못하기 때문이다(분리 서빙 KV 공유 시스템을 별도로 구성하지 않는 한).

따라서 캐시 어피니티는 같은 프리픽스 → 같은 인스턴스 라우팅을 의미한다.

단일 해시 어피니티의 부작용

단순한 방법은 프롬프트(또는 프리픽스 해시)를 해시해 인스턴스 번호를 결정하는 것이다. 이 방법은 캐시 어피니티를 잘 달성하지만, 인기 프리픽스(예: 수천 개 요청이 공유하는 긴 시스템 프롬프트)가 항상 같은 인스턴스로 집중되어 핫스팟이 된다. 부하 불균형은 SLO 위반, GPU 낭비, 전체 클러스터 처리량 저하로 이어진다.

기존 절충안의 한계

• 인기 프리픽스만 어피니티, 나머지는 라운드로빈: 인기도 임계값 설정이 어렵고, 인기 프리픽스의 정의가 워크로드에 따라 달라진다.
• 어피니티 + 부하 기반 에스컬레이션: 임계 부하를 넘으면 다른 인스턴스로 넘기지만, 넘기는 순간 KV 재사용이 끊긴다.

두 접근 모두 단일 해시 공간 내에서 두 목표를 균형 있게 조율하는 통합 메커니즘이 없다.

DualMap 핵심 설계: Power of Two Choices 적용

원리

"Power of two choices"는 1990년대 분산 시스템 이론의 고전 결과다. N개의 버킷에 공을 무작위로 던질 때, 두 버킷을 랜덤으로 고르고 더 비어 있는 쪽에 넣으면 최악 부하가 O(log N)에서 O(log log N)으로 급감한다. 선택지를 두 개로 늘리는 것만으로 부하 분산이 지수적으로 개선된다.

DualMap은 이 원리를 KV 캐시 어피니티에 맞게 재해석한다.

이중 해시 매핑

두 개의 독립 해시 함수 H1, H2를 사용한다.

• H1(프롬프트 프리픽스) → 후보 인스턴스 A
• H2(프롬프트 프리픽스) → 후보 인스턴스 B

같은 프리픽스를 가진 두 요청은 H1, H2 모두 동일하므로 같은 후보 쌍 (A, B) 중 하나로 라우팅된다. 이로 인해 캐시 어피니티는 두 인스턴스 사이에 집중된다.

서로 다른 프리픽스는 두 독립 해시로 서로 다른 인스턴스 쌍에 분산되어 클러스터 전체에 부하가 골고루 퍼진다.

후보 선택

요청이 도착하면 A와 B의 현재 상태를 비교해 더 유리한 쪽을 선택한다. 비교 기준:

1. KV 캐시 히트율 (높을수록 유리)
2. 현재 큐 길이 (짧을수록 유리)
3. 예상 TTFT (SLO와 비교)

세 가지 보조 기법

1. SLO 인식 라우팅

기본 정책은 KV 히트율이 높은 후보를 선택하는 캐시 어피니티 우선이다. 단, 선택된 후보의 예상 TTFT가 SLO를 초과할 것으로 예측되면 더 여유 있는 쪽으로 전환한다. 캐시 히트를 일부 포기하더라도 지연 SLO를 지키는 것을 우선한다.

이 스위칭은 양방향이다. 부하가 줄면 다시 캐시 어피니티 우선으로 복귀한다.

2. 핫스팟 인식 리밸런싱

실시간으로 인스턴스별 부하를 모니터링한다. 특정 인스턴스의 부하가 임계값을 초과하면 해당 인스턴스로 예정된 요청의 일부를 덜 바쁜 인스턴스로 이관한다. 어피니티를 일부 포기하지만 전체 클러스터 SLO를 방어한다. 임계값은 평균 부하의 배수로 설정한다.

3. 이중 해시링 스케일링

인스턴스를 추가하거나 제거할 때, 단일 해시링 방식은 많은 슬롯을 재매핑해야 한다. DualMap은 H1과 H2 각각 독립 해시링을 유지한다.

인스턴스 추가 시 두 링을 독립적으로, 최소한의 슬롯만 재할당한다. 전역 재매핑 없이 빠른 스케일링이 가능하며, 진행 중인 요청의 KV 캐시 무효화가 최소화된다. 기존 consistent hashing보다 스케일링 중 어피니티 손실이 적다.

성능 결과

vLLM 엔진 통합 실험과 실제 프로덕션 워크로드 패턴(ShareGPT 등) 기반 시뮬레이션 결과:

워크로드 특성 주의: 프리픽스 공유율이 높을수록(공통 시스템 프롬프트, RAG 문서 공유) 효과가 극대화된다. 완전히 균등한 랜덤 프롬프트 패턴에서는 단순 라운드로빈과 차이가 크지 않다.

운영 체크리스트

• [ ] 현재 라우터 타입 확인: 라운드로빈인지, 단순 어피니티 해시인지 파악 후 업그레이드 계획 수립
• [ ] 프리픽스 공유율 측정: KV 캐시 히트율 by prefix length 메트릭으로 어피니티 개선 여지 파악
• [ ] 인스턴스 수가 3개 이상인지 확인 — 2개 이하에서는 dual mapping의 효과가 미미
• [ ] SLO 값을 요청 유형별(대화형 vs 배치 vs RAG)로 분리 설정 — SLO-aware 전환 임계값에 직접 영향
• [ ] 핫스팟 임계값 설정: 인스턴스 평균 부하의 몇 배를 핫스팟으로 볼지 결정 (초기 기본값은 1.5배 권장)
• [ ] 스케일아웃 절차 문서화: 두 해시링 독립 업데이트 순서와 드레인 정책 명시
• [ ] 기존 방식과 A/B 비교 실험: KV 캐시 히트율, 인스턴스별 부하 편차, SLO 달성률 3가지 기준으로 비교

요점 정리

• 분산 LLM 서빙에서 캐시 어피니티와 부하 분산은 단일 해시 공간에서 동시에 최적화할 수 없다.
• DualMap은 각 요청을 두 독립 해시 함수로 두 후보 인스턴스에 매핑하고 현재 KV 상태와 부하를 보고 더 나은 쪽을 선택한다(power of two choices 적용).
• SLO-aware 라우팅, 핫스팟 리밸런싱, 이중 해시링 스케일링 세 가지 기법이 동적 워크로드에서도 두 목표를 함께 유지한다.
• vLLM 통합 실험에서 기존 SOTA 대비 유효 처리 용량 2.25배 향상. ICLR 2026 채택 논문(arXiv:2602.06502).

References

• DualMap 논문 (arXiv:2602.06502, ICLR 2026): https://arxiv.org/abs/2602.06502
• DualMap OpenReview 페이지: https://openreview.net/forum?id=zCadrJ32Xn
• vLLM 자동 prefix caching 문서: https://docs.vllm.ai/en/stable/design/prefix_caching/
• SGLang RadixAttention 설계: https://lmsys.org/blog/2024-01-17-sglang/
• The Power of Two Choices (Mitzenmacher 1996 원논문 요약): https://www.eecs.harvard.edu/~michaelm/postscripts/tpds2001.pdf