Series: nosqlite devlog, Part 3
Once I had page zero written to disk with those magic bytes NOSQLITE_DB___P8, I had a brief moment of satisfaction. I opened a hex editor, saw my custom signature staring back at me, and felt like I was actually getting somewhere.
Then reality set in.
I had an empty file with a header and absolutely no way to store anything useful yet. If you open a database, what is the very first thing you do? You create a collection. In SQL, you write CREATE TABLE. In MongoDB, you just start writing to a collection or create one explicitly. But what actually is a collection when you are sitting in front of a raw binary file?
It is not a folder on your hard drive. It is not some magical in-memory table. At the byte level, a collection is just a string name tied to a starting page number somewhere inside that single file.
My first lazy thought when planning this was tempting: why not just keep a HashMap<String, Vec<Document>> in memory and dump it to disk as a JSON blob when the program exits?
That would have taken an hour to write. But that is what you do if you are building a toy in Python or Node, and it completely misses the point of this experiment. If the power cuts out, your in-memory map is gone. If you copy the database file to another computer, that catalog has to travel with it inside the exact same file. The file has to be completely self-contained. It has to know its own collections, where they live, and how many documents they hold.
That meant building a catalog page.
The Table of Contents for Your Database
Think about a book. Before you read chapter three, you flip to the table of contents. The table of contents does not contain the story. It just tells you: Chapter 3 starts on page 45.
The catalog in nosqlite is literally just that table of contents.
For every collection you create, the engine needs to remember exactly three things:
What is the collection's name?
What page number does its first document live on?
How many documents are currently inside it?
That is all. If you know those three things, you can find the data, display counts in the shell, and know where to start scanning.
Where does this table of contents live? It gets its own dedicated page in the file. Specifically, it lives on page 1, sitting right after the file header. If you remember from the previous article, the file header on page 0 stores a field called catalog_page that holds the value 1. When the database boots up, it reads page 0, checks catalog_page, and immediately loads page 1 into memory.
The Anatomy of the Catalog Page
Let us look at how page 1 is laid out in memory and on disk.
// Catalog page layout:
//
// +-------------------------------+
// | Page Header | 16 bytes (generic header on every page)
// +-------------------------------+
// | collection_count (u32) | 4 bytes (how many collections exist)
// +-------------------------------+
// | entries... | packed one after another
// +-------------------------------+
//
// Each entry looks like this:
//
// +-------------------------------+
// | collection_name (\0) | variable length, null-terminated
// +-------------------------------+
// | first_document_page (u64) | 8 bytes
// +-------------------------------+
// | document_count (u64) | 8 bytes
// +-------------------------------+
The first 16 bytes belong to the generic page header that every single page in nosqlite has. That header records the page number, the page type (in this case, PageType::CollectionCatalog), and a couple of reserved bytes.
Right after those 16 bytes, we store 4 bytes for collection_count. This is an unsigned 32-bit integer that tracks how many collections currently exist in the database.
Why do we need this count? Because without it, a loop reading through the file would have no idea when to stop. It would keep reading random bytes until it crashed or hit corrupted memory. With collection_count, the reader knows upfront: there are 3 collections here, so read exactly 3 entries and then stop.
The catalog header size is therefore 20 bytes:
pub const CATALOG_HEADER_SIZE: usize = PAGE_HEADER_SIZE + 4; // 16 + 4 = 20
Since a page is 4096 bytes total, that leaves 4076 bytes for collection entries. In an embedded database where you usually have five, ten, or maybe thirty collections, 4076 bytes is plenty of room.
Null Terminators and C Strings
Here is the struct that represents a collection entry in Rust:
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct CatalogEntry {
pub name: String,
pub first_document_page: u64,
pub document_count: u64,
}
In Rust, this looks clean and friendly. But when this struct gets serialized into raw bytes on disk, we have to make an important choice: how do we store the string name?
In modern high-level languages, a string always carries its length with it. But at the raw binary level, there are two classic approaches. You can either use a Pascal string, where you write a length byte first and then the characters, or you can use a null-terminated C string, where you write the characters and end with a literal zero byte (\0).
I chose the null-terminated C string approach.
When you create a collection named "users", the engine writes the ASCII bytes for u, s, e, r, s, followed by 0x00. In hex, that is 75 73 65 72 73 00. That zero byte acts as a red light for the reader. The reader walks forward byte by byte, and the instant it sees a zero, it knows the name is finished.
Right after that zero byte, we write 8 bytes for first_document_page and 8 bytes for document_count, both encoded as little-endian unsigned 64-bit integers.
This brings up a fascinating detail about variable-length binary layouts. Because collection names can have different lengths, the entries do not have a fixed size. A collection named "users" takes 6 bytes for the name plus 16 bytes for the two u64 numbers, totaling 22 bytes. A collection named "audit_logs_v2" takes 14 bytes for the name plus 16 bytes for the numbers, totaling 30 bytes.
Because of this, you cannot simply calculate an offset with math like index * entry_size. You cannot jump directly to the fifth collection. You have to start at byte 20 and walk forward with a cursor, reading each entry to know where the next one begins.
Why the Catalog Struct Is Completely Empty
When you look at the source code in crates/nosqlite-core/src/catalog/catalog.rs, you find something that might look bizarre at first:
pub struct Catalog;
The struct has no fields. It holds no data in memory. It is a zero-sized type.
Every single method on Catalog takes a reference to a Page or Pager and acts directly on the byte buffer:
impl Catalog {
pub fn initialize(page: &mut Page) {
page.set_page_type(PageType::CollectionCatalog);
// collection_count = 0
page.data[PAGE_HEADER_SIZE..PAGE_HEADER_SIZE + 4]
.copy_from_slice(&0u32.to_le_bytes());
}
}
Let us look closely at what 0u32.to_le_bytes() is doing here, because this is fundamental to how systems programming works.
The number 0 as an unsigned 32-bit integer occupies 4 bytes. The method to_le_bytes() converts that number into a 4-byte array in little-endian order, where the least significant byte comes first. For zero, that array is just [0, 0, 0, 0]. If the count were 1, it would be [1, 0, 0, 0].
The call to copy_from_slice takes those 4 bytes and copies them directly into page.data starting at offset 16. That is how the collection count is set to zero when the database is first formatted.
Why did I make Catalog stateless instead of storing a Vec<CatalogEntry> inside it?
Because holding an in-memory copy of the catalog creates two sources of truth. What happens if your in-memory list says there are three collections, but a disk write failed and the file only has two? Now your program is in an inconsistent state, and debugging that will make you question your career choices.
By making Catalog stateless, the page itself is always the single source of truth. Every time we need to create, delete, or list collections, we read the page, do the work, and flush the page. There is zero risk of in-memory cache drift.
Creating a Collection: The Journey of a Write
When you type create users in the shell, here is the exact journey that command takes through the engine.
First, the engine calls the pager to load the catalog page into memory. The pager gives back a 4096-byte mutable slice of memory representing page 1.
The engine reads the first 4 bytes after the page header to find out how many collections already exist. Let us say collection_count is 2.
Next, it has to make sure we are not creating a duplicate. It sets a cursor variable to offset 20 (the start of the entries). It loops twice, reading each existing collection name using a helper function called read_cstring. If any name matches "users", it stops immediately and returns an error. We do not allow duplicate collections.
If no duplicate is found, the cursor is now pointing to the exact byte where the previous entry ended. That is our insertion point.
The engine checks whether there is enough space left on page 1 for the new entry. The new entry needs 6 bytes for "users\0", 8 bytes for the page pointer, and 8 bytes for the document count, which is 22 bytes. If the page has enough room, it writes the string bytes, writes 8 bytes of zero for first_document_page (since a new collection has no documents yet), and writes 8 bytes of zero for document_count.
Then it goes back to offset 16, increments the collection_count from 2 to 3, and writes the new count back to the page buffer.
Finally, the pager marks the page as dirty and flushes it to disk.
Notice how simple and mechanical that is. There is no query planner, no schema validator, no background worker. It is just reading a small buffer, checking for duplicates, appending 22 bytes, incrementing a counter, and writing the page back.
Listing Collections with a Cursor
Reading the list of collections reverses that entire process:
pub fn list(pager: &mut Pager) -> Result<Vec<CatalogEntry>> {
let page = pager.read_page(pager.header.catalog_page)?;
let count = Self::collection_count(&page)?;
let mut cursor = CATALOG_HEADER_SIZE;
let mut entries = Vec::new();
for _ in 0..count {
let name = read_cstring(&page.data, &mut cursor)?;
let first_document_page = read_u64(&page.data, &mut cursor);
let document_count = read_u64(&page.data, &mut cursor);
entries.push(CatalogEntry {
name,
first_document_page,
document_count,
});
}
Ok(entries)
}
The cursor pattern is one of the most useful patterns in binary parsing. A cursor is simply a usize variable that keeps track of where we are currently reading in the byte slice.
When read_cstring(&page.data, &mut cursor) runs, it starts at cursor, reads characters until it hits 0x00, constructs a Rust String, and advances cursor past the zero byte.
Then read_u64 reads the next 8 bytes as a little-endian number and advances cursor by 8. Then it does it again for document_count.
After looping count times, the function returns a clean Vec<CatalogEntry> ready for the shell to print.
Now, someone who took a computer science algorithms class might look at this and say: wait, that is an O(n) linear scan. Why didn't you build a B-tree or a hash map for the catalog?
Because context matters. The entire catalog page is 4096 bytes. That is 4 kilobytes. A modern CPU can scan 4KB of contiguous memory in its L1 cache in a fraction of a microsecond. If you have 20 collections, an O(n) linear scan takes virtually zero time. Building a complex B-tree just to store 20 collection names would be textbook over-engineering. Never pay for complexity you do not actually need.
Deleting a Collection: The Shift-Left Trick
Deleting a collection is where the byte manipulation gets interesting.
When someone deletes a collection, you cannot simply write zeros over its entry and leave a hole in the middle of the page. If the reader encounters a gap of zeros, it will either think the collection name is an empty string or get confused about where the next entry begins. The entries must always remain packed tightly together.
To solve this, I used a shift-left strategy.
Imagine a row of physical books sitting on a shelf. If you remove the book in the middle, you get an empty gap. What do you do? You slide all the books to the right of that gap one position to the left. The gap disappears, and all the books are neatly packed again.
In Rust, the standard library provides a method called copy_within on slices that does exactly this:
page.data.copy_within(entry_end..used_end, entry_start);
copy_within takes a source range of bytes and copies them to a new destination offset inside the exact same slice. It safely handles overlapping memory regions, which is crucial because when you slide bytes to the left, the source and destination overlap.
After sliding the bytes left, we decrement collection_count by 1.
What happens to the leftover bytes at the far right of the entries region? Nothing! We do not even need to zero them out. Because collection_count is decremented, the reader will stop reading earlier and will never look at those leftover bytes. They will simply be overwritten the next time a new collection is created.
When a collection is deleted, we also free any document pages that belonged to it so they can be reused later. We will see how page reuse works when we talk about the free-page list.
Preventing Catastrophe with a Lock File
Above the Catalog and the Pager sits the Database struct. This is the main entry point that the shell and external applications interact with:
pub struct Database {
pager: Pager,
lock_path: PathBuf,
_lock_file: File,
}
Notice that field named _lock_file with the leading underscore.
In Rust, if you declare a variable or a field and never call any methods on it, the compiler will yell at you about an unused variable. The underscore tells the compiler: I know this looks unused, but please leave it alone.
And leaving it alone is the whole point!
When Database::open is called, it creates a small file next to the database with a .lock extension. It opens that file and stores the open file handle inside _lock_file.
As long as the Database instance exists in your program, that file handle remains open. When your program finishes or the Database goes out of scope, Rust drops the struct. Rust's ownership system automatically closes the file handle, and the operating system releases the lock.
This is the classic RAII pattern, which stands for Resource Acquisition Is Initialization. You acquire the resource on creation, and cleanup happens automatically on destruction. You do not have to remember to call a close() method.
But what happens if the power cord is pulled out of the wall while the database is running?
If the system crashes violently, the .lock file remains sitting on the hard drive even though the process is dead. If another program tries to open the database later, it sees the .lock file and thinks the database is still in use.
To solve this, nosqlite checks for stale locks on startup:
pub fn open(path: impl AsRef<Path>) -> Result<Self> {
let lock_path = path.with_extension("lock");
if lock_path.exists() {
let stale = match read_lock_file(&lock_path) {
Ok(lock) => !process_exists(lock.pid),
Err(_) => true,
};
if stale {
eprintln!("Removing stale lock file");
let _ = std::fs::remove_file(&lock_path);
} else {
return Err(Error::DatabaseLocked);
}
}
// ... proceed with opening
}
When nosqlite creates a lock file, it writes the current process ID into it. On startup, if a lock file exists, the engine reads that PID and asks the operating system: is a process with this ID currently running?
If the answer is no, the previous process died without cleaning up. The lock is stale. nosqlite deletes the file and continues opening normally. If the process is still running, the database is genuinely in use by another instance, and the engine refuses to open to prevent data corruption.
It is a simple, pragmatic mechanism that prevents two processes from destroying the same database file while handling unexpected crashes gracefully.
Where We Stand
At this point in the project, nosqlite had a solid foundation.
It could format a file, stamp its magic bytes, maintain a catalog of collections, slide bytes around safely during deletions, and protect the file from concurrent access with process locking.
You could open the shell, run create users, run create orders, and run list. The database would print:
users: 0 documents
orders: 0 documents
Everything worked. But every single collection had first_document_page set to 0.
It was like having a filing cabinet with neatly labeled folders, but every single folder was completely empty. We had built the entire organizational structure of a database without storing a single byte of actual user data.
That changes in the next article.
In Part 4, we finally put real data into those folders. We take a JSON string typed into the terminal, break down why storing raw JSON is a terrible idea, convert it into binary BSON format, allocate document pages, link them together in a chain, and write our very first document to disk.
