Consistent Hashing in AS3

前回のエントリー「Redis AS3クライアント」に関連して、キーの分散処理を行うために Consistent Hashing をAS3で書いてみました。イマドキのNoSQLデータベース(MongoDBなどshardingで分散するもの以外)クライアントならだいたい実装されているアルゴリズムですね。

理論の説明は以下のサイトなどを参考に。
Consistent Hashing
スマートな分散で快適キャッシュライフ

* Consistent Hashing implementation in AS3
ハッシュ関数: MD5
ノード探索: 二分探索
仮想ノード利用 (libmemcachedの実装に合わせてデフォルトの仮想ノード数は160)

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

  public class ConsistentHash {
    private var ring:Dictionary;
    private var nodes:Vector.<String>;
    private var keys:Vector.<String>;
    private var replicas:uint;
    
    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;
    }
  }
}

package {

import com.adobe.crypto.MD5;

import flash.utils.Dictionary;

public class ConsistentHash {

private var ring:Dictionary;

private var nodes:Vector.<String>;

private var keys:Vector.<String>;

private var replicas:uint;

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;

}

JavaだとTreeMapとかあるから実装は楽ですけど、AS3は表示系以外のコアがけっこう弱いのでめんどくさいですね。。ハッシュ関数はいろいろ選択肢がありますが、ここではMD5を採用しました。ただし、各種ハッシュ関数もやはりAS3コアには含まれていないので as3corelib を利用しました。

テストコードはwonderflに投稿しておきました。仮想ノード数は100~200あたりで設定するといい感じに分散するようです。また、ノードの追加/削除があってもキーの再配置が少なく抑えられていることがわかります。

Consistent Hashing - wonderfl build flash online

あわせて読む:

Tags: actionscript, algorithm, database

Rest Term

Consistent Hashing in AS3

あわせて読む:

Comments