1. The problem: why can't the database just search?

When you tap the search bar on Instagram and type sun, you expect to instantly see @sunsetchaser, #sunset and Sunset Boulevard, Los Angeles — ranked so that the account your friend follows is on top. Then you type suns and the list updates again, in under 100 ms. Every keystroke is a new query.

Try that with the User DB (sharded PostgreSQL in our architecture):

SELECT * FROM users
WHERE username ILIKE '%sun%' OR full_name ILIKE '%sun%'
ORDER BY follower_count DESC LIMIT 10;

• It can't use a normal index. A B-tree index (see Indexing) helps with prefix matches on one column (LIKE 'sun%'), but not with "contains", multiple words, different word forms or typos. A leading wildcard forces a full table scan over billions of rows.
• It's sharded by user_id. A name search would have to hit every shard and merge the results — on every keystroke.
• It has no notion of relevance. Is "Sun" (exact) better than "Sunday_Brunch_Club" (prefix)? Should an account with 10M followers beat your friend with 300? SQL can sort by one column; it can't blend dozens of signals.
• It doesn't understand language. "Café" vs "cafe", "running" vs "run", "#SunsetVibes" vs "sunset vibes", emoji, scripts without spaces (Japanese, Thai)…

The solution is a dedicated Search Service backed by a search index (Elasticsearch in our diagram) that is built from the source-of-truth databases and optimised for one thing: finding the best few documents that match some text, fast.

2. Requirements and numbers

2.1 Functional requirements

• Search users by username and display name (e.g. maya → @maya_travels, "Maya Patel").
• Search hashtags (#sunset, with post counts) and open a hashtag page of top/recent posts.
• Search places (cafés, cities, landmarks), preferring places near the user.
• Typeahead / autocomplete: results update on every keystroke, starting from the first character; recent searches shown on focus.
• Relevant, personalised ranking: people you follow or interact with, and popular/verified accounts, rank higher.
• Respect privacy and safety: blocked users, deactivated accounts and banned hashtags never appear.

2.2 Non-functional requirements

• Latency: typeahead p99 under ~100 ms server-side (users perceive >100–150 ms as lag); full search under ~200 ms.
• Freshness: a new account, renamed username or new hashtag searchable within seconds to a minute — eventual consistency is acceptable.
• Availability: search going down must not affect posting or the feed (it's a separate read path with its own store).
• Scale: billions of documents, hundreds of thousands of queries per second at peak.

2.3 Back-of-the-envelope (assumptions)

Assume 500M DAU, 5 searches/day each           → 2.5B searches/day
Each search ≈ 6 typeahead keystroke requests    → 15B typeahead requests/day
15B / 86,400 s ≈ 175,000 requests/s average     → ~400,000/s at peak
(client-side debouncing and caching typically cut this by 30-50%)

Corpus (assumptions):
  users:    ~2B accounts × ~1 KB of searchable fields   ≈ 2 TB raw
  hashtags: ~1B distinct tags × ~100 B                   ≈ 100 GB raw
  places:   ~200M places × ~500 B                        ≈ 100 GB raw
Index overhead (postings, n-grams, doc values) ≈ 1-3× raw → ~3-6 TB primary data
With 2 replicas → ~10-18 TB across the search cluster

Note the shape: the corpus is moderate (a few TB) but the query rate is enormous and latency-critical. That pushes us toward many replicas, aggressive caching, and keeping hot data in RAM.

3. The inverted index, step by step

A normal (forward) index maps document → words: "user 17's bio contains these words". An inverted index flips it: word → documents. Let's build one by hand.

3.1 A worked example

Take three tiny documents (think of them as post captions or bios):

1. Analyze each document into terms (details in section 4): lowercase, drop stop words (at, the, on), stem (sunsets → sunset, chasing → chase, tacos → taco), keep hashtags and emoji as tokens.
   Doc 1 → sunset, beach, 🌅, #travel · Doc 2 → best, taco, beach · Doc 3 → chase, sunset, daily, #travel
2. Invert: for each term, record the IDs of documents containing it, in sorted order. Optionally store term frequency and positions (for phrase queries like "sunset beach").
3. Sort the terms into a dictionary (Lucene stores it as a compact FST, a finite-state transducer — think of it as a compressed trie) so any term can be located in microseconds.

3.2 Answering queries

Now the query sunsets beach is analysed with the same analyzer → terms sunset, beach. Look up both posting lists:

• AND query (all terms must match): intersect [1, 3] ∩ [1, 2] = [1].
• OR query (any term): union {1, 2, 3}, then rank — Doc 1 matches both terms so it scores highest.
• Phrase query "sunset beach": intersect, then check the stored positions to see whether the words are adjacent. In Doc 1, sunset is at position 0 and beach at position 3 (removed stop words leave gaps), so a strict phrase query does not match, while a phrase query with "slop" 2 (allow up to two positions of movement) does. Analysis choices directly change query results.

Because posting lists are sorted, intersection is a linear two-pointer walk — the same merge idea used in merge sort:

def intersect(a, b):                 # a, b sorted doc-ID lists
    i = j = 0; out = []
    while i < len(a) and j < len(b):
        if a[i] == b[j]: out.append(a[i]); i += 1; j += 1
        elif a[i] < b[j]: i += 1
        else: j += 1
    return out
# Real engines start with the SHORTEST list and use skip pointers to
# leap ahead in the long one: "rare AND common" costs ~ size of the rare list.

3.3 Why it's fast and small

• Lookup is independent of corpus size: finding a term in the dictionary is O(term length); work is proportional to the posting lists touched, not to the number of documents.
• Compression: posting lists store deltas between sorted IDs ([1000, 1003, 1010] → [1000, 3, 7]), packed into a few bits each (Lucene uses block-based bit packing). A posting often costs ~1 byte or less.
• Skip lists / blocks inside each posting list let intersection jump over thousands of IDs at a time.
• Early termination: with algorithms like WAND / block-max WAND, the engine can skip documents that provably can't make the top-k, so a query over a list of millions of postings may score only thousands.
• Doc values / stored fields: beside the inverted index, Lucene keeps column-oriented per-document values (follower_count, verified, location) for fast sorting, filtering and ranking, plus the original source document for display.

4. Text analysis: turning text into terms

Whether a search "finds" something depends entirely on whether the query and document produce the same terms. The component that does this is the analyzer, a pipeline of three stages:

4.1 The standard steps

4.2 Instagram-specific text: usernames, hashtags, emoji, scripts

• Usernames are not prose. maya_travels.2024 should match queries "maya", "travels", "mayatravels" and "maya_tr". So the username field is indexed several ways: the whole lowercase string (exact match), split on _ . digits (word parts), and as edge n-grams for prefixes (section 8). Do not stem usernames — "running_man" is a name, not a verb.
• Hashtags must keep their identity: #SunsetVibes is indexed as the exact tag #sunsetvibes (for hashtag search and the hashtag page) and optionally decomposed into sunset, vibes (camel-case split, or dictionary-based word segmentation for all-lowercase tags like #sunsetvibes) so caption search still matches. A naive tokenizer that strips # would merge hashtags with ordinary words.
• Emoji are real content (🌅, 🍕). Standard tokenizers may drop them; Instagram-style search wants them kept as tokens, and possibly mapped to keywords (🍕 → "pizza"). Watch out for multi-code-point emoji (skin-tone modifiers, ZWJ sequences like 👩‍💻) — treat a whole grapheme cluster as one token.
• Languages without spaces (Chinese, Japanese, Thai) can't be split on whitespace. Use language-specific dictionary tokenizers or character bigrams (each overlapping pair of characters becomes a term). Detect the language per field and pick the analyzer accordingly.
• Transliteration: a user may type "Mumbai" or "मुंबई"; indexing a transliterated form of names helps cross-script matching.

5. Lucene & Elasticsearch architecture

Lucene is a Java library that implements an inverted index on a single machine. Elasticsearch (and its fork OpenSearch, and Solr) wraps Lucene into a distributed system: it splits data across machines, replicates it, routes queries and exposes a JSON/HTTP API. Learn these terms precisely — interviewers love them.

5.1 Writing: routing, translog, refresh and near-real-time search

A document is routed to a primary shard by shard = hash(_routing) % number_of_primary_shards (the routing key defaults to the document ID). This is why the number of primary shards is fixed when the index is created — changing it changes every document's home (it requires a split, shrink or reindex; compare with consistent hashing). The primary indexes the document and forwards it to its replicas.

Inside a shard, Lucene never modifies existing files. New documents go to an in-memory buffer and an append-only translog (a write-ahead log, for durability):

 index request ──► in-memory buffer  +  translog append (fsync'd per request or every few s)
                         │
                         │  REFRESH  (default every 1 s)
                         ▼
               new small segment, opened for search   ──►  document is now SEARCHABLE
               (written to the OS page cache, not yet fsync'd)
                         │
                         │  FLUSH  (periodically, or when the translog grows large)
                         ▼
               segments fsync'd to disk + new commit point; translog trimmed
                         │
                         │  MERGE  (background, continuous)
                         ▼
     many small segments ──► fewer, larger segments; deleted docs physically removed

• Refresh is what makes Elasticsearch near-real-time (NRT): a document becomes searchable about 1 second after indexing, not immediately. You can lengthen the refresh interval (e.g. 30 s during a bulk backfill) to get much higher indexing throughput, because each refresh creates a segment.
• Updates and deletes: since segments are immutable, a delete just sets a bit in a "live docs" bitmap, and an update = delete old version + index new version. Deleted docs still occupy space and are skipped at query time until a merge drops them.
• Merges combine segments (like LSM-tree compaction — see Indexing) to keep the segment count low (each query must visit every segment) and to reclaim space. Merging is I/O-heavy; a heavy write load can make merges fall behind and slow down search.
• Durability comes from the translog: if a node crashes before a flush, the translog is replayed on restart. Replicas protect against losing the node entirely (see Replication).

5.2 Reading: query-then-fetch

1. The coordinating node (any node that receives the request) sends the query to one copy (primary or replica) of every shard of the index — a scatter-gather.
2. Query phase: each shard searches all its segments and returns only its top-k (doc ID, score) pairs. With 20 shards and k = 10, the coordinator receives 200 pairs.
3. The coordinator merges them into the global top 10 (a k-way merge again).
4. Fetch phase: it asks only the shards holding those 10 winners for the actual documents (or just the fields needed), then returns the results.

5.3 Sizing shards and replicas

• Shard size: a common rule of thumb is ~10–50 GB per shard. Too few large shards → slow recovery and limited parallelism; too many tiny shards → per-shard overhead (memory, file handles, cluster state) and wider scatter-gather fan-out.
• Replicas scale reads: each copy can serve queries, so 3 copies of every shard ≈ 3× the query throughput, plus survival of node failures. Writes must be applied to every copy, so replicas cost indexing capacity.
• Separate indices per entity: users, hashtags and places have different sizes, schemas, analyzers and traffic, so they're separate indices with their own shard counts — and can even live on separate clusters for isolation.

6. Document-partitioned vs term-partitioned indexes

There are two fundamentally different ways to split an inverted index across machines (this is sharding applied to search):

 DOCUMENT-partitioned (local index)              TERM-partitioned (global index)
 ┌──────────── Shard A ───────────┐              ┌──────────── Shard A ───────────┐
 │ docs 1-1M: ALL terms           │              │ terms a..m: postings for ALL   │
 │ beach → [3, 77, 902 ...]       │              │ docs: beach → [3,77,...,9.9M]  │
 │ sunset → [5, 77 ...]           │              └────────────────────────────────┘
 └────────────────────────────────┘              ┌──────────── Shard B ───────────┐
 ┌──────────── Shard B ───────────┐              │ terms n..z: postings for ALL   │
 │ docs 1M-2M: ALL terms          │              │ docs: sunset → [5,77,...,9.8M] │
 │ beach → [1000012 ...]          │              └────────────────────────────────┘
 └────────────────────────────────┘
 query "sunset beach" → ask EVERY shard         query "sunset beach" → ask shard A (beach)
 write doc → ONE shard                          and shard B (sunset), ship lists, intersect
                                                write doc → one shard PER TERM it contains

Document partitioning wins in practice because indexing stays simple and load stays balanced; its main cost — every query touches every shard — is managed by keeping the shard count moderate, using replicas, and caching. A useful hybrid is custom routing: if a query is always scoped to one key (e.g. "search within one user's own posts"), route documents by that key so the query touches one shard.

7. The indexing pipeline: Kafka, CDC and eventual consistency

The search index is a derived view of the source-of-truth databases. It must be kept up to date without slowing down or coupling the write path. In our architecture this is the Search Indexer consumer of Kafka.

7.1 Getting changes out of the databases

• Domain events: services publish events like post.created (with its hashtags) or user.renamed to Kafka.
• CDC (change data capture): a connector (e.g. Debezium) tails the database's replication log (PostgreSQL's WAL) and emits every committed row change to Kafka. This captures changes even from code paths that "forgot" to publish an event, and the order matches commit order per row.
• Avoid dual writes. Having the User Service write to PostgreSQL and Elasticsearch directly is fragile: if the second write fails, they diverge forever. CDC or the transactional outbox pattern (write the event into an outbox table in the same DB transaction, then relay it) guarantees every committed change eventually reaches the index (see Message queues).

7.2 The indexer

 User Svc     PostgreSQL     CDC connector     Kafka (user.changes)     Search Indexer        Elasticsearch
    | UPDATE username |            |                    |                       |                     |
    |---------------> | commit     |                    |                       |                     |
    |                 |-- WAL ---->|-- {id:17, username:"maya.t", lsn:9001} -->|                     |
    |                 |            |                    |-- poll batch (500) -->|                     |
    |                 |            |                    |                       | build search docs   |
    |                 |            |                    |                       | (denormalize: follower
    |                 |            |                    |                       |  count, verified...) |
    |                 |            |                    |                       |-- POST _bulk -----> |
    |                 |            |                    |                       |   version=9001      |
    |                 |            |                    |                       |   version_type=     |
    |                 |            |                    |                       |   external          |
    |                 |            |                    |                       |<-- 200 (per-item) --|
    |                 |            |                    |<-- commit offsets ----|                     |
    |                 |            |                    |                       |   ~1 s later: refresh
    |                 |            |                    |                       |   → "maya.t" searchable

• Bulk requests: batching ~1,000 documents (a few MB) per _bulk call is far more efficient than one request per document.
• Idempotency & ordering: Kafka delivers at-least-once and a retry can arrive after a newer update. Using external versioning (the source DB's log sequence number or an updated_at timestamp as the document version) makes Elasticsearch reject stale writes — so replays and reordering are harmless.
• Partition by entity ID in Kafka so all changes to user 17 are processed in order by the same consumer.
• Denormalization: the search document contains what ranking needs (follower_count, verified, is_private, language) so queries never join across services.
• Counters are aggregated, not streamed per event. #love may get thousands of new posts per minute; updating its document on every post would hammer one shard. A stream processor aggregates counts and updates hashtag docs every few minutes.

7.3 Eventual consistency and its user-visible effects

End-to-end lag = CDC delay + Kafka lag + batching + refresh interval — typically 1–10 seconds, longer during incidents. Consequences and fixes:

• "I renamed myself and search still shows the old name" — acceptable for a few seconds. For the user's own profile, the client can show local state (read-your-writes at the UI level; see Consistency models).
• Privacy must not depend on the index being fresh. If a user blocks you or goes private, the Search Service re-checks block/privacy status against the authoritative store (or a fast cache) before returning results — the same "derived view is not the source of truth" rule as in the feed.
• Deletions must flow through too (account deactivated → delete the doc); a periodic reconciliation job compares the index with the DB and fixes drift.

7.4 Reindexing without downtime

Changing a mapping or analyzer requires rebuilding the index. The standard pattern uses an alias (a pointer name that queries use):

1. Create users_v2 with the new mapping. Queries still go to alias users → users_v1.
2. Backfill users_v2 from a database snapshot (a Spark/batch job), recording the Kafka offset at snapshot time.
3. Start a second indexer consumer group writing live changes to users_v2 from that offset (external versioning resolves overlaps).
4. Validate (document counts, sample queries, relevance metrics), then atomically switch the alias users → users_v2. Keep v1 for quick rollback.

8. Relevance: deciding which match is best

Finding matching documents is half the job; the other half is ranking them. For "maya" there may be 2 million matching accounts — the user will look at the top 5.

8.1 TF-IDF: the classic intuition

Two common-sense ideas:

• TF (term frequency): a document that mentions the query term more often is probably more about it.
• IDF (inverse document frequency): rare terms are more informative than common ones. Matching "sunset" means more than matching "photo".

tf-idf(t, d) = tf(t, d) × idf(t)          idf(t) = log( N / df(t) )
   N = number of documents, df(t) = number of documents containing t

Worked example: N = 1,000,000 captions
  "sunset" appears in 1,000 docs    → idf = log10(1,000,000 / 1,000)   = 3.0
  "photo"  appears in 900,000 docs  → idf = log10(1,000,000 / 900,000) ≈ 0.046

Query "sunset photo": a caption that contains "sunset" once scores ~3.0 from that term,
while containing "photo" adds only ~0.05. The rare word dominates — as it should.

Plain TF-IDF has two weaknesses: TF grows without limit (a caption that spams "sunset sunset sunset ×50" wins), and long documents match more terms just by being long.

8.2 BM25: the modern default

BM25 ("Best Matching 25") is the default similarity in Lucene/Elasticsearch. It fixes both problems:

                         f(t,d) · (k1 + 1)
score(d, q) = Σ  IDF(t) · ─────────────────────────────────────────
             t∈q          f(t,d) + k1 · (1 − b + b · |d| / avgdl)

  f(t,d)  = how many times term t occurs in document d
  |d|     = length of d in terms;  avgdl = average document length
  k1 ≈ 1.2  controls TF saturation;  b ≈ 0.75 controls length normalization
  IDF(t)  = ln( 1 + (N − n + 0.5) / (n + 0.5) ),  n = docs containing t

Intuition, using an average-length document (|d| = avgdl, so the length term is 1):

• Saturation (k1): the first occurrence matters most; repeats help less and less — keyword stuffing stops paying off.
• Length normalization (b): a match in a short field (a username, a 5-word bio) counts more than the same match buried in a 300-word caption. With b = 0 length is ignored; with b = 1 it's fully normalised.
• IDF works like TF-IDF's: with N = 1M, a term in 1,000 docs gets IDF ≈ 6.9; a term in 900,000 docs gets ≈ 0.1.

Field boosts refine this further: a match in username is worth more than in full_name, which is worth more than in bio; an exact match ("maya" = @maya) beats a prefix match, which beats a fuzzy match.

8.3 Beyond text: popularity, social and personal signals

For people search, text relevance alone is nearly useless: thousands of accounts are called "maya". What users want is the Maya they mean. Signals:

A practical design is two-stage ranking, the same funnel as the feed:

1. Retrieval: the search engine finds candidates using text match plus cheap static boosts, returning the top ~200–1,000 per index.
2. Re-ranking: the Search Service fetches social and personal features for those candidates (batched) and scores them with a learning-to-rank model (e.g. gradient-boosted trees) trained on clicks: which result did people tap for this query?
3. Blending: results from the users, hashtags and places indices are merged into one list ("Top" tab), using per-type scores calibrated to be comparable, plus rules (e.g. an exact username match always first).

# Elasticsearch-style first stage for user search (simplified)
{
  "query": { "function_score": {
      "query": { "multi_match": {
          "query": "maya",
          "fields": ["username^3", "username.edge^2", "full_name"],
          "type": "best_fields" } },
      "functions": [
        { "field_value_factor": { "field": "follower_count", "modifier": "log1p", "factor": 0.5 } },
        { "filter": { "term": { "verified": true } }, "weight": 1.5 }
      ],
      "boost_mode": "multiply" } },
  "post_filter": { "term": { "is_searchable": true } },
  "size": 200
}

9. Typeahead (autocomplete)

Typeahead is the hardest latency target: a query per keystroke, very short and ambiguous prefixes ("s"), a budget of tens of milliseconds, and results that must feel personal. There are three main tools.

9.1 Tries with top-k at every node

A trie (prefix tree) stores strings character by character; every path from the root spells a prefix. Finding all completions of "su" means walking to the "su" node and exploring its subtree — but the subtree for "s" might contain 50 million terms. The fix: precompute and store the top-k completions at every node. Lookup becomes "walk |prefix| steps, read the list" — O(prefix length), independent of corpus size.

• Memory: storing k = 10 IDs at every node multiplies the size. Assume 100M popular terms with ~8 new nodes each → 800M nodes × 10 × 8 bytes ≈ 64 GB, plus the nodes themselves — fits on a handful of large-memory machines, and is usually sharded by first character(s) of the prefix and replicated.
• Updates: changing a term's score means updating top-k lists on every ancestor node. Real systems rebuild the trie offline (e.g. hourly from query logs and popularity counts) and swap it in atomically, with a small real-time overlay for trending items.
• Compressed tries (radix trees) and FSTs merge chains of single-child nodes to save memory; Elasticsearch's completion suggester is an in-memory FST of exactly this kind.

9.2 Edge n-gram indexes

The alternative that works inside a normal search engine: at index time, emit every prefix of each word as a term. For maya_travels:

edge n-grams (min 1, max 15) of "maya":    m, ma, may, maya
edge n-grams of "travels":                  t, tr, tra, trav, trave, travel, travels

Index time: analyzer = lowercase → split on _ . → edge_ngram
Query time: analyzer = lowercase only   (do NOT n-gram the query!)
Query "trav" → a plain term lookup of "trav" → matches maya_travels

Edge n-grams turn a prefix query into an ordinary, fast term lookup, and the result benefits from all the normal machinery (BM25, filters, function scores, personalization). The cost is a bigger index (each word produces up to ~10 terms) and very long posting lists for 1–2 letter prefixes. (Full n-grams — all substrings, not just prefixes — allow "contains" matching and some typo tolerance but are much larger.)

9.3 Top-k caching for short prefixes

Short prefixes are both the most frequent (every search starts with one letter) and the most expensive (posting lists of millions). But there are only 26 one-letter and ~1,000 common two-letter prefixes per language. So precompute: a batch job computes the global top-k for every prefix up to length 2–3 per country/language and stores it in Redis or in-process memory. Typeahead then becomes:

def typeahead(viewer, prefix):
    prefix = normalize(prefix)                       # lowercase, NFKC, trim
    personal = local_index[viewer].prefix_search(prefix)      # follows, recents (instant)
    if len(prefix) <= 2:
        global_ = topk_cache.get(f"ta:{viewer.country}:{prefix}")   # precomputed
    else:
        global_ = es.search(edge_ngram_query(prefix), size=50, timeout_ms=60)
    return rerank(viewer, dedupe(personal + global_))[:10]

9.4 Client-side tricks (they matter as much as the server)

• Debounce: wait ~50–150 ms after a keystroke before sending, so a fast typist sends 2 requests instead of 6.
• Cancel stale requests: if the user typed "sun" → "suns", drop the "sun" response if it arrives late — otherwise results flicker backwards.
• Client cache and filtering: results for "sun" can be filtered locally to show instant candidates for "suns" while the request is in flight.
• Prefetch the personal index (accounts you follow, recent searches) when the search tab opens.

10. Caching popular queries

Query popularity follows a Zipf-like distribution: a small set of queries (celebrity names, trending hashtags, big cities) accounts for a large share of traffic. That makes caching extremely effective (see Caching):

• Result cache: key = normalised query + type + locale (e.g. sq:users:en-IN:taylor) → top-200 candidate IDs, TTL 1–10 minutes. Hit ratios of 30–60% are plausible for typeahead.
• Cache the non-personal part only. Personalised final results can't be shared between users. So cache the retrieval output (global candidates) and run the cheap personalised re-rank on top per request.
• Elasticsearch's own caches: the node query cache (caches filter bitsets like is_searchable:true), the shard request cache (whole-result cache, invalidated on refresh) and the OS page cache holding segment files — keeping hot segments in RAM is the biggest performance lever.
• Negative caching: cache "no results" for gibberish queries briefly to absorb bots.
• Invalidation: short TTLs are usually enough (search is eventually consistent anyway); safety-critical removals (banned hashtag, deleted account) are enforced by a post-filter at serve time, not by the cache.

11. Geo search for places

For places, "relevant" mostly means near me and popular. Typing "starb" in Mumbai should show Starbucks branches in Mumbai, not Seattle. We need to answer "places matching X within ~5 km of (lat, lon)" quickly.

11.1 Geohash

A geohash encodes a latitude/longitude into a short string by repeatedly halving the world: the first bit says east or west half (longitude), the next says north or south half (latitude), and so on, alternating. Every 5 bits become one base-32 character. Each extra character makes the cell ~32× smaller in area, and points that share a prefix are in the same cell, so proximity becomes a prefix match — which inverted indexes and B-trees are great at.

 Worked example (Mumbai)
   Gateway of India      (18.9220, 72.8347) → te7g9kss
   CST railway station   (18.9400, 72.8350) → te7g9ruv   shares "te7g9" → same ~5 km cell
   Colaba, west side     (18.9067, 72.8147) → te7g8cy5   only ~3 km away, but shares just "te7g"
                                                          (it sits in the cell to the WEST)

   Real neighbours of cell te7g9 (precision 5):    ┌───────┬───────┬───────┐
   a point near a cell EDGE can be 50 m from a      │ te7gb │ te7gc │ te7gf │   N
   point in the next cell with a different prefix → ├───────┼───────┼───────┤
   so always search the cell AND its 8 neighbours   │ te7g8 │*te7g9*│ te7gd │
                                                    ├───────┼───────┼───────┤
                                                    │ te7g2 │ te7g3 │ te7g6 │   S
                                                    └───────┴───────┴───────┘
                                                       W                 E

Notice that the neighbours' last characters (b, c, f, 8, d, 2, 3, 6) don't follow alphabetical order: geohash cells are laid out along a zig-zag Z-order curve, so neighbours are computed with a small lookup algorithm (every geo library has one), never by incrementing characters.

11.2 Running a place query

1. Compute the user's geohash at a precision matching the search radius (5 chars ≈ 5 km), plus its 8 neighbours.
2. Filter place documents whose geohash starts with any of those 9 prefixes (cheap term/prefix filters), and whose name matches the text (edge n-grams for typeahead).
3. Compute exact distances for the survivors and score: text match × popularity (check-ins, tagged posts) × a distance decay function (e.g. Gaussian: full score within 1 km, half at 5 km).
4. If too few results, widen to precision 4 (city) and then drop the geo filter entirely ("Starbucks Reserve Roastery, Seattle" is still a valid answer if nothing is nearby).

# Elasticsearch has this built in: geo_point fields are indexed with BKD trees,
# and a distance decay can be applied inside function_score.
{ "query": { "function_score": {
    "query": { "bool": {
        "must":   { "match": { "name.edge": "starb" } },
        "filter": { "geo_distance": { "distance": "10km", "location": { "lat": 18.92, "lon": 72.83 } } } } },
    "functions": [
      { "gauss": { "location": { "origin": "18.92,72.83", "scale": "2km" } } },
      { "field_value_factor": { "field": "checkins", "modifier": "log1p" } } ] } } }

Alternatives to geohash: quadtrees (adaptive cells — small where places are dense, big where sparse), Google's S2 cells (on a sphere, fewer edge distortions) and Uber's hexagonal H3 (equal-distance neighbours). All share the idea: map 2-D space onto 1-D cell IDs so standard indexes can search it.

12. Search vs Explore: retrieval vs recommendation

Instagram has a search bar and an Explore grid on the same tab, but they are different systems:

They do converge: search ranking uses ML (learning to rank), and "keyword search for posts" (searching captions/topics) blends retrieval with recommendation — the hashtag page's "Top posts" are ranked with engagement models. But in an interview, keep them separate: search is pull with intent; Explore is push without a query.

13. Scaling search: putting numbers on it

Let's size the cluster for the assumptions in section 2.3 (all numbers are illustrative):

Data: ~4 TB of primary index (users ~3 TB with n-grams, hashtags ~0.5 TB, places ~0.5 TB)
Shard size target ~30 GB → users: ~100 primary shards; hashtags/places: ~16 each

Query load: ~400k typeahead req/s at peak
  − client debouncing & caches (~40%)           → ~240k req/s reach the Search Service
  − precomputed short-prefix & result caches (~50%) → ~120k req/s reach Elasticsearch
  Each request fans out to every shard of the index queried (scatter-gather)

Assume one shard copy handles ~500 simple queries/s with data in RAM
  users index: 120k q/s needs 120k / 500 = 240 copies of EVERY shard?  ✗ far too many
  → this is why typeahead is NOT a 100-shard scatter-gather:
     • short prefixes are served from precomputed top-k caches
     • a dedicated small "typeahead" index holds only the ~50M most searchable
       accounts (2-4 shards, fully in RAM), with ~20-40 replicas across regions
     • the full 100-shard users index serves only "see all results" queries

This calculation reveals the key scaling insights:

• Replicas scale queries; shards scale data. The number of shards should be as small as the data allows, because every extra shard multiplies query fan-out and tail latency.
• Tier the index by popularity. A small hot index of the most-searched entities (in RAM, many replicas) answers most typeahead queries; the long-tail full index answers the rest.
• Keep the working set in memory. Search latency collapses when segments must be read from disk; size nodes so hot indices fit in the OS page cache.
• Isolate workloads: indexing (heavy writes, merges) and querying compete for CPU and I/O; separate clusters per entity type or per region contain blast radius.
• Multi-region: each region runs its own search clusters fed by the same Kafka streams (replicated cross-region), so queries are served locally (see Multi-region).
• Protect the cluster: per-request timeouts with partial results (timeout + allow_partial_search_results), rate limiting of scrapers, and rejecting pathological queries (huge wildcards, regexes).

14. How Instagram uses search

1. When you open the search tab, the app shows recent searches and preloads a small personal index (accounts you interact with).
2. As you type, debounced requests go through the API Gateway to the Search Service, which queries the users, hashtags and places indices in parallel (short prefixes hit precomputed caches).
3. Candidates are re-ranked with social signals from the Follow/Graph Service and personal history, filtered for blocks, privacy and policy, and blended into the "Top" list; tabs (Accounts, Tags, Places) show per-type lists.
4. Every change that affects search — new account, rename, new post with hashtags, new place tag — flows through Kafka to the Search Indexer and into Elasticsearch within seconds.
5. Taps and query logs flow to Analytics & ML to train the ranking model and rebuild typeahead top-k lists.

15. Trade-offs & common pitfalls

Common pitfalls

• Using the search index as the source of truth — it's a derived, eventually consistent view; always be able to rebuild it from the DB + Kafka.
• Mismatched analyzers at index vs query time (e.g. n-gramming the query) → zero or garbage results.
• Stemming or stop-wording names — usernames and hashtags need exact and prefix handling, not English grammar.
• Too many shards "for future growth" — every query pays the scatter-gather cost today.
• Dual writes from the application to DB and index — silent divergence. Use CDC or an outbox.
• Per-event updates of hot counters (hashtag counts) — creates hot documents and merge storms; aggregate first.
• Deep pagination with from/size — use search_after cursors.
• Relying on the index for privacy — re-check blocks and visibility at serve time.
• No client debouncing — doubles or triples typeahead load for no user benefit.

16. Real-world technologies

17. Interview corner

18. Check your understanding

Related lessons

• Database Indexing & Storage Engines — B-trees vs LSM-trees; segments and merges are LSM ideas
• Message Queues & Kafka — the event stream and CDC that feed the indexer
• Sharding — document vs term partitioning is sharding applied to search
• Replication — how replicas provide failover and read throughput
• Caching — query result caches, top-k caches and hot keys
• Social Graph — the follow edges used to personalise people search
• Analytics & ML Ranking — learning-to-rank models and the Explore recommendation system
• CAP & Consistency Models — why an eventually consistent index is acceptable
• End-to-End Request Flows — a search request traced through the whole architecture