/** @var int[] Map of (location => UNIX timestamp) */
protected $ejectExpiryByLocation;
- /** @var array[] Non-empty list of (float, node name, location name) */
+ /** @var array[] Non-empty position-ordered list of (position, location name) */
protected $baseRing;
- /** @var array[] Non-empty list of (float, node name, location name) */
+ /** @var array[] Non-empty position-ordered list of (position, location name) */
protected $liveRing;
- /** @var int|null Number of nodes scanned to place an item last time */
- private $lastNodeScanSize;
-
/** @var float Number of positions on the ring */
const RING_SIZE = 4294967296.0; // 2^32
/** @var integer Overall number of node groups per server */
$this->algo = $algo;
$this->weightByLocation = $weightByLocation;
$this->ejectExpiryByLocation = $ejections;
- $this->baseRing = $this->buildLocationRing( $this->weightByLocation, $this->algo );
+ $this->baseRing = $this->buildLocationRing( $this->weightByLocation );
}
/**
}
/**
- * Get the location of an item on the ring, as well as the next locations
+ * Get the location of an item on the ring followed by the next ring locations
*
* @param string $item
* @param int $limit Maximum number of locations to return
* @param int $from One of the RING_* class constants
* @return string[] List of locations
+ * @throws InvalidArgumentException
* @throws UnexpectedValueException
*/
public function getLocations( $item, $limit, $from = self::RING_ALL ) {
throw new InvalidArgumentException( "Invalid ring source specified." );
}
- // Locate this item's position on the hash ring
- $position = $this->getItemPosition( $item );
-
- // Guess a nearby node based on the node list being ordered and the probabilistic
- // expected size of nodes being equal, varying less when with higher node counts
- $guessIndex = $this->guessNodeIndexForPosition( $position, $ring );
-
- // Find the index of the node within which this item resides
- $itemNodeIndex = $this->findNodeIndexForPosition( $position, $guessIndex, $ring );
- if ( $itemNodeIndex === null ) {
- throw new RuntimeException( __METHOD__ . ": no place for '$item' ($position)" );
+ // Short-circuit for the common single-location case. Note that if there was only one
+ // location and it was ejected from the live ring, getLiveRing() would have error out.
+ if ( count( $this->weightByLocation ) == 1 ) {
+ return ( $limit > 0 ) ? [ $ring[0][self::KEY_LOCATION] ] : [];
}
+ // Locate the node index for this item's position on the hash ring
+ $itemIndex = $this->findNodeIndexForPosition( $this->getItemPosition( $item ), $ring );
+
$locations = [];
- $currentIndex = $itemNodeIndex;
+ $currentIndex = null;
while ( count( $locations ) < $limit ) {
+ if ( $currentIndex === null ) {
+ $currentIndex = $itemIndex;
+ } else {
+ $currentIndex = $this->getNextClockwiseNodeIndex( $currentIndex, $ring );
+ if ( $currentIndex === $itemIndex ) {
+ break; // all nodes visited
+ }
+ }
$nodeLocation = $ring[$currentIndex][self::KEY_LOCATION];
if ( !in_array( $nodeLocation, $locations, true ) ) {
// Ignore other nodes for the same locations already added
$locations[] = $nodeLocation;
}
- $currentIndex = $this->getNextClockwiseNodeIndex( $currentIndex, $ring );
- if ( $currentIndex === $itemNodeIndex ) {
- break; // all nodes visited
- }
}
return $locations;
}
+ /**
+ * @param float $position
+ * @param array[] $ring Either the base or live ring
+ * @return int|null
+ */
+ private function findNodeIndexForPosition( $position, $ring ) {
+ $count = count( $ring );
+ if ( $count === 0 ) {
+ return null;
+ }
+
+ $index = null;
+ $lowPos = 0;
+ $highPos = $count;
+ while ( true ) {
+ $midPos = (int)( ( $lowPos + $highPos ) / 2 );
+ if ( $midPos === $count ) {
+ $index = 0;
+ break;
+ }
+
+ $midVal = $ring[$midPos][self::KEY_POS];
+ $midMinusOneVal = ( $midPos === 0 ) ? 0 : $ring[$midPos - 1][self::KEY_POS];
+ if ( $position <= $midVal && $position > $midMinusOneVal ) {
+ $index = $midPos;
+ break;
+ }
+
+ if ( $midVal < $position ) {
+ $lowPos = $midPos + 1;
+ } else {
+ $highPos = $midPos - 1;
+ }
+
+ if ( $lowPos > $highPos ) {
+ $index = 0;
+ break;
+ }
+ }
+
+ return $index;
+ }
+
/**
* Get the map of locations to weight (does not include zero weight items)
*
);
}
- /**
- * @param float $position
- * @param array[] $ring Either the base or live ring
- * @return int
- */
- private function guessNodeIndexForPosition( $position, $ring ) {
- $arcRatio = $position / self::RING_SIZE; // range is [0.0, 1.0)
- $maxIndex = count( $ring ) - 1;
- $guessIndex = intval( $maxIndex * $arcRatio );
-
- $displacement = $ring[$guessIndex][self::KEY_POS] - $position;
- $aveSize = self::RING_SIZE / count( $ring );
- $shift = intval( $displacement / $aveSize );
-
- $guessIndex -= $shift;
- if ( $guessIndex < 0 ) {
- $guessIndex = max( $maxIndex + $guessIndex, 0 ); // roll-over
- } elseif ( $guessIndex > $maxIndex ) {
- $guessIndex = min( $guessIndex - $maxIndex, 0 ); // roll-over
- }
-
- return $guessIndex;
- }
-
- /**
- * @param float $position
- * @param int $guessIndex Node index to start scanning
- * @param array[] $ring Either the base or live ring
- * @return int|null
- */
- private function findNodeIndexForPosition( $position, $guessIndex, $ring ) {
- $mainNodeIndex = null; // first matching node index
-
- $this->lastNodeScanSize = 0;
-
- if ( $ring[$guessIndex][self::KEY_POS] >= $position ) {
- // Walk the nodes counter-clockwise until reaching a node at/before $position
- do {
- $priorIndex = $guessIndex;
- $guessIndex = $this->getPrevClockwiseNodeIndex( $guessIndex, $ring );
- $nodePosition = $ring[$guessIndex][self::KEY_POS];
- if ( $nodePosition < $position || $guessIndex > $priorIndex ) {
- $mainNodeIndex = $priorIndex; // includes roll-over case
- } elseif ( $nodePosition === $position ) {
- $mainNodeIndex = $guessIndex;
- }
- ++$this->lastNodeScanSize;
- } while ( $mainNodeIndex === null );
- } else {
- // Walk the nodes clockwise until reaching a node at/after $position
- do {
- $priorIndex = $guessIndex;
- $guessIndex = $this->getNextClockwiseNodeIndex( $guessIndex, $ring );
- $nodePosition = $ring[$guessIndex][self::KEY_POS];
- if ( $nodePosition >= $position || $guessIndex < $priorIndex ) {
- $mainNodeIndex = $guessIndex; // includes roll-over case
- }
- ++$this->lastNodeScanSize;
- } while ( $mainNodeIndex === null );
- }
-
- return $mainNodeIndex;
- }
-
/**
* @param int[] $weightByLocation
- * @param string $algo Hashing algorithm
* @return array[]
*/
- private function buildLocationRing( array $weightByLocation, $algo ) {
+ private function buildLocationRing( array $weightByLocation ) {
$locationCount = count( $weightByLocation );
$totalWeight = array_sum( $weightByLocation );
throw new UnexpectedValueException( __METHOD__ . ": {$this->algo} is < 32 bits." );
}
- return (float)sprintf( '%u', unpack( 'V', $octets )[1] );
+ $pos = unpack( 'V', $octets )[1];
+ if ( $pos < 0 ) {
+ // Most-significant-bit is set, causing unpack() to return a negative integer due
+ // to the fact that it returns a signed int. Cast it to an unsigned integer string.
+ $pos = sprintf( '%u', $pos );
+ }
+
+ return (float)$pos;
}
/**
return ( $next < count( $ring ) ) ? $next : 0;
}
- /**
- * @param int $i Valid index for a node in the ring
- * @param array[] $ring Either the base or live ring
- * @return int Valid index for a node in the ring
- */
- private function getPrevClockwiseNodeIndex( $i, $ring ) {
- if ( !isset( $ring[$i] ) ) {
- throw new UnexpectedValueException( __METHOD__ . ": reference index is invalid." );
- }
-
- $prev = $i - 1;
-
- return ( $prev >= 0 ) ? $prev : count( $ring ) - 1;
- }
-
/**
* Get the "live" hash ring (which does not include ejected locations)
*
return time();
}
- /**
- * @return int|null
- */
- public function getLastNodeScanSize() {
- return $this->lastNodeScanSize;
- }
-
public function serialize() {
return serialize( [
'algorithm' => $this->algo,
dépôts / lhc / web / wiklou.git / blobdiff