Git二进制差异算法（增量存储）是否已经标准化？

Question

Git二进制差异算法（增量存储）是否已经标准化？

gitcompressionbinary-diffvcdiff

61

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

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

- Thilo

3个回答

25

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

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

作为一个非常简单的例子（取自论文“支持增量压缩的文件系统”），考虑我们想创建一个增量缓冲区，将文本“proxy cache”转换为“cache proxy”。结果的指令应该是:

从偏移量7处复制5个字节（从基本缓冲区复制'cache'）
插入两个空格
从偏移量0处复制5个字节（从基本缓冲区复制'proxy'）

这被转换为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。当需要更大的偏移量/长度时，复制操作码中的其他位也可以设置。

在此示例中，结果增量缓冲区有8个字节，这并没有太多压缩效果，因为目标缓冲区有12个字节，但是当这种编码应用于大型文本文件时，它可以产生巨大的差异。

我最近推出了一个node.js库，使用git delta编码实现了diff/patch函数。这个代码应该比git源代码更易读和注释，因为后者被严重优化。

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

- Thiago Padilha

以下文章还包含一些有用的信息：http://stefan.saasen.me/articles/git-clone-in-haskell-from-the-bottom-up/#pack_file_format - Ciro Santilli OurBigBook.com

5

这个算法是否标准化并在其他工具中使用？ pack格式是公共API的一部分：用于push和fetch操作的传输协议使用它来在网络上发送更少的数据。

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

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

这份文档中的神奇文件以有趣的评论形式描述了包算法中使用的启发式方法，其中提到了Linus的电子邮件：https://github.com/git/git/blob/v2.9.1/Documentation/technical/pack-heuristics.txt。

- Ciro Santilli OurBigBook.com

1

好观点（比我的“历史”答案更为实时）。+1 - VonC

@VonC 谢谢！这个问题非常开放，你和Thiago的回答都包含了有用的见解。能够在像你们这样的伟大程序员旁边得到答案让我感到非常高兴。 :) - Ciro Santilli OurBigBook.com

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- VonC · Accepted Answer

我认为用于压缩文件的差分算法与某些增量编码有关: 最初（2005年）xdelta, 然后是 libXDiff。
但后来，就像下面详细说明的那样，它转向了自定义实现。

无论如何，如此处提到的那样:

Git仅在打包文件中进行差异化处理。
但是当您通过SSH推送时，git会生成一个包含其他端没有的提交记录的打包文件，并且这些打包文件是瘦包，因此它们也具有增量...但远程端会将基础添加到这些薄包中使其独立存在。

(注意：创建许多packfiles，或在巨大的packfile中检索信息是代价高昂的，并解释了为什么Git无法处理大型文件或大型repo。
请参见"git with large files"了解更多信息)

这个帖子也提醒我们：

实际上，从我记得和理解的情况来看，Packfiles和差量化（LibXDiff，而不是xdelta）最初是因为网络带宽（比磁盘空间更昂贵）和使用单个mmapped文件而不是非常大量的松散对象的I/O性能。

LibXDiff在这个2008年的帖子中被提到。

然而，自那时以来，该算法已经发展，可能是一种定制的算法，正如这个2011 thread illustrates所示，以及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的更多信息：

packfile format

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无效。

差异化表示

从概念上讲，只有四种对象类型：提交、树、标签和blob。
然而为了节省空间，一个对象可以存储为另一个“基本”对象的“增量”。
这些表示被分配新类型ofs-delta和ref-delta，在pack文件中才有效。

ofs-delta和ref-delta都存储要应用于另一个对象（称为“基本对象”）以重构该对象的“增量”。
它们之间的区别是：

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

如果基本对象也是增量化的，则它也可能在同一个pack中。
Ref-delta还可以引用包外的对象（即所谓的“thin pack”）。但是，存储在磁盘上时，pack应该是自包含的，以避免循环依赖。

增量数据是一系列指令，用于从基本对象重构对象。
如果基本对象是增量化的，则必须首先将其转换为规范形式。每个指令都将更多的数据附加到目标对象，直到它完成为止。
到目前为止，支持两种指令：

一种是从源对象复制字节范围的指令，
另一种是插入嵌入在指令本身中的新数据的指令。

每个指令具有可变长度。指令类型由第一个八位组的第七位确定。以下图表遵循RFC 1951（Deflate压缩数据格式）的约定。