The Replication Log as the Ordering Unit in Single-Leader Replication

Two clients update the same account at the same moment. One increments it, one decrements it. If a replica receives those two operations in the opposite order, the final balance differs by the amount of the transaction, and the replica is wrong even though it applied exactly the same set of writes. The lesson is general: replication is not about shipping rows, it is about shipping an order. Every single-leader system therefore has one object at its centre, a log, and every replica is a replay of that log.

The leader serialises, and the log records the serialisation

A single-leader topology designates one node that accepts writes. That node already has to decide an order for concurrent transactions, because its local recovery depends on it: the write-ahead log is written before the pages it describes are modified, and redo replays it in order. Replication reuses that same artefact instead of inventing a second one. Each committed transaction is appended to the log as one or more records, and the append order is the serialisation order the leader chose.

This is a stronger statement than “the replica gets the same statements”. The leader’s order is a total order over all writes it accepted, including writes that were concurrent at the client. A follower applying that order reaches the same state as the leader because it is executing the same serial schedule, not merely the same set of operations.

The leader also has to decide what counts as a transaction boundary in the stream. A log record can carry part of a transaction, so the stream has a two-level structure: records, grouped into transactions, with the transaction end marker as the point at which the change becomes visible. A follower that applies half a transaction must not expose it to readers. This is why replay is tied to the same commit protocol as the leader’s own recovery, and why a replica that has applied the first record of a transaction still reports the transaction as absent.

A log record is a change, not a row

The record format is a design decision with consequences that reach the whole topology.

A physical log describes modifications to storage: which block in which relation, at which offset, with the before and after bytes. It is compact for updates that touch one row in a densely packed page, because it need not carry column names, types, or the whole row. It is also inseparable from the storage layout: a physical stream can only be replayed by a server whose page format, catalog layout, and major version match the sender’s. The consumer cannot be a different product, and often cannot be a different major version.

A logical log describes changes in terms of tables, keys, and column values. It survives a change of storage engine or version, can be filtered to a subset of tables, and can be consumed by something that is not a database server at all. It costs more bytes per change, because each record must be self-describing enough to be applied without knowledge of the page layout.

A statement log stores the SQL text that produced the change. It is by far the smallest for a statement that affects a million rows, and by far the most fragile, because the effect of the text depends on the state at execution time. The next article, statement-based and row-based logs, takes that failure apart.

Position is the clock

Every record carries an identifier that increases monotonically along the stream. In PostgreSQL the identifier is a log sequence number, a 64-bit value printed as two hexadecimal halves; in MySQL it is a pair of coordinates, the current binary log file name plus a byte offset inside it. The representation differs but the role is identical: the position is the only honest measure of how far a replica has got.

Wall-clock time is not a substitute. Two replicas can be at the same position at different times, and a replica’s clock can be wrong. A position, by contrast, is comparable across nodes: one replica is ahead of another if and only if its position is greater, because both are replaying the same stream. That comparability is what makes it possible to ask a replica to wait until it has reached a given position, and what makes a backup taken at a position a well-defined starting point for a new replica.

The position also defines the catch-up problem. A new replica cannot start at the current position, because it would miss everything before it and its state would be a suffix with no prefix. It starts from a base copy of the data taken at some position P, then replays from P. If the log has already been recycled past P, the copy is useless and the replica must be rebuilt. The window during which old log segments are still available therefore bounds how long a base copy remains usable, which is why operators keep a retention margin.

The retention margin has a cost that is easy to underestimate. The leader cannot discard log that any registered consumer still needs, so a single stalled replica pins the entire stream behind it. Storage then grows at the write rate, not at the retention policy’s rate. PostgreSQL makes this explicit with replication slots, which are durable registrations that survive a consumer disconnect; the slot guarantees the segments are kept, and the disk fills if the consumer never returns.

Followers as deterministic state machines

A follower is best understood as a state machine whose input alphabet is the set of log records and whose transition function is the apply routine. The model holds only if the transition function is genuinely a function of the record and the current state. Anything else reintroduces divergence:

• Evaluating now() inside the apply path, where leader and follower read different clocks.
• Choosing a row with LIMIT 1 and no ordering, where the planner may return different rows on two servers with identical data.
• Triggers or user-defined functions that read external state, a file, a sequence, or a network service.
• Allocating identifiers locally rather than logging the allocated value.

Physical and row-based logs avoid most of this by logging the values rather than the expressions that produced them. Statement logs cannot, which is why they impose a determinism requirement on the workload.

Replay also has to be crash-safe at record granularity. Each record carries its length and, in modern formats, a checksum over its bytes; a server that crashes mid-record discards the partial tail on restart and resumes at the last complete record boundary. Applying a record must be atomic with advancing the stored position, otherwise a crash between the two steps applies the record twice. The safe pattern writes both in one local transaction:

def replay(records, position, store):
    for rec in records:
        if rec.position <= position:
            continue                    # already applied before the crash
        if rec.position != position + 1:
            raise ReplayGap(position, rec.position)
        with store.transaction():       # effect and position commit together
            store.apply(rec)
            store.set_position(rec.position)
        position = rec.position

An apply routine that updates its position separately, or batches a hundred records and stores only the last position, is only safe if it can re-apply records idempotently. Most change records are not naturally idempotent: an increment applied twice is wrong, and a row image applied twice is fine only if it is a full after-image rather than a delta.

Where the ordering guarantee stops

The total order is per stream, not global. A system with sixteen shards has sixteen logs with sixteen independent orders, and no ordering relation between a write on shard 3 and a write on shard 7 unless something outside the log supplies one. Cross-shard invariants therefore need coordination that the log cannot provide, which is the subject of two-phase commit across shards.

Within one stream, a follower is always at some prefix of the log. It never holds the effect of record 900 without the effect of record 899. That prefix property is what gives per-follower read consistency: a read served by a single follower sees a state that existed on the leader at some earlier position, not a mixture of two states. It says nothing about reads spread across two followers, which may sit at different positions and therefore disagree.

The guarantee also weakens at the moment of a leader change. A new leader starts from whatever prefix it has, and if the old leader had acknowledged writes that the new one never received, those writes are gone. The log’s ordering survives; its continuity does not. Leader failover is the process of choosing where the new stream starts, and it is where the ordering model meets its hardest constraint.

Finally, the log describes changes, not the absence of them. A replica that has applied the whole stream has the leader’s data, but a replica that has applied a prefix and is asked a question whose answer depends on later records will answer as of that prefix. Replication lag is not an error in the mechanism; it is the mechanism working as designed, and the applications that read from followers must be written to tolerate it.