Pagination Across Microservices: Sorted Merges with Safe Cursors

Why offset pagination breaks when composing results across services

An aggregator or backend-for-frontend (BFF) endpoint often has to return one sorted list built from several services, such as orders, refunds and disputes shown as a single activity feed. This is pagination across microservices. Each service owns its own data and sort order, and the aggregator has to merge their results into one consistent sequence. The aggregator is the only component that sees the combined list, so it is also where offset pagination fails.

The cost grows with page depth

To serve page N with page size limit, the aggregator cannot ask each service for "its" page N. Any single service might own every row on that page. It has to fetch the first N × limit rows from every source, merge them, and throw away everything before the requested offset.

Illustrative estimate: with 3 services, limit = 20 and page 50, the aggregator pulls up to 3,000 rows to return 20.

Offsets shift under concurrent writes

An offset counts positions, not items. Suppose a row is inserted ahead of the reader's position in any service between two requests. Every item after it moves down one slot, and the next page repeats an item the reader has already seen. A deletion moves items up instead, so one is silently skipped. Each additional service is another independent source of these shifts.

A cursor records the last sort key the client has seen, and each service resumes from that key. The work per request stays roughly constant, and inserts or deletes elsewhere in the list do not shift the reader's position.

Defining a deterministic total order every service shares

That only holds if every service agrees on what "after" means. The aggregator interleaves rows from several sources, so each source must sort by the same key and break ties the same way. Otherwise a merged page can skip or duplicate rows at the boundaries.

The sort key and the tiebreaker

A timestamp alone is not a total order. Two rows can share created_at, and the cursor would then be ambiguous. Add a globally unique tiebreaker. A common choice is the row's ID prefixed with a source identifier, such as orders:8812 or refunds:8812. The prefix guarantees uniqueness across services that allocate IDs independently, and it makes the tiebreak deterministic even when two services emit the same timestamp.

Everything else that must match

• Timezone and precision: store and compare in UTC at the same precision. If one service truncates to milliseconds and another keeps microseconds, equal values can compare as unequal.
• Collation: if any key component is a string, every service must use the same byte-wise or locale collation.
• Null ordering: either forbid nulls in sort columns or fix NULLS LAST everywhere.
• Indexes: each service needs a composite index on (ts, id) in the sort direction, or the keyset query degrades to a scan.

The keyset predicate for "after (ts, id)" is ts > :ts OR (ts = :ts AND id > :id). Where the database supports it, the row-value form (ts, id) > (:ts, :id) is equivalent.

Treat this as a published contract. Changing the key, the precision, or the ID format later invalidates every outstanding cursor and requires a coordinated migration across all services.

Copy-- PostgreSQL. Every service creates its feed table with the same shape.
CREATE TABLE order_events (
  -- UTC instant at fixed microsecond precision in every service.
  ts  timestamptz(6) NOT NULL,
  -- Source-prefixed ID, e.g. 'orders:8812'. Unique across services.
  -- COLLATE "C" gives byte-wise ordering, independent of server locale.
  -- Comparison is lexical ('orders:900' > 'orders:8812'), which is fine:
  -- the tiebreak only needs to be deterministic and identical everywhere.
  id  text COLLATE "C" NOT NULL,   -- NOT NULL: no null-ordering rules needed
  payload jsonb NOT NULL,
  PRIMARY KEY (id)
);

-- Composite index matching the sort direction, so the keyset
-- query is an index range scan rather than a sort over the table.
CREATE INDEX order_events_ts_id ON order_events (ts, id);

-- Next page "after (:ts, :id)" taken from the cursor.
-- Expanded form, portable to databases without row-value comparison:
SELECT ts, id, payload
FROM order_events
WHERE ts > :ts
   OR (ts = :ts AND id > :id)
ORDER BY ts, id
LIMIT :page_size;

-- Equivalent row-value form; PostgreSQL can use the (ts, id) index for it.
SELECT ts, id, payload
FROM order_events
WHERE (ts, id) > (:ts, :id)
ORDER BY ts, id
LIMIT :page_size;

A PostgreSQL table and index that fix precision, collation and null handling for the shared (ts, id) order, followed by the keyset query for "after (ts, id)" in both expanded and row-value forms.

How scatter gather with a k-way merge works

The aggregator holds one position per source: the sort key of the last item it emitted from that source. On each request it fans out in parallel, asking every source for limit + 1 items strictly after that source's position, using the same keyset predicate defined above.

Each source needs that many items because the worst case is that every result on the page comes from a single source. Asking each source for only limit / k items would quietly drop rows whenever the data is skewed. The extra item is what lets the aggregator know whether a source is finished:

• If a source returns limit or fewer items, it is exhausted for this query.
• If it returns limit + 1, it still has more, even if none of its items make the page.

The merge loop

The merge itself is a standard k-way merge over already-sorted streams:

1. Build a min-heap keyed on the shared total order. Seed it with the first item from each non-empty response, and tag each entry with its source.
2. Pop the smallest entry and append it to the page.
3. Set that source's position to the popped item's key.
4. Push that source's next buffered item, if it has one.
5. Repeat until the page holds limit items or the heap is empty.

The heap never holds more than k entries, one head per source. Each emit therefore costs O(log k), and the whole page costs O(limit · log k) regardless of how large the responses were. Ties across sources cannot cause ambiguity, because the order already includes a unique ID component.

Positions advance only for items that were actually emitted. Items that were fetched but not used are discarded, and the next request asks for them again. This wastes some bandwidth, but it means the cursor depends only on what the client saw, not on what happened to be buffered. The next section turns this per-source position map into a cursor the client can carry.

Copyimport asyncio
import heapq

async def fetch_merged_page(sources, positions, limit):
    """sources: {name: client}; positions: {name: last emitted key or None}."""
    # Fan out in parallel. Each source may supply the whole page, so ask for limit + 1.
    names = list(sources)
    responses = await asyncio.gather(
        *(sources[n].fetch_after(positions.get(n), limit + 1) for n in names)
    )
    buffers = dict(zip(names, responses))

    # Seed the heap with one head per source. item.key is (sort_value, unique_id),
    # a total order. The source name breaks any remaining tie so items are never compared.
    heap = [(items[0].key, n, 0) for n, items in buffers.items() if items]
    heapq.heapify(heap)

    page = []
    new_positions = dict(positions)
    while heap and len(page) < limit:
        key, name, idx = heapq.heappop(heap)        # O(log k)
        page.append(buffers[name][idx])
        new_positions[name] = key                   # advance only on emit
        nxt = idx + 1
        if nxt < len(buffers[name]):
            heapq.heappush(heap, (buffers[name][nxt].key, name, nxt))

    # A non-empty heap means fetched rows were left unused; a full limit + 1
    # response means that source has more rows downstream.
    has_more = bool(heap) or any(len(r) > limit for r in responses)

    # Unused buffered rows are dropped and re-fetched next time from new_positions.
    return page, new_positions, has_more

A k-way merge sketch using Python's heapq: it fetches limit + 1 rows per source in parallel, keeps at most one heap entry per source, and advances each source's cursor position only for rows it actually emitted.

Designing the composite cursor

The cursor carries three fields: a version number, the last emitted sort key as a full tuple including the tiebreaker, and, when required, a map from source ID to the last key consumed from that source. Serialize these fields, compute an HMAC over the bytes with a server-held secret, append the signature, and base64url-encode the result. The aggregator verifies the signature before it reads any field, so a client cannot edit a position to skip data or probe another tenant's range. Encoding the cursor also tells clients not to depend on its internal layout.

A single key is enough when every source can answer "rows strictly after K." If filters differ per source, or a source's key is not monotonic, that question cannot be answered the same way everywhere. In those cases each source needs its own position.

Bump the version whenever the sort definition or field layout changes. During a rollout, decode the previous version too. If you cannot translate an old cursor safely, return a clear "restart pagination" error. Do not guess.

With dozens of sources, the per-source map can exceed URL length limits. Cap the number of sources or move cursors into POST bodies.

Backward pagination roughly doubles the work. You reverse every comparison, query each source with the opposite sort direction, and reverse the merged page before returning it. The cursor must also record the direction, because "previous page" is not the inverse of "next page" once rows have been inserted between requests.

Copyimport base64, hashlib, hmac, json

SECRET = b"placeholder-cursor-secret"  # load from a secret store; never ship to clients
CURRENT_VERSION = 2  # bump when sort definition or field layout changes
SIG_LEN = 32  # SHA-256 digest size

class RestartPagination(Exception):
    """Cursor cannot be honored safely; client must restart from page one."""

def encode_cursor(last_key, direction="next", positions=None):
    # last_key is the full sort tuple including the tiebreaker, e.g. (created_at, id)
    body = {"v": CURRENT_VERSION, "k": list(last_key), "d": direction}
    if positions:  # only when sources cannot all answer "rows strictly after K"
        body["p"] = {src: list(key) for src, key in positions.items()}
    payload = json.dumps(body, separators=(",", ":"), sort_keys=True).encode()
    sig = hmac.new(SECRET, payload, hashlib.sha256).digest()
    return base64.urlsafe_b64encode(payload + sig).rstrip(b"=").decode()

def decode_cursor(token):
    try:
        raw = base64.urlsafe_b64decode(token + "=" * (-len(token) % 4))
    except ValueError:
        raise RestartPagination("malformed cursor")
    payload, sig = raw[:-SIG_LEN], raw[-SIG_LEN:]
    expected = hmac.new(SECRET, payload, hashlib.sha256).digest()
    # Verify before reading any field so edited positions are rejected
    if len(raw) <= SIG_LEN or not hmac.compare_digest(sig, expected):
        raise RestartPagination("invalid cursor signature")
    body = json.loads(payload)
    if body.get("v") == 1:
        body["d"] = "next"  # v1 only supported forward paging: safe to translate
        body["v"] = CURRENT_VERSION
    elif body.get("v") != CURRENT_VERSION:
        raise RestartPagination("unsupported cursor version")  # do not guess
    return body

token = encode_cursor(("2026-10-29T12:00:00Z", "order-8812"),
                      positions={"orders-eu": ("2026-10-29T11:58:02Z", "order-8790")})
print(decode_cursor(token))

A versioned, HMAC-signed, base64url-encoded composite cursor that stores the last emitted key with its tiebreaker, the paging direction and optional per-source positions, and that translates or rejects old versions.

Partial failures, slow sources, and consistency semantics

Each source call needs its own timeout, set from the aggregator's overall latency budget. When a source misses it, you have two honest choices: fail the whole page or return a partial page that is explicitly flagged as partial. The dangerous option is a page that is partial without saying so.

A silent partial page corrupts the cursor. The merge emits rows up to some boundary key and writes that position into the cursor. If source B was missing, B's rows that sort before the boundary were never considered. The next page starts after the boundary, so those rows are skipped permanently. If the response names the missing sources and the cursor keeps B's old position, the client can at least see that ordering across that boundary is not guaranteed.

Even when every source responds, cursor pagination over live data is not a snapshot. It guarantees no duplicates and no skips only for items that existed for the whole traversal and whose sort-key fields did not change. When an update moves an item from ahead of the cursor to behind it, the client never sees that item. When an update moves an item from behind the cursor to ahead of it, the client sees it twice. New rows inserted behind the cursor are never seen.

This model has two other limits. Clients cannot jump to page N without walking every page before it. Exact totals would require counting every source at one consistent instant, so return a "has more" flag or a clearly labelled estimate instead.

When to avoid live scatter gather and what to use instead

Live scatter gather fits a narrow profile: a handful of sources, users who rarely go past the first few pages, and a requirement that results reflect each service's current state. Within that profile, composing at request time avoids extra infrastructure and never serves stale data.

It stops fitting when any of these hold:

• Deep pagination. Each page asks every source for a full page size of rows, and the merge then throws most of them away.
• Selective filters. A filter that matches little in one source forces repeated fetches before that source can fill its share of a page.
• Many sources. Every page is as slow as the slowest service, and the chance that some source is degraded grows with each one you add.

Alternatives

A read model moves the merge from read time to write time. Paging becomes a single indexed range scan, so depth no longer multiplies cost. In exchange you own a pipeline. A backfill or reindex must replay history without double-applying events, and it needs a way to swap from the old index to the new one with no visible gap.

Impact on cost and engineering time, and how to test the aggregator

Cost and engineering time

Illustrative estimate (assumed numbers, not a benchmark). Assume 5 sources and a page size of 50. Each source returns page_size + 1 rows so the aggregator can detect whether more rows exist. Rows fetched per page = sources × (page_size + 1) = 5 × 51 = 255. Only 50 are returned, so 205 rows (about 80%) are read, serialized, and sent over the network for nothing. Waste grows linearly with the number of sources.

There are two ways to reduce it. Per-source buffering asks each source for fewer rows, for example ceil(page_size / sources) + 1, and fetches more only from a source whose buffer runs dry. This trades fewer rows for extra round trips. The other way is to keep the unconsumed tail, either encoded in the cursor when it is small or in a short-lived store keyed by cursor ID, so the next page can start from rows already fetched. A tail stored this way goes stale, so give it a TTL and treat it only as a hint.

The larger cost is people. Every source team has to agree on the sort key, the tie-breaker, and the cursor semantics. A shared aggregator library that owns the merge and the cursor codec turns that agreement into code that is written once.

Testing

Generate random sources, page through them to the end, concatenate the pages, and assert that the result equals a reference merge, meaning a full sort of all rows. Test these cases specifically:

• heavy ties on the sort key
• empty sources
• rows inserted between page requests (no duplicates, and no skipped rows that sort after the cursor)
• backward pagination producing the reverse of forward pagination

A property-based framework can shrink a failing case down to a minimal set of sources, which is far easier to debug than a failure seen in production.

Copyfrom hypothesis import given, settings, strategies as st
from aggregator import fetch_page  # assumed: fetch_page(sources, page_size, cursor, direction) -> (rows, next_cursor or None)

keys = st.integers(min_value=0, max_value=5)  # tiny key range forces heavy ties

@st.composite
def sources_strategy(draw):
    n = draw(st.integers(min_value=1, max_value=5))
    srcs = []
    for s in range(n):
        ks = draw(st.lists(keys, max_size=30))  # empty sources are allowed
        # Row = (sort_key, source_id, row_id): source_id and row_id form the unique tie-breaker
        srcs.append(sorted((k, s, i) for i, k in enumerate(ks)))
    return srcs

def drain(sources, page_size, direction="forward"):
    out, cursor = [], None
    total = sum(len(s) for s in sources)
    for _ in range(total + 2):  # bound the loop so a cursor bug fails instead of hanging
        rows, cursor = fetch_page(sources, page_size, cursor, direction)
        out.extend(rows)
        if cursor is None:
            return out
    raise AssertionError("pagination did not terminate")

@settings(max_examples=500)
@given(sources_strategy(), st.integers(min_value=1, max_value=10))
def test_pages_concatenate_to_reference_merge(sources, page_size):
    reference = sorted(row for src in sources for row in src)  # full sort = reference merge
    assert drain(sources, page_size) == reference

@settings(max_examples=500)
@given(sources_strategy(), st.integers(min_value=1, max_value=10))
def test_backward_is_reverse_of_forward(sources, page_size):
    # Backward pagination from a None cursor starts at the end of the merged order
    forward = drain(sources, page_size, "forward")
    assert drain(sources, page_size, "backward") == forward[::-1]

A Hypothesis property-test sketch that pages through randomly generated sources, including tie-heavy and empty ones, and checks that the concatenated pages match a full-sort reference merge and that backward pagination returns the exact reverse of forward pagination.

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.
• Reviewers see the exact diff and the list of affected services up front, so approval is a decision rather than an investigation.

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.
• Per-service approve/reject means a bad shared value can be refused where it would break something, before it is live.
• 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.