什么分页方案可以处理快速变化的内容列表？

Question

当您的内容排名可以快速变化时,分页很难,当每个用户的排名不同时,分页就更难了.(让我们将无限卷轴视为一种链接不可见的分页.)有两个难题:顶部新添加的内容和重新排列的内容.

让我们忘记新添加的内容,并接受您必须刷新第1页才能看到它.我们也假装我们做的很纯粹ORDER BY position; 如果您按其他方式订购,则可能必须使用窗口功能.我们的页面每页有4行动物.他们开始:

+----+----------+-----------+
| id | position^|  animal   |
+----+----------+-----------+
|  1 |        1 | Alpacas   |
|  2 |        2 | Bats      |
|  3 |        3 | Cows      |
|  4 |        4 | Dogs      |
|  5 |        5 | Elephants |
|  6 |        6 | Foxes     |
|  7 |        7 | Giraffes  |
|  8 |        8 | Horses    |
+----+----------+-----------+

在我们获取第1页之后,在我们获取第2页之前,很多项目都会移动.DB现在是:

+----+----------+-----------+
| id | position^|  animal   |
+----+----------+-----------+
|  4 |        1 | Dogs      |
|  2 |        2 | Bats      |
|  1 |        3 | Alpacas   |
|  5 |        4 | Elephants |
|  6 |        5 | Foxes     |
|  7 |        6 | Giraffes  |
|  3 |        7 | Cows      |
|  8 |        8 | Horses    |
+----+----------+-----------+

有三种常见方法:

偏移/限制方法

这是典型的天真方法; 在Rails中,这就是will_paginate和Kaminari的工作方式.如果我想获取第2页,我会这样做

SELECT * FROM animals
ORDER BY animals.position
OFFSET ((:page_num - 1) * :page_size) 
LIMIT :page_size;

获得5-8行.我永远不会看到大象,我会看到奶牛两次.

最后看到ID方法

Reddit采用了不同的方法.客户端不是根据页面大小计算第一行,而是跟踪您看到的最后一项的ID,如书签.当您点击"下一步"时,他们会从该书签开始向前看:

SELECT * FROM animals
WHERE position > (
  SELECT position FROM animals 
  WHERE id = :last_seen_id
) 
ORDER BY position
LIMIT :page_size;

在某些情况下,这比页面/偏移更好.但在我们的案例中,最后看到的帖子Dogs缩小到#1.所以客户端发送?last_seen_id=4,我的第2页是Bats,Alpacas,Elephants和Foxes.我没有错过任何动物,但我两次看到蝙蝠和羊驼.

服务器端状态

HackerNews(以及我们的网站,现在)通过服务器端延续来解决这个问题; 它们为您存储整个结果集(或至少提前几页？),"更多"链接引用该延续.当我获取第2页时,我要求"我的原始查询的第2页".它使用相同的偏移/限制计算,但由于它与原始查询相反,我根本不关心事情现在已经移动了.我看到大象,狐狸,长颈鹿和马.没有重复,没有错过的项目.

缺点是我们必须在服务器上存储很多状态.在HN上,它存储在RAM中,实际上这些延续通常会在您按"更多"按钮之前到期,迫使您一直返回到第1页以查找有效链接.在大多数应用程序中,您可以将其存储在memcached中,甚至存储在数据库本身中(使用您自己的表,或者使用可保持的游标在Oracle或PostgreSQL中).根据您的应用程序,可能会有性能损失; 至少在PostgreSQL中,你必须找到一种方法来再次访问正确的数据库连接,这需要大量的粘性状态或一些聪明的后端路由.

这些是唯一可能的三种方法吗？如果没有,是否有计算机科学概念可以让我阅读这篇文章？有没有方法可以在不存储整个结果集的情况下逼近延续方法？从长远来看,存在复杂的事件流/时间点系统,其中"我获取第1页时的结果集"是永久可导出的.没错......？

Answer 1

Oracle处理得很好.只要光标处于打开状态,您就可以根据需要多次获取,结果将始终反映光标打开的时间点.它使用撤消日志中的数据虚拟回滚光标打开后提交的更改.

只要所需的回滚数据仍然可用,它就会起作用.最终日志被回收并且回滚数据不再可用,因此存在一些限制,具体取决于日志空间,系统活动等.

不幸的是(IMO),我不知道任何其他数据库是这样的.我使用的其他数据库使用锁来确保读取一致性,如果您希望读取一致性超过很短的持续时间,则会出现问题.

Answer 2

解决方案1:" hacky解决方案 "

解决方案可能包括您的客户端跟踪已经看到的内容,例如ID列表.每次需要其他页面时,都会将此ID列表添加到服务器调用的参数中.然后,您的服务器可以订购内容,删除已经看过的内容并应用偏移量来获取正确的页面.

我不会推荐它,但我坚持hacky.我只是把它写在这里,因为它很快,可以满足一些需求.这是我能想到的坏事:

1)在客户端需要做一些工作才能使它正确(在上面的句子中"已经看到"意味着什么,如果我转到上一页怎么办？)

2)结果订单不反映您的真实订购政策.内容可以显示在第2页中,尽管该策略应该将其放在第1页上.这可能会导致用户误解.让我们以堆栈溢出为例,使用其以前的排序策略,这意味着首先是最受欢迎的答案.我们可能有一个问题,第2页有6个upvotes,而第4页有4个upvotes的问题.当用户还在第1页时发生2个或更多的upvotes时会发生这种情况. - >对于用户来说可能会令人惊讶.

解决方案2:" 客户端解决方案"

它基本上是客户端等效的解决方案,你称之为"服务器端状态".只有在服务器端跟踪完整订单不够方便时才有用.如果项目列表不是无限的,它可以工作.

• 调用您的服务器以获取完整(有限)订单列表+项目/页面数
• 保存在客户端
• 直接通过内容的ID检索项目.

Answer 3

我们现在使用服务器端状态方法，缓存第一个查询的整个结果，以便我们始终返回一致的列表。只要我们的查询已经返回所有行，这就会起作用；最终我们需要使用最近邻方法，但这行不通。

但我认为还有第四种可能性，它的扩展性非常好，只要：

1. 您不需要保证不重复，只需要高可能性
2. 只要避免重复，在滚动过程中丢失一些内容就可以了

该解决方案是“最后看到的 ID”解决方案的一种变体：让客户保留 5 个、10 个或 20 个书签，而不是一个 - 数量足够少，以便您可以有效地存储它们。查询最终看起来像：

SELECT * FROM posts
WHERE id > :bookmark_1
AND id > :bookmark_2
...
ORDER BY id

随着书签数量的增加，出现以下情况的可能性会迅速减小：(a) 在某个时刻开始超过所有 n 个书签，但 (b) 无论如何都会看到重复的内容，因为它们都已重新排名。

如果将来有漏洞或者更好的答案，我会很乐意不接受这个答案。