Geo Quorum Route Planner

Plan latency-aware geo quorum routes and report quorum-safety status.

Types

type Region struct {
    Name     string
    Latency  int
    Replicas int
    Healthy  bool
}

type RoutePlan struct {
    ReadRegions      []string
    ReadLatency      int
    WriteRegions     []string
    WriteLatency     int
    IntersectionSafe bool
    Status           string // "ok", "insufficient-read", "insufficient-write", "unsafe-quorum"
}

Function signature

func GeoQuorumRoute(regions []Region, r, w int) RoutePlan

Contract

1. regions lists the complete configured replica membership for one key range, including currently unhealthy regions. Health describes availability from the caller; it does not remove replicas from membership. Only healthy regions can provide responses.
2. For routing, sort healthy regions with positive replica counts by (Latency asc, Name asc).
3. Build read route by accumulating replicas until >= r. Build write route similarly for w.
4. If a quorum cannot be met:
   • return empty region list and -1 latency for that quorum,
   • set status to:
     • "insufficient-read" if read quorum fails,
     • else "insufficient-write" if write quorum fails.
5. If both routes are feasible, let N be the total configured replica count, including unhealthy regions. Set IntersectionSafe iff:
   • r + w > N
   • 2*w > N
6. Status when both routes feasible:
   • "ok" if IntersectionSafe=true
   • "unsafe-quorum" otherwise.

Special case:

• if r <= 0 or w <= 0, that quorum is considered satisfied with empty route and latency 0.

Example

regions = [
  {Name:"us-east", Latency:20, Replicas:2, Healthy:true},
  {Name:"us-west", Latency:50, Replicas:2, Healthy:true},
  {Name:"eu",      Latency:80, Replicas:1, Healthy:true},
]
r=2, w=3

Read route  = ["us-east"], latency 20
Write route = ["us-east", "us-west"], latency 50
N=5, r+w=5 (not >5) => unsafe
Status = "unsafe-quorum"

Constraints

• 0 <= len(regions) <= 2000
• 0 <= Replicas <= 1_000_000
• Region names are unique; latencies are nonnegative and measured from one caller.
• Every listed replica belongs to the same fixed configuration; membership changes are outside this call.
• Leave the input slice unchanged.

Complexity target

• Time: O(n log n)
• Extra space: O(n)

Partition counterexample

A configured five-replica group has three replicas in west and two in east. When the connection breaks, west sees only its three replicas as healthy and east sees only its two. Both callers still supply the complete five-replica configuration, with different health flags.

With r=2,w=2, both have feasible routes, but both must return unsafe-quorum: 2+2 is not greater than 5 and two writes need not intersect. Shrinking N to each caller's healthy count would incorrectly mark both sides safe. With r=3,w=3, west can return ok; east returns insufficient-read.

IntersectionSafe describes the quorum-size intersection property, not a proof of linearizability, data freshness, or successful network requests. This planner has no log ordering, version selection, leader term, or reconfiguration protocol. Its latency is the largest selected region latency in a parallel-response model; it is not a full transaction latency prediction.

Worked routing and partition trace