[sglang] SGLang의 새로운 스케줄링 정책: HRRN 도입을 통한 TTFT 최적화

PR 링크: sgl-project/sglang#32911 상태: Merged | 변경: +220 / -4

들어가며

LLM 서빙 시스템에서 요청의 우선순위를 결정하는 스케줄링 정책은 시스템의 응답 속도와 처리량에 결정적인 영향을 미칩니다. 기존의 FCFS(First-Come, First-Served)나 LPM(Longest Prefix Match) 방식은 특정 상황에서 꼬리 지연 시간(tail latency)이 길어지거나, 짧은 요청이 긴 요청에 의해 차단되는 기아(starvation) 현상이 발생할 수 있습니다. SGLang에 새롭게 추가된 HRRN(Highest Response Ratio Next) 정책은 요청의 서비스 시간과 대기 시간을 모두 고려하여, 짧은 요청을 우선시하면서도 오래 대기한 요청에 가중치를 부여함으로써 이러한 문제를 해결합니다.

코드 분석

1. 스케줄러 상태 관리 (python/sglang/srt/managers/scheduler.py)

HRRN은 '얼마나 오래 기다렸는가'를 측정하기 위해 토큰 기반의 카운터를 사용합니다. processed_tokens_counter를 도입하여 시스템이 처리한 전체 프리필 토큰 수를 추적합니다.

# Before: 카운터 없음
# After:
self.processed_tokens_counter: int = 0

# 요청이 대기열에 진입할 때 스냅샷 저장
req.arrival_processed_tokens = self.processed_tokens_counter

2. HRRN 우선순위 계산 로직 (python/sglang/srt/managers/schedule_policy.py)

핵심 로직은 _sort_by_hrrn 함수에 구현되어 있습니다. 응답 비율(Response Ratio)을 계산하여 내림차순으로 정렬합니다.

# HRRN 핵심 로직
def _key(r: Req):
    uncached = SchedulePolicy._uncached_len(r)
    if uncached <= 0: return (-float("inf"), rid)
    waited_tokens = max(0, processed_tokens - r.arrival_processed_tokens)
    ratio_delta = waited_tokens / uncached
    return (-ratio_delta, rid)

왜 이게 좋은가

HRRN은 이론적으로 평균 응답 시간을 최소화하는 알고리즘입니다. 특히 SGLang의 테스트 결과에 따르면, 기존 FCFS 대비 TTFT(Time To First Token)가 평균적으로 69% 이상 개선되는 성능 향상을 보였습니다.

주요 교훈:

1. 토큰 기반 Aging: 실제 시간(wall-clock) 대신 처리된 토큰 수를 기준으로 삼음으로써, 분산 환경(TP ranks)에서도 일관된 정렬 결과를 보장합니다.
2. 기아 현상 방지: 단순히 짧은 작업만 우선하는 SJF(Shortest Job First)와 달리, 대기 시간이 길어질수록 우선순위가 자동으로 상승하므로 긴 요청도 언젠가는 반드시 처리됩니다.
3. 확장성: uncached_tokens를 기반으로 한 계산은 모델의 복잡도에 따라 가중치를 조절하기 용이한 구조를 가지고 있습니다.

리뷰어 피드백 반영

리뷰 과정에서 getattr 사용을 지양하고, 통합 모드(unified mode)에서도 arrival_processed_tokens가 올바르게 설정되도록 수정하여 코드의 안정성을 높였습니다. 또한, 대규모 큐에서 성능 저하를 방지하기 위해 128개 이상의 요청이 있을 경우 FCFS로 폴백하는 안전장치를 유지했습니다.

참고 자료

• https://docs.sglang.io/developer_guide/contribution_guide.html
• https://en.wikipedia.org/wiki/Highest_response_ratio_next

⚠️ 알림: 이 분석은 AI가 실제 코드 diff를 기반으로 작성했습니다.