estudy 한국어/English

Continuous Batching Algorithm

1,814 단어·4 분·원문(.md)

Let's start with a question. Dynamic Batching, which we covered in the previous topic, was an excellent technique for processing multiple requests together. But what if, when batching 4 requests for LLM text generation, 3 of them finish after generating only 10 characters, while the remaining one needs to generate 1000 characters?

In traditional batching methods, there's a problem where the 3 GPU computation slots that finished early must remain idle, waiting for the longest request to complete.

To overcome this significant inefficiency, a technique called continuous batching, or iteration-level scheduling, emerged.

  • Limitations of Static/Dynamic Batching: Once a batch is formed at the request level, it isn't released until all requests are complete. Since the length of text generated by LLMs varies greatly for each request, this leads to significant waste.
  • Continuous Batching (Iteration-Level): This algorithm ensures 100% GPU utilization by having the scheduler check the batch status every time a word (a single token) is generated. Requests that have finished generation are immediately evicted from the batch, and new requests from the waiting queue are instantly injected into the empty slots. This approach is adopted by core engines like vLLM and TGI.

Problem Definition #

In other words, because existing serving engines scheduled at the request level, the entire batch was tied to the longest response length within the batch, leading to a Head-of-Line Blocking phenomenon.

For example, in a GPU environment with a batch size of 4, even if 3 slots have finished their computations and are idle, dozens of new users waiting in the queue cannot even enter the GPU and experience delays (or timeouts) until the remaining single request is completed.

Solution #

  • Token-by-Token Scheduling Check: This is a token-unit check where the scheduler intervenes after each Forward Pass (1-token generation operation) by the LLM to identify sequences that have produced an EOS (End of Sentence) token.
  • Immediate State Transition (Eviction & Injection): The results of requests that have reached EOS are immediately streamed back to the client, and their VRAM is released. Simultaneously, prompts from new requests in the Pending Queue are pushed into the empty slots to join the next Forward Pass. This minimizes GPU idle time to near zero.

Forward Pass #

A forward pass is a feed-forward computational flow where data enters the neural network's input layer, undergoes matrix operations in the hidden layers, and then produces a final prediction. From an LLM serving perspective, completing one forward pass means the entire model has been traversed once to predict the next single token.

Typically, after a forward pass, weights are updated via backpropagation, which calculates the error and propagates it backward. However, in API servers operating real services, backpropagation is unnecessary; only forward passes are repeated infinitely to handle customer requests. If this distinction isn't clearly controlled at the code level, the framework might continuously hold onto unnecessary memory gradients, leading to VRAM leaks and potential OOM errors.

  • Prefill Phase (Prompt Processing): The entire user query is batched and processed with a single, heavy, and large forward pass to compute the full context KV cache for serving.
  • Decode Phase (Token Generation): Based on the prefill results, a light forward pass is repeatedly executed to generate one token at a time. The continuous batching discussed earlier maximizes efficiency precisely at this stage.

Detailed Operating Principles and Structure #

Let's compare the GPU slot utilization of traditional batching and Continuous Batching.

gantt
    title Traditional Batching vs Continuous Batching
    dateFormat  s
    axisFormat %S
    
    section Traditional (낭비 발생)
    Req 1 (10토큰) :active, a1, 0, 2s
    Req 2 (10토큰) :active, a2, 0, 2s
    Req 3 (30토큰) :active, a3, 0, 6s
    GPU 슬롯 1 유휴 상태 (Idle) :crit, c1, 2s, 6s
    GPU 슬롯 2 유휴 상태 (Idle) :crit, c2, 2s, 6s
    새로운 요청 진입 불가 :c3, 2s, 6s

    section Continuous Batching (즉시 투입)
    Req 1 (10토큰) :active, b1, 0, 2s
    Req 2 (10토큰) :active, b2, 0, 2s
    Req 3 (30토큰) :active, b3, 0, 6s
    새 요청 Req 4 즉시 투입 :done, b4, 2s, 6s
    새 요청 Req 5 즉시 투입 :done, b5, 2s, 5s

Example #

Let's understand this by looking at the Python pseudocode for the scheduling logic that operates within the engine for each token generation iteration.

class ContinuousBatchingScheduler:
    def __init__(self, max_batch_size=4):
        self.max_batch_size = max_batch_size
        self.waiting_queue = []  # 대기 중인 새 요청
        self.active_batch = []   # 현재 GPU에서 연산 중인 요청 슬롯

    def step(self):
        """매 토큰 생성(Forward Pass) 직후 호출되는 스케줄링 로직"""
        
        # 1. 종료된 요청 방출 (Eviction)
        retained_batch = []
        for req in self.active_batch:
            if req.is_finished(): # EOS 토큰이 나왔거나 최대 길이에 도달했는지 확인
                print(f"[{req.id}] 생성 완료. 배치에서 제거 및 결과 반환.")
            else:
                retained_batch.append(req)
        self.active_batch = retained_batch

        # 2. 빈자리만큼 새 요청 투입 (Injection)
        available_slots = self.max_batch_size - len(self.active_batch)
        while available_slots > 0 and self.waiting_queue:
            new_req = self.waiting_queue.pop(0)
            self.active_batch.append(new_req)
            print(f"[{new_req.id}] 빈 슬롯에 새 요청 즉시 투입.")
            available_slots -= 1

        # 3. 구성된 새로운 배치로 다음 1토큰 동시 추론 진행 (GPU Forward Pass)
        if self.active_batch:
            # model.forward(self.active_batch)
            pass

Typically, one doesn't write a scheduler directly as shown above. Instead, this is configuration code to control the engine's scheduling limits to maximize the efficiency of vLLM's Continuous Batching in production.

from vllm.engine.arg_utils import AsyncEngineArgs
from vllm.engine.async_llm_engine import AsyncLLMEngine

# Continuous Batching 스케줄러가 최적의 결정을 내릴 수 있도록 제어값을 부여
engine_args = AsyncEngineArgs(
    model="meta-llama/Llama-3-8B",
    
    # [핵심 파라미터 1] max_num_seqs
    # Continuous Batching 큐에서 '동시에 GPU 연산 슬롯에 올릴 수 있는 최대 문장(요청) 개수'
    # 이 값이 너무 크면 VRAM OOM이 발생하고, 너무 작으면 배치에 빈자리가 생겨 Throughput이 떨어짐
    max_num_seqs=256,
    
    # [핵심 파라미터 2] max_num_batched_tokens
    # 한 번의 스텝(Iteration)에서 처리할 수 있는 총 토큰 수의 합 (Prompt 토큰 + 생성 토큰)
    # 새 요청(프롬프트)이 중간에 Inject 될 때, 이 토큰 수 한계를 넘지 않는 선에서만 투입을 허용함
    max_num_batched_tokens=8192,
    
    # 앞서 학습한 PagedAttention과 결합되어 VRAM을 효율적으로 재활용
    gpu_memory_utilization=0.9
)

# 비동기 엔진 기동
engine = AsyncLLMEngine.from_engine_args(engine_args)

Continuous Batching rapidly adds and removes requests internally, making it difficult for an external API server to know how stressed the GPU is.

Here's a background observability pattern for performing zero-downtime scale-out by monitoring the engine's internal scheduler's pending queue during traffic spikes:

from fastapi import FastAPI
import asyncio
from prometheus_client import Gauge
import logging

logger = logging.getLogger(__name__)
app = FastAPI()

# 1. Prometheus 메트릭 정의 (그라파나 대시보드 연동용)
# 대기 중인 요청 수, 현재 처리 중인 요청 수, GPU 캐시 사용률을 추적합니다.
METRIC_PENDING_REQUESTS = Gauge('vllm_pending_requests', 'Number of requests waiting in queue')
METRIC_RUNNING_REQUESTS = Gauge('vllm_running_requests', 'Number of requests currently in continuous batch')
METRIC_KV_CACHE_USAGE = Gauge('vllm_kv_cache_usage_percent', 'GPU KV Cache usage percentage')

async def log_continuous_batching_stats(engine):
    """엔진 내부의 스케줄러 통계를 주기적으로 빼내어 메트릭으로 노출하는 백그라운드 태스크"""
    while True:
        try:
            # vLLM 엔진 내부의 현재 스케줄링 상태(Stats) 강제 조회
            stats = await engine.get_decoding_stats()
            
            # 메트릭 게이지 업데이트
            METRIC_PENDING_REQUESTS.set(stats.num_requests_waiting)
            METRIC_RUNNING_REQUESTS.set(stats.num_requests_running)
            METRIC_KV_CACHE_USAGE.set(stats.gpu_cache_usage)
            
            # 특정 임계치 초과 시 경고 로깅 (Auto-scaling 트리거 조건으로 활용 가능)
            if stats.num_requests_waiting > 100:
                logger.warning(f"🚨 Continuous Batching Queue 포화 상태! 대기 중: {stats.num_requests_waiting}건")
                
        except Exception as e:
            logger.error(f"메트릭 수집 중 오류: {e}")
            
        await asyncio.sleep(2.0) # 2초마다 수집

@app.on_event("startup")
async def startup_event():
    # 애플리케이션 시작 시 백그라운드 모니터링 루프 실행
    asyncio.create_task(log_continuous_batching_stats(engine))
  • While Continuous Batching isn't a silver bullet, requests will still accumulate in the waiting queue once the max_num_seqs limit is reached. Therefore, it shouldn't be treated as a black box; metrics must be extracted via internal API polling, such as get_decoding_stats().
  • The vllm_pending_requests metric collected this way can also be used as a custom metric for HPA configuration in k8s, allowing AI servers to auto-scale based on the actual waiting queue length, in addition to CPU/memory.
AI/optimize_runtime/opti5.md