是否存在用于存储关系的概率数据结构？

Question

我有数据库,用户订阅主题.目前,SQL数据库中存储了大约20 000个主题,20万个用户和200万个订阅.由于它的大小,数据库按主题分区,因此我无法在一个数据库查询中获取信息.有几个主题有10万个订阅,一对有10万,其他有数百或更少.

当一个事件发生时,它通常匹配几个主题,所以为了通知用户,我需要执行查询,例如"给我所有用户订阅主题x,y,z并执行集合的联合",以便一个用户获得新闻即使他同时订阅了主题x和z.

限制是:

• 联合集中必须没有重复项.(用户无法获取内容两次)
• 联合集中可能缺少大量用户.(如果有时候用户没有获得内容,那就不是那么糟糕,但它不能总是同一个主题的同一个用户)
• 可以订阅新主题而无需重建整个事物.

我想过为每个主题使用一组布隆过滤器,但是它们的约束是相反的:"用户要么没有订阅肯定,要么可能订阅".我需要一些类似"用户订阅肯定或可能不是"的内容.

有损哈希表可能是个好主意,但我不确定,如果它们可以像布隆过滤器那样具有内存效率,而且我担心它会永远是同一个用户,那就是缺少他主题中的内容.

你知道其他任何数据结构,这对解决这个问题有好处吗？

Answer 1

这可能不是您正在寻找的解决方案，但您可以利用 ElasticSearch 的术语过滤器并为每个用户提供一个如下所示的文档：

{
  "id": 12345,
  "topics": ["Apache", "GitHub", "Programming"]
}

术语过滤器直接响应“哪些用户订阅了至少其中一个主题”的查询，ES 在如何缓存和重新利用过滤器方面非常聪明。

它不是概率数据结构，但可以非常有效地解决这个问题。您需要使用scan api来序列化检索可能较大的 JSON 响应。如有必要，您可以将此解决方案扩展到分布在多台计算机上的数十亿用户，并且响应时间为 10 - 100 毫秒。您还可以找到主题之间的相关性（重要术语聚合）并使用 ES 作为进一步分析的引擎。

编辑：我在 Python 中实现了搜索和扫描/滚动 API 的使用，并得到了一些有趣的结果。我对这 2000 万个用户和 2 亿个订阅数据集进行了“订阅任意三个主题的用户”查询，一般来说，搜索本身会在 4 - 8 毫秒内完成。查询返回 350.000 - 750.000 个用户。

即使使用扫描/滚动 API，从 ES 中获取用户 ID 也会出现问题。在 Core i5 上，我似乎每秒只有 8200 个用户，因此不到 50 万/分钟（带有"_source": false）。查询本身如下所示：

{
  "filtered": {
    "filter": {
      "terms": {
        "topics": [ 123, 234, 345 ],
        "execution": "plain",
        "_cache": false
      }
    }
  }
}

在生产中，我将使用"execution": "bool"这样的方式，以便可以缓存部分查询结果并在其他查询中重新利用。我不知道获取结果的瓶颈是什么，服务器的 CPU 使用率为 50%，我在同一台机器上运行客户端的 python 脚本，利用elasticsearch.helpers.scan.