4

自分が取り組んでいるプロジェクトの「フレンドストリーム」を作成しようとしています。個々のユーザーのストリームをRedisZSETSに保存しています。何かのようなもの：

key : { stream_id : time }
user1-stream: { 1:9931112, 3:93291, 9:9181273, ...}
user2-stream: { 4:4239191, 2:92919, 7:3293021, ...}
user3-stream: { 8:3299213, 5:97313, 6:7919921, ...}
...

user4-friends: [1,2,3]

今のところ、user4のフレンドストリームを作成するには、次のように呼び出します。

ZUNIONSTORE user4-friend-stream, [user1-stream, user2-stream, user3-stream]

ただし、合計1〜2000個を超える要素のZSETをマージしようとすると、ZUNIONSTOREの速度が低下します。

RedisにZSETSでマージソートを実行させ、結果を数百要素に制限してもらいたいと思っています。私がやりたいことをする既製のデータストアはありますか？そうでない場合、redisのようなデータストアを開発するためのフレームワークはありますか？

Redisをフォークして必要な機能を追加するだけでよいと思いますが、それを避けたいと思っていました。

4

1 に答える 1

2

人々は、zsetは単なるスキップリストであると考える傾向があります。これは間違っています。これは、スキップリスト（順序付けされたデータ構造）と順序付けされていない辞書（ハッシュテーブルとして実装）です。マージ操作のセマンティクスを定義する必要があります。たとえば、共通のアイテムが同じスコアを持たない互いに素でないzsetをどのようにマージしますか？

ZUNIONSTOREのマージアルゴリズムを実装するには、アイテムを並べ替えて（スキップリストで簡単に）、出力を作成するときにそれらをマージする必要があります（これは、zsetでもあります：スキップリストと辞書）。

結果のカーディナリティはアルゴリズムの最初では推測できないため、このスキップリスト+辞書を線形時間で作成することは不可能だと思います。せいぜいO（n log n）になります。したがって、マージは線形ですが、出力の構築は線形ではありません。マージアルゴリズムを使用する利点が失われます。

ここで、ZUNIONを実装し（つまり、結果をzsetとしてビルドするのではなく、結果を直接返す）、結果を特定の数のアイテムに制限する場合は、マージアルゴリズムが理にかなっています。

マージ結合をサポートするRDBMSは通常それを行うことができます（ただし、ランダムI / Oのコストのため、これは通常あまり効率的ではありません）。同様の機能をサポートしているNoSQLストアを知りません。

Redisで実装するには、Luaサーバーサイドスクリプトを試すことができますが、複雑な場合があり、zsetがzunionで提供されている制限よりもはるかに大きい場合にのみ効率的だと思います。その場合、アイテム数の制限により、インタープリターされたLuaコードを実行するオーバーヘッドが相殺されます。

最後の可能性は、RedisソースコードのCで実装することですが、これはそれほど難しくありません。欠点は、使用するRedisバージョンのパッチを維持する負担です。Redis自体はそれを行うためのフレームワークを提供しておらず、Redisプラグイン（Redisソースコードから分離されている）を定義するというアイデアは、通常、作成者によって拒否されます。

于 2012-08-17T19:17:56.967 に答える