27

大家好，提前感谢。我是 NoSQL 游戏的新手，但我目前的工作地点要求我对一些大数据进行设置比较。

我们的系统有客户标签集和目标标签集。标签是一个 8 位数字。
一个客户标签集可能有多达 300 个标签，但平均有 100 个标签
目标标签集可能有多达 300 个标签，但平均有 40 个标签。

预先计算不是一种选择，因为我们正在为 10 亿用户的潜在客户群进行拍摄。

（这些标签是分层的，所以有一个标签意味着你也有它的父标签和祖先标签。暂时把这些信息放在一边。）

当客户访问我们的网站时，我们需要尽快将他们的标签集与一百万个目标标签集相交。客户集必须包含要匹配的目标集的所有元素。

我一直在探索我的选择，Redis 中的设置交叉点似乎是理想的。然而，我在互联网上的拖钓并没有透露需要多少内存才能容纳一百万个标签集。我意识到交叉口会快如闪电，但这是 Redis 的可行解决方案吗？

我意识到这是蛮力和低效的。我还想用这个问题来获得有关过去处理此类问题的方法的建议。如前所述，标签存储在树中。我也开始将 Mongodb 视为一种可能的解决方案。

再次感谢

4

3 回答 3

29

这是一个有趣的问题，我认为 Redis 可以在这里提供帮助。

Redis 可以使用优化的“intset”格式存储整数集。有关更多信息，请参阅http://redis.io/topics/memory-optimization。

我相信这里正确的数据结构是目标标签集的集合，加上将标签映射到目标标签集的反向索引。

存储两个目标标签集：

 0 -> [ 1 2 3 4 5 6 7 8 ]
 1 -> [ 6 7 8 9 10 ]

我会使用：

 # Targeted tag sets
 sadd tgt:0 1 2 3 4 5 6 7 8
 sadd tgt:1 2 6 7 8 9 10
 # Reverse index
 sadd tag:0 0
 sadd tag:1 0
 sadd tag:2 0 1
 sadd tag:3 0
 sadd tag:4 0
 sadd tag:5 0
 sadd tag:6 0 1
 sadd tag:7 0 1
 sadd tag:8 0 1
 sadd tag:9 1
 sadd tag:10 1

当从系统中添加/删除目标标签集时，这个反向索引很容易维护。

全局内存消耗取决于多个目标标签集共有的标签数量。在 Redis 中存储伪数据并模拟内存消耗非常容易。我使用简单的 node.js 脚本完成了它。

对于 100 万个目标标签集（标签为 8 位数字，每组 40 个标签），当目标标签集共享的标签很少（反向索引中超过 32M 条目）时，内存消耗接近4 GB ，当标签被大量共享时，大约500 MB（反向索引中只有 100K 条目）。

使用这种数据结构，查找包含给定客户的所有标签的目标标签集非常有效。

1- Get customer tag set (suppose it is 1 2 3 4)
2- SINTER tag:1 tag:2 tag:3 tag:4
   => result is a list of targeted tag sets having all the tags of the customer

交集操作是高效的，因为 Redis 足够聪明，可以按基数对集合进行排序，并从具有最低基数的集合开始。

现在我知道您需要实现相反的操作（即找到目标标签集，其所有标签都包含在客户标签集中）。反向索引仍然可以提供帮助。

这是一个丑陋的伪代码示例：

1- Get customer tag set (suppose it is 1 2 3 4)
2- SUNIONSTORE tmp tag:1 tag:2 tag:3 tag:4
   => result is a list of targeted tag sets having at least one tag in common with the customer
3- For t in tmp (iterating on the selected targeted tag sets)
      n = SCARD tgt:t (cardinality of the targeted tag sets)
      intersect = SINTER customer tgt:t
      if n == len(intersect), this targeted tag set matches

因此，您无需针对 1M 目标标签集测试客户标签集。您可以依靠反向索引将搜索范围限制在可接受的范围内。

于 2012-06-19T20:10:02.873 回答
6

这可能会有所帮助：

案例研究：在非常大的集合上使用 Redis 相交（120M+ 和 120M+）

http://redis4you.com/articles.php?id=016&name=Case+Study%3A+Using+Redis+intersect+on+very+large+sets

于 2012-08-29T15:34:53.387 回答
5

提供的答案最初对我有帮助。然而，随着我们客户群的增长，我偶然发现了一种很棒的技术，它涉及使用 redis 字符串位和位运算符来非常快速地对数亿用户执行分析。

看看这篇文章。Redis 的创建者 Antirez 也经常引用这一点。

http://blog.getspool.com/2011/11/29/fast-easy-realtime-metrics-using-redis-bitmaps/

于 2013-02-20T20:50:08.990 回答