インターリーブデルタ

インターリーブ デルタ( SCCS ウィーブ)は、ソース コード コントロール システムでファイルのすべてのリビジョンを保存するために使用する方法です。すべてのリビジョンのすべての行が 1 つのデータ ブロックにまとめられ、ファイルのどのリビジョンにどの行が含まれているかを示す制御命令が散在しています。インターリーブ デルタは、従来、行指向のテキスト ファイルを念頭に置いて実装されていますが、この方法をバイナリ ファイルにも適用できます。

インターリーブ デルタは、1975 年にMarc RochkindによってSCCS で初めて実装されました。その設計により、すべてのバージョンが同時に利用可能になるため、どのリビジョンを取得するのにも同じ時間がかかります。また、1 つのブロックに各行の作成者 (blaming) を識別するのに十分な情報が含まれています。 ^[1]一方、ファイルのすべてのリビジョンが解析されるため、リビジョンが追加されるにつれてすべての操作が遅くなります。インターリーブ デルタという用語は、1982 年後半に、 SCCS のウィーブをRCS の新しいリバース デルタメカニズムと比較した、 Revision Control Systemの作者であるWalter F. Tichyによって造られました。 ^[2]

SCCSでは、次の織りブロック

^AI1 1 2 3 4 5 6 7 8 9 10 11 12
 ^西暦2年
 フー
 ^AE2 より
 バー
 ^AI2 より
 バズ
 ^AE2 より
 ^AE1 1 1 1

最初のリリースの行「foo」と「bar」、および 2 番目のリビジョンの行「bar」と「baz」を含むファイルを表します。文字列「^A」は、コントロール A 文字を表します。

インターリーブデルタブロック内の制御ラインは次のような意味を持つ: ^[3]

• ^AI serial 指定されたシリアル番号で挿入された行のブロックを開始します。
• ^AD serial 指定されたシリアル番号で削除された行のブロックを開始します。
• ^AE シリアル同じシリアル番号を使用する対応する^AIまたは^ADステートメントの ブロック終了。

このようなインターリーブされたデルタ ブロックからリビジョンを抽出するのにかかる時間は、アーカイブのサイズに比例します。アーカイブのサイズは、すべてのリビジョンのすべての異なる行のサイズの合計です。

特定のリビジョンを抽出するには、インターリーブされたデルタ内のシリアル番号でタグ付けされた特定のブロックが出力にコピーされるかどうかを示す構造体の配列を構築する必要があります。元の SCCS 実装では、特定のリビジョンを抽出する方法を知るために、デルタ内の異なるシリアル番号ごとに約 100 バイトのストレージが必要です。したがって、100 万のデルタを含む SCCS 履歴ファイルを解凍するには、100 MB の仮想メモリが必要です。注釈付きファイルの取得が不要な場合は、デルタごとに約 32 バイトのサイズを削減できます。

織り方の利点は次のとおりです。

• ファイルのすべてのリビジョンの取得時間は均一です。
• 追加コストなしで、ファイルのすべての行に最終変更のリビジョン、最終変更の作成者、最終変更の時刻を注釈付けできます。
• 追加コストなしで重複しないブランチをマージする可能性。

• ソースコード管理システム
• サン ワークショップ チームウェア
• ビットキーパー^[4]

Bazaarは2006年にインターリーブデルタを使用する予定でしたが^[5]、実際にbzr 0.1で実装された後、パフォーマンスが悪かったため廃止されました。現在でもweaveスタイルのマージアルゴリズムを提供しています。^[6]

• デルタエンコーディング