3 ms·

Um. I read the article thinking it would make for a great brain puzzle, but I quickly decided there's something wrong with the question setup because the initi

by sfink 7d ago

Um. I read the article thinking it would make for a great brain puzzle, but I quickly decided there's something wrong with the question setup because the initial solution didn't make sense. I assumed it was just missing a constraint that would be revealed later, but I'm still not seeing it -- the article just kept patching up the flaws in the wrong solution, the one that is more complicated than the straightforward one. I'm probably still missing something obvious? It's probably something to do with "...in a way that does not require large changes when servers are added or removed." But let's start with the problem as initially posed: you have an infinite stream of tasks and you need to deterministically assign them to N servers. (Perhaps you have to shard the collections of servers, so not every load balancer knows about all of them? But no, that would break the solution in the article.) Ok, then hash the task request (I assume that you hash it, the article doesn't explicitly say, but that's how you'd get determinism) and take that hash mod N, that's your server index. Why hash the servers too? If you roll 6 dice, and then another one to choose which die to use, you're not getting any more randomness. You're matching up two sides, the tasks on one side and the servers on the other; no need to randomize both. Ooh, but that's not a perfect distribution? Ok, if the hash value is large enough to be in the at most N-1 slop values at the top of UINT_MAX, then roll again (compute another hash). But CF is happy with 8% unevenness, there should be no problem with this 0.1% or whatever. Also, how do they find the nearest server hash to a task hash? Surely it's not a log(n) binary search through sorted server hashes, I hope? Weights break this scheme. Now each server has some number of tickets. So you compute hash % T (where T=total tickets) and have to figure out what server that is. There's probably a more clever way, but you could make a big array of (2-byte!) server indexes, one per ticket, and just fill them in and look up at index hash % T. That's 2 bytes per ticket, which feels uncomfortably wasteful if weights can be large. That's where things get more complicated for me: since the tasks are hashed, it doesn't matter what order a server's indexes come in relative to other servers', so sort them by descending weight. [I'm starting to suspect I'm making a fool of myself here by missing something obvious with the whole setup...] Now you can make an array of indexes for servers with the highest weight, then the next lower, then the next. Record the number of servers of each weight. Then you can take the hash % T and figure out which array it's in, then divide by the weight to give the index within that array. To reduce the number of per-weight arrays, you can restrict the weights allowed. If you restrict weights to be powers of two, you can eliminate a division by using a shift. If you really want more flexible weights, you can allow servers to be in more than one of the arrays. Let the arrays be powers of two, and then add an entry to each array corresponding to 1 bits in the binary representation of the weights. That increases the total memory usage of the arrays, so you could somewhat restrict the allowed weights by rounding to the nearest number with, say, 2 or 3 "on" bits at most. With at most 2 bits, that means weights are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 16, 17, .... The error really isn't bad. And this should all be easily doable without any branches, I'm pretty sure. As long as you statically cap the max weight. Anyway, that's just plowing through with the straightforward approach, and I still think I'm probably missing something major here. I imagine with large numbers of servers, some go down, so fast deletions are probably important. You can get by a little while by marking dead servers and if you "roll" one, just roll again. (Yes, deterministically, assuming other load balancers agree that the server is down.) But when more than some number of servers go down, you'd want to kick off a background task to rebuild a new set of tables -- so that's a factor 2 in size usage to have them both in memory during the rebuild. Adding is trickier, you'd probably want to do a 2-level structure where first you use the hash to decide whether it's in the old set that the table is built for or the set of servers that hasn't been incorporated yet (you'd collect these over time, and empty them out on the next table rebuild.) It's a little weird, because the load balancers' outputs would only agree when the added and deleted sets agreed, but I don't see how to do better than that. (I think you could set up some kind of synchronization scheme so that the old sets would agree, which would make them usually agree on which of the old set of machines gets it.) Somebody, feel free to tell me I'm being stupid! I'm sure there's a constraint that I'm missing, given that my understanding of the initial problem doesn't require any memory at all except for the servers' info. (Or if not, I'll let you know where I'd like to receive shipment of 1% of the memory I've saved...)

procaryote 7d ago
You hash the servers because then adding or removing a server doesn't directly affect other servers position on the ring; adding a server just takes some load from som servers. This is useful because you want stickiness, so requests for the same key mostly go to the same server. Sorting servers by weight means that removing or adding a server will shift a lot of traffic from the servers it used to go to. A flapping server early in the list will break stickiness for the whole set of servers. The simplicity of stable hashing means you don't have to think about new sets, old sets, table rebuilds, synchronisation schemes etc, and that's useful because every such extra step adds bugs and corner cases
- sfink 7d ago
  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.
  - robotresearcher 7d ago
    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.
    - sfink 7d ago
      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.

by sfink 7d ago

procaryote 7d ago

You hash the servers because then adding or removing a server doesn't directly affect other servers position on the ring; adding a server just takes some load from som servers. This is useful because you want stickiness, so requests for the same key mostly go to the same server. Sorting servers by weight means that removing or adding a server will shift a lot of traffic from the servers it used to go to. A flapping server early in the list will break stickiness for the whole set of servers. The simplicity of stable hashing means you don't have to think about new sets, old sets, table rebuilds, synchronisation schemes etc, and that's useful because every such extra step adds bugs and corner cases

sfink 7d ago
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.
- robotresearcher 7d ago
  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.
  - sfink 7d ago
    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.