Re: RFC/Pull Request: Refs db backend

On Mon, Jun 22, 2015 at 08:50:56PM -0400, David Turner wrote:

Neat.

Can you describe a bit more about the reflog handling?

One of the problems we've had with large-ref repos is that the reflog storage is quite inefficient. You can pack all the refs, but you may still be stuck with a bunch of reflog files with one entry, wasting a whole inode. Doing a "git repack" when you have a million of those has horrible cold-cache performance. Basically anything that isn't one-file-per-reflog would be a welcome change. :)

It has also been a dream of mine to stop tying the reflogs specifically to the refs. I.e., have a spot for reflogs of branches that no longer exist, which allows us to retain them for deleted branches. Then you can possibly recover from a branch deletion, whereas now you have to dig through "git fsck"'s dangling output. And the reflog, if you don't expire it, becomes a suitable audit log to find out what happened to each branch when (whereas now it is full of holes when things get deleted).

Does your solution handle something like that?

I was thinking of actually moving to a log-structured ref storage. Something like:

  - any ref write puts a line at the end of a single logfile that
    contains the ref name, along with the normal reflog data

  - the logfile is the source of truth for the ref state. If you want to
    know the value of any ref, you can read it backwards to find the
    last entry for the ref. Everything else is an optimization.

    Let's call the number of refs N, and the number of ref updates in
    the log U.

  - we keep a key/value index mapping the name of any branch that exists
    to the byte offset of its entry in the logfile. This would probably
    be in some binary key/value store (like LMDB). Without this,
    resolving a ref is O(U), which is horrible. With it, it should be
    O(1) or O(lg N), depending on the index data structure.

  - the index can also contain other optimizations. E.g., rather than
    point to the entry in the logfile, it can include the sha1 directly
    (to avoid an extra level of indirection). It may want to include the
    "peeled" value, as the current packed-refs file does.

  - Reading all of the reflogs (e.g., for repacking) is O(U), just like
    it is today. Except the storage for the logfile is a lot more
    compact than what we store today, with one reflog per file.

  - Reading a single reflog is _also_ O(U), which is not as good as
    today. But if each log entry contains a byte offset of the previous
    entry, you can follow the chain (it is still slightly worse, because
    you are jumping all over the file, rather than reading a compact set
    of lines).

  - Pruning the reflog entries from the logfile requires rewriting the
    whole thing. That's similar to today, where we rewrite each of the
    reflog files.

One of the nice properties of this system is that it should be very resilient to corruption and races. Most of the operations are either appending to a file, or writing to a tempfile and renaming in place. The exception is the key/value index, but if we run into any problems there, it can be rebuilt by walking over the logfile (for a cost of O(U)).

I dunno. Maybe I am overthinking it. But it really feels like the _refs_ are a key/value thing, but the _reflogs_ are not. You can cram them into a key/value store, but you're probably operating on them as a big blob, then.

One of the complaints that Shawn had about sqlite is that there is no native Java implementation, which makes it hard for JGit to ship a compatible backend. I suspect the same is true for LMDB, but it is probably a lot simpler than sqlite (so reimplementation might be possible).

But it may also be worth going with a slightly slower database if we can get wider compatibility for free.

I think we'll need to bump core.repositoryformatversion, too. See the patches I just posted here:

  http://thread.gmane.org/gmane.comp.version-control.git/272447

-Peff