Consistent Hashing in AS3

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

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

* Consistent Hashing implementation in AS3
ハッシュ関数: MD5
ノード探索: 二分探索
仮想ノード利用 (libmemcachedの実装に合わせてデフォルトの仮想ノード数は160)
[as]
package {
import com.adobe.crypto.MD5;
import flash.utils.Dictionary;

public class ConsistentHash {
private var ring:Dictionary;
private var nodes:Vector.;
private var keys:Vector.;
private var replicas:uint;

public function ConsistentHash(nodes:Vector., replicas:uint = 160) {
this.ring = new Dictionary();
this.nodes = new Vector.();
this.keys = new Vector.();
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.):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.):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., 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; } } } [/as] JavaだとTreeMapとかあるから実装は楽ですけど、AS3は表示系以外のコアがけっこう弱いのでめんどくさいですね。。ハッシュ関数はいろいろ選択肢がありますが、ここではMD5を採用しました。ただし、各種ハッシュ関数もやはりAS3コアには含まれていないので as3corelib を利用しました。

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

Consistent Hashing – wonderfl build flash online

あわせて読む:

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です