Bday problem / hash collisions on Akka.Routing.ConsistentHash :: Create

[abeltsios]

Version Information
Version of Akka.NET? "1.5.40"
Which Akka.NET Modules? Core Akka.Net, ConsistentHashingPool

Describe the bug
When creating routees in ConsistentHashingPool, the aforementioned routees are "spread" by utilizing MurmurHash into a sorted dictionary.
Murmurhash has a key-space of 32bits. This implies a 50% probability of hash collision with roughly 70k routes count, though it may happen with way fewer.
(In our case in happened with 17 hashring nodes)

To Reproduce
Steps to reproduce the behavior:

public class ConsistentHashingPool_BDay : TestKit
{
    public class SampleActor : ReceiveActor
    {
        public SampleActor()
        {
            Receive<string>(msg => Sender.Tell(msg));
        }
    }

    [Fact]
    public async Task Test1()
    {
        var actor = Sys.ActorOf(Props.Create(() => new SampleActor()).WithRouter(new ConsistentHashingPool(100_000, (msg => msg.GetHashCode()))),
            "sampleActor");

        var req = "req";
        await Assert.ThrowsAnyAsync<Exception>(async () => await actor.Ask<string>(req, TimeSpan.FromSeconds(10)));
    }
}

Links to working reproductions on Github / Gitlab are very much appreciated

Expected behavior
Route pool should be successfully created

Actual behavior
from logs: [WARNING][01-26-2026 08:42:36.260Z][Thread 0019][ConsistentHashingRoutingLogic (akka://test)] Couldn't route message with consistent hash key [System.Byte[]] due to [An item with the same key has already been added. Key: [-1475268499, akka://test/user/sampleActor/$k~c]]

The above most probably has to do with the ConsistentHash:: Create that utilizes a SortedDictionary
Hash collisions happen there and they are unhandled (as SortedDictionary :: Add throws on duplicate key)

Environment
Are you running on Linux? Windows? Docker? Which version of .NET?
Windows 11 locally, Linux in prod. net80

Additional context
calculation are done via https://www.bdayprob.com/

[Aaronontheweb]

@abeltsios I've wanted to upgrade to a 64 bit version of Murmur hash for years but it's just never been a priority - probably much easier to do that now with either LLM help or third-party libraries (we generally won't do third party dependencies in core Akka though.)

Back in 2013/14 when I wrote our original Mumur3 hash function, I had to translate it from the canonical C++ implementation from its white paper. Good times.

Tricky part is: we can't easily change the hash function in a minor patch version of Akka.NET because it will constitute a breaking behavioral change for Akka.Cluster.Sharding:

akka.net/src/contrib/cluster/Akka.Cluster.Sharding/ClusterSharding.cs

Lines 189 to 193 in 99d7ea7

	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public virtual ShardId ShardId(string entityId, Msg? messageHint = null)
	{
	return _cachedIds[(Math.Abs(MurmurHash.StringHash(entityId)) % MaxNumberOfShards)];
	}

so if we were to change the output size / return value of the function, that'd need to go into v1.6.

[abeltsios]

My take on the matter:
by changing the hash function you just minimize (not eradicate) the probability from 50% in 7000000 to 50% in 4billion (still not zero)

I would just change the way the routees key is calculating (eg by spreading those even among int.MinValue / int.MaxValue)
Then hash the request (as it currently happens) and by utilizing Array.BinarySearch find the closest routee (effectively rule out the sorted set)

Hopefully I can submit (sooner or later) a PR for you to check if you are ok with the approach
(this might also provide a more fair distribution among routees)

[Aaronontheweb]

@abeltsios sounds good - here's a LINQPad script I wrote (for a YouTube video) that can be used to visualize the fairness / distribution of the Murmur3 has function if you want to use it https://gist.github.com/Aaronontheweb/13251d255c0f1e722b4704800aa53ff9

[to11mtm]

I think getting rid or being extra careful in use of SortedSet is the right call, I will note that Before/After benchmarks of routing performance will be fairly important here; both because we want to try to avoid regressions and also because looking at the way the existing set is implemented, there are definitely opportunities to improve performance and lower allocations on lookup/etc....