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

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`.

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