Saturday, September 12, 2009

Page replacement. 2Q

遠方にあるディスクに対して、SSDを使ったキャッシュを作れないかなと思っていた。

device-mapperを使ったdm-cache
http://users.cis.fiu.edu/~zhaom/dmcache/index.html
なるものがあり、私が欲しいのもこんな感じのものだ。
メインラインにマージはされていないが、このURLを見ると
比較的最近のカーネルに追従しているようだし、LKMLへパッチも送られた形跡がある。

欲しいものには近いのだが、SSDを使う場合、IOサイズを気にする必要がある。今時のRAIDに比べると
SSDのシーケンシャル性能は同等かひょっとすると悪いくらいで、得意なのはランダムREAD。サイズの考慮なしにシーケンシャルREADのデータでランダムREADデータを追い出してしまうとすごく損してしまう。
しかしdm-cacheのアルゴリズムは単純なLRUらしい。だからSSDではうまく行かないことが予想される。


さらに探していると、Rik van Rielのページに、
DmCache
http://kernelnewbies.org/KernelProjects/DmCache
というプロジェクトの説明を見つけた。名前がdm-cacheと似ていてまぎらわしい。
言っていることは大体私の希望どおりで、大きな単位のIOはキャッシュしない、などのアイディアが書いてある。
このプロジェクト、今どうなってるのかなあ。待っていてよいのだろうか。

この説明の中に、2Qというアルゴリズムを使う、と書いてあるのが気になっていた。
聞いたことがなかったが調べてみると、有名なもののようだ。元の論文にあたってみたので、メモを書いておこう。

最近まで全く知らなかったが、データベースの世界ではページ置換のアルゴリズムの研究というものが盛んなようだ(今でも?)。考えてみれば当然でしょうね。いままでデータベースといえばraw diskを自分で管理して、OSのキャッシュなんて使わなかったわけだから。しかし最近のデータベースはファイルサーバの上にデータを置いてしまったりする、という話を聞く。

話がすこし脇道にそれるけど、そういえば、この夏のSan DiegoのUSENIXで聞いた話の中で、もっとも感心したのが、
IBMの人のWriteキャッシュの話だった。

STOW
http://www.usenix.org/events/usenix09/tech/full_papers/gill/gill_html/index.html

同じ人の以前の仕事にやはりWriteキャッシュについての以下のものがあった。
WOW
http://www.usenix.org/events/fast05/tech/gill.html

おなじくIBMのARCはもうちょっと一般にも有名なのかもしれない。
やっている人の名前を見るとそれぞれ関係しあっているようだ。

http://www.usenix.org/events/fast03/tech/megiddo.html
http://www.almaden.ibm.com/cs/people/dmodha/arc-fast.pdf

このへんのものに、比較の対象として2Qが取り上げられている。
SolarisにL2ARCという名前で実装がある。たしかIBMの特許に引っかからないように実装したという
話だったと思う。

DmCacheのページに2Qと書いてあるのは特許の問題があるからなのだろう。


2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm
Theodore Johnson, Dennis Shasha

http://portal.acm.org/citation.cfm?id=672996

1994のVery Large Data Basesの論文。
著者のDennis Shashaの方は、「サイエンティフィックアメリカン」の数学パスルのページを書いている人。実は私は同じ職場にいたことがある。といっても向こうは全然おぼえていないと思うけど。私の丁稚奉公先がDennisのいた会社で、同じフロアの人だったというだけ。しかもこの論文の当時のことだ。NYUの先生をしていることは聞いていたが、こんなことやっている人だとすら知らなかった。背が高くて上品な感じの人だった。


Readデータのキャッシュの方法にLRUが使われてきたが、それを改善する。

LRU
一本のキューを用意する。
新しいエントリを追加する時には最後尾から一個捨てて、新しいエントリは先頭に追加。
キューの中にあるものに再度アクセスが来たら先頭に移す。


LRUの問題点。
使用頻度の低いエントリをLRUに追加してしまうと、LRUが一周するまでの間、使われないエントリを持ち続けることになる。

最近使ったかどうかということと、使用頻度は別で、使用頻度は低いが、最近使われたということがあるし、逆に、全体をとおして見れば使用頻度は高いが、他のものと比較して最近つかわれていない、ということがあり得る。滅多に読まないデータをスキャンしてLRUに乗ってしまったりすると、大事なデータが追い出されるという問題が起こる筈だ。ARCはその両方を折衷した構造になっていた。


LRU/K ( K=2がLRU/2) というアルゴリズムがあって、これを改善しようとしているが、プライオリティキューの操作のオーバヘッドが大きい。

以下が2Qの説明。2QとはQueueが2つあるという意味。


簡単な方から。
Simplified 2Q:

2つのキュー、A1とAmを用意する。
新しいエントリはA1に追加する。
A1にあるものに対して2度目のアクセスがあると、Amに移す。

A1はFIFOで、あふれると、古いものから捨てて行く。
Amは従来のLRUと同じ。


Simplified 2Qの問題点。
チューニングが難しい。A1の量が小さすぎるとすぐにA1から追い出されてしまう。
つまり頻度に対する条件が厳しく、Amに入れないことになる。
A1を大きくしすぎると、Amの量が減ってしまう。

また、アクセスパターンによる問題がある。現実の負荷では一時的にアクセスされやすいページが多い。
アクセス頻度が多いのでAmに入れたが、そのあと全然アクセスされないということが起こる。


この問題を改善したのが、以下の2Q。

2Q:

A1をA1inとA1outに分ける。A1outはページのアドレスを覚えておくだけ。
インデクスだけを覚えるので、メモリ領域はあまり消費しない。

新しいエントリはA1inに追加。
A1inで古くなるとメモリは解放して、A1outに入れる(つまりインデクスだけ覚えておく)。
A1inのものが再度アクセスされても、そのまま。
A1outに入っているものが再度アクセスされると、メモリを獲得してAmに入れる。
A1outは古い順に捨てる。
AmはLRUとして使う。


つまり、
一時的アクセスはA1inに滞在する間だけで処理される。
A1に入っていたことがある、というのは頻度に関する情報としてとっておく(A1out)。
A1inは比較的いそがしく入れ替わり、Amに入ったものはゆっくり流れて行くイメージかな。

このやり方でも頻度については、高いか低いかという2つの状態しかないように思える。というのでARCを考えたのだろう。まるで分かったように書いたが、ARCのこともちゃんと理解してないので、あとで勉強する。

No comments: