FlowPrefill: LLM 서비스에서 Head-of-Line Blocking 현상을 완화하기 위한 프리필 스케줄링의 분산화

FlowPrefill: Decoupling Preemption from Prefill Scheduling Granularity to Mitigate Head-of-Line Blocking in LLM Serving

대규모 언어 모델(LLM)에 대한 수요 증가로 인해, 서비스 시스템은 다양한 서비스 수준 목표(SLO)를 가진 많은 동시 요청을 처리해야 합니다. 이는 계산 집약적인 프리필 단계에서 발생하는 Head-of-Line (HoL) Blocking 현상을 악화시키는데, 이로 인해 장시간 실행되는 요청이 리소스를 독점하고 더 높은 우선순위의 요청을 지연시켜, Time-to-First-Token (TTFT) SLO 위반이 광범위하게 발생합니다. Chunked 프리필은 중단 가능성을 제공하지만, 응답성과 처리량 간의 고유한 상충 관계를 야기합니다. Chunk 크기를 줄이면 응답 지연 시간이 개선되지만 계산 효율성이 저하되고, Chunk 크기를 늘리면 처리량이 극대화되지만 Blocking 현상이 심화됩니다. 따라서 적응적인 프리엠션 메커니즘이 필요합니다. 그러나 실행 세분성(granularity)과 스케줄링 오버헤드 간의 동적 균형을 맞추는 것은 여전히 중요한 과제입니다. 본 논문에서는 TTFT와 처리량(goodput)을 최적화하는 서비스 시스템인 FlowPrefill을 제안합니다. FlowPrefill은 프리엠션 세분성을 스케줄링 빈도와 분리하여 이 문제를 해결합니다. FlowPrefill은 적응적인 프리필 스케줄링을 달성하기 위해 다음과 같은 두 가지 주요 혁신을 도입합니다. 1) Operator-Level Preemption: 이는 연산자 경계를 활용하여 고정된 작은 Chunk로 인한 효율성 손실 없이도 미세한 실행 중단을 가능하게 합니다. 2) Event-Driven Scheduling: 이는 요청 도착 또는 완료 이벤트 시에만 스케줄링 결정을 트리거하여 효율적인 프리엠션 응답성을 지원하면서 제어 영역 오버헤드를 최소화합니다. 실제 생산 데이터 추적을 사용한 평가 결과, FlowPrefill은 최첨단 시스템에 비해 최대 5.6배 향상된 처리량을 제공하며, 다양한 SLO를 만족시키는 것으로 나타났습니다.

The growing demand for large language models (LLMs) requires serving systems to handle many concurrent requests with diverse service level objectives (SLOs). This exacerbates head-of-line (HoL) blocking during the compute-intensive prefill phase, where long-running requests monopolize resources and delay higher-priority ones, leading to widespread time-to-first-token (TTFT) SLO violations. While chunked prefill enables interruptibility, it introduces an inherent trade-off between responsiveness and throughput: reducing chunk size improves response latency but degrades computational efficiency, whereas increasing chunk size maximizes throughput but exacerbates blocking. This necessitates an adaptive preemption mechanism. However, dynamically balancing execution granularity against scheduling overheads remains a key challenge. In this paper, we propose FlowPrefill, a TTFT-goodput-optimized serving system that resolves this conflict by decoupling preemption granularity from scheduling frequency. To achieve adaptive prefill scheduling, FlowPrefill introduces two key innovations: 1) Operator-Level Preemption, which leverages operator boundaries to enable fine-grained execution interruption without the efficiency loss associated with fixed small chunking; and 2) Event-Driven Scheduling, which triggers scheduling decisions only upon request arrival or completion events, thereby supporting efficient preemption responsiveness while minimizing control-plane overhead. Evaluation on real-world production traces shows that FlowPrefill improves maximum goodput by up to 5.6$\times$ compared to state-of-the-art systems while satisfying heterogeneous SLOs.