Μετάβαση στο περιεχόμενο

Αρχεία Pack

Προβολή ως Markdown Επεξεργασία στο GitHub Τεκμηρίωση στο bfe242f

Τα αρχεία pack είναι ο μηχανισμός του git για αποδοτική αποθήκευση και μεταφορά. Αντί να αποθηκεύουν κάθε αντικείμενο ως ξεχωριστό συμπιεσμένο με zlib αρχείο, συνδυάζουν πολλά αντικείμενα σε ένα αρχείο με προαιρετική συμπίεση delta. Σχεδόν κάθε κλωνοποιημένο αποθετήριο χρησιμοποιεί αρχεία 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 βάσει hash)

Ανάγνωση αρχείων 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. Για αντικείμενα delta: επιλύει τη βάση (ακολουθώντας αλυσίδες) και εφαρμόζει το delta, αποθηκεύοντας προσωρινά τα επιλυμένα αντικείμενα

Αρχεία ευρετηρίου 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 υποδεικνύουν πόσα hash αρχίζουν με κάθε πιθανό πρώτο byte.

Μορφή ευρετηρίου v1

Παλαιότερη μορφή χωρίς αθροίσματα ελέγχου CRC32. Το Pitmaster υποστηρίζει και τις δύο: το PackIndex::open() διαβάζει ένα αρχείο v1 όταν λείπει η μαγική τιμή v2, ώστε ο ίδιος κώδικας να λειτουργεί και για τις δύο.

Επίλυση delta

Τα αντικείμενα deltified αποθηκεύουν οδηγίες για την ανακατασκευή του περιεχομένου από ένα αντικείμενο βάσης, αντί να αποθηκεύουν ολόκληρο το περιεχόμενο. Έτσι επιτυγχάνεται σημαντική συμπίεση για παρόμοια αντικείμενα (e.g., διαδοχικές εκδόσεις του ίδιου αρχείου).

Τύποι delta

OFS_DELTA (τύπος 6): το αντικείμενο βάσης προσδιορίζεται από αρνητική μετατόπιση μέσα στο ίδιο αρχείο pack. Είναι συνηθέστερο, επειδή δεν απαιτεί να είναι γνωστό το hash του αντικειμένου βάσης.

REF_DELTA (τύπος 7): το αντικείμενο βάσης προσδιορίζεται από το hash του. Στο git, η βάση μπορεί να βρίσκεται εκτός του pack (thin packs). Το Pitmaster αναζητά βάσεις REF_DELTA μόνο μέσα στο ίδιο pack, επομένως τα thin packs δεν υποστηρίζονται (#16).

Οδηγίες delta

Το περιεχόμενο delta είναι μια ακολουθία οδηγιών αντιγραφής και εισαγωγής:

Κώδικας
Copy:   1XXXXXXX [offset bytes] [size bytes]   (copy from base)
Insert: 0LLLLLLL <L bytes of literal data>       (insert new data)

Οδηγίες αντιγραφής: τα 7 bit X υποδεικνύουν ποια byte μετατόπισης και μεγέθους υπάρχουν. Η μετατόπιση έχει έως 4 byte και το μέγεθος έως 3 byte. Αν το μέγεθος είναι μηδέν, σημαίνει 0x10000 (65536) byte.

Οδηγίες εισαγωγής: τα 7 bit L δίνουν το μήκος των κυριολεκτικών δεδομένων (1-127 byte). Το L=0 είναι δεσμευμένο/μη έγκυρο.

DeltaApplier

PHP
use Pitmaster\Pack\DeltaApplier;

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

Το DeltaApplier:

  1. Διαβάζει το αναμενόμενο μέγεθος βάσης και το μέγεθος αποτελέσματος από την κεφαλίδα delta (κωδικοποίηση LEB128)
  2. Διατρέχει τις οδηγίες:
    • Αντιγραφή: εξάγει τη μετατόπιση και το μέγεθος και αντιγράφει byte από το περιεχόμενο της βάσης
    • Εισαγωγή: εξάγει το μήκος και αντιγράφει κυριολεκτικά byte από τα δεδομένα delta
  3. Επαληθεύει ότι το μέγεθος του αποτελέσματος συμφωνεί με το αναμενόμενο μέγεθος

Αλυσίδες delta

Η βάση ενός deltified αντικειμένου μπορεί και η ίδια να είναι deltified. Τα PackFile::read() και readAtOffset() ακολουθούν την αλυσίδα:

  1. Διαβάζει την εγγραφή. Αν είναι βασικός τύπος (commit, tree, blob, tag), την επιστρέφει.
  2. Αν είναι OFS_DELTA: υπολογίζει τη μετατόπιση της βάσης (τρέχουσα μετατόπιση μείον την κωδικοποιημένη αρνητική μετατόπιση), διαβάζει την εγγραφή βάσης και συνεχίζει αναδρομικά.
  3. Αν είναι REF_DELTA: αναζητά τη βάση με hash στο ευρετήριο του ίδιου pack και συνεχίζει αναδρομικά.
  4. Εφαρμόζει τις οδηγίες delta στη βάση που έχει επιλυθεί.
  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

Προς το παρόν γράφει μόνο αντικείμενα βάσης (χωρίς συμπίεση delta). Η συμπίεση delta είναι μια βελτιστοποίηση που μπορεί να προστεθεί αργότερα· αφήστε το git gc να δημιουργήσει ξανά τα αρχεία pack για αποδοτικότερη αποθήκευση.

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, το multi-pack-index (MIDX) παρέχει ενιαία αναζήτηση σε όλα τα pack.

PHP
use Pitmaster\Pack\MultiPackIndex;

Το αρχείο MIDX (.git/objects/pack/multi-pack-index) περιέχει:

  • Έναν πίνακα fanout (όπως το ευρετήριο pack v2)
  • Αναγνωριστικά αντικειμένων ταξινομημένα σε όλα τα pack
  • Ονόματα αρχείων pack και αντιστοιχίσεις κάθε αντικειμένου σε pack
  • Μετατοπίσεις μέσα στα μεμονωμένα αρχεία pack

Το MultiPackIndex::open($path) αναλύει ένα αρχείο MIDX και παρέχει findObject($hex) και packNames(). Οι αναζητήσεις αντικειμένων στο αποθετήριο δεν το χρησιμοποιούν: η βάση δεδομένων αντικειμένων διαβάζει πάντα τα μεμονωμένα αρχεία .idx.

CommitGraph

Το αρχείο commit-graph επιταχύνει τη διάσχιση του ιστορικού των commit και τον υπολογισμό της βάσης συγχώνευσης.

PHP
use Pitmaster\Pack\CommitGraph;

Βρίσκεται στο .git/objects/info/commit-graph και περιέχει:

  • OID commit σε ταξινομημένη σειρά
  • Πληροφορίες γονέων (με ευρετήριο, χωρίς να απαιτείται ανάγνωση αντικειμένων)
  • Αριθμούς γενιάς (για ταχύτερα ερωτήματα προσβασιμότητας)
  • Χρονικές σημάνσεις commit

Όταν υπάρχει, ο υπολογισμός της βάσης συγχώνευσης πίσω από τα Repository::merge(), mergeBase(), isBranchMerged() και τον έλεγχο γρήγορης προώθησης του push διαβάζει τους συνδέσμους γονέων από το commit-graph αντί να διαβάζει μεμονωμένα αντικείμενα commit. Το CommitWalker (log) δεν το χρησιμοποιεί.

Ακέραιοι μεταβλητού μήκους

Τα αρχεία pack χρησιμοποιούν πολλές κωδικοποιήσεις ακεραίων μεταβλητού μήκους:

Git varint (κεφαλίδες τύπου/μεγέθους)

Κωδικοποίηση συνέχισης MSB, όπου το πιο σημαντικό bit υποδεικνύει ότι ακολουθούν περισσότερα byte:

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)

Χρησιμοποιείται στις κεφαλίδες οδηγιών delta για το μέγεθος βάσης και το μέγεθος αποτελέσματος:

PHP
use Pitmaster\Encoding\Leb128;

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

BinaryReader

Ροή byte χαμηλού επιπέδου με παρακολούθηση θέσης:

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