MediaWiki  1.34.0
HashRing Class Reference

Convenience class for weighted consistent hash rings. More...

Inheritance diagram for HashRing:
Collaboration diagram for HashRing:

Public Member Functions

 __construct (array $map, $algo='sha1', array $ejections=[])
 Make a consistent hash ring given a set of locations and their weight values. More...
 
 ejectFromLiveRing ( $location, $ttl)
 Remove a location from the "live" hash ring. More...
 
 getLiveLocation ( $item)
 Get the location of an item on the "live" ring. More...
 
 getLiveLocations ( $item, $limit)
 Get the location of an item on the "live" ring, as well as the next locations. More...
 
 getLiveLocationWeights ()
 Get the map of "live" locations to weight (does not include zero weight items) More...
 
 getLocation ( $item)
 Get the location of an item on the ring. More...
 
 getLocations ( $item, $limit, $from=self::RING_ALL)
 Get the location of an item on the ring followed by the next ring locations. More...
 
 getLocationWeights ()
 Get the map of locations to weight (does not include zero weight items) More...
 
 serialize ()
 
 unserialize ( $serialized)
 

Public Attributes

const KEY_LOCATION = 1
 
const KEY_POS = 0
 

Protected Member Functions

 getCurrentTime ()
 
 getLiveRing ()
 Get the "live" hash ring (which does not include ejected locations) More...
 
 init (array $map, $algo, array $ejections)
 

Protected Attributes

string $algo
 Hashing algorithm for hash() More...
 
array[] $baseRing
 Non-empty position-ordered list of (position, location name) More...
 
int[] $ejectExpiryByLocation
 Map of (location => UNIX timestamp) More...
 
array[] $liveRing
 Non-empty position-ordered list of (position, location name) More...
 
int[] $weightByLocation
 Non-empty (location => integer weight) More...
 

Private Member Functions

 buildLocationRing (array $weightByLocation)
 
 findNodeIndexForPosition ( $position, $ring)
 
 getItemPosition ( $item)
 
 getNextClockwiseNodeIndex ( $i, $ring)
 
 getNodePositionQuartet ( $nodeGroupName)
 

Detailed Description

Convenience class for weighted consistent hash rings.

This deterministically maps "keys" to a set of "locations" while avoiding clumping

Each location is represented by a number of nodes on a ring proportionate to the ratio of its weight compared to the total location weight. Note positions are deterministically derived from the hash of the location name. Nodes are responsible for the portion of the ring, counter-clockwise, up until the next node. Locations are responsible for all portions of the ring that the location's nodes are responsible for.

A location that is temporarily "ejected" is said to be absent from the "live" ring. If no location ejections are active, then the base ring and live ring are identical.

Since
1.22

Definition at line 39 of file HashRing.php.

Constructor & Destructor Documentation

◆ __construct()

HashRing::__construct ( array  $map,
  $algo = 'sha1',
array  $ejections = [] 
)

Make a consistent hash ring given a set of locations and their weight values.

Parameters
int[]$mapMap of (location => weight)
string$algoHashing algorithm listed in hash_algos() [optional]
int[]$ejectionsMap of (location => UNIX timestamp) for ejection expiries
Since
1.31

Definition at line 75 of file HashRing.php.

References $algo, and init().

Member Function Documentation

◆ buildLocationRing()

HashRing::buildLocationRing ( array  $weightByLocation)
private
Parameters
int[]$weightByLocation
Returns
array[]

Definition at line 282 of file HashRing.php.

References $weightByLocation, and getNodePositionQuartet().

Referenced by init().

◆ ejectFromLiveRing()

HashRing::ejectFromLiveRing (   $location,
  $ttl 
)

Remove a location from the "live" hash ring.

Parameters
string$location
int$ttlSeconds
Returns
bool Whether some non-ejected locations are left
Exceptions
UnexpectedValueException

Definition at line 222 of file HashRing.php.

References getCurrentTime().

Referenced by JobQueueFederated\tryJobInsertions().

◆ findNodeIndexForPosition()

HashRing::findNodeIndexForPosition (   $position,
  $ring 
)
private
Parameters
float$position
array[]$ringEither the base or live ring
Returns
int|null

Definition at line 167 of file HashRing.php.

References KEY_POS.

Referenced by getLocations().

◆ getCurrentTime()

HashRing::getCurrentTime ( )
protected
Returns
int UNIX timestamp

Definition at line 433 of file HashRing.php.

Referenced by ejectFromLiveRing(), getLiveLocationWeights(), and getLiveRing().

◆ getItemPosition()

HashRing::getItemPosition (   $item)
private
Parameters
string$itemKey
Returns
float Ring position; integral number in [0, self::RING_SIZE - 1]

Definition at line 334 of file HashRing.php.

Referenced by getLocations().

◆ getLiveLocation()

HashRing::getLiveLocation (   $item)
final

Get the location of an item on the "live" ring.

Parameters
string$item
Returns
string Location
Exceptions
UnexpectedValueException

Definition at line 242 of file HashRing.php.

References getLocations().

Referenced by JobQueueFederated\tryJobInsertions().

◆ getLiveLocations()

HashRing::getLiveLocations (   $item,
  $limit 
)
final

Get the location of an item on the "live" ring, as well as the next locations.

Parameters
string$item
int$limitMaximum number of locations to return
Returns
string[] List of locations
Exceptions
UnexpectedValueException

Definition at line 254 of file HashRing.php.

References getLocations().

◆ getLiveLocationWeights()

HashRing::getLiveLocationWeights ( )

Get the map of "live" locations to weight (does not include zero weight items)

Returns
int[]
Exceptions
UnexpectedValueException

Definition at line 264 of file HashRing.php.

References getCurrentTime().

Referenced by JobQueueFederated\doBatchPush(), and JobQueueFederated\tryJobInsertions().

◆ getLiveRing()

HashRing::getLiveRing ( )
protected

Get the "live" hash ring (which does not include ejected locations)

Returns
array[]
Exceptions
UnexpectedValueException

Definition at line 391 of file HashRing.php.

References $baseRing, $liveRing, getCurrentTime(), and KEY_LOCATION.

Referenced by getLocations().

◆ getLocation()

HashRing::getLocation (   $item)
final

Get the location of an item on the ring.

Parameters
string$item
Returns
string Location
Exceptions
UnexpectedValueException

Definition at line 109 of file HashRing.php.

References getLocations().

◆ getLocations()

HashRing::getLocations (   $item,
  $limit,
  $from = self::RING_ALL 
)

Get the location of an item on the ring followed by the next ring locations.

Parameters
string$item
int$limitMaximum number of locations to return
int$fromOne of the RING_* class constants
Returns
string[] List of locations
Exceptions
InvalidArgumentException
UnexpectedValueException

Definition at line 123 of file HashRing.php.

References $baseRing, findNodeIndexForPosition(), getItemPosition(), getLiveRing(), getNextClockwiseNodeIndex(), and KEY_LOCATION.

Referenced by getLiveLocation(), getLiveLocations(), and getLocation().

◆ getLocationWeights()

HashRing::getLocationWeights ( )

Get the map of locations to weight (does not include zero weight items)

Returns
int[]

Definition at line 210 of file HashRing.php.

References $weightByLocation.

◆ getNextClockwiseNodeIndex()

HashRing::getNextClockwiseNodeIndex (   $i,
  $ring 
)
private
Parameters
int$iValid index for a node in the ring
array[]$ringEither the base or live ring
Returns
int Valid index for a node in the ring

Definition at line 375 of file HashRing.php.

Referenced by getLocations().

◆ getNodePositionQuartet()

HashRing::getNodePositionQuartet (   $nodeGroupName)
private
Parameters
string$nodeGroupName
Returns
float[] Four ring positions on [0, self::RING_SIZE - 1]

Definition at line 356 of file HashRing.php.

Referenced by buildLocationRing().

◆ init()

HashRing::init ( array  $map,
  $algo,
array  $ejections 
)
protected
Parameters
int[]$mapMap of (location => integer)
string$algoHashing algorithm
int[]$ejectionsMap of (location => UNIX timestamp) for ejection expires

Definition at line 84 of file HashRing.php.

References $algo, $weightByLocation, and buildLocationRing().

Referenced by __construct(), and unserialize().

◆ serialize()

HashRing::serialize ( )

Definition at line 437 of file HashRing.php.

◆ unserialize()

HashRing::unserialize (   $serialized)

Definition at line 445 of file HashRing.php.

References $serialized, and init().

Member Data Documentation

◆ $algo

string HashRing::$algo
protected

Hashing algorithm for hash()

Definition at line 41 of file HashRing.php.

Referenced by __construct(), and init().

◆ $baseRing

array [] HashRing::$baseRing
protected

Non-empty position-ordered list of (position, location name)

Definition at line 48 of file HashRing.php.

Referenced by getLiveRing(), and getLocations().

◆ $ejectExpiryByLocation

int [] HashRing::$ejectExpiryByLocation
protected

Map of (location => UNIX timestamp)

Definition at line 45 of file HashRing.php.

◆ $liveRing

array [] HashRing::$liveRing
protected

Non-empty position-ordered list of (position, location name)

Definition at line 50 of file HashRing.php.

Referenced by getLiveRing().

◆ $weightByLocation

int [] HashRing::$weightByLocation
protected

Non-empty (location => integer weight)

Definition at line 43 of file HashRing.php.

Referenced by buildLocationRing(), getLocationWeights(), and init().

◆ KEY_LOCATION

const HashRing::KEY_LOCATION = 1

Definition at line 60 of file HashRing.php.

Referenced by getLiveRing(), and getLocations().

◆ KEY_POS

const HashRing::KEY_POS = 0

Definition at line 59 of file HashRing.php.

Referenced by findNodeIndexForPosition().


The documentation for this class was generated from the following file: