RedisのKEYS/SCANはタイムスタンプを更新するのか?

Redisにはメモリが不十分な場合にデータの一部を削除してメモリを確保する eviction (立ち退き) という機能があります。このとき削除対象を選ぶルールに LRU (least recently used; 最も未使用期間が長い) や LFU (least frequently used; 最も使用頻度が少ない) を選択することができますが、ここで "use" とは何かが問題になります。

一般論として、LRUやLFUを実装するときは書き込みだけではなく読み取りタイムスタンプも考慮するのが望ましいです。というのも、アクセスパターンによっては一度書き込んだデータを更新せずにずっと読み出すようなこともありえるからです。たとえばcontent hashをキーとするようなイミュータブルなキャッシュではしばしばそういったことが起こりえます。RedisのLRUやLFUは読み取りも考慮しますが、今度はどのような読み取りが考慮されるのかが問題になります。

結論

RedisのKEYS/SCANはタイムスタンプを更新しません。

一般論として、以下のようなコマンドはキーの読み取り・書き込み時にタイムスタンプを更新します。

キーを読み取るコマンド
- GET, GETEX, MGET, STRLEN など
キーに書き込むコマンド
- SET, SETEX, MSET, GETDEL, GETSET, INCR, DECR, COPY, RENAME, MOVE, SORT など
キーのメタデータを設定するコマンド
- EXPIRE, PERSIST, TOUCH など

いっぽう、以下のようなコマンドはタイムスタンプを更新しません。

キーのメタデータを読み取るコマンド
- EXISTS, TYPE, TTL, EXPIRETIME など
キーを一覧するコマンド
- KEYS, SCAN など

また、タイムスタンプを更新するコマンドであっても、以下のような場合には更新が行われません。

サーバー側で、データベースのファイル保存などのための子プロセスが実行中の場合。
クライアント側で CLIENT_NO_TOUCH フラグを設定して接続している場合。ただし、 CLIENT_NO_TOUCH フラグがあっても、 TOUCH コマンドはタイムスタンプを更新します。

調査過程

全体構造の把握

ドキュメントに明確な記載はなさそうだったので、ソースコードから挙動を解明していきます。

Redisのソースコードをまず眺めてみると、 src/ 以下が本体であることがわかります。Cで書かれているので、C/C++の解析ができるIDEを使います (今回はVS CodeのMicrosoft謹製のC/C++ extensionを利用)。

一般論として、LRUに関わる処理は大きく2箇所あると考えられます。

タイムスタンプを設定する処理 (読み書きコマンド内)。
タイムスタンプを参照してevictionの判定を行う処理。

そのため、手掛かりとしてどちらかの処理を探すことにします。今回探したい関連コードは後者により密集していると考えられるため、できればeviction関連の処理が見つかると嬉しいです。

探してみると evict.c があることがわかります。そのため、ここを起点に探していきます。

タイムスタンプフィールドの特定

evict.c を眺めてみます。すると、evictionのモード設定 (maxmemory-policy) を参照する分岐がいくつかあることがわかります。

evictionPoolPopulate 内
performEvictions 内

ここでは、各キーの処理をしていると思しき evictionPoolPopulate 内に注目します。すると、 MAXMEMORY_FLAG_LRU の場合の分岐で、 estimateObjectIdleTime という関数を呼んでいることがわかります。名前から考えると、ここでタイムスタンプを参照していると考えられます。

estimateObjectIdleTime を見てみると、 o->lru という値を参照しています。現在時刻から減算しているので、これがタイムスタンプである可能性が高いです。そのlruフィールドは server.h 内の struct redisObject で定義されています。また、このフィールドはLFUの計算に使われる頻度情報と兼用であることも読み取れます。 (以降では単にタイムスタンプと呼ぶことにします)

タイムスタンプの更新箇所を探す

IDEの機能でlruフィールドの更新箇所を探します。直接的には以下の関数で更新されていることがわかります。

updateLFU (db.c) ... lookupKeyの一部。
lookupKey (db.c) ... 読み取り・書き込みアクセスのコアとなる検索処理。
dbSetValue (db.c) ... DBの書き込み処理。タイムスタンプを変更しないように古い値からコピーしているだけなので、実質的には更新処理ではない。
createObject (object.c) ... 初期化。
initObjectLRUOrLFU (object.c) ... 初期化。
createEmbeddedStringObject (object.c) ... 初期化。
objectSetLRUOrLFU (object.c) ... タイムスタンプを更新するための一般のサブルーチン。

この中で追跡する必要があるのは lookupKey と objectSetLRUOrLFU であることがわかります。

objectSetLRUOrLFUの追跡

objectSetLRUOrLFU の利用箇所は以下のように評価できます。

restoreCommand (cluster.c) ... RESTOREコマンド。シリアライズされたキーのメタデータからタイムスタンプを復元する。
RM_SetLRU (module.c) ... プラグインから利用できるAPI。
RM_SetLFU (module.c) ... プラグインから利用できるAPI。
rdbLoadRioWithLoadingCtx (rdb.c) ... シリアライズされたDBデータからタイムスタンプを復元する。

この関数は特別な理由でメタデータを更新する目的で使われるもので、通常の読み取り・書き込みアクセス用ではないようです。

lookupKeyの追跡

まず、lookupKey内でタイムスタンプを設定しているコード本体を見てみます。ここでは、タイムスタンプを更新しない条件として以下の3つがあることがわかります。

LOOKUP_NOTOUCH フラグを付与して関数を呼び出している場合。
または、作業用の子プロセスが存在している場合。これには以下の場合が含まれます。
- RDB (Redis DB) 形式でのデータの保存用プロセス。
- AOF (Append-Only File) 形式でのデータの保存用プロセス。
- LDB (Lua Debugger) 用のプロセス。
- プラグインによって起動されるプロセス。
または、接続元クライアントが CLIENT_NO_TOUCH フラグをつけて接続してきていて、かつ現在のコマンドがTOUCHコマンドではない場合。

各コマンド実装はlookupKeyを直接呼ばず、以下の派生関数を経由します。

lookupKeyRead
lookupKeyReadOrReply
lookupKeyReadWithFlags
lookupKeyWrite
lookupKeyWriteOrReply
lookupKeyWriteWithFlags

LOOKUP_NOTOUCH フラグを指定しているのは以下の箇所であることもわかります。 (LOOKUP_NOEFFECTS が LOOKUP_NOTOUCH を含む点に注意)

EXISTS コマンド (existsCommand, db.c)
SCAN, HSCAN, SSCAN, ZSCAN コマンド (scanGenericCommand, db.c)
TYPE コマンド (typeCommand, db.c)
TTL, PTTL, EXPIRETIME, PEXPIRETIME コマンド (expire.c)
RM_KeyExists 関数 (module.c)
RM_OpenKey 関数 (module.c), REDISMODULE_OPEN_KEY_NOTOUCH または REDISMODULE_OPEN_KEY_NOEFFECTS が指定された場合
DBに対して行われた何らかのコマンドが、BLPOPなどのブロッキングコマンドのアンブロックを誘発する可能性がある場合 (handleClientsBlockedOnKey, blocked.c)
Redisクラスタにおいて、特定のhash keyに対応するスロットをインポートする必要がある場合 (getNodeByQuery, cluster.c)

以上のコマンドの共通の特徴として以下が考えられます。