From: elton sky Date: Fri, 06 Apr 2012 03:15:44 GMT Subject: Re: GSoC - Designing a faster index format Message-ID: In-Reply-To: NOTE: Please ignore the >- checkpoint : interleave with items in the block, 1 for every 100 items >       4-byte offset to next checkpoint That's irrelevant. Cheers, Elton On Fri, Apr 6, 2012 at 1:13 PM, elton sky wrote: > 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 wrote: >> Hello, >> >> Some updates for Nguyen's index: >> >> On Wed, Apr 4, 2012 at 10:20 PM, Nguyen Thai Ngoc Duy wrote: >>> On Wed, Apr 4, 2012 at 3:26 PM, elton sky 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