代表Git仓库的数学结构是什么

Question

我正在学习Git,如果我有一个代表Git repo的数学结构的描述,那将会很棒.例如:它是一个有向无环图; 它的节点代表提交; 它的节点有标签(每个节点最多一个标签,没有标签使用两次)代表分支等(我知道这个描述不正确,我只是想解释我在寻找什么.)

Answer 1

除了Nevik Rehnel评论中的链接(根据请求复制到此处: eagain.net/articles/git-for-computer-scientists和gitolite.com/gcs),以及提交图形成Merkle树的点,我'我会添加几个笔记.

• 对象存储中有四种对象类型:commit,tree,annotated-tag和blob(file).
• 提交对象只包含一个tree-ref(当然可以指向更多树),一个可能为空的父SHA-1哈希列表(必须全部提交更多),一个作者(名称,电子邮件和时间戳) ,提交者(与作者相同的形式)和提交文本.
• 树对象包含重复0次或更多次的(模式,子对象,文件名)列表.如果子对象是另一个树,则文件名表示目录.如果它是一个blob,它代表一个文件.该模式看起来像POSIX文件模式,如果是120000(符号链接的文件模式),文件的"内容"实际上是符号链接目标.某些模式值是(ab)用于子模块,但我忘了哪个.R和W模式位不存储,只存储X位(如果repo配置说忽略它们,它们甚至会被忽略).
• 带注释的标记对象包含对象引用,标记器(名称,电子邮件和时间戳)以及标记文本.引用的对象通常是提交,但标记对象可以指向任何对象(甚至是另一个标记对象).
• 标签(分支和标签以及reflog-references等)位于对象存储之外.对于带注释的标签,外面有一个标签,指向对象库内的带注释的标签对象.对于轻量级标记,外部标签指向提交.
• 没有限制只有一个root提交.任何没有父母的提交都是根.
• Git几乎从不创建一个空树(它代表一个空目录),除了两种情况:每个仓库中都有一个空树,如果你做一个初始的空提交(with git commit --allow-empty),它就会使用那个空树.(由于空树没有子对象,因此其SHA-1哈希值是常量.)
• "DAG"描述通常用于通过关闭提交父哈希形成的树.但是,树对象通常不应在其任何子树中包含自身,如果您设法创建循环树结构,则无法将其检出(因为它无限地递归).假设你不能用相同的校验和制作两个不同的树(如果你可以打破git),你将找不到包含树T2的树T1,树T2包含校验和为T1的不同树.因此,树也隐含地是DAG,并且附加到commit-DAG,它们形成更大的DAG.:-)
• 对象存储中的未引用对象将被垃圾收集git gc.空树似乎对收集免疫.在任何refs/与logs/目录和文件packed-refs(中.git,或裸回购或者$GIT_DIR设置,任何其他地方)作为基准的作用,就像做了特殊的名字(HEAD,ORIG_HEAD,等); 我不确定其他随机文件(如果在.git包含有效SHA-1中创建)是否可以作为引用.
• 索引有一些我从未挖过的格式.它包含对象库中对象的引用.当你git add是一个文件时,git将文件放入对象存储中并将(非文本)SHA-1哈希放入索引文件中.这些是防止垃圾收集的有效引用.

Answer 2

我认为最相关的答案需要包括Git修订树的最重要特征:加密签名(每个修订包括父修订和提交细节的哈希).

这被称为Merkle树:http://en.wikipedia.org/wiki/Merkle_tree

请参阅前面的答案以获取一些背景信息:( Git:如何处理提交以使文件的版本完整存在(不仅仅是差异))

背景

存储deltas由RCS,CVS,Subversion和其他人(SourceSafe？)推广.主要是因为模型可以很容易地转换变更集,因为它们已经是delta形式.现代VCS-es(主要是分布式的)已经从此发展而来,并强调数据完整性.

数据的完整性

由于对象数据库的设计,git非常强大,可以在快照或整个存储库中的任何位置检测到任何损坏的数据.有关Git存储库的加密属性的更多详细信息,请参阅此文章:Linus talk - Git与数据损坏？

在techno babble中:提交历史形成加密强大的merkle树.当提示提交(HEAD)的sha1总和匹配时,它在数学上遵循

• 树的内容
• 分支历史记录(包括所有签名和提交者/作者凭证)

是相同的.这是git(和其他共享此设计功能的SCM)的巨大安全功能