Jim Blandy wrote:
> Yes, when the time comes, I think something like this is the way to
> go: simply move directory entries out into a table somewhere. Choose
> the right ordering predicate, and you'll get Berkeley DB's btrees
> managing your directory searches for you. (Does this mean
> transactions needn't lock the whole directory to change one entry?
> Even better!) The structure still needs to allow sharing of entries
> between similar revisions of a directory, of course, but there are
> ways to make that work.
> Perhaps the table should be
> DIR-NODE-ID ENTRY-NAME REVISION -> ENTRY-NODE-ID
Hmmm. Would you really need REVISION?
> where REVISION is the filesystem revision in which this directory
> entry was last changed. Use a table order that makes it easy to
> search for "the last rev no later than N". To delete a directory
> entry, you'd add a table entry of the form:
> DIR-NODE-ID ENTRY-NAME REVISION -> deleted
> which would mask table entries for the younger directory entries.
But if you delete an entry, or add it, or replace it with a successor,
the directory's revision itself gets bumped, and so all the way to the
root. So you don't need REVISION after all. Within an active
transaction, the mapping may change, but it's set in stone once you commit.
You can't have two keys that differ only in the REVISION, because you
can't have a changed (or mutable) subtree in the filesystem that's
doesn't start at the root.
You don't have to do "last rev no later than N" searches, because we do
all lookups from the root (since yesterday, remember? Your own idea. :-)
), and we can find the correct root in the revisions table.
> This is very much like SCCS, which tags every line that ever appeared
> in the file with the set of the revisions in which it appears.
> When the time comes...
Aye. Let's hope the time comes before 1.0, I'd hate having to change the
layout after the release.
home: <brane_at_xbc.nu> http://www.xbc.nu/brane/
work: <branko.cibej_at_hermes.si> http://www.hermes-softlab.com/
ACM: <brane_at_acm.org> http://www.acm.org/
Received on Sat Oct 21 14:36:21 2006