ニコニコ生放送に見る Redis 活用ノウハウ

第4回 Redisを用いたアプリケーション開発(2)

この記事を読むのに必要な時間:およそ 4.5 分

前回紹介した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)です。

図1 SET型の集合演算

図1 SET型の集合演算

上図では2つのセット間の演算を示していますが,実際には2つ以上のセットを指定できます。

また,演算結果を直接返すのではなく,別のセットに格納するバージョン(SINTERSTORE, SUNIONSTORE, SDIFFSTORE)もあり,演算頻度の軽減のため一時的に結果を保存しておきたい場合や,結果に対してさらに別の演算を行いたい場合はこちらが便利です。

SET型を使ったタグ検索

SET型の基本操作にひと通り触れてみるために,定番の例として「タグ検索」機能をSET型で実装することを考えてみましょう。

各タグごとに,そのタグに関連するコンテンツIDを格納するSETが用意されているとします。次の図は,2つのタグ「踊ってみた(tag:dance)」「歌ってみた(tag:sing)」と,それぞれに関連するコンテンツIDが格納されたSETを図示しています。

図2 タグとコンテンツIDの関連付け例

図2 タグとコンテンツIDの関連付け例

基本的なタグの操作は,次のようなコードになるでしょう。

<?php
 // タグにコンテンツIDを関連付ける
 function tagset_add($tag_id, $content_id) {
   $redis = new Redis();
   $redis->connect('localhost', 6379);
   $redis->sAdd('tag:' . $tag_id, $content_id);
   $redis->close();
 }
 // タグとコンテンツIDの関連を削除する
 function tagset_remove($tag_id, $content_id) {
   $redis = new Redis();
   $redis->connect('localhost', 6379);
   $redis->sRemove('tag:' . $tag_id, $content_id);
   $redis->close();
 }
 // タグに関連するコンテンツIDを収得する
 function tagset_contents($tag_id) {
   $redis = new Redis();
   $redis->connect('localhost', 6379);
   $mems = $redis->sMembers('tag:' . $tag_id);
   $redis->close();
   return $mems;
 }

SETへの要素の追加はSADDコマンド,削除はSREMコマンドによって操作します。タグに関連するコンテンツIDをすべて取得するには,そのSETの要素をSMEMBERSコマンドで取得することで実現できます。

次に,複数のタグでAND検索することを考えてみます。前述の「歌ってみた」「踊ってみた」の両方のタグが関連付いたコンテンツを検索するには,両者のSETに対してSINTERコマンドで積集合を取ることで,AND検索が実現できます。

SINTER tag:dance tag:sing

実際のアプリケーションではもう少し後処理が必要になるかもしれません。例えば,検索結果から「R18」タグに関連するコンテンツを除外したい,といった場合です。この場合のコマンド実行例は次のようになります。

SINTERSTORE tmpset tag:dance tag:sing
SDIFF tmpset tag:r18

SINTERSTOREコマンドで,AND検索の結果を一時的な別のセット(tmpset)に格納した後,SDIFFコマンドによって,検索結果から「R18」タグに関連するにコンテンツIDを除いたものを取得します。

以上のコマンド操作をプログラムで実装すると次のようになります。なお,簡単のため,検索対象のタグは2つだけ取るようにしています。

<?php
 function tagset_search($tag_id1, $tag_id2) {
   $redis = new Redis();
   $redis->connect('localhost', 6379);
   // 指定されたタグのAND検索結果をtmpset1に格納
   // SINTERSTORE tmpset1 タグ1 タグ2
   $tmpset1 = /*適当なテンポラリキーを生成*/;
   $redis->sInterStore($tmpset1,
                       'tag:' . $tag_id1,
                       'tag:' . $tag_id2);
   // R18タグに関連するコンテンツを除外してtmpset2に格納
   // SDIFFSTORE tmpset2 tmpset1 tag:r18
   $tmpset2 = /*適当なテンポラリキーを生成*/;
   $redis->sDiffStore($tmpset2, $tmpset1, 'tag:r18');
   // アクセス数の多い順にソート
   // SORT tmpset2 BY access_count:* DESC
   $result = $redis->sort($tmpset2,
               array('sort'=>'desc', 'by'=>'access_count:*'));
   $redis->close();
   return $result;
 }

前回,LIST型に対するSORTコマンドの操作を紹介しましたが,実はSET型にも適応できます。このコードでは,検索結果に対して最後にSORTコマンドを実行することで,アクセス数でソートした結果を取得しています。

容量の問題

上記の手法によるタグ検索の問題は,Redisの特性上,タグとコンテンツIDの関連がすべてメモリに格納されるため,データ量に限界があるということです。しかも集合演算のためには,対象となるSETが同じRedisサーバー上に存在する必要があるため,分散も効きません。

本来であればRedis VMによってある程度解決できる問題であったはずですが,連載第1回でも言及したとおり,残念ながらパフォーマンスや安定性に問題があります。そのため,Redis2.4に控えるdiskstoreの登場を待つか,その先のRedis Clusterに期待するしかありません。

ただし,データセットがメモリの収まるように制御できるのであれば,とても高速で効果的であるのは間違いありません。その実例を次に紹介します。

著者プロフィール

小野侑一(おのゆういち)

株式会社ドワンゴ ニコニコ生放送システムリーダー。

ニコニコ生放送での開発経験を通して,ウェブをリアルタイム化する技術の重要性に着目。その成果としてリアルタイムタグ検索やRedisを活用したリアルタイム視聴者集計システムを開発。現在は全文検索のリアルタイム化に注目している。

Twitter@synk

コメント

コメントの記入