Building Kedis: How I Built a Redis-Inspired In-Memory Data Store From Scratch

Exploring storage engines, custom data structures, networking, persistence, concurrency, and the engineering trade-offs behind an in-memory database.

Repository: Hogwarts-coder10/kedis-python
Language: Python
Project type: In-memory data store and systems engineering project

1. Why I Decided to Build Kedis

Most developers interact with databases through an API. We send a query, receive a result, and move on. The database handles everything else: data structures, memory allocation, persistence, networking, concurrency, and recovery.

But what actually happens between sending a command and getting a response?

How does a database organize its data? What happens when two clients modify the same key? How does an in-memory database survive a restart? And what makes a seemingly simple key-value store difficult to implement correctly?

I wanted to understand these questions beyond their theoretical explanations.

That led me to build Kedis, a Redis-inspired in-memory data store implemented from scratch in Python.

The goal wasn't simply to recreate a collection of Redis commands. I wanted to explore the architectural decisions behind systems that developers often treat as black boxes.

I started with the fundamentals of key-value storage and expanded the project to explore multiple data structures, a custom wire protocol, TCP networking, persistence, transactions, replication, and performance under concurrent workloads.

As the project grew, the interesting problems stopped being about implementing individual commands. They became questions about how different subsystems interact and what happens when their requirements conflict.

That is what made Kedis an interesting engineering project for me.

The objective was simple: build a system that would teach me how systems are actually put together.

2. Starting With the Storage Engine

At its core, an in-memory data store needs to associate keys with values and support operations on that data.

The most straightforward starting point is a key-value interface:

SET language Python
GET language

Conceptually, SET inserts or updates a value, while GET retrieves it.

A minimal implementation could use a Python dictionary. That would provide a working starting point, but it wouldn't teach me much about the different data structures that power database operations.

I wanted Kedis to support multiple kinds of data and expose the operations appropriate to each type.

The engine eventually supported:

• Strings for ordinary key-value storage.
• Lists for ordered collections.
• Sets for collections of unique members.
• Hashes for field-value mappings.
• Sorted sets for ordered members associated with scores.
• Streams for append-only event records and consumer-group workflows.

These aren't merely different command names. Each data type has its own semantics and performance considerations.

For example, a list supports operations such as LPUSH, RPUSH, and LPOP. A set supports operations such as SADD and SMEMBERS. A hash exposes field-oriented operations such as HSET and HGET.

A sorted set introduces another problem: how do you efficiently maintain an ordered collection while allowing insertion, lookup, and positional queries?

That question led to one of my favourite parts of the project.

3. Implementing a Skip List for Sorted Sets

I implemented a custom skip list for Kedis sorted sets, inspired by the approach used in Redis.

A skip list is a probabilistic data structure that maintains an ordered sequence using multiple levels of forward pointers.

Imagine a sorted linked list containing thousands of elements. Finding a particular element by walking through the list could require examining a large fraction of the collection.

A skip list adds express lanes.

The bottom level contains the elements in sorted order. Higher levels contain progressively sparser forward links, allowing a search to skip over large portions of the collection before descending to a more detailed level.

Under its usual randomized-level assumptions, a skip list provides expected O(log N) search and insertion performance.

That makes it useful for maintaining ordered data without implementing a more complicated self-balancing tree.

Why ordinary skip-list pointers weren't enough

Kedis also uses rank-aware span tracking.

A conventional skip list helps locate an element by its ordering. However, operations that need to determine an element's position or retrieve a range by rank require additional information.

Spans track how many bottom-level elements are crossed by a forward link. By maintaining this information across levels, the implementation can support positional queries more efficiently.

For example:

ZADD leaderboard 100 karthik
ZRANGE leaderboard

The first operation associates a score with a member. The second retrieves members in sorted order according to the implementation's command semantics.

The interesting part isn't the command itself. It's the structure underneath it.

I had to think about how insertion affects forward links, how spans change when nodes are added, and how the structure maintains consistency as elements are updated.

This is the kind of implementation detail that is easy to overlook when using a library but becomes very real when building the data structure yourself.

The skip list also gave me an opportunity to experiment with optimizations and benchmark them rather than assuming that a theoretically efficient algorithm would automatically be fast in Python.

The broader lesson was that choosing an algorithm is only the beginning. Its implementation, memory layout, and interaction with the surrounding system all matter.

4. Designing the Architecture

As Kedis grew, I needed a way to keep its responsibilities separate.

I organized the system around a pipeline that moves a request from the client to the storage engine and then returns a response.

The high-level architecture is:

                  Client
                    |
                    v
              Asyncio Server
                    |
                    v
                KESP Parser
                    |
                    v
               Command Router
                    |
                    v
               Storage Engine
               /            \
              v              v
        Persistence       Replication
            (AOF)          (Master
                             to
                           Replica)

Each component has a distinct responsibility.

The networking layer handles client connections. The parser translates incoming bytes into structured requests. The command router dispatches operations. The storage engine executes them against the appropriate data structures.

Persistence and replication integrate with the engine to handle concerns beyond ordinary in-memory reads and writes.

This separation was important because I didn't want protocol parsing, command execution, and data storage to become one tightly coupled piece of code.

A dedicated parser can be tested independently. The storage engine can be exercised without requiring a live network connection. Networking changes can be explored without having to redesign every data structure.

It also makes the project easier to extend.

For example, adding a command should primarily involve implementing its semantics and connecting it to the command-dispatch mechanism, rather than rebuilding the entire request-handling pipeline.

The architecture is intentionally modular because Kedis is also an environment for experimenting with alternative implementations.

5. Building KESP: My Own Wire Protocol

One of the important design decisions in Kedis was implementing a custom wire protocol called KESP — Kedis Serialization Protocol.

Redis uses RESP, its own serialization protocol, for communication between clients and the server. I decided not to adopt RESP as the protocol for Kedis.

Instead, Kedis implements KESP with explicit byte-length framing.

Why does framing matter?

TCP provides a reliable, ordered byte stream. It does not preserve application-level message boundaries.

Suppose a client sends a command over a socket. A server might receive the bytes in one read, several reads, or alongside bytes from a subsequent command.

A call to recv() does not guarantee that the returned bytes correspond to exactly one complete request.

A naive server that assumes one socket read equals one command can therefore encounter incomplete messages or incorrectly grouped requests.

Explicit length-prefix framing provides a way to determine how many bytes belong to a message.

Conceptually, the receiver can:

1. Read enough bytes to determine the message length.
2. Determine how many payload bytes are expected.
3. Read until the complete payload has arrived.
4. Decode the message and pass the resulting request to the command router.

The exact framing rules must be defined by the protocol, including how lengths are represented and how invalid or oversized frames are handled.

KESP's encoder and decoder live in a dedicated parser module rather than being embedded in the networking implementation.

That separation matters. A protocol is an interface between independently operating components, not just a convenient way to turn Python objects into bytes.

It must define message boundaries clearly and behave predictably when data arrives in inconvenient chunks.

Building KESP taught me to think about the network boundary explicitly. Once a system communicates through sockets, it can no longer rely on the assumptions that are convenient inside a single process.

6. Moving to Asyncio Networking

Kedis originally used a threaded networking implementation. I benchmarked that design and eventually moved the networking layer to asyncio.

This was not a decision based solely on the popularity of asynchronous programming. It came from investigating the behaviour of the system under increasing concurrency.

The original threaded implementation

Threads provide a relatively intuitive way to handle concurrent client connections. Multiple threads can wait for network activity independently, and the operating system schedules them as they become runnable.

However, Python's Global Interpreter Lock (GIL) affects how Python bytecode executes in conventional CPython builds.

Kedis also used a global mutex to serialize access to shared state in its original core routing engine.

That mutex protected the shared state, but it meant that concurrent operations could contend for the same critical section.

These constraints didn't make threading useless. They meant that the design had a concurrency ceiling worth measuring.

What the benchmarks showed

The repository documents the following throughput results for the original threaded implementation:

The results show a clear pattern.

Throughput increased as the number of threads grew from one to ten. Beyond that point, performance declined.

The peak recorded result was approximately 21,492 requests per second at ten threads. At fifty threads, throughput fell to approximately 10,977 requests per second.

This is a useful example of why concurrency should be measured rather than assumed to improve performance.

Adding threads can help overlap waiting on network I/O. But more threads also introduce scheduling overhead, lock contention, and additional coordination.

The GIL and global mutex were identified in the project documentation as important contributors to the observed limitations.

No data corruption was observed in the documented stress tests up to fifty threads. That is useful evidence about those particular tests, although it is not a proof of correctness under every possible workload.

Why asyncio?

The networking layer now uses asyncio, allowing many client connections to be handled through an event loop rather than requiring a dedicated operating-system thread for every connection.

This is particularly relevant for workloads where connections spend a significant amount of time waiting for network input or output.

Asynchronous networking can reduce the overhead associated with managing many waiting connections. It does not, however, automatically make CPU-bound Python code parallel or eliminate contention in shared state.

That distinction matters.

Moving to asyncio changes the concurrency model of the networking layer. It doesn't magically make every operation faster, and the performance characteristics still depend on the workload and the implementation.

The original threaded measurements explain the motivation for the transition. They should not be interpreted as a direct performance comparison between the old and new implementations.

For me, this was one of the most valuable lessons from Kedis: a benchmark is not just a number to put in a README. It is evidence that helps guide an engineering decision.

7. Making an In-Memory Store Persistent

An in-memory database is attractive partly because memory operations can be fast. But memory is volatile.

If the process exits, its in-memory state disappears unless the system has a mechanism to recover that state.

Kedis implements persistence through an append-only file, or AOF.

The general idea is to record write operations in a log so that the system can reconstruct its state during startup.

Instead of relying exclusively on the current contents of memory, the engine can use its persisted operation history to recover data after a restart.

Kedis documents support for durable write logging, automatic startup recovery, and AOF compaction.

Compaction is important because an append-only log can grow as operations accumulate. Rewriting or compacting the log helps manage its size and the amount of historical data that must be retained.

The durability-throughput trade-off

The AOF implementation exposes different synchronization policies. Two documented configurations are appendfsync always and appendfsync everysec.

The repository reports these benchmark results:

These measurements were obtained on localhost with a single thread and a workload of 100,000 total operations: 50,000 SET operations and 50,000 GET operations.

The difference is substantial.

With appendfsync always, the system prioritizes durability by synchronizing writes to disk after each write. This can impose significant latency and reduce throughput.

With appendfsync everysec, synchronization is batched more aggressively, improving throughput while accepting a larger potential window of data loss during a crash.

The repository describes that window as up to approximately one second of writes.

Neither setting is universally better. They represent different trade-offs between durability requirements and performance.

A cache that can reconstruct its contents may tolerate a different risk profile from a system storing critical state. The correct choice depends on what the application expects from persistence.

There is also an important distinction between writing data to a file and guaranteeing that the data has reached durable storage. Buffering, synchronization, operating-system behaviour, and hardware all affect the final result.

Kedis is an educational systems project, and its documented limitations include unbuffered AOF writes and simplified memory accounting. The persistence layer remains an area for improvement.

Implementing AOF made one thing particularly clear to me: adding persistence isn't just a matter of saving a dictionary. It introduces a new set of failure modes and performance trade-offs.

8. Transactions and Optimistic Locking

A database must also handle operations that involve multiple commands.

Kedis supports transactional execution through commands such as MULTI and EXEC.

For example:

MULTI
SET account_a 100
SET account_b 200
EXEC

This illustrates a group of operations submitted for transactional execution.

The important engineering question is how the system handles a transaction when other clients may be modifying shared state.

Kedis also supports optimistic locking through WATCH and UNWATCH.

Consider a client that reads an account balance, calculates a new value, and then attempts to update it. If another client changes the same key between the initial observation and the attempted commit, the first client's calculation may be based on stale state.

Optimistic locking provides a way to detect this situation.

Conceptually, a client watches a key, prepares a transaction, and attempts to execute it. If the watched key changes before the transaction commits, the transaction is aborted rather than proceeding as though the original state were still valid.

This is particularly relevant to read-modify-write operations, where a stale read can otherwise lead to lost updates.

Transactions are not simply a feature that makes a command-line interface more convenient. They require careful reasoning about state changes, isolation, and what clients are allowed to observe.

The exact guarantees depend on the implementation, so it is important not to assume that supporting MULTI and EXEC automatically provides every isolation property of a production relational database.

9. Adding Streams and Consumer Groups

As Kedis evolved, I expanded it beyond conventional key-value operations to include streams and consumer groups.

Streams represent append-only event records. They are useful when the data model is closer to an event log than a single mutable value.

Kedis documents operations such as:

XADD orders * item book qty 2
XREAD BLOCK 5000 STREAMS orders $

The first command appends an event to a stream. The second illustrates reading from a stream with a blocking option.

Consumer groups introduce another layer of complexity. Instead of every consumer independently processing the same sequence, a group can distribute stream entries across workers.

Kedis documents group creation, group reads, pending-entry tracking, and acknowledgements:

XGROUP CREATE orders shipping 0
XREADGROUP GROUP shipping worker1 COUNT 10 STREAMS orders >
XPENDING orders shipping
XACK orders shipping 1718000000000-0

The underlying concepts are more involved than ordinary GET and SET operations.

The system must track stream entries and identifiers, manage pending work, and record acknowledgements. Consumers need a way to distinguish work that has been delivered from work that has been acknowledged.

The project also documents persistence and replication support for streams, including preservation of stream IDs and consumer-group state.

This made streams a useful extension of the original storage-engine idea. They brought more stateful workflows into the same architecture and created additional requirements for testing, persistence, and replication.

The current implementation does not claim complete compatibility with every Redis Streams feature. For example, the README lists XCLAIM and XAUTOCLAIM as missing.

That limitation is worth documenting honestly. A useful systems project can explore an architectural concept without implementing every feature of the production system that inspired it.

10. Replication: From One Process to Multiple Nodes

An in-memory store running on one machine is a useful starting point, but replication introduces a different class of problems.

Kedis supports master-replica replication.

The documented workflow involves a replica connecting to a master, performing a SYNC handshake to receive the initial dataset, and receiving subsequent writes from the master.

Replicas are read-only, and direct writes to a replica are rejected.

At a high level, the architecture looks like this:

              Client writes
                    |
                    v
                Kedis Master
                    |
           Initial sync + updates
                    |
             +------+------+
             |             |
             v             v
         Replica A      Replica B
         Read-only      Read-only

The diagram illustrates the documented master-to-replica relationship rather than a complete description of every internal synchronization detail.

Replication raises questions that do not exist in a purely local store.

How does a new replica obtain the existing dataset? How does it receive subsequent writes? What happens if the connection breaks? How should the replica behave while it is catching up?

A correct replication design must consider the ordering and completeness of state transfer, not merely the act of sending commands across a socket.

Kedis provides an environment for exploring these issues while keeping the implementation manageable.

It is not intended to provide all the fault-tolerance and recovery guarantees of a production distributed database. That distinction is important: supporting replication is not the same as guaranteeing strong consistency or uninterrupted availability under every failure scenario.

Still, implementing the feature helped broaden the project from a local data structure exercise into a more complete exploration of backend architecture.

11. Memory Management and Key Expiration

Another part of the project concerns the lifecycle of stored data.

Kedis supports key expiration through commands such as:

EXPIRE session 60
TTL session

Expiration allows a key to become invalid after a specified period. This is useful for temporary values such as sessions, short-lived cache entries, and other data that should not remain indefinitely.

The project also includes LRU-based eviction support.

LRU stands for Least Recently Used. The idea is to track key usage and identify entries that have not been accessed recently.

In a memory-constrained system, this policy can help decide which entries to remove when space is needed.

However, tracking usage and enforcing a memory ceiling are separate capabilities.

Kedis's documented limitations explicitly state that LRU tracking is not yet tied to a hard memory limit. Its memory accounting is also simplified.

That distinction matters because an eviction policy cannot, by itself, guarantee that a process stays within a particular memory budget.

Building these features encouraged me to think about memory as a resource that the engine must manage deliberately, rather than treating the Python runtime as an invisible implementation detail.

12. Testing the System

A systems project becomes much more interesting when its components must work together.

Testing an individual command is useful, but it is not enough to establish that the complete system behaves correctly.

A command may work against the storage engine but fail when requests are split across TCP reads. A write may succeed in memory but fail to survive a restart. A data structure may behave correctly in isolation but expose a bug when several components interact.

Kedis includes automated tests covering command execution, data structures, persistence recovery, expiration, streams, and consumer-group workflows, including tests that exercise live TCP sessions.

The repository also documents a dedicated testing structure and notes that coverage is still being expanded.

For me, this is an important part of building systems: testing needs to follow the architecture.

The storage engine needs tests for data-structure invariants. The protocol needs tests for encoding and decoding. The persistence layer needs recovery tests. Networking needs tests that exercise real connections. Stateful features such as consumer groups need tests that cover transitions between pending and acknowledged work.

No finite test suite proves that a system is bug-free. But carefully chosen tests make it much easier to detect regressions and reason about changes.

They also give future contributors a clearer way to verify that modifications have not broken existing behaviour.

13. What the Benchmarks Actually Tell Us

I want to be careful about how I present performance results.

The AOF measurements and the original threading measurements tell us something useful about Kedis, but they answer different questions.

The AOF benchmark compares two persistence synchronization configurations under a documented workload. The threading benchmark examines how the original threaded implementation behaved as the number of threads increased.

They should not be combined into one overall performance claim.

For reference, the documented results are:

These are measurements from the project's own benchmark documentation. They are not independently reproduced results, and the different experiments should not be treated as directly comparable.

A useful benchmark report should ideally include the hardware, software environment, exact workload, client configuration, number of operations, and the methodology used to collect results.

It should also distinguish throughput from latency. A system can achieve high aggregate throughput while still delivering poor tail latency for individual requests.

Likewise, a benchmark on localhost says something different from a benchmark across a real network.

I see benchmarking as an iterative process: measure a workload, identify a likely bottleneck, change one part of the implementation, and measure again under comparable conditions.

The point is not to produce the largest number possible. It is to understand why the system behaves the way it does.

14. What I Would Improve Next

Kedis is an educational systems project, not a production-ready database.

The repository already identifies several areas for future work, including buffered AOF persistence, improved observability, memory-based eviction, better benchmark tooling, and additional persistence optimizations.

These are meaningful engineering problems rather than cosmetic additions.

Buffered persistence, for example, could reduce the overhead associated with writing and synchronizing individual operations, but it would also require careful reasoning about flushing, failure recovery, and durability guarantees.

Improved observability could make it easier to understand how the engine behaves under different workloads, particularly when investigating latency, persistence overhead, and contention.

Benchmark tooling could help make performance experiments more reproducible and make it easier to compare different versions of the implementation.

Beyond these documented priorities, I would also want to continue investigating protocol edge cases, failure handling, transaction semantics, and replication behaviour under disconnects and restarts.

The important thing is to approach these improvements systematically. A feature that works under normal conditions may behave very differently when the process crashes, the network disconnects, or multiple clients modify the same state.

That is where much of the real systems engineering work begins.

15. What Building Kedis Taught Me

Building Kedis changed how I think about backend systems.

A database is not just a dictionary with a socket attached to it. It is a collection of interacting subsystems, each with its own correctness requirements and performance trade-offs.

Implementing the skip list taught me to reason about data structures beyond their asymptotic complexity.

Building KESP made me think about framing, byte streams, and the boundary between a client and a server.

Implementing AOF persistence exposed the relationship between durability and throughput.

Benchmarking the threaded implementation showed why adding concurrency does not necessarily improve performance indefinitely.

Transactions and replication introduced questions about state changes, coordination, and failure handling that do not appear in a simple local key-value store.

Streams and consumer groups expanded the problem further by introducing event history and stateful processing workflows.

Most importantly, these features forced me to think about how individual design decisions affect the rest of the system.

The choice of a network model affects how connections are handled. The persistence strategy affects write latency. The data structure affects the complexity of individual operations. The protocol determines how messages are represented and parsed. The testing strategy determines how confidently these components can be changed.

None of these decisions exists in isolation.

I also learned that implementing a feature and implementing it robustly are two different milestones. A working implementation is a valuable start, but it still needs testing, failure analysis, performance evaluation, and clear documentation.

That is one of the reasons I wanted to build Kedis instead of stopping at a theoretical understanding of databases.

Conclusion

Kedis started as a way to understand in-memory data stores and evolved into a broader exploration of systems engineering.

It now brings together a custom storage engine, five conventional data types plus streams, a skip-list implementation for sorted sets, a custom binary-safe wire protocol, asynchronous networking, append-only persistence, transactions, expiration, eviction tracking, replication, and automated tests.

There is still plenty of work to do. The project has known limitations, and I do not consider it a replacement for production databases.

But that was never the only point.

I wanted to understand what happens beneath the interfaces we use every day, and building Kedis gave me a way to investigate those questions through implementation, measurement, and iteration.

The most valuable outcome wasn't a particular benchmark number or a long list of supported commands. It was learning to look at a backend system as a collection of interacting components whose behaviour must be understood, measured, and tested.

And that is what I want to keep exploring as I work on more systems projects.

Kedis was built to understand systems, not just use them.

Explore the project

• Source code: github.com/Hogwarts-coder10/kedis-python
• Installation: kedis-python on PyPI
• Contributions and feedback: Issues and discussions are welcome on GitHub.

If you're interested in data structures, database internals, networking, or backend systems, I'd love for you to explore the project and share your thoughts.