Git
英语 ▾ 主题 ▾ 最新版本 ▾ gitformat-pack 最后更新于 2.44.0

名称

gitformat-pack - Git 包格式

概要

$GIT_DIR/objects/pack/pack-.{pack,idx}
$GIT_DIR/objects/pack/pack-.rev
$GIT_DIR/objects/pack/pack-*.mtimes
$GIT_DIR/objects/pack/multi-pack-index

描述

Git 包格式是 Git 存储其大部分主要存储库数据的方式。在存储库的生命周期中,松散对象(如果有)和较小的包会合并成较大的包。请参阅 git-gc[1]git-pack-objects[1]

包格式也用于网络传输,例如 gitprotocol-v2[5],并且在 gitformat-bundle[5] 的情况下,也是其他容器格式的一部分。

校验和和对象 ID

在使用传统 SHA-1 的存储库中,下面提到的包校验和、索引校验和和对象 ID(对象名称)都是使用 SHA-1 计算的。类似地,在 SHA-256 存储库中,这些值使用 SHA-256 计算。

pack-*.pack 文件具有以下格式

  • 开头会出现一个头部,包含以下内容:

    4-byte signature:
        The signature is: {'P', 'A', 'C', 'K'}
       4-byte version number (network byte order):
    Git currently accepts version number 2 or 3 but
           generates version 2 only.
    4-byte number of objects contained in the pack (network byte order)
    Observation: we cannot have more than 4G versions ;-) and
    more than 4G objects in a pack.
  • 头部后面跟着许多对象条目,每个条目如下所示:

    (undeltified representation)
    n-byte type and length (3-bit type, (n-1)*7+4-bit length)
    compressed data
       (deltified representation)
       n-byte type and length (3-bit type, (n-1)*7+4-bit length)
       base object name if OBJ_REF_DELTA or a negative relative
    offset from the delta object's position in the pack if this
    is an OBJ_OFS_DELTA object
       compressed delta data
    Observation: the length of each object is encoded in a variable
    length format and is not constrained to 32-bit or anything.
  • 尾部记录了上述所有内容的包校验和。

对象类型

有效的对象类型为:

  • OBJ_COMMIT (1)

  • OBJ_TREE (2)

  • OBJ_BLOB (3)

  • OBJ_TAG (4)

  • OBJ_OFS_DELTA (6)

  • OBJ_REF_DELTA (7)

类型 5 保留供将来扩展。类型 0 无效。

大小编码

本文档使用以下非负整数的“大小编码”:从每个字节中,使用最低有效七位来构成结果整数。只要最高有效位为 1,此过程就会继续;MSB 为 0 的字节提供最后七位。七位块被连接起来。后面的值更重要。

此大小编码不应与本文档中也使用的“偏移量编码”混淆。

增量表示

从概念上讲,只有四种对象类型:提交、树、标签和 Blob。但是为了节省空间,对象可以存储为另一个“基础”对象的“增量”。这些表示被分配了新的类型 ofs-delta 和 ref-delta,这仅在包文件中有效。

ofs-delta 和 ref-delta 都存储要应用于另一个对象(称为基础对象)以重建对象的“增量”。它们之间的区别在于,ref-delta 直接编码基础对象名称。如果基础对象在同一个包中,ofs-delta 则编码包中基础对象的偏移量。

如果基础对象在同一个包中,它也可能被增量化。Ref-delta 还可以引用包外部的对象(即所谓的“瘦包”)。但是,当存储在磁盘上时,包应自包含以避免循环依赖。

增量数据以基础对象的大小和要重建的对象的大小开头。这些大小使用上述的大小编码进行编码。增量数据的其余部分是一系列指令,用于从基础对象重建对象。如果基础对象被增量化,则必须先将其转换为规范形式。每个指令都会向目标对象追加越来越多的数据,直到它完成。到目前为止,有两个支持的指令:一个用于从源对象复制字节范围,另一个用于插入嵌入在指令本身的新数据。

每个指令的长度可变。指令类型由第一个八位字节的第七位确定。以下图表遵循 RFC 1951(Deflate 压缩数据格式)中的约定。

从基础对象复制的指令

+----------+---------+---------+---------+---------+-------+-------+-------+
| 1xxxxxxx | offset1 | offset2 | offset3 | offset4 | size1 | size2 | size3 |
+----------+---------+---------+---------+---------+-------+-------+-------+

这是从源对象复制字节范围的指令格式。它编码要从中复制的偏移量和要复制的字节数。偏移量和大小采用小端序。

所有偏移量和大小字节都是可选的。这是为了在编码小偏移量或大小是减少指令大小。第一个八位字节中的前七位确定接下来七个八位字节中的哪一个存在。如果设置了位零,则存在 offset1。如果设置了位一,则存在 offset2,依此类推。

请注意,更紧凑的指令不会更改偏移量和大小编码。例如,如果只省略了 offset2,如下所示,offset3 仍然包含位 16-23。即使它紧挨着 offset1,它也不会变成 offset2 并包含位 8-15。

+----------+---------+---------+
| 10000101 | offset1 | offset3 |
+----------+---------+---------+

在其最紧凑的形式中,此指令仅占用一个字节(0x80),并且偏移量和大小都被省略,这将具有默认值零。还有一个例外:大小零自动转换为 0x10000。

添加新数据的指令

+----------+============+
| 0xxxxxxx |    data    |
+----------+============+

这是在没有基础对象的情况下构造目标对象的指令。以下数据将附加到目标对象。第一个八位字节的前七位确定数据的字节大小。大小必须非零。

保留指令

+----------+============
| 00000000 |
+----------+============

这是为将来扩展保留的指令。

原始(版本 1)pack-*.idx 文件具有以下格式

  • 头部由 256 个 4 字节网络字节序整数组成。此表的第 N 个条目记录了相应包中对象的个数,其对象名称的第一个字节小于或等于 N。这称为第一级扇出表。

  • 头部后面跟着排序的 24 字节条目,包中的每个对象一个条目。每个条目为:

    4-byte network byte order integer, recording where the
    object is stored in the packfile as the offset from the
    beginning.
    one object name of the appropriate size.
  • 文件以尾部结尾:

    A copy of the pack checksum at the end of the corresponding
    packfile.
    Index checksum of all of the above.

包 Idx 文件

	--  +--------------------------------+
fanout	    | fanout[0] = 2 (for example)    |-.
table	    +--------------------------------+ |
	    | fanout[1]                      | |
	    +--------------------------------+ |
	    | fanout[2]                      | |
	    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
	    | fanout[255] = total objects    |---.
	--  +--------------------------------+ | |
main	    | offset                         | | |
index	    | object name 00XXXXXXXXXXXXXXXX | | |
table	    +--------------------------------+ | |
	    | offset                         | | |
	    | object name 00XXXXXXXXXXXXXXXX | | |
	    +--------------------------------+<+ |
	  .-| offset                         |   |
	  | | object name 01XXXXXXXXXXXXXXXX |   |
	  | +--------------------------------+   |
	  | | offset                         |   |
	  | | object name 01XXXXXXXXXXXXXXXX |   |
	  | ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~   |
	  | | offset                         |   |
	  | | object name FFXXXXXXXXXXXXXXXX |   |
	--| +--------------------------------+<--+
trailer	  | | packfile checksum              |
	  | +--------------------------------+
	  | | idxfile checksum               |
	  | +--------------------------------+
          .-------.
                  |
Pack file entry: <+
    packed object header:
1-byte size extension bit (MSB)
       type (next 3 bit)
       size0 (lower 4-bit)
       n-byte sizeN (as long as MSB is set, each 7-bit)
	size0..sizeN form 4+7+7+..+7 bit integer, size0
	is the least significant part, and sizeN is the
	most significant part.
    packed object data:
       If it is not DELTA, then deflated bytes (the size above
	is the size before compression).
If it is REF_DELTA, then
  base object name (the size above is the
	size of the delta data that follows).
         delta data, deflated.
If it is OFS_DELTA, then
  n-byte offset (see below) interpreted as a negative
	offset from the type-byte of the header of the
	ofs-delta entry (the size above is the size of
	the delta data that follows).
  delta data, deflated.
  offset encoding:
n bytes with MSB set in all but the last one.
The offset is then the number constructed by
concatenating the lower 7 bit of each byte, and
for n >= 2 adding 2^7 + 2^14 + ... + 2^(7*(n-1))
to the result.

版本 2 pack-*.idx 文件支持大于 4 GiB 的包,并且

have some other reorganizations.  They have the format:
  • 一个 4 字节的幻数\377tOc,这是一个不合理的扇出[0]值。

  • 一个 4 字节的版本号(= 2)

  • 一个 256 个条目的扇出表,就像 v1 一样。

  • 一个排序的对象名称表。这些对象被打包在一起,没有偏移量值,以减少特定对象名称的二分查找的缓存占用。

  • 一个 4 字节 CRC32 值表,表示打包的对象数据。这是 v2 中的新功能,因此在重新打包期间可以将压缩数据直接从一个包复制到另一个包,而不会出现未检测到的数据损坏。

  • 一个 4 字节偏移量值表(以网络字节序表示)。这些通常是 31 位包文件偏移量,但大偏移量被编码为下一个表的索引,其中 msbit 设置为 1。

  • 一个 8 字节偏移量条目表(对于小于 2 GiB 的包文件为空)。包文件以大量使用的对象位于前面进行组织,因此大多数对象引用不应该需要引用此表。

  • 与 v1 包文件相同的尾部

    A copy of the pack checksum at the end of the
    corresponding packfile.
    Index checksum of all of the above.

pack-*.rev 文件具有以下格式

  • 一个 4 字节的幻数0x52494458 (RIDX)。

  • 一个 4 字节的版本标识符(= 1)。

  • 一个 4 字节的哈希函数标识符(= 1 表示 SHA-1,2 表示 SHA-256)。

  • 一个索引位置表(每个打包的对象一个,总共有 num_objects 个,每个都是一个 4 字节的无符号整数,以网络顺序表示),按其在包文件中的对应偏移量排序。

  • 一个尾部,包含:

    checksum of the corresponding packfile, and
    a checksum of all of the above.

所有 4 字节数字均为网络顺序。

pack-*.mtimes 文件具有以下格式

所有 4 字节数字均为网络顺序。

  • 一个 4 字节的幻数0x4d544d45 (MTME)。

  • 一个 4 字节的版本标识符(= 1)。

  • 一个 4 字节的哈希函数标识符(= 1 表示 SHA-1,2 表示 SHA-256)。

  • 一个 4 字节无符号整数表。第 i 个值为相应包中第 i 个对象的修改时间 (mtime),按字典序 (索引) 排序。Mtime 计数标准纪元秒。

  • 一个尾部,包含相应包文件的校验和,以及上述所有内容的校验和(每个校验和的长度根据指定的哈希函数确定)。

多包索引 (MIDX) 文件具有以下格式

多包索引文件引用多个包文件和松散对象。

为了允许扩展将额外数据添加到 MIDX,我们将主体组织成“块”,并在主体的开头提供一个查找表。头部包括某些长度值,例如包的数量、基本 MIDX 文件的数量、哈希长度和类型。

所有 4 字节数字均为网络顺序。

头部

4-byte signature:
    The signature is: {'M', 'I', 'D', 'X'}
1-byte version number:
    Git only writes or recognizes version 1.
1-byte Object Id Version
    We infer the length of object IDs (OIDs) from this value:
	1 => SHA-1
	2 => SHA-256
    If the hash type does not match the repository's hash algorithm,
    the multi-pack-index file should be ignored with a warning
    presented to the user.
1-byte number of "chunks"
1-byte number of base multi-pack-index files:
    This value is currently always zero.
4-byte number of pack files

块查找

(C + 1) * 12 bytes providing the chunk offsets:
    First 4 bytes describe chunk id. Value 0 is a terminating label.
    Other 8 bytes provide offset in current file for chunk to start.
    (Chunks are provided in file-order, so you can infer the length
    using the next chunk position if necessary.)
The CHUNK LOOKUP matches the table of contents from
the chunk-based file format, see gitformat-chunk[5].
The remaining data in the body is described one chunk at a time, and
these chunks may be given in any order. Chunks are required unless
otherwise specified.

块数据

Packfile Names (ID: {'P', 'N', 'A', 'M'})
    Store the names of packfiles as a sequence of NUL-terminated
    strings. There is no extra padding between the filenames,
    and they are listed in lexicographic order. The chunk itself
    is padded at the end with between 0 and 3 NUL bytes to make the
    chunk size a multiple of 4 bytes.
Bitmapped Packfiles (ID: {'B', 'T', 'M', 'P'})
    Stores a table of two 4-byte unsigned integers in network order.
    Each table entry corresponds to a single pack (in the order that
    they appear above in the `PNAM` chunk). The values for each table
    entry are as follows:
    - The first bit position (in pseudo-pack order, see below) to
      contain an object from that pack.
    - The number of bits whose objects are selected from that pack.
OID Fanout (ID: {'O', 'I', 'D', 'F'})
    The ith entry, F[i], stores the number of OIDs with first
    byte at most i. Thus F[255] stores the total
    number of objects.
OID Lookup (ID: {'O', 'I', 'D', 'L'})
    The OIDs for all objects in the MIDX are stored in lexicographic
    order in this chunk.
Object Offsets (ID: {'O', 'O', 'F', 'F'})
    Stores two 4-byte values for every object.
    1: The pack-int-id for the pack storing this object.
    2: The offset within the pack.
	If all offsets are less than 2^32, then the large offset chunk
	will not exist and offsets are stored as in IDX v1.
	If there is at least one offset value larger than 2^32-1, then
	the large offset chunk must exist, and offsets larger than
	2^31-1 must be stored in it instead. If the large offset chunk
	exists and the 31st bit is on, then removing that bit reveals
	the row in the large offsets containing the 8-byte offset of
	this object.
[Optional] Object Large Offsets (ID: {'L', 'O', 'F', 'F'})
    8-byte offsets into large packfiles.
[Optional] Bitmap pack order (ID: {'R', 'I', 'D', 'X'})
    A list of MIDX positions (one per object in the MIDX, num_objects in
    total, each a 4-byte unsigned integer in network byte order), sorted
    according to their relative bitmap/pseudo-pack positions.

尾部

Index checksum of the above contents.

多包索引反向索引

与基于包的反向索引类似,多包索引也可用于生成反向索引。

此反向索引不是在偏移量、包和索引位置之间映射,而是在 MIDX 中对象的位置与其在 MIDX 描述的伪包中的位置之间映射(即,多包反向索引的第 i 个条目保存第 i 个对象在伪包顺序中的 MIDX 位置)。

为了阐明这些排序之间的区别,请考虑一个多包可达性位图(它尚不存在,但正是我们在此基础上构建的目标)。每个位需要对应于 MIDX 中的一个对象,因此我们需要一个从位位置到 MIDX 位置的有效映射。

一种解决方案是让比特占用 MIDX 存储的 oid 排序索引中的相同位置。但由于 oid 实际上是随机的,因此它们生成的连通性位图将没有局部性,因此压缩效果不佳。(这就是单包位图出于相同目的而使用包排序而不是 .idx 排序的原因。)

因此,我们希望基于包排序定义整个 MIDX 的排序,包排序具有更好的局部性(因此压缩效率更高)。我们可以认为,由 MIDX 中所有包的串联创建了一个伪包。例如,如果我们有一个包含三个包(a、b、c)的 MIDX,分别包含 10、15 和 20 个对象,我们可以想象对象的排序如下所示:

|a,0|a,1|...|a,9|b,0|b,1|...|b,14|c,0|c,1|...|c,19|

其中包的排序由 MIDX 的包列表定义,然后每个包中对象的排序与实际包文件中的排序相同。

给定包列表及其对象数量,您可以天真地重建该伪包排序(例如,位置 27 处的对象必须是 (c,1),因为包“a”和“b”占用了 25 个槽)。但有一个问题。对象可能在包之间重复,在这种情况下,MIDX 只存储一个指向该对象的指针(因此我们只希望位图中有一个槽)。

调用者可以通过按照其比特位置的顺序读取对象来自己处理重复项,但这与对象的数量成线性关系,对于普通的位图查找来说过于昂贵。构建反向索引可以解决此问题,因为它是索引的逻辑反向,并且该索引已经去除了重复项。但是,动态构建反向索引可能很昂贵。由于我们已经拥有基于包的反向索引的磁盘格式,因此让我们将其重用于 MIDX 的伪包。

MIDX 中的对象按以下顺序排列以串联伪包。令 pack(o) 返回 MIDX 从中选择 o 的包,并根据其数字 ID(由 MIDX 存储)定义包的排序。令 offset(o) 返回 opack(o) 中的对象偏移量。然后,如下比较 o1o2

  • 如果 pack(o1)pack(o2) 中的一个是首选的,而另一个不是,则首选的那个首先排序。

    (这是一个细节,允许 MIDX 位图确定包重用机制应使用哪个包,因为它可以向 MIDX 查询包含比特位置 0 处对象的包)。

  • 如果 pack(o1) ≠ pack(o2),则根据包 ID 以降序对这两个对象进行排序。

  • 否则,pack(o1) = pack(o2),并且对象按包顺序排序(即,当且仅当 offset(o1) < offset(o2) 时,o1 排在 o2 之前)。

简而言之,MIDX 的伪包是 MIDX 存储的包中对象的去重串联,按包顺序排列,包按 MIDX 顺序排列(首选包排在最前面)。

MIDX 的反向索引存储在 MIDX 本身内的可选 RIDX 块中。

BTMP

位图包文件 (BTMP) 块对多包索引的可达性位图中的对象编码附加信息。回想一下,来自 MIDX 的对象按“伪包”顺序排列(见上文)以用于可达性位图。

从上面的例子中,假设我们有包“a”、“b”和“c”,分别有 10、15 和 20 个对象。在伪包顺序中,它们的排列方式如下所示:

|a,0|a,1|...|a,9|b,0|b,1|...|b,14|c,0|c,1|...|c,19|

在使用单包位图(或等效地,具有首选包的多包可达性位图)时,git-pack-objects[1] 执行“逐字”重用,尝试重用位图或首选包文件的部分内容,而不是将对象添加到打包列表中。

当从现有包中重用字节块时,其中包含的任何对象都不需要添加到打包列表中,从而节省了内存和 CPU 时间。但是,只有在满足以下条件时才能重用来自现有包文件的部分内容:

  • 该块仅包含调用者请求的对象(即不包含调用者未明确或隐式请求的任何对象)。

  • 所有存储在非瘦包中作为偏移量或引用增量的对象也包含其基本对象在结果包中。

BTMP 块对必要的信息进行编码,以便如上所述在包集中实现多包重用。具体来说,BTMP 块为存储在 MIDX 中的每个包文件 p 编码三段信息(所有 32 位无符号整数,采用网络字节序),如下所示:

bitmap_pos

多包索引的可达性位图中由来自 p 的对象占用的第一个比特位置(在伪包顺序中)。

bitmap_nr

编码来自该包 p 的对象的比特位置数(包括 bitmap_pos 处的比特位置)。

例如,与上述示例(包“a”、“b”和“c”)相对应的 BTMP 块如下所示:

bitmap_pos bitmap_nr

包文件“a”

0

10

包文件“b”

10

15

包文件“c”

25

20

有了这些信息,我们可以将每个包文件视为单独可重用的,其方式与在实现 BTMP 块之前对单个包执行逐字包重用相同。

废弃包

废弃包功能提供了一种替代 Git 传统删除不可达对象的机制。本文档概述了 Git 的修剪机制,以及如何使用废弃包来实现相同目的。

背景

要从您的存储库中删除不可达对象,Git 提供了 git repack -Ad(参见 git-repack[1])。引用文档中的内容:

[...] unreachable objects in a previous pack become loose, unpacked objects,
instead of being left in the old pack. [...] loose unreachable objects will be
pruned according to normal expiry rules with the next 'git gc' invocation.

不可达对象不会立即被删除,因为这样做可能会与传入的推送发生冲突,而传入的推送可能会引用即将被删除的对象。相反,这些不可达对象将作为松散对象存储,并保持这种状态,直到它们比过期窗口更旧,此时它们将由 git-prune[1] 删除。

Git 必须将这些不可达对象存储为松散对象,以便跟踪它们的每个对象的 mtime。如果将这些不可达对象写入一个大包中,那么刷新该包(因为其中包含的对象被重写)或创建包含不可达对象的新包会导致包的 mtime 更新,并且其中的对象将永远不会离开过期窗口。相反,对象以松散的方式存储,以便跟踪各个对象的 mtime 并避免所有废弃对象同时被刷新。

当存储库包含许多尚未离开宽限期的不可达对象时,这可能会导致不良情况。在 .git/objects 的碎片中拥有大型目录会导致存储库性能下降。但是,如果存在足够多的不可达对象,这会导致 inode 饥饿并降低整个系统的性能。由于我们永远无法打包这些对象,因此这些存储库通常占用大量磁盘空间,因为我们只能对其进行 zlib 压缩,但不能将它们存储在增量链中。

废弃包

废弃包通过在包含所有松散对象的单个包旁边包含一个单独的文件(其中包含每个对象的 mtime)来消除将不可达对象存储为松散状态的需要。

生成新包时,git repack --cruft 会写入废弃包。 git-pack-objects[1]--cruft 选项。请注意,git repack --cruft 是一个经典的全合一重打包,这意味着结果包中的所有内容都是可达的,其他所有内容都是不可达的。写入后,--cruft 选项指示 git repack 生成另一个包,该包仅包含在上一步中未打包的对象(相当于将所有不可达对象打包在一起)。此过程如下:

  1. 枚举每个对象,将任何 (a) 不包含在保留包中,以及 (b) 其 mtime 在宽限期内的对象标记为遍历提示。

  2. 根据上一步中收集的提示执行可达性遍历,并将沿途的每个对象都添加到包中。

  3. 写入包以及记录每个对象时间戳的 .mtimes 文件。

当指示写入废弃包时,git-repack[1] 在内部调用此模式。至关重要的是,内存中保留包的集合恰好是重打包不会删除的包的集合;换句话说,它们包含存储库的所有可达对象。

当存储库已经有一个废弃包时,git repack --cruft 通常只向其中添加对象。一个例外是当 git repack 赋予 --cruft-expiration 选项时,这允许生成的废弃包省略过期的对象,而不是等待 git-gc[1] 稍后过期这些对象。

通常,git-gc[1] 负责删除过期的不可达对象。

替代方案

此设计的显著替代方案包括:

  • 每个对象的 mtime 数据的位置。

关于 mtime 数据的位置,选择了一个与包相关联的新辅助文件,以避免使 .idx 格式复杂化。如果 .idx 格式将来获得对可选数据块的支持,则可能需要将 .mtimes 格式合并到 .idx 本身中。

GIT

git[1] 套件的一部分

scroll-to-top