database - 哪些分页方案可以处理快速变化的内容列表？

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 页之前，很多项目都在移动。数据库现在是:

+----+----------+-----------+
| 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;

在某些情况下，这比 page/offset 效果更好。但在我们的例子中，最后看到的帖子 Dogs 直接放大到 #1。所以客户端发送了 ?last_seen_id=4，我的页面 2 是 Bats, Alpacas, Elephants and Foxes。我没有错过任何动物，但我看到了两次 bat 和羊驼。

服务器端状态

HackerNews(以及我们现在的网站)通过服务器端延续解决了这个问题；他们为您存储整个 结果集(或至少提前几页？)，并且“更多”链接引用该延续。当我获取第 2 页时，我要求“我的原始查询的第 2 页”。它使用相同的偏移量/限制计算，但由于它是针对原始查询的，所以我根本不关心事情现在已经发生了变化。我看到大象、狐狸、长颈鹿和马。没有重复，没有遗漏元素。

缺点是我们必须在服务器上存储大量状态。在 HN 上，它存储在 RAM 中，实际上，这些延续通常在您按下“更多”按钮之前就过期了，迫使您一直返回到第 1 页以找到有效链接。在大多数应用程序中，您可以将其存储在 memcached 中，甚至可以存储在数据库本身中(使用您自己的表，或者在 Oracle 或 PostgreSQL 中，使用可保持游标)。根据您的应用程序，可能会影响性能；至少在 PostgreSQL 中，您必须找到一种方法来再次建立正确的数据库连接，这需要大量的粘性状态或一些巧妙的后端路由。

只有这三种可能的方法吗？如果没有，是否有计算机科学概念可以让我谷歌果汁来阅读这个？有没有办法在不存储整个结果集的情况下近似延续方法？从长远来看，存在复杂的事件流/时间点系统，其中“我获取第 1 页时的结果集”永远是可导出的。缺少那个...？

Answer 1

Oracle 很好地处理了这个问题。只要游标处于打开状态，您就可以根据需要多次提取，并且您的结果将始终反射(reflect)游标打开的时间点。它使用撤消日志中的数据来虚拟回滚游标打开后提交的更改。

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

不幸的是(IMO)，我不知道有任何其他数据库可以像这样工作。我使用过的其他数据库使用锁来确保读取一致性，如果您希望在非常短的时间内保持读取一致性，这就会出现问题。