[jgit-dev] Update on JGit on DHT

[Shawn Pearce <spearce@xxxxxxxxxxx>]

I may be giving up on the concept of putting JGit on a DHT. I just
can't find any DHT that can handle the read traffic caused by the
schema, and a clone request for the linux-2.6 repository (2 million
objects / 400 MB).

What *may* work is putting the standard Git pack file and index file
onto a high-latency "filesystem"... and ensuring the Git process has a
bunch of memory available for caching. I simulated a filesystem with a
1 MB block read latency of 500-2000ms... if the linux-2.6 repository
is fully repacked, and we have ~1 GB of cache, a cold-cache clone can
still run in a matter of minutes. (Compared to the DHT stuff I
submitted before, where it may be 15-30 minutes!)

I am starting to suspect that I made some pretty poor design decisions
with the current DHT schema. The OBJECT_INDEX table is too expensive
to use during clone. The CHUNK table is very complicated to write
(look at the number of lines of code in DhtPackParser and
ChunkFormatter ~ 2000!), and even more complex to read (2055 spread
over 7 classes).


Yesterday I started a new DFS (distributed file system) storage
implementation for JGit. I'll get the files posted soon-ish, but its
essentially an Amazon S3 compatible API for the underlying storage
layer, storing native Git pack and index files. Most of the code is
the local storage provider trimmed down (WindowCache, PackFile,
PackIndex). I implemented my own read-ahead (220 lines of code), as I
assume the underlying storage system has no caching or read-ahead
capability. It turns out this is pretty effective.

I think the major difference between this "DFS" storage code, and the
native local one, is we abstract the entire file IO so it can be
pluggable (e.g. REST-ish HTTP like S3), we don't support loose
objects, and we have to tolerate lower-level limitations like a
writable file cannot seek back and overwrite prior regions (this has
implications for completing a thin pack received over the network).
The "DFS" code also does not try to keep files open while they are
being accessed, it assumes a file handle is actually just a thunk to
construct an HTTP byte-range request on demand. Therefore unlike POSIX
where keeping the file handle open ensures we can always access the
file (even it it was unlinked by a concurrent GC), the "DFS" code has
to make other arrangements to ensure object data is accessible.

The PackIndex code is shared with the local code (yay!), but I had to
duplicate WindowCache and PackFile. So little has changed though that
I may be able to refactor most things into a base class. Unfortunately
we use a lot of package-access methods/members between the PackFile
and its siblings WindowCache and WindowCursor, making it hard to move
WindowCache/PackFile into a common shared package without exposing
internals I don't want to expose.

There are a few other differences that may actually be worth
back-porting to the local file storage code. The "DFS" ObjectReader
looks up objects in the pack index files, then sorts them by pack and
offset before accessing them for things like getObjectSize(Iterable)
and selectObjectRepresentation(). On the local filesystem when data is
<1ms (if in kernel buffer cache) or <20ms (when cold cache), doing the
extra allocations required to presort these doesn't seem useful. But
when you have a 1 MB read latency of 2000ms, its incredibly helpful.
For what's worth, C Git does this sorting step. Their equivalent of
PackWriter (pack-objects.c) has the data structure organized to keep
this pack/offset data inside of the ObjectToPack and can sort the
entire array in-place using quicksort() pretty rapidly.


Anyway... right now I am certainly leaning towards deleting most (if
not all of) the DHT package and trying something else. Especially if
it would be shorter code (currently its 10,000 lines shorter!  5754
for "DFS' vs. 15841 for DHT) and we could share more code. Nearly 2000
lines of DFS's 5754 should be shared with the current local code if I
can allow myself to open up some current internals of WindowCache and
PackFile.

-- 
Shawn.