Module hash_ring

Description
Data Types
Function Index
Function Details

Consistent Hash Rings.

This module defines the hash_ring behaviour.
Required callback functions: make/2, add_nodes/2, remove_nodes/2, get_nodes/1, fold/4.

Description

Consistent Hash Rings

Data Types

fold_fun()

fold_fun() = fun((ring_node(), Acc::term()) -> {Continue::boolean(), AccNext::term()})

A folding function.

Acc and AccNext are ordinary accumulation variables.

If Continue is true and there are untraversed nodes, a next node will be folded, otherwise the folding will break.

hash_algorithm()

hash_algorithm() = crc32 | phash2 | md5 | sha | sha256

The hash algorithm which is used to determine locations of nodes and items on a ring

hash_ring_module()

hash_ring_module() = hash_ring_static | hash_ring_dynamic

A hash_ring behaviour implementing module

item()

item() = hash_ring_node:key()

An item.

All items have a virtual address (location) on a ring.

node_map()

node_map() = #{hash_ring_node:key() => ring_node()}

The map representation of nodes

option()

option() = {module, hash_ring_module()} | {virtual_node_count, pos_integer()} | {max_hash_byte_size, pos_integer()} | {hash_algorithm, hash_algorithm()}

module:

The hash_ring implementation module which will be used to create and manipulate a hash ring instance.
The default value is hash_ring_static

virtual_node_count:

The number of virtual nodes per node on the ring
The larger value is good for balancing of the ring but it consumes more memory
Actual virtual node count of a node is calculated by round(virtual_node_count * get_weight(Node))
The default value is 256

max_hash_byte_size:

The maximum number of significant bytes
The default value is 4

hash_algorithm:

The hash algorithm used for the ring
The default value is md5

options()

options() = [option()]

ring()

abstract datatype: ring(_Key, _Data)

A consistent hash ring.

It is an unidirection ring.

ring()

ring(Key) = ring(Key, Key)

ring()

ring() = ring(hash_ring_node:key())

ring_node()

ring_node() = hash_ring_node:ring_node()

A node on a ring

Function Index

add_node/2	Equivalent to `add_nodes([Node], Ring)`.
add_nodes/2	Adds `Nodes` to `Ring`
collect_nodes/3	Collects the `N` nodes which are logically adjacent to `Item` on `Ring`
find_node/2	Finds a node which is logically adjacent to `Item` on `Ring`
fold/4	Folds `Fun` over every node in `Ring` returning the final value of the accumulator.
get_node_count/1	Returns the number of nodes in `Ring`
get_node_list/1	Returns the nodes in `Ring` as a newly created list.
get_nodes/1	Returns the nodes in `Ring` as a map.
is_ring/1	Returns `true` if `X` is a `ring()`, otherwise `false`
list_to_nodes/1	Creates a list of ring_node()` from a list of `X
make/1	Equivalent to `make(Nodes, [])`.
make/2	Creates a new consistent hash ring instance.
remove_node/2	Equivalent to `remove_nodes([Node], Ring)`.
remove_nodes/2	Removes nodes which have a key included in `Keys` from `Ring`

Function Details

add_node/2

add_node(Node::ring_node(), Ring::ring()) -> ring()

Equivalent to add_nodes([Node], Ring).

add_nodes/2

add_nodes(Nodes::[ring_node()], Ring::ring()) -> ring()

Adds Nodes to Ring

Existing nodes which have the same key will be overwritten.

  > R0 = hash_ring:make([]).
  > R1 = hash_ring:add_nodes([hash_ring_node:make(a)], R0).
  > hash_ring:get_node_list(R1).
  [{hash_ring_node,a,a,1}]

collect_nodes/3

collect_nodes(Item::item(), N::non_neg_integer(), Ring::ring()) -> Nodes::[ring_node()]

Collects the N nodes which are logically adjacent to Item on Ring

In other words, it returns Nodes which are the N successor of Item.

If the number of nodes in Ring is less than N, it returns a list which contains all nodes in Ring, but the order of the elements depdends on Item.

  > Ring = hash_ring:make(hash_ring:list_to_nodes([a, b, c, d, e])).
 
  > hash_ring:collect_nodes(foo, 3, Ring).
  [{hash_ring_node,e,e,1},
   {hash_ring_node,d,d,1},
   {hash_ring_node,a,a,1}]
 
  > hash_ring:collect_nodes(bar, 10, Ring).
  [{hash_ring_node,b,b,1},
   {hash_ring_node,c,c,1},
   {hash_ring_node,e,e,1},
   {hash_ring_node,d,d,1},
   {hash_ring_node,a,a,1}]
 
  > hash_ring:collect_nodes(baz, 10, Ring).
  [{hash_ring_node,b,b,1},
   {hash_ring_node,a,a,1},
   {hash_ring_node,e,e,1},
   {hash_ring_node,d,d,1},
   {hash_ring_node,c,c,1}]

find_node/2

find_node(Item::item(), Ring::ring()) -> {ok, Node::ring_node()} | error

Finds a node which is logically adjacent to Item on Ring

In other words, it returns Node which is the successor of Item.

If the ring is empty, it returns error.

  > Ring = hash_ring:make(hash_ring:list_to_nodes(lists:seq(1, 100))).
 
  > hash_ring:find_node(a, Ring).
  {ok, {hash_ring_node,36,36,1}}
 
  > hash_ring:find_node(b, Ring).
  {ok, {hash_ring_node,53,53,1}}

fold/4

fold(Fun::fold_fun(), Item::item(), AccIn::term(), Ring::ring()) -> AccOut::term()

Folds Fun over every node in Ring returning the final value of the accumulator

The iteration is started from a node which logically placed at next location of Item on Ring. And it proceeds clockwise.

See also the documentation of fold_fun() type.

  %%
  %% Finds a node which is adjacent to the specified item (cf. `find_node/1').
  %%
  > Ring = hash_ring:make(hash_ring:list_to_nodes(lists:seq(1, 100))).
 
  > hash_ring:fold(fun (N, _) -> {false, {ok, N}} end, a, error, Ring).
  {ok, {hash_ring_node,36,36,1}}
 
  > hash_ring:fold(fun (N, _) -> {false, {ok, N}} end, b, error, Ring).
  {ok, {hash_ring_node,53,53,1}}

Unlike get_nodes/1, this function requires no memory allocation for the return value.

is_ring/1

is_ring(X::ring() | term()) -> boolean()

Returns true if X is a ring(), otherwise false

list_to_nodes/1

list_to_nodes(List::[X]) -> [ring_node()]

X = hash_ring_node:key() | {hash_ring_node:key(), hash_ring_node:data()} | {hash_ring_node:key(), hash_ring_node:data(), hash_ring_node:options()}

Creates a list of ring_node()` from a list of `X

  > Nodes0 = hash_ring:list_to_nodes([a, {b, 1}, {c, 2, [{weight, 0.2}]}]).
  > Nodes1 = [hash_ring_node:make(a), hash_ring_node:make(b, 1), hash_ring_node:make(c, 2, [{weight, 0.2}])].
  > Nodes0 = Nodes1.

make/1

make(Nodes::[ring_node()]) -> ring()

Equivalent to make(Nodes, []).

make/2

make(Nodes::[ring_node()], Options::options()) -> ring()

Creates a new consistent hash ring instance

  > R = hash_ring:make(hash_ring:list_to_nodes([a, b, c, d, e])).
  > hash_ring:get_node_list(R).
  [{hash_ring_node,a,a,1},
   {hash_ring_node,b,b,1},
   {hash_ring_node,c,c,1},
   {hash_ring_node,d,d,1},
   {hash_ring_node,e,e,1}]

remove_node/2

remove_node(Node::hash_ring_node:key(), Ring::ring()) -> ring()

Equivalent to remove_nodes([Node], Ring).

remove_nodes/2

remove_nodes(Keys::[hash_ring_node:key()], Ring::ring()) -> ring()

Removes nodes which have a key included in Keys from Ring

  > R0 = hash_ring:make(hash_ring:list_to_nodes([a, b])).
  > R1 = hash_ring:remove_nodes([b], R0).
  > hash_ring:get_node_list(R1).
  [{hash_ring_node,a,a,1}]

Generated by EDoc, Jul 8 2020, 21:51:52.