A Million Questions a Second

That's where I come in

Every time someone opens a product page on Amazon.com, an ad server has a tight time budget to fill its ad slots, and the page doesn't wait. The candidates come from every demand-side platform buying ads on Amazon's own sites. For each one, the ad server needs to know: does this creative belong next to this product?

Someone has to answer that question over a million times a second. That's where I come in. Well, that's where our team came in: no one builds at this scale alone, and I ran with a pack. The Ad Relevance API launched for Amazon Retail at over a million requests per second, which adds up to billions a day (more on Prime Day), and it was projected to add $10 million a year in ad revenue for Amazon DSP.

Ad tech in thirty seconds

Advertisers buy ads through demand-side platforms (DSPs); publishers sell space on their pages on the supply side. Amazon's own guide puts it neatly: "DSPs are the shoppers at the auction, and SSPs are the sellers." Amazon is both:

• Demand: Amazon DSP buys across Amazon's own properties (Amazon.com, Prime Video, Twitch, Fire TV, Thursday Night Football) and thousands of third-party sites and apps, and self-serve products like Sponsored Display bring more advertisers.
• Supply, for other publishers: Amazon Publisher Services runs server-side header bidding, through the Transparent Ad Marketplace and the Unified Ad Marketplace.
• Supply, for Amazon itself: Amazon Ads' Publisher Technology organization (PubTech, where I worked) builds supply-side technology for Amazon's own properties, as reported publicly in 2023.

We sat on that supply side. Every demand source buying on Amazon's own sites went through Amazon's ad server, and the ad server asked us which of its candidate ads were relevant to the page. Our answers decided which ads were marked relevant on Amazon.com and Amazon's first-party sites.

If you've watched The Brew Miles, think of it as a beer-pairing chart. The ad server brings the dish (the product on the page) and a tray of beers (the candidate creatives), and we say which ones go with it. A million pairings a second, no tasting allowed.

Today I keep a map of more than twelve billion Azure resources fast, reliable and correct. The bar I hold that work to is the frame for everything below: fast (the auction won't wait), reliable (at this volume, "rare" happens every second), and correct (a wrong "relevant" is an ad nobody wanted).

Amazon's internal frameworks are swapped for public equivalents, the numbers about this API are the ones already on my résumé, numbers about Amazon's wider ad stack are linked to Amazon's and AWS's public write-ups, and anything labelled toy or illustrative shows the shape of an idea, not a production measurement. Production was Java on AWS; the code here is Python because it reads like pseudocode that actually runs, and every output shown came from running it.

Do the math before the code

Two numbers decide most of the design: the gap between average and peak, and how many requests are in flight at once.

SECONDS_PER_DAY = 24 * 60 * 60

def average_rps(requests_per_day):
    return requests_per_day / SECONDS_PER_DAY

def in_flight(rps, latency_s):
    """Little's law: requests inside the system at any instant
    = arrival rate x how long each one stays."""
    return rps * latency_s

def gbit_per_s(rps, bytes_per_request):
    return rps * bytes_per_request * 8 / 1e9

print(f"1 billion a day   = {average_rps(1e9):>14,.0f} req/s")
print(f"1 million a sec   = {1e6 * SECONDS_PER_DAY:>14,.0f} req/day")
print(f"in flight at 1M/s, 5 ms each = {in_flight(1e6, 0.005):,.0f}")
print(f"on the wire at 1M/s, 2 KB each = "
      f"{gbit_per_s(1e6, 2_000):.0f} Gbit/s")

1 billion a day   =         11,574 req/s
1 million a sec   = 86,400,000,000 req/day
in flight at 1M/s, 5 ms each = 5,000
on the wire at 1M/s, 2 KB each = 16 Gbit/s

A billion a day sounds enormous and is only about 11,600 a second on average. A million a second, held for a day, would be 86 billion. Traffic is never flat, so you size for the peak and the average tells you very little.

The third line is Little's law: in flight = arrival rate × time each request takes. At a million a second, every extra millisecond is another thousand requests holding threads, sockets and memory. Latency isn't a nicety at this scale. It's capacity, and as section 10 shows, it's also garbage.

For a sense of the neighbourhood: AWS's preview of the 2021 re:Invent session "Under the Hood at Amazon Ads" describes an ad server handling "hundreds of millions of ad requests per second (trillions of ads per day) within a latency budget of 120 ms", aiming for more than 99.9999% availability, and scoring "thousands of ads per request within a 20 ms window". Every service an ad server calls gets a slice of a budget like that, never the whole thing. A classic AWS worked example for real-time bidding makes it concrete: 100 ms end to end, minus 40 ms of network round trip and a 20 ms jitter buffer, leaves 40 ms to decide, so each data fetch gets "single-digit milliseconds".

The last line is bytes. Even an illustrative 2 KB per request and response is 16 gigabits a second on the wire. That's why requests carried IDs (an ASIN and a few creative IDs), never the data behind them.

Relevance is a relationship problem

These days I'm in the business of saving relationships between Azure resources. Back then, it was between ASINs and creatives. An ASIN (Amazon Standard Identification Number) is a product: the trail shoe on the page you're looking at. A creative is an actual ad a DSP wants to show, and each one advertises one or more ASINs. Three datasets tied them together:

• Creative → ASIN mapping: which products each creative advertises.
• ASIN-to-ASIN similarity: how related two products are (a trail shoe and a running watch: very; a trail shoe and cat litter: not at all).
• Creative-to-creative similarity: how alike two ads are.

Describe each thing as numbers and "related" becomes geometry. Vectors that point the same way score high on cosine similarity; sets of tags score high on Jaccard (shared over total). These are the building blocks; our real features and strategies stay internal.

import math

def cosine(a, b):
    """1.0 = pointing the same way."""
    dot = sum(x * y for x, y in zip(a, b))
    return dot / (math.hypot(*a) * math.hypot(*b))

def jaccard(a, b):
    """Share of tags two sets have in common."""
    return len(a & b) / len(a | b) if a | b else 0.0

# Made-up IDs. Products (ASINs) as vectors...
asin_vec = {"B0TRAILSHOE": [0.9, 0.1, 0.4],
            "B0RUNWATCH": [0.8, 0.2, 0.5],
            "B0CATLITTER": [0.0, 0.9, 0.1]}
# ...creatives (ads from DSPs) mapped to the ASINs they advertise...
creative_asins = {"cr-17": ["B0RUNWATCH"], "cr-42": ["B0CATLITTER"],
                  "cr-18": []}  # a new creative, no product yet
creative_tags = {"cr-17": {"running", "gps", "outdoor"},
                 "cr-18": {"running", "gps", "outdoor", "trail"},
                 "cr-42": {"pets", "home"}}

def asin_to_asin(a, b):
    return cosine(asin_vec[a], asin_vec[b])

def creative_to_creative(c1, c2):
    return jaccard(creative_tags[c1], creative_tags[c2])

if __name__ == "__main__":
    print(f"ASIN-ASIN   trail shoe ~ run watch   "
          f"{asin_to_asin('B0TRAILSHOE', 'B0RUNWATCH'):.2f}")
    print(f"ASIN-ASIN   trail shoe ~ cat litter  "
          f"{asin_to_asin('B0TRAILSHOE', 'B0CATLITTER'):.2f}")
    print(f"creative-creative   cr-18 ~ cr-17    "
          f"{creative_to_creative('cr-18', 'cr-17'):.2f}")

ASIN-ASIN   trail shoe ~ run watch   0.98
ASIN-ASIN   trail shoe ~ cat litter  0.15
creative-creative   cr-18 ~ cr-17    0.75

Relevance isn't a nice-to-have at Amazon. In its public response to the FTC about Sponsored Ads, Amazon says it began testing machine-learning relevance models in 2014 and had them across all its store advertising by 2019. It cuts the "hundreds of thousands of ads" that could compete for one search to "less than a thousand candidates by removing less relevant ads", and ranks what's left on "a combination of which ad is most relevant to the customer and the price an advertiser is willing to pay". In 2024, "approximately 92% of selected Sponsored Products ads were not the highest bid". That's Sponsored Products on search, not our API, but it's the same principle: relevance decides who gets to compete.

Precompute, and let the request carry its own address

Here's the move the whole system rests on. The ad server already knew its candidates: the creatives the DSPs had put forward for this slot. So instead of asking us "what's relevant to this ASIN?", which is a search across every creative, it sent the page's ASIN along with its candidate creatives. That turned a search into a handful of point lookups, one per (ASIN, creative) pair.

Point lookups only work if the answers already exist. That's the batch's job: score every pair worth scoring, once a day, and keep the relevant ones. A creative's relevance to a page comes through the ASINs it advertises. Creative-to-creative similarity helps where a creative's own products don't tell the whole story; in this toy version, a brand-new creative borrows from a lookalike:

import similarity as sim  # the code above

def precompute(page_asins, creatives, threshold=0.5):
    """The daily batch: score every (page ASIN, creative) pair once
    and keep the ones worth keeping. Requests only read this."""
    table = {}
    for page in page_asins:
        for cr in creatives:
            products = sim.creative_asins[cr]
            if products:   # via the ASINs the creative advertises
                score = max(sim.asin_to_asin(page, a) for a in products)
            else:          # no product yet: borrow from lookalikes
                score = max((sim.creative_to_creative(cr, other) *
                             table.get(f"{page}|{other}", 0)
                             for other in creatives if other != cr),
                            default=0)
            if score >= threshold:
                table[f"{page}|{cr}"] = round(score, 2)
    return table

table = precompute(["B0TRAILSHOE"], ["cr-17", "cr-42", "cr-18"])
print(table)

# A request carries the page ASIN AND its candidate creatives,
# so answering is one dictionary lookup per creative:
request = {"asin": "B0TRAILSHOE", "creatives": ["cr-17", "cr-42"]}
print({cr: table.get(f"{request['asin']}|{cr}", "not relevant")
       for cr in request["creatives"]})

{'B0TRAILSHOE|cr-17': 0.98, 'B0TRAILSHOE|cr-18': 0.73}
{'cr-17': 0.98, 'cr-42': 'not relevant'}

Everything expensive (similarities, joins, thresholds) happened before the request arrived. The request itself became a dictionary lookup with an address on it. That's what made a million a second possible, and everything after this section is about making that lookup cheaper still.

Why not compute on the fly? Because the math is cheap, the data is not. A cosine over a few hundred numbers takes well under a microsecond. Fetching two vectors from a database across a network takes thousands of times longer.

The shape of the system

Two loops run at very different speeds. Once a day, a pipeline turns upstream datasets into precomputed answers and publishes them everywhere they're needed. On every request, each layer tries to answer before the next, more expensive one has to.

A key-value store is the natural home for "look up this exact pair". It's also proven at Amazon Ads' scale: the DynamoDB customer page says Amazon Ads' measurement team moved from hundreds of HBase instances to DynamoDB global tables, reaching up to 99.999% availability, with peaks "during events like Thursday Night Football and Prime Day reaching 90 million reads and 5 million writes per second".

One request, four possible journeys

Follow a single request. Every stop is cheaper than the next, and every stop exists to keep requests away from the next one. Pick a journey:

On our host, the whole hot path is a few lines:

def score_creatives(asin, creatives, bloom, cache, db):
    """One request: the page's ASIN plus the ad server's candidate
    creatives. Each answer is a lookup, because it was precomputed."""
    return {cr: relevance(f"{asin}|{cr}", bloom, cache, db)
            for cr in creatives}

def relevance(key, bloom, cache, db):
    if not bloom.might_contain(key):
        return NOT_RELEVANT           # 1. definitely absent: no I/O
    score = cache.get(key)            # 2. hot key: memory only
    if score is None:
        score = db.get(key)           # 3. one key-value read
        score = NOT_RELEVANT if score is None else score
        cache.put(key, score)
    return score

One detail worth copying: a Bloom-filter false positive comes back from the database empty, and that empty answer is cached too (negative caching), so the same false positive never costs a second read.

To see what each layer is worth, a toy world: 2,000 page ASINs × 100 creatives = 200,000 possible pairs, only 50,000 of them precomputed as relevant, with skewed popularity, and 60,000 requests carrying five creatives each:

database only    300,000 database reads
+ Bloom filter    72,154 database reads
+ host cache      20,565 database reads
(60,000 requests x 5 creatives = 300,000 lookups)

import random
from bloom import BloomFilter
from cache import LRUCache

NOT_RELEVANT = 0.0

class CountingDB:
    """Stands in for the key-value database; counts every read."""
    def __init__(self, rows):
        self.rows, self.reads = rows, 0
    def get(self, key):
        self.reads += 1
        return self.rows.get(key)

def score_creatives(asin, creatives, bloom, cache, db):
    """One request: the page's ASIN plus the ad server's candidate
    creatives. Each answer is a lookup, because it was precomputed."""
    return {cr: relevance(f"{asin}|{cr}", bloom, cache, db)
            for cr in creatives}

def relevance(key, bloom, cache, db):
    if not bloom.might_contain(key):
        return NOT_RELEVANT           # 1. definitely absent: no I/O
    score = cache.get(key)            # 2. hot key: memory only
    if score is None:
        score = db.get(key)           # 3. one key-value read
        score = NOT_RELEVANT if score is None else score
        cache.put(key, score)
    return score

class AlwaysMaybe:                    # "no filter": every key might exist
    def might_contain(self, key): return True

class NoCache:
    def get(self, key): return None
    def put(self, key, value): pass

# Toy world: 2,000 page ASINs x 100 creatives = 200k possible pairs,
# 50k of them precomputed as relevant. Popularity is skewed.
rng = random.Random(42)
asins = [f"B0{i:08d}" for i in range(2_000)]
creatives = [f"cr-{i}" for i in range(100)]
pairs = [f"{a}|{c}" for a in asins for c in creatives]
rows = {k: round(rng.random(), 3) for k in rng.sample(pairs, 50_000)}
hot = lambda items: rng.sample(items, len(items))  # random popularity
asin_w = [1 / r for r in range(1, len(asins) + 1)]
cr_w = [1 / r for r in range(1, len(creatives) + 1)]
by_asin, by_cr = hot(asins), hot(creatives)
requests = [(rng.choices(by_asin, asin_w)[0],
             rng.choices(by_cr, cr_w, k=5)) for _ in range(60_000)]

bloom = BloomFilter(len(rows), 0.01)
for k in rows:
    bloom.add(k)

for name, use_bloom, use_cache in [("database only", False, False),
                                   ("+ Bloom filter", True, False),
                                   ("+ host cache", True, True)]:
    db = CountingDB(rows)
    cache = LRUCache(5_000) if use_cache else NoCache()
    for asin, crs in requests:
        score_creatives(asin, crs,
                        bloom if use_bloom else AlwaysMaybe(), cache, db)
    print(f"{name:<15} {db.reads:>8,} database reads")
print("(60,000 requests x 5 creatives = 300,000 lookups)")

A bouncer with a guest list: Bloom filters

The precomputed table only holds the (ASIN, creative) pairs worth keeping. Ask about any other pair and the honest answer is "not relevant", but the naive way to learn that is a database read that comes back empty. At a million a second, empty reads add up to a whole database fleet spent learning nothing.

A Bloom filter is a bouncer with a very compressed guest list: a bit array and k hash functions.

• To add a key, hash it k ways and set those k bits to 1.
• To check a key, hash it the same k ways. If any bit is 0, the key was never added. That's certain: adding it would have set that bit.
• If all are 1, the key was probably added, or other keys happened to set the same bits. That "probably" is the false-positive rate, and you pick it.

The trade is lopsided in our favour. A false positive costs one wasted database read, the same as having no filter. A false negative would wrongly drop a relevant ad, and a Bloom filter can't produce one. Try it:

A real one fits in about twenty lines. It derives all k positions from two hashes of one BLAKE2 digest (the Kirsch–Mitzenmacher trick), with essentially the same false-positive rate as k independent hashes. In Java you don't write your own; Guava ships a solid BloomFilter.

import hashlib
import math

class BloomFilter:
    """A set that can say 'definitely not here' with certainty."""

    def __init__(self, expected_items, false_positive_rate):
        n, p = expected_items, false_positive_rate
        self.m = math.ceil(-n * math.log(p) / math.log(2) ** 2)  # bits
        self.k = max(1, round(self.m / n * math.log(2)))  # hash count
        self.bits = bytearray((self.m + 7) // 8)

    def _positions(self, key):
        d = hashlib.blake2b(key.encode(), digest_size=16).digest()
        h1 = int.from_bytes(d[:8], "little")
        h2 = int.from_bytes(d[8:], "little") | 1
        # k positions from two hashes (Kirsch-Mitzenmacher)
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, key):
        for p in self._positions(key):
            self.bits[p >> 3] |= 1 << (p & 7)

    def might_contain(self, key):
        return all(self.bits[p >> 3] >> (p & 7) & 1
                   for p in self._positions(key))

from bloom import BloomFilter

bf = BloomFilter(expected_items=100_000, false_positive_rate=0.01)
for i in range(100_000):
    bf.add(f"ad:{i}")

# Every key we added is found: no false negatives, ever.
assert all(bf.might_contain(f"ad:{i}") for i in range(100_000))

# Keys we never added: about 1% sneak through as "maybe".
fp = sum(bf.might_contain(f"other:{i}") for i in range(100_000))
print(f"{bf.m:,} bits = {bf.m / 8 / 1024:,.0f} KiB, k = {bf.k}")
print(f"false positives: {fp:,} of 100,000 = {fp / 1000:.2f}%")

958,506 bits = 117 KiB, k = 7
false positives: 1,011 of 100,000 = 1.01%

The measured rate lands right on the 1% we asked for, and every key we added is found.

How big does it need to be?

 keys  false+  bits/key      MiB   k
  10M  0.01         9.6       11   7
  10M  0.001       14.4       17  10
 100M  0.01         9.6      114   7
 100M  0.001       14.4      171  10
   1B  0.01         9.6    1,143   7
   1B  0.001       14.4    1,714  10

exact set of 8-byte keys, 100M: 763 MiB

import math

def bloom_size(n, p):
    bits = -n * math.log(p) / math.log(2) ** 2
    return bits / n, bits / 8 / 2**20, round(bits / n * math.log(2))

print(" keys  false+  bits/key      MiB   k")
for label, n in (("10M", 10**7), ("100M", 10**8), ("1B", 10**9)):
    for p in (0.01, 0.001):
        per_key, mib, k = bloom_size(n, p)
        print(f"{label:>5}  {p:<6}  {per_key:>8.1f} {mib:>8,.0f}  {k:>2}")

# An exact set of 64-bit fingerprints needs 64 bits/key, at best.
print(f"\nexact set of 8-byte keys, 100M: {10**8 * 8 / 2**20:,.0f} MiB")

About 9.6 bits per key buys a 1% false-positive rate, however long the key is, and each extra 4.8 bits cuts the rate tenfold. A hundred million keys fit in about 114 MiB, small enough for every host. An exact set would need 763 MiB even if every key were squeezed into an 8-byte hash. (Worked examples, not our dataset's size.)

The catch is versions. "No false negatives" only holds for the keys the filter was built from. If the database gets tomorrow's keys while a host still has yesterday's filter, the filter says "definitely not" about pairs that now exist. So the filter and its data are built and published together, as one version (section 08).

Caches on both sides of the wire

The fastest request is the one that never leaves the ad server. So the ad servers kept their own copy of the data, refreshed with every daily version. For most requests the comparison happened right there, with no vectors to fetch and no call to us. On our side, every host kept the hottest keys in memory, in a least-recently-used (LRU) cache. In Java you'd reach for a library like Caffeine, whose W-TinyLFU policy also weighs how often a key is used, not just how recently; plain LRU fits in a few lines:

from collections import OrderedDict

class LRUCache:
    """Keeps the most recently used keys; evicts the oldest."""

    def __init__(self, capacity):
        self.capacity, self.data = capacity, OrderedDict()

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)  # now the most recent
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)  # drop least recent

A small cache works because popularity is skewed: a few products and creatives get most of the traffic. If popularity follows a Zipf curve (a common shape, used here as an illustration), caching just 1% of keys catches about two-thirds of requests. And layers multiply:

behind a 90% client cache:    100,000 req/s
behind 90% then 80% caches:    20,000 req/s

cache the hottest  0.1% of keys -> 52% hits
cache the hottest    1% of keys -> 68% hits
cache the hottest    5% of keys -> 79% hits
cache the hottest   10% of keys -> 84% hits

def load_behind(rps, *hit_rates):
    """Requests per second that get past every cache layer."""
    for h in hit_rates:
        rps *= 1 - h
    return rps

def zipf_hit_rate(n_keys, cached, s=1.0):
    """Hit rate of a cache holding the `cached` hottest of n keys,
    when popularity follows a Zipf curve (rank r gets 1/r^s)."""
    weights = [1 / rank**s for rank in range(1, n_keys + 1)]
    return sum(weights[:cached]) / sum(weights)

print(f"behind a 90% client cache:  "
      f"{load_behind(1_000_000, 0.90):>9,.0f} req/s")
print(f"behind 90% then 80% caches: "
      f"{load_behind(1_000_000, 0.90, 0.80):>9,.0f} req/s\n")

for pct in (0.1, 1, 5, 10):
    hit = zipf_hit_rate(1_000_000, int(1_000_000 * pct / 100))
    print(f"cache the hottest {pct:>4}% of keys -> {hit:.0%} hits")

You'll find the same layering in Amazon's public write-ups. An AWS case study on Amazon Ads keeps "the most popular products … in a local cache and the less popular products in a remote cache", because hundreds of millions of embedding lookups a second would otherwise eat "several terabits per second of bandwidth". And the Sponsored Products retrieval team reports "p99 latencies under 5ms with 99.99% availability—even during traffic surges like Prime Day", at "tens of millions of read requests per second across terabytes of data" on ElastiCache.

With an illustrative 90% hit rate on the ad server and 80% on our hosts, a million requests a second at the edge becomes twenty thousand at the database. That's the difference between a database you can run and one you can't.

Stampedes. When a hot key misses (it expired, or a host just started), hundreds of concurrent requests miss together and stampede the database. The fix is single-flight: the first request fetches, the rest wait for its answer.

100 concurrent misses -> 1 backend call

import threading
import time

class SingleFlight:
    """Concurrent misses for the same key share ONE backend call."""

    def __init__(self):
        self.lock = threading.Lock()
        self.calls = {}  # key -> {"done": Event, "value"/"error"}

    def do(self, key, fetch):
        with self.lock:
            call = self.calls.get(key)
            leader = call is None
            if leader:
                call = self.calls[key] = {"done": threading.Event()}
        if leader:
            try:
                call["value"] = fetch()
            except Exception as err:
                call["error"] = err
            finally:
                with self.lock:
                    del self.calls[key]
                call["done"].set()
        else:
            call["done"].wait()
        if "error" in call:
            raise call["error"]
        return call["value"]

backend_calls = 0
def slow_fetch():
    global backend_calls
    backend_calls += 1
    time.sleep(0.05)  # a database read
    return 0.83

flight = SingleFlight()
threads = [threading.Thread(target=flight.do,
                            args=("ad7|pg3", slow_fetch))
           for _ in range(100)]
for t in threads: t.start()
for t in threads: t.join()
print(f"100 concurrent misses -> {backend_calls} backend call")

Staleness. Cache invalidation is famously hard, until data changes on a schedule. Put the dataset version in the cache key (or clear on version change) so yesterday's answers can't outlive yesterday, and add a little jitter to expiry times so a whole fleet doesn't refresh in the same second.

Rebuild everything, every day

Every day the pipeline rebuilt the whole dataset from scratch. It pulled the latest creatives from the DSPs (Amazon DSP, Sponsored Display and others), the creative-to-ASIN mappings and the product catalog; computed ASIN-to-ASIN and creative-to-creative similarities; joined them into (ASIN, creative) scores; validated the result; and published one new version to the database, to our hosts (scores, Bloom filter, snapshot) and to the ad servers' copies. That daily backfill is what kept both sides of the wire in agreement.

@dataclass(frozen=True)
class Snapshot:
    version: str        # the day it was built, e.g. "2026-10-30"
    scores: dict        # "ASIN|creative" -> relevance
    bloom: BloomFilter  # built from exactly these keys

class RelevanceData:
    """Readers always see ONE whole version; publishing swaps a
    single reference, so no request ever mixes two days of data."""
    def __init__(self, snapshot):
        self.current = snapshot
    def publish(self, new):
        if new.version <= self.current.version:
            raise ValueError("never go backwards")
        self.current = new

def validate(new, old, max_drift=0.2):
    """Refuse to publish a dataset that looks broken."""
    if not new.scores:
        raise ValueError("empty dataset")
    drift = abs(len(new.scores) - len(old.scores)) / len(old.scores)
    if drift > max_drift:
        raise ValueError(f"row count moved {drift:.0%}")

A toy run: on day one the catalog publishes a wrong vector for B0LITTER (it looks like a shoe, so it gets paired with the shoe creative). The correction lands the next day, and the rebuild pairs it with the right creative with no special handling. Then an empty dataset tries to publish and is stopped at the gate:

2026-10-31 ['B0LITTER|cr-2', 'B0SHOE|cr-1', 'B0WATCH|cr-1']
blocked: empty dataset

from dataclasses import dataclass
from bloom import BloomFilter

@dataclass(frozen=True)
class Snapshot:
    version: str        # the day it was built, e.g. "2026-10-30"
    scores: dict        # "ASIN|creative" -> relevance
    bloom: BloomFilter  # built from exactly these keys

class RelevanceData:
    """Readers always see ONE whole version; publishing swaps a
    single reference, so no request ever mixes two days of data."""
    def __init__(self, snapshot):
        self.current = snapshot
    def publish(self, new):
        if new.version <= self.current.version:
            raise ValueError("never go backwards")
        self.current = new

def validate(new, old, max_drift=0.2):
    """Refuse to publish a dataset that looks broken."""
    if not new.scores:
        raise ValueError("empty dataset")
    drift = abs(len(new.scores) - len(old.scores)) / len(old.scores)
    if drift > max_drift:
        raise ValueError(f"row count moved {drift:.0%}")

def build(day, sources, similarity, threshold=0.5):
    """Daily backfill: recompute everything from today's inputs,
    so late or corrected upstream data heals by tomorrow."""
    asins, creatives = {}, {}
    for source in sources:          # DSP creative feeds, the catalog
        for kind, item_id, vec in source(day):
            (asins if kind == "asin" else creatives)[item_id] = vec
    scores = {}
    for a, va in asins.items():
        for c, vc in creatives.items():
            if (s := similarity(va, vc)) >= threshold:
                scores[f"{a}|{c}"] = round(s, 3)
    bloom = BloomFilter(max(len(scores), 1), 0.01)
    for key in scores:
        bloom.add(key)
    return Snapshot(day, scores, bloom)

# Toy sources and similarity, so the sketch runs end to end.
def dot(a, b): return sum(x * y for x, y in zip(a, b))
def dsp_creatives(day):              # e.g. Amazon DSP, Sponsored Display
    return [("creative", "cr-1", (1, 0)), ("creative", "cr-2", (0, 1))]
def catalog(day):
    fixed = day >= "2026-10-31"          # a correction lands late
    return [("asin", "B0SHOE", (1, 0)), ("asin", "B0WATCH", (0.9, 0.4)),
            ("asin", "B0LITTER", (0, 1) if fixed else (1, 0))]

live = RelevanceData(build("2026-10-30", [dsp_creatives, catalog], dot))
new = build("2026-10-31", [dsp_creatives, catalog], dot)
validate(new, live.current)
live.publish(new)
print(live.current.version, sorted(live.current.scores))
try:
    validate(Snapshot("2026-11-01", {}, new.bloom), live.current)
except ValueError as err:
    print("blocked:", err)

"Swap a single reference" is the important part. In Java it's an AtomicReference or a volatile field: each request grabs the current snapshot once and uses it to the end, so no request ever sees half of Monday and half of Tuesday.

The all-pairs trap

Scoring in bulk is a matrix multiply: normalize the vectors, and one product gives every cosine.

import time
import numpy as np

rng = np.random.default_rng(0)
creatives = rng.standard_normal((50_000, 64), dtype=np.float32)
asins = rng.standard_normal((2_000, 64), dtype=np.float32)

def unit(m):
    return m / np.linalg.norm(m, axis=1, keepdims=True)

t = time.perf_counter()
scores = unit(asins) @ unit(creatives).T   # every cosine, one matmul
top10 = np.argpartition(-scores, 10, axis=1)[:, :10]
ms = (time.perf_counter() - t) * 1000
print(f"{scores.size:,} cosines + top 10 per ASIN: {ms:,.0f} ms")

# The all-pairs trap: work grows with ASINs x creatives.
def words(n):
    if n >= 1e12:
        return f"{n / 1e12:,.0f} trillion"
    return f"{n / 1e9:,.0f} billion"

for n_asins, n_creatives in [(10**6, 10**5), (10**8, 10**6)]:
    print(f"{n_asins:>13,} ASINs x {n_creatives:>9,} creatives "
          f"= {words(n_asins * n_creatives)} pairs")

100,000,000 cosines + top 10 per ASIN: 4,430 ms
    1,000,000 ASINs x   100,000 creatives = 100 billion pairs
  100,000,000 ASINs x 1,000,000 creatives = 100 trillion pairs

A hundred million cosines take seconds on one machine. The trap is the shape: the work grows with ASINs × creatives, and at catalogue scale that's trillions of pairs. Big pipelines first narrow each ASIN to candidate creatives (through the creative-to-ASIN mapping, by category, or with approximate-nearest-neighbour indexes such as FAISS or HNSW) and store only the pairs worth storing. That's exactly why "not in the dataset" is such a common answer, and why the Bloom filter earns its place.

Scaling on hosts

The API ran on a fleet of identical Java hosts on EC2, in an Auto Scaling group behind a load balancer. Any host can answer any request, but each carries read-only data in memory: the Bloom filter and the hot keys. Capacity is linear: add a host and you add its share of throughput; lose one and you lose only its share.

A scaling policy grows and shrinks the fleet, usually by tracking CPU or requests per host. Reactive scaling has one weakness: it acts on what it sees now, and a new host isn't useful the moment it launches. It has to boot, deploy, load its data and warm up its JIT. Against a sudden step in traffic, that lag is where requests get lost. An illustrative simulation:

reactive only           11.2% of requests not served in time
pre-scaled at minute 5  0.0% of requests not served in time

import math

def simulate(traffic, per_host, warmup, target=0.6, prescale=None):
    """Minute by minute: demand vs capacity under a reactive policy.
    New hosts only take traffic `warmup` minutes after the decision
    (boot, deploy, load the data, warm up the JVM)."""
    hosts = math.ceil(traffic[0] / (per_host * target))
    pending, unserved, log = [], 0, []
    for minute, rps in enumerate(traffic):
        if prescale and minute == prescale[0]:
            pending.append((minute + warmup, prescale[1] - hosts))
        hosts += sum(n for ready, n in pending if ready == minute)
        pending = [(r, n) for r, n in pending if r > minute]
        capacity = hosts * per_host
        unserved += max(0, rps - capacity) * 60
        want = math.ceil(rps / (per_host * target))
        coming = hosts + sum(n for _, n in pending)
        if want > coming:  # reactive: scale on what we see now
            pending.append((minute + warmup, want - coming))
        log.append(capacity)
    return unserved / (sum(traffic) * 60), log

# Illustrative: 300k req/s, then a sudden 3x step at minute 20.
traffic = [300_000] * 20 + [900_000] * 25
for name, pre in [("reactive only", None),
                  ("pre-scaled at minute 5", (5, 150))]:
    lost, log = simulate(traffic, per_host=10_000, warmup=8,
                         prescale=pre)
    print(f"{name:<23} {lost:.1%} of requests not served in time")

Testing a million a second is its own scaling problem. One laptop can't generate that load, so the load generators need a fleet of their own, and you have to check you're measuring the service, not the test harness. Load tests are also where you find out which ceiling comes first. It's rarely the CPU; it's usually the database or the network, which is why this design keeps both off the hot path.

Scaling policies aren't just a cost knob. The 10% request drop I root-caused at Amazon Ads came down to how the infrastructure was scaling, and the fix was better scaling policies and better alarms: if a dashboard can't show the problem, the next on-call can't see it either.

When the garbage collector stopped the world

The garbage collector is the only coworker who can stop the entire office to take out the trash.

We had our own run-in with it: under load, response latency climbed because requests were being paused, and the pauses were worst exactly when traffic was highest. I no longer have that incident's GC logs, so rather than invent numbers, here's the anatomy of the failure (it's remarkably consistent across Java services) and the playbook that fixes it.

The anatomy

1. Java frees memory with a garbage collector, and most collectors have stop-the-world phases: every application thread pauses while the collector works. A request that was 2 ms from done now waits for the whole pause.
2. Every request makes garbage: request and response objects, strings, boxed numbers, iterators. Most of it dies young, which is cheap, so young-generation collections are usually short and frequent.
3. Load turns that up. Garbage per second grows with requests per second, so collections come more often. And at high load more requests are mid-flight at each collection, so more objects are still alive, get copied, and get promoted to the old generation. Long-lived bulk like cache entries piles up there too, until the old generation needs a long collection.
4. The queue amplifies it. A pause doesn't end when it ends. Requests that arrived during it form a backlog, and the busier the host, the slower that backlog drains.

Point 4 surprises people, so here it is in a simulation. One host, the same 50 ms pause, the same garbage per request; only the load changes:

 load  pauses/s   p99 (ms)   requests slower than 10 ms
  30%     0.23       15.1       1.1%
  60%     0.46       40.9       4.3%
  80%     0.61       46.8      12.0%
  90%     0.69       48.6      26.7%

def simulate(load, seconds=30, capacity=10_000, pause_ms=50,
             kb_per_request=20, young_gen_mb=256):
    """One host serving requests in order. Every `young_gen_mb` of
    garbage, the collector stops the world for `pause_ms`.
    More load = more garbage per second = more frequent pauses."""
    rps = load * capacity
    service = 1000 / capacity                     # ms per request
    per_gc = young_gen_mb * 1024 // kb_per_request  # requests per GC
    free_at, latencies = 0.0, []
    for i in range(int(rps * seconds)):
        arrive = i * 1000 / rps
        start = max(arrive, free_at)
        if i and i % per_gc == 0:                 # stop the world
            start = max(start, arrive) + pause_ms
        free_at = start + service
        latencies.append(free_at - arrive)
    latencies.sort()
    p99 = latencies[int(0.99 * (len(latencies) - 1))]
    slow = sum(ms > 10 for ms in latencies) / len(latencies)
    return rps / per_gc, p99, slow

print(" load  pauses/s   p99 (ms)   requests slower than 10 ms")
for load in (0.3, 0.6, 0.8, 0.9):
    gcs, p99, slow = simulate(load)
    print(f"{load:>5.0%} {gcs:>8.2f} {p99:>10.1f}   {slow:>8.1%}")

At 30% load, a pause slows 1% of requests. At 90%, the same pause slows over a quarter of them, because pauses come more often and each backlog takes longer to drain (drain time grows with load ÷ (1 − load)). That's "it only happens under load", explained.

And here's why what lives on the heap matters. The collector has to walk every live object. The same two million scores held as small objects versus one flat array:

import gc
import time
from array import array

def full_gc_ms():
    t = time.perf_counter()
    gc.collect()
    return (time.perf_counter() - t) * 1000

# The same 2 million scores, held two ways.
as_objects = [[i, i * 0.5] for i in range(2_000_000)]  # 2M tiny lists
print(f"2M small objects:  full collection {full_gc_ms():6.1f} ms")
del as_objects

as_array = array("d", (i * 0.5 for i in range(2_000_000)))  # one object
print(f"one flat array:    full collection {full_gc_ms():6.1f} ms")

2M small objects:  full collection  188.3 ms
one flat array:    full collection    0.7 ms

That's Python's collector, not the JVM's, but the principle carries over: collection work scales with the number of objects, not the number of bytes.

The playbook

• See it first. Turn on GC logging (-Xlog:gc*) and chart pause time right next to p99 latency. If the spikes line up, you've found your culprit. Alarm on pause time and allocation rate, not just latency.
• Make less garbage per request. Reuse buffers, avoid boxing (long, not Long), and don't build throwaway strings and collections on the hot path.
• Keep big read-only data compact. A Bloom filter is one long[] the collector barely notices. Scores belong in primitive arrays or off-heap memory, not millions of tiny objects; cap on-heap caches, because every entry is old-generation weight.
• Size the heap on purpose. Set -Xms equal to -Xmx (no resize pauses), give the young generation room so short-lived garbage dies there, and pre-touch memory (-XX:+AlwaysPreTouch) so a fresh host doesn't stall on page faults.
• Keep headroom. The table above is the argument against running hosts hot.
• Load-test with real allocation patterns, because GC trouble only shows up under load.

You can watch both effects in the companion lab's Java experiment. On one machine, under the same synthetic load, switching from the Parallel collector to generational ZGC took the p99.9 from about 100 ms to 1.3 ms. Separately, capping a churning on-heap cache from a million entries to 100,000 cut Parallel's worst pause from about 127 ms to about 10 ms. Holding the big table as one flat array barely mattered there, because the cache was the real weight. Measure first.

Fast, reliable, correct, and visible

In my intro video I said the wolves keep me reliable. At a million requests a second, reliability is less about wolves and more about retries, timeouts, and knowing exactly which host is lying to you. Here are the challenges that come with this scale, and how they get solved.

Reliability: fail small, fail fast, fail open

Retries are a loaded gun. Every layer retrying the layer below multiplies traffic at the bottom, exactly when the bottom is struggling. Back off exponentially with jitter, and cap retries with a budget:

import random

def worst_case_calls(layers, attempts_per_layer):
    """Every layer retries the layer below it."""
    return attempts_per_layer ** layers

print(f"3 layers x 3 attempts = {worst_case_calls(3, 3)}x the "
      f"traffic at the bottom, exactly when it is struggling")

def backoff_s(attempt, base=0.01, cap=1.0):
    """Exponential backoff with 'full jitter': a random wait in
    [0, base * 2^attempt], so retries spread out instead of
    arriving as a synchronized wave."""
    return random.uniform(0, min(cap, base * 2 ** attempt))

class RetryBudget:
    """Retries may add at most `ratio` extra traffic."""
    def __init__(self, ratio=0.1):
        self.ratio, self.requests, self.retries = ratio, 0, 0
    def on_request(self):
        self.requests += 1
    def can_retry(self):
        if self.retries < self.ratio * self.requests:
            self.retries += 1
            return True
        return False

random.seed(1)
print("waits:", [f"{backoff_s(a) * 1000:.0f}ms" for a in range(5)])
budget = RetryBudget(0.1)
for _ in range(1_000):
    budget.on_request()
allowed = sum(budget.can_retry() for _ in range(1_000))
print(f"1,000 requests fail at once -> {allowed} retries allowed")

3 layers x 3 attempts = 27x the traffic at the bottom, exactly when it is struggling
waits: ['1ms', '17ms', '31ms', '20ms', '79ms']
1,000 requests fail at once -> 100 retries allowed

Relevance is an enhancement, not a dependency. An answer that arrives after the auction is the same as no answer, so the caller sets a tight timeout and, if relevance is slow or down, serves the page without the boost instead of failing it. A circuit breaker makes that automatic: after a run of failures it stops calling for a cooldown, then lets a trial request through ("half-open") to see whether the service has recovered:

100 requests during an outage -> 3 reached the service; all 100 still served

import time

class CircuitBreaker:
    """After `threshold` straight failures, stop calling for
    `cooldown` seconds and use the fallback instead."""
    def __init__(self, threshold=5, cooldown=1.0):
        self.threshold, self.cooldown = threshold, cooldown
        self.failures, self.open_until = 0, 0.0

    def call(self, fn, fallback):
        if time.monotonic() < self.open_until:
            return fallback()                  # open: fail fast
        try:
            result = fn()
            self.failures = 0                  # closed again
            return result
        except Exception:
            self.failures += 1
            if self.failures >= self.threshold:
                self.open_until = time.monotonic() + self.cooldown
            return fallback()

def relevance_service():
    raise TimeoutError("relevance call timed out")

breaker = CircuitBreaker(threshold=3, cooldown=5)
calls = {"tried": 0}
def tracked():
    calls["tried"] += 1
    return relevance_service()

# Serve the ad without a relevance boost instead of failing the page.
answers = [breaker.call(tracked, fallback=lambda: "no boost")
           for _ in range(100)]
print(f"100 requests during an outage -> {calls['tried']} reached "
      f"the service; all {answers.count('no boost')} still served")

• Shed load early. When a host's queue is already longer than the caller's deadline, say no immediately. A fast "no" beats a slow "yes" that arrives too late.
• Deploy like it's Prime Day. One host first, then small waves, with automatic rollback when alarms fire.
• Migrate like it's live, because it is. When Sponsored Products moved its retrieval caches from Redis to Valkey, they dual-wrote to both, shifted reads over gradually with a rollback ready, and reported no impact on availability or performance, plus over 45% lower infrastructure cost.
• Data publishes are deploys too. Validation gates, the last good version kept on hand, and a one-command rollback for data, not just code.
• Spread across Availability Zones, with N+1 headroom, so losing a zone is a bad afternoon, not an outage.

Failure modes, on one page

Correctness: everyone agrees on what "today" is

• Version skew is the quiet killer. A host still serving yesterday's filter gives confident wrong answers. Every host and every ad-server copy reports the version it has loaded, and an alarm fires when they disagree.
• Bad data never ships. Row counts, score distributions and spot checks are compared with yesterday before anything publishes, and anything odd keeps yesterday's version live.
• New logic proves itself before it serves. End-to-end tests run the whole path (ad server to database), shadow traffic compares new answers with old without affecting users, and only then does an A/B test decide.

Visibility: averages lie

Here's the trap that hides most problems at this scale. Fifty hosts, one of them stuck in GC pauses:

fleet average latency     2.9 ms
fleet p99 (true)          5.6 ms
average of host p99s      6.5 ms  <- not a p99
worst host: #49, p99 56.3 ms

import random
import statistics

random.seed(7)
def p99(xs):
    return sorted(xs)[int(0.99 * (len(xs) - 1))]

# 50 hosts. 49 are healthy; one is stuck in GC pauses.
hosts = [[random.lognormvariate(1.0, 0.3) for _ in range(2_000)]
         for _ in range(49)]
hosts.append([random.lognormvariate(1.0, 0.3) +
              (random.random() < 0.08) * random.uniform(20, 60)
              for _ in range(2_000)])
fleet = [ms for host in hosts for ms in host]

print(f"fleet average latency  {statistics.mean(fleet):6.1f} ms")
print(f"fleet p99 (true)       {p99(fleet):6.1f} ms")
print(f"average of host p99s   "
      f"{statistics.mean(p99(h) for h in hosts):6.1f} ms  <- not a p99")
worst = max(range(len(hosts)), key=lambda i: p99(hosts[i]))
print(f"worst host: #{worst}, p99 {p99(hosts[worst]):.1f} ms")

The fleet average says 2.9 ms and everything looks fine. One host is serving a p99 of 56 ms, and every ad request routed to it pays. Averaging per-host p99s doesn't help either: the result isn't a p99 of anything. Store latency as histograms that can be merged (HdrHistogram and t-digest are the usual tools), look at p99 and p99.9 per host, and alarm on the worst host, not the mean.

• You can't log a million requests a second, and shouldn't try. Count everything as metrics, log every error, and sample a small fraction of successful requests as traces.
• One dashboard per layer: hit rate of the ad-server copy and the host cache, the Bloom filter's "maybe" rate, database reads and throttles, GC pause time, latency percentiles per host, and loaded data version per host.
• Alarm on symptoms first (latency and errors against the SLO), with cause metrics one click away. On-call should know that something hurts before guessing why.

Proving it was worth it

A relevance model is a hypothesis until real traffic says otherwise. The launch went through end-to-end testing and then an A/B experiment. A deterministic hash of the user and the experiment name assigns each user to control or treatment, the same way on every host, with nothing to look up:

import hashlib
from collections import Counter

def bucket(user_id, experiment, treatment_pct=50):
    """Same user + same experiment -> same bucket, on every host,
    with no shared state to look up."""
    key = f"{experiment}:{user_id}".encode()
    slot = int.from_bytes(hashlib.sha256(key).digest()[:8]) % 100
    return "treatment" if slot < treatment_pct else "control"

users = [f"user{i}" for i in range(100_000)]
split = Counter(bucket(u, "relevance-v2") for u in users)
print(dict(split))
print("sticky:", all(bucket(u, "relevance-v2") ==
                     bucket(u, "relevance-v2") for u in users[:1000]))

{'treatment': 49922, 'control': 50078}
sticky: True

Treatment is compared with control on the metrics the business cares about, and only a real difference makes a launch. Ours held over a million requests per second and was projected to add $10 million a year in ad revenue for Amazon DSP.

The well-earned drink at the end

On my travel channel, The Brew Miles, every trip ends with a well-earned drink. Here's this one's:

1. Do the arithmetic first. Size for the peak, and use Little's law to turn latency into capacity.
2. Move work out of the request. Precompute whatever you can, on a schedule.
3. Make "no" cheap. A Bloom filter answers misses from memory, with no false negatives, for about 10 bits per key.
4. Cache where the request starts. The cheapest call is the one never made, and layers multiply.
5. Version everything that travels together, and swap atomically.
6. Rebuild instead of patching when inputs are messy. Idempotent backfills heal themselves.
7. Scale on hosts for hot, steady traffic, and scale before known peaks, not after.
8. Treat garbage as a latency budget. Fewer objects, compact data, a collector built for tail latency.
9. Fail open, retry on a budget, and watch percentiles per host. Averages are where problems hide.
10. Prove it with an experiment before you call it a win.