Ah, right. The joys of being a fool in public.

The part I missed is that the load balancers don't have a consistent view of the set of servers. There is no magical synchronization scheme that creates that consistent view. You want load balancers with slightly different ideas of what servers are available to mostly make the same choices for the servers they do agree on.

Doh! I should have been able to infer that from the original solution.

Not foolish. The constraint of no-need-for-globally-consistent-state is so important and rules out so many approaches that it was well worth stating in the article.

Indeed the statistical model described in the article does not model the distribution over server hash allocations you'd get if you allow them to be inconsistent across load balancer hosts, so the model actually models (and thus implies) a single global source of truth that they probably don't have in practice.

Well, given that I knew that I was probably missing something, and the fact that their solution made no sense with the constraints I was using, pretty strongly implied that there was an additional constraint. And that's a fairly obvious one to have.

I can't do the math to prove it, but their solution still seems wrong to me. Rather than generating and storing and searching so many hashes, it seems like you should get partway there with a different sampling procedure that doesn't do quite as well with the inconsistent sets of servers, and then only use duplication to limit the consistency loss.

Simple example: use their scheme but instead of choosing the first server to the left of the probe, grab the first two and flip a coin to decide which one to use. That already spreads the bucket variance out a bit, without using any extra space. It does have a penalty in that if one balancer has a server that the other doesn't, then it spreads out the range of probes that could get a disagreement. But I don't know how to quantify that; if the balancers disagree on the set of servers available, you have to produce different results part of the time, and I haven't thought through how to characterize when that disagreement is "bad".

Then you could extend that to looking at the previous 8 servers. Or the previous k tickets, if you give each server a ticket for each weight unit.

The math works out easier if you sample regions of probe space rather than server counts: hash the incoming task, map that to a range of space on the number line, and all servers within that range are your candidate set. Choose from that set, making the candidates be either equally weighted, weighted proportionally to their weight (size/capacity/whatever), or weighted by how much they got shafted by the random distribution of the server hashes.

I get EBRAINTOOSMALL when I try to work out the statistics, especially when I try to figure out what the inconsistency cost is, but intuitively it still seems better than recording a bajillion hashes for each server. (With the latter sampling mechanism, you'd need to deal with the possibility of probing a window with no server in it, either by double hashing the task and trying again, or expanding the probed region. Details schmetails.)

In practice, I'd probably simulate it and look at the distributions. Or nerd snipe a math geek.

The coin flip method you describe breaks the same-query same-server locality (unless adding or removing servers) that is one motivation for the consistent hashing method.

You could solve that by storing the new-query flip result, but the goal was reducing storage…

I'm assuming all coin flips are deterministic based on the task. In this case, it'd be equivalent to generating a slightly longer hash and using a couple of bits for the "coin flip". (Or just generating a new hash with 1 or 3 bits or whatever you need.)

Ah. That’s an unusual thing to mean by ‘coin flip’!