MiniDB : Building a database for educational purposes

This project builds a small database one layer at a time. The goal is learning, not production readiness.

Completed Steps

1. In-memory key-value store Basic SET, GET, DELETE, and KEYS behavior stored only in memory.
2. Append-only file persistence Changes are written to disk so data survives restarting the REPL.
3. Indexed current-state storage plus append-only audit log MiniDB keeps fast current-state lookup while preserving an audit history of changes.
4. Page-tree storage with write-ahead log recovery Values are stored as root and leaf pages, with WAL recovery protecting interrupted writes.
5. Compaction so deleted/old slots stop wasting space COMPACT rewrites the data file with only live records.
6. Checksummed page-tree storage Pages include CRC32 checksums so MiniDB can detect corrupted on-disk pages. Older unchecksummed tree pages are migrated when loaded.

Current Step: 7. Document Storage and Metadata

MiniDB is moving from the key/value foundation to a document-oriented model. Instead of tables and fixed rows, it will store JSON-like objects in named collections. Each stored document will have user data plus database-managed metadata needed for querying and future distribution.

A logical document will look like this:

{
  "_meta": {
    "id": "01J...",
    "collection": "users",
    "version": 3,
    "created_at": "2026-07-22T10:00:00Z",
    "updated_at": "2026-07-22T10:05:00Z",
    "origin_node": "node-a",
    "tombstone": false
  },
  "data": {
    "name": "Ada Lovelace",
    "active": true,
    "profile": {
      "language": "Python"
    }
  }
}

The metadata/data separation keeps application fields flexible while reserving the information required for replication, version comparison, deletion propagation, and conflict handling. The storage engine completed in steps 1-6 remains the local persistence layer beneath this model.

The first version uses a single-node document API. Distribution will be added only after document identity, versioning, tombstones, querying, and local indexes have well-defined behavior.

Document Commands

MiniDB currently supports:

• COMPACT: remove dead slots from the data file
• PUT <collection> [id] <json>: insert or replace a JSON document
• GET_DOC <collection> <id>: read a live document by ID
• DELETE_DOC <collection> <id>: create a deletion tombstone
• FIND <collection> [query-json]: match documents by field values
• COLLECTIONS: list document collections
• HELP: show commands
• EXIT: leave the shell

When you run the REPL, MiniDB stores documents in data.minidb. It also writes storage changes to data.minidb.audit, which is append-only history, and uses data.minidb.wal for crash recovery.

The raw key/value engine is intentionally internal. Application writes must go through the document API so every record receives identity, version, origin, timestamp, and tombstone semantics. This prevents writes that cannot be safely replicated later.

MiniDB keeps an in-memory hash index of key -> root page offset. The root page points to leaf pages, and each leaf page stores one chunk of the value. Updating an existing key can jump directly to the root and leaf offsets. If only one chunk changes, MiniDB writes only that leaf page instead of rewriting the whole value.

Each page also stores a CRC32 checksum. When MiniDB starts, it verifies every checksummed page before trusting it, so simple on-disk corruption fails with a clear error instead of silently returning bad data. Older unchecksummed tree pages are still readable and are rewritten with checksums after loading.

The write order is:

1. Write changed tree nodes to data.minidb.wal
2. Flush the WAL
3. Apply those node writes to data.minidb
4. Clear the WAL
5. Append a summary to data.minidb.audit

Run It

From this folder:

py -3 -m minidb.repl

You must run that command from the project root, the folder that contains README.md and the minidb folder. If your terminal is inside minidb, go up one level first:

cd ..
py -3 -m minidb.repl

You can also use the simpler launcher from the project root:

py -3 run.py

Then try:

db> PUT users user-1 {"name":"Ada Lovelace","active":true}
{"_meta":{"collection":"users","created_at":"...","id":"user-1","origin_node":"local","tombstone":false,"updated_at":"...","version":1},"data":{"active":true,"name":"Ada Lovelace"}}
db> EXIT
bye

Now start it again:

py -3 run.py

The document is still there because MiniDB loaded data.minidb:

db> GET_DOC users user-1
{"_meta":{"collection":"users","created_at":"...","id":"user-1","origin_node":"local","tombstone":false,"updated_at":"...","version":1},"data":{"active":true,"name":"Ada Lovelace"}}
db> COMPACT
OK
db> DELETE_DOC users user-1
OK
db> GET_DOC users user-1
NULL

The document interface operates on collections rather than tables:

PUT users user-1 {"name":"Ada Lovelace","active":true}
FIND users {"active":true}
GET_DOC users user-1
DELETE_DOC users user-1

Omit the ID in PUT to generate one automatically. Reusing an ID replaces the document data and advances its metadata version. FIND performs exact matches; dotted paths such as {"profile.language":"Python"} address nested fields.

Run Tests

py -3 -m unittest discover -s tests

Roadmap

We will build the database in small learning steps:

1. In-memory key-value store
2. Append-only file persistence
3. Indexed current-state storage plus append-only audit log
4. Page-tree storage with write-ahead log recovery
5. Compaction so deleted/old slots stop wasting space
6. Add checksums to detect corrupted pages
7. JSON-like documents, collections, and system metadata
8. Document queries and field-path matching
9. Secondary indexes for selected document fields
10. Node identity, cluster membership, and inter-node protocol
11. Replication log and follower catch-up
12. Versioning, tombstones, and deterministic conflict resolution
13. Partitioning, replica placement, and rebalancing
14. Configurable consistency for reads and writes

Each step should leave the database runnable and testable.