我有一个包含用户订阅主题的数据库。目前大约有2万个主题，2000万用户和2亿订阅存储在SQL数据库中。由于它的大小，数据库是按主题分区的，所以我不能在一个数据库查询信息。有几个话题有1000万的订阅量，有几个有10万的订阅量，还有一些只有几百甚至更少。
当一个事件发生时，它通常匹配几个主题，所以为了通知用户，我需要执行类似于"给我所有订阅了主题x, y, z的用户并执行集合并"的查询，这样一个用户即使订阅了主题x和z也能获得一次新闻。
约束条件是:
- 联合集中不能有重复项。(用户不能获得两次内容)
- 联合集中可能有有限数量的用户缺失。(如果有时用户没有得到的内容，它不是那么糟糕，但它不能总是相同的用户为同一主题)
- 可以订阅新主题，而无需重新构建整个主题。
我想过对每个主题使用一组bloom过滤器，但它们的约束是相反的:"用户要么不确定订阅，要么可能订阅"。我需要一些像"用户是否订阅了"之类的东西。
有损哈希表可能是个好主意，但我不确定，如果它们能像布隆过滤器一样内存效率高，我担心，它总是同一个用户，那就是缺少了他的主题中的内容。
你知道其他的数据结构，可能是解决这个问题的好方法吗?
如果每个用户记录都有一个BIT FIELD表示所有的主题会怎么样呢?
TABLE Users(ID INT, UserName VARCHAR(16)， Topics BINARY(8000))
二进制8k将允许您拥有64000个主题。我可能会使用多列BINARY(1024)，这样我可以很容易地添加更多的主题。
现在，当一个标记为主题1,10,20,30,40的事件进来时。我必须搜索每个用户，但这可以并行化，复杂度总是N，其中N是总用户数。
SELECT ID
FROM Users (READPAST)
WHERE
SUBSTRING(Topics, 1 / 8, 1) & (1 * POWER(2, (1 % 8))) > 0
OR
SUBSTRING(Topics, 10 / 8, 1) & (1 * POWER(2, (10 % 8))) > 0
OR
SUBSTRING(Topics, 20 / 8, 1) & (1 * POWER(2, (20 % 8))) > 0
OR
SUBSTRING(Topics, 30 / 8, 1) & (1 * POWER(2, (30 % 8))) > 0
OR
SUBSTRING(Topics, 40 / 8, 1) & (1 * POWER(2, (40 % 8))) > 0
OPTION (MAXDOP = 64)
- 没有重复我们扫描用户一次，所以我们不必担心联合
- 一些用户缺少 READPAST提示将跳过当前锁定(正在更新)的任何行，因此一些用户可能从结果中丢失。
- 订阅您可以[un]订阅一个主题，只需通过切换主题列中的主题位。
正如我在评论中所说，基于内存的精确解决方案当然是可行的。
但是如果你真的想要一个近似的数据结构，那么你要找的是一个大小有限的集合(每个主题的用户)，随机抽取。
您还需要在查询到达时快速计算联合。这里没有有用的预计算。如果主题集倾向于重复，您可以考虑缓存频繁使用的联合。
表示集合的所有常用方法都适用。哈希表(封闭的和开放的)、树和跳跃表(都包含用户id键;不需要值)是最有可能的。
如果您使用具有良好哈希函数的封闭哈希表，则会自动发生伪随机驱逐。碰撞时，只需替换之前的值。闭合哈希的问题总是为需要表示的集合选择一个合适的表大小。记住，要恢复集合元素，你必须遍历包括空条目在内的整个打开的表，所以从一个巨大的表开始并不是一个好主意;不如从一个小元素开始，然后重新组织，每次增加一个因子，这样重组就可以平摊到每个存储元素的常量时间开销。
对于其他方案，当表变得太大时，您可以执行伪随机驱逐。公平驱逐的最简单方法是将用户id存储在一个表中，并使用限制大小的存储索引集。通过在表中生成随机索引并在添加新id之前删除该id来取消。
也可以通过使用顺序统计树来公平地从BST集合表示中驱逐:在每个节点中存储后代的数量。然后你总是可以找到按键排序的第n个元素，其中n是伪随机的，并将其驱逐。
我知道你在寻找布隆过滤器的按位空间效率，但保证没有误报似乎排除了这一点。
这可能不是您正在寻找的解决方案，但您可以利用ElasticSearch的术语过滤器，并为每个用户提供一个这样的文档:
{
"id": 12345,
"topics": ["Apache", "GitHub", "Programming"]
}
Terms过滤器直接响应"哪些用户订阅了这些主题中的至少一个"的查询，ES在如何缓存和重用过滤器方面非常聪明。
这将不是一个概率数据结构，但将非常有效地解决这个问题。您需要使用scan api来序列化检索可能较大的JSON响应。如果需要，您可以将此解决方案扩展到分布在多台计算机上的数十亿用户，并且响应时间为10 - 100毫秒。您还可以找到主题之间的相关性(重要术语聚合)，并使用ES作为进一步分析的引擎。
Edit:我在Python中实现了搜索和扫描/滚动API的使用，并得到了一些有趣的结果。我对2000万用户和200万订阅数据集进行了"订阅其中任意三个主题的用户"查询，一般来说，搜索本身在4 - 8毫秒内完成。查询返回35万- 75万用户。
即使使用扫描/滚动API，从ES中获取用户id也会出现问题。在酷睿i5上，我似乎只有8200个用户/秒，所以它不到50万/分钟(使用"_source": false)。查询本身看起来像这样:
{
"filtered": {
"filter": {
"terms": {
"topics": [ 123, 234, 345 ],
"execution": "plain",
"_cache": false
}
}
}
}
在生产中，我将使用"execution": "bool"，以便可以缓存部分查询结果并在其他查询中重用。我不知道得到结果的瓶颈是什么，服务器的CPU使用率是50%，我在同一台机器上运行客户端的python脚本，利用elasticsearch.helpers.scan .
[这个解决方案类似于路易·里奇的，除了倒到主题表- 这可能使订阅更新不太实用，要警告!
)(概率数据结构方法很酷，但对于当前的数据大小来说没有必要。我最初着眼于压缩位集的非概率解决方案，因为它们非常适合在内存中执行集合操作，但我认为这也有点过头了。下面是这类用例的一个很好的实现。如果你感兴趣的话
但是看看数据的稀疏性， bitset比整型数组浪费空间。即使使用整数数组，考虑到每个主题平均只有10,000个订阅，union操作仍然非常便宜。所以也许，只是也许，在你的用例中，一个非常简单的数据结构就是:
Topic 1 => [array of subscriber IDs]
Topic 2 => [array of subscriber IDs]
...
Topic 20,000 => [array of subscriber IDs]
存储(平均)10,000个订阅者id(假设为32位整数)每个主题只需要大约40kb空间。
[在数组类型或BLOB中，取决于您的数据库]
对于20,000个主题，这只向主题表添加了800mb的数据…当通知事件发生时，需要将其中很少一部分(平均200kb)加载到内存中!
然后当一个平均事件(影响5个主题)发生时，需要发生的是:
查询/提取相关主题的数据(平均5条记录)到内存中(avg ~200kb of I/O)
将它们转储到Set数据结构中(删除重复用户列表)
通知集合中的订阅者。