Пагинация

У меня уже было пару постов про пагинацию, но хочется свести это всё в один + докинуть какой-то интересной инфы.

Пишу пост про пагинацию раз в год.

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

Я буду рассказывать про то, как можно решать задачу отображения большого количества данных в условиях stateless бекенда. Т.е. когда вы не хотите хранить информацию про запросы пользователей на подах/в базе/ещё где-либо.

Два основных подхода -- использование offset и курсора (можно сказать, что второе есть общий случай первого). 

Первый -- это указание, как много данных стоит пропустить от начала выдачи. После того, как вы получили первые 1000 значений, можно запросить тот же запрос с offset=1000 и получить следующие 1000 значений.

Простой пример -- сервис, который раздаёт данные. Например, мы продаём автомобили марки ОООО. У нас есть сервис, который знает про все возможные модели автомобилей. Другие сервисы ходят в него и забирают информацию про эти модели. Но моделей слишком много, чтобы получить все разом. Код ручки, раздающей данные, может выглядеть примерно так:

std::unordered_map<ModelId, ModelData> models; // мапка, чтобы при обновлении могли быстро вставлять данные
...
// где-то в коде ручки
std::vector<ModelData> result;
for (auto& [id, data] : models) {
  result.push_back(data);
}

std::ranges::sort(result);

auto left = result.begin() + request.offset;
auto right = std::min(result.begin() + request.offset + request.limit, result.end()); // псевдокод

return std::vector<ModelData>(left, right);

Видел, как строчку с сортировкой забывали, из-за чего при перехешировании мапки порядок элементов менялся (прям в процессе ответов на запросы) -> в итоговом результате регулярно терялось очень много данных. И это даже не сразу обнаружили как проблему!

Оффсет может быть чуть более сложным, чем просто число (например номер страницы и номер последнего элемента на последней странице), но суть одна -- сдвиг от начала. 

Проблема тут в том, что это может быть неэффективно. Например, если данные берутся из базы: вам необходимо сделать ваш [тяжёлый] запрос (мб с сортировкой и прочим) с чем-то вроде OFFSET 1000 LIMIT 100, читай отбросить первую тысячу результатов (== выкинуть работу в мусорку) и взять следующую нужную пачку. Чем больше данных и чем меньше размер одного батча, тем больше работы мы делаем зря. Ещё данные иногда приходится грузить в память (что не так плохо, когда у вас какой-нибудь новостной сайт без персонализации, т.к. тут данные могут переиспользоваться, но для чего-то более сложного не катит). И не очень хорошо работает, когда есть вставки/удаления.

Потому появился так же способ с помощью курсора. В базовом случае это может быть какой-то идентификатор (по сути индекс) строки в бд, которую можно получить быстро и выбрать после неё нужное количество данных. Удобно.

В более общем случае курсор может быть произвольного вида. Например для поисковой выдачи мы можем сделать курсор как множество метаданных для каждого дополнения нужного запроса:

[запрос: моло]

cursor: {
 молоко: {
  skip: 12,
  min_relevant: 0.57,
 },
 молочное: {
  skip: 27,
  min_relevant: 0.13,
 }
}

В примере выше по этому курсору можно попробовать снова сгенерить поисковую выдачу и просто отрезать первые skip позиций в ответе (важно, чтобы выдача генерировалась стабильно, иначе вы легко потеряете релевантные результаты). Или это может быть хеш данных, которые были получены последними, вроде ASdlakBLADSoPVDOUA. Или вместо явного курсора ещё можно генерить ссылку на следующую пачку данных. Или вот в Твиттере дают id первого и последнего объекта со страницы [2]. При таких подходах сложнее узнавать кол-во данных, но ниже вероятность их потерять (кроме случаев, когда запись, на которой основан курсор, удалили).

Понимать, что пагинация окончена, можно разными способами:

• дополнительное поле в респонсе (что в целом ок, но зачем, если можно следующий вариант?)
• присылать пустой курсор/не присылать никакой курсор вовсе
• повторять курсор. Правда так лучше не делать, т.к. это приводит к лишнему запросу на бекенд и некоторым артефактам на фронтенде, если делается пререндеринг контента.

Иногда пагинацию сделать корректно невозможно. Например когда у вас выдача нестабильная, но хочется показать пользователю очень много результатов. Тогда можно костылить. Например, сделать два запроса асинхронно: один маленький (например, на 20 айтемов, чтобы быстро отобразить первые результаты), а второй большой (например, на 200 айтемов, чтобы показать ещё много всего). И дедуплицировать результаты на клиенте (чтобы ничего не повторялось). Если надо, сделать ещё один запрос пошире (на 400 айтемов, например). Зачем расширять запрос, надеюсь, понятно.

Hashcash

Hashcash активно используется в разных криптоштуках в качестве proof-of-work. Но мы посмотрим на него в контексте пагинации.

С реализацией пагинации могут быть некоторые проблемы, если выдача у вас нестабильная. То есть офсет и курсор это круто, если множество данных у вас плюс-минус фиксировано и их порядок не меняется (плюс-минус, потому что можно добрасывать новое в конец и ничего в моменте не сломать). Но такая ситуация не всегда имеет место быть.

Например, вы хотите сделать пагинацию для рекомендаций. При каждом запросе у вас происходит полный цикл процесса рекомендаций, в конце которого находится ранжирование. Т.к. это обычно машинное обучение и фичей бывает очень много (или мы можем переобучаться в онлайне), сущность, которую вы отранжировали на 1-ю позицию в первом запросе, при втором запросе может вполне себе отранжироваться на 21-ю. И с оффестов 20 во втором запросе вы получите в выдаче то, что уже показывали. Почти наверняка это плохое решение, потому что пользователь уже видел этот контент и денег больше вы не заработаете. Да и выглядит тупо.

В зависимости от реализации поискового движка может возникнуть та же проблема. 

Получается, надо где-то сохранить инфу о том, что мы пользователю уже показывали. Учитывая, что эта инфа валидна только для конкретного юзера, на ум приходят варианты что-нибудь где-нибудь закешировать (например в Redis сложить и смотреть, есть ли инфа про конкретный запрос), но такой подход добавляет много технических сложностей. А давайте кешировать в курсоре! Пусть наш курсор теперь -- конкатенация хешей от объектов, которые мы уже показали пользователю. И из рекомендательной системы отдадим эту строку как курсор клиенту, после чего он может прислать этот курсор обратно, а мы уже поймём по нему, что мы показывали, а что нет. 

Хешировать тут можно всё что хотите. Хорошим вариантом будет какой-нибудь уникальный для каждой сущности idшник, множество которых вы просто заджойните в одну длинную строку. Потом можно засплитить эту строку по разделителю в множество хешей и проверить, какие айтемы вы уже пользователю отдавали, а какие нет. Это конечно может быть долговато, но можно покрутить хеш-функцию. 

А можно не просто хешировать id, а хранить в курсоре стейт фильтра Блума. Когда вы восстановите состояние фильтра Блума по курсору, вы сможете проверять, был ли уже показан такой-то товар. Для рекомендаций использование вероятностной структуры данных в целом подходит. Но если хочется использовать такой подход в поиске, надо быть осторожным: тут пространство для ошибки гораздо меньше, т.к. нельзя не показывать товар просто потому что так получилось.

Собственно примерно поэтому и называется hashcash: вы кешируете множество объектов с помощью их хеширования.

Ещё из проблем тут есть:

• т.к. хеширование двух различных объектов может давать один хеш, вы можете отсеять что-то, что на самом деле не показывали, но, насколько я могу понимать, это обычно не крит, потому что с таким же успехом товар мог отфильтроваться на каком-нибудь другом этапе рекомендаций (отбор кандидатов, после ранжирования оказаться слишком низко, реранкинг). Если такое возникает часто, опять же можно посмотреть в сторону других хеш-функций, которые дают более разнообразные результаты/покрутить фильтр Блума и прочее;
• т.к. с каждым запросом кол-во показанных сущностей растёт, сам курсор тоже будет расти. Тут можно выбрать какое-то ограничение для длины курсора с трейдоффом кол-во показанного юзеру контента <-> технические возможности вашей системы. Если вы понимаете, что из всех пользователей долистывает до 300-ого айтема только полпроцента, может не так страшно не показывать больше 300 объектов? Ну и длинную строку парсить на бекенде не хочется, т.к. это потенциально таймауты (а ещё та же проблема на клиенте, а ещё нагрузка на сеть вырастает). Можно выбрать хеш-функцию так, чтобы она давала более короткие хеши, но тут важно не переборщить, чтобы не получить прошлую проблему в большом объёме. 

Ещё один кейс

Давайте представим такую задачу:

• у нас есть 3 сервиса с рекомендациями. Каждый из них рекомендует какие-то свои айтемы.
• мы хотим принимать от всех них айтемы по общему протоколу и клеить в одну общую выдачу, для каждого пользователя определяя, данные от какого сервиса ему наиболее релевантны. То есть кто-то в результате может увидеть почти всё от service-1 и пару айтемов от service-2/service-3, а кто-то --равномерное распределение данных от всех сервисов. Это мы должны решать отдельной моделью в сервисе, который собирает данные.
• наша общая выдача должна быть пагинируемой. Т.е. каждый из сервисов должен уметь поддерживать эту пагинацию.

Первое, что приходит на ум, это поддерживать курсор от каждого сервиса и возвращать их вместе с результатами запроса на клиент, а он в свою очередь следующий запрос сделает с этими курсорами. Звучит отлично! Т.к. ни клиент, ни Собиратель ничего про это теперь не знают. Они просто шлют курсор туда-сюда и не думают про детали его реализации.

Всё бы ничего, но мы же всё-таки хотим подбирать наиболее релевантные данные в зависимости от пользователя. Тогда лучше сделать иначе. Т.к. клиент запрашивает не более N айтемов, можно сходить в каждый сервис за данными, попросив ровно столько:

После того, как Собиратель получил 3N айтемов, он может отранжировать их релевантность и вернуть клиенту N итоговых значений. При этом каждый сервис уже считает, что на этот запрос он вернул некоторые N товаров, что и поддерживает в своём курсоре. Но ведь мы уже не показали некоторые товары пользователю, когда Собиратель их доранжировал и отрезал лишнее! Тогда, если сделать следующий запрос, мы их больше никогда не сможем отобразить. А вдруг они были очень релевантными!

Добивается эта задача некрасиво. Зато работает. Создаём курсор (что-нибудь вроде hashcash, в который просто через разделитель складываем id айтемов) на Собирателе/клиенте, а сервисы-поставщики учим его парсить.

Links:

[1]. Five ways to paginate in Postgres, from basic to exotic. 

[2]. Paginating Real-Time Data with Cursor Based Pagination.