Skip to content

DynamoDB Write Sharding Breaks Your Pagination

By

In this article

I wouldn't consider a DynamoDB write-sharding design done until I can paginate its reads. Adding a suffix is easy enough. Returning the next fifty orders, in order, without losing the ones already fetched takes more thought.

Let's walk through a daily-orders design. All new orders go under PK = ORDERS#2026-02-21, with SK = <createdAt>#<orderId>. The date makes a daily listing convenient, but today's checkouts all target the same logical key. Tomorrow's key doesn't help today's traffic. I'll use this illustrative workload to build a listing that can stop and resume across shards.

My earlier DynamoDB quirks article introduces the service's constraints. Here I'll follow one access pattern through routing, merging, and pagination.

Check the concentration before adding suffixes

I'd first check whether throttling comes from one hot key, table capacity, or an index. Sharding won't fix an unrelated table-level limit, and a GSI that groups every order under one date can recreate the bottleneck.

We'd also ask whether the traffic deserves more capacity. In FinBox's production account, unusually aggressive tenants led the team to limit requests. Legitimate checkout volume and one uncontrolled producer call for different responses.

There is a difference between a partition key and a physical partition. DynamoDB owns physical placement and different suffixes can still share a physical partition; an item collection can span partitions when the table has no local secondary indexes. Sixteen suffixes do not reserve sixteen physical partitions. AWS's partition documentation makes that clear.

Nor can we assume automatic splitting makes this design harmless. With an ever-increasing timestamp sort key, new writes continue to arrive at the hot end. AWS explains why split for heat may not help that pattern. I'd spread logical keys deliberately, then measure the resulting traffic.

Choose a route I can reproduce

For this example, I'll expand the daily key into 16 values, ORDERS#2026-02-21#v1#00 through #15. Each order will be tied to one suffix. AWS documents both random and calculated suffixes.

Choice What I gain What I need to preserve
Random suffix Distribution independent of the order ID. Persist the chosen route so lookups and retries reuse it.
Deterministic hash of order ID Recompute the suffix from stable input. Keep the hash, input encoding, and shard count consistent across writers and readers.

For this case, I'd use deterministic routing so retrying the same order targets the same key. Picking a new random suffix on a retry could create another item; a condition on the first key doesn't protect the second. Stable routing still needs an idempotent write policy.

The Node.js routing function looks like this:

import { createHash } from "node:crypto";

function orderPK(day, orderId, count = 16, layout = "v1") {
  const hash = createHash("sha256").update(orderId, "utf8").digest();
  const suffix = String(hash.readUInt32BE(0) % count).padStart(2, "0");
  return `ORDERS#${day}#${layout}#${suffix}`;
}

The layout identifies this routing contract. For ordering, I keep createdAt immutable and normalize timestamps to fixed-width UTC milliseconds, such as 2026-02-21T10:00:00.000Z. Order IDs are unique canonical strings matching [A-Z0-9_-]+. This makes the sort key chronological with a stable tie-breaker.

Knowing the suffix isn't enough for GetItem: it needs the complete primary key. With this sort key, callers also need createdAt. If lookup by order ID alone matters, I'd supply a separate lookup path rather than pretend hashing solves it.

Sixteen ordered streams for one day

Deterministic routing helps with point lookups, but a whole-day listing still queries every suffix. DynamoDB's Query API accepts one partition-key value and sorts by sort key. It doesn't combine multiple queries for us.

I wouldn't pull all day and sort it before returning page one. Alex DeBrie's pagination discussion explains why draining internal pages in a user-facing request is slower as the collection grows. We need to stop merging when the caller has enough rows.

I'm using ascending order. Each shard uses the same upper bound and ScanIndexForward: true. This is still a live-data listing: a common cutoff and strongly consistent reads don't create a snapshot across queries.

Here's the adapter using AWS SDK for JavaScript v3, with an initialized DynamoDBDocumentClient called docClient:

import { QueryCommand } from "@aws-sdk/lib-dynamodb";

async function readShard(state, pk, after) {
  return docClient.send(new QueryCommand({
    TableName: state.table,
    KeyConditionExpression: "PK = :pk AND SK <= :upper",
    ExpressionAttributeValues: { ":pk": pk, ":upper": state.upper },
    ScanIndexForward: true,
    ConsistentRead: true,
    Limit: 20,
    ...(after ? { ExclusiveStartKey: after } : {}),
  }));
}

This queries the base table without a filter. Limit bounds evaluated items per call, and the 1 MB boundary can end a query sooner. Neither setting defines our API's page size. With filters, even an empty result can carry a continuation key. AWS's pagination guide makes the stopping condition explicit: continue until LastEvaluatedKey is absent or empty.

Suppose two shard batches contain sort-key endings [01, 04, 07] and [02, 03, 08]. A three-item API page returns [01, 02, 03]. It must remember [04, 07] and [08] for later. If those are the final batches, resuming returns [04, 07, 08] without another database call.

Saving only those batches' LastEvaluatedKey values skips the unread rows. Saving one key for the entire listing also loses the independent progress of the other shard queries.

Make the merge state visible

Let's give each shard three fields because fetched progress and emitted progress can differ: unread buffer, next query's after key, and exhausted. The buffer starts empty, after is null, and exhausted is false. A null key alone cannot distinguish an untouched shard from a finished one.

That separation has prior art: Chris Villa's combine-pagination retains unread data and also separate positions for each source. Its page contract differs from ours, but the state distinction is useful. Here I'll make it explicit for DynamoDB and a fixed maximum API page size.

Here's the full merge core. It accepts an injected query function so the awkward pagination cases can be tested without AWS:

async function fill(shard, state, read) {
  while (!shard.buffer.length && !shard.exhausted) {
    const result = await read(state, shard.pk, shard.after);
    shard.buffer = result.Items ?? [];
    const key = result.LastEvaluatedKey;
    shard.after = key && Object.keys(key).length ? key : null;
    shard.exhausted = shard.after === null;
  }
}

function compare(a, b) {
  return Buffer.compare(Buffer.from(a.SK), Buffer.from(b.SK)) ||
    Buffer.compare(Buffer.from(a.PK), Buffer.from(b.PK));
}

async function* merge(state, read) {
  for (;;) {
    await Promise.all(state.shards.map(s => fill(s, state, read)));
    let winner;
    for (const shard of state.shards) {
      if (shard.buffer.length && (!winner ||
          compare(shard.buffer[0], winner.buffer[0]) < 0)) {
        winner = shard;
      }
    }
    if (!winner) return;
    yield winner.buffer.shift();
  }
}

async function listPage(saved, size, read = readShard) {
  if (!Number.isInteger(size) || size < 1 || size > 100) {
    throw new Error("Page size must be an integer from 1 to 100");
  }
  const state = structuredClone(saved);
  const items = [];
  for await (const item of merge(state, read)) {
    items.push(item);
    if (items.length === size) break;
  }
  const more = state.shards.some(s => s.buffer.length || !s.exhausted);
  return { items, next: more ? state : null };
}

The iterator first fetches either a head item or confirmed exhaustion from each shard before emitting anything (otherwise there could be an earlier order in a slow shard). The comparator uses DynamoDB's UTF-8 string ordering, with PK breaking ties.

Marking a shard exhausted doesn't discard its final batch. No more queries are needed, but buffered items still get emitted. The refill loop also handles empty batches that have a continuation key.

For sixteen shards, I'd use this linear head selection before adding a heap. It costs O(page size × shard count) comparisons; a heap reduces selection to O(log shard count) per item. I'd make that change when profiling shows head selection matters to listing latency. Neither removes the network fan-out.

The cursor has to remember the whole listing

So here's a starting point for this example:

const saved = {
  v: 1,
  table: "Orders",
  day: "2026-02-21",
  layout: "v1",
  upper: "2026-02-21T18:00:00.000Z#~",
  direction: "asc",
  shards: Array.from({ length: 16 }, (_, n) => ({
    pk: `ORDERS#2026-02-21#v1#${String(n).padStart(2, "0")}`,
    after: null,
    buffer: [],
    exhausted: false,
  })),
};
const first = await listPage(saved, 50);
// Store first.next; resume with listPage(first.next, 50).

The ~ sorts after every character in the permitted order-ID alphabet, including all IDs at the cutoff millisecond. That's why I define the encoding contract alongside the cutoff: a timestamp alone isn't the complete sort key.

I'd store next server-side and return an opaque, unpredictable cursor ID. This follows Yan Cui's pagination argument: preserve the original query intent behind the cursor. The stored record binds the authenticated scope, query identity, layout, direction, upper bound, expiry, and each shard's progress and unread rows. On resume, the API validates those bindings and authorizes the request again. It accepts an approved query plan, not a client-selected table or shard list.

The saved cursor is tied to this sixteen-shard v1 layout. Changing the shard count calls for a new listing, not a silent change to an existing cursor.

An authenticated encrypted payload is another option. A signature prevents tampering but doesn't hide buffered order data; base64 hides nothing. I'd prefer server storage here because buffer size grows with shard count and query batch size.

In this toy example, sixteen full twenty-item batches can hold 320 items before emission. That's a state-size bound, not a capacity estimate. Item count alone doesn't bound storage tightly enough, so I'd enforce byte limits too.

Conclusion

This is the application work I care about in single-table design discussions. Moving work out of the database gives us ownership of that work.

I'd adopt sharding when measured key concentration justifies the additional reader state. Then I'd choose the smallest count that handles observed skew with headroom, and measure listing latency, query consumption, and cursor bytes alongside write throttling. If daily browsing dominates the workload, I'd reconsider the read model before multiplying suffixes again.