Storing Documents: From a JSON String to Bytes on Disk

Series: nosqlite devlog, Part 4

By the end of the third article, nosqlite had empty collections.

You could launch the shell, type create users, and the database would happily nod, update its catalog page, and save the collection name to disk. But a database that only stores collection names is just an expensive notepad. It is the architectural equivalent of putting empty cardboard boxes in a warehouse and calling it a logistics empire.

It was time to store actual data.

This was the part of the project I had been looking forward to the most, because this is where database theory stops being abstract and starts turning into raw binary operations. When someone uses a document database, they think in JSON. They type { "name": "Priyanshu", "age": 22 } and expect the database to tuck that object away safely on disk, keep it intact through computer reboots, and hand it back when asked.

Turning that simple expectation into bytes inside a 4096-byte page forced me to make some of the most critical design decisions in the entire project.

The Temptation of Raw JSON

When you sit down to build a document database from scratch, there is an obvious shortcut whispering in your ear: why not just store JSON strings?

Think about how easy that sounds. In Rust, you can add serde_json, call to_string(), and get a plain UTF-8 string. You write that string directly into the file. If you want to read it back, you read the string and parse it. It is human-readable, every language supports it, and you can inspect your database with a regular text editor.

It feels like the right move until you think about what a database actually does when it reads data.

Imagine you have a collection with ten thousand documents. Each document has fifty fields, and you want to find all users where the age field is greater than twenty.

If your documents are stored as raw JSON strings, the database has to parse the text of every single document from byte zero. It has to scan through characters, match curly braces, skip whitespace, interpret quotation marks, unescape special characters, and search for the characters "age". If you are scanning ten thousand documents, your CPU spends all its cycles doing string parsing instead of database work.

Then there is the data type problem. JSON is loose. When JSON says 42, is that an 8-bit integer, a 32-bit integer, a 64-bit integer, or a floating-point number? JSON does not specify. It just has numbers.

What if you want to store a binary payload, like a cryptographic hash or an image thumbnail? JSON has no native binary type. You have to encode the bytes as base64 strings, which inflates the size by thirty-three percent and wastes storage.

What if you want to store a timestamp? JSON has no date type. You store it as an ISO 8601 string like "2026-10-19T20:00:00Z", which takes twenty-four bytes and requires string parsing every time you want to compare two dates.

This is why the team behind MongoDB created BSON, which stands for Binary JSON.

Why BSON Changes the Game

BSON takes the flexibility of JSON and encodes it into a structured binary format.

Instead of writing text that has to be parsed character by character, BSON prefixes every single field with a type byte and a length.

Let me make this concrete. If a document has a string field named "name" with the value "Priyanshu", BSON does not write "name": "Priyanshu". It writes something closer to this:

First, a single type byte (0x02), which signals: the following value is a UTF-8 string.
Next, the field name as a null-terminated C string: name\0.
Next, a 4-byte integer recording the length of the string value: 10 (including the null terminator).
Finally, the string bytes themselves: Priyanshu\0.

Why does this matter so much for performance?

Because of the length prefix! If a reader is scanning a document looking for age, and it encounters the name field, it does not have to parse the string "Priyanshu". It reads the length prefix (10 bytes), adds 10 to its read cursor, and jumps over the string in a single CPU instruction.

Integers in BSON are stored as raw 4-byte or 8-byte little-endian numbers, not digit characters. Comparing two integers is a single CPU comparison, not string parsing. Binary blobs are stored as raw bytes with a length prefix, with zero base64 overhead.

The only downside is that you cannot open the database file in Notepad and read your documents. But for an embedded database engine, that is a trade I will make every single day. The shell handles formatting JSON for humans; the storage engine works in binary.

Rather than reinventing a binary serialization format, nosqlite uses the bson crate from crates.io. It is battle-tested, fast, and handles the full BSON specification.

The Twelve Bytes of an ObjectId

In a relational database, you usually have an auto-incrementing integer for your primary key: 1, 2, 3, and so on.

In a document database, that approach falls apart quickly. If two different worker threads or distributed clients insert documents at the same time, coordinating an auto-incrementing integer requires centralized locking.

Instead, document databases use an _id field containing an ObjectId.

When someone inserts a document into nosqlite without an _id, the engine generates one automatically. An ObjectId is exactly 12 bytes long. But those 12 bytes are not random noise. They are packed with information:

The first 4 bytes are a Unix timestamp representing seconds since 1970.
The next 5 bytes are a random value generated once when the process starts.
The final 3 bytes are an incrementing counter that starts at a random number.

The most elegant part of this design is the first 4 bytes. Because the Unix timestamp sits at the very beginning in big-endian order (most significant byte first), ObjectIds naturally sort chronologically!

If you take two ObjectIds and compare them byte by byte from left to right, the one created earlier will almost always sort before the one created later. This gives you time-ordered IDs for free. You can query documents by insertion time or extract the exact creation timestamp of any document directly from its ID without storing a separate created_at field.

The random 5 bytes ensure that two different processes or machines inserting at the exact same second will not generate conflicting IDs. The 3-byte counter ensures that a single process inserting thousands of documents within the same second generates unique IDs for every single one.

In Rust, generating a new ObjectId with the bson crate is a single line:

let id = bson::oid::ObjectId::new();

Simple on the surface, but mathematically brilliant underneath.

How Documents Live Inside Pages

In the second article, we established that nosqlite organizes its entire file into fixed 4096-byte pages.

A collection might have five documents, or it might have fifty thousand documents. A single 4096-byte page can hold only a few kilobytes of data. How do we store a collection that spans dozens or hundreds of pages?

We build a classic computer science data structure directly on disk: a singly linked list.

The first page of documents in a collection points to the second page. The second page points to the third page. The third page has its pointer set to 0, which signals that it is the end of the chain.

Here is what the header of every document page looks like:

// Document page layout:
// +-----------------------------------+
// | Generic Page Header               |   16 bytes (page number, page type)
// +-----------------------------------+
// | next_page (u64)                   |    8 bytes (pointer to next page in chain)
// +-----------------------------------+
// | document_count (u32)              |    4 bytes (active documents on this page)
// +-----------------------------------+
// | used_space (u32)                  |    4 bytes (bytes written in payload area)
// +-----------------------------------+
// | [records follow here]             |   up to 4064 bytes of document data
// +-----------------------------------+

And here are the offset constants from crates/nosqlite-core/src/document/page.rs:

pub const NEXT_PAGE_OFFSET: usize = PAGE_HEADER_SIZE;           // 16
pub const DOCUMENT_COUNT_OFFSET: usize = NEXT_PAGE_OFFSET + 8;  // 24
pub const USED_SPACE_OFFSET: usize = DOCUMENT_COUNT_OFFSET + 4; // 28
pub const DOCUMENT_HEADER_SIZE: usize = USED_SPACE_OFFSET + 4;  // 32

The first 16 bytes are the generic page header.
Bytes 16 to 23 hold next_page, which is an 8-byte page number pointing to the next document page in the collection.
Bytes 24 to 27 hold document_count, a 4-byte integer tracking how many active documents live on this specific page.
Bytes 28 to 31 hold used_space, a 4-byte integer tracking how many bytes of data have been written into the payload area so far.

Together, the header takes up exactly 32 bytes. Since a page is 4096 bytes, that leaves 4064 bytes of usable space for storing records.

Notice how important that used_space field is. When you want to insert a new document, you do not have to scan through the page to find where the free space begins. You just read the 4 bytes of used_space, add 32, and you immediately have the exact byte offset where the new record should be written. It turns finding the insertion point into an instant O(1) operation.

The Anatomy of a Record

Inside that 4064-byte payload region, records are packed one after another.

Each individual record has a small 5-byte header followed by the raw BSON document:

// Per-record layout:
// +-------------------------------+
// | deleted_flag (u8)             |    1 byte  (0 = active, 1 = deleted)
// +-------------------------------+
// | bson_size (u32)               |    4 bytes (length of the BSON payload)
// +-------------------------------+
// | bson_bytes...                 |    bson_size bytes of raw document data
// +-------------------------------+

pub const RECORD_DELETED_FLAG_SIZE: usize = 1;
pub const RECORD_BSON_SIZE: usize = 4;
pub const RECORD_HEADER_SIZE: usize = RECORD_DELETED_FLAG_SIZE + RECORD_BSON_SIZE; // 5

The first byte is the deleted_flag. If it is 0, the record is alive. If it is 1, the record has been deleted.

The next 4 bytes store bson_size as a little-endian unsigned 32-bit integer. This tells the reader exactly how many bytes to read for this document.

Why do we need bson_size right in the record header?

Because documents in a NoSQL database have variable lengths. One document might be 40 bytes. The next document might be 600 bytes. Without bson_size, the reader would have no idea where the current document ends and where the next record begins. Furthermore, if a record is marked as deleted, the reader can look at bson_size, skip forward by that exact number of bytes, and arrive at the next record header without wasting CPU cycles decoding dead BSON data.

The Insertion Pipeline: From Shell to Disk

Let us trace the complete path of an insertion. You sit at your terminal and run:

insert users { "name": "Priyanshu", "age": 22 }

Here is what happens inside nosqlite, step by step.

First, the shell parses the command. It extracts the collection name ("users") and the raw JSON text. It passes that JSON text to a conversion function that parses it into a bson::Document in memory.

Second, the engine inspects the document. Does it have an _id field? No. So the engine calls ObjectId::new(), generates a fresh 12-byte identifier, and inserts it into the document under the key _id.

Third, the engine serializes the document into binary BSON bytes using our codec helper:

pub fn encode_document(doc: &Document) -> Result<Vec<u8>> {
    let mut bytes = Vec::new();
    doc.to_writer(&mut bytes).map_err(Error::BsonEncode)?;
    Ok(bytes)
}

The method to_writer turns the in-memory document into a compact slice of bytes. Let us say this document serializes to 45 bytes.

Fourth, the engine looks up the "users" collection in the catalog. It reads the catalog entry and checks first_document_page.

If first_document_page is 0, this collection has never had a document before. The engine calls the pager to allocate a brand new page from disk. Let us say the pager allocates page 2. The engine initializes page 2 as a PageType::CollectionData page, sets next_page = 0, sets document_count = 0, and sets used_space = 0.

Fifth, the engine checks if there is enough space on page 2 for the new record.

The math is simple:

available_space = PAGE_SIZE - DOCUMENT_HEADER_SIZE - used_space
required_space  = RECORD_HEADER_SIZE + bson_bytes.len()

Plugging in our numbers:

available_space = 4096 - 32 - 0 = 4064 bytes
required_space  = 5 + 45 = 50 bytes

We have 4064 bytes available and only need 50. There is plenty of space.

Sixth, the engine writes the record into the page buffer starting at offset 32 + used_space:

// Write active flag
page.data[offset] = 0;
offset += 1;

// Write BSON size as little-endian u32
let size = bson_bytes.len() as u32;
page.data[offset..offset + 4].copy_from_slice(&size.to_le_bytes());
offset += 4;

// Write raw BSON bytes
page.data[offset..offset + bson_bytes.len()].copy_from_slice(&bson_bytes);

Seventh, the engine updates the page bookkeeping. document_count becomes 1. used_space increases by 50 bytes. The page is marked dirty and written back to disk.

Finally, because this was the very first document for the "users" collection, the engine updates the catalog entry on page 1 so that first_document_page points to page 2, and updates the catalog's document count.

What happens if a page does not have enough space for the new record?

The engine allocates a new page, updates the existing page's next_page field to point to the new page number, writes the existing page to disk, and then writes the new record onto the newly allocated page. The on-disk linked list grows by one node.

Reading Data: The Honest Linear Scan

When you run find users in the shell, the engine reverses that pipeline.

It reads the catalog to find first_document_page. It loads that page into memory. It sets a cursor to offset 32 (where the first record starts) and walks forward through the payload.

For every record, it reads the 1-byte deleted flag. If the flag is 0, it reads the 4-byte bson_size, slices out the BSON bytes, and decodes them into a document:

pub fn decode_document(bytes: &[u8]) -> Result<Document> {
    Document::from_reader(bytes).map_err(Error::BsonDecode)
}

The shell takes that document, converts it to readable JSON, and displays it in the terminal.

The cursor advances by 5 + bson_size. When the cursor reaches the end of the used space on the page, the engine checks next_page. If next_page is not 0, it loads the next page in the chain and repeats the process. When next_page is 0, the scan is complete.

This is a linear scan. Every record on every page in the collection is inspected.

There is no B-tree index. There is no hash map shortcut. If you have ten documents, it is instantaneous. If you have ten million documents, it will take several seconds.

And I love that this is how it works right now. Because when you build a database from scratch, starting with an honest linear scan teaches you why indexes exist in the first place. An index is not magic; it is simply a separate data structure built to avoid this exact linear scan. We will get to indexes in a later article.

Soft Deletion and the Concept of Tombstones

When someone runs delete users <id>, what should the database do?

If you were working with a Vec<u8> in RAM, your first thought might be to delete the bytes and slide everything after it to the left, just like we did in the catalog.

But on a data page, that is a terrible idea.

First, performance. If a document page holds forty documents, and you delete the second document, you would have to shift thousands of bytes of memory to the left, update the offsets, and recalculate used_space.

Second, crash safety. What happens if the program crashes or the power cuts out right in the middle of sliding those three thousand bytes? Half your page is shifted, half is unshifted, and your database file is irreparably corrupted.

Third, concurrency. If a background query is reading documents while a write operation shifts memory beneath its feet, the reader will read scrambled garbage.

Instead, nosqlite uses soft deletion, often called tombstoning:

// Mark the record as deleted
page.data[record_offset] = 1;

To delete a document, we write a single byte with the value 1 into the record's deleted_flag. We decrement the page's document_count, decrement the catalog's document count, and flush the page.

That is it. The actual BSON document bytes remain on disk. They do not move. But the next time a reader scans the page, it sees deleted_flag == 1, notes the bson_size, skips right over the dead bytes, and moves to the next record.

The trade-off is fragmentation. If you insert a hundred documents and delete ninety of them, those ninety dead records still consume space on disk. The page's used_space counter does not decrease.

In production databases, this is solved by a process called compaction, where the database rewrites pages in the background, copying only live records to fresh pages and reclaiming the free space. Compaction is on the roadmap for nosqlite, but for a learning project, soft deletion is the cleanest, safest, and most robust starting point.

What We Built

Take a step back and look at what we have now.

We started in Article 1 with an idea: build a single-file document database in Rust.
In Article 2, we formatted a file with 4096-byte pages and magic bytes.
In Article 3, we built a catalog page to track collections and added crash-safe locking.
And now, in Article 4, we have a fully functional document storage pipeline.

You can open nosqlite, create collections, insert arbitrary JSON documents, have them stored as structured binary BSON on disk, scan them back out, and safely delete them using tombstones. If you close the shell and turn off your computer, the data will still be there tomorrow morning.

It is a real database.

But right now, it only exists as a Rust library and a command-line tool. If someone wants to build a web backend in Go, a data science pipeline in Python, or a mobile app in Flutter, they cannot use nosqlite. Rust code cannot simply be imported into another language.

To make nosqlite accessible to the rest of the programming world, we need a bridge. We need an interface that every programming language on earth understands: the C Application Binary Interface.

In the next article, we dive into the FFI layer. We will look at how to expose Rust structs as opaque C pointers, how to pass strings and error codes across language boundaries safely, and how to stop Rust panics from crashing a foreign host program.