MediaWiki  REL1_31
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  final 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  $location = key( $this->ring );
120  if ( $location === $primaryLocation ) {
121  break; // don't go in circles
122  }
123  $locations[] = $location;
124  next( $this->ring );
125  }
126 
127  return $locations;
128  }
129 
135  public function getLocationWeights() {
136  return $this->sourceMap;
137  }
138 
146  public function ejectFromLiveRing( $location, $ttl ) {
147  if ( !isset( $this->sourceMap[$location] ) ) {
148  throw new UnexpectedValueException( "No location '$location' in the ring." );
149  }
150  $expiry = time() + $ttl;
151  $this->liveRing = null; // stale
152  $this->ejectionExpiries[$location] = $expiry;
153  $this->ejectionNextExpiry = min( $expiry, $this->ejectionNextExpiry );
154 
155  return ( count( $this->ejectionExpiries ) < count( $this->sourceMap ) );
156  }
157 
164  protected function getLiveRing() {
165  $now = time();
166  if ( $this->liveRing === null || $this->ejectionNextExpiry <= $now ) {
167  $this->ejectionExpiries = array_filter(
168  $this->ejectionExpiries,
169  function ( $expiry ) use ( $now ) {
170  return ( $expiry > $now );
171  }
172  );
173  if ( count( $this->ejectionExpiries ) ) {
174  $map = array_diff_key( $this->sourceMap, $this->ejectionExpiries );
175  $this->liveRing = count( $map ) ? new self( $map ) : false;
176 
177  $this->ejectionNextExpiry = min( $this->ejectionExpiries );
178  } else { // common case; avoid recalculating ring
179  $this->liveRing = clone $this;
180  $this->liveRing->ejectionExpiries = [];
181  $this->liveRing->ejectionNextExpiry = INF;
182  $this->liveRing->liveRing = null;
183 
184  $this->ejectionNextExpiry = INF;
185  }
186  }
187  if ( !$this->liveRing ) {
188  throw new UnexpectedValueException( "The live ring is currently empty." );
189  }
190 
191  return $this->liveRing;
192  }
193 
201  public function getLiveLocation( $item ) {
202  return $this->getLiveRing()->getLocation( $item );
203  }
204 
213  public function getLiveLocations( $item, $limit ) {
214  return $this->getLiveRing()->getLocations( $item, $limit );
215  }
216 
223  public function getLiveLocationWeights() {
224  return $this->getLiveRing()->getLocationWeights();
225  }
226 }
use
Apache License January AND DISTRIBUTION Definitions License shall mean the terms and conditions for use
Definition: APACHE-LICENSE-2.0.txt:10
HashRing\getLocations
getLocations( $item, $limit)
Get the location of an item on the ring, as well as the next locations.
Definition: HashRing.php:99
array
the array() calling protocol came about after MediaWiki 1.4rc1.
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:223
HashRing\getLiveRing
getLiveRing()
Get the "live" hash ring (which does not include ejected locations)
Definition: HashRing.php:164
HashRing\ejectFromLiveRing
ejectFromLiveRing( $location, $ttl)
Remove a location from the "live" hash ring.
Definition: HashRing.php:146
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:37
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:26
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:135
HashRing\$sourceMap
array $sourceMap
(location => weight)
Definition: HashRing.php:30
HashRing\$ring
array $ring
(location => (start, end))
Definition: HashRing.php:32
HashRing\getLiveLocations
getLiveLocations( $item, $limit)
Get the location of an item on the "live" ring, as well as the next locations.
Definition: HashRing.php:213
HashRing\$ejectionExpiries
array $ejectionExpiries
(location => UNIX timestamp)
Definition: HashRing.php:37
HashRing\$ejectionNextExpiry
int $ejectionNextExpiry
UNIX timestamp.
Definition: HashRing.php:39
HashRing\$liveRing
HashRing null $liveRing
Definition: HashRing.php:35
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:22
$hashes
$hashes
Definition: testCompression.php:66
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:201