From: Thomas Rast <hidden> Date: 2016-06-15 22:53:23
elton sky [off-list ref] writes:
On Mon, Mar 26, 2012 at 12:06 PM, Nguyen Thai Ngoc Duy
[off-list ref] wrote:
quoted
(I think this should be on git@vger as there are many experienced devs there)
On Sun, Mar 25, 2012 at 11:13 AM, elton sky [off-list ref] wrote:
quoted
About the new format:
The index is a single file. Entries in the index still stored
sequentially as old format. The difference is they are grouped into
blocks. A block contains many entries and they are ordered by names.
Blocks are also ordered by the name of the first entry. Each block
contains a sha1 for entries in it.
If I remove an entry in the first block, because blocks are of fixed
size, you would need to shift all entries up by one, thus update all
blocks?
We need some GC here. I am not moving all blocks. Rather I would
consider merge or recycle the block. In a simple case if a block
becomes empty, I ll change the offset of new block in the header point
to this block, and make this block points to the original offset of
new block. In this way, I keep the list of empty blocks I can reuse.
[...]
Doesn't that venture into database land?
If we go that far, wouldn't it be better to use a proper database
library? All other things being equal, writing such complex code from
scratch is probably not a good idea.
--
Thomas Rast
trast@{inf,student}.ethz.ch
On Mon, Mar 26, 2012 at 9:28 PM, Thomas Rast [off-list ref] wrote:
elton sky [off-list ref] writes:
quoted
On Mon, Mar 26, 2012 at 12:06 PM, Nguyen Thai Ngoc Duy
[off-list ref] wrote:
quoted
(I think this should be on git@vger as there are many experienced devs there)
On Sun, Mar 25, 2012 at 11:13 AM, elton sky [off-list ref] wrote:
quoted
About the new format:
The index is a single file. Entries in the index still stored
sequentially as old format. The difference is they are grouped into
blocks. A block contains many entries and they are ordered by names.
Blocks are also ordered by the name of the first entry. Each block
contains a sha1 for entries in it.
If I remove an entry in the first block, because blocks are of fixed
size, you would need to shift all entries up by one, thus update all
blocks?
We need some GC here. I am not moving all blocks. Rather I would
consider merge or recycle the block. In a simple case if a block
becomes empty, I ll change the offset of new block in the header point
to this block, and make this block points to the original offset of
new block. In this way, I keep the list of empty blocks I can reuse.
[...]
Doesn't that venture into database land?
If we go that far, wouldn't it be better to use a proper database
library? All other things being equal, writing such complex code from
scratch is probably not a good idea.
If there's a library that fits our needs (including linking
statically). I think we've come close to sqlite file format [1]. But
sqlite comes with sql engine, transactional updates... that we don't
need. Another obvious source for inspiration is file systems, but I
dare not go that way.
[1] http://www.sqlite.org/fileformat2.html
--
Duy
On Mon, Mar 26, 2012 at 08:25, Nguyen Thai Ngoc Duy [off-list ref] wrote:
On Mon, Mar 26, 2012 at 9:28 PM, Thomas Rast [off-list ref] wrote:
quoted
elton sky [off-list ref] writes:
quoted
On Mon, Mar 26, 2012 at 12:06 PM, Nguyen Thai Ngoc Duy
[off-list ref] wrote:
quoted
(I think this should be on git@vger as there are many experienced devs there)
On Sun, Mar 25, 2012 at 11:13 AM, elton sky [off-list ref] wrote:
quoted
About the new format:
The index is a single file. Entries in the index still stored
sequentially as old format. The difference is they are grouped into
blocks. A block contains many entries and they are ordered by names.
Blocks are also ordered by the name of the first entry. Each block
contains a sha1 for entries in it.
If I remove an entry in the first block, because blocks are of fixed
size, you would need to shift all entries up by one, thus update all
blocks?
We need some GC here. I am not moving all blocks. Rather I would
consider merge or recycle the block. In a simple case if a block
becomes empty, I ll change the offset of new block in the header point
to this block, and make this block points to the original offset of
new block. In this way, I keep the list of empty blocks I can reuse.
[...]
Doesn't that venture into database land?
If we go that far, wouldn't it be better to use a proper database
library? All other things being equal, writing such complex code from
scratch is probably not a good idea.
If there's a library that fits our needs (including linking
statically). I think we've come close to sqlite file format [1]. But
sqlite comes with sql engine, transactional updates... that we don't
need. Another obvious source for inspiration is file systems, but I
dare not go that way.
[1] http://www.sqlite.org/fileformat2.html
Or use LevelDb[2]. Its BSD license. Uses an immutable file format, but
writes updates to new smaller files and eventually collapses
everything back together into a bigger file. This can be a
dramatically simpler approach than dealing with your own free block
system inside of a single file. Its only real downside is needing to
periodically pay a penalty to rewrite the whole index. But this
rewrite is going to be faster than the time it takes to rewrite the
pack files for the same repository, which git gc or git repack
handles. So I don't think its actually a problem for the index.
You might even be able to take a two level approach to compacting the
LevelDb database (or something like it). In a minor compaction you
compact all of the files except the huge base file, leaving you with 2
files. A huge base file that contains the first tree the user checked
out, and a second smaller file containing any differences they have
since the initial checkout (this may just be updated stat data for a
handful of files that differed across two branches as they switched
back and forth). During a git gc or git repack, add a new stage to
collapse the base file and everything else into a single new base file
as a major compaction.
[2] http://code.google.com/p/leveldb/
On Mon, Mar 26, 2012 at 9:28 PM, Thomas Rast [off-list ref] wrote:
Doesn't that venture into database land?
How about this (a bit like memory management). Maybe it's simpler than
a database and fits us better.
The header consists of crc32 and three uint32_t, one points to the
root tree, one the first extension block, the last one the free list
at the end of the file. The rest of the file contains sizable blocks.
There can be free space between them. Free spaces (offset and size)
are recorded at the end of the file, pointed in header. The header's
crc32 covers the header and free list.
When we need a new block, we look up in free list. If we cannot find a
suitable space, we append to the end of the file (moving free list
further to keep it always the end of the file). Removing a block means
marking it in free list. We only truncate if there is free space at
the end. Operations that we know will scratch the whole index are our
opportunity to rewrite the index and make it compact again. No random
garbage collection (iow disk is cheap).
A block starts with a signature (a tree block, or an extension...). A
tree block consists of:
- uint32_t tree object's size
- sha-1 of tree object
- crc32 of the rest of the block except tree object
- maybe reference counter of a block can be refered by many blocks??
- tree object (i.e. something that tree-walk.c can parse)
- other index attributes, stored separately in the same order as in
tree object above, uint32_t block offset of subdirectories.
An extension block basically consists of what we have now in an
extension plus uint32_t offset to the next extension block, so we can
keep track of all extensions. crc32 is used for extension blocks.
This way we only need to verify checksum of the header (and free list)
and blocks we visit. We don't need cache-tree extension because it's
part of the format. There will be headache with unpack-trees.c because
of entry order change. But in the end we would use the same order tree
objects are using now, much simpler for us.
--
Duy
Or use LevelDb[2]. Its BSD license. Uses an immutable file format, but
writes updates to new smaller files and eventually collapses
everything back together into a bigger file. This can be a
dramatically simpler approach than dealing with your own free block
system inside of a single file. Its only real downside is needing to
periodically pay a penalty to rewrite the whole index. But this
rewrite is going to be faster than the time it takes to rewrite the
pack files for the same repository, which git gc or git repack
handles. So I don't think its actually a problem for the index.
You might even be able to take a two level approach to compacting the
LevelDb database (or something like it). In a minor compaction you
compact all of the files except the huge base file, leaving you with 2
files. A huge base file that contains the first tree the user checked
out, and a second smaller file containing any differences they have
since the initial checkout (this may just be updated stat data for a
handful of files that differed across two branches as they switched
back and forth). During a git gc or git repack, add a new stage to
collapse the base file and everything else into a single new base file
as a major compaction.
[2] http://code.google.com/p/leveldb/
I don't know leveldb, but like to have a look.
Just realize this solution is kinda popular. HDFS also uses the
similar image file with edit file format for its file block index.
Hi Nguyen,
Thanks for the idea. just a few questions
On Tue, Mar 27, 2012 at 3:19 AM, Nguyen Thai Ngoc Duy [off-list ref] wrote:
On Mon, Mar 26, 2012 at 9:28 PM, Thomas Rast [off-list ref] wrote:
quoted
Doesn't that venture into database land?
How about this (a bit like memory management). Maybe it's simpler than
a database and fits us better.
The header consists of crc32 and three uint32_t, one points to the
root tree, one the first extension block, the last one the free list
at the end of the file. The rest of the file contains sizable blocks.
There can be free space between them. Free spaces (offset and size)
are recorded at the end of the file, pointed in header. The header's
crc32 covers the header and free list.
How do you record free spaces at the end of file? Are you gonna have a
fixed size for the index and reserve space for free spaces offsets.
When we need a new block, we look up in free list. If we cannot find a
suitable space, we append to the end of the file (moving free list
further to keep it always the end of the file). Removing a block means
marking it in free list. We only truncate if there is free space at
the end. Operations that we know will scratch the whole index are our
opportunity to rewrite the index and make it compact again. No random
garbage collection (iow disk is cheap).
I agree with you. Maybe we just ignore free spaces in the index and
let a background thread to compact it.
A block starts with a signature (a tree block, or an extension...). A
tree block consists of:
- uint32_t tree object's size
- sha-1 of tree object
- crc32 of the rest of the block except tree object
- maybe reference counter of a block can be refered by many blocks??
- tree object (i.e. something that tree-walk.c can parse)
Do you mean each block contains a tree and all its blobs? So the tree
object here, effectively a dir, also contains files in the dir ? In
this way, some blocks can be very big.
- other index attributes, stored separately in the same order as in
tree object above, uint32_t block offset of subdirectories.
There can be many sub dirs some times. But maybe not a prob.
As tree object and offset of subdirectories are variables, how do you
make a block resizable?
An extension block basically consists of what we have now in an
extension plus uint32_t offset to the next extension block, so we can
keep track of all extensions. crc32 is used for extension blocks.
This way we only need to verify checksum of the header (and free list)
and blocks we visit. We don't need cache-tree extension because it's
part of the format. There will be headache with unpack-trees.c because
of entry order change. But in the end we would use the same order tree
objects are using now, much simpler for us.
--
Duy
From: David Barr <hidden> Date: 2016-06-15 22:53:23
On Tue, Mar 27, 2012 at 1:49 PM, elton sky [off-list ref] wrote:
Thanks Shawn,
quoted
Or use LevelDb[2]. Its BSD license. Uses an immutable file format, but
writes updates to new smaller files and eventually collapses
everything back together into a bigger file. This can be a
dramatically simpler approach than dealing with your own free block
system inside of a single file. Its only real downside is needing to
periodically pay a penalty to rewrite the whole index. But this
rewrite is going to be faster than the time it takes to rewrite the
pack files for the same repository, which git gc or git repack
handles. So I don't think its actually a problem for the index.
You might even be able to take a two level approach to compacting the
LevelDb database (or something like it). In a minor compaction you
compact all of the files except the huge base file, leaving you with 2
files. A huge base file that contains the first tree the user checked
out, and a second smaller file containing any differences they have
since the initial checkout (this may just be updated stat data for a
handful of files that differed across two branches as they switched
back and forth). During a git gc or git repack, add a new stage to
collapse the base file and everything else into a single new base file
as a major compaction.
[2] http://code.google.com/p/leveldb/
I don't know leveldb, but like to have a look.
Just realize this solution is kinda popular. HDFS also uses the
similar image file with edit file format for its file block index.
Or use LevelDb[2]. Its BSD license. Uses an immutable file format, but
writes updates to new smaller files and eventually collapses
everything back together into a bigger file. This can be a
dramatically simpler approach than dealing with your own free block
system inside of a single file. Its only real downside is needing to
periodically pay a penalty to rewrite the whole index. But this
rewrite is going to be faster than the time it takes to rewrite the
pack files for the same repository, which git gc or git repack
handles. So I don't think its actually a problem for the index.
Cool. I had an experiment with it. A database is created where are
keys `git ls-files` on linux-2.6. A few things after the experiment:
- we need to link to libstdc++.so. I still hope to avoid any new
runtime dependencies
- I use gettimeofday to time some operations. On linux-2.6,
read_cache() costs 27ms. leveldb_open() alone takes 90ms. Iterating
over all keys takes ~200ms.
Performance wise it does not look very good but maybe I'm just not
doing it right.
On Tue, Mar 27, 2012 at 10:34 AM, David Barr [off-list ref] wrote:
Another implementation in this general class is TinyCDB[1].
It is <1600 lines of plain C. Too few to be complete?
It is a derivative of DJB's CDB[2].
[1] http://www.corpit.ru/mjt/tinycdb.html
"CDB is a constant database, that is, it cannot be updated at a
runtime, only rebuilt.". It does not sound promising to me. I have not
read the description carefully though.
On Tue, Mar 27, 2012 at 10:20 AM, elton sky [off-list ref] wrote:
On Tue, Mar 27, 2012 at 3:19 AM, Nguyen Thai Ngoc Duy [off-list ref] wrote:
quoted
The header consists of crc32 and three uint32_t, one points to the
root tree, one the first extension block, the last one the free list
at the end of the file. The rest of the file contains sizable blocks.
There can be free space between them. Free spaces (offset and size)
are recorded at the end of the file, pointed in header. The header's
crc32 covers the header and free list.
How do you record free spaces at the end of file? Are you gonna have a
fixed size for the index and reserve space for free spaces offsets.
A list of (offset,size) with (0,0) to terminate. No index can shrink
or expand at will. Free list is always at the end of the index.
quoted
A block starts with a signature (a tree block, or an extension...). A
tree block consists of:
- uint32_t tree object's size
- sha-1 of tree object
- crc32 of the rest of the block except tree object
- maybe reference counter of a block can be refered by many blocks??
- tree object (i.e. something that tree-walk.c can parse)
Do you mean each block contains a tree and all its blobs? So the tree
object here, effectively a dir, also contains files in the dir ? In
this way, some blocks can be very big.
No, the tree object contains pathname, mode and SHA-1 of its entries,
one level only (try "git ls-tree HEAD"). If an entry is a directory
and we have not built it yet, we won't have its sha-1, so it will be
zero (similar to invalid cache-tree).
quoted
- other index attributes, stored separately in the same order as in
tree object above, uint32_t block offset of subdirectories.
There can be many sub dirs some times. But maybe not a prob.
As tree object and offset of subdirectories are variables, how do you
make a block resizable?
If there are free space right after it, it can be expanded. Otherwise
we need to move the block elsewhere and update its parent about its
new offset, then mark where the block was as free space.
--
Duy
From: Jeff King <hidden> Date: 2016-06-15 22:53:25
On Tue, Mar 27, 2012 at 01:33:33PM +0700, Nguyen Thai Ngoc Duy wrote:
On Tue, Mar 27, 2012 at 10:34 AM, David Barr [off-list ref] wrote:
quoted
Another implementation in this general class is TinyCDB[1].
It is <1600 lines of plain C. Too few to be complete?
It is a derivative of DJB's CDB[2].
[1] http://www.corpit.ru/mjt/tinycdb.html
"CDB is a constant database, that is, it cannot be updated at a
runtime, only rebuilt.". It does not sound promising to me. I have not
read the description carefully though.
No, you are right. I did some work with cdb many years ago. It optimizes
for lookup by spending time building an optimal hash table at generation
time. There is no way to add or modify an entry short of rewriting the
complete contents of the database, which is exactly what we are trying
to get away from with the current index format.
-Peff
Hi Nguyen,
Still have some questions on your idea:
On Tuesday, March 27, 2012, Nguyen Thai Ngoc Duy wrote:
On Tue, Mar 27, 2012 at 10:20 AM, elton sky [off-list ref] wrote:
quoted
On Tue, Mar 27, 2012 at 3:19 AM, Nguyen Thai Ngoc Duy [off-list ref] wrote:
quoted
The header consists of crc32 and three uint32_t, one points to the
root tree, one the first extension block, the last one the free list
at the end of the file. The rest of the file contains sizable blocks.
There can be free space between them. Free spaces (offset and size)
are recorded at the end of the file, pointed in header. The header's
crc32 covers the header and free list.
How do you record free spaces at the end of file? Are you gonna have a
fixed size for the index and reserve space for free spaces offsets.
A list of (offset,size) with (0,0) to terminate. No index can shrink
or expand at will. Free list is always at the end of the index.
quoted
quoted
A block starts with a signature (a tree block, or an extension...). A
tree block consists of:
- uint32_t tree object's size
- sha-1 of tree object
- crc32 of the rest of the block except tree object
- maybe reference counter of a block can be refered by many blocks??
- tree object (i.e. something that tree-walk.c can parse)
Do you mean each block contains a tree and all its blobs? So the tree
object here, effectively a dir, also contains files in the dir ? In
this way, some blocks can be very big.
No, the tree object contains pathname, mode and SHA-1 of its entries,
one level only (try "git ls-tree HEAD"). If an entry is a directory
and we have not built it yet, we won't have its sha-1, so it will be
zero (similar to invalid cache-tree).
Correct me if I am wrong, I assume:
* Although you only listed attributes in tree block, in index, we have
both tree and blob block.
* Sha1 of a tree block is computed by hashing all the Sha1s of blobs
and sub trees in the directory.
* Like cache tree struct, each tree object contains list of offsets to
children blocks.
How do you store blob blocks ? Is each blob object a block? just like
a tree object is a block? If so, each blob contains a sha1, the
overhead is high?
If we compute hash for a tree, and this tree happen to have 500
children do I have to access all 500 blocks to get their Sha1s?
quoted
quoted
- other index attributes, stored separately in the same order as in
tree object above, uint32_t block offset of subdirectories.
There can be many sub dirs some times. But maybe not a prob.
As tree object and offset of subdirectories are variables, how do you
make a block resizable?
If there are free space right after it, it can be expanded. Otherwise
we need to move the block elsewhere and update its parent about its
new offset, then mark where the block was as free space.
--
Duy
Also I ran some quick test on git-add over kernel 2.6. When I do "time
git add .":time git add .
cmd_add: validate_pathspec takes : 0 ms
read_index_from: xmmap&close takes : 0 ms
read_index_from: verify_hdr takes : 26 ms
read_index_from: create inmem struct takes : 4 ms
read_index: read_index_from takes : 31 ms
read_directory: qsort takes : 0 ms
fill_directory: read_directory takes : 97 ms
cmd_add: prune dir takes : 0 ms
cmd_add: add_files_to_cache takes : 37 ms
cmd_add: add_files takes : 0 ms
real 0m0.172s
user 0m0.120s
sys 0m0.050s
And when I ran "time git add arch/ia64" :
cmd_add: validate_pathspec takes : 0 ms
read_index_from: xmmap&close takes : 0 ms
read_index_from: verify_hdr takes : 20 ms
read_index_from: create inmem struct takes : 4 ms
read_index: read_index_from takes : 25 ms
read_directory: read_directory_recursive takes : 10 ms
read_directory: qsort takes : 0 ms
fill_directory: read_directory takes : 10 ms
cmd_add: fill_directory takes : 10 ms
cmd_add: prune dir takes : 0 ms
cmd_add: add_files_to_cache takes : 1 ms
real 0m0.043s
user 0m0.040s
sys 0m0.000s
In both cases, the time for sha1 is quite stable (~20ms).
fill_directory drops as I specify a sub directory, which make sense.
As Junio suggested, the sha1 time (verify_hdr) is a mix a read and
sha1. And this part is our focus to optimize, isn't it? But, as growth
of the whole repo, the processing time is getting dominated by
fill_directory (if we use '.', it takes 97ms) rather than verify_hdr.
In current system, The time complexity for fill_directory is nlogn (n
is number of objects). git recursively go thru sub directories and
files in it and check against current index. When searching index, it
uses binary search which makes it lg(n). If this is the case, will use
a producer/consumer model help?
Cheers,
Elton
On Mon, Apr 02, 2012 at 09:50:53PM +1000, elton sky wrote:
Hi Nguyen,
Still have some questions on your idea:
On Tuesday, March 27, 2012, Nguyen Thai Ngoc Duy wrote:
quoted
quoted
quoted
A block starts with a signature (a tree block, or an extension...). A
tree block consists of:
- uint32_t tree object's size
- sha-1 of tree object
- crc32 of the rest of the block except tree object
- maybe reference counter of a block can be refered by many blocks??
- tree object (i.e. something that tree-walk.c can parse)
Do you mean each block contains a tree and all its blobs? So the tree
object here, effectively a dir, also contains files in the dir ? In
this way, some blocks can be very big.
No, the tree object contains pathname, mode and SHA-1 of its entries,
one level only (try "git ls-tree HEAD"). If an entry is a directory
and we have not built it yet, we won't have its sha-1, so it will be
zero (similar to invalid cache-tree).
Correct me if I am wrong, I assume:
* Although you only listed attributes in tree block, in index, we have
both tree and blob block.
In current index, tree is implied in path names. We only store blob sha-1.
* Sha1 of a tree block is computed by hashing all the Sha1s of blobs
and sub trees in the directory.
* Like cache tree struct, each tree object contains list of offsets to
children blocks.
How do you store blob blocks ? Is each blob object a block? just like
a tree object is a block? If so, each blob contains a sha1, the
overhead is high?
If we compute hash for a tree, and this tree happen to have 500
children do I have to access all 500 blocks to get their Sha1s?
We don't store blobs in index. We only need their sha-1, which is
computed and content stored in object database at "git add".
By the way, I revised my new index format a little bit, see the end of
this email. It may work, or may not. Food for thoughts.
Also I ran some quick test on git-add over kernel 2.6. When I do "time
git add .":time git add .
cmd_add: validate_pathspec takes : 0 ms
read_index_from: xmmap&close takes : 0 ms
read_index_from: verify_hdr takes : 26 ms
read_index_from: create inmem struct takes : 4 ms
read_index: read_index_from takes : 31 ms
read_directory: qsort takes : 0 ms
fill_directory: read_directory takes : 97 ms
cmd_add: prune dir takes : 0 ms
cmd_add: add_files_to_cache takes : 37 ms
cmd_add: add_files takes : 0 ms
real 0m0.172s
user 0m0.120s
sys 0m0.050s
And when I ran "time git add arch/ia64" :
cmd_add: validate_pathspec takes : 0 ms
read_index_from: xmmap&close takes : 0 ms
read_index_from: verify_hdr takes : 20 ms
read_index_from: create inmem struct takes : 4 ms
read_index: read_index_from takes : 25 ms
read_directory: read_directory_recursive takes : 10 ms
read_directory: qsort takes : 0 ms
fill_directory: read_directory takes : 10 ms
cmd_add: fill_directory takes : 10 ms
cmd_add: prune dir takes : 0 ms
cmd_add: add_files_to_cache takes : 1 ms
real 0m0.043s
user 0m0.040s
sys 0m0.000s
In both cases, the time for sha1 is quite stable (~20ms).
fill_directory drops as I specify a sub directory, which make sense.
As Junio suggested, the sha1 time (verify_hdr) is a mix a read and
sha1. And this part is our focus to optimize, isn't it?
I think so. But until we can read just parts of index, we still have
to verify integrity for the whole index, which takes more or less the
same amount of time you see and should be proportional to index size
(or the number of entries in index). Either we shrink the index, or go
with cheaper checksum, or both.
But, as growth
of the whole repo, the processing time is getting dominated by
fill_directory (if we use '.', it takes 97ms) rather than verify_hdr.
{read,fill}_directory is not always used (for example, "git diff" does
not need it). Meanwhile, as working directory grows, index size grows,
verify_hdr() will take longer.
In current system, The time complexity for fill_directory is nlogn (n
is number of objects). git recursively go thru sub directories and
files in it and check against current index. When searching index, it
uses binary search which makes it lg(n). If this is the case, will use
a producer/consumer model help?
I think fill_directory is dominated by kernel time (read_dir,
stat...), there's little thing we can do there. Anyway I'm pretty sure
fill_directory is out of scope. It's just one of the code that uses
index.
-- 8< --
GIT index format
================
This format replaces the old "DIRC" format. Compared to the old
format, which is essentially a sorted list of pathnames, this one:
- is tree-based
- use crc32 as checksum
- only verify integrity on parts that git accesses, instead of whole
file
- append changes to the end
- allow index versioning
Updates can be made directly to the index by appending to the end. The
index traversed by locating the root tree block from the trailer. When
a path is updated, all related tree blocks are updated and appended to
the end, then a new trailer (with generation increased by one) is
written to conclude the index.
The index size will increase continuously. At some point, we will need
to repack it. Let assume a tree block is 64k on average and a path
generally consists of 3 path components. That means an entry update
adds 192k and we can do about 80 updates before index reaches 16M (in
addition to initial index size).
At 16M or when trailer generation hits a limit (the limit can be
configurable), we rewrite the index to reduce its size. Some heavy
operations can also be used to rewrite index, such as checkout or
reset.
The index integrity is verified by crc32. One crc32 covers header and
trailer. Each block has its own crc32. When the index is found
corrupt, we could try to roll back to latest good version by looking
for trailers from bottom up. Even when the index is not corrupt, users
can still look back this way for older index versions.
= The git index file has the following 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 1.
- 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 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
4-byte checksum:
CRC32 of the header and the trailer (excluding this field)
== Tree block
A tree block contains a (maybe invalid) tree object and extra
information of its companion in working directory. Tree block has
block type 'T'.
Tree block content is basically the list of non-recursive entries in
specified path, with all attributes we store in the index now. There
are a few changes though to intergrate cache-tree and allow
bsearch() on mmap'd block.
A tree block content consists of
- 4-byte tree object size
- 20-byte SHA-1 of the cached tree object
- 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. FIXME: make it 32-bit, relative to the
beginning of the file, so that we can reuse pathnames from other
(old) blocks?
- a list of NUL-terminated pathnames, pointed to from the 16-bit offset
above. This list does not have to be of the same order as the attribute
list. The reason this is separated from the attribute list is to make
attribute list fixed size, searchable using bsearch().
== 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.
-- 8< --
--
Duy
On Mon, Apr 2, 2012 at 08:31, Nguyen Thai Ngoc Duy [off-list ref] wrote:
-- 8< --
GIT index format
================
This format replaces the old "DIRC" format. Compared to the old
format, which is essentially a sorted list of pathnames, this one:
- is tree-based
- use crc32 as checksum
- only verify integrity on parts that git accesses, instead of whole
file
- append changes to the end
- allow index versioning
Updates can be made directly to the index by appending to the end. The
index traversed by locating the root tree block from the trailer. When
a path is updated, all related tree blocks are updated and appended to
the end, then a new trailer (with generation increased by one) is
written to conclude the index.
The index size will increase continuously. At some point, we will need
to repack it. Let assume a tree block is 64k on average and a path
generally consists of 3 path components. That means an entry update
adds 192k and we can do about 80 updates before index reaches 16M (in
addition to initial index size).
Only 3 path components? Java sources can easily have 8-10 with a long
Maven and Java package implied prefix. This will increase the
frequency of rewrites of the index file.
At 16M or when trailer generation hits a limit (the limit can be
configurable), we rewrite the index to reduce its size. Some heavy
operations can also be used to rewrite index, such as checkout or
reset.
The index integrity is verified by crc32. One crc32 covers header and
trailer. Each block has its own crc32. When the index is found
corrupt, we could try to roll back to latest good version by looking
for trailers from bottom up. Even when the index is not corrupt, users
can still look back this way for older index versions.
How do you deal with a partially written append to the index file?
E.g. if a prior update crashes or the filesystem doesn't write
everything out before power failure, you need to find the last good
trailer block in the file.
= The git index file has the following 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 1.
Why not DIRC version 4?
- A number of blocks of variable size
1-byte block type
3-byte content size in byte
block content
So you are limiting the size of a canonical tree now? Currently there
is no limit on the size a tree. But here the entire index structure
plus set of names must be under 16 MiB. Granted no project probably
hits that limit, but you are painting us into a corner with an upper
limit here that doesn't look like it will be easy to increase.
4-byte crc32 of all above
- 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
4-byte checksum:
CRC32 of the header and the trailer (excluding this field)
See above my question about how to find the last good trailer if the
last append attempt was incomplete.
== Tree block
A tree block contains a (maybe invalid) tree object and extra
information of its companion in working directory. Tree block has
block type 'T'.
Tree block content is basically the list of non-recursive entries in
specified path, with all attributes we store in the index now. There
are a few changes though to intergrate cache-tree and allow
bsearch() on mmap'd block.
A tree block content consists of
- 4-byte tree object size
- 20-byte SHA-1 of the cached tree object
- 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. FIXME: make it 32-bit, relative to the
beginning of the file, so that we can reuse pathnames from other
(old) blocks?
16 bit offset doesn't work well in a block that can be as large as 2^24.
If you reuse a path name list at the start of the file, how do you
handle new names?
On Mon, Apr 2, 2012 at 9:27 PM, Shawn Pearce [off-list ref] wrote:
On Mon, Apr 2, 2012 at 08:31, Nguyen Thai Ngoc Duy [off-list ref] wrote:
quoted
The index size will increase continuously. At some point, we will need
to repack it. Let assume a tree block is 64k on average and a path
generally consists of 3 path components. That means an entry update
adds 192k and we can do about 80 updates before index reaches 16M (in
addition to initial index size).
Only 3 path components? Java sources can easily have 8-10 with a long
Maven and Java package implied prefix. This will increase the
frequency of rewrites of the index file.
Yes, but in java case, users could adjust the rewrite limits to make
it less often. The index will be bigger, but because we mmap it and
only access parts of it, index size does not matter much.
quoted
At 16M or when trailer generation hits a limit (the limit can be
configurable), we rewrite the index to reduce its size. Some heavy
operations can also be used to rewrite index, such as checkout or
reset.
The index integrity is verified by crc32. One crc32 covers header and
trailer. Each block has its own crc32. When the index is found
corrupt, we could try to roll back to latest good version by looking
for trailers from bottom up. Even when the index is not corrupt, users
can still look back this way for older index versions.
How do you deal with a partially written append to the index file?
E.g. if a prior update crashes or the filesystem doesn't write
everything out before power failure, you need to find the last good
trailer block in the file.
By looking for the trailer signature "ROOT" from bottom up, then
verify if it's still good (i.e. verifying all trees) from there.
Repeat until we find a good one.
quoted
= The git index file has the following 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 1.
Why not DIRC version 4?
I thought of that, but because I don't keep header format the same as
v3, I thought signature should change too. But this is really not
important at this stage.
quoted
- A number of blocks of variable size
1-byte block type
3-byte content size in byte
block content
So you are limiting the size of a canonical tree now? Currently there
is no limit on the size a tree. But here the entire index structure
plus set of names must be under 16 MiB. Granted no project probably
hits that limit, but you are painting us into a corner with an upper
limit here that doesn't look like it will be easy to increase.
We can introduce a new block type, not a nice approach though. Not
saving block size is probably ok too. We would need something to mark
end-of-block. I wanted to save block size to do crc32 quickly without
parsing the block, but instead, we could make block parsing faster and
not worry about it.
quoted
== Tree block
A tree block contains a (maybe invalid) tree object and extra
information of its companion in working directory. Tree block has
block type 'T'.
Tree block content is basically the list of non-recursive entries in
specified path, with all attributes we store in the index now. There
are a few changes though to intergrate cache-tree and allow
bsearch() on mmap'd block.
A tree block content consists of
- 4-byte tree object size
- 20-byte SHA-1 of the cached tree object
- 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.
...
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?
16 bit offset doesn't work well in a block that can be as large as 2^24.
No it doesn't. That's the implication of using 16-bit offsets.
If you reuse a path name list at the start of the file, how do you
handle new names?
We don't drop this part even if we reuse a few path names elsewhere.
New path names can be put here. But I'm not really sure if reusing
names gains us anything because at least it breaks locality and
complicates handling code. We already save quite a bit by not
duplicating parent prefix.
--
Duy
-- 8< --
GIT index format
================
This format replaces the old "DIRC" format. Compared to the old
format, which is essentially a sorted list of pathnames, this one:
- is tree-based
- use crc32 as checksum
- only verify integrity on parts that git accesses, instead of whole
file
- append changes to the end
- allow index versioning
Updates can be made directly to the index by appending to the end. The
index traversed by locating the root tree block from the trailer. When
a path is updated, all related tree blocks are updated and appended to
the end, then a new trailer (with generation increased by one) is
written to conclude the index.
The index size will increase continuously. At some point, we will need
to repack it. Let assume a tree block is 64k on average and a path
generally consists of 3 path components. That means an entry update
adds 192k and we can do about 80 updates before index reaches 16M (in
addition to initial index size).
At 16M or when trailer generation hits a limit (the limit can be
configurable), we rewrite the index to reduce its size. Some heavy
operations can also be used to rewrite index, such as checkout or
reset.
The index integrity is verified by crc32. One crc32 covers header and
trailer. Each block has its own crc32. When the index is found
corrupt, we could try to roll back to latest good version by looking
for trailers from bottom up. Even when the index is not corrupt, users
can still look back this way for older index versions.
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?
Is the index looks like :
| HEADER | TREE BLOCKS | TRAILER | TREE BLOCKS | TRAILER | TREE
BLOCKS | TRAILER | ...
Blocks and trailers are interleaved. The index starts from a few
blocks (git add file1 file2 file3 ..) and expands as it goes. If file1
is updated, the tree block containing file1 is updated and appended.
(At this point, 2 versions of tree blocks containing file is in index
?) How do you organize these 2 block in a tree ?
Appended blocks are also a tree or just a list. If it's a list, it
needs O(n) read time. If it's like a sub tree, I assume it's small,
because I guess there won't be many changes each time. If it's too
small then lgn -> n, and in total read time -> n.
= The git index file has the following 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 1.
- 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 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
4-byte checksum:
CRC32 of the header and the trailer (excluding this field)
== Tree block
A tree block contains a (maybe invalid) tree object and extra
information of its companion in working directory. Tree block has
block type 'T'.
Tree block content is basically the list of non-recursive entries in
specified path, with all attributes we store in the index now. There
are a few changes though to intergrate cache-tree and allow
bsearch() on mmap'd block.
A tree block content consists of
- 4-byte tree object size
- 20-byte SHA-1 of the cached tree object
- 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. FIXME: make it 32-bit, relative to the
beginning of the file, so that we can reuse pathnames from other
(old) blocks?
It's nice to enable it for bsearch in a block by separate pathname.
If all names are shared by all blocks, this pathname tree will be
loaded for every operation. I guess the load&hash is expensive.
- a list of NUL-terminated pathnames, pointed to from the 16-bit offset
above. This list does not have to be of the same order as the attribute
list. The reason this is separated from the attribute list is to make
attribute list fixed size, searchable using bsearch().
== 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.
-- 8< --
--
Duy
On Wed, Apr 4, 2012 at 3:26 PM, elton sky [off-list ref] 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 | ...
Blocks and trailers are interleaved. The index starts from a few
blocks (git add file1 file2 file3 ..) and expands as it goes. If file1
is updated, the tree block containing file1 is updated and appended.
(At this point, 2 versions of tree blocks containing file is in index
?) How do you organize these 2 block in a tree ?
I leave them where they are. They will be indirectly referenced by two
different roots. At that point we have to new full trees, sharing many
subtrees except the one that contains file1 and its ancestors. This
makes it possible to access an old index version by traversing from an
older trailer. Heavy "add -p" users may like this.
Appended blocks are also a tree or just a list. If it's a list, it
needs O(n) read time. If it's like a sub tree, I assume it's small,
because I guess there won't be many changes each time. If it's too
small then lgn -> n, and in total read time -> n.
It's trees all the way down. I'm not sure why read time is related
here. You read it by traversing from root tree to leaves, no matter
old or new root. Appended trees may push trees farther away and
increase seek time. Other than that, I don't see significant read
performance degradation (really crowded trees may degrade a little bit
because we need to read trees in addition to leaves, but I don't think
it's a big problem).
--
Duy
Hello,
Some updates for Nguyen's index:
On Wed, Apr 4, 2012 at 10:20 PM, Nguyen Thai Ngoc Duy [off-list ref] wrote:
On Wed, Apr 4, 2012 at 3:26 PM, elton sky [off-list ref] wrote:
quoted
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.
quoted
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?
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 [off-list ref] wrote:
Hello,
Some updates for Nguyen's index:
On Wed, Apr 4, 2012 at 10:20 PM, Nguyen Thai Ngoc Duy [off-list ref] wrote:
quoted
On Wed, Apr 4, 2012 at 3:26 PM, elton sky [off-list ref] wrote:
quoted
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.
quoted
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:
quoted
= The git index file has the following format
As is, except there's only one trailer now. And trailer contains list
of free spaces.
quoted
- 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
quoted
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.
quoted
== Tree block
...
Above as is.
- 1 byte version num
- 4 byte offset to previous version block
quoted
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?
- 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 [off-list ref] 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 [off-list ref] wrote:
quoted
Hello,
Some updates for Nguyen's index:
On Wed, Apr 4, 2012 at 10:20 PM, Nguyen Thai Ngoc Duy [off-list ref] wrote:
quoted
On Wed, Apr 4, 2012 at 3:26 PM, elton sky [off-list ref] wrote:
quoted
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.
quoted
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:
quoted
= The git index file has the following format
As is, except there's only one trailer now. And trailer contains list
of free spaces.
quoted
- 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
quoted
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.
quoted
== Tree block
...
Above as is.
- 1 byte version num
- 4 byte offset to previous version block
quoted
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?
.... just realize I have to register and submit my proposal on gsoc
website, rather than here.
I stupidly missed that ...
silly enough..
On Fri, Apr 6, 2012 at 1:15 PM, elton sky [off-list ref] wrote:
NOTE:
Please ignore the
quoted
- 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 [off-list ref] wrote:
quoted
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 [off-list ref] wrote:
quoted
Hello,
Some updates for Nguyen's index:
On Wed, Apr 4, 2012 at 10:20 PM, Nguyen Thai Ngoc Duy [off-list ref] wrote:
quoted
On Wed, Apr 4, 2012 at 3:26 PM, elton sky [off-list ref] wrote:
quoted
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.
quoted
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:
quoted
= The git index file has the following format
As is, except there's only one trailer now. And trailer contains list
of free spaces.
quoted
- 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
quoted
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.
quoted
== Tree block
...
Above as is.
- 1 byte version num
- 4 byte offset to previous version block
quoted
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?