Paginierung und Cursor

1) Warum Pagination notwendig ist

Die Paginierung begrenzt die vom Client übertragene und gerenderte Datenmenge, reduziert die Speicher-/Netzwerkbelastung und legt eine deterministische Methode fest, um durch die Sammlung zu „laufen“. In realen Systemen ist Pagination nicht nur 'page = 1 & limit = 50', sondern eine Reihe von Protokollverträgen und Konsistenzinvarianten.

• Kontrolle von Latenz und Speicher auf Anfrage.
• Stabile Navigation bei Änderung des Datensatzes (Einfügen/Löschen).
• Möglichkeit der Wiederaufnahme aus dem Stand (Resumption).
• Caching und Vorladen (Prefetch).
• Schutz vor Missbrauch (Rate Limiting, Backpressure).

2) Paginationsmodelle

2. 1 OFFSET/LIMIT (Seite)

Die Idee: „N Zeilen überspringen, M zurückgeben“.
Vorteile: Einfachheit, kompatibel mit fast jedem SQL/NoSQL.

• Linearer Abbau: Große OFFSETs führen zu einem vollständigen Scan/Skip-Cost.
• Instabilität beim Einfügen/Entfernen zwischen Abfragen (Offsets „schweben“).
• Es ist schwierig, eine genaue „Erneuerbarkeit“ sicherzustellen.

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

2. 2 Cursor/Keyset/Seek-Pagination

Die Idee: „weiter mit dem K-Schlüssel“. Ein Cursor ist eine Position in einem sortierten Satz.

• O (1) Zugriff auf die Fortsetzung, wenn ein Index vorhanden ist.
• Stabilität bei Sammlungsänderungen.
• Bessere Latenz auf tiefen „Seiten“.

• Sie benötigen streng definierte, einzigartige und monotone Sortierschlüssel.
• Schwieriger zu implementieren und zu debuggen.

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 Token (undurchsichtige Token)

Die Idee: Der Server gibt ein Opaque-Token zurück, in dem die „Position“ (und möglicherweise der Zustand der Shards/Filter) kodiert ist. Der Kunde versteht die Interna nicht und gibt einfach das Token für die nächste Seite zurück.
Vorteile: Flexibilität, die Fähigkeit, das Schema zu ändern, ohne die API zu brechen.
Nachteile: Verwaltung der Lebensdauer von Token, Kompatibilität mit Deploys.

2. 4 Zeit- und Logikcursor

Zeitbasiert: „alle Einträge bis T“, Cursor - Zeitstempel (geeignet für Append-only-Streams).
Log-sequence/offset-based: Cursor - Offset im Log (Kafka offset, journal seq).
Global monotonic IDs: Snowflake/UUIDv7 als sortierbare Schlüssel für eine stabile Suche.

3) Gestaltung von Kursen und Token

3. 1 Eigenschaften eines guten Cursors

Opazität (opaque): Der Client ist unabhängig vom Format.
Urheberschaft/Integrität: HMAC-Signatur, um Spoofing/Manipulation zu verhindern.
Kontext: Enthält Sortierung, Filter, Schemaversion, tenant/shard.
Lebensdauer: TTL und „non-replay“ beim Wechsel der Indizes/Zugriffsrechte.
Größe: kompakt (<= 1-2 KB), geeignet für URLs.

3. 2 Token-Format

Empfohlener Stack: JSON → Kompression (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
}

Oben wird 'mac = HMAC (secret, payload)' hinzugefügt und alles in einem String-Token kodiert.

3. 3 Sicherheit

Signieren (HMAC/SHA-256).
Optional zu verschlüsseln (AES-GCM), wenn sensible Werte (PII) vorliegen.
Validierung auf dem Server: Version, TTL, Benutzerberechtigungen (RBAC/ABAC).

4) Konsistenz und Invarianten

4. 1 Stabile Sortierung

Verwenden Sie den vollständigen Determinismus: 'ORDER BY ts DESC, id DESC'.
Der Sortierschlüssel muss eindeutig sein ('id' als Tiebreaker hinzufügen).
Der Index muss der Sortierung (Covering Index) entsprechen.

4. 2 Snapshots (Snapshot) und Isolation

Verwenden Sie für „nicht abbildende“ Seiten den read-consistent snapshot (MVCC/txid).
Wenn der Snapshot unpraktisch ist (teuer/viele Daten), formulieren Sie den Vertrag: „Der Cursor gibt die Elemente zurück, streng vor der Position“. Das ist für Newsfeeds selbstverständlich.

4. 3 Einfügungen/Löschungen zwischen den Seiten

Das Seek-Modell minimiert „Duplikate/Auslassungen“.
Dokumentieren Sie das Lösch-/Änderungsverhalten: Seltene „Löcher“ zwischen den Seiten sind erlaubt, aber nicht „zurück in der Zeit“.

5) Indexierung und ID-Schemata

Die zusammengesetzten Indizes sind streng in der Sortierreihenfolge: „(created_at DESC, id DESC)“.
Monotone IDs: Snowflake/UUIDv7 geben die Reihenfolge der Zeit → beschleunigen die Suche.
Hot Keys: über Shard-Key verteilen (z.B. 'tenant _ id', 'region') und innerhalb des Shards sortieren.
ID-Generatoren: Vermeiden Sie Kollisionen und „Uhren aus der Zukunft“ (Clock Skew) - Zeitsynchronisation, „Regression“ bei NTP-Sprüngen.

6) Cross-Shard-Pagination

6. 1 Schemata

Scatter-Gather: parallele Abfragen in allen Shards, lokale Seek-Kurse, dann k-way merge auf dem Aggregator.
Per-Shard Cursors: Das Token enthält Positionen für jeden Shard.
Bounded Fan-Out: Begrenzen Sie die Anzahl der Shards in einem Schritt (Rate Limiting/Timeout Budget).

6. 2 Token für Multi-Shard

Speichern Sie das Array'{shard _ id, last_pos}'. Erneuern Sie im nächsten Schritt für jeden aktiven Shard und setzen Sie sich erneut durch und geben Sie eine global sortierte Seite zurück.

7) Protokollverträge

7. 1 REST

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

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

• 'limit' mit oberer Begrenzung (z.B. max = 200).
• 'next _ cursor' fehlt, wenn 'has _ more = false'.
• GET-Idempotenz, Cachefähigkeit der Antworten ohne' next _ cursor'(erste Seite bei festen Filtern und Snapshot).

7. 2 GraphQL (Relay-Ansatz)

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“ muss undurchsichtig und signiert sein; Verwenden Sie keine „rohe Base64 (id)“ ohne 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 Threads und WebSockets

Für fortlaufende Bänder: Cursor als „zuletzt gesehener Offset/ts“.

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

8) Caching, Vorladen, CDN

ETag/If-None-Match für die erste Seite mit stabilen Filtern.
Cache-Control mit kurzer TTL (z.B. 5-30s) für öffentliche Listen.
Prefetch: return 'next _ cursor' and tips ('Link: rel =' next''), der Client kann die nächste Seite vorladen.
Variationen: Berücksichtigen Sie' filter/sort/locale/tenant 'als Schlüssel des Cache-Teils.

9) Lastmanagement und Begrenzung

Obere Grenze' limit', z.B. 200.
Server-Side Backpressure: Wenn die Abfragezeit> Budget ist, reduzieren Sie das' Limit 'in der Antwort (und teilen Sie dem Kunden explizit die tatsächliche Seitengröße mit).
Rate limits per user/token/tenant.
Timeout/Retry: exponentielle Pause, idempotente Wiederholungsabfragen.

10) UX-Aspekte

Scrolling vs. Nummerierung: endloses Scrollen → Cursor; nummerierte Seiten → Offset (aber erklären Sie die Ungenauigkeit bei der Aktualisierung der Daten).
Button „back to place“: Speichern Sie den Clientcursor-Stack.
Leere Seiten: Wenn 'has _ more = false', zeigen Sie nicht die Schaltfläche' Mehr'.
Stabile Grenzen: Zeigen Sie das genaue' total 'nur an, wenn es billig ist (ansonsten ist es das ungefähre' approx _ total').

11) Tests und Edge-Fälle

• Stabile Sortierung: Elemente mit dem gleichen 'ts' „blinken“ nicht.
• Einfügungen/Löschungen: Es erscheinen keine Wiederholungen am Seitenrand.
• Ändern der Filter zwischen den Seiten: Das Token muss als „veraltet/inkompatibel“ abgelehnt werden.
• TTL des Tokens: korrekter Fehler nach Ablauf der Frist.
• Große Tiefe: Die Latenz wächst nicht linear.
• Multishard: korrekte Merge-Reihenfolge, keine Starvation von „langsamen“ Shards.

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

12) Beobachtbarkeit und SLO

• 'list _ request _ latency _ ms' (P50/P95/P99) entlang der Seitenlänge.
• 'seek _ index _ hit _ ratio' (Anteil der Anfragen, die auf dem Deckungsindex abgegangen sind).
• 'next _ cursor _ invalid _ rate' (Validierungs-/TTL-/Signaturfehler).
• 'merge _ fanout' (Anzahl der betroffenen Shards pro Seite).
• 'duplicates _ on _ boundary' und 'gaps _ on _ boundary' (Detail auf Client-Telemetrie).

• Korrelieren Sie' cursor _ id 'in den Protokollen, maskieren Sie payload.
• Tags Spans: 'page _ size', 'source _ shards', 'db _ index _ used'.

• Verfügbarkeit: 99. 9% auf 'Liste' Methoden.
• Latenz: P95 <200 ms für 'page _ size <= 50' bei lokalem Charme.
• Tokenfehler: <0. 1% aller Anrufe.

13) Migrationen und Kompatibilität

Aktivieren Sie'v 'im Token und pflegen Sie ältere Versionen von N Wochen.
Wenn Sie die Sortierschlüssel ändern, senden Sie den „weichen“ Fehler „409 Conflict“ mit der Aufforderung, eine neue Auflistung ohne Cursor durchzuführen.
Katastrophenfall (Heulen aller Token): Ändern Sie' signing _ key _ id 'und lehnen Sie die alten ab.

14) Beispiele für Implementierungen

14. 1 Token-Generierung (Pseudocode)

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

14. 2 Validierung des Tokens

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-Abfrage mit Composite-Schlüssel

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) Sicherheit und Compliance

Schließen Sie keine rohen Felder in Token ein, aus denen PII abgeleitet werden kann.
Signieren und begrenzen Sie die TTL.
Versuchen Sie, Token zwischen Benutzern intolerant zu machen (geben Sie' sub/tenant/roles' in payload ein und überprüfen Sie es bei der Validierung).
Loggen Sie nur Token-Hashes.

16) Häufige Fehler und Anti-Muster

Base64 (id) als Cursor: leicht zu fälschen/abholen, bricht den Vertrag beim Wechsel der Sortierung.
Kein Tie-Breaker: 'ORDER BY ts DESC' ohne' id '→ Duplikate/Sprünge.
Filterwechsel zwischen Seiten ohne Behinderung des Tokens.
Deep OFFSET: langsam und unvorhersehbar.
Token ohne Version und TTL.

17) Mini-Implementierungs-Checkliste

1. Definieren Sie die Sortierung und fügen Sie einen eindeutigen Tie-Breaker hinzu.
2. Erstellen Sie einen Deckindex für diese Reihenfolge.
3. Wählen Sie Ihr Modell: seek + opaque token.
4. Implementieren Sie die Signatur (und gegebenenfalls Verschlüsselung) des Tokens.
5. Legen Sie TTL und Versionierung fest.
6. Formulieren und dokumentieren Sie die Verträge' has _ more', 'next _ cursor'.
7. Denken Sie an ein Cross-Shard-Schema (falls erforderlich) und K-Way-Merge.
8. Fügen Sie Metriken, Alerts und SLOs hinzu.
9. Bedecken Sie den Seitenrand mit eigenschaftsbasierten Tests.
10. Beschreiben Sie die Migrationsstrategie der Token.

18) Kurze Empfehlungen zur Auswahl des Ansatzes

Verzeichnisse/Suchen, bei denen die „Seitenzahl“ und die ungefähre Summe wichtig sind: Lassen Sie „OFFSET/LIMIT“ + Cache; Geben Sie an, dass total ungefähr ist.
Feeds, Analysen, tiefe Listen, hohe RPS: nur Cursor/Seek.
Sharded/Distributed Collections: per-shard cursors + merge token.
Threads/CDC: Cursor als Offsets/ts mit Wiederaufnahme.

19) API-Vereinbarungsbeispiel (Zusammenfassung)

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

Die Antwort beinhaltet immer 'page. limit`, `page. has_more', optional 'page. next_cursor`.
Der Cursor ist undurchsichtig, signiert, c TTL.
Die Sortierung ist deterministisch: „ORDER BY created_at DESC, id DESC“.
Verhalten bei Satzänderungen: Elemente werden nicht relativ zum Cursor „zurückgestellt“.
Metriken und Fehler sind standardisiert: 'invalid _ cursor', 'expired _ cursor', 'mismatch _ filters'.

Dieser Artikel liefert architektonische Prinzipien und vorgefertigte Muster, um eine Pagination zu entwerfen, die auch unter Bedingungen von Big Data, Sharding und sich aktiv verändernden Datensätzen schnell, vorhersehbar und sicher bleibt.