Loading...
List the key functional requirements for the system (Ask the AI for hints if stuck)...
The user can tag certain item
The user can remove tag on certain item
the user can assign multiple tag to an item
user can search and retrieve item by tag
List the key non-functional requirements (performance, scalability, reliability, etc.)...
Scalability: Handle 100M registered users, 10M daily active users, and 1B tag-item associations. The system must scale horizontally as content and tagging volume grow.
Low-latency search: Tag-based search returns results in under 100ms at the 99th percentile. Autocomplete responds in under 50ms. These targets require inverted indexing and caching. SQL joins across a billion-row table cannot meet these latency requirements at 5,800 queries per second.
High availability: The service remains operational during partial infrastructure failures. Tag writes and tag searches degrade independently.
Eventual consistency for search: Tag writes are immediately durable in the primary database. Search index updates may lag by 1-5 seconds. This trade-off is acceptable. Users do not expect instant searchability of just-applied tags. The alternative, synchronous index updates, would couple the write path to Elasticsearch availability and add 20-50ms latency to every tag assignment.
Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...
Assume there are 10M active daily users, and the service is heavy on read compare to writes,
Write throughput: 10M DAU x 5 tag writes/day = 50M writes/day. That is roughly 580 writes per second on average, with peak throughput at 3x reaching about 1,700 writes per second. This is well within a single PostgreSQL primary's capacity.
The 5 tag operations per user per day breaks down roughly as: 2 tag assignments (adding tags to items), 1 tag search, 1 autocomplete interaction, and 1 browse/discover. The write-heavy operations (assignments) are the ones that hit PostgreSQL.
Read throughput: A 10:1 read-to-write ratio gives 500M tag-based searches per day. That is roughly 5,800 reads per second on average, with peak at 3x reaching about 17,400 reads per second. This read volume requires Elasticsearch and caching, raw SQL queries against a billion-row join table cannot sustain this throughput.
Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...
\
POST /v1/tags: Create a new tag. Request body: name (string, required). The service normalizes the name (lowercase, trim, alias check) and returns the canonical tag with its tag_id. If the canonical form already exists, returns the existing tag with 200 OK. Creation is idempotent. This means clients do not need to check whether a tag exists before creating it.
PUT /v1/tags/:id: Rename a tag. Updates the canonical name and triggers a reindex of all associated items in Elasticsearch. This is a rare, admin-level operation.
DELETE /v1/tags/:id: Delete a tag globally. Removes all item-tag associations and the Elasticsearch index entries. Requires admin authorization. Irreversible.
POST /v1/items/:itemId/tags: Attach one or more tags to an item. Request body: tags (array of strings). Each tag is normalized before storage. The response returns the canonical tags that were attached. Idempotent. Attaching an already-attached tag succeeds silently via INSERT ON CONFLICT DO NOTHING.
DELETE /v1/items/:itemId/tags/:tagId: Remove a specific tag from an item. Returns 204 No Content on success. Removing the last association for a tag does not delete the tag itself. The canonical tag remains in the tags table for reuse.
GET /v1/search?tags=javascript,react&op=AND&page=1&limit=20: Search items by tags. The op parameter controls boolean logic: AND returns items with all specified tags, OR returns items with any. Results are paginated and sorted by relevance (default) or recency. This endpoint queries Elasticsearch, not PostgreSQL. Pagination uses cursor-based pagination (after parameter with the last item's sort value) rather than offset-based to avoid deep pagination performance issues.
Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.
API Gateway: Single entry point handling authentication, rate limiting, and request routing. Routes tag write operations to the Tag Service, search queries to the Search Service, and autocomplete requests to the Suggestion Service.
Tag Service: Handles tag CRUD, normalization, and item-tag assignment. Every tag write passes through the normalization pipeline before reaching PostgreSQL. After a successful write, the service publishes an event to Kafka for async index sync. This is the only service that writes to PostgreSQL. Search Service and Suggestion Service are read-only consumers.
Search Service: Translates tag search queries into Elasticsearch boolean queries. Handles AND/OR logic, pagination, and result ranking. Never touches PostgreSQL. All data comes from Elasticsearch.
Suggestion Service: Powers autocomplete and popular tag endpoints. Reads from Redis sorted sets for prefix matching and from the popular tags cache. Falls back to Elasticsearch for complex suggestion queries.
PostgreSQL: Source of truth for tags, items, and their associations. ACID guarantees ensure tag assignments are never lost or duplicated.
Elasticsearch: Inverted index for tag-based search. Each item is indexed with its tag list, enabling both single-tag lookups and multi-tag boolean queries. Updated asynchronously via Kafka. The Search Indexer service sits between Kafka and Elasticsearch, transforming events into index operations.
Redis: Three roles: autocomplete (sorted sets), hot tag counters (INCR), and popular tag cache (TTL-based).
Kafka: Connects the write path to the search index. Tag Service publishes events, Search Indexer consumes them and updates Elasticsearch. Decouples write throughput from index update speed.
S3: Stores the actual items (documents, images, files). The tagging service manages metadata and relationships, not item content. Items are referenced by item_id. The tagging service never reads or writes item content directly.
The entire write path (steps 1-7, 10) completes in 20-50ms. The Elasticsearch update (steps 8-9) happens asynchronously, adding 1-5 seconds before the item appears in tag-based search results.
Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...
Three data stores for three access patterns: PostgreSQL for tag metadata and relationships (ACID writes), Elasticsearch for search (fast reads), Redis for caching and autocomplete (low latency). Forcing all three patterns into one database means it performs poorly for two of them.
Why three stores instead of one? Consider what happens with PostgreSQL alone. Tag CRUD and assignment work perfectly. Relational databases excel at this. But tag search across 1B associations at 5,800 QPS requires inverted indices that PostgreSQL's GIN index cannot serve as efficiently as Elasticsearch. And autocomplete at sub-millisecond latency requires in-memory data structures that disk-based PostgreSQL cannot provide. Each store handles the access pattern it was designed for.
sql
- Canonical tags with unique names
CREATE TABLE tags (
tag_id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
canonical_name VARCHAR(128) UNIQUE NOT NULL,
usage_count INT DEFAULT 0,
created_at TIMESTAMP DEFAULT NOW()
);
Items (documents, images, posts, etc.)
CREATE TABLE items (
item_id UUID PRIMARY KEY,
title VARCHAR(256),
storage_url VARCHAR(512),
created_at TIMESTAMP DEFAULT NOW()
);
Many-to-many join table (the largest table)
CREATE TABLE item_tags (
item_id UUID REFERENCES items(item_id),
tag_id UUID REFERENCES tags(tag_id),
created_at TIMESTAMP DEFAULT NOW(),
PRIMARY KEY (item_id, tag_id)
);
Alias mapping for normalization
CREATE TABLE tag_aliases (
alias VARCHAR(128) PRIMARY KEY,
canonical_tag_id UUID REFERENCES tags(tag_id)
);
Index for finding all tags on an item
CREATE INDEX idx_item_tags_tag ON item_tags(tag_id);
The primary key on item_tags (item_id, tag_id) serves dual purposes: it enforces uniqueness (no duplicate tag assignments) and provides an efficient clustered index for looking up all tags on a given item. Because item_id comes first in the composite key, rows for the same item are physically adjacent on disk, making "get all tags for item X" a sequential read.
The reverse index on tag_id (idx_item_tags_tag) enables looking up all items with a given tag. At small scale, this is fine for search queries. At 1B rows, this index becomes too large for PostgreSQL to scan efficiently at 5,800 QPS, that is when Elasticsearch takes over as the search path.
Each document in the Elasticsearch index represents one item with its tag list. The inverted index maps each tag name to a posting list of item IDs. Searching for "javascript AND react" is a posting list intersection. Elasticsearch finds all items for each tag and returns the overlap. This runs in milliseconds regardless of total data size.
The natural question: why not just add a GIN (Generalized Inverted Index) to PostgreSQL and skip Elasticsearch entirely? PostgreSQL GIN indices support array containment queries, which could handle tag search. The problem is scale and feature set. At 1B rows and 5,800 queries/sec, a GIN index on PostgreSQL would compete with write transactions for I/O. Elasticsearch runs on separate hardware, isolating search load from write load. Elasticsearch also provides built-in relevance scoring, aggregations, and fuzzy matching that PostgreSQL's GIN does not offer.
Three Redis data structures serve three use cases. A sorted set stores tag names with usage counts as scores. ZRANGEBYLEX for autocomplete prefix matching, ZINCRBY for incrementing popularity. A cache stores popular tag lists with a 5-minute TTL, reducing load on PostgreSQL for frequently accessed data. A counter tracks hot tag write rates using INCR. Buffering rapid updates before flushing to PostgreSQL every 60 seconds. This buffering is critical during hot tag storms where thousands of users apply the same tag simultaneously.
Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.
A user types "Java Script" with a space. Another types "javascript" lowercase. A third types "JS" as an abbreviation. Without normalization, these become three separate tags with three separate search results. The normalization pipeline is the GATE. It ensures one canonical tag regardless of how users express it.
Four stages applied at tag creation and assignment:
Stage 1: Trim and lowercase: " Java Script " becomes "java script". This catches the majority of duplicates (case variations and whitespace).
Stage 2: Remove special characters: Configurable per domain. For programming tags, "c++" becomes "cpp" and "c#" becomes "csharp". For general tags, strip hyphens and underscores: "machine-learning" becomes "machine learning".
Stage 3: Alias resolution: Query the tag_aliases table: "js" resolves to "javascript", "java script" resolves to "javascript", "ml" resolves to "machine learning". This catches synonyms and abbreviations that stages 1-2 cannot handle.
Stage 4: Canonical lookup: Check the tags table for the resolved name. If found, use the existing tag_id. If not found, create a new canonical tag. This is an atomic operation using INSERT ON CONFLICT to handle concurrent creation of the same tag.
The pipeline runs in 1-5ms per tag. One Redis cache check for the alias (or PostgreSQL if cache miss), one PostgreSQL lookup or insert. At 580 writes/sec, this adds negligible overhead.
Think about it this way: the normalization pipeline is a funnel. Stage 1 catches 70% of duplicates (case and whitespace). Stage 2 catches another 10% (special characters). Stage 3 catches another 15% (synonyms and abbreviations). Only 5% of tag inputs are genuinely new canonical tags. This means 95% of tag writes resolve to existing canonical tags. The pipeline's job is to prevent that 95% from becoming duplicates.
The alias table is the key to tag quality. Three sources populate it:
Manual curation: Admins define aliases for the top 1,000 tags (covers roughly 80% of usage). Examples: "js" to "javascript", "py" to "python", "ml" to "machine learning".
ML-based suggestions: A background job analyzes tags with similar usage patterns (applied to the same items by the same users). It flags potential aliases for admin review. Example: "react.js" and "reactjs" appear on 95% of the same items. Likely aliases. The algorithm computes tag co-occurrence on the same items using Jaccard similarity. Tags with similarity above 0.8 are flagged as potential synonyms.
Community voting: Users can propose tag merges. Popular proposals surface to admins. This catches domain-specific aliases that ML and manual curation miss.
Tags are stored in a Redis sorted set with usage count as the score:
ZADD tags:autocomplete 150000 "javascript"
ZADD tags:autocomplete 120000 "python"
ZADD tags:autocomplete 95000 "react"
Prefix matching uses ZRANGEBYLEX: typing "jav" returns "java", "javascript", "javafx" sorted by usage count. Response time is under 1ms. ZINCRBY updates counts on every tag assignment. Redis handles millions of increments per second.
Why a sorted set instead of a trie data structure? Redis sorted sets with ZRANGEBYLEX provide prefix matching natively without a custom trie implementation. The sorted set is also persistent. It survives Redis restarts. A trie would be faster for very deep prefixes (10+ characters), but tagging autocomplete rarely needs more than 3-5 characters to narrow results to under 10 suggestions. The sorted set's simplicity wins.
Debezium captures PostgreSQL WAL changes and publishes them to Kafka. The Search Indexer consumes these events, fetches the complete item-tag mapping, and writes to Elasticsearch. This CDC (Change Data Capture) approach has two advantages over application-level events: it captures all changes (including direct SQL updates) and guarantees no events are missed. If the row changed in PostgreSQL, Debezium sees it.
A nightly full reindex runs as a safety net. It reads all item-tag associations from PostgreSQL and rebuilds the Elasticsearch index from scratch using a blue-green strategy. Build the new index alongside the old one, then swap the alias atomically. This catches any events that were lost due to Kafka issues or indexer bugs. The reindex runs during off-peak hours and takes 2-4 hours for 1B associations. Users see no downtime because search queries hit the old index until the swap completes.
Key Insight
GATE. Write-time normalization makes search trivially correct. If every tag variant resolves to one canonical form before storage, then searching for 'javascript' returns all items regardless of how the tag was originally typed. The alternative (query-time deduplication) requires expanding every search query to include all known variants, which is fragile and slow.
Interview Tip
The alias table is the secret weapon for tag quality. Start with manual curation for the top 1,000 tags (covers 80% of usage). Add ML-based suggestions over time to catch new synonyms. Never auto-merge without human review. False positives (merging 'Java' and 'JavaScript') are worse than unmerged synonyms.
Three decisions shape the system: SQL vs NoSQL for the join table, flat vs hierarchical tags, and write-time vs read-time normalization. Each has a clear winner for this use case, but understanding the trade-offs shows when you would choose differently.
PostgreSQL wins for this workload. At 580 writes/sec, a single instance handles the volume easily. ACID guarantees prevent duplicate tag assignments. The unique constraint on (item_id, tag_id) enforces idempotency at the database level. Foreign keys ensure referential integrity (no orphaned tag associations). The dataset at 100GB fits comfortably in a well-provisioned instance with room to grow.
The key advantage is operational simplicity. PostgreSQL is a single technology with well-understood operational patterns. Backups, failover, monitoring, query optimization. Cassandra adds operational complexity (token ring management, compaction tuning, repair operations) that is only justified when PostgreSQL cannot handle the load.
Cassandra would become necessary at 10x scale, 5,000+ writes/sec sustained, 10B associations, multiple data centers. At that point, PostgreSQL's single-primary architecture becomes a bottleneck and Cassandra's leaderless replication with tunable consistency provides the horizontal write scaling needed. But you sacrifice ACID, foreign keys, and the unique constraint. All of which you would need to enforce in application code. This is a significant engineering cost. Idempotent tag assignment, which PostgreSQL gives you for free with a unique constraint, becomes an application-level concern that must handle race conditions explicitly.
Flat tags for the MVP. A tag is a string. No parent, no children, no tree structure. Searching for "javascript" finds all items with that tag. Simple to implement, simple to index, simple to search.
Hierarchical tags (programming/javascript/react) add organizational value. Browsing by category, inherited search (searching "programming" returns all children). But they require either materialized path queries (WHERE tag_path LIKE 'programming/%') or closure tables (precomputed ancestor-descendant pairs). Both significantly increase storage complexity and query latency.
The pragmatic path: ship with flat tags, add hierarchy as a future improvement if user research shows browsing-by-category is a high-value feature. Most successful tagging systems (Stack Overflow, GitHub, Flickr) started with flat tags and added limited hierarchy only after years of user feedback confirmed the need.
Write-time normalization wins decisively. The normalization pipeline adds 1-5ms per write (alias table lookup). This cost is paid once per tag assignment. The benefit: every search query operates on clean, canonical data. No expansion, no deduplication, no variant matching.
Read-time normalization would mean storing raw user input and expanding every search query to include all known variants. Searching for "javascript" would need to also search "js", "JS", "javascript", "Java Script", and any other known variant. This is fragile (new variants are missed until the expansion list is updated), slow (multiple index lookups per query), and error-prone (expansion lists diverge from reality).
The math makes the choice obvious. At 50M writes/day, write-time normalization costs 50M alias lookups per day (each taking 1ms or less). At 500M reads/day, read-time normalization would cost 500M expansion lookups per day, 10x more work, on the latency-sensitive path. Moving work from the read path to the write path is almost always the right trade-off in read-heavy systems.