Write-ahead logging (redo)

How does a write-ahead log turn many random durable writes into one sequential write, and why does redo exist?

Start from the cost, not from the definition.

A transaction changes k pages that are scattered over the address space. To make it durable by writing those pages, you must force k independent locations. So

and the cost of one force is dominated by a fixed part per force (on a disk: seek and rotation; on flash: program and flush), not by the number of bytes. With k = 8 and a 5 ms force, one transaction costs 40 ms. Different transactions touch different pages, so they cannot share the work.

Remember the rule: a fixed cost per operation creates a natural batch size. The ideal batch would be "all recent writes of the whole system". But those writes are spread across the address space, which is exactly what makes them impossible to batch.

So we change what we write. Instead of the new state of the pages, we write a compact, ordered description of the change to one append-only location (a file where we only add at the end). That file is the write-ahead log (WAL), also called the redo log. Now k random forces become one sequential force, whatever k is. The data pages still must be written at some point, but "later" is a time we choose, and then we can sort them, merge them, and write them in bulk.

That is the whole idea:

The cost is conserved (never removed, only moved). It moves from commit latency into: extra space (the log), extra background I/O (the later page writes), and recovery time.

A tiny sketch of the idea in pseudo-code:

def commit(txn):
    records = describe_changes(txn)       # e.g. "page 17: balance 100 -> 70"
    log.append(records)                   # sequential, at the end of the log file
    log.force()                           # ONE durable write: now we may say "yes"
    return "OK"                           # data pages are still dirty in memory

def background_flusher():                 # runs later, in bulk, sorted by page number
    for page in sorted(dirty_pages):
        write_to_disk(page)

If the machine crashes after log.force(), the pages are lost from memory, but the log is on disk, so recovery can replay (apply again) the log records to rebuild them. This is called redo.

Why redo is needed at all (the buffer-manager derivation)

The usual textbook explanation is a list of rules. A cleaner explanation comes from two policies of the buffer manager (the component that keeps pages in memory and decides when to write them):

• No-steal: never write to disk a page that was changed by an uncommitted transaction. Then you never need undo (see next section). But no transaction can be bigger than memory, and the memory pressure is severe.
• Force: when a transaction commits, write all its changed pages to disk. Then you never need redo. But you have just paid the k random forces that you wanted to avoid.

The standard recovery design, ARIES, chooses steal (pages of uncommitted transactions may reach disk) and no-force (commit does not write the data pages). That choice requires both logs. Undo exists because you steal. Redo exists because you do not force. So redo and undo are not two unrelated mechanisms. They are two consequences of one decision.

Logging granularity

What exactly goes into a log record? Three styles:

Almost every real engine (ARIES, InnoDB) converges on physiological logging.

To make replay safe, each page stores the LSN (Log Sequence Number: the position of a record in the log) of the last record applied to it, called pageLSN. During replay, a record is applied only if

pageLSN < recordLSN

This is a monotonic version counter used to make a non-repeatable operation safe to retry. It is the same device as the sequence number used in exactly-once message delivery. (This idea will matter again for fuzzy checkpoints.)

What the WAL assumes but cannot verify: that the order in which the log device accepted appends is the order in which it will read them back after a crash. Who pays when this is false: everyone, silently, at the next recovery.