MediaWiki  master
HashRing.php
Go to the documentation of this file.
1 <?php
44 class HashRing implements Serializable {
46  protected $algo;
48  protected $weightByLocation;
51 
53  protected $baseRing;
55  protected $liveRing;
56 
58  private const HASHES_PER_LOCATION = 40;
60  private const SECTORS_PER_HASH = 4;
61 
62  public const KEY_POS = 0;
63  public const KEY_LOCATION = 1;
64 
66  public const RING_ALL = 0;
68  public const RING_LIVE = 1;
69 
78  public function __construct( array $map, $algo = 'sha1', array $ejections = [] ) {
79  $this->init( $map, $algo, $ejections );
80  }
81 
87  protected function init( array $map, $algo, array $ejections ) {
88  if ( !in_array( $algo, hash_algos(), true ) ) {
89  throw new RuntimeException( __METHOD__ . ": unsupported '$algo' hash algorithm." );
90  }
91 
92  $weightByLocation = array_filter( $map );
93  if ( $weightByLocation === [] ) {
94  throw new UnexpectedValueException( "No locations with non-zero weight." );
95  } elseif ( min( $map ) < 0 ) {
96  throw new InvalidArgumentException( "Location weight cannot be negative." );
97  }
98 
99  $this->algo = $algo;
100  $this->weightByLocation = $weightByLocation;
101  $this->ejectExpiryByLocation = $ejections;
102  $this->baseRing = $this->buildLocationRing( $this->weightByLocation );
103  }
104 
112  final public function getLocation( $item ) {
113  return $this->getLocations( $item, 1 )[0];
114  }
115 
126  public function getLocations( $item, $limit, $from = self::RING_ALL ) {
127  if ( $from === self::RING_ALL ) {
128  $ring = $this->baseRing;
129  } elseif ( $from === self::RING_LIVE ) {
130  $ring = $this->getLiveRing();
131  } else {
132  throw new InvalidArgumentException( "Invalid ring source specified." );
133  }
134 
135  // Short-circuit for the common single-location case. Note that if there was only one
136  // location and it was ejected from the live ring, getLiveRing() would have error out.
137  if ( count( $this->weightByLocation ) == 1 ) {
138  return ( $limit > 0 ) ? [ $ring[0][self::KEY_LOCATION] ] : [];
139  }
140 
141  // Locate the node index for this item's position on the hash ring
142  $itemIndex = $this->findNodeIndexForPosition( $this->getItemPosition( $item ), $ring );
143 
144  $locations = [];
145  $currentIndex = null;
146  while ( count( $locations ) < $limit ) {
147  if ( $currentIndex === null ) {
148  $currentIndex = $itemIndex;
149  } else {
150  $currentIndex = $this->getNextClockwiseNodeIndex( $currentIndex, $ring );
151  if ( $currentIndex === $itemIndex ) {
152  break; // all nodes visited
153  }
154  }
155  $nodeLocation = $ring[$currentIndex][self::KEY_LOCATION];
156  if ( !in_array( $nodeLocation, $locations, true ) ) {
157  // Ignore other nodes for the same locations already added
158  $locations[] = $nodeLocation;
159  }
160  }
161 
162  return $locations;
163  }
164 
170  private function findNodeIndexForPosition( $position, $ring ) {
171  $count = count( $ring );
172  if ( $count === 0 ) {
173  return null;
174  }
175 
176  $index = null;
177  $lowPos = 0;
178  $highPos = $count;
179  while ( true ) {
180  $midPos = (int)( ( $lowPos + $highPos ) / 2 );
181  if ( $midPos === $count ) {
182  $index = 0;
183  break;
184  }
185 
186  $midVal = $ring[$midPos][self::KEY_POS];
187  $midMinusOneVal = ( $midPos === 0 ) ? 0 : $ring[$midPos - 1][self::KEY_POS];
188  if ( $position <= $midVal && $position > $midMinusOneVal ) {
189  $index = $midPos;
190  break;
191  }
192 
193  if ( $midVal < $position ) {
194  $lowPos = $midPos + 1;
195  } else {
196  $highPos = $midPos - 1;
197  }
198 
199  if ( $lowPos > $highPos ) {
200  $index = 0;
201  break;
202  }
203  }
204 
205  return $index;
206  }
207 
213  public function getLocationWeights() {
215  }
216 
225  public function ejectFromLiveRing( $location, $ttl ) {
226  if ( !isset( $this->weightByLocation[$location] ) ) {
227  throw new UnexpectedValueException( "No location '$location' in the ring." );
228  }
229 
230  $expiry = $this->getCurrentTime() + $ttl;
231  $this->ejectExpiryByLocation[$location] = $expiry;
232 
233  $this->liveRing = null; // invalidate ring cache
234 
235  return ( count( $this->ejectExpiryByLocation ) < count( $this->weightByLocation ) );
236  }
237 
245  final public function getLiveLocation( $item ) {
246  return $this->getLocations( $item, 1, self::RING_LIVE )[0];
247  }
248 
257  final public function getLiveLocations( $item, $limit ) {
258  return $this->getLocations( $item, $limit, self::RING_LIVE );
259  }
260 
267  public function getLiveLocationWeights() {
268  $now = $this->getCurrentTime();
269 
270  return array_diff_key(
271  $this->weightByLocation,
272  array_filter(
273  $this->ejectExpiryByLocation,
274  function ( $expiry ) use ( $now ) {
275  return ( $expiry > $now );
276  }
277  )
278  );
279  }
280 
285  private function buildLocationRing( array $weightByLocation ) {
286  $locationCount = count( $weightByLocation );
287  $totalWeight = array_sum( $weightByLocation );
288 
289  $ring = [];
290  // Assign nodes to all locations based on location weight
291  $claimed = []; // (position as string => (node, index))
292  foreach ( $weightByLocation as $location => $weight ) {
293  $ratio = $weight / $totalWeight;
294  // There $locationCount * (HASHES_PER_LOCATION * 4) nodes available;
295  // assign a few groups of nodes to this location based on its weight.
296  $nodesQuartets = intval( $ratio * self::HASHES_PER_LOCATION * $locationCount );
297  for ( $qi = 0; $qi < $nodesQuartets; ++$qi ) {
298  // For efficiency, get 4 points per hash call and 4X node count.
299  // If $algo is MD5, then this matches that of with libketama.
300  // See https://github.com/RJ/ketama/blob/master/libketama/ketama.c
301  $positions = $this->getNodePositionQuartet( "{$location}-{$qi}" );
302  foreach ( $positions as $gi => $position ) {
303  $node = ( $qi * self::SECTORS_PER_HASH + $gi ) . "@$location";
304  $posKey = (string)$position; // large integer
305  if ( isset( $claimed[$posKey] ) ) {
306  // Disallow duplicates for sanity (name decides precedence)
307  if ( $claimed[$posKey]['node'] > $node ) {
308  continue;
309  } else {
310  unset( $ring[$claimed[$posKey]['index']] );
311  }
312  }
313  $ring[] = [
314  self::KEY_POS => $position,
315  self::KEY_LOCATION => $location
316  ];
317  $claimed[$posKey] = [ 'node' => $node, 'index' => count( $ring ) - 1 ];
318  }
319  }
320  }
321  // Sort the locations into clockwise order based on the hash ring position
322  usort( $ring, function ( $a, $b ) {
323  if ( $a[self::KEY_POS] === $b[self::KEY_POS] ) {
324  throw new UnexpectedValueException( 'Duplicate node positions.' );
325  }
326 
327  return ( $a[self::KEY_POS] < $b[self::KEY_POS] ? -1 : 1 );
328  } );
329 
330  return $ring;
331  }
332 
337  private function getItemPosition( $item ) {
338  // If $algo is MD5, then this matches that of with libketama.
339  // See https://github.com/RJ/ketama/blob/master/libketama/ketama.c
340  $octets = substr( hash( $this->algo, (string)$item, true ), 0, 4 );
341  if ( strlen( $octets ) != 4 ) {
342  throw new UnexpectedValueException( __METHOD__ . ": {$this->algo} is < 32 bits." );
343  }
344 
345  $pos = unpack( 'V', $octets )[1];
346  if ( $pos < 0 ) {
347  // Most-significant-bit is set, causing unpack() to return a negative integer due
348  // to the fact that it returns a signed int. Cast it to an unsigned integer string.
349  $pos = sprintf( '%u', $pos );
350  }
351 
352  return (float)$pos;
353  }
354 
359  private function getNodePositionQuartet( $nodeGroupName ) {
360  $octets = substr( hash( $this->algo, (string)$nodeGroupName, true ), 0, 16 );
361  if ( strlen( $octets ) != 16 ) {
362  throw new UnexpectedValueException( __METHOD__ . ": {$this->algo} is < 128 bits." );
363  }
364 
365  $positions = [];
366  foreach ( unpack( 'V4', $octets ) as $signed ) {
367  $positions[] = (float)sprintf( '%u', $signed );
368  }
369 
370  return $positions;
371  }
372 
378  private function getNextClockwiseNodeIndex( $i, $ring ) {
379  if ( !isset( $ring[$i] ) ) {
380  throw new UnexpectedValueException( __METHOD__ . ": reference index is invalid." );
381  }
382 
383  $next = $i + 1;
384 
385  return ( $next < count( $ring ) ) ? $next : 0;
386  }
387 
394  protected function getLiveRing() {
395  if ( !$this->ejectExpiryByLocation ) {
396  return $this->baseRing; // nothing ejected
397  }
398 
399  $now = $this->getCurrentTime();
400 
401  if ( $this->liveRing === null || min( $this->ejectExpiryByLocation ) <= $now ) {
402  // Live ring needs to be regerenated...
403  $this->ejectExpiryByLocation = array_filter(
404  $this->ejectExpiryByLocation,
405  function ( $expiry ) use ( $now ) {
406  return ( $expiry > $now );
407  }
408  );
409 
410  if ( count( $this->ejectExpiryByLocation ) ) {
411  // Some locations are still ejected from the ring
412  $liveRing = [];
413  foreach ( $this->baseRing as $i => $nodeInfo ) {
414  $location = $nodeInfo[self::KEY_LOCATION];
415  if ( !isset( $this->ejectExpiryByLocation[$location] ) ) {
416  $liveRing[] = $nodeInfo;
417  }
418  }
419  } else {
421  }
422 
423  $this->liveRing = $liveRing;
424  }
425 
426  if ( !$this->liveRing ) {
427  throw new UnexpectedValueException( "The live ring is currently empty." );
428  }
429 
430  return $this->liveRing;
431  }
432 
436  protected function getCurrentTime() {
437  return time();
438  }
439 
440  public function serialize() {
441  return serialize( [
442  'algorithm' => $this->algo,
443  'locations' => $this->weightByLocation,
444  'ejections' => $this->ejectExpiryByLocation
445  ] );
446  }
447 
448  public function unserialize( $serialized ) {
449  $data = unserialize( $serialized );
450  if ( is_array( $data ) ) {
451  $this->init( $data['locations'], $data['algorithm'], $data['ejections'] );
452  } else {
453  throw new UnexpectedValueException( __METHOD__ . ": unable to decode JSON." );
454  }
455  }
456 }
HashRing\$ejectExpiryByLocation
int[] $ejectExpiryByLocation
Map of (location => UNIX timestamp)
Definition: HashRing.php:50
HashRing\$liveRing
array[] $liveRing
Non-empty position-ordered list of (position, location name)
Definition: HashRing.php:55
HashRing\__construct
__construct(array $map, $algo='sha1', array $ejections=[])
Make a consistent hash ring given a set of locations and their weight values.
Definition: HashRing.php:78
HashRing\getItemPosition
getItemPosition( $item)
Definition: HashRing.php:337
HashRing\getLiveLocationWeights
getLiveLocationWeights()
Get the map of "live" locations to weight (does not include zero weight items)
Definition: HashRing.php:267
HashRing\getLiveRing
getLiveRing()
Get the "live" hash ring (which does not include ejected locations)
Definition: HashRing.php:394
$serialized
foreach( $res as $row) $serialized
Definition: testCompression.php:88
HashRing\ejectFromLiveRing
ejectFromLiveRing( $location, $ttl)
Remove a location from the "live" hash ring.
Definition: HashRing.php:225
HashRing\getLocations
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:126
HashRing\$algo
string $algo
Hashing algorithm for hash()
Definition: HashRing.php:46
HashRing\$weightByLocation
int[] $weightByLocation
Non-empty (location => integer weight)
Definition: HashRing.php:48
HashRing\getLocation
getLocation( $item)
Get the location of an item on the ring.
Definition: HashRing.php:112
HashRing\getLocationWeights
getLocationWeights()
Get the map of locations to weight (does not include zero weight items)
Definition: HashRing.php:213
HashRing\getCurrentTime
getCurrentTime()
Definition: HashRing.php:436
HashRing\KEY_LOCATION
const KEY_LOCATION
Definition: HashRing.php:63
HashRing\unserialize
unserialize( $serialized)
Definition: HashRing.php:448
HashRing\getLiveLocations
getLiveLocations( $item, $limit)
Get the location of an item on the "live" ring, as well as the next locations.
Definition: HashRing.php:257
HashRing\serialize
serialize()
Definition: HashRing.php:440
HashRing\buildLocationRing
buildLocationRing(array $weightByLocation)
Definition: HashRing.php:285
HashRing\init
init(array $map, $algo, array $ejections)
Definition: HashRing.php:87
HashRing\getNextClockwiseNodeIndex
getNextClockwiseNodeIndex( $i, $ring)
Definition: HashRing.php:378
HashRing\getNodePositionQuartet
getNodePositionQuartet( $nodeGroupName)
Definition: HashRing.php:359
HashRing\findNodeIndexForPosition
findNodeIndexForPosition( $position, $ring)
Definition: HashRing.php:170
HashRing\$baseRing
array[] $baseRing
Non-empty position-ordered list of (position, location name)
Definition: HashRing.php:53
HashRing
Convenience class for weighted consistent hash rings.
Definition: HashRing.php:44
HashRing\KEY_POS
const KEY_POS
Definition: HashRing.php:62
HashRing\getLiveLocation
getLiveLocation( $item)
Get the location of an item on the "live" ring.
Definition: HashRing.php:245