How GitHub searches 200M+ repositories in milliseconds

The Problem Statement

Interviewer: "GitHub lets you search across 200 million repositories and billions of source files. When a developer types func handleRequest and hits enter, results come back in under a second. How does that work? Walk me through the indexing and query pipeline."

This question tests three things: your understanding of search index data structures (inverted indexes, trigram indexes), your ability to reason about scale (petabytes of source code, billions of documents), and whether you appreciate the difference between searching natural language text and searching code (regex support, symbol awareness, exact-match semantics).

Most candidates describe Elasticsearch and stop there. Strong candidates explain why general-purpose text search engines are a poor fit for code, how trigram indexes enable substring and regex matching, and how the index is kept fresh as millions of pushes happen every day.

Clarifying the Scenario

You: "Before I dive in, I want to clarify the scope."

You: "When you say 'code search,' are we talking about searching file contents (the actual source code), or also searching repository names, issues, pull requests, and commit messages?"

Interviewer: "Focus on source code search. Searching file contents across all repos."

You: "Got it. Should I also cover regex search? GitHub supports regex patterns in code search."

Interviewer: "Yes, that is an important capability."

You: "And should I assume we need to keep the index fresh? Developers push code constantly, so the index needs to reflect recent changes."

Interviewer: "Absolutely. Stale results would be a terrible user experience."

You: "OK, I will structure my answer in three parts: how the search index is built (the indexing pipeline), how a query is executed against the index (the query pipeline), and how the index stays fresh as new code is pushed (incremental updates)."

My Approach

I break this into five parts:

1. Why traditional search fails for code: Why Elasticsearch or Lucene-style full-text search is not sufficient for code search
2. Trigram indexing: How breaking code into 3-character sequences enables substring and regex search
3. The Blackbird engine: GitHub's custom Rust-based search engine (announced 2023) and its architecture
4. Sharded index architecture: How petabytes of code are distributed across search shards
5. Incremental index updates: How git pushes trigger index updates without rebuilding the entire index

The mental model I use: code search is fundamentally different from web search. Google indexes web pages and ranks them by relevance using PageRank. Code search indexes source files and must support exact substring matching, regex patterns, language-aware filtering, and repository scoping. These requirements disqualify most off-the-shelf search engines and demand a purpose-built solution.

The scale numbers drive every architectural decision. 200M+ repositories. Over 15 billion files. Petabytes of raw source code. Millions of git pushes per day that change the index. We cannot re-index everything on every push, we cannot store the full index on a single machine, and we cannot scan every file on every query. Everything must be pre-computed and distributed.

The Architecture

The code search system has four major layers: the ingestion pipeline (processing git pushes into indexable documents), the indexing pipeline (building trigram and metadata indexes), the search cluster (distributed query execution), and the API layer (parsing queries, merging results, ranking).

Here is the query lifecycle through the search stack:

Step 1: Developer submits a query. The developer types func handleRequest lang:go in the GitHub search bar. The UI sends this to the query parser.

Step 2: Query parser extracts trigrams and filters. The parser breaks the search string into trigrams: fun, unc, nc , c h, ha, han, and, ndl, dle, leR, eRe, Req, equ, que, ues, est. It also extracts the language filter (lang:go) and generates a query plan.

Step 3: Fan-out to search shards. The query is sent to all shards in parallel. Each shard searches its local trigram index for files that contain all the required trigrams (an AND operation across posting lists).

Step 4: Shard-local filtering. Each shard takes the candidate files from the trigram intersection and performs a full-text verification (checking that the actual string func handleRequest exists, not just the individual trigrams). It also applies the language filter. This filtering step is fast because the trigram intersection has already narrowed candidates from billions of files to thousands.

Step 5: Result aggregation. The aggregator collects results from all shards, deduplicates (forks of the same repo), ranks by relevance (repo stars, file path match, recency), and returns the top results.

For your interview: mention that the query is fan-out/gather across all shards. This is the same pattern used by distributed databases (scatter-gather) and web search engines (Google, Bing). It shows you understand distributed query execution.

Trigram Indexing for Code Search

This is the core data structure that makes code search possible. A trigram is a sequence of 3 consecutive characters in a string. The word handler produces the trigrams: han, and, ndl, dle, ler. The index maps each trigram to a list of files (posting list) that contain it.

When searching for handleRequest, the system extracts all trigrams from the query, looks up the posting list for each trigram, and intersects them. Only files that contain ALL trigrams are candidates. This intersection is extremely selective: even though each individual trigram appears in millions of files, combining 13 trigrams narrows the result to a handful of matching files.

Why trigrams instead of word-based indexing?

Traditional search engines tokenize text into words. The sentence "user clicked the button" becomes the tokens [user, clicked, the, button]. This works for natural language because people search for words. But code is different.

Developers search for substrings: handleReq, Request, equest. They search for symbols that are not words: fmt.Printf, __init__, std::vector. They search with regex: handle[A-Z]\w+. Word-based tokenization cannot support any of these patterns because it splits on whitespace and punctuation, destroying the structure engineers search for.

Trigrams solve this because they index every 3-character window, regardless of word boundaries. The substring equest matches any string containing the trigrams equ, que, ues, est, which includes Request, handleRequest, requestHandler, and any other string containing that substring. No word-boundary assumptions, no language-specific tokenization.

How regex search works on trigrams

This is the part that surprises most candidates. GitHub supports regex in code search (e.g., handle[A-Z]\w+Request). How does regex work on a trigram index?

The system converts the regex into a set of required trigrams. For handle[A-Z]\w+Request:

• The prefix handle produces mandatory trigrams: han, and, ndl, dle
• The suffix Request produces mandatory trigrams: Req, equ, que, ues, est
• The middle [A-Z]\w+ is a wildcard, so no mandatory trigrams can be extracted from it

The system intersects the mandatory trigrams to get candidates, then runs the full regex against each candidate file. Regexes that have no extractable trigrams (like .*) fall back to a full scan of a subset of files, which is much slower and may be limited by timeout.

I have seen candidates confuse trigram-based regex with running a regex engine over the entire corpus. The key insight is that trigrams act as a pre-filter: they eliminate 99.99% of files before the regex engine ever runs.

Index size and compression

The raw trigram index for 200M+ repositories would be enormous without compression. There are roughly 17,576 possible case-sensitive trigrams (26+26+10 characters cubed for alphanumeric, more including symbols). Each trigram's posting list can contain billions of file references.

GitHub uses several techniques to manage index size:

• Delta encoding: Posting lists store file IDs as deltas from the previous entry, which are small numbers that compress well.
• Varint encoding: Small integers use fewer bytes (1 byte for values under 128, 2 bytes for values under 16,384).
• Roaring bitmaps: For very common trigrams (like the which appears in virtually every file), bitmap representations are more compact than sorted lists.
• Content deduplication: Files that appear identically across multiple forks are indexed once and referenced by content hash (git blob SHA). This eliminates massive redundancy: popular libraries like lodash or react exist in millions of repos but have identical content.

My estimate: the compressed trigram index for all of GitHub is roughly 200-400TB. Large, but distributable across a few hundred search shards with commodity SSDs.

Sharded Search Architecture

No single machine can hold the full index. The search cluster distributes the index across many shards, with each shard holding a portion of the total data. The sharding strategy and query routing determine the system's latency, throughput, and availability.

Sharding strategy

The index is sharded by repository. All files from a single repository live on the same shard. This means a query scoped to a single repo (repo:facebook/react func) can be answered by one shard without fan-out. Unscoped queries require fan-out to all shards.

Why shard by repository instead of by file? Two reasons. First, repository-scoped queries are very common (developers searching within their own project), and single-shard queries are fast. Second, incremental updates happen at the repository level (a git push changes files within one repo), so updates only touch one shard.

The fan-out/gather pattern

For unscoped queries, the query router sends the query to every shard in parallel. Each shard returns its top N results (typically 100). The aggregator merges and re-ranks the combined results, deduplicates forks, and returns the final top N to the user.

The critical metric is tail latency. If one shard is slow (garbage collection pause, disk contention), the entire query waits for it. To mitigate this:

• Hedged requests: Send the query to both the primary and replica of each shard group. Use whichever responds first.
• Timeout with partial results: If a shard does not respond within 500ms, return results from the other shards with a note that results may be incomplete.
• Shard health monitoring: Route traffic away from slow shards and toward replicas.

Incremental Index Updates on Push

The index must stay fresh. Developers expect that code pushed minutes ago is searchable. But re-indexing 200M+ repositories on every push is impossible. The system must process incremental updates efficiently.

GitHub receives millions of git pushes per day. Each push changes a handful of files in one repository. The challenge is computing what changed, updating only the affected posting lists, and serving the new index without downtime.

The update pipeline

1. Push event arrives. A developer pushes commits to a repo. The git storage layer emits a push event containing the old and new commit SHAs.
2. Diff computation. An index worker computes the diff between the old and new tree objects. This gives the set of files added, modified, and deleted. Git's tree diffing is efficient because it compares SHA hashes at each directory level, skipping unchanged subtrees.
3. Trigram delta computation. For each changed file, compute the trigrams of the new version and the trigrams of the old version. The delta is: new trigrams to add to posting lists, and old trigrams to remove.
4. Posting list update. Apply the delta to the shard that owns this repository. Add the file to new trigram posting lists, remove it from old ones. This is a set of append and delete operations on sorted lists.
5. Index compaction. Over time, posting lists accumulate tombstones (deleted entries). A background compaction process rebuilds posting lists periodically, removing tombstones and re-compressing.

Handling the backlog

During peak hours, the push event queue can have millions of events waiting. The system must process them fast enough to keep the index fresh (target: under 2 minutes from push to searchable).

The solution is horizontal scaling of index workers. Each worker processes events independently (they are partitioned by repository, so two workers never update the same shard simultaneously). If the queue grows, spin up more workers. If a worker crashes, the event is retried from the queue.

Content-addressable deduplication

A critical optimization for both index size and update speed: content-addressable storage. Git already stores files by content hash (blob SHA). If two repositories contain the exact same file (e.g., a popular library's index.js), they share the same blob SHA.

The search index can exploit this. Instead of indexing the same content twice, index it once by blob SHA and reference it from every repository that contains it. When a push lands and a file's blob SHA already exists in the index, skip trigram computation entirely. Just add the repository reference to the existing posting list entry.

This optimization is massive for popular open-source libraries that exist in millions of forks. The README.md of a popular project might exist identically in 50,000 forks. Without deduplication, that is 50,000 redundant index entries. With deduplication, it is one entry with 50,000 repository references.

The Tricky Parts

1. Short queries produce too many results. A search for get matches virtually every codebase in existence. The trigram get appears in billions of files. The system needs aggressive result limiting: stop after finding the first 1,000 matches, apply ranking to surface the most relevant, and encourage the user to add filters (language, repo, org) to narrow results.

2. Binary files and generated code. The index should not include minified JavaScript (one giant line of unreadable code), compiled binaries, or generated protobuf files. GitHub uses heuristics (file extension, entropy analysis, line-length analysis) to detect and exclude these files. The open-source library linguist (used by GitHub) classifies files and identifies generated content.

3. Fork explosion. A popular repository with 100,000 forks multiplies the search space by 100,000x if each fork is indexed independently. GitHub deduplicates results from forks, showing only the original repository's result by default. Users can opt in to searching forks explicitly.

4. Case sensitivity. Code search must support both case-sensitive and case-insensitive queries. The index stores trigrams in their original case. For case-insensitive search, the system generates all case variants of each trigram and unions the posting lists. For Han, the case-insensitive variants are han, haN, hAn, hAN, Han, HaN, HAn, HAN, which is 8 posting list lookups per trigram instead of 1.

5. Hot queries and caching. Popular queries (like TODO, FIXME, or trending library names) hit the search cluster thousands of times per hour. A query cache in front of the search cluster stores recent results with a short TTL (60 seconds). Since the index is updated continuously, the TTL must be short enough to avoid returning stale results but long enough to absorb bursts.

What Most People Get Wrong

How I Would Communicate This in an Interview

Here is how I would actually say this:

"GitHub code search needs to find exact substrings and regex patterns across 200M+ repos and billions of files. Traditional text search engines like Elasticsearch use word-based tokenization, which breaks code patterns like camelCase identifiers and symbol names. So GitHub built a custom search engine called Blackbird, written in Rust.

The core data structure is a trigram index. Every source file is broken into 3-character sequences, and an inverted index maps each trigram to the list of files containing it. When I search for handleRequest, the system extracts all trigrams from my query, intersects the posting lists, and gets a small set of candidate files. Then it verifies each candidate with a full-text substring check.

The index is way too large for one machine, so it is sharded by repository across hundreds of search nodes. Unscoped queries fan out to all shards in parallel and merge results. Repo-scoped queries hit a single shard, which is the fast path for the most common use case.

For freshness, the system processes git push events incrementally. It computes the tree-level diff to find changed files, calculates trigram deltas for those files, and applies delta updates to the affected shard. Content-addressable deduplication by blob SHA means identical files across forks are indexed only once.

The result ranking considers repo stars, file path relevance, language match, and recency. Regex queries work by extracting mandatory trigrams from the regex pattern, using them to find candidates, then running the full regex against candidates."

Interview Cheat Sheet

• "Why not Elasticsearch?" → Word-based tokenization breaks code; trigrams support substring and regex matching
• "What is a trigram index?" → Map every 3-character sequence to a posting list of files; intersect posting lists to find candidates
• "How does regex work?" → Extract mandatory literal trigrams from the regex, intersect posting lists, run full regex on candidates
• "How is the index sharded?" → By repository; single-repo queries hit one shard, cross-repo queries fan out to all
• "How does it stay fresh?" → Git push events trigger tree-level diffs, trigram deltas applied incrementally to affected shard
• "What about forks?" → Content-addressable dedup by blob SHA; identical files indexed once, results deduplicated
• "How do you handle hot queries?" → Query cache with short TTL (60s); hedged requests to replicas for tail latency
• "What about ranking?" → Repo popularity (stars), file path relevance, language match, recency of last commit
• "Scale numbers?" → 200M+ repos, 15B+ files, petabytes of source, hundreds of search shards, thousands of queries/sec
• "What is Blackbird?" → GitHub's custom Rust-based code search engine, replaced Elasticsearch-based search in 2023

Test Your Understanding

---

---

---

---

---

---

---

Quick Recap

1. GitHub code search uses trigram indexes (3-character sequences) instead of word-based tokenization because code requires substring and regex matching.
2. The Blackbird engine, written in Rust, replaced an Elasticsearch-based system that could only search one repo at a time.
3. The index is sharded by repository across hundreds of nodes; unscoped queries fan out to all shards in parallel.
4. Regex queries work by extracting mandatory trigrams from the pattern, intersecting posting lists, then running the full regex on candidates.
5. Incremental updates process git push events by computing tree-level diffs and applying trigram deltas to the affected shard.
6. Content-addressable deduplication by blob SHA ensures identical files across forks are indexed only once, dramatically reducing index size.
7. Results are ranked by repository popularity, file path relevance, language match, and recency to surface the most useful matches.
8. Query-time optimizations include hedged requests to replicas, query caching with short TTL, and early termination for broad queries.

Related Concepts

• Inverted indexes for full-text search: Trigram indexes are a specialized form of inverted index. Understanding how Lucene/Elasticsearch builds and queries inverted indexes provides the foundation for trigram index internals.
• Consistent hashing for shard distribution: The shard assignment of repositories uses consistent hashing to minimize data movement when shards are added or removed from the cluster.
• Write-ahead logging for crash recovery: The atomic delta update mechanism uses WAL principles. Understanding WAL from database internals helps reason about the durability and consistency guarantees of index updates.
• Fan-out/gather query pattern: The scatter-gather pattern used for cross-shard queries is the same pattern used by distributed databases (CockroachDB, Vitess) and web search engines.
• Content-addressable storage: Git's blob SHA model is a form of content-addressable storage. The same principle powers systems like IPFS and Docker image layers.