Cache の match() は O(N) の場合がある

tl; dr

Chrome の Cache の match() に { ignoreSearch: true } を渡すと実行時間が O(N) になる。

詳細

Cache はHTTPレスポンスを端末内にキャッシュする時に使われるインターフェースです。Cache の match() メソッドは、リクエストをキーにしてレスポンスを検索し、該当するレスポンスがあればそれを返します。通常、クエリストリングが異なる 2 つのリクエストは異なるものとして扱われますが、オプションとして { ignoreSearch: true } を渡すとクエリストリングの違いを無視して一致判定が行われます。

Chrome の match() メソッドは通常、キャッシュの数によらず一定時間で結果を返しますが、ignoreSearch: true が渡された場合はキャッシュが多いほど実行に時間がかかるようです。

3048 個のエントリーがあるキャッシュで match() の実行時間を計測したところ、ignoreSearch: false の場合は 3 ミリ秒前後、ignoreSearch: true の場合は 1000 ミリ秒前後でした。

計測結果

for (let i = 0; i < 8; i += 1) { console.time(); await caches.open('foo').then(cache => cache.match(`https://${Math.random()}.example.com/`, {ignoreSearch: false})); console.timeEnd(); }
// default: 3.60107421875 ms
// default: 2.740966796875 ms
// default: 2.369873046875 ms
// default: 3.2021484375 ms
// default: 3.107177734375 ms
// default: 2.248046875 ms
// default: 1.548095703125 ms
// default: 2.1669921875 ms

for (let i = 0; i < 8; i += 1) { console.time(); await caches.open('foo').then(cache => cache.match(`https://${Math.random()}.example.com/`, {ignoreSearch: true})); console.timeEnd(); }
// default: 1183.406982421875 ms
// default: 1079.485107421875 ms
// default: 1099.9560546875 ms
// default: 1091.84912109375 ms
// default: 1113.6650390625 ms
// default: 1140.06103515625 ms
// default: 1088.77197265625 ms
// default: 1094.85888671875 ms

一方、195 個しかエントリーがないキャッシュでは、ignoreSearch: false の場合は 3 ミリ秒前後、ignoreSearch: true の場合は 70 ミリ秒前後でした。

計測結果

for (let i = 0; i < 8; i += 1) { console.time(); await caches.open('foo').then(cache => cache.match(`https://${Math.random()}.example.com/`, {ignoreSearch: false})); console.timeEnd(); }
// default: 3.56884765625 ms
// default: 1.650146484375 ms
// default: 2.532958984375 ms
// default: 2.970947265625 ms
// default: 2.761962890625 ms
// default: 2.308837890625 ms
// default: 2.575927734375 ms
// default: 2.3701171875 ms

for (let i = 0; i < 8; i += 1) { console.time(); await caches.open('foo').then(cache => cache.match(`https://${Math.random()}.example.com/`, {ignoreSearch: true})); console.timeEnd(); }
// default: 74.430908203125 ms
// default: 66.89501953125 ms
// default: 67.739013671875 ms
// default: 68.11376953125 ms
// default: 67.28515625 ms
// default: 67.64306640625 ms
// default: 71.7890625 ms
// default: 71.757080078125 ms

このことから、ignoreSearch: true の場合はキャッシュエントリーを一つずつ取り出してクエリストリング以外の部分が一致するかをチェックしていると推測しました。

Chromium では、JavaScript から match() メソッドを呼び出すと内部的に以下の関数が順次呼び出されるようです。

CacheStorageCache::Match -> CacheStorageCache::MatchImpl -> CacheStorageCache::MatchAllImpl -> CacheStorageCache::QueryCache

最後の QueryCache ではキャッシュの探索を行なっていて、ignoreSearch の値によって処理が分岐していました。ignoreSearch が真の場合はキャッシュのエントリーを全探索しているように見えます。

https://github.com/chromium/chromium/blob/131.0.6775.1/content/browser/cache_storage/cache_storage_cache.cc#L1091-L1142

以上から、エントリの数が多くなりうるキャッシュに対して { ignoreSearch: true } をつけて match() を呼び出すのは避けたほうが良いと思われます。比較の際にクエリストリングを無視することがわかっているのであれば、キャッシュに入れる前にリクエストを正規化 (クエリストリングを除去) すると良さそうです。