Re: [GSoC] Designing a faster index format

From: Michael Haggerty <mhagger@alum.mit.edu>
Date: Apr 3, 2012, 08:51 UTC
Message-ID: <4F7ABA19.7040408@alum.mit.edu>
In-Reply-To: <1604FE70-8B77-4EC1-823A-DC1F0334CD3A@gmail.com>

On 04/02/2012 11:02 PM, Thomas Gummerer wrote:

Show 19 quoted lines

> 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.

Show 17 quoted lines

> [...]
> - 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/