3 * Convenience class for weighted consistent hash rings.
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
10 * This program is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
15 * You should have received a copy of the GNU General Public License along
16 * with this program; if not, write to the Free Software Foundation, Inc.,
17 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
18 * http://www.gnu.org/copyleft/gpl.html
24 * Convenience class for weighted consistent hash rings
26 * This deterministically maps "keys" to a set of "locations" while avoiding clumping
28 * Each location is represented by a number of nodes on a ring proportionate to the ratio
29 * of its weight compared to the total location weight. Note positions are deterministically
30 * derived from the hash of the location name. Nodes are responsible for the portion of the
31 * ring, counter-clockwise, up until the next node. Locations are responsible for all portions
32 * of the ring that the location's nodes are responsible for.
34 * A location that is temporarily "ejected" is said to be absent from the "live" ring.
35 * If no location ejections are active, then the base ring and live ring are identical.
39 class HashRing
implements Serializable
{
40 /** @var string Hashing algorithm for hash() */
42 /** @var int[] Non-empty (location => integer weight) */
43 protected $weightByLocation;
44 /** @var int[] Map of (location => UNIX timestamp) */
45 protected $ejectExpiryByLocation;
47 /** @var array[] Non-empty position-ordered list of (position, location name) */
49 /** @var array[] Non-empty position-ordered list of (position, location name) */
52 /** @var float Number of positions on the ring */
53 const RING_SIZE
= 4294967296.0; // 2^32
54 /** @var integer Overall number of node groups per server */
55 const HASHES_PER_LOCATION
= 40;
56 /** @var integer Number of nodes in a node group */
57 const SECTORS_PER_HASH
= 4;
60 const KEY_LOCATION
= 1;
62 /** @var int Consider all locations */
64 /** @var int Only consider "live" locations */
68 * Make a consistent hash ring given a set of locations and their weight values
70 * @param int[] $map Map of (location => weight)
71 * @param string $algo Hashing algorithm listed in hash_algos() [optional]
72 * @param int[] $ejections Map of (location => UNIX timestamp) for ejection expiries
75 public function __construct( array $map, $algo = 'sha1', array $ejections = [] ) {
76 $this->init( $map, $algo, $ejections );
80 * @param int[] $map Map of (location => integer)
81 * @param string $algo Hashing algorithm
82 * @param int[] $ejections Map of (location => UNIX timestamp) for ejection expires
84 protected function init( array $map, $algo, array $ejections ) {
85 if ( !in_array( $algo, hash_algos(), true ) ) {
86 throw new RuntimeException( __METHOD__
. ": unsupported '$algo' hash algorithm." );
89 $weightByLocation = array_filter( $map );
90 if ( $weightByLocation === [] ) {
91 throw new UnexpectedValueException( "No locations with non-zero weight." );
92 } elseif ( min( $map ) < 0 ) {
93 throw new InvalidArgumentException( "Location weight cannot be negative." );
97 $this->weightByLocation
= $weightByLocation;
98 $this->ejectExpiryByLocation
= $ejections;
99 $this->baseRing
= $this->buildLocationRing( $this->weightByLocation
);
103 * Get the location of an item on the ring
105 * @param string $item
106 * @return string Location
107 * @throws UnexpectedValueException
109 final public function getLocation( $item ) {
110 return $this->getLocations( $item, 1 )[0];
114 * Get the location of an item on the ring followed by the next ring locations
116 * @param string $item
117 * @param int $limit Maximum number of locations to return
118 * @param int $from One of the RING_* class constants
119 * @return string[] List of locations
120 * @throws InvalidArgumentException
121 * @throws UnexpectedValueException
123 public function getLocations( $item, $limit, $from = self
::RING_ALL
) {
124 if ( $from === self
::RING_ALL
) {
125 $ring = $this->baseRing
;
126 } elseif ( $from === self
::RING_LIVE
) {
127 $ring = $this->getLiveRing();
129 throw new InvalidArgumentException( "Invalid ring source specified." );
132 // Short-circuit for the common single-location case. Note that if there was only one
133 // location and it was ejected from the live ring, getLiveRing() would have error out.
134 if ( count( $this->weightByLocation
) == 1 ) {
135 return ( $limit > 0 ) ?
[ $ring[0][self
::KEY_LOCATION
] ] : [];
138 // Locate the node index for this item's position on the hash ring
139 $itemIndex = $this->findNodeIndexForPosition( $this->getItemPosition( $item ), $ring );
142 $currentIndex = null;
143 while ( count( $locations ) < $limit ) {
144 if ( $currentIndex === null ) {
145 $currentIndex = $itemIndex;
147 $currentIndex = $this->getNextClockwiseNodeIndex( $currentIndex, $ring );
148 if ( $currentIndex === $itemIndex ) {
149 break; // all nodes visited
152 $nodeLocation = $ring[$currentIndex][self
::KEY_LOCATION
];
153 if ( !in_array( $nodeLocation, $locations, true ) ) {
154 // Ignore other nodes for the same locations already added
155 $locations[] = $nodeLocation;
163 * @param float $position
164 * @param array[] $ring Either the base or live ring
167 private function findNodeIndexForPosition( $position, $ring ) {
168 $count = count( $ring );
169 if ( $count === 0 ) {
177 $midPos = (int)( ( $lowPos +
$highPos ) / 2 );
178 if ( $midPos === $count ) {
183 $midVal = $ring[$midPos][self
::KEY_POS
];
184 $midMinusOneVal = ( $midPos === 0 ) ?
0 : $ring[$midPos - 1][self
::KEY_POS
];
185 if ( $position <= $midVal && $position > $midMinusOneVal ) {
190 if ( $midVal < $position ) {
191 $lowPos = $midPos +
1;
193 $highPos = $midPos - 1;
196 if ( $lowPos > $highPos ) {
206 * Get the map of locations to weight (does not include zero weight items)
210 public function getLocationWeights() {
211 return $this->weightByLocation
;
215 * Remove a location from the "live" hash ring
217 * @param string $location
218 * @param int $ttl Seconds
219 * @return bool Whether some non-ejected locations are left
220 * @throws UnexpectedValueException
222 public function ejectFromLiveRing( $location, $ttl ) {
223 if ( !isset( $this->weightByLocation
[$location] ) ) {
224 throw new UnexpectedValueException( "No location '$location' in the ring." );
227 $expiry = $this->getCurrentTime() +
$ttl;
228 $this->ejectExpiryByLocation
[$location] = $expiry;
230 $this->liveRing
= null; // invalidate ring cache
232 return ( count( $this->ejectExpiryByLocation
) < count( $this->weightByLocation
) );
236 * Get the location of an item on the "live" ring
238 * @param string $item
239 * @return string Location
240 * @throws UnexpectedValueException
242 final public function getLiveLocation( $item ) {
243 return $this->getLocations( $item, 1, self
::RING_LIVE
)[0];
247 * Get the location of an item on the "live" ring, as well as the next locations
249 * @param string $item
250 * @param int $limit Maximum number of locations to return
251 * @return string[] List of locations
252 * @throws UnexpectedValueException
254 final public function getLiveLocations( $item, $limit ) {
255 return $this->getLocations( $item, $limit, self
::RING_LIVE
);
259 * Get the map of "live" locations to weight (does not include zero weight items)
262 * @throws UnexpectedValueException
264 public function getLiveLocationWeights() {
265 $now = $this->getCurrentTime();
267 return array_diff_key(
268 $this->weightByLocation
,
270 $this->ejectExpiryByLocation
,
271 function ( $expiry ) use ( $now ) {
272 return ( $expiry > $now );
279 * @param int[] $weightByLocation
282 private function buildLocationRing( array $weightByLocation ) {
283 $locationCount = count( $weightByLocation );
284 $totalWeight = array_sum( $weightByLocation );
287 // Assign nodes to all locations based on location weight
288 $claimed = []; // (position as string => (node, index))
289 foreach ( $weightByLocation as $location => $weight ) {
290 $ratio = $weight / $totalWeight;
291 // There $locationCount * (HASHES_PER_LOCATION * 4) nodes available;
292 // assign a few groups of nodes to this location based on its weight.
293 $nodesQuartets = intval( $ratio * self
::HASHES_PER_LOCATION
* $locationCount );
294 for ( $qi = 0; $qi < $nodesQuartets; ++
$qi ) {
295 // For efficiency, get 4 points per hash call and 4X node count.
296 // If $algo is MD5, then this matches that of with libketama.
297 // See https://github.com/RJ/ketama/blob/master/libketama/ketama.c
298 $positions = $this->getNodePositionQuartet( "{$location}-{$qi}" );
299 foreach ( $positions as $gi => $position ) {
300 $node = ( $qi * self
::SECTORS_PER_HASH +
$gi ) . "@$location";
301 $posKey = (string)$position; // large integer
302 if ( isset( $claimed[$posKey] ) ) {
303 // Disallow duplicates for sanity (name decides precedence)
304 if ( $claimed[$posKey]['node'] > $node ) {
307 unset( $ring[$claimed[$posKey]['index']] );
311 self
::KEY_POS
=> $position,
312 self
::KEY_LOCATION
=> $location
314 $claimed[$posKey] = [ 'node' => $node, 'index' => count( $ring ) - 1 ];
318 // Sort the locations into clockwise order based on the hash ring position
319 usort( $ring, function ( $a, $b ) {
320 if ( $a[self
::KEY_POS
] === $b[self
::KEY_POS
] ) {
321 throw new UnexpectedValueException( 'Duplicate node positions.' );
324 return ( $a[self
::KEY_POS
] < $b[self
::KEY_POS
] ?
-1 : 1 );
331 * @param string $item Key
332 * @return float Ring position; integral number in [0, self::RING_SIZE - 1]
334 private function getItemPosition( $item ) {
335 // If $algo is MD5, then this matches that of with libketama.
336 // See https://github.com/RJ/ketama/blob/master/libketama/ketama.c
337 $octets = substr( hash( $this->algo
, (string)$item, true ), 0, 4 );
338 if ( strlen( $octets ) != 4 ) {
339 throw new UnexpectedValueException( __METHOD__
. ": {$this->algo} is < 32 bits." );
342 $pos = unpack( 'V', $octets )[1];
344 // Most-significant-bit is set, causing unpack() to return a negative integer due
345 // to the fact that it returns a signed int. Cast it to an unsigned integer string.
346 $pos = sprintf( '%u', $pos );
353 * @param string $nodeGroupName
354 * @return float[] Four ring positions on [0, self::RING_SIZE - 1]
356 private function getNodePositionQuartet( $nodeGroupName ) {
357 $octets = substr( hash( $this->algo
, (string)$nodeGroupName, true ), 0, 16 );
358 if ( strlen( $octets ) != 16 ) {
359 throw new UnexpectedValueException( __METHOD__
. ": {$this->algo} is < 128 bits." );
363 foreach ( unpack( 'V4', $octets ) as $signed ) {
364 $positions[] = (float)sprintf( '%u', $signed );
371 * @param int $i Valid index for a node in the ring
372 * @param array[] $ring Either the base or live ring
373 * @return int Valid index for a node in the ring
375 private function getNextClockwiseNodeIndex( $i, $ring ) {
376 if ( !isset( $ring[$i] ) ) {
377 throw new UnexpectedValueException( __METHOD__
. ": reference index is invalid." );
382 return ( $next < count( $ring ) ) ?
$next : 0;
386 * Get the "live" hash ring (which does not include ejected locations)
389 * @throws UnexpectedValueException
391 protected function getLiveRing() {
392 if ( !$this->ejectExpiryByLocation
) {
393 return $this->baseRing
; // nothing ejected
396 $now = $this->getCurrentTime();
398 if ( $this->liveRing
=== null ||
min( $this->ejectExpiryByLocation
) <= $now ) {
399 // Live ring needs to be regerenated...
400 $this->ejectExpiryByLocation
= array_filter(
401 $this->ejectExpiryByLocation
,
402 function ( $expiry ) use ( $now ) {
403 return ( $expiry > $now );
407 if ( count( $this->ejectExpiryByLocation
) ) {
408 // Some locations are still ejected from the ring
410 foreach ( $this->baseRing
as $i => $nodeInfo ) {
411 $location = $nodeInfo[self
::KEY_LOCATION
];
412 if ( !isset( $this->ejectExpiryByLocation
[$location] ) ) {
413 $liveRing[] = $nodeInfo;
417 $liveRing = $this->baseRing
;
420 $this->liveRing
= $liveRing;
423 if ( !$this->liveRing
) {
424 throw new UnexpectedValueException( "The live ring is currently empty." );
427 return $this->liveRing
;
431 * @return int UNIX timestamp
433 protected function getCurrentTime() {
437 public function serialize() {
439 'algorithm' => $this->algo
,
440 'locations' => $this->weightByLocation
,
441 'ejections' => $this->ejectExpiryByLocation
445 public function unserialize( $serialized ) {
446 $data = unserialize( $serialized );
447 if ( is_array( $data ) ) {
448 $this->init( $data['locations'], $data['algorithm'], $data['ejections'] );
450 throw new UnexpectedValueException( __METHOD__
. ": unable to decode JSON." );