WAL foundations: from a byte record to a durable decision

A transaction changes page 3 from ABC to xy. The page, an in-memory log buffer, and the durable log can each contain a different stage of that change. The first task is to encode its evidence unambiguously; later tasks decide when to persist and replay it. Passing a serialization test does not prove durability.

Preparation: index a byte slice, distinguish a byte from its printed hex, and read unsigned little-endian integers. You will derive a complete record layout, reject malformed records without panicking, and explain which persistence order permits recovery. Revisit the offsets below before attempting WAL Record Encoding.

Separate the storage responsibilities

Pages hold record bytes; the buffer pool holds resident copies; the WAL records changes; the index locates records; the transaction manager governs completion and access. A checksum detects some damaged bytes. It does not make them durable, prove a transaction committed, or enforce isolation.

In this course, an update record carries both before and after images. LSN orders records globally; Txn identifies a transaction; PrevLSN points to that transaction's previous record. If T7 wrote at 8 and T9 at 9, T7's update at 10 points to 8, not necessarily 9. A decoder reads this number; it cannot validate the transaction's history without the other records.

Derive the wire layout

Use half-open byte ranges: [a,b) includes a and excludes b. Fixed fields total 34 bytes. Every integer below, including the trailing checksum, is little-endian.

Range	Field	Worked update
[0,2)	Magic	57 4c (WL)
[2,3)	Type	02 (update)
[3,4)	Reserved	00
[4,12)	LSN	10: 0a 00 00 00 00 00 00 00
[12,16)	Txn	7: 07 00 00 00
[16,24)	PrevLSN	8: 08 00 00 00 00 00 00 00
[24,28)	PageID	3: 03 00 00 00
[28,30)	Offset	5: 05 00
[30,32)	BeforeLen	3: 03 00
[32,34)	AfterLen	2: 02 00
[34,37)	Before	41 42 43 (ABC)
[37,39)	After	78 79 (xy)
[39,43)	CRC32	IEEE checksum of bytes [0,39)

The complete record is 38 + BeforeLen + AfterLen bytes: 43 here. The length fields count payload bytes, not hex characters or the four checksum bytes. A non-update record is exactly 38 bytes because page, offset and image fields are zero. Encoding a Go struct's memory would introduce architecture/layout choices; write the documented fields instead.

The format's uint16 lengths can represent at most 65,535 bytes per image. The encoder returns nil for larger images or invalid record types. For begin, commit and abort (types 1,3,4), it ignores supplied update fields and emits their canonical zero values. The decoder rejects noncanonical wire records. These policies are explicit because the existing signatures have no encoder error.

Validate before publishing a record

Derive each check from an access or invariant:

1. Require at least 38 bytes before reading fixed fields or the checksum.
2. Require WL, type 1 through 4, and reserved=0.
3. Read the two uint16 lengths, widen to int, and require exact total length. This API decodes one complete record; trailing bytes are not another record.
4. Non-update records must have zero page/offset and no images.
5. Compare the stored CRC with crc32.ChecksumIEEE(data[:len(data)-4]).
6. Only then copy payloads into the returned record. Mutating the input buffer must not later change the decoded images.

A valid CRC does not replace checks 2–4. An unknown type with a freshly computed CRC remains unsupported. Checking only Decode(Encode(x)) is also insufficient: two functions can share the same wrong offset. Test an independently constructed byte vector as well as round trips. Go documents the exact checksum helper in hash/crc32.

Trace persistence, then crash

Start with durable pageLSN=8 and durable WAL through 8. T7 appends update 10, changes its cached page, appends commit 11, then acknowledges success.

Event	Durable WAL	Durable pageLSN	What is justified?
Append update to memory	8	8	Nothing new survives a crash
Flush WAL through 10	10	8	Updated page may now be written
Append commit to memory	10	8	Durable success cannot yet be acknowledged
Flush WAL through 11	11	8	Commit can be acknowledged without page flush
Crash before page flush	11	8	Recovery has the committed update to redo

The WAL rule requires durable log coverage through the page's latest change before writing that page. Durable commit acknowledgment also needs its commit record and preceding log records. PostgreSQL's WAL introduction explains log-before-data and why committed pages need not all be flushed. This course's before/after-image simulator is not PostgreSQL's recovery format.

No-force allows committed pages to remain only in memory, motivating redo. Steal allows uncommitted page changes to reach storage, motivating undo in this model. Neither policy says that appending a record equals flushing it. During redo, compare each record's LSN with the target page's pageLSN, not the largest LSN on another page. Later recovery modules teach transaction analysis, completed rollback, and compensation; the byte codec implements none of those.

Reconstruct with less help

A new update has Before=[9,8], After=[7,6,5,4]. Predict its total length, both payload ranges, and checksum range. Then explain why a commit record carrying the same images has a different encoding.

Check the layout

The update is 44 bytes. Before is [34,36), After [36,40), and CRC [40,44). The checksum covers [0,40). EncodeLog normalizes commit images/page/offset to zero, so its result is 38 bytes. DecodeLog rejects a wire commit that carries update fields even if its CRC matches.

Fresh diagnosis: durable log=25, cached pageLSN=27, transaction commit=28 still in memory. May the page flush? May the commit be acknowledged?

Check the persistence reasoning

Neither yet. Flush the log through 27 before the page write, and through 28 before durable commit acknowledgment. A CRC-valid in-memory commit is still volatile. Flushing through 28 satisfies both log-coverage requirements but does not itself write the page.

Implement the codec, take the checkpoint, then continue to slotted pages.