MediaWiki  1.30.0
HashRing.php
Go to the documentation of this file.
1 <?php
28 class HashRing {
30  protected $sourceMap = [];
32  protected $ring = [];
33 
35  protected $liveRing;
37  protected $ejectionExpiries = [];
39  protected $ejectionNextExpiry = INF;
40 
41  const RING_SIZE = 268435456; // 2^28
42 
46  public function __construct( array $map ) {
47  $map = array_filter( $map, function ( $w ) {
48  return $w > 0;
49  } );
50  if ( !count( $map ) ) {
51  throw new UnexpectedValueException( "Ring is empty or all weights are zero." );
52  }
53  $this->sourceMap = $map;
54  // Sort the locations based on the hash of their names
55  $hashes = [];
56  foreach ( $map as $location => $weight ) {
57  $hashes[$location] = sha1( $location );
58  }
59  uksort( $map, function ( $a, $b ) use ( $hashes ) {
60  return strcmp( $hashes[$a], $hashes[$b] );
61  } );
62  // Fit the map to weight-proportionate one with a space of size RING_SIZE
63  $sum = array_sum( $map );
64  $standardMap = [];
65  foreach ( $map as $location => $weight ) {
66  $standardMap[$location] = (int)floor( $weight / $sum * self::RING_SIZE );
67  }
68  // Build a ring of RING_SIZE spots, with each location at a spot in location hash order
69  $index = 0;
70  foreach ( $standardMap as $location => $weight ) {
71  // Location covers half-closed interval [$index,$index + $weight)
72  $this->ring[$location] = [ $index, $index + $weight ];
73  $index += $weight;
74  }
75  // Make sure the last location covers what is left
76  end( $this->ring );
77  $this->ring[key( $this->ring )][1] = self::RING_SIZE;
78  }
79 
86  public function getLocation( $item ) {
87  $locations = $this->getLocations( $item, 1 );
88 
89  return $locations[0];
90  }
91 
99  public function getLocations( $item, $limit ) {
100  $locations = [];
101  $primaryLocation = null;
102  $spot = hexdec( substr( sha1( $item ), 0, 7 ) ); // first 28 bits
103  foreach ( $this->ring as $location => $range ) {
104  if ( count( $locations ) >= $limit ) {
105  break;
106  }
107  // The $primaryLocation is the location the item spot is in.
108  // After that is reached, keep appending the next locations.
109  if ( ( $range[0] <= $spot && $spot < $range[1] ) || $primaryLocation !== null ) {
110  if ( $primaryLocation === null ) {
111  $primaryLocation = $location;
112  }
113  $locations[] = $location;
114  }
115  }
116  // If more locations are requested, wrap-around and keep adding them
117  reset( $this->ring );
118  while ( count( $locations ) < $limit ) {
119  list( $location, ) = each( $this->ring );
120  if ( $location === $primaryLocation ) {
121  break; // don't go in circles
122  }
123  $locations[] = $location;
124  }
125 
126  return $locations;
127  }
128 
134  public function getLocationWeights() {
135  return $this->sourceMap;
136  }
137 
144  public function newWithoutLocation( $location ) {
145  $map = $this->sourceMap;
146  unset( $map[$location] );
147 
148  return count( $map ) ? new self( $map ) : false;
149  }
150 
158  public function ejectFromLiveRing( $location, $ttl ) {
159  if ( !isset( $this->sourceMap[$location] ) ) {
160  throw new UnexpectedValueException( "No location '$location' in the ring." );
161  }
162  $expiry = time() + $ttl;
163  $this->liveRing = null; // stale
164  $this->ejectionExpiries[$location] = $expiry;
165  $this->ejectionNextExpiry = min( $expiry, $this->ejectionNextExpiry );
166 
167  return ( count( $this->ejectionExpiries ) < count( $this->sourceMap ) );
168  }
169 
176  public function getLiveRing() {
177  $now = time();
178  if ( $this->liveRing === null || $this->ejectionNextExpiry <= $now ) {
179  $this->ejectionExpiries = array_filter(
180  $this->ejectionExpiries,
181  function ( $expiry ) use ( $now ) {
182  return ( $expiry > $now );
183  }
184  );
185  if ( count( $this->ejectionExpiries ) ) {
186  $map = array_diff_key( $this->sourceMap, $this->ejectionExpiries );
187  $this->liveRing = count( $map ) ? new self( $map ) : false;
188 
189  $this->ejectionNextExpiry = min( $this->ejectionExpiries );
190  } else { // common case; avoid recalculating ring
191  $this->liveRing = clone $this;
192  $this->liveRing->ejectionExpiries = [];
193  $this->liveRing->ejectionNextExpiry = INF;
194  $this->liveRing->liveRing = null;
195 
196  $this->ejectionNextExpiry = INF;
197  }
198  }
199  if ( !$this->liveRing ) {
200  throw new UnexpectedValueException( "The live ring is currently empty." );
201  }
202 
203  return $this->liveRing;
204  }
205 
213  public function getLiveLocation( $item ) {
214  return $this->getLiveRing()->getLocation( $item );
215  }
216 
225  public function getLiveLocations( $item, $limit ) {
226  return $this->getLiveRing()->getLocations( $item, $limit );
227  }
228 
235  public function getLiveLocationWeights() {
236  return $this->getLiveRing()->getLocationWeights();
237  }
238 }
HashRing\getLocations
getLocations( $item, $limit)
Get the location of an item on the ring, as well as the next locations.
Definition: HashRing.php:99
captcha-old.count
count
Definition: captcha-old.py:249
HashRing\__construct
__construct(array $map)
Definition: HashRing.php:46
HashRing\getLiveLocationWeights
getLiveLocationWeights()
Get the map of "live" locations to weight (ignores 0-weight items)
Definition: HashRing.php:235
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
HashRing\getLiveRing
getLiveRing()
Get the "live" hash ring (which does not include ejected locations)
Definition: HashRing.php:176
HashRing\ejectFromLiveRing
ejectFromLiveRing( $location, $ttl)
Remove a location from the "live" hash ring.
Definition: HashRing.php:158
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
key
design txt This is a brief overview of the new design More thorough and up to date information is available on the documentation wiki at etc Handles the details of getting and saving to the user table of the and dealing with sessions and cookies OutputPage Encapsulates the entire HTML page that will be sent in response to any server request It is used by calling its functions to add in any and then calling but I prefer the flexibility This should also do the output encoding The system allocates a global one in $wgOut Title Represents the title of an and does all the work of translating among various forms such as plain database key
Definition: design.txt:25
HashRing\getLocation
getLocation( $item)
Get the location of an item on the ring.
Definition: HashRing.php:86
HashRing\getLocationWeights
getLocationWeights()
Get the map of locations to weight (ignores 0-weight items)
Definition: HashRing.php:134
HashRing\getLiveLocations
getLiveLocations( $item, $limit)
Get the location of an item on the "live" ring, as well as the next locations.
Definition: HashRing.php:225
HashRing\$sourceMap
Array $sourceMap
(location => weight)
Definition: HashRing.php:30
list
deferred txt A few of the database updates required by various functions here can be deferred until after the result page is displayed to the user For updating the view updating the linked to tables after a etc PHP does not yet have any way to tell the server to actually return and disconnect while still running these but it might have such a feature in the future We handle these by creating a deferred update object and putting those objects on a global list
Definition: deferred.txt:11
HashRing\$ejectionNextExpiry
int $ejectionNextExpiry
UNIX timestamp.
Definition: HashRing.php:39
HashRing\$liveRing
HashRing null $liveRing
Definition: HashRing.php:35
HashRing\$ring
Array $ring
(location => (start, end))
Definition: HashRing.php:32
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\$ejectionExpiries
Array $ejectionExpiries
(location => UNIX timestamp)
Definition: HashRing.php:37
$hashes
$hashes
Definition: testCompression.php:64
HashRing\RING_SIZE
const RING_SIZE
Definition: HashRing.php:41
HashRing
Convenience class for weighted consistent hash rings.
Definition: HashRing.php:28
HashRing\getLiveLocation
getLiveLocation( $item)
Get the location of an item on the "live" ring.
Definition: HashRing.php:213
array
the array() calling protocol came about after MediaWiki 1.4rc1.
HashRing\newWithoutLocation
newWithoutLocation( $location)
Get a new hash ring with a location removed from the ring.
Definition: HashRing.php:144