Marvin's Blog【程式人生】

Ability will never catch up with the demand for it

24 Jun 2018

分布式版本管理工具的内涵【一】Git篇

软件开发人员一直在寻找合适的版本管理工具来管理代码。从最早的CVS到现在的Git,经过时一二十年的时间。从早起的以CVS/SVN为代表的集中式版本管理系统(CVCS or Centralized Version Control System),发展到现在以Git/Mercurial为主的分布式版本管理工具(DVCS or Decentralized Version Constrol System)。本文旨在探讨眼下流行的DVCS的一些内涵,主要涉及Git、Mercurial和Fossil。

集中式和分布式的

传统的版本管理的工作流如下:

  1. 从中央仓库获取需要修改的文件
  2. 修改完目标文件,并提交到中央仓库
  3. 处理提交过程中出现的种种问题

不管是集中式还是分布式版本管理,都支持以上工作流。这两种工作模式最大的区别,是在第三步,也就是如何处理把改动合并到中央仓库中出现的问题。当一个项目参与的人数众多时,这一步尤其容易出错,大家的改动容易出现冲突。对于这个问题的处理方式不同,是集中式和分布式版本管理的最大差异。

集中式版本管理的特点

  • 以文件为中心,每个文件有单独的版本号
  • 如果多个人同时提交某个文件的改动,需要就文件级别对这个改动进行协调
  • 最简单的协调方式是给文件加上排他锁,只允许上锁的人修改文件,其他人排队
  • 但会导致锁冲突,比如说你需要同时修改文件A、文件B和文件C,但是这三个文件的锁是由不同的人持有的…… 如何协调?
  • 可以加大上锁力度来简化锁冲突问题,比如一个子目录作为一个整体,一次由一个人上锁。
  • 但上面的方式导致了另外的问题,想把改动提交到这个子目录的其他人,都必须在那里排队,什么都干不了。

分布式版本管理的特点

  • 以改动集为单位,而不是以单独的文件为单位。一个改动集代表仓库整体的一个状态,比如说在一个仓库中有三个文件被修改,从而整体状态发生变化,形成了一个新的改动集。这个改动集是由这三个文件的改动导致的。
  • 把仓库看成一个整体进行版本管理,并且仓库的版本由改动集构成。也就是说,当一个改动集提交到仓库时,仓库整体版本向前进一步。
  • 这样的做的好处是,改动集里面的文件改动要么全部提交成功,要么全部提交失败。不会出现部分成功和部分失败的状况。从而减少冲突。
  • 这样做并没有解决的问题是,当中央仓库在处理某个改动集的时候,其他改动集仍需要排队。为了处理这个问题,分布式版本管理系统通常在本地拥有某个分支的完整的版本历史,需要提交到中央仓库的改动集可以先寄放在本地的版本历史里。

做个总结,DVCS的主要特点是基于改动集(而不是单个文件),然后本地有完整的版本历史。

各DVCS的内涵分析

改动集、文件集和存储方式

基于改动集这个特点需要DVCS把仓库所有的文件作为一个文件集合来看待。这里需要用到另一个概念,那就是「文件集」。那「文件集」和「改动集」有什么区别呢:

  • 文件集包含了当前仓库中所有文件的特定版本。比如当前仓库有10个文件,构成文件集1;然后修改了其中三个文件,构成文件集2;文件集1和2都包含了10个文件,区别在于其中有三个文件版本不同。
  • 文件集是构成改动集的基础。一个改动集基于一个文件集,并包含其他信息,比如到前一个改动集的索引,还有形成改动集的时间戳和相关的注释等等。
  • 这两者一个是横向的一个是纵向的。文件集横向包括当前仓库的所有文件,改动集纵向记录仓库的改动历史。

对于一个DVCS系统,除了需要决定如何形成文件集和改动集以外,还要决定文件的内容是如何存储在仓库中的。下面的章节就这个问题对不同的DVCS展开探讨。

Git

存储方式

Git的实现方式是最朴实的,也是最灵活的。Git采用key/value的方式来存储所有内容。这里的key不是用文件名,而使用文件内容的hash id。具体存储的过程是这样,对于一个需要检入仓库的文件,Git采用SHA算法这个文件进行hash操作,生成一个相当长的hash id,然后根据hash id把文件内容经过一定的压缩后,存储到相应的位置(在.git/objects目录)。

下面是一个例子:

$ tree .git/objects

.git/objects
├── 02
│   └── 4776157941afc5d9ba02a8c1d98a6a2f99ba35
├── 03
│   └── 7877b91e14982c8257eac986ac5c7b66ceb959

其中024776157941afc5d9ba02a8c1d98a6a2f99ba35就是一个hash id。Git存储的时候会把hash id前两位相同的文件内容放在一个文件夹下面,然后把hash id除去前两位的部分作为文件内容的文件名。

术语

Git的术语中,把hash过的,存储在仓库中的文件内容叫做blob,每一个blob都有对应的hash id。另外,对于前面章节提到的「文件集」和「改动集」在Git的术语中叫做tree和commit,这两个也是以类似blob的方式存储在仓库中的。

所以,Git的仓库中至少有以下几种类型的对象:

  • blob,用于存储一般性的文件内容
  • tree,用于存储「文件集」的内容
  • commit,用于存储「改动集」的内容

commit

我们来看看一个git的commit里面包含什么内容

$ git cat-file -p 1c9d2c60202a5b87054f56e66eb6a9e819de864d 

tree af7833c300e5cca137b60dbeb2abf1c10f00b10b
parent d2df3f0051495bc15ad161749b65cbe2f6569955
author XXX 1529756427 +0800
committer XXX 1529756427 +0800

可以看出来,commit里面的内容很简单,包括一下信息:

  • 所对应的tree(也就是文件集)的hash id
  • 上一个commit(也就是改动集)的hash id
  • 时间和作者等其他信息

tree

我们再来看看上面commit所对应的tree里面包含的内容:

$ git cat-file -p af7833c300e5cca137b60dbeb2abf1c10f00b10b 
100644 blob da0f8ed91a8f2f0f067b3bdf26265d5ca48cf82c	a.txt
100644 blob c9c6af7f78bc47490dbf3e822cf2f3c24d4b9061	b.txt
040000 tree 769f2ae22960821421a69bb2c0c588669bffca5f	c

可以看出tree像一个文件目录,记录着该目录的文件的名字以及对应的信息(hash id,类型以及权限等等)。上面的tree包含了两个子文件,分别是a.txt和b.txt。另外,上面的tree还可以包含了一个名字叫c的tree,相当于一个目录包含一个子目录。

小结

Git通过blob/tree/commit这种组织方式,在仓库内构建了一个虚拟的文件系统。如果仔细思考的话,这种组织方式其实是存在一定的问题:

问题 1:同一文件的不同版本间分开存储

如果仓库中有一个相当大的文件,然后这个文件被修改了一行,那么在Git看来,这已经是一个不一样的文件了,生成一个新的blob。这会导致仓库膨胀。试想,一个blob为100K字节,如果其中的一个字节变了,那么就会生成一个新的blob,新旧blob的只有一个字节而已,导致很多空间浪费。

我猜想,Linus当时这么设计是出于计算效率的考虑,而不是处于存储效率的考虑。Git的初衷是管理Linux内核,其文件数目非常庞大,而且参与者非常多,经常需要合并(merge)别人的改动。合并的操作需要进行大量的文件对比。Git的这种设计让文件对比操作比较高效,因为直接从blob里面就可以解出文件内容使用(后续谈到Mercurial的时候就知道为什么这样做效率高了)。

这样做所导致的仓库体积膨胀问题显而易见。于是Git增加了一个打包机制,通过git gc命令把当前暂时用不到的blob收进pack里面,放在.git/object/pack目录:

$ ls .git/objects/pack
pack-faceceed516e12b7884f10fe0a37fe34b787a35a.idx
pack-faceceed516e12b7884f10fe0a37fe34b787a35a.pack

当这些blob被打包成pack的时候,同一文件的相同版本可以只存储增量部分,这导致打包后的Git仓库只占用比较少的恐惧。当然,为了获得这样的效果,你必须时不时打包一下Git仓库。

git gc的gc是garbage collection的缩写,意思是垃圾收集

问题 2:向前回溯文件版本容易,向后回溯文件版本困难

在Git中查找一个文件的版本,过程是这样的:

  • 根据当前commit的hash id在仓库中找到相应的commit内容
  • 根据当前commit的内容,找出当前tree的hash id以及对应内容
  • 根据当前tree的内容,查找目标文件的hash id及对应内容

为了找到文件的不同版本,必须重复执行上述过程,也就是要解析一系列的commit。那问题来了,怎么先找到这一系列的commit?

在前面章节的例子中,我们可以看到每个commit的内容中带有上一个commit的hash id。所以给定任意一个commit,只要根据commit内容中的上一个commit的hash id,就可以向前回溯某个文件的版本。但是给定一个任意的commit,如果找到这个commit的下一个commit呢?虽然不是不可能,但没有额外信息的帮助,想要完成这个操作也是十分繁琐的。

究其原因,向后回溯文件版本很难,是因为Git中的commit只能看到之前的commit,而看不到之后的commit。这样的设计是Linus有意而为之的,主要是为了保证安全性。正式因为每个commit都和之前的commit具有相关性,所以当之前的commit发生任意的改变时,当前commit的hash id就会发生变化。而且一个commit不和在它之后的任意commit有关联,这意味着一个commit在它诞生之际就是稳定的。只要手头的commit的hash id不变,就可以确定没有人对仓库里面的版本历史做过手脚。对于维护Linux内核这种至关重要的任务来说,确保没有人对代码动手脚,是一个合理而且十分恰当的做法。

参考链接

(未完待续)

Categories

Tags