MediaWiki  master
HashRing.php
Go to the documentation of this file.
1 <?php
39 class HashRing implements Serializable {
41  protected $algo;
43  protected $weightByLocation;
46 
48  protected $baseRing;
50  protected $liveRing;
51 
53  const RING_SIZE = 4294967296.0; // 2^32
55  const HASHES_PER_LOCATION = 40;
57  const SECTORS_PER_HASH = 4;
58 
59  const KEY_POS = 0;
60  const KEY_LOCATION = 1;
61 
63  const RING_ALL = 0;
65  const RING_LIVE = 1;
66 
75  public function __construct( array $map, $algo = 'sha1', array $ejections = [] ) {
76  $this->init( $map, $algo, $ejections );
77  }
78 
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." );
87  }
88 
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." );
94  }
95 
96  $this->algo = $algo;
97  $this->weightByLocation = $weightByLocation;
98  $this->ejectExpiryByLocation = $ejections;
99  $this->baseRing = $this->buildLocationRing( $this->weightByLocation );
100  }
101 
109  final public function getLocation( $item ) {
110  return $this->getLocations( $item, 1 )[0];
111  }
112 
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();
128  } else {
129  throw new InvalidArgumentException( "Invalid ring source specified." );
130  }
131 
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] ] : [];
136  }
137 
138  // Locate the node index for this item's position on the hash ring
139  $itemIndex = $this->findNodeIndexForPosition( $this->getItemPosition( $item ), $ring );
140 
141  $locations = [];
142  $currentIndex = null;
143  while ( count( $locations ) < $limit ) {
144  if ( $currentIndex === null ) {
145  $currentIndex = $itemIndex;
146  } else {
147  $currentIndex = $this->getNextClockwiseNodeIndex( $currentIndex, $ring );
148  if ( $currentIndex === $itemIndex ) {
149  break; // all nodes visited
150  }
151  }
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;
156  }
157  }
158 
159  return $locations;
160  }
161 
167  private function findNodeIndexForPosition( $position, $ring ) {
168  $count = count( $ring );
169  if ( $count === 0 ) {
170  return null;
171  }
172 
173  $index = null;
174  $lowPos = 0;
175  $highPos = $count;
176  while ( true ) {
177  $midPos = (int)( ( $lowPos + $highPos ) / 2 );
178  if ( $midPos === $count ) {
179  $index = 0;
180  break;
181  }
182 
183  $midVal = $ring[$midPos][self::KEY_POS];
184  $midMinusOneVal = ( $midPos === 0 ) ? 0 : $ring[$midPos - 1][self::KEY_POS];
185  if ( $position <= $midVal && $position > $midMinusOneVal ) {
186  $index = $midPos;
187  break;
188  }
189 
190  if ( $midVal < $position ) {
191  $lowPos = $midPos + 1;
192  } else {
193  $highPos = $midPos - 1;
194  }
195 
196  if ( $lowPos > $highPos ) {
197  $index = 0;
198  break;
199  }
200  }
201 
202  return $index;
203  }
204 
210  public function getLocationWeights() {
212  }
213 
222  public function ejectFromLiveRing( $location, $ttl ) {
223  if ( !isset( $this->weightByLocation[$location] ) ) {
224  throw new UnexpectedValueException( "No location '$location' in the ring." );
225  }
226 
227  $expiry = $this->getCurrentTime() + $ttl;
228  $this->ejectExpiryByLocation[$location] = $expiry;
229 
230  $this->liveRing = null; // invalidate ring cache
231 
232  return ( count( $this->ejectExpiryByLocation ) < count( $this->weightByLocation ) );
233  }
234 
242  final public function getLiveLocation( $item ) {
243  return $this->getLocations( $item, 1, self::RING_LIVE )[0];
244  }
245 
254  final public function getLiveLocations( $item, $limit ) {
255  return $this->getLocations( $item, $limit, self::RING_LIVE );
256  }
257 
264  public function getLiveLocationWeights() {
265  $now = $this->getCurrentTime();
266 
267  return array_diff_key(
268  $this->weightByLocation,
269  array_filter(
270  $this->ejectExpiryByLocation,
271  function ( $expiry ) use ( $now ) {
272  return ( $expiry > $now );
273  }
274  )
275  );
276  }
277 
282  private function buildLocationRing( array $weightByLocation ) {
283  $locationCount = count( $weightByLocation );
284  $totalWeight = array_sum( $weightByLocation );
285 
286  $ring = [];
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 ) {
305  continue;
306  } else {
307  unset( $ring[$claimed[$posKey]['index']] );
308  }
309  }
310  $ring[] = [
311  self::KEY_POS => $position,
312  self::KEY_LOCATION => $location
313  ];
314  $claimed[$posKey] = [ 'node' => $node, 'index' => count( $ring ) - 1 ];
315  }
316  }
317  }
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.' );
322  }
323 
324  return ( $a[self::KEY_POS] < $b[self::KEY_POS] ? -1 : 1 );
325  } );
326 
327  return $ring;
328  }
329 
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." );
340  }
341 
342  $pos = unpack( 'V', $octets )[1];
343  if ( $pos < 0 ) {
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 );
347  }
348 
349  return (float)$pos;
350  }
351 
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." );
360  }
361 
362  $positions = [];
363  foreach ( unpack( 'V4', $octets ) as $signed ) {
364  $positions[] = (float)sprintf( '%u', $signed );
365  }
366 
367  return $positions;
368  }
369 
375  private function getNextClockwiseNodeIndex( $i, $ring ) {
376  if ( !isset( $ring[$i] ) ) {
377  throw new UnexpectedValueException( __METHOD__ . ": reference index is invalid." );
378  }
379 
380  $next = $i + 1;
381 
382  return ( $next < count( $ring ) ) ? $next : 0;
383  }
384 
391  protected function getLiveRing() {
392  if ( !$this->ejectExpiryByLocation ) {
393  return $this->baseRing; // nothing ejected
394  }
395 
396  $now = $this->getCurrentTime();
397 
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 );
404  }
405  );
406 
407  if ( count( $this->ejectExpiryByLocation ) ) {
408  // Some locations are still ejected from the ring
409  $liveRing = [];
410  foreach ( $this->baseRing as $i => $nodeInfo ) {
411  $location = $nodeInfo[self::KEY_LOCATION];
412  if ( !isset( $this->ejectExpiryByLocation[$location] ) ) {
413  $liveRing[] = $nodeInfo;
414  }
415  }
416  } else {
418  }
419 
420  $this->liveRing = $liveRing;
421  }
422 
423  if ( !$this->liveRing ) {
424  throw new UnexpectedValueException( "The live ring is currently empty." );
425  }
426 
427  return $this->liveRing;
428  }
429 
433  protected function getCurrentTime() {
434  return time();
435  }
436 
437  public function serialize() {
438  return serialize( [
439  'algorithm' => $this->algo,
440  'locations' => $this->weightByLocation,
441  'ejections' => $this->ejectExpiryByLocation
442  ] );
443  }
444 
445  public function unserialize( $serialized ) {
446  $data = unserialize( $serialized );
447  if ( is_array( $data ) ) {
448  $this->init( $data['locations'], $data['algorithm'], $data['ejections'] );
449  } else {
450  throw new UnexpectedValueException( __METHOD__ . ": unable to decode JSON." );
451  }
452  }
453 }
findNodeIndexForPosition( $position, $ring)
Definition: HashRing.php:167
getCurrentTime()
Definition: HashRing.php:433
array [] $liveRing
Non-empty position-ordered list of (position, location name)
Definition: HashRing.php:50
const KEY_POS
Definition: HashRing.php:59
const KEY_LOCATION
Definition: HashRing.php:60
getLocationWeights()
Get the map of locations to weight (does not include zero weight items)
Definition: HashRing.php:210
getLiveLocation( $item)
Get the location of an item on the "live" ring.
Definition: HashRing.php:242
getLiveLocationWeights()
Get the map of "live" locations to weight (does not include zero weight items)
Definition: HashRing.php:264
getItemPosition( $item)
Definition: HashRing.php:334
init(array $map, $algo, array $ejections)
Definition: HashRing.php:84
buildLocationRing(array $weightByLocation)
Definition: HashRing.php:282
Convenience class for weighted consistent hash rings.
Definition: HashRing.php:39
getLocation( $item)
Get the location of an item on the ring.
Definition: HashRing.php:109
getLiveLocations( $item, $limit)
Get the location of an item on the "live" ring, as well as the next locations.
Definition: HashRing.php:254
getLiveRing()
Get the "live" hash ring (which does not include ejected locations)
Definition: HashRing.php:391
ejectFromLiveRing( $location, $ttl)
Remove a location from the "live" hash ring.
Definition: HashRing.php:222
string $algo
Hashing algorithm for hash()
Definition: HashRing.php:41
getLocations( $item, $limit, $from=self::RING_ALL)
Get the location of an item on the ring followed by the next ring locations.
Definition: HashRing.php:123
int [] $weightByLocation
Non-empty (location => integer weight)
Definition: HashRing.php:43
getNextClockwiseNodeIndex( $i, $ring)
Definition: HashRing.php:375
serialize()
Definition: HashRing.php:437
array [] $baseRing
Non-empty position-ordered list of (position, location name)
Definition: HashRing.php:48
unserialize( $serialized)
Definition: HashRing.php:445
foreach( $res as $row) $serialized
getNodePositionQuartet( $nodeGroupName)
Definition: HashRing.php:356
int [] $ejectExpiryByLocation
Map of (location => UNIX timestamp)
Definition: HashRing.php:45
__construct(array $map, $algo='sha1', array $ejections=[])
Make a consistent hash ring given a set of locations and their weight values.
Definition: HashRing.php:75