Redis の SCAN のコストに注意しよう

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

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

おそらく今一番よく使われるオンメモリDBの一種である [Redis](https://redis.io/) にはいろんなコマンドがありますが、そのうち特定のパターンのキーの一覧を返す [`SCAN` コマンド](https://redis.io/commands/scan/) での全件検索に気をつけようという話をします。[^1]

[^1]: 本記事の内容は Redis 6.2.14 で検証しています

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

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

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

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

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

```bash
# どこかに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秒 かかることになります。[^3]

[^3]: 往々にしてRedisのクライアントライブラリに`SCAN`のカーソルフェッチからの全件検索完了まで隠蔽されていたりして、「何か遅いけど動いているからまあいっか」となりがちなのが怖いところです。


## 何故こうなるのか？

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

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

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

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

そもそも[`SCAN` コマンド](https://redis.io/commands/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万個スキャンすることが期待できます。

```bash
$ 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`](https://redis.io/commands/get/) 等の高速なコマンドを利用できるのならそうしましょう。（まあそうできるならとっくにしてますよね……）


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

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


## まとめ

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

[^2]: ちなみに `KEYS` を使えばいいじゃないかという意見があるかもしれませんが、 `KEYS` は非常に大きなCOUNTを指定した `SCAN` と同じであり、根本的な問題は `SCAN` と同じです