Engineering Atlas › System Design Interviews

Design code search across repositories

19 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

Requirements

Functional

Non-functional

Out of scope

Back-of-envelope

Assume a hosting service with 50M indexed repositories. The sizes below are round figures I chose for the arithmetic, and the corpus shape follows what GitHub published for its beta, about 45M repositories, 115 TB of code and 15.5B documents, of which only about 28 TB was unique after deduplication (GitHub Engineering).

API

POST /v1/search
{ "q": "class\\s+\\w+Handler", "mode": "regex",       // "literal" or "regex"
  "filters": { "org": "acme", "lang": ["Go"], "path": "internal/**", "repo": null },
  "page_size": 50, "cursor": null, "timeout_ms": 2000 }

200 { "results": [ { "repo": "acme/api", "path": "internal/http/handler.go", "blob": "9f1c...",
                     "score": 12.7, "lines": [ { "n": 41, "text": "...", "ranges": [[6, 20]] } ] } ],
      "next_cursor": "opaque", "partial": false, "shards_failed": 0,
      "index_lag_ms": 3400 }
422 { "error": "query_too_broad", "hint": "add a literal of 3+ characters or a repo/org filter" }
GET  /v1/blob/{blob_id}?repo=acme/api&path=...       # file view, permission checked
POST /internal/events/push   { repo_id, before_sha, after_sha, ref }   # from the Git service

partial and shards_failed make a degraded answer visible to the caller instead of silently incomplete. index_lag_ms lets a client explain "your commit is not indexed yet".

Data model

High-level design

flowchart LR
  G["Git service"] -->|push event| K["Event log"]
  K --> C["Crawler / differ"]
  C -->|new blobs| B["Blob store"]
  C -->|blob ids by shard| K2["Per-shard queues"]
  K2 --> I["Shard indexer (segments)"]
  I --> S["Shard replicas (SSD, mmap)"]
  U["Client"] --> Q["Query service"]
  Q --> P["Planner: regex to n-gram plan"]
  Q --> A["Access service + cache"]
  Q -->|fan out| S
  S -->|top hits| Q
  Q -->|merge, re-filter| U

Write path. The Git service emits a push event to an ordered log. The differ compares before_sha and after_sha, lists added, changed and deleted paths, and keeps only blob ids the system has not seen. New blobs are written to the content-addressed store and routed to their shard by hash(blob_id). The shard indexer builds an immutable segment of the new documents, appends tombstones for removed (repo, path) references, and publishes it to the replicas. A repository state row records the indexed_sha once the shards that care have acknowledged.

Read path. The query service parses the request, plans the regex into an n-gram boolean expression, and asks the access service for the caller's readable repositories. It rewrites the query to carry the permission clause, sends it to one replica of every shard, and each shard intersects posting lists, verifies candidates against stored content and returns its top hits by score. The query service merges the lists, re-checks permissions on the survivors, builds snippets and returns a page.

Deep dives

1. The index and the query planner

Options. Word-level inverted indexes, as in Lucene, split text at word boundaries, so they cannot answer ndl inside handler, or punctuation such as ->. Word indexes do use k-grams for wildcards (Stanford IR book), but only over dictionary terms. A suffix array over the whole corpus answers any substring directly, and livegrep runs RE2 on the candidate regions it finds (Nelhage), but a suffix array needs several bytes per input byte, which hurts at 30 TB and is awkward to update. Trigram posting lists sit between: Cox found 2-grams too unselective and 4-grams too numerous (Cox).

Choice. Trigram posting lists per shard, with positions only where they pay for themselves. Zoekt keeps positional trigrams and checks that two rare ones sit at the right distance, at about 3x corpus size (Zoekt design). GitHub's engine also builds n-gram indexes (trigrams in its worked example) separately for content, symbols and paths (GitHub Engineering). Variable-length keys that make common text rarer are a possible refinement, not something I rely on here.

The planner is the hard part. A literal limits becomes lim AND imi AND mit AND its. A regex is analysed bottom-up for the strings, prefixes and suffixes any match must contain; Google.Search becomes the AND of the trigrams of both words, and a set of alternatives becomes an OR (Cox). Case-insensitive search multiplies alternatives, and . yields no constraint at all. The planner must therefore return a plan with an estimated cost: intersect the rarest lists first, use document-frequency statistics to estimate candidates, and when the plan is ANY, reject the query unless filters narrow it to a bounded number of repositories. Return query_too_broad rather than burning a thousand cores.

Verification. Check candidates with a linear-time engine such as RE2, never a backtracking one, so a user pattern cannot run in exponential time.

2. Sharding and incremental reindex

Options. (a) Shard by repository: filters can skip shards, but big repositories create skew and forks are indexed repeatedly. (b) Shard by blob id: even load and one copy of each distinct file, but every query touches every shard.

Choice. Shard by hash(blob_id). GitHub made the same choice, keying shards by Git blob object id to spread documents evenly and avoid hot shards, and reports dedup and delta indexing cutting 115 TB to about 28 TB (GitHub Engineering). Because a document lists every (repo, path) that contains it, a fork costs a few bytes of reference per file, not a second copy. Repo and org filters become posting lists inside each shard.

Incremental reindex. A push is a diff. Added or changed blobs make a new tiny segment in their shards. Deleted files and renamed paths remove a (repo, path) reference, and a document with no references is dropped at merge time. A shard applies events in log order, so a shard replica is a deterministic function of its stream, and reaching a given offset is a precise statement of freshness. Background merges bound the segment count. Merging also re-sorts documents by score so the best ones get the lowest ids, as in GitHub's compaction. A force-push is a diff against the stored indexed_sha; if that commit is unreachable, re-walk the repository.

Rule of thumb. The index is derived data. Jepsen found Elasticsearch 1.5 losing acknowledged writes under faults and recommended not using the search index as system of record (Jepsen). Keep Git and the blob store authoritative, make every indexing step idempotent by (blob_id, repo_id, path), and be able to rebuild any shard from the blob store.

3. Ranking, permissions and tail latency

Ranking. Results should rank by usefulness, not by index order. Cheap signals include whether the match is a symbol definition, in a comment or string, on a word boundary, near other matches, file path length and recency; Zoekt lists several (Zoekt design). Split ranking in two. A static score per document (popularity, language, whether it is vendored or generated) is baked into document order at merge time, so each shard can stop after enough high-scoring verified hits. A dynamic score (match quality) reorders those few.

Permissions. The index holds a repo-to-blob mapping, so permission is a property of the (repo, path) reference, not of the blob. A blob in one public and one private repository must be visible only through the public reference to a stranger. The query service builds a clause: PublicRepo() OR RepoIDs(user_private_repos) (GitHub's query rewrite adds such clauses and filters again after merging, per its write-up). Do not expand huge repository lists per query; cache per-org bitmaps with short TTLs and invalidate on change. The post-merge check asks the access service about the few hundred surviving results, so a stale cache can only cause a delayed removal of results, never a leak of anything the second check denies. Fail closed: if the access service is unreachable, return only public results.

Tail latency. A query waits for the slowest of about 1,000 shard answers. If each shard exceeds 100 ms in 1% of cases, then 1 − 0.99^1000 is essentially 100% of queries hit at least one slow shard. Four mitigations stack. Send each shard request to one replica chosen by load, and hedge to a second replica after the p95 latency. Give every request a deadline and have shards return partial results by score order rather than finishing a full intersection. Cap per-query CPU. Report partial: true when a shard times out, because a visible partial answer beats a silent one.

Down the stack

Layer 1The contract

Every returned line matches the query exactly, because verification runs on the real text. Results are complete up to index_lag_ms and the partial flag. A user never sees a result from a repository they cannot read, and a push is searchable within the freshness target. Not promised: matches in skipped files (binary, huge, invalid UTF-8, too many distinct trigrams; Cox's indexer skips such files, per his article), which a production system must surface to users.

Layer 2The mechanism

A shard file holds a format version, a trigram dictionary mapping each trigram to a posting-list offset, the posting lists, the document table, and compressed content with a line-offset table for snippets. Posting lists store gaps between sorted doc ids as variable-length integers, so a common trigram costs a byte or two per document. Zoekt uses uint32 offsets, which caps content near 1 GB per shard and shows that shard size is a design constraint (Zoekt design). Queries evaluate the plan with iterators that advance the shortest lists first, so full lists are never materialised; GitHub also reads lists lazily (GitHub Engineering). Each surviving doc is verified and kept in a bounded heap.

Layer 3The machine

Shards are read-mostly and mapped with mmap, so the page cache decides which lists are hot. A query touches few, mostly sequential lists, so NVMe (about 100 us per random 4 KB read, several GB/s sequential) suffices: a cold 1 MB list costs about 0.4 ms. GitHub reports about one core per query per shard, roughly 640 QPS on a 64-core host, with per-shard p99 near 100 ms (GitHub Engineering). Throttle merges, which compete for SSD bandwidth, and publish segments by atomic manifest swap.

Why it's built this way

  1. Grep needs 50,000 core-seconds per query at 30 TB, so build an index.
  2. Code has no word boundaries and users want regexes, so index fixed-size substrings; trigrams balance selectivity against key count.
  3. A trigram match is only necessary, so verify; this keeps the index free of positions.
  4. Most of the corpus is duplicate, so key content by hash and store references; that also gives the shard function.
  5. Content-hash sharding forces fan-out, so tail latency, early termination and replicas become the central operational concerns.

Failure modes

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Trigram postings + verifyExact regex and substring, small index, simple to updateWeak on common or short literals, needs a regex plannerGeneral code search with regex support
Positional trigrams (Zoekt style)Fewer false candidates, phrase checks without reading contentAbout 3x corpus size, heavier writesSmaller corpora, latency matters most
Sparse n-gramsRarer keys for common text, fewer candidatesMore complex build and query planningVery large corpus where common grams dominate cost
Suffix array (livegrep style)Direct substring and regex lookup on one structureSeveral bytes per input byte, hard to update incrementallySingle-repo or batch-built indexes
Shard by blob hashEven load, dedup, hot-shard freeAll queries fan outMillions of repos with many forks

Leadership lens

Check yourself

  1. Why must a trigram query always be followed by a verification step, and what would break if you trusted the index alone?

    Show answer

    A document can contain every trigram of the query without containing the query as a contiguous string (for example abc bcd for abcd). The index proves a necessary condition only, so without verification you would return false positives, and any regex that the planner approximates would return wrong lines.

  2. Your service shards by blob hash and p99 per shard is 100 ms across 1,000 shards. Why is the user-visible p99 much worse, and what do you change?

    Show answer

    The query waits for the slowest shard, so a 1% per-shard slow rate hits nearly every query at 1,000-way fan-out. Hedge to another replica after about p95, impose a deadline with partial results ordered by score, and cap per-query CPU.

  3. A file exists in a public fork and a private repository, with the same content. How does the design keep it from leaking?

    Show answer

    Visibility is attached to each (repo, path) reference, not to the blob. The query is rewritten to public repositories plus the caller's readable ones, and results are filtered again after the merge, failing closed if the access service is down.

  4. Using the numbers in this lesson, why does dedup matter more than index compression?

    Show answer

    Dedup cut the corpus from 100 TB to about 30 TB, a 70% reduction before indexing, and everything downstream (index, replicas, build time, I/O) scales with unique content. Compression typically gains a smaller constant factor on the remainder.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →