Perf: stop retaining the ConsistentHash ring's SortedDictionary (optionally build straight into sorted arrays)

Background

ConsistentHash<T> (src/core/Akka/Routing/ConsistentHash.cs) currently keeps the ring in a SortedDictionary<int, T> _nodes and lazily materializes parallel int[] / T[] arrays (RingTuple) that back the Array.BinarySearch in NodeFor. So a live ring retains both structures.

For rings built via ConsistentHash.Create — which is what ConsistentHashingRoutingLogic (and ClusterReceptionist) use — the SortedDictionary is only needed after construction by operator + / operator -, and those now rebuild via Create anyway (they only need the node set, which is the values array). So the retained tree is effectively dead weight once the lookup arrays exist.

Each SortedDictionary entry is a heap-allocated red-black-tree node (~56 bytes on 64-bit). Retained footprint per ring today:

routees × factor	ring points	retained tree	retained arrays	total retained
2000 × 10	20,000	~1.1 MB	~0.24 MB	~1.35 MB
5000 × 10	50,000	~2.8 MB	~0.60 MB	~3.4 MB

(Create timing for reference, from ConsistentHashCreateBenchmarks: 1000×10 ≈ 2.6 ms / 575 KB allocated; 5000×10 ≈ 17.9 ms / 2.9 MB — most of that allocation is the tree.)

This is two options at very different cost/benefit ratios. Do Option A; treat Option B as an optional stretch that's only worth it if profiling shows Create time or transient GC actually bites.

---

Option A (recommended, cheap) — stop retaining the SortedDictionary

Keep the current incremental tree build in Create exactly as-is (simple, correct collision probing — no change to collision handling), but don't hold onto the tree. In the constructor, extract the sorted int[] / T[] once and store those as the ring's state; drop the _nodes field. Redirect the few readers off the arrays:

• NodeFor(...) — already uses the arrays (RingTuple); no change.
• IsEmpty — read keys.Length == 0 instead of _nodes.Any().
• operator + / operator - — already rebuild via Create; feed them the values array (Distinct() by reference collapses the factor repeats) instead of _nodes.Values.

Reclaims the retained tree (~1.1 MB at 20k vnodes, ~2.8 MB at 50k) for a long-lived ring, with zero change to collision handling and trivial risk. Note: this keeps the transient tree allocation and tree-insert cost inside Create — only steady-state footprint improves, which is the thing that actually matters for a ring held for the router's lifetime.

Public API is preserved: the ConsistentHash(SortedDictionary<int,T>, int) constructor stays (extend-only); it simply materializes the arrays from the passed dictionary and doesn't retain it.

Option B (optional stretch) — build straight into sorted arrays

Eliminate the transient tree and the per-insert rebalancing by building the ring in a batch pass instead of a SortedDictionary:

1. Flatten to (slot, node, key, vnodeIndex) tuples: for each de-duplicated node (by ToString), Enumerable.Range(1, virtualNodesFactor) → ConcatenateNodeHash(nodeHash, i). Keep Range(1, factor) — starting at 0 shifts every key and breaks compatibility.
2. OrderBy(slot).ThenBy(key, StringComparer.Ordinal) — the ThenBy on the node string is the determinism tiebreak that replaces the current explicit node sort (it must live in the sort, or collisions resolve differently per node).
3. Single linear walk: first tuple of each equal-slot run wins its natural slot; the rest are losers.
4. Relocate losers by ConcatenateNodeHash(nodeHash, vnodeIndex + factor) + probe, checking freeness via Array.BinarySearch over the sorted prefix, then binary-insert (losers are ~0 per rebuild). Carry vnodeIndex through the flatten so a loser can be re-hashed.

Gets the full runtime + allocation win (one cache-friendly array sort, no RB-tree, no separate materialization), but inherits the fiddly two-phase collision handling above. Given Create runs once per membership change, off the message path, the runtime win is modest relative to that complexity — hence "stretch."

---

Constraints / caveats (both options)

• Must stay byte-identical to the current ring in the no-collision case. There is an executable before/after proof — ConsistentHashSpec.Create_must_produce_the_legacy_ring_whenever_the_legacy_algorithm_succeeds — that must still pass. This is what keeps rolling upgrades safe for the common path.
• Option B's collision resolution differs from #8294's in the (rare) collision case. #8294 resolves collisions iteratively (interleaved — a relocation can cascade into bumping an innocent natural vnode). Option B's batch resolution is naturals-first, no-cascade. Both are deterministic and both are byte-identical to today in the no-collision path, but they place the ~10⁻⁷ colliding keys differently. So switching to Option B is a coordinated change for those keys (negligible + self-healing on the next rebuild, but call it out) — or reproduce #8294's cascade if strict bit-identity is required (which throws away the batch elegance; not recommended).
• No public API removal — the SortedDictionary constructor stays.
• Update ConsistentHashCreateBenchmarks with before/after numbers for whichever option is taken.

Recommendation

Ship Option A — most of the practical benefit (retained footprint) at near-zero risk and no collision-code churn. Only pursue Option B if a profiler shows Create CPU or transient GC is a real problem for someone with a very large routee count.

Follow-up to #8031 (the collision-tolerance fix in Create, #8294).