본문으로 건너뛰기

[SGLang] 스케줄링 정책: FCFS, LPM, LOF, DFS-Weight 비교 분석

들어가며

LLM 서빙에서 대기 큐에 여러 요청이 쌓여 있을 때, 어떤 순서로 처리할지에 따라 전체 throughput과 latency가 크게 달라진다. 특히 RadixCache 기반의 KV 캐시 재사용 시스템에서는 정책 선택이 캐시 히트율에 직접적인 영향을 미친다.

이 글에서는 python/sglang/srt/managers/schedule_policy.py를 중심으로, SGLang이 제공하는 스케줄링 정책과 그 구현을 분석한다.

구조도

                 SchedulePolicy
                 ┌─────────────────────────────┐
                 │  policy: Policy              │
                 │  tree_cache: BasePrefixCache │
                 │                             │
                 │  calc_priority()             │
                 │    │                         │
                 │    ├─ CacheAwarePolicy       │
                 │    │   ├─ LPM (longest       │
                 │    │   │   prefix match)     │
                 │    │   └─ DFS-Weight         │
                 │    │                         │
                 │    └─ CacheAgnosticPolicy    │
                 │        ├─ FCFS               │
                 │        ├─ LOF                │
                 │        ├─ RANDOM             │
                 │        └─ ROUTING-KEY        │
                 └─────────────────────────────┘
                           │
                           v
                 PrefillAdder.add_one_req()
                 (메모리 예산 내에서 배치 구성)

정책 분류: Cache-Aware vs Cache-Agnostic

SGLang은 정책을 두 카테고리로 명확히 분리한다.

class CacheAwarePolicy(Enum):
    """Scheduling policies that are aware of the tree cache."""
    LPM = "lpm"          # longest prefix match
    DFS_WEIGHT = "dfs-weight"  # depth-first search weighting

class CacheAgnosticPolicy(Enum):
    """Scheduling policies that are not aware of the tree cache."""
    FCFS = "fcfs"        # first come first serve
    LOF = "lof"          # longest output first
    RANDOM = "random"
    ROUTING_KEY = "routing-key"

Cache-Aware 정책은 RadixCache 트리를 탐색하여 캐시 히트를 극대화하는 방향으로 요청을 정렬한다. Cache-Agnostic 정책은 캐시 상태와 무관하게 요청 자체의 속성만으로 정렬한다.

SchedulePolicy 클래스

class SchedulePolicy:
    def __init__(self, policy, tree_cache,
                 enable_hierarchical_cache,
                 enable_priority_scheduling,
                 schedule_low_priority_values_first):
        self.policy = self._validate_and_adjust_policy(
            policy, tree_cache
        )
        self.waiting_queue_radix_tree = RadixCache.create_simulated()

주목할 점은 _validate_and_adjust_policy에서의 자동 조정이다. Tree cache가 비활성화되어 있으면, Cache-Aware 정책을 요청해도 자동으로 FCFS로 fallback된다.

def _validate_and_adjust_policy(self, policy, tree_cache):
    try:
        policy_enum = CacheAwarePolicy(policy)
        if getattr(tree_cache, "disable", True):
            return CacheAgnosticPolicy.FCFS  # 자동 fallback
        return policy_enum
    except ValueError:
        return CacheAgnosticPolicy(policy)

calc_priority: 정책 실행 진입점

def calc_priority(self, waiting_queue, running_batch=None):
    if self.policy == CacheAgnosticPolicy.FCFS:
        if self.enable_priority_scheduling:
            SchedulePolicy._sort_by_priority_and_fcfs(
                waiting_queue, self.priority_sign
            )
        return False

    policy = self._determine_active_policy(waiting_queue)
    # ...

대기 큐가 128개를 초과하면 LPM도 FCFS로 전환된다. Prefix 매칭의 시간 복잡도가 큐 크기에 비례하기 때문이다.

def _determine_active_policy(self, waiting_queue):
    if self.policy == CacheAwarePolicy.LPM and len(waiting_queue) > 128:
        return CacheAgnosticPolicy.FCFS  # 비용 제한
    return self.policy

정책별 구현 분석

FCFS (First Come First Serve)

가장 단순한 정책으로, 요청 도착 순서를 유지한다. Priority scheduling이 활성화되면 우선순위를 먼저 고려한다.

@staticmethod
def _sort_by_priority_and_fcfs(waiting_queue, priority_sign):
    waiting_queue.sort(
        key=lambda x: (
            x.priority * priority_sign,
            x.time_stats.wait_queue_entry_time,
        )
    )

LPM (Longest Prefix Match)

RadixCache에서 가장 긴 prefix가 매칭되는 요청을 우선 스케줄링한다. 캐시 히트율을 극대화하여 불필요한 recompute를 줄인다.

@staticmethod
def _sort_by_longest_prefix(waiting_queue, temporary_deprioritized):
    waiting_queue.sort(
        key=lambda r: (
            -len(r.prefix_indices)
            if r.rid not in temporary_deprioritized
            else float("inf")
        )
    )

temporary_deprioritized는 In-Batch Prefix Caching 로직에서 중복 prefix를 가진 요청을 잠시 뒤로 미루는 메커니즘이다.

DFS-Weight

RadixCache 트리를 DFS로 탐색하며, 각 노드의 가중치(해당 subtree에서 대기 중인 요청 수)를 기반으로 정렬한다.

@staticmethod
def _sort_by_dfs_weight(waiting_queue, tree_cache):
    last_node_to_reqs = defaultdict(list)
    for req in waiting_queue:
        last_node_to_reqs[req.last_node].append(req)

    node_to_weight = defaultdict(int)
    for node in last_node_to_reqs:
        node_to_weight[node] = len(last_node_to_reqs[node])
    SchedulePolicy._calc_weight(
        tree_cache.root_node, node_to_weight
    )

트리의 leaf에서 root 방향으로 가중치를 합산한 뒤, 가중치가 높은 subtree의 요청을 먼저 스케줄링한다. 같은 prefix를 공유하는 요청들을 연속으로 처리하여 캐시 locality를 높이는 효과가 있다.

LOF (Longest Output First)

출력 길이가 긴 요청을 먼저 처리한다.

@staticmethod
def _sort_by_longest_output(waiting_queue,
                             enable_priority_scheduling,
                             priority_sign):
    if enable_priority_scheduling:
        waiting_queue.sort(
            key=lambda x: (
                x.priority * priority_sign,
                -x.sampling_params.max_new_tokens,
            )
        )
    else:
        waiting_queue.sort(
            key=lambda x: -x.sampling_params.max_new_tokens
        )

Routing-Key

Running batch에서 가장 많이 사용 중인 routing key를 가진 대기 요청을 우선 처리한다. Multi-LoRA 환경에서 같은 adapter를 사용하는 요청을 묶어 처리할 때 유용하다.

@staticmethod
def _sort_by_routing_key(waiting_queue, running_batch):
    routing_key_counts = Counter(
        r.routing_key for r in running_batch.reqs if r.routing_key
    )

    def sort_key(req):
        key = req.routing_key
        if key and key in routing_key_counts:
            count = routing_key_counts[key]
            return (0, -count, key)
        else:
            return (1, 0, key or "")

    waiting_queue.sort(key=sort_key)

In-Batch Prefix Caching

LPM 정책에서 특히 중요한 최적화다. 같은 prefix를 공유하지만 아직 캐시에 없는 요청이 여러 개 있을 때, 첫 번째 요청만 처리하고 나머지는 deprioritize한다.

if len(r.prefix_indices) <= IN_BATCH_PREFIX_CACHING_CHECK_THRESHOLD:
    in_batch_matching_prefixes = (
        self.waiting_queue_radix_tree.match_prefix(...)
    )
    if len(in_batch_matching_prefixes) >= \
       IN_BATCH_PREFIX_CACHING_DEPRIORITIZE_THRESHOLD:
        temporary_deprioritized.add(r.rid)

첫 번째 요청이 prefill되면 그 결과가 RadixCache에 저장되고, 다음 스텝에서 나머지 요청들은 캐시 히트를 얻어 더 빠르게 처리된다.

정책 비교표

정책 캐시 인식 정렬 기준 장점 단점 적합한 워크로드
FCFS X 도착 순서 공정, 오버헤드 최소 캐시 활용 못 함 다양한 요청, 캐시 불필요
LPM O prefix 길이 캐시 히트율 극대화 큐 > 128 시 FCFS로 fallback 공통 시스템 프롬프트
DFS-Weight O 트리 가중치 prefix 공유 locality 극대화 계산 복잡도 높음 대화형, prefix 공유 많은 경우
LOF X max_new_tokens 긴 작업 우선 완료 짧은 요청 기아 가능 배치 코드 생성
RANDOM X 무작위 편향 없음 최적화 없음 벤치마크, 테스트
Routing-Key X running batch key 빈도 LoRA 전환 최소화 running batch 의존 Multi-LoRA 서빙

왜 이 설계인가

1. 2계층 분류: Cache-Aware와 Cache-Agnostic의 분리는 RadixCache가 비활성화된 환경(ChunkCache 등)에서도 정책 코드가 안전하게 동작하도록 보장한다.

2. 동적 정책 전환: LPM이 큐 크기 128 초과 시 FCFS로 자동 전환되는 것은 실용적인 트레이드오프다. Prefix 매칭의 O(n * L) 비용이 큰 큐에서는 스케줄링 자체가 병목이 될 수 있기 때문이다.

3. In-Batch Prefix Caching: 같은 prefix를 가진 요청을 한꺼번에 처리하면 중복 연산이 발생한다. 첫 번째만 처리하고 나머지를 뒤로 미루는 전략은 캐시 효율을 극대화하면서도 구현이 간단하다.

관련 포스트

  • [SGLang] Zero-Overhead CPU Scheduler: 배치 스케줄링의 핵심 설계
  • [SGLang] ScheduleBatch & Req: 배치 데이터 구조의 설계와 생명주기
  • [SGLang] Continuous Batching & Chunked Prefill: 동적 배칭의 핵심

참고

댓글

관련 포스트

SGLang 의 다른글