Detailed Component Design

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.

Write-Time Normalization Pipeline

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.

Alias Table Management

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.

Autocomplete with Redis Sorted Sets

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.

Search Index Sync via CDC

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.

Trade-offs and tech choices

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.

SQL (PostgreSQL) vs NoSQL (Cassandra) for item_tags

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 vs Hierarchical Tags

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 vs Read-Time Normalization

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.

Submissions

Displaying Solutions with Scores Ranging from 1 to 10

Submissions

Displaying Solutions with Scores Ranging from 1 to 10