← Back to all projects

LEARN DISTRIBUTED KV

Learn Distributed Key-Value Stores: Building the Backbone of the Internet

Goal: Understand how systems like DynamoDB, Cassandra, Redis Cluster, and Etcd work by building them. You will learn about Sharding, Replication, Consensus, and the trade-off between Consistency and Availability (CAP Theorem).

Why Distributed Key-Value (DKV) Stores?

When an application grows, a single database server (like MySQL) becomes a bottleneck. It runs out of CPU, RAM, or Disk.

The Solution: Split the data across 10, 100, or 1,000 machines. The Problem:

  1. How do you know which machine holds the key user_123? (Sharding)
  2. What happens if the machine holding user_123 catches fire? (Replication)
  3. If two people update user_123 at the same time on different machines, who wins? (Consistency)

DKV stores are the “best solution” for high-scale applications (like shopping carts, session caches, real-time analytics) because they sacrifice complex queries (SQL Joins) in exchange for massive throughput and infinite horizontal scaling.

Core Concept Analysis

To master this, you need to understand the CAP Theorem Trade-off:

  1. CP (Consistency + Partition Tolerance): Data is always correct, but the system might reject writes if a node is down (e.g., Etcd, Zookeeper). Used for configuration, service discovery.
  2. AP (Availability + Partition Tolerance): System always accepts writes, but data might be slightly stale for a few milliseconds (e.g., Cassandra, DynamoDB). Used for high-speed apps.

Project List

Project 1: The “Ring” (Consistent Hashing Proxy)

  • File: LEARN_DISTRIBUTED_KV.md
  • Main Programming Language: Go (Golang)
  • Alternative Programming Languages: Node.js, Python
  • Coolness Level: Level 3: Genuinely Clever
  • Business Potential: 2. Micro-SaaS (Load Balancer technology)
  • Difficulty: Level 2: Intermediate
  • Knowledge Area: Sharding / Load Balancing
  • Software or Tool: HTTP Server
  • Main Book: “System Design Interview” by Alex Xu (Chapter on Consistent Hashing)

What you’ll build: A smart proxy server that sits in front of 3+ independent Redis (or simple map) instances. When you request put("user_123", "data"), the proxy calculates exactly which server the data belongs to using Consistent Hashing and routes it there.

Why it teaches DKV: The biggest challenge in distributed systems is Data Distribution. If you just do hash(key) % 3, adding a 4th server breaks all keys. Consistent Hashing solves this, allowing you to add/remove nodes with minimal data movement.

Core challenges you’ll face:

  • The Hash Ring: mapping a large hash space (0 to 2^32) to a circle.
  • Virtual Nodes: preventing “hot spots” where one server gets all the data.
  • Node Addition/Removal: Calculating which keys need to move when the cluster changes.

Key Concepts:

  • Horizontal Scaling: Adding machines to increase capacity.
  • Hashing Algorithms: MD5/SHA1 usage in distribution.
  • Hot Partitions: The problem of uneven data distribution.

Difficulty: Intermediate Time estimate: Weekend Prerequisites: Basic HTTP server knowledge.

Real world outcome:

  1. Start 3 storage nodes (Node A, B, C) on different ports.
  2. Start your Proxy.
  3. Send 100 keys to the Proxy.
  4. Kill Node A.
  5. Send 100 keys again.
  6. The Proxy automatically routes Node A’s traffic to Node B, but Node C is unaffected.

Implementation Hints: Visualize the “Ring” as a sorted array of hashes. [Hash(NodeA), Hash(NodeB), Hash(NodeC)]. To find where Hash(Key) goes, perform a Binary Search to find the first Node Hash greater than the Key Hash.

Learning milestones:

  1. Modulo Sharding - Implement hash % N and see why it fails when N changes.
  2. The Ring - Implement the sorted structure.
  3. Virtual Nodes - Add multiple entries per node to balance the load.

Project 2: The “Log” (LSM-Tree Storage Engine)

  • File: LEARN_DISTRIBUTED_KV.md
  • Main Programming Language: Rust or C++
  • Alternative Programming Languages: Go, Java
  • Coolness Level: Level 4: Hardcore Tech Flex
  • Business Potential: 4. Open Core Infrastructure
  • Difficulty: Level 4: Expert
  • Knowledge Area: Database Internals / File Systems
  • Software or Tool: Disk I/O
  • Main Book: “Designing Data-Intensive Applications” by Martin Kleppmann (Chapter 3)

What you’ll build: You won’t build the network part here; you will build the Storage Engine that runs on a single node. You will implement a Log-Structured Merge-Tree (LSM Tree), which is the underlying data structure for Cassandra, RocksDB, and LevelDB.

Why it teaches DKV: Distributed databases are almost always “Write Heavy”. B-Trees (used in SQL) are slow for heavy writes. LSM Trees are fast because they treat the disk like a log (Append Only). Understanding this explains why NoSQL is fast.

Core challenges you’ll face:

  • Memtable: Storing data in memory (Sorted Map/Red-Black Tree).
  • SSTable (Sorted String Table): Flushing memory to disk in a sorted, immutable file.
  • Compaction: Merging multiple SSTables in the background to reclaim space and delete old keys.
  • Bloom Filters: Optimizing reads so you don’t check every file.

Key Concepts:

  • Write Amplification: Trade-off between write speed and disk usage.
  • WAL (Write Ahead Log): Preventing data loss during crashes.
  • Sparse Indexing: Loading only part of the index into RAM.

Difficulty: Expert Time estimate: 2-3 weeks Prerequisites: Strong grasp of File I/O and Data Structures.

Real world outcome: You have a library where you can call db.set("key", "value") 1 million times per second. Even if you crash the program, the data is recovered from the WAL upon restart.

Implementation Hints:

  1. Write generic append to a file.
  2. Store keys in an in-memory TreeMap.
  3. When the Map hits 1MB, write it to disk as data_1.sst.
  4. Clear the Map.
  5. To Read: Check Map -> Check data_N.sst (newest to oldest).

Learning milestones:

  1. The Log - Append-only storage working.
  2. The Flush - Moving RAM to Disk.
  3. The Merge - Background process combining files.

Project 3: The “Consensus” (Raft Implementation)

  • File: LEARN_DISTRIBUTED_KV.md
  • Main Programming Language: Go (Golang)
  • Alternative Programming Languages: Rust
  • Coolness Level: Level 5: Pure Magic
  • Business Potential: 5. Industry Disruptor
  • Difficulty: Level 5: Master
  • Knowledge Area: Distributed Consensus / Strong Consistency
  • Software or Tool: RPC (gRPC or net/rpc)
  • Main Book: The Raft Paper (“In Search of an Understandable Consensus Algorithm”)

What you’ll build: A strongly consistent Key-Value store. This requires implementing the Raft Consensus Algorithm. You will have a cluster where nodes elect a Leader. All writes go to the Leader, who replicates them to Followers. If the Leader dies, the Followers vote for a new one.

Why it teaches DKV: This is how Etcd, Consul, and CockroachDB work. This explains Strong Consistency (CP). If you need to know for sure that a value is saved (e.g., processing a payment), you use this.

Core challenges you’ll face:

  • Leader Election: Handling timeouts, randomized timers, and voting logic.
  • Log Replication: Ensuring all followers have the exact same list of commands in the exact same order.
  • Brain Split: Handling network partitions where two nodes both think they are leader.

Key Concepts:

  • State Machine Replication: The concept that if two computers execute the same commands in the same order, they arrive at the same state.
  • Quorum: Understanding that you need (N/2) + 1 nodes to agree.
  • Heartbeats: How nodes know others are alive.

Resources for key challenges:

  • “The Secret Lives of Data” (Visualizing Raft) - Essential visualization.

Difficulty: Master Time estimate: 1 Month+ Prerequisites: Concurrency (Locks/Channels), RPCs.

Real world outcome:

  1. Start 5 nodes.
  2. Write key=10 to Node 1 (Leader).
  3. Kill Node 1.
  4. Node 3 becomes Leader automatically.
  5. Read key from Node 3 -> It returns 10.

Implementation Hints: Do not optimize. Follow the Raft paper logic exactly. Structure your code into: Election, LogReplication, and Commit. Use a distinct timeout for election (e.g., 150-300ms random).

Learning milestones:

  1. The Heartbeat - Nodes recognize when one is missing.
  2. The Election - Nodes successfully vote for a single leader.
  3. The Commit - Data is only “saved” when 51% of nodes acknowledge it.

Project 4: The “Gossip” (Dynamo-Style AP Store)

  • File: LEARN_DISTRIBUTED_KV.md
  • Main Programming Language: Elixir or Go
  • Alternative Programming Languages: Java
  • Coolness Level: Level 4: Hardcore Tech Flex
  • Business Potential: 4. Open Core Infrastructure
  • Difficulty: Level 4: Expert
  • Knowledge Area: Eventual Consistency / High Availability
  • Software or Tool: UDP / TCP
  • Main Book: “The Dynamo Paper” (Amazon)

What you’ll build: A “Leaderless” database (like Cassandra or Riak). Any node can accept a write. Nodes talk to each other periodically (“Gossip”) to sync data. If two nodes have different data for the same key, you resolve the conflict.

Why it teaches DKV: This explains High Availability (AP). This is used when you cannot afford downtime (e.g., Amazon Shopping Cart). You will learn that “truth” is relative in a distributed system.

Core challenges you’ll face:

  • Vector Clocks: Tracking version history to detect conflicts (e.g., Alice wrote X, then Bob wrote Y).
  • Gossip Protocol: Nodes randomly whispering state to each other to spread data like a virus.
  • Hinted Handoff: Storing data for a neighbor that is temporarily down.
  • Read Repair: Fixing data when a user reads it and realizes it’s stale.

Key Concepts:

  • Eventual Consistency: The system will agree eventually, but not right now.
  • Merkle Trees: Efficiently comparing huge datasets to find differences.
  • Sloppy Quorum: Allowing writes even if the “correct” nodes are offline.

Difficulty: Expert Time estimate: 3-4 weeks Prerequisites: Project 1 (Consistent Hashing).

Real world outcome:

  1. Cluster of 3 nodes.
  2. Disconnect Node A from the network.
  3. Write cart={milk} to Node B.
  4. Write cart={eggs} to Node A (it accepts it locally!).
  5. Reconnect Node A.
  6. Read cart.
  7. System detects conflict and returns both {milk} and {eggs} (Siblings) or merges them {milk, eggs}.

Implementation Hints: Use UDP for the Gossip protocol (it’s lightweight). Every second, pick a random peer and exchange a summary of keys you have. If versions differ, exchange the full data.

Learning milestones:

  1. The Virus - Write to Node A, see it appear on Node C via Gossip.
  2. The Conflict - Detect when two nodes have different values for the same key.
  3. The Resolution - Implement “Last Writer Wins” or “Vector Clock” resolution.

Project Comparison Table

Project Difficulty Time Consistency Model Use Case
1. The Ring Intermed. Weekend N/A (Routing) Load Balancing, Caching
2. The Log Expert 2-3 Wks Local Consistency Storage Engines (RocksDB)
3. Consensus Master 1 Mo+ Strong (CP) Configuration, Payments (Etcd)
4. Gossip Expert 3-4 Wks Eventual (AP) High Volume Data (Cassandra)

Recommendation

Start with Project 1 (The Ring). It gives you the immediate visual satisfaction of a distributed system (traffic moving between servers) without the nightmare of debugging race conditions.

Then, Make a Choice:

  • Path A: “I want to build reliable systems” (Kubernetes, Banking).
    • Go to Project 3 (Raft). It is the gold standard for “Modern Cloud Infrastructure”.
  • Path B: “I want to build massive scale systems” (Social Media, Big Data).
    • Go to Project 4 (Gossip). It teaches you how the internet giants handle millions of requests.
  • Path C: “I like low-level systems programming”.
    • Go to Project 2 (LSM Tree). This teaches you how databases actually touch the disk.

Final Overall Project: The “Distributed DB” Capstone

  • File: LEARN_DISTRIBUTED_KV.md
  • Main Programming Language: Go or Rust
  • Difficulty: Level 5: Master

What you’ll build: Combine all previous projects.

  1. Storage: Use your LSM Tree (Project 2) as the storage engine on each node.
  2. Distribution: Use Consistent Hashing (Project 1) to determine which node gets the data.
  3. Replication: Use Raft (Project 3) to replicate data between the primary node and its backups.

Real World Outcome: You will have built a functional clone of TiKV or CockroachDB. You can point a client to it, write data, kill random servers, unplug cables, and the data remains safe and available.

Summary

Project Concepts Learned Main Tech
1. The Ring Sharding, Consistent Hashing Go / HTTP
2. The Log LSM Trees, Disk I/O, Compaction Rust / File I/O
3. Consensus Strong Consistency, Raft, Leader Election Go / RPC
4. Gossip High Availability, Vector Clocks, Merkle Trees Elixir / UDP
5. Capstone Full System Integration Go / Rust

Essential Resources

Books (The “Bible” Tier)

  • “Designing Data-Intensive Applications” by Martin Kleppmann - Read Chapter 5 (Replication) and Chapter 6 (Partitioning). This is the single best book on this topic.
  • “Database Internals” by Alex Petrov - Deep dive into LSM Trees and storage.

Papers (The Source of Truth)

  • The Amazon Dynamo Paper - The birth of eventual consistency.
  • The Raft Paper - The birth of understandable consensus.
  • The Google BigTable Paper - The birth of LSM usage at scale.

Visualizations

  • Raft Visualization: thesecretlivesofdata.com/raft
  • Consistent Hashing: toptal.com/big-data/consistent-hashing