Implementation Strategies

ExRingRing provides two ring implementations: Static and Dynamic. They produce identical ring topologies (for the same nodes and configuration) but differ in their performance characteristics.

Both are immutable values: a ring can be shared across processes and read concurrently without locks. Modifications return a new ring and never mutate the original.

Comparison

Property	Static	Dynamic
Data Structure	Sorted tuple (array)	Balanced tree (`:gb_trees`)
Lookup	O(log N) binary search	O(log N) tree traversal
Add Node	O(N log N) — rebuilds vnodes	O(log N) — inserts vnodes
Remove Node	O(N) — filters vnodes	O(log N) — deletes vnodes
Memory	Lower — flat tuple	Higher — tree nodes + pointers
Choose when…	Reads >> writes	Writes >> reads

Both implementations produce identical results for find_node and collect_nodes given the same nodes and configuration — including hash collisions, where the first virtual node (by hash, then sequence) wins. The difference is only in performance.

Choosing an Implementation

Static (Default)

Best for rings that change infrequently but are queried often.

# Explicit static (also the default)
ring = ExRingRing.make(nodes, implementation: :static)

Good for:

Service discovery registries
Configuration distribution rings
Any ring with stable membership

Performance characteristics:

make/2 sorts all virtual nodes into a flat tuple — O(N log N) where N = nodes × vnodes
add_nodes/2 rebuilds the entire tuple — O(V log V) where V = total virtual nodes
remove_nodes/2 filters the tuple — O(V)
find_node/2 uses a lower-bound binary search over the sorted tuple — O(log V) guaranteed, independent of hash distribution

Dynamic

Best for rings with frequent membership changes.

ring = ExRingRing.make(nodes, implementation: :dynamic)

Good for:

Ephemeral nodes that join/leave frequently
Auto-scaling node pools
Real-time clustering

Performance characteristics:

make/2 inserts each virtual node into the tree — O(V log V)
add_node/2 inserts only new virtual nodes — O(log V) per insertion
remove_node/2 removes only affected virtual nodes — O(log V) per deletion
find_node/2 uses tree iterator and successor traversal — O(log V)

Verifying Equivalence

Both implementations produce the same lookup results:

nodes = ExRingRing.list_to_nodes([:a, :b, :c, :d, :e])

static_ring = ExRingRing.make(nodes, implementation: :static)
dynamic_ring = ExRingRing.make(nodes, implementation: :dynamic)

items = Enum.map(1..100, &"item_#{&1}")

Enum.each(items, fn item ->
  {:ok, s_node} = ExRingRing.find_node(static_ring, item)
  {:ok, d_node} = ExRingRing.find_node(dynamic_ring, item)
  assert s_node.key == d_node.key
end)

← Previous Page Configuration