Pagination Across Microservices: Composite Cursors and Merges

Why does offset/limit pagination break across microservices?

Paginating a single table with OFFSET and LIMIT is a database feature. Paginating a sorted list that spans several services is a distributed merge. The aggregator cannot ask each service for "its share" of page 50, because nobody knows in advance how the top rows are distributed across sources. Any one service might own every row on that page. To build a correct global page, each of N sources must return its first offset + limit rows. The aggregator merges them, discards the first offset, and keeps limit.

Illustrative estimate (assumed inputs, not measured)

Assume 4 sources, a page size of 20, and per-source latency of 30 ms at p50 and 200 ms at p99, with calls made in parallel.

Work grows linearly with page depth and with source count. Latency is set by the slowest of the four calls. If each call independently has a 1% chance of landing at p99, about 1 − 0.99⁴ ≈ 3.9% of page requests pay the 200 ms tail.

Offsets also drift. An offset describes a position, not a row. If any source inserts a row ahead of the current position between requests, the last item of page n shows up again on page n+1. A delete has the opposite effect and silently skips an item. With N independent writers, these shifts happen more often than they would against a single table.

What is cursor pagination and how does a keyset work?

Cursor pagination replaces "skip k rows" with "resume after this exact position." The position is a keyset: the values of the sort columns for the last row the client received. Those values travel in an opaque cursor token, and the next request turns them back into a predicate.

A sort key must be unique to be stable

Sorting on created_at alone is not enough. Two rows created in the same millisecond have no defined order, so the database can return them in either order on successive queries, and a page boundary that falls between them will drop or repeat one. The fix is to add a tiebreaker that is unique, usually the primary key, so the sort is (created_at, id). The order is then total and deterministic.

The next page is selected with a strict tuple comparison: rows where (created_at, id) is greater than the cursor tuple, in the same order, limited to the page size. Written out, that is created_at > c OR (created_at = c AND id > i). With a composite index on the same columns in the same direction, each page is an index seek rather than a scan past discarded rows.

What it fixes and what it costs

Inserts and deletes before the cursor no longer shift the window. The predicate anchors on a value, not a count, so earlier pages cannot leak into later ones.

The trade-offs are real:

• No random access. You cannot jump to page 40 without walking pages 1 through 39.
• No cheap exact totals. A count still requires a separate query, which is often expensive.
• No snapshot. If an update changes a row's sort key, the row can move across the cursor. It may then appear twice or not at all.

Copy-- Composite index matching the sort order: (created_at, id), both ascending.
CREATE INDEX orders_created_at_id_idx ON orders (created_at, id);

-- First page: no cursor yet, just the total order plus a limit.
SELECT id, created_at, customer_id, total_cents
FROM orders
ORDER BY created_at, id
LIMIT 50;

-- Next page: resume strictly after the last row the client received.
-- :c and :i are decoded from the opaque cursor token
-- (e.g. c = '2024-05-01 12:00:00.123+00', i = 98231).
SELECT id, created_at, customer_id, total_cents
FROM orders
WHERE created_at > :c
   OR (created_at = :c AND id > :i)   -- id breaks ties on equal timestamps
ORDER BY created_at, id                -- must match the predicate and the index
LIMIT 50;

-- Equivalent row-value form where supported (e.g. PostgreSQL):
-- WHERE (created_at, id) > (:c, :i)

-- Contrast: OFFSET counts rows, so an insert before the window
-- shifts every later page and the client sees duplicates or skips.
-- SELECT ... ORDER BY created_at, id LIMIT 50 OFFSET 2000;

Keyset pagination on (created_at, id) with a composite index and a strict 'after this tuple' predicate, contrasted with OFFSET.

How does a k-way merge paginate aggregated queries?

In API composition, the aggregator calls each source with that source's own cursor and asks for up to page_size items. One source might supply the entire next page, so fetching fewer is unsafe. Fetching more is wasteful. The aggregator merges the k sorted streams with a heap keyed on the global sort key, emits page_size items, and discards the rest.

The cursor must record, for each source, the last item consumed, not the last item fetched. If source B returned 50 rows but only 12 made the page, B's cursor points at row 12. Otherwise rows 13–50 are silently skipped on the next request. The discarded rows are fetched again later, which is the price of correctness.

A merge only works when every source produces a comparable key:

• Normalize values. Convert timestamps to UTC at the same precision. A service that truncates to milliseconds will interleave incorrectly with one that stores microseconds. Coerce numeric and string types the same way everywhere.
• Break ties globally. Local IDs collide across services. Append source name plus local id so the ordering is total and stable.
• Reject unindexed orders. If one source cannot serve a sort order from an index, it must scan deep for every page. Refuse that sort order at the API rather than degrade silently.

Filters applied after the merge, such as permission checks or cross-service joins, can drop items and leave a page short or empty. The aggregator then has to loop: advance consumed cursors and fetch again until the page fills or every source is exhausted. Cap the iterations, and return a partial page with a valid cursor rather than spin indefinitely.

Copyimport heapq

MAX_ROUNDS = 5  # cap refetch loop; return a partial page instead of spinning

def sort_key(item):
    # Shared key: UTC microseconds, then source name + local id for a total order.
    return (item["ts_us"], item["source"], item["id"])

def next_page(sources, cursor, page_size, allowed):
    """sources: {name: fetch(after_key, limit) -> rows sorted by sort_key}.
    cursor: {name: sort_key of last row CONSUMED from that source, or None}."""
    cursor, page = dict(cursor), []
    for _ in range(MAX_ROUNDS):
        need = page_size - len(page)
        # Any single source may supply the whole remainder, so ask each for `need`.
        batches = {n: f(cursor.get(n), need) for n, f in sources.items()}
        exhausted = all(len(rows) < need for rows in batches.values())
        heads = [(sort_key(r[0]), n, 0) for n, r in batches.items() if r]
        heapq.heapify(heads)
        taken = 0
        while heads and taken < need:
            key, name, i = heapq.heappop(heads)
            item = batches[name][i]
            cursor[name] = key  # advance to last consumed, never last fetched
            taken += 1
            if allowed(item):   # post-merge filter (e.g. permissions) may drop rows
                page.append(item)
            if i + 1 < len(batches[name]):
                nxt = batches[name][i + 1]
                heapq.heappush(heads, (sort_key(nxt), name, i + 1))
        # Unconsumed rows left in `heads` are discarded and refetched next time.
        if len(page) >= page_size or (exhausted and not heads):
            break
    return page, cursor  # may be short, but the cursor is always valid

A heap-based k-way merge that asks each source for the rows still needed, advances each source's cursor only past rows actually consumed, breaks ties with source name plus local id, and refetches a bounded number of times when a post-merge filter leaves the page short.

How do you design and implement a composite cursor?

A composite cursor has to carry everything the aggregator needs to resume the merge, so that no other client input is trusted. It holds four things:

• Per-source positions. Store the last keyset tuple consumed from each service and an exhausted flag, so a source that has run dry is not queried again.
• Sort definition. Record the fields, the directions and the tie-breaker. A position recorded under one ordering means nothing under another, so reject a cursor whose sort does not match the request instead of trying to reinterpret it.
• Filter parameters, or a hash of them. Without this, a client could replay a cursor against different filters and get a page from a different result set.
• Format version. This lets you change the layout later and still decode older tokens on purpose rather than by accident.

Serialize the cursor to JSON or a compact binary encoding. Compute an HMAC over the bytes with a key held only on the server, then base64url-encode the payload and the tag together. Verify the tag before you parse anything. A signature stops tampering but not reading, so encrypt the payload as well if the positions expose internal IDs.

The contract is simple: the token is opaque, clients echo it back unchanged, and its structure can change without notice.

Token size grows with every source and filter. When tokens get close to URL or proxy header limits, store the cursor state server-side and give the client a short random ID instead. That adds a store, a TTL and an explicit "cursor expired" error that clients must handle.

Opaque tokens are hard to debug. Log the decoded contents next to request IDs, and give operators an internal tool that verifies the signature and decodes a token.

Copyimport base64, hashlib, hmac, json

SECRET = b"placeholder-load-from-secret-store"  # server-only key, never shipped to clients
TAG_LEN = 32  # HMAC-SHA256 tag size in bytes

def _canon(obj) -> bytes:
    # Stable encoding so the same cursor always produces the same bytes
    return json.dumps(obj, sort_keys=True, separators=(",", ":")).encode()

def filter_hash(filters: dict) -> str:
    # Bind the cursor to the result set without embedding every filter value
    return hashlib.sha256(_canon(filters)).hexdigest()[:16]

def encode_cursor(positions: dict, sort: list, filters: dict) -> str:
    body = {"v": 1, "sort": sort, "fh": filter_hash(filters), "pos": positions}
    payload = _canon(body)
    tag = hmac.new(SECRET, payload, hashlib.sha256).digest()
    return base64.urlsafe_b64encode(tag + payload).rstrip(b"=").decode()

def decode_cursor(token: str, sort: list, filters: dict) -> dict:
    raw = base64.urlsafe_b64decode(token + "=" * (-len(token) % 4))
    tag, payload = raw[:TAG_LEN], raw[TAG_LEN:]
    expected = hmac.new(SECRET, payload, hashlib.sha256).digest()
    if not hmac.compare_digest(tag, expected):  # verify before parsing anything
        raise ValueError("invalid cursor")
    body = json.loads(payload)
    if body.get("v") != 1:
        raise ValueError("unsupported cursor version")
    if body["sort"] != sort or body["fh"] != filter_hash(filters):
        raise ValueError("cursor does not match this request")  # reject, don't reinterpret
    return body["pos"]

sort = [["created_at", "desc"], ["id", "desc"]]  # tie-breaker on id
filters = {"status": "open", "region": "eu"}
positions = {
    "orders":   {"after": ["2026-10-30T12:00:00Z", "ord_8812"], "done": False},
    "invoices": {"after": None, "done": True},  # exhausted: skip on next page
}
token = encode_cursor(positions, sort, filters)
print(len(token), decode_cursor(token, sort, filters))

A versioned composite cursor holding per-source keyset positions, the sort definition and a filter hash, serialized to canonical JSON, HMAC-signed and base64url-encoded, with the signature checked before the payload is parsed.

How should pagination handle slow or failed services?

A merged page cannot be emitted until every source has answered or been given up on, so page latency is set by the slowest source, not the average. One service with a long tail drags every aggregated request into that tail. Give each source its own timeout, sized to its normal latency, and keep their sum within the page's overall deadline. Without per-source limits, the client's timeout fires first and every source's work is lost.

When a source misses its deadline, you have two options:

If you return partial results, do not advance the failed source's position in the composite cursor. Write back the exact position the request started with, so the next page asks that source for the same range and its items rejoin the merge. Also cap the merge boundary: the healthy sources must not page past items the missing source would have sorted between. Otherwise those items appear later, out of order, or are skipped.

The partial flag only protects users if clients act on it. A client that ignores the flag shows a list that looks complete but silently drops a source's data. Make the flag a required field in the response contract and have UIs display it. Track partial-page rates per source so the degradation is visible to operators.

Copytype Item = { source: string; sortKey: number }; // sortKey assumed unique; ascending order
type Cursor = Record<string, number>;           // per-source position: last sortKey already emitted
type Source = {
  name: string;
  timeoutMs: number; // sized to this source's normal latency, within the page deadline
  fetch: (after: number, limit: number, signal: AbortSignal) => Promise<Item[]>;
};

export async function fetchPage(sources: Source[], cursor: Cursor, limit: number) {
  // Each source gets its own deadline so one slow service cannot consume the whole budget.
  const results = await Promise.allSettled(
    sources.map((s) => s.fetch(cursor[s.name], limit, AbortSignal.timeout(s.timeoutMs)))
  );

  const missing: string[] = [];
  const pool: Item[] = [];
  results.forEach((r, i) => {
    if (r.status === "fulfilled") pool.push(...r.value);
    else missing.push(sources[i].name); // timed out or errored
  });

  // Cap the merge: a missing source's next item sorts somewhere after its cursor position,
  // so healthy items beyond that point could be emitted out of order or skip its data.
  const cap = Math.min(...missing.map((name) => cursor[name]), Infinity);
  const items = pool
    .filter((it) => it.sortKey <= cap)
    .sort((a, b) => a.sortKey - b.sortKey)
    .slice(0, limit);

  // Advance only by what was actually emitted. Missing sources keep their exact
  // starting position, so the next request asks them for the same range again.
  const next: Cursor = { ...cursor };
  for (const it of items) next[it.source] = it.sortKey;

  // `partial` is always present in the contract so clients cannot treat absence as "complete".
  return { items, nextCursor: next, partial: { isPartial: missing.length > 0, missingSources: missing } };
}

A TypeScript merge that applies per-source timeouts with AbortSignal.timeout, returns a required partial flag naming missing sources, leaves their cursor positions unchanged, and caps healthy results at the missing sources' positions so their items rejoin in order on the next page.

Cursor lifecycle: expiry, versioning and data migrations

A composite cursor is a contract between your aggregator and every source behind it, and that contract decays. Treat each cursor as a short-lived artifact with explicit failure modes.

Expiry. Embed an issued-at timestamp and reject cursors past a fixed window, typically minutes to hours. Without expiry, a client can resume a scroll days later against data whose ordering has shifted. It will receive pages that skip or duplicate rows with no indication anything is wrong.

Versioning. Put a format version as the first field. When you add a source, change a tiebreaker column, or alter the encoding, bump the version. The decoder should accept known versions and reject unknown ones. It should never guess at an unfamiliar layout.

Request binding. Store a hash of the filters and sort order in the cursor. If a client sends the cursor with a different filter or sort, reject it. A keyset position from one ordering is meaningless in another, and silently applying it produces a plausible but wrong page.

Key rotation. Sign cursors and include a key identifier. During rotation, verify against both the current and previous key, and sign only with the new one. Retire the old key once the expiry window has passed, so no valid cursor depends on it.

Source migrations. If a source re-keys its primary IDs or changes its sort column, every outstanding position for that source is invalid. Record a per-source schema epoch in the cursor and reject cursors that carry a mismatched epoch.

In every case, return a distinct, machine-readable error such as cursor_invalid with a reason. Clients should treat it as "restart from the first page," not as a generic failure to retry.

When should you avoid read-time composition, and what are the alternatives?

Read-time composition is the right default only when the list is small, every page must be fresh, and few clients sort it in few ways. Load multiplication is the main reason to move away from it. Every page fans out to every source, and each source over-fetches to fill the merge.

Illustrative estimate (assumed numbers, not a benchmark): rows read per page = N × (P + 1). Assume N = 4 services and page size P = 50. That gives 4 × 51 = 204 rows read to return 50 rows, and the cost repeats on every page request.

Choose the read model when lists are large, many clients query them, or sorts span fields owned by different services. In return, you take on a pipeline you have to run and a reindex every time the sort changes.

You can cut engineering time in any of these options by dropping features nobody needs. Exact totals require counting across every source, so an approximate count or a "more results" flag saves that work. Rejecting unsupported sort orders keeps you from building indexes nobody asked for.

Write down the consistency promise, for example "lists may lag writes by up to a stated delay." Without that statement, every stale row turns into a fresh bug investigation.

How OneEnv can help

Disclosure: OneEnv is the product behind this blog.

OneEnv (oneenv.io) is a workspace-based governance platform for the things services share — environment variables, database structure, API routes and validation rules. A change to a shared value is staged on a branch, reviewed once, and then every affected service explicitly approves or rejects it before it goes live, so you can see who a change touches before it ships instead of finding out in production.

Applied to pagination across microservices, this is where it helps:

Saves time

• Every service that inherits a shared value is listed in one place, so nobody searches repos and chats to find out who is affected.
• One review per branch replaces coordinating each team separately; each service still keeps its own approve/reject.
• Changing a shared variable is one edit and one review instead of editing every service's .env by hand.

Saves cost

• Fewer production incidents and rollbacks caused by a shared value, route or column changing under a consumer unannounced.
• Less duplicated configuration to maintain: one shared definition inherited by many services.
• A wrong or stale value is caught at review time by the services it affects, not by a failed deploy.
• OneEnv has a free plan (1 workspace, unlimited services and members, full governance), so trying it costs nothing.

These are qualitative benefits, not measured results — how much you save depends on how many services share the value.

Want to try it? Start at oneenv.io.