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

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.