システム設計のケーススタディ #2: GitHub がコードをインデックスして超高速な検索と取得を実現する方法

GitHub は、既存の既製ソリューションが運用規模の要件に適合しなかったため、Project Blackbird と呼ばれる検索エンジンを Rust で最初からコーディングしました。 このエンジンは、識別子、句読点、部分文字列、正規表現、ワイルドカードなどを使用した検索などの機能をサポートしています。これらの機能は、通常のテキストベースの検索とは対照的に、コード検索に特有です。

この検索エンジンは、2 億のリポジトリにわたるグローバル クエリもサポートしており、数分以内にリポジトリ内のコード変更のインデックスを作成します。 コード検索インデックスは、GitHub が実行する群を抜いて最大のクラスターであり、5,184 個の vCPU、40TB の RAM、および 1.25PB のバッキング ストレージで構成され、平均 200 リクエスト/秒のクエリ負荷をサポートし、530 億を超えるソース ファイルのインデックスを作成します。

コードのインデックス作成

GitHub は、ドキュメント ID のソートされたリストへのキーであるインデックスとして情報を事前計算します。 たとえば、プログラミング言語による検索用のインデックスがどのように作成されるかを次に示します。各ドキュメントをスキャンして、そのドキュメントがどのようなプログラミング言語で書かれているかを検出し、ドキュメント ID を割り当てます。

ドキュメントID	コンテンツ
1	デフリム 「ミット」を入れる 終わり
2	fn 制限() {
3	関数 mit() {

次に、プログラミング言語をキーとし、そのプログラミング言語が出現するドキュメント ID のリストを値とする転置インデックスが作成されます。

言語	ドキュメント ID (投稿)
JavaScript	3、8、12、…
ルビー	1、10、13、…
さび	2、5、11、…

コード検索には、コンテンツの部分文字列の検索に役立つ、N グラム インデックスと呼ばれる特殊なタイプの逆インデックスが必要です。

Nグラム

N-gram インデックスは、シーケンス内で後に続く可能性が最も高い単語を予測することにより、「入力しながら検索」機能を実装するのに役立ちます。 これは、入力クエリにスペルミスやバリエーションがある場合でも、部分一致や類似テキストなどを容易にするデータのコーパスでトレーニングされた確率モデルです。

N グラムは、特定のテキストから抽出された n 個の文字または単語のシーケンスです。 したがって、たとえば 3 グラムのインデックス作成では、テキスト「Python」は「pyt」、「yth」、「tho」、「hon」に分割されます。

生成された 3 グラムには、ハッシュ テーブルや検索ツリーなどのデータ構造でインデックスを付けることができます。 各 N グラムは、それが発生するドキュメントの場所に関連付けられます。

N-gram インデックスは次のようになります。

ングラム	ドキュメント ID (投稿)
どうでも	1、2、…
親愛なる	2、…
でも	1、2、3、…
ホン	2、3、…

検索クエリを実行すると、クエリはインデックス付けと同じ方法で N グラムに分割され、それらの N グラムがインデックス内の N グラムと照合されて、一致するドキュメントのリストが取得されます。

検索エンジンは、検索クエリ、コンテキスト、インデックス付けされたデータに基づいて、n グラムに動的値 n を含めることができます。

GitHub コード検索エンジンによって作成されたインデックスは大きすぎてメモリに収まらないため、GitHub はインデックス全体をメモリにロードせずに各インデックスの要素に順次アクセスできるように各インデックスのイテレータを構築しました。

重複コンテンツを含む 2 億のリポジトリのインデックスを作成するために、GitHub はコンテンツ アドレス可能なストレージを活用しています。

コンテンツアドレス指定可能なストレージ

コンテンツアドレス指定可能なストレージは、ファイル名やファイルの場所を使用してデータを保存するのではなく、コンテンツによって生成された一意のハッシュに基づいてデータを保存する技術です。 これにより、重複したコンテンツを排除できます。 保管スペースを減らす そして多額の費用がかかります。

ハッシュは、MD5、SHA-1、SHA-2、 ハッシュの生成には SHA-256 などが一般的に使用されます。 ハッシュは一意であり、データの更新時に変更されるため、このアプローチでは強力なデータ整合性が提供されます。

データが時間の経過とともに変更されると、異なるハッシュが作成されるため、バージョン履歴を維持しながら、異なるバージョンのデータにアクセスできるようになります。

CDN はこの技術を使用して、データを効率的にキャッシュし、世界中のエッジ領域に分散します。

GitHub はこのアプローチを活用して、115 TB のデータを 28 TB の固有のコンテンツに削減しました。 圧縮後、ngram インデックスとすべての圧縮された一意のコンテンツを含むすべてのインデックスを含め、インデックス全体はわずか 25 TB になりました。 コンテンツ アドレス可能ストレージにより、総データ サイズが元のデータの約 4 分の 1 に削減されました。

GitHub は、Git BLOB オブジェクト ID に基づいてデータをシャード全体に均等に分散します。 これは役に立ちます システムを水平方向に拡張する。 クエリをシャード全体に分散することで、より多くの QPS (1 秒あたりのクエリ数) を処理できます。 データをディスク全体に分散して、ストレージ容量を増やすことができます。 また、データのインデックス作成時間も短縮されますが、これは個々のホストの CPU とメモリの制限によって制限されます。

ここで、GitHub が BLOB データをどのように保存するかを簡単に理解しましょう。

コードストレージ

Git は、コンテンツ ハッシュに基づいてデータを BLOB オブジェクトとしてオブジェクト ストアに保存します。オブジェクト ストアは、本質的にはキーと値のデータ ストアです。

Git はコードを保存するように構築されていますが、ドキュメント、構成ファイル、画像、PDF などをリポジトリに保存するため、データはオブジェクト ストレージに適した非構造化になっています。 Git に入力されるデータには必ず、そのデータを取得するために使用できる一意のキー (BLOB オブジェクト ID) があります。

このように、オブジェクト ストアは、オブジェクト ID とオブジェクト コンテンツの 2 つの列を持つキーと値のデータベース テーブルのように機能します。

画像ソース: GitHub

BLOB は生データです。 これらには、ファイル名や、リポジトリ名、所有者、可視性などの他のメタデータは含まれません。この情報はすべてツリーに保存されます。 ツリーはオブジェクトとペアになって、ファイルの階層をリポジトリに保存します。

画像ソース: GitHub

コードの取り込みとインデックス作成

以下は、コードがどのように取り込まれ、インデックスが作成されるかを示す概要図です。

画像ソース: GitHub

GitHub は、リポジトリに変更があったときにイベントを公開します。 Kafka を介したイベントは、検索エンジン取り込みクローラーに変更を取り込むように通知します。 クローラーはコードからシンボルを抽出し、ドキュメントを作成し、再び Kafka を介してドキュメントをシャードに保存します。

システムはデルタ エンコーディングを利用して、ファイル全体ではなくコード内の変更のみを保存することで検索インデックスのサイズを削減します。 これにより、コンテンツが常に変化するシステムにおいて、インデックス作成とクエリのプロセスが高速化され、ファイル全体の不必要な計算が回避されます。

検索エンジンは、デルタ エンコーディングを最大限に活用するために、ファイルが最初に取り込まれる順序を最適化します。

インデックス作成シャードはドキュメントを使用して N-gram インデックスを構築し、コンテンツをディスクにフラッシュする前に効率的なクエリを実行するために圧縮を実行して小さなインデックスを大きなインデックスにまとめます。 2 番目の Kafka 実装では、インデックス作成を取り込みとクロールから切り離します。

インデックス作成パイプラインには 1 秒あたり約 120,000 件のドキュメントを公開する能力があり、155 億件のドキュメントのインデックス作成には約 36 時間かかります。 ただし、デルタ インデックス作成により、クロールされるドキュメントの数が 50% 以上削減され、インデックス作成時間が 18 時間に短縮されます。

取り込み順序の最適化とデルタエンコーディングの最大限の活用

最適な取り込み順序を決定し、コンテンツに関してあるリポジトリが別のリポジトリとどの程度類似しているかを判断できるようにするために、彼らは幾何学的フィルターと呼ばれる新しい確率的データ構造を発明しました。

確率的データ構造では、ランダム化と近似を活用して、多少のエラーの可能性はありますが、データを効率的に保存およびクエリします。 これらは、メモリの削減とパフォーマンスの向上のためにある程度の精度を犠牲にすることができる、メモリに制約のある場合に役立ちます。 例としては、ブルーム フィルター、カウントミニ スケッチ、ハイパーログ、スキップ リストなどがあります。

幾何学的フィルターは、頂点がリポジトリであり、エッジが類似性メトリックで重み付けされるグラフを構築します。 このグラフの最小スパニング ツリーが計算され、デルタ エンコーディングを最大限に活用するための取り込み順序を取得するためにレベル順序のトラバーサルが実行されます。

このケーススタディでのシステム設計の学習

コンテンツアドレス指定可能なストレージを使用して重複データを効率的に保存する

ハッシュ ベースのコンテンツ アドレス可能ストレージは、大量のデータを保存するときに重複データを大量に生成する優れた方法です。

AWS S3、Google Cloud Storage、Azure Blob Storage などのオブジェクト ストレージは、データのコンテンツの一意のハッシュであるキーと値のペアでデータを保存するため、ハッシュ ベースのデータの保存に関連付けられています。 このアプローチでは、重複したコピーによって同じハッシュが作成されます。 したがって、同じ保存場所を指す複製インスタンスとともに、元のコピーのみをデータベースに保存する必要があります。

コンテンツの一意のハッシュを作成しない別のデータベースを使用する場合は、データベースに保存する前にアプリケーション レベルでコード内にハッシュを作成できます。

シャード間でデータを分散するためのハッシュベースのシャーディング

クラスター内のノード間でデータをシャーディングするには、範囲ベースのシャーディング、キーベースのシャーディング、ラウンドロビン シャーディング、ディレクトリベースのシャーディング、ランダム シャーディング、ハッシュ ベースのシャーディング、地理的リージョン ベースのシャーディングなど、複数の方法があります。の上。

GitHub は、カスタマイズされたハッシュベースのシャーディングである Git BLOB オブジェクト ID によってデータを均等にシャーディングします。 BLOB オブジェクト ID は、オブジェクトのコンテンツから生成される一意のハッシュです。

ハッシュベースのシャーディングにより、ハッシュ関数に基づいてデータがシャード間で均一に分散されます。 これにより、効率的なデータのアクセスと取得が容易になります。 クエリは、いくつかのホット ノードに集中するのではなく、クラスタ ノード全体に均一に分散されます。

新しいノードがクラスターに追加またはクラスターから削除されると、ハッシュが調整され、シャード間でのデータの再分散が最小限に抑えられます。 Slack はコンシステント ハッシュ技術を使用します これにより、クラスター内のノードの追加および削除時のデータの再バランスが最小限に抑えられます。 ここでそれについてのケーススタディを行いました。 ここでチェックしてください。

階層データを格納するためのツリー

ツリー データ構造は、階層データの保存に最適です。 Git はこれを利用してリポジトリ ファイル階層を保存します。 ツリーは親子関係を自然にモデル化し、最小限の遅延で階層データの移動、検索、並べ替えを容易にします。

ファイルシステム ディレクトリ構造、データベース インデックス (B ツリー、AVL ツリー)、圧縮アルゴリズム (ハフマン ツリー) を使用し、ツリーを活用して効率を高めます。

オブジェクト ストアは非構造化データの保存に最適です

クラウド ストレージには主に、ファイル、ブロック、オブジェクトの 3 種類があります。 オブジェクト ストレージは、一意のキーを持つ非構造化データの保存に最適です。

コードのほかに、GitHub には画像、ドキュメント、PDF などが保存されます。 この種のデータは構造化されていません。 したがって、オブジェクト ストアはこの使用例に最適です。

オブジェクト ストアを使用すると、HTTP 経由でデータに簡単にアクセスし、コンテンツ配信ネットワーク経由で共有できます。ストリーミング サービスはオブジェクト ストレージを利用して、ビデオ、オーディオ ファイル、画像などの異種データを保存します。

イベントキュー/メッセージブローカーを使用したシステムモジュールの分離

GitHub は Kafka を活用して、クローリング モジュールとインデックス作成モジュールを分離します。 メッセージ ブローカー/イベント キューの使用は、マイクロサービスを分離するための標準的なアーキテクチャ アプローチです。

これにより、疎結合で柔軟なシステム設計が容易になります。 イベント キューは、システム モジュールがイベントを同時に処理できるようにする必要がなく、システム モジュール間のアダプタとして機能し、ノンブロッキングの非同期通信を容易にします。

私は、Web スケールの企業が拡張、可用性の維持、フォールト トレラントを実現し、遅延を低く抑えるために活用しているアーキテクチャおよびシステム設計の概念を理解するために、現実世界のアーキテクチャを調査しています。
前回の事例はこちら: Slack のリアルタイム メッセージング アーキテクチャを探索する。 それをチェックしてください。

大規模なサービス設計の基本を詳しく知りたい場合は、これらの概念やその他の概念について、私の記事で説明しています。 ゼロからソフトウェア アーキテクチャをマスターする学習パス この 3 つのコースは、ソフトウェア アーキテクチャ、クラウド インフラストラクチャ、分散システム設計の領域について段階的に教育することを目的として私が作成した 3 つのコースで構成されています。

この学習パスは、構造化された学習体験を提供し、この分野に関する知識がまったくない状態から、YouTube、Netflix、ESPN などの Web スケールの分散システムを設計するプロになることができます。 それをチェックしてください。

情報源： GitHub エンジニアリング

私はシヴァンです。 これが私のXです そして LinkedIn プロフィール。 お気軽にメッセージを送ってください。 コンテンツが役に立ったと思われる場合は、より多くの人にリーチするためにネットワークで共有することを検討してください。

次の投稿でお会いしましょう。 それまで、乾杯！