# Distributed KV Store Part 4 Every part so far has had the same asterisk on `GET`: it only reads the local node. Part 3 made writes genuinely distributed — a value written through any node ends up on multiple replicas — but a read still only ever asked one of them. A client could write a key through `node-2`, then read it from `node-3`, and get a `404`, not because the write failed, but because `node-3` simply hadn't been asked to participate. This part closes that gap. `GET` becomes a quorum operation, the same shape as `PUT` and `DELETE`: ask the replicas, wait for enough of them to answer, and combine what they say into one answer. ## What a quorum read actually does Symmetric to Part 3's write: 1. Compute the key's replica set from the ring — the same `N` nodes a write for this key would have used. 2. Ask all `N` for what they currently hold. 3. Wait until `R` of them have responded. 4. Among those `R` responses, pick the one with the newest timestamp. 5. If the newest response is a tombstone, or if no responding replica has ever heard of the key, report "not found." The interesting part is step 3's definition of "responded." A replica correctly saying "I have never heard of this key" is a successful response, not a failure — it's a fact about that replica, cleanly distinguishable from a timeout or a connection error. `R` counts replicas that answered, not replicas that had a value. This is what makes step 5 correct: quorum being reached and the key genuinely not existing are both ordinary, non-error outcomes. Only running out of reachable replicas before reaching `R` is an error. ## Why R+W>N is the number that matters The read only consults `R` of the `N` replicas, not all of them, and a write only reaches `W`. Nothing about the mechanism as described so far guarantees those two subsets overlap. If they didn't, a read could complete successfully and still miss the most recent write — not because anything failed, but because the read simply asked a different set of replicas than the write reached. `R+W>N` is the condition that rules this out, and it's worth being precise about why rather than taking it on faith. Pick any `N` replicas. A write reaches some `W` of them; a later read consults some `R` of them. If those two subsets were completely disjoint, together they'd account for `R+W` distinct replicas out of only `N` available — which is impossible once `R+W` exceeds `N`. So if `R+W>N`, the write's replicas and the read's replicas are *forced* to share at least one member, regardless of which specific replicas either operation happened to reach. With this project's defaults — `N=3`, `W=2`, `R=2` — `R+W=4>3=N`, so every quorum read is guaranteed to include at least one replica that has the most recently acknowledged quorum write for that key. That's a claim about combinatorics, and claims about combinatorics are exactly the kind of thing worth checking mechanically rather than trusting a paragraph of reasoning about — the ring's remap-fraction claim in Part 2 got the same treatment. Below, this one gets checked by brute-force enumeration: for a given `N`, generate every possible `R`-sized subset and every possible `W`-sized subset, and confirm every pair of them shares a member exactly when `R+W>N`, and that a disjoint pair exists to find when it doesn't. This also explains why the read doesn't need to contact all `N` replicas, or even try to guess which ones have the newest data. The guarantee holds for *any* `R`-subset — it doesn't matter which `R` replicas happen to answer first, or how the goroutines scheduling the fan-out happen to race. As long as `R+W>N`, the newest write is unavoidably in reach. ## Distinguishing "never written" from "deleted" The write path already keeps tombstones instead of physically deleting entries — that's what Part 1 set up. A quorum read is the first place that distinction actually gets used across the network: comparing responses from several replicas requires telling apart "this replica has no idea this key ever existed" from "this replica knows the key existed and was deleted at time T." A key that was written and then deleted has to beat a stale replica that still has an old live value, and it can only do that if the coordinator can see the tombstone's timestamp at all. Part 1's `Get` intentionally hides tombstones — that's the right behavior for a purely local read. Quorum reads need the raw entry, so this part adds `GetRaw` alongside it, used only internally between nodes. ## Implementation checkpoint - Cluster config gains a `read_quorum` field (`R`), validated the same way `write_quorum` was. - `Store.GetRaw` exposes tombstones; `Store.Get` still hides them, unchanged from Part 1. - A new internal endpoint, `GET /internal/kv/{key}`, is what a coordinator calls on each replica during a read — the read-side counterpart to Part 3's `PUT /internal/kv/{key}`. - `Coordinator.Get` fans out to a key's replicas, waits for `R` responses, and returns the newest entry among them. - The client-facing `GET /kv/{key}` goes through the coordinator now, the same as `PUT` and `DELETE` already do — there is no longer any client-facing operation that reads or writes the local store directly, only the coordinator does, whether or not this node happens to be one of the key's replicas. - The `R+W>N` overlap guarantee is checked by exhaustive enumeration, not asserted in a comment. ## 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/replicate/protocol.go internal/coordinator/coordinator.go internal/coordinator/coordinator_test.go internal/coordinator/quorum.go internal/coordinator/quorum_test.go internal/api/handler.go internal/api/cluster_handler.go internal/api/cluster_handler_test.go internal/api/replica_handler.go cluster.json ``` One addition worth calling out: `quorum.go`. Part 3's write already had "wait for successes, bail out once failure makes success impossible" logic. This part needs the identical logic for reads — same shape, different meaning attached to "success." Rather than write that accounting twice and risk the two copies drifting apart, it's pulled out into one small, independently-tested function that both `write` and the new `Get` call. ## Extending the store: seeing tombstones on purpose ```go // internal/store/store.go (new method, Get shown for contrast) // Get returns the current entry for key. The second return value is false // if the key was never written, or if the current entry is a tombstone. func (s *Store) Get(key string) (Entry, bool) { s.mu.Lock() defer s.mu.Unlock() entry, exists := s.data[key] if !exists || entry.Deleted { return Entry{}, false } return cloneEntry(entry), true } // GetRaw returns the current entry for key exactly as stored, including // tombstones. Unlike Get, the second return value is true whenever the // key has ever been written, whether or not the current entry is a // tombstone. A caller that needs to tell "never written" apart from // "deleted" — such as a quorum read comparing what several replicas // hold, where a tombstone with a newer timestamp than another replica's // live value must win — needs this distinction. Get intentionally // collapses both cases to "not found" because the local-only API from // Part 1 has no use for it. func (s *Store) GetRaw(key string) (Entry, bool) { s.mu.Lock() defer s.mu.Unlock() entry, exists := s.data[key] if !exists { return Entry{}, false } return cloneEntry(entry), true } ``` Both methods lock, copy, and unlock the same way Part 1 established — nothing about the concurrency story changes. `GetRaw` isn't a relaxed version of `Get`; it's a different, equally strict view of the same underlying map. ## The shared quorum accounting ```go // internal/coordinator/quorum.go package coordinator // quorumOutcome reports how a quorum vote currently stands. total is how // many replicas were asked; need is how many successes are required to // call it a success. // // decided is true once no further response could change the eventual // answer: either need has already been met (ok=true), or so many // replicas have already failed that need can no longer be met even if // every remaining one succeeds (ok=false). While decided is false, the // outcome genuinely depends on responses that haven't arrived yet, and // the caller should keep waiting. func quorumOutcome(successes, failures, total, need int) (decided, ok bool) { if successes >= need { return true, true } remaining := total - successes - failures if successes+remaining < need { return true, false } return false, false } ``` This replaces the ad-hoc `maxFailures := len(replicas) - w` check from Part 3's `write` with something expressed directly in terms of what's actually being decided, and tested on its own: ```go // internal/coordinator/quorum_test.go (excerpt) func TestQuorumOutcome(t *testing.T) { cases := []struct { name string successes, failures int total, need int wantDecided, wantOK bool }{ {"need met exactly", 2, 0, 3, 2, true, true}, {"still possible, keep waiting", 1, 0, 3, 2, false, false}, {"one failure, still possible", 1, 1, 3, 2, false, false}, {"too many failures, impossible", 0, 2, 3, 2, true, false}, {"need is 1, first failure alone is not decisive", 0, 1, 3, 1, false, false}, // ... full table in the repo } // ... } ``` ## The overlap guarantee, checked exhaustively ```go // internal/coordinator/quorum_test.go (excerpt) // TestReadWriteQuorumsAlwaysOverlapWhenRPlusWExceedsN is a direct, // exhaustive proof of the property the whole design leans on: for any // set of N replicas, any R of them chosen for a read and any W of them // chosen for a write must share at least one member, as long as // R+W > N. func TestReadWriteQuorumsAlwaysOverlapWhenRPlusWExceedsN(t *testing.T) { const n = 3 overlaps := func(a, b []int) bool { seen := make(map[int]bool, len(a)) for _, x := range a { seen[x] = true } for _, x := range b { if seen[x] { return true } } return false } for r := 1; r <= n; r++ { for w := 1; w <= n; w++ { readSets := subsetsOfSize(n, r) writeSets := subsetsOfSize(n, w) allOverlap := true for _, rs := range readSets { for _, ws := range writeSets { if !overlaps(rs, ws) { allOverlap = false } } } guaranteed := r+w > n if guaranteed && !allOverlap { t.Fatalf("R=%d, W=%d, N=%d: R+W>N but found a disjoint read/write pair", r, w, n) } } } } ``` `subsetsOfSize` (full version in the repo) is a plain recursive combination generator — nothing fancy, just enough to enumerate every `k`-element subset of `{0, ..., n-1}`. Running this for `N=3` checks all nine `(R, W)` combinations from `1` to `3` and confirms the boundary exactly where the math says it should be: every combination with `R+W>N` has zero disjoint pairs; the ones at or below the boundary do have disjoint pairs available. This is a small proof, but it's a proof, not a comment asserting the property is true. ## The wire format, extended for reads ```go // internal/replicate/protocol.go (new type, Request/Response from Part 3 unchanged) // ReadResponse is what a replica sends back for a single-key read // during a quorum read. Found is true whenever the replica has ever // written this key, whether or not the current entry is a tombstone — // a coordinator comparing responses from several replicas needs to // know the difference between "this replica has never heard of this // key" and "this replica knows the key was deleted." Value and Deleted // are only meaningful when Found is true. type ReadResponse struct { Found bool `json:"found"` Value string `json:"value"` Timestamp int64 `json:"timestamp"` Deleted bool `json:"deleted"` } ``` ## The replica-side read endpoint ```go // internal/api/replica_handler.go (new route added to Part 3's ReplicaHandler) func (h *ReplicaHandler) Routes(mux *http.ServeMux) { mux.HandleFunc("PUT /internal/kv/{key}", h.handleReplicate) mux.HandleFunc("GET /internal/kv/{key}", h.handleReadRaw) } // handleReadRaw answers a coordinator's quorum-read fan-out with exactly // what this replica has for key, tombstone or not. It deliberately does // not apply Get's "hide tombstones" behavior — the coordinator needs the // raw entry to compare against what other replicas report. func (h *ReplicaHandler) handleReadRaw(w http.ResponseWriter, r *http.Request) { key := r.PathValue("key") if key == "" { http.Error(w, "missing key", http.StatusBadRequest) return } entry, found := h.store.GetRaw(key) resp := replicate.ReadResponse{Found: found} if found { resp.Timestamp = entry.Timestamp resp.Deleted = entry.Deleted if !entry.Deleted { resp.Value = base64.StdEncoding.EncodeToString(entry.Value) } } 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) } } ``` Same shape as Part 3's replicate handler: no opinion about quorums or other replicas, just an honest report of local state. ## The coordinator's read path ```go // internal/coordinator/coordinator.go (Get and its helper; Put/Delete/write unchanged in shape from Part 3) // Get coordinates a quorum read of key: it asks the key's replicas for // what they hold, waits for R of them to answer, and returns whichever // response has the newest timestamp. See the package-level docs on why // R responses reached this way are guaranteed to include at least one // replica that saw the most recent quorum write for the same key, as // long as the cluster is configured with R+W>N. func (c *Coordinator) Get(ctx context.Context, key string) (ReadResult, error) { replicas := c.ring.Replicas(key, c.cfg.ReplicationFactor) r := c.cfg.ReadQuorum if len(replicas) < r { return ReadResult{}, fmt.Errorf("%w: only %d replicas available for key, need %d", ErrQuorumUnreachable, len(replicas), r) } // Unlike write's fan-out, cancelling the remaining requests here // once quorum is decided is fine, not a bug waiting to happen: a // read has no side effect to lose by being aborted mid-flight. So, // unlike write, this context is derived from ctx and is cancelled // on return. fanoutCtx, cancel := context.WithCancel(ctx) defer cancel() type readOutcome struct { entry store.Entry found bool err error } results := make(chan readOutcome, len(replicas)) for _, id := range replicas { id := id go func() { entry, found, err := c.readOne(fanoutCtx, id, key) results <- readOutcome{entry: entry, found: found, err: err} }() } successes, failures := 0, 0 var best store.Entry haveBest := false for i := 0; i < len(replicas); i++ { res := <-results if res.err != nil { failures++ if decided, ok := quorumOutcome(successes, failures, len(replicas), r); decided && !ok { return ReadResult{}, fmt.Errorf("%w: got %d responses (needed %d) out of %d replicas", ErrQuorumUnreachable, successes, r, len(replicas)) } continue } successes++ if res.found && (!haveBest || res.entry.Timestamp > best.Timestamp) { best = res.entry haveBest = true } if decided, ok := quorumOutcome(successes, failures, len(replicas), r); decided && ok { return readResultFrom(best, haveBest, successes, len(replicas)), nil } } return ReadResult{}, fmt.Errorf("%w: got %d responses (needed %d) out of %d replicas", ErrQuorumUnreachable, successes, r, len(replicas)) } func readResultFrom(best store.Entry, haveBest bool, acks, total int) ReadResult { if !haveBest || best.Deleted { return ReadResult{Found: false, Acks: acks, Total: total} } return ReadResult{ Value: best.Value, Timestamp: best.Timestamp, Found: true, Acks: acks, Total: total, } } ``` Two things stand out next to Part 3's `write`, and both are deliberate rather than incidental: **The fan-out context is not detached this time.** Part 3 went out of its way to make replica writes survive the coordinator returning early, because an aborted write throws away real work. A read has no such cost — a GET that gets cancelled mid-flight hasn't lost anything, since it never had a side effect to preserve. So `Get` uses `context.WithCancel(ctx)` and cancels on return, the more obviously "correct-looking" pattern that would have been wrong for `write`. Seeing both side by side is the point: the right context lifetime depends on what the operation does, not on some general rule about contexts. **"Best" updates as responses arrive, not after all of them are in.** The loop tracks the newest entry seen so far and compares every new response's timestamp against it, so by the time quorum is reached (`successes >= r`), `best` already holds the answer — there's no separate pass afterward to compute it. This is also exactly where the `R+W>N` guarantee cashes out: whichever `R` responses happen to arrive first, at least one of them is guaranteed to be a replica that had the most recent quorum-acknowledged write, so it's guaranteed to win the timestamp comparison against anything older. ## Wiring it together ```go // internal/api/handler.go — handleGet, changed from local-only in Part 3 func (h *Handler) handleGet(w http.ResponseWriter, r *http.Request) { key := r.PathValue("key") if key == "" { http.Error(w, "missing key", http.StatusBadRequest) return } result, err := h.coordinator.Get(r.Context(), key) if err != nil { writeCoordinatorError(w, err) return } if !result.Found { http.Error(w, "key not found", http.StatusNotFound) return } resp := getResponse{ Value: string(result.Value), Timestamp: result.Timestamp, } w.Header().Set("Content-Type", "application/json") w.Header().Set("X-Acks", strconv.Itoa(result.Acks)+"/"+strconv.Itoa(result.Total)) if err := json.NewEncoder(w).Encode(resp); err != nil { http.Error(w, "failed to encode response", http.StatusInternalServerError) } } ``` `Handler` no longer holds a reference to the local `*store.Store` at all — as of this part, `PUT`, `GET`, and `DELETE` all go through the coordinator exclusively. There is no client-facing code path left anywhere that touches the local map directly, on any node, for any operation. That includes when this node happens to be a replica for the key being read or written: it still goes through the same coordinator logic as every other case, which happens to route to the local store as one of its `N` targets. One request handling path, regardless of role. `cluster.json` gains the new field: ```json { "nodes": [ {"id": "node-1", "addr": "localhost:8081"}, {"id": "node-2", "addr": "localhost:8082"}, {"id": "node-3", "addr": "localhost:8083"} ], "replication_factor": 3, "write_quorum": 2, "read_quorum": 2 } ``` ## Verifying it ### Unit and race tests ``` go test -race ./... ``` ``` ok distributed-kv-store/internal/api ok distributed-kv-store/internal/cluster ok distributed-kv-store/internal/coordinator ok distributed-kv-store/internal/hashring ok distributed-kv-store/internal/store ``` The coordinator test suite is the one that matters most here, and it's built the same way Part 3's was — real `httptest.Server`s standing in for remote replicas, a real local store for "self," nothing mocked: - `TestGetReturnsWhatWasPut` — a straightforward round trip. - `TestGetReturnsNotFoundForUnknownKey` — confirms this returns cleanly, with no error, since quorum agreeing "not found" is a valid outcome, not a failure. - `TestGetReturnsNotFoundAfterQuorumDelete` — a quorum `Put` followed by a quorum `Delete`, then confirms `Get` reports not found. - `TestGetPicksNewestAmongAStaleReplica` — the one that actually exercises the conflict-resolution logic: two of the three backing stores get a fresh value written directly (bypassing the coordinator, simulating "these already got the real write"), the third gets an older value at an older timestamp (simulating a replica that missed an update). `Get` is asserted to return the fresh value. This isn't probabilistic — with only one stale replica out of three and `R=2`, any two that respond are guaranteed to include at least one fresh one, so the test can't flake regardless of goroutine scheduling. - `TestGetFailsWhenQuorumUnreachable` / `TestGetSucceedsWithOneReplicaDown` — the same failure-boundary checks Part 3 ran for writes, now for reads. ### Three real processes, reading what they wrote ``` ./kvnode -id node-1 & ./kvnode -id node-2 & ./kvnode -id node-3 & ``` Write through one node, read through a different one: ``` $ curl -i -X PUT localhost:8081/kv/sku:42 -d "9.99" HTTP/1.1 200 OK X-Acks: 2/3 X-Timestamp: 1786538545342652901 $ curl -i localhost:8082/kv/sku:42 HTTP/1.1 200 OK X-Acks: 2/3 {"value":"9.99","timestamp":1786538545342652901} ``` The timestamp in the read response matches the write's exactly — the same coordinator-assigned value from Part 3, now confirmed readable from a node that wasn't even the one that coordinated the write. A key that was never written: ``` $ curl -o /dev/null -w "%{http_code}\n" localhost:8083/kv/never:written 404 ``` Delete through one node, confirm gone from another: ``` $ curl -i -X DELETE localhost:8083/kv/sku:42 HTTP/1.1 204 No Content X-Acks: 2/3 $ curl -o /dev/null -w "%{http_code}\n" localhost:8081/kv/sku:42 404 ``` And the read-side quorum boundary, checked the same way Part 3 checked the write side — by actually killing processes: with one of three nodes down, a read still succeeds — ``` $ curl -i localhost:8081/kv/cart:1 HTTP/1.1 200 OK X-Acks: 2/3 {"value":"1 widget","timestamp":1786538547412923386} ``` — and with two of three down, leaving only one reachable replica against `R=2`, the same read fails with the coordinator's own accounting in the message: ``` $ curl -i localhost:8081/kv/cart:1 HTTP/1.1 503 Service Unavailable quorum unreachable: got 1 responses (needed 2) out of 3 replicas ``` ## What this part does not guarantee A quorum read sees the newest value among the `R` replicas it happened to reach — not necessarily the newest value that exists anywhere in the cluster. If a write only reached `W` replicas (the common case: Part 3's coordinator returns as soon as `W` is met, without waiting for the rest) and a subsequent read's `R` responses happen to miss all of those `W`, the `R+W>N` guarantee is what rules that out — but the guarantee is a property of *this specific configuration*, not of quorum reads in general. Running with `R+W<=N` (say, `R=1, W=1, N=3`, which the config validation in this part still happily accepts) drops the guarantee entirely, silently, with no error anywhere warning that reads can now miss recent writes. That's a real configuration hazard this part doesn't protect against — it's on whoever sets `cluster.json` to keep the inequality true. Nothing here repairs the stale replica once a read notices it's behind. `TestGetPicksNewestAmongAStaleReplica` proves the *read* returns the correct value despite one replica being behind, but the stale replica itself is untouched — it still has the old value after the read completes, and will keep serving it to any read that happens not to select it into its `R` this time versus next time. Fixing the stale replica itself, not just routing around it, is Part 5's job: read repair, using exactly the same "compare timestamps, newest wins" logic this part just built, but writing the result back instead of only returning it to the client. And a version of Part 3's coordinator-crash gap applies here too, in miniature: if the coordinator dies mid-fan-out after receiving some responses but before deciding quorum, the client gets a connection error with no result at all — not a stale answer, just no answer. Nothing added in this part changes that.