ConsistentHash

ConsistentHash: consistent hashing ring for distributed load balancing.

Virtual nodes (replicas) are distributed evenly across the hash ring. Each physical node n gets replicas virtual nodes inserted at SHA-256(name ++ "#" ++ i) for i in 0..replicas-1.

Lookup: hash the key, walk the sorted ring to find the first virtual node whose position >= the key's hash; wrap around to the first node if none.

The internal ring is a sorted List((Hash, node)) — O(replicas) per add/remove, O(replicas) per lookup. Suitable for small-to-medium cluster sizes. (More precisely: add/remove/get are linear in the total number of virtual nodes on the ring, nodes * replicas, since the ring is a plain list.)

Types

ptypeHashRingHashRing(a) = HashRing(List((String, a)), Map(String, a), Int)#

(sorted_ring, name_map, replicas) sorted_ring: List((hash_str, node)) sorted by hash string name_map: Map(String, a) name -> node (for removal) replicas: virtual nodes per physical node

Functions

fnaddadd(ring : HashRing(a), name : String, node : a) : HashRing(a)#

Add physical node node under name, inserting replicas virtual nodes at Crypto.sha256(name ++ "#" ++ i) for i in 0..replicas-1. Adding a name that is already present replaces its entry in the name map but inserts a second set of virtual nodes, which still point at the old value; remove the name first to replace a node cleanly.

Examples

march> ConsistentHash.size(ConsistentHash.add(ConsistentHash.add(ConsistentHash.new(3), "n1", 1), "n2", 2))
2

fngetget(ring : HashRing(a), key : String) : Option(a)#

The node responsible for key: the first virtual node whose position (hex SHA-256 string, compared lexicographically) is >= Crypto.sha256(key). Returns None only when the ring has no virtual nodes. With a single physical node every key maps to it.

Examples

march> ConsistentHash.get(ConsistentHash.new(3), "user:42")
None
march> ConsistentHash.get(ConsistentHash.add(ConsistentHash.new(3), "n1", "node-1"), "user:42")
Some("node-1")

fnis_emptyis_empty(ring : HashRing(a)) : Bool#

True when no physical node is registered.

Examples

march> ConsistentHash.is_empty(ConsistentHash.add(ConsistentHash.new(3), "n1", 1))
false

fnnewnew(replicas : Int) : HashRing(a)#

An empty ring that will place replicas virtual nodes per physical node. More replicas spread keys more evenly at the cost of a longer ring. replicas of 0 or less makes add register the name without putting any virtual node on the ring, so get keeps returning None.

Examples

march> ConsistentHash.is_empty(ConsistentHash.new(3))
true
march> ConsistentHash.size(ConsistentHash.new(3))
0

fnnode_namesnode_names(ring : HashRing(a)) : List(String)#

All registered node names, in the name map's hash-traversal order.

Examples

march> ConsistentHash.node_names(ConsistentHash.add(ConsistentHash.new(3), "n1", "node-1"))
["n1"]

fnnodesnodes(ring : HashRing(a)) : List(a)#

All physical node values, one per registered name, in the name map's hash-traversal order (not ring order and not insertion order).

Examples

march> ConsistentHash.nodes(ConsistentHash.add(ConsistentHash.new(3), "n1", "node-1"))
["node-1"]

fnremoveremove(ring : HashRing(a), name : String) : HashRing(a)#

Remove the node registered under name and all its virtual nodes. Removing an unknown name returns an equivalent ring.

let ring = ConsistentHash.add(ConsistentHash.new(3), "n1", 1)
ConsistentHash.size(ConsistentHash.remove(ring, "n1"))   -- 0

fnsizesize(ring : HashRing(a)) : Int#

Number of registered physical nodes (names), not virtual nodes.

Examples

march> ConsistentHash.size(ConsistentHash.add(ConsistentHash.new(8), "n1", 1))
1