akkadotnet/akka.net

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

Open

#8,293 建立於 2026年7月1日

在 GitHub 查看
 (0 留言) (0 反應) (0 負責人)C# (1,035 fork)batch import
help wantedperf

倉庫指標

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

貢獻者指南