Cache::Lrq - LRU ハッシュによるプロセス内キャッシュ

車輪の再発明で、Least Recently Used (LRU) を使い Perl の配列オブジェクトでキャッシュをおこなうモジュールを作っていました。

2013年1月30日修正: v0.02 へ。双方向リンクを使って書き換えました。v0.03 へ。_list をフラットにしました。

https://github.com/tociyuki/libcache-lrq-perl

これを作ることになった発端は、Kazuho Oku さんによる Cache-LRU-0.03 を使おうと、ソースを読んでみると予想外に複雑なことをしていたからでした。私の用途では、要素数に上限をもつ単なる LRU キャッシュが必要だったので、素朴なものを作ってみたというわけでした。

利用方法は Cache-LRU-0.03 と同じです。パッケージ名が変化するだけで、まったく同じメソッド操作を受け付けます。

use Cache::Lrq;

my $cache = Cache::Lrq->new(size => 256); # 格納可能な最大キー数。デフォルトは 256。
$cache->set('key' => 'value');
my $value = $cache->get('key');  # 要素がないときは undef を返します。
my $latest_value = $cache->remove('key');

v0.01 交互リスト版

LRU としては最も素朴なやりかたを採用しており、要素数に上限をもつ交互リストをキー・値のコンテナとして使います。交互リストの先頭は古く、末尾が新しくなります。値を読みだすときは、対象ペアが末尾でないときは push と splice を使って末尾へ移動します。値を書き込むときは、既に保持しているキーの場合は空読みして末尾へペアを移動してから値を書き換えます。保持しておらず、かつ、要素数上限に達していたら先頭ペアを削除して空きを開けます。ペアの追加は常に末尾への push でおこないます。削除のときは、対象ペアを splice で削ります。交互リストのどの位置にキーがあるのかを素早く検索するために、交互リストのキー位置の配列添字をハッシュに記録してあり、交互リストの変更の都度、ハッシュへ _reindex メソッドで反映しています。

交互リストとハッシュの関係が正常かどうかは、デバッグ用メソッド _assert でチェックすることができます。というよりも、テストでふるまい記述をしてから、まっさきにこのメソッドを書いてから、new、_reindex、get、remove、set の順に書いていきました。

sub _assert {
    my($self) = @_;
    return if @{$self->{'_list'}} > $self->{'size'} * 2;
    my $n = 0;
    for my $key (keys %{$self->{'_index'}}) {
        my $i = $self->{'_index'}{$key};
        return if $i % 2 != 0;
        return if ! exists $self->{'_list'}[$i];
        return if $self->{'_list'}[$i] ne $key;
        ++$n;
    }
    return if @{$self->{'_list'}} != $n * 2;
    return 'good';
}

テストには、オブジェクトの内部状態をインジェクトしておいてから、メソッド操作で状態がどう変化するべきかの状態遷移のふるまいを並べてあります。これの副作用で、new に交互リストと索引を注入可能になっているのですが、モジュールを使うときはこれらを注入しないようにするべきです。次のバージョンで、ランタイム用のモジュールの new では内部状態を注入できないようにして、テスト時用パッケージへ継承し new を上書きするように変更するかもしれません。

v0.02 双方向リンク・リスト版

交互リストを使う素朴なやりかたでは、要素ペアを末尾へ移動したり空きを作るためにシフトする都度に、いちいちインデックスのハッシュを書き換えなければならないのが気に食わず、双方向リンクを使って書き換えました。ノードの並び順は交互リストと同じで、先頭が古く、末尾が新しくなります。

_list スロットを双方向リンクされるノードの配列に変更しました。ゼロ番目がフリーリストのヘッド。1番目が LRU キューのヘッドです。両方共、双方向リストになっていて、ヘッドを含めてリングを構成します。双方向リンクなので、参照を使うと循環参照になるため、可読性が損なわれますが、リンクに参照ではなく配列の添字を使ったシンボリックなリンクを使っています。

値を読みだすときは、対象ペアを含むノードが末尾でないときはリンクを末尾になるように付け替えします。値を書き込むときは、既に保持しているキーの場合は空読みして末尾になるようにノードのリンクを付け替えてから値を書き換えます。保持しておらず、かつ、要素数上限に達していたら先頭ノードを削除して空きを開けます。削除は対象ノードをフリーリストの末尾へ付け替えます。双方向リンクなので、削除と付け替えは高速で容易です。_move メソッドがノードをフリーリストか LRU キューの末尾への付け替えをおこなっています。原理的にノードの配列内での位置が変化せず、リンクが書き換わるだけなので、インデックスのハッシュの更新は追加と削除のときにおこなうだけで済みます。

v0.03 双方向リンク・リスト版のフラット配列化

LRU リストとハッシュの関係が正常かどうか、LRU リストとフリーリストが健全化どうかは、デバッグ用メソッド _assert でチェックすることができます。

# v0.03 用
sub _assert {
    my($self) = @_;
    my $e = $self->{'_list'};
    my $i = 0;
    while ($i < @{$e}) {
        return if ! ($e->[$e->[$i + $BACK] + $FORW] == $i
                  && $e->[$e->[$i + $FORW] + $BACK] == $i);
        $i += $NODESIZE;
    }
    my %idx = %{$self->{'_index'}};
    my $j = $e->[$ROOT + $FORW];
    while ($j != $ROOT) {
        my $key = $e->[$j + $FKEY];
        return if ! exists $idx{$key};
        return if $idx{$key} != $j;
        delete $idx{$key};
        $j = $e->[$j + $FORW];
    }
    return if %idx;
    return 'good';
}