Redisにできることとその限界、そしてデータ構造の基本

#まずは繰り言だ！

データ構造って、一番大まかに言って、同種のデータ同士の関係と、異種のデータ同士の関係がある。人同士の関係、出来事同士の関係、等が前者だとすれば、人と性別の関係とか、人と所属サークルの関係、なんていうのが後者だ。

で、その一番ざっくりした関係に加えて、ある向きに1対1の関係なのか1対多の関係なのか、逆方向に1対1の関係なのか1対多の関係なのか、というのがあって、これによって、それぞれ3通りに分類される。4通りではないのは、「ある向きに1対1、逆向きに1対多」と「ある向きに1対多、逆向きに1対1」とは同値だからだね。

でもって、これらの関係を持ったデータ群に対して、CRUDという基本操作がある。ここまでで完結するなら、それはRedisで充分、ということだ。

さらに次のレベルは、集合演算、順序付け、値の加減算、値の乗除算やその他の演算、変更可能なものとそうでないもの、など、データの「扱い」に関するテーマになるだろう。ただ、そこには敢えて踏み込まない。というか、この領域が本格的に必要になるならば、Redisでは力不足だ。RDBSやその他専用DBが必要になってくる。

もちろん、更なる応用として、部分一致を検索したいので、転置インデックスが必要、というパターンと、何らかの距離空間が定義されていて、距離空間上での操作が必要、というパターンがあるが、そこも本稿では扱わない。しかし、ものによってはRedisに向いているものもあるので、面白いのだ。このあたりはものすごく可能性があって、画像の特徴同士の距離空間を定義できれば類似画像検索みたいな技術になるし、差分の転置インデックス、なんていうものを作れば、編集履歴検索なんてのができて、それだけでちょっと強力なツールになるだろう。目下、転置と距離空間が一番可能性が高いと思うよ。機械学習だって、結局距離空間の扱いがキモになるわけだよね。

いつもどおり、余談が過ぎた。本題に戻ろう。

本稿の仮想コードは、CoffeeScript経由でRedis上にデータを登録するコードを元にしている。例えば、 SET foo:A1:bar = B1 とあったら、

redis = require("redis")
rcli  = redis.createClient()
rcli.SET ['foo:'+A1+':bar', B1],-> return

というコードでデータセットを追加できるということだ。

#データ構造いろいろ

##同種のデータの関係

Aから1つの別のA'への対応付け、A'から元を辿ると1つのA

【データ構造名】リンクリスト（全体が繋がっているなら）
応用：「背の順」など
解説：実際には、この程度のことにこんな構造を使うことは少ないだろうが、案外これが正解、ということもあるので、盲点にならないようにしたい。リンクリストがひとつながりになっている必要があるかどうかは要件次第だけど、いくつのリンクリストがあるかを探索できるようにするにはどうすれば良いか、わかるかな？

	SET relfoo:A1:next = A2
	SET relfoo:A2:prev = A1

Aから1つの別のA'への対応付け、A'から元を辿ると多くのA

【データ構造名】ツリー（全体が繋がっているなら）
応用：「組織図」など
解説：こういうまとめ方をしてみると、やはりツリー構造というのは基本なんだな、と思うよね。子供に順序があるかどうかで親→子の表現は変わる。順序が無ければ、SADDで良いわけだ。応用範囲が広いので、このデータ構造は大変様々な実装のバリエーションがある。長男と親が双方向で参照し合って、その他の子は兄弟と繋がっているような構造もあるし、入れ子区間モデルみたいな特殊な表現方法もある。要件に最も合った表現を見つけたいよね。

	SET   relfoo:A1:parent = A2
	LPUSH relfoo:A2:children = A1

Aから多くの別のA'への対応付け、A'から元を辿ると多くのA

【データ構造名】有向グラフ
応用：「フォロー関係など」
解説：Twitterのフォローにしても、リンク構造にしても、状態遷移グラフにしても、良く出てくる割に扱いが必ずしも効率的にやりにくいのがこのデータ構造。探索や巡回を効率的にやろうと思ったら、ちょいと工夫が要ることだろう。もちろん、無向グラフは有向グラフの特殊な形に過ぎないので、同じように扱える。ただし、無向グラフの場合は、下記の「to」と「from」は完全に一致するので、ふたつ持つ必要は無いよね。
なお、例えば閉じた3次元立体において、面と面の関係は、無向グラフで表せる。だけど、辺と辺の関係はどうだろう。なんか、やな感じだよね。敢えてデータ構造に納めるなら後述のハイパーグラフになる（エッジ＝サークルとして「面」を選ぶか、「頂点」を選ぶか、2通りの解釈があり得る）。頂点と頂点の関係は、無向グラフで表せるね。面白いもんだ。「辺」ってデータ構造の上で主役になりにくい、ってことだね。こういう風に、同じ対象でも「シンプルなデータ構造に納められるように主役を決めてあげる」というのが重要だ。3次元立体の場合は、まあ、自明なわけだが。

    SADD relfoo:A1:to = A2
    SADD relfoo:A2:from = A1

##異種のデータの関係

Aから1つのBへの対応付け、Bから元を辿ると1つのA

【データ構造名】1対1対応
応用：「ユーザーIDとセッションIDなど」
解説：1対1対応。あまりに自明で、出てくる場面も限られるが、扱わずに済むことはまずないので、超大事。たとえば、ユーザー名とユーザーID（連番）みたいな変換は当たり前に必要になる。上の例で上げた、ユーザーIDとセッションIDなんかの場合、生成したりEXPIREしたり、大変忙しい1対1対応なのだ。

    SET relfoo:A1:bar = B1
    SET relbar:B1:foo = A1

Aから1つのBへの対応付け、Bから元を辿ると多くのA

【データ構造名】属性
応用：「人と性別・住所など」
解説：RDBSで言うプライマリーキーとそれ以外のデータとの対応関係は、ほとんどの場合、コレだ。しかし、属性にはツリー状のカテゴリ階層があることが多いので、そのあたりが上手に扱えると素敵。時刻なんかの場合、曜日・旬・月・年みたいに、ツリーではなく、ラティス状のカテゴリ階層があるので、扱いは難しい。ある意味、一種の転置インデックスが必要、ってことなんだよ。ちなみに、どこだったか忘れたけど、曜日とか時間帯でも統計を取りたい、という質問に対して、「Redisには向かない、RDBS使え」っていう回答をしているのを見かけたことがあるけど、RDBSもそういうの、向いてないじゃんね。Redisに向いてなくて、RDBSに向いているのはむしろ「集約」の部分で、統計にはRedisは向いてない。RDBSだって重くなるけど、コーディングからして苦労する、ってことにはならない。ただし、常にリアルタイムで統計を提供したいんなら、仕様をがっちり固めてRedisで作り込んだ方が速くなるかもね。そこの柔軟性と性能はトレードオフにならざるを得ないと思うよ。
なお、値が数値ならソート済セット型に、値が文字列ならハッシュ型に全部放り込むのもひとつの手だ。本当は、辞書順をサポートする文字列版ソート済セット型があると素敵なのだが、そういうものは無い。

    SET  relfoo:A1:bar = B1
    SADD relbar:B1:foo = A1

Aから多くのBへの対応付け、Bから元を辿ると多くのA

【データ構造名】ハイパーグラフ
応用：「ユーザとコミュニティ・サークルなど」
解説：上の方に有向グラフが出てきたけど、さらにグラフを一般化するとコレになる。矢印には2つのメンバーしか居ないけど、これはメンバーの数に制約が無いわけだ。Wikipediaとか論文とかの説明は分かりにくいかも知れないが、ユーザとコミュニティの関係だと思えば分かりやすいだろう。なお、これを使うときには、総数の少ない方（ユーザとコミュニティならコミュニティ）を巡回できるように、SETに納めておくと良い。全探索なんて普段使いにはならないけど、バッチとか障害復旧とかで何かしら使う場面はありうるのよ。

    SADD relfoo:A1:bar = B1
    SADD relbar:B1:foo = A1

#後書きと追記

何の役に立つ記事かっていうと、Redisが通用する範囲を体感するためだ。道具には道具に適した応用範囲っていうものがあるからね。

で、あとはね。Redis Lua Scriptingは素敵。これで、悲観的ロック相当の処理ができる。ツリーの実装は、ムリにReadWriteロックを実装するんじゃなくて、ツリーノードの処理をひととおりLuaにやらせれば良いことが分かった。

でもね、クエリを通して起動するRedis Lua Scriptingも良いけどさ、なんでExpireにフックがかけられないのさ、って思う。高機能キャッシュなんだったら、RDBSとかへの書き戻しも、そこでできると有難いよね。Expireにフックがかけられないのはまあ百歩譲るとして、Redis Lua Scriptingで他のDBへのドライバ使えないんだよね。まあ、それってRDBSに待たされる可能性が有るから、できない理由は分かる。やりようは無かったのかな、僕もすぐには思いつかないけど。でも、その辺を解決する機構を持たないということは、前回のDB同期との差分を特定のQUEUEに積み込むLua Scriptとかを用意して、アプリケーション側でBLPOPとかで吸い出してRDBSと同期取ったりしないといけないわけで、結局その辺は凝ったことしないといけないのね、という覚悟は必要だと思う。次はその「賢い差分」というか、RDBSのキャッシュとしてのRedisを活用するコードでも考えてみるかな。