Katkat
Back

Evolve Cursor Pagination Without Breaking Clients

CoinbaseBackend Engineer · Onsite
MediumBackend EngineerOnsiteSoftware Engineering Fundamentals

Last updated

This problem tests the ability to design stable, deterministic cursor-based pagination systems that handle non-unique sort keys and schema evolution without breaking backward compatibility.

The Scenario

You are tasked with fixing a cursor-based pagination system for a transaction service. Currently, the API uses a cursor string which is a base64-encoded timestamp (created_at). Clients consume data using GET /transactions?limit=20&cursor=....

The Problem

  1. Ambiguity: Many transactions share the exact same millisecond timestamp, leading to missing or duplicate entries during pagination because the database ORDER BY created_at does not guarantee a stable row order.
  2. Requirement: You must add support for sorting by amount (e.g., GET /transactions?limit=20&sort=amount&cursor=...).
  3. Constraint: Existing clients must continue to function. You cannot force a breaking change on the cursor format if they are already integrated.

Your Task

  1. Define a stable composite sort key that resolves the timestamp collision issue.
  2. Design a versioned opaque cursor format that allows you to embed the sort strategy, ensuring the server can differentiate between old (timestamp-only) and new (timestamp + ID + amount) cursors.
  3. Write the pseudocode or logic for the database query construction that handles both the old and new cursor formats.

Constraints

  • The database contains millions of transactions.
  • You must avoid OFFSET pagination due to performance degradation at high page counts.
  • Assume transaction_id is a unique UUID.

Example

  • Current Cursor: MTcxNTg5MzAwMDAwMA== (Base64 of '1715893000000')
  • Required format: A system that can distinguish between v1 (simple timestamp) and v2 (composite key) cursors.

Questions

  • How do you construct the SQL WHERE clause for the new amount sort to ensure no data is skipped when multiple records have the same amount?
  • How do you handle the transition period where the database still holds legacy data?

Hints

Hint 1

To achieve stability, always include a unique column like `id` as the final part of your composite sort key.

Hint 2

Prefix your cursor string with a version identifier (e.g., 'v1:' or 'v2:') before base64 encoding to allow the server to parse it correctly.

Hint 3

For the SQL query, use the row tuple comparison syntax: (amount, id) < (cursor_amount, cursor_id) to correctly jump to the next page.

Follow-up questions

  • How does your design handle a scenario where a transaction's amount is updated while a user is paginating through the list?
  • What are the trade-offs between using a global sequence number versus a composite timestamp-plus-UUID key for pagination?
  • How would you implement 'prev' pagination (going backward) given that your cursor contains an inequality condition?