Rewrite HashRing to use consistent hashing
authorAaron Schulz <aschulz@wikimedia.org>
Thu, 8 Mar 2018 03:03:32 +0000 (19:03 -0800)
committerAaron Schulz <aschulz@wikimedia.org>
Thu, 7 Jun 2018 10:36:22 +0000 (03:36 -0700)
commitf2e6543c46fff5ce43839982ecd56ebcc10f4d62
treeaca60b1afab0ce3253a4f68c7a05197f88f7c53c
parent3b73014c55b75485366e25ea4b44f65a5f407bd3
Rewrite HashRing to use consistent hashing

This scheme avoids disruptive re-hashing when a node is
ejected; only the adjectent clockwise sector is affected,
the later taking responsibility for the former. Addition
of new nodes is likewise less disruptive.

When used with MD5, this maps keys the same as libketama.

Also:
* Make HashRing::getLocations() faster by guessing the
  sector list index and moving clockwise/counter-clockwise.
* Made HashRing Serializable for more robust storage.
* Allow for different hash functions to be specified.

Note:
* This makes PoolCounterRedis use the new hash scheme.
* Likewise for JobQueueFederated (for job de-duplication).
  Switching from one mode to the other will cause some of
  duplicated effort from old jobs only temporarily.

Change-Id: Iff432a4e5dc3fb40b2dda70fb3dbe9dda0b74933
includes/libs/HashRing.php
includes/poolcounter/PoolCounterRedis.php
tests/phpunit/includes/libs/HashRingTest.php