Pager and Buffer Pool

Why this stage exists

The previous stage turned a row into 60 bytes. Those bytes need somewhere to live, and the somewhere cannot be "wherever the language puts things": the next stage writes them to a file and a later run of the program reads them back. A file is read and written in fixed-size blocks, so the engine is built on the same idea. Storage is a sequence of pages of 4096 bytes each, named by number: page 0, page 1, page 2.

The pager is the one component that owns the pages. Every other layer asks it for page N and gets back that page's bytes; nothing else allocates a page or decides where one lives. In this stage the pages live in memory only. That is on purpose: numbering, bounds and the bytes of a page can be checked on their own, before a file adds the question of what is on disk and what is not.

Nothing else in the engine uses the pager yet. The B+Tree, from the btree-leaf stage on, stores its nodes in pages, one node per page, and asks for them by number.

What changes: numbered pages of bytes

A page is 4096 bytes and nothing else: no type, no header, no length. What a page means is decided by whoever writes it. For now that is you, with two debug commands: pager write puts a text at the start of a page followed by a zero byte, and pager read reads up to the first zero byte.

These are the first 16 bytes of page 0 after pager write 0 hello world, then pager write 0 hi:

The old bytes staying in the page is not a bug. A page is storage, not a string: writing to it changes the bytes you write and no others. Later stages rely on exactly that when they update one cell of a page and leave the rest alone.

Pages are named by number

A page number is a position: page 5 is the sixth page. It is never an address in memory. The next stage makes this matter, because page 5 is then the 4096 bytes at offset 5 × 4096 in the file, and that has to be true in every run of the program. So allocation always gives the next number, 0, 1, 2, in order, with no gaps, and a number that was never handed out names nothing.

A limit, and bounds

The pager holds at most 1000 pages. The 1001st allocation is error 00602: refused, not crashed, and the 1000 pages that exist are untouched.

Asking for a page that was never allocated is error 00601, whether it is the page just after the last one or page 999 of an empty pager. It is not a reason to allocate the page. A lookup that quietly creates what it looked for hides the bug that asked for the wrong page.

Why "buffer pool" and "cache hit" already

pager get reports CACHE_HIT and pager status reports how many pages are cached. In this stage every allocated page is in memory, so cached always equals total_pages and every get is a hit. The words are there because the next stage changes the answer: once pages come from a file, a page that has not been read yet is a CACHE_MISS, read from disk on first use. Later still, when the file can hold more pages than memory, the pager keeps some of them and lets others go, and the page table becomes a real buffer pool. The page table you build now is the thing those stages extend.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, sections 3 and 7.

A fresh start has total_pages=0 cached=0. cached counts the pages in memory, which in this stage is every allocated page. The text of pager write is the rest of the line after the page number and one space, spaces inside it included. A page nothing has written reads back as ''. An error changes nothing: no page is allocated, no byte is written.

What you should see when done

Welcome to droid!
>pager status
[PAGER] Status: total_pages=0 cached=0
>pager alloc
[PAGER] Alloc: page 0 (4096 bytes, zeroed)
>pager alloc
[PAGER] Alloc: page 1 (4096 bytes, zeroed)
>pager write 0 hello world
[PAGER] Write page 0: 11 bytes
>pager write 0 hi
[PAGER] Write page 0: 2 bytes
>pager read 0
[PAGER] Read page 0: 'hi'
>pager read 1
[PAGER] Read page 1: ''
>pager get 1
[PAGER] Get page 1: CACHE_HIT
>pager get 2
[ERROR:00601] Page 2 was never allocated
>pager get -1
[ERROR:00104] Not a page number: -1
>pager status
[PAGER] Status: total_pages=2 cached=2
>.exit
exiting.. good bye!

Three things to notice. hi written over hello world reads back as hi, although most of hello world is still in the page. Page 1 reads back empty after page 0 was written: pages share nothing. And the failed get 2 did not create page 2; the count is still 2. The error messages are yours to word; the tests check only the codes.

Common bugs in this stage

• Printing without storing. A counter and a few print statements pass status and alloc, and fail every write and read case. The page has to be real bytes.
• A page smaller than 4096 bytes. A short fixed field holds hello world and truncates a 4000-byte text. Give every page all 4096 bytes.
• New pages that are not zero. Memory from the language's allocator may hold whatever was there before. pager read of a new page must be '', so zero the page when you allocate it.
• One buffer shared by every page. Writing page 0 then reading page 1 gives page 0's text. Each page number needs its own 4096 bytes.
• No zero byte after the text. hi over hello world reads back as hillo world. The write puts a zero after what it copied.
• Off by one at the last page. With 2 pages, page 1 exists and page 2 does not. The valid numbers are 0 up to one less than the count.
• A lookup that allocates. pager get 5 on a pager with 2 pages creates pages up to 5, or bumps the count. An error changes nothing.
• A crash on a bad number. abc read as 0, or -1 wrapping around to a huge unsigned number and indexing past the page table. Check the argument is digits before you use it as a number.
• The 1001st page. Checking the limit after allocating, so page 1000 exists for a moment, or the count reads 1001.

Language notes

The page above is the same for every language. These are the only language-specific hints.

• C and C++: calloc returns zeroed memory; malloc does not. A table of pointers to pages lets each page stay where it was allocated. Parse page numbers with a function that reports where it stopped, such as strtoul with its end pointer, and reject a leading - yourself: strtoul accepts it.
• Rust: vec![0u8; 4096] or Box::new([0u8; 4096]) gives a zeroed page. str::parse::<u32> rejects -1 and abc for you.
• Zig: allocator.alloc(u8, 4096) does not zero the memory; @memset(page, 0) does. std.fmt.parseInt(u32, text, 10) returns an error for -1 and abc.
• Every language: if pages live inline in a growable array, adding a page may move all of them in memory. Nothing holds on to a page across commands yet, but the B+Tree will. Keeping each page in its own allocation avoids the problem.