mixi Engineers’ Blog » スマートな分散で快適キャッシュライフ
今日は以前のエントリーで書くと述べたConsistent Hashingに関して語らせて頂こうかと思います。ただしConsistent Hashingはセミナーやカンファレンスなどでかなり語られていると思いますので、コンセプトに関しては深入りせず、実用性に着目したいと思います。 問題定義 分散されたキャッシュ環境において、典型的なレコードを適切なノードに格納するソリューションはkeyのハッシュ値に対しmodulo演算を行い、その結果を基にノードを選出する事です。ただし、このソリューションはいうまでもなく、ノード数が変わるとキャッシュミスの嵐が生じます。つまり実世界のソリューションとしては力不足です。 ウェブサイトのキャッシュシステムの基本はキャッシュがヒットしなかったらデータベースにリクエストを発行し、レコードが存在したらキャッシュしてクライエントに返すという流れです。ここで問題なのが一瞬
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
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
