Neon: page versions from WAL, branches for free

Aurora’s idea, reimplemented for stock Postgres, in Rust, in the open — the best codebase to read for this topic. Compute streams WAL to a safekeeper quorum for durability; a pageserver indexes page versions by (key, LSN) and reconstructs any page at any LSN on demand, which is also why a branch costs O(1). This chapter builds those pieces step by step — the Postgres contract Neon hooks into, the durability/serving split, the version index, reconstruction, and branches — then hands you the anchors to walk both crates. Every anchor below was re-verified against the pinned neon clone at 8f60b04.

The problem in one sentence

Give stock Postgres bottomless, branchable storage without touching the engine: commits must be durable at local-disk speed (so S3’s ~14 ms median — our measured raw-S3 p50 — stays off the commit path), any page must be readable as of any point in history, and creating a copy-on-write branch of a multi-TB database must cost O(1), not O(size).

The concepts, step by step

Step 1 — the Postgres contract: WAL in, pages out

In: an unmodified Postgres and an UPDATE. Out: the two-sided contract Neon must honor — accept the WAL stream, answer GetPage@(key, LSN) — and the single Postgres interface (smgr) it hooks to do it. Ground floor for every later step.

Postgres stores tables as 8 KB pages and, before touching any page, appends a WAL record (write-ahead log — a small description of the change) at a monotonically increasing byte offset called the LSN (log sequence number). Every page version is therefore addressable as “page X as of LSN N”, and any version is derivable from an older copy plus the WAL records in between (REDO, topic 5). Postgres also has a narrow storage-manager interface (smgr) — “read page / write page” — that Neon replaces with a network hook. That is the entire integration surface: Neon receives the WAL stream and must answer one question, GetPage@(key, LSN), where key identifies the page. Compute stays stateless: its local disk is pure cache.

Step 2 — split durability from serving: safekeepers and the pageserver

In: the WAL stream and the GetPage@(key, LSN) obligation from Step 1. Out: the two separate services those two jobs are handed to, sized for opposite requirements (the Socrates lesson), and which one is on the commit path.

The write path and the read path get different services:

 Postgres (unmodified + smgr hook)
   │  WAL (streamed, synchronous quorum)          GetPage@(key, LSN)
   ▼                                                     ▲
 safekeepers ×3 ── consensus on WAL ──► pageserver ──────┘
   (durability NOW)                       │  ingests WAL -> delta layers
                                          │  compacts    -> image layers
                                          ▼
                                         S3 (all layers, all history)

A commit is durable the moment a quorum (a majority — 2 of 3 in the standard deployment) of safekeepers — small nodes whose only job is landing WAL on fast disks, coordinated by a term-based, Raft-flavored protocol (“Paxos-ish” per their docs; the on-the-wire message is AppendRequest, which also carries commit_lsn) — has the record. Commit latency never touches S3. The pageserver consumes the WAL stream asynchronously: it may lag, crash, or be rebuilt, because everything it holds is derivable from WAL + S3. Rosetta to the previous chapters: safekeepers = Socrates’ XLOG landing zone, pageserver = page servers, S3 = XStore — the same decomposition, arrived at independently.

Step 3 — the pageserver is an LSM over (key, LSN)

In: the WAL stream the pageserver ingests (Step 2). Out: the two-dimensional (key × LSN) index it stores that history in — delta layers and image layers — and the LSM shape that makes it familiar.

The pageserver’s job is to index page versions, so its key space is two-dimensional: (page key × LSN). It stores that history in two kinds of immutable layer files, each covering a rectangle of that space: delta layers hold raw WAL records sorted by (key, LSN); image layers hold fully materialized pages (the actual 8 KB bytes) as of one LSN. Fresh WAL is ingested into delta layers; compaction periodically produces image layers so history doesn’t have to be replayed from the beginning; old layers are uploaded to S3 and dropped from local disk; GC deletes history below the retention horizon.

The mental model: an LSM (topic 4) over the key space (key, LSN) — delta layers = level files, image layers = the compacted form — topic 4 for the third time, after GIN pending lists and differential arrangements (topic 27 notes). LayerMap::search(key, end_lsn) is the 2-D lookup that answers “which layers can contain versions of key at or below end_lsn”.

Step 4 — reconstruction: REDO on the read path

In: the (key, LSN) layer index from Step 3 and a GetPage@(key, LSN) request. Out: the reconstruction algorithm — one image layer plus a replay of the deltas above it — and which cost it puts on the read path.

GetPage@(key, LSN) is answered by rebuilding the page: find the newest image layer at or below the requested LSN, collect every delta (WAL record) between that image and the LSN, and replay them — using an actual sandboxed Postgres subprocess (walredo) as the replay engine, so Neon never reimplements record semantics. Topic 5’s REDO, promoted from crash recovery to the everyday read path. The loop, reduced:

#![allow(unused)]
fn main() {
// ILLUSTRATION — not literal neon code. The real gather+replay lives in
// pageserver/src/tenant/timeline.rs:4491 (get_vectored_reconstruct_data)
// with the ancestor walk at :4548; replay is walredo.rs:173/:473.
fn get_page(tl: &Timeline, key: Key, lsn: Lsn) -> Page {
    let (mut tl, mut lsn) = (tl, lsn);
    let mut deltas = vec![];
    loop {
        match tl.layers.search(key, lsn) {            // 2-D (key × LSN) search
            Found::Image(img) => {                    // ONE image suffices...
                return walredo(img, deltas);          // ...replay deltas on it
            }                                         //    (REDO on the READ path)
            Found::Delta(rec, below) => {             // collect, keep descending
                deltas.push(rec); lsn = below;
            }
            Found::Nothing => {                       // not born on this timeline:
                lsn = tl.ancestor_lsn.min(lsn);       // ask the parent, capped at
                tl = tl.ancestor();                   //   the branch point
            }
        }
    }
}
}

The cost gradient: a read needs at most one image layer but possibly many delta layers — concretely, every WAL record written to key since the last image at or below lsn must be replayed, so if compaction last cut an image for key at L0 and the request asks for L0 + K bytes of WAL, walredo replays exactly the records in that K-byte window. So compaction (creating fresh image layers) is what caps read latency (Q1). One more subtlety: because the pageserver may lag the safekeepers, compute sends the LSN it needs with each request, and the pageserver waits until it has ingested up to that LSN rather than serving a stale page (Q3).

Step 5 — branches: a branch is two numbers

In: the immutable, LSN-indexed layer history from Steps 3–4. Out: why creating a branch is O(1) — it writes two numbers and copies nothing — plus the two costs (deep ancestor walks, harder GC) that buys.

A branch (timeline) is metadata: (parent timeline, branch LSN) — created in O(1), copying nothing, because history is already immutable and indexed by LSN (Step 3). Concretely, branching a 1 TB database copies zero bytes; it writes one (ancestor_timeline_id, ancestor_lsn) tuple. Reads on a child that miss its own layers fall through to the parent, capped at the branch LSN — the Found::Nothing arm in the Step 4 loop, and exactly our branch.rs stub. The same trick as Snowflake’s file-list clones and SlateDB’s manifest-reference clones, at page granularity.

Two costs to watch: a deep branch chain makes reads walk many ancestors (Neon bounds this by materializing image layers into child timelines over time — Q4), and GC gets harder — a layer may be garbage for the child but live for the parent, so every child’s branch LSN becomes a retain point (Q2).

Where each step lives in the code

All line numbers verified against the pinned clone neon@8f60b04.

Pageserver anchors (Steps 1, 3–5, the read path):

For Q2, also look at how gc_info.insert_child (tenant.rs:591, inside from_timeline at :585) registers ancestor_lsn as a retain point.

Safekeeper anchors (Step 2, the write path):

Socrates rosetta: safekeepers = XLOG landing zone; pageserver = page servers; S3 = XStore. Same decomposition, independent arrival.

Questions to answer in notes.md

Q1. LayerMap::search answers “newest layer that could hold (key, ≤ lsn)”. Why does reconstruction need at most ONE image layer but possibly MANY delta layers, and what does compaction (creating new image layers) buy — in our tier_bench vocabulary, which lane’s latency does it cap?

Q2. Branches make GC hard: a layer can be garbage for the child but live for the parent (or vice versa). Look at how gc_info.insert_child (tenant.rs:591) registers ancestor_lsn as a retain point. State the GC rule in one sentence. (Keep everything ≥ min over children’s branch LSNs and the PITR horizon.)

Q3. Commit waits for a safekeeper quorum only — the pageserver may lag. What read anomaly does GetPage@LSN prevent that a lagging page service would otherwise cause, and what does compute have to send with each read request to get it? (The LSN it needs — reads wait for the pageserver to catch up to that LSN rather than returning stale pages.)

Q4 (M28). Our branch.rs stub resolves get(branch, page, lsn) by walking parents. Neon avoids unbounded walks: image layers get copied down (materialized) into child timelines by compaction over time. When would M28’s graph branches need the same trick — what query pattern makes a 64-deep ancestor walk show up, and what’s the graph equivalent of an image layer (a materialized matrix snapshot at the branch point)?

Done when

Answer each before unfolding it.

• You can state the Postgres contract Neon preserves: WAL in, pages out.

  Answer

  Postgres appends WAL records (each at a monotonic LSN) before touching 8 KB pages. Neon keeps that untouched and replaces only the smgr read/write hook: it ingests the WAL stream and must answer GetPage@(key, LSN) — any page as of any LSN. Compute stays stateless; its local disk is only a cache.

• You can explain the safekeeper/pageserver split as durability against serving.

  Answer

  Safekeepers land WAL on fast disk under a term-based majority quorum — that is what makes a commit durable, and S3 never touches the commit path. The pageserver ingests that WAL asynchronously to serve pages; it can lag or be rebuilt because everything it holds derives from WAL + S3. Durability tier ≠ serving tier — the Socrates split, reached independently.

• You can explain why the pageserver is an LSM keyed by (key, LSN).

  Answer

  It indexes page versions, so the key space is (page key × LSN). Fresh WAL lands in delta layers (records sorted by key, LSN); compaction cuts image layers (materialized pages at one LSN); old layers go to S3. Delta = level files, image = compacted form — an LSM over a 2-D key space, queried by LayerMap::search.

• You can explain reconstruction: REDO on the read path, and what it costs a cold read.

  Answer

  Find the newest image layer ≤ the requested LSN, collect every delta between it and the LSN, and replay them in a sandboxed walredo Postgres subprocess. Cost = one image read + N delta replays, where N is the WAL written to that key since the last image — so compaction frequency caps read latency. A cold read that must also fetch layers from S3 pays the ~14 ms S3 GET on top.

• You can explain why a branch is two numbers, and what that makes free.

  Answer

  A branch is a timeline recording (parent timeline, branch LSN) — branch_timeline_impl writes that tuple and copies zero bytes, even for a multi-TB database, because history is already immutable and LSN-indexed. Reads that miss the child’s own layers fall through to the parent capped at the branch LSN. The costs are deeper ancestor walks and harder GC (each branch LSN is a retain point).

References

Code

• neon — pageserver + safekeeper crates (Rust), pinned at 8f60b04; read-path anchors in pageserver/src/pgdatadir_mapping.rs, tenant/timeline.rs, tenant/layer_map.rs, tenant/storage_layer/, pageserver/src/walredo.rs; write path in safekeeper/src/. Every file:line above was re-verified at that commit with tools/pinned-source.py.
• Neon architecture posts and in-repo docs/ (skim the pageserver-storage and WAL-service design notes) for the safekeeper consensus and layer-map details in prose.