AnchorHash: A Scalable Consistent Hash

Their definition of "minimal disruption" seems really off to me. In distributed storage systems, it's not necessary for keys to be either left alone or reassigned only to the new bucket when a bucket is added. Other reassignments are perfectly valid, even if they're usually undesirable (part of a balancing act that I'll get to in a moment). Similarly, their definition of balance as equal probability seems unduly restrictive. Yes, it's desirable, but has to be weighed against the cost of reassignment. What they've done is set up an overly restrictive set of inclusion criteria, while ignoring the metrics that actual practitioners would use to compare hashing methods.

(1) Total number of reassignments when a bucket is added. Note that this can be minimized independently of whether those reassignments are only to the new bucket or include others as well. They're orthogonal properties.

(2) Number of reassignment destinations when a bucket is removed. Sometimes you want this to be low and sometimes you want it to be high, but it's rarely something you can ignore.

(3) Load associated with reassignments. Perfect balance (in the authors' sense) has to be weighed against the cost of reassignment, which can be high for storage applications. Depending on this cost and the rate of change, sometimes it's better to reach approximate balance and then leave things alone. I've worked on systems that over-optimized for perfect balance, and the results weren't good.

Perhaps this work is more applicable to something like load-balancing requests. For storage, it basically seems to be missing the point. IMO they should have left storage out of their introduction.

This looks like it's just copied from https://arxiv.org/abs/1812.09674.

I don’t like the branding of this algorithm at all. The biggest win from consistent hashing is you don’t have to keep any state, that’s kind of the whole point of it. Since this algorithm is stateful I don’t think it’s fair to put it in the same class of algorithms.

Link to their GitHub repo is buried in the PDF: https://github.com/anchorhash/cpp-anchorhash

I don't see how anyone can read that web page with the popup distraction in the corner. Every couple seconds it jumps and says "Bookmarked by X" or "New member X" and pulls my eyes away from the text.

Direct PDF link: https://export.arxiv.org/pdf/1812.09674.pdf