Subject: Re: RFC/Pull Request: Refs db backend

From: Jeff King <[email-masked]>
Date: Wed, 24 Jun 2015 04:51:41 -0400

On Tue, Jun 23, 2015 at 08:10:03PM +0700, Duy Nguyen wrote:

> >   - 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
> 
> One key/value mapping per branch, pointing to the latest reflog entry,
> or one key/valye mapping for each reflog entry?

Yeah, sorry, I meant to point only to the latest entry (and then from
there if you want to actually walk the reflog, you can do so by
following the backreference to the previous entry).

> >     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.
> 
> I'm thinking of the user with small or medium repos, in terms of refs,
> who does not want an extra dependency. If we store one mapping per
> branch, then the size of this mapping is small enough that the index
> in a text file is ok. If we also store the offset to the previous
> reflog entry of the same branch in the current reflog entry, like a
> back pointer, then we could jump back faster.
> 
> Or do you have something else in mind? Current reflog structure won't
> work because I think you bring back the reflog graveyard with this,
> and I don't want to lose that

I hadn't really thought about having multiple formats for the index. But
in theory, yes, you could, and the lowest common denominator could just
use the filesystem. Or even something similar to the packed-refs file,
where we have to write the whole thing to make a single update. That
doesn't perform well, but it's dirt simple and might be OK if you have
only a handful of refs.

-Peff