Quorum Read Plan

A client reads from a replicated key-value store. Each replica returns a value with a timestamp (larger is newer) and a liveness flag.

To answer a read, you need at least R live responses. The read should return the value with the highest timestamp (tie-break by lowest ReplicaID) and schedule read repair for any live replica that is stale.

Also report whether the quorum configuration guarantees the latest write (R + W > N).

Types

type ReplicaResponse struct {
    ReplicaID int
    Value     string
    Timestamp int
    Alive     bool
}

type ReadPlan struct {
    Ok               bool
    Value            string
    Repair           []int
    LatestGuaranteed bool
}

Function signature

func QuorumReadPlan(n, r, w int, responses []ReplicaResponse) ReadPlan

Example

N=3, R=2, W=2
responses = [
  {ID:0, Value:"a", Timestamp:1, Alive:true},
  {ID:1, Value:"b", Timestamp:3, Alive:true},
  {ID:2, Value:"b", Timestamp:3, Alive:false},
]

Ok=true
Value="b"
Repair=[0]
LatestGuaranteed=true

Constraints

• 0 <= len(responses) <= 100000
• 0 <= Timestamp <= 1_000_000
• 0 <= ReplicaID < N

Notes

• If Ok is false, return Value="" and Repair=nil.
• Repair should be sorted ascending by ReplicaID.