Tagging Service

The problem

"Design a tagging service that many products share." A photo site, an articles site and a help desk all need the same two lookups: the tags on an item, and the items with a tag.

This practice problem reuses the pattern of the Search Engine: a tag's list of item ids is an inverted index, with tags in place of words. Five things are new: lookups both ways, huge tags, many spellings of one tag, suggestions while you type, and many products in one service. Park tags read from what a photo shows: a project of its own.

The numbers

From the interviewer: 50 products, 2 billion items with about 5 tags each, and about 1 billion lookups a day, most of them to show an item's tags. Round a day to 100,000 seconds (86,400 really); busy hours run about 5× the average.

• Links: 2 billion items × 5 tags = 10 billion item–tag pairs.
• Lookups: 1 billion ÷ 100,000 = 10,000 a second on average (about 11,600 with 86,400), so about 50,000 a second at busy hours.
• Servers: say one database server answers about 5,000 lookups a second: about 10 servers, so each lookup must land on the right one.

Both ways: two tables

Tags and items are many-to-many, and products ask in both directions. As in Tables From Query Patterns, list the questions first and key a table for each busy one:

table     partition key    sorted by          holds
by tag    product, tag     tagged_at, item    item ids
by item   product, item    tag                tag names

Every lookup names its key and reads one partition. Each new tag is written twice and the space doubles: 10 billion links × 2 × about 50 bytes (say) = 1 TB, 3 TB with 3 copies.

One table fails at this size: keyed by item, "items with sunset" makes every server read all its rows, and with an index on tag in each server, a tag page still asks all 10. (A global index is the second table under another name.) The product always comes from the caller's API key:

POST /items/p1/tags          {"tag": "Sunset"}
  → 201 Created              {"tag": "sunset"}
GET /items/p1/tags
GET /tags/sunset/items?limit=20
GET /tags?prefix=su

Huge tags: cursors

On the photos product, sunset is on 5 million photos, and its tag page shows the newest 20 as people scroll. Sending all 5 million ids would be 40 MB per open. Offset paging breaks as in Pagination: page 5,001 is OFFSET 100000, 100,020 rows read to send 20, and photos tagged meanwhile push the rest down, so pages repeat.

A cursor fixes both: each reply ends with next_cursor, the last item's time and id, and the next page reads the 20 rows just after it. The id breaks ties between photos tagged in the same second.

A tag this big also strains its partition: 5 million rows × 50 bytes is 250 MB, past a common rule of thumb of about 100 MB. Split big tags by month, as Tables From Query Patterns split a giant chat; the cursor's time says which month to read next.

One tag per meaning

Writers on the articles product tag one topic JavaScript, javascript, js and JS: 100,000 articles, of which a lookup for javascript finds 40,000. The service cleans each name (trims, lowercases, puts accented letters in one standard form), then maps it through the product's synonym list: js → javascript. It stores that one tag and runs the same steps on every lookup, so JS finds all 100,000.

Storing names as typed and looking up every spelling turns one read into several and misses spellings nobody listed. Merging names spelled almost alike is worse: cat and car are one letter apart, while js is 8 letters away from javascript. Synonyms need a list people curate; when someone adds one, a background job moves the old tag's rows over.

Suggestions while you type

This is Autocomplete on a small scale: a trie of each product's tag names with each prefix's top 5 stored at its node, rebuilt from the counts every few minutes, so a keystroke costs a few memory reads, well within 100 ms. Rank by use: for ja, articles suggests javascript (100,000), java (60,000), japan (12,000), jasmine (4,000) and jazz (3,000), and the typo javscript, on 2 articles, drops off. People pick the tag that exists, so fewer duplicates are made. In alphabetical order, jakarta (900) would come first and javascript last.

Many products, one service

Fifty products share the servers, the tables and the cleaning code, from photos with 1 billion items to a help desk with 10,000 tickets; each gets its own tag names, synonyms, suggestions and request quota: a multi-tenant service. Every key starts with the product's id, read from the caller's API key, never from the request body, so no product can reach another's rows. A quota per product, as in the Rate Limiter, keeps a busy day on photos from slowing the help desk. A cluster each would isolate them too, but most would sit idle.

Same pattern as the Search Engine

The by-tag table is an inverted index, and both sides clean names by the same rules. But a tag lookup names one tag and wants its items in order: the index is split by tag, not by document, and there's no ranking, only an order to keep.

Summary

• Scope: tag items and find items by tag, for many products.
• Data: two tables, by tag and by item, every key starting with the product.
• API: POST /items/{id}/tags, GET /tags/{tag}/items?cursor=…, GET /tags?prefix=….
• Numbers: about 50,000 lookups a second at busy hours; about 1 TB of links.
• Services: one shared service; each product apart by key, with a quota.
• Scale: cursors through tags with millions of items; big tags split by month.
• Spellings: clean, map synonyms, store one tag.
• Suggestions: each product's top 5 tags per prefix, ready ahead.