aws memo

AWS関連の備忘録 (※本ブログの内容は個人的見解であり、所属組織及び企業の意見を代弁するものではありません。１年以上古いエントリは疑ってかかってください)

Amazon ElastiCache の分散方法

memcachedを知り尽くす：第4回　memcachedの分散アルゴリズム｜gihyo.jpを参考

ElastiCache/Memcached分散の大方針

  • 必要に応じてクライアント/アプリ側で分散させる。サーバ同士で何かすることは無い
  • 分散ロジックは色々。基本はキーのハッシュ値をサーバ台数でmodしてシャーディング、凝るならConsistent hashingにする
  • ノード追加、削除時のことを考える
  • ノード障害で落ちた時、ノード交換でキャッシュがクリアされた時のことを考える

ノードのスケールアウト、障害を考えると面倒だけどConsistent Hashingを使うべき。 AWSブログでも書かれている。

また、障害時のペナルティ（DBに負荷が移る）を緩和するには、大容量メモリのノードを少数用意するより、少ないメモリのノードを多数並べたほうが良いことになる。ここはコストも考える。

なぜConsistent hasingか？

単純にシャーディングするなら、キーoのハッシュ値hash(o)をノード数nでmodの結果結果のサーバを決定する。

 server = serverlist[hash(o) mod serverlist.length]

ただし、以下の懸念点がある。

  • hash(o)の偏りに起因して、ノードに偏りが出る可能性がある。偏りを制御できない
  • ノード数n変更時は、全ノードのキャッシュがクリアされたのと変わらないヒット率になり、再キャッシュが走る

散らす際に問題が起きにくいhashとして、Consistent hashingが代表的。

Consistent hashingとは？

WikiPedia Consistent hashing

yukiwiki コンシステント・ハッシュ法

mixi Engineer blog スマートな分散で快適キャッシュライフ

David Kargerの資料　Consistent Hashing

肝は、ハッシュ対象のキーoと、キャッシュ(用ノード)に同じハッシュ関数を使うこと(ただし良い関数であること）。hash(o)も、hash(キャッシュノード)も、同一のハッシュ値空間（円周）上のある区間に対応付けられる。その区間は多くのハッシュ値を含んでいる。キャッシュが除去されると、隣接する区間のキャッシュが除去されたキャッシュの区間を引き受け、その他のキャッシュには影響がない。全体としては、再キャッシュのペナルティが最小化される。ノードリストが、ハッシュ値でソートされたマップ(tail map,etc)で保持されていれば、hash(o)から、必要なノードを探索しやすくなる。

MemcachedでのConsistent Hashing

Consistent hashing法をサポートしたmemcachedクライアントとしては Last.fmの Richard Jones氏によるC実装 ketama (libketama)が最初。 Dustin Salling氏によるJava実装もある。 分散ハッシュテーブル実装の Chord、Amazon Dynamoなどでも利用されている。

とりあえず、libmemcachedに、libketamaをプラグインして使うのがいいらしい。

Libketama

PHPで使うことを想定してみる。

» [memcached]consistent hashingの動作とマッピングの互換性手間を惜しまず　http://matano-bros.com/blog/archives/1346

» PHPでmemcachedのconsistent hashingを実現する手間を惜しまず　http://matano-bros.com/blog/archives/1335

必要なのは

  • libmemcached: C実装のmemcachedクライアントライブラリ
  • PECL_memcached: PHP本家がリリースしている,libmemcached用PHPインターフェース
  • libketama : consistent hashingアルゴリズムライブラリ
  • php_ketama: ketamaに同梱のPHP版ketamaインターフェース

手順

Amazon Linux前提。 PHP,SVNなどをインストール

$ sudo yum install subversion  php-devel php-pear gcc make libmemcached　libmemcached-devel php-pecl-memcached　

ketamaを取得、コンパイル、インストール

$ svn co svn://svn.audioscrobbler.net/misc/ketama/
$ cd ketama/libketama
$ make
$ make test #失敗する。
$ sudo make install
$ ls /usr/lib/libketama*
/usr/lib/libketama.so  /usr/lib/libketama.so.1
$ sudo ldconfig #ライブラリを読み込む
$ make test #成功する
$ sudo ../..

2013.07.29 訂正

最近の libmemcachedは、Distribution アルゴリズムとしてモジュロとコンシステントが含まれているので、上記のうようにlibketamaを入れる必要は無さそう。

http://bazaar.launchpad.net/~tangent-trunk/libmemcached/1.2/view/head:/libmemcached/hash.cc

http://www.php.net/manual/ja/memcached.constants.php

PHPから使う場合は、Memcached::OPT_DISTRIBUTION に対して Memcached::OPT_LIBKETAMA_COMPATIBLE を指定しておくとよさそう。

 

 

2013.07.29追記

わかりやすい資料を見つけたので備忘のためリンク

Consistent hash