dépôts / lhc / web / wiklou.git / commit
? search:
summary | shortlog | log | commit | commitdiff | tree
(parent: f16caa5) | patch
HashRing: use bisection instead of guess and refine
authorTim Starling <tstarling@wikimedia.org>
Thu, 7 Jun 2018 05:26:47 +0000 (15:26 +1000)
committerAaron Schulz <aschulz@wikimedia.org>
Fri, 8 Jun 2018 09:36:49 +0000 (02:36 -0700)
commit4aecdad6477e7ddf2eee1a35a17ab9d9141c3ff9
tree5414c6c5ff437cbf499163f8e89b8df8b0332193tree | snapshot
parentf16caa5b06e0c428e19d46b7af2ce8d29c5831b6commit | diff
HashRing: use bisection instead of guess and refine

Use bisection to find the position within the ring, as in ketama.
According to my benchmarking this is faster than the guess/refine
algorithm for rings with 100 locations, i.e. 16000 ring nodes requiring
at most 14 bisection iterations.

Change-Id: I6042f382de093081971b5ec210eda8dfa74988f2
includes/libs/HashRing.php diff | blob | history
tests/phpunit/includes/libs/HashRingTest.php diff | blob | history
Wiklou, le Wiki du Wiklou