前回のエントリー「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.
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.
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.
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.
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