Summary

Spike to investigate and document the limitations of predictable replay (PR) in test/format, and to provide direction on how we might work around them. The output is a findings document, not an implementation.

Background

Predictable replay derives every operation purely from (timestamp, run_seed): the timestamp is XOR'd with the run seed to seed a per-operation RNG, which decides the table, op type, key and value. Reproducing a run needs only the seeds — no operation log. To stay deterministic under concurrency, PR uses lanes: the low bits of the timestamp pick a lane and the key's low bits are overwritten with the lane number, guaranteeing one in-flight op per key. On rollback, a thread retries the same timestamp rather than advancing.

This is elegant but rigid: every timestamp must produce exactly its deterministic op, and that op must fit a single lane / single key. The most notable costs are that truncate is disabled (it spans many keys = many lanes) and that two threads never contend on the same key.

Goals

1. Enumerate the limitations of predictable replay and explain why each exists, grounded in the lane model, seed determinism, and same-timestamp retry.
2. Identify which limitations are rigid and hard to remove (baked into the seed/lane design) versus those that are workable with reasonable effort.
3. Provide direction on how the workable limitations could be relaxed, and flag what would need prototyping or further design.

Deliverable

A findings doc that (1) documents the limitations of predictable replay and why they exist, and (2) outlines candidate directions for relaxing them. Specific approaches under discussion are captured in the comments.