HashRing::getLiveLocations() - Code Metrics - wikimedia/mediawiki - Measure and Improve Code Quality continuously with Scrutinizer

HashRing::getLiveLocations() A
last analyzed 2016-11-13 17:42 UTC

↳ Parent: HashRing

Complexity

Conditions	1
Paths	1

Size

Total Lines	3
Code Lines	2

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	1
eloc	2
nc	1
nop	2
dl	0
loc	3
rs	10
c	0
b	0
f	0

<?php
/**
 * Convenience class for weighted consistent hash rings.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 * http://www.gnu.org/copyleft/gpl.html
 *
 * @file
 * @author Aaron Schulz
 */

/**
 * Convenience class for weighted consistent hash rings
 *
 * @since 1.22
 */
class HashRing {
	/** @var Array (location => weight) */
	protected $sourceMap = [];
	/** @var Array (location => (start, end)) */
	protected $ring = [];

	/** @var Array (location => (start, end)) */
	protected $liveRing;
	/** @var Array (location => UNIX timestamp) */
	protected $ejectionExpiries = [];
	/** @var integer UNIX timestamp */
	protected $ejectionNextExpiry = INF;

	const RING_SIZE = 268435456; // 2^28

	/**
	 * @param array $map (location => weight)
	 */
	public function __construct( array $map ) {
		$map = array_filter( $map, function ( $w ) {
			return $w > 0;
		} );
		if ( !count( $map ) ) {
			throw new UnexpectedValueException( "Ring is empty or all weights are zero." );
		}
		$this->sourceMap = $map;
		// Sort the locations based on the hash of their names
		$hashes = [];
		foreach ( $map as $location => $weight ) {
			$hashes[$location] = sha1( $location );
		}
		uksort( $map, function ( $a, $b ) use ( $hashes ) {
			return strcmp( $hashes[$a], $hashes[$b] );
		} );
		// Fit the map to weight-proportionate one with a space of size RING_SIZE
		$sum = array_sum( $map );
		$standardMap = [];
		foreach ( $map as $location => $weight ) {
			$standardMap[$location] = (int)floor( $weight / $sum * self::RING_SIZE );
		}
		// Build a ring of RING_SIZE spots, with each location at a spot in location hash order
		$index = 0;
		foreach ( $standardMap as $location => $weight ) {
			// Location covers half-closed interval [$index,$index + $weight)
			$this->ring[$location] = [ $index, $index + $weight ];
			$index += $weight;
		}
		// Make sure the last location covers what is left
		end( $this->ring );
		$this->ring[key( $this->ring )][1] = self::RING_SIZE;
	}

	/**
	 * Get the location of an item on the ring
	 *
	 * @param string $item
	 * @return string Location
	 */
	public function getLocation( $item ) {
		$locations = $this->getLocations( $item, 1 );

		return $locations[0];
	}

	/**
	 * Get the location of an item on the ring, as well as the next locations
	 *
	 * @param string $item
	 * @param integer $limit Maximum number of locations to return
	 * @return array List of locations
	 */
	public function getLocations( $item, $limit ) {
		$locations = [];
		$primaryLocation = null;
		$spot = hexdec( substr( sha1( $item ), 0, 7 ) ); // first 28 bits
		foreach ( $this->ring as $location => $range ) {
			if ( count( $locations ) >= $limit ) {
				break;
			}
			// The $primaryLocation is the location the item spot is in.
			// After that is reached, keep appending the next locations.
			if ( ( $range[0] <= $spot && $spot < $range[1] ) || $primaryLocation !== null ) {
				if ( $primaryLocation === null ) {
					$primaryLocation = $location;
				}
				$locations[] = $location;
			}
		}
		// If more locations are requested, wrap-around and keep adding them
		reset( $this->ring );
		while ( count( $locations ) < $limit ) {
			list( $location, ) = each( $this->ring );
			if ( $location === $primaryLocation ) {
				break; // don't go in circles
			}
			$locations[] = $location;
		}

		return $locations;
	}

	/**
	 * Get the map of locations to weight (ignores 0-weight items)
	 *
	 * @return array
	 */
	public function getLocationWeights() {
		return $this->sourceMap;
	}

	/**
	 * Get a new hash ring with a location removed from the ring
	 *
	 * @param string $location
	 * @return HashRing|bool Returns false if no non-zero weighted spots are left
	 */
	public function newWithoutLocation( $location ) {
		$map = $this->sourceMap;
		unset( $map[$location] );

		return count( $map ) ? new self( $map ) : false;
	}

	/**
	 * Remove a location from the "live" hash ring
	 *
	 * @param string $location
	 * @param integer $ttl Seconds
	 * @return bool Whether some non-ejected locations are left
	 */
	public function ejectFromLiveRing( $location, $ttl ) {
		if ( !isset( $this->sourceMap[$location] ) ) {
			throw new UnexpectedValueException( "No location '$location' in the ring." );
		}
		$expiry = time() + $ttl;
		$this->liveRing = null; // stale

		$this->ejectionExpiries[$location] = $expiry;
		$this->ejectionNextExpiry = min( $expiry, $this->ejectionNextExpiry );

		return ( count( $this->ejectionExpiries ) < count( $this->sourceMap ) );
	}

	/**
	 * Get the "live" hash ring (which does not include ejected locations)
	 *
	 * @return HashRing
	 * @throws UnexpectedValueException
	 */
	public function getLiveRing() {
		$now = time();
		if ( $this->liveRing === null || $this->ejectionNextExpiry <= $now ) {
			$this->ejectionExpiries = array_filter(
				$this->ejectionExpiries,
				function( $expiry ) use ( $now ) {
					return ( $expiry > $now );
				}
			);
			if ( count( $this->ejectionExpiries ) ) {
				$map = array_diff_key( $this->sourceMap, $this->ejectionExpiries );
				$this->liveRing = count( $map ) ? new self( $map ) : false;


				$this->ejectionNextExpiry = min( $this->ejectionExpiries );
			} else { // common case; avoid recalculating ring
				$this->liveRing = clone $this;

				$this->liveRing->ejectionExpiries = [];
				$this->liveRing->ejectionNextExpiry = INF;
				$this->liveRing->liveRing = null;


				$this->ejectionNextExpiry = INF;
			}
		}
		if ( !$this->liveRing ) {
			throw new UnexpectedValueException( "The live ring is currently empty." );
		}

		return $this->liveRing;
	}

	/**
	 * Get the location of an item on the "live" ring
	 *
	 * @param string $item
	 * @return string Location
	 * @throws UnexpectedValueException
	 */
	public function getLiveLocation( $item ) {
		return $this->getLiveRing()->getLocation( $item );
	}

	/**
	 * Get the location of an item on the "live" ring, as well as the next locations
	 *
	 * @param string $item
	 * @param integer $limit Maximum number of locations to return
	 * @return array List of locations
	 * @throws UnexpectedValueException
	 */
	public function getLiveLocations( $item, $limit ) {
		return $this->getLiveRing()->getLocations( $item, $limit );
	}

	/**
	 * Get the map of "live" locations to weight (ignores 0-weight items)
	 *
	 * @return array
	 * @throws UnexpectedValueException
	 */
	public function getLiveLocationWeights() {
		return $this->getLiveRing()->getLocationWeights();
	}
}


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 = [];
32			/** @var Array (location => (start, end)) */
33			protected $ring = [];
34
35			/** @var Array (location => (start, end)) */
36			protected $liveRing;
37			/** @var Array (location => UNIX timestamp) */
38			protected $ejectionExpiries = [];
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 = [];
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 = [];
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] = [ $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 = [];
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
			0 ignored issues – show Documentation Bug introduced 2016-01-16 18:00 UTC by Report Bug Copy Issue Report It seems like `null` of type `null` is incompatible with the declared type `array` of property `$liveRing`. Our type inference engine has found an assignment to a property that is incompatible with the declared type of that property. Either this assignment is in error or the assigned type should be added to the documentation/type hint for that property.. Loading history...
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;
			0 ignored issues – show Documentation Bug introduced 2016-01-16 18:00 UTC by Report Bug Copy Issue Report It seems like `count($map) ? new self($map) : false` of type `object<HashRing>` or `false` is incompatible with the declared type `array` of property `$liveRing`. Our type inference engine has found an assignment to a property that is incompatible with the declared type of that property. Either this assignment is in error or the assigned type should be added to the documentation/type hint for that property.. Loading history...
189
190			$this->ejectionNextExpiry = min( $this->ejectionExpiries );
191			} else { // common case; avoid recalculating ring
192			$this->liveRing = clone $this;
			0 ignored issues – show Documentation Bug introduced 2016-01-16 18:00 UTC by Report Bug Copy Issue Report It seems like `clone $this` of type `this<HashRing>` is incompatible with the declared type `array` of property `$liveRing`. Our type inference engine has found an assignment to a property that is incompatible with the declared type of that property. Either this assignment is in error or the assigned type should be added to the documentation/type hint for that property.. Loading history...
193			$this->liveRing->ejectionExpiries = [];
194			$this->liveRing->ejectionNextExpiry = INF;
195			$this->liveRing->liveRing = null;
			0 ignored issues – show Documentation Bug introduced 2016-01-16 18:00 UTC by Report Bug Copy Issue Report It seems like `null` of type `null` is incompatible with the declared type `array` of property `$liveRing`. Our type inference engine has found an assignment to a property that is incompatible with the declared type of that property. Either this assignment is in error or the assigned type should be added to the documentation/type hint for that property.. Loading history...
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, $limit ) {
227			return $this->getLiveRing()->getLocations( $item, $limit );
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			}
240

wikimedia / mediawiki

HashRing::getLiveLocations() A last analyzed 2016-11-13 17:42 UTC

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like

HashRing::getLiveLocations() A
last analyzed 2016-11-13 17:42 UTC