Laravelのキャッシュのタグ機能はどのように実装されているのか

Laravelのキャッシュにはタグ機能というものがあります。キャッシュ登録時にタグを指定しておくと、タグ指定でキャッシュをまとめて削除することができます。タグ機能はmemcached等のタグ機能に対応したキャッシュドライバを使用する場合にのみ使用できますが、memcached本体にはタグ機能のようなものはないため、これは、Laravelにおいて実装されていることがわかります。

そこで、以前から以下の点がなんとなく気になっていました。

(1) タグ単位でアイテム削除する時どのようにしているのか？

アイテム数が多い状態でもパフォーマンス的に問題はないのか？
タグに属するアイテムを抽出するのにまさか全アイテムをwalkしたりしていないか？

(2) キャッシュ内のデータ構造

(1)の削除時のパフォーマンスのことを考えると、タグ関連の情報を何か別に持っているはず。

推測では、タグに属するアイテムを保持するアイテムを別途持つ(図1)ことで、削除対象のアイテムを抽出する処理を軽くしている。ただし、この場合でも削除対象アイテムが多い場合は重くなる。

また、タグに属するアイテムを保持するアイテム自体がEvicted(メモリ不足で削除)されたらどうなるか？
図1のデータ構造だと、タグ指定での削除ができなくなってしまう。

ということでタグ機能がどのような実装になっているか調べてみました。
ここではmemcachedを例に説明しますが、タグ機能の実装はキャッシュドライバには依存していないので、Redis等の他のキャッシュドライバでも同じです。

なお、参照したバージョンはLaravel 5.5 LTSです。

キャッシュのデータ構造

それでは調べた結果です。データ構造を図2に示します。

(1) タグ情報を保存するアイテム

予想通りタグの情報を保存するアイテムがありました。本ページでは以降、タグアイテムと呼びます。ただし、Valueの内容が予想と異なっています。

このアイテムはKeyが'tag:<タグ名>:key'という形式で、ValueにタグのIDを保持しています。このタグIDは、Cache::tags(['xxx'])->flush()でタグ付きアイテムを削除すると、IDが変更されるという特徴を持っています。

(2) タグ付きのキャッシュアイテム

一方、ユーザがput()したタグ付きのキャッシュアイテムはKeyが工夫されており、以下のような形式になっています。

<タグハッシュ値>:<キー名>

ここで、「タグハッシュ値」はアイテムが属するタグのIDを連結してハッシュ化(SHA1)した値となります。例えば、Cache::tags(['tag-a', 'tag-b'])->put('article-2', xxx)のようにして登録した、tag-a,tag-bに属するarticle-2アイテムでは以下のように算出されます。

タグのハッシュ値

tag-aのID: '5c9a54f498595471252074'
tag-bのID: '5c9ad7f99b0df192452727'

tag-a,tab-bに属するキャッシュアイテムのタグハッシュ値:
sha1('5c9a54f498595471252074' . '|' . '5c9ad7f99b0df192452727')
=> 3886a6d881fdb0ac7bc5c1062f809fd1de372e45

このため、article-2のキャッシュアイテムのKeyは'3886a6d881fdb0ac7bc5c1062f809fd1de372e45:article-2'となります。ハッシュ値には関連する全てのタグのIDが含まれているため、関連タグのIDが変更になった場合、タグハッシュ値も変更になります。

キャッシュを取得する際は、以下のようにput()時と同じタグを同じ順序で指定する必要があります。これは、指定したタグからKey内のタグハッシュ値を求めるのに必要なためです。

Cache::tags(['tag-a', 'tag-b'])->get('article-2')

=> '3886a6d881fdb0ac7bc5c1062f809fd1de372e45:article-2'のKeyのアイテムをmemcachedに取りに行く。

タグ付けキャッシュアイテムの削除

データ構造としてはこのような形になります。ここまでわかれば、察しのいい人ならタグ指定でのアイテム削除の動作もすでに理解できているでしょう。

図3を元に説明します。
Cache::tags(['tag-a'])->flush()として、tag-aのキャッシュアイテムを削除したとします。すると、tag-aのタグIDが変更になります。タグIDが変更になるとtag-aに属するアイテム検索時のタグハッシュ値も変更になるので、既存のアイテムがヒットしなくなります。

# article-1の取得
# タグハッシュ値は変更になったので、Key: 52af46..7357:article-1 のアイテムはもうヒットしない
Cache::tags(['tag-a'])->get('article-1')

# article-2の取得
# Key: 3886a6..2e45:article-2 のアイテムはもうヒットしない
Cache::tags(['tag-a', 'tag-b'])->get('article-2')

# article-3の取得
# タグハッシュ値は変わらないので、Key: 0ce199..b744:article-3 のアイテムがヒットする
Cache::tags(['tag-b'])->get('article-3')

このように、IDを変更して既存のアイテムにマッチしなくさせることで、アイテム削除を行っています。

参照されなくなったアイテムはメモリ上に残りますが、メモリが足りなくなれば、memcachedのLRU(Least Recently Used)の仕組みによって使われていないものから消されて(Evicted)いくので、いずれはなくなります。

削除時にタグに関連するアイテムを抽出する処理や、個々のアイテムをいちいち削除する必要もないうまい処理になっています。

タグアイテムが消えた場合は？

memcachedでは設定された使用メモリの上限に達するとLRUに従い、使っていないアイテムを削除していきます。それでは、タグIDを保存しているアイテム(Keyが'tag:<xxxx>:key'のアイテム)が消されてしまった場合はどうなるのでしょうか？

この場合、Cache::tags(['tag-a'])->get('article-1')のようにタグを参照した際に改めてタグアイテムが作成されます。この時、IDも新しいものが作成されるので、タグ関連のアイテムが削除されてしまったのと同じ動作になります。

タグアイテムが追い出されてしまうと、関連するアイテムまで根こそぎ削除されてしまうのはもったいないような気もしますが、タグ付きアイテムを参照する際はタグアイテムも頻繁に参照されるはずなので、LRU的にタグアイテムが率先して追い出されることはまずないのでしょう。

まとめ

気になっていたタグ指定によるアイテム削除のパフォーマンスについて、問題ないことがわかりました。また、個々のアイテム削除処理も行わずにすむ上手い実装であることがわかりました。

参考

今回調査した実装に関連するクラスです。

Illuminate\Cache\TagSet

キャッシュアイテムに関連付けたタグ群を表すクラス。
タグアイテムの作成やタグIDの再作成を行う。

[メモ]
reset():set内の全タグのID作成を行う。

Illuminate\Cache\TaggedCache

Cache::tags()で返されるタグ付きキャッシュのオブジェクト。

[メモ]
taggedItemKey($key): キャッシュアイテムのKeyを生成。タグハッシュ値の計算もここ。

補足

Laravelをデフォルト設定で使用するとキャッシュのキーには'laravel:'というプレフィクスが付与されます。図2中ではプレフィクスを省略して表記しています。このプレフィクスはconfig/cache.phpで変更可能です。

投稿日:2019/03/27 17:20

タグ: laravel

ブログ