When and how does git use deltas for storage?

Git 2.18 (Q2 2018) documents delta usage in Documentation/technical/pack-format

See commit 011b648 (11 May 2018) by Nguyễn Thái Ngọc Duy (pclouds).
(Merged by Junio C Hamano -- gitster -- in commit b577198, 23 May 2018)

pack-format.txt: more details on pack file format

The current document mentions OBJ_* constants without their actual values. A git developer would know these are from cache.h but that's not very friendly to a person who wants to read this file to implement a pack file parser.

Similarly, the deltified representation is not documented at all (the "document" is basically patch-delta.c). Translate that C code to English with a bit more about what ofs-delta and ref-delta mean.

So the documentation now states:

Object types

Valid object types are:

  • OBJ_COMMIT (1)
  • OBJ_TREE (2)
  • OBJ_BLOB (3)
  • OBJ_TAG (4)
  • OBJ_OFS_DELTA (6)
  • OBJ_REF_DELTA (7)

Type 5 is reserved for future expansion. Type 0 is invalid.

Deltified representation

Conceptually there are only four object types: commit, tree, tag and blob.
However to save space, an object could be stored as a "delta" of another "base" object.
These representations are assigned new types ofs-delta and ref-delta, which is only valid in a pack file.

Both ofs-delta and ref-delta store the "delta" to be applied to another object (called 'base object') to reconstruct the object.
The difference between them is,

  • ref-delta directly encodes 20-byte base object name.
    • If the base object is in the same pack, ofs-delta encodes the offset of the base object in the pack instead.

The base object could also be deltified if it's in the same pack.
Ref-delta can also refer to an object outside the pack (i.e. the so-called "thin pack"). When stored on disk however, the pack should be self contained to avoid cyclic dependency.

The delta data is a sequence of instructions to reconstruct an object from the base object.
If the base object is deltified, it must be converted to canonical form first. Each instruction appends more and more data to the target object until it's complete.
There are two supported instructions so far:

  • one for copy a byte range from the source object and
  • one for inserting new data embedded in the instruction itself.

Each instruction has variable length. Instruction type is determined by the seventh bit of the first octet. The following diagrams follow the convention in RFC 1951 (Deflate compressed data format).

With Git 2.20 (Q4 2018), malformed or crafted data in packstream can make our code attempt to read or write past the allocated buffer and abort, instead of reporting an error, which has been fixed.

t5303: use printf to generate delta bases

The exact byte count of the delta base file is important.
The test-delta helper will feed it to patch_delta(), which will barf if it doesn't match the size byte given in the delta.
Using "echo" may end up with unexpected line endings on some platforms (e.g,. "\r\n" instead of just "\n").

This actually wouldn't cause the test to fail (since we already expect test-delta to complain about these bogus deltas), but would mean that we're not exercising the code we think we are.

Let's use printf instead (which we already trust to give us byte-perfect output when we generate the deltas).

With Git 2.25 (Q1 2020), in a repository with many packfiles, the cost of the procedure that avoids registering the same packfile twice was unnecessarily high by using an inefficient search algorithm, which has been corrected.

See commit ec48540 (27 Nov 2019) by Colin Stolley (ccstolley).
(Merged by Junio C Hamano -- gitster -- in commit 6d831b8, 16 Dec 2019)

packfile.c: speed up loading lots of packfiles

Signed-off-by: Colin Stolley
Helped-by: Jeff King

When loading packfiles on start-up, we traverse the internal packfile list once per file to avoid reloading packfiles that have already been loaded. This check runs in quadratic time, so for poorly maintained repos with a large number of packfiles, it can be pretty slow.

Add a hashmap containing the packfile names as we load them so that the average runtime cost of checking for already-loaded packs becomes constant.

Add a perf test to p5303 to show speed-up.

The existing p5303 test runtimes are dominated by other factors and do not show an appreciable speed-up.
The new test in p5303 clearly exposes a speed-up in bad cases.
In this test we create 10,000 packfiles and measure the start-up time of git rev-parse, which does little else besides load in the packs.

Here are the numbers for the new p5303 test:

Test                         HEAD^             HEAD
---------------------------------------------------------------------
5303.12: load 10,000 packs   1.03(0.92+0.10)   0.12(0.02+0.09) -88.3%

[jc: squashed the change to call hashmap in install_packed_git() by peff]
Signed-off-by: Junio C Hamano


Git only uses deltas in "packfiles". Initially, each git object is written as a separate file (as you found). Later, git can pack many objects into one file, called a "pack file". The pack file is then compressed, which automatically exploits any repetitions between the files in the packfile (or repetitions inside files).

This packing is performed by git repack. You can see it in action by invoking it manually. If you run git repack -ad on a git repo, you should see used disk space and number of files under .git/objects drop, as files are combined into packs and compressed.

In practice, you don't usually need to run git repack. Git by default regularly runs git gc, which in turn runs git repack when necessary. So relax, git has your back :-).

The excellent "git book" also has a chapter on packfiles with more explanations: http://git-scm.com/book/en/v2/Git-Internals-Packfiles .

Tags:

Git

Recent Posts