{"issue":{"created_at":"2011-11-12T06:47:03Z","state":"open","updated_at":"2011-11-30T00:20:29Z","comments":6,"user":{"gravatar_id":"8be08911272b9e3d31e71956f205a648","id":486323,"url":"https://api.github.com/users/joecroninallen","avatar_url":"https://secure.gravatar.com/avatar/8be08911272b9e3d31e71956f205a648?d=https://a248.e.akamai.net/assets.github.com%2Fimages%2Fgravatars%2Fgravatar-140.png","login":"joecroninallen"},"body":"I use node-hashring on a Redis environment where I have 128 instances of redis in a sharded environment.  Half of the instances live on one box, and the other half live on the second box.  For some reason, the instances living on the second box seem to be getting twice as much data as the instances on the first box.\r\n\r\nI did not use weights, but it is as if all the instances on the second box had a weight of 2 whereas the instances on the first box had a weight of 1.\r\n\r\nDo you have any explanation as to what might be happening?","assignee":null,"id":2216181,"labels":[],"pull_request":{"patch_url":null,"html_url":null,"diff_url":null},"number":3,"title":"Uneven distribution of shards using node-hashring","html_url":"https://github.com/3rd-Eden/node-hashring/issues/3","closed_at":null,"url":"https://api.github.com/repos/3rd-Eden/node-hashring/issues/3","milestone":null},"action":"created","comment":{"created_at":"2011-11-30T00:20:29Z","updated_at":"2011-11-30T00:20:29Z","user":{"gravatar_id":"c23b8f2aff4d7741b3b10fe9863a65b1","id":225596,"url":"https://api.github.com/users/jstockdale","avatar_url":"https://secure.gravatar.com/avatar/c23b8f2aff4d7741b3b10fe9863a65b1?d=https://a248.e.akamai.net/assets.github.com%2Fimages%2Fgravatars%2Fgravatar-140.png","login":"jstockdale"},"body":"It looks to me like a couple of things are happening here. First, the hash keyspace is getting decimated during the hashing process.\r\n\r\nIn particular, `return CreateHash(this.algorithm).update(key).digest('hex').split('').map(function(v){ return v.charCodeAt(0) })` does not return the hex value of each character in the hash, but rather the character code for that value which is not a compact nor hexadecimal value.\r\n\r\nWhat you actually want there is something like return `+('0x'+v[0])` which takes the first element of v and forces it to be interpreted as a hex string.\r\n\r\nSecondly, the current hashValue function seems wrong, since each element is only a single hex character (a nibble not a byte), so you actually need to read two hex characters for every byte in the hash.\r\n\r\nThis is further complicated by the original Ketema implementation being little endian. So it should be something like:\r\n`(key[31-offset(0)]) |\r\n(key[31-offset(1)] << 4) |\r\n(key[31-offset(2)] << 8) |\r\n(key[31-offset(3)] << 12) |\r\n(key[31-offset(4)] << 16) |\r\n(key[31-offset(5)] << 20) |\r\n(key[31-offset(6)] << 24) |\r\n(key[31-offset(7)] << 28)`\r\n\r\nAnd then the offset function becomes `function(x) { return x + k*8 };`\r\n\r\nThis makes md5 work, and if I got the byte ordering right, then it'll map the same as vanilla libketama.\r\n\r\nAs a side-note, the vnode code is also broken -- you unconditionally override the passed options at `this.options = {vnode_count: 40};` and then the weight code `factor = Math.floor((this.options.vnode_count * len * weight) / totalweight);` should not be dependent on len (that makes each subsequent server get a larger chunk of space as we iterate from 0 to len.\r\n\r\nThat said:\r\n\r\nAfter I fixed all those things, I still had key distribution issues (down to 600 min and 1000 max per server, which isn't terrible). After further investigation the method Ketama uses to decimate the md5 hash to a hash_value is pretty crappy (as the c++ implementations also show this distribution issue). I'm working on a general solution for that and will report back if I make any progress.\r\n\r\nCheers,\r\n\r\n-S","id":2952958,"url":"https://api.github.com/repos/3rd-Eden/node-hashring/issues/comments/2952958"}}