純粋なデータ構造としてのRedis Streams
Redis 5で「Streams」という名前で導入された新しいRedisのデータ構造は、コミュニティで大きな注目を集めました。いずれ、本番環境で活用しているユーザーの方々に話を伺い、アンケートを実施して、その内容をブログで紹介したいと考えています。今回は別のテーマを取り上げます。最近、多くのユーザーがStreamsをKafka(TM)的なユースケースを解決するためのものとしてしか捉えていないのではないかと感じ始めています。確かにこのデータ構造は、プロデューサーとコンシューマーによるメッセージングの文脈でも機能するように設計されています。しかし、Redis Streamsがそれだけにしか役立たないと考えるのは、あまりにも矮小化しすぎです。ストリーミングはシステム設計に応用すると非常にうまくいく素晴らしいパターンであり「メンタルモデル」ですが、他の多くのRedisデータ構造と同様に、Redis Streamsはより汎用的で、互いに無関係な数多くの問題のモデリングに使うことができます。そこでこのブログ記事では、Streamsを純粋なデータ構造として捉えることに絞り、ブロッキング操作やコンシューマーグループなど、メッセージングに関わる部分は一切取り上げません。
Streamsはステロイドを打ったCSVファイル
一連の構造化されたデータをログに残したいと考え、結局データベースは大げさだと判断した場面を想像してみてください。次のように考えるかもしれません。追記専用モードでファイルを開き、1行ごとにCSV（Comma Separated Value）形式で記録していこう、と。
(open data.csv in append only) time=1553096724033,cpu_temp=23.4,load=2.3 time=1553096725029,cpu_temp=23.2,load=2.1
シンプルに見えますし、実際に人々は昔からこうしてきましたし、今でもそうしています。何をしているか分かっていれば、堅実なパターンです。しかし、これと等価なインメモリの表現は何でしょうか。メモリは追記専用ファイルよりもはるかに高機能で、このようなCSVファイルが抱える制約を自動的に取り除くことができます。
- ここでは範囲検索が困難（非効率）です。
- 冗長な情報が多すぎます。時刻はどのエントリでもほぼ同じですし、フィールド名も繰り返されています。一方で、それらを削ってしまうと、別のフィールドセットに切り替えたくなったときにフォーマットの柔軟性が失われてしまいます。
- アイテムのオフセットはファイル上のバイトオフセットに過ぎません。ファイル構造を変えればオフセットは無効になってしまうため、真の意味でのプライマリIDという概念がありません。つまり、エントリが何らかの形で一意にアドレス指定されているわけではないのです。
- エントリを削除することはできず、無効になったとマークするだけで、ログを書き直さない限りガベージコレクションができません。ログの書き直しはさまざまな理由で厄介なことが多く、避けられるなら避けた方がよいものです。
とはいえ、このようなCSVエントリのログにも優れた点があります。固定された構造がなくフィールドを自由に変えられること、生成が容易なこと、そして意外とコンパクトなことです。Redis Streamsで目指したのは、この良いところは残しつつ、制約を乗り越えることでした。その結果生まれたのが、RedisのSorted Setに非常によく似たハイブリッドなデータ構造です。根本的なデータ構造であるかのように*感じられる*のですが、その感覚を実現するために内部では複数の表現を使い分けています。
Streams入門（すでにRedis Streamsの基礎をご存知の方は読み飛ばしてください）
Redis Streamsは、デルタ圧縮されたマクロノードが基数木（radix tree）によって連結された形で表現されています。これにより、ランダムなエントリへのシークを非常に高速に行え、必要に応じて範囲取得ができ、古いアイテムを削除して長さに上限のあるStreamを作るといったことも可能になります。一方で、プログラマーから見えるインターフェースはCSVファイルに非常に近いものになっています。
> XADD mystream * cpu-temp 23.4 load 2.3 "1553097561402-0" > XADD mystream * cpu-temp 23.2 load 2.1 "1553097568315-0"
上記の例から分かるように、XADDコマンドはエントリIDを自動生成して返します。このIDは単調増加し、<time>-<counter>という2つの部分から構成されています。timeはミリ秒単位の時刻で、counterは同じミリ秒内に生成されたエントリに対して増加していきます。
つまり「追記専用のCSVファイル」という発想の上に乗る最初の新しい抽象化は、XADDのID引数にアスタリスクを指定することで、サーバー側でエントリIDを自動的に取得できるということです。このIDはStream内の特定のアイテムを指し示すのに役立つだけでなく、Streamに追加された時刻とも関連しています。実際、XRANGEを使えば範囲検索や単一アイテムの取得が可能です。
> XRANGE mystream 1553097561402-0 1553097561402-0
1) 1) "1553097561402-0"
2) 1) "cpu-temp"
2) "23.4"
3) "load"
4) "2.3"ここでは単一の要素を特定するために、範囲の開始と終了に同じIDを指定しました。もちろん任意の範囲を指定できますし、COUNT引数で結果の件数を制限することもできます。同様に、範囲指定に完全なIDを指定する必要はなく、IDのミリ秒部分だけを使って特定の時間範囲にある要素を取得することもできます。
> XRANGE mystream 1553097560000 1553097570000
1) 1) "1553097561402-0"
2) 1) "cpu-temp"
2) "23.4"
3) "load"
4) "2.3"
2) 1) "1553097568315-0"
2) 1) "cpu-temp"
2) "23.2"
3) "load"
4) "2.1"今回はこれ以上StreamsのAPIを紹介する必要はないでしょう。詳しくはRedisのドキュメントをご覧ください。ここではひとまず、XADDでデータを追加し、目的に応じてXRANGE（あるいはXREAD）で範囲を取得するという使い方に注目し、なぜStreamsがデータ構造としてこれほど強力なのかを見ていきます。
なお、Redis StreamsとそのAPIについてさらに学びたい方は、ぜひこちらのチュートリアルをご覧ください。https://redis.io/topics/streams-intro
テニスプレイヤーの例
数日前、最近Redisを学び始めた友人と一緒にアプリケーションのモデリングをしていました。地元のテニスコートやプレイヤー、試合を管理するアプリです。プレイヤーのモデリング方法はRedisではごく自然で、プレイヤーは小さなオブジェクトなので、player:<id>のようなキー名のHashを使えば十分です。さらにアプリのデータをモデリングし、Redisをプライマリストアとして使おうとすると、あるテニスクラブで行われた試合を追跡する方法が必要になることにすぐ気づきます。player:1とplayer:2が対戦し、player 1が勝った場合、Streamに次のようなエントリを書き込むことができます。
> XADD club:1234.matches * player-a 1 player-b 2 winner 1 "1553254144387-0"
このシンプルな操作で、次のことが実現できます。
- 試合の一意な識別子が得られます。Stream内のIDがそれにあたります。
- 試合を識別するためだけに別途オブジェクトを作る必要がありません。
- 試合のページネーションや、過去の特定の時点に行われた試合の確認といった範囲検索が、追加のコストなしで利用できます。
Streamsが登場する前は、スコアを時刻としたSorted Setを作る必要がありました。Sorted Setの要素は、別のキーにHashとして存在する試合のIDでした。これは単に手間が増えるだけでなく、信じられないほどのメモリの無駄でもあります。想像している以上に大きな無駄です（後述します）。
とりあえずここで示したいのは、Redis Streamsはある意味、時刻をキーとした追記専用のSorted Setであり、各要素が小さなHashであるということです。そしてこのシンプルさこそが、Redisにおけるモデリングの文脈では革命的なのです。
メモリ使用量
上記のユースケースは、単により堅牢なパターンだというだけの話ではありません。Streamによる解決策のメモリコストは、オブジェクトごとにSorted SetとHashを持つ従来のアプローチと比べてあまりにも異なるため、以前は現実的でなかったことが、今では十分に実現可能になっています。
先ほど紹介した構成で100万件の試合を格納した場合の数値は次のとおりです。
Sorted Set + Hash memory usage = 220 MB (242 RSS) Stream memory usage = 16.8 MB (18.11 RSS)
これは1桁以上の差（正確には13倍の差）であり、昨日までメモリ内に置くにはコストが高すぎたユースケースが、今では十分に現実的であることを意味します。この魔法の鍵はすべてRedis Streamsの内部表現にあります。マクロノードは非常にコンパクトなlistpackというデータ構造でエンコードされた複数の要素を含むことができます。listpackは例えば、意味的には文字列である整数をバイナリ形式でエンコードするといった工夫を担います。さらにその上でデルタ圧縮と同一フィールド圧縮を適用します。それでもIDや時刻によるシークが可能なのは、マクロノードがメモリ使用量を抑えるように設計された基数木で連結されているからです。これらすべてが合わさってメモリ使用量の少なさを実現していますが、面白いのは、ユーザーの視点からはStreamsを効率的にしている実装の詳細が一切見えないことです。
では簡単な計算をしてみましょう。100万エントリを約18MBのメモリで格納できるなら、1000万エントリは180MB、1億エントリは1.8GBです。わずか18GBのメモリで10億件のアイテムを持つことができるのです。
時系列データ
ここで指摘しておきたい重要な点は、Streamを使ってテニスの試合を表現した先ほどの使い方は、時系列データのためにRedis Streamを使う場合とは意味的に*大きく異なる*ということです。確かに論理的にはどちらも何らかのイベントをログに残しています。しかし根本的な違いが一つあります。一方ではログ記録とエントリの作成によってオブジェクトを具現化しているのに対し、時系列のケースでは、オブジェクトを表すわけではない外部で起きた何かを単に計測しているだけなのです。この違いは些細なものに思えるかもしれませんが、そうではありません。Redis Streamsは全順序を持つ小さなオブジェクトを作成し、それらのオブジェクトにIDを割り当てるためにも使える、という考えをRedisユーザーの皆様に持っていただくことが重要だと考えています。
とはいえ、時系列という最も基本的なユースケースでさえ、言うまでもなく非常に大きな意味を持ちます。なぜならStreams以前のRedisは、このユースケースに関しては少々お手上げだったからです。Streamsのメモリ特性や柔軟性に加え、長さに上限のあるStreamを作れること（XADDのオプションを参照）は、開発者にとって非常に重要なツールとなります。
まとめ
Streamsは柔軟で多くのユースケースを持っていますが、このブログ記事は短くまとめ、上記の例とメモリ使用量の分析における明確なメッセージを確実にお伝えしたいと思いました。すでに多くの読者にとっては自明のことだったかもしれませんが、ここ数ヶ月いろいろな方とお話しする中で、Streamsとストリーミングのユースケースが強く結び付けられ、あたかもそのデータ構造がそれにしか向いていないかのように捉えられている印象を受けました。実際はそうではありません :-)