MediaWiki  1.28.0
HashRing.php
Go to the documentation of this file.
1 <?php
29 class HashRing {
31  protected $sourceMap = [];
33  protected $ring = [];
34 
36  protected $liveRing;
38  protected $ejectionExpiries = [];
40  protected $ejectionNextExpiry = INF;
41 
42  const RING_SIZE = 268435456; // 2^28
43 
47  public function __construct( array $map ) {
48  $map = array_filter( $map, function ( $w ) {
49  return $w > 0;
50  } );
51  if ( !count( $map ) ) {
52  throw new UnexpectedValueException( "Ring is empty or all weights are zero." );
53  }
54  $this->sourceMap = $map;
55  // Sort the locations based on the hash of their names
56  $hashes = [];
57  foreach ( $map as $location => $weight ) {
58  $hashes[$location] = sha1( $location );
59  }
60  uksort( $map, function ( $a, $b ) use ( $hashes ) {
61  return strcmp( $hashes[$a], $hashes[$b] );
62  } );
63  // Fit the map to weight-proportionate one with a space of size RING_SIZE
64  $sum = array_sum( $map );
65  $standardMap = [];
66  foreach ( $map as $location => $weight ) {
67  $standardMap[$location] = (int)floor( $weight / $sum * self::RING_SIZE );
68  }
69  // Build a ring of RING_SIZE spots, with each location at a spot in location hash order
70  $index = 0;
71  foreach ( $standardMap as $location => $weight ) {
72  // Location covers half-closed interval [$index,$index + $weight)
73  $this->ring[$location] = [ $index, $index + $weight ];
74  $index += $weight;
75  }
76  // Make sure the last location covers what is left
77  end( $this->ring );
78  $this->ring[key( $this->ring )][1] = self::RING_SIZE;
79  }
80 
87  public function getLocation( $item ) {
88  $locations = $this->getLocations( $item, 1 );
89 
90  return $locations[0];
91  }
92 
100  public function getLocations( $item, $limit ) {
101  $locations = [];
102  $primaryLocation = null;
103  $spot = hexdec( substr( sha1( $item ), 0, 7 ) ); // first 28 bits
104  foreach ( $this->ring as $location => $range ) {
105  if ( count( $locations ) >= $limit ) {
106  break;
107  }
108  // The $primaryLocation is the location the item spot is in.
109  // After that is reached, keep appending the next locations.
110  if ( ( $range[0] <= $spot && $spot < $range[1] ) || $primaryLocation !== null ) {
111  if ( $primaryLocation === null ) {
112  $primaryLocation = $location;
113  }
114  $locations[] = $location;
115  }
116  }
117  // If more locations are requested, wrap-around and keep adding them
118  reset( $this->ring );
119  while ( count( $locations ) < $limit ) {
120  list( $location, ) = each( $this->ring );
121  if ( $location === $primaryLocation ) {
122  break; // don't go in circles
123  }
124  $locations[] = $location;
125  }
126 
127  return $locations;
128  }
129 
135  public function getLocationWeights() {
136  return $this->sourceMap;
137  }
138 
145  public function newWithoutLocation( $location ) {
146  $map = $this->sourceMap;
147  unset( $map[$location] );
148 
149  return count( $map ) ? new self( $map ) : false;
150  }
151 
159  public function ejectFromLiveRing( $location, $ttl ) {
160  if ( !isset( $this->sourceMap[$location] ) ) {
161  throw new UnexpectedValueException( "No location '$location' in the ring." );
162  }
163  $expiry = time() + $ttl;
164  $this->liveRing = null; // stale
165  $this->ejectionExpiries[$location] = $expiry;
166  $this->ejectionNextExpiry = min( $expiry, $this->ejectionNextExpiry );
167 
168  return ( count( $this->ejectionExpiries ) < count( $this->sourceMap ) );
169  }
170 
177  public function getLiveRing() {
178  $now = time();
179  if ( $this->liveRing === null || $this->ejectionNextExpiry <= $now ) {
180  $this->ejectionExpiries = array_filter(
181  $this->ejectionExpiries,
182  function( $expiry ) use ( $now ) {
183  return ( $expiry > $now );
184  }
185  );
186  if ( count( $this->ejectionExpiries ) ) {
187  $map = array_diff_key( $this->sourceMap, $this->ejectionExpiries );
188  $this->liveRing = count( $map ) ? new self( $map ) : false;
189 
190  $this->ejectionNextExpiry = min( $this->ejectionExpiries );
191  } else { // common case; avoid recalculating ring
192  $this->liveRing = clone $this;
193  $this->liveRing->ejectionExpiries = [];
194  $this->liveRing->ejectionNextExpiry = INF;
195  $this->liveRing->liveRing = null;
196 
197  $this->ejectionNextExpiry = INF;
198  }
199  }
200  if ( !$this->liveRing ) {
201  throw new UnexpectedValueException( "The live ring is currently empty." );
202  }
203 
204  return $this->liveRing;
205  }
206 
214  public function getLiveLocation( $item ) {
215  return $this->getLiveRing()->getLocation( $item );
216  }
217 
226  public function getLiveLocations( $item, $limit ) {
227  return $this->getLiveRing()->getLocations( $item, $limit );
228  }
229 
236  public function getLiveLocationWeights() {
237  return $this->getLiveRing()->getLocationWeights();
238  }
239 }
getLiveLocations($item, $limit)
Get the location of an item on the "live" ring, as well as the next locations.
Definition: HashRing.php:226
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
the array() calling protocol came about after MediaWiki 1.4rc1.
Array $liveRing
(location => (start, end))
Definition: HashRing.php:36
Array $ring
(location => (start, end))
Definition: HashRing.php:33
getLocation($item)
Get the location of an item on the ring.
Definition: HashRing.php:87
Apache License January AND DISTRIBUTION Definitions License shall mean the terms and conditions for use
Array $sourceMap
(location => weight)
Definition: HashRing.php:31
getLocationWeights()
Get the map of locations to weight (ignores 0-weight items)
Definition: HashRing.php:135
getLiveLocationWeights()
Get the map of "live" locations to weight (ignores 0-weight items)
Definition: HashRing.php:236
Convenience class for weighted consistent hash rings.
Definition: HashRing.php:29
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
ejectFromLiveRing($location, $ttl)
Remove a location from the "live" hash ring.
Definition: HashRing.php:159
getLiveRing()
Get the "live" hash ring (which does not include ejected locations)
Definition: HashRing.php:177
getLocations($item, $limit)
Get the location of an item on the ring, as well as the next locations.
Definition: HashRing.php:100
newWithoutLocation($location)
Get a new hash ring with a location removed from the ring.
Definition: HashRing.php:145
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
Array $ejectionExpiries
(location => UNIX timestamp)
Definition: HashRing.php:38
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
integer $ejectionNextExpiry
UNIX timestamp.
Definition: HashRing.php:40
__construct(array $map)
Definition: HashRing.php:47
this hook is for auditing only RecentChangesLinked and Watchlist RecentChangesLinked and Watchlist e g Watchlist removed from all revisions and log entries to which it was applied This gives extensions a chance to take it off their books as the deletion has already been partly carried out by this point or something similar the user will be unable to create the tag set and then return false from the hook function Ensure you consume the ChangeTagAfterDelete hook to carry out custom deletion actions as context called by AbstractContent::getParserOutput May be used to override the normal model specific rendering of page content as context as context the output can only depend on parameters provided to this hook not on global state indicating whether full HTML should be generated If generation of HTML may be but other information should still be present in the ParserOutput object to manipulate or replace but no entry for that model exists in $wgContentHandlers if desired whether it is OK to use $contentModel on $title Handler functions that modify $ok should generally return false to prevent further hooks from further modifying $ok inclusive $limit
Definition: hooks.txt:1046
getLiveLocation($item)
Get the location of an item on the "live" ring.
Definition: HashRing.php:214
const RING_SIZE
Definition: HashRing.php:42