Course contents
On this page
Alternative execution strategies — extended reference
Original detailed coverage and citations accompanying the focused alternative execution strategies lesson.
This reference preserves the earlier detailed chapter and its citations. Start with the guided explanation, then use these sections for additional mechanisms and qualifications. References to the original lesson sequence are historical.
Part 4: Transactions, concurrency, and recovery
Prerequisites: Lesson 21 and the preceding foundations.
Learning outcomes
- Compare optimistic validation, timestamp ordering, deterministic scheduling, and single-writer execution.
- Identify read/write conflicts and distinguish ordered execution from replicated durable agreement.
- Estimate wasted retry work and explain how contention changes a strategy’s useful operating range.
Concurrency has a cost even when it succeeds
A service with independent tenants can execute many transactions in parallel. A flash sale over one shared stock record produces a different outcome: optimistic transactions repeatedly do work that fails validation, while lock-based transactions wait. A serialized worker may avoid both repeated speculative work and fine-grained coordination, but it gives independent operations less opportunity to run simultaneously.
Concurrency control chooses how to order conflicting decisions. The relevant comparison includes useful completions, wasted attempts, metadata, cache behavior, and tail latency under the same correctness contract. Counting active workers alone does not measure progress.
Optimistic execution
Optimistic concurrency control lets a transaction read a snapshot or versions, compute tentative writes, then validate that the observations on which its decision depends remain acceptable. If validation succeeds, the transaction publishes its writes through an atomic commit protocol. Otherwise it aborts or retries.
attempt(transaction):
snapshot = begin_snapshot()
result, read_set, write_set = execute_privately(snapshot)
enter validation/publication protocol
require reads and predicates remain valid under target isolation
atomically commit write_set
return resultThe validation/publication protocol is essential. Two transactions cannot both validate against old state and then publish conflicting writes without further coordination. The exact read-set rules depend on the isolation guarantee. Protecting only rows returned by a query can miss a concurrent insertion into a previously empty range.
Optimism is attractive when conflicts are uncommon and transactions are short. It avoids holding long-lived logical locks during ordinary reads. It still spends resources tracking versions or reads, checking conflicts, and retrying aborted work. Those costs may be lower than waiting or lock management for one workload and higher for another.
Retry amplification under contention
Suppose each independent attempt has an illustrative 0.2 probability of success and retries continue under an unchanged probability model. Expected attempts per success are 1/0.2 = 5. At 10,000 useful commits per second, that model implies 50,000 attempts per second. Real conflicts are correlated and retry policies change arrival patterns, so this is a teaching calculation rather than a production prediction.
Wasted work can create feedback. More retries consume CPU and extend transaction duration, exposing attempts to more intervening changes. Randomized backoff, admission limits, and conflict-aware scheduling can reduce this effect. The business operation must remain idempotent and the transaction logic safe to repeat.
A serialization retry should re-read and recompute the decision. Reusing a stale calculated debit after a conflict defeats the purpose of validation. External side effects need separation or compatible idempotency because retrying database logic can otherwise charge, notify, or publish more than once.
Timestamp ordering
Timestamp-ordering schemes assign transactions or versions an order and enforce read/write rules consistent with it. A transaction may need to abort or wait if an access would violate that order. The timestamp can be logical rather than a wall-clock measurement.
The implementation must define allocation, uniqueness or tie-breaking, visibility, and the treatment of in-progress transactions. A larger wall-clock value does not automatically establish causal or commit order. Clock skew and uncertainty become especially important when timestamps cross machines, as later distributed lessons explain.
Timestamp metadata can itself become a bottleneck if every operation requires a centralized allocation or shared cache-line update. Batching or distributed allocation can help while changing the proof obligations. An ordering mechanism is a resource-consuming part of the engine, not free bookkeeping.
Deterministic scheduling
A deterministic design establishes an order or schedule before conflicting execution. If replicas or partitions execute compatible deterministic logic against the same ordered input, some coordination can move earlier in the pipeline. Knowing the read/write access set can help schedule nonconflicting work concurrently.
The difficult cases include data-dependent access, nondeterministic inputs, external I/O, and transaction logic that discovers keys while running. A design can restrict the programming model, predeclare accesses, perform reconnaissance, or use another protocol for exceptional work. Those constraints are part of the product’s workload fit.
Calvin’s original research is a historical example of deterministic transaction ordering for partitioned systems. Its claims and assumptions belong to that paper’s design and experiments. The general lesson is that coordination can be reorganized around a known schedule, with benefits that depend on the ability to establish and execute that schedule efficiently.
Single-writer execution
A single-writer or serialized execution path performs state transitions one at a time within a defined boundary. It can simplify mutable-state ownership and eliminate some conflict-detection or lock-management work. It can also keep hot data close to one execution resource.
The boundary is crucial. One writer per partition is different from one writer for an entire cluster. Network processing, replication, queries, and background work may use other threads. The phrase “single threaded” should identify the stage and scope it describes.
For short operations under heavy shared contention, serialized execution can avoid doing many incompatible speculative attempts. For long independent CPU-heavy transactions, it can leave parallel resources unused unless work is divided into independent execution domains. A long scan or callback in the serialized path can delay unrelated short work.
SpacetimeDB’s September 2026 architecture explanation states that each database uses a single-threaded execution model and reports that this outperformed its earlier parallel approach. That is a documented implementation report, not a proof that sequential execution wins for every engine or workload.
Compare equal contracts
A fair comparison keeps the invariant, transaction boundaries, isolation, durable acknowledgment, dataset, access distribution, and client workload fixed. Removing durable flushing from one design or weakening the conflict rule changes the task being measured.
The unit of useful progress should also be fixed. An optimistic engine can report many attempted transactions while completing fewer business operations. A lock-based engine can show low CPU because transactions wait on one hot resource. A serialized engine can show low coordination overhead while saturating one execution resource. Each observation needs the correct denominator.
Consider two illustrative workloads. In A, every request updates one shared inventory record. In B, every request updates a distinct tenant’s data. A design optimized for A can perform well by making the inevitable protected transition extremely short. B offers more independent work and can benefit from parallel execution or partition ownership. A product’s scalability depends on which workload the application actually resembles.
Hybrid strategies
An engine can combine methods. Reads may use versions, writes may acquire locks, validation may occur at commit, and partitions may execute in an ordered schedule. A global label such as optimistic or pessimistic often hides these combinations.
Hybridization introduces interfaces between mechanisms. A versioned reader and a locked writer must agree about visibility. A deterministic scheduler and a recovery log must agree about replayed inputs. A partition-local transaction and a cross-partition transaction must preserve the same promised isolation across different paths.
Adaptation based on contention can be useful, but mode changes need a safe transition protocol. Transactions already in flight cannot be interpreted under incompatible rules. The extra complexity must earn its value under measured workloads rather than exist only as unused flexibility.
A validation protocol must close its own race
Consider two transactions that read stock=1 and each proposes stock=0 while creating a different purchase. If both validate that the row is unchanged, then publish later without coordination, both can commit. The validation checks were individually true when performed, but neither protected the interval before publication. Optimism defers coordination; it does not eliminate the need for an atomic decision.
A simplified single-node design can serialize validation and publication under a commit gate. Each transaction reads versioned data, records relevant versions and predicates, then enters the gate. It checks whether observations still support its decision, constructs a commit record, and installs changes under a visibility protocol. The gate may cover durability or may hand off to a more elaborate ordered commit pipeline. Those choices affect failure behavior and throughput.
validate_and_publish(tx):
acquire commit_gate
if any_observation_invalid(tx.read_set, tx.range_reads):
release commit_gate
return RETRY_WHOLE_TRANSACTION
reserve_commit_order(tx)
commit_through_defined_durability_and_visibility_protocol(tx)
release commit_gate
return COMMITTEDThis sketch is intentionally conservative. A production engine can validate independent transactions concurrently or use fine-grained ownership, timestamps, and dependency tracking. The correctness argument must explain why two conflicting attempts cannot both pass and install incompatible results. A global gate is an explanatory baseline rather than an automatic scalable solution.
Read sets include absence when absence influenced the decision. A reservation query that found no overlapping booking cannot validate only the empty list of returned rows. It needs range or predicate evidence. Tracking only values that existed at read time quietly weakens the intended serializable contract.
Quantify useful work and wasted work separately
Suppose each attempt uses fifty microseconds of CPU before validation. With no retries, twenty thousand useful commits per second consume one CPU-second per second in attempt work. At an average of five attempts per successful operation, the same useful rate consumes five CPU-seconds per second before validation, logging, or scheduling costs. The machine can therefore become CPU-bound even while only a fraction of attempts contribute accepted changes.
A fixed success probability is a teaching approximation. Under contention, attempts are correlated: many read the same state and conflict together. Retrying immediately can synchronize another wave of losers. Randomized delay spreads attempts, while bounded admission reduces the number of simultaneous candidates. Backoff improves resource use by delaying work; it does not increase the rate at which one hot invariant can change.
Retry budgets need a business-operation boundary. If a proxy retries three times, an SDK retries three times, and a transaction callback retries three times, the combined attempt tree can exceed the intended limit. Attempts should consume a shared deadline and a bounded retry budget. Exhaustion should return a distinguishable contention or availability outcome rather than continue silently forever.
A transaction callback must also be replay-safe. Incrementing an external counter, sending mail, or charging a payment method inside the callback can repeat even if database changes abort. Move those consequences behind an outbox or use an external idempotency protocol with a clear authority. Automatic retries simplify some application code but cannot infer the semantics of arbitrary side effects.
Timestamp ordering in a concrete toy model
A classic teaching model assigns each transaction a unique logical timestamp. Each item records the largest successful reader timestamp and writer timestamp. A read or write that would contradict the timestamp order is rejected or handled by the protocol’s specific rules. The basic idea is to preserve one predetermined serial ordering rather than discover a compatible ordering afterward.
Suppose T10 reads X, establishing that a transaction ordered at 10 observed its current value. T8 later attempts to overwrite X in a manner that would need to precede T10’s read. Accepting it could invalidate the history, so the simple protocol aborts T8. The fact that T8 arrived at the physical write later does not change its assigned logical position.
Multiversion variants can let T10 read an older version rather than reject every out-of-order action. That increases scheduling flexibility but requires version selection, write rules, and garbage collection consistent with the timestamps. Timestamp ordering is therefore a family of designs, not one universal algorithm obtained by attaching a counter to every row.
A central timestamp allocator can become a contended cache line or remote service. Reserving blocks reduces allocator traffic but can create unused gaps and complicate progress watermarks. Hybrid logical clocks combine physical estimates and logical progression for certain distributed designs, but the clock alone does not prove serializability. The validation and commit protocol must still enforce the stated history.
Deterministic ordering moves uncertainty earlier
Imagine a sequencer creates batches of transaction requests in an agreed order. A scheduler knows each request’s read and write keys and lets nonconflicting requests run in parallel while respecting ordered conflicts. Replicas receiving the same ordered inputs can reproduce the same outcomes if execution is deterministic and starting state agrees.
For transfers over known account identifiers, access declarations are straightforward. For “purchase the cheapest available matching item,” the keys depend on a query result. The system may require a preliminary discovery phase, conservative access declaration, or restricted operation form. A preliminary result can become stale, so its use must remain part of the validated or ordered protocol.
External nondeterminism must be captured. A random reward can be chosen once and included as ordered input, or generated through a deterministic rule with agreed state. A remote API response cannot be independently fetched by every replica and assumed equal. Deterministic execution simplifies one class of agreement only after these input boundaries are defined.
Sequencing is itself a service with capacity, availability, and recovery requirements. Batching reduces per-request sequencing overhead but can add queueing and batch delay. Cross-partition execution can still wait for slow participants. The correct claim is that a known schedule can avoid some execution-time coordination, not that distributed work has become communication-free.
Serialized execution is an ownership strategy
A single mutable-state owner can execute short transactions with ordinary data-structure operations that would otherwise need fine-grained synchronization. It can improve locality because nearby actions reuse hot state in one cache hierarchy. The gain comes from removed coordination and shorter useful transitions, not from a claim that one core is inherently more powerful than many.
At a hypothetical twenty-five microseconds per transition, one execution resource has an ideal ceiling of forty thousand transitions per second before other overhead. An arrival rate of twenty thousand uses half that execution capacity. A single five-millisecond operation consumes the same execution interval as two hundred ordinary transitions, creating a burst of waiting behind it.
Moving expensive preparation outside the owner can help if the final decision is revalidated inside. Pathfinding, compression, or a recommendation calculation might produce a candidate result asynchronously, then a short transaction checks that its assumptions remain valid. Dividing an operation into pieces without revalidation can instead introduce the stale-decision races the serialized model was meant to prevent.
One owner per tenant or match can expose parallelism across independent state. Cross-owner operations then require messaging or distributed transactions. The ownership boundary should align with the scope of common invariants; arbitrary partitioning may make nearly every action cross-boundary and remove the simplicity advantage.
Compare three workload envelopes
In a contended inventory workload, many actions inspect and decrement one stock value. There is little independent state transition work. Locking queues attempts, optimism may waste attempts, and serialization can keep the required transition short. A conditional update can be effective regardless of the engine’s broader strategy because it minimizes application-held intermediate state.
In a partitionable multitenant workload, each transaction touches one tenant and tenant traffic is reasonably balanced. Parallel execution or independent owners can scale useful work. A single database-wide execution resource may become the ceiling even though no logical records conflict. Additional tenants help only if the architecture exposes their independence to more execution resources.
In a long analytical workload, transactions read large datasets and hold snapshots while performing substantial computation. Applying a short-transaction single-writer argument to the scan is misleading. Parallel scans, vectorization, asynchronous I/O, and version retention dominate. Keeping such work off the latency-sensitive mutation path can be more important than choosing between two commit-validation algorithms.
Real systems mix these envelopes. A dashboard query can overlap a flash sale; a background migration can turn formerly independent updates into widespread index work. Performance claims need workload duration, skew, read/write sets, retry behavior, and maintenance state. A short run with a fixed uniform key distribution does not characterize every application phase.
Adaptation requires an invariant during mode changes
An engine might route a hot key through a queue after observing excessive optimistic retries. To be correct, transactions already executing optimistically must coordinate with the queued path. If queued writes bypass the validation evidence seen by older attempts, both modes can accept incompatible decisions. A mode flag alone is not a transition protocol.
A safe transition can drain or fence old work, advance an epoch, and ensure new attempts use one compatible validation rule. Returning to optimistic execution needs similar care. Fine-grained adaptations may preserve one unified versioning protocol while changing scheduling only, reducing proof complexity. The simplest complete design is often to keep correctness fixed and adapt admission or order around it.
Metrics should include useful commits, attempts per commit, validation CPU, queue wait, conflict footprint, and tail latency. High attempt throughput with rising aborts is not success. Low CPU with a long hot-key queue is not spare capacity for that key. Understanding which work the mechanism spends or avoids is the foundation of a useful comparison.
Compare optimistic and ordered contention timelines
Optimistic hot stock:
A: read 1 -> compute -> validate/commit 0
B: read 1 -> compute -> validate fails -> reread 0 -> reject purchase
C: read 1 -> compute -> validate fails -> reread 0 -> reject purchase
Ordered hot stock:
A: [check 1; commit 0]
B: [check 0; reject]
C: [check 0; reject]The illustration counts rejection as a valid business result, distinct from an internal transaction abort. The ordered path avoids computing several stale purchase candidates, but it still processes requests and delivers rejections. An engine benchmark reporting only successful stock decrements cannot represent all work during a flash sale after stock reaches zero.
For independent keys, the picture changes. A, B, and C can compute and commit simultaneously if the engine’s protocol permits it. Serializing them under one database-wide owner would discard real independence. The appropriate comparison therefore includes both the hottest conflict group and the distribution of independent groups.
Bound the cost of admission
A queue can be placed before expensive optimistic execution. Suppose an attempt costs two hundred microseconds, but a lightweight admission check costs five microseconds. Rejecting or delaying excess arrivals before execution can save substantial CPU when the system already knows one hot ownership domain is saturated. The admission check must not claim a business success; it manages capacity rather than decides the transaction.
A per-key queue needs bounded metadata and safe cleanup. Millions of random key requests can otherwise allocate millions of queues. A shared scheduler can use a fixed number of buckets, accepting some false contention, or cap active domains and apply a fallback policy. Scheduling metadata is itself a resource that untrusted traffic can exhaust.
Fairness matters across domains. A constantly hot tenant should not monopolize the global admission structure while quiet tenants wait. Weighted scheduling or separate budgets can expose independent progress. These measures complement whichever concurrency-control algorithm validates state; they do not weaken the invariant to obtain throughput.
An ordering decision is useful only when its cost stays below the work it saves. At low contention, tracking fine-grained conflicts may expose valuable parallelism. At high contention, an explicit queue can avoid repeated failed work. The same engine may encounter both regimes during one day, so workload characterization should include quiet periods, bursts, and recovery rather than one steady peak.
Case connection and design conclusion
Convex documents optimistic concurrency control and automatic transaction retries. Calvin illustrates deterministic scheduling in a historical research architecture. SpacetimeDB documents a serialized per-database execution choice. These cases show legitimate alternatives around a common problem: ordering decisions whose observations and writes interact.
Choose a strategy by conflict frequency, transaction duration, access predictability, locality, and recovery requirements. The next lesson examines the physical shared-memory structures implementing those strategies, where even logically independent transactions can contend over cache lines, metadata, and memory reclamation.