Part 1 built one node: an HTTP server with an in-memory store behind it. This part turns that single process into a member of a cluster. By the end, three separate node processes will each be able to answer, independently and without contacting each other, exactly which nodes are supposed to hold a given key.
Nothing here stores data on a remote node yet. Writes and reads still only touch the local map from Part 1. This part answers one narrower question — for key X, which nodes own it — and answers it correctly and consistently across every node in the cluster. Part 3 uses that answer to actually forward requests.
Why key placement needs more than hash(key) % nodeCount
The obvious way to assign keys to nodes is to hash the key and take it modulo the number of nodes. It works, and it's wrong for a cluster that ever changes size. If a 5-node cluster grows to 6 nodes, hash(key) % 5 and hash(key) % 6 agree for almost no keys — nearly every key's owner changes, because the modulus itself changed. In a system with data behind that placement, growing the cluster by one node means most keys need to move to a new owner at once.
Consistent hashing fixes this by placing nodes and keys on the same ring instead of bucketing by remainder. Both nodes and keys get hashed into the same numeric space (here, a 64-bit integer). A key belongs to the first node found walking clockwise from the key's position. Adding a node only affects the section of the ring between it and its predecessor — every other key's owner is untouched. Removing a node only affects the keys that were assigned to it. The fraction of keys that move when the cluster changes size is proportional to 1 / nodeCount, not close to 100%.
A ring with one point per node has an uneven problem of its own: with only a few points scattered on a 64-bit circle, the arc each node owns can vary a lot, so some nodes end up with far more keys than others. The standard fix is virtual nodes: each physical node gets many points on the ring (this implementation uses 100 by default), each independently hashed. More points per node means the total arc length each physical node covers converges toward an even share, without changing the core algorithm.
Static cluster membership
For this part, cluster membership is a fixed list read from a JSON file at startup — no discovery, no runtime joins or leaves. Every node process is expected to load the identical file. That's the mechanism that lets nodes agree on placement without a coordination step: given the same node list and the same hashing scheme, every node builds an identical ring and computes an identical answer for any key, independently.
That "expected to load the identical file" is doing real work and isn't verified by anything in this part. If two nodes are started with cluster config files that disagree — a missing node, a different replication factor, a typo in an address — nothing in this code detects it. Both nodes will run, both will answer replica queries confidently, and they'll disagree with each other silently. Part 7 replaces static config with gossip specifically because a file that has to be copied to every machine by hand is exactly this kind of failure waiting to happen. Until then, the static file is a known, named simplification, not a solved problem.
Implementation checkpoint
- A cluster config file lists every node's ID and address, plus the replication factor
N. - Every node loads the same config file at startup and resolves its own identity from it via a
-idflag. - A consistent hash ring is built from the node ID list, with virtual nodes for even distribution.
GET /replicas/{key}returns theNdistinct physical nodes responsible forkey, in ring order — the first is the coordinator, the rest are replicas.- If
Nis larger than the cluster size, the endpoint returns every node it has rather than erroring or padding the response. - Two independently built rings from the same node list return identical replica sets for every key — this is the property the whole design rests on, and it needs to be demonstrated, not assumed.
- Local storage is untouched: each node still only reads and writes its own map.
Project layout
distributed-kv-store/
cmd/kvnode/main.go
internal/store/store.go
internal/store/store_test.go
internal/cluster/config.go
internal/cluster/config_test.go
internal/hashring/ring.go
internal/hashring/ring_test.go
internal/api/handler.go
internal/api/cluster_handler.go
internal/api/cluster_handler_test.go
cluster.json
Two new packages: cluster, which loads and validates the static membership file, and hashring, which is pure placement logic with no knowledge of HTTP or storage. api gets a second handler alongside the one from Part 1, for the new read-only routing endpoint.
The cluster config
// internal/cluster/config.go
package cluster
import (
"encoding/json"
"fmt"
"os"
)
// Node describes one member of the static cluster: its ID and the
// address other nodes and clients use to reach it.
type Node struct {
ID string `json:"id"`
Addr string `json:"addr"`
}
// Config is the static cluster membership loaded at startup. Every node
// is expected to load the same config file, so every node builds the
// same hash ring and agrees on replica placement without contacting
// anyone else first.
type Config struct {
Nodes []Node `json:"nodes"`
ReplicationFactor int `json:"replication_factor"`
}
// Load reads and validates a cluster config file.
func Load(path string) (Config, error) {
data, err := os.ReadFile(path)
if err != nil {
return Config{}, fmt.Errorf("reading cluster config: %w", err)
}
var cfg Config
if err := json.Unmarshal(data, &cfg); err != nil {
return Config{}, fmt.Errorf("parsing cluster config: %w", err)
}
if err := cfg.validate(); err != nil {
return Config{}, err
}
return cfg, nil
}
func (c Config) validate() error {
if len(c.Nodes) == 0 {
return fmt.Errorf("cluster config has no nodes")
}
if c.ReplicationFactor < 1 {
return fmt.Errorf("replication_factor must be at least 1, got %d", c.ReplicationFactor)
}
seen := make(map[string]bool, len(c.Nodes))
for _, n := range c.Nodes {
if n.ID == "" {
return fmt.Errorf("node with empty id")
}
if n.Addr == "" {
return fmt.Errorf("node %q has empty addr", n.ID)
}
if seen[n.ID] {
return fmt.Errorf("duplicate node id %q", n.ID)
}
seen[n.ID] = true
}
return nil
}
// Self returns the Node entry matching id, or an error if the config
// does not contain a node with that id.
func (c Config) Self(id string) (Node, error) {
for _, n := range c.Nodes {
if n.ID == id {
return n, nil
}
}
return Node{}, fmt.Errorf("node id %q not found in cluster config", id)
}
// NodeIDs returns the IDs of every node in the config, in the order
// they appear in the file.
func (c Config) NodeIDs() []string {
ids := make([]string, len(c.Nodes))
for i, n := range c.Nodes {
ids[i] = n.ID
}
return ids
}
// AddrOf returns the address registered for a node ID, and whether that
// ID exists in the config.
func (c Config) AddrOf(id string) (string, bool) {
for _, n := range c.Nodes {
if n.ID == id {
return n.Addr, true
}
}
return "", false
}
validate rejects the config outright rather than letting a malformed one run. A duplicate node ID or an empty address would otherwise surface later as a confusing routing bug — a key silently resolving to the wrong address, or two ring positions pointing at the same broken entry — far from where the actual mistake was made. Failing at load time, with a specific error naming the bad field, is cheaper than debugging a ring that's quietly wrong.
The corresponding cluster.json for a 3-node cluster:
{
"nodes": [
{"id": "node-1", "addr": "localhost:8081"},
{"id": "node-2", "addr": "localhost:8082"},
{"id": "node-3", "addr": "localhost:8083"}
],
"replication_factor": 3
}
The hash ring
// internal/hashring/ring.go
// Package hashring implements consistent hashing for mapping keys to a
// fixed set of nodes. It answers one question: given a key and a node
// list, which nodes own it? It does not know about HTTP, storage, or
// cluster membership changes over time — it is pure placement logic.
package hashring
import (
"fmt"
"hash/fnv"
"sort"
)
const defaultVirtualNodes = 100
// Ring is a consistent hash ring mapping keys to nodes. A Ring is
// immutable once built: to change cluster membership, build a new Ring
// rather than mutating an existing one. That keeps Replicas safe to call
// concurrently with no locking.
type Ring struct {
points []point // sorted by hash, ascending
}
type point struct {
hash uint64
nodeID string
}
// New builds a ring from a set of node IDs. virtualNodes controls how
// many points on the ring each physical node owns; more points produce
// a smoother key distribution across nodes, at the cost of a larger
// ring to search. Pass 0 to use the default of 100 virtual nodes.
func New(nodeIDs []string, virtualNodes int) *Ring {
if virtualNodes <= 0 {
virtualNodes = defaultVirtualNodes
}
r := &Ring{points: make([]point, 0, len(nodeIDs)*virtualNodes)}
for _, id := range nodeIDs {
for i := 0; i < virtualNodes; i++ {
r.points = append(r.points, point{
hash: hashString(fmt.Sprintf("%s#%d", id, i)),
nodeID: id,
})
}
}
sort.Slice(r.points, func(i, j int) bool {
return r.points[i].hash < r.points[j].hash
})
return r
}
// Replicas returns up to n distinct physical node IDs responsible for
// key, walking the ring clockwise starting from key's position. The
// first entry is the coordinator for the key; the remaining entries are
// its replicas. If the ring contains fewer than n distinct physical
// nodes, Replicas returns every node it has instead of erroring or
// padding the result.
func (r *Ring) Replicas(key string, n int) []string {
if len(r.points) == 0 || n <= 0 {
return nil
}
h := hashString(key)
start := sort.Search(len(r.points), func(i int) bool {
return r.points[i].hash >= h
})
seen := make(map[string]bool, n)
result := make([]string, 0, n)
for i := 0; i < len(r.points) && len(result) < n; i++ {
p := r.points[(start+i)%len(r.points)]
if seen[p.nodeID] {
continue
}
seen[p.nodeID] = true
result = append(result, p.nodeID)
}
return result
}
func hashString(s string) uint64 {
h := fnv.New64a()
h.Write([]byte(s))
return h.Sum64()
}
A few decisions here are worth spelling out rather than leaving implicit.
New builds the entire sorted point list once and never mutates it. That's what lets Replicas run with no locking: an immutable slice is safe for concurrent reads from any number of goroutines. When cluster membership eventually changes (Part 7), the plan is to build a new Ring and atomically swap a pointer to it, not to add mutation methods to this type.
Replicas finds the starting position with binary search (sort.Search), then walks forward from there, wrapping around the end of the slice with % len(r.points) — the ring is circular, so a key hashing near the top has to be able to wrap back to node points near the bottom. The seen map exists because a physical node owns many virtual points; walking forward will hit several points belonging to the same node before it hits a different physical node, and the result should list each physical node once, not once per virtual point it happens to pass.
The hash function is FNV-1a, not a cryptographic hash. That's intentional: this ring isn't a security boundary, and nothing here needs collision resistance against an adversary — it needs speed and a good enough distribution, and FNV-1a gives both with no import beyond the standard library.
One more thing the code doesn't enforce: two nodes only produce the same ring if they agree on virtual node count, not just node IDs. This implementation hardcodes the default (100) everywhere it's called, so it isn't an issue in this project as it stands — but it's a second implicit agreement alongside the config file itself, and it would silently break ring agreement if one node were ever started with a different value.
The replicas endpoint
// internal/api/cluster_handler.go
package api
import (
"encoding/json"
"net/http"
"distributed-kv-store/internal/cluster"
"distributed-kv-store/internal/hashring"
)
// ClusterHandler exposes read-only cluster routing: given a key, which
// nodes are responsible for it. It does not forward requests or talk to
// other nodes — that starts in Part 3. Every node computes this answer
// independently from the same static config and the same ring.
type ClusterHandler struct {
ring *hashring.Ring
replicationFactor int
addrs map[string]string // node ID -> address, for response payloads
}
func NewClusterHandler(cfg cluster.Config, ring *hashring.Ring) *ClusterHandler {
addrs := make(map[string]string, len(cfg.Nodes))
for _, n := range cfg.Nodes {
addrs[n.ID] = n.Addr
}
return &ClusterHandler{
ring: ring,
replicationFactor: cfg.ReplicationFactor,
addrs: addrs,
}
}
func (h *ClusterHandler) Routes(mux *http.ServeMux) {
mux.HandleFunc("GET /replicas/{key}", h.handleReplicas)
}
type replicaInfo struct {
ID string `json:"id"`
Addr string `json:"addr"`
}
type replicasResponse struct {
Key string `json:"key"`
Replicas []replicaInfo `json:"replicas"`
}
func (h *ClusterHandler) handleReplicas(w http.ResponseWriter, r *http.Request) {
key := r.PathValue("key")
if key == "" {
http.Error(w, "missing key", http.StatusBadRequest)
return
}
ids := h.ring.Replicas(key, h.replicationFactor)
resp := replicasResponse{
Key: key,
Replicas: make([]replicaInfo, 0, len(ids)),
}
for _, id := range ids {
resp.Replicas = append(resp.Replicas, replicaInfo{ID: id, Addr: h.addrs[id]})
}
w.Header().Set("Content-Type", "application/json")
if err := json.NewEncoder(w).Encode(resp); err != nil {
http.Error(w, "failed to encode response", http.StatusInternalServerError)
}
}
This handler is deliberately thin. It doesn't decide placement — Ring.Replicas does — it just translates node IDs into the {id, addr} pairs a caller actually needs, using a lookup map built once at construction rather than scanning the config on every request. ClusterHandler is a separate type from Part 1's Handler, registered on the same http.ServeMux, because the two have no shared state and no reason to be coupled: one serves the local key-value data, the other serves cluster routing information.
Wiring it together
// cmd/kvnode/main.go
package main
import (
"flag"
"log"
"net/http"
"distributed-kv-store/internal/api"
"distributed-kv-store/internal/cluster"
"distributed-kv-store/internal/hashring"
"distributed-kv-store/internal/store"
)
func main() {
configPath := flag.String("config", "cluster.json", "path to the cluster config file")
nodeID := flag.String("id", "", "this node's ID, must match an entry in the cluster config")
flag.Parse()
if *nodeID == "" {
log.Fatal("-id is required")
}
cfg, err := cluster.Load(*configPath)
if err != nil {
log.Fatalf("loading cluster config: %v", err)
}
self, err := cfg.Self(*nodeID)
if err != nil {
log.Fatalf("resolving self: %v", err)
}
ring := hashring.New(cfg.NodeIDs(), 0)
s := store.New()
kvHandler := api.NewHandler(s)
clusterHandler := api.NewClusterHandler(cfg, ring)
mux := http.NewServeMux()
kvHandler.Routes(mux)
clusterHandler.Routes(mux)
log.Printf("node %s listening on %s (cluster size %d, replication factor %d)",
self.ID, self.Addr, len(cfg.Nodes), cfg.ReplicationFactor)
if err := http.ListenAndServe(self.Addr, mux); err != nil {
log.Fatal(err)
}
}
A node no longer listens on a hardcoded port. It resolves its own address from the config via -id, which is also what makes it possible to run several nodes from the exact same binary and config file — only the -id flag differs between them.
Verifying it
The property the design depends on
The single most important claim in this part is that two nodes, given the same config, compute the same answer without talking to each other. That isn't obvious from reading the code — it needs to actually be checked:
// internal/hashring/ring_test.go (excerpt)
func TestReplicasAreDeterministicAcrossInstances(t *testing.T) {
nodes := []string{"node-1", "node-2", "node-3", "node-4"}
ringA := New(nodes, 0)
ringB := New(nodes, 0)
for i := 0; i < 1000; i++ {
key := fmt.Sprintf("key-%d", i)
a := ringA.Replicas(key, 3)
b := ringB.Replicas(key, 3)
// a and b must match, element for element, for every key
}
}
That's a same-process proxy for the real thing. The real thing is running separate processes and asking them directly:
go build -o kvnode ./cmd/kvnode
./kvnode -id node-1 &
./kvnode -id node-2 &
./kvnode -id node-3 &
curl -s localhost:8081/replicas/user:42
curl -s localhost:8082/replicas/user:42
curl -s localhost:8083/replicas/user:42
All three returned, byte-for-byte identical, including replica order:
{"key":"user:42","replicas":[{"id":"node-1","addr":"localhost:8081"},{"id":"node-3","addr":"localhost:8083"},{"id":"node-2","addr":"localhost:8082"}]}
And querying node-1 and node-3 for five different keys (order:1, order:2, order:3, session:abc, cart:99) produced identical replica sets, in identical order, from both nodes for every key. That's three independent OS processes, each with its own copy of the ring built from its own read of the same file, agreeing with no communication between them at request time. That agreement is the actual milestone for this part — the endpoint returning JSON at all is secondary to that.
Why consistent hashing, with a number attached
The earlier claim was that growing a cluster only remaps roughly 1/newSize of keys, against nearly 100% for modulo hashing. That claim gets tested directly, not just asserted:
// internal/hashring/ring_test.go (excerpt)
func TestAddingNodeRemapsSmallFraction(t *testing.T) {
before := []string{"node-1", "node-2", "node-3", "node-4", "node-5"}
after := append(append([]string{}, before...), "node-6")
ringBefore := New(before, 0)
ringAfter := New(after, 0)
// count how many of 100,000 keys changed primary owner
// between ringBefore and ringAfter
}
Running it against this implementation: adding a 6th node to a 5-node ring remapped 13.89% of primary key ownership across 100,000 sample keys. The theoretical target for a perfectly even ring is 1/6 ≈ 16.7%; 13.89% is in that neighborhood, with the gap explained by the ring not being perfectly uniform even with 100 virtual nodes per physical node. Either way, it's nowhere near the ~83% (5/6) that modulo hashing would remap for the same change. The test asserts a loose upper bound (30%) specifically so it catches an actual regression to modulo-style placement without being flaky over sampling noise.
Everything else
gofmt -l .
go vet ./...
go build ./...
go test -race ./...
gofmt -l . prints nothing (nothing to format), go vet is clean, the build succeeds, and every test — including Part 1's store tests, the new config tests, the ring tests above, and the handler tests — passes under the race detector.
What this part does not guarantee
The replicas endpoint reports who should own a key. It says nothing about whether those nodes are actually reachable right now — there's no health check, no liveness tracking, nothing that would notice if node-2 in the config is a dead address. A node that's down still shows up in every replica list exactly as if it were healthy, because the ring only knows about static configuration, not runtime state.
Nothing in this system verifies that separate node processes are actually running from the same config file. If someone edits cluster.json on one machine and forgets to copy the change everywhere, every node will keep computing confidently and disagreeing with the others, with no error raised anywhere. That's the gap gossip membership (Part 7) is built to close.
And this part still doesn't move any data. PUT, GET, and DELETE from Part 1 are completely unaware that /replicas/{key} exists — a client could write to node-1 for a key whose coordinator is actually node-3, and nothing would stop it or forward it. Part 3 is what makes the coordinator role real: accepting a write on any node and forwarding it to the replicas this part's ring computes.