「並列チェックアウト」(Parallel Checkout)機能は、複数のプロセスを使用して、ブロブの圧縮解除、コア内フィルターの適用、およびチェックアウト操作中に結果のコンテンツを作業ツリーに書き込む作業を並列化しようとします。 これは、 clone や checkout や reset や` sparse-checkout` などのすべてのチェックアウト関連コマンドで使用できます。

これらのコマンドは、以下の共通の基本構造を持っています:

  • ステップ1: 現在のインデックスファイルをメモリに読み込みます。

  • ステップ2: コマンドに基づいてメモリ内インデックスを変更し、更新が必要なすべてのキャッシュエントリに一時的なマークを付けます。

  • ステップ3: 新しい候補インデックスに一致するように作業ツリーにデータを配置します。これには、更新されるすべてのキャッシュエントリの反復と、作業ツリー内の関連ファイルの削除、作成、または上書き作業が含まれます。

  • ステップ4: 新しいインデックスをディスクに書き込みます。

ステップ3が、ここで説明する「並列チェックアウト」作業の焦点です。

Sequential Implementation

ここで説明する、ステップ3の現在の実装は、3つの部分に分かれており、それぞれが独自の機能で実装されています。

  • ステップ3a: unpack-trees.c:check_updates() には、 cache_entry の配列を反復処理する一連の処理ループが含まれています。この関数のメインループは、更新されるエントリごとに ステップ3b 関数を呼び出します。

  • ステップ3b: entry.c:checkout_entry() は、ファイルの競合、衝突、および保存されていない変更について、既存の作業ツリーを調べます。必要に応じてファイルを削除し、先頭のディレクトリを作成します。書き込まれるエントリごとに ステップ3c 関数を呼び出します。

  • ステップ3c: ： entry.c:write_entry() はブロブをメモリにロードし、必要に応じてsmudgeし、作業ツリーにファイルを作成し、smudgeされたコンテンツを書き込み、 fstat() または lstat() を呼び出します。収集された統計情報で、関連する cache_entry 構造体を更新します。

ファイルの作成と削除の間に競合状態が発生する可能性があるため、ステップ3bを並行して実行することは安全ではありません。代わりに、並列チェックアウトフレームワークにより、シーケンシャルコードでステップ3bを処理し、並列ワーカーを使用して、ステップ3cからのシーケンシャル entry.c:write_entry() 関数呼び出しを置き換えます。

Rejected Multi-Threaded Solution

最も「素直な」(straightforward)実装は、 更新されるキャッシュエントリのセットを複数のスレッドに分散させることです。ただし、 オブジェクト指向データベース内のスレッドセーフでない関数のため、 並列操作を調整するためにロックを使用する必要があります。 このソリューションの初期のプロトタイプは、 マルチスレッド・チェックアウトによってシーケンシャルコードよりもパフォーマンスが向上することを示していましたが、 それでもロックの競合が多すぎました。 perf プロファイリングは、(SSD上の)ローカルLinuxクローン中のランタイムの約20％が機能のロックに費やされたことを示しました。 このため、 このアプローチは却下され、複数の子プロセス利用を行うことでパフォーマンスが向上しました。

Multi-Process Solution

並列チェックアウトは、前述のステップ3を変更して、複数の checkout--worker バックグラウンドプロセスを使用して作業を分散します。長時間実行されるワーカープロセスは、既存のrun-command APIを使用するフォアグラウンドGitコマンドによって制御されます。

Overview

ステップ3bはわずかに変更されています。チェックアウトするエントリごとに、メインプロセスは以下の手順を実行します:

  • M1: 作業ツリーに、このエントリによって上書きされる、追跡されていないファイルまたはクリーンでないファイルがあるかどうかを確認し、続行する(ファイルを削除する)かどうかを決定します。

  • M2: 先頭のディレクトリを作成します。

  • M3: エントリのパスの変換属性をロードします。

  • M4: エントリのタイプと変換属性に基づいて、エントリが並列チェックアウトの対象であるかどうかを確認します(詳しくは後述します)。適格である場合は、エントリとロードされた属性をキューに入れて、後でエントリを並行して書き込みます。そうでない場合は、デフォルトのシーケンシャルコードを使用して、すぐにエントリを記述します。

注: ワーカーはメインプロセスのインデックス状態にアクセスできないため、各エントリに関連付けられた変換属性を保存します。そのため、ワーカーは属性を自分でロードできません(また、属性はエントリを適切にsmudgeするために必要です)。 さらに、これは、 (1)属性を2回ロードする必要がなく、 (2)属性機構がパスを順番に処理するように最適化されているため、パフォーマンスにプラスの影響を与えます。

すべてのエントリが上記の手順を通過した後、メインプロセスは、キューに入れられたエントリの数がワーカー間で分散するのに十分であるかどうかを確認します。 そうでない場合は、それらを順番に書き込みます。それ以外の場合は、ワーカーを生成し、キューに入れられたエントリを連続したチャンクに均一に分散します。これは、2人のワーカーが同じディレクトリに同時に書き込む可能性を最小限に抑えることを目的としています。これにより、カーネルでのロックの競合が増える可能性があります。

次に、割り当てられたアイテムごとに、各ワーカーは以下のようになります:

  • W1: エントリのパスの先頭部分にディレクトリ以外のファイルがあるかどうか、またはエントリのパスにファイルがすでに存在するかどうかを確認します。その場合は、エントリに PC_ITEM_COLLIDED のマークを付けてスキップします(これについては後で詳しく説明します)。

  • W2: ファイルを作成します(O_CREAT と O_EXCLを使用)。

  • W3: ブロブをメモリにロードします(インフレーションとデルタ再構築)。

  • W4: 行末変換や再エンコードなど、必要なインプロセスフィルターを適用します。

  • W5: 結果を、W2で開かれたファイルデスクリプターに書き込みます。

  • W6: 書き込んだパスで fstat()`または `lstat() を呼び出し、操作の終了ステータスとアイテムの識別番号とともに、結果をメインプロセスに送り返します。

注意: 可能な場合、ステップW3からW5はストリーミング機構に委任され、ブロブ全体をメモリに保持する必要がなくなることに注意してください。

ワーカーがブロブの読み取りまたは作業ツリーへの書き込みに失敗した場合、空のファイルが残らないように、作成されたファイルを削除します。これは、ワーカーがファイルを削除できる「唯一の」時間です。

前述のように、チェックアウト操作をブロックするファイルを削除するのはメインプロセスの責任です(または、削除によってデータが失われ、ユーザーが --force を要求しなかった場合は中止します)。これは、競合状態を回避し、ステップW1でパスの衝突を適切に検出するために重要です。

ワーカーがアイテムの書き込みと必要な情報の返送を完了した後、メインプロセスは以下の2ステップで結果を処理します:

  • 最初に、 ワーカーから送信された lsat() 情報でメモリ内のインデックスを更新します。 (この情報は次のステップで必要になる可能性があるため、 これを最初に行う必要があります。)

  • 次に、ディスクに、衝突したアイテム(つまり、 PC_ITEM_COLLIDED でマークされたアイテム)を書き込みます。これについては、以下で詳しく説明します。

Path Collisions

パスの衝突は、2つの異なるパスがファイルシステムの同じエントリに対応している場合に発生します。 例えば、パス a と A は、大文字と小文字を区別しないファイルシステムで衝突します。

シーケンシャルチェックアウトは、チェックアウト前に作業ツリーにすでに存在していたファイルを処理するのと同じ方法で衝突を処理します。基本的には、書き込みたいパスがディスク上に既に存在するかどうかをチェックし、既存のファイルに未保存のデータがないことを確認してから、上書きします。 （よりわかりやすくするために、既存のファイルを削除して新しいファイルを作成します。）したがって、チェックアウトする衝突ファイルが複数ある場合、シーケンシャルなコードではそれぞれを書き込みますが、実際には最後のファイルのみがディスク上に残ります。

並列チェックアウトは、同じ動作を再現することを目的としています。 ただし、ワーカーにディスク上の同じファイルにあわてて書き込むことはできません。代わりに、ワーカーは、チェックアウトするエントリが既存のファイルと衝突するタイミングを検出し、 PC_ITEM_COLLIDED でマークします。 後で、メインプロセスは、競合状態のリスクなしに、これらのエントリを順番に checkout_entry() にフィードバックできます。クローンでは、これには、従来のシーケンシャルチェックアウトと同様に、衝突するエントリにマークを付けて、後でユーザーに警告を発する効果もあります。

ワーカーは、 同時に書き込まれるエントリ間の衝突と、 並列適格エントリと不適格エントリ間の衝突の両方を検出できます。 衝突検出の一般的な考え方は非常に単純です。 並列に適格なエントリごとに、 メイン・プロセスは、 このエントリの書き込みを妨げるすべてのファイルを(キューに入れる前に)削除する必要があります。 これには、 エントリの先頭のパスにあるディレクトリ以外のファイルが含まれます。 その後、 ワーカーにエントリが割り当てられると、 非ディレクトリ・ファイルと、 エントリのパスにある既存のファイルが再度検索されます。 これらのチェックのいずれかで何かが見つかった場合、 ワーカーはパスの衝突があったことを認識します。

並列チェックアウトでは、パスの衝突を、チェックアウト前にファイルが作業ツリーにすでに存在していた場合と区別できるため、代わりに、衝突するエントリのチェックアウトをスキップすることもできます。ただし、書き込まれない各エントリには、インデックスにNULLの lstat() フィールドがあります。 これにより、エントリがダーティであるかどうかを確認するためにファイルシステムに移動する必要があるため、インデックスを更新する必要がある後続のコマンドのパフォーマンスが低下する可能性があります。 したがって、衝突するグループにN個のエントリがあり、そのうちの1つだけを書き込み、 lstat() を実行することにした場合、後続のすべての git-status は、書き込まれたファイルをN-1回読み取り、変換、およびハッシュする必要があります。衝突するすべてのエントリをチェックアウトすることにより（シーケンシャルコードのように）、チェックアウト中にオーバーヘッドを1回だけ支払います。

Eligible Entries for Parallel Checkout

前述のように、 checkout_entry() に渡されたすべてのエントリが並列チェックアウトの対象と見なされるわけではありません。 具体的には、以下を除外します:

  • シンボリックリンク。パスの衝突と組み合わせて、ワーカーが間違った場所にファイルを書き込む可能性がある競合状態を回避するため。たとえば、大文字と小文字を区別しないファイルシステムでシンボリックリンク a → b と通常のファイル A/f を同時にチェックアウトすると、競合状態のため a/f でファイル A/f を書き込む可能性があります。

  • 外部フィルター（「ワンショット」フィルターまたは長時間実行プロセスフィルター）を必要とする通常のファイル。 これらのフィルターはGitのブラックボックスであり、独自の内部ロックまたは非同時の仮定を持っている場合があります。 したがって、複数のインスタンスを並行して実行することは安全ではない可能性があります。

    さらに、長時間実行されるフィルターは、遅延チェックアウト機能を使用して、フィルター処理されたブロブの返送を延期する場合があります。 遅延チェックアウトキューと並列チェックアウトキューは互換性がないため、分離したままにする必要があります。

    注：行末変換や再エンコードなど、内部フィルターのみを必要とする通常のファイルは、並列チェックアウトの対象となります。

不適格なエントリは、ワーカーを生成する「前に」従来のシーケンシャルコードパスによってチェックアウトされます。

注：サブモジュールのファイルは、 並列チェックアウトの対象にもなります(上記の除外カテゴリのいずれにも該当しない場合)。 ただし、 各サブモジュールは独自の子プロセスでチェックアウトされるため、 スーパー・プロジェクトとサブモジュールのファイルを同じ並列チェックアウトプロセスまたはキューに混在させることはありません。

The API

並列チェックアウトAPIは、チェックアウト機構の現在のユーザーへの変更を最小限に抑えることを目的として設計されました。 これは、シーケンシャルまたはパラレルチェックアウトのために別の関数を呼び出す必要がないことを意味します。 すでに述べたように、この機能が有効でエントリが適格である場合、 checkout_entry() は指定されたエントリを並列チェックアウトキューに自動的に挿入します。 それ以外の場合は、シーケンシャルコードを使用して、エントリをすぐに書き込みます。 一般に、並列チェックアウトAPIの呼び出し元は以下のようになります:

int pc_workers, pc_threshold, err = 0;
struct checkout state;

get_parallel_checkout_configs(&pc_workers, &pc_threshold);

/*
 * This check is not strictly required, but it
 * should save some time in sequential mode.
 */
if (pc_workers > 1)
        init_parallel_checkout();

for (each cache_entry ce to-be-updated)
        err |= checkout_entry(ce, &state, NULL, NULL);

err |= run_parallel_checkout(&state, pc_workers, pc_threshold, NULL, NULL);