Function: writemeta in b-tree-storage-engine/btree.py

Date: 2026-05-29

Time: 10:58

writemeta — PageManager metadata page writer

Purpose

writemeta serializes the B-tree's global metadata into page 0 of the data file. Page 0 is reserved as the "superblock" — it holds the five integers that define the tree's current state. Every structural mutation (insert, delete, split, page allocation, page free) eventually calls this to persist the updated tree shape.

Contract

Preconditions:

• self._f is an open, writable file handle.
• All five arguments are unsigned 32-bit integers (0 to 2³²−1). This is not enforced — struct.pack('>5I', ...) will raise struct.error if a value is negative or exceeds 4 bytes.

Postconditions:

• Page 0 contains exactly self.page_size bytes: the 20-byte packed metadata followed by zero-padding.
• The data has been flushed to the OS buffer cache (but not fsynced to disk — a crash could lose it).

Invariant: Page 0 is always pagesize bytes and always starts with a valid METAFMT header.

Parameters

| Parameter | Type | Meaning |

|-----------|------|---------|

| root | int | Page number of the current root node. Starts at 1 (page 0 is metadata). |

| height | int | Tree height: 1 means the root is a leaf, 2+ means internal nodes exist above leaves. |

| total_keys | int | Total key-value pairs stored across all leaves. Maintained manually by callers. |

| next_free | int | Next page number to allocate when the free list is empty. Monotonically increases. |

| freehead | int | Head of the intrusive free list (a singly-linked list of deallocated pages). NOSIBLING (0xFFFFFFFF) means the list is empty. |

Return Value

None. This is a pure side-effect method.

Algorithm

1. Pack the five integers into 20 bytes using big-endian unsigned format ('>5I').

2. Pad to pagesize with null bytes via ljust. This ensures page 0 occupies exactly one page — the same size as every data page — so page arithmetic (pagenum * page_size) remains valid.

3. Seek to offset 0 — page 0 always lives at the start of the file.

4. Write the padded buffer.

5. Flush the Python-level buffer to the OS. This calls fflush semantics, pushing data out of Python's io.BufferedWriter into the kernel's page cache.

Side Effects

• File I/O: overwrites the first page_size bytes of the data file.
• File position: leaves the file cursor at byte page_size (just past page 0).
• No fsync: flush() does not guarantee durability. A power failure after writemeta but before os.fsync can lose the metadata update. The BTree class compensates by routing through walwritemeta, which logs to the WAL with fsync before writing the data file. However, PageManager.init calls write_meta directly during initialization — an unprotected write.

Error Handling

No explicit error handling. Possible exceptions:

• struct.error if any argument isn't a valid unsigned 32-bit int.
• OSError / IOError if the file write fails (disk full, closed handle).

Both propagate uncaught to the caller.

Usage Patterns

Two distinct call sites with different safety profiles:

1. PageManager._init_ — called directly during first-time file creation. No WAL protection exists yet; a crash here leaves a partially-initialized file. Acceptable because there's no data to lose.

2. PageManager.writemeta / BTree.writemeta — the public wrapper delegates here. The BTree class's walwritemeta logs to the WAL *before* calling this, providing crash recovery. allocatepage and freepage call write_meta directly (not through WAL), which is a durability gap — though these are always followed by WAL-protected writes in the put/delete paths.

Dependencies

• struct — binary packing via META_FMT ('>5I', 20 bytes big-endian).
• self.f — a raw file handle opened in init_.
• self.pagesize — determines the padding width; must be ≥ 20 (METASIZE).

Assumptions not enforced by types

• pagesize >= METASIZE (20 bytes). If page_size < 20, the ljust is a no-op but the packed data still overwrites into page 1's territory.
• Arguments represent a consistent tree state. Nothing prevents writing root=999 when only 3 pages exist — the corruption surfaces later on read.
• The file handle is open and writable. No check for closed handles.

Beliefs

• meta-page-is-page-zero — The B-tree metadata (root, height, totalkeys, nextfree, free_head) is always stored at file offset 0, occupying exactly one page
• meta-flush-without-fsync — writemeta calls flush() but not os.fsync(), so metadata writes are not durable against power loss unless the caller uses the WAL path
• meta-page-fixed-20-byte-payload — The metadata payload is always exactly 20 bytes (5 × 4-byte big-endian unsigned ints), zero-padded to page_size
• init-meta-unprotected-by-wal — During initial file creation, PageManager._init_ writes metadata and the root leaf page without WAL protection — acceptable because no user data exists yet
• allocate-free-bypass-wal — allocatepage and freepage call writemeta directly rather than through walwritemeta, relying on the caller's subsequent WAL commit for atomicity