Design a music identification system like Shazam: a user holds up a phone in a noisy cafe, records a 10-second snippet, and the app names the song within a second. Apple’s ShazamKit exposes the same matching to third-party apps, Google’s “Now Playing” identifies music continuously and offline on Pixel phones, and SoundHound even accepts hummed melodies.
How would you design this system? Cover the audio fingerprint representation, the matching index, the latency and scale budget, and how the system behaves under noise, tempo changes, and remixes.
The Problem: ten seconds of music buried in cafe noise must pick one recording out of tens of millions, in under a second, and a wrong answer is worse than none. Design the system that hears the song through the crowd.
Answer
The design is audio fingerprinting with landmark hashes, the approach Shazam published in 2003 and which remains the backbone of production matchers: convert audio to a spectrogram, keep only the strongest time-frequency peaks (a constellation map that survives noise), hash pairs of peaks into compact tokens, and match a query by finding reference tracks whose hashes recur with one consistent time offset. The two pivotal decisions are to match a lossy peak representation instead of the waveform (robustness to noise, codec compression, and reverb) and to use an inverted index over hashes with time-coherence voting, which turns “find this song” into a few hundred lookups and a histogram test rather than a comparison against the whole catalog.
(1) Constellation Frontend: STFT spectrogram, keep local peaks only; noise must out-shout a peak to erase it, so ~20 peaks/second survive a cafe.
(2) Combinatorial Hashing: each anchor peak pairs with peaks in a short target zone; the hash packs both frequencies and the time gap, giving millions of distinct tokens.
(3) Inverted Index + Offset Voting: hash to list of (track, time) postings; matching query hashes vote on the offset, and a histogram spike declares the track.
(4) Asymmetric Confidence: naming the wrong song costs more than “no match found”, so an answer needs enough aligned votes plus a margin over the runner-up.
(5) Catalog Ingestion at Scale: new releases are fingerprinted as labels deliver them; the index is sharded by hash and held in RAM for sub-second queries.
Figure 1: Register and recognize lanes share one fingerprinting frontend; recognition is index lookups plus offset voting, never a comparison against raw audio.
Clarify Before Designing:
(1) Query Conditions: phone microphone in noise versus clean line-in audio, and how short a snippet must work (5 s? 15 s?)?
(2) Catalog Scope: tens of millions of commercial tracks, and do covers, remixes, and live versions count as the same song?
(3) Latency Budget: sub-second answer on a mobile connection, or is a few seconds acceptable?
(4) On-Device versus Cloud: must matching run offline with a regional catalog subset (the Now Playing design), or is the phone always online?
(5) Beyond Exact Recordings: is humming or cover identification in scope (a different, melody-based representation), or exact audio only?
Leave a Reply