On this page
You open a travel site on your phone, type "cheap flights goa" and press Enter. Within a fraction of a second your words are split up, routed, cached, sent to several machines, looked up in a giant index and ranked. On the way, your request makes two very different kinds of trip. A round trip between two machines in the same data centre takes about 0.5 ms. A round trip from New York to London takes about 56 ms, even at the speed of light in fiber. Where those milliseconds go decides how fast search feels. Let's follow one query, one stop at a time.
Where this fits: Start here. This is the map for the whole Search & storage series.
Before you start: Nothing. This is the first read. If a word is new, check the glossary below.
After reading this you will be able to
- Walk a search query through all 14 stops, from the keyboard to the SSD and back, and say what each stop does.
- Point at the stops that cost milliseconds and the ones that cost nanoseconds, using real latency numbers.
- Explain scatter-gather and why the slowest shard sets your response time.
- Trace how a new record travels from the database into the search index, and why search lags behind by design.
- Present a search design in an HLD interview and handle the common follow-up questions.
01One query, fourteen stops
A user in Bengaluru searches for cheap flights goa on their phone. We'll follow that request to the data centre, down to the disk, and back. Then we'll follow a write: an airline adds a new cheap flight, and we'll see how long before this search can find it.
Think of a busy restaurant. The waiter at the door (the load balancer) seats you. The head chef (the coordinating node) splits your order across stations (the shards), each with its own recipe index (the inverted index). The pass puts the plate together (the merge). The pantry by the stove is the page cache; the cold store downstairs is the SSD.
What we cover, and what we skip
- We cover: the read path, the write path, the latency numbers that matter, what goes wrong, and the interview angle.
- We skip: TCP and TLS handshakes and page rendering. See what-happens-when and High Performance Browser Networking for those.
- Every number here is an order of magnitude, not a benchmark.
Each stop ends with a Go deeper link to the blog that explains it properly.
02Words you'll meet
Twenty terms, in the order the query meets them. Skim now, come back later.
| Term | What it means |
|---|---|
| Debounce | Wait for a pause in typing before sending, so "goa" sends one request, not three. |
| Autocomplete | Suggestions shown while you type, from a fast prefix index. |
| Latency | The time between asking for something and getting the answer. |
| DNS | The internet's phonebook: it turns a name like travel.example into an IP address. |
| CDN / edge | Servers close to users that cache content and end the connection near you. |
| Load balancer | Spreads incoming requests across many identical servers and skips unhealthy ones. |
| Cache | A fast copy of a recent answer kept in memory (here, Redis). |
| Cache hit / miss | The answer was, or wasn't, already in the cache. |
| Coordinating node | The node that fans a query out to shards and merges the answers. |
| Shard | One slice of the index, living on one machine. |
| Replica | A copy of a shard, for safety and extra read capacity. |
| Scatter-gather | Send the query to every shard (scatter), then collect and merge the results (gather). |
| Inverted index | A map from each word to the documents that contain it, like the index at the back of a book. |
| Posting list | The list of document IDs stored for one word. |
| Segment | A small, immutable mini-index file inside Lucene; a shard is made of many segments. |
| Analyzer | The step that splits text into words and normalizes them, so "Flights" can match "flight". |
| BM25 | The default formula that scores how well a document matches the query words. |
| Page cache | Spare RAM the operating system uses to keep recently read file data. |
| Refresh | In Elasticsearch, the step that makes newly written documents searchable (every 1 s by default). |
| Tail latency (p99) | How long the slowest 1% of requests take. |
03The whole trip on one page
Here's the full map. Don't memorize it; we'll walk it stop by stop. Blue stops cross the internet, purple ones live in the data centre, green ones happen inside one machine.
One search query, fourteen stops
04The read path, stop by stop
Stop 1: the browser and autocomplete
As you type "che...", the page waits for a short pause (debounce), then asks for suggestions from a prefix index built for speed. Elasticsearch's completion suggester, for example, uses structures that are fast to query but, in Elastic's words, "costly to build and are stored in-memory" (Elastic docs). Pressing Enter sends the real search as an HTTP request.
Go deeper: Types of search: autocomplete.
Stop 2: DNS
The browser needs the site's IP address. A DNS resolver walks the DNS hierarchy if it doesn't already know it, but the answer is usually cached, so this stop is often close to free.
Go deeper: Cloudflare: What is DNS?
Stop 3: the CDN edge
The request lands on an edge server near the user, which can cache static files and sometimes popular autocomplete answers. Personalized results usually go on to the origin data centre. Physics sets the floor: light in fiber travels at about 200,000,000 m/s, so a far-away origin costs tens of milliseconds per round trip (HPBN, chapter 1).
Go deeper: Cloudflare: What is a CDN? and HPBN: Primer on latency and bandwidth.
Stop 4: the load balancer
The load balancer spreads requests across identical app servers and skips any that fail health checks, like a supermarket sending you to the shortest checkout queue. In an interview, name it and move on.
Go deeper: Cloudflare: What is load balancing?
Stop 5: the app server
This is your code. It turns intent into structure: "cheap" becomes a sort by price, "goa" becomes destination GOI, dates come from the form. Before calling the search cluster, it checks the cache.
Go deeper: How search engines work: text analysis (what happens to "flights" vs "flight"), and Choosing a search engine (do you even need a search cluster for this?).
Stop 6: the Redis cache
The app looks up the normalized query in Redis. A hit returns right away; a miss goes to the search cluster and then fills the cache. This is the look-aside pattern; Facebook's memcache paper calls it a "demand-filled look-aside cache" (NSDI 2013). Fares change constantly, so keep the expiry short or invalidate on price changes.
Go deeper: Reads and writes: caching.
Stop 7: the coordinating node
Whichever Elasticsearch node receives the search becomes its coordinator. It picks one copy of each shard, primary or replica. By default it uses adaptive replica selection, which steers each request toward the copies that are responding well (Elastic docs).
Go deeper: Elasticsearch: the pieces.
Stop 8: the shards (scatter-gather)
The coordinator sends the query to every shard in parallel. Each shard searches only its own slice and returns its own top results. Ask for 10 results across n shards and the coordinator has to merge up to 10 × n candidates (Elasticsearch from the Top Down). Here's the catch: the coordinator can't answer until the slowest shard replies, so one sluggish machine slows down every search.
Here's that conversation in slow motion.
Scatter-gather: ask every shard, merge, then fetch only the winners
Seen this before?
Scatter-gather shows up all over this series. Elasticsearch calls its version query_then_fetch (Elasticsearch: the read path). Google splits its web index by document and fans every query out the same way (How Google Search works). And it's the reason facet counts can be approximate (Types of search).
Stop 9: segments and the inverted index
Inside one shard, the index is a set of immutable segments. Lucene's own docs describe each segment as a "fully independent index" (Lucene file formats). For each word, "cheap", "flight" and "goa", Lucene looks up the term, reads its posting list, finds the documents that match, and scores them with BM25. Elasticsearch's defaults are k1 = 1.2 and b = 0.75 (similarity settings).
Seen this before?
The inverted index is the heart of How search engines work, and Postgres and Redis have their own versions (Choosing a search engine). "Write immutable files, merge them later" is the same idea as an LSM tree (Reads and writes, Storage data structures).
Go deeper: How search engines work: BM25 and Storage data structures.
Stop 10: the OS page cache
Lucene reads its index files through the operating system, and the OS keeps recently read file pages in spare RAM. The Kafka docs put it nicely: a modern OS will divert "all free memory" to disk caching (Kafka design). A warm index is mostly served from memory, at about 100 ns per RAM reference. That's why search nodes want lots of free RAM beyond the JVM heap.
Go deeper: Disk I/O and durability.
Stop 11: the SSD
On a page-cache miss, the read goes to flash. A random SSD read takes about 16 µs in Colin Scott's model, while a spinning-disk seek takes about 8 ms in Norvig's list. That's roughly 500x by our own arithmetic, and it's why search clusters run on SSDs.
Go deeper: Disk I/O and durability: HDD vs SSD.
Stop 12: back up, each shard returns its top N
Now we turn around. Each shard sends back only IDs and scores. Sending 2 KB over a 1 Gbps network takes about 20 µs (Norvig), so this is cheap.
Go deeper: Elasticsearch: the read path.
Stop 13: merge, rank, fetch
The coordinator merges the per-shard lists into one global top 10, then fetches the full documents from the shards that own them. Many products then re-rank in the app with business signals like price or popularity. Slack describes this two-stage shape: Solr retrieves candidates with cheap features, then the app re-ranks them with a learned model (Search at Slack).
Many candidates offer page 500
With from and size, Elasticsearch won't page past 10,000 hits by default, because every shard would have to send its top 10,000 to the coordinator. For deep scrolling, use search_after (Elastic docs).
Go deeper: Elasticsearch: query then fetch and Search case studies (two-stage ranking in the wild).
Stop 14: the response
The app server stores the result in Redis, returns JSON through the load balancer and edge, and the browser draws the list. People start to notice lag at about 100-200 ms (HPBN). That is the budget the whole trip has to fit inside, and one cross-ocean round trip can eat half of it.
Go deeper: Types of search (the filters and facets shown next to results).
05The latency cheat sheet
These numbers come from three sources that mostly agree: Peter Norvig's list (Teach Yourself Programming in Ten Years, 2002 figures), Colin Scott's interactive latency page, and the speed-of-light table in HPBN.
| Operation | About | Source | Where it shows up in our query |
|---|---|---|---|
| L1 cache reference | 0.5 ns | Norvig | CPU scoring a posting list |
| Main memory (RAM) reference | 100 ns | Norvig, Colin Scott | Index pages in the page cache |
| SSD random read | 16 µs | Colin Scott | Page-cache miss on a shard |
| Send 2 KB over a 1 Gbps network | 20 µs | Norvig | A shard returning its top-N IDs |
| Read 1 MB sequentially from memory | 250 µs | Norvig | Scanning a big posting list in RAM |
| Round trip within the same data centre | 0.5 ms | Colin Scott | App to Redis, coordinator to shard |
| Spinning-disk seek | 8 ms | Norvig | Why we avoid spinning disks for search |
| Read 1 MB sequentially from disk | 20 ms | Norvig | Bulk reads on a hard drive |
| New York to San Francisco and back, in fiber | 42 ms | HPBN | A user across the country |
| New York to London and back, in fiber | 56 ms | HPBN | A user across an ocean |
| US to Europe and back (a real packet) | 150 ms | Norvig, Colin Scott | An origin far from the user |
| New York to Sydney and back, in fiber | 160 ms (200-300 ms in practice) | HPBN | The worst case for a single global origin |
| People notice lag | 100-200 ms | HPBN | The total budget |
What this means for our query (the ratios are our own rough arithmetic):
- Hops inside the data centre are cheap. Five at 0.5 ms each is still under 3 ms.
- One ocean crossing is expensive: New York to London is roughly 100x a data-centre hop.
- RAM vs SSD is roughly 160x (100 ns vs 16 µs), so a warm page cache matters.
- Disk seek vs SSD read is roughly 500x (8 ms vs 16 µs), so busy indexes live on SSDs.
The same numbers look clearer as a ladder on a log scale.
The latency ladder on a log scale
06The write path: a new flight is added
Now flip it around. An airline adds a cheap Bengaluru to Goa flight. How long until "cheap flights goa" shows it? About a second, plus however long your pipeline takes.
- Source of truth. An ops tool or partner feed writes the flight to Postgres. Postgres writes the change to its write-ahead log and flushes the log before touching the data pages (Postgres WAL docs).
- Capture the change. A CDC tool such as Debezium reads Postgres's logical replication stream (Debezium architecture), or the app writes an event to an outbox table in the same transaction (transactional outbox). CDC (change data capture) streams every database change to other systems.
- Kafka. The change lands on a Kafka topic, an append-only log that other systems read at their own pace.
- Indexer. A consumer builds the search document (route, fare, times) and sends it to Elasticsearch.
- Primary shard. Elasticsearch hashes the document ID to pick a primary shard, which writes to its translog (a write-ahead log) and an in-memory buffer, then copies to the replicas. With the default durability setting, the translog is fsynced on the primary and the replicas before the write is acknowledged (translog settings).
- Refresh. About once a second, the buffer becomes a new searchable segment. By default that happens every 1 s, but only on indices that got a search in the last 30 s (near real-time search). Small segments get merged into bigger ones in the background.
- Cache. The Redis entry for "cheap flights goa" expires or gets invalidated, so the next search sees the new flight.
Here's that path as a picture. Count the logs.
A new flight travels from the database to the search box
Why so many logs? On the same spinning disks, the Kafka team measured linear writes at "about 600MB/sec" and random writes at "about 100kB/sec" (Kafka design).
The big lesson: search is eventually consistent with the database. MongoDB says this outright about its own search feature, which is fed from change streams (MongoDB docs). Real systems choose their delay on purpose. Discord set its message indices to refresh every 60 minutes, because people mostly search older messages (Discord). DoorDash applies high-priority updates right away and leaves bulk changes for a full rebuild, usually every six hours (DoorDash).
Seen this before?
The write-ahead log is everywhere: Postgres, Redis and Kafka (Reads and writes), the filesystem journal and fsync (Disk I/O and durability), and the Elasticsearch translog (Elasticsearch: the write path). Immutable segments plus merging is covered in How search engines work.
Go deeper: Reads and writes: the write path, Elasticsearch: buffer, translog, refresh and Disk I/O and durability: write and fsync.
07What can go wrong
The happy path is fast. Here are five ways it goes wrong.
Failure modes to name
- Cache stampede. A popular key expires and hundreds of requests miss at once and hit the cluster together. Let one request refill the key while the others wait or get the stale copy.
- One slow shard. Scatter-gather waits for the slowest reply, so one busy node drags every query. Jeff Dean's WSDM 2009 keynote notes that touching thousands of machines per query turns variance into the new problem (slides).
- Too many tiny shards. Each shard has overhead and widens the fan-out. Elastic's guidance is 10-50 GB and fewer than 200 million documents per shard (size your shards).
- Cold page cache. After a restart or reindex, the first queries hit the SSD instead of RAM until the index warms up. Dean's slides warn about the same spike when the index is updated or a cache is flushed.
- Index lag. The write path stalls and search shows stale prices. Decide which fields must be fresh (price, seats) and which can wait.
Go deeper: Elasticsearch and Search case studies: Discord.
08How this shows up in HLD interviews
"Design search for a travel site" or "design product search" is a classic prompt. When I ask it, I'm listening for four things: where the index lives, how it stays fresh, how a query fans out, and where you cache. Most candidates cover one or two.
Draw the read path across the top and the write path along the bottom, then let the interviewer pick one to drill into.
Whiteboard summary
- Read: client → load balancer → search API → Redis → ES coordinator → shards → merge → response.
- Write: Postgres → CDC or outbox → Kafka → indexer → ES primary → replicas.
- Freshness: about 1 s refresh. Shard size: 10-50 GB.
- Source of truth: Postgres. Elasticsearch is a copy you can rebuild.
The 60-second talk track
"Postgres is the source of truth. Changes flow through CDC into Kafka and an indexer into Elasticsearch, so search is a read-optimized copy that lags by about a second. Queries hit a Redis cache first, then a coordinating node that scatters to every shard and merges the top N. I'd size shards in the tens of GB, keep the hot index in the page cache on SSD nodes, and treat the slowest shard as my latency budget."
Many candidates draw Elasticsearch as the database
It's a derived, eventually consistent copy built for reading. Keep a real source of truth next to it, so a broken index is a rebuild, not data loss.
Many candidates forget the write path
They draw the query side and never say how a new record reaches the index, or they promise "real-time" without saying what refresh costs.
These are the follow-ups I'd ask next, with where to read up on each.
How does autocomplete stay fast enough while someone is typing?
Debounce on the client, a separate prefix index on the server, and a cache for popular prefixes. Read Types of search: autocomplete.
What if the price changed one second ago?
Search may show the old price for about a refresh interval, plus any pipeline delay. Re-check the price from the source of truth at booking time. Read Elasticsearch: the write path.
Why not use Postgres full-text search?
Often you should, at first. One fewer system is a real win until you need fuzzy matching, heavy relevance tuning or more scale. Read Choosing a search engine.
How do you shard the index?
Usually by document, so every query fans out to all shards. Splitting by word is the alternative Google weighed. Read Elasticsearch: document routing and How Google Search works.
Is the data safe if a node dies?
Yes, with replicas and a translog fsynced before the ack. And the index can be rebuilt from Postgres. Read Disk I/O and durability and Reads and writes: replication.
How do you rank results?
BM25 inside the engine, then an app-side second stage that mixes in price and popularity. Read How search engines work: BM25 and Search case studies.
The user wants page 500. What happens?
From and size stop at 10,000 hits by default. Use search_after, and ask whether anyone needs page 500. Read Elasticsearch: the read path.
09The series map: where to go next
Starting cold? Read in this order; it builds from the disk upward.
| # | Blog | What you'll get | Access |
|---|---|---|---|
| 1 | Disk I/O and durability | What "saved" really means: page cache, fsync and why disks can lie. | Members |
| 2 | Storage data structures | B-trees, LSM trees, Bloom filters, inverted, geo and vector indexes in one place. | Members |
| 3 | Reads and writes | WAL, B-tree vs LSM, caching, replication and sharding, and what each costs. | Free |
| 4 | How search engines work | Text analysis, the inverted index, TF-IDF and BM25 from scratch. | Free |
| 5 | Types of search | Autocomplete, fuzzy, phrase, geo, faceted, vector and hybrid, and the index each needs. | Members |
| 6 | Elasticsearch | Shards, replicas, translog, refresh, merges and query then fetch. | Members |
| 7 | Choosing a search engine | Postgres, Redis, Elasticsearch, OpenSearch, Solr, Typesense: when each one wins. | Members |
| 8 | How Google Search works | Crawling, indexing, PageRank, serving and freshness at web scale. | Members |
| 9 | Search case studies | What Discord, GitHub, LinkedIn, Uber, Pinterest and others faced, chose and learned. | Members |
Key takeaways
- A search makes two kinds of trip: short hops inside a data centre (about 0.5 ms) and maybe one long hop to the user (tens of ms). The long one usually dominates.
- The search cluster is a read-optimized copy of your data, fed by a log-based write path. It lags by design, about 1 s by default in Elasticsearch.
- Scatter-gather means the slowest shard sets your latency.
- The inverted index is fast because its hot parts live in RAM through the page cache; SSDs catch the misses.
- The same few ideas repeat at every layer: append to a log, write immutable files and merge them, and cache what's hot.
Next up
Disk I/O and durability: start at the bottom of the stack and find out what "saved" really means.
Real-world story
Discord: chose a 60-minute refresh on purpose, and shows how far a deliberate delay on the write path can take you.
Further reading
- What happens when...The full keyboard-to-pixels walk, for everything we skipped.
- HPBN: Primer on latency and bandwidthWhy physics sets a floor on latency, and where the rest of the time goes.
- Cloudflare: What is DNS?The clearest beginner explanation of how a name becomes an IP address.
- Colin Scott: Latency numbers every programmer should knowThe classic numbers, with a slider to see how they changed by year.
- Elasticsearch from the Top DownOne search request traced across an Elasticsearch cluster.
- Scaling Memcache at FacebookThe look-aside cache pattern at enormous scale.
Go deeper
Deep dives from this guide
Interview practice