Thank you everyone for ideas, clues, explanations and questions. Collectively I wrote my proposal. This one is mostly based on Duy's suggestion with minor changes.
Problem:
Current index store all files in a list. This implies that:
1. Each operation has to read the whole index and write the whole index back.
2. computing the checksum for the whole index.
These become expensive when the repo is large.
Requirement: Suppose n is the number objects in a repo -Keep the read/write time <= O(logn). -Keep the checksum computed against only necessary objects. -New format is easy to parse. -Backward compatible. -Potentially use faster hash method.
Proposed solution:
Store the repo structure in a canonical tree. Each directory is a tree block. A tree block contains blobs and offsets to sub directories. It has its own checksum. A read/write will be done on tree block base. A tree block also contains an offset points to its previous version (if there's one).
The root of offset is stored in trailer, which stays at the end of file. Each update creates a new trailer which points to the new tree. (details below)
To save the pain of modify a tree block and track the free spaces in the index, changed blocks are appended at the end. Based on the assumption that user won't change too many files each time, for an updated file, all its parent blocks to Root was copied and appended to index. In other words, all traversed blocks are copied. The offset of previous version of the updated block is stored in the new block. A new generation number is stored in copied and updated blocks. Other blocks are not copied. They are referenced by offsets. After update a new trailer is created at the end. In this way, there's no harm to read, and makes write fast.
Trailer stores the offset of previous trailer. It makes tracking old versions easy.
Each operation will load and rewrite the header and visited trailer .
Checksum for non identifier purpose will use crc32. Otherwise it uses sha1.
For compatibility, old format of index will be transformed to new format in the first operation.
== Index format:
- A 8-byte header consisting of
4-byte signature:
The signature is { 'T', 'R', 'E', 'E' } 4-byte version number:
The current supported versions are 4. - A number of blocks of variable size
1-byte block type
3-byte content size in byte
block content
4-byte crc32 of all above
- A 20-byte trailer consisting of
4-byte trailer signature:
The signature is { 'R', 'O', 'O', 'T' } 4-byte root block offset
4-byte extension table offset:
Zero means no extension 4-byte offset to previous trailer
4-byte checksum:
CRC32 of the header and the trailer (excluding this field)== Tree block:
Tree block content is basically the list of entries in a specified path, with all attributes we store in the index now. This entry list is sorted by pathname. For doing a bsearch in the list, pathnames are stored at the end of block, which makes the size of entry fixed. The pathname is pointed from each entry with 2 byte offset (relative to a block). This should not be problem as a block is never modified.
It stores the generation number and the offset to old block. It also integrates the content of cache-tree.
A tree block content consists of
- 4-byte tree object size
- 20-byte SHA-1 of the cached tree object
- checkpoint : interleave with items in the block, 1 for every 100 items
4-byte offset to next checkpoint
- a list attributes corresponding to tree object's item, in the same
order. These attributes are the same as in DIRC entry format
except that entry name is removed, and a tree block offset is
added in case the item is a directory.
32-bit ctime seconds, the last time a file's metadata changed
this is stat(2) data 32-bit ctime nanosecond fractions
this is stat(2) data 32-bit mtime seconds, the last time a file's data changed
this is stat(2) data 32-bit mtime nanosecond fractions
this is stat(2) data 32-bit dev
this is stat(2) data 32-bit ino
this is stat(2) data 32-bit mode, split into (high to low bits)
4-bit object type
valid values in binary are 1000 (regular file), 1010 (symbolic link)
and 1110 (gitlink) 3-bit unused
9-bit unix permission. Only 0755 and 0644 are valid for regular files.
Symbolic links and gitlinks have value 0 in this field. 32-bit uid
this is stat(2) data 32-bit gid
this is stat(2) data 32-bit file size
This is the on-disk size from stat(2), truncated to 32-bit. 160-bit SHA-1 for the represented object if blobs or the offset
to another tree block if trees A 32-bit 'flags' field split into (high to low bits)
1-bit assume-valid flag
1-bit extended flag (must be zero in version 2)
2-bit stage (during merge)
12-bit name length if the length is less than 0xFFF; otherwise 0xFFF
is stored in this field. 1-bit skip-worktree flag (used by sparse checkout)
1-bit intent-to-add flag (used by "git add -N")
14-bit unused, must be zero
A 16-bit offset, relative to the beginning of this block, to the
pathname of this entry
- 2-byte generation number, starts from 1
- 4-byte previous version offset
- a list of NUL-terminated pathnames, pointed to from the 16-bit offset
above
== Extension table block
Extension table has block type 'X'. It consists of a series of 4-byte extension block offset.
== Extension block
Extension block has block type 'E'. Extension content is the same as in the old format.
Time line:
24/04 ~ 21/05: get familiar with code base and revise proposal benchmark with linux kernel on major operations write prototype to prove feasibility of proposed solution consult mailing list & irc
22/05 ~ 25/06 write code, test and benchmark
modify tree lib
modify index format operations
modify git operations
transform from old to new
26/06 ~ 30/07 revise things according to benchmark
31/07 ~ 13/08 update documentation
About me
My name is Elton Tian, I am from China. I have been living in Australia for quite a few years. I am currently a Master student from Australia National University. After graduate I worked on linux based web development (using tcl) for 2.5 years. I have been programming with c, c#, java, tcl, php, javascript and shell script. But I prefer c, which gives me the feeling of full control over the program. I am interested in data intensive computing. I played with hadoop and mapreduce since 2010. I maintained my 3 node cluster behind my desk. As linus hates cvs with a passion, I still want to mention I was using cvs in work, don't like it though. And I guess this is the good chance to get over it.
On Thu, Apr 5, 2012 at 2:22 AM, elton sky <eltonsky9404@gmail.com> wrote:
