【Redis】KEYSによるKey取得の危険性とSCANによる安全な対処

Redisにおける`KEYS`の危険性、及び`SCAN`による対処をできる限り簡潔に紹介します。

# Redis , KEYSとは

※分かる方は飛ばしてOKです

Redisは、**KVS型**(Key Value Store)データベースの一つであり、オープンソース（BSDライセンス）のインメモリデータ構造ストア(ストレージではなくメインメモリで処理するもの)です。僕の知る限りWebによくある**キャッシュを保存するのに使われることが多い**です。

構造は極めて単純で、**ひとつの`Key`に対して一対の`Value`がある**というものです。

<img width="967" alt="スクリーンショット 2020-06-26 19.06.13.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/305969/794b23fe-62ce-8cf8-d8e8-d8765eb39025.png">

キャッシュを扱う場合、Keyには「ページの部品のURL」、Valueには「CSSやJavaScriptなど」を保存します。

**`KEYS`**は、特定のパターンにマッチする**Keyを検索する手法**です（[Redis(KEYS)](https://redis.io/commands/keys)）。全てのKeyとパターンを比較するため、時間計算量は`O(N)`となります(Nはデータベース内のKeyの数)。つまり計算量は、保存されているKeyの数に直接影響します。

以下、KEYSコマンドの例。

```
redis> KEYS *name*
1) "lastname"
2) "firstname"

redis> KEYS a??
1) "age"

redis> KEYS *
1) "age"
2) "lastname"
3) "firstname"
```



# KEYSによる全検索の危険

> While the time complexity for this operation is O(N), the constant times are fairly low. For example, Redis running on an entry level laptop can scan a 1 million key database in 40 milliseconds.

公式リファレンス[Redis(KEYS)](https://redis.io/commands/keys)にあるように、単純な参照の処理速度は高速のようです。

問題は、保存されたKeyの数が「数百万、数千万」という膨大な数の場合に起こります。その悲劇の順序は以下の通りです。

<img width="973" alt="スクリーンショット 2020-06-26 22.28.40.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/305969/e578191c-b2d2-51d2-a4bb-c25af880bbf8.png">

### 1. KEYSのレスポンスが長くてRedisが何も返せない

Redisサーバは基本、単一の処理しか行えない**シングルスレッド**です。ゆえに、「数百万、数千万」という膨大な件数を参照しに行く場合、**その処理が終わるまでレスポンスを返せない**状態になります。

### 2. 他のRedisへのGETリクエストなどが詰まる

Redisが「数百万、数千万」という件数の参照を繰り返してる間にも、次々と**Redisサーバに対するリクエストは増え続けます**。ちなみに、もしRedisがマルチスレッド（シングルスレッドの逆で並列処理が可能）であれば、一つ重たいリクエストがあったとしても、軽い処理は次々とレスポンスされていくので最低限の動作は可能になります（後で詳しく紹介します）。

### 3. Redisのレスポンスを期待しているApp側（Railsなど）が詰まる

Redisはレスポンスを長時間返せないので、当然アプリケーション側は何もできない時間が増え、詰まります。

### 4. ユーザへリクエストを返せず、最悪の場合サーバダウン

レスポンスタイムが増えると、サーバへの負荷も増えます。結果、ユーザのリクエストに対し多くの時間を費やすことになり、**最悪の場合高負荷によりサーバがダウン**してしまう危険性が高まるのです。

ちなみにこのような危険性が考慮されているため、公式リファレンスでも非推奨とされています。

> Warning: consider KEYS as a command that should only be used in production environments with extreme care. It may ruin performance when it is executed against large databases. This command is intended for debugging and special operations, such as changing your keyspace layout. Don't use KEYS in your regular application code. If you're looking for a way to find keys in a subset of your keyspace, consider using SCAN or sets.

# SCANでカーソルベースで参照しに行く

`KEYS`でのKey取得の危険性がわかったところで、解決策を考えます。

先ほど軽く触れたように、マルチスレッドであれば一つの重いリクエストがあっても詰まることはありません。しかしそれは現実的に不可能なので、別のアプローチを考えます。それが、公式でも推奨されている**`SCAN`**という方法です。

`SCAN`は、`KEYS`と同じく、パターンマッチするKeyを検索する手法です。`SCAN`の特徴は、**参照をカーソルベースで行う**という点です。これにより、参照を一括で行うのではなく、**分割して参照することが可能**になります。ここで言うカーソルとは「次参照する位置を示すもの」で、次のカーソルがない（参照が終わっている）場合`SCAN`は"0"を返します。詳しくは[Redis(SCAN)](https://redis.io/commands/scan)。

`SCAN`コマンドの例。

```
redis> scan 0
1) "17"
2)  1) "key:12"
    2) "key:8"
    3) "key:4"
    4) "key:14"
    5) "key:16"
    6) "key:17"
    7) "key:15"
    8) "key:10"
    9) "key:3"
   10) "key:7"
   11) "key:1"

redis> scan 17
1) "0"
2) 1) "key:5"
   2) "key:18"
   3) "key:0"
   4) "key:2"
   5) "key:19"
   6) "key:13"
   7) "key:6"
   8) "key:9"
   9) "key:11"
```

プログラムで実装する場合は、カーソルが"0"になるまで（参照が終わるまで）`SCAN`でリクエストを繰り返すようにします。

# 終わり

Redisそのもののデータ構造は単純でも、内部的な処理を調べていくと危険性も多くあるので非常に興味深いですね。

質問や編集リクエストがあればコメントにお願いします。

# Greeting late

長期インターンを始めて2ヶ月目の[@TsuboyaTaiki](https://.com/tsuboyataiki)です。

現在Railsアプリの業務でRedisサーバを用いたキャッシュ周りの修正issueを担当しています。その過程で`KEYS`や`SCAN`といったバリュー検索について知ったことが多くあったので書き残しておきます。