apache / apache/pekko

ConsistentHash silently drops virtual nodes on hash collisions

Open
#3,279 2 comments 0 reactions 0 assignees View on GitHub
bug
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.