Re: RFC/Pull Request: Refs db backend

From: Jeff King <peff@peff.net>
Date: Jun 24, 2015, 08:51 UTC
Message-ID: <20150624085141.GA5436@peff.net>
In-Reply-To: <CACsJy8B=jthxn_E-zWnDfua29FGGgz221N-cLw=NxeVOKadUxA@mail.gmail.com>

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

Show 5 quoted lines

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

Show 14 quoted lines

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