Redis の `SCAN` の全件検索に気をつけろ！

こんにちは！Redis初心者です！

おそらく今一番よく使われるオンメモリDBの一種である Redis にはいろんなコマンドがありますが、そのうち特定のパターンのキーの一覧を返す SCAN コマンドでの全件検索に気をつけようという話をします。¹

たとえば、まっさらなRedisを立てた後に、下記のように find_my_key のキーの一覧を SCAN で取得しようとすると、どれぐらいのコストがかかるでしょうか？

# 何もデータが入っていないRedis

# カーソルが0 'find_my_key' で検索
$ SCAN 0 MATCH find_my_key
  => 次のカーソルは 0 (検索は終了)

「コストはほぼかからない」というのが答えになります。即座に 0 (終了) のカーソルが返却されることにより、SCAN による全件検索はその場で終了します。

では、これが 10万件ほどデータが既に入っているRedis に対してであればどうなるでしょうか？

# どこかに10万件のデータを抱えているRedis

# カーソルが0 'find_my_key' で検索
$ SCAN 0 MATCH find_my_key
  => 次のカーソル XXXXX0001 (検索は継続)

# 引き続き上記のカーソルで検索続行
$ SCAN XXXXX0001 MATCH find_my_key
  => 次のカーソル XXXXX0002 (検索は継続)

# 引き続き上記のカーソルで検索続行 ...
$ SCAN XXXXX0002 MATCH find_my_key
  => 次のカーソル XXXXX0003 (検索は継続)

:
: (同じやりとりを計9,999回)
:

# ようやく検索終了 コマンド発行 計1万回!
$ SCAN XXXXX9999 MATCH find_my_key
  => 次のカーソル 0 (検索は終了)

1万回ほどの検索を経た後にカーソルがようやく0で終了します。 言い換えれば1万回Redisと通信しないと全件検索が終了しません。1回のやり取りにかかる時間が仮に 100μsec (0.0001秒) だったとしても 1秒かかることになります。²

何故こうなるのか？

そもそもRedisはRDBのような効率的にインデックスを用いて必要なキーを前方一致検索する仕組みを備えていません。

ざっくりいうとRedisができるのは、キーが完全一致するエントリをすぐに取り出すか(GET)、エントリ全部を一つ一つ検索するか(SCAN)だけです。

よって SCAN コマンドで特定の名前のキーを全て列挙しようとするとRedis内の全てのエントリをフルスキャンするしかありません。

上記の例におけるSCANによる検索は、たった1件のデータを探すためであっても、10万件の既存エントリをスキャンしないといけないことになります。

そもそもSCAN コマンドのページには以下のように説明されています。

O(1) for every call. O(N) for a complete iteration, including enough command calls for the cursor to return back to 0. N is the number of elements inside the collection.

SCAN でカーソルを一つ辿るのは O(1) であり、カーソルを全て辿って検索を完了させるのにかかるコストは O(N), N=コレクション内の要素数 かかると説明されています。

補足: 勘違いしてはいけないカーソルの仕様

「カーソルなんて全部辿らなくても、最初のあたりで結果が返ってくるんだから問題ない」という勘違いをしてはいけません。

たしかに、「10件の結果だけを集める」といった場合に10件の結果が取れた時点でカーソルを辿るのをやめるのは理にかなっていますが、その10件が最後の最後まで取れないということは普通にあります。また、特定条件のキーを全て列挙するのは、やはりカーソルを最後まで辿らないと分かりません。

それではどうすればよいのか？

方法1. `SCAN` の COUNT を上げる

SCAN コマンドには一度にスキャンするコレクション中のエントリの量をコントロールできる引数 COUNT が用意されています。以下の例では、一度に1万個スキャンすることが期待できます。

$ SCAN 0 MATCH find_my_key COUNT 10000

今回の例のような10万件エントリが入っている場合、おそらく10回カーソルを消費すれば (10 = 100,000 / 10,000) 検索が終わるようになります。

COUNTの値はデフォルトでは 10 であり、大きなRedisでCOUNTを指定しないまま全件検索すると、既存エントリの数によってはとんでもないラウンドトリップ回数になり、それが処理遅延を招くことは容易に想像できます。

ちなみに大きなCOUNTを指定すると一見問題が解決したかのように見えますが、そこそこRedisに負荷をかけてしまうことに注意してください。データヒット件数が多ければ当然Redisサーバとの間の送受信コストもありますし、Redis自体がシングルプロセスであり、コレクションの全件フェッチを処理している間、他のリクエストが後回しにされることが想像できます。

バッチ処理等でたまに巨大COUNTの SCAN を発行するぐらいならいいですが、オンライン処理で利用するのは慎重になるべきです。

方法2. 即時性が必要な処理に `SCAN` を使わない

そもそも SCAN での全件検索は重いので、 SCAN を用いず GET 等の高速なコマンドを利用できるのならそうしましょう。（まあそうできるならとっくにしてますよね……）

方法3. そもそも大きなRedisを持たない

コレクションの数で SCAN の性能が劣化するのであれば、Redisを分割してしまうのも最悪一つの手です。ただRedisが増えればそれだけ別のコストがかかるわけで、最終手段です。

まとめ

成長中のシステムにおいて、Redisの SCAN コマンド利用はRedisが成長した時に初めて発覚する時限爆弾になりえます。基本的に SCAN による全件検索をオンライン処理では使わないようにしましょう。³

本記事の内容は Redis 6.2.14 で検証しています ↩
往々にしてRedisのクライアントライブラリにSCANのカーソルフェッチからの全件検索完了まで隠蔽されていたりして、「何か遅いけど動いているからまあいっか」となりがちなのが怖いところです。 ↩
ちなみに KEYS を使えばいいじゃないかという意見があるかもしれませんが、 KEYS は非常に大きなCOUNTを指定した SCAN と同じであり、根本的な問題は SCAN と同じです ↩