The technology behind GitHub’s new code search
Search is a fascinating topic because it&#x27;s such a fundamental problem and every search engine is based around the same extremely simple data structure (Posting list&#x2F;inverted index). Despite that, search isn&#x27;t easy and every search engine seems to be quite unique. It also seems to get exponentially harder with scale.<p>You can write your own search engine that will perform very well on a surprisingly large amount of data, even doing naive full-text search. A search tool I came across a while back is a great example of something at that scale: <a href="https:&#x2F;&#x2F;pagefind.app&#x2F;" rel="nofollow">https:&#x2F;&#x2F;pagefind.app&#x2F;</a>.<p>For anyone who doesn&#x27;t know anything about search I highly recommend reading this (It&#x27;s mentioned in the blog post as well): <a href="https:&#x2F;&#x2F;swtch.com&#x2F;~rsc&#x2F;regexp&#x2F;regexp4.html" rel="nofollow">https:&#x2F;&#x2F;swtch.com&#x2F;~rsc&#x2F;regexp&#x2F;regexp4.html</a>.<p>Algolia also has a series of blog posts describing how their search engine works: <a href="https:&#x2F;&#x2F;www.algolia.com&#x2F;blog&#x2F;engineering&#x2F;inside-the-algolia-engine-part-1-indexing-vs-search&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.algolia.com&#x2F;blog&#x2F;engineering&#x2F;inside-the-algolia-...</a>.<p>---<p>It&#x27;s interesting that GitHub seems to have quite a few shards. Algolia basically has a monolithic architecture with 3 different hosts which replicate data and they embed their search engine in Nginx:<p><i>&quot;Our search engine is a C++ module which is directly embedded inside Nginx. So when the query enters Nginx, we directly run it through the search engine and send it back to the client.&quot;</i><p>I&#x27;m guessing GitHub probably doesn&#x27;t store repos in a custom binary format like Algolia does though:<p><i>&quot;Each index is a binary file in our own format. We put the information in a specific order so that it is very fast to perform queries on it.&quot;</i><p><i>&quot;Our Nginx C++ module will directly open the index file in memory-mapped mode in order to share memory between the different Nginx processes and will apply the query on the memory-mapped data structure.&quot;</i><p><a href="https:&#x2F;&#x2F;stackshare.io&#x2F;posts&#x2F;how-algolia-built-their-realtime-search-as-a-service-product" rel="nofollow">https:&#x2F;&#x2F;stackshare.io&#x2F;posts&#x2F;how-algolia-built-their-realtime...</a><p>100ms p99 seems pretty good, but I&#x27;m curious what the p50 is and how much time is spent searching vs ranking. I&#x27;ve seen Dan Luu say that majority of time should be spent ranking rather than searching and when I&#x27;ve snooped on <a href="https:&#x2F;&#x2F;hn.algolia.com" rel="nofollow">https:&#x2F;&#x2F;hn.algolia.com</a> I&#x27;ve seen single digit millisecond search times in the responses, which seems to corroborate this.<p>I&#x27;m curious why they chose to optimize ingestion when it only took 36hrs to re-index the entire corpus without optimizations. A 50% speedup is nice, but 36hrs and 18hrs are the same order of magnitude and it sounds like there was a fair amount of engineering effort put into this. An index 1&#x2F;5 of the size is pretty sweet though, I have to assume that&#x27;s a bigger win that 50% faster ingestion.<p>Since they&#x27;re indexing by language I wonder if they have custom indexing&#x2F;searching for each language, or if their ngram strategy is generic over all languages. Perhaps their &quot;sparse grams&quot; naturally token different for every language. Hard to tell when they leave out the juiciest part of the strategy though: &quot;Assume you have some function that given a bigram gives a weight&quot;.<p>Search is so cool. I could talk about it all day.