search

mgalushka / spymemcached

Automatically exported from code.google.com/p/spymemcached
0 stars 0 forks source link

Possible subtle weighting bias on hash misses in the KetamaNodeLocator #243

Closed GoogleCodeExporter closed 9 years ago

GoogleCodeExporter commented 9 years ago 
What version of the product are you using? On what operating system?

2.4rc1, windows

Tell me more...

This is really a cross-post of this issue on 
https://github.com/enyim/EnyimMemcached/issues/100

Not really sure if it is a bug particularly, but I *think* the implementation 
of KetamaNodeLocator#getNodeForKey has a bias towards towards choosing the 
*first* server key for certain hashes.  

To be a (little) clearer if the passed key's hash is smaller than than all the 
recorded server hashes then TreeMap#tailMap() returns a map of *all* the nodes 
and the 'firstKey' is chosen.  However if the passed key's hash is bigger than 
all the recorded server hashes then TreeMap#tailMap() returns no entries, in 
this scenario ketamaNodes.firstKey() is used (which will again be the same [I 
think] node as was returned in the other case.

So (if this is correct) for all low key misses and for all high key misses the 
same (first) server key will be returned. I am (perhaps unfairly?) assuming a 
uniform distribution of keys, which in turn should result in a uniform 
distribution of hash misses (both high and low) but currently they will not be 
uniformly distributed between the first and last servers.

 (FWIW This is using the FNV1A hashing algorithm which quite possibly is the route of my 'issue' ;) )

Original issue reported on code.google.com by ciar...@gmail.com on 20 Mar 2012 at 10:30

GoogleCodeExporter commented 9 years ago 
Hmm, I see the problem is rather more complicated than just 'choosing the last 
server',  I hadn't read the implementation of the Iterator previously.

Original comment by ciar...@gmail.com on 20 Mar 2012 at 10:53

GoogleCodeExporter commented 9 years ago 
The common thing to do is to use ketama hashing.  I believe, from internal 
tests that verify compatibility with libketama, that we're doing things 
correctly.  I'm glad to look further into things, but it seems you may have 
discovered what was different.

Please let me know if this needs reopening.

Original comment by ingen...@gmail.com on 19 Apr 2012 at 6:07