Series: nosqlite devlog, Part 2
The first article was about the why. This one is where things get concrete.
I remember the exact moment I opened a hex editor on a SQLite file for the first time. The first 16 bytes said 53 51 4C 69 74 65 20 66 6F 72 6D 61 74 20 33 00. That decodes to SQLite format 3. A literal string. Right there at byte zero. Before any data, before any tables, before anything useful, the file just tells you what it is.
I thought that was brilliant. And I knew immediately that nosqlite would need the same thing.
When you open a nosqlite database for the first time, the file does not exist yet. The code creates it. But it does not just create a blank file and start dumping data. It sets up a structure. A layout. A way of knowing where everything is and what it means.
This is the file format.
Why Structure Matters
Imagine a file that contains two documents, both stored as raw BSON bytes, one after another. How do you know where the first document ends and the second begins? How do you know if the file is a valid nosqlite database and not a corrupted archive or a random binary blob? How do you find a specific document without reading everything from byte zero?
You cannot answer any of those questions without structure.
Every database engine, from SQLite to PostgreSQL to LevelDB, has a defined file format. It is as much a part of the project as the code itself. nosqlite is no different.
The Page: The Fundamental Unit
The core abstraction in nosqlite is the page. A page is a fixed-size block of bytes, exactly 4096 bytes. This number is not arbitrary.
Most modern operating systems use a memory page size of 4096 bytes. When you read a file, the OS reads it in chunks that align to this boundary. If your database reads in 4096-byte units, you are playing along with the OS instead of fighting it. One read operation brings in exactly one page.
Here is how the page is defined in the code:
pub const PAGE_SIZE: usize = 4096;
pub const PAGE_HEADER_SIZE: usize = 16;
#[repr(u8)]
pub enum PageType {
Free = 0,
CollectionCatalog = 1,
CollectionData = 2,
}
Every page has a header that occupies the first 16 bytes. The rest of the page is available for data. The page type tells the engine what kind of data is in this page. Right now there are three types: a free page (not in use), a catalog page (which tracks collections), and a data page (which holds actual documents).
That enum attribute #[repr(u8)] is a Rust thing worth understanding. It tells the compiler to represent the enum as a single byte. This matters because this value gets written directly into the file. When you read that byte back, you can determine what kind of page you are looking at.
The File Header
The very first thing in a nosqlite database file is the file header. It lives in the first 4096 bytes, which is a full page. Even though it does not fill all 4096 bytes, it reserves the entire first page so that page numbering is consistent. Page 0 is always the header.
pub const FILE_HEADER_SIZE: u64 = 4096;
pub const MAGIC_BYTES: &[u8; 16] = b"NOSQLITE_DB___P8";
#[derive(Debug, Clone)]
pub struct FileHeader {
pub version: u32,
pub total_pages: u64,
pub free_list_head: u64,
pub catalog_page: u64,
}
Take a look at MAGIC_BYTES. This 16-byte sequence is the first thing written into every nosqlite database file. When you open a file, the very first check is: do these first 16 bytes match? If they do not, this is not a nosqlite database, and the engine refuses to proceed.
This is called a magic number or magic bytes. Every well-designed binary format has one. PNG files start with \x89PNG\r\n\x1a\n. ZIP files start with PK. SQLite files start with SQLite format 3. The magic bytes let any reader quickly identify the format before attempting to parse anything.
The P8 at the end is personal. It is a nod to p8labs, my own project namespace. Every file this engine creates carries that marker.
What the Header Tracks
The FileHeader struct holds four pieces of information:
version is a u32 that identifies the format version. This is future-proofing. If the file format changes in a breaking way, the version number changes too. An older reader can detect that the format is newer than it understands and refuse gracefully.
total_pages is a u64 counting how many pages exist in the file right now. Every time a new page is allocated, this counter increments.
free_list_head is a u64 holding the page number of the first free page. When you delete a collection or its documents, those pages do not disappear from the file. They go onto a linked list of free pages. Next time you need a new page, you can reuse one from this list instead of growing the file. This is 0 when there are no free pages.
catalog_page is a u64 holding the page number of the catalog page. The catalog is where the list of all collections is stored. You need to know where it is to do anything useful.
Binary Encoding
The file header and every other structure in nosqlite is encoded in little-endian format. Little-endian means the least-significant byte comes first.
For example, the number 1 as a u32 in little-endian is 01 00 00 00. In big-endian it would be 00 00 00 01. Most consumer hardware (x86, ARM in modern Linux defaults) is little-endian, which is why most database formats choose it.
The codec module handles reading and writing these values:
pub fn read_u32(buffer: &[u8], cursor: &mut usize) -> Result<u32> {
let bytes = buffer.get(*cursor..*cursor + 4).ok_or(Error::Corruption)?;
*cursor += 4;
Ok(u32::from_le_bytes(
bytes.try_into().map_err(|_| Error::Corruption)?,
))
}
pub fn read_u64(buffer: &[u8], cursor: &mut usize) -> Result<u64> {
let bytes = buffer.get(*cursor..*cursor + 8).ok_or(Error::Corruption)?;
*cursor += 8;
Ok(u64::from_le_bytes(
bytes.try_into().map_err(|_| Error::Corruption)?,
))
}
The cursor is a mutable reference to a position. Each read_* call advances the cursor by the number of bytes consumed. This pattern makes sequential reading clean. You start the cursor at 0, call read_u16, then read_u32, then read_u64, and the cursor tracks your position through the buffer automatically. No manual offset arithmetic.
The ok_or(Error::Corruption) at the end is the defensive part. If the buffer is shorter than expected, the engine returns a Corruption error instead of panicking. In a storage engine, unexpected short reads almost always mean the file has been truncated or corrupted. Detecting this rather than crashing is the correct behavior.
The Pager
The structure that manages all page reads and writes is called the Pager. This is a concept borrowed directly from SQLite's architecture.
pub struct Pager {
file: File,
pub header: FileHeader,
}
impl Pager {
pub fn open(path: impl AsRef<Path>) -> Result<Self> {
let mut file = OpenOptions::new()
.create(true)
.read(true)
.write(true)
.open(path)?;
let header = if file.metadata()?.len() == 0 {
Self::initialize_database(&mut file)?
} else {
read_header(&mut file)?
};
Ok(Self { file, header })
}
// ...
}
When you call Pager::open, it either initializes a fresh database or reads the existing header. The check is simple: if the file length is 0, the file is brand new and needs to be set up. Otherwise, read the header and trust that the rest of the file is structured correctly.
The OpenOptions call is standard Rust file I/O. create(true) means create the file if it does not exist. read(true) and write(true) give the handle both read and write permissions.
The Pager is the only thing in the codebase that directly interacts with the file. Every other module that needs to read or write pages goes through the Pager. This is important for correctness. Centralizing file access means page reads and writes are consistent. In the future, caching pages in memory before writing them to disk will happen inside the Pager, without touching anything else.
Bootstrap: First Database Write
When initialize_database runs on a fresh file, it does a few things:
It writes the magic bytes at byte 0. It writes an initial FileHeader. It allocates the first real page (page 1) as the catalog page and initializes it. It updates the header to point catalog_page at 1. Then it flushes everything to disk.
After that, the file is a valid nosqlite database with no collections and no documents, but with the infrastructure in place to hold them.
On every subsequent open, the Pager reads the header, verifies the magic bytes, and trusts the structure. Nothing needs to be rebuilt.
The File Layout So Far
Here is what the file looks like after initialization:
Byte 0 : NOSQLITE_DB___P8 (16 bytes, magic)
Byte 16 : version (u32, 4 bytes)
Byte 20 : total_pages (u64, 8 bytes)
Byte 28 : free_list_head (u64, 8 bytes)
Byte 36 : catalog_page (u64, 8 bytes)
Byte 44-4095 : padding / reserved
Byte 4096 : Catalog page header (16 bytes)
Byte 4112+ : Catalog page data
This is the foundation. Every feature built on top of nosqlite reads and writes through this structure.
In the next article, we look at collections. What is a collection in a NoSQL database? How does the catalog page know what collections exist and where their documents live? What happens at the byte level when you create a collection or delete one?
That is where the data starts to feel real.
Top comments (0)