ConsistentHash silently drops virtual nodes on hash collisions

[He-Pin]

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:

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:

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:

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.

[He-Pin]

https://github.com/RJ/ketama

[pjfanning]

https://github.com/jinoos/ketama-java is BSD licensed which means we could copy/paste that code if we need it, with proper attribution in our license. RJ/ketama is LGPL licensed so we can't copy its code.