CSE Roadmap

Core tier · about 3 hours · 8 parts

Part 7 of 8 · 4 min read

How the log is built

Statement, WAL shipping, logical and trigger-based replication.

How the log is built

Think of two ways to tell a friend how to rebuild a Lego house. You can send the instructions you followed ("put a red brick on the left") or a list of exactly which bricks sit where now. The first is short but depends on the friend having the same set of bricks and following in the same order. The second is longer and always gives the same house.

The book describes four ways to build the replication log.

Statement-based replication. The leader logs every write statement it runs (INSERT, UPDATE, DELETE) and sends it to the followers, which run it again. It breaks in several cases:

  • Statements with non-deterministic functions, such as NOW() or RAND(), give different values on each replica.
  • Statements that depend on existing data or on auto-incrementing columns must run in exactly the same order everywhere.
  • Statements with side effects (triggers, stored procedures) may act differently on each replica.

Workarounds exist, such as replacing function calls with fixed values in the log, but there are so many edge cases that other methods are now preferred. MySQL used this before version 5.1, and VoltDB uses it by requiring deterministic transactions.

Write-ahead log (WAL) shipping. The storage engine already writes every change to an append-only log (Level 2, module 4). The leader sends this same log to followers, which build identical data structures. PostgreSQL and Oracle do this. The drawback: the log describes which bytes changed in which disk blocks, so replication is tied to the storage engine. If the format changes between versions, leader and followers usually cannot run different versions, and a zero-downtime upgrade (upgrade followers, then fail over) is not possible.

Logical (row-based) log. A separate log format that describes changes row by row. For an inserted row it holds the new values. For a deleted row, enough to identify it, usually the primary key. For an updated row, the identity and the new values. A transaction that changes several rows produces several records and then a commit record. MySQL's row-based binlog does this. Because it is separate from the storage engine, it stays compatible across versions, and it is easy for outside programs to read. This enables change data capture: sending the contents of a database to another system such as a data warehouse, or to build custom indexes and caches.

Trigger-based replication. A trigger runs custom application code when data changes and records the change in a table for an outside process to read. This gives flexibility: copy only part of the data, copy to a different kind of database, or add conflict-handling logic. It has more overhead and is more prone to bugs than built-in replication.

Method Strength Weakness
Statement Compact Non-determinism and order problems
WAL shipping Exact copy, simple Tied to storage format and version
Logical (row) Independent of storage engine, readable by other tools Larger than statements for big updates
Trigger Flexible Overhead and bugs

A worked example of size. A statement UPDATE accounts SET bonus = 10 WHERE region = 'north' changes 100,000 rows. As a statement, the log entry is about 60 bytes. As row-based records of 40 bytes each, it is 4,000,000 bytes, about 4 MB. The statement is shorter, but it is only safe if every replica evaluates it the same way.

Interview angle

Answer in your head first, then open it.

Why replicate a database?

Availability, read capacity and latency. Give the read-capacity arithmetic and note that writes still go through one leader.

Synchronous or asynchronous?

Describe semi-synchronous: one synchronous follower nearby for durability and asynchronous ones elsewhere. State the data that can be lost under pure asynchronous replication.

What happens when the leader fails?

Detect by timeout, choose the most up-to-date follower, redirect clients, fence the old leader. Name lost writes and split brain.

How does a new follower catch up?

Consistent snapshot plus the log from the snapshot's position.

Which log format would you pick?

A logical row-based log, for version independence and change data capture. WAL shipping if the same version is guaranteed and simplicity matters.

Check yourself:

  • Why can statement-based replication give different data on different replicas?
  • Which log type is easiest for an outside system to read, and what use does that allow?

Words you will meet

Word Plain meaning
Replica A node that holds a copy of the database
Replication Keeping copies in step as data changes
Leader (primary, master) The replica that accepts writes
Follower (secondary, read replica) A replica that copies the leader and serves reads
Replication log The ordered list of changes the leader sends to followers
Synchronous replication The leader waits for a follower before confirming the write
Asynchronous replication The leader does not wait for followers
Semi-synchronous One follower is synchronous and the rest are asynchronous
Snapshot A consistent copy of the database at one moment
Catch-up recovery A follower asks the leader for changes since its last log position
Failover Promoting a follower after the leader fails
Split brain Two nodes both believe they are the leader
Fencing Shutting down or blocking a node that must not act as leader
Logical (row-based) log A log of row changes, independent of the storage engine
Change data capture Sending a database's changes to another system
Consensus Getting several nodes to agree on one value