Skip to content
Rust · Project-First

Day 29 · Parallel Execution

Everything so far has been setup for this page. Day 27 gave us a cheap clock; Day 28 gave us transactions whose footprint is declared up front. Today we cash that in: a scheduler that runs thousands of transactions in parallel across cores — Solana’s Sealevel idea — and we’ll watch it tie itself in a perfect knot with the very first rule of this playbook. The borrow checker’s “shared XOR mutable,” which you met as a rule about variables on the very first page, turns out to be the same rule that makes parallel transactions safe — now about accounts.

The conflict rule is “shared XOR mutable” for accounts

Section titled “The conflict rule is “shared XOR mutable” for accounts”

When can two transactions run at the same time? When they can’t interfere. And they can’t interfere exactly when they don’t share a writable account:

Two transactions conflict if they share any account and at least one of them writes it. Read–read on the same account is not a conflict.

Read that again with Day 5 of kvlite in mind. That’s RwLock’s “many readers XOR one writer.” That’s the borrow checker’s “any number of & XOR one &mut.” Same rule, three altitudes: within a function (the compiler), within one shared structure (a lock), and now across a whole batch of transactions (the scheduler). Once you see it’s one idea, the scheduler writes itself:

   pub fn conflicts(a: &Transaction, b: &Transaction) -> bool {
       for ma in &a.accounts {
           for mb in &b.accounts {
               if ma.key == mb.key && (ma.is_writable || mb.is_writable) {
                   return true;          // shared account, at least one writer → conflict
               }
           }
       }
       false
   }

A Transaction carries the declaration the rule needs — which accounts, and whether each is writable:

   pub struct AccountMeta { pub key: Pubkey, pub is_writable: bool }
   pub struct Transaction { pub program: Pubkey, pub accounts: Vec<AccountMeta>, pub data: Vec<u8> }

That is_writable flag is your Anchor #[account(mut)]. You’ve been declaring conflict information every time you wrote a #[derive(Accounts)] struct.

Scheduling: dependency layering into conflict-free batches

Section titled “Scheduling: dependency layering into conflict-free batches”

We want to split the transactions into batches such that within a batch nothing conflicts (so the batch runs in parallel) and conflicting transactions still execute in submission order (so a later writer sees the earlier one’s effects). One clean rule does both — put each transaction in the earliest batch strictly after every earlier transaction it conflicts with:

   batch(i) = 1 + max{ batch(j) : j < i and conflicts(i, j) }      (0 if it conflicts with nothing earlier)
   pub fn schedule(txs: &[Transaction]) -> Vec<Vec<usize>> {
       let mut batch_of = vec![0usize; txs.len()];
       let mut num_batches = 0;
       for i in 0..txs.len() {
           let mut b = 0;
           for j in 0..i {
               if conflicts(&txs[i], &txs[j]) { b = b.max(batch_of[j] + 1); }
           }
           batch_of[i] = b;
           num_batches = num_batches.max(b + 1);
       }
       // group transaction indices by their batch number
       let mut batches = vec![Vec::new(); num_batches];
       for (i, &b) in batch_of.iter().enumerate() { batches[b].push(i); }
       batches
   }

Why this is correct, in one line each: within a batch nothing conflicts — if two transactions in a batch did conflict, the later one would have been bumped to a higher batch; order is preserved — a later writer always lands in a strictly later batch than the writers before it, and batches run sequentially, so it observes their writes. Five transactions writing accounts A B A C B schedule like this:

   batch 0 (parallel):  t0[A]  t1[B]  t3[C]     ← disjoint, run together
   batch 1 (parallel):  t2[A]  t4[B]            ← each waited on an earlier writer of its account

The conflict scan is O(n^2) — fine for teaching, not for a mainnet. Real Solana avoids it with per-account read/write locks: a transaction grabs a read or write lock on each declared account, and the scheduler runs any set of transactions whose locks don’t clash. Same rule, faster bookkeeping.

Executing a batch in parallel — and why it can’t race

Section titled “Executing a batch in parallel — and why it can’t race”

Here’s the part that would be a minefield in C and is boring in Rust. For each batch we clone every transaction’s declared accounts into a private working set, run the transactions in parallel, then commit each one’s writable accounts back — but only if it succeeded:

   for batch in &batches {
       // 1. Gather each tx's accounts into its own owned Vec (a private sandbox).
       let mut work: Vec<Vec<Account>> = batch.iter().map(|&i| self.working_set(&txs[i])).collect();


       let programs = &self.programs;     // &dyn Program is Sync — safe to share, proven by the type system
       let compute  = self.compute_per_tx;


       // 2. PARALLEL: rayon hands each thread a DISJOINT &mut to one tx's working set.
       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 (sequential): conflict-free batch ⇒ each writable key is touched by exactly one tx.
       for (slot, &i) in batch.iter().enumerate() {
           if batch_results[slot].is_ok() {
               self.commit(&txs[i], &work[slot]);   // write back only the writable accounts
           }
       }
   }

Three things are doing quiet, load-bearing work:

  1. work.par_iter_mut() gives out non-overlapping &mut. rayon will only ever hand element k to one thread, as a &mut, never aliased. So each transaction mutates its own Vec<Account> and nothing else — the threads share no mutable data at all. This is the ownership / message-passing model from kvlite’s Day 5, not the lock model: instead of guarding shared state, we hand each worker disjoint state it owns for the duration. No lock to forget, no lock to contend.
  2. The clone-then-commit shape gives free rollback. A transaction mutates a copy; we only write the copy back on Ok. A failed transfer (or a panic-free error) leaves the real state untouched — exactly the atomicity property you’d otherwise have to engineer.
  3. Conflict-freedom makes the commit safe. Because the scheduler guaranteed no two transactions in the batch share a writable account, writing each one’s writable accounts back can’t clobber another’s. The scheduler is what makes the parallel step’s results mergeable.

Under the hood — par_iter_mut is the borrow checker, at the data-parallel level

Section titled “Under the hood — par_iter_mut is the borrow checker, at the data-parallel level”

Why is this safe where “spawn a thread per transaction and let them all poke the account map” would be a data race? Because rayon’s par_iter_mut is an IndexedParallelIterator: it splits a slice into disjoint sub-slices and proves, in the type system, that no two threads receive overlapping &mut. It is the same “shared XOR mutable” guarantee the borrow checker gives you for a single &mut, generalized to “one &mut per element, across many threads.” So the unsafe version doesn’t merely fail at runtime — it won’t compile: try to capture &mut self.accounts into a closure handed to multiple threads and the borrow checker rejects the aliased mutable borrow before any thread exists. The data race that “just parallelize it” invites elsewhere is, here, unrepresentable — and that’s why you can be aggressive about throwing transactions at threads.

   kvlite (Day 5):  many threads → ONE shared map → guard it with Arc<RwLock>   (lock model)
   solmini (today): many threads → DISJOINT owned working sets → no lock needed (ownership model)

Prove it: the integration tests

Section titled “Prove it: the integration tests”

tests/runtime.rs nails down both halves of the promise. Independent work parallelizes:

   // 500 transfers across 1000 distinct accounts → exactly ONE parallel batch.
   let batches = schedule(&txs);
   assert_eq!(batches.len(), 1);
   // …and every payer ends at 7, every payee at 3.

Conflicting work serializes, with no lost updates:

   // 50 increments to ONE counter → 50 single-tx batches (fully serialized), final count == 50.
   let batches = schedule(&txs);
   assert_eq!(batches.len(), 50);
   assert_eq!(state.count, 50);

And the headline guarantee — parallel produces byte-for-byte the same state as the obvious sequential baseline, even on a workload mixing independent and contended transactions:

   seq_rt.run_sequential(&txs);
   par_rt.run_parallel(&txs);
   assert_eq!(seq_rt.accounts, par_rt.accounts);     // determinism: same final world

Run cargo test and they pass. Then run cargo run and watch the demo race 1,200 independent transfers: on a many-core box the parallel path finishes several times faster than sequential — a real speedup, shaped exactly like the lesson.

Honest trade-offs: what the scheduler does and doesn’t buy

Section titled “Honest trade-offs: what the scheduler does and doesn’t buy”

This is a strictly stronger safety story than kvlite’s, and it’s worth being precise about why:

  • Data races: gone, by the compiler. As above — disjoint &mut, unrepresentable to alias.
  • Lost updates: gone, by the scheduler. On Day 5, two threads doing read-modify-write on one key under an RwLock could lose an update (a logic race the lock couldn’t catch). Here, two transactions writing the same account are forced into ordered, separate batches — the second sees the first’s result. The scheduler removes the very race the lock left to you. That’s the upgrade declaring footprints buys.
  • What it doesn’t remove: contention itself. Serializing the hot account is correct, but it’s still serial — throughput on that account is capped (the Amdahl ceiling above). And our toy pays an O(n^2) scan and clones accounts; real Solana locks in place and scans with per-account locks.

The thread

Section titled “The thread”

What does building Sealevel force you to understand? That parallelism isn’t something you add — it’s something you reveal, by making conflicts visible before execution. Declare footprints and the independent work was parallel all along. And what is Rust protecting you from? The scariest thing in this whole project — handing live, mutating transactions to a pool of threads — and it protected you so thoroughly you barely noticed: par_iter_mut’s disjoint &mut made the data race a compile error, and the scheduler’s conflict-free batches made the lost update a non-event. The same “shared XOR mutable” rule you met on page one, enforced now at three levels at once, is the reason a high-throughput parallel runtime can be boring to get right.

→ Next: Day 30 · Capstone & the Anchor Bridge · Prev: Day 28 · The Account Model · Back to the Project 7 overview

Check your understanding

Section titled “Check your understanding”
  1. State the transaction conflict rule. Why is it the same idea as RwLock’s “many readers XOR one writer” and the borrow checker’s & vs &mut?
  2. The scheduler places transaction i in 1 + max{batch(j) : j < i, conflicts(i,j)}. Explain how this single rule guarantees both that a batch is conflict-free and that conflicting transactions keep their order.
  3. The parallel executor clones each transaction’s accounts into a private working set and commits only on success. What two distinct properties does that buy — one about safety across threads, one about a failed transaction?
  4. Why would “spawn one thread per transaction and let them all mutate the shared account map” fail to compile in Rust, and how does par_iter_mut give you the parallelism safely instead?
  5. Fifty transactions all incrementing one counter get zero speedup no matter how many cores you have. Explain why using the conflict rule, and connect it to Amdahl’s law and Solana’s local fee markets.
Show answers
  1. Two transactions conflict if they share an account and at least one writes it (read–read doesn’t conflict). It’s the same rule because all three say “many simultaneous readers are fine, but a writer needs exclusive access” — just applied at different scopes: a single &mut (compiler), one shared structure (RwLock), and a batch of transactions over accounts (scheduler).
  2. Conflict-free: if two transactions in the same batch conflicted, the later one’s formula would have forced it to batch ≥ (earlier's batch) + 1, a strictly higher batch — contradiction, so no two in a batch conflict. Order preserved: a later writer is always pushed to a strictly higher batch than the writers it conflicts with, and batches run sequentially, so it executes after — and sees — their writes.
  3. (a) No data race across threads: each thread mutates its own owned clone, so the threads share no mutable state (ownership model, no lock). (b) Atomic rollback: a failed transaction’s clone is discarded (only committed on Ok), so it leaves the real state untouched.
  4. Capturing &mut self.accounts into closures handed to multiple threads creates aliased mutable borrows, which the borrow checker rejects — it won’t compile. par_iter_mut instead splits a slice into disjoint sub-slices and proves (via IndexedParallelIterator) that no two threads get overlapping &mut, so each works on non-overlapping data and there’s nothing to race.
  5. Every increment writes the same counter account, so each conflicts with all earlier ones — the scheduler puts each in its own batch (fully serialized), giving serial fraction s = 1. By Amdahl’s law speedup → 1/s = 1, so cores don’t help. Because contention is per writable account, Solana’s fix is per-account: local fee markets / priority fees localize the bidding for a hot account’s limited serial throughput instead of congesting the whole chain.