Feed 算法 + 数据库：要么行太多，要么检索速度太慢

Question

假设我有一个通用网站，允许某人在短时间内下载他们的 feed。一个用户可以 subscribed 到许多不同的 pages，并且用户的 feed 必须从服务器 returned 到最多只有 N 的用户最近订阅的所有页面之间 posts。最初当用户向服务器查询 feed 时，算法如下：

查看所有pages个用户subscribed到
从每个 page

N

posts

对所有 posts
return N 最近 post 用户作为他们的 feed

事实证明，每次用户尝试刷新提要时都这样做真的很慢。因此，我将数据库更改为具有 feedposts 的 table，它仅具有指向用户的外键和指向 post 的外键。每次页面创建一个新 post 时，它都会为其每个订阅的关注者创建一个供稿 post。这样，当用户想要他们的提要时，它已经创建并且不必在检索时创建。

我这样做的方式是创建太多的行，而且似乎无法扩展。例如，如果一个页面有 1 post 并且有 1,000,000 个关注者，那么我们刚刚在 feedpost table 中创建了 1,000,000 个新行。

请帮忙！ facebook等公司是如何处理这个问题的？他们会根据要求生成提要吗？我的数据库关系很糟糕吗？

Answer 1

这并不是说原始架构本身就存在错误，至少根据您提供的高级描述而言并非如此。缓慢的原因是您没有以应该访问关系数据库的方式访问数据库。

一般来说，在查询关系数据库时，应尽可能使用 JOIN 和数据库内排序，而不是获取一堆数据，然后尝试连接相关对象并在代码中对它们进行排序。如果你让数据库为你做这一切，它会更快，因为它可以利用索引，并且只访问那些实际需要的对象。

根据经验，如果您需要对 Python 代码中 QuerySet 的结果进行排序，或者遍历多个查询集并以某种方式组合它们，您很可能会这样做出了点问题，你应该弄清楚如何让数据库为你做。当然，并非每次都如此，但肯定足够频繁了。

让我试着用一段简单的代码来说明。假设您有以下型号：

class Page(models.Model):
    name = models.CharField(max_length=47)
    followers = models.ManyToManyField('auth.User', related_name='followed_pages')

class Post(models.Model):
    title = models.CharField(max_length=147)
    page = models.ForeignKey(Page, related_name='posts')
    content = models.TextField()
    time_published = models.DateTimeField(auto_now_add=True)

例如，您可以使用以下单行代码获取当前登录用户后跟页面的最后 20 个帖子的列表：

latest_posts = Post.objects.filter(page__followers=request.user).order_by('-time_published')[:20]

这会对您的数据库运行单个 SQL 查询，其中只有 returns（最多）20 个匹配的结果，除此之外别无其他。由于您要连接所有涉及的表的主键，因此它将方便地为所有连接使用索引，从而使其非常快。事实上，这正是关系数据库旨在高效执行的操作类型。

Answer 2

缓存将是这里的解决方案。您将不得不减少数据库读取，与缓存读取相比，数据库读取要慢得多。

您可以使用 Redis 之类的东西来缓存 post。为了更好地理解，这里有一个惊人的答案

Is Redis just a cache

每个页面都可以分配一个键，您可以在该键下提取该页面的所有 post。

您不需要缓存所有内容，只需缓存重新发送的 M posts，其中 M>>N 并且足够安全以减少数据库 calls.Now 如果用户请求 posts超出了最新的M，那么可以直接从数据库中获取。

现在，当您必须生成提要时，您可以进行数据库调用以获取所有订阅的页面（或者您也可以放入缓存中），然后只获取所需数量的 post来自缓存。

这里的问题是使缓存保持最新。

为此，您可以使用 django-signals 之类的东西。每当添加新的 post 时，也使用信号将其添加到缓存中。

因此，对于每个数据库写入，您也必须写入缓存。但是你不必从数据库中读取，因为 Redis 是一个内存数据存储，与标准关系数据库相比它非常快。

编辑：这些是更多的文章，可以帮助更好地理解

Does Stack Exchange use caching and if so, how

How Twitter Uses Redis to Scale - 105TB RAM, 39MM QPS, 10,000+ Instances

Feed 算法 + 数据库：要么行太多，要么检索速度太慢

Feed Algorithm + Database: Either too many rows or too slow retrieval

database

django

algorithm

web-services

relational-database