includes/libs/HashRing.php

   1 <?php
   2 /**
   3  * Convenience class for weighted consistent hash rings.
   4  *
   5  * This program is free software; you can redistribute it and/or modify
   6  * it under the terms of the GNU General Public License as published by
   7  * the Free Software Foundation; either version 2 of the License, or
   8  * (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License along
  16  * with this program; if not, write to the Free Software Foundation, Inc.,
  17  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  18  * http://www.gnu.org/copyleft/gpl.html
  19  *
  20  * @file
  21  */
  22
  23 /**
  24  * Convenience class for weighted consistent hash rings
  25  *
  26  * This deterministically maps "keys" to a set of "locations" while avoiding clumping
  27  *
  28  * Each location is represented by a number of nodes on a ring proportionate to the ratio
  29  * of its weight compared to the total location weight. Note positions are deterministically
  30  * derived from the hash of the location name. Nodes are responsible for the portion of the
  31  * ring, counter-clockwise, up until the next node. Locations are responsible for all portions
  32  * of the ring that the location's nodes are responsible for.
  33  *
  34  * A location that is temporarily "ejected" is said to be absent from the "live" ring.
  35  * If no location ejections are active, then the base ring and live ring are identical.
  36  *
  37  * @since 1.22
  38  */
  39 class HashRing implements Serializable {
  40         /** @var string Hashing algorithm for hash() */
  41         protected $algo;
  42         /** @var int[] Non-empty (location => integer weight) */
  43         protected $weightByLocation;
  44         /** @var int[] Map of (location => UNIX timestamp) */
  45         protected $ejectExpiryByLocation;
  46
  47         /** @var array[] Non-empty position-ordered list of (position, location name) */
  48         protected $baseRing;
  49         /** @var array[] Non-empty position-ordered list of (position, location name) */
  50         protected $liveRing;
  51
  52         /** @var float Number of positions on the ring */
  53         const RING_SIZE = 4294967296.0; // 2^32
  54         /** @var integer Overall number of node groups per server */
  55         const HASHES_PER_LOCATION = 40;
  56         /** @var integer Number of nodes in a node group */
  57         const SECTORS_PER_HASH = 4;
  58
  59         const KEY_POS = 0;
  60         const KEY_LOCATION = 1;
  61
  62         /** @var int Consider all locations */
  63         const RING_ALL = 0;
  64         /** @var int Only consider "live" locations */
  65         const RING_LIVE = 1;
  66
  67         /**
  68          * Make a consistent hash ring given a set of locations and their weight values
  69          *
  70          * @param int[] $map Map of (location => weight)
  71          * @param string $algo Hashing algorithm listed in hash_algos() [optional]
  72          * @param int[] $ejections Map of (location => UNIX timestamp) for ejection expiries
  73          * @since 1.31
  74          */
  75         public function __construct( array $map, $algo = 'sha1', array $ejections = [] ) {
  76                 $this->init( $map, $algo, $ejections );
  77         }
  78
  79         /**
  80          * @param int[] $map Map of (location => integer)
  81          * @param string $algo Hashing algorithm
  82          * @param int[] $ejections Map of (location => UNIX timestamp) for ejection expires
  83          */
  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 );
 100         }
 101
 102         /**
 103          * Get the location of an item on the ring
 104          *
 105          * @param string $item
 106          * @return string Location
 107          * @throws UnexpectedValueException
 108          */
 109         final public function getLocation( $item ) {
 110                 return $this->getLocations( $item, 1 )[0];
 111         }
 112
 113         /**
 114          * Get the location of an item on the ring followed by the next ring locations
 115          *
 116          * @param string $item
 117          * @param int $limit Maximum number of locations to return
 118          * @param int $from One of the RING_* class constants
 119          * @return string[] List of locations
 120          * @throws InvalidArgumentException
 121          * @throws UnexpectedValueException
 122          */
 123         public function getLocations( $item, $limit, $from = self::RING_ALL ) {
 124                 if ( $from === self::RING_ALL ) {
 125                         $ring = $this->baseRing;
 126                 } elseif ( $from === self::RING_LIVE ) {
 127                         $ring = $this->getLiveRing();
 128                 } else {
 129                         throw new InvalidArgumentException( "Invalid ring source specified." );
 130                 }
 131
 132                 // Short-circuit for the common single-location case. Note that if there was only one
 133                 // location and it was ejected from the live ring, getLiveRing() would have error out.
 134                 if ( count( $this->weightByLocation ) == 1 ) {
 135                         return ( $limit > 0 ) ? [ $ring[0][self::KEY_LOCATION] ] : [];
 136                 }
 137
 138                 // Locate the node index for this item's position on the hash ring
 139                 $itemIndex = $this->findNodeIndexForPosition( $this->getItemPosition( $item ), $ring );
 140
 141                 $locations = [];
 142                 $currentIndex = null;
 143                 while ( count( $locations ) < $limit ) {
 144                         if ( $currentIndex === null ) {
 145                                 $currentIndex = $itemIndex;
 146                         } else {
 147                                 $currentIndex = $this->getNextClockwiseNodeIndex( $currentIndex, $ring );
 148                                 if ( $currentIndex === $itemIndex ) {
 149                                         break; // all nodes visited
 150                                 }
 151                         }
 152                         $nodeLocation = $ring[$currentIndex][self::KEY_LOCATION];
 153                         if ( !in_array( $nodeLocation, $locations, true ) ) {
 154                                 // Ignore other nodes for the same locations already added
 155                                 $locations[] = $nodeLocation;
 156                         }
 157                 }
 158
 159                 return $locations;
 160         }
 161
 162         /**
 163          * @param float $position
 164          * @param array[] $ring Either the base or live ring
 165          * @return int|null
 166          */
 167         private function findNodeIndexForPosition( $position, $ring ) {
 168                 $count = count( $ring );
 169                 if ( $count === 0 ) {
 170                         return null;
 171                 }
 172
 173                 $index = null;
 174                 $lowPos = 0;
 175                 $highPos = $count;
 176                 while ( true ) {
 177                         $midPos = (int)( ( $lowPos + $highPos ) / 2 );
 178                         if ( $midPos === $count ) {
 179                                 $index = 0;
 180                                 break;
 181                         }
 182
 183                         $midVal = $ring[$midPos][self::KEY_POS];
 184                         $midMinusOneVal = ( $midPos === 0 ) ? 0 : $ring[$midPos - 1][self::KEY_POS];
 185                         if ( $position <= $midVal && $position > $midMinusOneVal ) {
 186                                 $index = $midPos;
 187                                 break;
 188                         }
 189
 190                         if ( $midVal < $position ) {
 191                                 $lowPos = $midPos + 1;
 192                         } else {
 193                                 $highPos = $midPos - 1;
 194                         }
 195
 196                         if ( $lowPos > $highPos ) {
 197                                 $index = 0;
 198                                 break;
 199                         }
 200                 }
 201
 202                 return $index;
 203         }
 204
 205         /**
 206          * Get the map of locations to weight (does not include zero weight items)
 207          *
 208          * @return int[]
 209          */
 210         public function getLocationWeights() {
 211                 return $this->weightByLocation;
 212         }
 213
 214         /**
 215          * Remove a location from the "live" hash ring
 216          *
 217          * @param string $location
 218          * @param int $ttl Seconds
 219          * @return bool Whether some non-ejected locations are left
 220          * @throws UnexpectedValueException
 221          */
 222         public function ejectFromLiveRing( $location, $ttl ) {
 223                 if ( !isset( $this->weightByLocation[$location] ) ) {
 224                         throw new UnexpectedValueException( "No location '$location' in the ring." );
 225                 }
 226
 227                 $expiry = $this->getCurrentTime() + $ttl;
 228                 $this->ejectExpiryByLocation[$location] = $expiry;
 229
 230                 $this->liveRing = null; // invalidate ring cache
 231
 232                 return ( count( $this->ejectExpiryByLocation ) < count( $this->weightByLocation ) );
 233         }
 234
 235         /**
 236          * Get the location of an item on the "live" ring
 237          *
 238          * @param string $item
 239          * @return string Location
 240          * @throws UnexpectedValueException
 241          */
 242         final public function getLiveLocation( $item ) {
 243                 return $this->getLocations( $item, 1, self::RING_LIVE )[0];
 244         }
 245
 246         /**
 247          * Get the location of an item on the "live" ring, as well as the next locations
 248          *
 249          * @param string $item
 250          * @param int $limit Maximum number of locations to return
 251          * @return string[] List of locations
 252          * @throws UnexpectedValueException
 253          */
 254         final public function getLiveLocations( $item, $limit ) {
 255                 return $this->getLocations( $item, $limit, self::RING_LIVE );
 256         }
 257
 258         /**
 259          * Get the map of "live" locations to weight (does not include zero weight items)
 260          *
 261          * @return int[]
 262          * @throws UnexpectedValueException
 263          */
 264         public function getLiveLocationWeights() {
 265                 $now = $this->getCurrentTime();
 266
 267                 return array_diff_key(
 268                         $this->weightByLocation,
 269                         array_filter(
 270                                 $this->ejectExpiryByLocation,
 271                                 function ( $expiry ) use ( $now ) {
 272                                         return ( $expiry > $now );
 273                                 }
 274                         )
 275                 );
 276         }
 277
 278         /**
 279          * @param int[] $weightByLocation
 280          * @return array[]
 281          */
 282         private function buildLocationRing( array $weightByLocation ) {
 283                 $locationCount = count( $weightByLocation );
 284                 $totalWeight = array_sum( $weightByLocation );
 285
 286                 $ring = [];
 287                 // Assign nodes to all locations based on location weight
 288                 $claimed = []; // (position as string => (node, index))
 289                 foreach ( $weightByLocation as $location => $weight ) {
 290                         $ratio = $weight / $totalWeight;
 291                         // There $locationCount * (HASHES_PER_LOCATION * 4) nodes available;
 292                         // assign a few groups of nodes to this location based on its weight.
 293                         $nodesQuartets = intval( $ratio * self::HASHES_PER_LOCATION * $locationCount );
 294                         for ( $qi = 0; $qi < $nodesQuartets; ++$qi ) {
 295                                 // For efficiency, get 4 points per hash call and 4X node count.
 296                                 // If $algo is MD5, then this matches that of with libketama.
 297                                 // See https://github.com/RJ/ketama/blob/master/libketama/ketama.c
 298                                 $positions = $this->getNodePositionQuartet( "{$location}-{$qi}" );
 299                                 foreach ( $positions as $gi => $position ) {
 300                                         $node = ( $qi * self::SECTORS_PER_HASH + $gi ) . "@$location";
 301                                         $posKey = (string)$position; // large integer
 302                                         if ( isset( $claimed[$posKey] ) ) {
 303                                                 // Disallow duplicates for sanity (name decides precedence)
 304                                                 if ( $claimed[$posKey]['node'] > $node ) {
 305                                                         continue;
 306                                                 } else {
 307                                                         unset( $ring[$claimed[$posKey]['index']] );
 308                                                 }
 309                                         }
 310                                         $ring[] = [
 311                                                 self::KEY_POS => $position,
 312                                                 self::KEY_LOCATION => $location
 313                                         ];
 314                                         $claimed[$posKey] = [ 'node' => $node, 'index' => count( $ring ) - 1 ];
 315                                 }
 316                         }
 317                 }
 318                 // Sort the locations into clockwise order based on the hash ring position
 319                 usort( $ring, function ( $a, $b ) {
 320                         if ( $a[self::KEY_POS] === $b[self::KEY_POS] ) {
 321                                 throw new UnexpectedValueException( 'Duplicate node positions.' );
 322                         }
 323
 324                         return ( $a[self::KEY_POS] < $b[self::KEY_POS] ? -1 : 1 );
 325                 } );
 326
 327                 return $ring;
 328         }
 329
 330         /**
 331          * @param string $item Key
 332          * @return float Ring position; integral number in [0, self::RING_SIZE - 1]
 333          */
 334         private function getItemPosition( $item ) {
 335                 // If $algo is MD5, then this matches that of with libketama.
 336                 // See https://github.com/RJ/ketama/blob/master/libketama/ketama.c
 337                 $octets = substr( hash( $this->algo, (string)$item, true ), 0, 4 );
 338                 if ( strlen( $octets ) != 4 ) {
 339                         throw new UnexpectedValueException( __METHOD__ . ": {$this->algo} is < 32 bits." );
 340                 }
 341
 342                 $pos = unpack( 'V', $octets )[1];
 343                 if ( $pos < 0 ) {
 344                         // Most-significant-bit is set, causing unpack() to return a negative integer due
 345                         // to the fact that it returns a signed int. Cast it to an unsigned integer string.
 346                         $pos = sprintf( '%u', $pos );
 347                 }
 348
 349                 return (float)$pos;
 350         }
 351
 352         /**
 353          * @param string $nodeGroupName
 354          * @return float[] Four ring positions on [0, self::RING_SIZE - 1]
 355          */
 356         private function getNodePositionQuartet( $nodeGroupName ) {
 357                 $octets = substr( hash( $this->algo, (string)$nodeGroupName, true ), 0, 16 );
 358                 if ( strlen( $octets ) != 16 ) {
 359                         throw new UnexpectedValueException( __METHOD__ . ": {$this->algo} is < 128 bits." );
 360                 }
 361
 362                 $positions = [];
 363                 foreach ( unpack( 'V4', $octets ) as $signed ) {
 364                         $positions[] = (float)sprintf( '%u', $signed );
 365                 }
 366
 367                 return $positions;
 368         }
 369
 370         /**
 371          * @param int $i Valid index for a node in the ring
 372          * @param array[] $ring Either the base or live ring
 373          * @return int Valid index for a node in the ring
 374          */
 375         private function getNextClockwiseNodeIndex( $i, $ring ) {
 376                 if ( !isset( $ring[$i] ) ) {
 377                         throw new UnexpectedValueException( __METHOD__ . ": reference index is invalid." );
 378                 }
 379
 380                 $next = $i + 1;
 381
 382                 return ( $next < count( $ring ) ) ? $next : 0;
 383         }
 384
 385         /**
 386          * Get the "live" hash ring (which does not include ejected locations)
 387          *
 388          * @return array[]
 389          * @throws UnexpectedValueException
 390          */
 391         protected function getLiveRing() {
 392                 if ( !$this->ejectExpiryByLocation ) {
 393                         return $this->baseRing; // nothing ejected
 394                 }
 395
 396                 $now = $this->getCurrentTime();
 397
 398                 if ( $this->liveRing === null || min( $this->ejectExpiryByLocation ) <= $now ) {
 399                         // Live ring needs to be regerenated...
 400                         $this->ejectExpiryByLocation = array_filter(
 401                                 $this->ejectExpiryByLocation,
 402                                 function ( $expiry ) use ( $now ) {
 403                                         return ( $expiry > $now );
 404                                 }
 405                         );
 406
 407                         if ( count( $this->ejectExpiryByLocation ) ) {
 408                                 // Some locations are still ejected from the ring
 409                                 $liveRing = [];
 410                                 foreach ( $this->baseRing as $i => $nodeInfo ) {
 411                                         $location = $nodeInfo[self::KEY_LOCATION];
 412                                         if ( !isset( $this->ejectExpiryByLocation[$location] ) ) {
 413                                                 $liveRing[] = $nodeInfo;
 414                                         }
 415                                 }
 416                         } else {
 417                                 $liveRing = $this->baseRing;
 418                         }
 419
 420                         $this->liveRing = $liveRing;
 421                 }
 422
 423                 if ( !$this->liveRing ) {
 424                         throw new UnexpectedValueException( "The live ring is currently empty." );
 425                 }
 426
 427                 return $this->liveRing;
 428         }
 429
 430         /**
 431          * @return int UNIX timestamp
 432          */
 433         protected function getCurrentTime() {
 434                 return time();
 435         }
 436
 437         public function serialize() {
 438                 return serialize( [
 439                         'algorithm' => $this->algo,
 440                         'locations' => $this->weightByLocation,
 441                         'ejections' => $this->ejectExpiryByLocation
 442                 ] );
 443         }
 444
 445         public function unserialize( $serialized ) {
 446                 $data = unserialize( $serialized );
 447                 if ( is_array( $data ) ) {
 448                         $this->init( $data['locations'], $data['algorithm'], $data['ejections'] );
 449                 } else {
 450                         throw new UnexpectedValueException( __METHOD__ . ": unable to decode JSON." );
 451                 }
 452         }
 453 }