ConsistentHash silently drops virtual nodes on hash collisions
- Dominant language
- Scala
- Stars
- 1.6k
- Forks
- 211
- Avg merge
- 1d 6h
- Merged PRs (30d)
- 89
Description
## Summary
`org.apache.pekko.routing.ConsistentHash` stores ring points in an `immutable.SortedMap[Int, T]`. If two different virtual nodes produce the same 32-bit ring hash, the later `(hash -> node)` entry overwrites the earlier one. This silently drops virtual nodes and can make routing depend on construction order.
Observed on `main` at `26c5086c7c`.
## Code evidence
- `ConsistentHash.apply` builds the ring with `immutable.SortedMap.empty[Int, T] ++ (...)`: `actor/src/main/scala/org/apache/pekko/routing/ConsistentHash.scala` lines 125-133.
- `:+` adds virtual nodes with `nodes ++ (...)`: `actor/src/main/scala/org/apache/pekko/routing/ConsistentHash.scala` lines 49-54.
- `:-` removes virtual nodes with `nodes -- (...)`: `actor/src/main/scala/org/apache/pekko/routing/ConsistentHash.scala` lines 69-74.
`SortedMap` cannot hold duplicate `Int` keys, so a ring-point collision is last-write-wins rather than preserving both virtual nodes.
## Reproducer
From the repo root, this uses the current Pekko `MurmurHash` and `ConsistentHash` implementations and two node names with known virtual-node collisions:
```scala
import org.apache.pekko.routing.ConsistentHash
val a = "node-4230"
val b = "node-14323"
def arrays(ch: ConsistentHash[String]) = {
val hf = ch.getClass.getDeclaredField("nodeHashRing")
hf.setAccessible(true)
val nf = ch.getClass.getDeclaredField("nodeRing")
nf.setAccessible(true)
(hf.get(ch).asInstanceOf[Array[Int]], nf.get(ch).asInstanceOf[Array[String]])
}
def counts(ch: ConsistentHash[String]) =
arrays(ch)._2.groupBy(identity).view.mapValues(_.length).toMap
val ab = ConsistentHash(Seq(a, b), 10)
val ba = ConsistentHash(Seq(b, a), 10)
println(s"ab size=${arrays(ab)._1.length}, counts=${counts(ab)}")
println(s"ba size=${arrays(ba)._1.length}, counts=${counts(ba)}")
println(s"after removing a from ab: size=${arrays(ab :- a)._1.length}, counts=${counts(ab :- a)}")
println(s"key-3: ab=${ab.nodeFor(\"key-3\")}, ba=${ba.nodeFor(\"key-3\")}")
```
I ran this with:
```bash
scala-cli --server=false -S 2.13.16 \
actor/src/main/scala/org/apache/pekko/routing/MurmurHash.scala \
actor/src/main/scala/org/apache/pekko/routing/ConsistentHash.scala \
-e ''
```
Output:
```text
ab size=18, counts=Map(node-4230 -> 8, node-14323 -> 10)
ba size=18, counts=Map(node-4230 -> 10, node-14323 -> 8)
after removing a from ab: size=8, counts=Map(node-14323 -> 8)
key-3: ab=node-14323, ba=node-4230
```
Expected ring points for 2 nodes with `virtualNodesFactor = 10` is 20. The current implementation has 18 because these nodes collide at two virtual-node hashes.
## Impact
- Virtual nodes can be silently lost, skewing distribution.
- If construction order differs for the same logical node set, collided virtual nodes can be assigned to different owners, producing different routing results.
- Incremental removal can remove a collided hash point currently owned by another node, as shown by `ab :- a` leaving `node-14323` with 8 virtual nodes instead of 10.
Call sites include:
- classic `ConsistentHashingRoutingLogic`: `actor/src/main/scala/org/apache/pekko/routing/ConsistentHashing.scala` line 219
- typed `RoutingLogics.ConsistentHashingLogic`: `actor-typed/src/main/scala/org/apache/pekko/actor/typed/internal/routing/RoutingLogic.scala` lines 107 and 113-114
- cluster client `ClusterReceptionist`: `cluster-tools/src/main/scala/org/apache/pekko/cluster/client/ClusterClient.scala` lines 981 and 1061-1074
## Probability
Approximate probability of at least one 32-bit ring-point collision is:
`P ~= 1 - exp(-n * (n - 1) / (2 * 2^32))`, where `n = nodes * virtualNodesFactor`.
Examples:
| Ring points | Collision probability |
| ---: | ---: |
| 1,000 | 0.0116% |
| 5,000 | 0.2906% |
| 20,000 | 4.55% |
| 50,000 | 25.25% |
| 100,000 | 68.78% |
## Possible fix direction
A compatibility-preserving fix should probably keep the no-collision ring unchanged, and only resolve collisions deterministically. Options include:
- deterministic linear probing to the next free `Int` ring position;
- storing per-hash buckets instead of a single owner;
- using a Ketama-style continuum implementation, if it preserves existing compatibility expectations or is introduced behind an explicit compatibility boundary.
Tests should cover:
- known colliding nodes still produce `nodes * virtualNodesFactor` ring points;
- constructing the same logical node set in different orders is deterministic;
- removing one node does not remove collided virtual nodes belonging to another node.
Contributor guide
Research direction
Start in actor/src/main/scala/org/apache/pekko/routing/ConsistentHash.scala, especially apply, :+, and :-, and run the supplied scala-cli reproducer with the cited MurmurHash implementation. Compare the collision behavior against the proposed compatibility constraints, then add coverage for full virtual-node counts, order-independent construction, and safe removal of a collided node.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- scala
- Domain
- distributed-systems
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 48/100