Git使用增量压缩来存储相似的对象。
这个算法是否被标准化并在其他工具中使用?是否有描述格式的文档?它是否与xdelta/VCDIFF/RFC 3284兼容?
Git使用增量压缩来存储相似的对象。
这个算法是否被标准化并在其他工具中使用?是否有描述格式的文档?它是否与xdelta/VCDIFF/RFC 3284兼容?
我认为用于压缩文件的差分算法与某些增量编码有关: 最初(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的更多信息:
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
都存储要应用于另一个对象(称为“基本对象”)以重构该对象的“增量”。
它们之间的区别是:
如果基本对象也是增量化的,则它也可能在同一个pack中。
Ref-delta还可以引用包外的对象(即所谓的“thin pack”)。但是,存储在磁盘上时,pack应该是自包含的,以避免循环依赖。
增量数据是一系列指令,用于从基本对象重构对象。
如果基本对象是增量化的,则必须首先将其转换为规范形式。每个指令都将更多的数据附加到目标对象,直到它完成为止。
到目前为止,支持两种指令:
每个指令具有可变长度。指令类型由第一个八位组的第七位确定。以下图表遵循RFC 1951(Deflate压缩数据格式)的约定。
Git增量编码是基于复制/插入的。
这意味着派生文件被编码为一系列操作码,它可以表示复制指令(例如:从偏移量x开始复制来自基本文件y个字节到目标缓冲区)或插入指令(例如:将下一个x个字节插入到目标缓冲区)。
作为一个非常简单的例子(取自论文“支持增量压缩的文件系统”),考虑我们想创建一个增量缓冲区,将文本“proxy cache”转换为“cache proxy”。结果的指令应该是:
这被转换为git的编码:
(字节1-3表示第一个指令)
(字节4-6表示第二个指令)
(字节7-8表示最后一个指令)