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  * @author Aaron Schulz
  22  */
  23
  24 /**
  25  * Convenience class for weighted consistent hash rings
  26  *
  27  * @since 1.22
  28  */
  29 class HashRing {
  30         /** @var Array (location => weight) */
  31         protected $sourceMap = array();
  32         /** @var Array (location => (start, end)) */
  33         protected $ring = array();
  34
  35         /** @var Array (location => (start, end)) */
  36         protected $liveRing;
  37         /** @var Array (location => UNIX timestamp) */
  38         protected $ejectionExpiries = array();
  39         /** @var integer UNIX timestamp */
  40         protected $ejectionNextExpiry = INF;
  41
  42         const RING_SIZE = 268435456; // 2^28
  43
  44         /**
  45          * @param array $map (location => weight)
  46          */
  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 = array();
  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 = array();
  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] = array( $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
  81         /**
  82          * Get the location of an item on the ring
  83          *
  84          * @param string $item
  85          * @return string Location
  86          */
  87         public function getLocation( $item ) {
  88                 $locations = $this->getLocations( $item, 1 );
  89
  90                 return $locations[0];
  91         }
  92
  93         /**
  94          * Get the location of an item on the ring, as well as the next locations
  95          *
  96          * @param string $item
  97          * @param integer $limit Maximum number of locations to return
  98          * @return array List of locations
  99          */
 100         public function getLocations( $item, $limit ) {
 101                 $locations = array();
 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
 130         /**
 131          * Get the map of locations to weight (ignores 0-weight items)
 132          *
 133          * @return array
 134          */
 135         public function getLocationWeights() {
 136                 return $this->sourceMap;
 137         }
 138
 139         /**
 140          * Get a new hash ring with a location removed from the ring
 141          *
 142          * @param string $location
 143          * @return HashRing|bool Returns false if no non-zero weighted spots are left
 144          */
 145         public function newWithoutLocation( $location ) {
 146                 $map = $this->sourceMap;
 147                 unset( $map[$location] );
 148
 149                 return count( $map ) ? new self( $map ) : false;
 150         }
 151
 152         /**
 153          * Remove a location from the "live" hash ring
 154          *
 155          * @param string $location
 156          * @param integer $ttl Seconds
 157          * @return bool Whether some non-ejected locations are left
 158          */
 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
 171         /**
 172          * Get the "live" hash ring (which does not include ejected locations)
 173          *
 174          * @return HashRing
 175          * @throws UnexpectedValueException
 176          */
 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 = array();
 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
 207         /**
 208          * Get the location of an item on the "live" ring
 209          *
 210          * @param string $item
 211          * @return string Location
 212          * @throws UnexpectedValueException
 213          */
 214         public function getLiveLocation( $item ) {
 215                 return $this->getLiveRing()->getLocation( $item );
 216         }
 217
 218         /**
 219          * Get the location of an item on the "live" ring, as well as the next locations
 220          *
 221          * @param string $item
 222          * @param integer $limit Maximum number of locations to return
 223          * @return array List of locations
 224          * @throws UnexpectedValueException
 225          */
 226         public function getLiveLocations( $item ) {
 227                 return $this->getLiveRing()->getLocations( $item );
 228         }
 229
 230         /**
 231          * Get the map of "live" locations to weight (ignores 0-weight items)
 232          *
 233          * @return array
 234          * @throws UnexpectedValueException
 235          */
 236         public function getLiveLocationWeights() {
 237                 return $this->getLiveRing()->getLocationWeights();
 238         }
 239 }