[B! memcached][algorithm] dannのブックマーク

dann id:dann

memcachedとalgorithmに関するdannのブックマーク (2)

Consistent Hashing
Tom White's Blog: Consistent Hashing(翻訳: ConsistentHashing - コンシステント・ハッシュ法)でconsistent hashingというアルゴリズムを知った。大略こういうことらしい。問題複数台のキャッシュサーバがあり、オブジェクトのキャッシュをどのサーバに配置するかを決めたい。普通のハッシュ利用法だとどうなるかオブジェクトのハッシュ値 mod N (Nはキャッシュサーバの台数)で決める。しかし、これではキャッシュサーバを追加したり削除したりすると全てのオブジェクトのキャッシュ配置先が変わってしまう。望ましいのはキャッシュサーバを追加すれば既存のサーバから少しずつ分担が新しいサーバに移動し、キャッシュサーバが取り除かれれば残りのサーバに負担が分散、それ以外のオブジェクトのキャッシュ先は変わらない、というのがよい。 Con
dann 2008/06/11
memcached

algorithm
リンク
Consistent Hashing を試す
Consistent Hashing は、複数のノードにレコードを分散させる方法として、 Amazon Dynamo や Cache::Memcached::Fast などで使われているアルゴリズムです。この文章では、Perl で実際に Consistent Hashing を実装し、その特徴を理解することを目的とします。更新履歴 2008-06-01: 公開サーバー台数で割った余り (mod) を使用するまず Consistent Hashing と比較するために、レコードに対して整数のハッシュ値を求め、ハッシュ値をノード数で割った余り (mod) で、ノードを選択するという方法を書いてみます。ここでは、ハッシュ値の算出に CRC (Cyclic Redundancy Check) を使用しています。 use strict; use String::CRC; use Pe
dann 2008/06/03
algorithm

consistenthashing

memcached
リンク
1