skip to content

In a cloud-drive service, how should the API list a folder that holds millions of entries without timing out?

level: seniorimportance: must knowfreq 55%

answer

  1. never all at once
  2. a pre-sorted range per folder
  3. resume after, not skip over
  4. why deep offsets hurt
  5. count kept, not computed

basics

~20 s

Return the folder's children in capped pages through a cursor: read a sorted index on parent ID and name, and resume after the last name returned. Never load the whole folder, use deep offsets, or read blobs to build a listing.

solid answer

~50 s

A million-entry folder is too big to load, sort and send in one response, and offset paging gets slower with depth and skips or repeats entries while the folder changes. So the metadata database keeps a unique index on `(parent_id, name)`, which makes one folder's children a pre-sorted range. Each request reads a capped page, say 1,000 rows, with `name > :last_seen`, and returns an opaque continuation token holding that last name; the next request seeks straight to it, so every page costs the same. Other sort orders need their own index plus a tie-breaker ID in the cursor. The child count comes from a counter maintained on the folder row, not a `COUNT(*)`. The listing is served from metadata, never by scanning the object store, and it is not a snapshot: clients that must stay in sync use a change feed.

code

sql · 6 lines
sql
SELECT id, name, is_folder, size_bytes, modified_at
FROM entries
WHERE parent_id = :folder_id
  AND name > :last_name_seen
ORDER BY name
LIMIT 1000;

go deeper

for a junior

Remember that big folders are returned in pages, and that the next page is requested with a token from the previous one.

for a middle

Explain keyset pagination on a (parent, name) index and why it beats OFFSET on both speed and correctness under concurrent writes.

for a senior

Cover the production details: tie-breakers, extra sort indexes and their write cost, maintained counters, page caps, token validation, and non-snapshot semantics.

for a principal

Weigh which sort orders and counts the product truly needs against index and write cost, and decide when very large folders justify partitioning or a separate listing service.

## Why a huge folder is hard In a **cloud-drive service**, most folders hold a handful of entries, but some - a camera-upload folder, a log dump, a shared team archive - accumulate **millions**. Listing such a folder naively breaks in several ways at once: - **Response size.** A million entries at a few hundred bytes each is hundreds of megabytes of JSON - too large to build in memory, send, or render. - **Query cost.** Loading every child, sorting it and returning it holds database resources for seconds and competes with every other user. - **Moving target.** Entries are added and removed while the user scrolls, so any position-based scheme drifts. - **Side lookups.** Computing each child's permissions, thumbnail or size one row at a time multiplies the cost by a million. ## Keyset pagination over a sorted index The standard answer is **cursor (keyset) pagination** backed by an index that already stores children in display order. With a unique index on `(parent_id, name)`, the children of one folder form a contiguous, pre-sorted range. ```sql SELECT id, name, is_folder, size_bytes, modified_at FROM entries WHERE parent_id = :folder_id AND name > :last_name_seen ORDER BY name LIMIT 1000; ``` 1. The first request omits the cursor and reads the first 1,000 children. 2. The response carries an opaque **continuation token** encoding the last `name` returned. 3. The next request sends the token back; the database **seeks** straight to that point in the index and reads the next 1,000. 4. When a page comes back with no continuation token, the listing is finished. Every page costs about the same regardless of depth, because the index seek jumps directly to the resume point. ## Why not OFFSET `LIMIT 1000 OFFSET 900000` looks equivalent but is not. The database still walks and discards 900,000 index entries to reach the page, so deep pages grow steadily slower. And if an entry is inserted or deleted before the current offset between two requests, every later row shifts position - the user sees duplicates or silently misses entries. A keyset cursor avoids both: entries created before the cursor simply are not in this pass, and existing entries are not repeated because of unrelated inserts. ## The details that make it production-grade | Concern | Approach | |---|---| | Other sort orders | A separate index per order, such as `(parent_id, modified_at, id)`, with the cursor holding both values | | Ties in the sort key | Add a unique tie-breaker, the entry ID, to the index and the cursor | | "12,345,678 items" label | A child counter on the folder row, updated with inserts and deletes, instead of `COUNT(*)` | | Permissions | Evaluate access once for the folder where rules are inherited, not per child | | Page size | A server-enforced maximum, so a client cannot request a million rows | | Tampered tokens | Sign or validate the token so it cannot be pointed at another folder | Each extra sort order is another index that every insert, rename and delete must maintain, so services usually offer only a few server-side orders and sort locally only for small folders. ## Why the object store is the wrong place to list Object stores expose a **flat namespace**: keys are strings, and "folders" are just shared prefixes. They typically support listing by prefix with a continuation token, but only in key order and without the names, permissions or version state the user needs. If blob keys are opaque IDs - as they should be - there is no folder prefix to list at all. Listing belongs to the **metadata database**, which already holds the tree. ## Consistency expectations A paginated listing is not a snapshot. Entries created behind the cursor after paging began will not appear in this pass, and an entry renamed across the cursor may be seen twice (moved forward) or not at all (moved backward). That is normally acceptable: clients that need to stay in sync rely on a separate change feed rather than repeated relisting. Holding a long-lived snapshot open for a million-row scroll would pin database resources far longer than it is worth. ## In an interview Explain why the naive approach fails, then describe the index, the cursor and the page cap. Contrast with `OFFSET`, mention the stored counter, and note that a folder too large for one database partition raises a separate sharding question that is out of scope here.

  • Why is OFFSET pagination a poor fit for a million-entry folder?
    With `OFFSET 900000` the database still walks and discards 900,000 index entries before returning a page, so each deeper page is slower. Concurrent inserts or deletes before the offset also shift positions, so users see repeated or missing entries. A keyset cursor seeks directly to the last key seen, costing the same at any depth and staying stable under inserts.
  • How would you support sorting that folder by last-modified time?
    Add an index on `(parent_id, modified_at, id)` and make the cursor carry both the last `modified_at` and `id`, resuming with a tuple comparison so ties are broken deterministically. Every such index adds write cost to each insert, rename and edit, so offer a small fixed set of server-side sort orders.
  • Why not list the folder straight from the object store by key prefix?
    Object stores have a flat namespace, list only in key order, and return none of the names, permissions or version state the user needs. With opaque blob IDs there is no folder prefix to list anyway. The metadata database already holds the tree and its indexes, so listings belong there.

saying these in an interview costs you the question

  • Return all children in one response and let the client paginate.
  • OFFSET and LIMIT work fine; deep pages cost the same as the first.
  • Run a COUNT over the children on every listing request.
  • List the folder by scanning the object store for matching keys.
  • Writes to the folder must be blocked while a user is paging through it.