[注：この投稿はRedis 6の最終実装におけるクライアントサイドキャッシングの実装を説明するものではなくなりました。実装は大幅に変更されています。https://redis.io/topics/client-side-cachingを参照してください]

ニューヨークでのRedis Dayが終わった。ホテルで5時30分に目が覚めた。まだイタリアの時間帯に体が合っているのだろう。すぐにマンハッタンの街へ散歩に出かけた。風景にすっかり魅了され、何百万人もの中のただ一つの数字でしかないという素晴らしい感覚に浸っていた。それでも私は、Redis 6のリリースについて考えていた。おそらくあらゆる機能の中で最も重要だったはずの、新バージョンのRedisプロトコル（RESP3）が、非常にゆっくりとした普及曲線をたどるだろうという感覚があった。それにはもっともな理由がある。賢明な人たちは、よほどの理由がない限りツールを切り替えたりはしないのだ。そもそも、なぜ私はあれほどプロトコルを改善したかったのか？ 主に二つの理由があった。クライアントにより意味のある（セマンティックな）応答を提供するため、そして旧プロトコルでは実装が困難だった新機能への道を開くためだ。その中でも、特に私にとって最も重要だった機能が一つあった。それがクライアントサイドキャッシングだった。

話を約1年前に巻き戻そう。私はサンフランシスコで開催されたRedisConf 2018に、クライアントサイドキャッシングこそRedisの未来において最も重要なものだという確信を抱いて参加した。高速なストアと高速なキャッシュが必要なのであれば、情報の一部をクライアントの中に保存する必要がある。これは、小さな遅延で大規模にデータを提供するという考え方の自然な延長である。実際、ほぼすべての超大規模企業がすでにそうしている。なぜなら、最終的に負荷を生き延びるための唯一の方法だからだ。しかしRedisには、クライアントがそのプロセスを進めるのを支援する方法がなかった。幸運な偶然か、Ben MalecがちょうどRedisConfでクライアントサイドキャッシングについて講演していた[1]。Redisが提供するツールと数々の非常に巧妙なアイデアだけを使ったものだった。

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

Benがとったアプローチは、本当に私の想像力をかき立てた。彼の設計を機能させるためにBenが使った重要なアイデアは二つあった。一つ目は、Redis Clusterの「ハッシュスロット」という考え方を利用して、キーを16kのグループに分割することだった。そうすればクライアントは各キーの有効性を追跡する必要がなく、キーのグループごとに一つのメタデータエントリを使えばよくなった。Benはキーが変更された際の通知を送るためにPub/Subを使っていたため、アプリケーションのあらゆる部分での協力が必要だったが、それでもスキームは非常に堅牢だった。キーを変更したら？ それを無効化するメッセージもパブリッシュするのだ。クライアント側では、キーをキャッシュしているだろうか？ 各キーをキャッシュした際のタイムスタンプを覚えておき、無効化メッセージを受信した際には各スロットの無効化時刻も覚えておく。キャッシュされた特定のキーを使う際には、キャッシュしたキーのタイムスタンプが、そのキーが属するスロットについて受信した無効化のタイムスタンプよりも古いかどうかをチェックすることで、遅延的（レイジー）に追放（eviction）を行う。その場合はそのキーは古いデータであり、再びサーバーに問い合わせなければならない。

講演を見た後、これはサーバー内部で利用するのに素晴らしいアイデアだと気づいた。Redisがクライアントのために作業の一部を担うことで、クライアントサイドキャッシングをよりシンプルかつ効果的にできるのだ。そこで私は帰宅後、自分の設計を説明するドキュメントを書いた[2]。

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

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

それでも私はニューヨークの街路を歩きながら、このアイデアについて考えていた。その後、カンファレンスで知り合った友人たちと昼食やコーヒーブレイクをとった。ホテルの部屋に戻ると、丸々一晩と、飛行機が出発するまでの翌日の大半が残っていた。そこで私はRedis 6向けのクライアントサイドキャッシングの実装を書き始めた。1年前にグループに向けて書いた提案に忠実に従ったものだ。今見ても、やはり素晴らしく思えた。

Redisのサーバー支援型クライアントサイドキャッシングは、最終的に「tracking（トラッキング）」と呼ばれるようになった（ただし気が変わるかもしれない）が、わずか数個の重要なアイデアからなる非常にシンプルな機能だ。

キー空間は「caching slots（キャッシングスロット）」に分割されるが、これはBenが使ったハッシュスロットよりもはるかに数が多い。CRC64の出力の24ビットを使用するため、1600万強の異なるスロットが存在する。なぜこれほど多いのか？ 1億個のキーを持つサーバーを想定しても、無効化メッセージがクライアント側のキャッシュ内のわずかなキーにしか影響しないようにしたいからだ。無効化テーブルを保持するためのRedis内部のメモリオーバーヘッドは130メガバイトだ。16Mエントリに対する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ビットのハッシュ関数を使ったこのアプローチは問題にならない。なぜなら、数千万個のキーをキャッシュしている場合でも、リストが非常に長くなることはないからだ。無効化メッセージを送信した後、エントリを無効化テーブルから削除できる。そうすれば、それらのクライアントがそのスロットについて再びキーを読み取るまで、無効化メッセージを送ることはなくなる。

なお、クライアントはハッシュ関数の24ビットすべてを実際に使うことを強制されているわけではない。例えば20ビットだけを使い、Redisから送られてくる無効化メッセージのスロットをシフトすることもできる。そうする十分な理由がどれほどあるかはわからないが、メモリが制約されたシステムでは一つのアイデアかもしれない。

私の話を注意深く追ってきたなら、同じ接続が通常のクライアントへの応答と無効化メッセージの両方を受信することに気づいただろう。これはRESP3では可能なことだ。無効化は「push」メッセージタイプとして送信されるからだ。しかしクライアントがブロッキング型で、イベント駆動型ではない場合、これは複雑になり始める。アプリケーションは時々新しいデータを読み取る何らかの方法を必要とし、それは複雑で壊れやすく見える。その場合、別のアプリケーションスレッドと、無効化メッセージを受信するための別のクライアント接続を使う方がはるかに良いかもしれない。そこで次のようなことが許されている。

CLIENT TRACKING on REDIRECT 1234

基本的に、現在の接続で取得したすべてのキーについて、無効化メッセージをクライアント1234に送信してほしいと言うことができるのだ。例えばコネクションプールの場合など、複数のクライアントが無効化メッセージを単一のクライアントにリダイレクトするよう要求することもある。必要なことは、この特別な接続を作成して無効化メッセージを受信し、CLIENT IDを呼び出してこのクライアント接続が持つIDを知り、その後トラッキングを有効にすることだけだ。

一つ残された問題がある。無効化リンクのサーバーとの接続が切れたらどうなるか？ 無効化メッセージがもはや受信されなくなるため、問題が生じる可能性がある。通常、アプリケーションはリンクが切断されたことを検出し、再接続して現在のキャッシュをフラッシュする（あるいは、すべてのスロットのタイムスタンプを数秒先の未来に設定して、数秒古いかもしれないデータを提供しながらキャッシュを再構築する時間を作るといった、より緩やかな解決策をとる）。しかし、無効化スレッドが時々接続にpingを送り、接続が生きていることを確認する方がより良いアイデアかもしれない。しかし古いデータ（stale data）のリスクを減らすため、Redisは無効化メッセージを他のクライアントにリダイレクトしていたクライアントに対して、そのクライアントが現在切断されたことについても、特別なpushメッセージを使って知らせるようになる。次にクエリを実行した際に、クライアントはその状況を知ることになる。

私が説明したものは、Redisのunstable版にちょうどマージされた。おそらくこれが最終的なものではないが、最初のRedis 6リリース候補まであと数ヶ月あり、すべてを変更する時間はある。ぜひフィードバックを送ってほしい。私はまた、RESP2向けにこの機能を有効にする方法も検討している。それはリダイレクションが有効な場合にのみ機能し、メッセージをリッスンするクライアントはおそらくPub/Subモードに入る必要があるだろう。そうすれば一種のPub/Subメッセージを送ることができる。この方法なら、古いクライアントを完全に再利用できる。

これで皆さんの食欲を十分に刺激できたことを願っている。もしこれをRedis内部で非常にうまく実行し、クライアント作者向けにサポートを提供する方法を文書化できれば、データはこれまで以上にアプリケーションの近くに置かれるようになるだろう。これまでクライアントサイドキャッシングの実装を避けてきた小規模なチームが運営するアプリケーションでさえそうなる。すでにこれを行っている大規模なチームや非常に大規模なアプリケーションにとっては、実装の複雑さとともにオーバーヘッドを削減できるだろう。