[Summary view] [Print] [Text view]

   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  }