Building YKV: A Key-Value Database from Scratch in C
Motivation
One of the best ways to learn a programming language, concept, or framework is to build something with it. I have always been curious about how databases work internally, and since many popular database systems have significant portions of their codebases written in C, I decided that one of the best ways to deepen my understanding of the language was to build a database from scratch.
At the same time, I wanted to gain a deeper understanding of network programming, concurrency, memory management, persistence, and replication—not simply by reading about these concepts, but by encountering the problems that make them necessary and implementing solutions myself. YKV, a simple distributed key-value database written in C, is the result of that learning journey.
Features
YKV currently supports:- A custom TCP wire protocol
- Event-driven networking using Linux epoll
- Per-client connection state and buffered I/O
- A fixed worker-thread pool for query execution
- An in-memory hash map with dynamic resizing and separate chaining
- SET, GET, and DEL operations
- Write-ahead logging for persistence and recovery
- Primary-replica replication
- Custom memory allocation wrappers with leak tracking
- A Spring Boot HTTP API and web-based client
Architecture
High-Level Architecture
User │ ▼ React Web Client │ HTTP/HTTPS ▼ Spring Boot API │ Custom TCP Protocol ▼ YKV Primary │ WAL Replication ▼ YKV Replica
The application comprises a web UI built with angular, a springboot api, then ykv primary service and one ykv replication service. The web UI is essentially a tiny client that aids in performing database operations: setting a key, getting a key, deleting a key, etc.
The web UI communicates with the Spring Boot API over HTTP, while the Spring Boot API communicates with YKV through a custom TCP protocol. YKV processes read and write operations, persists writes to a Write-Ahead Log (WAL), and streams write commands from the primary node to the replica. The replica maintains a redundant copy of the database.
When the Spring Boot API has active connections to both the primary and replica, GET requests are served by the replica, while write operations are directed to the primary. If either node becomes unavailable, the Spring Boot API redirects requests to the remaining active node, allowing the application to continue operating in a degraded single-node mode.
This introduces an important consistency challenge. If one node accepts writes while the other is unavailable, the two databases may contain different states when the unavailable node comes back online. YKV does not yet implement automatic WAL synchronization, replication offsets, or state reconciliation between recovering nodes. This functionality is therefore documented as future work for a later version.
Deployment Architecture
┌─────────────────────┐
│ User │
│ Web Browser │
└──────────┬──────────┘
│
HTTPS
│
▼
┌─────────────────────┐
│ CloudFront │
│ CDN │
└──────────┬──────────┘
│
▼
┌─────────────────────┐
│ Amazon S3 │
│ │
│ YKV SPA │
└──────────┬──────────┘
│
HTTP / HTTPS
│
▼
┌────────────────────────────────┐
│ EC2 Instance 1 │
│ │
│ ┌──────────────────┐ │
│ │ Nginx │ │
│ │ Reverse Proxy │ │
│ └────────┬─────────┘ │
│ │ │
│ ▼ │
│ ┌──────────────────┐ │
│ │ Spring Boot API │ │
│ └────────┬─────────┘ │
└───────────────┼────────────────┘
│
Custom TCP Protocol
│
┌────────────────┴────────────────┐
│ │
▼ ▼
┌───────────────────────┐ ┌───────────────────────┐
│ EC2 Instance 2 │ │ EC2 Instance 3 │
│ │ │ │
│ YKV Primary │───────▶│ YKV Replica │
│ │ Stream │ │
│ ┌─────────────────┐ │ Writes │ ┌─────────────────┐ │
│ │ In-Memory Map │ │ │ │ In-Memory Map │ │
│ └─────────────────┘ │ │ └─────────────────┘ │
│ │ │ │
│ ┌─────────────────┐ │ │ ┌─────────────────┐ │
│ │ WAL │ │ │ │ WAL │ │
│ └─────────────────┘ │ │ └─────────────────┘ │
└───────────────────────┘ └───────────────────────┘
The web UI is a SPA on Amazon S3, and exposed via cloudfront. The springboot API runs in an ec2 instance behind an nginx proxy while both primary and replica nodes run on independent EC2 instances.
Network Layer
Ykv implements an event-driven TCP networking layer designed to handle multiple concurrent client connections efficiently. Ykv uses Linux epoll instead of having per-thread connections. A dedicated thread runs the event loop where connections are handled, incoming bytes are received, processed through various client states, and then dispatched to worker queues where worker threads pick them up for execution.
TCP Clients
┌────────┼────────┐
▼ ▼ ▼
Client 1 Client 2 Client 3
│ │ │
└────────┼────────┘
▼
Listening Socket
│
▼
epoll_wait()
│
┌────────────┴────────────┐
▼ ▼
New Connection Data Available
│ │
▼ ▼
accept() recv()
│ │
▼ ▼
Create Client State Append to Buffer
│
▼
Protocol State Machine
│
┌────────┴────────┐
▼ ▼
Incomplete Command Complete Command
│ │
▼ ▼
Wait for More Data Worker Queue
Linux Epoll
The reason I picked epoll was to avoid the inefficiencies of earlier technologies like polling where a complete set of clients has to be iterated over continuously. With epoll, only the ready clients are looped over, thus more efficient. So once the listening server and epoll instance are created, the listening socket is registered.
YKV holds a maximum of 1024 connections, and these clients are held in a clients array where the index is the fd of the active client. While I was tempted to use a map for this to ensure I can handle file descriptors greater than 1024, I opted for the array for this first version as it gives O(1) lookup (Client *client = db_context->clients[client_fd]). And for a demo application, I believe 1024 connections is well sufficient.
Per Client State
Each client has a state for a couple of reasons. One is because TCP is a byte stream and does not preserve application message boundaries; we need a way to store 'message received so far' while the event loop runs over and over. The next obvious one is that we use an event loop, and on each iteration data stored in local variables is rewritten, hence the need for persistent storage.
Protocol Framing
A length-prefixed custom protocol was used. A message conceptually looks like
Client State Machine
With the per state client and the protocol framing described above, each client can be in one of three states so that within the event loop, the appropriate operation can be carried out. When in the READING_HEADER state, continue to read till you find new line and move state to READING_COMMAND. When in the reading command state, continue to read till all expected bytes are read then move state to COMMAND_READY. Once the command is ready, prepare the task and dispatch to the queue so a worker thread can pick it up.
┌─────────────────┐
│ READING_HEADER │
└────────┬────────┘
│ newline found
▼
┌─────────────────┐
│ READING_COMMAND │
└────────┬────────┘
│ expected bytes received
▼
┌─────────────────┐
│ COMMAND_READY │
└────────┬────────┘
│ dispatched
▼
┌─────────────────┐
│ READING_HEADER │
└─────────────────┘
Event Loop
The event loop is an endless loop responsible for monitoring client connections and responding to I/O events. YKV uses Linux epoll to efficiently monitor multiple file descriptors and determine when a socket is ready for reading or writing.
When a client socket generates an EPOLLIN event, the server reads the available data from the socket and processes it according to the client's current protocol state. When a client generates an EPOLLOUT event, the server attempts to send the prepared response back to the client.
One interesting challenge arose from the separation between the event loop thread and worker threads. The event loop is responsible for socket I/O, while worker threads execute database commands. Once a worker thread finishes executing a query and prepares the response, the event loop needs to be notified that the corresponding client is now ready to transition from read mode to write mode.
To solve this, YKV creates a Linux eventfd during database initialization and registers it with the same epoll instance used to monitor client sockets. When a worker finishes processing a query, it places the completed task in a completed-task queue and writes to the eventfd. This causes epoll_wait() to wake and report the eventfd as ready.
The event loop recognizes this special event, drains the completed-task queue, and changes the corresponding client sockets to write mode by registering interest in EPOLLOUT. On a subsequent event-loop iteration, epoll reports those sockets as writable, allowing the prepared responses to be sent back to their respective clients.
Threads
YKV uses a small, fixed number of threads, with each thread assigned a specific responsibility. This prevents potentially blocking or computationally expensive operations from stalling the event loop. Mutexes are used to lock queues when enqueuing and dequeuing to prevent collisions and race conditions.
The I/O thread runs the event loop and is responsible for accepting new connections, monitoring client sockets through epoll, reading incoming data, managing client state, and sending responses. The event loop does not directly execute database commands.
Two worker threads are responsible for query execution. Once the I/O thread has received and parsed a complete command, it creates a task and places it onto a shared task queue. An available worker thread dequeues the task, executes the corresponding database operation, prepares the response, places the completed task onto the completed-task queue, and signals the event loop through eventfd.
A dedicated WAL thread handles writes to the Write-Ahead Log. Separating WAL persistence from the event loop prevents disk I/O from blocking network operations and allows the server to continue accepting and processing client connections while persistence work is handled independently.
The threading architecture can be summarized as:
┌───────────────────┐
│ I/O Thread │
│ │
│ epoll_wait() │
│ accept() │
│ recv() │
│ send() │
└─────────┬─────────┘
│
Task Queue
│
┌────────────┴────────────┐
▼ ▼
┌─────────────────┐ ┌─────────────────┐
│ Worker 1 │ │ Worker 2 │
│ │ │ │
│ Execute queries │ │ Execute queries │
└────────┬────────┘ └────────┬────────┘
│ │
└────────────┬────────────┘
│
Completed Task Queue
│
eventfd signal
│
▼
I/O Thread
┌───────────────────┐
│ WAL Thread │
│ │
│ Persist writes │
│ to disk │
└───────────────────┘
In-Memory Database
YKV uses a custom-built, in-memory hash map as its primary data structure for storing key-value pairs. The hash map provides average-case O(1) insertion, retrieval, and deletion. Rather than relying on an external collection library, the data structure was implemented from scratch to provide direct control over memory allocation, collision handling, dynamic resizing, and integration with YKV's custom memory manager.Hash Map Structure
The hash map is created with an initial capacity. On each insertion, the load factor is computed, and the map is resized once it reaches 75% of its capacity. The map maintains three primary pieces of information:
Size: The number of key-value pairs currently stored.Capacity: The number of available buckets.
Buckets: An array of pointers to bucket entries. Each bucket may serve as the head of a linked list when collisions occur.
Hashing
YKV uses the DJB2 hash function to transform a string key into an unsigned integer. For each character in the key, the current hash value is shifted left by five bits and added to itself, effectively multiplying the current hash by 33. The numeric value of the current character is then added to the result.
Conceptually:
new_hash = (old_hash × 33) + current_character
Once the complete hash has been calculated, the target bucket is determined using:
bucket_index = hash(key) % capacity
This ensures that the resulting bucket index falls within the current bounds of the bucket array.
Collision Handling
After a key has been hashed, another entry may already exist in the resulting bucket. YKV handles these collisions using separate chaining, in which each bucket serves as the head of a linked list. When inserting a new key into an occupied bucket, head insertion is used: Before:Bucket 3 → [A] → [B] → [C]
Insert [D]:
Bucket 3 → [D] → [A] → [B] → [C]
Head insertion avoids traversing the existing chain during insertion and therefore takes O(1) time once the correct bucket has been determined. Retrieving an item requires traversing only the linked list associated with its bucket. In the worst case, if many keys collide into the same bucket, retrieval can degrade to O(n). However, with a good hash distribution and appropriate resizing, entries should remain reasonably distributed across available buckets.
Dynamic Resizing
As the number of stored entries grows, YKV monitors the hash map's load factor. Once the configured threshold of 75% is reached, the bucket array is doubled in capacity, and all existing nodes are redistributed according to their new bucket indices.
For example, if the previous capacity is 4, the new capacity becomes 8:
BEFORE RESIZE — Capacity 4
Bucket 0 → [A] → [E]
Bucket 1 → [B]
Bucket 2 → NULL
Bucket 3 → [C]
AFTER RESIZE — Capacity 8
Bucket 0 → [A]
Bucket 1 → NULL
Bucket 2 → [B]
Bucket 3 → [C]
Bucket 4 → [E]
Bucket 5 → NULL
Bucket 6 → NULL
Bucket 7 → NULL
Because the bucket index is calculated using hash(key) % capacity, changing the capacity may change the correct bucket for every existing key. Therefore, all nodes must be rehashed and redistributed during resizing.
The existing MapNode objects themselves do not need to be reallocated. Instead, YKV relinks them into the appropriate buckets of the new bucket array. Once redistribution is complete, the old bucket array is freed.
Memory Management
YKV uses a custom memory management layer that wraps the standard C malloc, calloc, strdup, and free functions. The goal was not to replace the system allocator, but to provide visibility into how memory is allocated and released throughout the lifetime of the database.
Each allocation is tracked in a linked list containing the allocated address, size, source file, and line number where the allocation occurred. Macros automatically capture this information using __FILE__ and __LINE__, allowing memory usage to be traced back to its origin.
Allocation ├── address ├── size ├── file name ├── line number └── next
The memory manager also maintains statistics including total allocations, deallocations, bytes allocated, bytes freed, and peak memory usage. When kv_free is called, the corresponding allocation is located in the tracking list, its statistics are updated, the memory is released, and its tracking record is removed.
This proved particularly useful during development. For example, the memory manager exposed an allocation/deallocation mismatch caused by the old bucket array not being freed after a hash map resize. The custom wrappers therefore became both a memory-tracking system and a debugging tool for reasoning about memory ownership and detecting leaks in YKV.
CRUD Operations
SET: Inserts a new key-value pair or replaces the value associated with an existing key. Returns OK when successful.
GET: Retrieves the value associated with a key. If the key exists, its value is returned; otherwise, NULL is returned.
DEL: Deletes a key-value pair. If the key exists and is successfully deleted, OK is returned; otherwise, NULL is returned
Write Ahead Log
YKV uses a Write-Ahead Log (WAL) to provide persistence for write operations. Since the primary database is held in memory, all stored data would otherwise be lost when the database process terminates or the server restarts.
Before a write operation is considered complete, a representation of the operation is written to the WAL. This creates a persistent history of changes made to the database that can later be replayed to reconstruct the in-memory state.
WAL writes are handled by a dedicated thread. This separates disk I/O from the main event loop and worker threads, preventing file operations from blocking the networking layer. Write operations are submitted to the WAL thread through a queue, allowing persistence work to be handled independently of network I/O.
When YKV starts, the WAL is replayed to reconstruct the database state. Each recorded operation is read in sequence and applied to the in-memory hash map, restoring keys and values that existed before the previous shutdown.
The WAL therefore serves two primary purposes: preserving database state across restarts and maintaining an ordered record of write operations. Because the WAL is append-only, new operations can be written sequentially without rewriting the entire database state for every change.
Request Lifecycle
A request to YKV passes through several layers of the system before a response is returned to the client. Consider the following command: SET name David. The complete request lifecycle is:
Client │ │ TCP request ▼ Listening Socket │ ▼ epoll_wait() │ │ EPOLLIN ▼ I/O Thread │ │ Reads available bytes ▼ Client Input Buffer │ ▼ Protocol State Machine │ │ Complete command detected ▼ Task Queue │ ▼ Worker Thread │ ├──────────────► Execute operation against Hash Map │ ├──────────────► Submit write operation to WAL │ └──────────────► Replicate operation to Replica │ ▼ Response Prepared │ ▼ Completed Task Queue │ ▼ eventfd signaled │ ▼ epoll_wait() wakes │ ▼ I/O Thread processes eventfd │ ▼ Client registered for EPOLLOUT │ ▼ Socket becomes writable │ ▼ Response sent to client
When data arrives on a client socket, epoll generates an EPOLLIN event. The I/O thread reads the available bytes into the client's input buffer. Because TCP is a byte-stream protocol and does not preserve message boundaries, YKV maintains per-client state to determine whether a complete request has been received.
Once a complete command has been assembled, it is placed onto a shared task queue. One of the two worker threads dequeues the task, parses and executes the requested database operation, and prepares a response. For write operations, the change may also be persisted through the Write-Ahead Log and propagated from the primary database to the replica.
Once query processing is complete, the worker places the completed task onto a completed-task queue and writes to the database's eventfd. Because the eventfd is registered with the same epoll instance as the client sockets, this wakes the event loop.
The I/O thread then processes the completed-task queue and changes the appropriate client's interest to EPOLLOUT. When the socket is ready for writing, the response is sent to the client, after which the connection returns to read mode and waits for another command.
Current Limitations
YKV is intentionally a small database built to explore the internals of networking, memory management, storage, concurrency, persistence, and replication. Its current design therefore has several known limitations.
Limited command set. YKV currently supports basic SET, GET, and DEL operations and does not yet provide richer data structures, transactions, expiration policies, or advanced query capabilities. Other simple commands like PING and INFO help the spring API check health and the info provides some metrics. Single primary and single replica. The current replication architecture supports one primary and one replica.
There is no automatic leader election, replica discovery, quorum-based replication, or consensus protocol. No automatic failover. If the primary database becomes unavailable, the replica is not automatically promoted to primary. Recovery currently requires external intervention.
Fixed client lookup capacity. Client connections are stored in an array indexed by file descriptor. This provides O(1) client lookup but requires the file descriptor to remain within the configured client-table bounds.
Limited protocol state management. The current implementation handles the states required by the existing client and replication protocols, but a more explicit connection state machine would provide a cleaner foundation as additional protocol phases and replication behaviors are introduced.
Simple concurrency model. YKV currently uses a single I/O thread, two query worker threads, and a dedicated WAL thread. The number of workers is fixed rather than dynamically configured according to workload or available hardware. Coarse-grained data access. As concurrency increases, synchronization around the shared in-memory map may become a bottleneck. More granular locking, sharding, or lock-free techniques could improve parallelism. No authentication or transport encryption at the database protocol layer. The custom TCP protocol currently focuses on database communication rather than authentication, authorization, or TLS. In-memory dataset constraints. The active dataset is stored entirely in memory and is therefore limited by available RAM. YKV does not currently implement disk-backed pages, buffer pools, eviction policies, or tiered storage. Basic observability. Although the custom memory manager tracks allocations, deallocations, allocation sizes, source files, and line numbers, the database does not yet expose a complete production-grade metrics, tracing, or monitoring system.
Future Work
Future development of YKV will focus on improving reliability, scalability, observability, and the clarity of its internal architecture while preserving its role as a systems-engineering project built largely from first principles.
Potential improvements include introducing a more explicit connection state machine for both normal clients and replication connections. States such as reading headers, reading payloads, executing commands, waiting for replication acknowledgements, streaming replication data, and writing responses could make connection behavior easier to reason about as the protocol evolves.
The replication subsystem could be expanded beyond a single primary-replica pair. Possible additions include replica reconnection, partial resynchronization, replication offsets, heartbeats, automatic replica promotion, and eventually leader election or consensus-based coordination.
Persistence could be strengthened through configurable WAL durability policies, WAL rotation, log compaction, snapshots, checksums, and crash-recovery testing. Combining periodic snapshots with WAL replay would prevent startup time and log size from growing indefinitely as more operations are executed.
The custom memory manager could evolve into a richer diagnostic subsystem capable of reporting outstanding allocations, grouping memory usage by source file or subsystem, displaying memory in human-readable units such as KiB and MiB, identifying the largest allocations, and distinguishing process-lifetime allocations from connection- and request-lifetime allocations.
The networking layer could support dynamically sized client tables based on the operating system's file-descriptor limits rather than relying on a fixed MAX_CLIENTS value. Additional work could also include configurable worker counts, backpressure, connection timeouts, graceful shutdown, and more sophisticated handling of slow clients.
The database itself could eventually support additional features such as key expiration, TTLs, atomic counters, multiple value types, batch operations, transactions, snapshots, and alternative storage structures.
Finally, the deployment architecture could evolve to include automated service discovery, private networking between database nodes, health checks, automatic restart and recovery, infrastructure as code, monitoring dashboards, and automated deployment pipelines.
YKV is not intended to compete with mature production databases. Its purpose is to explore how the fundamental components of a database system fit together: network I/O, protocol framing, concurrency, in-memory storage, persistence, replication, memory ownership, and failure handling. Future improvements will continue to deepen these areas while keeping the implementation understandable enough to study from first principles.