For Gauche 0.9.6


Next: , Previous: , Up: ライブラリモジュール - ユーティリティ   [Contents][Index]

12.7 data.cache - キャッシュ

Module: 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->stringpathを引数として呼ばれ、 それが返したファイルの中身がキャッシュに登録され、返されます。 キャッシュの容量は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が使われます。

あるいは、 (同じ種類のキャッシュからコピーされた)辞書をストレージとして渡すことで、 既にエントリがある状態のキャッシュを作ることもできます。 キャッシュが辞書に登録している構造はキャッシュアルゴリズムごとに異なるので、 何でも辞書を渡せるわけではないことに注意してください。 同じ種類のキャッシュによって作られた辞書しか渡せません。 ストレージとなる辞書を渡した場合、比較器はその辞書から取られます。

従ってキャッシュのコンストラクタは共通してcomparatorstorageの キーワード引数を取ります。デフォルトの動作で良ければ、 どちらかひとつ、あるいは両方とも省略することができます。

定義済みのキャッシュ

storagecomparatorキーワード引数については上の節を参照してください。

Function: make-fifo-cache capacity :key storage comparator

{data.cache} capacity個までのエントリを保持できる、FIFO(先入れ先出し)キャッシュを作って返します。 エントリ数がcapacityを越えそうになった場合、一番古いものから削除されます。

Function: make-lru-cache capacity :key storage comparator

{data.cache} capacity個までのエントリを保持できる、 LRU(least recently used)キャッシュを作って返します。 エントリ数がcapacityを越えそうになった場合、一番長く使われなかったものから削除されます。

Function: make-ttl-cache timeout :key storage comparator timestamper

{data.cache} タイムアウト値timeoutを持つTTL(生存時間)キャッシュを作って返します。 各エントリには、挿入された時間が記録されます。timeoutを経過したエントリは削除されます。 実際の削除は、キャッシュがアクセスされた時に行われます。

デフォルトではUnixシステム時間(Epochからの秒数)がタイムスタンプに使われます。 1秒より短い間隔でたくさんのエントリが追加される場合にはこれでは分解能が足りないかもしれません。 timestamperにサンクを与えることで、タイムスタンプをカスタマイズすることができます。 キャッシュは時刻が必要になる度にtimestamperを引数無しで呼び出します。 timestamperは単調非減少な実数を返さねばなりません(物理的な時間と結びついている必要は ありません)。 timestamperを与えた場合、timeout引数の単位は timestamperが返す値の単位と同じでなければなりません。

Function: make-ttlr-cache timeout :key storage comparator timestamper

{data.cache} TTLキャッシュのバリエーションで、エントリは書き込まれた時だけでなく、 読み出された時にもタイムスタンプが更新されます。 手続きの名前TTLRは、リフレッシュ付きTTL(TTL with refresh)という意味です。 ただ、これをタイムアウト付きLRUキャッシュと見ることもできます。

タイムアウトの単位およびtimestamper引数の役割については、 make-ttl-cacheと同じです。

キャッシュに共通の操作

以下のAPIはキャッシュのユーザに向けたものです。

Function: cache-lookup! cache key :optional default

{data.cache} cacheからkeyに結びつけられたエントリを探し、見つかれば返します。 エントリが無い場合は、defaultが与えられていればそれを返し、 与えられていなければエラーを投げます。

キャッシュアルゴリズムによってはこの操作でcacheがアップデートされる場合があるため、 名前にエクスクラメーションマークがついています。

Function: cache-through! cache key value-fn

{data.cache} cacheからkeyに結びつけられたエントリを探し、見つかれば返します。 見つからなかった場合、value-fnkeyを引数として呼び出され、 その結果がcacheに新たなエントリとして追加され、またcache-through!の 戻り値として返されます。

Generic function: cache-write! cache key value

{data.cache} cacheに、keyvalueの関係を追加します。既にkeyに 結びつけられたエントリがあった場合は上書きされ、そうでなければ新たなエントリが作られます。

同じ効果は、cache-evict!を呼んでからcache-through!を呼ぶことでも 達成できますが、アルゴリズムによってはcache-write!に対して効率のよい 実装を提供しているかもしれません。

Generic function: cache-evict! cache key

{data.cache} cacheからkeyに結びついたエントリを(もしあれば)削除します。

Generic function: cache-clear! cache

{data.cache} cache内のエントリを全て取り除きます。

キャッシュアルゴリズムの実装

新たなキャッシュアルゴリズムを提供するには、<cache>を継承したクラスを定義し、 次の二つの必須メソッドを実装します。高レベルAPIはこれらの必須メソッドを呼び出します。

Generic function: cache-check! cache key

{data.cache} cacheからkeyに結びついたエントリを探します。 見つかれば、keyとその値とのペアを、見つからなければ#fを返します。 この時、必要ならばキャッシュを更新して構いません。 例えば読み出されたエントリのタイムスタンプを更新するなどです。

Generic function: cache-register! cache key value

{data.cache} cacheに、keyと対応するvalueを追加します。 このメソッドは、cachekeyに対応するエントリが無いことが確認された後で 呼び出されます。

アルゴリズムの実装は、また以下の点を考慮しなければなりません。

There are several procedures that help implementing cache subclasses:

Function: cache-comparator cache
Function: cache-storage cache

{data.cache} Returns the comparator and the storage of the cache, respectively.

Typical caches may be constructed with a storage (dictionary) and a queue, where the storage maps keys to (<n> . <value>), and queues holds (<key> . <n>), <n> being a number (timestamp, counter, etc.) Here are some common operations work on this queue-and-dictionary scheme:

Function: cache-populate-queue! queue storage

{data.cache} You can call this in the initialize method to set up the queue. This procedure walks storage to construct (<key> . <n>) pairs, sorts it in increasing order of <n>, and pushes them into the queue.

Function: cache-compact-queue! queue storage

{data.cache} The queue may contain multiple pairs with the same key. Sometimes the queue gets to have too many duplicated entries (e.g. the same entry is read repeatedly). This scans the queue and removes duplicated entries but the up-to-date one. After this operation, the length of the queue and the number of entries in the storage should match.

Function: cache-renumber-entries! queue storage

{data.cache} This procedure renumbers <n>s in the queue and the storage starting from 0, without changing their order, and returns the maximum <n>. The duplicated entries in the queue is removed as in cache-compact-queue!.

When you’re using monotonically increasing counter for <n> and you don’t want <n> to get too big (i.e. bignums), you can call this procedure occasionally to keep <n>’s in reasonable range.


Next: , Previous: , Up: ライブラリモジュール - ユーティリティ   [Contents][Index]