【Technical Help】Questions About 《Google SRE》

Hi Alejandro Forero Cuervo,I am an engineer from China. I am very sorry to bother you in the issue of github. We read about the Limiting the Connections Pool with Subsetting in the 21st chapter of the book "Google Sre". We are very interested in this algorithm and implemented it ourselves using golang, but in practice we have encountered some problems. I would like to ask you here:

When the number of backend nodes changes (such as when a node goes offline), rand.Shuffle does not guarantee that only one node's location is changed, resulting in a new subset that is completely different from the old one. So, is there any detail that has not been announced or is there a problem with our code? Here is our code:

func subset(backends []*Backend, clientID string, size int64) []*Backend {
if len(backends) <= int(size) {
    return backends
}
sort.Slice(backends, func(i, j int) bool {
    return backends[i].Hostname < backends[j].Hostname
})
count := int64(len(backends)) / size

id := farm.Fingerprint64([]byte(clientID))
round := int64(id / uint64(count))

s := rand.NewSource(round)
ra := rand.New(s)
ra.Shuffle(len(backends), func(i, j int) {
    backends[i], backends[j] = backends[j], backends[i]
})
start := (id % uint64(count)) * uint64(size)
return backends[int(start) : int(start)+int(size)]
}

Golang shuffle implementation:

func (r *Rand) Shuffle(n int, swap func(i, j int)) {
    if n < 0 {
        panic("invalid argument to Shuffle")
    }
    i := n - 1
    for ; i > 1<<31-1-1; i-- {
        j := int(r.Int63n(int64(i + 1)))
        swap(i, j)
    }
    for ; i > 0; i-- {
        j := int(r.int31n(int32(i + 1)))
        swap(i, j)
    }
}

We also found that if the "client_id" distribution is not uniform, then the final load is not uniform, is it necessary to ensure that the "client_id" interval is the same? If so, what is the implementation?

I look forward to your reply, thank you very much! My Email is longxboyhi@gmail.com

alefore / edge

【Technical Help】Questions About 《Google SRE》 #2