[svn.haxx.se] · SVN Dev · SVN Users · SVN Org · TSVN Dev · TSVN Users · Subclipse Dev · Subclipse Users · this month's index

RE: RE: Re: Maintaining NodeID sanity

From: Bill Tutt <rassilon_at_lyra.org>
Date: 2002-05-08 09:37:27 CEST

Oh blech, I hate DAGs and lazy actions, it makes life much more
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
> > 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
> 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.
> 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
> 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:
> Case 1: Used to verify that Source is ordered after Target which is
> ordered after Ancestor in a (NodeID, BranchID, ChangeSetID) sense
> the schema change.
> During a commit, this is guaranteed by our caller, relaxing to
> AreNodeChangesTimelesslyRelated is ok here.

If you have the example:


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

> 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
> somehow. (including via copy history)
> The new schema offers check_related some more attempts for
> 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.

> 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
> A successor is simply a new (NodeID, BranchID, ChangeSetID) tuple
> 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
> 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.
> and retry your svn commit.
> Case 2 is an annoying race condition, but it's very important to
> check it. Fortunately, this code just needs to know if
> AreNodeChangesTimelesslyRelated. (i.e. they differ only in
> 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
> 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
> 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

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
Received on Wed May 8 09:38:28 2002

This is an archived mail posted to the Subversion Dev mailing list.