独孤九剑 Dit (0x02) - 数据结构篇
穷则独善其身，达则兼济天下。一个人一旦能够喂饱自己并有个安身之所，剩下的就是该别人做点什么了。我现在所做的一切，还都是为了自己。
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 使用 Golang 实现，优选官方包，尽量不使用第三方库)。
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 值的前两位，文件名为之后的 38 位。Git 按内容存储文件快照，内容不同(sha1 值不同)的版本，对应不同的快照文件。
blob 只保存文件的实际内容，不能引用其它 object，没有签名和认证，使用sha1值来保证存储内容的正确性。blob 是 Git 中最小的内容存储结构。blob 文件生成后不再改变。
假如需要添加一个内容为 dit 的文件 a 到 Git 仓库，则实际在 objects 中生成的快照文件为：
$ tree .git/objects/
.git/objects/
├── 8f
│ └── 2c96ad676d7423d2c319fffb78cfb87c78c3e2
.
blob 文件压缩前的结构为 "blob size\0实际内容"，其中 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 size\0" 后计算 sha1 值，并用 zlib 压缩后存储在 .git/objects 目录下。
tree 同样没有签名和认证，生成后不再改变。
注：Git 只在存储 tree 的内容时，使用了二进制存储，而不是文本文件。如下所示的 tree，实际长度只有 29, 如果用二进制存储，实际长度应该是 55 才对。dit 使用简单的文本文件存储。
$ git cat-file 42477c2be645032c4dc8699fa4fa8acfcbc633af -t
tree
$ git cat-file 42477c2be645032c4dc8699fa4fa8acfcbc633af -p
100644 blob 8f2c96ad676d7423d2c319fffb78cfb87c78c3e2 a
$ git cat-file 42477c2be645032c4dc8699fa4fa8acfcbc633af -s
29
$ echo "100644 blob 8f2c96ad676d7423d2c319fffb78cfb87c78c3e2 a" | wc -c
55
commit
commit 只引用 tree, 每次提交时的文件信息都由 tree 来管理，commit 通过引用不同的 tree 来标记不同的版本。commit 拥有一个 parent 的引用，指明本次更改的父节点，通过父节点，可以查询整个提交历史。以下是某个 commit 的内容:
$ git cat-file -p 1029cd09aa6c72f142931d7cd0cb3fef7486ca14
tree 42477c2be645032c4dc8699fa4fa8acfcbc633af
parent 547b47e3d43b13bf48a2cbfbb589ecb878062b37
author zdd <zddhub@gmail.com> 1439825985 +0800
committer zdd <zddhub@gmail.com> 1439825985 +0800
Add a
detail description
如果一个 commit 对象没有 parent 信息，那把它称为 root 结点。理论上每个项目可以有多个 root 结点，但在实际使用中，通常把 Initial commit 做为 root 结点。
加头 "commit size\0" 后计算 sha1 值，并用 zlib 压缩后存储在 .git/objects 目录下。
tag
软件开发时，每个 commit 就是一个版本，tag 持有一个 commit，做为一个 “重要” 版本存在。tag 持有的 commit id 存在 .git/refs/tags 中。在初始版本的 Dit 中不被实现。
Git 当前目录缓存
Git 在缓存 (cache) 中记录当前仓库的状态，缓存的状态存储在.git/index 文件中，来保证不同命令之间信息的传递。缓存是 Git 运作的关键, 搞清了它的数据结构和运作模式，Git 的实现思路也就呼之欲出了。
如果你喜欢这篇文章，欢迎赞赏作者以示鼓励
