You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Bill Tutt <bi...@microsoft.com> on 2002/05/08 00:22:42 UTC
Maintaining NodeID sanity
Branko came up with a decent idea to restore NodeID sanity to the
universe in the face of the weird side-effects of O(1) copies.
The thinking goes something like this:
We want to keep the NodeID the same for branches, but different for
copies.
We want to only change the NodeID on the destination of the copy.
A copy is really almost a branch. Let's think about just branches for
the moment.
So, we need a way to distinguish a NodeChange besides just the normal
(NodeID, ChangeSetID) data.
Let's add a BranchID to the PK of a NodeChange so that you have (NodeID,
BranchID, ChangeSetID) as the PK of NodeChange.
So when you "branch <src> <dest>" the result of the branch is a new
NodeChange that looks like this:
(<src NodeID>, <some opaque BranchID type>, <branch operation's
ChangeSetID>)
Now all we need is to know exactly what a BranchID is.
Branko's idea was to define a BranchID as:
NodeChangePKOf(parentOf(<dest>)).
The problem with that is that the PK contains BranchID which is now
recursively defined. That's good for nested branches, but bad for a
schema.
One alternative is to add a unique column to NodeChange: NodeChangeID.
NodeChangeID is a monotonically increasing integer (possibly a
fixed-precision decimal considering that NodeChangeIDs will be used much
more quickly than NodeIDs) that is unique for each NodeChange.
NodeChangeID is not an additional part of the PK. It is an AK
(alternative key).
BranchID can now be defined to be: NodeChangeID of <dest>.
When the user creates a branch of path "/foo" to "/bar" the following
can now happen:
Create a new NodeChange of ("/foo".NodeID, BranchID ==
this.NodeChangeID, ChangeSetID) and associate it with "/bar". This
doesn't set any of the copy related properties, and only changes the
BranchID.
When you are committing new changes to things under /bar (or revision
bumps of /bar), any new nodes will have the BranchID set to "/bar''s
BranchID.
The problem now becomes what I do when I have one of these complicated
nested branch cases.
e.g.:
/foo/main/A
/foo/alt/A
where /foo/alt is a branch of /foo/main.
I then: "branch /foo /bar"
I then make a modification to "/bar/alt/A".
What BranchID does A's NodeChange row now have?
If we lazily flatten sub-branches then it could be "/bar"'s BranchID.
If we lazily create sub-branches then it could be "/bar/alt/"'s
BranchID.
Flattening isn't terribly friendly to our users, so let's think about
what we have to do if we lazily create our sub-branches.
When examining /bar/alt we notice that the existing BranchID != /bar's
BranchID. This may mean any number of things:
* It might be a copy, since we haven't told you how to differentiate
between a copy and a branch. If it existed inside of a copy, the
BranchID is unimportant since if it needs to change to be /bar's
BranchID.
* It might be a branch, and if so, we need to create a new NodeChange
for alt, containing a new BranchID. The origin of this branch is
recorded as being /foo/alt.
Once we have this new BranchID, we can then use it while creating the
new NodeChange for /bar/alt/A.
But, how do we detect that /bar/alt is a branch instead of a copy? (i.e.
it might be a copy of a branch)
Alt.BranchID points to /foo/alt's data. (The location of the original
branch.) When I look that data up, I'll notice that the copy information
is absent. This tells me I have a branch. If I had a copy, the copy
properties would be filled in.
The only additional annoyance is that copy/branch destination nodes
don't record the path that they were created at. Given the DAGgy nature
of our data store, it would certainly help if they included what their
creation path was.
i.e.: /bar was created at path /bar.
To sum up:
Add a BranchID to the PK of NodeChange.
Add a NodeChangeID as an AK of NodeChange. (i.e. monotonically
increasing integer that uniquely, but not usefully defines a NodeChange
row)
Use the NodeChangeID as the BranchID when creating copies/branches.
Add a CreatedPath to NodeChange that is only used for copy/branch
operations.
Alternatively, you could get away without having NodeChangeID since it
requires a separate BDB table to repeat the PK of NodeChange to point to
the correct NodeChange row.
If we do the above we get the following benefits:
* NodeIDs stay the same for branches, but change for copies.
* NodeIDs are attached to the path that they're created in. No more
non-deterministic migrating of NodeID usages depending on which side of
a copy got modified first.
* We get the easy possibility of handling O(1) branches, sub-branches,
and sub-sub-branches, etc....
* Computing the next NodeID to use for a NodeChange alteration is much
quicker.
(It's built up as you traverse the path space looking for NodeChange's
to create new revisions of.)
* svn log for branched items includes all of the history of the node
before the branch. Since the inline history revision data is preserved.
* The addition of created path to copy/branch points reduces poor svn
log's workload when told to figure out what it needs to do, but can't
easily output where a nested branch/copy came from.
Sounds like utter goodness to me. :)
Bill
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
Karl Fogel <kf...@newton.ch.collab.net> writes:
> Blobs are okay unless you're searching in them often for information.
> If we have to constantly load and/or scan a whole blob to find out
> whether node FOO is an ancestor of BAR or not, that seems like a bit
> of downgrade from the current system.
Well, once alleviating factor is that in the case of directories, we
don't actually need to know whether the "other" node is an ancestor or
a successor; we just need to establish that it's related so we can
merge entry lists.
(Speaking off the cuff; am not in that code right now.)
-K
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by "Glenn A. Thompson" <gt...@cdr.net>.
Thanks Karl!!!!
It seems like all I post are "I don't understand" questions.
I get more confused every day.
This will help me a great deal.
Karl Fogel wrote:
> Bill, I'm sort of losing track of exactly what's being proposed and
> what its goals are, at this point.
>
> A *really* helpful thing would be a fresh mail, that begins with a
> list of the problems you're trying to solve, including a small
> concrete example for each problem. These should only be problems that
> exist in the current filesystem implementation, not problems in prior
> incarnations of various proposals. Describe solutions only after the
> problems are presented.
I assume you mean in a real "svn ...." context right?
>
>
> For example, you seem to want to treat branches as different from
> copies, but that's only something I've inferred slowly from your
> mails. Maybe there's a reason to do so, but right now branches and
> copies are just two words for exactly the same thing in Subversion.
> There's no difference, and distinguishing between them would be a
> major design change [read: unlikely before 1.0 :-), though if failure
> to distinguish leads to horrible problems, then of course we need to
> rethink]. Until we understand whether or not this is a goal, and if
> it is then why, it's hard to evaluate or even think clearly about the
> proposals.
thank you again.
>
> Just to be clear: I really, really appreciate that you're bringing
> years of db experience and schema design to bear on Subversion's
> problems, and want to benefit from this. But without clear
> communication, there's no way we'll grok the wonderful things going on
> in your head :-).
>
> Btw: I know it's much easier for you to speak in generic RDB language,
> and that you look forward to the day when Subversion uses a real
> relational database backend... But, as we are using Berkeley DB right
> now, and also in 1.0, so it would help a lot to talk about how things
> would be implemented in bdb specifically.
>
I totally agree here. When porting to "blah blah blah" it helps to always
have a point of reference.
It seems to me that BDB and the existing code have to be considered the
reference implementation.
I'm not saying ignore SQL impacts to the schema; But it is hard to jump
back and forth between the future and the present.
gat
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
Greg Stein <gs...@lyra.org> writes:
> > <root>
> > / | \
> > / | \
> > / | \
> > A(3.m) B Y(3.p.jfb)
> > / \ | / \
> > foo bar qux foo bar
> > (5.abc) (5.abc)
> > : :
> > : :
> > (5.ejk) (b.mht.jfb)
> > : :
> > : :
> > (5.xyz) (b.uuu.jfb)
> > : :
> > : :
> > (5.r2d2) (b.2pz.jfb)
> > : :
> > : :
> > (5.c3po) (b.rdt.jfb)
> >...
> > During this walk, you can always tell when you encounter a node that
> > results from a copy, because the copyID portion will either change or
> > disappear entirely. When this happens, you know one of two things is
> > true: either the previous node in the walk was the top of a copied
> > tree, or *this* node (the one with the different copyID) was one of
> > the unchanged nodes down inside a copied tree.
>
> Why do we care about the status of the child node? Or, to put another way,
> why do we generate a new copyID? Isn't it sufficient to just change the
> NodeID and leave it at that?
>
> Ah... you use that '.jfb' and the copies table to relate the node to 5.*,
> right?
Goodness me, what a confusing typo I made.
All those "b.*.jfb" should be "5.*.jfb", sorry for the confusion!
> Oh... and why bother with base64? To keep the keys shorter in the DB? That
> seems rather obscure. When debugging, I think it will be much nicer for the
> humans to just use a plain old integer.
It's just to avoid the endless questions from people worried about
running out of keys :-).
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
Greg Stein <gs...@lyra.org> writes:
> That confusion would only true on the presumption that people will attempt
> to relate and compare the two txn-ids. I don't believe anybody will do that.
> Thus, you won't have a "semantic confusion", but you'll still end up with
> the "syntactic confusion" (as you termed them).
What I'm more worried about is the copyIDs, because it's easy to fall
into thinking that higher ones must have been committed after lower
ones. Of course, anyone who's done their homework will know
otherwise; but I think there's value in being friendly to those who
haven't done their homework too, since you never know who will need to
track a bug down into the filesystem. (n.b. I'm aware that the point
being questioned was whether or not this is more "friendly", not over
whether being friendly is a Good Thing :-) ).
Heck, txnIDs actually can be ordered reliably by their keys, at least
if you're trying to order which txn was opened first, not which was
committed first. Why anyone would want to do that, I can't imagine
either.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Greg Stein <gs...@lyra.org>.
On Sat, May 11, 2002 at 03:11:07PM -0500, Ben Collins-Sussman wrote:
>...
> - Karl argues that integers imply ordering of txn-ids, so
> programmers will be *semantically* confused when they they seem to
> be out-of-order.
That confusion would only true on the presumption that people will attempt
to relate and compare the two txn-ids. I don't believe anybody will do that.
Thus, you won't have a "semantic confusion", but you'll still end up with
the "syntactic confusion" (as you termed them).
-g
--
Greg Stein, http://www.lyra.org/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Greg Stein <gs...@lyra.org>.
On Fri, May 10, 2002 at 11:26:30PM -0500, Karl Fogel wrote:
> Branko Cibej <br...@xbc.nu> writes:
> > * Base64 conversion is faster than itoa (no division); more natural
> > for marshaling integers
>
> Greg's not talking about the conversion, he's talking about
> comparisons after you've already done the conversion.
I'm hoping there isn't ANY conversion. "Conversion" implies that you have
two different representations for the same concept. And I don't see any
rational reason to make these "different", other than "because we can".
-g
--
Greg Stein, http://www.lyra.org/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
Branko Čibej <br...@xbc.nu> writes:
> * Base64 conversion is faster than itoa (no division); more natural
> for marshaling integers
Greg's not talking about the conversion, he's talking about
comparisons after you've already done the conversion.
> * Base64 representation is not user-friendly, because it's
> case-sensitive and uses non-alphanumeric characters (among them
> the famous ".", which is liable to screw up key parsing)
>
> Might I suggest Base16? Perhaps with a little gold leaf around the
> hinges, and a nickel-plated padlock? :-)
Sorry, I've been saying base64 when that's not what I mean.
I mean base36 or base62. That is, all numbers, and all letters,
possibly in both cases. No other chars allowed.
-K
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Ben Collins-Sussman <su...@collab.net>.
Branko Čibej <br...@xbc.nu> writes:
> Might I suggest Base16? Perhaps with a little gold leaf around the
> hinges, and a nickel-plated padlock? :-)
LOL!
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Branko Čibej <br...@xbc.nu>.
Greg Stein wrote:
>On Fri, May 10, 2002 at 03:52:12PM -0500, Karl Fogel wrote:
>
>
>>Greg Stein <gs...@lyra.org> writes:
>>
>>
>>>Oh. Using base64 (strings) would be a negative system perf change, given the
>>>ID comparison pointed out above.
>>>
>>>
>>Um, we're talking about reading data from db pages here. I somehow
>>doubt that key comparison is a meaningful performance bottleneck.
>>
>>
>
>Oh, it's still moot [because of the I/O], it is just that at a micro level,
>using strings rather than integers [in the ID structure] is a negative
>impact.
>
>
>Seriously... the ID structure should be integers. Thus, you would also want
>to marshal the IDs into BDB as integers.
>
Oh my, I'm gonna love this, beating you both down:
* Base64 conversion is faster than itoa (no division); more natural
for marshaling integers
* Base64 representation is not user-friendly, because it's
case-sensitive and uses non-alphanumeric characters (among them
the famous ".", which is liable to screw up key parsing)
Might I suggest Base16? Perhaps with a little gold leaf around the
hinges, and a nickel-plated padlock? :-)
>Do you have a specific problem with that approach?
>
>
--
Brane Čibej <br...@xbc.nu> http://www.xbc.nu/brane/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Greg Stein <gs...@lyra.org>.
On Fri, May 10, 2002 at 03:52:12PM -0500, Karl Fogel wrote:
> Greg Stein <gs...@lyra.org> writes:
> > Oh. Using base64 (strings) would be a negative system perf change, given the
> > ID comparison pointed out above.
>
> Um, we're talking about reading data from db pages here. I somehow
> doubt that key comparison is a meaningful performance bottleneck.
Oh, it's still moot [because of the I/O], it is just that at a micro level,
using strings rather than integers [in the ID structure] is a negative
impact.
Seriously... the ID structure should be integers. Thus, you would also want
to marshal the IDs into BDB as integers.
Do you have a specific problem with that approach?
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
Greg Stein <gs...@lyra.org> writes:
> Oh. Using base64 (strings) would be a negative system perf change, given the
> ID comparison pointed out above.
Um, we're talking about reading data from db pages here. I somehow
doubt that key comparison is a meaningful performance bottleneck.
-K
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Voting, WAS: RE: Maintaining NodeID sanity
Posted by Sander Striker <st...@apache.org>.
> From: Karl Fogel [mailto:kfogel@newton.ch.collab.net]
> Sent: 12 May 2002 21:53
> Greg Stein <gs...@lyra.org> writes:
> > > +1 on base36 with `const char *'; -1 on integers whatever the
> > > marshalling.
> >
> > well, with a veto on integers, I'll shut up now.
>
> Erp! I meant that as a vote only, should have written "-1, no veto".
Nope, you should have written -0. For the record, valid votes are:
-1 (veto, always)
-0 (won't veto it, but am not supporting it/don't like it much)
+0 (don't feel strongly about it, but positive on overall)
+1 (agree)
Sander
PS. The topic may be misleading now. This _isn't_ a call for votes.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
Greg Stein <gs...@lyra.org> writes:
> > +1 on base36 with `const char *'; -1 on integers whatever the
> > marshalling.
>
> well, with a veto on integers, I'll shut up now.
Erp! I meant that as a vote only, should have written "-1, no veto".
I don't want to tie cmike's hands. Have already given my reasons for
preferring `const char *' in memory, if outvoted by the other
committers, that's fine. In case of tie, let cmike choose, he's doing
the coding :-).
-K
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
Daniel Berlin <db...@dberlin.org> writes:
> What he really means to say is probably
>
> "+1 on base36 marshalled as A-Z0-9 (through modulo 36) in a const char *;
> -1 on integers accessed through integer types, whatever base"
Yep, that's what I meant.
> After all, we need to be explicit.
We need to be explicit enough for the people we're talking to to
understand us, yes. You seemed to manage well enough :-).
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Daniel Berlin <db...@dberlin.org>.
On Sun, 12 May 2002, Greg Stein wrote:
> On Sat, May 11, 2002 at 02:54:28PM -0500, Karl Fogel wrote:
> >...
> > +1 on base36 with `const char *'; -1 on integers whatever the
> > marshalling.
>
> well, with a veto on integers, I'll shut up now.
Well, what he says makes no real sense anyway, if it makes you feel
better.
base36 == integers transformed into another base, one that happens to map
nicely onto 0-9,A-Z
They are still integers.
So by saying "-1 on integers whatever the marshalling", he's just
contradicted himself.
Since base36 is integers, with a marshalling that nicely maps onto
the english alphabet + 0-9.
Just cause they *look* like strings doesn't mean they are.
:)
What he really means to say is probably
"+1 on base36 marshalled as A-Z0-9 (through modulo 36) in a const char *;
-1 on integers accessed through integer types, whatever base"
After all, we need to be explicit.
Saying "base36" doesn't mean much, as one
could map base36 onto the words
"
CAT HAT SAT PAT FAT RAT VAT EAT COG DOG
LOG HOG JOG HIT BIT SIT FIT WIT KIT LIT
NIT ZIT BOP LOP ROP TOP NOP POP COP MOP
HOP CAP LAP MAP NAP RAP
"
>
> -g
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Greg Stein <gs...@lyra.org>.
On Sat, May 11, 2002 at 02:54:28PM -0500, Karl Fogel wrote:
>...
> +1 on base36 with `const char *'; -1 on integers whatever the
> marshalling.
well, with a veto on integers, I'll shut up now.
-g
--
Greg Stein, http://www.lyra.org/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
Ben Collins-Sussman <su...@collab.net> writes:
> Greg has made two arguments against base36: translation-speed and
> obfuscation. He even says that above.
Yes, I saw them. I was referring to something outside his actual
arguments, ahem :-).
> Obfuscation is the only real issue here, it seems. The silly thing is
> that Karl and Greg are each accusing one another of it!
Oh, I don't think there's any accusation going on here. We're
disagreeing about what is "obfuscation". Since obfuscation is about
what is clear to a human, the answer will depend partly on which human
is considering the question. Another way of saying it is that it's a
matter of taste.
The question of whether integer space is big enough is also, in a
sense, a matter of taste, at least until many years from now.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Ben Collins-Sussman <su...@collab.net>.
Karl Fogel <kf...@newton.ch.collab.net> writes:
> > Base-36 (or your suggestion for base-62) is way beyond the insane.
> > Completely non-standard in all respects, none of the speed Brane
> > was talking about with base-16 encoding, and still obfuscates the
> > underlying integer that these keys are derived from.
>
> Base 36 is what I'd like to do; I've already presented the reasons.
> Calling it "way beyond insane" doesn't add any substance to the
> discussion.
Greg has made two arguments against base36: translation-speed and
obfuscation. He even says that above.
However, I don't think I agree with Greg. I don't believe that
translation-speed is an issue at all when we're talking about
disk-bound DB lookups. It's a drop in the ocean.
Obfuscation is the only real issue here, it seems. The silly thing is
that Karl and Greg are each accusing one another of it!
- Greg argues that the txn-ids are integers, so programmers will be
*syntactically* confused when we make them look like weird base36
strings.
- Karl argues that integers imply ordering of txn-ids, so
programmers will be *semantically* confused when they they seem to
be out-of-order.
My vote goes with Karl, because I thing semantic confusion is much
worse. Coders are more likely to poke around the fs and try to
understand the semantic structure of trees. I don't know why they'd
care exactly what data-type a txn-id "really" is... they'll just be
treating txn-ids like opaque blobs anyway.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: DB and Node sanity.
Posted by "Glenn A. Thompson" <gt...@cdr.net>.
Hey
> - The DB backend can/should impose a key width limit. In the
> unlikely event that some repos actually bumps up against the
> limit, it's no big deal to resize.
>
Cool!
>
> - But the in-memory form of the keys should not impose any limit.
> That way, no code needs to change just because someone expanded
> their backend's width.
>
> (Hmmm, you know, taken out of context by a non-programmer, that last
> sentence could really sound odd.)
>
Even to a programmer:-)
gat
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: DB and Node sanity.
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
cmpilato@collab.net writes:
> Regardless of what is chosen, we will not allow a schema in which the
> keys can grow without bound (heh...though in this case, we sure wish
> we could easily let them grow forever :-). If we choose a 64-bit
> integer, you can simply make sure to set your table width to however
> many characters needed to hold the largest collection of those things.
Ah, okay, now I think I know how to make the distinction I've been
trying to make:
- The DB backend can/should impose a key width limit. In the
unlikely event that some repos actually bumps up against the
limit, it's no big deal to resize.
- But the in-memory form of the keys should not impose any limit.
That way, no code needs to change just because someone expanded
their backend's width.
(Hmmm, you know, taken out of context by a non-programmer, that last
sentence could really sound odd.)
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: DB and Node sanity.
Posted by cm...@collab.net.
"Glenn A. Thompson" <gt...@cdr.net> writes:
> Folks:
>
> Will whatever Node sanity you arrive at be three separate thingy's?
> Or all one blob sort of thing? I'm hoping for three separate
> thing-a-ma-bobs or (do-hickys:-). When you guys mention space
> conservation in your discussions, I get a little squeamish. SQL DBs
> piss disk away like beer at a football game. Am I going to get beat
> about the head and shoulder for their wastefulness? I was planing
> on keeping this ID as a number in the SQL Tables. But I don't want
> to argue about it. I will do strings if you guys want me to. One
> thing I do prefer is that I keep any (ID/or potentially indexed sort
> of thing) a fixed length if possible. Some DBs have the ability to
> widen a column on the fly if needed or you can always export then
> import to the wider columns.
Regardless of what is chosen, we will not allow a schema in which the
keys can grow without bound (heh...though in this case, we sure wish
we could easily let them grow forever :-). If we choose a 64-bit
integer, you can simply make sure to set your table width to however
many characters needed to hold the largest collection of those things.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
DB and Node sanity.
Posted by "Glenn A. Thompson" <gt...@cdr.net>.
Folks:
Will whatever Node sanity you arrive at be three separate thingy's? Or all one
blob sort of thing? I'm hoping for three separate thing-a-ma-bobs or
(do-hickys:-). When you guys mention space conservation in your discussions, I
get a little squeamish. SQL DBs piss disk away like beer at a football game. Am
I going to get beat about the head and shoulder for their wastefulness? I was
planing on keeping this ID as a number in the SQL Tables. But I don't want to
argue about it. I will do strings if you guys want me to. One thing I do prefer
is that I keep any (ID/or potentially indexed sort of thing) a fixed length if
possible. Some DBs have the ability to widen a column on the fly if needed or you
can always export then import to the wider columns.
I've been getting my DB dev environment sorted out. I have resurrected (Twice,
damn disk drives) a Sparc Ultra10 with Ultra2 SCSI drives running Oracle 9i and
MySQL 4.0.1. I may put up PostGres as well. Anyhoo. It will serve only as my DB
box.
I want to give ODBC a run around the block. I've never used it before but there
seems to be many recent improvements under 3.51.x. I've always used PRO C or
MySql's native interface from my C code. However, the bulk of my DB usage has
been from Java (JDBC) and Perl (DBI). ODBC feels more like them to me. Plus the
Management layer may come in handy. Given all the heated debates over performance
I thought I would give the list an oportunity to veto ODBC before I waste any
time evaluating it. My mind is hardly made up. I thought some of the Windows
guys might want to way in. I've always understoood them to be the biggest users
of ODBC.
I have to run. I'll check back to the list later tonight.
Thanks,
gat
Karl Fogel wrote:
> Greg Stein <gs...@lyra.org> writes:
> > > Also, Greg, you argued for txn keys to be base36 when you were here in
> > > Chicago last. Well, not "argued", because we all agreed with you, but
> > > you were in fact the person who emphasized it first.
> >
> > Wha??!?! Um, no. If I *really* did, then I was smoking crack because that
> > certainly isn't what we want to build.
>
> Oh -- hunh, I do remember it pretty clearly, but since you don't
> really hold that position, it probably means I misunderstood what you
> were saying at the time.
>
> > Base-36 (or your suggestion for base-62) is way beyond the insane.
> > Completely non-standard in all respects, none of the speed Brane was talking
> > about with base-16 encoding, and still obfuscates the underlying integer
> > that these keys are derived from.
>
> Base 36 is what I'd like to do; I've already presented the reasons.
> Calling it "way beyond insane" doesn't add any substance to the
> discussion.
>
> > Work out the math. If you manage to *sustain* one per second, you've got 136
> > years worth (unsigned 32-bit number). You'll definitely burst at times, but
> > a sustained rate of one per second, year after year, is absolutely amazing.
> > Running out is simply not going to happen. If there is any possible scenario
> > where we believe that 4 billion transactions will actually occur, then hell:
> > make it an apr_uint64_t.
>
> This is not "amazing" at all. Not only humans use repositories; other
> programs will start using them too. And Moore's Law still held last
> time I checked. Why not make *sure* the problem is solved, once and
> for all? It's trivial for us to do -- I know, because I did it for
> txns already and it was no effort -- it doesn't affect performance in
> any meaningful way, and (for me at least, don't know about others)
> improves maintainability by not implying ordering when there is no
> ordering going on, and by making IDs a bit more readable.
>
> When the designers of IPv6 considered network address allocation
> (which was already supposed to be more than enough at 32 bits, years
> ago when IPv4 was designed), they jumped all the way to 128 bits,
> wisely skipping 64. They realized that the *rate* of consumption can
> increase unexpectedly -- since it already happened once, as everyone
> and their toaster started wanting an IP address. (Nevertheless,
> within our lifetimes I expect to see debates about how to handle the
> impending exhaustion of 128 bits.)
>
> +1 on base36 with `const char *'; -1 on integers whatever the
> marshalling.
>
> I believe we've both presented our complete arguments for and against.
> If you have something new and constructive to add, please do! FUD
> like "way beyond insane" and "completely non-standard in all respects"
> doesn't count :-).
>
> -K
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
> For additional commands, e-mail: dev-help@subversion.tigris.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by "Kirby C. Bohling" <kb...@birddog.com>.
Karl Fogel wrote:
> Greg Stein <gs...@lyra.org> writes:
<snip>
>>Work out the math. If you manage to *sustain* one per second, you've got 136
>>years worth (unsigned 32-bit number). You'll definitely burst at times, but
>>a sustained rate of one per second, year after year, is absolutely amazing.
>>Running out is simply not going to happen. If there is any possible scenario
>>where we believe that 4 billion transactions will actually occur, then hell:
>>make it an apr_uint64_t.
>>
>
> This is not "amazing" at all. Not only humans use repositories; other
> programs will start using them too. And Moore's Law still held last
> time I checked. Why not make *sure* the problem is solved, once and
> for all? It's trivial for us to do -- I know, because I did it for
> txns already and it was no effort -- it doesn't affect performance in
> any meaningful way, and (for me at least, don't know about others)
> improves maintainability by not implying ordering when there is no
> ordering going on, and by making IDs a bit more readable.
>
> When the designers of IPv6 considered network address allocation
> (which was already supposed to be more than enough at 32 bits, years
> ago when IPv4 was designed), they jumped all the way to 128 bits,
> wisely skipping 64. They realized that the *rate* of consumption can
> increase unexpectedly -- since it already happened once, as everyone
> and their toaster started wanting an IP address. (Nevertheless,
> within our lifetimes I expect to see debates about how to handle the
> impending exhaustion of 128 bits.)
>
128 bit is only limiting if there is only one of them in the world.
Subversion should have multiple repositories in the world, so I think
that IPv6 analogy is flawed.
Personally, I'd make the convention be a completely opaque type that is
based on the backend used for storing it. Define the operations it must
do explicitly, and carry the opaque type around with you everywhere you
go . Make the operations based off of a vtable they point to internally
(like is done with the fs/editor/wc and everything else in subversion).
For BDB 4.0.14 a 48 bit number ( 256TB --> 2^48 addressable bytes)
will do the job (if the average thing takes 64K on disk then a 32bit
type would do it fine). It is completely unneccessary to have anything
larger for BDB 4.0.14. If BDB 5.0 supports a bigger size, write a new
opaque type which should take a couple hours of work which should be a
drop in the bucket in comparision to all the other stuff that has to go
on to make that work.
Make the ability to convert to/from a known format like base36 or base10
const char* a requirement for the ability to convert from one backend to
another, and for doing a dump. The only serious problem then is doing
conversions from one repository to another might be slow because of the
required conversion.
It should however be an uncommon operation as repositories that are
related will likely use the same backend. You can also optimize the
problem significantly for the common case by using a lookup table for
hand tuned conversions from a->b, and hard code a->a to be a nop. Using
a type that is extremely computer efficient would probably make up for
the function call to realize it is a nop. That only becomes an issue
when you have cross repository functionality. I didn't think that
exists just yet, could be wrong.
Thus allowing the backend to efficiently store the number in the most
native and unlimited format allowable for that storage mechanism. Every
backend you'll ever find will be written by somebody who thinks like
Greg Stein. Well, every back end worth using that is *grin*.
Using a type that has no limitations on it leads to problems being
unbounded. That really bothers Database guys because having unbounded
size for the keys means no performance guaruntees, which leads to low
sales volumes which means not eating. It is just a fact that all
databases are limited in size because of all the speed it buys them, and
makes them sell like hot cakes.
I can make an argument that a 64bit number is just enough. 64 bit is so
incredibly huge that you can check in the PC counter after every
instruction on my machine for ~250 years and not run out of revisions.
So when you can check in a revision in the current CPU cycle time you
have about 250 years until your in serious trouble. That and the
largest database I know of (Oracle8i) only supports 2^80 rows in the
database which is pretty stinking large and Oracle considers solving
problems for the largest companies and governments in the world. They
probably have a good handle on how large is necessary. If you support
128bit now, you'll be ahead of the single largest database vendor on the
planet. Okay IBM might be larger provider, and DB2 might have a larger
key. Either way, 64bit is enough, and if it is truely bothersome to
have it be limited, you can make it so it is specific to the storage
mechanism which would obviously be good enough.
Kirby
> +1 on base36 with `const char *'; -1 on integers whatever the
> marshalling.
>
> I believe we've both presented our complete arguments for and against.
> If you have something new and constructive to add, please do! FUD
> like "way beyond insane" and "completely non-standard in all respects"
> doesn't count :-).
>
> -K
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
> For additional commands, e-mail: dev-help@subversion.tigris.org
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
Greg Stein <gs...@lyra.org> writes:
> > Also, Greg, you argued for txn keys to be base36 when you were here in
> > Chicago last. Well, not "argued", because we all agreed with you, but
> > you were in fact the person who emphasized it first.
>
> Wha??!?! Um, no. If I *really* did, then I was smoking crack because that
> certainly isn't what we want to build.
Oh -- hunh, I do remember it pretty clearly, but since you don't
really hold that position, it probably means I misunderstood what you
were saying at the time.
> Base-36 (or your suggestion for base-62) is way beyond the insane.
> Completely non-standard in all respects, none of the speed Brane was talking
> about with base-16 encoding, and still obfuscates the underlying integer
> that these keys are derived from.
Base 36 is what I'd like to do; I've already presented the reasons.
Calling it "way beyond insane" doesn't add any substance to the
discussion.
> Work out the math. If you manage to *sustain* one per second, you've got 136
> years worth (unsigned 32-bit number). You'll definitely burst at times, but
> a sustained rate of one per second, year after year, is absolutely amazing.
> Running out is simply not going to happen. If there is any possible scenario
> where we believe that 4 billion transactions will actually occur, then hell:
> make it an apr_uint64_t.
This is not "amazing" at all. Not only humans use repositories; other
programs will start using them too. And Moore's Law still held last
time I checked. Why not make *sure* the problem is solved, once and
for all? It's trivial for us to do -- I know, because I did it for
txns already and it was no effort -- it doesn't affect performance in
any meaningful way, and (for me at least, don't know about others)
improves maintainability by not implying ordering when there is no
ordering going on, and by making IDs a bit more readable.
When the designers of IPv6 considered network address allocation
(which was already supposed to be more than enough at 32 bits, years
ago when IPv4 was designed), they jumped all the way to 128 bits,
wisely skipping 64. They realized that the *rate* of consumption can
increase unexpectedly -- since it already happened once, as everyone
and their toaster started wanting an IP address. (Nevertheless,
within our lifetimes I expect to see debates about how to handle the
impending exhaustion of 128 bits.)
+1 on base36 with `const char *'; -1 on integers whatever the
marshalling.
I believe we've both presented our complete arguments for and against.
If you have something new and constructive to add, please do! FUD
like "way beyond insane" and "completely non-standard in all respects"
doesn't count :-).
-K
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Greg Stein <gs...@lyra.org>.
On Fri, May 10, 2002 at 11:43:00PM -0500, Karl Fogel wrote:
> Greg Stein <gs...@lyra.org> writes:
> > struct svn_fs_id_t
> > {
> > apr_uint32_t nodeID;
> > apr_uint32_t copyID;
> > apr_uint32_t txnID;
> > };
>
> Also, Greg, you argued for txn keys to be base36 when you were here in
> Chicago last. Well, not "argued", because we all agreed with you, but
> you were in fact the person who emphasized it first.
Wha??!?! Um, no. If I *really* did, then I was smoking crack because that
certainly isn't what we want to build.
Base-36 (or your suggestion for base-62) is way beyond the insane.
Completely non-standard in all respects, none of the speed Brane was talking
about with base-16 encoding, and still obfuscates the underlying integer
that these keys are derived from.
> The reason was that more txns get created than stay around
> permanently. We use them for updates, also failed commits (perhaps
> due to conflict) happen. A busy repository will eventually make it
> into high numbers. Running out of integers is a danger, and anyway
> the numbers will start getting long sooner rather than later.
Work out the math. If you manage to *sustain* one per second, you've got 136
years worth (unsigned 32-bit number). You'll definitely burst at times, but
a sustained rate of one per second, year after year, is absolutely amazing.
Running out is simply not going to happen. If there is any possible scenario
where we believe that 4 billion transactions will actually occur, then hell:
make it an apr_uint64_t.
But when you've got these things in memory, they should be integers. Plain
and simple. I'm a bit less concerned about their marshalling into the BDB
records; I think they should be base-10 to simplify everything, but I can
see Brane's position about using base-16 as a quick way to (un)marshal
between memory and BDB.
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
Greg Stein <gs...@lyra.org> writes:
> struct svn_fs_id_t
> {
> apr_uint32_t nodeID;
> apr_uint32_t copyID;
> apr_uint32_t txnID;
> };
Also, Greg, you argued for txn keys to be base36 when you were here in
Chicago last. Well, not "argued", because we all agreed with you, but
you were in fact the person who emphasized it first.
The reason was that more txns get created than stay around
permanently. We use them for updates, also failed commits (perhaps
due to conflict) happen. A busy repository will eventually make it
into high numbers. Running out of integers is a danger, and anyway
the numbers will start getting long sooner rather than later.
-K
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Greg Stein <gs...@lyra.org>.
On Fri, May 10, 2002 at 01:39:03PM -0700, Greg Stein wrote:
> On Fri, May 10, 2002 at 03:07:31PM -0500, Karl Fogel wrote:
>...
> > - Integers imply ordering. But we're not comparing these keys for
> > ordering (there's one rare circumstance where we could do so with
> > copyIDs, but we may not even use it). We're using them as unique
> > keys, period. To use integers would be misdocumenting.
>
> But they *are* integers. That is the point behind the "next-key" stuff. An
> integer sits in there, and it gets incremented. Applying a transformation to
> that value is obscuring its origin.
And I'll further point out that the new ID structure (in id.h) would be:
struct svn_fs_id_t
{
apr_uint32_t nodeID;
apr_uint32_t copyID;
apr_uint32_t txnID;
};
To put strings in there will just screw up the FS. All of your comparisons
would become more difficult and take longer.
>...
> > I also feel more comfortable knowing that the length grows so much
> > more slowly, but I think that's probably just superstition.
> > Nonetheless, it can't *hurt*, right :-)?
>
> Yes, that is superstition. The different between itoa() and a base64
> encoding is three digits once you finally reach the billion mark. Down in
> the first hundred thousand, you're talking three versus five digits. That
> length difference is so negligible from the system standpoint, that it
> shouldn't even be considered :-)
Oh. Using base64 (strings) would be a negative system perf change, given the
ID comparison pointed out above.
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
Greg Stein <gs...@lyra.org> writes:
> But they *are* integers. That is the point behind the "next-key" stuff. An
> integer sits in there, and it gets incremented. Applying a transformation to
> that value is obscuring its origin.
>
> The base64 values also have an ordering (ever hear of strcmp() ?). So this
> point doesn't really seem to apply.
Um, yes, any two strings have an ordering, if you assign values to
their symbols. But we're not *using* the ordering, that's the
important thing.
(The fact that we use ordering trivially as part of the process of
generating a new unique ID is irrelevant. Call it the "next" key is
misleading: it's just a "new" key, and the method by which we
guarantee its uniqueness doesn't need to infect the rest of the code.)
> > - As a developer debugging the code, it's easier for me to
> > recognize and remember shorter strings in an alphabet with more
> > symbols, than longer strings in an alphabet with fewer symbols.
> > Long strings of numbers start to look all alike pretty quickly
> > (at least to me).
>
> That is FUD, too. "abcdef" and "abcdeg" look awfully the same, too.
Nah, calling it FUD is FUD :-). My statement was personal, and
completely accurate. If it's not true for you, that's great -- I
never said it was.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Greg Stein <gs...@lyra.org>.
On Fri, May 10, 2002 at 03:07:31PM -0500, Karl Fogel wrote:
> cmpilato@collab.net writes:
> > Seriously, who cares? With the exception of the revisions, these
> > things are never anything bat const char * values, so they can be whatever
> > we want (as long as we can definitively answer the is-greater-than
> > question). Whatever, I'm not personally sold on either way.
>
> I care a bit -- I'd prefer base64, for two reasons:
>
> - Integers imply ordering. But we're not comparing these keys for
> ordering (there's one rare circumstance where we could do so with
> copyIDs, but we may not even use it). We're using them as unique
> keys, period. To use integers would be misdocumenting.
But they *are* integers. That is the point behind the "next-key" stuff. An
integer sits in there, and it gets incremented. Applying a transformation to
that value is obscuring its origin.
The base64 values also have an ordering (ever hear of strcmp() ?). So this
point doesn't really seem to apply.
We've got unordered keys. Period. You don't need to obfuscate their origin
in an attempt to "enforce" the concept of unorderedness.
[ and when moving to SQL, the replacement for "next-key" will (almost
always (impl. dependent)) generate integers ]
> - As a developer debugging the code, it's easier for me to
> recognize and remember shorter strings in an alphabet with more
> symbols, than longer strings in an alphabet with fewer symbols.
> Long strings of numbers start to look all alike pretty quickly
> (at least to me).
That is FUD, too. "abcdef" and "abcdeg" look awfully the same, too.
> I also feel more comfortable knowing that the length grows so much
> more slowly, but I think that's probably just superstition.
> Nonetheless, it can't *hurt*, right :-)?
Yes, that is superstition. The different between itoa() and a base64
encoding is three digits once you finally reach the billion mark. Down in
the first hundred thousand, you're talking three versus five digits. That
length difference is so negligible from the system standpoint, that it
shouldn't even be considered :-)
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
cmpilato@collab.net writes:
> Seriously, who cares? With the exception of the revisions, these
> things are never anything bat const char * values, so they can be whatever
> we want (as long as we can definitively answer the is-greater-than
> question). Whatever, I'm not personally sold on either way.
I care a bit -- I'd prefer base64, for two reasons:
- Integers imply ordering. But we're not comparing these keys for
ordering (there's one rare circumstance where we could do so with
copyIDs, but we may not even use it). We're using them as unique
keys, period. To use integers would be misdocumenting.
- As a developer debugging the code, it's easier for me to
recognize and remember shorter strings in an alphabet with more
symbols, than longer strings in an alphabet with fewer symbols.
Long strings of numbers start to look all alike pretty quickly
(at least to me).
I also feel more comfortable knowing that the length grows so much
more slowly, but I think that's probably just superstition.
Nonetheless, it can't *hurt*, right :-)?
-K
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by cm...@collab.net.
Karl Fogel <kf...@newton.ch.collab.net> writes:
> cmpilato@collab.net writes:
> > Seriously, who cares? With the exception of the revisions, these
> > things are never anything bat const char * values, so they can be whatever
> > we want (as long as we can definitively answer the is-greater-than
> > question). Whatever, I'm not personally sold on either way.
>
> When do we ask the is-greater-than question on anything but revision
> numbers?
We don't (not that I know of, anyways), but I assumed that having some
sort of order made it easier for the database to dole out unique keys,
to keep ordered indices, etc.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
cmpilato@collab.net writes:
> Seriously, who cares? With the exception of the revisions, these
> things are never anything bat const char * values, so they can be whatever
> we want (as long as we can definitively answer the is-greater-than
> question). Whatever, I'm not personally sold on either way.
When do we ask the is-greater-than question on anything but revision
numbers?
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by "Glenn A. Thompson" <gt...@cdr.net>.
Hey:
This whole thread has been really educational for me. Thanks to all who contributed
to it.
> > Seriously, who cares? With the exception of the revisions, these
> > things are never anything bat const char * values, so they can be whatever
> > we want (as long as we can definitively answer the is-greater-than
> > question). Whatever, I'm not personally sold on either way.
>
> I care. My point is: why obscure the integers with a base64 encoding?
>
> If you do, then you need the comments. If you leave them as plain integers,
> then you don't need them :-)
>
> Yes, they can be arbitrary strings, but why? "Just because we can, doesn't
> mean we should."
>
I agree with gstein here. The concepts in this code are tough enough (for feebs
like myself) without obfuscated integers.
gat
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Greg Stein <gs...@lyra.org>.
On Thu, May 09, 2002 at 08:49:44PM -0500, cmpilato@collab.net wrote:
> Greg Stein <gs...@lyra.org> writes:
>
> > Why? Why convert them to base64? Why not keep them *all* as integers? You're
> > working with integers, so keep them that way; otherwise, people will wonder
> > WTF those weird character sequence are, go to dig, and then go "oh. that's
> > it? just integers. damn them for wasting my time."
>
> Oh that's right, you're the guy that doesn't believe in using inline
> comments in the code ... ;-)
>
> Seriously, who cares? With the exception of the revisions, these
> things are never anything bat const char * values, so they can be whatever
> we want (as long as we can definitively answer the is-greater-than
> question). Whatever, I'm not personally sold on either way.
I care. My point is: why obscure the integers with a base64 encoding?
If you do, then you need the comments. If you leave them as plain integers,
then you don't need them :-)
Yes, they can be arbitrary strings, but why? "Just because we can, doesn't
mean we should."
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by cm...@collab.net.
Greg Stein <gs...@lyra.org> writes:
> Why? Why convert them to base64? Why not keep them *all* as integers? You're
> working with integers, so keep them that way; otherwise, people will wonder
> WTF those weird character sequence are, go to dig, and then go "oh. that's
> it? just integers. damn them for wasting my time."
Oh that's right, you're the guy that doesn't believe in using inline
comments in the code ... ;-)
Seriously, who cares? With the exception of the revisions, these
things are never anything bat const char * values, so they can be whatever
we want (as long as we can definitively answer the is-greater-than
question). Whatever, I'm not personally sold on either way.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Greg Stein <gs...@lyra.org>.
On Thu, May 09, 2002 at 07:50:38PM -0500, cmpilato@collab.net wrote:
>...
> > Oh... and why bother with base64? To keep the keys shorter in the DB? That
> > seems rather obscure. When debugging, I think it will be much nicer for the
> > humans to just use a plain old integer.
>
> Consistency with the representations and strings tables would be my
> reason. The revision keys are the only user-visible keys (node keys,
> rep keys, strings keys, and txn ids are not), so those can stay
> numeric. In fact, we could make the nodeIDs be base64 as well, now
> that I think about it.
Why? Why convert them to base64? Why not keep them *all* as integers? You're
working with integers, so keep them that way; otherwise, people will wonder
WTF those weird character sequence are, go to dig, and then go "oh. that's
it? just integers. damn them for wasting my time."
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by cm...@collab.net.
Greg Stein <gs...@lyra.org> writes:
> On Thu, May 09, 2002 at 05:34:11PM -0500, Karl Fogel wrote:
> >...
> > <root>
> > / | \
> > / | \
> > / | \
> > A(3.m) B Y(3.p.jfb)
> > / \ | / \
> > foo bar qux foo bar
> > (5.abc) (5.abc)
> > : :
> > : :
> > (5.ejk) (b.mht.jfb)
> > : :
> > : :
> > (5.xyz) (b.uuu.jfb)
> > : :
> > : :
> > (5.r2d2) (b.2pz.jfb)
> > : :
> > : :
> > (5.c3po) (b.rdt.jfb)
> >...
> > During this walk, you can always tell when you encounter a node that
> > results from a copy, because the copyID portion will either change or
> > disappear entirely. When this happens, you know one of two things is
> > true: either the previous node in the walk was the top of a copied
> > tree, or *this* node (the one with the different copyID) was one of
> > the unchanged nodes down inside a copied tree.
>
> Why do we care about the status of the child node? Or, to put another way,
> why do we generate a new copyID? Isn't it sufficient to just change the
> NodeID and leave it at that?
I'm thinking of `svn log' where the user wants to know changes that
happened to a given node as it currently sits in the directory
heirarchy, and therefore doesn't want to step backward across "copy
history". That is, "show me all the changes to /branches/my_branch,
but not all the history prior to the copy I made to create that
branch."
> Oh... and why bother with base64? To keep the keys shorter in the DB? That
> seems rather obscure. When debugging, I think it will be much nicer for the
> humans to just use a plain old integer.
Consistency with the representations and strings tables would be my
reason. The revision keys are the only user-visible keys (node keys,
rep keys, strings keys, and txn ids are not), so those can stay
numeric. In fact, we could make the nodeIDs be base64 as well, now
that I think about it.
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Greg Stein <gs...@lyra.org>.
On Thu, May 09, 2002 at 05:34:11PM -0500, Karl Fogel wrote:
>...
> <root>
> / | \
> / | \
> / | \
> A(3.m) B Y(3.p.jfb)
> / \ | / \
> foo bar qux foo bar
> (5.abc) (5.abc)
> : :
> : :
> (5.ejk) (b.mht.jfb)
> : :
> : :
> (5.xyz) (b.uuu.jfb)
> : :
> : :
> (5.r2d2) (b.2pz.jfb)
> : :
> : :
> (5.c3po) (b.rdt.jfb)
>...
> During this walk, you can always tell when you encounter a node that
> results from a copy, because the copyID portion will either change or
> disappear entirely. When this happens, you know one of two things is
> true: either the previous node in the walk was the top of a copied
> tree, or *this* node (the one with the different copyID) was one of
> the unchanged nodes down inside a copied tree.
Why do we care about the status of the child node? Or, to put another way,
why do we generate a new copyID? Isn't it sufficient to just change the
NodeID and leave it at that?
Ah... you use that '.jfb' and the copies table to relate the node to 5.*,
right?
>...
Oh... and why bother with base64? To keep the keys shorter in the DB? That
seems rather obscure. When debugging, I think it will be much nicer for the
humans to just use a plain old integer.
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by cm...@collab.net.
Greg Stein <gs...@lyra.org> writes:
> On Thu, May 09, 2002 at 05:34:11PM -0500, Karl Fogel wrote:
> >...
> > <root>
> > / | \
> > / | \
> > / | \
> > A(3.m) B Y(3.p.jfb)
> > / \ | / \
> > foo bar qux foo bar
> > (5.abc) (5.abc)
> > : :
> > : :
> > (5.ejk) (b.mht.jfb)
> > : :
> > : :
> > (5.xyz) (b.uuu.jfb)
> > : :
> > : :
> > (5.r2d2) (b.2pz.jfb)
> > : :
> > : :
> > (5.c3po) (b.rdt.jfb)
>
> On AIM, Bill pointed the 'bar' under 'Y' is wrong. The NodeID should not
> have changed. Those nodes should be 5.mht.jfb, 5.uuu.jfb, etc
Oops, you're right. Just a mistake in the diagram, though, not the
schema. "It's the thought that counts", right? :-)
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Greg Stein <gs...@lyra.org>.
On Thu, May 09, 2002 at 05:34:11PM -0500, Karl Fogel wrote:
>...
> <root>
> / | \
> / | \
> / | \
> A(3.m) B Y(3.p.jfb)
> / \ | / \
> foo bar qux foo bar
> (5.abc) (5.abc)
> : :
> : :
> (5.ejk) (b.mht.jfb)
> : :
> : :
> (5.xyz) (b.uuu.jfb)
> : :
> : :
> (5.r2d2) (b.2pz.jfb)
> : :
> : :
> (5.c3po) (b.rdt.jfb)
On AIM, Bill pointed the 'bar' under 'Y' is wrong. The NodeID should not
have changed. Those nodes should be 5.mht.jfb, 5.uuu.jfb, etc
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
Branko Čibej <br...@xbc.nu> writes:
> Just two comments from me; Bill, Mike and I hashed them out on #svn:
Incidentally, excuse me for neglecting to thank you (Brane) along with
Bill for spending so much time hashing this stuff out. It's just that
I wasn't on IRC for those discussions; but I did hear about them. Oh
yes. I certainly _did_ _hear_ about them :-).
> * Give the root directory in revision 0 and initial copy id of 0.
> This means that:
> o You have a nice, handy value for initializing the copies table
> o Every node will get a copy id, making node numbering more
> consistent and incidentally promoting branches to
> first-class status
+1
> * Swap the txn and copy id in the key, making it "node.copy.txn".
> This will cause related keys to be clustered closer together,
> making relatedness searches faster.
+1 again.
-K
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
RE: Re: Maintaining NodeID sanity
Posted by Bill Tutt <ra...@lyra.org>.
+1 for me too. Woo! Let the partying, and Mike's suffering begin! ;)
Bill
----
Do you want a dangerous fugitive staying in your flat?
No.
Well, don't upset him and he'll be a nice fugitive staying in your flat.
> -----Original Message-----
> From: cmpilato@collab.net [mailto:cmpilato@collab.net]
> Sent: Friday, May 10, 2002 10:05 AM
> To: Branko Cibej
> Cc: Karl Fogel; Bill Tutt; Subversion Dev list
> Subject: Re: Maintaining NodeID sanity
>
> =?UTF-8?B?QnJhbmtvIMSMaWJlag==?= <br...@xbc.nu> writes:
>
> > Just two comments from me; Bill, Mike and I hashed them out on #svn:
> >
> > * Give the root directory in revision 0 and initial copy id of
0.
> > This means that:
> > o You have a nice, handy value for initializing the copies
> table
> > o Every node will get a copy id, making node numbering
more
> > consistent and incidentally promoting branches to
> > first-class status
> > * Swap the txn and copy id in the key, making it
"node.copy.txn".
> > This will cause related keys to be clustered closer together,
> > making relatedness searches faster.
>
> +1. The coding begins (soon).
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
> For additional commands, e-mail: dev-help@subversion.tigris.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by cm...@collab.net.
=?UTF-8?B?QnJhbmtvIMSMaWJlag==?= <br...@xbc.nu> writes:
> Just two comments from me; Bill, Mike and I hashed them out on #svn:
>
> * Give the root directory in revision 0 and initial copy id of 0.
> This means that:
> o You have a nice, handy value for initializing the copies table
> o Every node will get a copy id, making node numbering more
> consistent and incidentally promoting branches to
> first-class status
> * Swap the txn and copy id in the key, making it "node.copy.txn".
> This will cause related keys to be clustered closer together,
> making relatedness searches faster.
+1. The coding begins (soon).
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Branko Čibej <br...@xbc.nu>.
Karl Fogel wrote:
>Thanks for the clarifying mail, Bill. It helped a lot.
>
>Below, Mike and I (we're writing this together) will respond briefly
>to a couple of the things you said, and then describe the proposal
>we've worked out. We *think* it's the same thing you've been
>proposing all along, we just want to describe it in our own words to
>make sure.
>
Just two comments from me; Bill, Mike and I hashed them out on #svn:
* Give the root directory in revision 0 and initial copy id of 0.
This means that:
o You have a nice, handy value for initializing the copies table
o Every node will get a copy id, making node numbering more
consistent and incidentally promoting branches to
first-class status
* Swap the txn and copy id in the key, making it "node.copy.txn".
This will cause related keys to be clustered closer together,
making relatedness searches faster.
All in all, it looks like we have a sane design now. :-)
/me dances a jig for sheer glee
--
Brane Čibej <br...@xbc.nu> http://www.xbc.nu/brane/
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
Thanks for the clarifying mail, Bill. It helped a lot.
Below, Mike and I (we're writing this together) will respond briefly
to a couple of the things you said, and then describe the proposal
we've worked out. We *think* it's the same thing you've been
proposing all along, we just want to describe it in our own words to
make sure.
> Relatedness: Needs to be very fast. O(1)
> Immediate Predecessor: Needs to be very fast, but could be slightly
> slower than the Relatedness check if necessary. O(1)
> Ancestry check: Needs to be efficient, but by necessity is going to be
> more expensive then the immediate predecessor check. O(n)
+1 on all of these.
Note that the ancestry check is really only used during merge(), that
is, during commits. If entry "somedir/blah" has NodeID Y in the txn
being committed, and NodeID X in head tree being merged into that txn,
then we need to make sure X is an ancestor of Y, so that when the
commit replaces X with Y, we know we're not losing any history.
(You probably already knew this, I'm just describing it for my own
sanity and that of others on this list.)
Therefore, we think we can get away with storing the ancestors in a
distributed fashion, as a chain: each node knows its immediate
predecessor (or "precessors", in the future), and you walk back until
you have your answer. In real life, we won't usually be walking back
too far, and, as we'll describe below, there's a technique by which we
can bound the search even further.
As you pointed out, we *could* store a node's full ancestry set for
each revision of that node, in a separate table or something. If
performance demands that, we will, but we're guessing it's not needed.
(And, as we just discussed on the phone, some of tree.c:merge() can be
made more efficient, to minimize the impact of an O(N) ancestry
check.)
> However, the current is_related() check is implemented by performing an
> Ancestry check. So, the current performance of is_related() is currently
> O(n) as opposed to what it hopefully should be: O(1).
Yup, this becomes O(1) in the new proposal.
Okay, now we're going to describe the plan we've come up with, which
will sound suspiciously like the plan *you* came up with. Funny
thing, that.
Note:
- We're describing this in terms of the BDB implementation, for the
most part. Translate as necessary.
- This proposal supports one copy (a.k.a. branch) operation. You
can call it anything you want: "copy", "branch", "split",
"pumpkin", whatever. We're calling it "copy" :-). It is the SCM
branch operation.
Here we go...
First, a node's key consists of three parts
nodeID.txnID[.copyID]
This is a bit implementation-specific, but you get the idea. The
"txnID" is just a unique identifier, but we happened to inherit it
from the fs txn, and we needed a name for that portion, so... :-)
Also, the copyID could live in the node's value instead of in its key;
it doesn't really matter which way we go on that.
There are no more mutability flags -- mutability is determined by
examining whether the node key's txnID matches the txn in question.
Therefore, there is no stabilization walk at commit time.
When we commit a change to a node, the nodeID and copyID stay the
same, only the txnID changes. The new txnID is not necessarily
greater than the old one (sometimes txns get committed out of order!),
but anyway it's different from the old txnID, and the same new txnID
is used for all other changes in that commit. A txnID is just a
unique string; in fact, we're going to use base64 probably.
After a commit, the txn record in the transactions table does not go
away; instead, it is updated so it now maps the txnID to the new
revision. This allows us to determine the revision a node was
committed in, in constant time, from the node's key.
Each new version of a node stores the node's predecessor (and does not
store copyform history). When node "5.fzb" is committed as a
successor to "5.qnr", the new node's value stores a reference to
"5.qnr".
What about copies?
As in the current fs, copies are shallow. The top of the copied tree
gets a new node, but the nodes below it are shared with the copy
source. The new node key keeps the same nodeID, but gets a new txnID,
and gets the next unique copyID (replacing the current copyID, if
any).
In the example below, we copy `A' to `Y'. Node keys for `A', `Y', and
`bar' are given in parentheses:
BEFORE THE COPY AFTER THE COPY
<root> <root>
/ | / | \
/ | / | \
/ | / | \
A(3.m) B A(3.m) B Y(3.p.jfb)
/ \ | / \ | / \
foo bar qux foo bar qux foo bar
(5.abc) (5.abc) (5.abc)
Let's flesh out the example with some commits under A and Y. To save
space, the colons represent time flow, not directory hierarchy --
imagine they're the Z axis coming out of the screen or something :-).
<root>
/ | \
/ | \
/ | \
A(3.m) B Y(3.p.jfb)
/ \ | / \
foo bar qux foo bar
(5.abc) (5.abc)
: :
: :
(5.ejk) (b.mht.jfb)
: :
: :
(5.xyz) (b.uuu.jfb)
: :
: :
(5.r2d2) (b.2pz.jfb)
: :
: :
(5.c3po) (b.rdt.jfb)
Let's see how easy it is to answer various questions in this system:
Obviously, is_related() is simple -- just check that the nodeID
portion is the same. You may not know if the relationship is cousins
vs ancestor/descendant, but you know whether or not they're related.
Asking is_predecessor(A,B) is also easy. Just fetch the predecessor
pointer from B and see if it's A.
Finding out what revisions a node changed in is proportional to the
number of changes the node has undergone: start at the node, walk back
through its predecessors, and for each txnID, look up the revision
number via the transactions table (as described earlier).
During this walk, you can always tell when you encounter a node that
results from a copy, because the copyID portion will either change or
disappear entirely. When this happens, you know one of two things is
true: either the previous node in the walk was the top of a copied
tree, or *this* node (the one with the different copyID) was one of
the unchanged nodes down inside a copied tree.
One might think "Oh, we'll distinguish between these cases by walking
up the parents of the node, and seeing if we eventually encounter the
old copyID in one of the parents. That would tell us that we're in
the second case. If we never encounter it, that tells us we're in the
first."
Not so fast, Spidey. We don't have parent pointers -- this is a
predecessor walk by node keys; we can't just walk up the parent path
like that. Fortunately, copyIDs are generated from a new `copies'
table, which maps unique copyIDs onto (REV COPY_DST_PATH
COPY_DST_NODEKEY). We look up the the rev/path for the old copyID,
convert it to a node key, and compare it to the node key we're
currently on. Voilà! Actually, we're not sure we'll store all of
those in the copies table, it may boil down to just the DST_NODEKEY or
just the other two, we'll see.
Writing those predecessor walk loops well is left as an exercise for
the reader (umm, more likely for the writers, heh), but you can see
that the necessary questions can be answered efficiently.
Note that, like txnIDs, copyIDs are just unique numbers. They may be
increasing monotonically in the `copies' table, but (due to the fact
that txn A may be started before txn B yet be committed afterwards)
it's quite possible that a higher copyID will appear in the revision
history before a lower one.
The one thing we can know is that a lower copyID can never be a
branchwise descendent of a lower copyID, since the lower one must have
been committed before any of its descendants txns were started, of
course. I'm not sure this minimal inference will ever be useful, but
anyway it's all we've got. Anyway, right now, we only ever need ask
if two copyIDs are equal -- we don't order them.
Okay, now what if A already had copied trees underneath it when we
copied it to Y? Suppose `bar' is down in one of those subdirectories?
(This is the question you just asked me on the phone, I'm repeating it
for the benefit of our radio audience.)
Then when we're committing on /Y/.../bar, we watch for copyIDs as we
walk down from root, like usual, and if we're in a copy underneath a
copy, we bubble down a _new_ copyID, distinct from both Y's and B's,
starting from that point. Justification: a branch of a branch is
still a branch, so it gets its own copyID.
At this point, I'm going to hand-wave on describing the
copy-under-copy behavior any further. I think the above is enough to
see that there are no insurmountable problems here, and that the
filesystem will now have node keys that [lazily] reflect actual
branching patterns. It's time to send this email :-). Unless you (or
anyone else) sees something alarming in this proposal, we're ready to
start on this.
Thanks for all your brainwork, it's been a real help!
-Karl (& Mike, who had to leave before this mail was finished)
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
RE: Re: Maintaining NodeID sanity
Posted by Bill Tutt <ra...@lyra.org>.
> From: Karl Fogel [mailto:kfogel@newton.ch.collab.net]
>
> Bill, I'm sort of losing track of exactly what's being proposed and
> what its goals are, at this point.
>
> A *really* helpful thing would be a fresh mail, that begins with a
> list of the problems you're trying to solve, including a small
> concrete example for each problem. These should only be problems that
> exist in the current filesystem implementation, not problems in prior
> incarnations of various proposals. Describe solutions only after the
> problems are presented.
>
Ok. That's good, your summary batched up the entire list of issues for
me, so I'll add examples. I've also re-ordered them a little bit to
restack their priorities as I see them.
> Just to be clear: I really, really appreciate that you're bringing
> years of db experience and schema design to bear on Subversion's
> problems, and want to benefit from this. But without clear
> communication, there's no way we'll grok the wonderful things going on
> in your head :-).
>
I totally hear that, I'm trying to get the concepts out of my head as
quickly as I can because I know that you want to do the work now, and I
do have to accomplish the work I get paid for, so please allow me to
continue apologizing from writing fragmented and disjointed emails.
*grovels before everyone to ask forgiveness for doing fragmented brain
dumps*
> Right now, the goals (as I understand them) of any new scheme are,
> roughly in order of priority:
>
> 1. To avoid unbounded NodeID length on certain directories
> See http://subversion.tigris.org/issues/show_bug.cgi?id=573
>
Indeed, this is the case. The issue explains the problem very precisely.
i.e.:
Revision histories are unbounded, and if our BDB Key in our NodeRevision
table is our entire revision history that makes our Key be unbound in
size, which is a very bad situation.
> 2. To eliminate the pre-commit stabilization walk that currently
> unsets the mutability flags of new nodes. This is the same as
> saying "make commit be a one-row insert" in RDB-speak, I guess.
>
I think this might be an orthogonal, but still very important issue.
It's more of a "make the SVN transaction commit BDB transaction shorter"
kind of a thing. The longer the transaction lasts, the more time you're
preventing other people from acquiring locks on the data you care about.
> 3. To preserve the ability to ask is_related(NodeA, NodeB) and
> is_ancestor(NodeA, NodeB) and get the answer in a reasonable
> amount of time; oh, and the same with get_predecessor(NodeA),
> except that there might be multiple predecessors and we need to
> think more on that.
>
Yep. We definitely want to preserve as much of the quickness of access
of the ancestry information as we can.
I'd also break the performance needs into a bunch of various categories,
and treat them separately.
Relatedness: Needs to be very fast. O(1)
Immediate Predecessor: Needs to be very fast, but could be slightly
slower than the Relatedness check if necessary. O(1)
Ancestry check: Needs to be efficient, but by necessity is going to be
more expensive then the immediate predecessor check. O(n)
In the face of multiple predecessors the Ancestry check performance item
might need to be broken down into two separate checks:
Direct Line Ancestry check: This is what we normally think of as Node
ancestry information. (i.e. the NodeID never varies at all)
This should needs to execute just as quickly as the Ancestry check
defined above.
Unbounded Ancestry check:
An Unbounded Ancestry check looks up each possible predecessor's
ancestry chain in addition to the direct line ancestry predecessors.
This kind of check is very expensive, and should be avoided as much as
possible.
Currently all of the above checks (except for Unbounded Ancestry Checks
which aren't yet possible) are very easy to calculate since the
NodeRevisionID embeds all of the necessary information and we always
have the key of our BDB row very available and handy.
However, the current is_related() check is implemented by performing an
Ancestry check. So, the current performance of is_related() is currently
O(n) as opposed to what it hopefully should be: O(1).
The is_related(NodeA, NodeB) check is just as expensive with just
(NodeID, ChangeSetID) as the BDB key for a NodeChange as explained in
more detail in the response to issue #4.
The is_related() check with a (NodeID, BranchID, ChangeSetID) key
suddenly becomes O(1) since NodeIDs have been stabilized.
> 4. To avoid the silly non-determistic migration of NodeID portions
> depending on which side of a copy gets modified first. Think of
> this as a maintainability fix -- we need things to be
> predictable.
>
This is definitely an issue. Analyzing and generating reports on the
repository is much easier to accomplish when NodeIDs function in a
deterministic manner. Having a stable NodeID also allows us to have a
much cheaper is_related() check, which as I explained above is very
important for performance.
i.e. it prevents the following weird and counter-intuitive NodeID
assignments:
Prexisting state:
/foo/main (NodeIDMain, ChangeSetIDMain)
/foo/main/A (NodeIDA, ChangeSetIDA)
The user performs: "svn cp /foo/main /foo/alt"
This produces:
/foo/alt (NodeID alt, ChangeSetAlt)
Now there are two possibilities of what can occur here if somebody
submits a change to A. (in terms of generating a new NodeChange for A)
Possibility 1: (in time order)
The user modifes "/foo/main/A"
Some other user modifies "/foo/alt/A"
This produces:
/foo/main/A (NodeIDA, ArbitraryChangeSetID)
/foo/alt/A (NewNodeID, ArbitrryChangeSetID+1)
Nothing weird happens here, the NodeID is always the same under a given
repository path for the file when a new revision is made to replace the
existing "lazyily copied" data.
Possibility 2: (again in time order)
The user modifies "/foo/alt/A"
Some other modifies "/foo/main/A"
This produces:
/foo/alt/A (NodeIDA, ArbitraryChangeSetID)
/foo/main/A (NewNodeID, ArbitraryChangeSetID + 1)
The fact that after a O(1) "svn copy" /foo/main/A doesn't retain NodeIDA
is weird and massively complicates the time cost of the ancestry
relatedness checks. That is, the is_related() check described earlier
ends up being a O(n) check because it can't be short circuited based on
the NodeID being useful enough to use as the relatedness check.
> 5. To preserve the ability to get_copy_history(NodeA). Yes, this
> is possible in the current scheme, even though the actual copy
> history property is set only on the top node of copied tree and
> only in the revision that the copy occurred in. We record a
> small bit of information in a single place, but it affects
> answers about many other places. Right now,
> "get_copy_history()" means the same as "get_branch_history()".
>
Well, to preserve the current abilities of the existing schema is always
a good thing. I think I'd rephrase this as:
To more efficiently know which branch is the owner of a given repository
path.
It's very expensive now to answer the question: "Which branch does
repository path <Path> belong to?"
Say you have the following repository:
e.g.:
/foo/main/A
/foo/alt/A
where /foo/alt is a branch of /foo/main.
You'd like to know that /foo/alt/A is a member of the "/foo/alt/A"
branch.
In the currently implemented schema, we have no efficient mechanism to
answer this question.
And quite frankly, this "goal" is more of one of the handy side-effects
that easily fall out from wanting to solve issues #3 and #4.
I'll leave as an implemention argument whether or not branched files
should retain their de-normalized ancestral history or not since each
NodeChange (after adding the BranchID) would now know very efficiently
where it would need to look for more information.
Additional discussion points that come out of adding a "BranchID" to the
NodeChange key:
* NodeID aren't only completely stable now, they can also not change
when the file branches.
This allows you to perform queries that users expect you to be able to
perform based on concepts of how branching should work.
* Since NodeIDs can stay the same after a "branch/copy" you need to
answer the following question:
Should the repository support a "branch" operation only, or should the
repository also support a "copy" operation where the NodeID actually
changes, and the ancestry information is truncated.
I think if we can get away with it that we should only allow branches.
The schema change does allow you to support copies, but I think that
unnecessarily complicates the user interface. If the user wants the
result of a copy, they can just make the copy on their own and add the
file(s) back into the repository under a different repository path on
their own.
That pretty much sums up the goals of adding a BranchID, and stabilizing
NodeIDs, but I want to comment on one more semi-related topic Karl
brought up recently.
--------------------- Unbounded ancestry storage
---------------------------
Karl, you were also concerned about the unbounded size of complete
ancestry information even if it wasn't in the key of the NodeChange.
There are various ways to handle this issue. Each of which has their own
pros and cons. Let's look at some of those alternatives for a second.
* Just move the ancestry information from the key, and insert it into
the value of your BDB row.
* Create a secondary table to store the ancestry information
There are two sub-options to this option.
* Option 1: Have a row in this secondary table for each NodeChange
ancestor, and insert the immediate Predecessor NodeChange key into the
NodeChange BDB value.
* Option 2: Just use this secondary table as the place to stick the
ancestry information in the value, and have the normal BDB key be the
key in this table as well.
* Option 3: Only store the immediate predecessor in the BDB value in
your NodeChange row.
There isn't much difference between option #1 and #2, except possibly
from a BDB implementation point of view. The major difference occurs
between #1/#2 and #3. #3 is the most normalized way of storing the data.
(i.e. no data redundancies) However, #3 suffers from a performance
issue. When you need to perform your ancestry check you don't know how
far back in the ancestry you need to go, and the predecessor NodeChanges
might be in wildly differing physical data store pages. Options #1 and
#2 try to reduce that problem by de-normalizing the entire ancestry
information locally.
Given the ways in which we want to access ancestry information Option #1
seems to look more favorable.
The reason for that is that we don't always need all of the ancestry
information, we really (95% of the time) just want enough ancestry
information to answer our question. Failure cases will occur, but that
is very infrequently.
If each piece of ancestry information is stored separately you can stop
reading BDB rows when you've answered your current ancestry question.
Additionally, the only place we call the predecessor API directly is
when we're doing stabilization (and/or deltification).
Does that help clarify things?
Bill
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
Bill, I'm sort of losing track of exactly what's being proposed and
what its goals are, at this point.
A *really* helpful thing would be a fresh mail, that begins with a
list of the problems you're trying to solve, including a small
concrete example for each problem. These should only be problems that
exist in the current filesystem implementation, not problems in prior
incarnations of various proposals. Describe solutions only after the
problems are presented.
For example, you seem to want to treat branches as different from
copies, but that's only something I've inferred slowly from your
mails. Maybe there's a reason to do so, but right now branches and
copies are just two words for exactly the same thing in Subversion.
There's no difference, and distinguishing between them would be a
major design change [read: unlikely before 1.0 :-), though if failure
to distinguish leads to horrible problems, then of course we need to
rethink]. Until we understand whether or not this is a goal, and if
it is then why, it's hard to evaluate or even think clearly about the
proposals.
Just to be clear: I really, really appreciate that you're bringing
years of db experience and schema design to bear on Subversion's
problems, and want to benefit from this. But without clear
communication, there's no way we'll grok the wonderful things going on
in your head :-).
Btw: I know it's much easier for you to speak in generic RDB language,
and that you look forward to the day when Subversion uses a real
relational database backend... But, as we are using Berkeley DB right
now, and also in 1.0, so it would help a lot to talk about how things
would be implemented in bdb specifically.
Right now, the goals (as I understand them) of any new scheme are,
roughly in order of priority:
1. To avoid unbounded NodeID length on certain directories
See http://subversion.tigris.org/issues/show_bug.cgi?id=573
2. To eliminate the pre-commit stabilization walk that currently
unsets the mutability flags of new nodes. This is the same as
saying "make commit be a one-row insert" in RDB-speak, I guess.
3. To preserve the ability to ask is_related(NodeA, NodeB) and
is_ancestor(NodeA, NodeB) and get the answer in a reasonable
amount of time; oh, and the same with get_predecessor(NodeA),
except that there might be multiple predecessors and we need to
think more on that.
4. To preserve the ability to get_copy_history(NodeA). Yes, this
is possible in the current scheme, even though the actual copy
history property is set only on the top node of copied tree and
only in the revision that the copy occurred in. We record a
small bit of information in a single place, but it affects
answers about many other places. Right now,
"get_copy_history()" means the same as "get_branch_history()".
5. To avoid the silly non-determistic migration of NodeID portions
depending on which side of a copy gets modified first. Think of
this as a maintainability fix -- we need things to be
predictable.
Note that throughout this mail, "branch" means branch in the
user-visible sense, not in the fs-internal-nodeID sense.
-Karl
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
RE: RE: Re: Maintaining NodeID sanity
Posted by Bill Tutt <ra...@lyra.org>.
Oh blech, I hate DAGs and lazy actions, it makes life much more
complicated.
Snippets below about how things might change if I actually think about
each case related to the lazy branching scheme.
> From: Bill Tutt [mailto:rassilon@lyra.org]
> > From: Karl Fogel [mailto:kfogel@newton.ch.collab.net]
> > > From: Bill Tutt [mailto:rassilon@lyra.org]
> > > For BDB you could always create a separate NodeChangeAnecstorBlob
> table
> > > if it's deemed that it makes more perf sense that way.
> >
> > This is the assertion I need to be comforted about... :-)
> >
> > Blobs are okay unless you're searching in them often for
information.
> > If we have to constantly load and/or scan a whole blob to find out
> > whether node FOO is an ancestor of BAR or not, that seems like a bit
> > of downgrade from the current system.
> >
> > Am I worrying about nothing? Look in the filesystem at where we do
> > ancestry and predecessor checks... I just don't see how it can
> > possibly be efficient enough to use this ancestry mechanism :-(.
> >
> Most of these answers rely on BranchID being implemented since they
> restore NodeID to sanity and lets me make the following comments:
>
> Let's define a handy function in (NodeID, BranchID, ChangeSetID) land
> because we'll be seeing it a lot:
> AreNodeChangesTimelesslyRelated(Source, Target)
> {
> return (Source.NodeID == Target.NodeID &&
> Source.BranchID == Target.BranchID);
> }
>
I'm currently guessing that by the time this function is called all
mutability rules for lazy BranchID application will have kicked in. See
the discussion about directory auto-merging for specifics.
> Ok, let's check our ancestry examination functions out:
> svn_fs__id_is_parent: only svn_fs_txn_path_is_id uses this function.
> Returns true if A is a parent of B. i.e. if A == B then false.
>
> svn_fs__id_is_parent is only called by:
>
> svn_fs_txn_path_is_id: mod_dav_svn uses this function. I don't know
why
> mod_dav_svn uses this function. I don't quite understand the WebDAV
> context this is occurring in, so I can't analyze this one very well.
I'm
> guessing WebDAV is trying to figure out if a directory is the correct
> version or not, and it only wants to succeed if it cheaply appears to
be
> auto-mergable. So I'd guess a simple check with
> AreNodeChangesTimelesslyRelated should do the trick.
>
Don't have any idea what Branches mean here.
> svn_fs__id_is_ancestor: The only caller of this is directory merging.
> Returns true if A == B or A is parent of B
>
> Regarding the directory merging call site:
[...snip...]
> Case 1: Used to verify that Source is ordered after Target which is
> ordered after Ancestor in a (NodeID, BranchID, ChangeSetID) sense
after
> the schema change.
>
> During a commit, this is guaranteed by our caller, relaxing to
> AreNodeChangesTimelesslyRelated is ok here.
>
If you have the example:
/foo/main/A
/foo/alt/A
and alt is a branch of main, but A hasn't been modified under alt yet.
/foo/alt/A is currently (</foo/main/A NodeID>, NULL, ChangeSet0)
User 1 commits a change to /foo/alt/A.
The process of acquiring a mutable NodeChange yields a Source of:
(</foo/main/A NodeID>, </foo/alt BranchID>, ChangeSet1)
This is compared against a Target NodeChange of:
(</foo/main/A NodeID>, NULL, ChangeSet0)
In this case Ancestor == Target and so it's just allowed to succeed.
Since BranchID changes during the "acquire a mutable node phase", I
don't think Case 1 will ever get hit for a weird non Source.BranchID !=
Target.BranchID when the NodeID's are identical. Since this would imply
some bizarre operation like: "branch /foo/alt /foo/alt" which is illegal
in any operation that doesn't also involve either Target or Source not
existing.
> Case 2: Used to detect unrelated-ness between Source and Transaction
> We know that S != T because we just got done checking that.
>
> During a commit, S can't be a successor of T because T hasn't been
> committed yet, so we could optimize the ancestor check out.
>
This isn't really affected by Branching.
> svn_fs_id_distance is called by the following functions:
>
> svn_fs_check_related: Uses it to prove that they're related via
ancestry
> somehow. (including via copy history)
>
> The new schema offers check_related some more attempts for
optimization
> before it has to call id_distance.
>
> However, check_related isn't called atm!
>
Node ancestry isn't truncated when performing a branch, so check_related
keeps on working for Branches. So, you still have to do the hard work.
Whee!
> tree.c:merge(): Directory merging
> Source == proposed HEAD NodeChange for directory
> Target == current HEAD NodeChange for directory
> Ancestor == common parent NodeChange for directory
> Case 1: Used to re-id a directory node if necessary due to trying to
> auto-resolve directory versioning, and trying to be nice about
> generating complete auto-merge history for directories.
>
> I don't think this makes any sense any more given the new NodeChange
PK.
> A successor is simply a new (NodeID, BranchID, ChangeSetID) tuple
that's
> just later in time. It's not even like the auto-merging delta details
> operation are recorded separately, the original version of the
> NodeChange is deleted.
> This made more sense with the old NodeRevisionIDs.
>
Ditto. No change here for Branches.
> Case 2: Target recreated something that was deleted in Source.
> This is essentially an out-of-dateness check. If you're going to
delete
> something in Source that was updated in Target, then you should have a
> more up to date directory then the one you tried to commit with.
Update
> and retry your svn commit.
>
> Case 2 is an annoying race condition, but it's very important to
double
> check it. Fortunately, this code just needs to know if
> AreNodeChangesTimelesslyRelated. (i.e. they differ only in
ChangeSetID)
>
> The reason for this is that time order between Target and Source never
> applies for this case. Source doesn't exist to compare against, and
> Ancestor is always <= Target by definition.
>
This doesn't change at all. Deletion doesn't alter this case at all.
Branches don't do weird things with Deletions.
> Libsvn_repos/delta.c:
> repos_dir_delta():
> Only called from mod_dav_svn, svnlook, libsvn_repos/log.c, and
> libsvn_repos/reporter.c
> Used to détermine the appropriate delta operation to perform/report
> based on the returned id distance.
>
> This can use our new found friend AreNodeChangesTimelesslyRelated
> because the time order isn't important here.
>
This is actually only used from a logging data scavenging point of view,
so using fs_distance_id would work. Esp. since the source/target dirs
aren't likely to be next to each other.
> Find_nearest_entry:
> /* Find the distance between the target entry and this source
> entry. This returns -1 if they're completely unrelated.
> Here we're using ID distance as an approximation for delta
> size. */
>
> No escape here, we have to do the work atm, unless we want to use a
> different heuristic.
>
Nothing different here.
> delta_dirs:
> /* Check the distance between the ids.
>
> 0 means they are the same id, and this is a noop.
>
> -1 means they are unrelated, so try to find an
ancestor
> elsewhere in the directory. Theoretically, using an
> ancestor as a baseline will reduce the size of the
> deltas.
>
> Any other positive value means the nodes are related
> through ancestry, so go ahead and do the replace
> directly. */
> We can use AreNodeChangesTimelesslyRelated here as well. If
> AreNodeChangesTimelesslyRelated returns FALSE, then we'll call
> find_nearest_entry which will do the really expensive work for us. No
> need to call the expensive check twice for one chunk of data.
>
Well, scratch that, we need to be able to crawl backwards over BranchID
changes boundaries in the direct line of change. So fs_distance_id would
work here too, and our new helper wouldn't.
> The important conclusion:
> The directory auto-merging process is now ancestor checking free for a
> commit. However, delta editor work still can require arbitrary
ancestry
> hopping, but only some of the time (when find_nearest_entry gets
> called). Additionally, anybody who ever calls svn_fs_check_related is
> just going to have to wait, but that was true before the schema
change.
>
Good news is that the summary is still the same.
> Phew... talk about a lot of work,
> Bill
>
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
> For additional commands, e-mail: dev-help@subversion.tigris.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
RE: Re: Maintaining NodeID sanity
Posted by Bill Tutt <ra...@lyra.org>.
> From: Karl Fogel [mailto:kfogel@newton.ch.collab.net]
>
> "Bill Tutt" <ra...@lyra.org> writes:
> > Efficiently accessing ancestor lists:
> > Karl's concerned with the change from NodeRevisionID to (NodeID,
> > ChangeSetID) because it removes the ancestry information from the
row.
> >
> > Bill's reply:
> > This is true. I think you still want to store the entire predecessor
> > list inline using some kind of (hopefully server side merge history
> > recording friendly) string format. Here's an example format that
allows
> > server side merge history recording.
> > E.g: in a Python like way:
> > # Ancestor history list:
> > [
> > # Initial revision NodeChangePK info:
> > [(NodeID1, ChangeSet1)],
> > # Incremental change of this Node:
> > [(NodeID1, ChangeSet2)],
> > # A merge from a different file in the repository (again, just the
> > # NodeChangePK facts here):
> > [(NodeID2, ChangeSet2)],
> > # A star merge from two separate files in the repository:
> > [(NodeID2, ChangeSet3), (NodeID3, ChangeSet4)]
> > ]
> >
> > Just because we're moving the data out of the PK doesn't mean we
can't
> > keep the data around in the row. We just don't want to use it in the
PK.
> > :)
>
> Sure... But the common case so far has been successive single-ancestor
> changes to each node (where the single "ancestor" is the predecessor,
> of course), and we've been able to record that in a highly compressed
> way by using place-value notation: When you see that your ID is
> `X.some_integer', you know to count nodes X.1 through
> X.(some_integer-1) as ancestors. This trick doesn't work when the
> node id is `X.unique_txn_id'.
>
> So my problem isn't that the information is gone from the primary key;
> we can still store it in the row, that's fine. The question is,
> *what* are we storing in the row? If the representation of the
> ancestry line grows linearly with the ancestry line itself, I submit
> that we have a problem. Subversion is supposed to scale :-), not just
> in data size, but number of changes to a given node.
>
> > Put another way: Blob's are bad in index keys (i.e. Primary key),
but
> > are perfectly ok as columns in your table.
> >
> > For BDB you could always create a separate NodeChangeAnecstorBlob
table
> > if it's deemed that it makes more perf sense that way.
>
> This is the assertion I need to be comforted about... :-)
>
> Blobs are okay unless you're searching in them often for information.
> If we have to constantly load and/or scan a whole blob to find out
> whether node FOO is an ancestor of BAR or not, that seems like a bit
> of downgrade from the current system.
>
> Am I worrying about nothing? Look in the filesystem at where we do
> ancestry and predecessor checks... I just don't see how it can
> possibly be efficient enough to use this ancestry mechanism :-(.
>
Most of these answers rely on BranchID being implemented since they
restore NodeID to sanity and lets me make the following comments:
Let's define a handy function in (NodeID, BranchID, ChangeSetID) land
because we'll be seeing it a lot:
AreNodeChangesTimelesslyRelated(Source, Target)
{
return (Source.NodeID == Target.NodeID &&
Source.BranchID == Target.BranchID);
}
Ok, let's check our ancestry examination functions out:
svn_fs__id_is_parent: only svn_fs_txn_path_is_id uses this function.
Returns true if A is a parent of B. i.e. if A == B then false.
svn_fs__id_is_parent is only called by:
svn_fs_txn_path_is_id: mod_dav_svn uses this function. I don't know why
mod_dav_svn uses this function. I don't quite understand the WebDAV
context this is occurring in, so I can't analyze this one very well. I'm
guessing WebDAV is trying to figure out if a directory is the correct
version or not, and it only wants to succeed if it cheaply appears to be
auto-mergable. So I'd guess a simple check with
AreNodeChangesTimelesslyRelated should do the trick.
svn_fs__id_is_ancestor: The only caller of this is directory merging.
Returns true if A == B or A is parent of B
Regarding the directory merging call site:
Both of the cases below revolve around whether directory auto-merging is
performed only by a commit or not.
Given the current schema proposal, I'd argue that merge() needs to know
if it's participating in a commit or not, so that the logic can optimize
on that fact and not examine ancestor history any more than necessary.
In fact both of these listed cases could use
AreNodeChangesTimelesslyRelated if merge() knew that a commit was in
progress.
I thought about suggesting assuming that merge() always gets called
during a commit, but that'd be incorrect if we suddenly allowed
long-term pending transactions that could be extracted into working copy
for various reasons. i.e. either inter-repository merges, or other
various odd reasons like being able to save your in-progress work tree
into a pending-ChangeSet.
Case 1: Used to verify that Source is ordered after Target which is
ordered after Ancestor in a (NodeID, BranchID, ChangeSetID) sense after
the schema change.
During a commit, this is guaranteed by our caller, relaxing to
AreNodeChangesTimelesslyRelated is ok here.
Case 2: Used to detect unrelated-ness between Source and Transaction
We know that S != T because we just got done checking that.
During a commit, S can't be a successor of T because T hasn't been
committed yet, so we could optimize the ancestor check out.
svn_fs_id_distance is called by the following functions:
svn_fs_check_related: Uses it to prove that they're related via ancestry
somehow. (including via copy history)
The new schema offers check_related some more attempts for optimization
before it has to call id_distance.
However, check_related isn't called atm!
tree.c:merge(): Directory merging
Source == proposed HEAD NodeChange for directory
Target == current HEAD NodeChange for directory
Ancestor == common parent NodeChange for directory
Case 1: Used to re-id a directory node if necessary due to trying to
auto-resolve directory versioning, and trying to be nice about
generating complete auto-merge history for directories.
I don't think this makes any sense any more given the new NodeChange PK.
A successor is simply a new (NodeID, BranchID, ChangeSetID) tuple that's
just later in time. It's not even like the auto-merging delta details
operation are recorded separately, the original version of the
NodeChange is deleted.
This made more sense with the old NodeRevisionIDs.
Case 2: Target recreated something that was deleted in Source.
This is essentially an out-of-dateness check. If you're going to delete
something in Source that was updated in Target, then you should have a
more up to date directory then the one you tried to commit with. Update
and retry your svn commit.
Case 2 is an annoying race condition, but it's very important to double
check it. Fortunately, this code just needs to know if
AreNodeChangesTimelesslyRelated. (i.e. they differ only in ChangeSetID)
The reason for this is that time order between Target and Source never
applies for this case. Source doesn't exist to compare against, and
Ancestor is always <= Target by definition.
Libsvn_repos/delta.c:
repos_dir_delta():
Only called from mod_dav_svn, svnlook, libsvn_repos/log.c, and
libsvn_repos/reporter.c
Used to détermine the appropriate delta operation to perform/report
based on the returned id distance.
This can use our new found friend AreNodeChangesTimelesslyRelated
because the time order isn't important here.
Find_nearest_entry:
/* Find the distance between the target entry and this source
entry. This returns -1 if they're completely unrelated.
Here we're using ID distance as an approximation for delta
size. */
No escape here, we have to do the work atm, unless we want to use a
different heuristic.
delta_dirs:
/* Check the distance between the ids.
0 means they are the same id, and this is a noop.
-1 means they are unrelated, so try to find an ancestor
elsewhere in the directory. Theoretically, using an
ancestor as a baseline will reduce the size of the
deltas.
Any other positive value means the nodes are related
through ancestry, so go ahead and do the replace
directly. */
We can use AreNodeChangesTimelesslyRelated here as well. If
AreNodeChangesTimelesslyRelated returns FALSE, then we'll call
find_nearest_entry which will do the really expensive work for us. No
need to call the expensive check twice for one chunk of data.
The important conclusion:
The directory auto-merging process is now ancestor checking free for a
commit. However, delta editor work still can require arbitrary ancestry
hopping, but only some of the time (when find_nearest_entry gets
called). Additionally, anybody who ever calls svn_fs_check_related is
just going to have to wait, but that was true before the schema change.
Phew... talk about a lot of work,
Bill
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
"Bill Tutt" <ra...@lyra.org> writes:
> Efficiently accessing ancestor lists:
> Karl's concerned with the change from NodeRevisionID to (NodeID,
> ChangeSetID) because it removes the ancestry information from the row.
>
> Bill's reply:
> This is true. I think you still want to store the entire predecessor
> list inline using some kind of (hopefully server side merge history
> recording friendly) string format. Here's an example format that allows
> server side merge history recording.
> E.g: in a Python like way:
> # Ancestor history list:
> [
> # Initial revision NodeChangePK info:
> [(NodeID1, ChangeSet1)],
> # Incremental change of this Node:
> [(NodeID1, ChangeSet2)],
> # A merge from a different file in the repository (again, just the
> # NodeChangePK facts here):
> [(NodeID2, ChangeSet2)],
> # A star merge from two separate files in the repository:
> [(NodeID2, ChangeSet3), (NodeID3, ChangeSet4)]
> ]
>
> Just because we're moving the data out of the PK doesn't mean we can't
> keep the data around in the row. We just don't want to use it in the PK.
> :)
Sure... But the common case so far has been successive single-ancestor
changes to each node (where the single "ancestor" is the predecessor,
of course), and we've been able to record that in a highly compressed
way by using place-value notation: When you see that your ID is
`X.some_integer', you know to count nodes X.1 through
X.(some_integer-1) as ancestors. This trick doesn't work when the
node id is `X.unique_txn_id'.
So my problem isn't that the information is gone from the primary key;
we can still store it in the row, that's fine. The question is,
*what* are we storing in the row? If the representation of the
ancestry line grows linearly with the ancestry line itself, I submit
that we have a problem. Subversion is supposed to scale :-), not just
in data size, but number of changes to a given node.
> Put another way: Blob's are bad in index keys (i.e. Primary key), but
> are perfectly ok as columns in your table.
>
> For BDB you could always create a separate NodeChangeAnecstorBlob table
> if it's deemed that it makes more perf sense that way.
This is the assertion I need to be comforted about... :-)
Blobs are okay unless you're searching in them often for information.
If we have to constantly load and/or scan a whole blob to find out
whether node FOO is an ancestor of BAR or not, that seems like a bit
of downgrade from the current system.
Am I worrying about nothing? Look in the filesystem at where we do
ancestry and predecessor checks... I just don't see how it can
possibly be efficient enough to use this ancestry mechanism :-(.
> Karl was wondering about whether it's important or not for ChangeSet's
> to be incrementally ordered on a NodeChange's versioning timeline. i.e.
> point in time 1 could have a ChangeSetID that's larger than the
> NodeChange of the Node at point in time 2.
>
> Bill's reply:
> Yes this is possible to have, but it doesn't cause us any problems,
> since an ordering still exists. You just have to join to the Repository
> Revision Number -> ChangeSetID data. It imposes a little extra overhead,
> but in general shouldn't be that nasty. Especially since repository
> point in times -> ChangeSetID mappings are completely non-alterable,
> ever... (i.e. they're easily cacheable)
Agreed (I think Mike Pilato and I came to the same conclusion today).
-K
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
RE: Maintaining NodeID sanity
Posted by Bill Tutt <ra...@lyra.org>.
I'm sorry for it being a bit dense; I wanted to get the idea out and
about and didn't have enough time to properly thrash the idea into a
power point slide deck, or some Visio diagrams. This unfortunately would
have helped a bunch given the bizarre DAGgy-ness that abounds here.
I'm afraid I'm not on the issues list atm, but I'll be adding myself to
654 shortly, but I'll paste these comments on your points in Issuezilla
as well.
Efficiently accessing ancestor lists:
Karl's concerned with the change from NodeRevisionID to (NodeID,
ChangeSetID) because it removes the ancestry information from the row.
Bill's reply:
This is true. I think you still want to store the entire predecessor
list inline using some kind of (hopefully server side merge history
recording friendly) string format. Here's an example format that allows
server side merge history recording.
E.g: in a Python like way:
# Ancestor history list:
[
# Initial revision NodeChangePK info:
[(NodeID1, ChangeSet1)],
# Incremental change of this Node:
[(NodeID1, ChangeSet2)],
# A merge from a different file in the repository (again, just the
# NodeChangePK facts here):
[(NodeID2, ChangeSet2)],
# A star merge from two separate files in the repository:
[(NodeID2, ChangeSet3), (NodeID3, ChangeSet4)]
]
Just because we're moving the data out of the PK doesn't mean we can't
keep the data around in the row. We just don't want to use it in the PK.
:)
Put another way: Blob's are bad in index keys (i.e. Primary key), but
are perfectly ok as columns in your table.
For BDB you could always create a separate NodeChangeAnecstorBlob table
if it's deemed that it makes more perf sense that way.
Karl was wondering about whether it's important or not for ChangeSet's
to be incrementally ordered on a NodeChange's versioning timeline. i.e.
point in time 1 could have a ChangeSetID that's larger than the
NodeChange of the Node at point in time 2.
Bill's reply:
Yes this is possible to have, but it doesn't cause us any problems,
since an ordering still exists. You just have to join to the Repository
Revision Number -> ChangeSetID data. It imposes a little extra overhead,
but in general shouldn't be that nasty. Especially since repository
point in times -> ChangeSetID mappings are completely non-alterable,
ever... (i.e. they're easily cacheable)
Bill
----
Do you want a dangerous fugitive staying in your flat?
No.
Well, don't upset him and he'll be a nice fugitive staying in your flat.
> -----Original Message-----
> From: Karl Fogel [mailto:kfogel@newton.ch.collab.net]
> Sent: Tuesday, May 07, 2002 5:36 PM
> To: Bill Tutt
> Cc: Subversion Dev list
> Subject: Re: Maintaining NodeID sanity
>
> I'm printing this out and reading it at home right now, Bill (it's,
> uh, a bit dense, and so am I :-) ). I'm curious if you've been
> watching my recent annotations to
>
> http://subversion.tigris.org/issues/show_bug.cgi?id=654
>
> They describe some concerns I have about the new NodeID scheme. Not
> showstoppers yet, afaict, but I'd like to know what you (and Brane,
> and everyone else) think of them...
>
> Thanks,
> -K
>
> "Bill Tutt" <bi...@microsoft.com> writes:
> > Branko came up with a decent idea to restore NodeID sanity to the
> > universe in the face of the weird side-effects of O(1) copies.
> >
> > The thinking goes something like this:
> >
> > We want to keep the NodeID the same for branches, but different for
> > copies.
> >
> > We want to only change the NodeID on the destination of the copy.
> >
> > A copy is really almost a branch. Let's think about just branches
for
> > the moment.
> >
> > So, we need a way to distinguish a NodeChange besides just the
normal
> > (NodeID, ChangeSetID) data.
> >
> > Let's add a BranchID to the PK of a NodeChange so that you have
(NodeID,
> > BranchID, ChangeSetID) as the PK of NodeChange.
> >
> > So when you "branch <src> <dest>" the result of the branch is a new
> > NodeChange that looks like this:
> > (<src NodeID>, <some opaque BranchID type>, <branch operation's
> > ChangeSetID>)
> >
> > Now all we need is to know exactly what a BranchID is.
> >
> > Branko's idea was to define a BranchID as:
> > NodeChangePKOf(parentOf(<dest>)).
> >
> > The problem with that is that the PK contains BranchID which is now
> > recursively defined. That's good for nested branches, but bad for a
> > schema.
> >
> > One alternative is to add a unique column to NodeChange:
NodeChangeID.
> > NodeChangeID is a monotonically increasing integer (possibly a
> > fixed-precision decimal considering that NodeChangeIDs will be used
much
> > more quickly than NodeIDs) that is unique for each NodeChange.
> >
> > NodeChangeID is not an additional part of the PK. It is an AK
> > (alternative key).
> >
> > BranchID can now be defined to be: NodeChangeID of <dest>.
> >
> > When the user creates a branch of path "/foo" to "/bar" the
following
> > can now happen:
> > Create a new NodeChange of ("/foo".NodeID, BranchID ==
> > this.NodeChangeID, ChangeSetID) and associate it with "/bar". This
> > doesn't set any of the copy related properties, and only changes the
> > BranchID.
> >
> > When you are committing new changes to things under /bar (or
revision
> > bumps of /bar), any new nodes will have the BranchID set to "/bar''s
> > BranchID.
> >
> > The problem now becomes what I do when I have one of these
complicated
> > nested branch cases.
> >
> > e.g.:
> >
> > /foo/main/A
> > /foo/alt/A
> >
> > where /foo/alt is a branch of /foo/main.
> >
> > I then: "branch /foo /bar"
> > I then make a modification to "/bar/alt/A".
> >
> > What BranchID does A's NodeChange row now have?
> > If we lazily flatten sub-branches then it could be "/bar"'s
BranchID.
> > If we lazily create sub-branches then it could be "/bar/alt/"'s
> > BranchID.
> >
> > Flattening isn't terribly friendly to our users, so let's think
about
> > what we have to do if we lazily create our sub-branches.
> >
> > When examining /bar/alt we notice that the existing BranchID !=
/bar's
> > BranchID. This may mean any number of things:
> > * It might be a copy, since we haven't told you how to differentiate
> > between a copy and a branch. If it existed inside of a copy, the
> > BranchID is unimportant since if it needs to change to be /bar's
> > BranchID.
> >
> > * It might be a branch, and if so, we need to create a new
NodeChange
> > for alt, containing a new BranchID. The origin of this branch is
> > recorded as being /foo/alt.
> > Once we have this new BranchID, we can then use it while creating
the
> > new NodeChange for /bar/alt/A.
> >
> > But, how do we detect that /bar/alt is a branch instead of a copy?
(i.e.
> > it might be a copy of a branch)
> >
> > Alt.BranchID points to /foo/alt's data. (The location of the
original
> > branch.) When I look that data up, I'll notice that the copy
information
> > is absent. This tells me I have a branch. If I had a copy, the copy
> > properties would be filled in.
> >
> > The only additional annoyance is that copy/branch destination nodes
> > don't record the path that they were created at. Given the DAGgy
nature
> > of our data store, it would certainly help if they included what
their
> > creation path was.
> >
> > i.e.: /bar was created at path /bar.
> >
> > To sum up:
> > Add a BranchID to the PK of NodeChange.
> > Add a NodeChangeID as an AK of NodeChange. (i.e. monotonically
> > increasing integer that uniquely, but not usefully defines a
NodeChange
> > row)
> > Use the NodeChangeID as the BranchID when creating
copies/branches.
> > Add a CreatedPath to NodeChange that is only used for copy/branch
> > operations.
> >
> > Alternatively, you could get away without having NodeChangeID since
it
> > requires a separate BDB table to repeat the PK of NodeChange to
point to
> > the correct NodeChange row.
> >
> > If we do the above we get the following benefits:
> > * NodeIDs stay the same for branches, but change for copies.
> > * NodeIDs are attached to the path that they're created in. No more
> > non-deterministic migrating of NodeID usages depending on which side
of
> > a copy got modified first.
> > * We get the easy possibility of handling O(1) branches,
sub-branches,
> > and sub-sub-branches, etc....
> > * Computing the next NodeID to use for a NodeChange alteration is
much
> > quicker.
> > (It's built up as you traverse the path space looking for
NodeChange's
> > to create new revisions of.)
> > * svn log for branched items includes all of the history of the node
> > before the branch. Since the inline history revision data is
preserved.
> > * The addition of created path to copy/branch points reduces poor
svn
> > log's workload when told to figure out what it needs to do, but
can't
> > easily output where a nested branch/copy came from.
> >
> > Sounds like utter goodness to me. :)
> >
> > Bill
> >
> >
---------------------------------------------------------------------
> > To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
> > For additional commands, e-mail: dev-help@subversion.tigris.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by Karl Fogel <kf...@newton.ch.collab.net>.
I'm printing this out and reading it at home right now, Bill (it's,
uh, a bit dense, and so am I :-) ). I'm curious if you've been
watching my recent annotations to
http://subversion.tigris.org/issues/show_bug.cgi?id=654
They describe some concerns I have about the new NodeID scheme. Not
showstoppers yet, afaict, but I'd like to know what you (and Brane,
and everyone else) think of them...
Thanks,
-K
"Bill Tutt" <bi...@microsoft.com> writes:
> Branko came up with a decent idea to restore NodeID sanity to the
> universe in the face of the weird side-effects of O(1) copies.
>
> The thinking goes something like this:
>
> We want to keep the NodeID the same for branches, but different for
> copies.
>
> We want to only change the NodeID on the destination of the copy.
>
> A copy is really almost a branch. Let's think about just branches for
> the moment.
>
> So, we need a way to distinguish a NodeChange besides just the normal
> (NodeID, ChangeSetID) data.
>
> Let's add a BranchID to the PK of a NodeChange so that you have (NodeID,
> BranchID, ChangeSetID) as the PK of NodeChange.
>
> So when you "branch <src> <dest>" the result of the branch is a new
> NodeChange that looks like this:
> (<src NodeID>, <some opaque BranchID type>, <branch operation's
> ChangeSetID>)
>
> Now all we need is to know exactly what a BranchID is.
>
> Branko's idea was to define a BranchID as:
> NodeChangePKOf(parentOf(<dest>)).
>
> The problem with that is that the PK contains BranchID which is now
> recursively defined. That's good for nested branches, but bad for a
> schema.
>
> One alternative is to add a unique column to NodeChange: NodeChangeID.
> NodeChangeID is a monotonically increasing integer (possibly a
> fixed-precision decimal considering that NodeChangeIDs will be used much
> more quickly than NodeIDs) that is unique for each NodeChange.
>
> NodeChangeID is not an additional part of the PK. It is an AK
> (alternative key).
>
> BranchID can now be defined to be: NodeChangeID of <dest>.
>
> When the user creates a branch of path "/foo" to "/bar" the following
> can now happen:
> Create a new NodeChange of ("/foo".NodeID, BranchID ==
> this.NodeChangeID, ChangeSetID) and associate it with "/bar". This
> doesn't set any of the copy related properties, and only changes the
> BranchID.
>
> When you are committing new changes to things under /bar (or revision
> bumps of /bar), any new nodes will have the BranchID set to "/bar''s
> BranchID.
>
> The problem now becomes what I do when I have one of these complicated
> nested branch cases.
>
> e.g.:
>
> /foo/main/A
> /foo/alt/A
>
> where /foo/alt is a branch of /foo/main.
>
> I then: "branch /foo /bar"
> I then make a modification to "/bar/alt/A".
>
> What BranchID does A's NodeChange row now have?
> If we lazily flatten sub-branches then it could be "/bar"'s BranchID.
> If we lazily create sub-branches then it could be "/bar/alt/"'s
> BranchID.
>
> Flattening isn't terribly friendly to our users, so let's think about
> what we have to do if we lazily create our sub-branches.
>
> When examining /bar/alt we notice that the existing BranchID != /bar's
> BranchID. This may mean any number of things:
> * It might be a copy, since we haven't told you how to differentiate
> between a copy and a branch. If it existed inside of a copy, the
> BranchID is unimportant since if it needs to change to be /bar's
> BranchID.
>
> * It might be a branch, and if so, we need to create a new NodeChange
> for alt, containing a new BranchID. The origin of this branch is
> recorded as being /foo/alt.
> Once we have this new BranchID, we can then use it while creating the
> new NodeChange for /bar/alt/A.
>
> But, how do we detect that /bar/alt is a branch instead of a copy? (i.e.
> it might be a copy of a branch)
>
> Alt.BranchID points to /foo/alt's data. (The location of the original
> branch.) When I look that data up, I'll notice that the copy information
> is absent. This tells me I have a branch. If I had a copy, the copy
> properties would be filled in.
>
> The only additional annoyance is that copy/branch destination nodes
> don't record the path that they were created at. Given the DAGgy nature
> of our data store, it would certainly help if they included what their
> creation path was.
>
> i.e.: /bar was created at path /bar.
>
> To sum up:
> Add a BranchID to the PK of NodeChange.
> Add a NodeChangeID as an AK of NodeChange. (i.e. monotonically
> increasing integer that uniquely, but not usefully defines a NodeChange
> row)
> Use the NodeChangeID as the BranchID when creating copies/branches.
> Add a CreatedPath to NodeChange that is only used for copy/branch
> operations.
>
> Alternatively, you could get away without having NodeChangeID since it
> requires a separate BDB table to repeat the PK of NodeChange to point to
> the correct NodeChange row.
>
> If we do the above we get the following benefits:
> * NodeIDs stay the same for branches, but change for copies.
> * NodeIDs are attached to the path that they're created in. No more
> non-deterministic migrating of NodeID usages depending on which side of
> a copy got modified first.
> * We get the easy possibility of handling O(1) branches, sub-branches,
> and sub-sub-branches, etc....
> * Computing the next NodeID to use for a NodeChange alteration is much
> quicker.
> (It's built up as you traverse the path space looking for NodeChange's
> to create new revisions of.)
> * svn log for branched items includes all of the history of the node
> before the branch. Since the inline history revision data is preserved.
> * The addition of created path to copy/branch points reduces poor svn
> log's workload when told to figure out what it needs to do, but can't
> easily output where a nested branch/copy came from.
>
> Sounds like utter goodness to me. :)
>
> Bill
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
> For additional commands, e-mail: dev-help@subversion.tigris.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org
Re: Maintaining NodeID sanity
Posted by "Glenn A. Thompson" <gt...@cdr.net>.
OH my:-)
I read what Karl posted to issues.
I think I'll review this posting in the AM.
I will have questions!
gat
Bill Tutt wrote:
> Branko came up with a decent idea to restore NodeID sanity to the
> universe in the face of the weird side-effects of O(1) copies.
>
> The thinking goes something like this:
>
> We want to keep the NodeID the same for branches, but different for
> copies.
>
> We want to only change the NodeID on the destination of the copy.
>
> A copy is really almost a branch. Let's think about just branches for
> the moment.
>
> So, we need a way to distinguish a NodeChange besides just the normal
> (NodeID, ChangeSetID) data.
>
> Let's add a BranchID to the PK of a NodeChange so that you have (NodeID,
> BranchID, ChangeSetID) as the PK of NodeChange.
>
> So when you "branch <src> <dest>" the result of the branch is a new
> NodeChange that looks like this:
> (<src NodeID>, <some opaque BranchID type>, <branch operation's
> ChangeSetID>)
>
> Now all we need is to know exactly what a BranchID is.
>
> Branko's idea was to define a BranchID as:
> NodeChangePKOf(parentOf(<dest>)).
>
> The problem with that is that the PK contains BranchID which is now
> recursively defined. That's good for nested branches, but bad for a
> schema.
>
> One alternative is to add a unique column to NodeChange: NodeChangeID.
> NodeChangeID is a monotonically increasing integer (possibly a
> fixed-precision decimal considering that NodeChangeIDs will be used much
> more quickly than NodeIDs) that is unique for each NodeChange.
>
> NodeChangeID is not an additional part of the PK. It is an AK
> (alternative key).
>
> BranchID can now be defined to be: NodeChangeID of <dest>.
>
> When the user creates a branch of path "/foo" to "/bar" the following
> can now happen:
> Create a new NodeChange of ("/foo".NodeID, BranchID ==
> this.NodeChangeID, ChangeSetID) and associate it with "/bar". This
> doesn't set any of the copy related properties, and only changes the
> BranchID.
>
> When you are committing new changes to things under /bar (or revision
> bumps of /bar), any new nodes will have the BranchID set to "/bar''s
> BranchID.
>
> The problem now becomes what I do when I have one of these complicated
> nested branch cases.
>
> e.g.:
>
> /foo/main/A
> /foo/alt/A
>
> where /foo/alt is a branch of /foo/main.
>
> I then: "branch /foo /bar"
> I then make a modification to "/bar/alt/A".
>
> What BranchID does A's NodeChange row now have?
> If we lazily flatten sub-branches then it could be "/bar"'s BranchID.
> If we lazily create sub-branches then it could be "/bar/alt/"'s
> BranchID.
>
> Flattening isn't terribly friendly to our users, so let's think about
> what we have to do if we lazily create our sub-branches.
>
> When examining /bar/alt we notice that the existing BranchID != /bar's
> BranchID. This may mean any number of things:
> * It might be a copy, since we haven't told you how to differentiate
> between a copy and a branch. If it existed inside of a copy, the
> BranchID is unimportant since if it needs to change to be /bar's
> BranchID.
>
> * It might be a branch, and if so, we need to create a new NodeChange
> for alt, containing a new BranchID. The origin of this branch is
> recorded as being /foo/alt.
> Once we have this new BranchID, we can then use it while creating the
> new NodeChange for /bar/alt/A.
>
> But, how do we detect that /bar/alt is a branch instead of a copy? (i.e.
> it might be a copy of a branch)
>
> Alt.BranchID points to /foo/alt's data. (The location of the original
> branch.) When I look that data up, I'll notice that the copy information
> is absent. This tells me I have a branch. If I had a copy, the copy
> properties would be filled in.
>
> The only additional annoyance is that copy/branch destination nodes
> don't record the path that they were created at. Given the DAGgy nature
> of our data store, it would certainly help if they included what their
> creation path was.
>
> i.e.: /bar was created at path /bar.
>
> To sum up:
> Add a BranchID to the PK of NodeChange.
> Add a NodeChangeID as an AK of NodeChange. (i.e. monotonically
> increasing integer that uniquely, but not usefully defines a NodeChange
> row)
> Use the NodeChangeID as the BranchID when creating copies/branches.
> Add a CreatedPath to NodeChange that is only used for copy/branch
> operations.
>
> Alternatively, you could get away without having NodeChangeID since it
> requires a separate BDB table to repeat the PK of NodeChange to point to
> the correct NodeChange row.
>
> If we do the above we get the following benefits:
> * NodeIDs stay the same for branches, but change for copies.
> * NodeIDs are attached to the path that they're created in. No more
> non-deterministic migrating of NodeID usages depending on which side of
> a copy got modified first.
> * We get the easy possibility of handling O(1) branches, sub-branches,
> and sub-sub-branches, etc....
> * Computing the next NodeID to use for a NodeChange alteration is much
> quicker.
> (It's built up as you traverse the path space looking for NodeChange's
> to create new revisions of.)
> * svn log for branched items includes all of the history of the node
> before the branch. Since the inline history revision data is preserved.
> * The addition of created path to copy/branch points reduces poor svn
> log's workload when told to figure out what it needs to do, but can't
> easily output where a nested branch/copy came from.
>
> Sounds like utter goodness to me. :)
>
> Bill
>
> ---------------------------------------------------------------------
> To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
> For additional commands, e-mail: dev-help@subversion.tigris.org
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org