HashRing (libring v1.6.0) View Source

This module defines an API for creating/manipulating a hash ring. The internal data structure for the hash ring is actually a gb_tree, which provides fast lookups for a given key on the ring.

The ring is a continuum of 2^32 "points", or integer values.
Nodes are sharded into 128 points, and distributed across the ring.
Each shard owns the keyspace below it.
Keys are hashed and assigned a point on the ring, the node for a given ring is determined by finding the next highest point on the ring for a shard, the node that shard belongs to is then the node which owns that key.
If a key's hash does not have any shards above it, it belongs to the first shard, this mechanism is what creates the ring-like topology.
When nodes are added/removed from the ring, only a small subset of keys must be reassigned.

Link to this section Summary

Functions

add_node(ring, node, weight \\ 128)

Adds a node to the hash ring, with an optional weight provided which determines the number of virtual nodes (shards) that will be assigned to it on the ring.

add_nodes(ring, nodes)

Adds a list of nodes to the hash ring.

key_to_node(ring, key)

Determines which node owns the given key.

key_to_nodes(hash_ring, key, count)

Determines which nodes owns a given key. Will return either count results or the number of nodes, depending on which is smaller.

new()

Creates a new hash ring structure, with no nodes added yet.

new(node, weight \\ 128)

Creates a new hash ring structure, seeded with the given node, with an optional weight provided which determines the number of virtual nodes (shards) that will be assigned to it on the ring.

nodes(hash_ring)

Returns the list of nodes which are present on the ring.

remove_node(ring, node)

Removes a node from the hash ring.

Link to this section Types

t()

Specs

t() :: %HashRing{nodes: [term()], ring: :gb_trees.tree()}

Link to this section Functions

add_node(ring, node, weight \\ 128)

Specs

add_node(t(), term(), pos_integer()) :: t()

Adds a node to the hash ring, with an optional weight provided which determines the number of virtual nodes (shards) that will be assigned to it on the ring.

The default weight for a node is 128.

Examples

iex> ring = HashRing.new()
...> ring = HashRing.add_node(ring, "a")
...> %HashRing{nodes: ["b", "a"]} = ring = HashRing.add_node(ring, "b", 64)
...> HashRing.key_to_node(ring, :foo)
"b"

add_nodes(ring, nodes)

Specs

add_nodes(t(), [term() | {term(), pos_integer()}]) :: t()

Adds a list of nodes to the hash ring.

The list can contain just the node key, or a tuple of the node key and it's desired weight.

See also the documentation for add_node/3.

Examples

iex> ring = HashRing.new()
...> ring = HashRing.add_nodes(ring, ["a", {"b", 64}])
...> %HashRing{nodes: ["b", "a"]} = ring
...> HashRing.key_to_node(ring, :foo)
"b"

key_to_node(ring, key)

Specs

key_to_node(t(), term()) :: term() | {:error, {:invalid_ring, :no_nodes}}

Determines which node owns the given key.

This function assumes that the ring has been populated with at least one node.

Examples

iex> ring = HashRing.new("a")
...> HashRing.key_to_node(ring, :foo)
"a"

iex> ring = HashRing.new()
...> HashRing.key_to_node(ring, :foo)
{:error, {:invalid_ring, :no_nodes}}

key_to_nodes(hash_ring, key, count)

Specs

key_to_nodes(t(), term(), pos_integer()) ::
  [term()] | {:error, {:invalid_ring, :no_nodes}}

Determines which nodes owns a given key. Will return either count results or the number of nodes, depending on which is smaller.

This function assumes that the ring has been populated with at least one node.

Examples

iex> ring = HashRing.new()
...> ring = HashRing.add_node(ring, "a")
...> ring = HashRing.add_node(ring, "b")
...> ring = HashRing.add_node(ring, "c")
...> HashRing.key_to_nodes(ring, :foo, 2)
["b", "c"]

iex> ring = HashRing.new()
...> HashRing.key_to_nodes(ring, :foo, 1)
{:error, {:invalid_ring, :no_nodes}}

new()

Specs

new() :: t()

Creates a new hash ring structure, with no nodes added yet.

Examples

iex> ring = HashRing.new()
...> %HashRing{nodes: ["a"]} = ring = HashRing.add_node(ring, "a")
...> HashRing.key_to_node(ring, {:complex, "key"})
"a"

new(node, weight \\ 128)

Specs

new(term(), pos_integer()) :: t()

Creates a new hash ring structure, seeded with the given node, with an optional weight provided which determines the number of virtual nodes (shards) that will be assigned to it on the ring.

The default weight for a node is 128.

Examples

iex> ring = HashRing.new("a")
...> %HashRing{nodes: ["a"]} = ring
...> HashRing.key_to_node(ring, :foo)
"a"

iex> ring = HashRing.new("a", 200)
...> %HashRing{nodes: ["a"]} = ring
...> HashRing.key_to_node(ring, :foo)
"a"

nodes(hash_ring)

Specs

nodes(t()) :: [term()]

Returns the list of nodes which are present on the ring.

The type of the elements in this list are the same as the type of the elements you initially added to the ring. In the following example, we used strings, but if you were using atoms, such as those used for Erlang node names, you would get a list of atoms back.

iex> ring = HashRing.new |> HashRing.add_nodes(["a", "b"])
...> HashRing.nodes(ring)
["b", "a"]

remove_node(ring, node)

Specs

remove_node(t(), term()) :: t()

Removes a node from the hash ring.

Examples

iex> ring = HashRing.new()
...> %HashRing{nodes: ["a"]} = ring = HashRing.add_node(ring, "a")
...> %HashRing{nodes: []} = ring = HashRing.remove_node(ring, "a")
...> HashRing.key_to_node(ring, :foo)
{:error, {:invalid_ring, :no_nodes}}