CS61B Gitlet 完结记录

又名：Gitlet in Hindsight: Why I Suggest U Always Read the DON’Ts Part in Spec First

花了几天补票了61b的知名项目Gitlet——60页重量级spec面面俱到（笑），项目内容自带科普性，覆盖从系统设计到集成测试的每种技术基础普及和训练，不愧是该课史上评价最高的pj。

项目概述

Gitlet是一个版本管理系统，仿照主流系统Git的功能并实现了其部分基本命令，包括init, add, commit, rm, checkout, branch, reset, rm-branch, merge等。

作为一个课程个人项目，开局仅有几个必要的类.java和几行代码样例，要求根据需求自行设计并完成系统、对象方法、数据结构和少量算法的构造。

Gitlet版本控制原理

Git（let）的版本控制说白了就是「怎么保存某个版本」和「怎么切换到某个版本」的问题。可以从由上至下三个层面理解这两个问题：一是从最上面的用户层面；二是从对象层面；三是从文件读写层面。

从设计上来说这三层之间应该存在abtraction barrier。也就是说用户使用命令时不需要知道也不能操作对象、指针这些，对象之间也不应该出现文件读写操作。

用户层面

先是一些上层发生的事情，也就是用户能知道的部分。

git初始化干了什么？在当前工作目录（CWD）创建一个.git的隐藏目录目录和里面的一些文件。
怎么保存文件的版本？每次commit时，获取所提交的文件的当前快照（snapshot），并保存在.git中。
怎么切换到指定的版本？使用像是checkout, reset 这样切换版本的命令时，git会根据给定的分支名/commit id等，在.git中查找对应的快照，然后把CWD中指定的文件或是整个目录还原成这个快照的样子。

对象层面

然后再看对象层是如何实现这几个步骤的。gitlet在一定程度上简化了git的目录结构，各个对象少存了一些元数据，但本质不变，就用gitlet举例了。下图里是.gitlet目录的结构示意。

gitlet的版本控制实现用到了两类的对象：Commit和Blob。
- 每个Blob对象对应一个文件快照。
- 每个Commit对象对应一次commit。
怎么利用这些对象记录文件的版本？
- 每次把文件加入staging area暂存区（add [file name]）时，会创建一个Blob对象存储当前的文件内容，然后把（文件名: 对应的Blob实例）映射关系丢到暂存区里。
- 每次commit一些文件时，会创建一个Commit对象，从暂存区把可以提交的映射关系保存进Commit对象中。每个对象里除了索引对以外还会记录其父Commit、时间戳、commit message等。
- 例子：下图中每个蓝色方块代表一个Commit对象，每个Commit对象中存有一个Map，里面记录了当前commit的文件对应的文件快照。比如Commit 1和Commit 2的Hello.txt都指向Blob 0，这就是说在两次commit时文件内容（快照）没有变化。
怎么实现切换到指定的版本？——移动指针
- 要让HEAD指针切换到另一个分支branchB的branchHeadCommit，这在对象层就等于：HEAD指针本来指向branchA上的某个Commit对象，现在让它指向另一个branchHeadCommit这个Commit对象。类似updatePointerToCommit(HEAD, branchHeadCommit)。

文件读写层面

最后看更低一层，文件读写层。因为执行一部分命令时要把Blob对象和Commit对象以及暂存区的当前内容存储到本地，这就涉及到两个问题：

如何对象存成数据（方便后续需要的时候从文件中取出调用）？

利用Java的序列化（Serialization）。Java里的序列化读写操作：
在gitlet里，所有对象都是可以序列化存进文件里的，包括Blob、Commit和StagingArea（如有）。在.git里，它们被存放在/.git/objects/目录中。
而指针变动实际是通过文件读写实现的（不需要序列化）。每个指针都是一个文件，文件里存着它指向的对象的id。在修改指针指向时，实际修改的是文件里的id。在.git里，它们被存放在.git/refs/目录中。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


/* Serialize a Model object */
Model m = ....; // 可序列化前提：Model类需要implements Serializable
File outFile = new File(saveFileName); // 新建File
try {
    ObjectOutputStream out =
        new ObjectOutputStream(new FileOutputStream(outFile));
    out.writeObject(m); // 将对象写入steam
    out.close();
} catch (IOException excp) {
    ...
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


/* Deserialize a Model object */
Model m;
File inFile = new File(saveFileName);
try {
    ObjectInputStream inp =
        new ObjectInputStream(new FileInputStream(inFile));
    m = (Model) inp.readObject();  // cast object into expected class
    inp.close();
} catch (IOException | ClassNotFoundException excp) {
    ...
    m = null;
}

如何查找并获取对象/修改指针指向？
- Gitlet和Git都使用SHA-1（Secure Hash Algorithm 1）加密数据，产生一个160位的哈希值作为当前对象的id（40个十六进制数）。每个对象在创建时会根据自身的内容产生id，比如相同的文件内容经过加密会产生相同的id；并且它们保存的文件名就是它们的id。这意味着通过id就可以在目录中找到对应序列化过的对象。更重要的是，这就允许根据内容寻找文件的地址（content-addressable)。
- 关于对象获取，以获取Commit对象为例，步骤是：获得commit id（对象在构造时应有id字段） -> 根据id获取文件路径（因为都存放在指定目录下，根据id寻址） -> 反序列化文件。同理，修改就是修改对象内容后，再序列化写入文件。
- 关于修改指针指向，在文件读写层实际需要完成的操作是：获取targetCommit的id -> 把id写入HEAD指针对应的文件中。

（提醒自己）需要注意的是这些操作都应该封装在对象里，在主逻辑里不该出现commitMap.put(readContentAsString(commitPath), readContentAsString(blobPath))这种东西。写完翻别人实现的时候，看到有人是这样在对象层混用文件读写操作的，达咩。

小结

以上是三遍不同的废话。版本控制系统类比一下基本就是：

初始化版本控制系统 == 在当前工作目录放一个小盒子
保存文件的版本 == 每次提交时，把提交的东西拷一份存档放盒子里
切换当前目录/目录中某个文件到某个版本 == 在盒子里找对应的存档，拿出来放在CWD

其余的对象、指针和编码等等方式，都是用来精简每次拷贝的东西、加快盒子里找东西的速度的tricks（至少我是这么理解）：

Blob对象 == 一个文件的存档
Commit对象 == 一张记录哪个时候该找哪个文件版本的小抄
Commit tree == 小抄们的目录大纲
SHA-1编码 == 给每个文件按照他们的内容起名（在快速对比文件内容、寻址上都有用）
指针 == 写着现在盒子里是哪个版本的标签

暴力存档谁都会（试想：paper_final_final_final.docx)，要说的话，我觉得精髓在于sha-1。

思考

边写代码边记录的，比较乱

关于spec阅读顺序

gitlet的项目说明很长，一次读完再开始不现实。如果再写一次，我会先看视频+扫读所有commands说明和avoids事项，然后边写边看。
spec里的「注意不要xxx」部分要仔细看，之所以写上去是因为大家真的会这样做，比如默认Map都是HashMap然后写出Heisenbug，实际为了维护顺序应该用TreeMap。←callback开头

关于设计

一开始需要整体地阅读spec，明确每个对象的作用和它们之间的常用交互方法，设计好了再开始实现。

正面案例：在写<branch>命令的时候准备大改目录，但因为前面abstraction设计得还不错，除了File目录加一句以外什么都不需要改。
保护abstraction barrier。上层对象之间的交互一定要避免使用底层操作。

反面案例：前期直接在主逻辑里完成hashing、序列化，中间为了封装重构改了好久
起名很重要。经过血的教训总结以下几点：
- 统一性–就像数据表连接一样，既然对象之间需要通信，那它们一定有一些共通的名字。反面案例就像是我一开始干的，把sha-1 hash得到的id，在不同类里写成shaName、shaId、hashName…
- 直观性–变量名越具体越好，比如map可以写出keyToVal，不然想起来费劲
- 泛用性–方法最好不要太具体，这样再别处调用的时候也能想起来。比如getHead getMaster就可以写成getCommit/getPointer。

其他

可以读下git的源码寻找better practice，虽然只看spec也基本够用。

数据

time and space

代码总行数大约1k；时间上大概花了4.5天，wakatime统计的用时是40小时左右，虽然里面十多个小时在debug（。）这方面我记得Josh课上有分享同学的数据，大部分人完成时间也差不多是30-40hrs。

从统计上看gitlet体量不大，不过考虑到它要求独立完成且涉及到了设计、单元和集成测试、makefile、java file i/o、算法、编码、甚至git本身的训练，还是非常rewarding的。

Autograder情况

通过了所有功能性测试。Fail的几个Extra-Credit，style (mainly naming，下次一定)和迟交我认为无伤大雅，就没有继续面向autograder编程。

没有写EC的原因：1）到了后期很多指令都是组合前面的指令，边际效益低；2）gitlet中的remote指令和git相去甚远，不见得有助于学习git的底层逻辑；3）在de了一个Heisenbug以后心力憔悴。

感想

Gitlet是一款我的世界名校震撼.jpg 就像开头吹的一样，我坚信大部分水平和我类似的人都能通过这个project收获很多，具体只要看一眼spec就知道了。

技术上我太菜也没资格说什么，只能最后讲几句别的。Josh在不记得哪节课上分享过Gitlet的survey结果，印象深刻的是有一部分学生在这个pj上花了50+小时（就我个人经历，这远超出正常大一的一门课的一个课设的workload），但是最后给了负面评价的只有寥寥几人，Josh好像还单独拿出来表示抱歉了。从侧面反映了The Gitlet Grind的价值。

61B至此完结，感恩开源！继续肝别的去咯

附录

以下是从写的readme中转载的my gitlet设计方面的说明

Design

Abstraction Principle

An issue with version control systems:

Requires cumbersome operations like hashing, serialization, map operations, directory concatenation, file I/O, etc.
Solution:
- On a higher level, involve only communications between objects (between Blob and Commit, there should only be Blob b = commit1.get(filename))
- Eliminate the need to dive into low-level operations through encapsulation. i.e. Outside the class of that object, never try to hash things, or modify maps inside Commit/Blob objects. E.g. The StagingArea supports common map operations. Upon put (fileName, Commit), it completes: read commit into commit id -> put into its map -> serialize itself and write into the file for staging.

Persistence

The directory structure looks like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


CWD
 └──.gitlet
     └── --commits/       # all commits
        ├──blobs/         # file content
        ├──branchHeads/   # branch heads
        |  └──--master      # master branch
        |    ├──..	      # other branches
        ├──HEAD	          # HEAD commit
        ├──add            # staging area for addition
        └──rm             # staging area for removal

The Main class is the entry class of the project. It is responsible for calling different functions according to given commands.

The Repository class will set up all persistance. It will

Create and initialize files and directories in the .gitlet folder if the directory does not exist;
Handle all updates of HEAD , master, branchHeads and the serialization of two StagingAreas add and rm.
Execute the commands / function calls from Main.

The Commit class handles the serialization of Commit objects. It also deals with conversion between commit ids and commit objects. Each Commit records mappings of held file names and their corresponding file content. Specifically, it fulfil the following purposes:

Constructs Commit objects;
Serializes and saves Commit objects to the .gitlet/commits directory;
Given a commit id, retrieves the corresponding Commit object.

The Blob class handles the serialization of Blob objects. A blob is a snapshot of a file’s content at the moment of addition. For instance, a file named “hello.txt” can refer to different Blobs in different Commits.

Its functions are similar to Commit, namely object construction, serialization and retrieval.

The StagingArea class stores files for addition and removal. A StagingArea works like a Java Map, stores mappings of file plain names to their blob ids, and supports basic map operations (remove, get, put). add and rm are StagingAreas for staged addition and removal respectively.

项目概述#

Gitlet版本控制原理#

用户层面#

对象层面#

文件读写层面#

小结#

思考#

关于spec阅读顺序#

关于设计#

其他#

数据#

time and space#

Autograder情况#

感想#

附录#

Design#

Abstraction Principle#

Persistence#