Atomic transactions and logging — 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 18 and the preceding foundations.

Learning outcomes

• Define transaction states and distinguish execution, commit decision, durable acknowledgment, and visibility.
• Explain undo, redo, and WAL ordering under explicitly stated buffer policies.
• Follow a crash at each boundary without committing an incomplete logical transaction.

A transfer is one outcome, not two writes

A transfer moves 20 units from Alice’s balance to Bob’s. A crash occurs after Alice’s new balance reaches a data page but before Bob’s does. If restart merely opens the files and trusts their contents, money has disappeared. Atomicity requires the database to recover either the complete accepted transfer or a state without its effects.

The implementation needs a durable description of what happened and a rule for interpreting incomplete work. A log is useful only when its ordering, completeness, and relationship to data pages are precisely defined. Appending human-readable events after each write does not automatically create a transaction protocol.

Transaction states and visibility

A transaction begins active, performs reads and tentative changes, then either aborts or reaches a commit decision. The engine must distinguish a decision from later cleanup and client delivery. A committed transaction can remain temporarily unknown to its client if communication fails.

Tentative changes can be kept private until commit or installed into shared structures with visibility metadata. Private writes simplify some abort behavior but need publication and conflict handling. Installed writes can support efficient buffering while requiring readers and recovery to distinguish committed from uncommitted state.

Atomic visibility means readers do not observe an arbitrary subset of one transaction’s logical changes under the promised isolation contract. Physical pages may reach storage at different times. Recovery and visibility metadata reconcile those physical differences. Atomicity therefore does not require one hardware write containing the entire transaction; it requires a protocol that makes the logical outcome indivisible.

Undo and redo

Undo records enough information to reverse tentative changes. Redo records enough information to reconstruct accepted changes not fully installed in data files. A log design can use physical byte changes, logical operations, or physiological records that combine page identity with operation meaning.

The required combination depends on buffer policy. If uncommitted dirty pages may be written to data files, often called steal, recovery needs a way to eliminate their uncommitted effects. If commit does not force all changed pages to disk, often called no-force, recovery needs redo. A steal/no-force design commonly needs both, with additional detail to handle partial rollback and repeated recovery.

These labels describe policy, not a complete algorithm. An MVCC engine can retain physically present versions while marking them invisible rather than restoring every old byte immediately. A private-write engine may avoid writing uncommitted data pages. The log and visibility design must be evaluated together rather than combining rules from incompatible models.

Write-ahead ordering

The write-ahead rule requires recovery information to become durable before a data page containing the dependent change can become durably installed. Otherwise a crash can preserve a page modification without the information needed to explain or reverse it.

A page may record the log sequence position of its latest applied change. Before writing that page, the engine ensures the log is durable through the required position. This connects buffer writeback with log flushing. The page’s sequence position also helps redo avoid applying an already represented change incorrectly.

At commit, the engine makes the required commit information durable before acknowledging under a synchronous durability contract. It need not flush every changed data page if redo can recover them. This is a major reason logging can reduce foreground persistence cost: a sequential durable log can stand in for many immediate random data-page writes.

A simplified redo-oriented protocol

Consider a deliberately limited teaching design with serialized writers, private tentative writes, and a recoverable log containing complete transaction mutations plus a commit marker. Readers do not see tentative state. This model is chosen to make the atomic boundary visible; it is not ARIES and not a complete concurrent production engine.

commit(transaction):
    validate transaction preconditions
    append framed mutation records
    append commit record with transaction identity
    wait until log is durable through commit position
    publish the complete transaction to the current in-memory state
    release result to caller

The engine must also define memory publication so readers cannot see half the installed transaction. A global execution boundary or immutable state publication can supply that in the teaching model. Concurrent publication would require additional machinery. The log must detect incomplete trailing records and validate transaction completeness before replay.

If the process crashes before the commit record is durable, recovery ignores the incomplete transaction. If it crashes after the record is durable but before memory publication, recovery replays the complete transaction. If it crashes after publication but before replying, the transaction remains committed and the client needs the operation identity protocol from Lesson 5.

Framing and integrity

A log consists of records with lengths, types, identifiers, and integrity information appropriate to the design. Recovery must distinguish a valid prefix from a partial tail. A checksum helps detect corruption but does not prove the record is authorized or semantically valid. Length bounds prevent corrupted metadata from causing arbitrary allocation or out-of-bounds access.

A transaction spanning several records needs a completeness rule. A commit marker should refer to a transaction whose required records are known and valid. Sequence continuity or checksums can help identify missing material, but the exact protocol must be explicit. A recovery process should not guess that an isolated commit-looking byte pattern means a valid transaction exists.

Log positions also serve as watermarks. Appended, written, durable, committed, and applied positions can differ. Collapsing them into one number obscures both performance and correctness. A subscriber or replica may wait for a particular watermark depending on the guarantee it exposes.

Group commit

Several transactions can share one durable flush. If an illustrative flush takes 2 milliseconds and covers forty commits, the flush time amortizes to 50 microseconds per transaction in an accounting sense. Each transaction may still wait close to the full flush duration, plus batching and queueing. Amortized work is not individual latency.

A group-commit controller needs a policy for when to flush: elapsed time, accumulated bytes, waiting commits, or a combination. Waiting longer can improve throughput while increasing acknowledgment latency. Under light load, waiting for a large batch can be especially harmful. A bounded delay policy can preserve responsiveness.

The engine must release only transactions whose required log positions are durable. A later append can share the flush if included; otherwise it waits for another durable advance. A flush failure requires a safe error path and often a transition that prevents further unsafe acknowledgments.

Aborts and partial work

An abort reverses or makes invisible the transaction’s tentative effects according to the engine model. It also releases logical locks, memory, temporary files, and reservations. Reversing data while forgetting an index entry or allocation can leave latent corruption or leaks.

Partial rollback and savepoints complicate the model because some transaction work is undone while the transaction remains active. Recovery may itself crash. A robust algorithm records enough progress to resume safely rather than repeatedly undoing work in an unsafe way. The ARIES paper is a foundational reference for this family of problems.

An external side effect does not participate automatically. If application code sends a payment request before its local transaction aborts, local undo does not reverse the remote charge. Atomic database changes and atomic cross-system effects are different scopes. The outbox and idempotency patterns later make that boundary explicit.

A crash matrix for the private-write teaching engine

Start with Alice at 100 units and Bob at 50. A transfer of 20 should leave 80 and 70. The teaching engine holds those tentative values in private memory and serializes writers. Its base snapshot contains a committed applied watermark, and replay installs complete committed transactions after that watermark in log order. It never flushes tentative private pages into the base snapshot. These restrictions make a redo-only explanation coherent; relaxing them would require more machinery.

The log contains a transaction identifier, the expected number of mutation records, target identifiers, resulting values, and a final commit record referring to the mutation set. Record framing detects an incomplete tail, while the transaction envelope lets recovery reject a commit whose necessary mutations are missing or invalid. A checksum catches certain damaged bytes but does not replace the completeness rule.

Recovery decides from the valid history that actually survived, not from whether the process invoked or completed an explicit synchronization call. Buffered writes can reach persistent storage before such a call, so an unacknowledged transaction with a valid surviving commit can still be recovered as committed. The third row is the essential no-force benefit: committed data pages do not have to be installed before acknowledgment if durable replay information is sufficient. The fourth row demonstrates why client request identity belongs in the transaction. Recovery establishes database outcome; it does not deliver the missing reply retroactively.

The snapshot row needs a separate publication protocol. A simple engine can write a complete new snapshot to a separate generation, synchronize it, then atomically publish a durable manifest identifying that generation and its applied log position. The old snapshot remains available until the new manifest is safely installed. Atomic file replacement and directory durability depend on the operating system and filesystem; a real implementation must use documented primitives rather than assume that renaming implies every byte is persistent.

Atomic visibility is a different synchronization problem

Durable ordering does not by itself hide partial in-memory publication. If one thread writes Alice’s balance and is paused before writing Bob’s, another reader can observe a broken sum unless a visibility protocol prevents it. Serialized writers alone are insufficient because readers might still run concurrently. The earlier pseudocode therefore requires either a common execution boundary for readers and writers or a state publication mechanism with equivalent guarantees.

One teaching solution builds a new immutable root that references both new account versions and atomically publishes the root after durability. Readers hold one root for their entire read transaction. This avoids partial visibility but introduces version retention and reclamation obligations. Another solution uses a reader/writer gate around installation. That is easier to reason about but can delay readers behind writes. MVCC offers a richer design by associating changes with transaction visibility metadata.

This distinction matters when explaining the word commit. A transaction has a durable acceptance point and an externally visible state transition. Their relationship must satisfy the engine’s isolation and durability promises. A process can crash between them, so recovery must complete an accepted transaction even if no live reader saw it. Conversely, exposing a transaction before the promised durable point permits observations that disappear after a crash.

A system may explicitly offer such weaker durability for latency reasons. That can be a valid product option, but it changes the contract and must be reflected in acknowledgments and subscriptions. The guarantee should be expressed in observable failure behavior rather than an imprecise label such as fast commit.

WAL is an ordering constraint, not a file format

The essential dependency is that durable data changes must not outrun the recovery information they require. In a page-oriented design, each dirty page can carry a page log sequence number, or pageLSN. Before issuing a page write, the buffer manager forces the log through that position. A global durable-log watermark allows it to avoid flushing repeatedly if the necessary position is already covered.

write_dirty_page(page):
    copy_or_latch_stable_page_image(page)
    required = image.page_lsn
    ensure_log_durable(required)
    write_image_to_page_location(image)
    record_write_completion_without_losing_later_dirties()

The last line addresses a common race. A page can become dirty again while an older copied image is being written. Completing the old write must not mark the newer modifications clean. Generation counters or carefully synchronized dirty tracking distinguish the image that was written from the current buffer contents. Recovery ordering and buffer-state correctness meet at this boundary.

The log itself needs monotonic sequence allocation, bounded record sizes, robust handling of short writes, and a clear response to storage errors. A successful buffered write system call does not necessarily establish durability. A failed synchronization cannot safely be reported as a durable commit merely because the application changes are present in RAM.

A torn log record at the end can often be treated as an incomplete suffix according to the format. Corruption in the middle of previously accepted durable history is a different event. Silently skipping it could connect incompatible states or lose committed work. Recovery should fail safely or use a documented repair/redundancy path, preserving evidence for diagnosis.

Choose records according to replay semantics

Physical redo stores a resulting byte image or byte-level modification. Logical redo stores an operation such as inserting a key. Physiological logging associates a page with an operation within that page. Each choice changes replay dependencies and the amount of information needed when physical placement has changed.

A logical instruction balance = balance - 20 cannot be replayed blindly twice. A resulting value balance = 80 is idempotent only relative to the correct transaction order and target version: replaying it after a later legitimate balance of 75 would overwrite accepted work. PageLSNs, transaction identities, or an applied-prefix watermark establish where replay is needed. Idempotence is a property of the entire protocol, not simply of an assignment statement.

An index split illustrates why byte images alone may be awkward. Updating a parent, allocating a sibling, and moving records require recovery to preserve a navigable structure at every restart boundary. Some systems treat structural modifications with specialized logging and recovery rules. An application-level transaction log that says only “insert item” has not yet explained how an interrupted physical split is made safe.

Log records also need schema and encoding context. If software upgrades change how a value is represented, old log records must remain interpretable until they are no longer needed for restart, replication, or point-in-time recovery. A versioned record format can preserve that boundary. Upgrading the reader before writing the new format is a typical compatibility requirement, while downgrades may be restricted.

Steal and no-force change the recovery obligations

With steal, the buffer manager may persist an uncommitted modification to reclaim memory. A crash can then leave tentative bytes in data files. A traditional undo/redo design needs records that let recovery remove those loser effects. With no-force, committed modifications can remain only in buffers, so recovery needs redo. Combining steal and no-force offers flexibility but requires a well-specified recovery algorithm.

An MVCC engine may solve loser visibility through transaction status and version metadata instead of physically restoring every overwritten byte. That does not make the problem disappear: indexes, allocation metadata, transaction-status pages, and retained versions still need recovery rules. Statements such as “uncommitted writes are ignored” are meaningful only when the engine defines how all readers and maintenance paths recognize those writes.

For a no-steal private-write model, abort can discard the private set because shared committed pages never contained its effects. Memory use then grows with transaction write sets, and large transactions can exceed a simple budget. Spilling private data to separate temporary storage is possible but introduces cleanup, integrity, and commit-installation work. A simpler recovery explanation often trades complexity for memory or workload constraints.

The lesson is to choose a consistent set of policies rather than assemble isolated attractive properties. A private-write commit sketch, ARIES recovery phases, and an MVCC visibility rule cannot be mixed casually. Each describes assumptions about when and where changes become visible and persistent.

Group commit, backpressure, and latency

Consider a device that completes a particular durable synchronization in an illustrative 2 milliseconds. With one transaction per synchronization, the flush path alone permits about 500 flush cycles per second. Forty transactions sharing each cycle could support 20,000 committed transactions per second on that resource if log bytes and other work fit. The batch does not give each transaction a fifty-microsecond response time.

At constant high load, an arriving transaction may wait for the current flush, join a subsequent batch, and wait for its own durable watermark. The batch controller should report both batch wait and device wait. Under light load, a fixed delay of 2 milliseconds before every flush directly increases latency even if no other transaction arrives to benefit.

The log queue must be bounded. If incoming log bytes exceed sustainable writing or synchronization capacity, unbounded buffering postpones failure and amplifies recovery work. Backpressure can stop admitting new writers before memory exhaustion. A durable engine also needs an emergency policy when the device is full: failed transactions must not be acknowledged as committed, and existing accepted history must remain recoverable.

Long transactions require attention because they may generate much log data before commit. Reserving or limiting expected log space can prevent one writer from consuming the space needed for others to complete or abort. In undo-oriented systems, rollback can itself require log space, making an emergency reserve part of correctness rather than optional tuning.

A complete statement of the transaction boundary

For the transfer, the externally meaningful promise is that either both balances change and the operation result is recorded, or neither accepted change remains. It is insufficient to say that two SQL statements were issued within one function. The implementation needs an isolation rule for concurrent readers, a durable decision rule, a recovery interpretation for every crash point, and a safe client retry protocol.

The same checklist applies to a game inventory, a stock reservation, or a tenant quota. The business facts differ, but the engine must connect private state, shared visibility, logged history, and acknowledged outcome. Logging removes immediate data-page flushing from the foreground only because later recovery can reconstruct exactly the accepted history. That is the correctness argument behind its performance benefit.

Read the transaction timeline against durable progress

execution:   validate -> private mutations -> commit decision -> publish -> reply
log:                    append changes ----> append commit
storage:                                      flush through commit
pages:                                                       later checkpoint

The captioned flush must finish before publication and reply in the synchronous private-write model used here. Page installation can occur much later because replay has complete accepted mutations. In another engine, tentative physical updates can occur earlier, but their visibility and undo rules must then be supplied explicitly.

Suppose the append position is 1,000 while the durable position is 900. A transaction ending at 950 cannot receive a durable acknowledgment merely because its bytes exist in the log buffer. Once a successful flush advances durability to 980, it can be released along with any other covered commits. A transaction ending at 990 still waits. This watermark rule permits batching without confusing appended work with durable acceptance, and it remains valid even if transactions entered the flush queue in a different scheduling order.

Case connection and design conclusion

PostgreSQL’s WAL introduction documents the write-ahead principle and the separation between durable log records and later data-page writeback. ARIES describes a particular recovery architecture for fine-grained locking and partial rollback. The teaching protocol above is intentionally simpler and must not be mistaken for either implementation.

An atomic transaction design states where tentative state lives, how readers avoid partial visibility, what the log contains, when acknowledgment is legal, and how every crash point is interpreted. Lesson 20 adds concurrency through locks, increasing the number of interleavings that this atomic foundation must support.

Sources and further reading

• PostgreSQL 18 WAL introduction
• ARIES original paper, IBM, 1992

Course index · Lesson plan