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.

Types

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

Functions

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

Add a named node to the ring, inserting replicas virtual nodes.

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

Find the node responsible for key. Returns None only when the ring is empty.

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

True when the ring has no nodes.

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

Create an empty ring with the given virtual node count per physical node.

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

All registered node names.

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

All distinct physical node values (in ring insertion order of their first virtual node).

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

Remove a named node and all its virtual nodes from the ring.

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

Number of distinct physical nodes.