一、Git存储原理分析

题目的目标是编写引擎，能够解析 Git 的各种对象，并且能够为对象设计数据存储机制，可以将对象存储在数据库中。

第一章我们首先分析了 git 的存储原理；然后在二、三章节分析了 git object 和 packfile 的存储机制和解析方法；第四章分析了 git push 过程的传输协议，使用网关程序拦截信息（packfile文件）并将其存入数据库里；第五章是数据库的现阶段设计。

git 对象生命周期和 git 对象间的关系

分析 git 对象的生命周期和对应关系。对于 git 对象现在阶段需要分析 commit、 tree、 blob 三种类型的文件，几种对象的状态，存储方式要实现对提交内容实现数据库支持的检索。

git 生命周期：git init，初始化git项目，生成 .git 文件夹创建文件并git add之后，会生成一个文件对应的 blob 对象存储到松散区 .git/object 文件夹git commit 之后，会生成tree对象和 commit对象存储到 .git/object

git 对象的对应关系：一个 commit 对应一个 tree一个 tree 对应 1个 blob+1个tree （n>=0）一个 tag 对应一个 commit

储存对象方式

Git 保存对象的格式有两种——松散对象和打包对象。

git对象储存目录设计逻辑

.git/objects 目录的设计逻辑(在 objects 目录下生成文件夹和文件)

数据blob对象、树tree对象和提交commit对象都是在.git/objects目录下以key-value形式存储，key是Git对象的40位hash，在文件系统里分为两部分：头两位作为文件夹，后38位作为对象文件名（目的是减少文件夹下的文件数目，查找更快）。

hash的计算：

header = "<type>" + " (空格)" + content.length(数据内容的字节数) + "\0"

hash = sha1(header + content)

tree/blob/commit object 对象的存储机制:

Git对象会在原内容前加个一个头部：

store = header + content

头部

header = "<type>" + content.length + "\0" hash = sha1(header + content)

Git对象在存储前，会使用zlib的deflate算法进行压缩，即简要描述为：

zlib_store = zlib.deflate(store)

content内容保存方式

文本、图像、音频。。。。。

store = header + content 二进制拼接

二、解析Git Object.md

object 对象的存储机制

数据对象 blob

blob <content length><NULL><content>

储存文件内容，不包括文件名，经过SHA1哈希算法得到对应的哈希值

树对象 tree

tree <content length><NULL><file mode> <filename><NULL><item sha>...

<item sha>部分是二进制形式的sha1码，而不是十六进制形式的sha1码。
树对象，作用是存储目录信息，包含了n条树对象记录和n个数据对象记录，
其中每条记录都指向一个数据对象或者是子树对象的SHA-1指针以及相应的模式、类型、文件名

提交对象 commit

commit <content length><NUL>tree <tree sha>

parent <parent sha>[parent <parent sha> if several parents from merges]

author <author name> <author e-mail> <timestamp> <timezone>

committer <author name> <author e-mail> <timestamp> <timezone>

<commit message>

提交对象中包含一个树对象条目，代表着当前项目快照
其他之外还有一些作者/提交者的信息，
最后一行是提交注释。

一个 commit 可能会有多个 parent

Tag

**Tag 对象:**打上 tag 之后，这个 tag 代表的内容将永远不可变，因为 tag 只会关联当时版本库中最后一个 commit 对象。
Tag 类型有两种：
1 lightweight (轻量级) git tag tagName
这种方式创建的 Tag，git 底层不会创建一个真正意义上的 tag 对象，而是直接指向一个 commit 对象，此时如果使用 git cat-file -t tagName 会返回一个 commit。
2 annotated (含附注) git tag -a tagName -m''
这种方式创建的标签，git 底层会创建一个 tag 对象，tag 对象会包含相关的 commit 信息和 tagger 等额外信息，此时如果使用 git cat-file -t tagname 会返回一个 tag

tag 内容

object d5d55a49c337d36e16dd4b05bfca3816d8bf6de8 //commit 对象SHA-1

type commit

tag v3 //tagName

tagger xxx 1506230900 +0800 //本次commit的人

message

branch

本质上是一个有名字的指针，指向特定的commit

指向自己的最新的commit

HEAD文件指针：指向当前工作分支的最新commit

分支保存在 .git/refs/heads/（分支名：指向->commit）

remote

执行git remote add origin http://xxxxxxx
生成 .git/config

[remote "origin"]

url = 远程仓库地址

fetch = 对应远程仓库本地仓库分支信息git

本地生成远程远程仓库信息
- .git/refs/remotes/（sha-1->分支指向commit）

三、解析Git Packfile.md

git对象的压缩

压缩主要是 blob，add 之后就会压缩（压缩率不同，重复率高的txt压缩率高，二进制文件反而比原始文件大一些），使用 zlib 进行压缩。
git gc后，再次压缩（相似文件存储第一个对象和第二个对象存储的差异）---> 出现两个文件 idx、pack；

packfile 信息格式

SHA-1 type size size-in-packfile offset-in-packfile depth base-SHA-1

git gc 之后打包成一个packfile，offset-in-packfile 记录在packfile内的偏移量

pack 目录下的逻辑(idx、pack)

上面都是松散区，当增加大量内容大小几乎完全相同的对象，手动执行 git gc 命令，或者向远程服务器执行推送时，这些对象打包成一个称为“包文件（packfile）”的二进制文件。
原理：Git 会完整保存其中一个，再保存另一个对象与之前版本的差异内容。即Git将只保存第二个文件中更改的部分，并使用一个指针指向与之相似的文件。并使用一个指向该文件的指针。
具体过程：会新创建一个包文件pack和一个索引idx，包文件包含了打包时从文件系统中移除的所有对象的内容。索引文件包含了包文件的偏移信息，通过索引文件就可以快速定位任意一个指定对象。
git verify-pack 命令查看已打包的内容
1,2,3 commit - pack1 idx1; 4,5 commit - pack2 idx2;

unpack

新建一个 git 项目 git init newrepo cd newrepo
git unpack-objects < 原项目/.git/objects/xxxx.pack

pack方式

松散文件打包成pack、idx过程
两次pack间的过程
- 后一个替换前一个
索引的方式
- 相似文件以最后一次commit的文件为源文件，之前的保存与其的差异。

packfile 解析

因为只传输packfile文件，所以我们首先要从 packfile 中解析出 packfile 的索引，

Packfile 以12字节的元信息开始，以20字节的校验和结束，所有这些都可以用来验证我们的结果。前四个字节拼写为“ PACK”，后四个字节包含版本号——在我们的程序中是[0,0,0,2]。接下来的四个字节是包中包含的对象数，所以一个 packfile 不能包含超过2^32个对象。后面是一系列打包的对象，按照它们的 SHAs 顺序排列，每个 SHAs 由一个对象头和对象内容组成。Packfile 的末尾是该 packfile 中所有 shas (按排序顺序)的20字节 SHA1和。

Packfile 的核心是一系列打包的对象，每个数据块前面都有一些元信息。元信息后面的数据是 zlib 压缩的对象数据，在上面我们提到过解析对象的方法。元信息是由一个或多个1字节(8位)大块组成的序列，用于指定以下数据的对象类型以及展开时的数据大小。每个字节实际上是7位的数据，第一位用来表示数据开始之前是否是最后一位。如果第一位是1，那么将读取另一个字节，否则数据将从下一位开始。根据下表，第一个字节的前3位指定了数据的类型。

obj_commit = 001

obj_tree = 010

obj_blob = 011

obj_tag = 100

obj_ofs_delta = 110

obj_ref_delta = 111

两种特别的压缩方式：

ofs
- 表示的是 Delta 存储，当前 git 对象只是存储了增量部分，对于基本的部分将由接下来的可变长度的字节数用于表示 base object 的距离当前对象的偏移量，接下来的可变字节也是用 1-bit MSB 表示下一个字节是否是可变长度的组成部分。对偏移量取负数，就可知 base 对象在当前对象的前面多少字节
ref
- 表示的是 Delta 存储，当前 git 对象只是存储了增量部分，对于基本的部分，用 20-bytes 存储 Base Object 的 SHA-1 。

四、网关

本项目使用 tokio 的 Web框架 Axum 编写网关程序，在这之前首先要了解 git 客户端和服务端的传输协议。

传输协议

两种主要的方式在版本库之间传输数据：“哑（dumb）”协议和“智能（smart）”协议

哑协议

哑协议特点如下

只读，只提供下载
1、拉取info/refs GET info/refs 得到一个远程引用和 SHA-1 值的列；2、确定 HEAD 引用 GET HEAD ref: refs/heads/master；3、得到分支对象（第二部master指向的），一个commit对象（master）GET objects/xx/xxxxx；4、获取第三步对应的tree对象和父提交 GET objects/xx/xxxx；可能无法找到则需要获取 packfile GET objects/info/packs

哑协议效率略低，而且它不能从客户端向服务端发送数据。所以我们要使用的是智能协议。

智能协议

智能协议分为以下几步：

1、引用发现

GET https://{仓库地址}/info/refs?service=git-{upload|receive}-pack
- 服务端的各个引用的版本信息，让服务端或者客户端知道两方之间的差异以及需要什么样的数据。
- 客户端请求
  - => GET http://server/simplegit-progit.git/info/refs?service=git-receive-pack
- 服务端回应
  - 001f# service=git-receive-pack 00ab6c5f0e45abd7832bf23074a333f739977c9e8188 refs/heads/master report-status \ delete-refs side-band-64k quiet ofs-delta \ agent=git/2:2.1.1~vmg-bitmaps-bugaloo-608-g116744e 0000
  - 第一首行的四个字符符合正则^[0-9a-f]{4}#，这里的四个字符是代表后面内容的长度然后是# service=$servicename；每一行结尾需要包含一个LF换行符；以0000标识结束本次请求响应
master 分支和它的 SHA-1 值。第一行响应中也包含了一个服务端能力的列表（这里是 report-status、delete-refs 和一些其它的，包括客户端的识别码）。

2、数据传输

POST https://{仓库地址}/git-{upload|receive}-pack
数据传输分为两部分：客户端向服务端传输（Push）、服务端向客户端传输（Fetch）。
Push 操作获取到服务端的引用列表后，由客户端本地计算出客户端所缺失的数据，将这些数据打包，并POST给服务端，服务端接收到后进行解压和引用更新
- Push 时，客户端会根据服务端的引用信息计算出服务端所需要的对象，直接通过 Post 请求发送给服务端，并同时附带一些指令信息，比如新增、删除、更新哪些引用，以及更新前后的版本，
=> POST http://server/simplegit-progit.git/git-receive-pack
- 请求的内容是 send-pack 的输出和相应的包文件。
- 知道了服务端的状态， send-pack 进程会判断哪些提交记录是它所拥有但服务端没有的。 send-pack 会告知 receive-pack 这次推送将会更新的各个引用。举个例子，如果你正在更新 master 分支，并且增加 experiment 分支，这个 send-pack 的响应将会是像这样：
  - 0076ca82a6dff817ec66f44342007202690a93763949 15027957951b64cf874c3557a0f3547bd83b3ff6 \ refs/heads/master report-status 006c0000000000000000000000000000000000000000 cdfdb42577e2506715f8cfeacdbabc092bf63e8d \ refs/heads/experiment 0000
- 第一行也包括了客户端的能力。这里的全为 0 的 SHA-1 值表示之前没有过这个引用——因为你正要添加新的 experiment 引用。删除引用时，将会看到相反的情况：右边的 SHA-1 值全为 0。
- 然后，客户端会发送一个包含了所有服务端上所没有的对象的包文件。
  - 这里的包数据格式为"PACK" <binary data> ，会以PACK开头。服务端接收到这些数据后，启动一个远程调用命令receive-pack，然后将数据以管道的形式传给这个命令即可。pack <binary date>
- 最终，服务端会响应一个成功（或失败）的标识。
  - 000eunpack ok

tokio-rs/axum

axum 是一个使用了 Tokio、Tower 和 Hyper，并专注于模块化的 Web 应用程序框架。

根据协议网关提供了两个请求引用发现的 info/refs，数据传输用到的 git-receive-pack

引用发现返回本地仓库差异结果，然后客户端会传给服务器一个包含packfile的请求，我们从这个请求中得到 packfile 然后解析他就可以得到 packfile 内所有 git 对象的索引信息和内容。解析过程见第三章 packfile 解析。

主要过程是:

1、读 pacfile 建立 index（先把索引解析出来）
2、根据索引再读 packfile （索引要倒序，建立 vec index）
3、读 index 的时候写数据库，

五、数据库设计

数据库使用了 mysql ，使用的是异步的 Rust SQL Toolkit ：sqlx 来写入数据的。

create datebase git;
create table git_index
(
 sha_1 char(40) null,
 obj_type TINYINT UNSIGNED null,
 size BIGINT UNSIGNED null,
 size_in_packfile BIGINT UNSIGNED null,
 offset_in_pack BIGINT UNSIGNED null,
 depth BIGINT UNSIGNED null,
 base_sha_1 char(40) null
)
comment 'git 对象索引';

create table `blob`
(
 sha_1 char(40) null,
 name varchar(256) null,
 context text null,
 file_type varchar(64) null
);

文件内容部分暂时以 blob 存储所有类型，之后计划提取信息构建 commit、tree等对象类型

参考资料

Git - Book

Unpacking Git packfiles (recurse.com)

Git Book - The Packfile (shafiul.github.io)

Git - 传输协议 (git-scm.com)

launchbadge/sqlx: 🧰 The Rust SQL Toolkit

tokio-rs/axum

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

项目分析整体文档.md

项目分析整体文档.md

一、Git存储原理分析

git 对象生命周期和 git 对象间的关系

储存对象方式

git对象储存目录设计逻辑

二、解析Git Object.md

object 对象的存储机制

数据对象 blob

树对象 tree

提交对象 commit

Tag

tag 内容

branch

remote

三、解析Git Packfile.md

git对象的压缩

pack 目录下的逻辑(idx、pack)

unpack

pack方式

packfile 解析

四、网关

传输协议

哑协议

智能协议

1、引用发现

2、数据传输

tokio-rs/axum

五、数据库设计

参考资料

Files

项目分析整体文档.md

Latest commit

History

项目分析整体文档.md

File metadata and controls

一、Git存储原理分析

git 对象生命周期和 git 对象间的关系

储存对象方式

git对象储存目录设计逻辑

二、解析Git Object.md

object 对象的存储机制

数据对象 blob

树对象 tree

提交对象 commit

Tag

tag 内容

branch

remote

三、解析Git Packfile.md

git对象的压缩

pack 目录下的逻辑(idx、pack)

unpack

pack方式

packfile 解析

四、网关

传输协议

哑协议

智能协议

1、引用发现

2、数据传输

tokio-rs/axum

五、数据库设计

参考资料