Hinted Handoff Targets

In a replicated ring of N nodes, the coordinator writes to the primary replicas: start, start+1, ... (wrapping) for rf total replicas.

If a primary replica is down, the coordinator writes to the next available node instead and stores a hint indicating which primary replica this write is standing in for.

Given:

• n total nodes (0..n-1)
• start coordinator index
• rf replication factor
• alive[i] indicating if node i is up

Return the write targets in ring order starting from start, skipping down nodes, until you have rf targets.

Each target contains:

• Node: the actual node written to
• HintFor: the original primary replica this write stands in for, or -1 if none

Primary replicas are the first rf nodes starting at start (wrapping).

Types

const NoHint = -1

type WriteTarget struct {
    Node    int
    HintFor int
}

Function signature

func HintedHandoffTargets(n, start, rf int, alive []bool) []WriteTarget

Example

N=5, start=4, rf=3
alive = [true, false, true, true, true]
primaries = [4,0,1]

output = [
  {Node:4, HintFor:-1},
  {Node:0, HintFor:-1},
  {Node:2, HintFor:1}
]

Constraints

• 1 <= n <= 100000
• 1 <= rf <= n
• 0 <= start < n
• len(alive) == n
• At least rf nodes are alive

Notes

• Hints are assigned in primary order to the first available fallback nodes.