HRW (hrw v0.2.0)

Copy Markdown

HRW (Highest Random Weight), also known as rendezvous hashing, maps a key to a node out of a set in a way that stays stable when nodes are added or removed.

This module is stateless. For O(log n) lookups over large node sets, build a skeleton with build/2 and pass it to owner/3.

Summary

Types

t()

Functions

build(nodes, opts \\ [])

Builds a skeleton from nodes for O(log n) lookups.

owner(key, nodes_or_skeleton, opts \\ [])

Returns the node responsible for key.

owners(key, nodes, count, opts \\ [])

Returns the top count nodes responsible for key, in descending weight order.

score(hrw, key, node)

Default scorer. Hashes {key, node} with the struct's hash_fn, falling back to :erlang.phash2/1 when hash_fn is nil.

Types

t()

@type t() :: %HRW{hash_fn: (term() -> integer()) | nil}

Functions

build(nodes, opts \\ [])

@spec build(
  [term()],
  keyword()
) :: HRW.Skeleton.t()

Builds a skeleton from nodes for O(log n) lookups.

Pass the result to owner/3.

Options

  • :fanout - branching factor of the virtual tree. Defaults to 3.
  • :cluster_size - target number of nodes per cluster. Defaults to 16.
  • :scorer - scoring strategy struct. Defaults to %HRW{}.

Examples

iex> HRW.build(["server1", "server2", "server3"], fanout: 3)
#HRW.Skeleton<3 nodes, fanout: 3, scorer: %HRW{hash_fn: nil}>

owner(key, nodes_or_skeleton, opts \\ [])

@spec owner(term(), [term()] | HRW.Skeleton.t(), keyword()) :: term()

Returns the node responsible for key.

Each node is hashed together with the key; the highest-scoring node wins.

Options

  • :scorer - scoring strategy struct. Defaults to %HRW{}. Ignored when the second argument is a skeleton — pass :scorer to build/2 instead.

Examples

iex> HRW.owner("192.168.0.1", ["server1", "server2", "server3"])
"server2"

iex> skeleton = HRW.build(["server1", "server2", "server3"])
iex> HRW.owner("192.168.0.2", skeleton)
"server3"

owners(key, nodes, count, opts \\ [])

@spec owners(term(), [term()], non_neg_integer(), keyword()) :: [term()]

Returns the top count nodes responsible for key, in descending weight order.

Options

  • :scorer - scoring strategy struct. Defaults to %HRW{}.

Examples

iex> HRW.owners("192.168.0.1", ["server1", "server2", "server3"], 2)
["server2", "server3"]

score(hrw, key, node)

@spec score(t(), term(), term()) :: integer()

Default scorer. Hashes {key, node} with the struct's hash_fn, falling back to :erlang.phash2/1 when hash_fn is nil.

Implements HRW.Scorer. Called internally whenever the default scorer is selected (no :scorer option, or scorer: %HRW{} passed explicitly).