［注：本記事で解説しているクライアントサイドキャッシングの実装は、Redis 6 の最終的な実装とは異なります。内容は大きく変更されています。詳細は https://redis.io/topics/client-side-caching をご覧ください。］

ニューヨークでの Redis Day が終わり、ホテルで朝5時半に目が覚めました。まだイタリアの時間感覚が残ったまま、すぐにマンハッタンの街へ散歩に出ました。風景にすっかり魅了され、数百万人の中のただ一つの数字になれたという素晴らしい感覚に浸っていました。そんな中でも、頭の中では Redis 6 のリリースのことを考えていました。そして、おそらく最も重要な機能である Redis プロトコルの新バージョン（RESP3）は、普及にかなり時間がかかるだろうという予感がありました。それも当然のことです。賢明な人ほど、よほどの理由がなければ使っている道具を切り替えたりはしません。そもそも、なぜ私はそこまでプロトコルを改善したかったのでしょうか。主な理由は二つあります。クライアントにより意味の豊かな応答を返せるようにすることと、旧プロトコルでは実現が難しかった新機能への道を開くことです。その中でも、私にとって最も重要だったのがクライアントサイドキャッシングでした。

1年ほど前に話を戻します。サンフランシスコで開かれた RedisConf 2018 に、私は「クライアントサイドキャッシングこそ Redis の未来で最も重要だ」という確信を抱いて参加していました。高速なストアや高速なキャッシュが必要なのであれば、情報の一部はクライアント側に持つべきです。これは、データを小さな遅延で大規模に提供するという考え方の自然な延長です。実際、非常に大規模な企業のほとんどはすでにそうしています。最終的には、そうしなければ負荷に耐えられないからです。しかし Redis には、クライアントがそのような処理を行うのを支援する手段がありませんでした。幸運な偶然で、Ben Malec 氏が RedisConf でまさにクライアントサイドキャッシングについて講演していました［1］。Redis が提供するツールと数々の巧妙なアイデアだけを使った内容でした。

[1] https://www.youtube.com/watch?v=kliQLwSikO4

Ben のアプローチは、私の想像力を大いに刺激しました。その設計を成り立たせていた鍵は二つあります。一つ目は、Redis Cluster の「ハッシュスロット」という考え方を使って、キーを16,384個のグループに分けることです。そうすればクライアントはキーごとに有効性を追跡する必要がなく、グループ単位で一つのメタデータを持てばよくなります。二つ目は、キーが変更されたときの通知に Pub/Sub を使うことです。そのためアプリケーション全体での協力が必要になりますが、仕組み自体は非常に堅牢でした。キーを変更したら？そのキーを無効化するメッセージも Publish します。クライアント側でキーをキャッシュしていますか？各キーをキャッシュした時刻を覚えておき、無効化メッセージを受け取ったときにはスロットごとの無効化時刻も覚えておきます。キャッシュしたキーを使うときは、遅延的に検証します。キャッシュしたキーのタイムスタンプが、そのキーが属するスロットについて受け取った無効化のタイムスタンプより古ければ、そのキーは古いデータです。サーバーに再度問い合わせる必要があります。

講演を見た後、これはサーバー内部で活かせる素晴らしいアイデアだと気づきました。Redis がクライアントの作業の一部を肩代わりすれば、クライアントサイドキャッシングはよりシンプルで効果的になるはずです。そこで帰国後、自分の設計を説明するドキュメントを書きました［2］。

[2] https://groups.google.com/d/msg/redis-db/xfcnYkbutDw/kTwCozpBBwAJ

しかし自分の設計を動かすには、Redis のプロトコルをより良いものへ切り替えることに注力しなければなりませんでした。そこで私は RESP3 の仕様を書き始め、やがて実装や、ACL をはじめとする Redis 6 の他の機能に取り組みました。そしてクライアントサイドキャッシングは、時間不足で私が何らかの形で放棄してきた、Redis に関する数多くのアイデアが集まる大きな部屋の仲間入りをしました。

それでも私は、ニューヨークの街を歩きながらこのアイデアについて考えていました。その後、カンファレンスで知り合った友人たちと昼食やコーヒーを楽しみ、ホテルの部屋に戻ると、夕方から翌日のフライトまでのほとんどの時間が丸々空いていました。そこで、1年前にグループに提案した内容にほぼ沿って、Redis 6 向けのクライアントサイドキャッシングの実装を書き始めました。今見ても、やはり素晴らしい内容に思えました。

Redis のサーバー支援型クライアントサイドキャッシングは、最終的に「tracking（トラッキング）」と呼ばれるようになりました（まだ名前を変えるかもしれません）。ごく少数の核となるアイデアからなる、とてもシンプルな機能です。

キー空間は「caching slots（キャッシングスロット）」に分割されます。Ben が使っていたハッシュスロットよりもはるかに数が多いのが特徴です。CRC64 の出力のうち24ビットを使うため、スロット数は1,600万強になります。なぜこれほど多くするのでしょうか。1億個のキーを抱えるサーバーを想定しても、1つの無効化メッセージでクライアント側のキャッシュに影響するキーがわずか数個に収まるようにしたいからです。Redis 内部で無効化テーブルを持つためのメモリオーバーヘッドは130メガバイトです。1,600万エントリ分の8バイトポインタの配列です。私としてはこれで十分だと思っています。この機能を求めるのであれば、クライアント側のメモリを存分に活用することになるのですから、サーバー側で130MBを使うのは妥当です。得られるのは、はるかにきめ細かい無効化です。

クライアントは、この機能を次のようなシンプルなコマンドでオプトインの形で有効にします。

CLIENT TRACKING on

サーバーはおなじみの +OK を返します。そしてその瞬間から、コマンドテーブルで「読み取り専用」とされているコマンドは、呼び出し元にキーを返すだけでなく、副作用として、そのクライアントがこれまでに読み取り専用コマンドでリクエストしたすべてのキーのキャッシングスロットを記憶するようになります（読み取り専用コマンドで取得したものだけが対象です。これがサーバーとクライアントの間の取り決めです）。この情報を Redis がどのように保存するかはシンプルです。各 Redis クライアントは一意の ID を持っています。たとえばクライアント ID 123 がスロット1、2、5にハッシュされるキーについて MGET を実行すると、Invalidation Table（無効化テーブル）には次のようなエントリが作られます。

1 -> [123]
2 -> [123]
5 -> [123]

その後、クライアント ID 444 もスロット5のキーについて問い合わせると、テーブルは次のようになります。

5 -> [123, 444]

ここで、別のクライアントがスロット5の何らかのキーを変更したとします。すると Redis は Invalidation Table を確認し、クライアント123と444がいずれもそのスロットのキーをキャッシュしている可能性があることを見つけます。両方のクライアントに無効化メッセージを送信します。受け取ったクライアントは、好きな方法で処理できます。一つは、スロットが無効化された最後の時刻をタイムスタンプで覚えておき、後でキャッシュしたオブジェクトのタイムスタンプ（より安全なので、増加する「エポック」と考えてもかまいません）と遅延的に比較して、比較結果に基づいて追い出す方法です。別の方法として、クライアントがそのスロットについてキャッシュした内容のテーブルを持ち、オブジェクトを直接回収する方法もあります。24ビットのハッシュ関数を使うこのアプローチは、たとえ数千万個のキーをキャッシュしていても、リストが非常に長くなることがないため問題になりません。無効化メッセージを送信した後は、Invalidation Table からそのエントリを削除できます。そうすれば、そのスロットのキーを再び読み取るまで、そのクライアントに無効化メッセージを送ることはなくなります。

なお、クライアントは必ずしもハッシュ関数の24ビットすべてを使う必要はありません。たとえば20ビットだけを使い、Redis から送られてくる無効化メッセージのスロットもシフトして扱うこともできます。そうする明確な理由がどれほどあるかはわかりませんが、メモリが制約された環境では一つのアイデアになるかもしれません。

ここまでを注意深く読まれた方は、通常のクライアント応答と無効化メッセージの両方を同じコネクションで受け取ることになるのでは、と考えたかもしれません。これは RESP3 では可能です。無効化は「push」型のメッセージとして送られるからです。しかしクライアントがブロッキング型で、イベント駆動型でない場合は話が複雑になります。アプリケーションは何らかの方法で定期的に新しいデータを読み取る必要があり、これは複雑で壊れやすくなります。そのような場合は、別のアプリケーションスレッドと別のクライアントコネクションを用意して、無効化メッセージを受け取る方がはるかに良いでしょう。そのために、次のように実行することが許されています。

CLIENT TRACKING on REDIRECT 1234

基本的な考え方は、現在のコネクションで取得したすべてのキーについて、無効化メッセージはクライアント1234に送ってほしい、と伝えることです。たとえばコネクションプールの場合のように、複数のクライアントが無効化メッセージの転送先を単一のクライアントにまとめることもできます。必要なのは、無効化メッセージを受け取るための特別なコネクションを作成し、CLIENT ID を呼び出してそのコネクションの ID を把握し、その後で tracking を有効化することだけです。

まだ一つ問題が残っています。無効化リンクのサーバーとのコネクションが切れたらどうなるでしょうか。無効化メッセージが届かなくなるため、問題が起こり得ます。通常、アプリケーションはリンクが切断されたことを検知し、再接続して現在のキャッシュをフラッシュします（あるいは、スロットごとのタイムスタンプを数秒先の未来に進めておき、数秒古いデータを提供しながらキャッシュを再構築するといった、より穏やかな対処を取ることもできます）。ただ、無効化スレッドが時々コネクションに ping を送り、生きているか確認する方がより良いかもしれません。とはいえ、古いデータが残るリスクを減らすため、Redis は無効化メッセージの転送先となっていたクライアントが切断された場合に、その状況を、転送元だったクライアントに特別な push メッセージで知らせるようにもなります。クライアントは次にクエリを実行したときに、そのことを知ることができます。

ここで説明した内容は、すでに Redis の unstable ブランチにマージされています。おそらくこれが最終形ではありませんが、最初の Redis 6 リリース候補までまだ数か月あります。すべてを変更する時間はありますので、ぜひフィードバックをお寄せください。私は RESP2 でもこの機能を有効にする方法も検討しています。その場合はリダイレクトが有効なときだけ動作し、メッセージを待ち受けるクライアントはおそらく Pub/Sub モードに入る必要があります。そうすれば、Pub/Sub メッセージのような形で送ることができます。この方法なら、古いクライアントもそのまま再利用できます。

これで興味を持っていただけたでしょうか。もしこの機能を Redis 内部でうまく実装し、クライアント作者向けにサポート方法をきちんと文書化できれば、データはこれまで以上にアプリケーションの近くに置けるようになります。これまでクライアントサイドキャッシュの実装を避けてきた小さなチームのアプリケーションでも、そしてすでにこれを実装している大規模なチームや非常に大きなアプリケーションでも、オーバーヘッドと実装の複雑さの両方を減らせるはずです。