Distribution is not uniform

[paulmach]

Please see strava/go.serversets#7 for more details. That library uses a vendored version of this consistent hash library. What I'm seeing is a distribution like:

  58856 - 10.0.16.69:11211
  18389 - 10.0.22.188:11211
  22755 - 10.0.26.214:11211

(count - server for 10k random strings)

This uneven distribution is what we're seeing in production so I don't think it's an issue with the random key generation. Have you guys encountered this before? Am I using the code wrong?

[andyxning]

I run into this situation also, i think the crc32 hash algorithm is not suitable to be used to distribute keys.

[Ewan-GrandSlam]

I see something similar, two of 3 instances appear to be relatively even and as soon as you add a third it gets very uneven

[jian-en]

I come with the same problem. maybe the hash returns a uint32 key. the space is not big enough? I am not sure.

[saswatp]

+1 Same issue.

[dawei101]

+1

[mikegleasonjr]

Increase the replicas (ie.: 100)

[andyxning]

Increase the replicas (ie.: 100)

This can just decrease the in-balance but can not resolve it completely.

[mikegleasonjr]

Increase the replicas (ie.: 100)

This can just decrease the in-balance but can not resolve it completely.

I don't think we can achieve perfect balance..

I am using another library, but using a replicas of 100 coupled with the fnv32a hash gives me pretty uniform results...

[andyxning]

@mikegleasonjr

I don't think we can achieve perfect balance..
I am using another library, but using a replicas of 100 coupled with the fnv32a hash gives me pretty uniform results...

I agree. fnv32a is a pretty good hash function for use in consistent hash for its uniform distribution.

[patrickxb]

I added an option to use fnv32a: UseFnv.

    x := New()
    x.UseFnv = true
    x.Add("abcdefg")
    x.Add("hijklmn")
    x.Add("opqrstu")

There are some tests that show it has a more uniform distribution.

[chasememeda]

still not uniformly distributed.... and it differs A LOT when different elements are added, which is very confusing...... // why the name of elements will influence the result so much???

I finally solved the problem with the solution from this: strava/go.serversets@cb6a0bf

[jiangz222]

Since this repo is not maintained?
Make a progress in my repo
Support custom hash function, and use Murmur3 to make distribution more uniform.