Designing an Audio Search Engine

What you'll learn

• Problem Statement

  Design a system that can identify a song from a short audio clip (approximately 10 seconds). The system must match the clip against a database of millions of songs, even in the presence of background noise such as crowd chatter, traffic,…

• Functional Requirements

  - Accept a short audio clip (5-15 seconds) as input - Return the matching song title, artist, and timestamp within 2-3 seconds - Handle noisy environments (restaurants, streets, concerts)

• Non-Functional Requirements

  - Low latency ( 95% match rate in moderate noise) - Scale to 1 million+ songs in the catalog - Support 1000+ concurrent identification requests per second ---

• Audio Representation

  Sound is a pressure wave. When digitized, we capture amplitude (loudness) at regular time intervals (e.g., 44,100 samples/second for CD quality). However, raw amplitude over time is not useful for matching because: - Two recordings of th…

• Spectrogram

  A spectrogram transforms audio from the time domain into the time-frequency domain: Each vertical slice shows which frequencies are present at that moment and how strong they are. This is computed using a Short-Time Fourier Transform (ST…

• Feature Extraction — Why Not Raw Audio?

  Storing and searching raw audio is impractical for three reasons: | Problem | Impact | |---------|--------| | Storage overhead | Raw audio at 44.1kHz, 16-bit = ~10 MB/min. For 1M songs at 3 min avg = 30 TB raw | | Search cost | Comparing…

• Choosing Interesting Points

  From the spectrogram, we select peaks — points where amplitude is locally maximal in the frequency domain.

• Why peaks?

  - Peaks represent the strongest frequency components at a given time - Background noise raises the overall floor but does NOT shift where peaks occur - Even with 20 dB of added noise, the dominant peaks remain in approximately the same f…

• Why not raw amplitude values?

  We care about which frequencies dominate (relative transitions), not absolute loudness values. A recording at half volume has the same peaks in the same positions — only the floor changes. ---

• Combinatorial Hashing

  Once we have a set of interesting points (peaks), we need to convert them into searchable fingerprints.

• The Algorithm

  1. Divide the song into overlapping chunks (e.g., 10-second windows) 2. Within each chunk, identify k interesting points (e.g., k = 10) 3. For every pair of points within the chunk, compute a hash: Each hash is 3 integers = 12 bytes.

• Why pairs instead of individual points?

  A single frequency value is not distinctive enough — many songs share similar frequency peaks. A pair with a time delta creates a much more unique signature.

• Why time deltas instead of absolute timestamps?

  Time deltas are offset-agnostic. Whether you start recording at second 45 or second 47 of a song, the relative spacing between peaks within your clip remains the same. Absolute timestamps would require knowing exactly where in the song t…

• Example

  ---

• Sliding Window for Chunk Boundaries

  A fixed chunking scheme has a boundary problem: if the user's clip straddles two chunks, neither chunk fully contains the clip's peaks. Solution: Use overlapping windows with 50% overlap. With 10-second chunks and 50% overlap, we get a c…

• Storage Structure

• The Fingerprint Dictionary

  Each entry in the bucket is a tuple: (songID, chunkoffset) — telling us which song and which part of that song produced this hash.

• Search Algorithm

  1. Extract peaks from the user's clip 2. Compute all combinatorial hashes (same algorithm as indexing) 3. For each hash, look up the bucket in the dictionary 4. Accumulate a vote count per (songID, chunkoffset) 5. The (songID, chunkoffse…

• Capacity Estimation

• Storage

  | Parameter | Value | |-----------|-------| | Total songs | 1,000,000 | | Average song length | 200 seconds (~3.3 min) | | Chunk size | 10 seconds | | Overlap | 50% (chunk every 5 sec) | | Chunks per song | 200 / 5 = 40 | | Interesting p…

• Ingestion Throughput

  - 1M songs 40 chunks 50 pairs = 2 billion fingerprints to index - At 100K inserts/second per node, 10 nodes can index the full catalog in ~2000 seconds (~33 minutes) ---

• Processing Estimation

• Query Load

  | Parameter | Value | |-----------|-------| | Requests per second | 1,000 | | Pairs per clip | 50 (from 10 peaks in one 10-sec chunk) | | Hash lookups per request | 50 | | Time per hash lookup (in-memory) | 5 ms (including network hop) |…

• Compute Requirement

  This can be served by approximately 50 machines with 8 cores each, or via an auto-scaling cluster. ---

• Design Evolution & Trade-offs

  How this system grew from an MVP to what a production version looks like — and the choices you'd defend in an interview. Audio search is a read-heavy, latency-sensitive workload with a distinctive shape: each query fans out to ~50 hash l…

• Stage 1 — MVP: One box, one database

  The simplest thing that could possibly work for audio-search-engine. - A single API server that accepts an uploaded audio clip. - A single Postgres database with one big table: fingerprints(hash BIGINT, songid INT, chunkoffset INT) index…

• Stage 2 — Scale-out: Multiple pods behind a load balancer

  - API layer becomes stateless; N replicas behind an L7 load balancer. - Split the API into two logical tiers: Audio Processing (CPU-bound: decode, spectrogram, peak extraction) and Matching (I/O-bound: hash lookups + vote tally). Same bi…

• Stage 3 — Bottleneck: Fingerprint lookup fan-out at scale

  This is THE hard problem in audio identification. Every query is a 50-way fan-out against a two-billion-entry index, and hot hashes have posting lists in the thousands. You need sub-millisecond point lookups, tolerable behavior on hot ke…

• Stage 4 — Second bottleneck: Audio processing CPU and ingestion throughput

  Even with a perfectly scaled fingerprint store, the front half of the pipeline (decode → spectrogram → peak extraction → hash-pair generation) is expensive. At 1000 QPS with ~50 ms of CPU per clip, you need ~50 cores of processing capaci…

• Stage 5 — Mature architecture

  The full production system with all the additions from stages 2–4: Key notes on this diagram: - Mobile bypasses the FFT service — it sends hashes directly, so its request skips the CPU tier entirely. - Redis shards are keyed by hash % N;…

• Cost vs Complexity — When to Pick What

  | Concern | MVP choice | Growth choice | Enterprise choice | |---------|-----------|---------------|-------------------| | Compute | Single VM (Python + numpy) | K8s deployment with native FFT service | Multi-region K8s + GPU spot fleet…

• Migration Path (MVP → Enterprise)

  An ordered playbook — HOW you'd migrate a live system, in what order, and how to avoid downtime. Not every step has to happen; each depends on hitting a specific pain point. 1. Split the API into Audio Processing and Matching tiers. Same…

• Architecture Diagram

  ---

• Handling Edge Cases

• Noise Robustness

  - Peaks are chosen at high-amplitude frequency points that persist through noise - Combinatorial pairing means even if some peaks are missed due to noise, many pairs still match - A threshold (e.g., match at least 20% of expected pairs)…

• Time Stretching / Pitch Shifting

  - Minor tempo variations: the overlapping window approach absorbs small timing differences - Significant pitch shifting would require storing multiple versions of fingerprints (rarely needed for identification use cases)

• Duplicate/Cover Songs

  - Different recordings of the same composition produce different peaks (different instruments, vocals, mastering) - The system identifies specific recordings, not compositions ---

• Summary

  | Component | Choice | Why | |-----------|--------|-----| | Representation | Spectrogram peaks | Noise-resistant, compact | | Fingerprint | Combinatorial hash of peak pairs | Unique, offset-agnostic | | Storage | Distributed hash table |…