59

Git 使用增量压缩来存储彼此相似的对象。

该算法是否已标准化并用于其他工具？是否有描述格式的文档？它与 xdelta/VCDIFF/RFC 3284 兼容吗？

4

3 回答 3

70

我认为用于打包文件的 diff 算法与那里的delta 编码之一相关联：最初是 (2005) xdelta，然后是 libXDiff。
但是，如下所述，它转向了自定义实现。

无论如何，如此处所述：

Git仅在包文件中进行 deltification。
但是当你通过 SSH 推送时，git 会生成一个包文件，其中包含另一方没有的提交，并且这些包是瘦包，所以它们也有 deltas ......但是远程端然后将基础添加到那些制作它们的瘦包独立的。

（注意：创建许多包文件，或在大包文件中检索信息的成本很高，并解释为什么 git 不能很好地处理大文件或大仓库。
请参阅“ git with large files ”了解更多信息）

这个话题也提醒我们：

实际上，根据我的记忆和理解， packfiles 和 deltification（ LibXDiff，而不是 xdelta ）最初是因为网络带宽（比磁盘空间昂贵得多），以及使用单个 mmaped 文件而不是非常大的I/O 性能松散的物体。

这个2008 线程中提到了 LibXDiff 。

然而，从那时起，算法已经演变，可能是在自定义算法中，正如这个2011 线程所说明的那样，并且正如标题diff-delta.c指出的那样：

所以，严格来说，Git 中的当前代码与 libxdiff 代码根本没有任何相似之处。
然而，这两种实现背后的基本算法是相同的。
研究 libxdiff 版本可能更容易理解它是如何工作的。

/*
 * diff-delta.c: generate a delta between two buffers
 *
 * This code was greatly inspired by parts of LibXDiff from Davide Libenzi
 * http://www.xmailserver.org/xdiff-lib.html
 *
 * Rewritten for GIT by Nicolas Pitre <nico@fluxnic.net>, (C) 2005-2007
 */

更多关于Git Book的包文件：

包文件格式

Git 2.18在这个新文档部分中添加了增量描述，现在（2018 年第二季度）指出：

对象类型

有效的对象类型是：

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

类型 5 保留用于未来扩展。类型 0 无效。

分层表示

从概念上讲，只有四种对象类型：commit、tree、tag 和 blob。
然而，为了节省空间，一个对象可以存储为另一个“基础”对象的“增量”。
这些表示被分配了新的 s-delta 和 ref-delta 类型，它们只在包文件中有效。

两者ofs-delta并ref-delta存储要应用于另一个对象（称为“基础对象”）以重建对象的“增量”。
它们之间的区别在于，

  • ref-delta 直接编码 20 字节的基础对象名称。
    • 如果基础对象在同一个包中，ofs-delta 将编码基础对象在包中的偏移量。

如果基础对象在同一个包中，它也可以被删除。
Ref-delta 也可以指包外的对象（即所谓的“瘦包”）。然而，当存储在磁盘上时，包应该是自包含的，以避免循环依赖。

增量数据是从基础对象重建对象的指令序列。
如果基础对象是 detified，则必须首先将其转换为规范形式。每条指令都会将越来越多的数据附加到目标对象，直到完成。
到目前为止，有两个支持的指令：

  • 一个用于从源对象复制一个字节范围和
  • 一种用于插入嵌入指令本身的新数据。

每条指令都有可变长度。指令类型由第一个八位字节的第七位决定。下图遵循 RFC 1951（Deflate 压缩数据格式）中的约定。

于 2012-02-28T08:25:49.870 回答
25

Git delta 编码是基于复制/插入的。

这意味着派生文件被编码为一系列操作码，可以表示复制指令（例如：从基本文件复制从偏移量 x 开始的 y 字节到目标缓冲区）或插入指令（例如：将下一个 x 字节插入目标缓冲区）。

作为一个非常简单的例子（取自论文'File System Support for Delta Compression'），考虑我们想要创建一个增量缓冲区来将文本“代理缓存”转换为“缓存代理”。生成的说明应该是：

  1. 从偏移量 7 复制 5 个字节（从基本缓冲区复制“缓存”）
  2. 插入两个空格
  3. 从偏移量 0 复制 5 个字节（从基本缓冲区复制“代理”）

翻译成 git 的编码变成：

（字节 1-3 代表第一条指令）

  • 0x91（10010001），分为
    • 0x80 (10000000)（最高有效位设置使其成为“从基址复制到输出”指令）
    • 0x01 (00000001)(意思是'前进一个字节并将其用作基本偏移量)
    • 0x10 (00010000)（前进一个字节并用作长度）
  • 0x07（偏移量）
  • 0x05（长​​度）

（字节 4-6 代表第二条指令）

  • 0x02（由于没有设置 MSB，这意味着“将接下来的两个字节插入输出”）
  • 0x20（空格）
  • 0x20（空格）

（字节 7-8 代表最后一条指令）

  • 0x90（10010000），分为
    • 0x80 (10000000)（表示“复制”）
    • 0x10 (00010000)（前进一个字节并用作长度）
  • 0x05（长​​度）

请注意，在最后一个复制指令中没有指定偏移量，这意味着偏移量 0。当需要更大的偏移量/长度时，也可以设置复制操作码中的其他位。

在这个例子中，结果 delta 缓冲区有 8 个字节，因为目标缓冲区有 12 个字节，所以压缩效果不大，但是当这种编码应用于大型文本文件时，它会产生巨大的差异。

我最近将一个node.js 库推送到 github，它使用 git delta 编码实现了 diff/patch 函数。该 代码应该比 git 源代码中的代码更具可读性和注释性，后者经过大量优化。

我还编写了一些 测试来解释每个示例中使用的输出操作码，格式与上述类似。

于 2013-01-13T13:30:54.543 回答
5

该算法是否已标准化并用于其他工具？

包格式是公共 API 的一部分：用于推送和获取操作的传输协议使用它通过网络发送更少的数据。

除了参考之外，它们至少在其他两个主要的 Git 实现中实现：JGit和libgit2。

因此，不太可能对格式进行向后不兼容的更改，并且在这个意义上可以被认为是“标准化”的。

来自 docs 的这个惊人的文件将 pack 算法中使用的启发式描述为 Linus 对一封电子邮件的有趣评论：https://github.com/git/git/blob/v2.9.1/Documentation/technical/pack-heuristics。文本文件

于 2014-12-13T18:27:53.913 回答