English
Building a Distributed KV Store from Scratch (Part 1): Introduction and the CAP Theorem
What you learn from books is ultimately shallow; to truly understand it, you must put it into practice. This series will guide you through implementing a production-grade distributed KV storage system from scratch.
Why write this series?
For Golang developers without experience in distributed systems, distributed systems often seem like a "black box":
I've heard of the fancy Raft algorithm, but I don't know how to implement it in code.
You know the twelve-character mantra of the CAP theorem, but you don't know how to make trade-offs in real-world scenarios.
I’ve read the source code of etcd and TiKV, but when faced with a blank editor, I don’t know where to start.
This series is designed to solve this problem.
We will start with the simplest single-node KV storage,Add a distributed feature to each article, ultimately building a complete distributed system.
Series roadmap
| Stage | article | Core output |
|---|---|---|
| Foundation | 01 Introduction and CAP Theorem | Understanding the core trade-offs in distributed systems |
| Foundation | 02 Single-node KV Storage | A runnable HTTP KV service |
| distributed | 03 gRPC Node Communication | Multi-node RPC call |
| distributed | 04 Raft Consensus Algorithm | Strong consistency guarantee |
| distributed | 05 Service Discovery and Registration | Dynamic Node Management |
| Advanced | 06 Consistent Hashing Sharding | Horizontal scalability |
| Advanced | 07 Observability | Prometheus Monitoring |
| Wrap-up | 08 Cluster Deployment and Testing | Docker local cluster |
Final output: A distributed KV storage system that supports multiple nodes, strong consistency, horizontal scalability, and observability.
What is a distributed system?
Before delving into the CAP theorem, let's first clarify the definitions.
Distributed systems It is a system composed of a group of independent computer nodes that communicate and collaborate over a network. Externally, it appears as a unified whole.
Challenges of Distributed Systems
Compared with stand-alone systems, distributed systems introduce entirely new problems:
| Challenge | Description | analogy |
|---|---|---|
| Network latency | Communication between nodes has unpredictable delays. | The letter may arrive late. |
| Network partition | The network between nodes may be disconnected. | The couriers went on strike. |
| Node failure | Any node may go down at any time. | An employee suddenly requests leave. |
| Clock not synchronized | System times are inconsistent across different nodes. | Wall clocks each run on their own. |
| Partial failure | An operation may succeed on some nodes and fail on others. | Only half the guests at the table were served their food. |
These problems do not exist (or are easy to handle) in a single-machine system, but in a distributed system they are normal state. The CAP theorem is precisely the theoretical abstraction of these challenges.
CAP Theorem: The First Principle of Distributed Systems
Before we start writing code, we must first understand the CAP theorem—it explains the fundamental trade-offs of distributed systems.
Historical background
The CAP theorem was proposed in 2000 by Professor Eric Brewer of the University of California, Berkeley, and formally proved in 2002 by Seth Gilbert and Nancy Lynch of MIT. It has become a cornerstone of distributed systems design.
Theorem content
The CAP theorem states that a distributed system can only satisfy at most at the same time Two of the following three:
| Characteristics | meaning | Plain explanation |
|---|---|---|
| Consistency (C) | All nodes see the same data at the same time. | After you update the data, anyone can read the latest value. |
| Availability (A) | Every request receives a non-error response. | The system is always online and will never deny service. |
| Partition Tolerance (P) | The system can still operate normally during network partitions. | Network disconnection between nodes does not crash the system. |
Deeply understand the three characteristics.
Consistency (Consistency)
Strong consistency requirements:After a write operation completes, all subsequent read operations must return the value written by that write..
Weak consistency/eventual consistency, by contrast, allows temporary inconsistency; eventually, the data on all nodes will tend to become consistent.
Availability
Availability requirements:Every non-faulty node must respond to requests within a finite time..
Note: Availability does not require "returning the latest data"; it only requires "returning a non-error response."
Partition Tolerance
Network partition refers to the complete disconnection of network connections between nodes:
Partition tolerance requirements:Even if a network partition occurs, the system can continue to operate..
Core insight: P is mandatory!
P is a required option!
In a network environment, network partitioning is Inevitably happen of (switch failure, loose network cable, packet loss, etc.). Therefore, distributed systems must make a trade-off between C and A:
CP system
Choose: Ensure consistency and partition tolerance, sacrificing availability
behavior: During a network partition, the system suspends service and waits for the partition to recover.
representative: ZooKeeper, etcd, HBase, MongoDB (default configuration)
AP system
Choose: Guarantee availability and partition tolerance, sacrifice consistency
Behavior: During a network partition, the system continues to serve, but data may be temporarily inconsistent.
represent: Cassandra, Amazon Dynamo, CouchDB, Riak
A classic example
Suppose there are two nodes A and B, storing the same data x (initial value 1). The client writes x=2 to A, but the network between A and B is disconnected:
| System type | Processing method | Result |
|---|---|---|
| CP | Refuse to write or read B, and return an error. | Data is consistent, but some requests failed. |
| AP | Allow writing to A, continue service. | Data is inconsistent, but the system is available. |
How should we choose?
The KV store implemented in this series will be a CP system(similar to etcd):
Prioritize ensuring consistency: Strong consistency is easier to understand and reason about than eventual consistency.
Availability: During a single-node failure, as long as a majority (more than half of the nodes) survives, the system remains available.
Suitable scenarios: Configuration management, service discovery, distributed locks
Express with a formula:CP = Consistency + Partition Tolerance - Partial Availability
Overall Architecture Design
Core Module Description
| module | Responsibilities | Technology selection |
|---|---|---|
| API layer | Receive client requests and return responses. | HTTP + gRPC |
| Raft consensus layer | Leader election, log replication, and ensuring consistency | hashicorp/raft |
| state machine | Store KV data, application log entries | In-memory Map + persistence |
| WAL log | Write-ahead logging ensures no data loss. | File storage (e.g., BoltDB) |
| Service Discovery | Dynamic node registration and discovery | Consul |
| Monitoring | Expose metrics and observe system status | Prometheus |
Request processing flow
Environment Preparation
Before you start coding, please make sure you have installed:
bash
# Go version requirements
go version # >= 1.21
# Verify installation
go env
# Create project directory
mkdir -p ~/projects/distributed-kv
cd ~/projects/distributed-kv
go mod init github.com/yourname/distributed-kv
# Dependencies that will be used in subsequent parts (you can install them in advance)
go get google.golang.org/[email protected]
go get google.golang.org/protobuf@latest
go get github.com/hashicorp/[email protected]
go get github.com/hashicorp/[email protected]
go get github.com/hashicorp/consul/[email protected]
go get github.com/prometheus/[email protected]Next installment preview
In the second article, we will officially start coding and implement a Standalone version of KV storage:
Based on
sync.RWMutexin-memory storageHTTP API（
/put,/get,/delete)Simple file persistence
unit testing
By then you will have a working service, laying the foundation for adding distributed features later.
bash
# The effect at the end of the second article
$ curl -X PUT localhost:8080/put -d '{"key":"name","value":"Alice"}'
{"status":"ok"}
$ curl localhost:8080/get?key=name
{"key":"name","value":"Alice"}Discussion Questions
While waiting for the second piece, you can first consider the following questions:
If we want to implement an AP system, how should write conflicts be handled when a network partition occurs?
Why does etcd recommend using an odd number of nodes (3, 5, 7) instead of an even number?
Consistent hashing and traditional hash modulo (
hash(key) % N), what are the advantages and disadvantages compared to it?
The answer will be discussed in a follow-up article or in the comments section.
All code in this series will be open-sourced on GitHub (link to be added).
Next: Building a Distributed KV Store from Scratch (Part 2): Standalone KV and HTTP API (To be written)