Design a cursor-based pagination API

01The design, in the six-step framework

1. Requirements and use cases

Reported from a machine-coding round: an API over a sorted dataset where a client walks pages with a cursor. The test is what happens to page three when somebody inserts into page one.

• A client requests the first page with a page size and receives items plus a next cursor.
• A client requests the next page by passing the cursor back.
• A client walking pages never sees a row twice and never misses a row that existed throughout the walk, even with concurrent inserts and deletes.
• A client can walk backwards with a previous cursor.
• An invalid or tampered cursor gets a clear error, not a silent first page.

Out of scope: total counts, jumping to page 40, and multi-column filter changes mid-walk (a cursor is bound to one query). Non-functional constraints: page fetch O(log n + page size), independent of how deep the client is; the cursor is opaque to clients so its contents can change; and the server keeps no per-client state, so cursors survive restarts.

2. Core entities and relationships

• Row: a record with a sort key and a unique id.
• SortKey: the (sort value, id) pair; the id breaks ties so ordering is total.
• Cursor: a value object holding the last seen SortKey, the direction and a hash of the query it belongs to.
• CursorCodec: encodes a Cursor to an opaque signed string and back.
• Paginator: the API object; validates, seeks into the store and builds a Page.
• SortedStore: rows ordered by SortKey with a seek operation.

The paginator aggregates a store and a codec. It depends on a seek interface, not on a list, so the same class works over a database index. A Cursor is a value object: immutable and compared by contents. The total order on SortKey is a matter of identity and equality: without the id, two rows with the same timestamp have no defined order, and a page boundary between them loses one.

3. Interfaces and key methods

from typing import List, Optional, Tuple

SortKey = Tuple[int, str]


class SortedStore:
    def after(self, key: Optional[SortKey], n: int) -> List[SortKey]:
        """Up to n keys strictly greater than key, ascending; None means from the start."""

    def before(self, key: SortKey, n: int) -> List[SortKey]:
        """Up to n keys strictly smaller than key, ascending."""


class InvalidCursor(Exception):
    """Malformed, tampered, or issued for a different query."""


class Paginator:
    def page(self, size: int, cursor: Optional[str] = None, query: str = ""):
        """Raises ValueError for a bad size, InvalidCursor for a bad cursor. Returns a Page."""

Invariants: SortKey order is total; a cursor names a position between rows, not an index, so it stays meaningful after inserts and deletes; a row present for the entire walk appears exactly once; and an empty or final page has no next cursor, which is how clients know to stop.

4. Design patterns and the choices behind them

Keyset cursors, not offsets

The force is rows moving under a walking client. With offset 20, an insert at the front shifts everything down one, so row 20 is shown again on the next page; a delete makes a row disappear unseen. Offsets are also O(offset) in most stores because the skipped rows must be walked. A keyset cursor says "after this key", which is unaffected by changes elsewhere and turns into a seek in O(log n). The cost is losing "jump to page 40". The rejected option of server-side snapshots per client gives perfect stability but holds state for every abandoned walk.

An opaque, signed token

The force is the freedom to change. If clients can read the cursor, they will build them, and the format freezes forever. Base64 of a small JSON document plus an HMAC keeps it opaque, and a tampered value fails verification. The token is integrity-protected, not secret; say so. This is method design at the level of a wire format, and failing loudly at the boundary applies: a bad cursor raises rather than quietly returning page one, which would loop a client forever.

Fetch one extra to detect the end

The force is knowing whether a next page exists without a count. Asking the store for size + 1 keys answers it in one call, and the extra is dropped. This works as an iterator over a remote collection, with the position held by the client.

5. Core flow and code

Flow for a second page of size 2, with keys (10,a), (10,b), (20,c), (30,d), (40,e):

1. The client sends the cursor from page one, which encodes key (10,b), forward.
2. The codec verifies the signature and the paginator checks the query hash.
3. The store seeks past (10,b) and returns three keys, one more than requested.
4. The paginator keeps two rows, (20,c) and (30,d), and because a third key existed it issues a next cursor at (30,d), plus a previous cursor at (20,c).

import base64
import bisect
import hashlib
import hmac
import json
from dataclasses import dataclass
from typing import Dict, List, Optional, Tuple

SortKey = Tuple[int, str]


@dataclass(frozen=True)
class Row:
    score: int
    id: str
    body: str = ""

    @property
    def key(self) -> SortKey:
        return (self.score, self.id)


class SortedStore:
    def __init__(self) -> None:
        self.keys: List[SortKey] = []
        self.rows: Dict[SortKey, Row] = {}

    def insert(self, row: Row) -> None:
        if row.key not in self.rows:
            bisect.insort(self.keys, row.key)
        self.rows[row.key] = row

    def delete(self, row: Row) -> None:
        if self.rows.pop(row.key, None) is not None:
            del self.keys[bisect.bisect_left(self.keys, row.key)]

    def after(self, key: Optional[SortKey], n: int) -> List[SortKey]:
        lo = 0 if key is None else bisect.bisect_right(self.keys, key)
        return self.keys[lo:lo + n]

    def before(self, key: SortKey, n: int) -> List[SortKey]:
        hi = bisect.bisect_left(self.keys, key)
        return self.keys[max(0, hi - n):hi]


class InvalidCursor(Exception):
    pass


@dataclass(frozen=True)
class Cursor:
    key: SortKey
    forward: bool
    query_hash: str


class CursorCodec:
    def __init__(self, secret: bytes) -> None:
        self.secret = secret

    def _sign(self, payload: bytes) -> str:
        return hmac.new(self.secret, payload, hashlib.sha256).hexdigest()[:16]

    def encode(self, c: Cursor) -> str:
        body = json.dumps([list(c.key), c.forward, c.query_hash]).encode()
        return base64.urlsafe_b64encode(body).decode() + "." + self._sign(body)

    def decode(self, token: str) -> Cursor:
        try:
            encoded, signature = token.split(".")
            body = base64.urlsafe_b64decode(encoded)
            if not hmac.compare_digest(self._sign(body), signature):
                raise InvalidCursor("bad signature")
            key, forward, query_hash = json.loads(body)
            return Cursor((key[0], key[1]), forward, query_hash)
        except (ValueError, TypeError, IndexError) as exc:
            raise InvalidCursor("malformed cursor") from exc


@dataclass(frozen=True)
class Page:
    items: List[Row]
    next_cursor: Optional[str]
    prev_cursor: Optional[str]


class Paginator:
    def __init__(self, store: SortedStore, codec: CursorCodec, max_size: int = 100) -> None:
        self.store, self.codec, self.max_size = store, codec, max_size

    def page(self, size: int, cursor: Optional[str] = None, query: str = "") -> Page:
        if not 1 <= size <= self.max_size:
            raise ValueError("size out of range")
        qh = hashlib.sha256(query.encode()).hexdigest()[:8]
        c = self.codec.decode(cursor) if cursor else None
        if c is not None and c.query_hash != qh:
            raise InvalidCursor("cursor belongs to another query")
        if c is None or c.forward:
            keys = self.store.after(c.key if c else None, size + 1)
            more_after, keys = len(keys) > size, keys[:size]
            more_before = bool(keys) and bool(self.store.before(keys[0], 1))
        else:
            keys = self.store.before(c.key, size + 1)
            more_before, keys = len(keys) > size, keys[-size:]
            more_after = bool(keys) and bool(self.store.after(keys[-1], 1))
        items = [self.store.rows[k] for k in keys]
        nxt = self.codec.encode(Cursor(keys[-1], True, qh)) if keys and more_after else None
        prv = self.codec.encode(Cursor(keys[0], False, qh)) if keys and more_before else None
        return Page(items, nxt, prv)


if __name__ == "__main__":
    store = SortedStore()
    rows = [Row(10, "a"), Row(10, "b"), Row(20, "c"), Row(30, "d")]
    for r in rows:
        store.insert(r)
    api = Paginator(store, CursorCodec(b"k"))
    p1 = api.page(2)
    assert [r.id for r in p1.items] == ["a", "b"] and p1.prev_cursor is None
    store.insert(Row(5, "z"))                     # insert before the cursor: nothing repeats
    store.delete(rows[2])                         # delete after it: nothing breaks
    p2 = api.page(2, p1.next_cursor)
    assert [r.id for r in p2.items] == ["d"] and p2.next_cursor is None
    back = api.page(2, p2.prev_cursor)
    assert [r.id for r in back.items] == ["a", "b"]
    for bad, q in [("junk", ""), (p1.next_cursor[:-1] + "0", ""), (p1.next_cursor, "other")]:
        try:
            api.page(2, bad, q)
            assert False
        except InvalidCursor:
            pass

6. Extensions, concurrency and what interviewers probe

• Ties in the sort value. The id tie-break is mandatory. Show it with two rows at the same score split across a page boundary.
• What stability really means. A row inserted behind the cursor is not seen; a row inserted ahead is. Surviving rows appear once. That is the guarantee; state it rather than promising a snapshot.
• Deleted cursor row. The cursor is a position, so seeking past a deleted key still works. An id-based lookup of the last row would fail here.
• Changing sort order or filters. The query hash rejects a cursor used with different parameters; a client must restart the walk.
• Thread safety. The store needs a read-write lock around after, before and insert; the paginator is stateless and needs none.
• Common mistake. Returning a next cursor on every full page, so clients make one extra empty request, or using a timestamp alone as the key.

02Where this question was reported

• GitHub · API design: cursor semantics over sorted data