ORCA: continuous batching은 어디서 왔는가 (1) — iteration-level scheduling과 selective batching

vLLM을 써보셨다면 “continuous batching” 혹은 “in-flight batching”이라는 말을 한 번쯤 들어보셨을 겁니다. 요청이 도중에 들어와도 배치에 끼워 넣고, 먼저 끝난 요청은 바로 반환하는 그 기능입니다. LLM 서빙의 처리량을 끌어올린 핵심 기법이지만, 이 아이디어의 원형은 vLLM이 아니라 2022년 OSDI에 발표된 ORCA라는 논문입니다.

ORCA는 서울대와 FriendliAI가 함께 낸 논문으로, 정식 제목은 ORCA: A Distributed Serving System for Transformer-Based Generative Models 입니다. 이 글에서는 ORCA가 제기한 문제와 그 해법 두 가지 — iteration-level scheduling과 selective batching — 을 정리합니다. 오늘날 우리가 당연하게 쓰는 continuous batching이 정확히 어떤 문제를 풀기 위해 등장했는지 이해하는 것이 목표입니다.

왜 생성 모델 서빙은 기존 방식으로 안 되는가

먼저 생성 모델(GPT류)이 다른 모델과 근본적으로 다른 지점부터 짚어야 합니다.

ResNet이나 BERT 같은 모델은 요청 하나를 처리할 때 모델을 한 번만 실행하면 끝납니다. 입력을 넣으면 출력이 한 번에 나옵니다. 반면 GPT는 autoregressive 방식이라, 토큰을 하나씩 순차적으로 생성합니다. 매 실행이 토큰 하나를 만들고, 그 토큰이 다음 실행의 입력이 됩니다. 논문은 “모든 레이어를 한 번 통과하는 것”을 iteration이라고 정의하는데, 요청 하나를 끝내려면 생성할 토큰 수만큼 iteration을 반복해야 합니다.

이 과정은 두 단계로 나뉩니다.

• initiation phase: 클라이언트가 준 입력 토큰 전체를 한 번에 병렬 처리해 첫 출력 토큰을 생성합니다. 보통 1 iteration으로 끝납니다.
• increment phase: 직전에 생성한 토큰 하나를 입력으로 받아 다음 토큰을 생성합니다. <EOS>(문장 종료 토큰)가 나올 때까지 이 과정을 반복합니다.

즉 요청마다 필요한 iteration 수가 제각각입니다. 어떤 요청은 토큰 10개를 만들고 끝나고, 어떤 요청은 200개를 만듭니다. 바로 이 multi-iteration 특성이 기존 서빙 시스템의 설계와 충돌합니다.

문제 1: 먼저 끝난 요청도 못 나가고, 새 요청도 못 들어온다

기존 서빙 시스템(Triton 등)과 실행 엔진(FasterTransformer 등)은 request 단위로 스케줄링합니다. 서빙 시스템이 요청 여러 개를 하나의 배치로 묶어 엔진에 던지면, 엔진은 배치 안의 모든 요청이 끝날 때까지 결과를 돌려주지 않습니다. 서빙 시스템과 엔진이 상호작용하는 순간은 딱 두 번뿐입니다. 유휴 엔진에 새 배치를 넣을 때, 그리고 엔진이 현재 배치를 완전히 끝냈을 때.

문제는 요청마다 필요한 iteration 수가 다르다는 점에서 터집니다.

• 먼저 끝난 요청이 발이 묶입니다. 배치 안의 x2가 x1보다 먼저 끝나도, 엔진은 x1이 끝날 때까지 x2를 붙잡고 있습니다. 그동안 이미 끝난 x2에 대해서도 불필요한 연산이 계속 돌아갑니다. 먼저 끝난 요청을 클라이언트에 즉시 반환하지 못하니 지연(latency)이 늘어납니다.
• 새 요청이 대기해야 합니다. 배치가 실행되는 도중에 새 요청이 도착하면, 현재 배치가 전부 끝날 때까지 기다려야 합니다. 큐잉 지연이 급격히 커집니다.

참고로 이 문제는 학습(training) 때는 발생하지 않습니다. 학습은 teacher forcing 기법으로 배치 전체를 한 iteration에 처리하기 때문입니다. 오직 추론 서빙에서만, 그것도 생성 모델에서만 불거지는 문제입니다.

해법 1: iteration-level scheduling

ORCA의 첫 번째 제안은 스케줄링의 단위를 request에서 iteration으로 낮추는 것입니다.

스케줄러는 다음 절차를 반복합니다.

1. 다음에 실행할 요청들을 선택한다.
2. 선택한 요청들에 대해 딱 1 iteration만 실행하도록 엔진에 지시한다.
3. 실행 결과(토큰)를 받는다.

매 iteration마다 결과가 돌아오므로, 스케줄러는 매번 요청의 완료 여부를 확인할 수 있습니다. 끝난 요청은 그 즉시 클라이언트에 반환합니다. 새로 도착한 요청도 현재 iteration 하나만 끝나면 바로 다음 선택 대상에 낄 수 있습니다. 배치가 통째로 끝나기를 기다릴 필요가 없어진 겁니다.

ORCA의 구조를 보면, 새로 온 요청은 일단 request pool이라는 곳에 들어갑니다. 스케줄러는 이 pool을 감시하며 매 iteration마다 어떤 요청을 돌릴지 새로 결정합니다. 엔진이 토큰을 하나씩 반환하면 pool의 해당 요청에 이어 붙이고, 끝난 요청은 pool에서 제거한 뒤 응답을 내보냅니다. 핵심은 매 iteration마다 처리 대상을 자유롭게 바꿀 수 있다는 점입니다. 이것이 오늘날 continuous batching의 골격입니다.

문제 2: 임의로 고른 요청들을 배칭할 수가 없다

그런데 iteration-level scheduling을 실제로 구현하려 하면 골치 아픈 문제가 하나 튀어나옵니다. 바로 배칭(batching)입니다.

GPU를 효율적으로 쓰려면 여러 요청을 큰 텐서 하나로 묶어 한 번에 처리해야 합니다. 배칭 없이 요청을 하나씩 처리하면 GPU의 병렬 연산 능력을 살릴 수 없습니다. 문제는, 스케줄러가 매 iteration마다 임의로 고른 요청 집합이 항상 배칭 가능하지는 않다는 것입니다. 다음 세 경우엔 두 요청을 한 배치로 묶을 수 없습니다.

1. 둘 다 initiation phase인데 입력 토큰 수가 다름 → 텐서의 length 차원이 안 맞습니다.
2. 둘 다 increment phase인데 처리 중인 토큰 index가 다름 → Attention의 key/value 텐서 shape이 달라집니다.
3. 한쪽은 initiation, 한쪽은 increment → 입력 토큰 수 자체가 다릅니다.

배칭은 “같은 phase + 같은 토큰 수(또는 같은 index)”라는 까다로운 조건을 만족할 때만 가능합니다. 실제 워크로드에서 이 조건을 동시에 만족하는 요청들이 존재할 확률은 낮고, 배치 크기를 키울수록 그 확률은 지수적으로 떨어집니다. iteration-level scheduling의 유연함이 오히려 배칭을 어렵게 만든 셈입니다.

해법 2: selective batching

ORCA의 두 번째 제안은 발상의 전환입니다. 모델의 모든 연산을 배칭하려 들지 말고, 일부 연산에만 선택적으로 배칭을 적용하자는 것입니다.

여기서 핵심 통찰은, 문제를 일으키는 연산이 사실상 Attention 하나뿐이라는 점입니다.

Linear, LayerNorm, Add, GeLU 같은 non-Attention 연산들은 요청 간 구분이 필요 없습니다. 이런 연산은 여러 요청의 토큰을 그냥 [∑L, H] 형태(모든 토큰을 일렬로 이어 붙인 2차원 텐서)로 평탄화(flatten)해서 통째로 처리할 수 있습니다. 배치 차원 없이 token 단위로 배칭하는 것입니다.

반면 Attention만은 “같은 요청 안의 토큰끼리만” 계산해야 하므로 요청 구분이 필요합니다. 그래서 selective batching은 이런 샌드위치 구조로 동작합니다.

1. non-Attention 연산은 [∑L, H]로 평탄화해 배칭 실행 (QKV Linear까지)
2. Attention 직전에 Split — 배치를 쪼개 요청별로 개별 Attention 실행
3. Merge — 개별 결과를 다시 [∑L, H]로 합침
4. 합쳐진 상태로 나머지 non-Attention 연산 계속 (Attn Out Linear 등)

즉 전체는 평탄화된 상태로 흐르다가, Attention 구간만 잠깐 쪼갰다 다시 합치는 형태입니다.

그렇다면 Attention을 배칭하지 않으면 손해가 크지 않을까요? 그렇지 않습니다. 배칭의 이득은 모델 파라미터를 GPU 메모리에서 한 번 읽어 여러 요청이 재사용하는 데서 나옵니다. 그런데 Attention 연산에는 모델 파라미터가 없습니다. 따라서 Attention을 배칭해도 파라미터 재사용 이득이 애초에 없고, 배칭하지 않는 결정이 효율에 미치는 영향도 작습니다. 이것이 selective batching이 성립하는 이유입니다.

K/V는 누가, 언제까지 들고 있는가

한 가지 짚고 넘어갈 부분이 있습니다. increment phase의 요청은 이전 토큰들의 key/value가 있어야 Attention을 계산할 수 있습니다. 이 상태를 관리하는 것이 Attention K/V manager입니다.

여기서 저장하는 것은 key와 value뿐이라는 점에 주의해야 합니다. Query는 저장하지 않습니다. Attention은 “현재 토큰의 Q”와 “이전+현재 토큰들의 K/V”로 계산되는데, 이전 토큰들의 Q는 재사용할 일이 없기 때문입니다. 누적해서 들고 있어야 하는 것은 K/V입니다. (이름이 QKV cache가 아니라 K/V manager인 이유입니다.)

manager는 이 K/V를 요청별로 따로 보관합니다. 그리고 언제 지울까요? 중간 결과 버퍼처럼 즉시 회수되지 않고, 스케줄러가 해당 요청이 끝났다고 판단해 명시적으로 제거를 지시할 때까지 계속 들고 있습니다. 이 때문에 스케줄러는 K/V 메모리의 잔여 공간까지 인지하고 있어야 하는데, 이 부분은 다음 글에서 다룰 ORCA의 메모리 예약 스케줄링으로 이어집니다.

정리

ORCA가 제기한 문제와 해법을 한 줄로 요약하면 이렇습니다.

• request 단위 스케줄링은 요청마다 길이가 달라 지연을 유발한다 → iteration 단위로 스케줄링해 끝난 요청은 즉시 반환하고 새 요청은 바로 합류시킨다.
• iteration 단위로 하면 스케줄러가 고른 임의의 요청 집합을 배칭할 수 없다 → selective batching으로 non-Attention은 평탄화해 배칭하고, Attention만 Split/Merge로 개별 처리한다.

이 두 기법이 바로 오늘날 vLLM의 continuous batching으로 이어지는 원형입니다. 다음 글에서는 ORCA가 이를 대규모 모델로 확장하기 위해 도입한 분산 아키텍처와, K/V 메모리를 고려한 스케줄링 알고리즘을 다루겠습니다.

---

📚 시리즈: LLM 서빙 인프라

1. OS의 페이징을 KV Cache에 가져온 PagedAttention
2. ORCA: continuous batching은 어디서 왔는가 (1) — iteration-level scheduling과 selective batching ← 지금 글
3. ORCA: continuous batching은 어디서 왔는가 (2) — 분산 아키텍처와 예약 스케줄링
4. GPU, TPU, NPU — AI 칩은 무엇이 다르고 언제 무엇을 쓰는가