4

我正在尝试为我正在进行的项目制作“朋友流”。我在 Redis ZSETS 中保存了个人用户流。就像是：

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 个元素的 ZSETS 时，ZUNIONSTORE 会很慢。

我真的很想让 Redis 在 ZSETS 上进行合并排序，并将结果限制为几百个元素。是否有任何现成的数据存储可以满足我的需求？如果没有，是否有任何框架来开发类似 redis 的数据存储？

我想我可以只 fork Redis 并添加我需要的功能，但我希望避免这种情况。

4

1 回答 1

2

人们倾向于认为 zset 只是一个跳过列表。这是错误的。它是一个跳过列表（有序数据结构）加上一个无序字典（实现为哈希表）。必须定义合并操作的语义。例如，您将如何合并其共同项目不具有相同分数的非不相交 zset？

要为 ZUNIONSTORE 实现合并算法，您必须对项目进行排序（使用跳过列表很容易），在构建输出时合并它们（恰好也是一个 zset：skiplist 加字典）。

因为在算法开始时无法猜测结果的基数，所以我认为不可能在线性时间内构建这个跳过列表+字典。充其量是 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 回答