MediaWiki  1.33.0
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, $this->algo );
100  }
101 
109  final public function getLocation( $item ) {
110  return $this->getLocations( $item, 1 )[0];
111  }
112 
122  public function getLocations( $item, $limit, $from = self::RING_ALL ) {
123  if ( $from === self::RING_ALL ) {
124  $ring = $this->baseRing;
125  } elseif ( $from === self::RING_LIVE ) {
126  $ring = $this->getLiveRing();
127  } else {
128  throw new InvalidArgumentException( "Invalid ring source specified." );
129  }
130 
131  // Locate this item's position on the hash ring
132  $position = $this->getItemPosition( $item );
133  $itemNodeIndex = $this->findNodeIndexForPosition( $position, $ring );
134 
135  $locations = [];
136  $currentIndex = $itemNodeIndex;
137  while ( count( $locations ) < $limit ) {
138  $nodeLocation = $ring[$currentIndex][self::KEY_LOCATION];
139  if ( !in_array( $nodeLocation, $locations, true ) ) {
140  // Ignore other nodes for the same locations already added
141  $locations[] = $nodeLocation;
142  }
143  $currentIndex = $this->getNextClockwiseNodeIndex( $currentIndex, $ring );
144  if ( $currentIndex === $itemNodeIndex ) {
145  break; // all nodes visited
146  }
147  }
148 
149  return $locations;
150  }
151 
157  private function findNodeIndexForPosition( $position, $ring ) {
158  $count = count( $ring );
159  if ( $count === 0 ) {
160  return null;
161  }
162  $lowPos = 0;
163  $highPos = $count;
164  while ( true ) {
165  $midPos = intval( ( $lowPos + $highPos ) / 2 );
166  if ( $midPos === $count ) {
167  return 0;
168  }
169  $midVal = $ring[$midPos][self::KEY_POS];
170  $midMinusOneVal = $midPos === 0 ? 0 : $ring[$midPos - 1][self::KEY_POS];
171 
172  if ( $position <= $midVal && $position > $midMinusOneVal ) {
173  return $midPos;
174  }
175 
176  if ( $midVal < $position ) {
177  $lowPos = $midPos + 1;
178  } else {
179  $highPos = $midPos - 1;
180  }
181 
182  if ( $lowPos > $highPos ) {
183  return 0;
184  }
185  }
186  }
187 
193  public function getLocationWeights() {
195  }
196 
205  public function ejectFromLiveRing( $location, $ttl ) {
206  if ( !isset( $this->weightByLocation[$location] ) ) {
207  throw new UnexpectedValueException( "No location '$location' in the ring." );
208  }
209 
210  $expiry = $this->getCurrentTime() + $ttl;
211  $this->ejectExpiryByLocation[$location] = $expiry;
212 
213  $this->liveRing = null; // invalidate ring cache
214 
215  return ( count( $this->ejectExpiryByLocation ) < count( $this->weightByLocation ) );
216  }
217 
225  final public function getLiveLocation( $item ) {
226  return $this->getLocations( $item, 1, self::RING_LIVE )[0];
227  }
228 
237  final public function getLiveLocations( $item, $limit ) {
238  return $this->getLocations( $item, $limit, self::RING_LIVE );
239  }
240 
247  public function getLiveLocationWeights() {
248  $now = $this->getCurrentTime();
249 
250  return array_diff_key(
251  $this->weightByLocation,
252  array_filter(
253  $this->ejectExpiryByLocation,
254  function ( $expiry ) use ( $now ) {
255  return ( $expiry > $now );
256  }
257  )
258  );
259  }
260 
267  $locationCount = count( $weightByLocation );
268  $totalWeight = array_sum( $weightByLocation );
269 
270  $ring = [];
271  // Assign nodes to all locations based on location weight
272  $claimed = []; // (position as string => (node, index))
273  foreach ( $weightByLocation as $location => $weight ) {
274  $ratio = $weight / $totalWeight;
275  // There $locationCount * (HASHES_PER_LOCATION * 4) nodes available;
276  // assign a few groups of nodes to this location based on its weight.
277  $nodesQuartets = intval( $ratio * self::HASHES_PER_LOCATION * $locationCount );
278  for ( $qi = 0; $qi < $nodesQuartets; ++$qi ) {
279  // For efficiency, get 4 points per hash call and 4X node count.
280  // If $algo is MD5, then this matches that of with libketama.
281  // See https://github.com/RJ/ketama/blob/master/libketama/ketama.c
282  $positions = $this->getNodePositionQuartet( "{$location}-{$qi}" );
283  foreach ( $positions as $gi => $position ) {
284  $node = ( $qi * self::SECTORS_PER_HASH + $gi ) . "@$location";
285  $posKey = (string)$position; // large integer
286  if ( isset( $claimed[$posKey] ) ) {
287  // Disallow duplicates for sanity (name decides precedence)
288  if ( $claimed[$posKey]['node'] > $node ) {
289  continue;
290  } else {
291  unset( $ring[$claimed[$posKey]['index']] );
292  }
293  }
294  $ring[] = [
295  self::KEY_POS => $position,
296  self::KEY_LOCATION => $location
297  ];
298  $claimed[$posKey] = [ 'node' => $node, 'index' => count( $ring ) - 1 ];
299  }
300  }
301  }
302  // Sort the locations into clockwise order based on the hash ring position
303  usort( $ring, function ( $a, $b ) {
304  if ( $a[self::KEY_POS] === $b[self::KEY_POS] ) {
305  throw new UnexpectedValueException( 'Duplicate node positions.' );
306  }
307 
308  return ( $a[self::KEY_POS] < $b[self::KEY_POS] ? -1 : 1 );
309  } );
310 
311  return $ring;
312  }
313 
318  private function getItemPosition( $item ) {
319  // If $algo is MD5, then this matches that of with libketama.
320  // See https://github.com/RJ/ketama/blob/master/libketama/ketama.c
321  $octets = substr( hash( $this->algo, (string)$item, true ), 0, 4 );
322  if ( strlen( $octets ) != 4 ) {
323  throw new UnexpectedValueException( __METHOD__ . ": {$this->algo} is < 32 bits." );
324  }
325 
326  return (float)sprintf( '%u', unpack( 'V', $octets )[1] );
327  }
328 
333  private function getNodePositionQuartet( $nodeGroupName ) {
334  $octets = substr( hash( $this->algo, (string)$nodeGroupName, true ), 0, 16 );
335  if ( strlen( $octets ) != 16 ) {
336  throw new UnexpectedValueException( __METHOD__ . ": {$this->algo} is < 128 bits." );
337  }
338 
339  $positions = [];
340  foreach ( unpack( 'V4', $octets ) as $signed ) {
341  $positions[] = (float)sprintf( '%u', $signed );
342  }
343 
344  return $positions;
345  }
346 
352  private function getNextClockwiseNodeIndex( $i, $ring ) {
353  if ( !isset( $ring[$i] ) ) {
354  throw new UnexpectedValueException( __METHOD__ . ": reference index is invalid." );
355  }
356 
357  $next = $i + 1;
358 
359  return ( $next < count( $ring ) ) ? $next : 0;
360  }
361 
368  protected function getLiveRing() {
369  if ( !$this->ejectExpiryByLocation ) {
370  return $this->baseRing; // nothing ejected
371  }
372 
373  $now = $this->getCurrentTime();
374 
375  if ( $this->liveRing === null || min( $this->ejectExpiryByLocation ) <= $now ) {
376  // Live ring needs to be regerenated...
377  $this->ejectExpiryByLocation = array_filter(
378  $this->ejectExpiryByLocation,
379  function ( $expiry ) use ( $now ) {
380  return ( $expiry > $now );
381  }
382  );
383 
384  if ( count( $this->ejectExpiryByLocation ) ) {
385  // Some locations are still ejected from the ring
386  $liveRing = [];
387  foreach ( $this->baseRing as $i => $nodeInfo ) {
388  $location = $nodeInfo[self::KEY_LOCATION];
389  if ( !isset( $this->ejectExpiryByLocation[$location] ) ) {
390  $liveRing[] = $nodeInfo;
391  }
392  }
393  } else {
395  }
396 
397  $this->liveRing = $liveRing;
398  }
399 
400  if ( !$this->liveRing ) {
401  throw new UnexpectedValueException( "The live ring is currently empty." );
402  }
403 
404  return $this->liveRing;
405  }
406 
410  protected function getCurrentTime() {
411  return time();
412  }
413 
414  public function serialize() {
415  return serialize( [
416  'algorithm' => $this->algo,
417  'locations' => $this->weightByLocation,
418  'ejections' => $this->ejectExpiryByLocation
419  ] );
420  }
421 
422  public function unserialize( $serialized ) {
424  if ( is_array( $data ) ) {
425  $this->init( $data['locations'], $data['algorithm'], $data['ejections'] );
426  } else {
427  throw new UnexpectedValueException( __METHOD__ . ": unable to decode JSON." );
428  }
429  }
430 }
HashRing\$ejectExpiryByLocation
int[] $ejectExpiryByLocation
Map of (location => UNIX timestamp)
Definition: HashRing.php:45
HashRing\$liveRing
array[] $liveRing
Non-empty list of (float, node name, location name)
Definition: HashRing.php:50
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:75
HashRing\getItemPosition
getItemPosition( $item)
Definition: HashRing.php:318
captcha-old.count
count
Definition: captcha-old.py:249
HashRing\getLiveLocationWeights
getLiveLocationWeights()
Get the map of "live" locations to weight (does not include zero weight items)
Definition: HashRing.php:247
HashRing\getLiveRing
getLiveRing()
Get the "live" hash ring (which does not include ejected locations)
Definition: HashRing.php:368
$serialized
foreach( $res as $row) $serialized
Definition: testCompression.php:81
HashRing\ejectFromLiveRing
ejectFromLiveRing( $location, $ttl)
Remove a location from the "live" hash ring.
Definition: HashRing.php:205
HashRing\getLocations
getLocations( $item, $limit, $from=self::RING_ALL)
Get the location of an item on the ring, as well as the next locations.
Definition: HashRing.php:122
php
injection txt This is an overview of how MediaWiki makes use of dependency injection The design described here grew from the discussion of RFC T384 The term dependency this means that anything an object needs to operate should be injected from the the object itself should only know narrow no concrete implementation of the logic it relies on The requirement to inject everything typically results in an architecture that based on two main types of and essentially stateless service objects that use other service objects to operate on the value objects As of the beginning MediaWiki is only starting to use the DI approach Much of the code still relies on global state or direct resulting in a highly cyclical dependency which acts as the top level factory for services in MediaWiki which can be used to gain access to default instances of various services MediaWikiServices however also allows new services to be defined and default services to be redefined Services are defined or redefined by providing a callback the instantiator that will return a new instance of the service When it will create an instance of MediaWikiServices and populate it with the services defined in the files listed by thereby bootstrapping the DI framework Per $wgServiceWiringFiles lists includes ServiceWiring php
Definition: injection.txt:35
HashRing\$algo
string $algo
Hashing algorithm for hash()
Definition: HashRing.php:41
HashRing\$weightByLocation
int[] $weightByLocation
Non-empty (location => integer weight)
Definition: HashRing.php:43
HashRing\getLocation
getLocation( $item)
Get the location of an item on the ring.
Definition: HashRing.php:109
$data
$data
Utility to generate mapping file used in mw.Title (phpCharToUpper.json)
Definition: generatePhpCharToUpperMappings.php:13
HashRing\getLocationWeights
getLocationWeights()
Get the map of locations to weight (does not include zero weight items)
Definition: HashRing.php:193
HashRing\getCurrentTime
getCurrentTime()
Definition: HashRing.php:410
HashRing\buildLocationRing
buildLocationRing(array $weightByLocation, $algo)
Definition: HashRing.php:266
HashRing\KEY_LOCATION
const KEY_LOCATION
Definition: HashRing.php:60
HashRing\unserialize
unserialize( $serialized)
Definition: HashRing.php:422
HashRing\getLiveLocations
getLiveLocations( $item, $limit)
Get the location of an item on the "live" ring, as well as the next locations.
Definition: HashRing.php:237
HashRing\serialize
serialize()
Definition: HashRing.php:414
use
as see the revision history and available at free of to any person obtaining a copy of this software and associated documentation to deal in the Software without including without limitation the rights to use
Definition: MIT-LICENSE.txt:10
array
The wiki should then use memcached to cache various data To use multiple just add more items to the array To increase the weight of a make its entry a array("192.168.0.1:11211", 2))
string
This code would result in ircNotify being run twice when an article is and once for brion Hooks can return three possible true was required This is the default since MediaWiki *some string
Definition: hooks.txt:175
HashRing\init
init(array $map, $algo, array $ejections)
Definition: HashRing.php:84
HashRing\getNextClockwiseNodeIndex
getNextClockwiseNodeIndex( $i, $ring)
Definition: HashRing.php:352
HashRing\getNodePositionQuartet
getNodePositionQuartet( $nodeGroupName)
Definition: HashRing.php:333
HashRing\findNodeIndexForPosition
findNodeIndexForPosition( $position, $ring)
Definition: HashRing.php:157
as
This document is intended to provide useful advice for parties seeking to redistribute MediaWiki to end users It s targeted particularly at maintainers for Linux since it s been observed that distribution packages of MediaWiki often break We ve consistently had to recommend that users seeking support use official tarballs instead of their distribution s and this often solves whatever problem the user is having It would be nice if this could such as
Definition: distributors.txt:9
HashRing\$baseRing
array[] $baseRing
Non-empty list of (float, node name, location name)
Definition: HashRing.php:48
HashRing
Convenience class for weighted consistent hash rings.
Definition: HashRing.php:39
HashRing\KEY_POS
const KEY_POS
Definition: HashRing.php:59
HashRing\getLiveLocation
getLiveLocation( $item)
Get the location of an item on the "live" ring.
Definition: HashRing.php:225