微酔半壊

※本記事は当初HTMLに整形せずに掲載してしまい、ご覧になった方にはご不便をおかけしました。お詫び申し上げます。

consistent hashingの記事でmemcachedが名前だけ出てきたので少し調べてみた。

memcachedは単純なキーと値のペアによる分散キャッシュサーバ。高速で、非常に台数にスケールすることが利点という。ほとんど設定いらずでインストールしてそのまま起動できる。

動的に生成するウェブページのキャッシュ等に用いられる。キャッシュの他HTTPのセッション情報のような消えてしまっても致命的でない情報の保持に使われることもある。検索してみると国内でもmixiやはてな等で広く使われているようだ。各種言語のクライアントライブラリも多い。

Tom White's Blog: Consistent Hashing(翻訳: ConsistentHashing - コンシステント・ハッシュ法)でconsistent hashingというアルゴリズムを知った。大略こういうことらしい。

問題

複数台のキャッシュサーバがあり、オブジェクトのキャッシュをどのサーバに配置するかを決めたい。

普通のハッシュ利用法だとどうなるか

オブジェクトのハッシュ値 mod N (Nはキャッシュサーバの台数)で決める。

しかし、これではキャッシュサーバを追加したり削除したりすると全てのオブジェクトのキャッシュ配置先が変わってしまう。

望ましいのは

キャッシュサーバを追加すれば既存のサーバから少しずつ分担が新しいサーバに移動し、キャッシュサーバが取り除かれれば残りのサーバに負担が分散、それ以外のオブジェクトのキャッシュ先は変わらない、というのがよい。

Consistent Hashingとは

キャッシュサーバを決めるのに、mod Nをしない。つまりサーバの台数に依存した計算をしない。しかしそれでどうやってキャッシュサーバを決定するのだろうか。

表題の書籍を読んだ。

An Introduction to Kernel Hacking との副題の通り、悪いことをするための本というよりはそれをネタにしたFreeBSDカーネルへのいざないという感じの本。以下に紹介するようにカーネルコードに密着した話題だけが扱われている。

カーネルのソースコードに手を出してみたい気持ちはあるものの、難しそうだとか先に知らないといけない事が多そうで敷居が高そうだと感じて先へ進めない読者(筆者のことです)のハードルを下げるには丁度具合のいい本だと思う。130ページ程度と薄く、考え込むほど難しいところもなく(5章は例外)気軽に読めた。

内容は次のよう。トピック毎に内容に即した短いプログラムが提示されていて、自分で実際に試してみることができるのは非常に大きい。ただしどこか間違えると大体リブートする破目になるので、qemu上に環境を作って試す方がいい(特に5章以降)。 下心なくとも、ルートがあればこんなことも可能なのかというだけでも単純に面白い。

この本はほぼ唯一といっていいgarbage collectionの教科書。初歩的なアルゴリズムから並列GCまで幅広く、複数のアルゴリズムがあるものはそれぞれ解説して利点欠点も比較している。

Garbage Collection: Algorithms for Automatic Dynamic Memory Management

posted with amazlet on 07.04.04

Richard Jones Rafael Lins
John Wiley & Sons Ltd (Import) (1996/07/12)
売り上げランキング: 3600

おすすめ度の平均:

よくまとまっていて分かりやすい

Amazon.co.jp で詳細を見る

米Amazon.comのページを見たい方はこちら。当然ながらカスタマーレビューが日本のアマゾンより多い。

なまじ良く書かれているだけに、Amazonの太っ腹機能「なか見!検索」(検索した単語のある周辺のページを立ち読みさせてくれる)がかなり便利に使える。アルゴリズム名などで検索するのがお勧め。検索して出てきたところから2〜3ぺージも読めば用が足りることも多い。

例えば、マルチスレッド・プログラム用のGC (concurrent GC)としてTreadmillという方式がある。 これで検索すると p.188, p.218, p.219, p.220, p.221, p.225 が出てくる。これはもう明らかに、p.218〜221辺りを読めばいいわけだ。案の定、p.218をクリックすると、そこから「8.8 Baker's Treadmill collector」という節が始まっている。

目次も詳しい。そのおかげで、検索のアタリをつけるのも簡単。いいんだか悪いんだか。

※目次などを除いて、「なか見!検索」で出てきた本文中のページを立ち読みするにはアマゾンのアカウントでログインしていることが必要。ページをクリックして「この機能は利用できません」のように表示されたら、おそらくアカウントでログインしていないことが原因です。

前回の記事ではcopying GCを取り上げた。今回はその続きとしてcopying GCに対する改良を2つ取り上げる。

2つはそれぞれcopying GCの短所、つまり「毎回全てのオブジェクトがコピーされること」「確保したメモリの半分しかプログラムで利用できないこと」に対応している。

大きい、または長命なオブジェクトの別扱い

copying GCは生き残るオブジェクトを毎回全てコピーするので、オブジェクトが短命でかつ小さい程都合がよい。裏を返すとオブジェクトが大きかったり長命だとコストが嵩む。

そこで、そのようなオブジェクトは別領域にとりmark & sweepで管理することにして、copying GCの対象からは外してしまう。

アルゴリズム

コンパクションの際に、ポインタがmark & sweepで管理されるオブジェクトを指す場合はマークも同時に行う。

ポインタのとりえる値は次の3種類に分けられる。

1. from-spaceにあるコピー前のオブジェクトを指す場合
2. from-spaceを指すがオブジェクトは既にコピーされていた場合
3. mark & sweepで管理するオブジェクトを指す場合

それぞれに応じて処理は次のようになる。

• from-space内のコピー前のオブジェクトを指す場合:
  1. to-spaceにコピー、freeポインタを進める
  2. forwarding pointerを記録
  3. ポインタを更新
• from-space内を指すがオブジェクトが既にコピー済の場合:
  1. ポインタを更新
• mark & sweep対象のオブジェクトを指す場合:
  1. そのオブジェクトをマークし、オブジェクト内のポインタを再帰的に処理。

ポインタの種類も3種類、ルートポインタ、to-spaceにコピーされたオブジェクト内のポインタ、markされたオブジェクト内のポインタ、とあるが、どの場合も処理は同じになる。

マークを兼ねたコンパクションが終わったら、mark & sweepの領域の回収処理を行う。