From Zero to Thread-Safe: Building the Foundation of a Distributed Key-Value Store

Building a distributed system from scratch is one of the most rewarding ways to learn how the tools we rely on every day actually work under the hood. Over this tutorial series, we will evolve a simple Java application into a fully-fledged distributed key-value store modeled after systems like Amazon DynamoDB and Apache Cassandra.

By the end of this series, our system will feature:

• Durability: Write-Ahead Logging (WAL) and SSTables to persist data across crashes.
• Scalability: Consistent hashing to distribute data evenly across a dynamic cluster.
• High Availability: Peer-to-peer gossip protocol for failure detection and hinted handoff for self-healing.
• Fault Tolerance: Asynchronous quorum replication and tunable consistency.
• Conflict Resolution: Vector clocks for detecting and resolving concurrent modifications.

(You can follow along with the complete source code for the finished project here: https://github.com/rahulch07/kvstore)

But every complex system starts with a simple foundation. In this first article, we’ll start at the very beginning: building a basic in-memory store and uncovering the hidden dangers of concurrent access.

The Naive Approach: Starting with a HashMap

Commits covered in this milestone: ff1f21b, 035c6e0

To build a key-value store, we need two things: an HTTP server to receive requests and a data structure to store the data. Using Spring Boot, creating the REST API is trivial.

For the storage layer, the most obvious choice in Java is the ubiquitous HashMap. Let's implement a simple StorageEngine interface using it:

@Component
public class HashMapStorageEngine implements StorageEngine {
    private final Map<String, byte[]> store = new HashMap<>();

    @Override
    public void put(String key, byte[] value) {
        store.put(key, value);
    }
    @Override
    public byte[] get(String key) {
        return store.get(key);
    }
}

(Note: We store the values as byte[] rather than String to ensure our store can handle any arbitrary binary data, not just text.)

If you boot up the application and test it using curl(given below), it works perfectly. You can PUT a key and GET it back.

But there is a catastrophic flaw hiding in this code.

The Silent Killer: Race Conditions

A HashMap is inherently not thread-safe. When multiple HTTP requests (handled by separate threads in Tomcat) attempt to write to the HashMap simultaneously, they can collide.

Inside the HashMap, data is stored in an array of "buckets." When two threads try to insert a value into the same bucket at the exact same millisecond, a race condition occurs. One thread's write will silently overwrite the other's, or worse, corrupt the internal linked list used to handle hash collisions.

Collision in HashMap

If we run a load test sending 100 concurrent PUT requests to our server, we might find that only 93 of those keys were actually saved. The other 7 simply vanished into the void, with no exceptions thrown. In a database, silent data loss is the ultimate sin.

The Solution: Thread Safety and Lock Striping

To fix this, we need thread safety. The easiest fix would be to wrap the HashMap in Collections.synchronizedMap(). This places a giant lock over the entire map—only one thread can read or write at a time. While it stops data loss, it destroys performance. If one thread is writing, all other threads (even those just trying to read unrelated keys) are blocked.

Instead, we use Java’s ConcurrentHashMap.

@Component
public class ConcurrentMapStorageEngine implements StorageEngine {
    private final Map<String, byte[]> store = new ConcurrentHashMap<>();

    @Override
    public void put(String key, byte[] value) {
        store.put(key, value);
    }
    @Override
    public byte[] get(String key) {
        return store.get(key);
    }
}

ConcurrentHashMap is a masterclass in concurrent design. Instead of locking the entire map, it uses lock striping (and synchronized nodes in newer Java versions). It divides the data into segments and only locks the specific bucket being modified.

ConcurrentHashMap

This allows dozens of threads to write to the map simultaneously — as long as they aren’t trying to write to the exact same bucket — while reads remain completely lock-free.

If we run our 100 concurrent request load test against the ConcurrentMapStorageEngine, 100% of the data is saved, and throughput remains incredibly high.

Test it Yourself

You can verify the system’s behavior using these commands:

for i in $(seq 1 100); do
  curl -s -X PUT http://localhost:8080/api/v1/keys/key:$i \
    -H "Content-Type: application/json" \
    -d "{\"value\": \"value-$i\"}" &
done
wait

What’s Next?

We now have a blazing fast, thread-safe, in-memory key-value store. But there is a glaring limitation: volatility.

If the JVM crashes, the server reboots, or we deploy an update, the ConcurrentHashMap is wiped out. Every single piece of data is permanently lost.

In Part 2, we will solve this by implementing the industry standard for durability: Write-Ahead Logging (WAL) and SSTables, transforming our volatile cache into a truly persistent database.