From: Junio C Hamano <hidden> Date: 2016-06-15 22:53:25
Thomas Gummerer [off-list ref] writes:
After the discussion on IRC and the taking your suggestions into account
I've rewritten my proposal draft as follows.
Just a few comments after a cursory review over the draft.
-- Problem --
The current git index is pretty slow when working with large git repositories,
because the whole index has to be rewritten for nearly every operation. For
example for adding a single file with git add, even though logically only one
single blob sha-1 is changed in the index, git has to recompute the hash over
the whole index and rewrite the index file.
Is it really the time consuming part in the overall picture? Do you have
vital statistics for various pieces to justify that you are solving the
right problem? E.g. (not exhaustive)
- read_index(): overhead to
- validate the checksum of the whole index;
- extract entries into the_index.cache[] array;
- write_index(): overhead to
- serialize entries into the on-disk format;
- compute the checksum over the entire index;
- write the whole index to disk;
- frequency of the above two operations.
I think the current code tries to do the checksumming, in both read and
write directions, in line with the actual I/O operation, not as a separate
phase. You may have to instrument (read: butcher) the current code to
replace the streaming checksum code with no-op to measure the checksum
overhead. In other words, running "time git update-index foo" from the
command line and subtracting "time sha1sum .git/index" would not be a
right way to compute it (it subtracts both disk I/O and checksum
overhead).
Also, optimizing the write codepath by penalizing the read codepath is a
wrong trade-off if the index is read far more often than it is written
during a single day of a developer.
-- Proposed solution --
The proposed solution is to rework the index, using a append-only data
structure. That shall allow for changes to the index in O(k) time, with k being
the number of files that changed. To reach this goal, the first part of the
index will be sorted and changes will always be written to the end, in the order
in which the changes occured. This last part of the index will be merged with
the rest using a heuristic, which will be the execution of git commit and git
status.
To make sure the index isn't corrupted, without calculating the sha-1 hash for
the whole index file every time something is changed.
This is not a sentence. "do Z" in "To do X without Y, do Z" is missing.
The hash is always
calculated for the whole index when merging, but when a file is changed the
sha-1 hash is only calculated for the last entry.
I know this is still a loosely written draft, but "only calculated for the
last entry" is very disturbing. When we say "entry" in the context of
index we always mean a single cache entry, but obviously that is not what
you are using this word for. You mean the last "batch" of entries in a
log structured index file format.
The new batch in the log structured file, if it were to be protected with
the checksum, should take the checksum of the previous part into account
when computing the checksum of the new part, by chaining. Imagine an
index file that was written twice, consisting of parts A and B, in an
append-only fashion. Somewhere in part A (probably near the end but it
does not have to be), there is a checksum to verify part A's consistency.
If the checksum for B is derived solely on the data in B, a bug could
replace the part B with different data C that satisfy its self consistency
check, but when you take A followed by C together, the result may not make
sense. One technique to avoid such mistakes is to use checksum in A and
data in B to compute checksum for B.
This has some cost when
reading the index, but the performance improvements when writing the index
should more then make up for that.
Obviously, "should more than make up" needs substanciation.
... In addition to that it
can also give the index a structure, which in turn makes it easier to search
through.
I do not think you are saying "The current index does not have a structure
so it is hard to search through. Let's give it a structure to make it easy
to search.", but then it becomes unclear what the purpose of saying "give
the index a structure" here. The sentences in this paragraph may need to
be reworked somewhat.
In order to be able to only rewrite a part the way the lock file currently works
has to be changed. Currently the new index is always written into the lock file,
which then is renamed once the writing is complete. Since we now change to an
append only format, if the operation fails, only the last record in the index
is corrupted and we can easily recover by removing the corrupt record.
Careful.
Two processes trying to append to the same index at the same time still
needs to be coordinated via some kind of lock.
When the
is merged the old lock file algorithm will be used.
-ECANNOTPARSE.
To maintain the speed even if a file is already in the index, git will always
append a new record on the end, instead of finding the record in the index and
changing it.
This makes it sound as if you think you can append without reading, but I
do not think that is what you meant. You would need to know what is in the
index to deal with D/F conflicts, so you need to "find" the entry (and
paths related to it) first. The append-only arrangement allows you to
avoid updating in place, which is the plus (i.e. "changing it" part in the
above sentence is valid, "finding" is not).
This will give us a lot of benefit in terms of speed, since
otherwise we would have to search the record (log(n)), change it (1) and update
the sha-1 hash over the whole file (n).
See the comment about on "search the record" part.
Of course the reader suffers because it needs to read more to learn what
the end result of replaying all the log records. The question is by how
much.
Also you would need to worry about the case where an index entry is
removed (your log record needs to be able to express "remove this path").
Backward compatibility will be broken (at least for write) once the in-memory
structure is changed.
That is totally backwards, isn't it?
The in-memory structure can be improved in new implementation without any
compatibility issues as long as the on-disk format is not changed.
Git could still keep compatibility for reading the index
and converting it to the new in-memory format, but keeping write compatibility
would slow down the operation and mess up the code.
The new on-disk format is poorly designed if that has to happen.
-- Timeline --
24/04 - 29/04: Document the new index format.
30/04 - 15/05: Map the current internal structure to the new index format.
That sounds very aggressive, as I am assuming that by Apr 29 you will have
all the data that justifies the "new index format" will solve whatever
problem you are solving and also justifies the "problem" you are solving
is really what we want to solve (e.g. optimizing for writers by penalizing
readers, when readers are predominant, is not solving the right problem).
On Fri, Mar 30, 2012 at 4:06 AM, Junio C Hamano [off-list ref] wrote:
Is it really the time consuming part in the overall picture? Do you have
vital statistics for various pieces to justify that you are solving the
right problem? E.g. (not exhaustive)
- read_index(): overhead to
- validate the checksum of the whole index;
- extract entries into the_index.cache[] array;
- write_index(): overhead to
- serialize entries into the on-disk format;
- compute the checksum over the entire index;
- write the whole index to disk;
- frequency of the above two operations.
Also maybe the frequency of entry updates vs additions/removals. I
suspect refresh operation in some case can update a lot of entries. If
that's the case (and happens often), we may need special treatment for
it because simply appending entries might be costly.
Also, optimizing the write codepath by penalizing the read codepath is a
wrong trade-off if the index is read far more often than it is written
during a single day of a developer.
I suspect so too, but some measurement has to be done there. It'd be
good if you provide a patch to collect index operation statistics.
Some of us can try it on for a few weeks. That would give us a better
picture.
On Thu, Mar 29, 2012 at 10:21 PM, Thomas Gummerer [off-list ref] wrote:
- Tree structure
The advantage of the tree structure over the append-only data structure that was
proposed would be that it would not require any merge or other maintainance work
work after a change of a file. The disadvantage however is that changing a file
would always require log(n) changes to the index, where n is the number of
entries in the index. Another problem might be the integrity check, which would
need either to use a hash over the whole index file or a hash on the tree,
which would however take more time for checking.
I'd say it takes less time for checksuming because we only verify the
trees we read. And tree-based structure allows us to read just a
subdirectory, an advantage for multi-project repositories where people
stay in a subdir most of the time. Shawn suspected crc32 checksum over
a large chunk of data may be insufficient. By hashing tree by tree,
the chunks are significantly shorter, making crc32 viable and cheap
candidate compared to sha-1 (also note that crc32 is used to verify
compressed objects in a pack)
--
Duy
From: Thomas Gummerer <hidden> Date: 2016-06-15 22:53:27
After taking into consideration Junios and Duys comments, and some more
discussion on IRC, I have written a new draft of the proposal. The proposed
solution is based on a tree-structure, as the append only structure penalizes
the read path, which after doing some measurements isn't the right tradeoff.
Included in this proposal are also the index formats that were taken into
consideration but scrapped for one or another reason.
First I'd like to thank all those who helped me by discussing the ideas here
on the mailing list or over at the #git-devel irc channel.
-- Credits --
Big thanks for discussing the ideas with me on IRC goes to charon, jast,
mhagger, shruggar, GitZilla, andrew_sayers and barrbrain. Hope I didn't forget
anyone. Thanks also to those who discussed my ideas with me on the mailing list
(Nguyen Thai Ngoc Duy, Thomas Rast, Junio C Hamano)
And here is the proposal:
Designing a faster index format
-- Problem --
The current git index is pretty slow when working with large git repositories,
because the whole index has to be rewritten for nearly every operation. For
example for adding a single file with git add, even though logically only one
single blob sha-1 is changed in the index, git has to recompute the hash over
the whole index and rewrite the index file. In addition to that the speed up
for writing the index can not come to the expense of the read operation, since
it is executed more often throughout a normal developers day compared to
writing the index. The current index also doesn't allow simple partial reading,
which could help speed up some commands, like git status and git diff, which
often don't need the whole index.
-- Proposed solution --
The proposed solution is to redesign the index to a B-tree based format. This
allows changes to the index in O(log(n)) time, with n being the number of
entries in the index.
The sha1 hash, to verify the index isn't corrupted, will have to be computed
over log(s) data in the worst case, where s is the size of the index, which
will be bigger then the number of entries because of the structure of the
b-tree.
The new index format will also save on the size of each entry, by storing each
path only once, and using it for all files in the same path. This will reduce
the amount of data we have to calculate the hash over, when both reading and
writing the index, thus having faster operations especially on repositories
with deep directory structures.
The tree structure will also allow for fast partial loading of the index. Since
every bucket of the tree will have it's own hash, the hash will only need to be
calculated for the parts we load. This reduces the amount of data for which the
hash will need to be calculated. Commands like git status and git diff will
benefit from this. The benefit could be fully explored by a implementation with
inotify, of which Thomas Rast created a POC.
(https://github.com/trast/git/commit/6c9825fdca76d01fb5a83923558831743ae477bc)
In order to be able to only rewrite the parts of the index that really changed,
the current lock file structure will have to be changed. The new lock file
will keep a journal of the changes, to be able to recover in case of a crash.
Deleting the lockfile "commits" the changes.
The in-memory structure will be modified in two steps. In the first step it
will only be modified to keep track of the changes, in order to be able to only
write the changes to disk and eliminate the need to rewrite the whole tree. In
the second step the in-memory structure will be changed to reflect the tree
format, getting the full benefits from the new format.
To ensure backward compatibility, git shall keep the ability to read version
2/3 of the index. The user shall also have the possibility to configure git to
write the index in either the new or the old format. While this will produce
some code overhead, it will make the life of git users which don't use core git
exclusively easier in the transition phase. If the user sets the write format to
the new format and the repository is a already existing version 2/3 repository,
the old index will be transformed to the new format. Transformations in the
other direction will also be possible, since the in-memory format is the same.
Once the in-memory structure is changed, making git backward compatible will
still be possible, even though it will come at the expense of the
reading/writing time of the old index, since the tree will have to be
constructed in memory from the on disk format, and transformed back to the flat
format when writing it back to disk.
To make the project feasible for Google Summer of Code the in-meory structure
will only be modified to keep track of the changes, not making it
tree-structured yet and the partial loading will not be implemented.
-- Solutions that were also considered --
These solutions will not be described in as much detail as the tree-structure,
but they were also considered in the process of chosing the best index format
and will be described below.
- Append-only data structure
An append-only data structure will allow for changes to the index in O(k) time,
with k being the number of files that changed. To reach this goal, the first
part of the index will be sorted and changes will always be written to the end,
in the order in which the changes occured. This last part of the index will be
merged with the rest using a heuristic, which will be the execution of git
commit and git status.
To make sure the index isn't corrupted, without calculating the sha1 hash for
the whole index file every time something is changed, the hash is always
calculated for the whole index when merging, but when only a single entry is
changed the sha-1 hash is only calculated for the last change. This will
increase the cost for reading the index to log(n) + k * log(k) where n is the
number of entries in the sorted part of the index and k is the number of entries
in the unsorted part of the index, which will have to be merged with the rest
of the index.
The index format shall also save on file size, by storing the paths only once,
which currently are stored for every file. This can make a big difference
especially for repositories with deep directory structures. (e.g. in the webkit
repository this change can save about 10MB on the index). In addition to that it
can also give the index a structure, which in turn makes it easier to search
through. Except for the appended part, but that should never grow big enough to
make a linear search through it costly.
With this index format the lock file could be a simple empty file, since if a
operation fails, only the last entry would be corrupted making it easy to
recover.
The current in-memory structure of git would only have to be slightly changed,
adding a flag or keeping a list of the changed files. The rest of it could be
changed in an other step, to better represent the new structure of the index.
To ensure backward compatibility, git shall keep the ability able to read
version 2/3 of the index. The user shall also have the possibility to configure
git to write the index in either the new or the old format. While this will
produce some code overhead, it will make the life of git users which don't use
core git exclusively easier in the transition phase. If the user sets the write
format to the new format and the repository is a already existing version 2/3
repository, the old index will be transformed to the new format.
This idea was dropped, because as mentioned in the problem description reads
are more common then writes and therefore trading write speed for read speed
is not a good tradeoff.
- Database format
A database format as index structure will allow for changes to the index in
O(log(n)) time for a single change, with n always being the number of entries
in the index, assuming a b-tree index on the path in the database.
The check for the index corruption could be left to the database, which would
have about the same cost as the check in the tree-structure, in the read and
write direction. Partial loading with the right indices would also have the
same cost as the tree-structure, by executing a simple select query.
The drawback of this solution however would be the introduction of a database
library (one could also write one, but that certainly would be overkill).
Another drawback would be that it's harder to read for programs like libgit2
and jgit and the codebase certainly wouldn't get any cleaner.
- Padded structure
Another index format that was taken into consideration was to create a padded
structure. Basically that would be an append-only like structure, but split into
sections, where every section would leave some space at the end for appending
changes. This would leave us with a complexity of O(k) where k is the number of
sections.
This structure will bring advantages for faster partial loading, when splitting
the sections in the right way.
The structure was however only briefly taken into consideration, since it would
have close to no advantages (except for the partial loading) compared to the
append-only structure, would make the index file larger due to the spaces for
appending and have the same drawbacks as the append-only structure.
-- Timeline --
24/04 - 01/05: Document the new index format.
02/05 - 21/05: Map the current internal structure to the new index format.
22/05 - 07/06: Change the current in-memory structure to keep track of the
changed files.
08/06 - 16/06: Write the index to disk in both the old and the new format
depending on the choice of the user and make sure only the changed parts are
really written to disk in the new format.
17/06 - 21/07: Parse the index from disk to the current in-memory format.
/* Development work will be a bit slower from 18/06 to 21/07 because at my
* University there are exams in this period. I probably will only be able to
* work half the hours. I'll be back up to full speed after that. */
22/07 - 10/08: Read the new structure and map it to the current in meory format.
Make sure the old format still gets read correctly.
11/08 - 13/08: Test the new index and profile the gains compared to the old
format.
-- Why git --
I'm using git since about 2-3 years and wanted to contribute to it earlier, but
couldn't find the time to do it. I would also like to continue contributing
once the Summer of Code is over.
-- About me --
I'm Thomas Gummerer (@tgummerer on Twitter, tgummerer on IRC), 21 years old
from Italy. I'm currently a 3rd year Bachelor student in Applied Computer
Science at the Free University of Bolzano. I started programming in High School
about 8 years ago with Pascal and then learned C and Java. For some of my
projects you can visit my homepage (http://tgummerer.com/projects), most of them
were for university and some personal projects I did in my free time. My blog is
also on the same homepage, but not really active. Unfortunately I couldn't yet
participate in any bigger open source project, although I'm interested in
it basically since I started programming.
From: Michael Haggerty <hidden> Date: 2016-06-15 22:53:27
On 04/02/2012 11:02 PM, Thomas Gummerer wrote:
And here is the proposal:
Designing a faster index format
-- Problem --
The current git index is pretty slow when working with large git repositories,
because the whole index has to be rewritten for nearly every operation. For
example for adding a single file with git add, even though logically only one
single blob sha-1 is changed in the index, git has to recompute the hash over
the whole index and rewrite the index file. In addition to that the speed up
for writing the index can not come to the expense of the read operation, since
it is executed more often throughout a normal developers day compared to
writing the index. The current index also doesn't allow simple partial reading,
which could help speed up some commands, like git status and git diff, which
often don't need the whole index.
-- Proposed solution --
The proposed solution is to redesign the index to a B-tree based format. This
allows changes to the index in O(log(n)) time, with n being the number of
entries in the index.
I thought that the index lock currently only blocks writers, not readers
(am I wrong?). So given that you want to be able to mutate the index
file without rewriting the whole file, it seems to me that you have to
pick from one of these alternatives:
1. Change the locking semantics so that readers also block when the file
is locked. This choice would have some important consequences: (a)
readers will also have to obtain a lock before starting to read. (b) to
avoid deadlock, it will become crucial that the lock is never held
across the execution of any other git (sub-)commands that might want to
read the index.
2. Implement a file format that can be read even while it is being
mutated. If so, please explain the data file format in more detail; in
particular, how do you plan to mutate the file in a way that does not
disturb readers? How do you plan to read the whole index efficiently (I
imagine that reading the whole index will remain a frequent operation)?
I encourage you to include an analysis of the number of disk seeks when
you are analyzing the cost of read/write operations on the index. This
will have a strong effect on the time for working with the index when
the disk cache is cold. The current index requires O(1) seeks for
reading and writing, which I believe is a big part of the reason that
the current read-the-whole-index/write-the-whole-index design performs
excellently despite the amount of data that it is touching.
[...]
- Append-only data structure
An append-only data structure will allow for changes to the index in O(k) time,
with k being the number of files that changed. To reach this goal, the first
part of the index will be sorted and changes will always be written to the end,
in the order in which the changes occured. This last part of the index will be
merged with the rest using a heuristic, which will be the execution of git
commit and git status.
To make sure the index isn't corrupted, without calculating the sha1 hash for
the whole index file every time something is changed, the hash is always
calculated for the whole index when merging, but when only a single entry is
changed the sha-1 hash is only calculated for the last change. This will
increase the cost for reading the index to log(n) + k * log(k) where n is the
number of entries in the sorted part of the index and k is the number of entries
in the unsorted part of the index, which will have to be merged with the rest
of the index.
I don't understand this analysis of the reading time. I suppose you are
assuming that you want to read the status of a single file. But in that
case, it is enough to find the entry in the old index (O(log(n))
assuming some sort of tree structure) plus do a linear scan through the
unsorted entries (i.e., O(k), not O(k log(k))).
[...]
This [append-only] idea was dropped, because as mentioned in the problem description reads
are more common then writes and therefore trading write speed for read speed
is not a good tradeoff.
The amount of read speed that would have to be sacrificed depends on the
size of k and n. Under the assumption that k << n, the read speed of an
append-only index file format (with periodic compaction) would be close
to optimal. For the append-only format, k is the number of files that
have been changed since the index was last rewritten (including
duplicates if a file has been changed more than once). Supposing that
the index is compacted on branch changes and "occasionally" when k grows
too large, I have the feeling that k will typically be quite small in
comparison to n, especially in the huge repositories that need this
optimization.
Remember that a full index rewrite/compaction will only take as long as
it currently takes for *any* change to the index (which is not *that*
terrible). It would also be easy to estimate the size of k and n on
every operation. Therefore, if an operation is expected to force a
large fraction of index file entries to be invalidated, it is OK for it
to force an index compaction to keep subsequent read operations fast.
And even if, once in a blue moon, somebody changes *all* of the files in
his huge repository while somehow evading compaction, the time to read
the full index would still only be a factor of two slower than the
current design. (Granted, the time to read a single entry in this
scenario would be much longer than the log(n) that would be possible
given a pure-tree-based design.)
Michael
--
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/
On Tue, Apr 3, 2012 at 3:51 PM, Michael Haggerty [off-list ref] wrote:
quoted
-- Proposed solution --
The proposed solution is to redesign the index to a B-tree based format. This
allows changes to the index in O(log(n)) time, with n being the number of
entries in the index.
I thought that the index lock currently only blocks writers, not readers
(am I wrong?).
I think you are right.
So given that you want to be able to mutate the index
file without rewriting the whole file, it seems to me that you have to
pick from one of these alternatives:
1. Change the locking semantics so that readers also block when the file
is locked. This choice would have some important consequences: (a)
readers will also have to obtain a lock before starting to read. (b) to
avoid deadlock, it will become crucial that the lock is never held
across the execution of any other git (sub-)commands that might want to
read the index.
2. Implement a file format that can be read even while it is being
mutated. If so, please explain the data file format in more detail; in
particular, how do you plan to mutate the file in a way that does not
disturb readers? How do you plan to read the whole index efficiently (I
imagine that reading the whole index will remain a frequent operation)?
Copy-on-write B-trees, aka btrfs. Does anybody like to go that route ;)
I encourage you to include an analysis of the number of disk seeks when
you are analyzing the cost of read/write operations on the index. This
will have a strong effect on the time for working with the index when
the disk cache is cold. The current index requires O(1) seeks for
reading and writing, which I believe is a big part of the reason that
the current read-the-whole-index/write-the-whole-index design performs
excellently despite the amount of data that it is touching.
From: Thomas Gummerer <hidden> Date: 2016-06-15 22:53:27
On Apr 3, 2012, at 10:51 AM, Michael Haggerty wrote:
On 04/02/2012 11:02 PM, Thomas Gummerer wrote:
quoted
And here is the proposal:
Designing a faster index format
-- Problem --
The current git index is pretty slow when working with large git repositories,
because the whole index has to be rewritten for nearly every operation. For
example for adding a single file with git add, even though logically only one
single blob sha-1 is changed in the index, git has to recompute the hash over
the whole index and rewrite the index file. In addition to that the speed up
for writing the index can not come to the expense of the read operation, since
it is executed more often throughout a normal developers day compared to
writing the index. The current index also doesn't allow simple partial reading,
which could help speed up some commands, like git status and git diff, which
often don't need the whole index.
-- Proposed solution --
The proposed solution is to redesign the index to a B-tree based format. This
allows changes to the index in O(log(n)) time, with n being the number of
entries in the index.
I thought that the index lock currently only blocks writers, not readers
(am I wrong?). So given that you want to be able to mutate the index
file without rewriting the whole file, it seems to me that you have to
pick from one of these alternatives:
1. Change the locking semantics so that readers also block when the file
is locked. This choice would have some important consequences: (a)
readers will also have to obtain a lock before starting to read. (b) to
avoid deadlock, it will become crucial that the lock is never held
across the execution of any other git (sub-)commands that might want to
read the index.
2. Implement a file format that can be read even while it is being
mutated. If so, please explain the data file format in more detail; in
particular, how do you plan to mutate the file in a way that does not
disturb readers? How do you plan to read the whole index efficiently (I
imagine that reading the whole index will remain a frequent operation)?
Did not think about this first, but I will use the first alternative. The most
important thing about this project is the speed and it will be best kept with
the first alternative. I am thinking about two different kind of locks, the read
lock, which blocks writing, but not other reading processes and a write lock,
which will block both other processes to read and write.
I encourage you to include an analysis of the number of disk seeks when
you are analyzing the cost of read/write operations on the index. This
will have a strong effect on the time for working with the index when
the disk cache is cold. The current index requires O(1) seeks for
reading and writing, which I believe is a big part of the reason that
the current read-the-whole-index/write-the-whole-index design performs
excellently despite the amount of data that it is touching.
Seeking took: 429430 (cold)
Reading took: 581 (hot)
Reading took: 1031357 (cold)
Reading took: 53850 (hot)
Writing took: 524909
This is just from a short test program I wrote. Just reads the index, and seeks
over it (obviously not directly one after another but in different scripts). The
writing time is for writing the index that was read back to disk. And this is with
a highly exaggerated number of seeks (1000).
Also to take into consideration is that the disk cache will (nearly) never be
cold since git always reads the index first.
quoted
[...]
- Append-only data structure
An append-only data structure will allow for changes to the index in O(k) time,
with k being the number of files that changed. To reach this goal, the first
part of the index will be sorted and changes will always be written to the end,
in the order in which the changes occured. This last part of the index will be
merged with the rest using a heuristic, which will be the execution of git
commit and git status.
To make sure the index isn't corrupted, without calculating the sha1 hash for
the whole index file every time something is changed, the hash is always
calculated for the whole index when merging, but when only a single entry is
changed the sha-1 hash is only calculated for the last change. This will
increase the cost for reading the index to log(n) + k * log(k) where n is the
number of entries in the sorted part of the index and k is the number of entries
in the unsorted part of the index, which will have to be merged with the rest
of the index.
I don't understand this analysis of the reading time. I suppose you are
assuming that you want to read the status of a single file. But in that
case, it is enough to find the entry in the old index (O(log(n))
assuming some sort of tree structure) plus do a linear scan through the
unsorted entries (i.e., O(k), not O(k log(k))).
The current way git operates it always reads the whole index, making it necessary
to merge the unsorted entries with the sorted part. Thinking about it it would even
be O(k log(n)), because the appended part is unsorted.
O(log(n)) + O(k) would be the complexity for loading only a single entry from the
index.
quoted
[...]
This [append-only] idea was dropped, because as mentioned in the problem description reads
are more common then writes and therefore trading write speed for read speed
is not a good tradeoff.
The amount of read speed that would have to be sacrificed depends on the
size of k and n. Under the assumption that k << n, the read speed of an
append-only index file format (with periodic compaction) would be close
to optimal. For the append-only format, k is the number of files that
have been changed since the index was last rewritten (including
duplicates if a file has been changed more than once). Supposing that
the index is compacted on branch changes and "occasionally" when k grows
too large, I have the feeling that k will typically be quite small in
comparison to n, especially in the huge repositories that need this
optimization.
Remember that a full index rewrite/compaction will only take as long as
it currently takes for *any* change to the index (which is not *that*
terrible). It would also be easy to estimate the size of k and n on
every operation. Therefore, if an operation is expected to force a
large fraction of index file entries to be invalidated, it is OK for it
to force an index compaction to keep subsequent read operations fast.
And even if, once in a blue moon, somebody changes *all* of the files in
his huge repository while somehow evading compaction, the time to read
the full index would still only be a factor of two slower than the
current design. (Granted, the time to read a single entry in this
scenario would be much longer than the log(n) that would be possible
given a pure-tree-based design.)
Lets take another scenario. Someone changes a lot of files and then executes
some commands which would usually only read the index. In that case either you
would need the load time (O(n)) plus the time for merging (O(k*log(n)), as
described above plus the time for writing the index (O(n)) which usually wouldn't
be necessary.
In addition to that it would also be more complicated and slower to realize
the partial loading, which would be beneficial to a lot of commands. Taking that
into account the tree-based structure will be more future proof, and faster (if
there are enough changes in a repository) then the append-only structure.
Lets take another scenario. Someone changes a lot of files and then executes
some commands which would usually only read the index. In that case either you
would need the load time (O(n)) plus the time for merging (O(k*log(n)), as
described above plus the time for writing the index (O(n)) which usually wouldn't
be necessary.
note that in a large repository you are not that likely to change a very
large percentage of the files with one update. yes, there are some use
cases where this happens, but in general, the number of files changed in a
changeset grows at a much slower rate than the total number of files in a
repository. As projects get big they tend to get fewer across-the-board
changes.
David Lang
From: Thomas Gummerer <hidden> Date: 2016-06-15 22:53:28
This is another small revision of my proposal draft, taking into consideration
Michael Haggerty and David Langs comments.
First I would again like to mention the people which helped me discussing the
ideas and gave me valuable input.
-- Credits --
Big thanks for discussing the ideas with me on IRC goes to charon, jast,
mhagger, shruggar, GitZilla, andrew_sayers and barrbrain. Hope I didn't forget
anyone. Thanks also to those who discussed my ideas with me on the mailing list
(Nguyen Thai Ngoc Duy, Thomas Rast, Junio C Hamano, Michael Haggerty,
David Lang)
Designing a faster index format
-- Problem --
The current git index is pretty slow when working with large git repositories,
because the whole index has to be rewritten for nearly every operation. For
example for adding a single file with git add, even though logically only one
single blob sha-1 is changed in the index, git has to recompute the hash over
the whole index and rewrite the index file. In addition to that the speed up
for writing the index can not come to the expense of the read operation, since
it is executed more often throughout a normal developers day compared to
writing the index. The current index also doesn't allow simple partial reading,
which could help speed up some commands, like git status and git diff, which
often don't need the whole index.
-- Proposed solution --
The proposed solution is to redesign the index to a B-tree based format. This
allows changes to the index in O(log(n)) time, with n being the number of
entries in the index.
The sha1 hash, to verify the index isn't corrupted, will have to be computed
over log(s) data in the worst case, where s is the size of the index, which
will be bigger then the number of entries because of the structure of the
b-tree.
The new index format will also save on the size of each entry, by storing each
path only once, and using it for all files in the same path. This will reduce
the amount of data we have to calculate the hash over, when both reading and
writing the index, thus having faster operations especially on repositories
with deep directory structures.
The tree structure will also allow for fast partial loading of the index. Since
every bucket of the tree will have it's own hash, the hash will only need to be
calculated for the parts we load. This reduces the amount of data for which the
hash will need to be calculated. Commands like git status and git diff will
benefit from this. The benefit could be fully explored by a implementation with
inotify, of which Thomas Rast created a POC.
(https://github.com/trast/git/commit/6c9825fdca76d01fb5a83923558831743ae477bc)
In order to be able to only rewrite the parts of the index that really changed,
the current lock file structure will have to be changed. The new lock file
will keep a journal of the changes, to be able to recover in case of a crash.
Deleting the lockfile "commits" the changes. To ensure that the readers never
read a partially mutated file, reading the index will respect the write lock.
Readers will also have a "read lock", which is respected by operations that
write on the index, but can be ignored by operations that read the index, such
that simultaneous reads are still possible.
The in-memory structure will be modified in two steps. In the first step it
will only be modified to keep track of the changes, in order to be able to only
write the changes to disk and eliminate the need to rewrite the whole tree. In
the second step the in-memory structure will be changed to reflect the tree
format, getting the full benefits from the new format.
To ensure backward compatibility, git shall keep the ability to read version
2/3 of the index. The user shall also have the possibility to configure git to
write the index in either the new or the old format. While this will produce
some code overhead, it will make the life of git users which don't use core git
exclusively easier in the transition phase. If the user sets the write format to
the new format and the repository is a already existing version 2/3 repository,
the old index will be transformed to the new format. Transformations in the
other direction will also be possible, since the in-memory format is the same.
Once the in-memory structure is changed, making git backward compatible will
still be possible, even though it will come at the expense of the
reading/writing time of the old index, since the tree will have to be
constructed in memory from the on disk format, and transformed back to the flat
format when writing it back to disk.
To make the project feasible for Google Summer of Code the in-meory structure
will only be modified to keep track of the changes, not making it
tree-structured yet and the partial loading will not be implemented.
-- Solutions that were also considered --
These solutions will not be described in as much detail as the tree-structure,
but they were also considered in the process of chosing the best index format
and will be described below.
- Append-only data structure
An append-only data structure will allow for changes to the index in O(k) time,
with k being the number of files that changed. To reach this goal, the first
part of the index will be sorted and changes will always be written to the end,
in the order in which the changes occured. This last part of the index will be
merged with the rest using a heuristic, which will be the execution of git
commit and git status.
To make sure the index isn't corrupted, without calculating the sha1 hash for
the whole index file every time something is changed, the hash is always
calculated for the whole index when merging, but when only a single entry is
changed the sha-1 hash is only calculated for the last change. This will
increase the cost for reading the index to log(n) + k * log(n) where n is the
number of entries in the sorted part of the index and k is the number of entries
in the unsorted part of the index, which will have to be merged with the rest
of the index.
The index format shall also save on file size, by storing the paths only once,
which currently are stored for every file. This can make a big difference
especially for repositories with deep directory structures. (e.g. in the webkit
repository this change can save about 10MB on the index). In addition to that it
can also give the index a structure, which in turn makes it easier to search
through. Except for the appended part, but that should never grow big enough to
make a linear search through it costly.
With this index format the lock file could be a simple empty file, since if a
operation fails, only the last entry would be corrupted making it easy to
recover.
The current in-memory structure of git would only have to be slightly changed,
adding a flag or keeping a list of the changed files. The rest of it could be
changed in an other step, to better represent the new structure of the index.
To ensure backward compatibility, git shall keep the ability able to read
version 2/3 of the index. The user shall also have the possibility to configure
git to write the index in either the new or the old format. While this will
produce some code overhead, it will make the life of git users which don't use
core git exclusively easier in the transition phase. If the user sets the write
format to the new format and the repository is a already existing version 2/3
repository, the old index will be transformed to the new format.
This idea was dropped, because as mentioned in the problem description reads
are more common then writes and therefore trading write speed for read speed
is not a good tradeoff. The slowdown depends mostly on the size of the appended
(unsorted) part, which in most cases will be much less then the size of the
sorted part, but in other cases might grow quite big. I think it is preferrable
to have a structure that is usually faster on the read operation and where the
read speed will not depend on the way the user works. This is worth the slight
trade-off in write speed. In addition to that the tree-structure will also allow
faster partial loading, which makes it more future-proof.
- Database format
A database format as index structure will allow for changes to the index in
O(log(n)) time for a single change, with n always being the number of entries
in the index, assuming a b-tree index on the path in the database.
The check for the index corruption could be left to the database, which would
have about the same cost as the check in the tree-structure, in the read and
write direction. Partial loading with the right indices would also have the
same cost as the tree-structure, by executing a simple select query.
The drawback of this solution however would be the introduction of a database
library (one could also write one, but that certainly would be overkill).
Another drawback would be that it's harder to read for programs like libgit2
and jgit and the codebase certainly wouldn't get any cleaner.
- Padded structure
Another index format that was taken into consideration was to create a padded
structure. Basically that would be an append-only like structure, but split into
sections, where every section would leave some space at the end for appending
changes. This would leave us with a complexity of O(k) where k is the number of
sections.
This structure will bring advantages for faster partial loading, when splitting
the sections in the right way.
The structure was however only briefly taken into consideration, since it would
have close to no advantages (except for the partial loading) compared to the
append-only structure, would make the index file larger due to the spaces for
appending and have the same drawbacks as the append-only structure.
-- Timeline --
24/04 - 01/05: Document the new index format.
02/05 - 21/05: Map the current internal structure to the new index format.
22/05 - 07/06: Change the current in-memory structure to keep track of the
changed files.
08/06 - 16/06: Write the index to disk in both the old and the new format
depending on the choice of the user and make sure only the changed parts are
really written to disk in the new format.
17/06 - 21/07: Parse the index from disk to the current in-memory format.
/* Development work will be a bit slower from 18/06 to 21/07 because at my
* University there are exams in this period. I probably will only be able to
* work half the hours. I'll be back up to full speed after that. */
22/07 - 10/08: Read the new structure and map it to the current in meory format.
Make sure the old format still gets read correctly.
11/08 - 13/08: Test the new index and profile the gains compared to the old
format.
-- Why git --
I'm using git since about 2-3 years and wanted to contribute to it earlier, but
couldn't find the time to do it. I would also like to continue contributing
once the Summer of Code is over.
-- About me --
I'm Thomas Gummerer (@tgummerer on Twitter, tgummerer on IRC), 21 years old
from Italy. I'm currently a 3rd year Bachelor student in Applied Computer
Science at the Free University of Bolzano. I started programming in High School
about 8 years ago with Pascal and then learned C and Java. For some of my
projects you can visit my homepage (http://tgummerer.com/projects), most of them
were for university and some personal projects I did in my free time. My blog is
also on the same homepage, but not really active. Unfortunately I couldn't yet
participate in any bigger open source project, although I'm interested in
it basically since I started programming.
From: Michael Haggerty <hidden> Date: 2016-06-15 22:53:28
On 04/03/2012 09:07 PM, Thomas Gummerer wrote:
On Apr 3, 2012, at 10:51 AM, Michael Haggerty wrote:
quoted
On 04/02/2012 11:02 PM, Thomas Gummerer wrote:
quoted
- Append-only data structure
[...]
To make sure the index isn't corrupted, without calculating the sha1 hash for
the whole index file every time something is changed, the hash is always
calculated for the whole index when merging, but when only a single entry is
changed the sha-1 hash is only calculated for the last change. This will
increase the cost for reading the index to log(n) + k * log(k) where n is the
number of entries in the sorted part of the index and k is the number of entries
in the unsorted part of the index, which will have to be merged with the rest
of the index.
I don't understand this analysis of the reading time. I suppose you are
assuming that you want to read the status of a single file. But in that
case, it is enough to find the entry in the old index (O(log(n))
assuming some sort of tree structure) plus do a linear scan through the
unsorted entries (i.e., O(k), not O(k log(k))).
The current way git operates it always reads the whole index, making it necessary
to merge the unsorted entries with the sorted part. Thinking about it it would even
be O(k log(n)), because the appended part is unsorted.
O(log(n)) + O(k) would be the complexity for loading only a single entry from the
index.
I was confused because in your original mail you seemed to claim that
reading the whole sorted part of the index scales like O(log(n)), where
it certainly scales at least like O(n).
To read the whole index if using an append-only data structure, I would
do the following:
1. Read the file header to find where the addenda begin: one seek plus O(1).
2. Read the addenda in order (I assume each addendum to be sorted on
disk), and merge-sort the addenda together, discarding the earlier of
any duplicates: one seek plus O(k) I/O plus O(k log k) computation (this
is the worst case, if each addendum contains a single file).
3. Read the sorted part of the file in order, while merging it together
with the combined addenda: one seek plus O(n) I/O plus O(n + k) computation.
Total: 3 seeks plus O(n+k) I/O plus O(n + k log(k)) computation.
Whereas for a B-tree, it is hard to estimate the complexity because you
have provided very little detail about how you want to lay the data
structure out on disk. But presumably the number of seeks will be
significantly larger. And if you are not careful, the number of seeks
will approach the number of nodes in the index O(n) or perhaps the
number of added nodes (not files!) which could go something like O(k
log(k)).
Michael
--
Michael Haggerty
mhagger@alum.mit.edu
http://softwareswirl.blogspot.com/
-- Proposed solution --
The proposed solution is to redesign the index to a B-tree based format. This
allows changes to the index in O(log(n)) time, with n being the number of
entries in the index.