He-Pin opened a new issue, #3279:
URL: https://github.com/apache/pekko/issues/3279
## 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 '<snippet above>'
```
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.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
