Bounded Staleness Read

A replica can serve a bounded staleness read if its applied time is within a staleness window of the latest write.

Given the time of the latest write and each replica's last applied time and latency, choose the lowest-latency replica that is within the window. If no replica is eligible, return -1.

Eligibility: replica.AppliedTime >= latestWrite - window

Tie-breaks: lower latency, then lower replica ID.

Types

type Replica struct {
    ID          int
    AppliedTime int
    Latency     int
}

Function signature

func BoundedStalenessRead(latestWrite int, window int, replicas []Replica) int

Example

latestWrite = 100
window = 10
replicas = [
  {ID:1, AppliedTime:95, Latency:30},
  {ID:2, AppliedTime:92, Latency:10},
  {ID:3, AppliedTime:89, Latency:5},
]

Eligible: ID 1 (95) and ID 2 (92)
Pick ID 2 (lower latency)

Constraints

• 0 <= len(replicas) <= 100000
• 0 <= latestWrite, window, AppliedTime, Latency <= 1_000_000