Dynamic batching

Deep dive

How it works

Parts:

• request queue — FIFO (or one per priority level); entries carry arrival time and reply channel
• batcher — one thread per model instance; owns the flush decision
• backend — list of inputs in, list of outputs of the same length out

Operations:

1. Enqueue. Stamp the request with its arrival time and push it. If the queue is over its limit, reject at once.
2. Wait. With an empty queue the batcher blocks, with no timer. Once a request is queued, the deadline is arrival(oldest) + max_delay.
3. Flush on size or time. Dispatch when len == max_batch_size or the deadline passes, whichever comes first.
4. Shape. Pad or bucket inputs to a common shape (below).
5. Run once, scatter. One backend call; results go back by position.
6. Repeat. Arrivals during the call queue with their deadlines already ticking, so under load the next batch leaves at once.

 clients ──► [ queue: r1 r2 r3 … ] ──► batcher ──► backend(batch) ──► scatter ──► clients
                  │ oldest.arrival + max_delay            ▲
                  └──────── full? or deadline? ───────────┘ flush
 latency ≈ queue wait (≤ max_delay + running batch) + S(batch);   S(n) = fixed + n·per_item

Choosing the knobs. Measure the backend's service time S(n); throughput at batch n is n / S(n). Pick max_batch_size where that curve flattens, within memory limits. Set max_delay ≤ SLO − S(max_batch) − margin. Triton's guide: pick a max batch, enable the defaults, measure, and if latency is within budget raise the batch size or the delay until the budget is used. TF Serving: a few ms for online GPU serving, sometimes 0, a large timeout for bulk jobs. Clipper finds the max batch itself: add a fixed amount per step until a batch exceeds the SLO, then back off by 10 % (AIMD).

Variable-length inputs. Padding to the longest item wastes compute. Bucket requests by length (a queue per bucket), or budget by total size: Ray Serve's batch_size_fn caps total tokens or nodes instead of item count. Triton batches ragged inputs (allow_ragged_batch). TF Serving's allowed_batch_sizes pads the batch with dummy data to a fixed set of sizes.

Instances, priorities, overload.

• Several instances: one batcher per instance (Clipper: a queue and thread per container), or a shared queue with several workers (TF Serving num_batch_threads).
• Priorities: Triton's priority_levels let urgent requests bypass lower ones.
• Overload: bound the queue and reject or time out (Triton max_queue_size, TF Serving max_enqueued_batches). Rejecting early beats serving everything late; see backpressure and circuit breakers.
• Autoscaling: batching raises per-replica capacity, so scale on queue wait or SLO burn, not CPU (autoscaling).

Code

Batcher thread, fake backend (cost = 2 ms + 100 µs per item, busy-waited; no real model), Poisson clients. Asserts: each request answered once, no batch above max_batch, queue wait bounded.

use std::sync::mpsc::{channel, Receiver, RecvTimeoutError, Sender};
use std::thread;
use std::time::{Duration, Instant};

const FIXED: Duration = Duration::from_micros(2000); // per-batch cost (launch, RPC, weight read)
const PER_ITEM: Duration = Duration::from_micros(100); // marginal cost per item

struct Req { id: u64, enq: Instant, reply: Sender<Resp> }
struct Resp { id: u64, enq: Instant, dispatched: Instant, done: Instant }

fn busy_wait(d: Duration) { let t = Instant::now(); while t.elapsed() < d { std::hint::spin_loop(); } }

/// Fake backend: cost = FIXED + PER_ITEM * n (busy-wait, not a real model). Answers each request.
fn run_batch(batch: &mut Vec<Req>, max_batch: usize) -> usize {
    let n = batch.len();
    assert!(n >= 1 && n <= max_batch, "batch of {n} exceeds max_batch {max_batch}");
    let dispatched = Instant::now();
    busy_wait(FIXED + PER_ITEM * n as u32);
    let done = Instant::now();
    for r in batch.drain(..) {
        r.reply.send(Resp { id: r.id, enq: r.enq, dispatched, done }).unwrap();
    }
    n
}

/// Flush when the batch is full, or when the OLDEST request has waited max_delay.
fn batcher(rx: Receiver<Req>, max_batch: usize, max_delay: Duration) -> usize {
    let (mut batch, mut batches): (Vec<Req>, usize) = (Vec::with_capacity(max_batch), 0);
    loop {
        let got = match batch.first() {
            None => rx.recv().map_err(|_| RecvTimeoutError::Disconnected), // idle: block, no timer
            Some(oldest) => {
                let deadline: Instant = oldest.enq + max_delay; // measured from arrival, not from dequeue
                rx.recv_timeout(deadline.saturating_duration_since(Instant::now()))
            }
        };
        match got {
            Ok(r) => { batch.push(r); if batch.len() < max_batch { continue; } }
            Err(RecvTimeoutError::Timeout) => {}
            Err(RecvTimeoutError::Disconnected) => {
                if !batch.is_empty() { run_batch(&mut batch, max_batch); batches += 1; }
                return batches;
            }
        }
        run_batch(&mut batch, max_batch);
        batches += 1;
    }
}

fn run(max_batch: usize, max_delay: Duration, clients: usize, per_client: u64, rate: f64) {
    let (tx, rx) = channel::<Req>();
    let server = thread::spawn(move || batcher(rx, max_batch, max_delay));
    let start = Instant::now();
    let handles: Vec<_> = (0..clients as u64).map(|c| {
        let tx = tx.clone();
        thread::spawn(move || {
            let (rtx, rrx) = channel::<Resp>();
            let mut s = 0x9E3779B97F4A7C15u64 ^ (c + 1); // xorshift64
            let mut t = start;
            for k in 0..per_client {
                s ^= s << 13; s ^= s >> 7; s ^= s << 17;
                let u = ((s >> 11) as f64 + 1.0) / (1u64 << 53) as f64;
                t += Duration::from_secs_f64(-u.ln() / rate); // Poisson arrivals, open loop
                while Instant::now() < t { thread::sleep(Duration::from_micros(50)); }
                tx.send(Req { id: c * per_client + k, enq: Instant::now(), reply: rtx.clone() }).unwrap();
            }
            drop(rtx);
            rrx.iter().collect::<Vec<Resp>>() // ends when the server has dropped all reply senders
        })
    }).collect();
    drop(tx);
    let resps: Vec<Resp> = handles.into_iter().flat_map(|h| h.join().unwrap()).collect();
    let batches = server.join().unwrap();

    let total = clients as u64 * per_client;
    let mut seen = vec![false; total as usize];
    for r in &resps { assert!(!std::mem::replace(&mut seen[r.id as usize], true), "answered twice"); }
    assert_eq!(resps.len() as u64, total, "lost a request");
    let mut lat: Vec<f64> = resps.iter().map(|r| (r.done - r.enq).as_secs_f64() * 1e3).collect();
    lat.sort_by(|a, b| a.partial_cmp(b).unwrap());
    let max_wait = resps.iter().map(|r| r.dispatched - r.enq).max().unwrap();
    let end = resps.iter().map(|r| r.done).max().unwrap();
    println!("max_batch {max_batch:>2} delay {:>4}us | {:>6.0} req/s | avg batch {:>5.1} | p50 {:>7.2} ms p99 {:>7.2} ms | max queue wait {:>7.2} ms",
        max_delay.as_micros(), total as f64 / (end - start).as_secs_f64(), total as f64 / batches as f64,
        lat[lat.len() / 2], lat[(lat.len() * 99 / 100).min(lat.len() - 1)], max_wait.as_secs_f64() * 1e3);
    if max_batch > 1 { // stable settings only: a full queue (overload) legitimately waits longer
        let bound = max_delay + FIXED + PER_ITEM * max_batch as u32 + Duration::from_millis(5);
        assert!(max_wait <= bound * 2, "queue wait {max_wait:?} far beyond max_delay + service time");
    }
}

fn main() {
    println!("synthetic cost model: {:?} + {:?} x n per batch; 4 clients, 1500 req/s total, 1600 requests", FIXED, PER_ITEM);
    for (b, d) in [(1, 0), (32, 0), (8, 1000), (32, 2000), (32, 5000)] { run(b, Duration::from_micros(d), 4, 400, 375.0); }
}

Complexity and constants

• Enqueue and scatter are O(1) per request; the backend call costs S(n) = F + n·c. Capacity n / (F + n·c) rises toward 1/c, reaching half of it at n = F/c.
• Tail latency ≈ max_delay + S(max_batch) plus the batch in flight.
• Measured on this Mac (Apple M4 Pro), synthetic cost model F = 2 ms, c = 100 µs, 4 client threads, 1500 req/s Poisson, 1600 requests; three runs agreed within a few percent (one p99 outlier of 8.1 ms in the 8 / 1 ms row):

Batch 1 saturates at 1 / 2.1 ms = 476 req/s, so its queue grows without bound. The batched rows keep up with the offered load. Here the delay only adds latency: the backend is busy often enough that batches form on their own. A delay pays off under bursty load with a high fixed cost (Clipper: a 2 ms delay gave 3.3x on its scikit-learn SVM, none on Spark). This is a simulation, not a model server.

Efficiency

• Cost: per request F/n + c of backend time: 2.1 ms at batch 1, 0.35 ms at batch 8 in the simulation's model (arithmetic; the measured 476 req/s matches batch 1). Bound: the fixed cost at small batches, compute or memory bandwidth at large ones; max_delay bounds the latency price.
• Levers:
  • larger max_batch_size — up to 26x throughput (Clipper, scikit-learn SVM, 20 ms SLO) — fixed cost dominates
  • short max_queue_delay — 3.3x at 2 ms (Clipper, scikit-learn SVM) — bursty load, high fixed cost
  • AIMD on the batch size — finds the SLO-limited max automatically (Clipper) — model or hardware changes
  • length buckets or allowed sizes — less padding, fewer shapes (TF Serving, Ray Serve) — variable-shape inputs
  • bounded queue — bounded queue wait (TF Serving max_enqueued_batches) — overload
• Naive → standard → state of the art:
  • one backend call per request · 476 req/s ceiling (simulation)
  • size-or-time batcher, fixed knobs · 1464 req/s at p99 ≈ 5 ms (simulation)
  • adaptive batch size, per-instance queues, priorities, admission control · holds the SLO under overload; LLMs use continuous batching

Implementation notes

• Start the deadline at the oldest request's arrival time, not at dequeue; block with no timer when idle.
• Scatter by index and check the output count equals the input count.
• Preallocate the batch and padded buffers; copy inputs once.
• Start with delay 0, then try 1-10 ms (TF Serving's CPU advice: 1,000-10,000 µs); re-tune when hardware or model changes.
• Report queue wait and service time separately; watch p99, not the mean.

Pitfalls

• At low load every request pays the full delay: check the SLO in quiet hours too.
• Closed-loop load tests hide queueing; use open-loop arrivals.
• One invalid or slow input delays or fails its whole batch: validate before enqueue.
• An unbounded queue turns overload into minutes of latency (the batch-1 row above).
• Retries on timeout add load to a full queue: cap them with a retry budget or token bucket.
• Keeping response order across batches or instances costs waiting; ask only if needed (Triton preserve_ordering).

Variants and alternatives

In production

Triton Inference Server, TensorFlow Serving, TorchServe, Ray Serve, Clipper. Outside ML: Vector sinks flush on batch.max_bytes / batch.max_events or batch.timeout_secs; TigerBeetle batches events per request; databases use group commit; NICs coalesce interrupts (Linux NAPI).

Implementations

Sources

• Crankshaw et al., Clipper: A Low-Latency Online Prediction Serving System, NSDI 2017. paper
• NVIDIA, Triton Inference Server: Batchers. docs
• TensorFlow Serving, Batching Guide. docs
• TorchServe, Batch Inference. docs
• Ray Serve, Dynamic Request Batching. docs
• Linux kernel, NAPI. docs
• Vector, Elasticsearch sink (batch options). docs
• TigerBeetle, Requests: batching events. docs