ElasticSearch を放棄し、GitHub が検索エンジンをゼロから構築します。 2 億のコード ウェアハウスを検索するにはどうすればよいですか?

2021 年 12 月、GitHub はテクノロジー プレビューをリリースし、GitHub コード検索で「何も見つからない」という問題に対処するための包括的な最適化を実施しました。

昨年 11 月の GitHub Universe 開発者カンファレンスで、公式は パブリック ベータ バージョン をリリースしました。これは主に、開発者が検索、読み取り、検索する際の問題を解決します。コードに問題があります。

カンファレンスで、「コード検索」の改善の背後にある原理は何ですか?という重要な質問をした人がいました。

最近、GitHub は、新しいモデルの背後にある技術原則とシステム アーキテクチャを詳細に説明するブログを公開しました。

GitHub 検索エンジンをゼロから構築する

簡単に言えば、新しい検索エンジンの背後には、研究者が Rust で 書き直したホイールがあります。コード検索、コードネーム Blackbird。

一見すると、検索エンジンをゼロから構築するのは不可解な決断のように思えるかもしれません。 なぜゼロから始めるのでしょうか?オープンソース ソリューションはすでにたくさんあるのではないでしょうか?新しいものを構築するためにこれ以上エネルギーを浪費する必要はありません。

実際、GitHub は既存のソリューションを使用して検索の問題を解決しようとしていますが、残念ながら、一般的なテキスト検索用の製品は「コード」の検索に適応するのが困難です。 。インデックス作成速度が遅すぎるため、ユーザー エクスペリエンスが悪く、必要なサーバーの数が多く、ランニング コストが高すぎるためです。

コード検索に特化した新しいオープン ソース プロジェクトがいくつかありますが、それらは依然として GitHub ほどの大規模なコード ベースには適していません。

上記の観察に基づいて、GitHub 開発者は 3 つの主な目標と結論を設定しました:

1. ユーザーは次のことを検索しています。プロセス中に新しいエクスペリエンスを得る いくつかのコードに関する質問をし、コードの検索、参照、移動 (ナビゲート)、および読み取りを繰り返し行うことで、回答を得ることができます。

#2. コード検索と一般的なテキスト検索には多くの違いがあります。

開発者は機械が理解できるようにコードを作成するため、コード検索プロセスではコードの構造と関連性を利用する必要があり、ユーザーは句読点を検索する可能性があります (例:コード内のピリオドや開き括弧などの演算子)、コード内の語幹を使用しない、クエリからストップ ワードを削除しない、検索に正規表現を使用しない。

3. GitHub の規模には特有の課題があります。

古いバージョンの検索エンジンは Elasticsearch を使用していましたが、最初にデプロイしたときは、GitHub 上のすべてのコードのインデックスを作成するのに数か月かかりました (当時は約 800 ありました)コード ライブラリは 1 万個ありますが、現在ではコード リポジトリの数は 2 億を超えており、これらのコードは静的ではありません。開発者は常に提出しており、コードは常に変更されているため、検索エンジンを構築するのは非常に困難です。

現在ベータ版では、ユーザーは 115 TB のコードと 155 億のドキュメントを含む約 4,500 万のコード ベースを検索できます。

結論から言えば、既成のものではニーズに応えられないので、一から作るということです。

Grep を試してみますか?

検索するときによく使われるツールは「grep」です。式を入力するとテキスト内で一致するので、grep を使用して総当たり検索の問題を解決してみてはいかがでしょうか。

この質問に答えるには、まず 115TB のコードを ripgrep で照合するのにかかる時間を計算します。

8 コア Intel CPU を搭載したマシンでは、ripgrep は 2.769 秒 (約 0.6 GB/ sec/core) は、メモリにキャッシュされた 13 GB ファイルに対して正規表現クエリを実行します。

単純な計算の後、この方法は現在の膨大なデータには実行不可能であることがわかります。コード検索プログラムが 32 台のサーバーを備えたクラスター上で実行されており、すべてのサーバーがあったとしても各マシンに 64 個のコアがあると仮定します。 115TB のコードがメモリに置かれ、すべてがスムーズに実行されます。2,048 個の CPU コアが「1 つの」クエリを実行するのに約 96 秒かかります。クエリは 1 つだけです。他のユーザーはキューに並ぶ必要があり、QPS だけが実行されます。 0.01 は grep

でのみ使用できるため、総当たり攻撃は機能しないため、最初にインデックスを構築することしかできません。

検索インデックス (検索インデックス)

関連情報がインデックスの形式で事前に計算されている場合にのみ、検索エンジンはクエリ時に迅速に応答できます。単純に、インデックスはキーと値のマッピングです。転置インデックスの場合、キーはキーワードで、値は単語が出現するドキュメント ID の順序付きリストです。

コード検索タスクでは、研究者らは特殊なタイプの転置インデックスである ngram インデックスを使用しました。

ngram は、長さ n の文字シーケンスです。たとえば、n = 3 (トライガム) は、キーの最大長が 3 のみであることを意味します。より長いキーの場合は、次のようになります。必要な長さに応じてカットします。 3. たとえば、lim、imi、mit とその値に分割されます。

検索を実行する場合、複数のキーのクエリ結果が結合され、文字列は次のようになります。表示されるドキュメントのリスト

次の質問は、比較的妥当な時間内にインデックスの構築を完了する方法です。

研究者らは、Git がコンテンツ アドレス ハッシュを使用していること、および実際に GitHub 上に重複コンテンツがかなり多く存在することを観察したため、インデックスを構築するために次の 2 つの方法を提案しました。

1. Git BLOB オブジェクト ID による shard は、シャード間でドキュメントを均等に分散する優れた方法を提供し、必要に応じて使用しながら重複を回避できます。シャードの数をいつでも確認できます。

2. インデックスをツリーとしてモデル化します、差分エンコーディング (デルタ エンコーディング) を使用してクロールの数を減らし、インデックス内のメタデータを最適化します。メタデータ データには、ドキュメントが表示される場所 (パス、ブランチ、リポジトリ) のリストと、これらのオブジェクトに関する情報 (リポジトリ名、所有者、可視性など) が含まれます。一部の人気のあるリポジトリでは、メタデータの量が非常に多くなる場合があります。

GitHub は、クエリ結果と送信されたコードの一貫性を保つシステムも設計しました。

チーム メンバーがコードをプッシュしているときにユーザーがコード ベースを検索した場合、システムが新しく送信されたドキュメントを完全に処理するまで、新しく送信されたドキュメントは検索結果に含まれないようにする必要があります。そして、Blackbird は、その設計の中核部分として、コミット クエリの一貫した性別を作成します。

Blackbird

以下は、Blackbird 検索エンジンのアーキテクチャ図です。

まず、Kafka はインデックスの内容を指定するイベントを提供します。その後、多数のイベントが発生します。クローラー プログラム コードからシンボルを抽出するサービスも備えている Git と対話し、再び Kafka を使用して各シャードのインデックスを作成し、ターゲット ドキュメントを取得します。

システムは変更を取得するために「git Push」などのイベントにのみ応答しますが、すべてのコード ベースを初めて取り込むには追加の作業が必要です。

このシステムの重要な機能は、インクリメンタル エンコーディングを最大限に活用するための最初の取り込み順序の最適化です。

GitHub は、新しい確率的データ構造を使用してコード ベースの類似性を表し、コード ベースの類似性グラフの最小スパニング ツリーの水平方向の順次走査から計算されます。摂取する。

最適化された取り込み順序に基づいて、デルタ ツリーの構築プロセスでは、各コード ベースを親コード ベースから区別します。これは、システムが現在のコード ベースをクロールするだけでよいことも意味します。コード ベース BLOB に特有のクロールには、Git から BLOB コンテンツを取得し、それを解析してシンボルを抽出し、インデックスへの入力として機能するドキュメントを作成することが含まれます。

その後、ファイルは別の Kafka トピックにパブリッシュされ、ここでデータがシャード間でパーティション分割されます。各シャードはトピック内の Kafka パーティションを使用します。

Kafka を使用すると、インデックスをクロールから切り離すことができ、Kafka でのメッセージの並べ替えによってクエリ結果の一貫性を保つこともできます。

インデクサー シャードはこれらのドキュメントを検索してインデックスを構築します。コンテンツ、シンボル、パスをトークン化して ngram インデックスやその他の有用なインデックス (言語、所有者、コード ベースなど) を構築し、結果をディスクにフラッシュします。 。

最後に、シャードを圧縮し、小さなインデックスを大きなインデックスに集約します。これにより、クエリがより効率的になり、移動が容易になります。

クエリのライフ サイクル

インデックスを使用すると、システム全体でクエリを追跡することが簡単になります。各クエリは正規表現であり、「 / 」と書くことができます。 argument?/ org:rails lang:Ruby"、Rails 組織によって Ruby 言語で書かれたコードを検索します。

GitHub.com とシャードの間には、ユーザー クエリの受信を調整して分散するサービスもあります。検索クラスター内の各ホストへのリクエストを処理し、最後に Redis を使用してディスク領域 (クォータ) を管理し、一部のアクセス制御データをキャッシュします。

フロントエンドはユーザー クエリを受け入れて Blackbird に渡します。その後、Blackbird はクエリを解析して抽象構文ツリーにし、正規言語 ID に書き換えて、文にマークを追加します。権限と範囲。

#次のステップは、n 個の同時リクエストを送信することです。検索クラスター内の各シャードとシステムに 1 個ずつリクエストを送信します。特定のシャーディング戦略では、クラスター内の各シャードにクエリ リクエストを送信します。

次に、インデックス内の情報を見つけるために、クエリが個々のシャードごとに多少変換されます。

最後に、すべてのシャードから返された結果を集計し、スコア順に並べ替え、フィルター処理し (権限を再度確認して)、次のページに戻ります。上位 100 位に達すると、GitHub.com のフロントエンドが構文の強調表示、用語の強調表示、ページネーションを実行し、最後に結果をページに表示できます。

実際の使用では、単一シャードの p99 応答時間は約 100 ミリ秒ですが、応答の集約、権限の確認、構文の強調表示などの理由により、合計の応答時間はより長いです。

1 つのクエリはインデックス サーバー上の 1 つの CPU コアを 100 ミリ秒占有するため、64 コアのホストの上限は 1 秒あたり約 640 クエリです。 grep 方式 (0.01 QPS) と比較すると、この方式はかなり高速であると言えます。

概要

完全なシステム アーキテクチャを導入した後、問題の規模を再検討できます。

GitHub の取り込みパイプラインは 1 秒あたり約 120,000 個のドキュメントを公開できるため、155 億個のドキュメントすべてを処理するには約 36 時間かかりますが、デルタ インデックスを使用するとその数を 50% 以上削減できます。クロールする必要があるドキュメントの数に応じて、プロセス全体でコーパス全体のインデックスを再作成するのに約 18 時間かかりました。

インデックス スケールの点でいくつかのブレークスルーが行われ、初期のコンテンツ ボリュームは 115 TB でしたが、重複コンテンツを削除し、増分インデックスを使用した後、コンテンツの量は約 28 TB に減少しました。

そして、インデックス自体はわずか 25 TB です。これには、すべてのインデックス (ngram を含む) だけでなく、すべての一意のコンテンツの圧縮コピーも含まれます。つまり、コンテンツを含むインデックスの合計サイズも元のデータ サイズの約 4 分の 1 です。

以上がElasticSearch を放棄し、GitHub が検索エンジンをゼロから構築します。 2 億のコード ウェアハウスを検索するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。