Why code search can’t just be grep

Before explaining how GitHub’s new code search works, it’s worth addressing the most common question: why not just use grep? The math doesn’t support it. At the time of the public beta, the index covers roughly 45 million repositories, 115 TB of code, and 15.5 billion documents. A single eight-core machine running ripgrep can scan about 0.6 GB/sec/core for an exhaustive regular expression query. Even if that entire corpus were cached in memory and perfectly parallelized across 64-core, 32-machine clusters, one query would saturate all 2,048 cores for about 96 seconds. That yields roughly 0.01 queries per second—useless for a multi-tenant service.

This is why the team built Blackbird, a custom search engine written in Rust specifically for code. General-purpose text search engines have repeatedly failed here: indexing was too slow (months for ~8 million repositories in an early Elasticsearch deployment), and the query model doesn’t fit code. Code search needs to handle punctuation, regular expressions, and exact matches without stemming or stop-word removal. Nothing off the shelf handled GitHub’s scale and constraints, so the engineering team started from scratch.

The indexing foundation

Search engines trade pre-computation for query speed. The core data structure is an inverted index: a map from a key (like a language or token) to a sorted posting list of document IDs. A forward index stores the original documents; the inverted index reverses that mapping so lookups are fast.

Code search needs a special variant: an ngram index. An ngram is a contiguous sequence of n characters. With trigrams (n=3), the string limits produces lim, imi, mit, and its. To find documents containing limits, the engine intersects the posting lists for each of those four trigrams.

These posting lists are far too large to hold entirely in memory. Instead, Blackbird builds lazy iterators that return document IDs in sorted order—sorted by a precomputed relevance score, with higher-ranked documents getting lower IDs. Queries intersect and union these iterators, reading only as far as needed to fetch the requested number of results.

Two insights that shaped the architecture

Indexing 45 million repositories would be impossibly slow without exploiting two properties of the data. First, Git uses content-addressable storage with blob object IDs that uniquely identify file content. Second, GitHub hosts enormous amounts of duplicated content across repositories.

These observations drive two architectural decisions:

  • Shard by Git blob object ID. This distributes documents evenly across shards with no duplication, avoids hot shards from popular repositories, and scales horizontally by adding shards.
  • Model the index as a tree with delta encoding. Instead of storing full metadata (paths, branches, repository names, owners) with every document, the index stores deltas relative to a parent. This dramatically reduces crawling work and metadata volume, especially for widely copied content.

The tree model also gives commit-level consistency during incremental updates: each shard consumes a single Kafka partition in message order. A search query sees documents only up to the point the shard has fully processed—no partial results from a concurrent git push. Different shards may be at different points, but every response is internally consistent.

Inside the ingestion pipeline

Blackbird’s indexing side is event-driven. Kafka events signal what to crawl (typically triggered by git push); crawlers fetch blob content from Git, extract symbols, and produce documents that flow back into Kafka. Each shard consumes its own partition, so crawling and indexing stay decoupled and each shard proceeds at its own pace.

For the initial ingest of 45 million repositories, the system optimizes order using a novel probabilistic data structure that estimates repository similarity. Thinking of repositories as nodes in a graph, the ingest order follows a level-order traversal of a minimum spanning tree of that similarity graph. Each repository is then crawled by diffing against its parent in the tree—only blobs unique to that repository are fetched, not the whole tree.

Shards tokenize documents to build ngram indices for content, symbols, and paths, along with other indices for languages, owners, and repositories. Instead of flushing every small batch, the system accumulates and compacts indices in a k-way merge that re-sorts posting lists by score, ensuring relevant documents get lower IDs and are returned first by the lazy iterators. During initial ingest, compaction is deferred to one large final pass; under steady-state incremental load, it runs on shorter intervals and also handles document deletions.

Following a Query Through the System

To see how the index pays off, consider a regular expression scoped to the Rails organization and the Ruby language: /arguments?/ org:rails lang:Ruby. A coordinating service sits between the GitHub.com front end and the individual index shards, handling query fan-out, Redis-backed quotas, and cached access-control data.

Architecture diagram of a query path.

The front end passes the user's query to the Blackbird query service, which parses it into an abstract syntax tree. Rewriting resolves languages to canonical Linguist language IDs and appends clauses for permissions and scopes, ensuring users only see results from public repositories or their own private ones.

And(
    Owner("rails"),
    LanguageID(326),
    Regex("arguments?"),
    Or(
        RepoIDs(...),
        PublicRepo(),
    ),
)

Because of the sharding strategy, the query fans out as n concurrent requests — one to each shard in the cluster. Each shard performs its own query conversion, translating the regex into a set of substring lookups on the ngram indices. In this example, the engine produces the grams arg, rgu, gum, and then either ume plus ment or the six-gram uments.

and(
  owners_iter("rails"),
  languages_iter(326),
  or(
    and(
      content_grams_iter("arg"),
      content_grams_iter("rgu"),
      content_grams_iter("gum"),
      or(
        and(
         content_grams_iter("ume"),
         content_grams_iter("ment")
        )
        content_grams_iter("uments"),
      )
    ),
    or(paths_grams_iter…)
    or(symbols_grams_iter…)
  ), 
  …
)

The approach of reducing regular expressions to substring queries is covered in Russ Cox's article on Regular Expression Matching with a Trigram Index. Blackbird uses a different algorithm with dynamic gram sizes rather than fixed trigrams. Once the shard runs the iterators — and intersects, or unions — it gets a candidate document list. Each document must then be fetched and checked to validate matches and locate ranges before scoring, sorting, and returning results.

Back at the query service, results from all shards are aggregated, re-sorted by score, filtered for permission double-checks, and the top 100 are returned. The front end then handles syntax highlighting, term highlighting, and pagination before rendering the page.

Shard-level p99 response times run around 100 ms, with total response times slightly longer due to aggregation, permission checks, and highlighting. Each query occupies a single CPU core for that 100 ms, putting a 64-core host's practical ceiling at roughly 640 queries per second. Compared to the grep-based approach measured at 0.01 QPS, the difference is several orders of magnitude.

Index Size and Ingest Efficiency

The pipeline can publish about 120,000 documents per second. At that rate, processing the full 15.5 billion documents would take around 36 hours, but delta indexing cuts the crawl volume by more than half, bringing a complete corpus re-index down to roughly 18 hours.

The storage savings are just as significant. The source material starts at 115 TB; content deduplication and delta indexing reduce that to about 28 TB of unique content. The complete index — including ngram indexes and a compressed copy of all unique content — totals just 25 TB, or about a quarter of the original data size.

An interesting wrinkle in the shard design is the use of sparse grams. At GitHub's scale, trigrams on common sequences like for generate far too many false positives — documents containing each trigram separately but not in the expected proximity. Checking those requires fetching and validating each candidate document, wasting significant work. Follow masks (bitmasks for the character following a trigram) saturated too quickly to help.

Sparse grams solve the problem by weighting each bigram in a string and tokenizing at intervals where inner weights are strictly lower than the border weights. The inclusive characters form the ngram, with recursion proceeding until reaching trigrams naturally. Query time applies the same algorithm but keeps only the covering ngrams, since the rest are redundant.

Determining the optimal delta-encoding ingest order relies on a custom data structure called a geometric filter. Similar to MinHash and HyperLogLog, it computes set similarity and symmetric differences in logarithmic space, applied here to each repository's (path, blob_sha) tuples. The resulting repository graph — with millions of vertices and trillions of edges — gets an approximate minimum spanning tree calculated in minutes, still capturing roughly 90% of the delta compression benefits.