Open-loop load generation

Deep dive

How it works

Parts:

• Schedule — list of intended send times: fixed interval 1/rate, or Poisson (exponential gaps, mean 1/rate).
• Sender — fires each request at its slot without waiting for earlier replies; many in flight at once.
• Recorder — latency = reply time − intended send time; stored in an HDR histogram or a Vec.
• Server under test — here a FIFO queue with a fixed service time and one stall.

1. Fix the target rate λ below the expected capacity μ.
2. Precompute intended send times t₀, t₁, … (interval or exponential gaps).
3. At each tᵢ send request i; never delay it because an earlier one is pending.
4. On reply, record now − tᵢ, not now − actual_send.
5. If the sender falls behind its schedule, still use tᵢ; report the lag.
6. Report p50, p99, max, achieved vs target rate, errors.

closed:  send─►wait────reply─►send─►wait─reply      (stall = 1 slow sample)
open:    t0   t1   t2   t3   t4   t5   t6   t7        (stall = every slot inside it is late)
         ▼    ▼    ▼    ▼    ▼    ▼    ▼
         └ latency measured from each ti ┘

The correction. If you cannot go open loop: a reply taking L with expected interval T implies about L/T − 1 unsent requests with latencies L−T, L−2T, …. HdrHistogram does this while recording, recordValueWithExpectedInterval(value, expectedInterval), or afterwards with copyCorrectedForCoordinatedOmission; use only one. It is a model, not a measurement.

Closed versus open. Schroeder, Wierman and Harchol-Balter (NSDI 2006) show the choice changes conclusions about response time; match the model to real clients.

Code

Virtual-time server (1 ms service, one 2 s stall at t = 50 s of 100 s), driven closed loop (one worker) and open loop (10 ms interval, 10 % load); percentiles from a sorted Vec; the correction; a seeded Poisson schedule.

// Virtual time in microseconds; nothing sleeps.
struct Server { svc: u64, free: u64, stall_at: u64, stall: u64, stalled: bool }
impl Server {
    /// FIFO single server. The first request that starts at or after `stall_at`
    /// is held for `stall` extra µs (GC pause, failover, disk hiccup).
    fn serve(&mut self, arrive: u64) -> u64 {
        let mut start = arrive.max(self.free);
        if !self.stalled && start >= self.stall_at {
            self.stalled = true;
            start += self.stall;
        }
        self.free = start + self.svc;
        self.free
    }
}

/// One worker, back to back: the next send waits for the last reply.
fn closed_loop(s: &mut Server, horizon: u64) -> Vec<u64> {
    let (mut t, mut lat) = (0, vec![]);
    while t < horizon {
        let done = s.serve(t);
        lat.push(done - t);
        t = done;
    }
    lat
}

/// Sends on a fixed schedule; latency counts from the intended send time.
fn open_loop(s: &mut Server, horizon: u64, interval: u64) -> Vec<u64> {
    (0..horizon / interval).map(|i| { let t = i * interval; s.serve(t) - t }).collect()
}

/// HdrHistogram-style correction: a reply that took `lat` > `interval` also
/// stands for the requests that should have been sent while it was pending.
fn corrected(lat: &[u64], interval: u64) -> Vec<u64> {
    let mut out = vec![];
    for &l in lat {
        out.push(l);
        let mut m = l;
        while m > interval { m -= interval; out.push(m); }
    }
    out
}

/// (p50, p99, max) of a sample set; sorted copy, nearest-rank percentile.
fn pct(v: &[u64]) -> (u64, u64, u64) {
    let mut s = v.to_vec();
    s.sort_unstable();
    let at = |p: f64| s[((p * s.len() as f64).ceil() as usize).max(1) - 1];
    (at(0.5), at(0.99), *s.last().unwrap())
}

struct Rng(u64); // splitmix64
impl Rng {
    fn next(&mut self) -> u64 {
        self.0 = self.0.wrapping_add(0x9E37_79B9_7F4A_7C15);
        let mut z = self.0;
        z = (z ^ (z >> 30)).wrapping_mul(0xBF58_476D_1CE4_E5B9);
        z = (z ^ (z >> 27)).wrapping_mul(0x94D0_49BB_1331_11EB);
        z ^ (z >> 31)
    }
    fn unit(&mut self) -> f64 { (self.next() >> 11) as f64 / (1u64 << 53) as f64 } // [0,1)
}

/// Poisson arrivals at `rate` per second: exponential gaps, as µs timestamps.
fn poisson_schedule(rng: &mut Rng, rate: f64, n: usize) -> Vec<u64> {
    let mut t = 0.0;
    (0..n).map(|_| { t += -(1.0 - rng.unit()).ln() / rate * 1e6; t as u64 }).collect()
}

fn main() {
    let (svc, interval, horizon, stall) = (1_000, 10_000, 100_000_000, 2_000_000);
    let srv = |stall| Server { svc, free: 0, stall_at: 50_000_000, stall, stalled: false };

    // no stall: both generators see the same p50 (the service time)
    let c0 = pct(&closed_loop(&mut srv(0), horizon));
    let o0 = pct(&open_loop(&mut srv(0), horizon, interval));
    assert_eq!(c0.0, o0.0);

    // 2 s stall once in 100 s
    let c = closed_loop(&mut srv(stall), horizon);
    let o = open_loop(&mut srv(stall), horizon, interval);
    let (cp, op) = (pct(&c), pct(&o));
    let cc = pct(&corrected(&c, svc));
    println!("closed n={} p50/p99/max us = {cp:?}", c.len());
    println!("open   n={} p50/p99/max us = {op:?}", o.len());
    println!("closed + correction        = {cc:?}");
    assert!(cp.1 < stall / 100);   // closed loop hides the stall: one sample in ~100k
    assert!(op.1 > stall / 4);     // open loop: ~2 % of scheduled sends were delayed
    assert_eq!(cp.2, op.2);        // both record the worst request
    assert!(cc.1 > stall / 4);     // correcting at the loop's own 1 ms pace restores it

    // Poisson schedule: mean gap within 1 % of 1/rate over 1e6 samples
    let sched = poisson_schedule(&mut Rng(42), 1000.0, 1_000_000);
    let mean = *sched.last().unwrap() as f64 / sched.len() as f64;
    println!("poisson mean gap {mean:.1} us (target 1000)");
    assert!((mean - 1000.0).abs() < 10.0);
}

Run (release, asserts pass): closed 98,000 samples, p50/p99/max = 1.0 / 1.0 / 2001 ms; open 10,000 samples, 1.0 / 1101 / 2001 ms; closed with correction: p99 1001 ms; Poisson mean gap 1001.0 µs for a 1000 µs target.

Complexity and constants

• Percentiles: sort O(n log n) once; an HDR histogram records in O(1) with bounded memory.
• Queueing: for Poisson arrivals at rate λ into one server with exponential service (M/M/1), mean time in system is S/(1−ρ) with ρ = λS. At ρ = 0.5, 0.9, 0.99 that is 2×, 10×, 100× the service time S. Real services differ, but the knee is real (queueing theory).

Efficiency

• Cost: one timestamp pair and one histogram increment per request; the bound is the generator's own CPU, NIC and connections, not the target.
• Levers:
  • HDR histogram instead of every sample — bounded memory, mergeable across machines — long runs
  • one pre-opened connection pool — no handshake per request (see connection pooling) — when production traffic is keep-alive
  • several generator machines, merged histograms — no one-client ceiling — beyond one NIC or core
• Naive → standard → state of the art:
  • N closed-loop workers, latency from actual send · hides stalls
  • constant-rate sender, latency from intended send · fixes omission
  • Poisson schedule + HDR histogram + multiple generators + lag reporting · realistic bursts, checked generator

Implementation notes

• Schedule from a base time (t0 + i·interval), never last_send + interval: that drifts and re-introduces omission.
• Cap in-flight requests and count drops, or the backlog exhausts the generator first.
• Separate sender and receiver (threads or async): a blocking read must not delay the next send.
• Warm up and discard the first seconds; run long enough to contain rare stalls.
• Monotonic clock; a 1 ms sleep may overshoot, so busy-wait the last slice or send all slots that are due. A token bucket also paces sends.

Pitfalls

• Latency from actual send time is coordinated omission again, even with an open sender.
• Generator CPU saturation or GC pauses look like server latency; watch its CPU and schedule lag.
• One client machine: one NIC, port range or core caps the rate and shapes traffic.
• Keep-alive versus new connections differs by a handshake per request; copy production.
• Above capacity you measure the backlog, not the service; sweep rates and plot latency against rate.
• Services with backpressure or load shedding answer fast with errors; count errors, not only latencies.
• Stalls are hard to repeat: provoke them with fault injection, replay with record-replay or deterministic simulation testing.

Variants and alternatives

In production

wrk2 (HTTP, constant throughput with coordinated-omission-correct latency), Vegeta (constant request rate), k6 (constant-arrival-rate executor) and Gatling (open and closed injection profiles) test web services; YCSB's -target paces database benchmarks; HdrHistogram is the usual recorder.

Implementations

Sources

• Gil Tene, How NOT to Measure Latency, conference talk (no link given; not verified).
• Bianca Schroeder, Adam Wierman, Mor Harchol-Balter, Open Versus Closed: A Cautionary Tale, NSDI 2006. paper
• wrk2 README, coordinated omission. code
• HdrHistogram, recordValueWithExpectedInterval. code
• Grafana k6 docs, constant arrival rate executor. docs
• Gatling docs, injection (open and closed models). docs