요청이 GPU에 올라가는 순서는 TTFT(Time to First Token)에서 끝이 아니다. decode가 시작된 다음에도 스케줄러는 매 iteration마다 이 요청을 이번 배치에 넣을지 다시 결정한다. 그 결정이 TPOT(Time Per Output Token) SLO를 망가뜨리는 경로는 생각보다 직접적이고, 우선순위 정책이 이 경로에 관여하는 방식은 처음 설계할 때보다 훨씬 복잡하다.
TPOT SLO가 위반되는 경로는 생성 중간에 있다
decode 중인 요청이 배치에서 밀려나는 순간, 그 요청의 다음 토큰 생성은 멈춘다. A100에서 Llama-3 8B를 돌릴 때 정상 decode 요청은 iteration당 약 40ms 간격으로 토큰을 생성한다. 이 요청이 preemption을 당하면 다음 토큰 간격이 200ms를 넘기 시작한다. KV cache를 CPU로 swap했다 복구하는 경로를 타면 gap이 더 벌어진다.
TPOT p99가 SLO를 밟는 패턴 대부분은 이 지점에서 발생한다 — 모델 연산이 느린 게 아니라 스케줄러가 어떤 요청을 밀어낸 결과다. 사용자는 스트림이 수백 밀리초 동안 멈추는 걸 느끼고, 그 원인은 decode 단계의 중단이다.
vLLM 스케줄러는 KV block 가용량을 기준으로 preemption 대상을 정하는데, 기본 FCFS 정책에서는 큐의 후미 요청(가장 나중에 도착한 요청)부터 밀어낸다. preemption은 두 가지 비용을 낳는다. 밀려난 요청이 재개될 때까지의 wall-clock gap과, recompute 방식일 때 prefill을 처음부터 다시 돌리는 중복 연산이다.
Iteration-level 스케줄러의 결정 순서
Orca(Yu et al., 2022)가 iteration-level scheduling을 도입하기 전, LLM 서빙 시스템은 요청 단위로 배치를 구성했고 한번 배치가 구성되면 그 요청들이 EOS 토큰을 뱉을 때까지 GPU를 점유했다. Orca는 이 단위를 iteration으로 쪼갰다. 매 forward pass가 끝날 때마다 스케줄러가 다음 배치를 새로 구성한다.
이 구조에서 스케줄러는 매 iteration 시작 시 다음 순서로 결정을 내린다:
1. running 요청들이 다음 iteration에 필요한 KV block 확인
2. 여유 block이 없으면 preemption 대상 선정 (running → waiting으로 강등)
3. waiting 큐에서 추가할 요청 선택 ← 우선순위 정책이 개입하는 자리
4. running + 신규 요청으로 배치 구성 → forward pass 실행
3번 단계가 FCFS·SJF·Priority 세 정책이 갈리는 자리다. 어떤 요청을 waiting 큐에서 꺼낼지, 그리고 2번에서 누구를 밀어낼지가 정책마다 다르게 결정된다.
FCFS는 도착 순서 그대로 큐를 처리한다. 구현이 단순하고 도착 순서 기준의 공정성을 보장하지만, 긴 요청이 앞에 있으면 뒤에 온 짧은 요청이 대기해야 한다 — head-of-line blocking이다. Orca 자체도 FCFS를 기본으로 썼고, vLLM 역시 기본 정책은 FCFS다.
SJF(Shortest Job First)는 예측된 출력 길이가 짧은 요청을 먼저 실행한다. 짧은 요청들을 빠르게 처리해 queue depth를 줄이고 평균 latency를 개선한다는 이론적 이점이 있다.
Priority Scheduling은 요청에 우선순위 레이블을 붙이고 높은 등급부터 처리한다. 유료 티어 구분이나 인터랙티브 vs 배치 트래픽 분리에 자연스럽게 매핑된다.
Priority Scheduling이 starvation을 피할 수 없는 이유
높은 우선순위 요청이 지속적으로 유입되는 상황을 생각해보자. 스케줄러는 매 iteration마다 waiting 큐를 우선순위 내림차순으로 훑어 배치를 채운다. 낮은 우선순위 요청은 이미 running 중이더라도, KV block이 부족해지는 순간 preemption 후보가 된다. 높은 우선순위 신규 요청을 받기 위해 낮은 우선순위의 decode 중 요청이 밀려나는 것이다.
KV block을 점유하고 있던 낮은 우선순위 요청이 preemption되면 두 경로를 탄다. swap(KV block을 CPU로 이동)이면 나중에 재개할 수 있지만 메모리 대역폭 비용이 발생한다. recompute면 prefill을 처음부터 다시 돌린다. 두 경우 모두 그 요청의 TPOT는 이미 spike를 기록한 다음이다.
aging 기법으로 완화를 시도할 수 있다. 대기 시간이 길어질수록 해당 요청의 유효 우선순위를 높여 결국 스케줄러가 처리하게 만드는 방식이다. vLLM SJF RFC에서도 이를 TimeAndLengthScorer로 공식화했다 — 대기 시간 가중치(기본 0.5)와 예측 길이의 역수를 조합한 스코어로 큐를 정렬한다. 공정성 스케줄링 연구에서 aging 정책은 평균 end-to-end latency를 FCFS 대비 10% 이상 감소시킨다.
그러나 aging이 낮은 우선순위 요청의 유효 우선순위를 높이는 동안, 그 요청이 이미 KV block을 점유하고 있으면 aging이 작동하기 전에 eviction이 먼저 일어날 수 있다. KV 캐시 용량 경합이 aging 가중치 계산보다 먼저 결정되기 때문이다. aging은 큐 순서를 조정하지만 KV block 회수 결정은 별도 로직이다. 이 두 결정이 충돌할 때 낮은 우선순위 요청은 aging으로 올라온 큐 순서에도 불구하고 block이 없어서 실행되지 못하는 상황이 생긴다.
λ_high=2 req/s로 높은 우선순위 요청이 지속 유입되는 조건에서 낮은 우선순위 요청은 수십 iteration 후 preemption을 경험하는 패턴을 보인다. 실제 서비스에서는 수초~수십초의 TPOT spike로 나타난다.
SJF는 왜 LLM 서빙에서 이론만큼 동작하지 않는가
SJF의 전제는 작업 길이를 미리 안다는 것이다. LLM 서빙에서는 출력 토큰 수를 prefill 시점에 알 수 없다. max_tokens를 사용자가 지정하지 않으면 모델이 EOS를 뱉을 때까지 알 수 없고, 지정하더라도 실제 생성이 그 앞에서 멈출지는 모른다.
예측 모델로 우회할 수 있다. 입력 길이·컨텍스트 특성으로 출력 길이를 추정해 SJF 큐를 구성한다. 문제는 예측 오차다. 짧다고 판단해서 먼저 배치에 넣은 요청이 예상보다 훨씬 긴 생성을 시작하면, 그 요청이 차지한 배치 슬롯과 KV block이 다른 요청들의 TPOT를 잠식한다. 이 시나리오에서 SJF는 FCFS보다 p99 TPOT가 높게 나온다.
vLLM SJF RFC 실험에서 SJF는 변동 길이 입력 시나리오에서 throughput을 6.2% 개선했다. 이 수치는 평균 성능 기준이고, 예측 오차가 큰 heavy-tail 분포 트래픽에서는 반대 결과가 나온다. SJF가 FCFS보다 p99 TPOT를 오히려 악화시키는 조건은 정확히 요청 길이 편차가 클 때다 — 예측이 틀릴 확률이 가장 높은 그 조건에서다.
동일 트래픽에서 세 정책의 TPOT 분포
동일 Poisson 도착률(λ=4 req/s) 조건에서 요청 길이 분포에 따라 세 정책의 TPOT 분포가 어떻게 갈리는지 정리한다. 처리량 수치(+6.2%)는 vLLM RFC 실험값이고, 나머지는 분포 조건별 상대 경향이다.
| 정책 | 균등 분포 p99 TPOT | 장꼬리 분포 p99 TPOT | starvation 위험 | 처리량(균등) |
|---|---|---|---|---|
| FCFS | 기준 | 기준 대비 크게 증가 | 낮음 | 기준 |
| SJF | 소폭 감소 | 기준보다 높게 증가 | 긴 요청에 높음 | +6.2% |
| Priority(고우선) | 감소 | 감소 유지 | 낮음 | 유사 |
| Priority(저우선) | 크게 증가 | 매우 크게 증가 | 매우 높음 | 유사 |
요청 길이 편차가 클수록 정책 선택 효과가 커진다. 균등 분포에서는 세 정책 간 차이가 수십 ms 수준이지만, 장꼬리 분포에서는 정책에 따라 p99 TPOT가 수백 ms 단위로 달라진다. Priority Scheduling에서 저우선순위 요청의 p99가 가장 크게 오르는 이유는 preemption이 반복·누적되기 때문이다.
공정성 SLO와 처리량 SLO의 충돌
처리량을 최대화하려면 배치를 꽉 채워야 한다. 꽉 찬 배치는 KV block 여유가 없고, 여유가 없으면 신규 요청 추가를 위해 기존 요청을 밀어내야 한다. 공정성 SLO(모든 요청이 일정 TPOT 이내)를 지키려면 preemption을 줄여야 하고, preemption을 줄이면 배치 크기를 보수적으로 제한한다 — 처리량이 낮아진다. 단일 정책으로 두 목표를 동시에 달성하는 방법은 없다.
Sarathi-Serve(Agrawal et al., OSDI 2024)는 chunked prefill로 이 충돌을 부분적으로 완화한다. prefill을 고정 chunk 크기로 쪼개 decode 중인 요청과 같은 iteration에 함께 실행하는 decode-first 방식이다. 진행 중인 decode를 멈추지 않으면서 새 요청을 점진적으로 배치에 올릴 수 있어, Mistral-7B 기준 2.6배, Yi-34B 기준 3.7배 서빙 용량이 개선됐다. 이 접근이 해결하는 범위는 throughput-latency tradeoff고, 우선순위 편향이 낳는 starvation은 별도 문제로 남는다.
SGLang 스케줄러는 prefix caching을 스케줄링에 통합한다. 동일 prefix를 가진 요청들을 묶어 KV cache hit를 극대화하는데, 이 과정에서 도착 순서와 무관하게 cache locality가 실질적인 우선순위로 작동한다. vLLM의 FCFS 또는 Priority 정책과는 다른 형태의 스케줄 편향이다.
운영자가 정책을 선택하는 기준은 서비스 목적으로 귀결된다. 모든 요청의 TPOT를 균등하게 보장해야 하는 단일 티어 API라면 FCFS가 가장 안전한 기준선이다. 짧은 요청의 빠른 완료가 중요하고 긴 요청의 지연을 일부 용인할 수 있으면 SJF를 고려할 수 있되, 출력 길이 예측 품질이 뒷받침되어야 한다. Priority Scheduling을 써야 한다면 aging을 함께 설정해야 하고, 저우선순위 요청의 p99 TPOT SLO는 보장하기 어렵다는 전제로 임계값을 정해야 한다.