Fixing the Song Search Rate Limits

On 15 September, Spotify stopped answering. Every song typed into the search box came back as a 429 with a body of QUOTA_EXCEEDED and a Retry-After header of roughly sixteen hours. Over the twenty hours that followed, the API served 1,891 rate-limit errors to real people and made fourteen actual calls to Spotify. Song search was simply down, and there was nothing behind it to fall back to.

It took three attempts to fix, spread over six days. The first two were both correct and both insufficient, and the reason they were insufficient is the most useful thing I learned all week. This post is the whole sequence: what I measured, what I built, what it did to the numbers, and what I had wrong at the start.

The number that explains all of it

The search box queries on every settled keystroke. That is what makes it feel like a search box rather than a form field, and it is also the entire problem. Typing bohemian rhapsody does not cost one search, it costs searches for bo, bohem, bohemian r and everything in between. Measured across the live query log over 4.2 days, that came to about 1,376 distinct query strings a day, with 506 distinct queries in the busiest single hour. Two thirds of those distinct queries were a strict prefix of another query in the same set: cho, chopp, choppe, chopped, chopped a, chopped an.

In the same period, the number of songs people actually submitted was between 55 and 144 a day, around 90 on average.

So the expensive endpoint was being asked roughly fifteen times more often than anybody picked a song, and almost every one of those extra questions was a half-typed word nobody meant to search for. A Spotify app in development mode gets a small, undocumented allowance, and 1,376 novel queries a day is nowhere near it. That gap is the whole story, and every attempt below is a different idea about how to close it.

Attempt one: cache it

The obvious move, and the first one I shipped. A Postgres table holding one row per source and normalised query, storing each response at the maximum result count so a smaller request is just a slice of it. A row under 24 hours old is served without calling out at all.

The part that mattered more than the freshness window: a row of any age is served when the live source fails. That is what turns a sixteen-hour ban from an outage into results that might be a day stale, which is a completely different experience for somebody trying to submit a song. The whole layer is best-effort, so any cache error falls straight through to the live API. A caching problem must never be the thing that takes song search down.

Two smaller holes went with it. The endpoint only set cache headers when no source had failed, so during a ban nothing cached at all, which is precisely backwards. And the 429 returned before any cache header was set, so the failure path was the one path guaranteed to be uncacheable.

The next day I measured it. In 24 hours the endpoint served 3,260 rate-limit errors and 1,604 successes. Two thirds of every API response the site produced was a 429, against a baseline of 1,891 over twenty hours during the original outage.

The cache was working exactly as designed. The design was not enough, and it could not have been. The box needs roughly 150 novel queries an hour, and a cache does nothing for a novel query by definition. A miss is the whole point of what a typeahead generates.

The thing I had wrong about the ban

Before the second attempt I went and measured the penalty itself, because the first attempt had been designed around an assumption I had never checked: that asking again during a ban extends it.

It does not. Two probes seventeen seconds apart returned Retry-After values of 39098 and 39081. Across three hours of production logs, 49323 at 03:14 and 39115 at 06:04: 10,200 seconds of wall clock, and the header fell by 10,208. The penalty counts down to one absolute expiry and nothing you do inside it moves that expiry.

Which means the thing re-arming the ban was much simpler and much dumber. The moment a window opened, the search box spent the entire allowance within minutes, because it searches on every settled keystroke and there was nothing anywhere limiting how fast that could happen. The fix was never going to be politeness at the moment of failure. It had to be a ceiling on the rate the allowance gets spent.

Attempt two: one backoff, shared by everything

The existing guard was a variable at module scope inside a serverless function, which means it was per warm instance. Every cold start began at zero and had to buy its own 429 to learn about a ban every other instance already knew about. The logs show three 429s inside a single second, at 04:58:34, :35 and :36: three instances each paying for the same lesson, and each one charging a player a failed search for it.

It also threw away the information the source was handing over. The hold was capped at an hour, so a thirteen-hour penalty got re-probed eleven times, and every one of those probes was a client-facing error plus a round trip of latency.

So the block moved into Postgres, next to the cache: one row per source, holding the expiry, a rolling window start and a call counter. A single function does both checks in one round trip under a row lock, because two instances asking at once must not both be told they were the last one under the ceiling. It answers one of three ways.

• ok: take a token, make exactly one live call.
• blocked, with the expiry attached, which the instance adopts into its own memory so it stops paying for the round trip for the rest of the ban.
• over budget, with the seconds remaining in the window.

The expiry only ever moves forward. Two instances racing into the same 429 report expiries a second or two apart, and taking the later one also means a stale retry from a frozen instance can never shorten a live ban. The whole thing is advisory in the same way the cache is: if the database is unreachable the answer is yes, and the in-memory hint is the only guard left. That is deliberate. It meant the code could ship before the migration was applied, and it means a database hiccup cannot be what takes search down.

The other half is a global ceiling on live calls per hour, in the same table. There was already a per-IP token bucket, but the constraint Spotify applies is per application, so a per-IP limit cannot see the thing that actually gets you banned. The ceiling is an environment variable specifically so it can be tuned against the 429 count without a deploy.

And ask less per person typing

Shipped alongside it. The local catalogue, which is a Postgres search over songs this game's own players have already submitted, kept its existing behaviour of two characters and a 220ms debounce. It costs nothing and it is what makes the box feel instant, so there was no reason to touch it.

The remote layer got its own, stricter gate: a five character minimum, a 450ms debounce, and a rule that it will not fire while the trailing word is under three characters. That last one is the interesting one. It means chopped a and chopped an never go out, and chopped and does.

Against the real sample of 2,420 queries, those three rules suppress 47.4% of them, and they suppress the least useful half. I tried a four character floor first: it only suppresses 36.3%, and the queries it buys back are load, nigh, supa, elep, numb, blac and toky. Mid-word, almost without exception. Nobody typing blac wanted results for blac.

There is also a prefix fallback now. If the exact cache key misses and the source is blocked, the box takes the longest cached prefix of whatever is typed and filters it in memory. It is a heuristic and it is sometimes slightly wrong, and a slightly wrong dropdown beats an empty one.

The bug that was making everything look worse than it was

While measuring the above I found something that had been quietly running since the cache shipped. SoundCloud search was never configured in production, and the function that searches it returned early with zero rows and no error. An unconfigured source was reporting success.

That reads as success everywhere downstream. It wrote an empty cache row, it counted as an answered source, and it earned the response an edge-cache header it had no business having. 5,799 SoundCloud cache rows, 100% of them empty, 73% of the entire table.

The worst part was third-order. With SoundCloud contributing zero rows and Spotify rate limited, the condition no results and at least one failure fired, and the whole request returned a 429 to the player. The true answer was that one source could not be searched at all and the other was capped, and the empty-success bug is what laundered that into a rate-limit error.

The fix is a single check: a source that cannot be searched leaves the fan-out before any call, so it neither calls, nor caches, nor counts as answered. And in SoundCloud's case that is permanent rather than a config change waiting to happen. Registering for their API now requires a paid Artist Pro subscription, and I am not buying a music subscription to power a search box. Pasting a SoundCloud link still works and always will, because that path is keyless and has nothing to do with any of this.

94% better, and still wrong

Three days later the numbers were genuinely good. Client-facing 429s fell from 3,260 in 24 hours to 207, a 94% cut. The backoff worked, the expiry was honoured in full, the counter ticked, and the three-in-one-second clusters were gone.

Then I looked at the hourly call counts and they read like this: 20, 20, 20, 20, 25, 19, 18, 15, 14, 8, 6. Five of the last 24 hours sitting flat on the ceiling.

A flat line at a limit is not demand being met. It is demand being cut off. The budget had stopped being a safety margin and had become the thing turning people away, and every one of those remaining 207 errors was somebody typing a song name and getting nothing back. 28% of every API response was still a failure.

That is when it became obvious that all three attempts were the same move wearing different clothes. Caching, backoff and debouncing all ration demand. None of them find supply. The demand is not unreasonable, it is just what a search box is, and no amount of rationing makes a music API sell more answers per day than it sells.

The fix that actually worked

Spotify is very good at two things this app genuinely needs: turning a pasted link into a track, and playing a track we already hold an id for. Neither of those is search. So the change was to stop asking Spotify what a half-typed word means, and keep it for the part it is actually the only option for.

Typing now queries Deezer. It is keyless, needs no signup and no environment variable, and the documented limit is 50 requests per 5 seconds with no daily cap at all. Our measured peak is 0.14 requests per second against an allowance of 10, which is 71 times more headroom than the busiest hour this game has ever had. It is also a burst bucket that refills every five seconds rather than a daily budget that refills once a day, which is a completely different failure mode: the worst case is a few seconds of degradation instead of sixteen hours of it.

The fact that made it cheap enough to be worth doing: Deezer returns the ISRC inline in the search response. An ISRC is the standard identifier for a specific recording. I had previously written this design off because I assumed pulling the ISRC would mean a second call per row, which would have been worse than what I already had. It is right there in the first response.

So Spotify is now called exactly once, at the moment somebody commits to a song, to trade that ISRC for a playable Spotify id. On a live sample of 29 real picks, 27 resolved, 93.1%, and they resolved to the right recording rather than an approximation: the original, the remix with the featured artist and the live cut all came back as three distinct correct tracks. That takes Spotify from roughly 1,376 search calls a day to roughly 90, one per submitted song.

And most of those get cheaper over time, because an ISRC identifies a recording and never changes. A resolution is cached permanently, so the second person ever to pick that song costs nothing at all. A recorded absence is cached too, but only believed for a week, since a song genuinely can arrive on a platform later.

Quality was the part that decided it

Headroom is easy to find if you do not care about results. I ran six queries against both Deezer and the iTunes search API in the same second and compared the top four rows of each.

Deezer took bohemain rapsody, two typos in one word, and returned Bohemian Rhapsody with every row being Queen. iTunes found it too but mixed in covers. On the weeknd blinding, Deezer gave the original first and then the remix and the live version; iTunes led with the remix. On chopped an, which is exactly the kind of mid-word fragment a debounced box produces on the way to a real query, Deezer had the right track first and iTunes had something unrelated.

It was also two to four times faster: 80 to 190ms against 260 to 360ms. Typo tolerance and mid-word prefixes are the actual workload of a box that searches while you type, so that comparison was not close. iTunes stays written up as the fallback, because roughly 20 calls a minute is 2.4 times our peak where Deezer gives 71 times, and on a shared serverless egress IP a 2.4x margin is not a margin.

One rule keeps this from leaking everywhere

Deezer is a search middleman, never a music source. Nothing is ever stored, linked or played as a Deezer track. It belongs to the set of things the server knows how to query, and deliberately not to the set of things the game can play, and those are now two different sets on purpose.

That one sentence is why this did not turn into a refactor. Nothing downstream gained a branch, because nothing downstream ever sees a Deezer row. The resolve hands back the full Spotify track, so a song picked from the dropdown is indistinguishable from one pasted as a link, which matters because playback keys on the source and its id while the song stats key on artist and title. A mismatch there would be a silent data bug rather than a visible one.

It also settled a small interface question. A row in the dropdown is badged with where it is going, not where it came from, because the question a badge answers is what will this play on, and Deezer is not an answer to that in a game that cannot play Deezer.

One trap worth writing down, since it is the SoundCloud bug wearing a new coat: Deezer answers a spent burst quota with HTTP 200 and an error object in the body. Checking the status code alone would cache a rate limit as an empty result set, permanently, for that query. Refusals are read out of the body, and a refusal writes a backoff row through the same shared function Spotify uses, with a ten second window rather than hours, because a five second burst bucket and a thirteen hour penalty deserve very different patience.

A footnote about YouTube, which changed under me

YouTube search has always run on a magnifier press rather than on typing, because it was the expensive one. The comment in the code explaining why said a search costs 100 quota units out of a 10,000 per day pool.

That stopped being true on 1 June 2026. Google split the quota into independent buckets, and a search is now 1 unit in a bucket that allows 100 calls a day, full stop. The practical ceiling is the same number, because the old arithmetic happened to produce it, but the shape is different and two things follow. The budget is a call count now, so nothing about how a query is phrased and no smaller result count makes a call cheaper. And a lookup by id lives in a separate bucket entirely and is effectively free, which is the only YouTube lever left.

Since no phrasing can make a call cheaper, the only multiplier remaining is cache time, so YouTube results are now cached for seven days while everything else stays at 24 hours. One line, worth roughly seven times the coverage. The cost is that a video uploaded this week can be up to a week late into the box, which is an easy trade for a source that exists as a deliberate second look rather than as the typeahead.

What it cost and what is still open

• Title drift. The row you click shows Deezer's title and the row that gets submitted shows Spotify's. The ISRC guarantees it is the same recording, so the difference is cosmetic, something like Blinding Lights against Blinding Lights - Live. Writing it down here so it does not get filed as a bug later.
• The 7% that does not resolve. Bootlegs and regional masters that Spotify genuinely does not carry. Those are real absences rather than lookup failures, so the honest answer is to say so and offer the paste box. On a failed resolve the dropdown deliberately stays open, because the next row down is usually the recovery.
• No second typeahead source yet. Deezer is the only one, and if it goes down the local catalogue of previously submitted songs is the floor. That floor is real and instant, but it is a floor. iTunes is specified and not built.
• A shared egress IP. Deezer's limit is per IP and serverless functions leave from a shared, rotating pool, so our calls spread across several addresses and those addresses are shared with strangers. At 0.14 against 10 requests per second there is room for that to be true and still not matter, and it is exactly why Deezer got its own backoff row on day one rather than eventually.

The swap to Deezer for every real search surface went live last night, so the number I actually care about, client-facing rate-limit errors across a full day, is still being counted. The target is near zero, from 207. What I can already say is that the hourly Spotify ceiling has stopped binding, because the thing that used to spend it 1,376 times a day now spends it about 90 times.

What I would take from this

The first two attempts were both good engineering and both the wrong shape. Caching, shared backoff and debouncing are all versions of make the demand smaller, and they got a 94% cut between them, which sounds like success right up until you notice that the remaining 6% is a flat line against a ceiling. Rationing has a floor, and the floor was still failure.

What actually worked was noticing that the endpoint I was banned from was not the endpoint I needed. What I need Spotify for is a playable id for a song somebody has chosen, which happens about 90 times a day. What I was spending it on was guessing what a half-typed word meant, 1,376 times a day. Those are two different jobs, and only one of them was ever expensive. Once they were separated, the quota problem stopped being a quota problem.

And the smaller lesson, which cost me the most time: measure the failure before designing around it. I spent an entire attempt believing that retrying during a ban extended the ban. It never did. One unchecked assumption about somebody else's rate limiter shaped a week of work.