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

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

	__serialize ()

	__unserialize ( $data)

	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 followed by the next ring locations.

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

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 position-ordered list of (position, location name)

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

array[] null	$liveRing
	Non-empty position-ordered list of (position, location name)

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

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.

This class is designed in a way that using the "md5" algorithm will make it compatible with libketama, e.g. OPT_LIBKETAMA_COMPATIBLE from the PECL memcached extension or "ketama" from twemproxy. This can simplify the process of switching client libraries. However, note that different clients might use incompatible 32-bit memcached value flag conventions.

Since: 1.22

Definition at line 36 of file HashRing.php.

Constructor & Destructor Documentation

◆ __construct()

Wikimedia\HashRing\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 70 of file HashRing.php.

References Wikimedia\HashRing\HashRing\$algo, and Wikimedia\HashRing\HashRing\init().

Member Function Documentation

◆ __serialize()

Wikimedia\HashRing\HashRing::__serialize ( )

Definition at line 432 of file HashRing.php.

References Wikimedia\HashRing\HashRing\$algo, Wikimedia\HashRing\HashRing\$ejectExpiryByLocation, and Wikimedia\HashRing\HashRing\$weightByLocation.

◆ __unserialize()

Wikimedia\HashRing\HashRing::__unserialize ( $data )

Definition at line 440 of file HashRing.php.

References Wikimedia\HashRing\HashRing\init().

◆ ejectFromLiveRing()

Wikimedia\HashRing\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 217 of file HashRing.php.

References Wikimedia\HashRing\HashRing\getCurrentTime().

Referenced by MediaWiki\JobQueue\JobQueueFederated\tryJobInsertions().

◆ getCurrentTime()

Wikimedia\HashRing\HashRing::getCurrentTime ( )

protected

Returns: int UNIX timestamp

Definition at line 428 of file HashRing.php.

Referenced by Wikimedia\HashRing\HashRing\ejectFromLiveRing(), Wikimedia\HashRing\HashRing\getLiveLocationWeights(), and Wikimedia\HashRing\HashRing\getLiveRing().

◆ getLiveLocation()

Wikimedia\HashRing\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 237 of file HashRing.php.

References Wikimedia\HashRing\HashRing\getLocations().

Referenced by MediaWiki\JobQueue\JobQueueFederated\tryJobInsertions().

◆ getLiveLocations()

Wikimedia\HashRing\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 249 of file HashRing.php.

References Wikimedia\HashRing\HashRing\getLocations().

◆ getLiveLocationWeights()

Wikimedia\HashRing\HashRing::getLiveLocationWeights ( )

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

Returns: int[]

Exceptions

UnexpectedValueException

Definition at line 259 of file HashRing.php.

References Wikimedia\HashRing\HashRing\getCurrentTime().

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

◆ getLiveRing()

Wikimedia\HashRing\HashRing::getLiveRing ( )

protected

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

Returns: array[]

Exceptions

UnexpectedValueException

Definition at line 386 of file HashRing.php.

References Wikimedia\HashRing\HashRing\$baseRing, Wikimedia\HashRing\HashRing\$liveRing, Wikimedia\HashRing\HashRing\getCurrentTime(), and Wikimedia\HashRing\HashRing\KEY_LOCATION.

Referenced by Wikimedia\HashRing\HashRing\getLocations().

◆ getLocation()

Wikimedia\HashRing\HashRing::getLocation ( $item )

final

Get the location of an item on the ring.

Parameters

string $item

Returns: string Location

Exceptions

UnexpectedValueException

Definition at line 104 of file HashRing.php.

References Wikimedia\HashRing\HashRing\getLocations().

◆ getLocations()

Wikimedia\HashRing\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	$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 117 of file HashRing.php.

References Wikimedia\HashRing\HashRing\$baseRing, Wikimedia\HashRing\HashRing\getLiveRing(), and Wikimedia\HashRing\HashRing\KEY_LOCATION.

Referenced by Wikimedia\HashRing\HashRing\getLiveLocation(), Wikimedia\HashRing\HashRing\getLiveLocations(), and Wikimedia\HashRing\HashRing\getLocation().

◆ getLocationWeights()

Wikimedia\HashRing\HashRing::getLocationWeights ( )

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

Returns: int[]

Definition at line 205 of file HashRing.php.

References Wikimedia\HashRing\HashRing\$weightByLocation.

◆ init()

Wikimedia\HashRing\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 79 of file HashRing.php.

References Wikimedia\HashRing\HashRing\$algo, and Wikimedia\HashRing\HashRing\$weightByLocation.

Referenced by Wikimedia\HashRing\HashRing\__construct(), and Wikimedia\HashRing\HashRing\__unserialize().

Member Data Documentation

◆ $algo

string Wikimedia\HashRing\HashRing::$algo

protected

Hashing algorithm for hash()

Definition at line 38 of file HashRing.php.

Referenced by Wikimedia\HashRing\HashRing\__construct(), Wikimedia\HashRing\HashRing\__serialize(), and Wikimedia\HashRing\HashRing\init().

◆ $baseRing

array [] Wikimedia\HashRing\HashRing::$baseRing

protected

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

Definition at line 45 of file HashRing.php.

Referenced by Wikimedia\HashRing\HashRing\getLiveRing(), and Wikimedia\HashRing\HashRing\getLocations().

◆ $ejectExpiryByLocation

int [] Wikimedia\HashRing\HashRing::$ejectExpiryByLocation

protected

Map of (location => UNIX timestamp)

Definition at line 42 of file HashRing.php.

Referenced by Wikimedia\HashRing\HashRing\__serialize().

◆ $liveRing

array [] null Wikimedia\HashRing\HashRing::$liveRing

protected

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

Definition at line 47 of file HashRing.php.

Referenced by Wikimedia\HashRing\HashRing\getLiveRing().

◆ $weightByLocation

int [] Wikimedia\HashRing\HashRing::$weightByLocation

protected

Non-empty (location => integer weight)

Definition at line 40 of file HashRing.php.

Referenced by Wikimedia\HashRing\HashRing\__serialize(), Wikimedia\HashRing\HashRing\getLocationWeights(), and Wikimedia\HashRing\HashRing\init().

◆ KEY_LOCATION

const Wikimedia\HashRing\HashRing::KEY_LOCATION = 1

Definition at line 55 of file HashRing.php.

Referenced by Wikimedia\HashRing\HashRing\getLiveRing(), and Wikimedia\HashRing\HashRing\getLocations().

◆ KEY_POS

const Wikimedia\HashRing\HashRing::KEY_POS = 0

Definition at line 54 of file HashRing.php.

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

includes/libs/HashRing/HashRing.php

Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Constructor & Destructor Documentation

◆ __construct()

Member Function Documentation

◆ __serialize()

◆ __unserialize()

◆ ejectFromLiveRing()

◆ getCurrentTime()

◆ getLiveLocation()

◆ getLiveLocations()

◆ getLiveLocationWeights()

◆ getLiveRing()

◆ getLocation()

◆ getLocations()

◆ getLocationWeights()

◆ init()

Member Data Documentation

◆ $algo

◆ $baseRing

◆ $ejectExpiryByLocation

◆ $liveRing

◆ $weightByLocation

◆ KEY_LOCATION

◆ KEY_POS