Consistent Hashing

Consistent Hashing implementation

see also:
  http://rest-term.com/archives/2902/

by wellflat 26 Jun 2011

Embed

/**
 * Copyright wellflat ( http://wonderfl.net/user/wellflat )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/7BDF
 */

package {
  import flash.display.Graphics;
  import flash.display.Sprite;
  import flash.text.TextField;
  import flash.text.TextFormat;
  
  [SWF(width="465", height="465", backgroundColor="#000000")]
  
  public class Main extends Sprite {
    private var nodes:Vector.<String>;
    private var hash:ConsistentHash;
    private var hist:Object;
    private var num:uint = 40;
    private var replicas:uint = 150;
    private var tf:TextField;
        
    public function Main():void {
      p("*** Consistent Hashing Implementation ***\n");
      nodes = new <String>['node_01', 'node_02', 'node_03', 'node_04'];
      hash = new ConsistentHash(nodes.slice(0, 3), replicas);
      hist = {'node_01':[], 'node_02':[], 'node_03':[], 'node_04':[]};
      p('number of replicas: ' + replicas);
      p('key: [1..' + num + "]\n");
      p('node list: ' + hash.toString());
      createHist();
      p("\nadd node: " + nodes[3]);
      hash.add(nodes[3]);
      p('node list: ' + hash.toString());
      createHist();
      p("\nremove node: " + nodes[0]);
      hash.remove(nodes[0]);
      p('node list: ' + hash.toString());
      createHist();
    }
    private function createHist():void {
      var text:String, len:uint;
      for each(var bin:Array in hist) {
        bin.length = 0;
      }
      for(var i:int = 0; i < num; i++) {
        hist[hash.get(i.toString())].push(i);
      }
      for each(var node:String in nodes) {
        len = hist[node].length;
        text = '  ' + node;
        if(0 < len && len < 10) {
          p(text + ' ( ' + len + ' keys): ' + hist[node]);
        }else if(len >= 10) {
          p(text + ' (' + len + ' keys): ' + hist[node]);
        }else {
          p(text + ' ( ' + len + ' keys): unknown node');
        }
      }
    }
    private function p(str:String):void {
      if(!tf) {
        var g:Graphics = this.graphics;
        g.beginFill(0x000000);
        g.drawRect(0, 0, stage.stageWidth, stage.stageHeight);
        g.endFill();
        tf = new TextField();
        tf.x = 10;
        tf.y = 20;
        tf.width = tf.height = 465;
        tf.defaultTextFormat = new TextFormat('Courier New', 12, 0x00ff66, true);
        addChild(tf);
      }
      tf.appendText(str + "\n");
    }
  }
}


  import com.adobe.crypto.MD5;
  import flash.utils.Dictionary;

  class ConsistentHash {
    private var ring:Dictionary;
    private var nodes:Vector.<String>;
    private var keys:Vector.<String>;
    private var replicas:uint; // indicates how many virtual points should be used per node
    
    public function ConsistentHash(nodes:Vector.<String>, replicas:uint = 160) {
      this.ring = new Dictionary();
      this.nodes = new Vector.<String>();
      this.keys = new Vector.<String>();
      this.replicas = replicas;
      for each(var node:String in nodes) {
        add(node);
      }
    }
    public function toString():String {
      return '[' + nodes.join(', ') + ']';
    }
    // Gets the node in the Hash Ring for this key.
    public function get(key:String):String {
      if(nodes.length == 0) return null;
      var i:uint = search(keys, MD5.hash(key));
      return ring[keys[i]];
    }
    // Adds the node to the Hash Ring (including a number of replicas).
    public function add(node:String):void {
      nodes.push(node);
      for(var i:int = 0; i < replicas; i++) {
        var key:String = MD5.hash(node + ':' + i);
        ring[key] = node;
        keys.push(key);
      }
      keys.sort(compare);
    }
    // Removes the node from the Hash Ring.
    public function remove(node:String):void {
      nodes = nodes.filter(
        function(item:String, i:uint, v:Vector.<String>):Boolean {
          return item != node;
        }
      );
      for(var i:int = 0; i < replicas; i++) {
        var key:String = MD5.hash(node + ':' + i);
        delete ring[key];
        keys = keys.filter(
          function(item:String, i:uint, v:Vector.<String>):Boolean {
            return item != key;  
          }
        );
        keys.sort(compare);
      }
    }
    // Finds the closest index in the Hash Ring with value <= the given value
    // using Binary Search algorithm O(logn) .
    private function search(nodes:Vector.<String>, value:String):uint {
      var head:int = 0, tail:int = nodes.length - 1;
      while(head <= tail) {
        var i:int = int((head + tail)/2);
        var c:int = compare(nodes[i], value);
        if(c == 0)     return i;
        else if(c > 0) tail = i - 1;
        else           head = i + 1;
      }
      if(tail < 0) tail = nodes.length - 1;
      return tail;
    }
    private function compare(a:String, b:String):int {
      return a > b ? 1 : a < b ? -1 : 0;
    }
  }