Getting Started with Git (1) History Storage

The goal of this story

• Commentary for those who have used Git a little
• Behind the scenes of git add, commit, know that history is stored in a simple data structure
• I feel like trying my best to think about what to write in the commit log

Introduction

Git is one of the version control systems. What is a version control system?

• Store a set of files
• Quickly retrieve a set of files at a certain point in time
• You can see the history of changes

It is a system with functions such as. Here, "change history" is

• Who messed with what, when
• Commit log message
• Summary of changes
• Background you selected to change
• Actual changes

Refers to a series of information recorded in chronological order.

In addition to Git, there are other version control systems such as CVS and Subversion, but Git has the following features.

• Keep the contents of the file itself
• CVS and Subverion keep the difference
• Manage history with SHA1 hash value
• CVS and Subversion are managed by serial numbers
• Do not manage moving or copying files or directories
• Subversion manages moves and copies
• In Subversion, branches and tags are represented by a spatial copy of the directory.
• CVS manages only the history of each file, so it is not possible to manage movement and copying.
• History cannot be tampered with
• CVS and Subversion can be tampered with if you want to
• You can easily recreate the history
• History can be integrated between multiple repositories
• CVS and Subversion are closed in one repository, so it is impossible
• Facilitates collaboration with multiple people

Content storage

First, let's take a look at how git works as a content hangar. First, create an empty git repository

% mkdir repo1
% cd repo1
% git init
Initialized empty Git repository in repo1/.git/

Create a file called readme.txt, store its contents in the repository, overwrite the file with other contents, and store it in the repository.

% echo aaa > readme.txt
% git hash-object -w readme.txt
72943a16fb2c8f38f9dde202b7a70ccc19c52f34
% echo bbb > readme.txt
% git hash-object -w readme.txt
f761ec192d9f0dca3329044b96ebdb12839dbff6
% rm -f readme.txt

The contents of the stored file can be retrieved using the character string displayed when the hash-object command is executed as a key.

% git cat-file -p 72943a16fb2c8f38f9dde202b7a70ccc19c52f34 > readme.txt
% cat readme.txt
aaa
% git cat-file -p f761ec192d9f0dca3329044b96ebdb12839dbff6 > readme.txt
% cat readme.txt
bbb

What should be noted

• I was able to store and retrieve the contents of the file (using a string that I don't understand as a key)
• File name (path) cannot be stored yet
• File changes (differences from the contents at one point to another) cannot be stored

That is. When the unfinished part becomes possible, it becomes possible to keep the history of changes, but before looking at it, "something I don't understand" is the SHA1 hash value of the file contents (+ α). Let's make sure there is.

hash-object.py

import hashlib
import sys

if len(sys.argv) != 2:
    print("usage: %s file" % sys.argv[0])
    sys.exit(-1)

try:
    f = open(sys.argv[1])
except Exception:
    print("open %s failed" % sys.argv[1])
    sys.exit(-1)

data = f.read()
sha1 = hashlib.sha1("blob %d" % len(data) + "\0" + data).hexdigest()
print(sha1)

This python program

• The string "blob"
• Content (file content) size
• Null character
• Content

Calculates the SHA1 hash value of the concatenation of and outputs its hexadecimal representation. When I actually use it for the above two contents,

% echo aaa | python hash-object.py /dev/stdin
72943a16fb2c8f38f9dde202b7a70ccc19c52f34
% echo bbb | python hash-object.py /dev/stdin
f761ec192d9f0dca3329044b96ebdb12839dbff6

And you can see that the calculation result matches the key used to store the content earlier (the content is stored using the SHA1 hash value of the file content + α as the key). Now, where is the content stored in the repository?

% find .git/objects -type f
.git/objects/72/943a16fb2c8f38f9dde202b7a70ccc19c52f34
.git/objects/f7/61ec192d9f0dca3329044b96ebdb12839dbff6

The SHA1 hash value is the concatenation of the directory name and the file name. If you take the SHA1 value of these files themselves

% sha1sum `find .git/objects -type f`
cf6e4f80cfae36e20ae7eb1a90919ca48f59514b  .git/objects/72/943a16fb2c8f38f9dde202b7a70ccc19c52f34
cdb05607e2e073287a81a908564d9d901ccdd687  .git/objects/f7/61ec192d9f0dca3329044b96ebdb12839dbff6

And the value is different. This is because the contents are compressed and stored, for example.

decompress_sha1.py

import hashlib
import sys
import zlib

if len(sys.argv) != 2:
    print("usage: %s git_object_file" % sys.argv[0])
    sys.exit(-1)

path = sys.argv[1]
try:
    f = open(path)
except Exception:
    print("open %s failed" % path)
    sys.exit(-1)

data = zlib.decompress(f.read())
sha1 = hashlib.sha1(data).hexdigest()
print("%s: %s" % (path, sha1))

If you calculate the hash value after decompressing using the program

% for i in `find .git/objects -type f`; do python ../decompress_sha1.py $i; done
.git/objects/72/943a16fb2c8f38f9dde202b7a70ccc19c52f34: 72943a16fb2c8f38f9dde202b7a70ccc19c52f34
.git/objects/f7/61ec192d9f0dca3329044b96ebdb12839dbff6: f761ec192d9f0dca3329044b96ebdb12839dbff6

You can see that they match properly (the hash values match, so the contents are expected to match).

Directory tree storage

I saw how to store the contents of a file under .git / objects /. Git also stores filename and commit log message information in a file under .git / objects / called a Git object.

At the time of creating the repository, no objects are stored.

% mkdir repo2
% cd repo2
% git init
Initialized empty Git repository in repo2/.git/
% ls .git
HEAD         config       hooks/       objects/
branches/    description  info/        refs/
% find .git/objects -type f

Let's add a file to the staging area with git add.

% echo aaa > readme.txt
% git add readme.txt
% find .git/objects -type f
.git/objects/72/943a16fb2c8f38f9dde202b7a70ccc19c52f34
% ls .git
HEAD         config       hooks/       info/        refs/
branches/    description  index        objects/

One object has been added and a file called index has been created. You can check the contents of the Git object with git cat-file.

% git cat-file -t 729
fatal: Not a valid object name 729
% git cat-file -t 7294
blob
% git cat-file -s 7294
4
% wc -c readme.txt
4 readme.txt
% git cat-file -p 7294
aaa
% cat readme.txt
aaa

As a way to use cat-file

• Gives a hash value, but if you give the first 4 characters or more, it will pick up the one that matches it.
• If there are 3 characters or less, it will be played if there are multiple matches.
• If you check the type with -t, it is a blob object that stores the contents of the file as we saw in the previous section.
• When displaying the size with -s and the contents with -p, it matched the contents of the actual file.

Next, let's write out the information contained in the index as an object.

% git write-tree
580c73c39691399d09ad01152ad0a691ce80bccf
% find .git/objects -type f
.git/objects/58/0c73c39691399d09ad01152ad0a691ce80bccf
.git/objects/72/943a16fb2c8f38f9dde202b7a70ccc19c52f34
% git cat-file -t 580c
tree
% git cat-file -p 580c
100644 blob 72943a16fb2c8f38f9dde202b7a70ccc19c52f34    readme.txt

At this time,

• A new object of the tree type 580c has been stored
• Contains the filename and a pointer to the blob object.

I understand this.

Next, create a directory and a file under it and try git add.

% mkdir tmp
% echo bbb > tmp/bbb.txt
% git add tmp/bbb.txt
% find .git/objects -type f
.git/objects/58/0c73c39691399d09ad01152ad0a691ce80bccf
.git/objects/72/943a16fb2c8f38f9dde202b7a70ccc19c52f34
.git/objects/f7/61ec192d9f0dca3329044b96ebdb12839dbff6
% git cat-file -t f761
blob
% git cat-file -p f761
bbb

The newly added object is a blob object that contains the contents of bbb.txt. If you write index as an object again in this state,

% git write-tree
6434b2415497a42647800c7e828038a2fb6fbbaf
% find .git/objects -type f
.git/objects/58/0c73c39691399d09ad01152ad0a691ce80bccf
.git/objects/5c/40d98927de9cdb27df5b3a7bd4f7ee95dbfc85
.git/objects/64/34b2415497a42647800c7e828038a2fb6fbbaf
.git/objects/72/943a16fb2c8f38f9dde202b7a70ccc19c52f34
.git/objects/f7/61ec192d9f0dca3329044b96ebdb12839dbff6
% git cat-file -t 6434
tree
% git cat-file -p 6434
100644 blob 72943a16fb2c8f38f9dde202b7a70ccc19c52f34    readme.txt
040000 tree 5c40d98927de9cdb27df5b3a7bd4f7ee95dbfc85    tmp
% git cat-file -t 5c40
tree
% git cat-file -p 5c40
100644 blob f761ec192d9f0dca3329044b96ebdb12839dbff6    bbb.txt

here,

• The tree object 580c we saw earlier remains intact.
• Git repositories are basically only appends.
• Two new tree objects have been added.
• Each tree object represents a directory.
• From the root tree object (580c or 6434), you can identify the set of files at a certain point in time.

You can see that.

I wrote a parser for tree because it was a big deal.

parse_tree.py

import hashlib
import sys
import zlib

if len(sys.argv) != 2:
    print("usage: %s git_object_file" % sys.argv[0])
    sys.exit(-1)

try:
    f = open(sys.argv[1])
except Exception:
    print("open %s failed" % sys.argv[1])
    sys.exit(-1)

data = zlib.decompress(f.read())
sha1 = hashlib.sha1(data).hexdigest()

eoh = data.find("\0")
if eoh < 0:
    print("no end of header")
    sys.exit(-1)

header = data[:eoh]
t, n = header.split(" ")

if len(data) - eoh - 1 != int(n):
    print("size mismatch %d,%d" % (len(data) - eoh - 1, int(n)))
    sys.exit(-1)
if t != "tree":
    print("not tree: %s" % t)
    sys.exit(-1)

dsize = hashlib.sha1().digest_size
ptr = eoh + 1
while ptr < len(data):
    eorh = data.find("\0", ptr)
    if eorh < 0:
        print("no end of reference header")
        sys.exit(-1)
    mode, name = data[ptr:eorh].split(" ")
    sha1_ = "".join(map(lambda x: "%02x" % ord(x), data[eorh+1:eorh+1+dsize]))
    print("%s (%6s) %s" % (sha1_, mode, name))
    ptr = eorh + 1 + dsize

% python parse_tree.py .git/objects/64/34b2415497a42647800c7e828038a2fb6fbbaf
72943a16fb2c8f38f9dde202b7a70ccc19c52f34 (100644) readme.txt
5c40d98927de9cdb27df5b3a7bd4f7ee95dbfc85 ( 40000) tmp

The data structure of the tree object is in zlib-compressed data (similar to blobs).

• The string "tree"
• Content size
• Null character
• Content

The content part is

• Pointed object type and file mode
• The name of the file or directory
• Null character
• SHA1 hash value of the object to point to

It is a repetition of.

Commit history storage

Now that we've seen two types of objects, blob and tree, let's look at the commit object at the end. Try creating a commit that references the tree object 580c.

% git commit-tree -m "initial commit" 580c
7a5c786478f17fd96b385c725c95d10fa74e4576
% ls .git/objects/7a/5c786478f17fd96b385c725c95d10fa74e4576
.git/objects/7a/5c786478f17fd96b385c725c95d10fa74e4576
% git cat-file -t 7a5c
commit
% git cat-file -p 7a5c
tree 580c73c39691399d09ad01152ad0a691ce80bccf
author Yoichi Nakayama <[email protected]> 1447772602 +0900
committer Yoichi Nakayama <[email protected]> 1447772602 +0900

initial commit

Next, let's create a commit that references the tree object 6434, with that commit object 7a5c as the parent.

% git commit-tree -p 7a5c -m "second commit" 6434
88470d975c1875e2e03a46877c13dde9ed2fd1ea
% ls .git/objects/88/470d975c1875e2e03a46877c13dde9ed2fd1ea
.git/objects/88/470d975c1875e2e03a46877c13dde9ed2fd1ea
% git cat-file -t 8847
commit
% git cat-file -p 8847
tree 6434b2415497a42647800c7e828038a2fb6fbbaf
parent 7a5c786478f17fd96b385c725c95d10fa74e4576
author Yoichi Nakayama <[email protected]> 1447772754 +0900
committer Yoichi Nakayama <[email protected]> 1447772754 +0900

second commit

If you enter the hash value of this commit object in master referenced by HEAD, You can see the history with git log.

% cat .git/HEAD
ref: refs/heads/master
% echo 88470d975c1875e2e03a46877c13dde9ed2fd1ea > .git/refs/heads/master
% git log
commit 88470d975c1875e2e03a46877c13dde9ed2fd1ea
Author: Yoichi Nakayama <[email protected]>
Date:   Wed Nov 18 00:05:54 2015 +0900

    second commit

commit 7a5c786478f17fd96b385c725c95d10fa74e4576
Author: Yoichi Nakayama <[email protected]>
Date:   Wed Nov 18 00:03:22 2015 +0900

    initial commit

You can now see the history you normally see after git commit. You can also give git diff the hash value of the target commit object to see the diff.

% git diff 7a5c 8847
diff --git a/tmp/bbb.txt b/tmp/bbb.txt
new file mode 100644
index 0000000..f761ec1
--- /dev/null
+++ b/tmp/bbb.txt
@@ -0,0 +1 @@
+bbb

The data structure of the commit object is the same as the blob object except that it starts with "commit" and as content

• The root tree object of a set of files
• This identifies the entire target file set
• Parent commit object
• author, committer (details will be seen next time)
• Commit log message

Includes.

Summary

• Git manages history using commit, tree, blob
• Objects are identified by SHA1 hash
• Basically only objects are added. Does not disappear without permission
• What happens if a hash collision occurs? → I will give you references
• The commit object contains the following information:
• Who committed when
• Commit log message
• Parent commit object
• File set
• Actual changes (differences) are not explicitly stored
• Calculated from the file sets pointed to by the commit object
• File movements and copies are also calculated → You may make a mistake
• The content of the commit log message is left to the user
• Do your best and write useful content!
• Useful content = Information that Git doesn't store on its own
• Summary of changes → You can see what kind of changes have been made
• Background of choosing the change → You can grasp the restrictions at the time of future renovation
• If the supplementary information is in the issue management system, it may be good to write down the ticket number.
• Commit → Refurbishment ticket → Original implementation ticket → ...

reference

• Command reference
• man git-{command name}
• https://git-scm.com/docs
• Inside Git-Git object (https://git-scm.com/book/ja/v1/ Inside Git-Git object)
• Git index format
• stackoverflow - How would git handle a SHA-1 collision on a blob?
• Unfinished forever-Git can't track file movements

Continued

• Introduction to Git (2) Not scary reset