Rest Term

Consistent Hashing in AS3

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

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

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

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

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

Consistent Hashing - wonderfl build flash online

あわせて読む:

 

Tags: , ,

Comments

No comments so far.

  • Leave a Reply
     
    Your gravatar
    Your Name