Re: RFC: Flat directory for notes, or fan-out? Both!

From: Boyd Stephen Smith Jr. <bss@iguanasuicide.net>
Date: Feb 11, 2009, 01:58 UTC
Message-ID: <200902101958.21284.bss@iguanasuicide.net>
In-Reply-To: <20090210131600.GD17305@coredump.intra.peff.net>

On Tuesday 10 February 2009 07:16:00 you wrote:

Show 11 quoted lines

> On Tue, Feb 10, 2009 at 01:58:41AM -0600, Boyd Stephen Smith Jr. wrote:
> > On Monday 09 February 2009 15:12:06 Johannes Schindelin wrote:
> > > So I think it would be a sane plan to do the following when a commit
> > > note is requested:
> >
> > So, something like a Trie data structure?  I think that is a great way to
> > store fixed-length strings from a limited alphabet with arbitrary data
> > attached.
>
> I don't think a Trie quite makes sense here. We still have to look
> linearly through each git tree (an artifact of the tree implementation).

Perhaps it's not a traditional trie structure but that was the closest analogy I could come up with. I was actually thinking of something between a trie and a b-tree, I think. (It has been a long time since data structures class...)

The issue, as I understand it, it that we don't have gargantuan tree objects. Reading and writing are slow and they'd also take up way to much memory if you are only trying to find a few commits.

So, we figure out a maximum tree size that is reasonable, figure out a fan-out that prevents the tree from growing above that size, but *dynamically* apply that fan-out. I.e. if the fanout is 2 characters, and we've added notes for both ff82730c and ff23abc0, then our tree would have ff/ -> some_tree_sha, but if we had only a note for the one one our tree would have ff82730c... -> some_note_sha. Unlike .git/objects, we should probably also do dynamic fanout in subtrees.

Yes, this would require a custom merge strategy for notes to flatten -> merge -> canonicalize.

> Or did you mean something else entirely?

Yeah, that.

While I'm throwing out crazy ideas, why not makes a notes tree look just like .git/objects, including info and pack directories?

-- 
Boyd Stephen Smith Jr.                   ,= ,-_-. =.
bss@iguanasuicide.net                   ((_/)o o(\_))
ICQ: 514984 YM/AIM: DaTwinkDaddy         `-'(. .)`-'
http://iguanasuicide.net/                    \_/