On Tue, Feb 11, 2014 at 11:29 AM, Junio C Hamano <gits...@pobox.com> wrote:
> Shawn Pearce <spea...@spearce.org> writes:
>> Why would you do this? Perhaps you need more time in your day
>> to consume tea or coffee. Set GIT_RTT and enjoy a beverage.
> So the conclusion is that it is not practical to do a lazy fetch if
> it is done extremely naively at "we want this object --- wait a bit
> and we'll give you" level?

Yes, this is what I thought when someone proposed this hack in
sha1_file.c to me on Monday. So I ran a quick experiment to see if my
instinct was right.

> I am wondering if we can do a bit better, like "we want this object
> --- wait a bit, ah that's a commit, so it is likely that you may
> want the trees and blobs associated with it, too, if not right now
> but in a near future, let me push a pack that holds them to you"?

Ah, smart observation. That might work. However I doubt it.

I implemented a version of Git on top of Google Bigtable (and Apache
HBase and Apache Cassandra) multiple times using JGit. tl;dr: this
approach doesn't work in practice.

The naive implementation for these distributed NoSQL systems is to
store each object in its own row keyed by SHA-1, and lookup the object
when you want it. This is very slow and is more or less what this
stupid patch shows. Worse, none of them were able to even get close to
the 1ms latency I used in this example.

In another implementation (which I published into JGit as the "DHT"
backend) I stored a group of related commits together in a row. Row
target sizes were in the 1-2 MiB range when using pack style
compression for commits, so the average row held hundreds of commits.
Reading one commit would actually slurp back a number of related
commits. The idea was if we need commit A now we will need B, C, D, E
(its parents and ancestors) soon as the application walks the revision
history, like rev-list or pack-objects.

For a process like pack-objects this almost seems to work. If commits
are together we can slurp a group at a time to amortize the round trip
latency. Unfortunately the application can still go through hundreds
of commits faster than the real world RTT is. So I tried to fix this
by storing an extra metadata pointer in each row to identify the next
row, so next block of commits could start loading right away. Its
still slow, as the application can scan through data faster than the

At least for pack generation the traversal code does commits and
builds up a list of all root trees. The root trees can be async loaded
in batches, but the depth first traversal is still a killer. There are
stalls while the application waits for the next subtree, even if you
cluster the trees also into groups using depth first traversal the way
the packer produces pack files today.

Junio's idea to cluster data by commit and its related trees and blobs
is just a different data organization. It may be necessary to make two
copies of the data, one clustered by commits and another by
commit+tree+blob to satisfy different access patterns. And in the
commit+tree+blob case you may need multiple redundant copies of blobs
near commits that use them if those commits are frequently accessed.
Its a lot of redundant disk space.

We always say disk is cheap, but disk is slow and not getting faster.
SSDs are helping, but SSDs are expensive and have size limitations
compared to spinning disk. Just making many copies of data isn't
necessarily a solution.
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Reply via email to