Pagination patterns (cursor, offset) in HLD - System Design Exercise

Design: Pagination System for Large Data Sets

Design covers backend pagination API and data retrieval patterns. UI and client implementation are out of scope.

Functional Requirements

FR1: Support efficient retrieval of data in pages for large datasets

FR2: Provide two pagination methods: offset-based and cursor-based

FR3: Allow clients to request any page of data with a fixed page size

FR4: Ensure consistent ordering of data across pages

FR5: Handle data changes (inserts, deletes) gracefully during pagination

FR6: Support high read throughput with low latency (p99 < 150ms)

FR7: Allow pagination for datasets with millions of records

Non-Functional Requirements

NFR1: System must handle 10,000 concurrent pagination requests

NFR2: API response latency p99 under 150ms

NFR3: Availability target 99.9% uptime (max 8.77 hours downtime/year)

NFR4: Data consistency: eventual consistency acceptable for cursor pagination

NFR5: Offset pagination must support random page access

NFR6: Cursor pagination must support forward-only navigation

Think Before You Design

Questions to Ask

❓ Question 1

❓ Question 2

❓ Question 3

❓ Question 4

❓ Question 5

❓ Question 6

Key Components

API layer to accept pagination parameters

Database or storage system with indexing support

Cache layer to speed up repeated queries

Pagination logic module implementing offset and cursor methods

Ordering and filtering mechanisms

Design Patterns

Offset-based pagination using LIMIT and OFFSET

Cursor-based pagination using unique, ordered keys

Keyset pagination for efficient forward navigation

Caching frequently accessed pages

Handling data changes with snapshot or versioning

Reference Architecture

Client
  |
  | HTTP Request with pagination params
  v
API Server
  |-- Validate pagination params
  |-- Choose pagination method (offset or cursor)
  |-- Query DB with pagination logic
  |-- Return paged data + next cursor or page info
  v
Database
  |-- Indexed on ordering key(s)
  |-- Supports LIMIT/OFFSET and key-based queries
  
Cache (optional)
  |-- Stores popular pages or cursors
  

Components

API Server

REST/GraphQL API

Receives pagination requests, validates parameters, and returns paged data

Database

Relational DB (e.g., PostgreSQL) or NoSQL with indexing

Stores data and supports efficient queries with LIMIT/OFFSET or key-based filters

Cache Layer

Redis or Memcached

Caches frequently requested pages or cursor results to reduce DB load

Pagination Logic Module

Backend service code

Implements offset and cursor pagination algorithms and manages ordering

Request Flow

1. Client sends request with pagination parameters: page number and size for offset, or cursor and size for cursor pagination.

2. API Server validates parameters and determines which pagination method to use.

3. For offset pagination, API Server queries the database using LIMIT and OFFSET clauses.

4. For cursor pagination, API Server queries the database using WHERE clauses on the ordering key greater than the cursor value, with LIMIT.

5. Database returns the requested page of data ordered by the specified key.

6. API Server constructs response including data and next page info: next offset or next cursor value.

7. Response sent back to client for display or further navigation.

8. Optionally, popular pages or cursor results are cached to speed up future requests.

Database Schema

Entity: DataRecord - id (primary key, unique identifier) - created_at (timestamp, indexed for ordering) - other_data_fields Relationships: - None required for pagination; focus is on single large table Indexes: - Index on created_at for cursor pagination - Primary key index on id for uniqueness This schema supports ordering by created_at or id for pagination.

Scaling Discussion

Bottlenecks

Offset pagination becomes slow with large OFFSET values due to scanning and skipping rows

Cursor pagination requires stable ordering keys and may not support backward navigation

Database query load increases with high concurrency and large datasets

Cache invalidation complexity when underlying data changes

API server CPU and memory limits under high request volume

Solutions

Use cursor pagination for large datasets and sequential access to avoid OFFSET performance issues

Implement composite cursors with multiple keys to ensure stable ordering

Add caching layer for popular pages or cursors to reduce DB load

Use read replicas to distribute database read traffic

Implement rate limiting and request batching at API server

Use database partitioning or sharding for very large datasets

Design cache invalidation strategies based on data update patterns

Interview Tips

Time: Spend 10 minutes clarifying requirements and constraints, 20 minutes designing the architecture and data flow, 10 minutes discussing scaling and trade-offs, and 5 minutes summarizing.

Explain difference between offset and cursor pagination with pros and cons

Discuss how ordering and consistency affect pagination design

Describe how the system handles large datasets and high concurrency

Mention caching strategies and database indexing importance

Highlight trade-offs between random access and efficient navigation

Show awareness of real-world challenges like data changes during pagination

Practice

1. What is the main advantage of cursor pagination over offset pagination in system design?

easy

A. Cursor pagination is faster and more reliable for large datasets.

B. Cursor pagination uses page numbers to navigate pages.

C. Cursor pagination requires less memory than offset pagination.

D. Cursor pagination always returns the total number of pages.

Solution

1. Step 1: Understand offset pagination limitations

   Offset pagination uses page numbers and offsets, which can be slow and inconsistent on large or changing datasets.

2. Step 2: Analyze cursor pagination benefits

   Cursor pagination uses a unique cursor (like an ID) to fetch the next set of results, making it faster and more reliable for large data.

3. Final Answer:

   Cursor pagination is faster and more reliable for large datasets. -> Option A

4. Quick Check:

   Cursor pagination = faster, reliable [OK]

Hint: Cursor uses unique IDs, offset uses page numbers [OK]

Common Mistakes:

• Confusing cursor with page number
• Thinking cursor pagination returns total pages
• Assuming offset is always faster

2. Which of the following is the correct way to represent an offset pagination request in an API call?

easy

A. /items?start=abc123&count=10

B. /items?cursor=abc123&limit=10

C. /items?page=2&limit=10

D. /items?offset=abc123&limit=10

Solution

1. Step 1: Identify offset pagination syntax

   Offset pagination typically uses page numbers and limit, e.g., page=2 and limit=10.

2. Step 2: Check options for correct syntax

   /items?page=2&limit=10 uses page=2 and limit=10, which matches offset pagination style.

3. Final Answer:

   /items?page=2&limit=10 -> Option C

4. Quick Check:

   Offset pagination = page + limit [OK]

Hint: Offset uses page and limit parameters [OK]

Common Mistakes:

• Using cursor parameter for offset pagination
• Confusing offset with cursor values
• Using invalid parameter names like start or offset with strings

3. Given the following cursor pagination code snippet, what will be the next cursor value returned?

items = [
  {"id": 101, "name": "A"},
  {"id": 102, "name": "B"},
  {"id": 103, "name": "C"}
]

last_cursor = 101
page_size = 2

next_page = [item for item in items if item["id"] > last_cursor][:page_size]
next_cursor = next_page[-1]["id"] if next_page else None
print(next_cursor)

medium

A. 102

B. 101

C. None

D. 103

Solution

1. Step 1: Filter items with id greater than last_cursor

   Items with id > 101 are 102 and 103.

2. Step 2: Take first 2 items as page size is 2

   Next page items are [{"id": 102, "name": "B"}, {"id": 103, "name": "C"}].

3. Step 3: Get last item's id as next cursor

   Last item id is 103, so next_cursor = 103.

4. Final Answer:

   103 -> Option D

5. Quick Check:

   Next cursor = last id in next page = 103 [OK]

Hint: Next cursor = last item's unique id in current page [OK]

Common Mistakes:

• Choosing last_cursor as next cursor
• Selecting first item id instead of last
• Ignoring page size limit

4. A developer implemented offset pagination but users report inconsistent results when data changes rapidly. What is the likely cause and fix?

medium

A. Cause: Using offset with changing data causes duplicates or skips; Fix: Switch to cursor pagination.

B. Cause: Using cursor pagination causes slow queries; Fix: Use offset pagination instead.

C. Cause: Not caching pages; Fix: Add caching layer for offset pages.

D. Cause: Using limit too high; Fix: Reduce limit to 1.

Solution

1. Step 1: Understand offset pagination issues with changing data

   Offset pagination can skip or repeat items if data changes between requests because offset is position-based.

2. Step 2: Identify solution with cursor pagination

   Cursor pagination uses unique IDs, avoiding duplicates or skips even if data changes.

3. Final Answer:

   Cause: Using offset with changing data causes duplicates or skips; Fix: Switch to cursor pagination. -> Option A

4. Quick Check:

   Offset pagination = inconsistent with changing data [OK]

Hint: Offset breaks with data changes; cursor stays consistent [OK]

Common Mistakes:

• Thinking caching fixes offset pagination issues
• Confusing cursor and offset pagination roles
• Reducing limit does not solve data inconsistency

5. You need to design a scalable API for a social media feed with millions of posts. Which pagination pattern should you choose and why?

hard

A. Offset pagination, because it is simple and supports jumping to any page.

B. Cursor pagination, because it handles large, changing datasets efficiently and avoids duplicates.

C. Offset pagination, because it requires less backend logic and is faster for large datasets.

D. Cursor pagination, because it returns total page count quickly.

Solution

1. Step 1: Analyze requirements for large, changing datasets

   Social media feeds have millions of posts and frequent updates, so pagination must be efficient and consistent.

2. Step 2: Compare offset and cursor pagination suitability

   Offset pagination is simple but slow and inconsistent with large, changing data. Cursor pagination efficiently handles these issues by using unique cursors.

3. Final Answer:

   Cursor pagination, because it handles large, changing datasets efficiently and avoids duplicates. -> Option B

4. Quick Check:

   Large dynamic data = cursor pagination best [OK]

Hint: For big changing data, use cursor pagination [OK]

Common Mistakes:

• Choosing offset for large dynamic datasets
• Assuming offset is faster for big data
• Thinking cursor returns total pages