GitHub

HashRing

API reference for HashRing.

class HashRing[A: PrimaryKey]

A mutable ring of nodes. base_weight (at least 1) is the number of virtual points per unit of weight.

Attributes

AttributeTypeDescription
base_weightint

Functions

__init__

__init__(*, base_weight=128) -> None
ParameterTypeDescription
base_weightint = 128
def __init__(self, *, base_weight: int = 128) -> None:
    self._base_weight = max(base_weight, 1)
    self._total_weight = 0.0
    self._nodes: dict[str, tuple[A, float]] = {}
    self._ring: list[tuple[int, str]] = []

add_many

add_many(nodes, *, weight=1) -> None

Add nodes with weight (at least 0.1). A node whose key is already there replaces the stored node and takes the new weight.

ParameterTypeDescription
nodesIterable[A]
weightfloat = 1
def add_many(self, nodes: Iterable[A], *, weight: float = 1) -> None:
    """Add ``nodes`` with ``weight`` (at least 0.1). A node whose key is
    already there replaces the stored node and takes the new weight."""
    weight = max(weight, 0.1)
    keys: list[str] = []
    reweighted: set[str] = set()
    for node in nodes:
        key = node.primary_key()
        entry = self._nodes.get(key)
        self._nodes[key] = (node, weight)
        if entry is not None:
            if entry[1] == weight:
                continue
            reweighted.add(key)
        keys.append(key)
    if reweighted:
        self._ring = [point for point in self._ring if point[1] not in reweighted]
    self._add_points(keys, _js_round(weight * self._base_weight))
    self._update_total_weight()

add

add(node, *, weight=1) -> None

add_many([node], weight=weight).

ParameterTypeDescription
nodeA
weightfloat = 1
def add(self, node: A, *, weight: float = 1) -> None:
    """``add_many([node], weight=weight)``."""
    self.add_many([node], weight=weight)

remove

remove(node) -> None

Remove the node with node's key, if there is one.

ParameterTypeDescription
nodeA
def remove(self, node: A) -> None:
    """Remove the node with ``node``'s key, if there is one."""
    key = node.primary_key()
    if self._nodes.pop(key, None) is not None:
        self._ring = [point for point in self._ring if point[1] != key]
        self._update_total_weight()

has

has(node) -> bool

Whether a node with node's key is on the ring.

ParameterTypeDescription
nodeA

Returns bool

def has(self, node: A) -> bool:
    """Whether a node with ``node``'s key is on the ring."""
    return node.primary_key() in self._nodes

get

get(input) -> A | None

The node nearest input's hash; None on an empty ring.

Only as even as the node keys hash, so short keys can split inputs very unevenly; get_shards with a shard per input is balanced.

ParameterTypeDescription
inputstr

Returns A | None

def get(self, input: str) -> A | None:
    """The node nearest ``input``'s hash; ``None`` on an empty ring.

    Only as even as the node keys hash, so short keys can split inputs
    very unevenly; ``get_shards`` with a shard per input is balanced."""
    if not self._ring:
        return None
    index = self._index_for(string_hash(input), None)[0]
    return self._nodes[self._ring[index][1]][0]

get_shards

get_shards(count) -> list[A] | None

A node for each of count shards (floored; at most zero is none), no node taking more than its share of the weight while another has room; None on an empty ring.

ParameterTypeDescription
countfloat

Returns list[A] | None

def get_shards(self, count: float) -> list[A] | None:
    """A node for each of ``count`` shards (floored; at most zero is
    none), no node taking more than its share of the weight while
    another has room; ``None`` on an empty ring."""
    if not self._ring:
        return None
    count = _normalize_count(count)
    shards: list[A | None] = [None] * count
    allocations: dict[str, int] = {}
    remaining: dict[int, None] = {}
    exclude: set[str] = set()

    distances: list[tuple[int, str, int]] = []
    for shard in range(count):
        index, distance = self._index_for(_shard_hash(shard), None)
        distances.append((shard, self._ring[index][1], distance))
        remaining[shard] = None
    distances.sort(key=lambda entry: entry[2])
    for shard, key, _ in distances:
        if key in exclude:
            continue
        value, weight = self._nodes[key]
        shards[shard] = value
        del remaining[shard]
        if self._allocate(allocations, key, weight, count):
            exclude.add(key)

    all_at_max = len(exclude) == len(self._nodes)
    for shard in remaining:
        index = self._index_for(_shard_hash(shard), None if all_at_max else exclude)[0]
        key = self._ring[index][1]
        value, weight = self._nodes[key]
        shards[shard] = value
        if all_at_max:
            continue
        if self._allocate(allocations, key, weight, count):
            exclude.add(key)
            all_at_max = len(exclude) == len(self._nodes)
    return [shard for shard in shards if shard is not None]