Перейти к содержимому

Pack-файлы

Просмотреть как Markdown Редактировать на GitHub Документация по bfe242f

Pack-файлы — это механизм git для эффективного хранения и передачи данных. Вместо хранения каждого объекта в отдельном сжатом с помощью zlib файле pack-файлы объединяют множество объектов в один файл с необязательным дельта-сжатием. Почти каждый клонированный репозиторий использует 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 Коммит
2 Дерево
3 Blob
4 Тег
6 OFS_DELTA (дельта на основе смещения)
7 REF_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:

  1. Проверяет заголовок PACK и номер версии
  2. Находит смещение в файле .idx и разбирает varint типа и размера записи
  3. Распаковывает данные, сжатые с помощью zlib
  4. Для базовых объектов: напрямую возвращает содержимое
  5. Для дельта-объектов: находит базовый объект (переходя по цепочке) и применяет дельту, кэшируя разрешенные объекты

Индексные файлы pack

Каждому файлу .pack соответствует файл .idx для быстрого поиска. Без индекса поиск объекта требует сканирования всего pack-файла.

Формат индекса 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();

Таблица fanout позволяет выполнять двоичный поиск O(log n): записи 256 указывают, сколько хешей начинаются с каждого возможного первого байта.

Формат индекса v1

Старый формат без контрольных сумм CRC32. Pitmaster поддерживает оба формата: PackIndex::open() читает файл v1, если отсутствует магическое значение v2, поэтому один и тот же код работает с обоими форматами.

Разрешение дельт

Дельта-объекты хранят инструкции для восстановления содержимого из базового объекта вместо полного содержимого. Это позволяет значительно сжимать похожие объекты (e.g., последовательные версии одного файла).

Типы дельт

OFS_DELTA (тип 6): базовый объект определяется отрицательным смещением в том же pack-файле. Этот тип встречается чаще, потому что для него не нужно знать хеш базового объекта.

REF_DELTA (тип 7): базовый объект определяется по хешу. В git базовый объект может находиться вне pack-файла (тонкие pack-файлы). Pitmaster ищет базовые объекты REF_DELTA только в том же pack-файле, поэтому тонкие 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 байт. Если размер равен нулю, он означает 0x10000 (65536) байт.

Инструкции вставки: 7 битов L задают длину литеральных данных (1-127 байт). L=0 зарезервировано и недопустимо.

DeltaApplier

PHP
use Pitmaster\Pack\DeltaApplier;

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

DeltaApplier:

  1. Читает ожидаемый размер базы и размер результата из заголовка дельты (кодировка LEB128)
  2. Перебирает инструкции:
    • Копирование: извлекает смещение и размер, копирует байты из содержимого базового объекта
    • Вставка: извлекает длину, копирует литеральные байты из данных дельты
  3. Проверяет, что размер результата совпадает с ожидаемым

Цепочки дельт

Базовый объект дельта-объекта сам может быть дельта-объектом. PackFile::read() и readAtOffset() проходят по цепочке:

  1. Читает запись. Если это базовый тип (commit, tree, blob, tag), возвращает ее.
  2. Если OFS_DELTA: вычисляет смещение базового объекта (текущее смещение минус закодированное отрицательное смещение), читает базовую запись и вызывает себя рекурсивно.
  3. Если REF_DELTA: ищет базовый объект по хешу в индексе того же pack-файла и вызывает себя рекурсивно.
  4. Применяет инструкции дельты к разрешенному базовому объекту.
  5. Ограничивает 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 может записывать pack-файлы для сетевых операций (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. Собирает объекты для включения в pack-файл
  2. Сериализует каждый объект с заголовком varint типа и размера
  3. Сжимает содержимое с помощью zlib
  4. Записывает заголовок PACK, записи и трейлер SHA-1

Сейчас записываются только базовые объекты (без дельта-сжатия). Дельта-сжатие — это оптимизация, которую можно добавить позже; для повышения эффективности хранения позвольте git gc выполнять перепаковку.

PackEnumerator

Перебирает все объекты в pack-файле в порядке индекса:

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

Для репозиториев с множеством pack-файлов мультииндекс (MIDX) обеспечивает единый поиск по всем pack-файлам.

PHP
use Pitmaster\Pack\MultiPackIndex;

Файл MIDX (.git/objects/pack/multi-pack-index) содержит:

  • Таблицу fanout (как в индексе pack-файла v2)
  • Идентификаторы объектов, отсортированные по всем pack-файлам
  • Имена pack-файлов и распределение объектов по ним
  • Смещения в отдельных pack-файлах

MultiPackIndex::open($path) разбирает файл MIDX и предоставляет findObject($hex) и packNames(). Поиск объектов в репозитории его не использует: база объектов всегда читает отдельные файлы .idx.

CommitGraph

Файл графа коммитов ускоряет обход истории коммитов и вычисление базового коммита слияния.

PHP
use Pitmaster\Pack\CommitGraph;

Находится в .git/objects/info/commit-graph и содержит:

  • OID коммитов в отсортированном порядке
  • Данные о родителях (индексированные, не требуют чтения объектов)
  • Номера поколений (для более быстрых запросов достижимости)
  • Временные метки коммитов

Если файл графа коммитов существует, вычисление базового коммита слияния для Repository::merge(), mergeBase(), isBranchMerged() и проверка ускоренной перемотки при push читают ссылки на родителей из графа коммитов, а не из отдельных объектов коммитов. CommitWalker (log) его не использует.

Целые числа переменной длины

В pack-файлах используются несколько кодировок целых чисел переменной длины:

Varint Git (заголовки типа и размера)

Кодировка с продолжением по старшему биту: старший бит указывает, что следуют дополнительные байты:

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 (заголовки дельты)

Используется в заголовках инструкций delta для размера исходных данных и результата:

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