Next: ヒープ, Previous: パスワードハッシュ, Up: ライブラリモジュール - ユーティリティ [Contents][Index]
data.cache - キャッシュキャッシュは、キーと値を結びつけるという点では辞書と似たように動作しますが、 キャッシュアルゴリズムの方針によってエントリが消去されることがあります。 このモジュールは、キャッシュについて共通のプロトコルを定義し、 またいくつかの典型的なキャッシュの実装を提供します。
まず簡単な例によって、どんな具合かを示しましょう。
指定されたファイルを読み込むルーチンに、
頻繁に読むファイルをキャッシュする機能をつけたいとします。
次のコードはfile->stringにキャッシュ機能を持たせたものです。
(use data.cache)
(use file.util)
(define file->string/cached
(let1 file-cache (make-lru-cache 10 :comparator string-comparator)
(^[path] (cache-through! file-cache path file->string))))
この手続きはfile-cache変数をクロージャの中に綴じ込んでいます。
その値は文字列のパス名とファイルの中身を結びつけるLRU(least recently used)キャッシュです。
キャッシュの動作はcache-through!で実現されています。
この手続きは、
まずpathをキーとして持つエントリがfile-cacheにあるかどうか調べます。
そのキーを持つエントリがキャッシュ中にあればその値(ファイルの中身)が返されます。
キャッシュ中に無ければ、file->stringがpathを引数として呼ばれ、
それが返したファイルの中身がキャッシュに登録され、返されます。
キャッシュの容量はmake-lru-cacheの第1引数で指定され、ここでは10になっています。
つまり、11個目のファイルが読まれた時に、一番長く使われていない
(least recently used)ファイルがキャッシュから消去されます。
上の例そのままではキャッシュの効果が見え辛いです。
次の例の通り、printスタブをいれて、いろいろなファイルを
file->string/cachedで読んでみて下さい。
いつキャッシュが実際にファイルの中身を取りにゆくかわかるでしょう。
(define file->string/cached
(let1 file-cache (make-lru-cache 10 :comparator string-comparator)
(^[path]
(print #"file->string/cached called on ~path")
(cache-through! file-cache path
(^[path]
(print #"cache miss. fetching ~path")
(file->string path))))))
注意: キャッシュ自身はスレッドセーフではありません。 マルチスレッドプログラムでキャッシュを使う場合は、キャッシュをatomでラップしてください。
(use data.cache)
(use file.util)
(use gauche.threads)
(define file->string/cached
(let1 file-cache (atom (make-lru-cache 10 :comparator string-comparator))
(^[path]
(atomic file-cache (cut cache-through! <> path file->string)))))
どんなキャッシュにも、比較器とストレージがあります。
比較器はキーを比較するのに使われます。上の例ではパス名を比較するために
string-comparatorを渡しています
比較器について詳しくは基本的な比較器を参照してください。
ストレージは、キーとキャッシュ内部の構造とをマッピングする辞書です。
デフォルトでは与えられた比較器を使うハッシュテーブルが使われるので、
比較器はハッシュ関数を持っていなければなりません。
比較器が省略された場合はdefault-comparatorが使われます。
あるいは、 (同じ種類のキャッシュからコピーされた)辞書をストレージとして渡すことで、 既にエントリがある状態のキャッシュを作ることもできます。 キャッシュが辞書に登録している構造はキャッシュアルゴリズムごとに異なるので、 何でも辞書を渡せるわけではないことに注意してください。 同じ種類のキャッシュによって作られた辞書しか渡せません。 ストレージとなる辞書を渡した場合、比較器はその辞書から取られます。
従ってキャッシュのコンストラクタは共通してcomparatorとstorageの キーワード引数を取ります。デフォルトの動作で良ければ、 どちらかひとつ、あるいは両方とも省略することができます。
storageとcomparatorキーワード引数については上の節を参照してください。
{data.cache} capacity個までのエントリを保持できる、FIFO(先入れ先出し)キャッシュを作って返します。 エントリ数がcapacityを越えそうになった場合、一番古いものから削除されます。
{data.cache} capacity個までのエントリを保持できる、 LRU(least recently used)キャッシュを作って返します。 エントリ数がcapacityを越えそうになった場合、一番長く使われなかったものから削除されます。
{data.cache} タイムアウト値timeoutを持つTTL(生存時間)キャッシュを作って返します。 各エントリには、挿入された時間が記録されます。timeoutを経過したエントリは削除されます。 実際の削除は、キャッシュがアクセスされた時に行われます。
デフォルトではUnixシステム時間(Epochからの秒数)がタイムスタンプに使われます。 1秒より短い間隔でたくさんのエントリが追加される場合にはこれでは分解能が足りないかもしれません。 timestamperにサンクを与えることで、タイムスタンプをカスタマイズすることができます。 キャッシュは時刻が必要になる度にtimestamperを引数無しで呼び出します。 timestamperは単調非減少な実数を返さねばなりません(物理的な時間と結びついている必要は ありません)。 timestamperを与えた場合、timeout引数の単位は timestamperが返す値の単位と同じでなければなりません。
{data.cache} TTLキャッシュのバリエーションで、エントリは書き込まれた時だけでなく、 読み出された時にもタイムスタンプが更新されます。 手続きの名前TTLRは、リフレッシュ付きTTL(TTL with refresh)という意味です。 ただ、これをタイムアウト付きLRUキャッシュと見ることもできます。
タイムアウトの単位およびtimestamper引数の役割については、
make-ttl-cacheと同じです。
以下のAPIはキャッシュのユーザに向けたものです。
{data.cache} cacheからkeyに結びつけられたエントリを探し、見つかれば返します。 エントリが無い場合は、defaultが与えられていればそれを返し、 与えられていなければエラーを投げます。
キャッシュアルゴリズムによってはこの操作でcacheがアップデートされる場合があるため、 名前にエクスクラメーションマークがついています。
{data.cache}
cacheからkeyに結びつけられたエントリを探し、見つかれば返します。
見つからなかった場合、value-fnがkeyを引数として呼び出され、
その結果がcacheに新たなエントリとして追加され、またcache-through!の
戻り値として返されます。
{data.cache} cacheに、keyとvalueの関係を追加します。既にkeyに 結びつけられたエントリがあった場合は上書きされ、そうでなければ新たなエントリが作られます。
同じ効果は、cache-evict!を呼んでからcache-through!を呼ぶことでも
達成できますが、アルゴリズムによってはcache-write!に対して効率のよい
実装を提供しているかもしれません。
{data.cache} cacheからkeyに結びついたエントリを(もしあれば)削除します。
{data.cache} cache内のエントリを全て取り除きます。
新たなキャッシュアルゴリズムを提供するには、<cache>を継承したクラスを定義し、
次の二つの必須メソッドを実装します。高レベルAPIはこれらの必須メソッドを呼び出します。
{data.cache}
cacheからkeyに結びついたエントリを探します。
見つかれば、keyとその値とのペアを、見つからなければ#fを返します。
この時、必要ならばキャッシュを更新して構いません。
例えば読み出されたエントリのタイムスタンプを更新するなどです。
{data.cache} cacheに、keyと対応するvalueを追加します。 このメソッドは、cacheにkeyに対応するエントリが無いことが確認された後で 呼び出されます。
アルゴリズムの実装は、また以下の点を考慮しなければなりません。
initializeメソッドは最初にnext-methodを呼ばなければなりません。
それによってcomparatorとstorageスロットが適切に初期化されます。
また、storageスロットに既にデータが入っているかどうかを調べ、
そうであれば他の内部構造をそれに合わせて初期化する必要があります。
cache-evict!とcache-clear!のデフォルトメソッドはキャッシュの
storageだけを更新します。サブクラスが他の内部状態を持っている場合は、
それらの一貫性を保つようなメソッドを定義する必要があります。
cache-write!のデフォルトメソッドは、cache-evict!を呼んでから
cache-register!を呼ぶだけです。
より効率の良い実装があれば(あることが多いでしょう)、
このメソッドをオーバライドするのが良いでしょう。
キャッシュのサブクラスを実装するのに便利な手続きがいくつか用意してあります:
{data.cache}
キャッシュのcomparatorとstorageを返します。
典型的なキャッシュは、storageとしての辞書と、キューで作られます。
ここでstorageは、キーを(<n> . <value>)にマップし、
キューは(<key> . <n>)を保持します。
ただし<n>はタイムスタンプやカウンタなど何からの数値です。
キャッシュがこの「キューと辞書」を使って実装されている場合は、
以下の共通手続きが使えるでしょう:
{data.cache}
initializeメソッドの中でこの手続きを呼ぶことにより、
キューを初期化できます。この手続きは、キーを(<n> . <value>)にマップする辞書である
storageを走査し、(<key> . <n>)というペアを作り、
<n>の昇順にソートしてそれをqueueにプッシュします。
{data.cache} キューに、同じキーを持つエントリが複数含まれることがあります。 しばしば、そういった重複エントリが多くなりすぎる場合があります (例えばキーが読み出される度にタイムスタンプをキューにプッシュしていて、 同じキーが何度も読まれた場合)。この手続きはキューを走査し、 キーが重複しているエントリは最新のもの以外を取り除きます。 この操作の後では、キューの長さとstorageのエントリ数は一致しているはずです。
{data.cache}
この手続きはキュー内の<n>を、順序を変えることなく、0から昇順に付け直し、
<n>の最大値を返します。キーが重複するエントリはcache-compact-queue!と
同様に、最新のもの以外取り除かれます。
<n>に単調増加する数を使っていて、長い時間の後では<n>がbignum
になって効率が落ちる心配があれば、この手続きを適宜呼ぶことで<n>を適切な
範囲内に収めることができるでしょう。
Next: ヒープ, Previous: パスワードハッシュ, Up: ライブラリモジュール - ユーティリティ [Contents][Index]