简体中文 ▾ 主题 ▾ 最新版本 ▾ gitformat-commit-graph 最后更新于 2.47.0

名称

gitformat-commit-graph - Git 提交图格式

概要

$GIT_DIR/objects/info/commit-graph
$GIT_DIR/objects/info/commit-graphs/*

描述

Git 提交图存储了一系列提交对象标识符(OID)及一些关联的元数据,包括:

  • 提交的生成编号(generation number)。

  • 根树(root tree)的 OID。

  • 提交日期。

  • 提交的父提交,使用图文件内的位置引用进行存储。

  • 如果需要,存储提交的布隆过滤器(Bloom filter),其中包含该提交与其第一个父提交之间发生变更的路径。

这些位置引用存储为 32 位无符号整数,对应于提交 OID 列表中的数组位置。由于我们使用一些特殊的常量来追踪父提交,因此最多可以存储 (1 << 30) + (1 << 29) + (1 << 28) - 1(约 18 亿)个提交。

提交图文件具有以下格式

为了允许添加额外数据的扩展,我们将主体组织为“块”(chunks),并在主体开头提供一个二进制查找表。头部包含某些值,例如块的数量和哈希类型。

所有多字节数字均采用网络字节序。

头部 (HEADER)

4-byte signature:
    The signature is: {'C', 'G', 'P', 'H'}
1-byte version number:
    Currently, the only valid version is 1.
 1-byte Hash Version
     We infer the hash length (H) from this value:
1 => SHA-1
2 => SHA-256
     If the hash type does not match the repository's hash algorithm, the
     commit-graph file should be ignored with a warning presented to the
     user.
1-byte number (C) of "chunks"
1-byte number (B) of base commit-graphs
    We infer the length (H*B) of the Base Graphs chunk
    from this value.

块查找 (CHUNK LOOKUP)

(C + 1) * 12 bytes listing the table of contents for the chunks:
    First 4 bytes describe the chunk id. Value 0 is a terminating label.
    Other 8 bytes provide the byte-offset in current file for chunk to
    start. (Chunks are ordered contiguously in the file, so you can infer
    the length using the next chunk position if necessary.) Each chunk
    ID appears at most once.
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.

块数据 (CHUNK DATA)

OID 分支 (ID: {O, I, D, F}) (256 * 4 字节)

The ith entry, F[i], stores the number of OIDs with first
byte at most i. Thus F[255] stores the total
number of commits (N).

OID 查找 (ID: {O, I, D, L}) (N * H 字节)

The OIDs for all commits in the graph, sorted in ascending order.

提交数据 (ID: {C, D, A, T }) (N * (H + 16) 字节)

  • 前 H 个字节为根树的 OID。

  • 接下来的 8 个字节用于存储第 i 个提交的前两个父提交的位置。如果该位置没有父提交,则存储值 0x70000000。如果父提交多于两个,第二个值的最高位会被置位,其余位存储指向“额外边缘列表”(Extra Edge List)块中的数组位置。

  • 接下来的 8 个字节存储提交的拓扑层级(生成编号 v1)和提交时间(自 EPOCH 以来的秒数)。生成编号使用前 4 个字节中的高 30 位,提交时间使用后 4 个字节的 32 位,加上最低字节的最低 2 位,用于存储提交时间的第 33 位和第 34 位。

生成数据 (ID: {G, D, A, 2 }) (N * 4 字节) [可选]

  • 此 4 字节值列表存储提交的修正提交日期偏移量,排列顺序与提交数据块相同。

  • 如果修正提交日期偏移量无法存储在 31 位内,则该值的最高位置位,其余位存储修正提交日期在“生成数据溢出”(Generation Data Overflow)块中的位置。

  • 生成数据块仅在提交图文件由兼容版本的 Git 写入时存在;在拆分提交图链的情况下,最顶层也会包含生成数据块。

生成数据溢出 (ID: {G, D, O, 2 }) [可选]

  • 此 8 字节值列表存储无法存储在 31 位内的修正提交日期偏移量。

  • 生成数据溢出块仅在生成数据块存在且至少有一个修正提交日期偏移量无法存储在 31 位内时存在。

额外边缘列表 (ID: {E, D, G, E}) [可选]

This list of 4-byte values store the second through nth parents for
all octopus merges. The second parent value in the commit data stores
an array position within this list along with the most-significant bit
on. Starting at that array position, iterate through this list of commit
positions for the parents until reaching a value with the most-significant
bit on. The other bits correspond to the position of the last parent.

布隆过滤器索引 (ID: {B, I, D, X}) (N * 4 字节) [可选]

  • 第 i 个条目 BIDX[i] 存储从提交 0 到提交 i(含)的所有布隆过滤器的总字节数(按字典序)。第 i 个提交的布隆过滤器范围从 BIDX[i-1] 到 BIDX[i](加上头部长度),其中 BIDX[-1] 为 0。

  • 如果 BDAT 块不存在,则忽略 BIDX 块。

布隆过滤器数据 (ID: {B, D, A, T}) [可选]

  • 它以包含三个无符号 32 位整数的头部开头:

    • 所使用的哈希算法版本。我们目前支持值 2,对应于 murmur3 哈希的 32 位版本,其实现完全按照 https://en.wikipedia.org/wiki/MurmurHash#Algorithm 的描述,以及使用种子值 0x293ae76f 和 0x7e646e2 的双重哈希技术,如 https://doi.org/10.1007/978-3-540-30494-4_26 “Bloom Filters in Probabilistic Verification” 中所述。版本 1 的布隆过滤器在 char 类型为有符号且仓库中包含路径名字符 >= 0x80 时存在 Bug;Git 支持读取和写入它们,但此功能将在 Git 的未来版本中被移除。

    • 路径被哈希的次数,因此也是累积决定文件是否存在于提交中的比特位数。

    • 布隆过滤器中每个条目的最小比特数 b。如果过滤器包含 n 个条目,则过滤器大小为包含 n*b 位所需的最小 64 位字数。

  • 该块的其余部分是按字典序排列的所有已计算提交布隆过滤器的串联。

  • 注意:无变更或变更超过 512 次的提交,其布隆过滤器长度为 1,所有位分别设为 0 或 1。

  • BDAT 块仅当 BIDX 存在时才存在。

基础图列表 (ID: {B, A, S, E}) [可选]

This list of H-byte hashes describe a set of B commit-graph files that
form a commit-graph chain. The graph position for the ith commit in this
file's OID Lookup chunk is equal to i plus the number of commits in all
base graphs.  If B is non-zero, this chunk must exist.

尾部 (TRAILER)

H-byte HASH-checksum of all of the above.

历史说明

生成数据 (GDA2) 和生成数据溢出 (GDO2) 块的 ID 中带有数字 2,是因为旧版本 Git 在这些块中写入了 ID 为 “GDAT” 和 “GDOV” 的可能错误数据。通过更改 ID,较新版本的 Git 会静默忽略那些旧块并写入新信息,而不会信任不正确的数据。

GIT

Git[1] 套件的一部分