Consistent Hashing
Asides
Programmer’s Toolbox Part 3: Consistent Hashing. It would be interesting if something like this could be folded into the currently random slave server selection for HyperDB.
Mar
30
30
2
Programmer’s Toolbox Part 3: Consistent Hashing. It would be interesting if something like this could be folded into the currently random slave server selection for HyperDB.
This is actually an old trick for randomly picking from uneven lists:
1-Create an array, with each entry representing the server capacity.
2-Now pick a random number from this total.
3-Find the server that represents that position in the list.
Eg:
$server=array(10,50,20,7);
$x=mt_rand(0,array_sum($server)-1);
$i=-1;
while ($x-$server[++$i]>=0) $x-=$server[$i];
// or more cryptic but faster:
// while ( ($x-=$server[++$i]) >= 0 ) {;}
The server to use is ‘$i’.
You can get fancier, but that will split based on ‘how much’ each can handle of the whole.
…of course, the above assumes all data is equal, and any server pick is as good as another. If you need consistency (say like the original article, where a specific key goes to the same server each time) then you don’t want mt_rand() – the recommendation of md6(keyvalue) works well until # of servers change.