The Account-Locks Scheduler: Running Non-Conflicting Transactions in Parallel

The previous page moved state out of the code and into named external accounts owned by stateless programs. That move looked like a modelling choice about where data lives. This page cashes it in for the thing the whole part is after: speed. Because state lives in named accounts, a transaction can list them up front — and a list of accounts is exactly the input a scheduler needs to decide which transactions may run at the same time.

This is the page where the throughline stops being a slogan. How do you build one global state machine that runs at hardware speed without falling apart? Falling apart, concretely, is two transactions writing the same account on two cores at once. So we build the piece that prevents it: a scheduler that reads every transaction’s declared footprint, works out which transactions conflict, and partitions them into batches where nothing conflicts — batches you can hand to as many cores as you have without a single lock. We will build AccountMeta, Transaction, the conflicts rule, and schedule, and prove their behaviour with tests. We do not run anything yet; execution is the next page. This page is purely about deciding who is allowed to run together.

The footprint must be explicit

A transaction cannot ask the scheduler “is it safe to run me next to that one?” unless it can state, before running, which accounts it touches and how. So the first type we build makes the access mode of every account reference explicit.

/// One account reference inside a transaction, with its access mode declared.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct AccountMeta {
    pub key: Pubkey,
    pub is_writable: bool,
}

impl AccountMeta {
    pub fn writable(key: Pubkey) -> Self {
        AccountMeta { key, is_writable: true }
    }
    pub fn readonly(key: Pubkey) -> Self {
        AccountMeta { key, is_writable: false }
    }
}

That single is_writable flag is the entire hinge of Solana’s throughput story. It is the difference between “I only need to look at this account” and “I need it to myself.” A Transaction is then just the program to invoke, the ordered list of AccountMetas it touches, and an opaque data payload the program interprets:

#[derive(Clone, Debug)]
pub struct Transaction {
    pub program: Pubkey,
    pub accounts: Vec<AccountMeta>,
    pub data: Vec<u8>,
}

The accounts vector is the declaration the scheduler trusts. A transfer, for example, declares both endpoints as writable, because both balances change:

impl Transaction {
    /// A transfer of `amount` lamports from `from` to `to`. Both endpoints are
    /// writable (both balances change), so two transfers sharing an endpoint
    /// conflict and will be serialized.
    pub fn transfer(from: Pubkey, to: Pubkey, amount: u64) -> Self {
        Transaction::new(
            TransferProgram::id(),
            vec![AccountMeta::writable(from), AccountMeta::writable(to)],
            amount.to_le_bytes().to_vec(),
        )
    }

    /// Increment `counter` by `step`.
    pub fn increment(counter: Pubkey, step: u64) -> Self {
        Transaction::new(
            CounterProgram::id(),
            vec![AccountMeta::writable(counter)],
            step.to_le_bytes().to_vec(),
        )
    }
}

Notice what has happened. Before a single line of program logic runs, the runtime already knows the complete read/write footprint of every transaction, just by reading its accounts list. That is the whole premise. Real Solana enforces that the declaration is honest — a program that touches an undeclared account fails — and demands that read-only accounts really are unwritten. We simply trust the declaration here, because a program only ever receives the accounts it named.

Under the hood — why the ordering of accounts matters

The accounts vector is ordered on purpose: a program receives its accounts as a slice and indexes into it by position (accounts[0] is the source, accounts[1] the destination, and so on). So AccountMeta carries two pieces of information at once — the identity of an account (for the scheduler) and its role in the instruction (for the program). The scheduler only cares about key and is_writable; the program only cares about position. One list, two readers. Keeping them in one place is why a transaction’s footprint and its calling convention can never drift apart.

The conflict rule: shared XOR mutable, at the account level

Now the core decision. Given two transactions, may they run at the same time? They may — unless they would race. Two threads race when they touch the same memory and at least one writes it; simultaneous reads of unchanged data are always safe. Lift that from memory to accounts and you have the rule verbatim:

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

This is Rust’s own “shared XOR mutable” — the borrow checker’s rule for references — promoted from variables to accounts. Any number of transactions may hold a shared (read-only) view of an account at once; a mutable (writable) view must be exclusive. The scheduler is a borrow checker whose “variables” are accounts and whose “scope” is a batch.

/// Do two transactions conflict? They do when they share any account and at least
/// one of them writes it (read–read on the same account is *not* a conflict).
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;
            }
        }
    }
    false
}

The predicate is same key && (writer_a || writer_b). Walk the four cases for a shared account and the rule falls out:

   tx A on X   tx B on X    conflict?   why
   ─────────   ─────────    ─────────   ───────────────────────────────
   read        read         no          both only observe X; safe together
   read        write        YES         A could read X mid-mutation by B
   write       read         YES         symmetric to the above
   write       write        YES         two writers to X — the classic race

The read–read exemption is not a nicety; it is where the parallelism comes from. A hot read-only account — a price oracle, a config account, a program’s own data everyone consults — can be shared by every transaction in a block without forcing a single one of them to wait. If read-read counted as a conflict, any popular account would serialize the whole chain, and the account model’s promise would collapse.

By the numbers — how much parallelism the rule unlocks

The exemption is the difference between a chain that scales with cores and one that does not.

   Scenario: 10,000 transactions in a block, all touch account C.

   If C is WRITABLE for each tx:
       every pair conflicts → 10,000 serial batches → ~1 tx per "core-slot"
       effective parallelism ≈ 1×   (a hot writable account is a global lock)

   If C is READ-ONLY for each tx (and their other accounts are disjoint):
       no pair conflicts → 1 batch → all 10,000 run together
       effective parallelism ≈ min(10,000, cores)   (bounded only by hardware)

Same 10,000 transactions, same account. A single is_writable bit is the difference between a serial chain and a fully parallel one. This is exactly why Solana programs are written to mark accounts read-only wherever a write is not truly needed.

Scheduling by dependency layering

The conflict rule tells us whether two transactions may share a batch. Scheduling is the whole-block version: partition all n transactions into an ordered list of batches such that (1) within any batch, no two transactions conflict — so the batch is safe to run in parallel — and (2) conflicting transactions keep their submission order, so the later one sees the earlier one’s effects. Both properties fall out of one assignment rule:

   batch(i) = 1 + max{ batch(j) : j < i  and  conflicts(i, j) }     (0 if none)

Read it in English: place transaction i in the batch one after the latest batch of any earlier transaction it conflicts with. If nothing earlier conflicts, it goes in batch 0. This is topological layering of the conflict graph, restricted to edges that point backwards in submission order.

   txs (submission order):  t0   t1   t2   t3   t4
   accounts they write:      A    B    A    C    B

   t0: no earlier conflict            → batch 0
   t1: no earlier conflict            → batch 0
   t2: conflicts t0 (both write A)    → 1 + batch(t0) = 1
   t3: no earlier conflict            → batch 0
   t4: conflicts t1 (both write B)    → 1 + batch(t1) = 1

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

Why does this simultaneously guarantee both properties?

• Within a batch, nothing conflicts. Suppose two conflicting transactions i > j landed in the same batch. Then conflicts(i, j) is true, so by the rule batch(i) >= batch(j) + 1 > batch(j) — a contradiction. The later one was forced one layer up. So same-batch implies conflict-free, which is precisely the invariant that makes parallel execution safe.
• Conflicting transactions keep submission order. If i conflicts with an earlier j, then batch(i) > batch(j) strictly, so i runs in a strictly later batch and observes j’s committed writes. The chain of writers to a hot account is stretched across successive batches, in order — never reordered, never overlapped.

Here is the implementation. It is a plain double loop: for each transaction, scan the earlier ones, and take the max conflicting batch plus one.

/// Partition transactions into conflict-free batches by dependency layering.
/// Returns a list of batches, each a list of transaction indices, ready to run
/// batch by batch, in parallel.
pub fn schedule(txs: &[Transaction]) -> Vec<Vec<usize>> {
    let mut batch_of = vec![0usize; txs.len()];
    let mut num_batches = 0usize;
    for i in 0..txs.len() {
        let mut b = 0usize;
        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);
    }
    let mut batches = vec![Vec::new(); num_batches];
    for (i, &b) in batch_of.iter().enumerate() {
        batches[b].push(i);
    }
    batches
}

The output is a Vec<Vec<usize>>: an ordered list of batches, each holding the indices of transactions that may run together. The next page feeds these batches to rayon — one batch at a time, all transactions in a batch at once — and because a batch is conflict-free, no two threads can ever reach the same writable account. The type system then proves the absence of a data race for free.

Under the hood — layering is a scan, not a sort

It is tempting to picture scheduling as “sort transactions by dependency.” It is not a sort — the submission order is fixed and must be preserved; we never reorder. Layering only decides how far down each transaction falls, never before which of its peers. A transaction with no earlier conflict always reaches batch 0 no matter how late it was submitted (that is why t3 sits in batch 0 above, next to t0). The block’s order is sacred; layering just discovers how much of it can collapse onto the same wall-clock instant.

Proving the behaviour with tests

A scheduler you cannot inspect is a scheduler you cannot trust. Three tests pin down the three behaviours that matter, and each maps to one claim we made above.

Independent transfers land in one batch. Six transfers across twelve distinct accounts share nothing, so no pair conflicts and all six collapse into a single parallel batch — the best case, full width.

#[test]
fn independent_transfers_land_in_one_batch() {
    let txs: Vec<Transaction> = (0..6)
        .map(|i| {
            Transaction::transfer(
                Pubkey::from_seed(&format!("from{i}")),
                Pubkey::from_seed(&format!("to{i}")),
                1,
            )
        })
        .collect();
    let batches = schedule(&txs);
    assert_eq!(batches.len(), 1);
    assert_eq!(batches[0].len(), 6);
}

Transfers draining a hot account serialize. Four transfers all drain the same hot account. Because every transfer marks hot writable, each conflicts with all earlier ones, and layering stretches them into four separate single-transaction batches — the worst case, no width at all.

#[test]
fn transfers_sharing_an_account_are_serialized() {
    let hot = Pubkey::from_seed("hot");
    let txs: Vec<Transaction> = (0..4)
        .map(|i| Transaction::transfer(hot, Pubkey::from_seed(&format!("sink{i}")), 1))
        .collect();
    let batches = schedule(&txs);
    assert_eq!(batches.len(), 4);
    assert!(batches.iter().all(|b| b.len() == 1));
}

Read-only sharing does not conflict. Two transactions both read a shared config account but write different accounts. The read–read on config is exempt, so conflicts returns false and the two are free to batch together.

#[test]
fn conflict_rule_ignores_read_read() {
    let shared = Pubkey::from_seed("config");
    let a = Transaction::new(
        TransferProgram::id(),
        vec![
            AccountMeta::readonly(shared),
            AccountMeta::writable(Pubkey::from_seed("a")),
        ],
        vec![],
    );
    let b = Transaction::new(
        TransferProgram::id(),
        vec![
            AccountMeta::readonly(shared),
            AccountMeta::writable(Pubkey::from_seed("b")),
        ],
        vec![],
    );
    assert!(!conflicts(&a, &b));
}

Run them:

cargo test -p solmini schedule
cargo test -p solmini conflict

The three cases — full parallelism, full serialization, and the read-only exemption — are the whole behavioural envelope of the scheduler. Everything a real block does is a mixture of these three shapes.

The honest simplification

Two things here are deliberately smaller than real Solana, and it is worth naming them so you know where the map ends.

First, the conflict scan is O(n^2). Every transaction is compared against every earlier one, and each comparison walks both account lists. For a demo of a few dozen transactions this is invisible; for a real block of thousands it would be a bottleneck. Solana does not scan pairs. It maintains a lock table keyed by account: as it walks transactions, it records for each account the latest batch that read or wrote it, and computes a transaction’s batch from just the accounts it names — closer to linear in total account references than quadratic in transactions. The bookkeeping differs; the answer is identical.

Second, the layering we built is exactly the idea real Solana uses, even though the machinery around it is heavier (per-account read/write locks, priority ordering, compute-unit budgeting per batch). The core move — declared footprints → a conflict rule → conflict-free batches that preserve order — is not a toy version of Solana’s scheduler. It is Solana’s scheduler, with the fast data structures and the production concerns stripped away so the idea is visible.

It actually happened — the write-lock stampede of Sept 14, 2021

On September 14, 2021, Solana’s mainnet-beta halted for roughly 17 hours and required a coordinated validator restart. The trigger: a burst of bots submitted a flood of transactions all contending for the same accounts during a token launch, reportedly peaking around 400,000 transactions per second of load. Every one of those transactions wanted a write lock on the same hot accounts — which is precisely the transfers_sharing_an_account_are_serialized case above, at network scale. Contention that the scheduler correctly serialized still overwhelmed the machinery around it (forwarding, memory), and consensus stalled.

The lesson maps straight onto this page: a hot writable account is a serialization point, and no scheduler can parallelize away a genuine data dependency. It can only refuse to run conflicting transactions together — which, under a stampede, means refusing to run most of them at once at all. The long-term fixes (localized fee markets, QUIC, stake-weighted quality of service) are all attempts to price and shape contention before it reaches the scheduler, precisely because the scheduler’s honest answer to “everyone wants to write the same account” is “then almost none of you run in parallel.”

The architect’s lens

• Why does it exist? To convert declared account footprints into permission to use every core. Without a scheduler, “state lives in named accounts” is just tidy bookkeeping; the scheduler is the component that turns those declarations into safe parallelism.
• What problem does it solve? It answers, before execution, “which of these transactions can run at the same time without racing?” — and it answers it from data alone (the accounts lists), never by running the code it is trying to schedule.
• What are the trade-offs? Correctness for pessimism. It serializes any two transactions that might race, even if their code paths would not actually collide at runtime — a hot writable account throttles throughput to one-at-a-time. And the naive conflict check is O(n^2); production needs a per-account lock table.
• When should I avoid it? When there is no parallelism to win — a single-threaded VM, or a workload where nearly every transaction writes the same account (an NFT mint, a token launch). There the scheduler’s overhead buys nothing, because the honest answer is “these must run in order.”
• What breaks if I remove it? Everything the part is for. Without the scheduler you either run strictly sequentially (the throughput ceiling this book set out to break) or you run in parallel unsafely and let two transactions corrupt the same account — the “falling apart” in the throughline, made real.

Check your understanding

1. State the conflict rule in one sentence, and explain why read–read on the same account is exempt. What would happen to a chain’s throughput if read–read did count as a conflict?
2. Write out batch(i) and use it to explain why two conflicting transactions can never land in the same batch.
3. In the diagram with writes A B A C B, why does t3 (writing C) end up in batch 0 rather than batch 1, even though it was submitted after t2?
4. The transfers_sharing_an_account_are_serialized test produces four single-transaction batches. Which real-world situation does this model, and why can no scheduler do better for it?
5. Name the two honest simplifications on this page. For each, say what real Solana does instead and whether the result of scheduling would differ.

Show answers

1. Two transactions conflict when they share an account and at least one writes it. Read–read is exempt because two simultaneous reads of an unchanged account cannot race — neither observes a half-finished mutation. If read–read counted as a conflict, any popular read-only account (a price oracle, a config account) would force every transaction that consults it into a separate batch, serializing the whole chain and destroying the parallelism the account model exists to enable.
2. batch(i) = 1 + max{ batch(j) : j < i and conflicts(i, j) }, or 0 if nothing earlier conflicts. If two conflicting transactions i > j were in the same batch, then conflicts(i, j) is true, so the rule forces batch(i) >= batch(j) + 1 > batch(j) — a contradiction. The later one is always pushed at least one layer above the earlier one it conflicts with.
3. Because t3 writes C, and no earlier transaction (t0 writes A, t1 writes B, t2 writes A) touches C. With no earlier conflict, its batch is 0. Layering places a transaction as early as its dependencies allow, never as late as its submission position — order is preserved only among conflicting transactions.
4. It models a hot writable account: many transactions all draining or mutating the same account (a token launch, a single popular wallet, an NFT mint). Every pair genuinely depends on the previous one’s result, so they form a true dependency chain. No scheduler can parallelize a real data dependency; it can only run them in order, one batch each.
5. (a) The O(n^2) conflict scan — real Solana keeps a per-account lock table and computes each transaction’s batch from just the accounts it names, closer to linear; the result (the batching) is identical, only faster to compute. (b) The layering algorithm’s surrounding machinery is simplified (no per-account locks, priorities, or compute-unit budgets), but the layering idea itself is exactly what Solana uses, so the conflict-free, order-preserving batches it produces are the same in kind.