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

2016-07-26 21:06:00

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 目录下。