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#
| Attribute | Type | Description |
|---|---|---|
base_weight | int |
Functions#
__init__#
__init__(*, base_weight=128) -> None| Parameter | Type | Description |
|---|---|---|
base_weight | int = 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) -> NoneAdd nodes with weight (at least 0.1). A node whose key is
already there replaces the stored node and takes the new weight.
| Parameter | Type | Description |
|---|---|---|
nodes | Iterable[A] | |
weight | float = 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) -> Noneadd_many([node], weight=weight).
| Parameter | Type | Description |
|---|---|---|
node | A | |
weight | float = 1 |
def add(self, node: A, *, weight: float = 1) -> None:
"""``add_many([node], weight=weight)``."""
self.add_many([node], weight=weight)remove#
remove(node) -> NoneRemove the node with node's key, if there is one.
| Parameter | Type | Description |
|---|---|---|
node | A |
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) -> boolWhether a node with node's key is on the ring.
| Parameter | Type | Description |
|---|---|---|
node | A |
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._nodesget#
get(input) -> A | NoneThe 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.
| Parameter | Type | Description |
|---|---|---|
input | str |
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] | NoneA 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.
| Parameter | Type | Description |
|---|---|---|
count | float |
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]