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@xxxxxxxxx> wrote:
> Hello,
>
> Some updates for Nguyen's index:
>
> On Wed, Apr 4, 2012 at 10:20 PM, Nguyen Thai Ngoc Duy <pclouds@xxxxxxxxx> wrote:
>> On Wed, Apr 4, 2012 at 3:26 PM, elton sky <eltonsky9404@xxxxxxxxx> wrote:
>>> I am not sure how the trailer works.
>>> I assume there can be multiple trailers, each update will generate a
>>> new one. Every trailer will point to the root tree (i.e. all trailers
>>> point to the same block?). So if there are some changes to root, like
>>> rename, trailers all point to the latest root block?
>>
>> Each trailer points to the whole new tree. Because trees are
>> immutable, changing in a tree meangs creating a new one and will also
>> make a new parent tree (to point to the updated tree because old
>> parent will always point to old tree). This eventually leads to root
>> tree change, recorded by the trailer.
>>
>>> Is the index looks like :
>>> | HEADER | TREE BLOCKS | TRAILER | TREE BLOCKS | TRAILER | TREE
>>> BLOCKS | TRAILER | ...
>>>
>
> Once an update happened to a block, all parent blocks to root will be
> copied to the end of the index. And the updated block will be at leaf
> of the new tree. Finding this path costs logn time anyway. This is no
> harm for read for the whole tree. But in order to find all previous
> changes to a block, we have to go through all trailers and trees.
>
> Otherwise, just modify the original tree. Let the parent points to the
> updated block and let the updated block points to the old block:
>
> parent
> |
> V
> updated old old
> block (v3) --> block(v2) --> block (v1)
> |
> V
> child
> blocks
>
> A version number in a tree block is used to track the changes.
> In this way, there's still no harm to read, and it's more easy to
> trace the change history of a block. Also, we don't need to create
> interleaved blocks and trailers. There's only one trailer in the end
> of file. We also need to add another offset points to previous
> version.
>
> Trailer is kept at the end of index, as its size is variable. It
> contains offset to root and list of free spaces.
>
> Changes to format:
>
>> = The git index file has the following format
>
> As is, except there's only one trailer now. And trailer contains list
> of free spaces.
>
>>- A 18-byte trailer consisting of
>>
>> 4-byte trailer signature:
>> The signature is { 'R', 'O', 'O', 'T' }
>>
>> 2-byte generation:
>> The first trailer is 0, the second 1 and so on.
>>
>> 4-byte root block offset
>>
>> 4-byte extension table offset:
>> Zero means no extension
>>
> list of free spaces
> - 4 byte offset
> - 2 byte length
>
>> 4-byte checksum:
>> CRC32 of the header and the trailer (excluding this field)
>
> Free space list is read/written in whole for each operation, together
> with trailer.
>
>>
>> == Tree block
>> ...
>
> Above as is.
>
> - 1 byte version num
>
> - 4 byte offset to previous version block
>
>>
>> 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. FIXME: make it 32-bit, relative to the
>> beginning of the file, so that we can reuse pathnames from other
>> (old) blocks?
>>
>
> -Elton
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html