3 * Convenience class for weighted consistent hash rings.
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.
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.
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
21 * @author Aaron Schulz
25 * Convenience class for weighted consistent hash rings
30 /** @var Array (location => weight) */
31 protected $sourceMap = array();
32 /** @var Array (location => (start, end)) */
33 protected $ring = array();
35 const RING_SIZE
= 268435456; // 2^28
38 * @param array $map (location => weight)
40 public function __construct( array $map ) {
41 $map = array_filter( $map, function ( $w ) {
44 if ( !count( $map ) ) {
45 throw new UnexpectedValueException( "Ring is empty or all weights are zero." );
47 $this->sourceMap
= $map;
48 // Sort the locations based on the hash of their names
50 foreach ( $map as $location => $weight ) {
51 $hashes[$location] = sha1( $location );
53 uksort( $map, function ( $a, $b ) use ( $hashes ) {
54 return strcmp( $hashes[$a], $hashes[$b] );
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
);
62 // Build a ring of RING_SIZE spots, with each location at a spot in location hash order
64 foreach ( $standardMap as $location => $weight ) {
65 // Location covers half-closed interval [$index,$index + $weight)
66 $this->ring
[$location] = array( $index, $index +
$weight );
69 // Make sure the last location covers what is left
71 $this->ring
[key( $this->ring
)][1] = self
::RING_SIZE
;
75 * Get the location of an item on the ring
78 * @return string Location
80 public function getLocation( $item ) {
81 $locations = $this->getLocations( $item, 1 );
87 * Get the location of an item on the ring, as well as the next clockwise locations
90 * @param integer $limit Maximum number of locations to return
91 * @return array List of locations
93 public function getLocations( $item, $limit ) {
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 ) {
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;
107 $locations[] = $location;
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
117 $locations[] = $location;
124 * Get the map of locations to weight (ignores 0-weight items)
128 public function getLocationWeights() {
129 return $this->sourceMap
;
133 * Get a new hash ring with a location removed from the ring
135 * @param string $location
136 * @return HashRing|bool Returns false if no non-zero weighted spots are left
138 public function newWithoutLocation( $location ) {
139 $map = $this->sourceMap
;
140 unset( $map[$location] );
141 if ( count( $map ) ) {
142 return new self( $map );