You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Jim Blandy <ji...@zwingli.cygnus.com> on 2001/02/09 22:36:29 UTC
Re: filesystem changes
Branko =?ISO-8859-2?Q?=C8ibej?= <br...@xbc.nu> writes:
> > Well, keep in mind that Berkeley DB is caching stuff for us. So we
> > won't usually be doing any I/O.
>
> I/O isn't the problem, linear searching could be. You don't even need an
> SVN filesystem to thest that: For typical path lookups, NTFS (which
> stores directory entries in a B+tree) beats the average Unix filesystem
> (which uses a list).
>
> All of this isn't important for small directories. But ... when I was
> working on that other versionable filesystem, we saw reports of people
> using directories with 5-10000 files -- all of them COBOL source. That
> stressed our caches a bit.
Yeah, this is something I'm interested in addressing in the long
term. For 1.0, though, I think we should leave it as is. We know the
Linux filesystem is good enough for a lot of stuff.
> How about
>
> (<dir node id>, <entry name>) -> <entry node id>
>
> ?
>
> You still get duplicates (although not so many), and a rename won't
> bother you.
>
> But any sort of index would mean duplicating the directory entry list
> and having to keep the two in sync. Bad, bad. *Except* if the index is
> the only place where you store this; and you rip out the ENTRIES list
> from DIR skels.
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
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.
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...
Re: filesystem changes
Posted by Karl Fogel <kf...@galois.collab.net>.
Branko =?ISO-8859-2?Q?=C8ibej?= <br...@xbc.nu> writes:
> Doh. Communication failure again: node revisions vs. filesystem revisions.
>
> We'll have to change these names, this is the third time we've been
> bitten ... filesystem avatars, maybe? Node incarnations? :-)
"rnode" (revisioned node) or "vnode" (versioned node) would both be
fine, IMHO.
Jim or Branko, if you want to change it across the board to something
less confusing, here is my +1 in advance. :-)
Re: filesystem changes
Posted by Branko Čibej <br...@xbc.nu>.
Jim Blandy wrote:
> No, you're missing my point. The idea is to store all revisions of
> all directories in a single table. Using the revision as part of the
> key allows successive revisions of the same directory to share
> structure.
>
> For example, if we have a directory with the following revisions:
>
> 10.1: foo->12.4 bar->13.6 baz->14.7
> 10.2: foo->12.5 bar->13.6 baz->14.7
> 10.3: foo->12.5 bar->13.6 baz->14.8
>
> then that would be represented by the following entries in the table:
>
> 10 foo 1 -> 12.4
> 10 bar 1 -> 13.6
> 10 baz 1 -> 14.7
> 10 foo 2 -> 12.5
> 10 baz 3 -> 14.8
>
> To find an entry E in a node N, node revision R, you search for N E x,
> where x is the largest x <= R. So searching for "bar" in node 10.3
> probes for "10 bar x", largest x <= R, which is "10 bar 1", which is
> 13.6.
>
> So node revisions two and three each share two table entries with the
> previous node revision.
Doh. Communication failure again: node revisions vs. filesystem revisions.
We'll have to change these names, this is the third time we've been
bitten ... filesystem avatars, maybe? Node incarnations? :-)
> Is there something broken about this?
Not that I can see -- of course, this is exactly the same scheme I was
proposing, except that the pieces of the node revision ID are laid out
differently in the key.
--
Brane �ibej
home: <br...@xbc.nu> http://www.xbc.nu/brane/
work: <br...@hermes.si> http://www.hermes-softlab.com/
ACM: <br...@acm.org> http://www.acm.org/
Re: filesystem changes
Posted by Jim Blandy <ji...@zwingli.cygnus.com>.
Branko =?ISO-8859-2?Q?=C8ibej?= <br...@xbc.nu> writes:
> > 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.
No, you're missing my point. The idea is to store all revisions of
all directories in a single table. Using the revision as part of the
key allows successive revisions of the same directory to share
structure.
For example, if we have a directory with the following revisions:
10.1: foo->12.4 bar->13.6 baz->14.7
10.2: foo->12.5 bar->13.6 baz->14.7
10.3: foo->12.5 bar->13.6 baz->14.8
then that would be represented by the following entries in the table:
10 foo 1 -> 12.4
10 bar 1 -> 13.6
10 baz 1 -> 14.7
10 foo 2 -> 12.5
10 baz 3 -> 14.8
To find an entry E in a node N, node revision R, you search for N E x,
where x is the largest x <= R. So searching for "bar" in node 10.3
probes for "10 bar x", largest x <= R, which is "10 bar 1", which is
13.6.
So node revisions two and three each share two table entries with the
previous node revision.
Is there something broken about this?
Re: filesystem changes
Posted by Branko Čibej <br...@xbc.nu>.
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.
--
Brane �ibej
home: <br...@xbc.nu> http://www.xbc.nu/brane/
work: <br...@hermes.si> http://www.hermes-softlab.com/
ACM: <br...@acm.org> http://www.acm.org/