Shazam

0) Problem Restatement

Design a music recognition system like Shazam that can identify songs from short audio clips (5-10 seconds) captured in noisy environments. Core challenges include creating robust audio fingerprints, matching against millions of songs in real-time (< 5 seconds), handling background noise, and scaling to billions of recognition requests.

1) Requirements

1.1 Functional

• Recognize songs: Identify songs from short audio clips (5-10 seconds).
• Handle noise: Work in noisy environments (cafes, bars, concerts).
• Display metadata: Show song title, artist, album, lyrics.
• History: Store user's recognition history.
• Music links: Provide links to Spotify, Apple Music, YouTube.
• Offline mode: With no connection, record and fingerprint the clip on the device, queue it, and match it when the phone is back online.
• Search: Users can search for songs by name/artist.

1.2 Non-Functional

• Accuracy: > 95% recognition rate for clean audio, > 80% for noisy audio.
• Latency: Recognize song in < 5 seconds (P99).
• Scalability: Handle billions of recognition requests/month.
• Database Size: Index 70M+ songs.
• Availability: 99.9% uptime.
• Storage: Efficient fingerprint storage (compact representation).

1.3 Scale Estimates

• Songs in database: 70 million songs.
• Recognition requests: ~1B recognitions/month ≈ 33M/day ≈ 400 requests/sec avg; ~3× at evening/weekend peaks → ~1,200 requests/sec.
• Index lookups: each request carries ~50–100 hashes → ~100K hash lookups/sec at peak.
• Query fingerprint: 5–10 s clip → ~50–100 hashes × ~8 bytes ≈ < 1 KB uploaded (vs ~100 KB of compressed audio).
• Hashes per song: a 3–4 minute track produces ~5K–10K hashes.
• Index size: 70M songs × ~10K hashes = ~700B postings × ~8 bytes (song_id + time offset) ≈ 5.6 TB. Too big for one machine's RAM, so the index is sharded (Deep Dive C).
• Postings per hash: with a 32-bit hash (~4.3B possible values), 700B postings ÷ 4.3B ≈ ~160 songs per hash on average — each query scans ~100 × 160 ≈ 16K postings.
• Song metadata: 70M songs × 5 KB metadata = 350 GB.

1.4 API Design

The core APIs required for the service:

• Identify Song: POST /v1/identify - Upload audio fingerprint for matching.
• Get Song Details: GET /v1/songs/:song_id - Retrieve metadata (title, artist, lyrics).
• Get User History: GET /v1/users/:user_id/history - Retrieve past recognitions.
• Get Trending: GET /v1/charts/trending - Retrieve top identified songs.

2) High-Level Architecture

2.1 Overview

• Recognition Pipeline: Audio Capture → Fingerprint Generation → Fingerprint Matching → Metadata Retrieval.
• Indexing Pipeline: Song Audio → Fingerprint Extraction → Index Storage.
• Key components: Audio fingerprinting algorithm, inverted index for fast lookup, distributed matching service.

2.2 Architecture Diagram

flowchart TB
    %% User Recognition Flow
    User["User - Mobile App"] -->|"1. Capture Audio (10s)"| App["Shazam App"]
    App -->|"2. Generate Fingerprint"| FPGen["Fingerprint Generator<br/>(Client-side)"]
    FPGen -->|"3. Send Fingerprint"| AG["API Gateway"]
    
    AG -->|"4. Match Request"| Matcher["Matching Service"]
    Matcher -->|"5. Lookup Fingerprint"| Index["Fingerprint Index<br/>(Inverted Index)"]
    Index -->|"6. Candidate IDs"| Matcher
    
    Matcher -->|"7. Verify Match"| Verifier["Match Verifier"]
    Verifier -->|"8. Confirmed Song ID"| MetadataDB["Metadata Service"]
    MetadataDB -->|"9. Fetch Details"| Cache["Metadata Cache<br/>(Redis)"]
    Cache -->|"10. Return Song Info"| User
    
    %% Indexing Pipeline (Offline)
    Songs["Music Catalog<br/>(70M songs)"] -->|"I1. Audio Files"| Ingestion["Ingestion Service"]
    Ingestion -->|"I2. Extract Fingerprints"| FPExtract["Fingerprint Extractor"]
    FPExtract -->|"I3. Hashes"| Indexer["Indexer Service"]
    Indexer -->|"I4. Update Index"| Index
    Indexer -->|"I5. Store Metadata"| MetadataDB[(Metadata DB)]
    
    %% Analytics
    Matcher -->|"11. Log Recognition"| Analytics["Analytics Service"]
    Analytics -->|"12. Update Trending"| TrendingDB[(Trending DB)]
    
    %% Styling
    classDef user fill:#e3f2fd,stroke:#1976d2,stroke-width:2px;
    classDef matching fill:#c8e6c9,stroke:#388e3c,stroke-width:2px;
    classDef indexing fill:#fff9c4,stroke:#f57f17,stroke-width:2px;
    classDef storage fill:#f3e5f5,stroke:#7b1fa2,stroke-width:2px;
    
    class User,App user;
    class FPGen,Matcher,Verifier,MetadataDB matching;
    class Ingestion,FPExtract,Indexer indexing;
    class Index,Cache,Analytics,TrendingDB,MetadataDB storage;

3) Components (what & why)

Mobile App

• Capture audio from microphone (5-10 seconds).
• Generate audio fingerprint on-device (reduces bandwidth).
• Send fingerprint to backend for matching.
• Display song results with metadata.

Fingerprint Generator (Client-side)

• Convert raw audio to spectrogram (frequency analysis over time).
• Identify prominent frequency peaks (constellation map).
• Generate fingerprint hashes from peak patterns.
• Output: Compact query fingerprint (~50–100 hashes, < 1 KB).

Matching Service

• Receive fingerprint from client.
• Query inverted index for candidate songs.
• Rank candidates by match score.
• Return top match (song_id).

Fingerprint Index (Inverted Index)

• Structure: {hash: [(song_id, time_offset), ...]}
• Maps fingerprint hashes to songs containing those hashes.
• Enables fast lookup (O(log n) or better with proper indexing).
• Storage: Distributed key-value store (Cassandra, DynamoDB).

Match Verifier

• Verify that candidate song matches user's audio.
• Check temporal consistency (hashes appear in correct time order).
• Calculate confidence score.

Metadata Service

• Retrieve song details: title, artist, album, artwork, lyrics.
• Integrate with music streaming APIs (Spotify, Apple Music).

Metadata DB

• Store song metadata and links.
• DB Choice: PostgreSQL or MongoDB.

Metadata Cache (Redis)

• Cache frequently recognized songs.
• TTL: 1 hour.

Ingestion Service (Offline)

• Ingest new songs from music labels.
• Trigger fingerprint extraction.
• Update index and metadata.

Fingerprint Extractor (Offline)

• Process full song audio (3-5 minutes).
• Generate fingerprints for all time windows.
• Output: ~5K–10K hashes per song.

Indexer Service (Offline)

• Build and update inverted index.
• Batch processing for millions of songs.

Analytics Service

• Track recognition requests, success rate, trending songs.
• Use data for improving algorithm and music charts.

4) Data Model

Song

Song(
  song_id,
  title,
  artist,
  album,
  duration_seconds,
  release_date,
  artwork_url,
  spotify_link,
  apple_music_link
)

Fingerprint Index (Inverted Index)

hash_value -> [
  (song_id: 123, time_offset: 5.2),
  (song_id: 456, time_offset: 12.8),
  ...
]

Recognition History

RecognitionHistory(
  recognition_id,
  user_id,
  song_id,
  timestamp,
  confidence_score,
  location
)

Trending Songs

TrendingSongs(
  song_id,
  recognition_count_last_24h,
  trending_score,
  rank
)

5) Key Flows

5.1 Song Recognition Flow

1. User taps "Shazam" button in app.
2. App records 10 seconds of audio from microphone.
3. App generates audio fingerprint locally:

• Convert audio to spectrogram (frequency vs time).
• Identify frequency peaks (constellation points).
• Generate hashes from peak patterns.

1. Matching Service queries inverted index for each hash.
2. Index returns candidate songs containing those hashes.
3. Match Verifier checks temporal consistency (hashes in correct order).
4. Top match (highest confidence) returned as song_id.
5. Metadata Service fetches song details from cache or DB.
6. App displays song info to user.

5.2 Song Indexing Flow (Offline)

1. New song uploaded to Ingestion Service.
2. Fingerprint Extractor processes full audio:

• Generate spectrogram for entire song.
• Identify peaks at multiple time windows (e.g., every 0.5 seconds).
• Generate thousands of hashes covering the song.

• For each hash, append (song_id, time_offset) to index.

1. Invalidate cache for updated songs.

5.3 Trending Songs Flow

1. Analytics Service aggregates recognition counts per song.
2. Calculate trending score: recognition_count_last_24h × recency_boost.
3. Update Trending DB with top 100 songs.
4. App displays trending chart to users.

6) Deep Dive A: Audio Fingerprinting Algorithm (~10 mins)

Problem

Convert 10 seconds of audio (with noise) into a compact, robust fingerprint that can match against 70M songs.

Shazam's Algorithm (Simplified)

Step 1: Spectrogram Generation

• Input: Raw audio waveform (time-domain signal).
• Process: Apply Short-Time Fourier Transform (STFT) to convert to frequency domain.
• Output: Spectrogram (2D matrix: frequency bins × time frames).
• Example: 10 seconds at 44.1 kHz → spectrogram with ~200 time frames × 512 frequency bins.

Spectrogram (brightness = loudness)

freq ▲
 4kHz│ ░ ░░   ░  ▒   ░░ ░    ░▒  ░
 2kHz│ ▒▓▒░ ░▒▓▒ ░▓█▓░ ▒▓▒ ░▒▓▓▒░ ░▒
 1kHz│▒▓██▓▒▓██▓▒▓███▓▓██▓▒▓███▓▒▓█
200Hz│██▓▓██▓▓██▓▓██▓▓██▓▓██▓▓██▓▓█
     └──────────────────────────────▶ time
      0s        1s        2s      3s

Step 2: Peak Detection

• Goal: Identify prominent frequency peaks (loudest frequencies at each time frame).
• Method:
• For each time frame, find local maxima in frequency bins.
• Apply threshold to filter weak peaks (remove noise).
• Output: Constellation map (list of (time, frequency) peaks).
• Example: 10-second clip → ~500-1000 peaks.

Constellation map (only the strongest local peaks survive)

freq ▲
 4kHz│             •
 2kHz│   •     •          •
 1kHz│      •       •  •      •
200Hz│ •          •      •
     └──────────────────────────▶ time
      0s       1s       2s    3s

Step 3: Hash Generation (Combinatorial Hashing)

• Goal: Create robust hashes from peak patterns.
• Method:
• For each anchor peak, pair it with nearby peaks (target zones).
• Create hash: hash = f(anchor_freq, target_freq, time_delta).
• Example: Anchor at (t=2s, f=1200Hz), target at (t=3s, f=2400Hz) → hash = hash(1200, 2400, 1s).
• Robustness: Time-shift and noise resistant (relative frequencies and time deltas).
• Output: List of hashes with time offsets.

Step 4: Fingerprint Structure

[
  {"hash": "a3f5b2", "time_offset": 2.1},
  {"hash": "c7e9d1", "time_offset": 2.5},
  {"hash": "b4a8f3", "time_offset": 3.2},
  ...
]

Fingerprinting Pipeline

flowchart LR
    Audio["Raw Audio<br/>(10 sec)"] -->|"STFT"| Spec["Spectrogram<br/>(freq × time)"]
    Spec -->|"peak detection"| Peaks["Constellation Map<br/>(time, freq pairs)"]
    Peaks -->|"combinatorial hashing"| Hashes["Fingerprint Hashes<br/>(hash + time_offset)"]
    
    classDef process fill:#c8e6c9,stroke:#388e3c,stroke-width:2px;
    classDef output fill:#e3f2fd,stroke:#1976d2,stroke-width:2px;
    
    class Spec,Peaks process;
    class Hashes output;

Why This Works

• Robust to Noise: Peaks are most robust features (survive noise).
• Time-Shift Invariant: Uses relative time deltas, not absolute times.
• Compact: < 1 KB query fingerprint vs ~100 KB of audio.
• Fast Matching: Hashes enable O(1) lookup in inverted index.

7) Deep Dive B: Fast Matching with Inverted Index (~10 mins)

Problem

Match user's fingerprint (50-100 hashes) against 70M songs (~700B indexed hashes, ~5.6 TB) in < 1 second.

Inverted Index Structure

Index Layout

hash: "a3f5b2" -> [
  (song_id: 123, time_offset: 45.2),
  (song_id: 456, time_offset: 12.1),
  (song_id: 789, time_offset: 102.5),
  ...
]

Storage

• Key: Hash value (32-bit integer or string).
• Value: List of (song_id, time_offset) tuples.
• Database: Cassandra (partitioned by hash) or DynamoDB.

Matching Algorithm

Step 1: Query Index

• For each hash in user's fingerprint:
• Lookup hash in inverted index.
• Retrieve list of (song_id, time_offset) pairs.

Step 2: Vote on (Song, Time Offset) Pairs

Counting raw hash hits per song is not enough: with ~160 songs per hash, popular hashes hit thousands of songs by chance. The signal is time alignment — for the true song, every matching hash sits at the same offset into the song.

• For each match, compute delta = song_time_offset − clip_time_offset.
• Count votes per (song_id, delta) pair (a histogram of deltas per song), rounding delta to the hash time resolution.
• Example:
• Clip hash at t=2s matches song 123 at t=47s → vote for (123, 45s).
• Clip hash at t=3s matches song 123 at t=48s → vote for (123, 45s).
• Clip hash at t=3s matches song 456 at t=10s → vote for (456, 7s).
• Result: (123, 45s) has 2 aligned votes; song 456's votes are scattered across different deltas.

Step 3: Pick the Tallest Peak

• The best candidate is the (song, delta) bucket with the most votes.
• A real match stands far above the rest (e.g. 40 aligned hashes vs a background of 2–3 per bucket). The delta also tells you *where* in the song the user is, which the app uses to sync lyrics.

Step 4: Confidence Score

• Score = aligned votes in the best bucket, relative to the number of hashes in the clip and to the runner-up bucket.
• Threshold: Return a match only if the best bucket clears an absolute minimum (e.g. ≥ 5–10 aligned hashes) and beats the runner-up by a clear margin; otherwise "no match" and ask the user to try again.

Matching Pipeline

flowchart TD
    UserFP["User Fingerprint<br/>(50 hashes)"] --> Query["Query Inverted Index"]
    Query -->|"hash lookup"| Index["Inverted Index"]
    
    Index -->|"(song_id, song_offset) postings"| Vote["Vote per (song_id, delta)<br/>delta = song_offset − clip_offset"]
    Vote -->|"histogram of deltas"| Temporal["Pick Tallest Peak"]
    
    Temporal -->|"best bucket vs runner-up"| Score["Confidence Scorer"]
    Score -->|"clear winner"| Match["Return Matched Song"]
    Score -->|"no clear winner"| NoMatch["No Match Found"]
    
    classDef match fill:#c8e6c9,stroke:#388e3c,stroke-width:2px;
    classDef nomatch fill:#ffcdd2,stroke:#c62828,stroke-width:2px;
    
    class Vote,Temporal,Score,Match match;
    class NoMatch nomatch;

Performance Optimization

• Early Termination: Once one (song, delta) bucket is far ahead, stop scanning the remaining postings.
• Hash Pruning: Ignore very common hashes (low discriminative power).
• Caching: Cache popular songs' fingerprints in memory.

Time Complexity

• Index Lookup: O(num_hashes × avg_songs_per_hash) = O(100 × ~160) ≈ 16K postings read (fewer after pruning very common hashes).
• Vote Counting: O(16K) hash-map increments.
• Peak Pick: O(number of buckets) — a single pass.
• Total: < 100ms for matching logic.

8) Deep Dive C: Scalability & Distributed Architecture (~8 mins)

Problem

Handle ~1,200 requests/sec peak (~100K hash lookups/sec), hold a ~5.6 TB index, and serve globally with low latency.

Horizontal Scaling

Matching Service

• Stateless: Each request independent.
• Load Balancer: Distribute requests across instances; matching is CPU-light, so a few dozen instances per region is plenty — the index is the expensive part.
• Auto-scaling: Scale based on request rate.

Inverted Index

• Sharding: Partition by hash value (consistent hashing).
• Example:
• Shard 1: hashes starting 0x00-0x1F.
• Shard 2: hashes starting 0x20-0x3F.
• ...
• Parallel Queries: Query all shards simultaneously, merge results.

Caching Strategy

Metadata Cache (Redis)

• Cache top 10K most recognized songs.
• TTL: 1 hour.
• Cache hit rate: > 90% (Pareto principle: 20% songs = 80% recognitions).

Index Cache

• Cache hot hashes (most queried) in memory.
• Reduce database lookups.

Geo-Distribution

Multi-Region Deployment

• Deploy in US, EU, Asia regions.
• Route users to nearest region (low latency).

Index Replication

• Replicate inverted index across regions.
• Eventual consistency acceptable (songs don't change frequently).

Indexing at Scale

Batch Processing

• Use MapReduce or Spark for offline indexing.
• Process millions of songs in parallel.

Incremental Updates

• New songs added incrementally (no full reindex).
• Update only relevant shards.

Distributed Architecture

flowchart TB
    LB["Load Balancer"] --> M1["Matching Service 1"]
    LB --> M2["Matching Service 2"]
    LB --> MN["Matching Service N"]
    
    M1 --> Shard1["Index Shard 1<br/>(hash 0x00-0x3F)"]
    M1 --> Shard2["Index Shard 2<br/>(hash 0x40-0x7F)"]
    M1 --> Shard3["Index Shard 3<br/>(hash 0x80-0xFF)"]
    
    M2 --> Shard1
    M2 --> Shard2
    M2 --> Shard3
    
    MN --> Shard1
    MN --> Shard2
    MN --> Shard3
    
    Shard1 --> Replica1["Replica 1"]
    Shard2 --> Replica2["Replica 2"]
    Shard3 --> Replica3["Replica 3"]
    
    classDef service fill:#c8e6c9,stroke:#388e3c,stroke-width:2px;
    classDef storage fill:#fff9c4,stroke:#f57f17,stroke-width:2px;
    
    class M1,M2,MN service;
    class Shard1,Shard2,Shard3,Replica1,Replica2,Replica3 storage;

9) Scaling & Performance (~5 mins)

Performance Metrics

• Recognition Latency: < 5 seconds (2s client processing + 1s network + 2s backend matching).
• Accuracy: 95% for clean audio, 80% for noisy.
• Throughput: ~1,200 requests/sec peak (~100K index lookups/sec).
• Database Size: ~5.6 TB (fingerprint index, sharded and replicated) + 350 GB (metadata).

Bottlenecks & Mitigations

• Index Lookups: Shard aggressively, cache hot hashes.
• Network Latency: Use CDN for app downloads, geo-distributed backends.
• Cold Starts: Pre-warm caches with trending songs.

10) Failure Modes & Recovery

Index Shard Failure

• Impact: Some hashes not queryable.
• Mitigation: Replicate shards (3× replication), route to healthy replicas.

Matching Service Failure

• Impact: Requests fail.
• Mitigation: Load balancer routes to healthy instances, auto-restart failed instances.

Network Partition

• Impact: Clients can't reach backend.
• Mitigation: Offline mode — fingerprint on the device, queue the request, and match when the connection returns.

11) Trade-offs & Alternatives

Client-side vs Server-side Fingerprinting

• Client-side: Saves bandwidth; with no connection the app can fingerprint now and match later.
• Server-side: More powerful processing, but requires uploading audio.
• Shazam: Client-side for speed and privacy.

Inverted Index vs Locality-Sensitive Hashing (LSH)

• Inverted Index: Exact hash matching, fast lookup.
• LSH: Approximate matching, handles variations better.
• Shazam: Inverted index (exact hashes are robust enough).

12) Security & Privacy

Audio Privacy

• No Storage: Audio clips not stored on server (only fingerprints).
• Encrypted Transmission: TLS for all API calls.

Licensing

• Music Rights: Legal agreements with music labels for metadata.

13) Interview Time Allocation (45 min)

• 5 min: Requirements & scope (functional, non-functional, scale).
• 10 min: HLD & architecture diagram (recognition + indexing pipelines).
• 5 min: Data model & key flows (recognition, indexing).
• 10 min: Deep dive on audio fingerprinting (spectrogram, peaks, hashing).
• 10 min: Deep dive on fast matching (inverted index, temporal consistency).
• 5 min: Scalability, distributed architecture, trade-offs.

14) Summary

• Core Challenges: Robust audio fingerprinting, fast matching against 70M songs, handling noise, scaling to billions of requests.
• Key Components:
• Fingerprinting: Spectrogram → peak detection → combinatorial hashing.
• Inverted Index: Hash → [(song_id, time_offset), ...] for O(1) lookup.
• Matching: Vote counting + temporal consistency check.
• Distributed: Sharded index, geo-replicated, cached metadata.
• Performance: < 5s recognition, 95% accuracy, 200 req/sec, 70M songs indexed.

This design enables Shazam to recognize songs from noisy audio clips in seconds, serving millions of users globally.