Search case studies

Search case studies show that real search systems are built from the same few parts: an inverted index or a cousin of it, immutable segments, document-partitioned shards and a ranking funnel, each bent by one dominant constraint. GitHub bent its index for substrings, Twitter its write path for tweets searchable in seconds, Yelp its shards and deploys for local ranking, Airbnb its ranker for bookings, Amazon its retrieval for meaning, and Uber its whole store for cost.

This is the last part of the search engines series. Parts 1–7 built search for Bazaar’s 50 million products: part 1 mapped the kinds of search, part 2 built the inverted index, part 3 put it on disk, part 4 chose the engine, part 5 ran the cluster, part 6 scaled to the web and part 7 assembled the whole system; here we test those ideas against real systems that published how they work. Every source is the company’s own write-up, dated. The systems have probably changed since.

Picture it first: six shops on one street

Walk the lanes around Mumbai’s Lamington Road. Every shop has a godown at the back, a register saying what is where, and someone at the counter deciding what to show you first. Yet no two are laid out alike, because one thing rules each.

The station newspaper stall lives on minutes: the evening edition must be on the rack before the 6:10 local pulls in. The electronics spares dealer finds a part from a scrap of its number, “…7805”, so his register is indexed by fragments. The dabbawalas’ sorting point arranges everything by locality before anything else. The property broker has learned from years of deals which flats families actually take, and each flat can be let only once. The chemist understands “something for a headache, not too strong” though no box says it. And the municipal record room keeps every receipt for years, so the cheapest shelf wins; its clerks mostly count.

Map it back: the godown is the source of truth, the register the index, the counter ranking. The newspaper stall is Twitter’s Earlybird, the spares dealer GitHub code search, the dabbawalas Yelp’s geo-shards, the broker Airbnb’s learned ranker, the chemist Amazon’s semantic matcher, and the record room Uber’s log store.

One recipe, six constraints

Parts 1–7 gave a default design: an inverted index of immutable segments, refreshed every second, split into document-partitioned shards that a coordinator fans out to, with cheap retrieval followed by a learned reranker. Every system below keeps most of that recipe and changes one or two stages, the ones its dominant constraint presses on (Fig. 1).

Each case uses six labels: the constraint, what they built, the trick worth stealing, numbers with their year, back to the series, and what you’d say in an interview.

GitHub code search

The constraint. Code is not prose: developers search for ., ( and ::, want no stemming or stop-word removal, and use regexes. GitHub’s Elasticsearch cluster grew to 162 nodes, 40 TB of RAM and 1.25 PB of storage by December 2021, but its tokenizer split text on punctuation, so punctuation was never searchable, and the first full index took months.

Why not grep? ripgrep scans 13 GB ÷ 2.769 s ÷ 8 cores ≈ 0.59 GB/s per core; 2,048 cores scan about 1.2 TB/s, so 115 TB takes about 96 seconds a query with every core busy: 0.01 queries a second.

What they built. Blackbird, a search engine written from scratch in Rust (Fig. 2):

• n-gram indices for content, symbols and paths, plus plain indices for language, owner and repository. Gram lengths are dynamic, so /arguments?/ becomes arg, rgu, gum, then either ume and ment or the six-gram uments.
• Doc IDs in rank order. Compaction k-way merges postings by score, so the best documents get the lowest IDs and lazy iterators stop once they have enough.
• Shards keyed by Git blob SHA. A file copied into thousands of forks is one blob, indexed once, and hashes spread load with no hot repositories. The price: every query visits every shard.
• Delta crawling. Each repository is crawled as a diff against a similar parent, so only its unique blobs are fetched.
• Kafka for consistency. Each shard consumes exactly one partition, and message order means you never see half a push.

A query is rewritten (languages to IDs, plus permission clauses) and sent to every shard, which runs its gram iterators, checks each candidate against the real text and returns its best; the query service merges, re-checks permissions and returns the top 100.

The trick worth stealing. Shard by content hash. Deduplication, even load and cheap fork indexing all fall out of one key.

Numbers (February 2023, public beta). 45 million repositories, 115 TB, 15.5 billion documents. Ingest publishes about 120,000 documents a second: 15.5 billion ÷ 120,000 ≈ 129,000 s ≈ 36 hours, cut to about 18 hours because delta crawling skips over half the documents. Deduplication leaves 28 TB of unique content, and the index, compressed content included, is 25 TB: 25 ÷ 115 ≈ 22% of the raw data. A shard answers in about 100 ms at p99 on one core, so a 64-core host tops out near 640 queries a second.

Back to the series. It is part 2’s n-gram index with a verification step, and part 4’s build-or-buy question answered “build” after a decade of buying.

What you’d say in an interview. “I’d index n-grams of content, symbols and paths, verify candidates against the text, and shard by content hash so a file shared by a thousand forks is indexed once.”

Twitter’s Earlybird

The constraint. In autumn 2011 users posted over 250 million tweets and ran over two billion searches a day: 250,000,000 ÷ 86,400 ≈ 2,900 tweets and 2,000,000,000 ÷ 86,400 ≈ 23,000 queries a second on average. Results came newest first, a tweet had to be findable almost at once, and the same machines had to index and serve at full speed.

What they built. Earlybird (Busch et al., ICDE 2012): Java on Lucene, everything in memory. Tweets are hash-partitioned across servers; a Blender front end fans each query out with the searcher’s social graph, then merges and re-ranks. Inside a server, time partitions the index (Fig. 3):

• Segments in time order. A server held several segments (12 then), each capped at 2²⁴ doc IDs and in practice 2²³ ≈ 8.4 million tweets. Only the newest is writable; when it fills, a background job writes a compressed, read-only copy and swaps it in.
• Postings as plain integers. In the active segment a posting is one 32-bit int: 24 bits of doc ID, 8 of position, enough for 140 characters. A term’s list grows through linked slices of 2, 16, 128 and then 2,048 ints, so nothing is copied and the garbage collector stays idle. Readers walk each list backwards from its tail: newest first, no sorting.
• One writer, many readers, no locks. A single thread indexes. After writing every posting of tweet n, it sets a volatile counter, maxDoc, to n. Java’s memory model guarantees that a reader which reads maxDoc first sees every write before it; postings that leak through early, above maxDoc, are ignored.

The trick worth stealing. Make visibility a single number. One writer publishes a high-water mark; readers trust only what lies below it.

Numbers (2012). Tweets were usually searchable within 10 seconds, at 50 ms average query latency. On a 72 GB server, one 16-million-tweet segment served 17,000 queries a second at p99 under 200 ms, and a full server of 144 million tweets about 5,000 at p99 170 ms. A stress test indexed 7,000 tweets a second under near-full query load, at p95 indexing latency of 150 ms.

Back to the series. This is part 3’s immutable segments plus a small mutable head, the one-second refresh replaced by a per-tweet publish. With indexing at 0.15 s, most of the 10 seconds is upstream, in part 7’s pipeline.

What you’d say in an interview. “For post search I’d keep recent posts in in-memory segments, one writer each publishing a max doc ID, readers walking postings newest first, and full segments frozen and compressed.”

Yelp business search

The constraint. Local search is text plus place: “tacos” means tacos near you, ranked by Yelp’s own signals, and the ranking team shipped changes several times a day.

Its legacy engine, custom code on Lucene, used two-tier sharding: geoshards by business location (San Francisco and Chicago in different indexes), each split into microshards by business_id % n, each with replicas. A coordinator picked the geoshard and broadcast to its microshards. Masters uploaded index snapshots to S3 for serving replicas to download, so updates lagged a few minutes; bookable features needed seconds, so the application also queried Elasticsearch and merged the two result lists itself. And every ranking push restarted every instance, each downloading tens of gigabytes and warming caches: several hours per push.

What they built. Core search on Elasticsearch (2017):

• Ranking as a plugin. The scoring code sees only two small interfaces, Document and Scorer, so it doesn’t know which engine runs it.
• Hot reload. A deploy uploads the ranking jar to S3 and calls a custom endpoint; the plugin loads it in a private class loader. No restart.
• Features in doc values. Data that had lived on the JVM heap moved to doc values, served by the page cache. Each business’s popular-queries data became fixed-size binary records, binary-searched in place rather than deserialised for every candidate.
• Shards for CPU. Scoring was the bottleneck, so more shards meant more parallel scoring, up to a sweet spot.

The trick worth stealing. Separate where the data lives from how you rank it, so ranking ships in minutes and the engine can change underneath.

Numbers (June 2017). The post is light on figures: pushes went from several hours to a few minutes, regular reindexing became possible, and real-time indexing (seconds, not minutes) was a stated goal.

Back to the series. Part 4’s buy decision, taken after years of building, and part 5’s shards and doc values. Sharding by place is the geospatial index idea applied at cluster level.

What you’d say in an interview. “For nearby search I’d cut by geography first, with routing or a geo filter, and keep ranking code in a plugin I can redeploy without restarting the cluster.”

Airbnb search ranking

The constraint. A guest searches for homes in a place; ranking orders a handful of the thousands available by the chance of a booking. Each listing is unique and scarce: even the most popular can be booked at most 365 times a year. Gradient-boosted trees had brought big wins, then long spells of neutral experiments.

What they built. Applying Deep Learning to Airbnb Search (Haldar et al., KDD 2019) tells a two-year road in four steps:

1. A simple network: one hidden layer of 32 ReLUs, the trees’ features and objective. Bookings neutral, but it proved the pipeline could serve live traffic.
2. A LambdaRank network: pairs of booked and unbooked listings from the same search, weighted by ΔNDCG. The first real win.
3. A hybrid fed tree leaf indices and a factorisation machine’s prediction in as inputs.
4. A deep network: 195 input features, hidden layers of 127 and 83, and 10× more data, 1.7 billion pairs, which closed the train–test gap and let them delete the hybrid.

What failed teaches more. Listing-ID embeddings overfit: 365 bookings a year can’t train a vector the way millions of plays train one for a video. Multi-task learning with long listing views as a helper raised long views a lot and left bookings flat. Dropout cost offline NDCG.

Features beat layers. Each was scaled to about −1 to 1, and lumpy distributions exposed bugs, such as monthly prices logged as nightly ones for stays over 28 days. The query city hashed with the listing’s level-12 S2 cell became an embedding that learned which neighbourhoods guests prefer.

The trick worth stealing. Launch the boring version first: new machinery, same features, same objective. Then change one thing at a time.

Numbers (2019). 1.7 billion training pairs; switching training input from CSV to protobufs made training 17× faster and lifted GPU use from about 25% to 90%. Offline NDCG gives the booked listing relevance 1 and every other 0; launches needed significant conversion gains in A/B tests.

Back to the series. This is the L2 stage of part 7’s funnel: ΔNDCG-weighted pairs, NDCG offline, A/B tests online.

What you’d say in an interview. “For a booking marketplace I’d start with boosted trees on booking labels, judge by NDCG and A/B conversion, and expect item-ID embeddings to overfit when each item sells only a few times.”

Amazon semantic product search

The constraint. Lexical matching misses what shoppers mean. “Running shoes” should find sneakers and “burgundy dress” a red one, while “latex examination gloves” wrongly matches latex-free gloves; a stemmer turns “reading glasses” into “reading glass”; and an estimated 10–15% of web search queries are misspelt. The fix had to answer in 20 ms at thousands of queries a second.

What they built. Semantic Product Search (Nigam et al., KDD 2019): a two-tower model with product vectors precomputed, whose nearest neighbours join the lexical match set before the usual rankers (Fig. 4).

• One shared embedding table, 256 dimensions, for query and product tokens, so the same word lands in the same place even before training.
• Average pooling, then batch normalisation and cosine similarity. LSTMs and GRUs came within 0.5% but were far slower; queries and titles are short.
• A bag of tokens: words, word bigrams (so “chocolate milk” differs from “milk chocolate”), character trigrams for typos, and hashed out-of-vocabulary tokens, hashed identically in both towers so an unseen model number still matches itself. 10,000 hash bins collided; 5–10× the vocabulary size worked.
• A three-part hinge loss: purchased products pushed above 0.9 cosine, shown-but-not-purchased below 0.55, random ones below 0.2, sampled at 6 shown and 7 random per purchase. Many shown-but-unbought products are fine matches, so lumping them with random ones blurred the scores.

The trick worth stealing. “Seen but not bought” is a different kind of negative from “random”: give it its own margin.

Numbers (2019). Training used 11 months of logs: 54 billion sampled query–product pairs, aggregated into 650 million weighted rows. Recall@100 on 20,000 queries over a million-product test corpus rose from 0.238 with a squared-error loss to 0.735 with the three-part hinge, and 0.794 with every token type. Growing the data from 200 million to 1.2 billion pairs added about 10%. Online, in toys and games, kitchen and pets, conversion and revenue rose significantly, but only after guard rails filtered irrelevant matches.

Back to the series. Part 1’s semantic and hybrid search, and part 7’s hybrid retrieval, except that Amazon unions the candidates and lets the rankers order them instead of fusing with RRF. More in embeddings and semantic search.

What you’d say in an interview. “I’d keep lexical retrieval for exact tokens, add a two-tower retriever trained on purchases with shown-but-unbought items as hard negatives, union both into the candidate set and guard precision before ranking.”

Uber’s log analytics

The constraint. Cost, at log volume. Uber ran ELK from 2014; by 2021 the platform took millions of logs a second, held several petabytes and served hundreds of queries a second, most of them not text search at all. Uber’s write-up names four problems:

• Schema. Elasticsearch fixes a field’s type from what it sees first; a later log with another type is a conflict and gets dropped.
• Operations. Over 20 clusters and 50 Logstash pipelines per region, to contain mapping explosions and heavy queries that could freeze clusters.
• Hardware. Indexing means inverted and forward structures, translog, flushes and merges, so fields were indexed only three levels deep, and still only part of Uber’s logs fit the budget.
• Aggregations. Over 80% of queries were terms, histogram or percentile aggregations. A busy service’s dashboard over the last hour, about 1.3 TB, loaded slowly; over six hours it timed out.

And only 5% of indexed fields were ever queried.

What they built. A schema-agnostic layer over ClickHouse, a columnar database (Fig. 5). Common metadata gets real columns; every other field is flattened into key-value pairs, grouped by type into parallel arrays (string.names, string.values and so on), with the raw log kept in a _source column. Types seen per field are recorded at ingest and resolved at query time, so a type conflict is normal, not an error. Often-queried fields are materialised into their own columns in the background. Kafka feeds an ingester and batcher that write large batches and commit offsets only after ClickHouse acknowledges, and a translation layer kept about 10,000 Kibana dashboards working.

The rejected designs teach too: raw JSON alone was too slow to parse, and one column per field, though 50× faster, multiplied files until background merges choked.

The trick worth stealing. Index adaptively: pay up front only for the fields people query, and read the rest by brute force.

Numbers (February 2021). One ClickHouse node ingested 300,000 logs a second, about 10× an Elasticsearch node; reading a field from the arrays was 5× faster than parsing JSON; compression ran 3×, up to 30×; ingestion latency stayed under a minute; and hardware cost fell by more than half while carrying more traffic.

Back to the series. Part 4 called logs a different problem; this is that answer at petabyte scale, with part 5’s data tiers as the Elasticsearch-side alternative.

What you’d say in an interview. “If most queries aggregate recent logs, I’d use a columnar store partitioned by time, materialise hot fields and keep the raw line for text matching, and save inverted indexes for workloads where full-text search is the main job.”

Six systems side by side

Patterns that repeat

The index is a copy. Git is GitHub’s source of truth, and the corpus reindexes in about 18 hours; Uber keeps the raw line and lets Kafka buffer; Yelp’s migration made reindexing routine. Plan the rebuild before you need it (part 7).

Immutable segments plus a small mutable head. Earlybird writes one active segment and freezes the rest; Blackbird flushes and compacts; Lucene refreshes and merges under Yelp; ClickHouse merges parts under Uber. Mutation is confined to the newest, smallest piece, and merges are the bill (part 3).

Partition by document, then scatter-gather. GitHub, Twitter’s Blender, Yelp’s coordinator and Uber’s query nodes all fan out to every partition. Only Yelp prunes the fan-out, because local search has a natural routing key: place (part 6).

A funnel. GitHub verifies and scores only what its iterators return; Earlybird servers score and the Blender re-ranks; Amazon and Airbnb rank a candidate set. Cheap work on many items, expensive work on few.

Measure before you tune. GitHub’s grep arithmetic, Uber’s 80% and 5%, Yelp’s profilers, Airbnb’s feature histograms, Amazon’s Recall@100: each decision came with a number.

Build versus buy. GitHub built after a decade on Solr and Elasticsearch, because code isn’t prose. Twitter kept Lucene’s query code but replaced its index structures to publish each tweet as it was written. Yelp went the other way, from home-grown to Elasticsearch, because its own engine slowed every change. Uber adopted open-source ClickHouse plus a thin layer. Amazon and Airbnb built models, not engines.

Going deeper: what the write-ups leave out

• Survivorship bias. Companies publish what worked. Airbnb’s failed models are a rare exception; abandoned projects, money spent, team sizes and migration time rarely appear.
• Scale mismatch. GitHub’s 115 TB and Uber’s petabytes dwarf most interview problems. Bazaar’s 50 million products fit a handful of Elasticsearch nodes (part 4); proposing a custom Rust engine for them is a red flag. Borrow the reasoning, not the architecture.
• Numbers age fast. Earlybird is a 2012 design built for 140-character tweets; GitHub’s figures describe a 2023 beta; Yelp’s plugin used 2017-era Elasticsearch APIs.
• Missing tails. Earlybird reports average latency, GitHub per-shard p99; end-to-end p99, the number users feel, is rarely published.
• Business metrics decide. Airbnb ships on bookings and Amazon on conversion and revenue. A relevance gain that doesn’t move them doesn’t ship.

Cheat sheet

How to say it in the interview

“Take GitHub code search, from its 2023 write-up. Code isn’t prose: you need substrings, punctuation and regexes, which word analysers throw away, and grep over 115 TB would take about 96 seconds a query. So GitHub built an n-gram index in Rust: gram iterators intersected per query, every candidate verified against the text. Shards are keyed by Git blob SHA, so a file shared by thousands of forks is indexed once and load is even, at the cost of sending every query to every shard, each answering in about 100 ms at p99. My lesson: build only the stage your constraint bends.”

Why didn’t GitHub just keep Elasticsearch? It did for a decade, up to 162 nodes. But its analyser dropped punctuation, indexing took months and hosting was expensive. Code needed a different index, not a bigger cluster.

How does Earlybird make a tweet searchable without locks? One writer thread per active segment appends postings, then bumps a volatile maxDoc. Readers read maxDoc first and ignore postings above it; the memory barrier guarantees everything below is visible.

Would you copy Blackbird for product search? No. Product search is word-based, and 50 million products fit a small Elasticsearch cluster. I’d copy the reasoning: name the query shape, then choose the index.

How do you stop a semantic retriever hurting precision? Keep lexical retrieval for exact tokens, train with shown-but-unbought items as hard negatives, and let rankers and precision guards filter the union, as Amazon did.

When is an inverted index the wrong tool? When queries aggregate rather than search, as with Uber’s logs: 80% aggregations and 5% of fields used. A columnar store with adaptive columns cut hardware cost by more than half.

Where to go next

• Back to the start: Types of search, part 1 of the series. How search engines work is a one-page overview of the same ground.
• The design problems that use these ideas: Design product search for an online store, Design typeahead, Design a web crawler, Design a search engine like Google, Design post search, Design a distributed logging system, Design RAG search over company documents and Design nearby places search.
• The key technologies: Elasticsearch, Vector databases, Embeddings and semantic search and Kafka.

References and further reading

1. Clem, The technology behind GitHub’s new code search (GitHub blog, February 2023)github.blogBlackbird in Rust: the grep arithmetic, n-gram indices with dynamic gram sizes, sharding by blob SHA, delta crawling, Kafka ordering, the query path and the ingest, size and latency numbers.
2. Avgustinov, A brief history of code search at GitHub (GitHub blog, December 2021)github.blogSolr, git grep and Elasticsearch eras; the 162-node cluster; why the pattern tokenizer made punctuation unsearchable; goals of minutes-fresh and p95 well under a second.
3. Busch, Gade, Larson, Lok, Luckenbill and Lin, Earlybird: Real-Time Search at Twitter (ICDE 2012)cs.uwaterloo.caRequirements, hash partitioning and the Blender, segments, 32-bit postings in slice pools, the single writer with a volatile maxDoc, optimised segments, and the 2011–2012 performance figures.
4. Moving Yelp’s Core Business Search to Elasticsearch (Yelp Engineering, June 2017)engineeringblog.yelp.comGeoshards and microshards, snapshot shipping through S3, hours-long ranking pushes, the scoring plugin with hot reload, and custom data as binary doc values.
5. Haldar et al., Applying Deep Learning To Airbnb Search (KDD 2019)arxiv.orgThe model sequence from a 32-unit network to a 195-feature deep network, the failed listing-ID and multi-task models, feature normalisation, S2-cell features and the 17× training speedup.
6. Nigam et al., Semantic Product Search (KDD 2019)arxiv.orgWhere lexical matching fails, the shared-embedding two-tower model, the three-part hinge loss, token hashing, training data sizes, Recall@100 tables and the online tests.
7. Fast and Reliable Schema-Agnostic Log Analytics Platform (Uber Engineering, February 2021)uber.comWhy ELK hit limits (type conflicts, 20+ clusters a region, 80% aggregations, 5% of fields queried) and the ClickHouse design, ingest path and cost and latency results.