Packファイル

Markdownとして表示 GitHubで編集ドキュメント: bfe242f

Packファイルは、gitで効率よく保存・転送するための仕組みです。オブジェクトを個別のzlib圧縮ファイルとして保存する代わりに、多数のオブジェクトを任意のdelta圧縮とともに1つのファイルにまとめます。ほぼすべてのクローン済みリポジトリがPackファイルを使用しています。

Packファイルの構造

Packファイル（.git/objects/pack/pack-{hash}.pack）には次の内容が含まれます：

コード

Header:   PACK (4 bytes) + version (4 bytes, big-endian) + count (4 bytes, big-endian)
Entries:  [type+size varint] [delta-base] [zlib-compressed data] ...
Trailer:  checksum of the pack (20 bytes SHA-1, 32 bytes SHA-256)

オブジェクト種類のエンコード

各エントリは、種類とサイズが交互に含まれる可変長整数から始まります：

コード

First byte: 1TTTSSSS
  TTT  = object type (1-4 for base objects, 6 for OFS_DELTA, 7 for REF_DELTA)
  SSSS = first 4 bits of uncompressed size
  MSB  = 1 means more size bytes follow

種類の値：

値	種類
1	Commit
2	Tree
3	Blob
4	Tag
6	OFS_DELTA（オフセットベースのdelta）
7	REF_DELTA（ハッシュベースのdelta）

Packファイルの読み込み

PHP

use Pitmaster\Pack\PackFile;

$pack = PackFile::open(
    '/path/to/.git/objects/pack/pack-abc123.pack',
    '/path/to/.git/objects/pack/pack-abc123.idx',
);

$pack->has($hex);               // Is the object in this pack?
$object = $pack->read($hex);    // Resolved GitObject, or null
$object = $pack->readAtOffset($offset);
$hashes = $pack->allHashes();

PackFileクラスは次の処理を行います：

PACKヘッダーとバージョン番号を検証する
.idxファイル内のオフセットを特定し、エントリーの型／サイズを表す可変長整数を解析する
zlib圧縮されたデータを展開する
ベースオブジェクトの場合：内容をそのまま返す
デルタオブジェクトの場合：ベースを解決し（チェーンをたどり）、デルタを適用して、解決済みオブジェクトをキャッシュする

パックインデックスファイル

すべての.packファイルには、高速な検索のために対応する.idxファイルがあります。インデックスがない場合、オブジェクトを見つけるにはパック全体をスキャンする必要があります。

v2インデックス形式

コード

Magic:    FF 74 4F 63 (identifies v2)
Version:  00 00 00 02
Fanout:   256 x 4-byte big-endian counts (cumulative)
Names:    N x 20-byte SHA-1 hashes, sorted (32 bytes for SHA-256)
CRC32s:   N x 4-byte CRC32 checksums
Offsets:  N x 4-byte pack offsets (MSB=1 means large offset table)
Large:    M x 8-byte offsets (for packs > 2GB)
Checksums: pack checksum + index checksum (20 bytes each for SHA-1)

PHP

use Pitmaster\Pack\PackIndex;

$index = PackIndex::open('/path/to/pack-abc123.idx');

// Look up an object
$offset = $index->findOffset($hex);  // Pack file offset, or null

// List all objects in the pack
$hashes = $index->allHashes();
$count = $index->objectCount();

ファンアウトテーブルによりO(log n)二分探索が可能になります。256個のエントリーは、各候補の先頭バイトで始まるハッシュの数を示します。

v1インデックス形式

CRC32チェックサムのない古い形式です。Pitmasterは両方に対応しています。PackIndex::open()はv2のマジックナンバーがない場合にv1ファイルを読み込むため、どちらの形式でも同じコードを使えます。

デルタの解決

デルタ化されたオブジェクトには、全内容の代わりに、ベースオブジェクトから内容を復元するための命令が保存されます。これにより、類似したオブジェクト（e.g、同じファイルの連続するバージョンなど）を大幅に圧縮できます。

デルタの種類

OFS_DELTA（型6）：ベースオブジェクトは、同じパックファイル内の負のオフセットで識別されます。ベースオブジェクトのハッシュを知る必要がないため、より一般的です。

REF_DELTA（型7）：ベースオブジェクトはハッシュで識別されます。Gitでは、ベースはパックの外部にある場合があります（thin pack）。PitmasterはREF_DELTAのベースを同じパック内だけで検索するため、thin packには対応していません（#16）。

デルタ命令

デルタの内容は、コピー命令と挿入命令の列です：

コード

Copy:   1XXXXXXX [offset bytes] [size bytes]   (copy from base)
Insert: 0LLLLLLL <L bytes of literal data>       (insert new data)

コピー命令：7つのXビットで、オフセットとサイズのどのバイトが存在するかを示します。オフセットは最大4バイト、サイズは最大3バイトです。サイズが0の場合は、0x10000（65536）バイトを意味します。

挿入命令：7つのLビットでリテラルデータの長さ（1～127バイト）を示します。L=0は予約済みであり、無効です。

DeltaApplier

PHP

use Pitmaster\Pack\DeltaApplier;

$result = DeltaApplier::apply($baseContent, $deltaInstructions);

DeltaApplierは次の処理を行います：

デルタヘッダーから、予想されるベースサイズと結果サイズを読み取る（LEB128エンコード）
命令を順に処理する：
- コピー：オフセットとサイズを取り出し、ベースの内容からバイトをコピーする
- 挿入：長さを取り出し、デルタデータからリテラルバイトをコピーする
結果サイズが予想サイズと一致することを確認する

デルタチェーン

デルタ化されたオブジェクトのベース自体も、デルタ化されている場合があります。PackFile::read()とreadAtOffset()はチェーンをたどります：

エントリーを読み込む。ベース型（commit、tree、blob、tag）なら、そのまま返す。
OFS_DELTAの場合：エンコードされた負のオフセットを現在のオフセットから引いてベースオフセットを計算し、ベースエントリーを読み込んで再帰処理する。
REF_DELTAの場合：同じパックのインデックスでハッシュからベースを検索し、再帰処理する。
解決済みのベースにデルタ命令を適用する。
無限に続くチェーンを防ぐため、PITMASTER_MAX_DELTA_CHAIN（既定値は50）を適用する。

PHP

// Configure max chain depth (integer)
define('PITMASTER_MAX_DELTA_CHAIN', 50);

// Read the effective limit
$max = \Pitmaster\Pack\DeltaResolver::maxChainDepth();

PackWriter

Pitmasterはネットワーク操作（push）用のパックファイルを書き込めます。

PHP

use Pitmaster\Pack\PackWriter;
use Pitmaster\Pack\PackIndexer;

$packData = PackWriter::encode($objects);           // GitObject[] to pack bytes
$paths = PackWriter::write($packDir, $objects);     // ['packPath' => ..., 'idxPath' => ..., 'hash' => ...]

$idxPath = PackIndexer::writeIndex($packPath);      // Build the .idx for a received pack

PackWriterは次の処理を行います：

パックに含めるオブジェクトを収集する
各オブジェクトを型／サイズの可変長整数ヘッダー付きでシリアライズする
内容をzlibで圧縮する
PACKヘッダー、エントリー、SHA-1トレーラーを書き込む

現在はベースオブジェクトのみを書き込みます（デルタ圧縮なし）。デルタ圧縮は後から追加できる最適化です。ストレージ効率の向上にはgit gcで再パックしてください。

PackEnumerator

パック内のすべてのオブジェクトをインデックス順に反復します：

PHP

use Pitmaster\Pack\PackEnumerator;

$enumerator = new PackEnumerator($packFile); // a PackFile opened with its .idx

foreach ($enumerator->enumerate() as $object) {
    echo "{$object->type->value} {$object->id->hex} {$object->size()}\n";
}

各項目は解決済みのGitObjectです。

MultiPackIndex

パックファイルが多数あるリポジトリでは、マルチパックインデックス（MIDX）を使うと、すべてのパックを対象に一括検索できます。

PHP

use Pitmaster\Pack\MultiPackIndex;

MIDXファイル（.git/objects/pack/multi-pack-index）には次の情報が含まれます：

ファンアウトテーブル（pack index v2と同様）
すべてのパックを通じてソートされたオブジェクトID
パックファイル名とオブジェクトごとのパック割り当て
各パックファイル内のオフセット

MultiPackIndex::open($path)はMIDXファイルを解析し、findObject($hex)とpackNames()を提供します。リポジトリ内のオブジェクト検索では使用されず、オブジェクトデータベースは常に個々の.idxファイルを読み込みます。

CommitGraph

commit-graphファイルは、コミット履歴のたどりとマージベースの計算を高速化します。

PHP

use Pitmaster\Pack\CommitGraph;

場所は.git/objects/info/commit-graphで、次の情報が含まれます：

ソート順のコミットOID
親情報（インデックス化されており、オブジェクトの読み込みは不要）
世代番号（到達可能性のクエリを高速化）
コミットのタイムスタンプ

Repository::merge()、mergeBase()、isBranchMerged()の内部にあるマージベース計算と、pushの早送りチェックでは、個々のコミットオブジェクトを読み込まず、commit-graphから親リンクを読み取ります。CommitWalker（log）は使用しません。

可変長整数

パックファイルでは、複数の可変長整数エンコード方式を使います：

Git varint（型／サイズヘッダー）

最上位ビットで後続バイトの有無を示す、MSB継続方式のエンコードです：

PHP

use Pitmaster\Encoding\VarInt;

$size = VarInt::decodePackSize($reader, $initialBits);  // continues the size from the first header byte
$offset = VarInt::decodeOfsOffset($reader);             // OFS_DELTA base distance
$header = VarInt::encodePackSize($type, $size);

LEB128（デルタヘッダー）

ベースサイズと結果サイズを表すデルタ命令ヘッダーで使われます：

PHP

use Pitmaster\Encoding\Leb128;

$value = Leb128::decodeUnsigned($reader);   // a BinaryReader
$bytes = Leb128::encodeUnsigned($value);

BinaryReader

位置を追跡する低レベルのバイトストリーム：

PHP

use Pitmaster\Encoding\BinaryReader;

$reader = new BinaryReader($data);
$byte = $reader->readByte();
$int = $reader->readUint32();   // big-endian
$bytes = $reader->read(20);
$hash = $reader->readHash(20);
$reader->position();  // Current offset
$reader->seek(0);