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         const RING_SIZE = 268435456; // 2^28
  36
  37         /**
  38          * @param array $map (location => weight)
  39          */
  40         public function __construct( array $map ) {
  41                 $map = array_filter( $map, function ( $w ) {
  42                         return $w > 0;
  43                 } );
  44                 if ( !count( $map ) ) {
  45                         throw new UnexpectedValueException( "Ring is empty or all weights are zero." );
  46                 }
  47                 $this->sourceMap = $map;
  48                 // Sort the locations based on the hash of their names
  49                 $hashes = array();
  50                 foreach ( $map as $location => $weight ) {
  51                         $hashes[$location] = sha1( $location );
  52                 }
  53                 uksort( $map, function ( $a, $b ) use ( $hashes ) {
  54                         return strcmp( $hashes[$a], $hashes[$b] );
  55                 } );
  56                 // Fit the map to weight-proportionate one with a space of size RING_SIZE
  57                 $sum = array_sum( $map );
  58                 $standardMap = array();
  59                 foreach ( $map as $location => $weight ) {
  60                         $standardMap[$location] = (int)floor( $weight / $sum * self::RING_SIZE );
  61                 }
  62                 // Build a ring of RING_SIZE spots, with each location at a spot in location hash order
  63                 $index = 0;
  64                 foreach ( $standardMap as $location => $weight ) {
  65                         // Location covers half-closed interval [$index,$index + $weight)
  66                         $this->ring[$location] = array( $index, $index + $weight );
  67                         $index += $weight;
  68                 }
  69                 // Make sure the last location covers what is left
  70                 end( $this->ring );
  71                 $this->ring[key( $this->ring )][1] = self::RING_SIZE;
  72         }
  73
  74         /**
  75          * Get the location of an item on the ring
  76          *
  77          * @param string $item
  78          * @return string Location
  79          */
  80         public function getLocation( $item ) {
  81                 $locations = $this->getLocations( $item, 1 );
  82
  83                 return $locations[0];
  84         }
  85
  86         /**
  87          * Get the location of an item on the ring, as well as the next clockwise locations
  88          *
  89          * @param string $item
  90          * @param integer $limit Maximum number of locations to return
  91          * @return array List of locations
  92          */
  93         public function getLocations( $item, $limit ) {
  94                 $locations = array();
  95                 $primaryLocation = null;
  96                 $spot = hexdec( substr( sha1( $item ), 0, 7 ) ); // first 28 bits
  97                 foreach ( $this->ring as $location => $range ) {
  98                         if ( count( $locations ) >= $limit ) {
  99                                 break;
 100                         }
 101                         // The $primaryLocation is the location the item spot is in.
 102                         // After that is reached, keep appending the next locations.
 103                         if ( ( $range[0] <= $spot && $spot < $range[1] ) || $primaryLocation !== null ) {
 104                                 if ( $primaryLocation === null ) {
 105                                         $primaryLocation = $location;
 106                                 }
 107                                 $locations[] = $location;
 108                         }
 109                 }
 110                 // If more locations are requested, wrap-around and keep adding them
 111                 reset( $this->ring );
 112                 while ( count( $locations ) < $limit ) {
 113                         list( $location, ) = each( $this->ring );
 114                         if ( $location === $primaryLocation ) {
 115                                 break; // don't go in circles
 116                         }
 117                         $locations[] = $location;
 118                 }
 119
 120                 return $locations;
 121         }
 122
 123         /**
 124          * Get the map of locations to weight (ignores 0-weight items)
 125          *
 126          * @return array
 127          */
 128         public function getLocationWeights() {
 129                 return $this->sourceMap;
 130         }
 131
 132         /**
 133          * Get a new hash ring with a location removed from the ring
 134          *
 135          * @param string $location
 136          * @return HashRing|bool Returns false if no non-zero weighted spots are left
 137          */
 138         public function newWithoutLocation( $location ) {
 139                 $map = $this->sourceMap;
 140                 unset( $map[$location] );
 141                 if ( count( $map ) ) {
 142                         return new self( $map );
 143                 }
 144
 145                 return false;
 146         }
 147 }