Concurrent engine internals — extended reference

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 22 and the preceding foundations.

Learning outcomes

Distinguish logical transaction locks from short-lived structural latches.
Explain atomic publication, memory ordering, cache-line sharing, and safe reclamation under the stated memory model.
Identify why lock-free access does not automatically mean bounded latency or safe lifetime management.

A valid transaction can follow an invalid pointer

A reader locates an index node. Before it reads the next field, a writer removes and frees that node. The allocator reuses the memory for another object. The reader then interprets unrelated bytes as an index entry. Transaction isolation did not prevent the failure because the immediate problem is structural memory safety.

Database engines need both logical concurrency control and physical synchronization. Logical locks or validation protect transaction semantics. Latches, atomic operations, pins, and reclamation protocols protect internal structures while they are accessed and changed. Confusing the two leaves gaps in both correctness and performance reasoning.

Locks versus latches

A transaction lock can be retained until commit and participate in deadlock handling. A latch generally protects a short physical operation on an internal object. An engine should avoid holding a short structural latch while performing long or unpredictable work unless its protocol explicitly requires and tolerates it.

A page split might acquire latches to preserve tree structure while transaction-level rules independently determine which keys are visible. Releasing the latch does not commit the transaction. Committing the transaction does not prove that every raw pointer held by another worker is still valid.

Internal deadlocks remain possible if latch order is inconsistent. Because structural critical sections are often short and pervasive, designs commonly use strict acquisition orders, try-and-restart patterns, or carefully proven traversal protocols. A restart must release every acquired resource and leave no partially published structure.

Atomic operations and memory ordering

An atomic operation prevents certain torn or interleaved accesses to one atomic object. It does not make a collection of ordinary fields appear as one atomic state transition. Publication requires ordering: a reader that sees a pointer to a new node must also see the initialized contents that the pointer makes reachable.

writer:
    node = allocate_and_initialize()
    publish_pointer_with_release_semantics(node)

reader:
    node = load_pointer_with_acquire_semantics()
    if node exists:
        read_initialized_fields(node)

This is conceptual pseudocode, not a portable implementation. The language memory model, object lifetime, and reclamation protocol still apply. Acquire/release publication does not prevent the node from being freed after the load. It establishes one ordering relationship, not the entire safety argument.

A memory-ordering bug may disappear in ordinary tests and emerge on another architecture or under optimization. Correctness should follow the language and hardware model rather than empirical confidence that a race has not yet occurred. The cited C++ working draft is a primary reference for the relevant language-level concepts, even though the course uses language-neutral algorithms.

Two independent 8-byte counters may occupy one illustrative 64-byte cache line. If separate cores repeatedly update them, the coherence mechanism can move line ownership between cores even though the logical counters do not interact. This is false sharing.

Padding or partitioning can reduce this traffic while increasing memory use. Per-worker counters can avoid shared updates and combine later, but exact immediate totals require additional coordination. The suitable choice depends on whether the counter is approximate telemetry or an authoritative business invariant.

True sharing occurs when workers genuinely update the same value. Padding cannot divide that ownership. Sharding a counter can help when the operation’s semantics permit aggregation, but a strict global limit needs an additional protocol. Physical layout and logical contract must be analyzed separately.

Concurrent tree traversal

Latch coupling acquires protection on a child before releasing relevant protection on the parent, under a defined protocol. It prevents a traversal from following a structure that changes incompatibly during the handoff. It can also increase contention near hot upper levels.

Optimistic traversal reads metadata and validates that the node did not change incompatibly. A version counter or sequence can identify a concurrent modification. If validation fails, the reader restarts. The implementation must avoid reading freed memory before validation can even occur; validation and reclamation solve different hazards.

Sibling links and fence keys can allow a search to recover from a split by moving to a neighboring node. Such a design requires exact rules for key ranges and publication order. Adding a sibling pointer without changing the search and recovery algorithms consistently does not create a correct concurrent tree.

Memory reclamation

Reference counting retains an object while references exist. It adds update traffic and can struggle with cycles or hot counters. Hazard pointers let readers publish which objects they may dereference, so reclamation waits until no hazard remains. Epoch-based methods defer reclamation until relevant readers have passed a safe boundary.

Each method has a progress and resource tradeoff. A stalled reader can delay epoch reclamation and accumulate memory. Hazard publication has per-access costs and careful retry rules. Reference counts require safe acquisition of a reference from a shared pointer; incrementing a count after the object is already freed is not safe.

The ABA problem arises when a shared value changes from A to B and back to a value that looks like A. A compare operation can mistakenly conclude that nothing relevant changed. Tagged generations can help under bounded assumptions, but wraparound and lifetime must be considered. Preventing address reuse until readers are safe is often part of the solution.

Lock-free does not mean wait-free or faster

A lock-free algorithm guarantees a form of system-wide progress under its model: some operation completes despite interference. A wait-free algorithm gives a stronger per-operation bound. Neither label establishes low latency on a particular workload or the absence of resource contention.

A compare-and-swap loop can waste work under heavy contention. Memory reclamation, cache misses, and allocation can dominate. A simple mutex around a short critical section can outperform a complicated nonblocking structure in some conditions. The design decision should include implementation proof, maintainability, and measured behavior.

Blocking operations also have progress properties. A lock holder can be descheduled, creating a convoy. Priority inversion can delay important work. Bounded critical sections and ownership partitioning can be more valuable than replacing every lock with atomics. The smallest safe mechanism that meets the workload is often preferable to a universally flexible one.

NUMA-aware ownership

On a NUMA machine, allocating and accessing shared structures can incur remote-memory costs. Per-node caches, partition-local metadata, and stable worker placement can improve locality. Cross-node transactions then need explicit coordination and may transfer data or ownership.

A globally shared allocator or statistics counter can undermine otherwise partitioned execution. Profiling should inspect cache-line and remote-memory behavior rather than assuming that independent tenant keys guarantee independent physical access. Conversely, overpartitioning can strand memory and make rebalancing expensive.

Failure and verification

Concurrency bugs require tests that explore interleavings, lifetime boundaries, and interruption points. Stress tests alone provide incomplete evidence. Sanitizers, model checking of small algorithms, deterministic schedules, and targeted fault injection can reveal different classes of error.

A test should verify invariants rather than only final throughput. For a tree, every reachable key should remain searchable under the defined visibility model, nodes should obey range boundaries, and no reclaimed memory should remain reachable to valid readers. A recovery test adds interrupted publication and replay to that argument.

Publication and reclamation are independent proofs

Suppose a writer allocates a node, initializes its key array, then publishes a pointer. A reader loading the pointer with the matching acquire operation can observe the initialized fields when the language’s release/acquire rules establish the required synchronization. That does not protect a subsequent mutation of those fields. If the node remains mutable, readers need a compatible synchronization protocol for those updates too.

Now suppose the writer unlinks the node immediately afterward. The reader may already hold its address. Even if every pointer load and store was atomic, freeing the allocation can invalidate the reader’s access. The design needs a second proof: no object is destroyed while any legitimate reader can still dereference it. Correct publication and safe lifetime are different conditions, and both must hold.

A hazard-pointer-style acquisition illustrates the dependency. The reader loads a candidate pointer, publishes that candidate in its hazard slot, then reloads the shared pointer to check that the candidate is still current. If the shared pointer changed, the reader clears or replaces its hazard and retries before dereferencing. A matching reclamation protocol waits until retired nodes are absent from the relevant hazard set. Exact memory orders and scanning rules require a complete language-specific implementation.

repeat:
    candidate = load_shared_pointer()
    publish_hazard(candidate)
    if candidate == load_shared_pointer():
        break
    clear_hazard()
use_node_while_hazard_remains_published(candidate)
clear_hazard()

The second load matters because removal can race with the first load. Publishing an address after the reclaimer already freed it does not restore its lifetime. The protocol’s ordering ensures the reader either protects a node that is still valid or detects the change before use. This explanatory sketch must not be copied into a language without selecting correct atomic operations and reclamation assumptions.

Epoch reclamation trades per-object work for delayed reuse

In an epoch scheme, a reader announces entry to a protected interval and leaves when it no longer holds relevant references. A writer retires removed nodes with an epoch marker. Reclamation waits until every reader that could have observed those nodes has passed a safe boundary. Readers can traverse many nodes without publishing a hazard for each one, which can reduce per-node overhead.

A paused reader can delay reclamation for the entire interval. Suppose writers retire 200,000 nodes per second at an average 128 bytes per node. A stalled protected reader lasting thirty seconds can retain an illustrative 768 MB of retired-node payload. That excludes allocator metadata and associated buffers. The reader may consume almost no CPU while causing substantial memory pressure.

A database must decide whether protected intervals may span blocking I/O, user callbacks, or long computations. Keeping them short reduces retained memory, but exiting and reentering requires discarding or revalidating old pointers. A transaction snapshot can outlive a physical-memory critical section: persistent version identifiers can be resolved again after a pause. Conflating transaction lifetime with raw-pointer protection often creates unnecessarily long reclamation horizons.

Thread failure creates additional obligations. A permanently abandoned epoch registration can prevent reuse forever unless the system has a safe way to establish that the participant no longer accesses memory. Marking it inactive based only on elapsed time is unsafe if it can resume. The same “paused does not mean dead” principle later appears in distributed leadership.

A concurrent split needs an observable intermediate state

Imagine a B+ tree leaf covering keys 100 through 199. A split creates a right sibling covering 150 through 199, while the old leaf retains 100 through 149. Updating every parent and reader atomically is impractical. A correct protocol defines intermediate states readers can navigate safely, often using fence keys and sibling links along with latch rules.

One conceptual sequence is to initialize the new sibling, install a right link and updated high boundary in the old leaf under protection, then install the parent separator through the algorithm’s chosen mechanism. A reader descending through an old parent can find the old leaf, compare its target against the high boundary, and follow the right link. The precise order and logging rules are algorithm-specific; the point is that a temporarily stale parent must still lead to a valid search path.

parent separator not yet updated
             |
             v
 old leaf: [100,150) --right link--> new leaf: [150,200)

The diagram uses half-open intervals so the boundary key 150 belongs unambiguously to the new leaf. Readers need protection against the old or new node being reclaimed, and they must not observe a half-initialized sibling. Transaction visibility remains separate: a structurally reachable inserted entry can still belong to an uncommitted transaction.

A split can also crash between persistent steps. Recovery must restore a searchable structure or complete the unfinished structural work. Logging only the application insertion is not enough to explain every physical intermediate state. Concurrency and crash consistency are therefore designed together for index structures, even though their correctness arguments address different failure dimensions.

Atomics cannot repair an undefined access pattern

A sequence counter is sometimes used to detect concurrent modification: a reader reads an even sequence, copies fields, then checks the sequence stayed unchanged. In a language where those field reads race with ordinary writes, the program can be undefined even if the final sequence check rejects the copy. The validation does not retroactively make an invalid read legal. A correct implementation must use permitted atomic representations, immutable versions, locks, or another language-supported mechanism.

The same issue appears in hand-written double-checked initialization. Testing a pointer and then reading ordinary fields without the necessary publication ordering can expose partially initialized state. volatile has different meanings across languages and generally should not be treated as a universal concurrency primitive. The engine must follow its implementation language’s actual memory model.

Atomic widths are also platform-dependent. An operation described as atomic by an API may use an internal lock on a particular target. Alignment, representation, and object lifetime affect legality. Portability claims need explicit supported architectures and compiler assumptions. A high-level pseudocode algorithm can explain intent, but production correctness requires the lower-level contract.

Stronger ordering can simplify reasoning at some cost, while weakening order without a proof can introduce rare corruption. Start from a correct synchronization design and optimize observed hot paths. Replacing every operation with a minimally ordered atomic because a benchmark improved once is not a safe method for engine internals.

Coherence traffic can dominate independent work

Consider eight workers incrementing a single global completed-operation counter for every operation. At five million operations per second, the counter receives five million read-modify-write updates per second. Its ownership can bounce among cores even though the underlying database records are independent. The counter becomes a physical serialization point introduced by telemetry.

Per-worker counters remove that shared update from the hot path. A metrics reader can sum them periodically, accepting a non-instantaneous observation for operational reporting. This is suitable for approximate monitoring but not automatically for enforcing a strict quota. A strict quota may require reserved budgets or another explicit coordination protocol.

False sharing can occur even after sharding. If eight counters sit consecutively in one cache line, independent updates still invalidate each other’s cached copies. Padding or alignment can separate them, but more memory and cache footprint are consumed. Arrays of frequently read immutable data have different layout needs from arrays of frequently written counters.

NUMA adds distance to the coherence picture. Allocating all worker-local data on one memory node can cause remote access from other sockets. First-touch placement, stable ownership, and local allocation can help. Rebalancing or work stealing may move execution away from its data, so the scheduler and allocator need a compatible policy rather than isolated local optimizations.

Progress guarantees do not imply latency bounds

A lock-free stack can guarantee that some operation completes while one particular thread repeatedly loses its compare-and-swap race. That is system-wide progress, not starvation freedom for every caller. A wait-free algorithm provides a stronger bounded-step property under its model, but actual elapsed time still includes scheduling, cache misses, and preemption.

A mutex-based queue can be fast under low contention because the uncontended path is short. Under contention, a descheduled owner can delay all waiters. A spinning lock avoids a sleep/wakeup transition only when the holder is likely to run soon and the critical section is sufficiently brief. Spinning while the holder waits on disk wastes CPU without accelerating progress.

Hybrid locks spin briefly and then block, but their parameters depend on workload and scheduling. The important engineering decision is the maximum protected work and whether it can block, allocate unpredictably, or invoke external code. Reducing the critical section often yields more reliable gains than changing its primitive.

Verification should separate semantic layers

A tree stress test can verify that inserted committed keys remain reachable, but it may miss use-after-free if the allocator rarely reuses memory. A memory sanitizer can detect certain illegal accesses but cannot establish transaction serializability. A history checker can detect invalid transaction results while missing a benign-looking internal race that has not yet corrupted output. These tools provide complementary evidence.

Small-state exploration is valuable for publication and reclamation protocols. Model a few nodes, two readers, one writer, and pauses at every relevant transition. Check that no protected pointer refers to freed storage and that every completed traversal returns a permitted result. Keeping the model small makes interleavings tractable and forces the algorithm’s assumptions to become explicit.

Performance review then asks where synchronization work lands: latch hold times, retry loops, cache misses, remote-memory accesses, and retained retired objects. Logical independence does not guarantee physical independence. A database intended for large concurrency needs both a correct state-ordering protocol and data structures that avoid unnecessary shared ownership on the critical path.

A reader lifetime timeline

reader:     enter protection -> load pointer -> verify -> use -> exit protection
writer:                  unlink node -> retire node ............ reclaim later
publication: initialize node -> release publish -> acquire observe

The first two lanes describe reclamation, while the third describes initial publication. They are separate timelines because an object can be initialized correctly yet destroyed too early. The writer may unlink a node while a reader still uses it, but reclamation waits for the selected lifetime protocol’s safe boundary. Physical unreachability from the current root does not prove no reader holds a reference.

A hazard-based protocol and an epoch-based protocol place their protection boundaries differently. The former can protect individual nodes with more frequent publication work; the latter can protect an interval containing many nodes while delaying reuse if a reader stalls. The correct selection depends on traversal length, pause behavior, allocation rate, and required progress properties.

Separate a transaction retry from a structural restart

An optimistic tree traversal may restart because a node split during search. That restart can be invisible to the transaction and need not invalidate the transaction’s logical snapshot. Conversely, a transaction retry after serialization failure restarts business decisions and may repeat application code. Both are called retries informally, but their semantics and cost differ.

A structural restart must not leak latches, pins, hazards, or temporary allocations. It must also avoid carrying unvalidated offsets from an earlier node incarnation into the new traversal. A version tag can detect a changed structure, while a reclamation protocol preserves legal memory access until detection completes.

Metrics should distinguish structural retries, lock waits, transaction aborts, and application retries. Combining them into one counter hides the layer causing overhead. A high structural retry rate near one root might suggest a latch or split problem, while a high transaction retry rate might reflect a genuine shared invariant. The same response—adding more worker threads—can worsen either bottleneck if it increases interference.

A safe design also states what happens when allocation fails while a node is protected. The failure path must release protection and leave the published structure valid. Exceptional paths deserve the same lifetime argument as the fast path because resource pressure makes them more likely precisely when concurrency is highest.

Design conclusion

Internal concurrency is a combination of atomicity, ordering, ownership, and lifetime. A pointer can be correctly published yet reclaimed too early; a transaction can be serializable while an index implementation is memory unsafe. Every shared structure needs its own safety and progress argument.

Lesson 24 extends those arguments across process termination and partial storage writes. The engine must preserve a recoverable representation even when execution stops between two apparently adjacent instructions.

Sources and further reading

Course index · Lesson plan