Malachi.Cluster.HashRing (malachi v0.8.13)

View Source

A consistent-hashing ring that maps metadata keys to the vnode that owns them, the foundation of NorthGuard's DS-RSM (Dynamically-Sharded Replicated State Machine).

Each vnode sits at a token (a position) on a ring [0, ring_size). A key is hashed with :erlang.phash2/2 and routed to the first vnode whose token is >= hash, wrapping around past the largest token back to the smallest. So a vnode at token T owns the arc (predecessor_token, T] (with wraparound). Topic metadata is hashed by topic name, range and segment metadata by range id, which is how the DS-RSM shards metadata with minimal movement when vnodes are added or removed.

The ring is a pure value: a vnode_id => token map is the source of truth, plus a derived list sorted by token for routing. Membership changes (rare) rebuild the sorted list; routing (frequent, over a modest number of vnodes) is a linear ceiling search, which is plenty fast for the ~hundreds of vnodes a cluster has.

Summary

Types

t()
token()
vnode_id()

Functions

add_vnode(ring, vnode_id, token)

Places vnode_id at token on the ring.

boundaries(ring, vnode_id)

The arc {start_exclusive, end_inclusive} that vnode_id owns (with wraparound). When start == end the vnode is the only one on the ring and owns the whole ring. {:error, :not_found} if the vnode is not present.

new(opts \\ [])

Builds an empty ring over [0, 2^ring_bits).

remove_vnode(ring, vnode_id)

Removes vnode_id from the ring. {:error, :not_found} if it is not present.

route(ring, key)

Routes key to the vnode that owns it. {:error, :empty} if the ring has no vnodes.

size(ring)

The number of vnodes on the ring.

vnode_ids(ring)

The ids of the vnodes on the ring.

Types

t()

@type t() :: %Malachi.Cluster.HashRing{
  ring_size: pos_integer(),
  sorted: [{token(), vnode_id()}],
  tokens: %{required(vnode_id()) => token()}
}

token()

@type token() :: non_neg_integer()

vnode_id()

@type vnode_id() :: term()

Functions

add_vnode(ring, vnode_id, token)

@spec add_vnode(t(), vnode_id(), token()) :: {:ok, t()} | {:error, atom()}

Places vnode_id at token on the ring.

Fails with {:error, :token_out_of_range} if token is outside [0, ring_size), {:error, :token_taken} if another vnode already holds it, or {:error, :already_present} if the vnode is already on the ring.

boundaries(ring, vnode_id)

@spec boundaries(t(), vnode_id()) :: {:ok, {token(), token()}} | {:error, :not_found}

The arc {start_exclusive, end_inclusive} that vnode_id owns (with wraparound). When start == end the vnode is the only one on the ring and owns the whole ring. {:error, :not_found} if the vnode is not present.

new(opts \\ [])

@spec new(keyword()) :: t()

Builds an empty ring over [0, 2^ring_bits).

Options

  • :ring_bits - ring spans [0, 2^ring_bits) (default 32, max 32 because :erlang.phash2/2 supports a range up to 2^32).

remove_vnode(ring, vnode_id)

@spec remove_vnode(t(), vnode_id()) :: {:ok, t()} | {:error, :not_found}

Removes vnode_id from the ring. {:error, :not_found} if it is not present.

route(ring, key)

@spec route(t(), term()) :: {:ok, vnode_id()} | {:error, :empty}

Routes key to the vnode that owns it. {:error, :empty} if the ring has no vnodes.

size(ring)

@spec size(t()) :: non_neg_integer()

The number of vnodes on the ring.

vnode_ids(ring)

@spec vnode_ids(t()) :: [vnode_id()]

The ids of the vnodes on the ring.