Katkat
Back

Design query pagination for large datasets

CoinbaseSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSystem Design

Last updated

This question tests the ability to design a scalable, consistent pagination system for high-throughput transactional data, focusing on the trade-offs between offset-based and cursor-based approaches.

Scenario

You are designing a public API endpoint for Coinbase that allows users to fetch their transaction history. The transaction table is massive (billions of rows) and is updated continuously.

Requirements

  1. The API must support fetching data in pages of variable sizes (default 50, max 100).
  2. The system must handle high write concurrency without missing or duplicating records as users navigate between pages.
  3. The latency for each page request must be consistent, regardless of how deep into the history the user is scrolling.

Task

  • Design the API request/response schema for fetching transactions.
  • Propose an underlying data storage and indexing strategy.
  • Compare and contrast 'Offset-based pagination' and 'Cursor-based (keyset) pagination' in the context of this specific use case.
  • Explain how your system handles the case where new transactions are inserted while a user is paginating.

Constraints

  • Use a relational database (e.g., PostgreSQL) as the primary storage.
  • Assume the transactions table contains transaction_id, user_id, amount, and created_at (timestamp with nanosecond precision).
  • The API should be performant even for users with millions of transactions.

Hints

Hint 1

Consider the performance impact of the 'OFFSET' clause in SQL as the offset value grows larger.

Hint 2

Think about how a unique, monotonically increasing column or a combination of timestamp and ID can serve as an immutable cursor.

Hint 3

Address how you would handle potential duplicates if two transactions have the exact same `created_at` timestamp.

Follow-up questions

  • How would you ensure the cursor remains valid if the underlying database shard or partition changes?
  • If the client requests to 'jump' to page 1,000,000 immediately, does your cursor design still work?
  • How would you design the system to handle 'soft-deleted' transactions without leaking information or breaking pagination indexes?