Durable Pages

Why this stage exists

Until now every page has lived in memory, and everything the program built was gone when it exited. A database is the thing that is still there the next time. This stage gives the pager a file, and it adds nothing else: no rows, no tree, no SQL. What the file holds is exactly the pages you already have, so the only new questions are where each page goes, when it is read, and when it is written.

It comes right after the pager, before the B+Tree, on purpose. Every tree stage after this one ends with a test that closes the program and opens the file again. Those tests can only mean something if pages already survive a restart, and if the file layer was tested on its own first, with pages whose bytes you chose yourself.

The classic mistake of this stage, stated up front: opening a file must never reset it. A program that treats every start as a new database, by truncating the file, zeroing the page count, or setting up page 0 again, passes every test in a single session and loses everything at the second one. The B+Tree will need a root in page 0, and it will create it only when the file has no pages at all. Everything in this stage is built so that the second session finds exactly what the first one left.

What changes: the file is the pages

The database file has no header and no index. It is the pages, one after the other, each at the offset its number gives:

Two things follow. The file's size tells you how many pages there are, so opening needs no scan: 12288 bytes is 3 pages. And a size that is not a multiple of 4096, such as 5000 bytes, cannot be a droid database: it is error 00604. Refuse it before the session starts, and do not "fix" it by cutting it short or padding it. A file you cannot read is still somebody's data.

A page allocated and never written is 4096 zero bytes in the file, like any other page. It is not skipped.

Choosing the file

--db <path> names the file; without it the file is droid.db in the working directory. --db may come before or after -c. A missing file is created empty, and an empty file is a database with no pages. Two paths share nothing.

The database is opened before the welcome line. When the file cannot be used, the program prints one error line, nothing else, and exits with status 1. A path that cannot be opened as a file, such as a directory, is 00603.

Reading a page on first use

Opening a file reads no page. A fresh session on a file of three pages says total_pages=3 cached=0. A page is read the first time a command needs it:

pager get is the only command that says which of the two happened. pager read and pager write load a page the same way, silently, and after either one the page counts in cached.

A write changes only what it writes

In the pager stage a write already left the bytes after its zero byte as they were. With a file behind the pager, that rule has a consequence: the page you write into has to be the page from the file. These are the first 16 bytes of page 0 in the file after one session wrote hello world and the next one wrote hi, without reading the page first:

This will matter as soon as a page holds more than one thing. A B+Tree leaf holds many rows, and inserting one must not wipe the others.

Saving when the session ends

A session ends in three ways: .exit, the end of input, or the end of the one command run by -c. All three save. Every page allocated or written during the session goes back to its offset; the rest of the file is not touched. A session that only reads, gets or asks for status leaves the file byte for byte as it was.

In this part nothing leaves memory before the session ends, so the end of the session is the one moment that must save. Writing a page back earlier, when memory runs short, comes with the Memory and Space part. What survives a crash in the middle of a session is the subject of the Transactions part.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, sections 2, 3, 7 and 8. The pager commands and their lines are the ones from the pager stage; this stage adds CACHE_MISS and three errors.

The file itself is part of the contract: page n at offset n × 4096, nothing else in it, and its size total_pages × 4096 after every session.

What you should see when done

Three sessions on the same file, the first two interactive, the last one a single command:

$droid --db demo.db
Welcome to droid!
>pager alloc
[PAGER] Alloc: page 0 (4096 bytes, zeroed)
>pager alloc
[PAGER] Alloc: page 1 (4096 bytes, zeroed)
>pager write 1 still here
[PAGER] Write page 1: 10 bytes
>.exit
exiting.. good bye!
$droid --db demo.db
Welcome to droid!
>pager status
[PAGER] Status: total_pages=2 cached=0
>pager get 1
[PAGER] Get page 1: CACHE_MISS (loaded from disk)
>pager get 1
[PAGER] Get page 1: CACHE_HIT
>pager read 1
[PAGER] Read page 1: 'still here'
>pager get 2
[ERROR:00601] Page 2 was never allocated
>pager status
[PAGER] Status: total_pages=2 cached=1
>.exit
exiting.. good bye!
$droid --db demo.db -c "pager read 0"
[PAGER] Read page 0: ''

The second session starts with nothing in memory and two pages in the file. Page 1 is a miss once, then a hit. The file is 8192 bytes after all three sessions, and the last two changed none of them.

A file that is not a whole number of pages is refused before the session starts:

$head -c 5000 /dev/zero > broken.db
$droid --db broken.db
[ERROR:00604] broken.db is 5000 bytes, not a multiple of 4096
$echo $?
1

The error messages are yours to word; the tests check only the codes.

Common bugs in this stage

• Opening truncates the file. Many "open for writing" modes empty the file first. The second session then finds 0 pages. Open for reading and writing without truncating, and create the file only if it is missing.
• Starting over on every run. Setting the page count to 0, or allocating page 0, whenever the program starts. The page count comes from the file's size, and a file with pages already has them.
• Reading every page at open. It works for three pages and wastes time for a thousand, and cached shows it: a fresh session must say cached=0.
• A write into a fresh buffer. Writing to a page of the file without reading it first saves zeros over the rest of the page. pager read still gives back the text, so only the file shows it.
• The wrong offset. Page n goes at n × 4096 bytes, not at the end of the file and not at n × the size of whatever you wrote. Writing only the bytes up to the text, instead of the whole page, leaves the file too short.
• Saving only on .exit. Input that ends without .exit, and every -c run, must save too.
• Nothing reaches the file. Written data can sit in a buffer inside the program or the language's library. If the program exits without flushing or closing the file, the bytes are lost.
• Writing back pages that did not change. Harmless to the bytes, but a session that only reads should not have to write at all. Keep track of which pages were allocated or written.
• "Fixing" a broken file. Rounding a 5000-byte file down to one page, or padding it to two, destroys what was there. Refuse it with 00604 and leave it alone, and make sure nothing saves on the way out.
• Printing the welcome line first. The file is opened, and checked, before anything is printed. A refused file prints its error and nothing else.

Language notes

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

• C: fopen mode "w+" truncates and "r+" fails when the file is missing; the POSIX open with read-write and create flags, and no truncate flag, does both jobs. fstat gives the size. fwrite buffers, so the bytes reach the file at fflush or fclose. fopen of a directory for reading only can succeed on Linux; opening it for writing fails.
• C++: an std::fstream opened with in | out fails when the file does not exist, and adding trunc empties it. Create a missing file first, then open it with in | out | binary. std::filesystem::file_size gives the size.
• Rust: OpenOptions with read, write and create, and without truncate, opens or creates without emptying. metadata().len() gives the size; seek with read_exact and write_all move whole pages. A File is closed when it is dropped, but a BufWriter around it must be flushed.
• Zig: createFile truncates unless its flags say .truncate = false, and it needs .read = true for reading. getEndPos gives the size; preadAll and pwriteAll read and write at an offset.
• Every language: the end of input is a normal way to end the session. Make sure the path that handles it saves, the same as .exit.