Perf: build ConsistentHash ring into sorted arrays instead of retaining a SortedDictionary
#8,293 创建于 2026年7月1日
仓库指标
- Star
- (4,543 star)
- PR 合并指标
- (平均合并 2天 21小时) (30 天内合并 32 个 PR)
描述
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
NodeForidentical (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.