Fractional indexing

Deep dive

How it works

In: neighbour keys a and b (either may be None for the list's start or end) · Out: a key k with a < k < b byte-wise · State: none beyond the keys stored in the rows; a replica id for the concurrent variant · Cost: O(length of a and b), usually 1-3 digits

A key is the digit string of a fraction in (0, 1) with the leading 0. omitted, over a sorted alphabet (base 62: 0-9A-Za-z, base 95: printable ASCII). Keys never end in 0, so every fraction has exactly one spelling.

1. Insert between a and b: strip the common prefix, then compare the first differing digits da < db.
2. If db - da > 1, return the single digit halfway; done.
3. If the digits are consecutive and b has more digits, return b's first digit (a prefix of b is smaller than b, larger than a).
4. Otherwise keep da and recurse on the rest of a against 1.0.
5. At the list end (b = None) bump the last digit of a; at the start (a = None) decrement the last digit of b.
6. Store the key on that one row; the list is ORDER BY key.

Floats fail because an f64 has a 52-bit mantissa: 0.5 and 1.0 can be bisected only 52 times before the midpoint equals a neighbour (computed, asserted in the test).

Integer part. David Greenspan's scheme, implemented by Rocicorp's fractional-indexing package, prefixes each key with a length-marked integer head: a0 is the first key, then a1, a2 ... az, then b00; Zz sorts before a0. Appends and prepends then grow keys only when the head's range overflows: 10,000 appends with v4.0.0 end at c1aH, 4 characters (measured), instead of one bit per insert. Inserting 10,000 times into one gap still reaches 1,669 characters with that package (measured): the integer part helps the ends, not a hot gap. The code below omits it, so its repeated appends grow linearly (small slope, see Efficiency).

Concurrency. Two clients inserting between the same a and b compute the same key. Figma's server assigns a fresh position to the second insert. Without a server, append a fixed-width replica id or random jitter (key_between_unique). Runs of inserts from two clients in one gap can still interleave (Figma lists this as a drawback; Kleppmann et al. study the same effect in text editors).

Code

const D: &[u8] = b"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const B: usize = 62;

fn val(c: u8) -> usize { D.iter().position(|&x| x == c).expect("not a base-62 digit") }

/// Midpoint of fractions 0.a and 0.b (digit strings, no trailing '0'); b = None means 1.0.
/// Requires a < b.
fn midpoint(a: &[u8], b: Option<&[u8]>) -> Vec<u8> {
    if let Some(b) = b {
        // strip the common prefix (a is padded with '0' digits)
        let n = (0..).take_while(|&i| *a.get(i).unwrap_or(&b'0') == b[i]).count();
        if n > 0 {
            let mut k = b[..n].to_vec();
            k.extend(midpoint(a.get(n..).unwrap_or(&[]), Some(&b[n..])));
            return k;
        }
    }
    let da = a.first().map_or(0, |&c| val(c));
    let db = b.map_or(B, |b| val(b[0]));
    if db - da > 1 {
        return vec![D[(da + db + 1) / 2]]; // a digit strictly between
    }
    match b {
        Some(b) if b.len() > 1 => b[..1].to_vec(), // proper prefix of b: below b, above a
        _ => { // consecutive digits: keep da, go one digit deeper below the 1.0 bound
            let mut k = vec![D[da]];
            k.extend(midpoint(a.get(1..).unwrap_or(&[]), None));
            k
        }
    }
}

/// A key k with a < k < b (byte-wise). None = -inf / +inf. Panics unless a < b.
pub fn key_between(a: Option<&str>, b: Option<&str>) -> String {
    if let (Some(a), Some(b)) = (a, b) { assert!(a < b, "need a < b"); }
    let k = match (a, b) {
        (None, None) => vec![D[B / 2]],
        (Some(a), None) => { // append: bump the last digit, else extend
            let (last, head) = a.as_bytes().split_last().unwrap();
            let mut k = head.to_vec();
            if val(*last) + 1 < B { k.push(D[val(*last) + 1]); } else { k.push(*last); k.push(D[B / 2]); }
            k
        }
        (None, Some(b)) => { // prepend: decrement the last digit, never ending in '0'
            let (last, head) = b.as_bytes().split_last().unwrap();
            let mut k = head.to_vec();
            if val(*last) > 1 { k.push(D[val(*last) - 1]); } else { k.extend([b'0', D[B / 2]]); }
            k
        }
        (Some(a), Some(b)) => midpoint(a.as_bytes(), Some(b.as_bytes())),
    };
    String::from_utf8(k).unwrap()
}

/// Concurrent-safe variant: append a fixed-width replica suffix (last digit != '0') so two
/// replicas inserting into the same gap get different keys. The suffix must not push the key past b.
pub fn key_between_unique(a: Option<&str>, b: Option<&str>, replica: &str) -> String {
    assert!(!replica.ends_with('0'));
    let mut m = key_between(a, b);
    loop {
        let k = format!("{m}{replica}");
        if b.map_or(true, |b| k.as_str() < b) { return k; }
        m = key_between(Some(&m), b); // m was a prefix of b: move closer to b
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn sorted_under_random_inserts_and_replicas() {
        let (mut v, mut s) = (Vec::<String>::new(), 88172645463325252u64);
        for _ in 0..10_000 {
            s ^= s << 13; s ^= s >> 7; s ^= s << 17;
            let i = (s >> 11) as usize % (v.len() + 1);
            let k = key_between(i.checked_sub(1).map(|j| v[j].as_str()), v.get(i).map(|x| x.as_str()));
            v.insert(i, k);
        }
        assert!(v.windows(2).all(|w| w[0] < w[1]));
        let (k1, k2) = (key_between_unique(Some("V"), Some("V5"), "r1x"), key_between_unique(Some("V"), Some("V5"), "r2y"));
        assert!(k1 != k2 && "V" < &k1[..] && &k1[..] < "V5" && "V" < &k2[..] && &k2[..] < "V5");
        // f64 midpoints between 0.5 and 1.0 run out after 52 steps
        let (lo, mut hi, mut n) = (0.5f64, 1.0f64, 0);
        while (lo + hi) / 2.0 > lo && (lo + hi) / 2.0 < hi { hi = (lo + hi) / 2.0; n += 1; }
        assert_eq!(n, 52);
    }
}

Compiled and run with cargo test --release (stable Rust, std only).

Complexity and constants

key_between walks the shared prefix once: O(len). Cost drivers: one String allocation per key and, in the store, the key bytes in the row and in the index. Comparison is memcmp, with no locale: sort by raw bytes (COLLATE "C" in PostgreSQL, BINARY in SQLite), or case-folding collations break the order.

Efficiency

• Cost: on an Apple M4 Pro, release build, 1,000-key list: 81 ns per key_between (1M calls, dominated by the allocation). Bound: the row write, not the computation.
• Levers:
  • base 62 or 95 instead of 10 — 5.95 or 6.57 bits per character instead of 3.3 (computed: log2 of the base; Figma uses base 95) — always.
  • integer-part prefix for appends and prepends — O(log n) head growth instead of one bit or more per insert — when users mostly add at the ends.
  • background re-key when a key passes a length limit (e.g. 64 characters): one batch update renumbers the list evenly — adversarial same-gap patterns.
  • index the key column with binary collation — one B-tree range scan per list (B+tree) — large tables.
• Naive → standard → state of the art:
  • integer positions, renumber the tail · O(n) rows written per move.
  • f64 midpoint · O(1) row, fails after 52 same-gap inserts.
  • base-62 strings, integer head, replica suffix, background re-key · O(1) row, short keys.

Measured here (10,000 inserts, no integer part): random positions: average key 3.5 characters, maximum 6. Always at the front or back: average 162, maximum 323. Always into the same gap: average 835, maximum 1,668.

Implementation notes

• Keep the key column NOT NULL with a unique (list_id, key) index; a unique violation tells you to retry with a new key.
• Re-key in one transaction and tell clients the generation changed, so offline clients rebase their queued moves (offline mutation queue).

Pitfalls

• Sorting with locale-aware comparison (localeCompare, default collations): the order silently changes.
• Same key for concurrent inserts: either a unique index error or a nondeterministic tie. Break ties by (key, replica_id).
• No bound on length: one hot gap can reach thousands of characters; cap and re-key.

Variants and alternatives

In production

• Figma uses fractional indexing for the order of children in multiplayer documents.
• The rocicorp package is a port of David Greenspan's algorithm; its README lists byte-compatible ports for Go, Python, Kotlin and Ruby, and a jittered extension against concurrent collisions.

Implementations

Sources

• Evan Wallace, Realtime Editing of Ordered Sequences, Figma blog 2017. post
• David Greenspan, Implementing Fractional Indexing, Observable. notebook · code
• Martin Kleppmann, Victor B. F. Gomes, Dominic P. Mulligan, Alastair R. Beresford, Interleaving anomalies in collaborative text editors, PaPoC 2019. paper
• Evan Wallace, CRDT: Fractional Indexing, notes on random jitter. notes