Partitioning, Indexing, and Pagination

In one line: the partitioning decision here goes against the usual advice. Every other chapter said "hash the key for even distribution." This one deliberately does not, and the reason is a lesson in reading your access pattern.

Partitioning: not by blob ID

Distributing blobs randomly (e.g. by Blob ID) creates performance bottlenecks. Partitioning by blob ID scatters data, increasing overhead when listing blobs for a specific account or container.

To resolve this, we partition based on the full path: Account ID + Container ID + Blob ID. This co-locates a user's blobs on the same partition server, enhancing performance.

Partition by blob_ID (bad)
--------------------------
account A, container pics, blob 1  -> partition 7
account A, container pics, blob 2  -> partition 2
account A, container pics, blob 3  -> partition 9

"List blobs in A/pics"  ->  query every partition. Scatter-gather.

Partition by full path: account_ID + container_ID + blob_ID (good)
------------------------------------------------------------------
account A, container pics, blob 1  \
account A, container pics, blob 2   >  same partition (contiguous range)
account A, container pics, blob 3  /

"List blobs in A/pics"  ->  one partition, one range scan.

Note: the manager node maintains partition mappings in distributed metadata storage.

This is range partitioning by prefix — and it contradicts every other chapter for a good reason

The Distributed Cache, Key-Value Store, and Pub-Sub chapters all argued for hashing the key: it spreads load evenly and it is computable without a lookup.

Here the design picks range partitioning on a composite prefix instead, and it is right — because the dominant query is a prefix scan. listBlobs(containerPath) is a functional requirement, and hashing destroys the locality that query depends on. Under hash partitioning, listing one container means scatter-gather across every partition; under prefix partitioning it is one partition and one contiguous scan.

The general rule: hash when you only ever look up single keys; range-partition when you scan ranges. The Databases chapter made exactly this argument, and this is the cleanest example of it in the course.

The cost is what the databases material warned about, and you should volunteer it: range partitioning creates hotspots. One enormous account, or a burst of activity on one container, lands entirely on one partition server — where hashing would have spread it. The mitigation is splitting hot ranges, and the manager node's partition map is what makes that possible without changing any blob's identity.

Blob indexing

As storage grows, finding specific blobs becomes difficult. A blob index facilitates efficient management and querying.

Users define key-value tags — upload date, media type, container name — during upload. An indexing engine reads these tags and populates a searchable index.

Indexing also supports sorting and pagination.

Tags exist because the store cannot look inside the blob

Lesson 1 established that a blob store treats data as unstructured — it never parses the bytes. That is what lets it hold anything, and it is also why it can answer no questions about content.

Tags are the workaround: user-supplied structured metadata attached to unstructured data. The store still does not know what a video is; it knows this blob is tagged type=video.

That keeps the separation clean — the store stays generic, and searchability becomes an opt-in the uploader provides. It is also why the index is a separate engine: indexing is a different workload from storing bytes, with different scaling and different consistency needs.

Practical consequence worth mentioning: because indexing is asynchronous, a freshly uploaded blob may be retrievable by ID before it is findable by tag. Strong consistency on the object, eventual on the index.

Pagination for listing

Listing returns blobs matching a user-provided prefix — a string that the blob name must start with.

A query might match thousands of blobs, and the system cannot return the entire list in a single response. So it uses pagination to return results in pages.

If an account has 2,000 blobs, returning them all at once can degrade performance. Pagination returns the first five results and provides a next button to fetch the subsequent five.

The number of results per page depends on:

Target query response time
Payload size constraints

Continuation tokens

Pagination requires a continuation token to track the current position in the list. If a query's results exceed the page limit, the response includes this token. The client sends the token in the subsequent request to fetch the next batch.

Continuation tokens beat offset-based pagination, and the reason matters at this scale

The naive alternative is LIMIT 5 OFFSET 1995, which fails badly here.

It gets slower as you page. The store must walk past 1,995 entries to return five — page 400 costs 400 times page one.

It skips and duplicates under concurrent writes. If a blob is inserted before your current position between requests, everything shifts by one: you re-see an item you already had, or miss one entirely.

A continuation token instead encodes where you stopped — effectively "resume after key X." Cost is constant per page, and a concurrent insert before X simply does not affect you.

This is the same mechanism as the offset in pub-sub: a position rather than a count. Positions are stable under concurrent modification; counts are not. That is a genuinely transferable API design principle.

Sorting has to happen at write time, not query time

"How do we decide which five blobs to return first out of the 2,000 total?"

We utilize indexing to sort and categorize the blobs. We should do this beforehand, while we store the blobs. Otherwise it becomes challenging when returning the list to the user. There could be millions or billions of blobs, and we can't sort them quickly when the list request is received.

The reasoning is the important part. Sorting billions of entries per query is impossible at interactive latency. So the order must already exist when the query arrives — the index is maintained incrementally on write, and a listing walks it in order.

Which also explains why "first five" is well-defined at all. Without a pre-established order there is no such thing as first, and pagination is meaningless — you cannot resume from a position in an unordered set.

Pagination requires an order; an order at this scale requires a write-time index. The three requirements in this lesson are one requirement.

Key takeaway

Partition by account_ID + container_ID + blob_ID, not by blob ID — because the dominant query is a prefix scan, and hashing would turn every listing into scatter-gather. Accept that range partitioning risks hotspots. Tags provide searchability over data the store cannot interpret, and continuation tokens paginate by position rather than offset, which is stable under concurrent writes.

Interview signal by level

Level	What a strong answer sounds like
L4	"Partition the blobs across servers and return results a page at a time."
L5	Explains the partition key: "partition on the full path rather than blob ID, so one user's blobs are co-located and listing a container hits one partition instead of all of them."
Staff+	Names the reversal and its cost: "this is the one place we range-partition instead of hashing, because the dominant query is a prefix scan and hashing would make every listing a scatter-gather. The price is hotspots on large accounts, so I'd want the ability to split hot ranges. And I'd paginate with continuation tokens rather than offsets — offset gets slower as you page and skips or duplicates under concurrent inserts, whereas a position is stable."

Next: how many copies, and where.