Deterministic and partition-serial execution

What disappears when execution follows an agreed input order, and when does a single thread per partition win?

Remove the nondeterminism

Every scheme so far pays because the outcome of concurrent execution is nondeterministic: it depends on timing. So the outcome must be communicated to replicas, to participants and to the log. Determinism attacks that premise directly. If execution is a pure function of an agreed input order, then any node that has the same input produces the same output, and nothing needs to be communicated except the input.

Three things follow at once:

1. Replication becomes shipping the input log instead of the write set.
2. Replicas never need to agree on an outcome, only on an order.
3. Distributed transactions no longer need a commit vote, because no participant can abort for a reason the others do not already know. This is the central claim of Calvin, a deterministic database design: agreeing on order up front removes the need for 2PC instead of optimizing it.

The costs are steep and specific

• You must know the read and write set before execution. This rules out data-dependent access ("read X, then read the row that X points to"). The standard escape is a reconnaissance query that finds the set, then executes and validates that the set did not change, retrying if it did. That is OCC, brought back one level up: the cost was relocated, not removed.
• You need a global sequencer (the component that decides the order). It is a serialization point that bounds throughput, and since it works in batches it bounds latency at the epoch length.
• Interactive transactions are gone. Everything must be a one-shot stored procedure (code that runs entirely inside the database).

Single-threaded per partition: the sharpest inversion

This is the same idea pushed to its limit, and its derivation is the sharpest inversion here. Recall the argument of Why concurrency is different: concurrency is forced by Little's Law, because L = λW and W is large. But why is W large? Because transactions wait, for disk and for the network.

Now make the working set fit in memory. W becomes pure CPU, perhaps 50 µs. A single core running transactions one after another then delivers 1 / 50 µs = 20,000 transactions per second on that partition, and L = 1.

H-Store and VoltDB, Redis, Kafka's per-partition ordering, the LMAX Disruptor's single-writer principle, and shard-per-core engines like Seastar and ScyllaDB all converged on this design. Independent convergence is evidence of a deep constraint, not of fashion.

The boundary condition

The limit is severe, and worth stating precisely.

• A cross-partition transaction stalls the single thread for the whole coordination round trip. Throughput is therefore not a smooth function of the fraction of multi-partition transactions. It is a cliff.
• And the moment the working set exceeds memory, W includes I/O again and the whole argument reverses.

Partition-serial designs are excellent for workloads whose partition key matches their transaction boundary, and catastrophic for workloads where it does not. The choice of concurrency control has been converted into a data-modelling choice.

Partitioning buys parallelism by declaring that cross-partition order does not matter. When that declaration is false, you pay all of it back at once.

Concurrency exists because transactions wait; eliminate the waiting and the whole control problem evaporates, until one transaction crosses two partitions.