独孤九剑(002) - 数据结构篇

Dit 和 Git 使用相同的设计思路和数据结构,在表述上会优先使用 Git,当出现差别时会特别说明。本文说明两种最基本的数据结构:仓库和对象。

Git 仓库

Git 做为一个内容控制系统(版本控制器),所有的信息都保存在 Git 仓库(.git/)中。Git 仓库实际上是一个文件系统,它保存了所有的历史数据和当前项目的状态,保证被 Git track 的项目数据不丢失。

Dit 和 Git 一样,存储文件快照,所谓快照,就是指文件本身(实际使用 zlib 压缩之后存储),如果文件没有改变,那么只存储该文件的引用。你可以使用 git init 初始化一个 Git 仓库, 并查看生成的文件目录结构:

$ git init
Initialized empty Git repository in /Users/zdd/Projects/test_git_init/.git/
$ tree -a
.
└── .git # 在当前路径下生成 .git 目录,存放本地仓库
├── HEAD # 文件索引
├── config # 配置文件
├── description # 被 Git-Web 程序引用,Dit 暂不使用
├── hooks # 钩子脚本,Dit 暂不使用
│ ├── applypatch-msg.sample
│ ├── commit-msg.sample
│ ├── post-update.sample
│ ├── pre-applypatch.sample
│ ├── pre-commit.sample
│ ├── pre-push.sample
│ ├── pre-rebase.sample
│ ├── prepare-commit-msg.sample
│ └── update.sample
├── info # Dit 暂不使用
│ └── exclude
├── objects # 存储 Git 对象
│ ├── info
│ └── pack
└── refs # 存放索引和 tags
├── heads
└── tags # Dit 暂不使用
9 directories, 13 files
依样画葫芦,Dit 初始版本只创建 3 个目录 和 1 个文件:

永远只关心最重要的事

.
└── .dit
├── HEAD
├── objects
└── refs
└── heads
3 directories, 1 file
文件创建使用 package os 来实现 (Dit 优选官方包,尽量不使用第三方库)。

Git 基础类型

Git 的基础类型有四种,blob,tree,commit 和 tag。blob 管理文件,tree 管理目录,commit 管理每次提交,tag 设置标签。为了统一,抽象出一个公共类 object,存储基本信息。

object

Git 仓库中主要就存储了这些 object 对象。每个 object 对象按实际内容的 sha1 值命名,压缩之后存储在 .git/objects 目录下。内容相同的 object 具有相同的文件名和 sha1 值,在 Git 中只存储一份。object 可被其它 object 引用,形成树型结构,类似文件目录结构。

blob

blob 记录项目文件快照。实际文件通过 zlib 压缩后存储在本地仓库的 objects 目录下。快照文件目录为其内容 sha1 值的前 2 位,文件名为之后的 38 位。Git 按内容存储文件快照,内容不同(sha1 值不同)的版本,对应不同的快照文件。

blob 只保存文件的实际内容,不能引用其它 object,没有签名和认证,使用sha1值来保证存储内容的正确性。blob 是 Git 中最小的内容存储结构。blob 文件生成后不再改变。

假如需要添加一个内容为 dit 的文件 a 到 Git 仓库,则实际在 objects 中生成的快照文件为:

$ tree .git/objects/
.git/objects/
├── 8f
│ └── 2c96ad676d7423d2c319fffb78cfb87c78c3e2
.
blob 文件结构为 "blob size0实际内容",其中 size 为文件所占用的字节数。sha1 值按以下算法计算:

利用 git 命令计算

$ echo dit | git hash-object --stdin
8f2c96ad676d7423d2c319fffb78cfb87c78c3e2

利用 shasum 计算

$ echo -e "blob 4\0dit" | shasum
8f2c96ad676d7423d2c319fffb78cfb87c78c3e2 -

利用 openssl sha1计算

echo -e "blob 4\0dit" | openssl sha1
(stdin)= 8f2c96ad676d7423d2c319fffb78cfb87c78c3e2

go 的实现: 我是试了很久才想到 \x00 的,:(

fmt.Printf("%x\n", sha1.Sum([]byte("blob 4\x00dit\n")))

tree

只有 blob 会保存文件的实际内容,tree 引用 blob 或者 tree,每个对象占一行,按文件名排序。以下是某个 tree 的内容:

$ git cat-file -p af3d9d135f68fbec7e4ea7fde3ef19844746ae6f
100644 blob f0462300828522d14f9faeb75d80f66fa89457ae blob.go
100644 blob 1b022329b3817b54c37e6704b7b9e4df49d8dee9 commit.go
040000 tree af8db5dbe85bc5f695ab3ddc1ad7a5fcf6617ae9 main
100644 blob 523a6539be6dc1a1d188965683091ce37e2f898e object.go
同样加上头 "tree size0" 后计算 sha1 值,并用 zlib 压缩后存储在 .git/objects 目录下。

tree 同样没有签名和认证,生成后不再改变。

commit

commit 只引用 tree, 每次提交时的文件信息都由 tree 来管理,commit 通过引用不同的 tree 来标记不同的版本。commit 拥有一个 parent 的引用,指明本次更改的父节点,通过父节点,可以查询整个提交历史。以下是某个 commit 的内容:

$ git cat-file -p 1029cd09aa6c72f142931d7cd0cb3fef7486ca14
tree 42477c2be645032c4dc8699fa4fa8acfcbc633af
parent 547b47e3d43b13bf48a2cbfbb589ecb878062b37
author zdd 1439825985 +0800
committer zdd 1439825985 +0800
Add a
detail description
如果一个 commit 对象没有 parent 信息,那把它称为 root 结点。理论上每个项目可以有多个 root 结点,但在实际使用中,通常把 Initial commit 做为 root 结点。

加头 "commit size0" 后计算 sha1 值,并用 zlib 压缩后存储在 .git/objects 目录下。

tag

软件开发时,每个 commit 就是一个版本,tag 持有一个 commit,做为一个 “重要” 版本存在。tag 持有的 commit id 存在 .git/refs/tags 中。在初始版本的 Dit 中不被实现。

Git 当前目录缓存

Git 在缓存 (cache) 中记录当前仓库的状态,缓存的状态存储在 .git/index 文件中,来保证不同命令之间信息的传递。缓存是 Git 运作的关键, 搞清了它的数据结构和运作模式,Git 的实现思路也就呼之欲出了。

木乙言己 zddhub 出品
微信号: zddnotes
Just for fun!

文章只写给自己,如果你也喜欢,欢迎扫描以下二维码关注哦~

关键字:git

版权声明

本文来自互联网用户投稿,文章观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符,请点击 举报 进行投诉反馈!

立即
投稿

微信公众账号

微信扫一扫加关注

返回
顶部