RFC: split-inventories design: children-of-node/path-traversal

[Robert Collins]

On Wed, 2008-10-29 at 16:43 -0500, John Arbash Meinel wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Robert Collins wrote:
> > Opening this up for discussion; I don't have a solid answer yet, so this
> > is a bit of a brain-dump at this pont.
> > 
> > Doing path traversal - a/b/c could be done a few ways.
> > 
> > basename index w/value list:
> > here we would have a index on the basename, which isn't unique, so we'd
> > need to be able to treat the value as a list, or allow repeated keys, or
> > some such. Path traversal would then be a matter of doing set reduction
> > - to get b, we could just lookup b, grab all the fileids with a basename
> > of b, and walk up from them to the root - one will resolve to a/b/c.
> 
> Do you mean "b" here, or do you mean "c"?

yah, read to get c, we could just lookup c etc.

> 
> > 
> > fullpath index:
> ...
> > fullpath index w/hashed keys:
> ...
> > 
> > parentid->childid index w/value list:
> 
> This seems like the same way we would do it now in the in-memory inventory.

Its quite different. In memory we have N dicts, one per entry, and a
dict of fileid->entry(which has the child dicts); the N dicts are also
basename->child rather than being keyed by childid. This is one dict for
the whole inventory, and maps to childid rather than childname. So
rather than process one lookup to find a fileid, and then a separate
dict to find childrenobjects, we would do one lookup to find all the
children, another to obtain all their data, and then select.

> > parentid,child_basename->childid index:
> > here we would have an index on (fileid, child_basename). This requires a
> > index which supports things like 'foo bar' as keys, or encoding of
> > basenames before using it.
> > 
> > Now, directory objects in memory have a children attribute listing all
> > the paths within the directory; call this path discovery or 'ls'.
> > 
> > So doing ls: ls a/*:
> > 
> > basename index :- doesn't help
> 
> Well, if I understand correctly, means that you would do a basename
> lookup to find the file-id corresponding to 'a', and then you would look
> by file-id to find the children of a. (I suppose you could start at
> root, and do everything by file-id.) I guess it depends on what other
> indexes you have available.

Yes, you'd obtain 'a' via directory traversal, but then you'd read the
entire inventory to determine entries with 'a' as a parent.

> > 
> > fullpath index :- if we can iterate on keys starting with 'a/' we can
> > find a/b and a/b/c, but this would need some logic to avoid finding out
> > about c when we are only interested in children of a.
> 
> we could always make it a 'dirblock' style index, right? So that all
> children of 'a' would be clumped together, and all children of 'a/b'
> would be clumped together.
> 
> It is a little bit harder to compare keys in dirblock order, but we
> pretty much have that worked out, I believe.
> 
> But your comment that we would need to support whitespace, etc, in the
> index still applies. Though I think btree indexes pretty much only use
> '\0' as the key separator, so they are a lot more flexible with what
> they would allow.

We could make it a dirblock style index, yes.

> > 
> > fullpath hash-keys :- doesn't help
> > 
> > parentid-> childid :- works fine, just read everything.
> > 
> > parentid,child_basename :- works well, if we can get everything with the
> > parent's value.
> 
> so you would start at root, find its file-id, then look for
> (root_id,"a") to find its file-id, and then look for (a_id,*) to find
> the rest of the entries?

For ls a/*:
We know the root fileid (its in the inventories meta block at the
moment, though we could choose to remove it once we have a path based
lookup facility). Lets call this parentid,child_basename index
'children'.
1) children.iteritems([(root_id, "a")]) -> file_id_of_a
2) children.iteritems_prefix([(file_id_of_a, None)]) ->
file_ids_of_children.

> > 
> > I think the parentid,child_basename -> childid approach has legs, and I
> > intend to make sure the CHKMap will support it.
> > 
> > -Rob
> 
> I would lean towards fullpath index. Because if you are using btree
> index the keys end up compressed anyway, so the duplication is mostly
> removed by the time we've writted pages to disk.

It won't be a btree index because we need one version per revision
object; so its a version index using the CHKMap logic - regardless of
whether this is considered core data and fetched and validated, or
derived data and written to a cache alongside the actual commits, we
want to do as little IO as possible as we generate each revisions
edition. Testing would be needed to see what the duplication overhead
is. I seem to recally that when we had a similar situation in cached
annotations that it made a significant difference to remove the
duplication in a single record.

> Also, there is the same duplication in parent_id,child_basename, except
> a "parent_id" is a string that is 60 characters long which is longer
> than most of the paths are going to be.
>
> The average path is 30 characters in bzr.dev, and that includes the
> basename. The average path length in mysql is 37 characters, also
> including basename.
> 
> So while I think "parentid,child_basename" is interesting, I think a
> fullpath index is much more what we want. Possibly a dirblock sorted
> fullpath index, but fullpath nonetheless.

I think both are worth bring up far enough to compare size and baseline
performance.

a fileid,child_basename index is more general (because we can seek into
it without resolving file id to full path). So children(fileid) with a
fullpath index is done by walking the file ids to the root to get the
full path, and then back into the fullpath index. Thats height(tree)
overhead, compared to a direct lookup.

-Rob


-- 
GPG key available at: <http://www.robertcollins.net/keys.txt>.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: This is a digitally signed message part
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20081030/591f73a8/attachment.pgp