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

// 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

// 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:

// 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

// 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

// 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

// 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

// 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

// 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:

{
  "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.Servers 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.