ex_ring_ring

# 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.

## 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. The difference is only in performance.

## Choosing an Implementation

### Static (Default)

Best for rings that change infrequently but are queried often.

```elixir
# 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 binary-search-like jump across partitions — O(log V)

### Dynamic

Best for rings with frequent membership changes.

```elixir
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:

```elixir
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)
```