こんにちは！やっと暑くなくなったなと思ったら極寒が訪れて戸惑っている@hansprocsです！
サーバーとのやりとりを減らすためにキャッシュをするときよく使われているRedis。 そのRedis上で検索を行いたいとき、KEYSを使うと簡単に調べたいものを見つけることができます。
しかし、公式ドキュメントにも書いている通り、RedisはKEYSを実行するために他の操作を止めることになりアプリケーションに障害をもたらします。
（本文）
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.
（和訳）
警告: KEYSコマンドは、本番環境では細心の注意を払って使用すべきコマンドとして考えてください。大規模なデータベースに対して実行すると、パフォーマンスに深刻な影響を及ぼす可能性があります。このコマンドは、デバッグやキースペースレイアウトの変更といった特殊な操作のために設計されています。通常のアプリケーションコードではKEYSを使用しないでください。キースペースの一部からキーを検索する必要がある場合は、SCANコマンドまたはセットの使用をご検討ください。
SCAN？
警告にも書いていますが、このようなKEYSの副作用を補うため、SCANというコマンドが登場しました。 KEYSのようにRedisを止めずに検索をしつつ、遅くならない。魔法のような機能ですね。
というところで、今回はこのSCANが裏でどのような動きをしているかを見ていきたいと思います！
SCANコマンド
Redisには、SET・SETEX・SETNXのように一つの機能を細かに分けたコマンドが存在することがよくあります。
同じように、SCANもSCAN・SSCAN・ZSCAN・HSCANの4つのコマンドがあります。 SCANの前につくS・Z・Hはデータ構造を指していて、以下のような意味を持っています。
SCAN：全レコード SSCAN：Set ZSCAN：Sorted Set HSCAN：Hash
ZSCAN
Sorted Setなのに何でZSCAN！？と思い少し調べてみたらいろいろな話がありました。
- Setの2次元世界(x, y)に「順番」というz軸を足しているから説
- ssは発音しにくい zが入ると賢い響きがあるとのことです
コマンドの構成
という雑談はさておき、次はSCANコマンドの使い方についてみていきたいと思います。 SCANは以下のような書き方で実行することができます。
SCAN cursor [MATCH pattern] [COUNT count] [TYPE type]
私はこの例を見ただけではすぐ理解ができなかったため、使用例を考えてみました。
まずは、Redisに以下のようなキーが入っていると仮定しましょう。
user:1 user:2 user:3 product:1 product:2
1. 基本的な使い方
実行例
SCAN 0
SCANは検索を行う機能ですが、Match Patternを明記しない場合はレコードの中でランダムなキーを探し出します。 基本的には上記のようにcursorに0を設定して検索を始めます。
結果
1) "3427" 2) 1) "user:1" 2) "product:2"
ここの"3427"は次に実行される新しいcursorの値になります。次にはSCAN 3427を行ってください、という意味ですね。
このようにSCANを行っていき、結果に返ってくる新しいcursorが0になったら全てのレコードを見回ったことになります。
要するに、SCANは一気に全てのレコードを検索するわけではなく、少しずつデータを取って確認することを繰り返す仕組みになっているんですね。
2. オプションの活用
実行例
SCAN 0 MATCH product:* COUNT 100 TYPE string
今回はオプションをフル活用したパターンです。
MATCH
MATCH session:*はsession:で始まるものを検索してという意味です。
*は「ワイルドカード」と呼び、どんな文字列にも一致することを指す記号です。SQLではLIKEで%がワイルドカードとして使われています。
COUNT
COUNTは一回の検索で取得するキーの数を表しています。
今回のようにCOUNT 100だと検索条件に一致するキーを100個探すまでSCANが走ります。
TYPE
TYPEではデータ構造の指定ができます。RedisではString, List, Hash, Set, Sorted Setを使用することができて、このオプションを書くことで指定したデータ構造を持つキーだけを検索します。
お気づきの方もいらっしゃると思いますが、前述のSSCANなどを使って指定することもできます。
SCANの実装
これまではSCANの使い方について見てきました。 SCANの結果は基本的にKEYSと同じくなりますが、必ずしもそうではない時があります。 どういうことかについて知るためにはRedisの実装を見る必要があります。
SCANのソースコード
以下はC言語で実装されているRedisのソースコードです。
その中で、SCAN系（SCAN・SSCAN・ZSCAN・HSCAN）を処理するにあたって核になるscanGenericCommandというメソッドをピックアップしました。
主な処理内容は以下のようになります。
1. scanData構造体に必要な情報を設定
scanData data = {
.keys = keys, // キーを格納するリスト
.o = o, // 対象のオブジェクト
.type = type, // スキャン対象の型
.pattern = use_pattern ? pat : NULL, // マッチングパターン
.sampled = 0,
.no_values = no_values,
.strlen = (isKeysHfield) ? hfieldlen : sdslen,
};
2. keysリストに追加（Hash tableの場合）
while文の中でキーをスキャンし、keysリストにキーを追加しています。
do { if (o == NULL) { cursor = kvstoreScan(c->db->keys, cursor, onlydidx, scanCallback, NULL, &data); } else { cursor = dictScan(ht, cursor, scanCallback, &data); } } while (cursor && maxiterations-- && data.sampled < count);
Redisのデータ構造
ソースコードからはSCANが多様なデータ構造に対応するため様々な処理方式を取っているという点では、全レコードを見回るだけのKEYSと違っていることがわかります。 しかし、これだけだとまだどのような処理をしているかしっくりこないため、そもそもRedisがどのようなデータ構造を持っているかについて考えていきたいと思います。
Namespace
皆さんのご存じのように、RedisはKVSとして、KeyとValueでデータを保存しています。 その実装の中で、RedisはNamespace(Bucketとも言う)を使った単方向リストを採択しています。 最初は4つのBucketで始まり、Bucketに入るキーは単方向リストで保存されます。
たとえば、下のようなイメージになります。
Namespace KVSの単方向リスト
[00] -> Apple -> Banana
[01] ->
[10] -> Kiwi
[11] -> Orange -> Mango -> Pineapple
SCANの原理
結論からいいますと、SCANはこのNamespaceを一回に一つずつ回ることが基本的な動きになります。 RedisのSCANで扱うcursorは次に検索するNamespaceのindexの値であって、そのため最初はcursorを0(Namespaceの頭)に設定することになっていたんですね。
KEYSと異なる処理
SCANがどう動いているか大体見えてきたところですが、まだ前述した「KEYSと結果が同じくならない場合」について解消できていません。もう少しお付き合いください🙇♂️
Redisで単方向リストを使うと効率の良いKVSを実装することができますが、結局、レコードが増えると探索速度が遅くなります。
その問題に対応するため、RedisはRehashという処理を行います。
Rehashを行うと、RedisはNamespaceの数を2倍にします。 そうすることで単一の単方向リストに入るデータ量を減らすことができます。
Rehashのソースコード
github.com
Rehash
Rehashを行うと以下のようなものが
Namespace KVSの単方向リスト
[00] -> Apple -> Banana
[01] ->
[10] -> Kiwi
[11] -> Orange -> Mango -> Pineapple
以下のようになります！
Namespace KVSの単方向リスト
[000] -> Apple
[001] ->
[010] -> Kiwi
[011] -> Orange
[100] -> Banana
[101] ->
[110] ->
[111] -> Mango -> Pineapple
こうやってRehashを使うと単方向リストごとに入る値を減らせることができますね。 実際にRedisには数十万、多くは数千万のレコードが入るため、こうやってRehashの処理をすることで非常に効率がよくなります。
まだ課題はある
このようにNamespaceを増やして探索効率を上げることはとてもいいですが、Rehashの処理には時間がかかります。 ということは、Rehashが行われる途中でRedisが使われるケースが少なからず存在するということにもなります。
Rehash途中だと、まだ全てのレコードが移行できていないため、この時SCANで検索をかけると全データからの検索ができなくなります。 そのために、RedisはRehashを行う時に元々のデータを破棄せずに保持します。
以下のようなケースがRehash途中のデータになります。()の中のものはもともとその場所にそのキーが存在したことを意味します。
旧Redis
Namespace KVSの単方向リスト
[00] -> Apple -> (Banana)
[01] ->
[10] -> (Kiwi)
[11] -> Orange -> (Mango) -> (Pineapple)
新Redis
Namespace KVSの単方向リスト
[000] ->
[001] ->
[010] -> Kiwi
[011] -> Mango
[100] -> Banana
[101] ->
[110] ->
[111] -> Pineapple
もし新Redisだけを検索するとSCANが始まったあとにRehashが始まれば()の中のデータが取れないこともありえます。
上記の例ではAppleやOrangeのような場合ですね。
そのような例外を除くため、SCANは旧Redisもともに保持したまま、両方の検索を行います。
KEYSは？
この時、KEYSは実行時にRedisを完全にロックしてしまうため、途中でRehashが行われません。 KEYSとSCANの結果が必ずしも同じくならないのはRehashが原因になります！
SCANも万能ではない
SCANも結局は細切れにしただけであって、データが膨大であるときはKEYSのようにタイムアウトの原因になります。 また、検索を始めた後に追加されたレコードは当然ですがSCANでも取れません。
システムの安定性を考えるとなるべくGETを使ってキーを明示的に取ってこれるような仕組みにすることが望ましいですね。
おわりに
インゲージでは今回の題材であったRedis(Elasticache)を業務でも使っています！ 様々なポジションでの求人を行っておりますので、ぜひ採用ページをご確認ください〜
