C Key-Value Store

A fast embedded key-value database with persistence on disk, crash recovery, and B-tree indexing.

• B-tree Storage Engine: Efficient indexing with configurable page sizes
• Persistence: All data stored on disk with immediate consistency
• Crash Recovery: Write-ahead logging (WAL) ensures durability
• Simple API: Clean C interface for put/get/delete operations
• CLI Interface: Interactive shell for database operations
• Configurable: Adjustable page size for performance tuning

make

This will compile the kvstore executable.

# Use default database (kvstore.db) with default page size (4096 bytes)
./kvstore

# Specify database path
./kvstore mydata.db

# Specify database path and page size
./kvstore mydata.db 8192

Once running, you can use the following commands:

• put <key> <value> - Insert or update a key-value pair
• get <key> - Retrieve value for a key
• delete <key> - Delete a key-value pair
• sync - Synchronize all changes to disk
• help - Show available commands
• exit or quit - Close database and exit

$ ./kvstore
Opening database: kvstore.db
Page size: 4096 bytes (default)
Database opened successfully.
Type 'help' for available commands.

kvstore> put name Alice
OK
kvstore> put age 30
OK
kvstore> get name
Alice
kvstore> get age
30
kvstore> delete age
OK
kvstore> get age
Error: Key not found
kvstore> sync
OK - All changes synchronized to disk
kvstore> exit

Closing database...
Database closed.

#include "kvstore.h"

kvstore_t* kvstore_open(const char* path, size_t page_size);

Opens or creates a key-value store at the specified path. Set page_size to 0 for default (4096 bytes).

Returns: Pointer to kvstore or NULL on error.

int kvstore_put(kvstore_t* store, const char* key, const void* value, size_t value_len);

Inserts a new key-value pair or updates an existing one.

Parameters:

• store: Pointer to kvstore
• key: Null-terminated key string (max 256 bytes)
• value: Value data (any binary data)
• value_len: Length of value in bytes (max 4096 bytes)

Returns: KV_SUCCESS on success, error code otherwise.

int kvstore_get(kvstore_t* store, const char* key, void* value, size_t* value_len);

Retrieves the value associated with a key.

Parameters:

• store: Pointer to kvstore
• key: Null-terminated key string
• value: Buffer to store retrieved value
• value_len: Pointer to size; input: buffer size, output: actual value size

Returns: KV_SUCCESS on success, KV_NOT_FOUND if key doesn't exist, error code otherwise.

int kvstore_delete(kvstore_t* store, const char* key);

Deletes a key-value pair from the store.

Returns: KV_SUCCESS on success, KV_NOT_FOUND if key doesn't exist, error code otherwise.

int kvstore_sync(kvstore_t* store);

Forces all pending changes to be written to disk.

Returns: KV_SUCCESS on success, error code otherwise.

void kvstore_close(kvstore_t* store);

Flushes all changes and closes the database.

The database consists of two files:

The database file is organized into fixed-size pages:

• Page 0: Meta page containing:

  • Magic number (0x4B565354 - "KVST")
  • Version number
  • Page size
  • Root page ID
  • Next available page ID
  • WAL LSN (log sequence number)

• Page 1+: B-tree node pages containing:

  • Page header (type, page ID, checksum)
  • Node metadata (is_leaf, num_keys)
  • Keys and values (variable length)
  • Child page IDs (for internal nodes)

The WAL file contains transaction records for crash recovery:

• Each record has: LSN, type, page ID, data length
• Types: INSERT, DELETE, CHECKPOINT
• Replayed on recovery to restore consistency

┌─────────────┐
│     CLI     │  Interactive shell interface
└──────┬──────┘
       │
┌──────▼──────┐
│  KVStore API│  Public API layer
└──────┬──────┘
       │
┌──────▼──────┐
│   B-Tree    │  Indexing and search operations
└──────┬──────┘
       │
┌──────▼──────────┐
│  Page Manager   │  Disk I/O, caching, and WAL
└─────────────────┘
       │
┌──────▼──────┐
│  Disk Files │  .db and .wal files
└─────────────┘

• Minimum degree (t): 3 (configurable)
• Keys per node: 2t-1 = 5 maximum
• Children per node: 2t = 6 maximum
• Operations: O(log n) search, insert, delete

• Page cache: In-memory cache for recently accessed nodes
• Cache capacity: 128 pages (configurable)
• Write strategy: Write-ahead logging for durability
• Checksum validation: All pages checksummed

1. On startup, check meta page LSN
2. Replay WAL records newer than last checkpoint
3. Rebuild in-memory state
4. Truncate WAL after successful recovery

Smaller pages (512-2048 bytes):

• ✓ Less memory usage
• ✓ Faster individual page reads
• ✗ More I/O operations for large datasets
• ✗ Deeper B-tree (more disk seeks)

Larger pages (8192-16384 bytes):

• ✓ Better sequential I/O performance
• ✓ Shallower B-tree (fewer disk seeks)
• ✗ More memory usage
• ✗ Slower individual page reads
• ✗ More wasted space for small values

Default (4096 bytes): Balanced for most use cases

Lower degree (t=2-3):

• ✓ Simpler implementation
• ✓ Less memory per node
• ✗ Deeper tree (more disk I/O)

Higher degree (t=10+):

• ✓ Shallower tree (fewer disk seeks)
• ✓ Better cache locality
• ✗ More complex splitting
• ✗ More memory per node

Default (t=3): Good balance between simplicity and performance

With WAL:

• ✓ Crash recovery capability
• ✓ Data durability guarantees
• ✗ Extra write I/O overhead
• ✗ Additional disk space

Without WAL (not implemented):

• ✓ Faster writes
• ✓ Less disk usage
• ✗ No crash recovery
• ✗ Data loss on crashes

Larger cache (256+ pages):

• ✓ Fewer disk reads
• ✓ Better performance for hot data
• ✗ More memory usage
• ✗ Longer flush times

Smaller cache (32-64 pages):

• ✓ Less memory usage
• ✗ More disk I/O
• ✗ Slower for repeated access

Default (128 pages): ~512KB with 4KB pages

Expected performance characteristics:

• Sequential writes: ~10,000-50,000 ops/sec (depends on page size)
• Random writes: ~5,000-20,000 ops/sec
• Sequential reads: ~50,000-200,000 ops/sec (with caching)
• Random reads: ~10,000-50,000 ops/sec

Performance varies based on:

• Page size configuration
• Data size and access patterns
• Available system memory
• Disk speed (SSD vs HDD)

• Keys limited to 256 bytes
• Values limited to 4096 bytes
• No compression
• Simple B-tree (not B+ tree)
• No range queries
• No transaction support
• Single-threaded access
• No encryption

• B+ tree for better range queries
• Variable-length value support
• Compression (Snappy, LZ4)
• Multi-version concurrency control (MVCC)
• Bloom filters for faster negative lookups
• Log-structured merge tree (LSM) option
• Encryption at rest

Run basic tests:

make test

This will:

1. Create a test database
2. Insert key-value pairs
3. Retrieve values
4. Test persistence by reopening
5. Test deletion
6. Clean up test files

See LICENSE file for details.

Contributions are welcome! Please ensure:

• Code follows existing style
• Changes are well-documented
• Tests pass

Created as an embedded key-value store demonstration project.