git二进制差异算法(增量存储)是否标准化？

Question

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

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

Answer 1

我认为用于包文件的差异算法与其中一个delta编码相关联:最初(2005)xdelta,然后是libXDiff.
但是,如下所述,它转移到自定义实现.

无论如何,正如这里提到的:

Git 仅在packfiles中进行解除.
但是当你通过SSH推送git会生成一个包文件,其中包含另一方没有的提交,并且这些包是瘦包,所以它们也有增量...但是远程端然后为这些瘦包增加了基础独立.

(注意:创建许多packfiles,或者在巨大的packfile中检索信息是昂贵的,并解释为什么git不能处理好的大文件或巨大的repo.
请参阅" git with large files ")

这个帖子也提醒我们:

实际上,包装文件和分层(LibXDiff,而不是xdelta),从我记忆和理解,最初是因为网络带宽(比磁盘空间昂贵得多),以及使用单个mmapped文件而不是非常大的数量的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的packfiles:

Git 2.18增加了这个新文档部分中的delta描述,现在(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.
然而,为了节省空间,可以将对象存储为另一个"基础"对象的"增量".
这些表示被分配了新类型的delta和ref-delta,它们仅在包文件中有效.

既ofs-delta与ref-delta存储"增量"要被施加到另一个对象(称为"基础对象")以重建该对象.
他们之间的区别是,

• ref-delta直接编码20字节的基础对象名称.
  • 如果基础对象位于同一个包中,则ofs-delta会对包中基础对象的偏移量进行编码.

如果它在同一个包中,那么基础对象也可以被解除.
Ref-delta也可以指包外的物体(即所谓的"薄包").但是,当存储在磁盘上时,包应该是自包含的,以避免循环依赖.

的差分数据是指令序列来重建从基础对象的对象.
如果基础对象已经过分层,则必须首先将其转换为规范形式.每条指令都会向目标对象附加越来越多的数据,直到完成为止.
到目前为止,有两条支持的说明:

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

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

Answer 2

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

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

作为一个非常简单的示例(摘自文章"Delta Compression的文件系统支持"),考虑我们要创建一个delta缓冲区来将文本"代理缓存"转换为"缓存代理".结果说明应为:

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源中的 代码更具可读性和评论性,后者经过了大量优化.

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

Answer 3

这个算法是否标准化并在其他工具中使用？

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

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

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

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