Log-Structured NoSQL Database Engine

The Log-Structured NoSQL Database Engine is a lightweight Key-Value and Document storage engine implemented from scratch in C.

It delivers predictable O(1) read and write performance, crash durability via append-only Write-Ahead Log (WAL), and optimized memory usage through Least Recently Used (LRU) cache.

Architecture & Data Flow

At its core, the engine is built on the principle that sequential disk access is faster than random disk access.

Design Map

flowchart TD
    User([Client / CLI]) -->|1. API Call| API[C API Layer: nosql.h]

    subgraph Memory_RAM [Volatile Memory: RAM]
        LRU[LRU Cache: lru_cache.h]
        KeyDir[Key-Offset HashMap: hashmap.h]
        WALBuf[WAL Buffer: 4KB]
    end

    subgraph Disk_Storage [Non-Volatile Storage: SSD/HDD]
        WALFile[(WAL Database File: data.db)]
    end

    API -->|2. Check Cache| LRU
    API -->|3. Query Index| KeyDir
    API -->|4. Batch Writes| WALBuf

    WALBuf -->|5. Commit & fsync| WALFile
    KeyDir -->|6. Seek DB Pointer| WALFile
    LRU -->|7. Load on Miss| WALFile

    style Memory_RAM fill:none,stroke:#ff9900,stroke-width:2px
    style Disk_Storage fill:none,stroke:#33b5e5,stroke-width:2px

Core Architecture

Write-Ahead Log (WAL) (wal.c): All updates (put / delete) are strictly appended to the active database .db file. This avoids in-place modifications (which cause random disk seeks and fragment files). To maximize disk throughput, writes are batched in an in-memory 4KB wal_buffer. Data is flushed and forced onto non-volatile storage using platform-specific synchronization (fsync on POSIX or _commit on Windows).
The KeyDir Index (hashmap.c): To maintain O(1) read speeds, the engine maintains an in-memory hash table mapping keys to DB Pointers (the physical byte offset of the record on disk). When the database boots, the KeyDir is reconstructed by replaying the binary WAL sequentially.
Double-Linked LRU Cache (lru_cache.c): An in-memory cache sits between the C API and the physical disk. It is implemented using a Doubly-Linked List (to track usage order) and a secondary Hash Map (for O(1) cache node lookups). Cache hits bypass disk reads, returning values in microseconds.

Components

1. WAL Binary Record Layout

Records are serialized and written directly to the disk in a compact binary layout to prevent encoding overhead:

+-------------------+-------------------+---------------------+-------------------+---------------------+
| Key Length (4B)   | Value Length (4B) | CRC32 Checksum (4B) | Key Bytes (Var)   | Value Bytes (Var)   |
+-------------------+-------------------+---------------------+-------------------+---------------------+

Lengths: 32-bit unsigned integers representing key and value byte-lengths.
CRC32 Checksum: Computed over both the key and value bytes to ensure data block integrity.
Payload: Raw UTF-8 or binary data for keys and values.

2. Crash Recovery & Validation

When a power failure occurs, in-memory structures are lost. On startup, wal_replay rebuilds the HashMap by reading the WAL sequentially:

Checks the file size and reads the custom magic header 0x4E53514C ("NSQL") and format version.
Loops until End-of-File (EOF).
Reads record headers (lengths, CRC) and performs Boundary Validation: offset + record_size <= file_size
Dynamically allocates buffers to read key-value pairs.
Recalculates the CRC32 of the key-value bytes. If it does not match the header's CRC, recovery truncates the corrupted bytes, rollbacks the invalid write, and safely stops.
Re-populates the HashMap with the valid record's physical disk offset.

3. Deletions, Tombstones, & Log Compaction

Because the WAL is append-only, deletions cannot free physical disk space immediately.

Tombstones: Deleting a key appends a record with a special value __TOMBSTONE__ to the WAL. The KeyDir drops the key from memory immediately. A consistency barrier flushes the WAL to disk before updating the memory state to ensure the tombstone persists.
Log Compaction (nosql_compact): Over time, overwritten keys and tombstoned values leak disk space. The compaction process runs as a blocking utility:
1. Creates a new temporary database file (e.g. data.db.tmp).
2. Iterates over active keys in the KeyDir Hash Map, reading their values from the old database.
3. Writes only these live, non-tombstone key-value pairs to the temporary database.
4. Closes both files, deletes the bloated database under a Windows-safe file-locking retry handler, and renames the temporary database.
5. Rebuilds a compact, and clean memory index.

Bloated Log (Disk):   [K1:V1] -> [K2:V1] -> [K1:V2 (Updated)] -> [K2:TOMBSTONE (Deleted)]
Compacted Log (Disk): [K1:V2]

4. Logical Namespacing

The engine supports document-oriented storage on top of the Key-Value core via document.c:

Hierarchical Paths: Users work with logical namespaces: Project → Collection → Document.
Composite Key Inversion: Behind the scenes, the high-level API maps this hierarchy to a flat key string formatted as: project | collection | document_id
JSON Serialization: Integrates the lightweight cJSON library to parse documents. Inserts auto-generate a unique 16-character hexadecimal _id if one is not present.
API Interaction Flow: The Document API wraps the Key-Value API. For writes, it constructs the composite key and serialized JSON value, then passes them down to the Key-Value API (nosql_put). For reads, it requests the composite key and receives the raw string back from the Key-Value API (nosql_get).

5. Multi-User Authentication

The engine includes physical isolation for multi-user deployments:

Auth Database: A dedicated database file (system.db) stores user records and credentials.
Credential Protection: Passwords are hashed using SHA-256 before storage via sha256.c.
Physical Separation: Upon successful login, the engine closes the active database and opens a user-specific file named user_<username>.db. Users have completely separated physical files, eliminating data leaks between users.

Performance & Benchmarking

Benchmarks are executed using test_benchmark.c, running direct calls against the C API to eliminate CLI parsing and terminal I/O overhead.

Benchmark Setup

Dataset: 50,000 JSON documents.
Document Payload: {"test_key": "benchmark_value", "number": 12345}
Test Actions: Sequential insertion (forces JSON validation, CRC32 hashing, WAL buffer flushes, and HashMap updates), followed by sequential reads (forces cache check, HashMap lookup, disk read seek, and CRC verification).

Test Results

The engine achieves the following throughput metrics:

Writes (Inserts): ~40,000 to 75,000 operations/second
Reads: ~80,000 to 120,000 operations/second (mix of RAM cache hits and indexed physical disk reads)

System Trade-offs

Trade-off	Current Engine Behavior	Enhancements
Index Scaling	RAM Bottleneck: The entire KeyDir HashMap must fit in RAM. Scalability is limited by server memory, not disk capacity.	Transition to storing the index on disk to allow scaling beyond physical memory capacity.
Durability vs. Performance	WAL Buffering: Appends are buffered in a 4KB RAM buffer and flushed (`fsync`/`_commit`) only when full, before reads, or on database close. This optimizes write speed but risks losing up to 4KB of uncommitted data on sudden power failure.	Implement configurable synchronization policies: standard sync-on-write (slow but safe).
Compaction Cost	Compacting locks the engine and blocks write operations.	Introduce Background Compaction that will merge segment files in the background without locking the engine.

C APIs

The engine exposes a low-level Key-Value API (for raw string storage) and a high-level Document API (for namespaced JSON documents with automated validation and ID generation) through nosql.h:

/* Initialization */
int nosql_init(const char *dbfile);  /* Opens the WAL file and recovers index */
void nosql_close(void);              /* Flushes buffers and frees RAM structures */

/* Low-level Key-Value API */
int nosql_put(const char *key, const char *value);  /* Appends record, updates Cache & HashMap */
char *nosql_get(const char *key);                   /* Fetches value (checks LRU cache -> falls back to disk) */
int nosql_delete(const char *key);                /* Appends tombstone to WAL and clears cache/index */

/* Maintenance & Stats */
int nosql_flush(void);                              /* Forcefully flushes write-buffer to disk */
int nosql_compact(void);                            /* Re-writes WAL to purge stale records */
int nosql_key_count(void);                          /* Returns number of active keys */
long nosql_wal_size(void);                          /* Returns current physical file size */

/* High-level Document API */
int nosql_document_insert(const char *project, const char *collection, const char *json_str, char **out_id);
char *nosql_document_get(const char *project, const char *collection, const char *id);
int nosql_document_delete(const char *project, const char *collection, const char *id);

Usage

Compilation

Compile the CLI executable and the testing suite:

# Build all targets (CLI engine + test suites)
make all

Run the CLI

Launch the database engine with:

./nosql.exe

nosql> register admin securepass admin
User created successfully.
nosql> login admin securepass
Authentication successful. Active session: admin
nosql:admin> use university
switched to project university
nosql:admin:university> collection courses
switched to collection courses
nosql:admin:university/courses> insert {"title": "Operating Systems", "code": "CS-301"}
Document inserted. Inferred ID: 0123456789abcdef
nosql:admin:university/courses> doc_get 0123456789abcdef
{"_id":"0123456789abcdef","title":"Operating Systems","code":"CS-301"}
nosql:admin:university/courses> stats
WAL Size: 301 bytes | Active Keys: 2

Test Verification

# Test WAL writing, appending, and raw binary format
./tests/test_wal.exe

# Test high-level API parsing and composite key routing
./tests/test_document.exe

# Test SHA-256 user database isolation and multi-tenant security
./tests/test_auth.exe

# Test custom double-linked LRU Cache evictions and hits
./tests/test_lru.exe

# Verify CRC32 validation, torn write drops, and automatic recovery safety
./tests/test_corruption.exe

# Execute performance benchmarking
./tests/test_benchmark.exe

Navigation Menu

Log-Structured NoSQL Database Engine

Architecture & Data Flow

Design Map

Core Architecture

Components

1. WAL Binary Record Layout

2. Crash Recovery & Validation

3. Deletions, Tombstones, & Log Compaction

4. Logical Namespacing

5. Multi-User Authentication

Performance & Benchmarking

Benchmark Setup

Test Results

System Trade-offs

C APIs

Usage

Compilation

Run the CLI

Test Verification

References

FilesExpand file tree

README.md

Latest commit

History

README.md

File metadata and controls

Log-Structured NoSQL Database Engine

Architecture & Data Flow

Design Map

Core Architecture

Components

1. WAL Binary Record Layout

2. Crash Recovery & Validation

3. Deletions, Tombstones, & Log Compaction

4. Logical Namespacing

5. Multi-User Authentication

Performance & Benchmarking

Benchmark Setup

Test Results

System Trade-offs

C APIs

Usage

Compilation

Run the CLI

Test Verification

References