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

Inheritance diagram for HashRing:

Collaboration diagram for HashRing:

[legend]

Public Member Functions
	__construct (array $map, $algo='sha1', array $ejections=[])
	Make a consistent hash ring given a set of locations and their weight values.

	ejectFromLiveRing ( $location, $ttl)
	Remove a location from the "live" hash ring.

	getLiveLocation ( $item)
	Get the location of an item on the "live" ring.

	getLiveLocations ( $item, $limit)
	Get the location of an item on the "live" ring, as well as the next locations.

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

	getLocation ( $item)
	Get the location of an item on the ring.

	getLocations ( $item, $limit, $from=self::RING_ALL)
	Get the location of an item on the ring, as well as the next locations.

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

	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)

	init (array $map, $algo, array $ejections)

Protected Attributes
string	$algo
	Hashing algorithm for hash()

array[]	$baseRing
	Non-empty list of (float, node name, location name)

int[]	$ejectExpiryByLocation
	Map of (location => UNIX timestamp)

array[]	$liveRing
	Non-empty list of (float, node name, location name)

int[]	$weightByLocation
	Non-empty (location => integer weight)

Private Member Functions
	buildLocationRing (array $weightByLocation, $algo)

	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[]	$map	Map of (location => weight)
string	$algo	Hashing algorithm listed in hash_algos() [optional]
int[]	$ejections	Map 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,
			$algo )

private

Parameters

int[]	$weightByLocation
string	$algo	Hashing algorithm

Returns: array[]

Definition at line 266 of file HashRing.php.

References $weightByLocation, getNodePositionQuartet(), and string.

Referenced by init().

◆ ejectFromLiveRing()

HashRing::ejectFromLiveRing	(		$location,
			$ttl )

Remove a location from the "live" hash ring.

Parameters

string	$location
int	$ttl	Seconds

Returns: bool Whether some non-ejected locations are left

Exceptions

UnexpectedValueException

Definition at line 205 of file HashRing.php.

References getCurrentTime().

Referenced by JobQueueFederated\tryJobInsertions().

◆ findNodeIndexForPosition()

HashRing::findNodeIndexForPosition	(		$position,
			$ring )

private

Parameters

float	$position
array[]	$ring	Either the base or live ring

Returns: int|null

Definition at line 157 of file HashRing.php.

References KEY_POS.

Referenced by getLocations().

◆ getCurrentTime()

HashRing::getCurrentTime ( )

protected

Returns: int UNIX timestamp

Definition at line 410 of file HashRing.php.

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

◆ getItemPosition()

HashRing::getItemPosition ( $item )

private

Parameters

string $item Key

Returns: float Ring position; integral number in [0, self::RING_SIZE - 1]

Definition at line 318 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 225 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	$limit	Maximum number of locations to return

Returns: string[] List of locations

Exceptions

UnexpectedValueException

Definition at line 237 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 247 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 368 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, as well as the next locations.

Parameters

string	$item
int	$limit	Maximum number of locations to return
int	$from	One of the RING_* class constants

Returns: string[] List of locations

Exceptions

UnexpectedValueException

Definition at line 122 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 193 of file HashRing.php.

References $weightByLocation.

◆ getNextClockwiseNodeIndex()

HashRing::getNextClockwiseNodeIndex	(		$i,
			$ring )

private

Parameters

int	$i	Valid index for a node in the ring
array[]	$ring	Either the base or live ring

Returns: int Valid index for a node in the ring

Definition at line 352 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 333 of file HashRing.php.

Referenced by buildLocationRing().

◆ init()

HashRing::init	(	array	$map,
			$algo,
		array	$ejections )

protected

Parameters

int[]	$map	Map of (location => integer)
string	$algo	Hashing algorithm
int[]	$ejections	Map 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 414 of file HashRing.php.

References serialize().

Referenced by serialize().

◆ unserialize()

HashRing::unserialize ( $serialized )

Definition at line 422 of file HashRing.php.

References $serialized, init(), and unserialize().

Referenced by unserialize().

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 list of (float, node name, 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 list of (float, node name, 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(), and HashRingTest\testHashRingKetamaMode().

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

includes/libs/HashRing.php

Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Private Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ __construct()

Member Function Documentation

◆ buildLocationRing()

◆ ejectFromLiveRing()

◆ findNodeIndexForPosition()

◆ getCurrentTime()

◆ getItemPosition()

◆ getLiveLocation()

◆ getLiveLocations()

◆ getLiveLocationWeights()

◆ getLiveRing()

◆ getLocation()

◆ getLocations()

◆ getLocationWeights()

◆ getNextClockwiseNodeIndex()

◆ getNodePositionQuartet()

◆ init()

◆ serialize()

◆ unserialize()

Member Data Documentation

◆ $algo

◆ $baseRing

◆ $ejectExpiryByLocation

◆ $liveRing

◆ $weightByLocation

◆ KEY_LOCATION

◆ KEY_POS