Re: [GSoC] Designing a faster index format

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.