8 Log structured store versus Write ahead logging

Write Ahead Logging and the CEDA LSS make fundamentally different choices about persistent layout and whether non-volatile durability lies on the normal transaction path.

Write Ahead Logging

Most conventional transactional database systems use Write Ahead Logging (WAL), commonly with ARIES or a similar recovery algorithm. WAL allows data pages to be updated in place while supporting transaction atomicity and crash recovery. A change is first represented in the WAL and is later written again as part of its data page.

Write-ahead invariant

The defining invariant is that a dirty data page must not reach persistent storage before every WAL record needed to recover that version of the page is persistent. A page may be changed immediately in the in-memory buffer pool, but before the page is written to storage the WAL must be flushed through the page's log sequence number. "Before" refers to persistence, not merely to the order in which the application issues writes.

For a strictly durable transaction, WAL also puts a flush on the commit path. The transaction's commit record must be written to the WAL and the WAL must be flushed through that record before commit can return successfully. The data pages need not be written at commit, but the thread cannot begin a causally subsequent operation that depends on successful commit until the WAL flush completes.

Performance consequences

With strict ACID durability, a successful WAL commit must wait for a flush that covers its commit record. If transactions are serialised, this puts one completed persistence barrier between successive transactions. Serialization may arise because one thread performs the transactions in sequence, because a later transaction causally depends on the earlier durable result, or because transactions contend on the same pages or other shared state. The achievable transaction rate is then bounded by flush latency, irrespective of the WAL's sequential transfer rate.

Group commit changes this only when the system has multiple transactions concurrently ready to commit and is allowed to hold them at the durability boundary together. It does not improve a genuinely serial stream in which the next transaction cannot proceed until the preceding commit is known to be durable. Asynchronous commit removes the wait only by relaxing the D in ACID. These are direct consequences of the force-at-commit design used by a synchronously durable WAL system.

WAL has further costs:

• Every change is written to the WAL and later written again in its data pages. In the basic case this means writing the changes twice, so effective write performance can be roughly halved. Log framing, page granularity, indexes, and check pointing can increase the write amplification further.
• The page writer must continually respect the write-ahead invariant, introducing coordination between WAL progress, dirty-page eviction, and check pointing.
• In-place page writes can be scattered. Lazy writers and page scheduling reduce the cost, but cannot make them equivalent to a single append stream. For typical HDDs and SSDs, the product of sequential bandwidth and I/O latency is commonly between about 64 kB and several megabytes. This latency-equivalent transfer size is usually much larger than a database page, so writing individual dirty pages tends to be dominated by I/O latency rather than transfer bandwidth. Sorting, batching, and concurrent I/O mitigate the effect, but require additional buffering and coordination and cannot make scattered page writes equivalent to the LSS append stream.
• In-place allocation makes variable-sized values awkward, particularly strings, which are extremely common in database records. A page representation must reserve a fixed amount of space, impose a size limit, move records when their strings grow, or store the string data separately. Separate storage introduces indirection and harms clustering, so reading one logical record can require access to data held elsewhere. When an object shrinks, its old allocation can leave unused space within the page. More generally, in-place update favours keeping objects at their previous physical locations, making compaction difficult and causing free space and live data to become fragmented over time.
• WAL is principally a recovery mechanism for in-place updates, which is the opposite of the natural requirement of Multi-Version Concurrency Control (MVCC): old versions must remain available while readers can still see them. WAL-based systems can implement MVCC, but must compensate using mechanisms such as undo records, copied tuples, version chains, and vacuum or garbage collection. These add indirection, write amplification, and reclamation work. If MVCC is a primary design goal, an in-place update architecture is therefore a poor starting point.

The durability barriers are implemented using the mechanisms described in Write ordering on storage devices. Volatile drive caches do not normally need to be disabled, but every layer of the storage stack must honour the barrier.

Log structured store

The CEDA LSS writes new and changed serial elements to the end of the log. The log is the persistent representation of the data; there is no separate set of in-place data pages to which every change must later be copied. Writes are large and sequential, serial elements can vary in size, and related values can be clustered together. Write performance is therefore typically limited only by the maximum sequential transfer rate of the storage device. The LSS performance measurements demonstrate this behaviour in practice.

The append model is also naturally compatible with MVCC. Updating an element creates a new rendition without requiring the previous rendition to be overwritten immediately. Readers can continue to use an older rendition while it is visible to them, and obsolete renditions can be reclaimed later by the cleaner. Cleaning copies live renditions out of sparsely used segments and recovers whole segments, so object shrinkage and relocation do not leave permanent holes at old physical locations.

Transaction path

Ordinary LSS transaction close does not flush the log. Transactions are serialised and atomic, and a subsequent transaction on the same thread can begin immediately, without waiting for a storage device. The lazy flusher advances durability independently in large sequential units. A failure can therefore lose a recent suffix of closed transactions, but recovery retains an atomic, internally consistent prefix.

This deliberate separation of transaction close from non-volatile durability is central to LSS performance. It allows the CEDA LSS to process about one million serial transactions per second using one thread. A strictly durable WAL transaction cannot follow the same path: its commit cannot return until its WAL record has crossed a persistence barrier. Comparing ordinary LSS transaction throughput with synchronous WAL commit throughput is therefore also a comparison of their intentionally different durability contracts, not merely their file layouts.

FlushWhenClose() is an exceptional escape hatch for code that must coordinate an LSS transaction with an external durable event. One example is two-phase commit, a blocking protocol that is expensive and impractical, and whose coordination and forced-durability costs make it a poor fit for the normal LSS model. FlushWhenClose() exists to make such exceptional integration possible, not to recommend it. When requested, it necessarily sacrifices the ordinary fast path and waits for the transaction and all preceding transactions to become durable.

Check-point publication

Check pointing is also outside the ordinary per-transaction path. During recovery the LSS validates the segment containing the check point referenced by the newest root-block division. If the segment is not valid through the recorded position, recovery rejects that division and reverts to the other root-block division. This makes an out-of-order root-block write recoverable while the preceding division and its reachable data remain intact.

The preferred publication protocol first makes the new check point's dependent log data durable, then writes and makes durable the root-block division that publishes it. This avoids unnecessary fallback and preserves the intended ordering without putting a flush into every transaction:

1. Write all data on which the new check point depends.
2. Issue and wait for a durability barrier covering those writes.
3. Write the root-block division that publishes the check point.
4. Issue and wait for a durability operation covering the root-block division.

The current RAS API has no explicit durability operation. Other Proposals proposes one for correct check-point publication and for the exceptional FlushWhenClose() path. CRCs, flush sequence numbers, and alternating root-block divisions allow recovery to reject many torn or inconsistent states, but do not themselves impose persistence order.