+ $now = $this->getCurrentTime();
+
+ return array_diff_key(
+ $this->weightByLocation,
+ array_filter(
+ $this->ejectExpiryByLocation,
+ function ( $expiry ) use ( $now ) {
+ return ( $expiry > $now );
+ }
+ )
+ );
+ }
+
+ /**
+ * @param int[] $weightByLocation
+ * @return array[]
+ */
+ private function buildLocationRing( array $weightByLocation ) {
+ $locationCount = count( $weightByLocation );
+ $totalWeight = array_sum( $weightByLocation );
+
+ $ring = [];
+ // Assign nodes to all locations based on location weight
+ $claimed = []; // (position as string => (node, index))
+ foreach ( $weightByLocation as $location => $weight ) {
+ $ratio = $weight / $totalWeight;
+ // There $locationCount * (HASHES_PER_LOCATION * 4) nodes available;
+ // assign a few groups of nodes to this location based on its weight.
+ $nodesQuartets = intval( $ratio * self::HASHES_PER_LOCATION * $locationCount );
+ for ( $qi = 0; $qi < $nodesQuartets; ++$qi ) {
+ // For efficiency, get 4 points per hash call and 4X node count.
+ // If $algo is MD5, then this matches that of with libketama.
+ // See https://github.com/RJ/ketama/blob/master/libketama/ketama.c
+ $positions = $this->getNodePositionQuartet( "{$location}-{$qi}" );
+ foreach ( $positions as $gi => $position ) {
+ $node = ( $qi * self::SECTORS_PER_HASH + $gi ) . "@$location";
+ $posKey = (string)$position; // large integer
+ if ( isset( $claimed[$posKey] ) ) {
+ // Disallow duplicates for sanity (name decides precedence)
+ if ( $claimed[$posKey]['node'] > $node ) {
+ continue;
+ } else {
+ unset( $ring[$claimed[$posKey]['index']] );
+ }
+ }
+ $ring[] = [
+ self::KEY_POS => $position,
+ self::KEY_LOCATION => $location
+ ];
+ $claimed[$posKey] = [ 'node' => $node, 'index' => count( $ring ) - 1 ];
+ }
+ }
+ }
+ // Sort the locations into clockwise order based on the hash ring position
+ usort( $ring, function ( $a, $b ) {
+ if ( $a[self::KEY_POS] === $b[self::KEY_POS] ) {
+ throw new UnexpectedValueException( 'Duplicate node positions.' );
+ }
+
+ return ( $a[self::KEY_POS] < $b[self::KEY_POS] ? -1 : 1 );
+ } );
+
+ return $ring;
+ }
+
+ /**
+ * @param string $item Key
+ * @return float Ring position; integral number in [0, self::RING_SIZE - 1]
+ */
+ private function getItemPosition( $item ) {
+ // If $algo is MD5, then this matches that of with libketama.
+ // See https://github.com/RJ/ketama/blob/master/libketama/ketama.c
+ $octets = substr( hash( $this->algo, (string)$item, true ), 0, 4 );
+ if ( strlen( $octets ) != 4 ) {
+ throw new UnexpectedValueException( __METHOD__ . ": {$this->algo} is < 32 bits." );
+ }
+
+ $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;
+ }
+
+ /**
+ * @param string $nodeGroupName
+ * @return float[] Four ring positions on [0, self::RING_SIZE - 1]
+ */
+ private function getNodePositionQuartet( $nodeGroupName ) {
+ $octets = substr( hash( $this->algo, (string)$nodeGroupName, true ), 0, 16 );
+ if ( strlen( $octets ) != 16 ) {
+ throw new UnexpectedValueException( __METHOD__ . ": {$this->algo} is < 128 bits." );
+ }
+
+ $positions = [];
+ foreach ( unpack( 'V4', $octets ) as $signed ) {
+ $positions[] = (float)sprintf( '%u', $signed );
+ }
+
+ return $positions;
+ }
+
+ /**
+ * @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 getNextClockwiseNodeIndex( $i, $ring ) {
+ if ( !isset( $ring[$i] ) ) {
+ throw new UnexpectedValueException( __METHOD__ . ": reference index is invalid." );
+ }
+
+ $next = $i + 1;
+
+ return ( $next < count( $ring ) ) ? $next : 0;
+ }
+
+ /**
+ * Get the "live" hash ring (which does not include ejected locations)
+ *
+ * @return array[]
+ * @throws UnexpectedValueException
+ */
+ protected function getLiveRing() {
+ if ( !$this->ejectExpiryByLocation ) {
+ return $this->baseRing; // nothing ejected
+ }
+
+ $now = $this->getCurrentTime();
+
+ if ( $this->liveRing === null || min( $this->ejectExpiryByLocation ) <= $now ) {
+ // Live ring needs to be regerenated...
+ $this->ejectExpiryByLocation = array_filter(
+ $this->ejectExpiryByLocation,
+ function ( $expiry ) use ( $now ) {
+ return ( $expiry > $now );
+ }
+ );
+
+ if ( count( $this->ejectExpiryByLocation ) ) {
+ // Some locations are still ejected from the ring
+ $liveRing = [];
+ foreach ( $this->baseRing as $i => $nodeInfo ) {
+ $location = $nodeInfo[self::KEY_LOCATION];
+ if ( !isset( $this->ejectExpiryByLocation[$location] ) ) {
+ $liveRing[] = $nodeInfo;
+ }
+ }
+ } else {
+ $liveRing = $this->baseRing;
+ }
+
+ $this->liveRing = $liveRing;
+ }
+
+ if ( !$this->liveRing ) {
+ throw new UnexpectedValueException( "The live ring is currently empty." );
+ }
+
+ return $this->liveRing;
+ }
+
+ /**
+ * @return int UNIX timestamp
+ */
+ protected function getCurrentTime() {
+ return time();
+ }
+
+ public function serialize() {
+ return serialize( [
+ 'algorithm' => $this->algo,
+ 'locations' => $this->weightByLocation,
+ 'ejections' => $this->ejectExpiryByLocation
+ ] );
+ }
+
+ public function unserialize( $serialized ) {
+ $data = unserialize( $serialized );
+ if ( is_array( $data ) ) {
+ $this->init( $data['locations'], $data['algorithm'], $data['ejections'] );
+ } else {
+ throw new UnexpectedValueException( __METHOD__ . ": unable to decode JSON." );
+ }