Software Transactional Memory: Logs, Validation, and Retry

A lock-based program must name, in advance and in the source, which data each critical section protects. Software transactional memory removes that requirement: the programmer marks a region as atomic, and the runtime makes the region appear to execute instantaneously with respect to every other atomic region. The data a region touches is discovered at runtime, by watching it touch things.

The mechanism is optimistic. A transaction runs without acquiring exclusive rights to anything, records what it read and what it wrote, and only at commit time checks whether the world still matches what it observed. If the check passes, the writes become visible together; if it fails, the transaction is discarded and run again.

The read set, the write set, and the version check

Every access inside a transaction is intercepted, by a compiler transformation, a library API, or a word-level metadata scheme. A read records the address and the version it observed into the read set. A write is buffered in the write set and not applied to shared memory; subsequent reads within the same transaction consult the buffer first, so the transaction sees its own writes.

Versions are per-location counters, typically a word alongside the value or a bit-packed field within it. A transaction’s read set therefore stores pairs of (address, observed version). At commit, the runtime validates: for every entry in the read set, is the version still the one recorded? If yes for all, the transaction’s view is still valid, and the write set can be published. If any entry has moved, the transaction is stale and must abort.

The order matters. Validation must complete before publication, and publication must be atomic with respect to other transactions’ validation. If a transaction publishes its writes and then validates, another transaction may have validated against the pre-publication state in the gap. The standard solution is a global commit lock, held only during validation and publication, which serialises commits while leaving the long body of the transaction concurrent. That lock is the reason commit is not free, and it gives every transaction a fixed cost that a long transaction amortises better than a short one.

Publication itself is the hard part. Writing the write set word by word is not atomic; a concurrent reader could see half the update. Implementations therefore either hold a commit lock that readers also respect at validation, or publish through indirection, swapping a pointer to a new version of the structure, or use ownership records that transfer exclusive rights to a word. The version counters that make validation possible are ordinary atomics, and the ordering they need is exactly the release/acquire pairing described in Happens-Before and the Memory Model Contract. Each choice moves cost between readers and writers.

Why retry is a livelock, not a deadlock

An aborted transaction is retried immediately, in a loop. Two transactions that each write a location the other reads will abort each other indefinitely, and neither makes progress. This is livelock: the system is not blocked, the threads are running, and the work is being discarded.

The distinction from deadlock is not cosmetic. A deadlock is a stable state that can be detected by a cycle in a wait-for graph. A livelock is a probabilistic property of a schedule, and detecting it requires noticing that a particular transaction has aborted too many times. Runtimes handle it with contention management: exponential backoff, aborting the older transaction, or giving priority to the transaction that has already been retried. None of these is a guarantee. Long-running transactions are the known pathological case, because a long transaction accumulates a large read set and therefore a high probability that at least one entry has been invalidated before it commits.

This is the fundamental trade of optimistic concurrency: the cost of a transaction is proportional to its length times its conflict probability, and the conflict probability grows with the amount of shared data touched. Locks do not have this property: a long critical section holds the lock for its duration, and no amount of contention can force it to restart. Locks degrade by waiting; STM degrades by wasting work.

Retry as a first-class operation

The composability argument for STM is that atomic blocks compose: a transaction that calls another transaction simply extends its read and write sets, and the result is atomic as a whole. This is not true of locks, where composing two lock-based operations requires knowing their lock order to avoid deadlock.

Composability enables a primitive that has no lock equivalent: retry. A transaction that finds the state it needs absent can call retry, which blocks the transaction until one of the locations in its read set changes, then restarts it. The implementation is to park the thread on the read set’s version words, so the next write to any of them wakes it.

-- atomically retries until the queue is non-empty, without polling
pop :: TVar [a] -> STM a
pop q = do
  xs <- readTVar q
  case xs of
    []     -> retry
    (x:rest) -> writeTVar q rest >> return x

The consequence is that a consumer waiting on an empty queue consumes no CPU while waiting and is woken exactly when a producer commits. A lock-based equivalent would need a condition variable plus a predicate loop, and the predicate would have to be evaluated under the lock, which is the same mechanism, written by hand and easy to get wrong.

orElse is the other composable primitive: it runs the first transaction, and if that one calls retry, runs the second instead. Together, retry and orElse make blocking choice expressible as a value, which is what makes STM usable for coordination rather than only for counters.

Where the log lives and what it costs

The log has a memory cost proportional to the transaction’s footprint, and that cost is paid on every transaction regardless of whether it commits. A transaction that reads a thousand elements of a list records a thousand entries; validation then walks all of them. For a read-only workload this is pure overhead, which is why some implementations special-case read-only transactions: they record no write set and skip publication, though they must still validate their read set before returning.

The instrumentation cost depends on the implementation strategy. A compiler-based STM can inline the logging and is fast but requires whole-program transformation. A library-based STM intercepts through function calls and is portable but pays a call per access. Word-level STM packs a version and an ownership marker into the same machine word as the value, which avoids indirection at the cost of shrinking the usable value range, since several bits of each word are reserved for metadata.

Garbage collection interacts badly with STM in managed runtimes. A transaction that aborts must have its write set discarded, and any object allocated inside it becomes garbage; a long transaction that aborts repeatedly allocates repeatedly. Some implementations allow the transaction’s allocations to survive the abort, which is safe only if the aborted transaction’s effects on those objects are also discarded.

The boundary with other models

STM does not compose with blocking operations. A transaction that blocks on I/O holds its log and its read set while the world changes around it, which makes an abort at commit likely because anything it read has had time to move. The Haskell implementation restricts transactions to a monad that excludes I/O for exactly this reason, and the restriction is a feature: it makes the set of effects a transaction can have visible in its type.

Nor does STM replace message passing. It coordinates shared memory, so it presupposes that the participants share an address space. A mailbox-based design avoids the problem entirely by not sharing, at the cost of the ordering and queueing issues described in Mailbox Semantics and Ordering Guarantees in the Actor Model. The two are complementary: STM for fine-grained shared structures, message passing for coarse-grained ownership boundaries, and the choice is about where the sharing line is drawn rather than about which mechanism is faster.