You hold your phone up to a speaker in a loud cafe, capture five seconds of a song you half-recognize, and a moment later the screen names the track, the artist, and the exact timestamp you were listening to. There is background chatter, the audio is compressed by a cheap phone mic, the recording started somewhere in the middle of the song, and the match is drawn from a catalog of over 100 million tracks. And it comes back in under three seconds.

The core question this design has to answer is: given a short, noisy, distorted snippet of audio captured at an unknown offset into an unknown song, find the one matching track out of 100M+ candidates, fast, even though the snippet will never be byte-for-byte identical to anything we stored. That last clause is the whole problem. You cannot hash the raw bytes, because a phone-mic recording in a cafe shares almost no bytes with the studio master. You need a representation that survives noise, compression, volume changes, and equalization, yet is still specific enough that two different songs never collide. That representation is an acoustic fingerprint, and the system is built around computing it, indexing it, and matching it at scale. Let me build it properly.

Functional Requirements (FR)

In scope:

  • Identify a song from a short audio sample. The user records ~5 seconds of ambient audio; the system returns the matching track (title, artist, album, and the offset into the song that the sample corresponds to), or an honest “no match.”
  • Robustness to real-world distortion. The match must survive background noise, phone-mic frequency response, lossy compression, moderate pitch/tempo intactness, volume changes, and starting at an arbitrary point in the song.
  • Catalog ingestion. New tracks are continuously added: we take the reference audio, compute its fingerprints, and index them so the song becomes matchable.
  • Return match confidence. The response carries a confidence signal so the client can distinguish a strong hit from a weak guess and show “no match” rather than a wrong answer.
  • Match history. A user can see the list of songs they previously identified. (A thin feature on top of the core, included for completeness.)

Explicitly out of scope (so I own the scope):

  • Music streaming / playback. Once we identify the track we hand off to Spotify / Apple Music via a link. We do not stream audio.
  • Humming / singing search (query-by-humming). That is a fundamentally different problem (melodic contour matching, not exact acoustic fingerprinting) and deserves its own design. Shazam needs the actual recorded song playing.
  • Live speech / podcast / ad identification beyond the same fingerprinting mechanism. The technique generalizes, but I focus on music.
  • Rights management, licensing, royalties. A separate business system we feed match counts into.
  • The recommendation / discovery feed. Downstream of identification, not part of it.

The one decision that drives everything: the match is not a lookup of the audio, it is a lookup of a compact, noise-robust fingerprint derived from the audio, and the entire architecture is an inverted index from fingerprint hashes to (song, time-offset), plus a time-coherence scoring step that turns thousands of individually-ambiguous hash hits into one confident answer. Get the fingerprint right and the rest is a large but standard inverted-index search problem. Get it wrong and no amount of infrastructure saves you.

Non-Functional Requirements (NFR)

  • Scale: 100M+ songs in the catalog, average track ~3.5 minutes. That is the reference corpus. On the query side, assume 100M+ DAU across the app and OS integrations, each identifying a couple of songs a day, so hundreds of millions of identification queries per day. The reference-fingerprint index is the large object: on the order of trillions of fingerprint entries (arithmetic in BoE).
  • Latency: the end-to-end identification must return in under 3 seconds p95, and much of that budget is the 5-second recording itself plus network. The server-side match (fingerprint the query if not done on device, probe the index, score, rank) must complete in a few hundred milliseconds so the perceived time is dominated by capture, not compute.
  • Availability: 99.9%+ on the query/identify path. A failed identification degrades to “couldn’t hear that, try again,” which is annoying but not catastrophic. Ingestion can lag for hours with no user-visible effect (a brand-new release is simply not matchable until indexed).
  • Consistency: eventual consistency is fine for the catalog. A newly ingested song becoming matchable minutes or hours after upload is acceptable. Once indexed, a fingerprint is immutable; songs are effectively append-only reference data.
  • Durability: the reference audio and the derived fingerprint index are durably stored and replicated. Losing the index means re-fingerprinting the catalog from reference audio, which is expensive but always possible - the reference audio is the source of truth.
  • Accuracy target: high precision is more important than high recall. Returning a wrong song erodes trust far more than returning “no match.” The scoring stage must be tuned so that a low-confidence result is reported as no match rather than a guess.

Back-of-the-Envelope Estimation (BoE)

Real numbers with the arithmetic, because they set the architecture.

Fingerprints per song (this is the number that sizes the whole system):

The fingerprinter finds spectral peaks (a “constellation” of strong time-frequency points), then combinatorially pairs each anchor peak with several nearby target peaks. A rough, defensible density:

Spectral peaks after filtering:      ~30 peaks/sec of audio
Combinatorial fan-out per anchor:    ~10 target peaks -> ~10 hashes/anchor
Hash rate:                           30 * 10 = ~300 fingerprint hashes/sec
Average track length:                3.5 min = 210 sec
Fingerprints per song:               300 * 210 ≈ 63,000, round to ~60k/song

Total reference index size:

Fingerprints total:  100M songs * 60k = 6,000,000,000,000 ≈ 6 trillion entries
Per entry we store:  hash key (32-bit) + posting {song_id (~5 bytes),
                     time_offset (~3 bytes)} ≈ ~8 bytes as a posting.
Index payload:       6e12 * 8 bytes ≈ 48 TB  (before replication/overhead)

So the inverted index is on the order of tens of terabytes - too big for one machine, comfortably shardable across a fleet. Note the lever: the fan-out factor and peak density trade index size and bandwidth against noise robustness. Denser fingerprints match noisier audio but blow up storage; this is the central knob.

Query load:

Assume 100M DAU * ~2 identifications/day = 200M queries/day
= 200,000,000 / 86,400 ≈ 2,300 queries/sec average
Peak (evenings, events, concerts) ~4x ≈ ~9,000 queries/sec

Per-query work:

5-second sample fingerprinted = 300 hashes/sec * 5 = ~1,500 query hashes
Each query hash probes the inverted index for its posting list.
At peak: 9,000 qps * 1,500 probes = 13.5M index probes/sec.

That 13.5M probes/sec is the real read pressure - not the query count, but the fan-out of ~1,500 probes each. It has to hit an in-memory or SSD-backed sharded index, never spinning disk per probe.

Query bandwidth:

If the phone uploads raw 5s audio: 5s * 16 kHz * 16-bit ≈ 160 KB/query.
  9,000 qps * 160 KB ≈ 1.4 GB/sec ingress. Non-trivial.
If the phone uploads only fingerprints: 1,500 hashes * ~8 bytes ≈ 12 KB/query.
  9,000 qps * 12 KB ≈ 108 MB/sec. ~13x cheaper and faster.

That gap decides a key design choice: fingerprint on the device, uploading ~12KB of hashes instead of 160KB of audio, which cuts bandwidth ~13x and removes server-side fingerprint compute from the hot path.

Ingestion:

New releases: ~100k tracks/day industry-wide (generous).
Fingerprints/day = 100k * 60k = 6e9 new entries/day = ~70k inserts/sec.
Bulk backfill of 100M-song catalog is a one-time (re-runnable) batch:
6e12 entries through a Spark job partitioned by hash.

Takeaways: a ~48TB inverted index of ~6 trillion fingerprints is the large object and must be sharded; the read pressure is ~13.5M single-key probes/sec at peak, so the index must be memory/SSD-resident and sharded by hash; fingerprinting on the device cuts query bandwidth ~13x; and ingestion is a latency-insensitive batch/stream problem entirely off the hot path.

High-Level Design (HLD)

The system splits into three planes: an ingestion plane (reference audio in, fingerprints indexed), a query plane (a phone snippet in, a matched song out), and the shared fingerprint index they meet at. The fingerprinting algorithm is identical on both sides - that symmetry is the whole trick: index the reference the same way you fingerprint the query, so matching is just set intersection over hashes plus a time-alignment check.

   ┌──────────────┐  record 5s, fingerprint on-device   ┌──────────────────┐
   │  User phone   │ ──── upload ~1,500 query hashes ───▶ │  Query API / LB  │
   │  - mic        │                                       │  (edge, stateless)│
   │  - fingerprint│ ◀──── {song, artist, offset, conf} ─ └────────┬─────────┘
   │    extractor  │                                                │
   └──────────────┘                                        ┌────────▼─────────┐
                                                            │  Match Service    │
                                                            │  (scatter probes, │
   ┌──────────────────────┐   scatter query hashes          │   gather, score)  │
   │  Fingerprint Index    │◀────────────────────────────── └────────┬─────────┘
   │  (inverted:           │                                          │ candidate
   │   hash -> [ {song_id, │  posting lists per hash                  │ song_ids
   │   offset}, ... ])     │──────────────────────────────────────────┘
   │  sharded by HASH      │
   └──────────▲───────────┘                              ┌──────────────────┐
              │ build/append                              │ Metadata Store    │
   ┌──────────┴───────────┐    ┌────────────────────┐    │ (song_id -> title,│
   │  Ingestion Pipeline   │    │  Reference Audio    │    │  artist, album,   │
   │  (fingerprint every    │◀── │  Store (S3, source  │    │  cover, links)    │
   │   reference track)     │    │  of truth)          │    └──────────────────┘
   └──────────▲───────────┘    └─────────▲──────────┘
              │ new tracks               │ upload masters
   ┌──────────┴───────────────────────────┴──────────┐
   │  Catalog onboarding (labels, distributors)        │
   └───────────────────────────────────────────────────┘

Ingestion flow (write path):

  1. A label/distributor uploads the reference master; it lands in the Reference Audio Store (object storage, the durable source of truth) with a new song_id and metadata rows in the Metadata Store.
  2. The Ingestion Pipeline pulls the audio, runs the same fingerprinting algorithm the client uses, producing ~60k (hash, offset) pairs for the track.
  3. For each pair it appends a posting {song_id, offset} to the Fingerprint Index under key hash. The index is sharded by hash, so writes fan out across shards. Once appended, the song is matchable.

Query flow (read path):

  1. The user taps identify. The app records ~5s from the mic and runs the on-device fingerprint extractor, producing ~1,500 (hash, offset) pairs. It uploads just those hashes (~12KB), not audio.
  2. The Match Service scatters the query hashes across the index shards, gathering the posting list for each hash: every (song_id, ref_offset) where that hash appears in the catalog.
  3. It runs time-coherence scoring (deep dive 2): a true match shows up as many query hashes hitting the same song at a consistent time offset. It ranks candidate songs, picks the top one if it clears a confidence threshold, and looks up its metadata.
  4. It returns {song, artist, album, matched_offset, confidence} (or no_match) to the phone, which renders the result and stores it in the user’s match history.

The key insight: the reference and the query are fingerprinted by the identical algorithm, so identification reduces to “which catalog song shares many of the query’s fingerprint hashes at a single consistent time alignment.” The index answers the first half (which songs share hashes); the scoring answers the second half (are they time-aligned). Both halves are cheap; the fingerprint is what makes them possible.

Component Deep Dive

The hard parts, naive-first then evolved: (1) the fingerprinting algorithm - the constellation map and combinatorial hashing, which is the heart; (2) matching at scale via time-coherence scoring; (3) the inverted index storage and sharding; (4) the sub-3-second query path and noise robustness.

1. The fingerprint - constellation map and combinatorial hashing (the core)

Everything hinges on a fingerprint that is compact, reproducible from a noisy recording, and specific enough that different songs do not collide. Let me evolve to it.

Naive approach: hash the raw audio bytes (or a checksum of the waveform) and look it up.

Where it breaks immediately:

  • A cafe recording through a phone mic shares essentially zero bytes with the studio master. Noise, mic frequency response, lossy codecs, and volume all change the samples. A byte hash of the query matches nothing. This is a non-starter, but it clarifies the requirement: we need features that survive distortion, not raw bytes.

Second attempt: compare spectrograms directly. Convert audio to a spectrogram (a time-frequency image via short-time Fourier transform) and correlate the query spectrogram against every reference. Loudness and phase noise matter less in the spectral domain.

Where it breaks:

  • No index, so it is O(catalog). Correlating a query image against 100M full-song spectrograms per identification is astronomically slow. There is nothing to look up; you scan everything.
  • Still noise-sensitive. Raw spectrogram magnitudes shift with equalization and background noise; direct correlation is fragile. Also the query starts at an unknown offset, so you would slide the correlation over every position of every song. Hopeless.

The answer: reduce the spectrogram to a sparse constellation of peaks, then combinatorially hash pairs of peaks into a searchable key. This is the Wang/Shazam insight.

  • Spectrogram. Slice the audio into overlapping frames, FFT each frame, giving magnitude over (time, frequency). This is a 2D map of energy.
  • Peak picking -> constellation map. In this map, keep only the local maxima - the points that are louder than their neighborhood in both time and frequency. These peaks are the most robust feature there is: adding background noise or changing the EQ rarely removes a strong spectral peak, and the peaks form a sparse “constellation” of dots. We throw away the magnitudes and keep only the locations (time, frequency) of peaks. This is why it survives noise: a strong peak in the original is still a strong peak with a cafe behind it.
   freq
    ▲     .        *              .          *  = kept peak (local max)
    │        *          .    *              .  = discarded (not a local max)
    │   *        .   *            .    *
    │      .        *      .           *
    └───────────────────────────────────────▶ time
   Constellation map: only the strong, noise-robust peaks survive.
  • Why peaks alone are not enough. A single peak is (t, f) - low entropy, shared by countless songs, and its absolute time is meaningless because the query starts at an unknown offset. If we indexed single peaks, every query hash would hit a huge fraction of the catalog. Useless selectivity.
  • Combinatorial hashing of peak pairs. For each peak (an anchor), look at a small target zone of peaks just ahead of it in time. Pair the anchor with each target and form a hash from (f_anchor, f_target, delta_t) - the two frequencies and the time gap between them. This triple is:
    • Time-translation invariant: it encodes the gap delta_t, not absolute time, so it is identical whether the query starts at 0:03 or 1:47 into the song.
    • Far more specific: two frequencies plus a delta is a ~32-bit key with huge cardinality, so a single hash hits only a handful of songs, not millions. Specificity comes from the pairing, not the peak.
    • Noise-robust: built only from surviving peaks.
  • Fan-out. Each anchor pairs with several targets in its zone (fan-out ~10). This multiplies fingerprint density, so even if noise kills some peaks in the query, enough anchor-target pairs survive to match. The fan-out factor is the tunable robustness-vs-size knob from BoE.
  • The stored fingerprint. Alongside each hash we store the anchor’s absolute time offset in the reference track. So one fingerprint entry is hash(f1, f2, dt) -> {song_id, anchor_offset}. The hash is what we search by; the offset is what lets us check time coherence later.
build_fingerprints(audio):
  spec  = stft(audio)                       # time-frequency magnitude
  peaks = local_maxima(spec)                # constellation map (t, f)
  for anchor in peaks:
     for target in target_zone_ahead(anchor):     # fan-out ~10
        dt   = target.t - anchor.t
        h    = hash(anchor.f, target.f, dt)       # ~32-bit, translation-invariant
        emit (h, anchor.t)                         # anchor.t = offset in this track

The elegance: we turn a fragile audio waveform into a sparse set of location-only peaks that survive noise, then combine pairs of peaks into high-entropy, time-shift-invariant hashes that are both robust to distortion and specific enough to index. The query and the reference run this identical function; matching two songs is now comparing two bags of ~32-bit integers.

2. Matching at scale - time-coherence scoring

We have ~1,500 query hashes. Probing the index gives, per hash, a posting list of (song_id, ref_offset). Now we must decide which song matches.

Naive approach: the song with the most hash hits wins. Count, per candidate song, how many query hashes appear in it; return the max.

Where it breaks:

  • Coincidental hash collisions. With billions of postings, a popular hash appears in thousands of songs. Many songs will accumulate incidental hits from unrelated hashes scattered across their whole duration. Raw hit count is noisy; a long or popular song can rack up more coincidental hits than the true short match.
  • It ignores time structure. The defining property of a real match is not just that hashes overlap, but that they overlap in the same time arrangement. If the query is truly a 5-second slice starting at 1:12 into song X, then every matching hash should appear in song X at its own offset that is a constant amount later than in the query. Coincidental matches have no such alignment. Naive counting throws away exactly the signal that separates a real match from noise.

The answer: score by time coherence - the histogram of offset differences. For each candidate song and each shared hash, compute delta = ref_offset - query_offset. For the true song, a large number of shared hashes yield the same delta (that delta is where the query sits inside the song). For every wrong song, the deltas are scattered randomly. So the score is: the height of the tallest bin in the histogram of deltas.

score(query_hashes):
  # 1. probe index, gather postings
  candidates = {}                       # song_id -> list of (query_offset, ref_offset)
  for (h, q_off) in query_hashes:
     for (song_id, ref_off) in index[h]:      # posting list for this hash
        candidates[song_id].append((q_off, ref_off))

  # 2. for each candidate, find the most consistent time alignment
  best = None
  for song_id, pairs in candidates.items():
     hist = {}                          # delta -> count
     for (q_off, ref_off) in pairs:
        delta = ref_off - q_off
        hist[delta] += 1
     peak_delta, peak_count = argmax(hist)     # tallest bin
     if best is None or peak_count > best.count:
        best = (song_id, peak_delta, peak_count)

  # 3. threshold: only accept a confident, sharply-aligned match
  if best.count >= MATCH_THRESHOLD:
     return { song_id: best.song_id,
              matched_offset: best.peak_delta,  # where in the song the query was
              confidence: best.count }
  else:
     return no_match

Why this is powerful:

  • It converts thousands of individually-ambiguous hits into one sharp signal. A wrong song might share 40 hashes with the query, but spread across 40 random deltas (one per bin). The right song shares, say, 120 hashes that all pile into a single delta bin. The tallest-bin height cleanly separates real from coincidental - even when the raw hit counts are similar.
  • It yields the offset for free. The winning delta is the position of the sample inside the song, which is why Shazam can tell you where you were in the track and pop you to that spot.
  • It is robust to missing hashes. Noise removes some peaks, so some query hashes are absent - fine, the surviving ones still align at the same delta. You do not need all 1,500 hashes to hit; a few dozen coherent ones suffice, which is why 5 seconds in a loud room is enough.
  • Threshold tunes precision. Requiring a minimum tallest-bin height (and a margin over the second-best song) is what lets the system say “no match” instead of guessing - honoring the precision-over-recall NFR.

The point: a match is not “shares the most hashes,” it is “shares many hashes at a single consistent time offset,” and the height of the peak in the offset-difference histogram is the confidence score that both selects the song and locates the sample within it.

3. The inverted index - storage and sharding

The 48TB, 6-trillion-entry index is the large object. Its shape and sharding decide whether 13.5M probes/sec is feasible.

Naive approach: one big table fingerprints(hash, song_id, offset) in a relational DB, indexed on hash.

Where it breaks:

  • Volume. 6 trillion rows with a B-tree index on hash is far beyond a single relational instance; index maintenance and storage overhead alone kill it.
  • Probe amplification. Every query is 1,500 point lookups on hash. At 9,000 qps that is 13.5M lookups/sec against one indexed table - impossible on a single node, and relational per-row overhead is pure waste for what is fundamentally a key -> posting-list map.
  • Hot posting lists. Some hashes (common frequency pairs) have enormous posting lists (appearing in millions of songs). A naive index returns the whole list per probe, drowning the match service.

The answer: a sharded, in-memory/SSD inverted index keyed by hash, with posting lists, hot-hash trimming, and hash-based sharding.

  • Structure: hash -> posting list of {song_id, offset}. This is a pure inverted index, not a relational table. The natural fit is a distributed key-value / LSM store (RocksDB-backed service, Cassandra, or a purpose-built in-memory index) where the key is the 32-bit hash and the value is the compact posting list. Point lookups on the key are O(1)-ish; there are no joins, no transactions, no scans.
  • Shard by hash. Partition the keyspace by hash (hash-range or hash-of-hash). This is the right shard key because: (a) a query’s 1,500 hashes spread evenly across all shards, so every query is a balanced scatter-gather that uses the whole fleet rather than hammering one shard; (b) hashes are naturally high-cardinality and uniform, so load is even; (c) ingestion writes also spread evenly. Sharding by song_id would be wrong - a query touches thousands of different songs, so it would scatter unpredictably and offer no locality.
  • Scatter-gather match. The match service splits the 1,500 query hashes by shard, sends one batched multi-get per shard (not 1,500 individual RPCs), and gathers posting lists. Batching per shard is what keeps the RPC count at ~N_shards per query instead of 1,500.
  • Trim hot posting lists. A tiny fraction of hashes are ultra-common and have gigantic posting lists that contribute almost no discriminative signal (they hit everything). Cap posting-list length (keep, say, the most useful K entries) or drop hashes whose list exceeds a threshold. This bounds the worst-case gather size, removes near-useless probes, and defuses the hot-key problem - much like stop-word pruning in text search.
  • Keep it resident. At tens of TB across a fleet, shards hold their index in memory or on fast SSD (LSM with block cache). No probe touches spinning disk. The index is read-mostly and effectively immutable per song, so aggressive caching and compression (delta-encode offsets within a posting list) are easy wins.
  • Rebuildable. The index is derived; the reference audio in object storage is the source of truth. A corrupted shard is rebuilt by re-fingerprinting its songs. So the index replicates for availability but does not need heroic durability guarantees.
Index shard (key-value, LSM/in-memory):
  key   = hash (uint32)
  value = posting list, delta-encoded:
          [ {song_id, offset}, {song_id, offset}, ... ]   # capped length
  Shard by: hash  (uniform scatter across fleet per query)
  Query:    per-shard batched multi-get of the query's hashes for that shard
  Hot-hash policy: cap list length K; drop hashes with |list| > MAX

The lesson: it is a text-search inverted index in disguise - hashes are terms, songs are documents, offsets are positions - so we borrow every trick from search: shard by term (hash), batch probes per shard, prune stop-word-like hot hashes, and keep posting lists resident and compressed.

4. The sub-3-second query path and noise robustness

The budget is ~3 seconds end to end, most of it the recording itself. Server compute must be a few hundred ms.

Naive approach: phone uploads 5s of raw audio; server fingerprints it, probes, scores.

Where it breaks:

  • Bandwidth. Raw 5s audio is ~160KB/query; at peak that is ~1.4 GB/sec ingress plus upload latency on a weak cafe connection, eating a big chunk of the 3s budget.
  • Server fingerprint compute on the hot path. FFT + peak-picking + hashing per query, at 9,000 qps, adds load and latency the client could have absorbed.

The answer: fingerprint on the device, upload hashes, and lay out the server path as a fast scatter-gather with early cutoffs.

  • On-device fingerprinting. The phone runs the same STFT + constellation + combinatorial hashing locally while (or right after) recording, producing ~1,500 hashes = ~12KB. This is ~13x less data than raw audio, uploads fast even on poor networks, and removes fingerprint compute from the server. Modern phones do this trivially. It also means the raw audio never leaves the device unless we choose to send it - a privacy bonus.
  • Budget breakdown.
  record audio ............ ~5 s (fixed; overlaps with fingerprinting)
  on-device fingerprint ... tens of ms (streamed during recording)
  upload ~12 KB ........... ~50-200 ms on a normal mobile link
  scatter-gather probes ... N_shards batched multi-gets, ~20-50 ms
  time-coherence scoring .. a few ms (histogram over gathered postings)
  metadata lookup ......... ~5 ms (single key)
  ---------------------------------------------------
  server side ≈ under ~100-150 ms; total dominated by the 5s capture.
  • Noise robustness comes from the fingerprint design, reinforced by fan-out and offset alignment, not from a heavier query path. Because we only need a few dozen time-coherent hash hits (not all 1,500), the system tolerates most of the query’s peaks being destroyed by noise. If a first pass is inconclusive, the client can extend the recording (capture a few more seconds and re-probe with more hashes) rather than fail - graceful degradation instead of a hard “no.”
  • Stateless match service, regionally replicated. The match service holds no per-user state; it fans out to the nearest index replica set. Regional replicas keep the scatter-gather local and the round trip short. Scale it horizontally with load.
  • Caching the obvious. Extremely popular tracks (a viral song everyone is Shazaming this week) recur heavily; their metadata and even hot posting-list fragments cache well. A per-region cache of “recently identified songs” absorbs the day’s viral spikes.

The standard low-latency lesson applies: push work to the edge (fingerprint on the device), send the smallest possible payload (hashes, not audio), parallelize the lookup (batched scatter-gather across hash shards), and require only partial evidence (a few coherent hits) so noise never forces a full re-capture. The 3-second budget is met because at query time the server does a scatter-gather and a histogram, never signal processing over the whole catalog.

API Design & Data Schema

The identify path is a tiny hash-upload; ingestion and history are separate surfaces.

Client-facing REST

POST /api/v1/identify
  body: { fingerprints: [ {hash: 0x9af31c02, offset_ms: 120}, ... ],  # ~1,500
          sample_ms: 5000, client_ts }
  -> 200 { match: true,
           song_id: "s_88213",
           title: "Midnight City", artist: "M83", album: "Hurry Up...",
           matched_offset_ms: 72000,        # where in the song the sample was
           confidence: 0.94,
           links: { spotify: "...", apple: "..." } }
  -> 200 { match: false }                    # honest no-match below threshold

GET  /api/v1/history?user_id=U123&limit=50
  -> { items: [ {song_id, title, artist, identified_at, matched_offset_ms}, ... ] }

# Ingestion (internal / partner)
POST /internal/v1/catalog/ingest
  body: { song_id, audio_ref: "s3://ref/s_88213.wav",
          title, artist, album, isrc, links }
  -> { song_id, status: "queued_for_fingerprinting" }

Data stores - the right tool per plane

1. Fingerprint Index - distributed key-value / LSM, key hash, value posting list. The hot read path. 6T entries, ~48TB, read-mostly, no joins, no transactions, pure point lookups on a high-cardinality key with scatter-gather across shards. A relational store buys nothing and cannot serve 13.5M probes/sec; this is a textbook inverted-index workload for a sharded KV/LSM engine (RocksDB-backed service, Cassandra, or in-memory).

Table: fingerprint_index      (KV / LSM, key = hash)
  hash          UINT32   PARTITION KEY        -- from (f1, f2, dt)
  postings      LIST<{ song_id UINT40, offset_ms UINT24 }>   -- delta-encoded, capped
  Query:  point get by hash -> posting list (batched per shard)
  Write:  append posting on ingest (idempotent per (hash, song_id, offset))
  Shard by: hash. Hot-hash cap: |postings| <= K.

2. Metadata Store - relational, keyed by song_id. Titles, artists, albums, ISRC, cover art URLs, streaming links. Small relative to the index (100M rows), needs joins (artist -> songs), occasional updates, strong consistency for correctness of what we display. Postgres/MySQL is right; it is off the hot path (one point lookup after the match is decided).

Table: songs                  (relational)
  song_id     BIGINT   PK
  title       TEXT
  artist_id   BIGINT   FK -> artists(artist_id)   INDEX
  album       TEXT
  isrc        CHAR(12) UNIQUE
  duration_ms INT
  audio_ref   TEXT                                 -- pointer to reference audio
  links       JSONB                                -- streaming service deep links
  Index: (artist_id), (isrc)

3. Reference Audio Store - object storage (S3/GCS). The durable source of truth. Large blobs, write-once, read-by-batch during (re)fingerprinting, never on the query hot path. Object storage is the obvious fit: cheap, durable, and the index is always rebuildable from it.

4. Match History Store - wide-column / KV, partition key user_id, clustering key identified_at. Append-only per user, time-ordered reads, no cross-user queries. A wide-column store (Cassandra) sharded by user_id serves “my recent identifications” as a single-partition scan.

Table: match_history          (wide-column)
  user_id       BIGINT     PARTITION KEY
  identified_at TIMESTAMP   CLUSTERING KEY (DESC)
  song_id       BIGINT
  matched_offset_ms INT
  Shard by: user_id.  Query: recent-first scan of one partition.

Why KV/LSM on the fingerprint hot path, relational only for the small metadata catalog: the index has no per-request entity, no joins, no transactions, and shards cleanly on a uniform high-cardinality hash, demanding extreme single-key read throughput - exactly what a sharded LSM/KV store delivers and relational does not. The one place with real relational needs, the song/artist metadata with joins and authoritative fields, is small, slow-changing, and off the hot path, so it lives in Postgres.

Bottlenecks & Scaling

Where it breaks first, in order, and the fix for each:

1. Probe amplification on the index (breaks first). Each query is ~1,500 point lookups; at peak that is ~13.5M probes/sec. Fix: shard by hash so every query is a balanced scatter-gather across the whole fleet, and batch probes per shard so it is ~N_shards RPCs per query, not 1,500. Keep shards memory/SSD-resident. Add index replicas to scale read throughput linearly and to serve queries region-locally.

2. Hot posting lists (hot keys). A few ultra-common hashes appear in millions of songs; returning their full lists drowns the gather and adds no signal. Fix: cap posting-list length and drop stop-word-like hashes whose lists exceed a threshold. These contribute nothing discriminative (they align at random deltas), so trimming them improves both latency and precision.

3. Coincidental matches / precision. Raw hit counts confuse long or popular songs with the true match. Fix: time-coherence scoring - rank by the tallest bin in the offset-difference histogram, not by hit count, and require an absolute floor plus a margin over the runner-up. This is what turns thousands of ambiguous hits into a confident single answer and lets the system say “no match.”

4. Index size / storage. 6 trillion entries, ~48TB, growing with the catalog and with fingerprint density. Fix: tune the fan-out and peak-density knob (denser = more robust but bigger), delta-encode and compress posting lists, and shard horizontally. The fan-out factor is the deliberate trade of storage and bandwidth against noise robustness.

5. Query bandwidth and server-side fingerprint compute. Uploading raw audio is ~13x more data and pushes signal processing onto the hot path. Fix: fingerprint on the device, uploading ~12KB of hashes. Bandwidth drops ~13x, fingerprint compute leaves the server entirely, and raw audio can stay on the phone.

6. Ingestion spikes and full re-fingerprinting. A new release wave, or a change to the fingerprint algorithm requiring the whole catalog re-indexed. Fix: ingestion is off the hot path; run it as a hash-partitioned batch (Spark) plus a streaming appender for new releases. A full re-fingerprint is a big but embarrassingly parallel batch over the reference audio in object storage, done as a background rebuild into a new index version, then swapped in.

7. Single points of failure and multi-region. Fix: the match service is stateless and regionally replicated; the index and metadata are replicated across regions so the latency-critical scatter-gather stays local. The index is rebuildable from reference audio, so a lost shard is recoverable. An ingestion outage only delays new songs becoming matchable, invisible to existing queries.

8. Viral spikes. A song trends and everyone Shazams it at once, concentrating load on a few songs’ postings and metadata. Fix: per-region caches for recently-identified songs’ metadata and hot posting fragments absorb the spike; the scatter-gather still spreads the probe load across all hash shards regardless of which song is trending, so the index itself does not develop a per-song hot spot on reads.

Wrap-Up

The trade-offs that define this design:

  • A noise-robust fingerprint over matching the audio. We never compare waveforms or even spectrograms directly; we reduce audio to a sparse constellation of spectral peaks and hash pairs of peaks into time-shift-invariant keys, trading a lossy representation for one that survives a cafe, a phone mic, and lossy compression.
  • An inverted hash index over a full-scan search. Fingerprinting the reference and the query identically turns identification into inverted-index retrieval - hashes are terms, songs are documents - so we borrow sharding-by-term, batched scatter-gather, and stop-word pruning wholesale.
  • Time-coherence scoring over hit-counting. A real match is many shared hashes at one consistent offset, so we rank by the tallest bin of the offset-difference histogram, which both selects the song and locates the sample, and lets us return an honest “no match” rather than a wrong guess.
  • Fingerprint on the device over uploading audio. ~12KB of hashes instead of ~160KB of audio cuts bandwidth ~13x, removes signal processing from the server, and keeps raw audio on the phone.
  • Precompute and shard the index over compute-at-query-time. All the signal processing happens at ingest; the query path is a scatter-gather plus a histogram, which is how 100M+ songs resolve in a few hundred milliseconds of server time.
  • Precision over recall. A confidence threshold and a margin over the runner-up mean the system prefers silence to a wrong answer, because a wrong song costs more trust than a “try again.”

One-line summary: an audio-identification service that fingerprints both catalog and query into sparse, time-shift-invariant peak-pair hashes, indexes 100M+ songs as a ~48TB hash-sharded inverted index of ~6 trillion postings, and answers a noisy 5-second on-device fingerprint in under 3 seconds by a batched scatter-gather over hash shards followed by an offset-difference histogram whose tallest bin names the song, its position in the track, and the confidence that it is right.