Пагинация и курсоры

1) Зачем нужна пагинация

Пагинация ограничивает объем данных, передаваемых и рендеримых клиентом, снижает нагрузку на хранилища/сети и задает детерминированный способ «прогулки» по коллекции. В реальных системах пагинация — это не только `page=1&limit=50`, а набор протокольных контрактов и инвариантов согласованности.

• Контроль латентности и памяти на запрос.
• Стабильная навигация при изменении набора данных (вставки/удаления).
• Возможность возобновления с места (resumption).
• Кеширование и предзагрузка (prefetch).
• Защита от злоупотреблений (rate limiting, backpressure).

2) Модели пагинации

2.1 OFFSET/LIMIT (страничная)

Идея: «пропусти N строк, верни M».
Плюсы: простота, совместимо почти с любым SQL/NoSQL.

• Линейная деградация: большие OFFSET приводят к полному сканированию/skip-cost.
• Нестабильность при вставках/удалениях между запросами (смещения «плавают»).
• Трудно обеспечить точную «возобновляемость».

sql
SELECT
FROM orders
ORDER BY created_at DESC, id DESC
OFFSET 1000 LIMIT 50;

2.2 Cursor/Keyset/Seek-пагинация

Идея: «продолжай с ключа K». Курсор — это позиция в отсортированном наборе.

• O(1) доступ к продолжению при наличии индекса.
• Стабильность при изменениях коллекции.
• Лучшая латентность на глубоких «страницах».

• Нужны строго определенные, уникальные и монотонные ключи сортировки.
• Сложнее реализации и отладки.

sql
-- Resumption after steam (created_at, id) = (:last_ts,:last_id)
SELECT
FROM orders
WHERE (created_at, id) < (:last_ts,:last_id)
ORDER BY created_at DESC, id DESC
LIMIT 50;

2.3 Continuation tokens (непрозрачные токены)

Идея: сервер возвращает opaque-токен, в котором закодирована «позиция» (и, возможно, состояние шардов/фильтров). Клиент не понимает внутренностей и просто возвращает токен для следующей страницы.
Плюсы: гибкость, возможность менять схему без ломки API.
Минусы: управление сроком жизни токенов, совместимость при деплоях.

2.4 Временные и логические курсоры

Time-based: «все записи до T», курсор — метка времени (подходит при append-only потоках).
Log-sequence/offset-based: курсор — смещение в логе (Kafka offset, journal seq).
Global monotonic IDs: Snowflake/UUIDv7 как сортируемые ключи для стабильного seek.

3) Проектирование курсов и токенов

3.1 Свойства хорошего курсора

Непрозрачность (opaque): клиент не зависит от формата.
Авторство/целостность: подпись HMAC, чтобы предотвратить подмену/манипуляцию.
Контекст: включает сортировку, фильтры, версию схемы, tenant/shard.
Срок жизни: TTL и «неподнимаемость» (non-replay) при смене индексов/прав доступа.
Размер: компактный (<= 1–2 KB), пригодный для URL.

3.2 Формат токена

Рекомендуемый стек: JSON → сжатие (zstd/deflate) → Base64URL → HMAC.

json
{
"v": 3 ,//token version
"sort": ["created_at:desc","id:desc"],
"pos": {"created_at":"2025-10-30T12:34:56. 789Z","id":"987654321"},
"filters": {"user_id":"42","status":["paid","shipped"]},
"tenant": "eu-west-1",
"shards": [{"s ": "a, "" hi":"..."}] ,//optional: cross-shard context
"issued_at": "2025-10-31T14:00:00Z",
"ttl_sec": 3600
}

Сверху добавляется `mac = HMAC(secret, payload)` и все кодируется в один строковый токен.

3.3 Безопасность

Подписывать (HMAC/SHA-256).
Опционально шифровать (AES-GCM) при наличии чувствительных значений (PII).
Валидация на сервере: версия, TTL, полномочия пользователя (RBAC/ABAC).

4) Согласованность и инварианты

4.1 Стабильная сортировка

Используйте полный детерминизм: `ORDER BY ts DESC, id DESC`.
Ключ сортировки должен быть уникальным (добавляйте `id` как tiebreaker).
Индекс должен соответствовать сортировке (covering index).

4.2 Снимки (snapshot) и изоляция

Для «нескачущих» страниц используйте read-consistent snapshot (MVCC/txid).
Если снапшот нецелесообразен (дорого/много данных), формулируйте контракт: «курсор возвращает элементы, строго ранее позиции». Это естественно для новостных лент.

4.3 Вставки/удаления между страницами

Seek-модель минимизирует «дубликаты/пропуски».
Документируйте поведение при удалении/изменении: допускаются редкие «дырки» между страницами, но не «назад во времени».

5) Индексирование и схемы идентификаторов

Композитные индексы строго в порядке сортировки: `(created_at DESC, id DESC)`.
Монотонные ID: Snowflake/UUIDv7 дают порядок по времени → ускоряют seek.
Горячие ключи: распределяйте по shard-key (например, `tenant_id`, `region`) и сортируйте внутри шарда.
Генераторы ID: избегайте коллизий и «часов из будущего» (clock skew) — синхронизация времени, «регрессия» при NTP-прыжках.

6) Кросс-шардовая пагинация

6.1 Схемы

Scatter-Gather: параллельные запросы во все шарды, локальные seek-курсы, затем k-way merge на агрегаторе.
Per-Shard Cursors: токен содержит позиции по каждому шарду.
Bounded fan-out: ограничивайте число шардов за один шаг (rate limiting/timeout budget).

6.2 Токены для multi-shard

Храните массив `{shard_id, last_pos}`. На следующем шаге возобновляйтесь для каждого активного шарда и снова мержите, отдавая глобально отсортированную страницу.

7) Протокольные контракты

7.1 REST

GET /v1/orders? limit=50&cursor=eyJ2IjoiMyIsInNvcnQiOiJjcmVh... (opaque)

json
{
"items": [ /... / ],
"page": {
"limit": 50,
"next_cursor": "eyJ2IjozLCJwb3MiOiJjcmVh...==",
"has_more": true
}
}

• `limit` с верхней границей (например, max=200).
• `next_cursor` отсутствует, если `has_more=false`.
• Идемпотентность GET, кэшируемость ответов без `next_cursor` (первая страница при фиксированных фильтрах и snapshot).

7.2 GraphQL (Relay-подход)

graphql type Query {
orders(first: Int, after: String, filter: OrderFilter): OrderConnection!
}

type OrderConnection {
edges: [OrderEdge!]!
pageInfo: PageInfo!
}

type OrderEdge {
node: Order!
cursor: String! // opaque
}

type PageInfo {
hasNextPage: Boolean!
endCursor: String
}

`cursor` должен быть непрозрачным и подписанным; не используйте «сырой Base64(id)» без HMAC.

7.3 gRPC

proto message ListOrdersRequest {
string filter = 1;
int32 page_size = 2;
string page_token = 3; // opaque
}

message ListOrdersResponse {
repeated Order items = 1;
string next_page_token = 2; // opaque bool has_more = 3;
}

7.4 Потоки и WebSockets

Для непрерывных лент: курсор как «последний увиденный offset/ts».

json
{ "action":"subscribe", "topic":"orders", "resume_from":"2025-10-31T12:00:00Z#987654321" }

8) Кеширование, предзагрузка, CDN

ETag/If-None-Match для первой страницы со стабильными фильтрами.
Cache-Control с коротким TTL (например, 5–30 с) для публичных списков.
Prefetch: возвращайте `next_cursor` и подсказки (`Link: rel="next"`), клиент может предзагрузить следующую страницу.
Вариации: учитывайте `filter/sort/locale/tenant` как ключ части кеша.

9) Управление нагрузкой и лимитирование

Верхняя граница `limit`, например 200.
Server-side backpressure: если время запроса > budget, уменьшайте `limit` в ответе (и явно сообщайте клиенту фактический размер страницы).
Rate limits на пользователя/токен/tenant.
Timeout/Retry: экспоненциальная пауза, идемпотентные повторные запросы.

10) UX-аспекты

Скролл против нумерации: бесконечная прокрутка → курсоры; номерные страницы → offset (но объясните неточность при обновлении данных).
Кнопка «вернуться на место»: храните стек курсоров клиента.
Пустые страницы: если `has_more=false`, не показывайте кнопку «Еще».
Стабильные границы: показывайте точный `total` только если он дешев (иначе — приблизительный `approx_total`).

11) Тестирование и edge-кейсы

• Стабильная сортировка: элементы с одинаковым `ts` не «мигают».
• Вставки/удаления: не появляются повторы на стыке страниц.
• Изменение фильтров между страницами: токен должен отклоняться как «устаревший/несовместимый».
• TTL токена: корректная ошибка по истечении срока.
• Большая глубина: латентность не растет линейно.
• Мультишард: корректный merge-порядок, отсутствие starvation «медленных» шардов.

python
Generate N entries with random inserts between calls
Verify that all pages are merged = = whole ordered fetch

12) Наблюдаемость и SLO

• `list_request_latency_ms` (P50/P95/P99) по длине страницы.
• `seek_index_hit_ratio` (доля запросов, ушедших по покрывающему индексу).
• `next_cursor_invalid_rate` (ошибки валидации/TTL/подписи).
• `merge_fanout` (кол-во задействованных шардов на страницу).
• `duplicates_on_boundary` и `gaps_on_boundary` (детект на клиентской телеметрии).

• Коррелируйте `cursor_id` в логах, маскируйте payload.
• Тегируйте спаны: `page_size`, `source_shards`, `db_index_used`.

• Доступность: 99.9% на `List` методы.
• Латентность: P95 < 200 мс для `page_size<=50` при локальном шарде.
• Ошибка токена: < 0.1% от общего числа вызовов.

13) Миграции и совместимость

Включайте `v` в токене и поддерживайте старые версии N недель.
При смене ключей сортировки — отправляйте «мягкую» ошибку `409 Conflict` с подсказкой выполнить свежий листинг без курсора.
Катастрофический случай (ревок всех токенов): меняйте `signing_key_id` и отклоняйте старые.

14) Примеры реализаций

14.1 Генерация токена (псевдокод)

python payload = json. dumps({...}). encode()
compressed = zlib. compress(payload)
mac = hmac_sha256(signing_key, compressed)
token = base64url_encode(mac + compressed)

14.2 Валидация токена

python raw = base64url_decode(token)
mac, compressed = raw[:32], raw[32:]
assert mac == hmac_sha256(signing_key, compressed)
payload = json. loads(zlib. decompress(compressed))
assert now() - payload["issued_at"] < payload["ttl_sec"]
assert payload["filters"] == req. filters

14.3 Seek-запрос с композитным ключом

sql
-- Page # 1
SELECT FROM feed
WHERE tenant_id =:t
ORDER BY ts DESC, id DESC
LIMIT:limit;

-- Next pages, continued after (ts0, id0)
SELECT FROM feed
WHERE tenant_id =:t
AND (ts <:ts0 OR (ts =:ts0 AND id <:id0))
ORDER BY ts DESC, id DESC
LIMIT:limit;

15) Безопасность и соответствие

Не включайте в токены сырые поля, из которых можно вывести PII.
Подписывайте и ограничивайте TTL.
Старайтесь делать токены непереносимыми между пользователями (вписывайте `sub/tenant/roles` в payload и сверяйте при валидации).
Логируйте только хеши токенов.

16) Частые ошибки и анти-паттерны

Base64(id) как курсор: легко подделать/подобрать, ломает контракт при смене сортировки.
Отсутствие tie-breaker: `ORDER BY ts DESC` без `id` → дубликаты/скачки.
Смена фильтров между страницами без инвалидирования токена.
Глубокий OFFSET: медленно и непредсказуемо.
Токены без версии и TTL.

17) Мини-чеклист внедрения

1. Определите сортировку и добавьте уникальный tie-breaker.
2. Создайте покрывающий индекс под этот порядок.
3. Выберите модель: seek + непрозрачный токен.
4. Реализуйте подпись (и, при необходимости, шифрование) токена.
5. Заложите TTL и версионирование.
6. Сформулируйте и задокументируйте контракты `has_more`, `next_cursor`.
7. Продумайте кросс-шардовую схему (если нужно) и k-way merge.
8. Добавьте метрики, алерты и SLO.
9. Покройте property-based тестами границы страниц.
10. Опишите миграционную стратегию токенов.

18) Краткие рекомендации по выбору подхода

Каталоги/поиски, где важен «номер страницы» и приблизительный total: допустим `OFFSET/LIMIT` + кэш; сообщайте, что total приблизителен.
Ленты, аналитика, глубокие списки, высокие RPS: только cursor/seek.
Шардированные/распределенные коллекции: per-shard cursors + merge токен.
Потоки/CDC: курсоры как offsets/ts с возобновлением.

19) Пример договоренности API (резюме)

`GET /v1/items?limit=50&cursor=...`

Ответ всегда включает `page.limit`, `page.has_more`, опционально `page.next_cursor`.
Курсор непрозрачный, подписанный, c TTL.
Сортировка детерминирована: `ORDER BY created_at DESC, id DESC`.
Поведение при изменениях набора: элементы не «возвращаются назад» относительно курсора.
Метрики и ошибки стандартизированы: `invalid_cursor`, `expired_cursor`, `mismatch_filters`.

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