Какие схемы разбивки на страницы могут обрабатывать быстро меняющиеся списки контента?

Разбивка на страницы сложна, когда рейтинг вашего контента может быстро меняться, и еще сложнее, когда этот рейтинг различается для каждого пользователя. (Давайте будем рассматривать бесконечную прокрутку как тип страницы, где ссылки невидимы.) Есть две серьезные проблемы: недавно добавленный контент вверху и переоцененный контент.

Давайте забудем о недавно добавленном контенте и согласимся с тем, что вам придется обновить страницу 1, чтобы посмотрите на это. Давайте также представим, что мы делаем чистый ORDER BY position; если вы упорядочиваете что-то еще, вам, возможно, придется использовать оконные функции. Наши страницы имеют 4 ряда животных на странице. Они начинаются out:

+----+----------+-----------+
| 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. Слонов я никогда не увижу, а коров увижу дважды.

Идентификатор последнего увиденного

Reddit использует другой подход. Вместо того, чтобы вычислять первую строку на основе размера страницы, клиент отслеживает идентификатор последнего элемента, который вы видели, как закладку. Когда вы нажимаете «Далее», они начинают искать с этой закладки и далее:

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

В некоторых случаях это работает лучше, чем страница/смещение.Но в нашем случае «Собаки», последний просмотренный пост, увеличился прямо до № 1. Итак, клиент отправляет ?last_seen_id=4, а моя страница 2 — это летучие мыши, альпаки, слоны и лисы. Я не пропустил ни одного животного, но дважды видел летучих мышей и альпак.

Состояние на стороне сервера

HackerNews (и наш сайт прямо сейчас) решает эту проблему с помощью продолжений на стороне сервера; они хранят для вас весь набор результатов (или, по крайней мере, несколько страниц заранее?), а ссылка «Дополнительно» ссылается на это продолжение. Когда я получаю страницу 2, я запрашиваю «страницу 2 моего исходного запроса». Он использует тот же расчет смещения/предела, но, поскольку он противоречит исходному запросу, меня просто не волнует, что теперь все изменилось. Я вижу слонов, лис, жирафов и лошадей. Нет дубликатов, нет пропущенных элементов.

Недостатком является то, что нам приходится хранить много информации о состоянии на сервере. В HN это хранится в ОЗУ, и на самом деле эти продолжения часто истекают, прежде чем вы сможете нажать кнопку «Дополнительно», что вынуждает вас вернуться на страницу 1, чтобы найти действительную ссылку. В большинстве приложений вы можете сохранить это в memcached или даже в самой базе данных (используя свою собственную таблицу или в Oracle или PostgreSQL, используя удерживаемые курсоры). В зависимости от вашего приложения производительность может снизиться; по крайней мере, в PostgreSQL вам нужно найти способ снова установить правильное соединение с базой данных, что требует большого количества фиксированных состояний или какой-то умной внутренней маршрутизации.

Это единственные три возможных подхода? Если нет, то существуют ли концепции информатики, которые дадут мне возможность прочитать об этом в Google? Существуют ли способы аппроксимации метода продолжения без сохранения всего набора результатов? В долгосрочной перспективе существуют сложные системы потоковой передачи событий/на определенный момент времени, в которых «набор результатов на момент получения первой страницы» всегда можно вывести. Если не считать этого... ?