前回紹介したRedisのLIST型に続き、今回はSET型とSORTED SET型について、その構造とWebアプリケーション開発への応用を紹介します。
SET型の構造
RedisのSET型は、重複のない文字列要素の集合を保持するデータ型です。Javaのコレクションフレームワークをご存知の方には、「HashSet」のようなもの、と想像していただくと分かりやすいかと思います。
LIST型のPUSHやPOPと同様、SET型への追加/削除の時間計算量はO(1)となり、理論上はサイズに関係なく一定時間で操作できることになります。実際、ニコニコ生放送のシステムでは、要素数にして数万規模のSET型に対して、分間数千~数万回の追加操作を行っています。
一見、SET型のデータ構造は単純すぎて、アプリケーションで活用する機会が想像しにくいかもれません。RedisにはHash型という連想配列のように使えるデータ型もあるため、単にオブジェクト情報を格納するならSET型よりもHash型のほうが良さそうです。SET型の利点とはなんでしょうか。
実は、SET型には集合演算という強力な武器があるのです。
集合演算
SET型には3種類の集合演算コマンドが用意されています。積集合(SINTER)、和集合(SUNION)、差集合(SDIFF)です。
上図では2つのセット間の演算を示していますが、実際には2つ以上のセットを指定できます。
また、演算結果を直接返すのではなく、別のセットに格納するバージョン(SINTERSTORE, SUNIONSTORE, SDIFFSTORE)もあり、演算頻度の軽減のため一時的に結果を保存しておきたい場合や、結果に対してさらに別の演算を行いたい場合はこちらが便利です。
SET型を使ったタグ検索
SET型の基本操作にひと通り触れてみるために、定番の例として「タグ検索」機能をSET型で実装することを考えてみましょう。
各タグごとに、そのタグに関連するコンテンツIDを格納するSETが用意されているとします。次の図は、2つのタグ「踊ってみた(tag:dance)」「歌ってみた(tag:sing)」と、それぞれに関連するコンテンツIDが格納されたSETを図示しています。
基本的なタグの操作は、次のようなコードになるでしょう。
SETへの要素の追加はSADDコマンド、削除はSREMコマンドによって操作します。タグに関連するコンテンツIDをすべて取得するには、そのSETの要素をSMEMBERSコマンドで取得することで実現できます。
次に、複数のタグでAND検索することを考えてみます。前述の「歌ってみた」と「踊ってみた」の両方のタグが関連付いたコンテンツを検索するには、両者のSETに対してSINTERコマンドで積集合を取ることで、AND検索が実現できます。
実際のアプリケーションではもう少し後処理が必要になるかもしれません。例えば、検索結果から「R18」タグに関連するコンテンツを除外したい、といった場合です。この場合のコマンド実行例は次のようになります。
SINTERSTOREコマンドで、AND検索の結果を一時的な別のセット(tmpset)に格納した後、SDIFFコマンドによって、検索結果から「R18」タグに関連するにコンテンツIDを除いたものを取得します。
以上のコマンド操作をプログラムで実装すると次のようになります。なお、簡単のため、検索対象のタグは2つだけ取るようにしています。
前回、LIST型に対するSORTコマンドの操作を紹介しましたが、実はSET型にも適応できます。このコードでは、検索結果に対して最後にSORTコマンドを実行することで、アクセス数でソートした結果を取得しています。
容量の問題
上記の手法によるタグ検索の問題は、Redisの特性上、タグとコンテンツIDの関連がすべてメモリに格納されるため、データ量に限界があるということです。しかも集合演算のためには、対象となるSETが同じRedisサーバー上に存在する必要があるため、分散も効きません。
本来であればRedis VMによってある程度解決できる問題であったはずですが、連載第1回でも言及したとおり、残念ながらパフォーマンスや安定性に問題があります。そのため、Redis2.4に控えるdiskstoreの登場を待つか、その先のRedis Clusterに期待するしかありません。
ただし、データセットがメモリの収まるように制御できるのであれば、とても高速で効果的であるのは間違いありません。その実例を次に紹介します。
ニコニコ生放送のリアルタイム視聴者集計
ニコニコ生放送の公式番組では、毎回、数万人分の視聴者のセグメント分布を分析し、のちの番組制作に役立てています。
従来この分析を行うには、放送翌日のバッチ処理によって視聴ログが集計されるまで待たなくてはなりませんでしたが、現在はRedisのSET型と集合演算を駆使することにより、この集計を“放送中”に、リアルタイムに参照できるようになっています。
これらの分析情報は放送中だけRedisに格納しておけばよいので、前述のタグ検索のようにメモリ容量の限界を気にする必要がないのです。
リアルタイム視聴者集計の仕組み
番組IDごとに、視聴したユーザーのIDを格納するSETを用意します。SETはセグメント(性別、年代、地域、等)ごとに用意し、ユーザーが視聴ページを開いたタイミングで、該当するセグメント別SETにそのユーザーのIDを格納します。
表1 セグメント別SET(実際とは異なります)
性別 | userid:man:番組ID
userid:woman:番組ID |
年代 |
userid:20:番組ID
userid:30:番組ID |
地域 |
userid:kantou:番組ID
userid:touhoku:番組ID |
SETに格納した要素は自動的にユニークになるため、SCARDコマンドでそれぞれのセグメント別SETの要素数をカウントすれば、その時点での各セグメントのユニーク視聴者数が分かるという仕組みです。さらに、複数のセグメント別SETに集合演算を掛けることで、より細かくセグメントを組み合わせて分析をおこなうことができます。
SORTED SET型の構造
最後に紹介するデータ型は、SORTED SET型です。簡単にいえば、SET型の各要素に順序付けのための“スコア”が付随したもの、と考えることができます。
重複のない要素を保持する点や、集合演算(積集合と和集合)が用意されているなど、基本的にはSET型と同様の使い勝手です。
SORTED SET型ではさらに、スコアで順序付けされた要素の並びを範囲取得することができるのが特徴です。
範囲指定取得
範囲指定取得の方法は2通りあり、指定したインデックスの範囲内を取得するZRANGEと、スコアの下限と上限を指定するZRANGEBYSCOREがあります。加えて、ソート順序を逆順(降順)で取得するZREVRANGEコマンド等が用意されています。
表2 ZRANGE系コマンド
ZRANGE | インデックス範囲の要素を取得する。順序はスコアの昇順。 |
ZREVRANGE | ZRANGEの降順バージョン |
ZRANGEBYSCORE | スコア範囲の要素を取得する。順序はスコアの昇順。 |
ZREVRANGEBYSCORE | ZRANGEBYSCOREの降順バージョン(バージョン2.2から) |
LIST型との使い分け
SORTED SET型では、要素の追加時にスコアを設定することで、任意の基準で順序付けられた状態を保持できます。また、個々の要素のスコアを更新することで、常に適切な順序に保つことができます。
LIST型の場合、先頭や末尾への要素追加を行うので、自ずと要素の追加順の並びになります。任意の基準で順序付けしたい場合は、都度SORTコマンドに外部キーを指定してソートする必要があります。
ここで問題になるのは、SORTコマンドの頻度が高い場合、全体のパフォーマンスが影響を受ける可能性があることです。Redisのコマンドは基本的にシングルスレッドで処理されるため、巨大なソートが頻繁に走るような状態だと、その間、他のコマンド処理がブロックされてしまいます。
このため我々のシステムでは、時系列順(追加順)で参照される箇所にLIST型を、特定の順序で参照される箇所にはSORTED SET型を、と使い分けています。
- LIST型の使用例
- リアルタイムログ(追加順)
- 開始時間順のユーザー番組一覧(時系列順)
- 更新通知キュー(追加順)
- SORTED SET型の使用例
- 人気順番組ランキング(視聴者数やコメント数順)
- コンテンツタイムアウトリスト(最終参照日時順)
コンテンツのアクセス数順リストの構築
前回のSORTコマンドの例で紹介した、コンテンツのリストをアクセス数によってソートする事例を、SORTED SET型で実装してみます。
キー名“contents_zset”でSORTED SETを用意し、ZADDコマンドによってコンテンツIDを追加します。追加の際、アクセス数をスコアの初期値としてセットしています。
アクセス数は最初、0から始まり、徐々に増えていくはずです。アクセス数が変化したら、コンテンツIDに付随するスコアも更新する必要があります。
既に追加済みにコンテンツIDに対して上記のコードを実行すると、スコアが上書きされ、適切な位置に並び替えられます。この例ではアクセス数をスコアとしているので、毎回スコアを上書きするよりも、ユーザーがコンテンツにアクセスする度にスコアを1づつインクリメントするほうが簡単です。つまり、スコアをアクセス数カウンタ代わりに使ってしまうわけです。
スコアのインクリメントにはZINCRBYコマンドを使います。
最後に、アクセス数のトップ10を取得してみます。ZREVRANGEコマンドを使って、スコアの降順にコンテンツIDを取得します。
以上が、SORTED SET型の基本的な操作です。
LIST型もSORTED SET型も、複数要素の並びを格納することができる高速で使い勝手のよいデータ構造となっていますが、それぞれの特徴を知ることにより、開発の場面ごとにより適切に使い分けられると思います。
コンテンツのタイムアウト制御の実装
SORTED SET型の応用例として、ニコニコ生放送での事例を一つ紹介します。
我々のサービスでは様々なコンテンツ情報をRedisに格納していますが、Redisのメモリ容量には限りがあるため、一定時間参照されないコンテンツはメモリから消去する必要があります。
このような場合、通常はEXPIREコマンドを使えばよいのですが、タイムアウトしたコンテンツ情報が完全に消えてしまうのがまずい場合もあります。そこで我々は、一定期間参照されなかったコンテンツをプログラムで検出し、MySQLに退避する仕組みを実装しました。手順は次の通りです。
- コンテンツIDを格納するSORTED SETを用意します。スコアとして、そのコンテンツの最終参照時刻のタイムスタンプをセットします。
- コンテンツが参照されるたびに、スコアを現在時刻で更新します。SORTED SETの内部は、常に最終参照時刻で並んだ状態になります。
- ZRANGEBYSCOREコマンドを使って、最終参照時刻が退避基準時刻(例えば現在時刻の24時間前)よりも古いコンテンツIDを列挙します。
- 列挙されたコンテンツIDを元に、関連する情報をRedisから回収/削除し、必要な情報をMySQLにバックアップしていきます。
ニコニコ生放送のようなコンシューマー向けのWebサイトでは、一部のコンテンツにアクセスが偏る場合があります。上記のような仕組みがあれば、アクティブなコンテンツはRedisに格納し、それ以外をMySQLに退避してしまうことができるため、RedisとMySQLの両方の強みを活かすことができます。
おわりに
4回に渡って、Redisの導入から応用例までを紹介してきました。
著者がRedisを調べようと思ったのは、「永続化できるオンメモリKVS」という特徴に興味を持ったからなのですが、実際に使っていくうちにRedisのデータ型のもたらす応用力、シンプルながら多様な処理が可能となる点に驚き、それこそがRedisの最大のアドバンテージだと思うようになりました。本連載の後半では特にその点をお伝えしたかったのですが、いかがでしたでしょうか。
しかし一方、MySQLのようなデータベースと異なり、データ容量についてシビアにコントロールが必要となる点について注意が必要です。そのため現時点では、あくまでメインのデータベースにはMySQL等を使い、Redisはその補助として、極端な高頻度更新やリアルタイム性が求められる箇所に限定して、効果的に使っていくのがよいでしょう。
今後、バージョン2.4でdiskstore(データをディスクに格納する機能)、3.0でRedis Cluster(複数のRedisサーバーでクラスタを構成する機能)が登場する予定ですので、データ容量の制限を乗り越える日が来るかもしれません。開発者のSalvatore Sanfilippo氏とPieter Noordhuis氏、ならびに開発コミュニティの活躍に期待したいと思います。