💭

Redis、無限に成長し続けるEXPIRE設定済みのKeyを解体した話

2020/11/20に公開

TL; DR

すべての Key に Expire が設定されているからといって油断してはいけません。
Application Code 中に既存の Key の Expire を延長する Code がないか、十分注意しましょう。
無限に成長する Key を見つけるには、 RDB ファイルの分析が最も安全かつ漏れもありません。

まえがき

このお話はフィクションです!!!!

とある API サーバー開発でのお話

ある API サーバーでは、 API リクエストのためにユーザー ID 単位で有効期限 1 時間の token を発行し、認証認可を行っていました。
具体的な token の要件は下記の通りです。

API token の要件

  • token あたり有効期限 1 時間である
  • ユーザー ID 単位である
  • 有効期限内ならば何度でも利用できる
  • あるユーザー が同時に複数の token を持つことが出来る
  • そのユーザーが退会した場合、有効期限が残っていてもすべての token は即座に無効化する必要がある
  • あるユーザーの特定の token を指定して無効化することも出来る
  • token 検証は 1ms 以下で完了しなければならない

要件を受けて実装

  • token は UUID で生成する
  • token は Redis の Hash 型で保存し、下記のようなデータ設計にする
(Hash 型 ) (key, field, value) = (userID, token, TTL)

下記のようなコードで処理されていました。
※ 疑似コードです。

token 生成

token を生成し、 Redis の Hash 型に詰める。
その際、 Hash 型の有効期限は保存されている token の最長の有効期限に更新する。

public String createToken(userId){
  String token = UUID.randomeUUID();
  long ttl = Instant.now().getEpochSecond() + 3600L;
  redis.hset(userId, token, ttl);
  redis.expire(userId, 3600); // 最新のtokenと同じ有効期限にする
  return token;
}

token 検証

Redis に保存されている token から有効期限を取得し、取得出来るかつ有効期限内であれば true を返す。

public boolean validateToken(userId, token){
    int ttl = redis.hget(userId, token)
    long current = Instant.now().getEpochSecond();
    return ttl >= current;
}

ユーザー退会時の全 token の無効化

Redis に保存されている Hash 型の Key そのものを削除する。

public void deleteTokenByUserId(userId){
    redis.del(userId);
}

あるユーザーの特定 token の無効化

Redis に保存されている Hash 型の (Key, Field) を削除する。

public void deleteToken(userId, token){
    redis.hdel(userId, token);
}

何が起きたのか?

この実装はほとんどのケース ( 実際に API サーバーが稼働して 2 年余り ) では問題ありませんでした。
有効期限が無限に延長されうると言っても、あるユーザーが常に 1 時間の間を置くことなくアクセスし続けることは皆無なためです。
アクセスが 1 時間途絶えれば、 Redis の有効期限切れによって、自動で Key が掃除されていました。

しかしあるとき、 ひとりのユーザーが機械的に毎分アクセス するようになりました。
毎分のアクセスですので、当然ながら負荷的にも問題なく、あらゆる検知機構には引っかかりません。
また、その機械的なアクセスでは毎回新規に token 生成から実行しているようでした。

その結果、 Redis の特定のユーザーの token 保存用の Key のみが大きく育っていきました。
しかし、 token 検証用の HGET コマンドも、 token 生成の HSET コマンドも、どちらも O(1) という定数時間での処理だったため
特にアプリケーションが遅くなるということすらありませんでした。

しかしこの状況は非常に危険です。
そのユーザーが退会した場合、 O(n) n=field 数である DEL コマンドが発行され、アプリケーションは数十秒停止することが懸念されました。
そのトリガが該当のユーザーの行動にかかっており、アンコントローラブルな状態でした。

そして、 1.2GB 以上の Key へ...

そのまま特に検知されることもなく、時は流れました。
あるとき、別の理由から Redis の中身を確認しました。

その際に使ったのは下記のツールで、 Redis のスナップショットである RDB ファイルを解析しました。
sripathikrishnan/redis-rdb-tools: Parse Redis dump.rdb files, Analyze Memory, and Export Data to JSON

そして容量順にソートすると、 1.2GB 以上にまで育った Key が発見されました。

データ設計の変更

今回のデータ設計の問題は、ユーザー単位の無効化と token の保存を単一の Key で行ってしまったことです。
そのため、下記のようなデータ設計に変更しました。
これによって、結果的に token が Key ごとに分散されたことで水平シャーディングも行いやすくなったなどの利点も享受できました。

# token の保管
(String 型 ) (key, value) = (token, userId)

# ユーザーの無効化フラグ
(String 型 ) (key, value) = (revoked_userId, true)

コードも下記のように変更しています。
※ 疑似コードです。

token 生成

token を生成し、 Redis の String 型に詰める。
その際、 String 型の有効期限は token の有効期限と一致させる。

public String createToken(userId){
  String token = UUID.randomeUUID();
  redis.setex(token, userId, 3600);
  return token;
}

token 検証

Redis に保存されている token からユーザー ID を取得。
Redis に保存されている無効化されたユーザー ID も取得。
token が存在し、無効化されたユーザー ID でもなければ、 true

public boolean validateToken(userId, token){
    String savedUserId = redis.get(token)
    boolean revokedUserId = redis.exists("revoked_"+userId)
    return ( !revokedUserId && userId == savedUserId )
}

ユーザー退会時の全 token の無効化

Redis に revoked_userId のフラグを立てる。
有効期限はその時点の token の最大長である 3600 秒。

public void deleteTokenByUserId(userId){
    redis.setex("revoked_"+userId, true, 3600);
}

あるユーザーの特定 token の無効化

Redis に保存されている String 型の token を削除する。

public void deleteToken(userId, token){
    String savedUserId = redis.get(token);
    if(savedUserId == userId){
        redis.del(token);
    }
}

まとめ

Hash 型や Set 型などの要素数がどんどん増えていきうる型で、有効期限を更新する使い方は十分に注意しましょう。
今まで特に Redis の中身を検めたことがないようであれば、一度 RDB ファイルから分析してみるのも良いでしょう。

Discussion