You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Karl Fogel <kf...@galois.collab.net> on 2001/03/05 17:30:26 UTC
Re: delta metric
Jim Blandy <ji...@zwingli.cygnus.com> writes:
> > > Since revision numbers increase by one each time a delta is added,
> > > we can compute how many deltas separate two related node revisions
> > > simply by comparing their ID's. For example, the distance between
> > > 100.10.3.2 and 100.12 is the distance from 100.10.3.2 to their
> > > common ancestor, 100.10 (two deltas), plus the distance from 100.10
> > > to 100.12 (two deltas).
> >
> > This metric really isn't true anymore is it? I mean we can't really
> > say (in the example above) that the two node revisions are 4 deltas
> > apart, because we can have "holes" in our nodes table, right?
>
> Can you give me an example of the sort of hole you have in mind?
I think he meant:
Jane starts a Subversion txn.
Bill starts a Subversion txn.
Jane makes a change to node N in her txn.
Bill makes a change against the same base revision of N, in his txn.
Jane aborts her txn.
Bill commits his txn.
Re: delta metric
Posted by Jim Blandy <ji...@zwingli.cygnus.com>.
Ben Collins-Sussman <su...@newton.ch.collab.net> writes:
> Ah, yeah. I just read svn_fs__new_successor_id(). Id's *do* get
> recycled.
But even if node revision ID's were not recycled, it wouldn't be a
problem.
Re: delta metric
Posted by Ben Collins-Sussman <su...@newton.ch.collab.net>.
Karl Fogel <kf...@galois.ch.collab.net> writes:
> >
> > My thoughts weren't as complex as Karl's, though; if Jane begins and
> > then aborts a transaction -- acting alone -- the deleted node-revision
> > numbers will never be recycled, right? The next person who comes
> > along and clones the same node as Jane is going to get the "next"
> > node-rev num, beyond the deleted one.
>
> No, they will be recycled. Remember, when Jane aborts her txn, all
> new node revisions created in that txn get deleted from the database
Ah, yeah. I just read svn_fs__new_successor_id(). Id's *do* get
recycled.
> (those node revs are invisible to the revision roots -- they're
> "garbage", in the sense that a floodfill from the any revision root
> can never reach them).
Floodfill? My, what an interesting brain you have. :)
Re: delta metric
Posted by Karl Fogel <kf...@galois.collab.net>.
Ben Collins-Sussman <su...@newton.ch.collab.net> writes:
> > I think he meant:
> >
> > Jane starts a Subversion txn.
> > Bill starts a Subversion txn.
> > Jane makes a change to node N in her txn.
> > Bill makes a change against the same base revision of N, in his txn.
> > Jane aborts her txn.
> > Bill commits his txn.
>
> Yup. Aborted transactions result in deleted node-revisions.
>
> My thoughts weren't as complex as Karl's, though; if Jane begins and
> then aborts a transaction -- acting alone -- the deleted node-revision
> numbers will never be recycled, right? The next person who comes
> along and clones the same node as Jane is going to get the "next"
> node-rev num, beyond the deleted one.
No, they will be recycled. Remember, when Jane aborts her txn, all
new node revisions created in that txn get deleted from the database
(those node revs are invisible to the revision roots -- they're
"garbage", in the sense that a floodfill from the any revision root
can never reach them).
-K
Re: delta metric
Posted by Ben Collins-Sussman <su...@newton.ch.collab.net>.
Karl Fogel <kf...@galois.ch.collab.net> writes:
> Jim Blandy <ji...@zwingli.cygnus.com> writes:
> > > > Since revision numbers increase by one each time a delta is added,
> > > > we can compute how many deltas separate two related node revisions
> > > > simply by comparing their ID's. For example, the distance between
> > > > 100.10.3.2 and 100.12 is the distance from 100.10.3.2 to their
> > > > common ancestor, 100.10 (two deltas), plus the distance from 100.10
> > > > to 100.12 (two deltas).
> > >
> > > This metric really isn't true anymore is it? I mean we can't really
> > > say (in the example above) that the two node revisions are 4 deltas
> > > apart, because we can have "holes" in our nodes table, right?
> >
> > Can you give me an example of the sort of hole you have in mind?
>
> I think he meant:
>
> Jane starts a Subversion txn.
> Bill starts a Subversion txn.
> Jane makes a change to node N in her txn.
> Bill makes a change against the same base revision of N, in his txn.
> Jane aborts her txn.
> Bill commits his txn.
Yup. Aborted transactions result in deleted node-revisions.
My thoughts weren't as complex as Karl's, though; if Jane begins and
then aborts a transaction -- acting alone -- the deleted node-revision
numbers will never be recycled, right? The next person who comes
along and clones the same node as Jane is going to get the "next"
node-rev num, beyond the deleted one.
Re: delta metric
Posted by Ben Collins-Sussman <su...@newton.ch.collab.net>.
Karl Fogel writes:
> Jane starts a Subversion txn 0.
> Bill starts a Subversion txn 1.
> Jane makes a change against 3.7 in txn 0, creating node rev 3.8
> Bill makes a change against 3.7 in txn 1, creating node rev 3.8.1.1.
> Jane aborts her txn, node rev 3.8 is removed from the database.
> Bill commits his txn, node rev 3.8.1.1 is committed for all time.
> =====> Now 3.8.1.1 exists, but 3.8 does not
>
> there isn't a "hole", and won't be a hole in the future, because no
> two-component noderev ID of the form 3.N (where N >= 8) will ever be
> created after the above scenario has happened.
and Jim Blandy writes:
> 3.10 cannot exist unless 3.8 does.
<ding!> Ahhhhhhhhhh...... enlightenment.
Re: delta metric
Posted by Karl Fogel <kf...@galois.collab.net>.
Greg Stein <gs...@lyra.org> writes:
> > > Jane starts a Subversion txn 0.
> > > Bill starts a Subversion txn 1.
> > > Jane makes a change against 3.7 in txn 0, creating node rev 3.8
> > > Bill makes a change against 3.7 in txn 1, creating node rev 3.8.1.1.
> > > Jane aborts her txn, node rev 3.8 is removed from the database.
> > > Bill commits his txn, node rev 3.8.1.1 is committed for all time.
> > > =====> Now 3.8.1.1 exists, but 3.8 does not
>
> Huh? You sure?? ... I thought you would end up with 3.8 and 3.7.1.1. Bill's
> change is *not* derived from 3.8.
I'm not sure, no, but I think that the "branch" numbers don't indicate
derivation in the way you think they do. That is, 3.8.1.1 doesn't
mean "derived from 3.8", it just means "when I tried to create 3.8, I
found it was already there, so I sidetracked onto 3.8.1.1 instead".
-K
> Therefore, you'd end up with 3.7 and 3.7.1.1. I would presume that further
> changes occur on the 3.7.1 line.
>
> There are still no holes, but I don't think the above numbering is correct.
>
> Cheers,
> -g
>
> --
> Greg Stein, http://www.lyra.org/
Re: branching (was: Re: delta metric)
Posted by Jim Blandy <ji...@zwingli.cygnus.com>.
Greg Stein <gs...@lyra.org> writes:
> On Sun, Mar 11, 2001 at 10:36:13PM -0500, Jim Blandy wrote:
> >...
> > Karl's correct that branches in node revision ID's have nothing to do
> > with branches at the user level.
>
> We don't even *have* branches at the user level, do we? Was there going to
> be something more than "just copy it somewhere else" ? Hmm. I guess there
> are three possibilities:
>
> 1) we do nothing. the user explicitly copies.
> 2) the user thinks they are branching, but underneath we're just copying
> 3) "something" different happens for a branch
>
>
> IMO, option (1) is where we ought to head.
Yes, that's my preference, too.
Re: branching (was: Re: delta metric)
Posted by Karl Fogel <kf...@galois.collab.net>.
Greg Stein <gs...@lyra.org> writes:
> We don't even *have* branches at the user level, do we? Was there going to
> be something more than "just copy it somewhere else" ? Hmm. I guess there
> are three possibilities:
>
> 1) we do nothing. the user explicitly copies.
> 2) the user thinks they are branching, but underneath we're just copying
> 3) "something" different happens for a branch
>
>
> IMO, option (1) is where we ought to head.
>
> We can certainly recommend a "best practices" of a tree that looks like:
>
> /
> main/
> tags/
> branches/
>
> And let people just work within that "typical" layout.
I think (1) is what we agreed on, too, yeah.
-K
branching (was: Re: delta metric)
Posted by Greg Stein <gs...@lyra.org>.
On Sun, Mar 11, 2001 at 10:36:13PM -0500, Jim Blandy wrote:
>...
> Karl's correct that branches in node revision ID's have nothing to do
> with branches at the user level.
We don't even *have* branches at the user level, do we? Was there going to
be something more than "just copy it somewhere else" ? Hmm. I guess there
are three possibilities:
1) we do nothing. the user explicitly copies.
2) the user thinks they are branching, but underneath we're just copying
3) "something" different happens for a branch
IMO, option (1) is where we ought to head.
We can certainly recommend a "best practices" of a tree that looks like:
/
main/
tags/
branches/
And let people just work within that "typical" layout.
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
Re: delta metric
Posted by Jim Blandy <ji...@zwingli.cygnus.com>.
Greg Stein <gs...@lyra.org> writes:
> On Thu, Mar 08, 2001 at 12:17:21PM -0500, Jim Blandy wrote:
> > Karl Fogel <kf...@galois.ch.collab.net> writes:
> > > Ahh. I *think* I understand now. Jim, in that example I posted:
> > >
> > > Jane starts a Subversion txn 0.
> > > Bill starts a Subversion txn 1.
> > > Jane makes a change against 3.7 in txn 0, creating node rev 3.8
> > > Bill makes a change against 3.7 in txn 1, creating node rev 3.8.1.1.
> > > Jane aborts her txn, node rev 3.8 is removed from the database.
> > > Bill commits his txn, node rev 3.8.1.1 is committed for all time.
> > > =====> Now 3.8.1.1 exists, but 3.8 does not
> > >
> > > there isn't a "hole", and won't be a hole in the future, because no
> > > two-component noderev ID of the form 3.N (where N >= 8) will ever be
> > > created after the above scenario has happened.
> > >
> > > However, it is not a problem that, say, 3.10 can never exist.
> > > Revisions of that node after 3.7 will be on some 3.8.X branch, and
> > > that's just fine. It's not like "branch" in this context has anything
> > > to do with user-visible branches (i.e., copies). Relatedness distance
> > > between node revisions, for whatever it's worth, can still be computed
> > > according to the formula given in structure.
> > >
> > > Is this an accurate summary?
> >
> > Yes.
>
> Huh? You sure?? ... I thought you would end up with 3.8 and 3.7.1.1. Bill's
> change is *not* derived from 3.8.
>
> Therefore, you'd end up with 3.7 and 3.7.1.1. I would presume that further
> changes occur on the 3.7.1 line.
>
> There are still no holes, but I don't think the above numbering is correct.
Yes, Greg is right. I didn't look at Karl's numbers carefully enough.
3.7.1.1 is an immediate successor of 3.7. Bill's change in txn 1
would create 3.7.1.1, not 3.8.1.1.
How, you may ask, does Bill's transaction "know" to create a branch of
3.7, instead of working from the youngest node in the line, 3.8?
Well, 3.7 is the node that appears in the base revision of Bill's
transaction. Whenever you clone a node revision (i.e., make a mutable
successor of a node revision in some transaction which had previously
been immutable and shared with the txn's base revision tree), you
create an immediate successor of that node revision. If you look at
svn_fs__new_successor_id, the function that chooses an ID for a new
immediate successor of an existing node revision, you'll see that if
3.8 isn't taken, it'll use that as a successor to 3.7, but if 3.8
already exists, it'll make a new revision on a branch 3.7.N.1.
Karl's correct that branches in node revision ID's have nothing to do
with branches at the user level.
Re: delta metric
Posted by Greg Stein <gs...@lyra.org>.
On Thu, Mar 08, 2001 at 12:17:21PM -0500, Jim Blandy wrote:
> Karl Fogel <kf...@galois.ch.collab.net> writes:
> > Ahh. I *think* I understand now. Jim, in that example I posted:
> >
> > Jane starts a Subversion txn 0.
> > Bill starts a Subversion txn 1.
> > Jane makes a change against 3.7 in txn 0, creating node rev 3.8
> > Bill makes a change against 3.7 in txn 1, creating node rev 3.8.1.1.
> > Jane aborts her txn, node rev 3.8 is removed from the database.
> > Bill commits his txn, node rev 3.8.1.1 is committed for all time.
> > =====> Now 3.8.1.1 exists, but 3.8 does not
> >
> > there isn't a "hole", and won't be a hole in the future, because no
> > two-component noderev ID of the form 3.N (where N >= 8) will ever be
> > created after the above scenario has happened.
> >
> > However, it is not a problem that, say, 3.10 can never exist.
> > Revisions of that node after 3.7 will be on some 3.8.X branch, and
> > that's just fine. It's not like "branch" in this context has anything
> > to do with user-visible branches (i.e., copies). Relatedness distance
> > between node revisions, for whatever it's worth, can still be computed
> > according to the formula given in structure.
> >
> > Is this an accurate summary?
>
> Yes.
Huh? You sure?? ... I thought you would end up with 3.8 and 3.7.1.1. Bill's
change is *not* derived from 3.8.
Therefore, you'd end up with 3.7 and 3.7.1.1. I would presume that further
changes occur on the 3.7.1 line.
There are still no holes, but I don't think the above numbering is correct.
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
Re: delta metric
Posted by Jim Blandy <ji...@zwingli.cygnus.com>.
Karl Fogel <kf...@galois.ch.collab.net> writes:
> Ahh. I *think* I understand now. Jim, in that example I posted:
>
> Jane starts a Subversion txn 0.
> Bill starts a Subversion txn 1.
> Jane makes a change against 3.7 in txn 0, creating node rev 3.8
> Bill makes a change against 3.7 in txn 1, creating node rev 3.8.1.1.
> Jane aborts her txn, node rev 3.8 is removed from the database.
> Bill commits his txn, node rev 3.8.1.1 is committed for all time.
> =====> Now 3.8.1.1 exists, but 3.8 does not
>
> there isn't a "hole", and won't be a hole in the future, because no
> two-component noderev ID of the form 3.N (where N >= 8) will ever be
> created after the above scenario has happened.
>
> However, it is not a problem that, say, 3.10 can never exist.
> Revisions of that node after 3.7 will be on some 3.8.X branch, and
> that's just fine. It's not like "branch" in this context has anything
> to do with user-visible branches (i.e., copies). Relatedness distance
> between node revisions, for whatever it's worth, can still be computed
> according to the formula given in structure.
>
> Is this an accurate summary?
Yes.
Re: delta metric
Posted by Karl Fogel <kf...@galois.collab.net>.
Brian Moore <mo...@epinions-inc.com> writes:
> i hope that the statement "3.10 cannot exist unless 3.8 does" is false,
> because that means if there's a hole (as described earlier today)
> in the revision tree, development must stop on that branch, unless i
> totally misunderstand how the revision numbers are assigned.
Ahh. I *think* I understand now. Jim, in that example I posted:
Jane starts a Subversion txn 0.
Bill starts a Subversion txn 1.
Jane makes a change against 3.7 in txn 0, creating node rev 3.8
Bill makes a change against 3.7 in txn 1, creating node rev 3.8.1.1.
Jane aborts her txn, node rev 3.8 is removed from the database.
Bill commits his txn, node rev 3.8.1.1 is committed for all time.
=====> Now 3.8.1.1 exists, but 3.8 does not
there isn't a "hole", and won't be a hole in the future, because no
two-component noderev ID of the form 3.N (where N >= 8) will ever be
created after the above scenario has happened.
However, it is not a problem that, say, 3.10 can never exist.
Revisions of that node after 3.7 will be on some 3.8.X branch, and
that's just fine. It's not like "branch" in this context has anything
to do with user-visible branches (i.e., copies). Relatedness distance
between node revisions, for whatever it's worth, can still be computed
according to the formula given in structure.
Is this an accurate summary?
-K
> On 5 Mar 2001, Jim Blandy wrote:
>
> > Brian Moore <mo...@epinions-inc.com> writes:
> > > so if revision 3.8.1.1 exists but revision 3.8 does not exist,
> > > will the merge from 3.8.1.1 to 3.10 work properly? i'm thinking
> > > that finding a common ancestor will not be as simeple as i thought
> > > it would be.
> >
> > 3.10 cannot exist unless 3.8 does.
> >
Re: delta metric
Posted by Brian Moore <mo...@epinions-inc.com>.
i hope that the statement "3.10 cannot exist unless 3.8 does" is false,
because that means if there's a hole (as described earlier today)
in the revision tree, development must stop on that branch, unless i
totally misunderstand how the revision numbers are assigned.
b
On 5 Mar 2001, Jim Blandy wrote:
> Brian Moore <mo...@epinions-inc.com> writes:
> > so if revision 3.8.1.1 exists but revision 3.8 does not exist,
> > will the merge from 3.8.1.1 to 3.10 work properly? i'm thinking
> > that finding a common ancestor will not be as simeple as i thought
> > it would be.
>
> 3.10 cannot exist unless 3.8 does.
>
Re: delta metric
Posted by Jim Blandy <ji...@zwingli.cygnus.com>.
Brian Moore <mo...@epinions-inc.com> writes:
> so if revision 3.8.1.1 exists but revision 3.8 does not exist,
> will the merge from 3.8.1.1 to 3.10 work properly? i'm thinking
> that finding a common ancestor will not be as simeple as i thought
> it would be.
3.10 cannot exist unless 3.8 does.
Re: delta metric
Posted by Karl Fogel <kf...@galois.collab.net>.
Brian Moore <mo...@epinions-inc.com> writes:
> so if revision 3.8.1.1 exists but revision 3.8 does not exist,
> will the merge from 3.8.1.1 to 3.10 work properly? i'm thinking
> that finding a common ancestor will not be as simeple as i thought
> it would be.
It's not much more complex. The general rule is, if the thing you
expected to find isn't there, you always have a formula that tells you
what to look for instead. Does that make sense?
-K
> On 5 Mar 2001, Karl Fogel wrote:
>
> > Jim Blandy <ji...@zwingli.cygnus.com> writes:
> > > > I think he meant:
> > > >
> > > > Jane starts a Subversion txn.
> > > > Bill starts a Subversion txn.
> > > > Jane makes a change to node N in her txn.
> > > > Bill makes a change against the same base revision of N, in his txn.
> > > > Jane aborts her txn.
> > > > Bill commits his txn.
> > >
> > > Yes, and what kind of problematic node numbers could this situation
> > > produce? Give me a specific example.
> >
> > Actually, I don't think they are problematic, should have said so up
> > front. I was just concurring with Ben that there can be skips in the
> > sequence of node revision numbers off a given node.
> >
> > Jane starts a Subversion txn 0.
> > Bill starts a Subversion txn 1.
> > Jane makes a change against 3.7 in txn 0, creating node rev 3.8
> > Bill makes a change against 3.7 in txn 1, creating node rev 3.8.1.1.
> > Jane aborts her txn, node rev 3.8 is removed from the database.
> > Bill commits his txn, node rev 3.8.1.1 is committed for all time.
> >
> > I don't see any problem with 3.8.1.1 existing even though 3.8
> > doesn't.
> >
> > -K
> >
Re: delta metric
Posted by Brian Moore <mo...@epinions-inc.com>.
so if revision 3.8.1.1 exists but revision 3.8 does not exist,
will the merge from 3.8.1.1 to 3.10 work properly? i'm thinking
that finding a common ancestor will not be as simeple as i thought
it would be.
b
On 5 Mar 2001, Karl Fogel wrote:
> Jim Blandy <ji...@zwingli.cygnus.com> writes:
> > > I think he meant:
> > >
> > > Jane starts a Subversion txn.
> > > Bill starts a Subversion txn.
> > > Jane makes a change to node N in her txn.
> > > Bill makes a change against the same base revision of N, in his txn.
> > > Jane aborts her txn.
> > > Bill commits his txn.
> >
> > Yes, and what kind of problematic node numbers could this situation
> > produce? Give me a specific example.
>
> Actually, I don't think they are problematic, should have said so up
> front. I was just concurring with Ben that there can be skips in the
> sequence of node revision numbers off a given node.
>
> Jane starts a Subversion txn 0.
> Bill starts a Subversion txn 1.
> Jane makes a change against 3.7 in txn 0, creating node rev 3.8
> Bill makes a change against 3.7 in txn 1, creating node rev 3.8.1.1.
> Jane aborts her txn, node rev 3.8 is removed from the database.
> Bill commits his txn, node rev 3.8.1.1 is committed for all time.
>
> I don't see any problem with 3.8.1.1 existing even though 3.8
> doesn't.
>
> -K
>
Re: delta metric
Posted by Karl Fogel <kf...@galois.collab.net>.
Jim Blandy <ji...@zwingli.cygnus.com> writes:
> > I think he meant:
> >
> > Jane starts a Subversion txn.
> > Bill starts a Subversion txn.
> > Jane makes a change to node N in her txn.
> > Bill makes a change against the same base revision of N, in his txn.
> > Jane aborts her txn.
> > Bill commits his txn.
>
> Yes, and what kind of problematic node numbers could this situation
> produce? Give me a specific example.
Actually, I don't think they are problematic, should have said so up
front. I was just concurring with Ben that there can be skips in the
sequence of node revision numbers off a given node.
Jane starts a Subversion txn 0.
Bill starts a Subversion txn 1.
Jane makes a change against 3.7 in txn 0, creating node rev 3.8
Bill makes a change against 3.7 in txn 1, creating node rev 3.8.1.1.
Jane aborts her txn, node rev 3.8 is removed from the database.
Bill commits his txn, node rev 3.8.1.1 is committed for all time.
I don't see any problem with 3.8.1.1 existing even though 3.8
doesn't.
-K
Re: delta metric
Posted by Jim Blandy <ji...@zwingli.cygnus.com>.
Karl Fogel <kf...@galois.ch.collab.net> writes:
> Jim Blandy <ji...@zwingli.cygnus.com> writes:
> > > > Since revision numbers increase by one each time a delta is added,
> > > > we can compute how many deltas separate two related node revisions
> > > > simply by comparing their ID's. For example, the distance between
> > > > 100.10.3.2 and 100.12 is the distance from 100.10.3.2 to their
> > > > common ancestor, 100.10 (two deltas), plus the distance from 100.10
> > > > to 100.12 (two deltas).
> > >
> > > This metric really isn't true anymore is it? I mean we can't really
> > > say (in the example above) that the two node revisions are 4 deltas
> > > apart, because we can have "holes" in our nodes table, right?
> >
> > Can you give me an example of the sort of hole you have in mind?
>
> I think he meant:
>
> Jane starts a Subversion txn.
> Bill starts a Subversion txn.
> Jane makes a change to node N in her txn.
> Bill makes a change against the same base revision of N, in his txn.
> Jane aborts her txn.
> Bill commits his txn.
Yes, and what kind of problematic node numbers could this situation
produce? Give me a specific example.