Przejdź do treści

Pliki pakietów

Wyświetl jako Markdown Edytuj w GitHub Dokumentacja: bfe242f

Pliki pakietów to mechanizm git służący do wydajnego przechowywania i przesyłania danych. Zamiast przechowywać każdy obiekt jako osobny plik skompresowany zlib, pliki pakietów łączą wiele obiektów w jeden plik z opcjonalną kompresją deltową. Prawie każde sklonowane repozytorium korzysta z plików pakietów.

Struktura pliku pakietu

Plik pakietu (.git/objects/pack/pack-{hash}.pack) zawiera:

Kod
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)

Kodowanie typów obiektów

Każdy wpis zaczyna się liczbą całkowitą o zmiennej długości, w której typ i rozmiar są przeplatane:

Kod
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

Wartości typów:

Wartość Typ
1 Commit
2 Drzewo
3 Blob
4 Tag
6 OFS_DELTA (delta oparta na przesunięciu)
7 REF_DELTA (delta oparta na skrócie)

Odczytywanie plików pakietów

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();

Klasa PackFile:

  1. Weryfikuje nagłówek PACK i numer wersji
  2. Odczytuje przesunięcie z pliku .idx i analizuje zapis varint typu/rozmiaru wpisu
  3. Dekompresuje dane skompresowane zlib
  4. W przypadku obiektów bazowych zwraca bezpośrednio zawartość
  5. W przypadku obiektów deltowych rozwiązuje obiekt bazowy (podążając za łańcuchami) i stosuje deltę, buforując rozwiązane obiekty

Pliki indeksu pakietów

Każdemu plikowi .pack odpowiada plik .idx, który umożliwia szybkie wyszukiwanie. Bez indeksu znalezienie obiektu wymaga przeszukania całego pakietu.

Format indeksu v2

Kod
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();

Tabela fanout umożliwia wyszukiwanie binarne O(log n): wpisy 256 wskazują, ile skrótów zaczyna się od każdego możliwego pierwszego bajtu.

Format indeksu v1

Starszy format bez sum kontrolnych CRC32. Pitmaster obsługuje oba formaty: PackIndex::open() odczytuje plik v1, gdy brakuje sygnatury v2, dzięki czemu ten sam kod działa w obu przypadkach.

Rozwiązywanie delt

Obiekty deltowe przechowują instrukcje odtwarzania zawartości na podstawie obiektu bazowego, zamiast przechowywać całą zawartość. Pozwala to znacznie zmniejszyć rozmiar podobnych obiektów (e.g., kolejnych wersji tego samego pliku).

Typy delt

OFS_DELTA (typ 6): obiekt bazowy jest identyfikowany przez ujemne przesunięcie w tym samym pliku pakietu. Ten typ jest częstszy, ponieważ nie wymaga znajomości skrótu obiektu bazowego.

REF_DELTA (typ 7): obiekt bazowy jest identyfikowany na podstawie swojego hasza. W Git obiekt bazowy może znajdować się poza pakietem (w przypadku pakietów typu thin). Pitmaster wyszukuje podstawy REF_DELTA tylko w tym samym pakiecie, dlatego pakiety typu thin nie są obsługiwane (#16).

Instrukcje delty

Zawartość delty to sekwencja instrukcji kopiowania i wstawiania:

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

Instrukcje kopiowania: 7 bitów X wskazuje, które bajty przesunięcia i rozmiaru są obecne. Przesunięcie może mieć do 4 bajtów, a rozmiar do 3 bajtów. Jeśli rozmiar wynosi zero, oznacza 0x10000 (65536) bajtów.

Instrukcje wstawiania: 7 bitów L określa długość danych literalnych (1–127 bajtów). L=0 jest zarezerwowane/niedozwolone.

DeltaApplier

PHP
use Pitmaster\Pack\DeltaApplier;

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

DeltaApplier:

  1. Odczytuje oczekiwany rozmiar bazowy i rozmiar wyniku z nagłówka delty (zakodowane w LEB128)
  2. Iteruje po instrukcjach:
    • Kopiowanie: wyodrębnia przesunięcie i rozmiar, a następnie kopiuje bajty z zawartości bazowej
    • Wstawianie: wyodrębnia długość, a następnie kopiuje bajty literalne z danych delty
  3. Weryfikuje, czy rozmiar wyniku odpowiada oczekiwanemu rozmiarowi

Łańcuchy delt

Podstawa obiektu deltowego może sama być obiektem deltowym. PackFile::read() i readAtOffset() podążają za łańcuchem:

  1. Odczytuje wpis. Jeśli jest to typ bazowy (commit, drzewo, blob, tag), zwraca go.
  2. Jeśli OFS_DELTA: oblicza przesunięcie bazowe (bieżące przesunięcie minus zakodowane ujemne przesunięcie), odczytuje wpis bazowy i wywołuje się rekurencyjnie.
  3. Jeśli REF_DELTA: wyszukuje obiekt bazowy według skrótu w indeksie tego samego pakietu i wywołuje się rekurencyjnie.
  4. Stosuje instrukcje delty do rozwiązanej podstawy.
  5. Wymusza PITMASTER_MAX_DELTA_CHAIN (domyślnie 50), aby zapobiec niekontrolowanemu rozrostowi łańcuchów.
PHP
// Configure max chain depth (integer)
define('PITMASTER_MAX_DELTA_CHAIN', 50);

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

PackWriter

Pitmaster może zapisywać pliki pakietów na potrzeby operacji sieciowych (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:

  1. Zbiera obiekty, które mają znaleźć się w pakiecie
  2. Serializuje każdy obiekt z nagłówkiem varint typu/rozmiaru
  3. Kompresuje zawartość zlib
  4. Zapisuje nagłówek PACK, wpisy i końcową sumę kontrolną SHA-1

Obecnie zapisuje tylko obiekty bazowe (bez kompresji deltowej). Kompresja deltowa to optymalizacja, którą można dodać później; pozwól git gc przepakować dane, aby zwiększyć wydajność przechowywania.

PackEnumerator

Iteruj po wszystkich obiektach w pakiecie, w kolejności indeksu:

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";
}

Każdy element to rozwiązany GitObject.

MultiPackIndex

W repozytoriach z wieloma plikami pakietów multi-pack-index (MIDX) umożliwia wyszukiwanie w jednym indeksie obejmującym wszystkie pakiety.

PHP
use Pitmaster\Pack\MultiPackIndex;

Plik MIDX (.git/objects/pack/multi-pack-index) zawiera:

  • Tabelę fanout (podobną do indeksu pakietu v2)
  • Identyfikatory obiektów posortowane w ramach wszystkich pakietów
  • Nazwy plików pakietów i przypisanie każdego obiektu do pakietu
  • Przesunięcia w poszczególnych plikach pakietów

MultiPackIndex::open($path) analizuje plik MIDX i udostępnia findObject($hex) oraz packNames(). Wyszukiwanie obiektów w repozytorium z niego nie korzysta: baza obiektów zawsze odczytuje poszczególne pliki .idx.

CommitGraph

Plik commit-graph przyspiesza przechodzenie przez historię commitów i obliczanie bazy scalania.

PHP
use Pitmaster\Pack\CommitGraph;

Znajduje się w .git/objects/info/commit-graph i zawiera:

  • Identyfikatory OID commitów w kolejności sortowania
  • Informacje o rodzicach (indeksowane, bez konieczności odczytywania obiektów)
  • Numery generacji (na potrzeby szybszych zapytań o osiągalność)
  • Znaczniki czasu commitów

Gdy plik commit-graph jest dostępny, obliczanie bazy scalania wykorzystywane przez Repository::merge(), mergeBase(), isBranchMerged() i kontrolę szybkiego przewijania przy push odczytuje powiązania z rodzicami z commit-graph zamiast odczytywać poszczególne obiekty commitów. CommitWalker (log) z niego nie korzysta.

Liczby całkowite o zmiennej długości

Pliki pakietów korzystają z kilku kodowań liczb całkowitych o zmiennej długości:

Varint Git (nagłówki typu/rozmiaru)

Kodowanie z kontynuacją MSB, gdzie najbardziej znaczący bit wskazuje, że następują kolejne bajty:

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 (nagłówki delt)

Używane w nagłówkach instrukcji delty dla rozmiaru bazowego i rozmiaru wyniku:

PHP
use Pitmaster\Encoding\Leb128;

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

BinaryReader

Strumień bajtów niskiego poziomu ze śledzeniem pozycji:

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);