GitHubの新しいコード検索を支える技術

1年前に新しいコード検索エクスペリエンスのテクノロジープレビューを発表してから、昨年11月のGitHub Universeでパブリックベータ版をリリースするまで、私たち開発者がコードを見つけ、読み、ナビゲートする方法に関する革新とGitHub製品のコア体験への劇的変化が相次いでいます。

新しいコード検索エクスペリエンスについてよく聞かれる質問のひとつに、"どのように動作するのか "というものがあります。この記事では、GitHub Universeで行った講演を補足する形で、この質問に対するハイレベルな答えと、この製品のシステムアーキテクチャや技術的基盤についての小さな窓を提供するものです。

では、どのように動作するのでしょうか？簡単に言うと、私たちはコード検索に特化した独自の検索エンジンをRustで一から作り上げました。この検索エンジンをBlackbirdと呼んでいますが、その仕組みを説明する前に、私たちのモチベーションをお伝えします。一見すると、ゼロから検索エンジンを作るというのは疑問のある決断のように思えます。なぜそんなことをするのでしょうか？既存のオープンソースのソリューションはすでにたくさんあります。ではなぜ、新しいものを作るのでしょうか？

公平を期すために、私たちはGitHubの歴史のほとんどすべてにおいて、この問題に対して既存のソリューションを利用することをまず検討し、またそうしてきました。私たちの道のりについては Pavel Avgustinov の投稿「A brief history of code search at GitHub」の中で紹介されています。この中で印象に残っていることは、コード一般的なテキスト検索製品をコード検索のために使うのは、あまり良いことではないということです。ユーザーエクスペリエンスが悪く、インデックス作成に時間がかかり、ホスティングにコストがかかるからです。コードに特化した新しいオープンソースプロジェクトもありますが、GitHubの規模では間違いなく機能しません。このような状況を知っていた私たちは、以下の3つの点に着目し、独自のソリューションを作ることにしました。

1. コードに質問をし、検索、ブラウズ、ナビゲート、読み込みを繰り返しながら答えを得ることができる、全く新しいユーザーエクスペリエンスのビジョン
2. 私たちはコード検索が、一般的なテキスト検索とは明らかに異なるものであると理解しています。コードはすでに機械が理解できるように設計されており、その構造と関連性を利用することができるはずです。コードの検索には、句読点（ピリオドや開カッコなど）を検索したい、ステミングをしたくない、クエリーからストップワードを削除したくない、正規表現で検索したい、などの独自の要件もあります。
3. GitHubのサービス規模に対しての開発は非常にユニークであり、挑戦でもあります。Elasticsearchを初めて導入した時、GitHub上の全てのコード（当時は約800万リポジトリ）のインデックスを作成するのに数ヶ月かかりました。現在ではその数は2億を超え、しかもそのコードは静的なものではなく、常に変化しており、検索エンジンが扱うにはかなり困難なものです。ベータ版では、現在約4500万のリポジトリを検索することができ、これは115TBのコードと155億のドキュメントに相当します。

結局、既成のものでは我々のニーズを満たせなかったので、ゼロから何かを作り上げたのです。

grepを使うだけでいいのか？

まず、この問題に対するブルートフォース・アプローチについて説明します。よくこんな質問を受けます。"なぜgrepを使わないのですか？"その答えとして、115TBのコンテンツに対してripgrepを使った計算を少ししてみましょう。8コアのIntel CPUを持つマシンで、ripgrepはメモリにキャッシュされた13GBのファイルに対して、網羅的な正規表現クエリを2.769秒、つまり約0.6GB/秒/コアで実行することができます。

これでは、大量のデータを処理することができないことがすぐにわかります。コード検索は64コア、32マシンのクラスターで実行されます。仮に115TBのコードをメモリに格納し、完璧に並列化できたとしても、1つのクエリを実行するために2,048個のCPUコアを96秒間飽和させることになります！そうすると1つのクエリしか実行できません。他のクエリーは順番に実行しなければなりません。これは、1 秒あたりのクエリ数 (QPS) が 0.01 という驚異的な数字であり、うまくいけば QPS が 2 倍になります。これでは、インフラストラクチャの請求について経営陣との楽しい会話をすることになるでしょう。

このアプローチをGitHubの全コードと全ユーザーに適用するには、費用対効果の高い方法はありません。この問題に大量の資金を投入したとしても、ユーザー体験の目標を達成することはできないでしょう。

つまり、インデックスを作成する必要があるのです。

検索インデックス入門

インデックスとは、キーと、そのキーが出現する文書IDのソートされたリスト（「投稿リスト」と呼ばれる）の対応表と考えることができます。例えば、プログラミング言語に関する小さなインデックスがあります。各文書をスキャンしてどのプログラミング言語で書かれているかを検出し、文書IDを割り当てて、言語をキー、文書IDの投稿リストを値とする転置インデックスを作成します。

転置インデックス

転置インデックス

コード検索には、コンテンツの部分文字列を検索するのに便利な、ngram インデックスと呼ばれる特殊な転置インデックスが必要です。例えば、n=3 (trigrams)とすると、コンテンツ「limit」を構成するngramはlim,imi,mit,itsとなる。上の文書で、これらのtrigramのインデックスは次のようになります。

検索を行うには、複数の検索結果を交差させて、その文字列が出現する文書のリストを得ます。トリグラムインデックスの場合、lim、imi、mit、itsの4つの検索が必要です。

しかし、ハッシュマップとは異なり、これらのインデックスは大きすぎてメモリに収まらないので、代わりにアクセスする必要のあるインデックスごとにイテレータを構築します。これらはソートされたドキュメントID（IDは各ドキュメントのランキングに基づいて割り当てられる）を遅延的に返し、イテレータを（特定のクエリの要求に応じて）交差させたり結合したりして、要求された数の結果を取得するのに十分な距離だけ読み取ります。こうすることで、投稿リスト全体をメモリ上に保持する必要がなくなるのです。

4,500万件のリポジトリへのインデックス付け

次の問題は、このインデックスを合理的な時間で構築する方法です（最初の反復作業では数ヶ月かかったことを思い出してください）。よくあることですが、ここでのコツは、作業している特定のデータについて何らかの洞察を得て、アプローチの指針とすることです。私たちの場合、それは2つのことです。GitがContent Addressable Hashingを使用していることと、GitHubに非常に多くの重複コンテンツが存在することです。この二つの洞察から、私たちは次のような決定を下しました。

1. シャードはGit BlobオブジェクトIDで管理し、重複を避けつつシャード間でドキュメントを均等に分配します。特別なリポジトリが原因でサーバーが熱くなることもありませんし、必要に応じてシャードの数を簡単に拡張することができます。
2. インデックスをツリーとしてモデル化し、デルタエンコーディングを使用してクロールの量を減らし、インデックスのメタデータを最適化します。私たちにとってメタデータとは、文書が出現する場所のリスト（どのパス、ブランチ、リポジトリか）や、それらのオブジェクトに関する情報（リポジトリ名、所有者、可視性など）のようなものです。このデータは、人気のあるコンテンツではかなり大きくなることがあります。

また、クエリの結果がコミットレベルで一貫しているように設計されています。チームメイトがコードをプッシュしている間にリポジトリを検索した場合、システムで完全に処理されるまで、新しいコミットからのドキュメントが結果に含まれないはずです。実際、あなたがリポジトリを対象としたクエリから結果を得ている間、他の誰かがグローバルな結果をページングして、別の、より前の、しかし依然として一貫した 一貫性のあるの状態を見ることができます。これは、他の検索エンジンでは難しいことです。Blackbirdはこのレベルのクエリの一貫性を設計の中核部分として提供しています。

インデックスを構築しよう

これらの洞察を得た上で、Blackbirdでインデックスを構築することに目を向けてみましょう。この図は、システムのインジェストとインデックス作成側のハイレベルな概観を表しています。

Kafkaは私たちにインデックスを作成するように指示するイベントを提供します。Gitやコードからシンボルを抽出するサービスとやり取りするクローラーがたくさんあり、それからKafkaを使って、各シャードが自分のペースでインデックスのためのドキュメントを消費できるようにしています。

システムは通常、git pushのようなイベントに反応して変更されたコンテンツをクロールするだけですが、初めてすべてのリポジトリを取り込むために、いくつかの作業を行いました。このシステムの重要な特性の一つは、デルタエンコーディングを最大限に活用するために、この最初のインジェストを行う順番を最適化することです。これは、リポジトリの類似性を表す新しい確率的データ構造と、リポジトリの類似性を表すグラフの最小スパニングツリーのレベルオーダーのトラバーサルからインジェスト順序を駆動することによって実現されています。¹.

最適化された取り込み順序を使用して、各リポジトリは、構築したデルタツリー内の親に対して差分を取ることでクロールされます。つまり、（リポジトリ全体ではなく）そのリポジトリに固有のBlobのみをクロールする必要があります。クロールでは、GitからBlobの内容を取得し、それを解析してシンボルを抽出し、インデックス作成のための入力となるドキュメントを作成します。

これらのドキュメントは、別のKafkaトピックにパブリッシュされます。ここでパーティション²のデータをシャード間で分割します。各シャードは、トピック内の1つのKafkaパーティションを消費します。インデックス作成は、Kafkaを使用することでクロールから切り離され、Kafka内のメッセージの順序がクエリの一貫性を得る方法となります。

インデックス作成用シャードは、これらのドキュメントを受け取り、インデックスを作成します：トークン化により、ngramインデックスを作成します。³(トークン化し、ngramインデックス3（コンテンツ、シンボル、パス）やその他の有用なインデックス（言語、所有者、リポジトリなど）を構築し、十分な作業が蓄積されたらシリアライズしてディスクにフラッシングします。

最後に、シャードはコンパクションを実行し、小さなインデックスをクエリの効率がよく、移動しやすい大きなインデックスにまとめます（たとえば、読み込みレプリカやバックアップのためなど）。コンパクションはまた、投稿リストをスコアでkマージし、関連文書がより低いIDを持ち、遅延イテレータによって最初に返されるようにします。最初のインジェストではコンパクションを遅らせ、最後に大きなコンパクションを実行します。しかし、インデックスが逐次変更されるにつれて、より短い間隔でコンパクションを実行し、ドキュメントの削除などを処理します。

クエリの寿命

インデックスができたので、システムを通してクエリを追跡してみるのも面白いでしょう。これから追うクエリは、Rubyプログラミング言語で書かれたコードを探しているRails組織に適格な正規表現です。/arguments?/ org:rails lang:Ruby。クエリパスの高レベルなアーキテクチャは、次のようなものです。

GitHub.com とシャードの間には、ユーザーのクエリを受け取り、検索クラスタの各ホストにリクエストを分散させるサービスを配置しています。Redis を使ってクォータを管理し、アクセス制御データをキャッシュしています。

フロントエンドはユーザーのクエリを受け取り、それをBlackbirdクエリサービスに渡します。クエリは抽象的な構文ツリーに解析され、言語などを正規のLinguist言語IDに解決し、パーミッションやスコープのための追加の句をタグ付けして、書き直されます。この場合、パブリック・リポジトリや、私がアクセスできるプライベート・リポジトリからの結果が、どのように書き換えられるかがわかると思います。

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

次に、検索クラスタの各シャードに1つずつ、ファンアウトしてn個の同時リクエストを送信します。シャーディング戦略のため、クエリーリクエストはクラスタ内の各シャードに送信されなければなりません。

各シャードでは、インデックスの情報を検索するために、さらにクエリの変換を行います。ここでは、正規表現がngramインデックスに対する一連の部分文字列クエリに変換されていることがわかります。

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…)
  ), 
  …
)

正規表現を部分文字列クエリにする方法についてもっと知りたい場合は、Russ Coxの記事「Regular Expression Matching with a Trigram Index」を参照してください。私たちは異なるアルゴリズムと、trigramの代わりに動的なグラムサイズを使っています(³).この場合、エンジンは次のグラムを使います：arg, rgu,gum、そしてumeと ment、または6グラムのumentsのいずれかです。

各節のイテレータは、andは交差を意味し、unionは結合を意味します。その結果、文書のリストが得られます。各文書をダブルチェックし（マッチの検証や範囲の検出）、スコアリング、ソート、そして要求された数の結果を返さなければならなりません。

クエリサービスに戻ると、すべてのシャードの結果を集約し、スコアで再ソートし、フィルタリングして (パーミッションを再確認して) 上位 100 件を返します。GitHub.com のフロントエンドでは、構文強調や用語強調、ページ送りを行い、最後に結果をページにレンダリングします。

個々のシャードからのp99のレスポンスタイムは100ミリ秒程度ですが、レスポンスの集約やパーミッションのチェック、シンタックスハイライトなどのため、全体のレスポンスタイムはもう少し長くなっています。クエリはインデックスサーバーの1CPUコアを100ミリ秒拘束するので、64コアのホストでは1秒あたり640クエリ程度が上限となります。grepのアプローチ（0.01QPS）と比較すると、これは非常に高速で、同時ユーザクエリや将来の拡張にも十分対応できるものです。

まとめ

システム全体を見たところで、問題の規模を再確認してみましょう。我々のインジェストパイプラインは、1秒間に約12万文書を公開できるので、155億文書を処理するのに約36時間かかるはずです。しかし、デルタインデックスにより、クロールしなければならない文書数が50%以上削減され、コーパス全体のインデックスを約18時間で再作成することができます。

インデックスのサイズに関しても、大きな成果があります。私たちは115TBの検索対象コンテンツからスタートしたことを思い出してください。コンテンツの重複排除とデルタインデックスにより、ユニークなコンテンツは約28TBに減少しました。インデックス自体は25TBで、これにはすべてのインデックス（ngramを含む）だけでなく、すべてのユニークコンテンツの圧縮コピーも含まれています。つまり、コンテンツを含むインデックスの総容量は、元データのおよそ4分の1ということになります。

まだサインアップしていない方は、ぜひベータ版に参加して、新しいコード検索体験を試してみてください。ご感想をお聞かせください。私たちは積極的にリポジトリを追加し、あなたのような人々からのフィードバックに基づいて、ラフエッジを修正します。

ノート