Deterministic bucketing

Deep dive

How it works

In: unit id, salt, bucket count B · Out: bucket in [0, B); "in" for percentage p · State: none; salt and B sit in config · Cost: one hash over the key, O(length).

1. Choose the unit: the stable id the decision must follow.
2. Choose a salt per purpose (flag, experiment, sampler).
3. Build the key: salt, separator, unit, as UTF-8.
4. Hash with a fixed, unkeyed 32-bit hash.
5. Scale: (h * B) >> 32, or h % B.
6. In iff bucket < p * B; arms are consecutive ranges.
7. Ramp by raising p; reshuffle by changing the salt.
8. Check arm sizes against the design.

What SDKs do (read in source):

Monotone ramp. The 10 % set lies inside the 20 % set (asserted on 100,000 ids). Unleash and OpenTelemetry's trace samplers promise it. A new salt keeps only 0.102 of the old 10 % set (measured): chance level.

Independence. Distinct salts give independent buckets; a shared salt gives identical ones (Unleash: a shared groupId correlates flags). Layers and ranges: experiment layering.

Unit. User id: stable, absent before login. Device: early, one person may see several arms. Session: arms change per visit. Request: no stickiness. Trace id: all spans agree.

Login changes the id. Hashing the device id before login and the user id after gives a new bucket and a possible arm flip mid-funnel (Unleash's default input is userId, else sessionId, so a login changes it). Keep the first id, store an alias at login, or gate the test on login.

Same bytes everywhere. Fix UTF-8, separator (GrowthBook's unseparated seed+value makes ("ab","c") equal ("a","bc")), integer text (LaunchDarkly stringifies integers, cannot bucket floats), hash, seed, scaling and 0- or 1-based buckets. GrowthBook JS feeds charCodeAt (UTF-16) units to FNV, unlike a byte-wise UTF-8 FNV on non-ASCII ids. OpenTelemetry warns that TraceIdRatioBased was never specified, so SDKs may disagree. Share test vectors.

Sample-ratio check. Chi-square of arm counts against the design, alarm 10.828 at 1 df (A/B testing). Clean 50/50: 0.20; 3 % of arm A lost in logging: 27.3 (measured). Causes: salt reuse, mid-flight re-salt, login id change, bots, uneven logging.

Stateless or stored. Stateless is free, but a new salt, B, layout or hash moves units and cannot pin one. Store when eligibility is mutable or a flip is unacceptable (GrowthBook's test cases include sticky bucketing).

Code

Murmur3 and FNV-1a from primitives, asserted against the published vectors (Murmur3 also matches Optimizely's Java class on nine strings). Std only, rustc -O.

use std::time::Instant;

/// FNV-1a 32-bit (GrowthBook).
fn fnv1a32(data: &[u8]) -> u32 {
    data.iter().fold(0x811c_9dc5u32, |h, &b| (h ^ b as u32).wrapping_mul(0x0100_0193))
}

/// MurmurHash3 x86_32 (Unleash, Optimizely).
fn murmur3_32(data: &[u8], seed: u32) -> u32 {
    let (c1, c2) = (0xcc9e_2d51u32, 0x1b87_3593u32);
    let mut h = seed;
    let mut blocks = data.chunks_exact(4);
    for b in &mut blocks {
        let k = u32::from_le_bytes([b[0], b[1], b[2], b[3]]);
        h ^= k.wrapping_mul(c1).rotate_left(15).wrapping_mul(c2);
        h = h.rotate_left(13).wrapping_mul(5).wrapping_add(0xe654_6b64);
    }
    let tail = blocks.remainder();
    if !tail.is_empty() {
        let k = tail.iter().rev().fold(0u32, |k, &b| (k << 8) | b as u32);
        h ^= k.wrapping_mul(c1).rotate_left(15).wrapping_mul(c2);
    }
    h ^= data.len() as u32;
    h ^= h >> 16;
    h = h.wrapping_mul(0x85eb_ca6b);
    h ^= h >> 13;
    h = h.wrapping_mul(0xc2b2_ae35);
    h ^ (h >> 16)
}

/// Bucket in 0..b of the UTF-8 key "salt:unit", multiply-shift scaled.
fn bucket(unit: &str, salt: &str, b: u32) -> u32 {
    let h = murmur3_32(format!("{salt}:{unit}").as_bytes(), 0);
    ((h as u64 * b as u64) >> 32) as u32
}

fn in_rollout(unit: &str, salt: &str, p_bp: u32) -> bool {
    bucket(unit, salt, 10_000) < p_bp
}

fn chi2(obs: &[f64], exp: &[f64]) -> f64 {
    obs.iter().zip(exp).map(|(o, e)| (o - e) * (o - e) / e).sum()
}

fn main() {
    // Optimizely BucketerTest: murmur3 seed 1, floor(10000 * h / 2^32).
    for (id, want) in [("ppid11886780721", 5254), ("ppid21886780721", 4299), ("ppid21886780722", 2434)] {
        let h = murmur3_32(id.as_bytes(), 1);
        assert_eq!((10_000.0 * (h as f64 / 4294967296.0)).floor() as u32, want);
    }
    // GrowthBook cases.json: v1 = fnv(value+seed) % 1000, v2 = fnv(fnv(seed+value) as text) % 10000.
    let v1 = |s: &str, v: &str| fnv1a32(format!("{v}{s}").as_bytes()) % 1000;
    let v2 = |s: &str, v: &str| fnv1a32(fnv1a32(format!("{s}{v}").as_bytes()).to_string().as_bytes()) % 10_000;
    assert_eq!((v1("", "a"), v1("b", "a"), v2("seed", "a"), v2("seed", "b")), (220, 946, 505, 2696));

    let ids: Vec<String> = (0..100_000).map(|i| format!("user-{i}")).collect();
    let n = ids.len() as f64;

    // 10 % set inside the 20 % set; a new salt reshuffles.
    let set = |salt: &str, p| ids.iter().map(|u| in_rollout(u, salt, p)).collect::<Vec<_>>();
    let (s10, s20, other) = (set("flag-a", 1000), set("flag-a", 2000), set("flag-b", 1000));
    assert!(s10.iter().zip(&s20).all(|(a, b)| !a || *b));
    let n10 = s10.iter().filter(|x| **x).count();
    let kept = s10.iter().zip(&other).filter(|(a, b)| **a && **b).count();
    println!("10% set {n10}; re-salt keeps {:.3} of it", kept as f64 / n10 as f64);

    // 10 x 10 cross-tab of two salts, chi-square, 99 df (p = 0.001 at 148.2).
    let cross = |sa: &str, sb: &str| {
        let mut t = [0.0f64; 100];
        for u in &ids { t[(bucket(u, sa, 10) * 10 + bucket(u, sb, 10)) as usize] += 1.0; }
        chi2(&t, &[n / 100.0; 100])
    };
    let (ind, same) = (cross("flag-a", "flag-b"), cross("flag-a", "flag-a"));
    assert!(ind < 148.2 && same > 1e5);
    println!("cross-tab chi2: distinct salts {ind:.1}, same salt {same:.0}");

    // Sample-ratio check, 1 df, alarm 10.828; then 3 % of arm A lost.
    let a = ids.iter().filter(|u| bucket(u, "exp-7", 2) == 0).count() as f64;
    let srm = |a: f64, b: f64| chi2(&[a, b], &[(a + b) / 2.0; 2]);
    assert!(srm(a, n - a) < 10.828 && srm(a * 0.97, n - a) > 10.828);
    println!("SRM chi2 {:.2}; with 3% of A lost {:.1}", srm(a, n - a), srm(a * 0.97, n - a));

    // Modulo bias, exact: 8-bit hash % 100; 32-bit hash % 10000.
    let mut c = [0u32; 100];
    (0..256u32).for_each(|h| c[(h % 100) as usize] += 1);
    assert_eq!((c[55], c[56]), (3, 2));
    let (q, r) = ((1u64 << 32) / 10_000, (1u64 << 32) % 10_000);
    println!("32-bit % 10000: {r} buckets get {}, the rest {q}; excess {:.1e}", q + 1, 1.0 / q as f64);

    // Cost per id: whole bucket() (allocates the key) vs the hash alone.
    let keys: Vec<Vec<u8>> = ids.iter().map(|u| format!("flag-a:{u}").into_bytes()).collect();
    let (mut sum, t) = (0u64, Instant::now());
    for u in &ids { sum += bucket(u, "flag-a", 10_000) as u64; }
    let all = t.elapsed().as_nanos() as f64 / n;
    let t = Instant::now();
    for k in &keys { sum += murmur3_32(k, 0) as u64; }
    println!("per id: bucket() {all:.1} ns, murmur3 {:.1} ns ({sum})", t.elapsed().as_nanos() as f64 / n);
}

Complexity and constants

• Time O(key length); state none; 64-bit scaling keeps bias under B/2^32.
• h % B on 32 bits: 2^32 mod B buckets hold one extra value out of floor(2^32/B). For B = 10,000: 7,296 buckets get 429,497 values, the rest 429,496, excess 2.3e-6 (exact). An 8-bit hash into 100 buckets: 3 vs 2 values, 50 % excess. Multiply-shift has the same count bias.

Efficiency

• Cost: per id, measured on this Mac (Apple M4 Pro), 100,000 ids, seven runs: murmur3_32 2.6-6.8 ns on 16-byte keys (noisy), whole bucket() 61-64 ns, mostly the format! allocation. No memory per unit.
• Levers:
  • allocation-free key (reused buffer, integer mix) — 60 to a few ns (measured) — hot path
  • evaluate in the SDK from cached config — no RPC (design) — every flag check
  • u64 ids through a bijective mixer — no string (design) — numeric ids
• Naive → standard → state of the art:
  • stored coin flip per user · a lookup per decision
  • scaled hash(salt:unit) in the SDK · stateless, ns to hash
  • plus versioned hash, shared vectors, ratio alarm · same cost, safe under change

Implementation notes

• Fixed named algorithm and seed: Rust RandomState and Python str hashing are seeded per process.
• Treat the hash as unsigned (Optimizely masks it and tests negative codes).
• Keep a hash_version beside the salt, as GrowthBook does.

Pitfalls

• Changing salt or B mid-test: units change arm.
• A re-created flag with the old name inherits the old cohort.
• < vs <= with 1-based buckets: a 0 % rollout lets one bucket through.

Variants and alternatives

In production

• The four SDKs tabled (feature flags, staged rollout).
• OpenTelemetry: ProbabilitySampler compares 56 bits of trace-id randomness with a threshold.

Implementations

Sources

• GrowthBook, Build your own SDK. docs · code · vectors
• Unleash, Stickiness. docs · code
• LaunchDarkly, Percentage rollouts. docs · code
• Optimizely Java SDK. Bucketer · BucketerTest
• OpenTelemetry, Trace SDK specification. spec