Executing a Batch in Parallel

The previous page, Scheduling Into Conflict-Free Batches, did the hard thinking: it took a stream of transactions, read each one’s declared footprint, applied the conflict rule, and layered them into batches where nothing inside a batch conflicts. That is a promise about the shape of the work. This page cashes it in.

We now have a batch — a list of transactions that provably do not fight over any writable account — and a machine with a dozen cores sitting idle. The job is to run them all at once and end up with exactly the state we would have reached running them one at a time. The remarkable part is how little code that takes, and how much of the correctness is carried by the type system rather than by us being careful. Handing live transactions to a thread pool should be terrifying. This page is about why, here, it is boring.

The three-step shape

Every batch runs through the same three moves. Gather, run, commit.

   ┌─────────────────────────────────────────────────────────────┐
   │  batch = [ t0(A,B)   t1(C)   t3(D,E) ]   ← conflict-free     │
   └─────────────────────────────────────────────────────────────┘

   1. GATHER  (sequential reads of the DB)
        clone each tx's declared accounts into a private Vec<Account>
        work = [ [A,B]      [C]      [D,E] ]     ← disjoint owned copies

   2. RUN     (parallel: rayon hands each thread a disjoint &mut)
        thread ─► t0 mutates its [A,B]
        thread ─► t1 mutates its [C]        ← all at the same time
        thread ─► t3 mutates its [D,E]

   3. COMMIT  (sequential, on Ok only)
        for each tx that returned Ok: write its *writable* accounts back
        A,B ◄─ t0    C ◄─ t1    D,E ◄─ t3
        a tx that returned Err: its clone is discarded — nothing written

In the book’s companion crate solmini, this is the whole of run_parallel — around a dozen lines. Read it top to bottom; every line maps to one of the three steps.

pub fn run_parallel(&mut self, txs: &[Transaction]) -> Vec<Result<()>> {
    let batches = schedule(txs);
    let mut results: Vec<Result<()>> = (0..txs.len()).map(|_| Ok(())).collect();

    for batch in &batches {
        // 1. GATHER: pull each tx's declared accounts out of the DB as a
        //    private, owned working set (sequential reads).
        let mut work: Vec<Vec<Account>> =
            batch.iter().map(|&i| self.working_set(&txs[i])).collect();

        let programs = &self.programs;
        let compute = self.compute_per_tx;

        // 2. RUN: rayon hands out a disjoint `&mut Vec<Account>` per element,
        //    and the batch is conflict-free, so no two threads can ever reach
        //    the same writable account.
        let batch_results: Vec<Result<()>> = batch
            .par_iter()
            .zip(work.par_iter_mut())
            .map(|(&i, accts)| Self::run_tx(programs, compute, &txs[i], accts))
            .collect();

        // 3. COMMIT: each writable key in a conflict-free batch is touched by
        //    exactly one tx, so write-back never clobbers. Failures are dropped.
        for (slot, &i) in batch.iter().enumerate() {
            if batch_results[slot].is_ok() {
                self.commit(&txs[i], &work[slot]);
            }
        }
        for (slot, r) in batch_results.into_iter().enumerate() {
            results[batch[slot]] = r;
        }
    }
    results
}

Three quiet properties hold this together, and each earns a section: disjoint mutable borrows make the parallel step a compile-time guarantee, clone-then-commit gives free rollback, and conflict-freedom makes the write-back safe. Get those three and the thread pool is an implementation detail.

Step 1 — Gather: a private working set per transaction

Before any thread runs, we copy. For each transaction, working_set walks its declared account list and pulls a clone of every account out of the shared database:

/// Pull a transaction's declared accounts out of the DB as an owned working
/// set (missing accounts default to an empty account). This clone is the
/// transaction's private sandbox: it can mutate freely, and only its writable
/// accounts are written back — on success.
fn working_set(&self, tx: &Transaction) -> Vec<Account> {
    tx.accounts
        .iter()
        .map(|m| self.accounts.get(&m.key).cloned().unwrap_or_default())
        .collect()
}

The key word is cloned. The transaction never touches the live database while it executes. It gets a sandbox — an owned Vec<Account> it fully controls. This is a deliberate choice with two payoffs that land later: nothing a running transaction does is visible to anyone until we choose to commit it, and a transaction that fails leaves the database untouched simply because we drop its sandbox on the floor.

Gathering is done sequentially, one HashMap read at a time, because reading the database is cheap next to running a program. The expensive work — signature verification, deserialization, the program logic itself — happens in step 2, where the parallelism pays off.

Step 2 — Run: the data race is a compile error

This is the line that would be a minefield in C, and is a non-event in Rust:

let batch_results: Vec<Result<()>> = batch
    .par_iter()
    .zip(work.par_iter_mut())
    .map(|(&i, accts)| Self::run_tx(programs, compute, &txs[i], accts))
    .collect();

work.par_iter_mut() is rayon’s parallel mutable iterator. Its guarantee is precise and it is exactly the guarantee we need: it hands each closure invocation a disjoint &mut Vec<Account> — element 0 to one thread, element 1 to another — and the borrow checker knows those &muts cannot alias. That is IndexedParallelIterator: a parallel iterator that can address its elements by index and therefore split them into non-overlapping mutable slices. No two threads can ever hold a mutable reference into the same working set, because there is no such shared reference to hand out.

So the classic recipe for a data race — two threads writing the same memory with no synchronization — is not something we defend against at runtime. It is unrepresentable. If you tried to write a version that shared a working set across threads, it would not compile: the closure would need to capture a &mut twice, and Send/Sync and the borrow checker would reject it. The race is a type error, caught before the program runs, not a Heisenbug caught in production at 3 a.m.

Notice what run_tx does not take:

fn run_tx(
    programs: &HashMap<Pubkey, Box<dyn Program>>,
    compute_per_tx: u64,
    tx: &Transaction,
    accounts: &mut [Account],
) -> Result<()> { /* ... */ }

It is an associated function — no &self. A worker thread must not borrow the whole Runtime, because that would mean every thread sharing one &Runtime while another part of the code wants &mut self. Instead each thread gets only what it truly shares (&programs, which is read-only and Send + Sync) plus its own private &mut [Account]. The API shape is the safety argument: shared things are shared by immutable reference, owned things are owned outright, and nothing mutable is shared.

Under the hood — why disjoint ownership beats a shared lock

It is worth naming what we did not do, because the earlier kvlite project in the Rust playbook did the opposite, and both are correct.

kvlite is a key–value store built for concurrency the mainstream way: a single shared map behind a lock (an Arc<RwLock<HashMap<..>>> or a sharded set of them). Every worker holds a reference to the same map. Safety comes from coordination at runtime: before you touch a key you acquire the lock, you do your work, you release it. Threads take turns. The map is shared; the discipline that keeps it correct is the lock protocol, enforced dynamically.

Sealevel’s runtime here is the message-passing / ownership model instead. There is no shared mutable map during execution and therefore no lock to acquire. Each transaction owns a disjoint slice of state outright, mutates it alone, and the results are merged back afterward. Safety comes from the structure of the data, enforced statically:

   kvlite (shared-lock)                  Sealevel runtime (disjoint ownership)
   ────────────────────                  ────────────────────────────────────
   one shared HashMap                    N private Vec<Account>, one per tx
   Arc<RwLock<..>> around it             no lock — nothing is shared
   threads contend for the lock          threads never meet
   correctness = lock protocol           correctness = "shared XOR mutable" on
     (checked at runtime)                  accounts (checked at compile time)
   scales until lock contention          scales until two txs want one account

Neither is universally better. A lock lets any two operations touch any keys and sorts out safety on the fly — flexible, but the lock itself becomes the bottleneck under contention, which is the whole lesson of Why the EVM Runs Serially. Disjoint ownership needs the footprint known up front so the scheduler can partition state cleanly, but once it has that, threads literally never synchronize on shared data during the hot path. Solana paid for that with the account- declaration rule; this page is where the bill turns into speedup.

Step 3 — Commit: mergeable write-back, and free rollback

After the parallel run, every transaction has a finished working set and a Result. Now we fold the successful ones back into the database:

fn commit(&mut self, tx: &Transaction, working: &[Account]) {
    for (meta, acct) in tx.accounts.iter().zip(working) {
        if meta.is_writable {
            self.accounts.insert(meta.key, acct.clone());
        }
    }
}

Two properties make this the easy part.

Free atomic rollback. A transaction either committed all of its writable accounts or none of them. The mutations lived only in the private clone; if the program returned Err, we simply never call commit, and the clone is dropped when the loop moves on. There is no undo log, no reverting of partial writes, no compensating transaction — the rollback is the absence of a commit. An overdrawn transfer, a failed counter increment, a program that panicked its way to an error: all of them leave the database byte-for-byte as it was. Atomicity is a property of the architecture, not a feature we coded.

Mergeable commits. We commit sequentially, and the commits cannot clobber each other, because of the one property the scheduler guaranteed: within a conflict-free batch, each writable key is touched by exactly one transaction. If two transactions in this batch both wrote account A, that would be a conflict, and the scheduler would have put the later one in a different batch. So when we write t0’s copy of A back and then t1’s accounts back, there is no account they both wrote — t1 never had A as writable. The write-backs commute; their order does not matter; nothing overwrites anything. That is why the commit loop can be a plain sequential for with no coordination at all.

Note the asymmetry: a batch can have two transactions that both read the same account (read–read is not a conflict), and both of their clones will contain a copy of it — but neither writes it, so commit skips it in both. Only writable accounts flow back, and each writable key has a single author.

By the numbers — where the parallelism actually helps

The gather and commit steps are sequential; only the run step goes parallel. So the speedup follows Amdahl’s law, applied to a batch:

   Suppose a batch of N transactions where the run step dominates
   (real per-tx cost: signature verification + program execution),
   and gather+commit are a small fixed fraction f of total work.

   sequential time  ≈  N · run
   parallel time    ≈  N · f · overhead   +   (N · run) / cores

   With N = 64 independent txs, run ≫ gather+commit, and 8 cores:
     sequential  ≈ 64 · run
     parallel    ≈ 8  · run   +   small
     speedup     ≈ ~8×  (bounded by cores, not by N)

The ceiling is the number of cores — and, crucially, the width of the batch. A batch of one transaction gets no speedup at all: one hot account serializes everything, which is the subject of the next page, The Hot-Account Ceiling. The companion crate’s demo binary exposes a compute_per_tx knob precisely so you can dial the per-transaction work up and watch the wall-clock gap between run_sequential and run_parallel open.

The headline guarantee

The whole design earns exactly one promise, and it is the promise that makes it trustworthy:

run_parallel produces byte-for-byte the same state as run_sequential.

The sequential runner is the obviously-correct baseline — run transactions in submission order, one at a time, commit each on success. The parallel runner reorders execution across cores. If those two ever disagreed on the final database, the parallelism would be a lie. They do not, and the reason is the chain of guarantees this part built: the scheduler keeps conflicting transactions in submission order across batches (so a later writer still sees an earlier writer’s effect), and within a batch nothing conflicts (so intra-batch order is irrelevant). Determinism is not a nice-to-have here — a blockchain where two validators replaying the same block reach different states cannot reach consensus at all. The companion crate pins this down with an integration test that runs the same transaction set both ways and asserts the resulting accounts maps are equal.

The architect’s lens

• Why does it exist? Because scheduling a conflict-free batch is worthless if executing it is unsafe or slow. This step turns the scheduler’s promise into actual multi-core throughput — the payoff for declaring footprints in the first place.
• What problem does it solve? Running many live transactions on a thread pool without data races, without a shared lock, and without giving up deterministic replay — the three things that usually make “just parallelize it” a trap.
• What are the trade-offs? You pay a clone per transaction (memory and copy cost) and two sequential phases (gather, commit) around the parallel one. In return the parallel phase needs zero synchronization, and rollback and atomicity come for free.
• When should I avoid it? When the workload has no width — if almost every transaction touches one hot account, batches collapse to size one and you get sequential execution plus clone overhead. That is the hot-account ceiling, and it is a real limit.
• What breaks if I remove it? Remove the private clones and threads write the shared database directly: you reintroduce data races and lose free rollback. Remove the conflict-free precondition and the commit loop starts clobbering. Each of the three properties is load-bearing.

Check your understanding

1. Why does each transaction execute against a clone of its accounts instead of the live database? Name the two properties this buys.
2. work.par_iter_mut() is what makes step 2 safe. What exactly does it guarantee, and why does that turn a potential data race into a compile-time error?
3. The commit loop is a plain sequential for with no locking, yet two commits never clobber each other. Which earlier guarantee makes that true, and what would go wrong without it?
4. A transaction returns Err. Describe precisely what happens to its writes — and explain why this gives atomic rollback with no undo log.
5. Contrast this runtime’s safety model with kvlite’s shared-lock model. Where does each check correctness — runtime or compile time — and what does each need from the workload to scale?

Show answers

1. The transaction gets a private, owned working set, so (a) its mutations are invisible to everyone until commit — nothing races on the live DB during execution — and (b) a failure is undone for free by simply dropping the clone. Isolation and free rollback.
2. par_iter_mut (an IndexedParallelIterator) hands each closure a disjoint &mut into a distinct element — no two threads can hold a mutable reference to the same working set. There is no shared mutable reference to alias, so a data race isn’t defended against at runtime; it is unrepresentable, rejected by the borrow checker before the program runs.
3. Conflict-freedom: within a batch, each writable key is touched by exactly one transaction (any second writer would have been pushed to a later batch). So the write-backs never overlap and commute. Without it, two transactions could both write account A, and the second commit would silently clobber the first — a lost update.
4. We never call commit for a failed transaction, and its clone is dropped as the loop advances. None of its writes ever reach the database, so the DB is byte-for-byte unchanged. Because all its mutations lived only in the clone, “commit all or commit nothing” is automatic — atomicity without an undo log.
5. kvlite shares one HashMap behind an Arc<RwLock<..>> and enforces safety at runtime via the lock protocol; it scales until lock contention. This runtime gives each transaction a disjoint owned slice of state and enforces “shared XOR mutable” on accounts at compile time; it needs the footprint declared up front so the scheduler can partition state, and scales until two transactions want the same writable account.