Consistent Hashing for Fun and Profit

With David Banham

Centralised system

Distributed system

We have some nodes...

[
    {
        "hostName": "one"
    },
    {
        "hostName": "two"
    },
    {
        "hostName": "three"
    },
    {
        "hostName": "four"
    },
    {
        "hostName": "five"
    },
]
          

First hash them

hashes = jobs.map(function(job) {
  return md5(job);
});
[ "6ecf35e7a633be3aa565ba87a3c6b8e3" ]
          

Now turn that hash into a number

nums = hashes.map(function(hash) {

  num = 0
  for ( var i = 0 ; i < hash.length ; i++ ) {
    num += hash.charCodeAt(i)
  }
  return num

});
[ 2386 ]
          

Now turn that number into an angle

var sub360 = function(num) {
  if (num < 360) return num;
  num = num - 360;
  return sub360(num);
};

angles = nums.map(sub360);

[ 184 ]
          

Now we have a ring!

We have some jobs...

[
    {
        "job": "Threatening Oryx"
    },
    {
        "job": "Super Yak"
    },
    {
        "job": "Statuesque Koala"
    },
    {
        "job": "Sudden Dolphin"
    },
    {
        "job": "Stormy Cobra"
    },
]
          

First hash them

hashes = jobs.map(function(job) {
  return md5(job);
});
[ "ab9d82b9ae7d7d7256a95efe3447ec78" ]
          

Now turn that hash into a number

nums = hashes.map(function(hash) {

  num = 0
  for ( var i = 0 ; i < hash.length ; i++ ) {
    num += hash.charCodeAt i
  }
  return num

});
[ 2365 ]
          

Now turn that number into an angle

var sub360 = function(num) {
  if (num < 360) return num;
  num = num - 360;
  return sub360(num);
};

angles = nums.map(sub360);

[ 205 ]
          

Now we add them to the ring.

Randomness is not evenly distributed

var adjustHash = function(targetNode, nodes, job) {
  var matchingNode = findMatchingNode(nodes, job)

  if (targetNode === matchingNode) return job

  job = job + 1

  return adjustHash(targetNode, nodes, job)
};
          

Balanced!

Rebalanced!

Pretty colours!

More information