akkadotnet/akka.net

Perf: build ConsistentHash ring into sorted arrays instead of retaining a SortedDictionary

Open

#8,293 opened on Jul 1, 2026

View on GitHub
 (0 comments) (0 reactions) (0 assignees)C# (1,035 forks)batch import
help wantedperf

Repository metrics

Stars
 (4,543 stars)
PR merge metrics
 (Avg merge 2d 21h) (32 merged PRs in 30d)

Description

Background

ConsistentHash<T> (src/core/Akka/Routing/ConsistentHash.cs) stores the ring in a SortedDictionary<int, T> _nodes and also lazily materializes parallel int[] / T[] arrays (RingTuple) that back the Array.BinarySearch in NodeFor.

For rings built via ConsistentHash.Create<T>(...) — which is what ConsistentHashingRoutingLogic uses — the SortedDictionary is only needed after construction by operator + / operator -, which the routers never call. So once the lookup arrays are built, the tree is retained dead weight.

Cost

Each SortedDictionary entry is a heap-allocated red-black-tree node (~56 bytes on 64-bit: object header + KeyValuePair<int,T> + Left/Right pointers + color). At large ring sizes this dominates allocation:

routees × virtual-nodes-factor ring points Create allocated
1000 × 10 10,000 ~2.6 ms ~575 KB
5000 × 10 50,000 ~17.9 ms ~2.9 MB

(~2.8 MB of the 2.9 MB is the 50,000 tree nodes.) The tree is also rebalanced on every insert during construction and, for Create-based rings, retained for the ring's lifetime on top of the lookup arrays.

Proposal

Build the ring directly into pre-sized, sorted int[] / T[] arrays: materialize the (key, node) pairs, sort once, resolve collisions (the linear-probe added in #8031), and fill the arrays — skipping the SortedDictionary entirely for the Create path. This:

  • drops the retained tree (~2.8 MB at 50k points) for Create-based rings,
  • avoids per-insert red-black rebalancing during construction,
  • keeps NodeFor identical (same sorted arrays + BinarySearch).

operator + / operator - can keep their own path or rebuild from the arrays.

Constraints

Correctness-neutral refactor — it must preserve the exact ring Create produces today (there is a byte-identical before/after proof in ConsistentHashSpec.Create_must_produce_the_legacy_ring_whenever_the_legacy_algorithm_succeeds) and cross-node determinism. Add before/after allocation + throughput benchmarks to ConsistentHashCreateBenchmarks.

Follow-up performance opportunity noticed while fixing #8031.

Contributor guide