寻找1 x 100万套路口的最佳解决方案？Redis,Mongo,其他

Question

大家好,提前谢谢.我是NoSQL游戏的新手,但我现在的工作地点让我对一些大数据进行了比较.

我们的系统具有客户标签集和目标标签集.标签是8位数字.
客户标签集最多可包含300个标签,但平均为100个标签
.目标标签集最多可包含300个标签,但平均为40个标签.

由于我们正在为十亿用户的潜在客户群拍摄,因此预先计算不是一种选择.

(这些标签是分层的,因此有一个标签意味着你也有它的父标签和祖先标签.暂时把这些信息放在一边.)

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

我一直在探索我的选择,Redis中的集合交集似乎是理想的.然而,我在互联网上的拖钓并没有透露需要多少公羊才能容纳一百万个标签.我意识到交叉点会很快,但这对Redis来说是一个可行的解决方案.

我意识到这是蛮力和低效率.我也想用这个问题作为获取过去处理这类问题的方法的建议.如前所述,标签存储在树中.我已经开始将Mongodb视为一种可能的解决方案.

再次感谢

Answer 1

这是一个有趣的问题,我认为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目标标记集测试客户标记集.您可以依赖反向索引将搜索范围限制在可接受的范围内.

Answer 2

这可能会有所帮助:

案例研究:使用Redis在非常大的集合上交叉(120M + 120M +)

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

Answer 3

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

看看这篇文章.Redis的创造者Antirez也引用了很多.

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