You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Julian Foad <ju...@btopenworld.com> on 2013/09/11 17:21:45 UTC
Moves in FSFS
While discussions continue about the "editor" and the WC side of move
tracking, I'd like to make some progress on the Repository side.
The Wiki page
http://wiki.apache.org/subversion/MoveDev/MoveDev#Move_Semantics
declares the semantic model and
http://wiki.apache.org/subversion/MoveDev/MovesInFSFS
attempts to specify the changes needed. I think the model for move
semantics in the repository as presented there is pretty solid --
precise and complete and having a nice set of properties.
Can anyone review this? If anyone can take it forward in any way that
would be a great help, otherwise I'll tackle the implementation
myself.
One issue that may be harder than it sounds at first is the concept of
'node-line-id' rather than (node-id, copy-id) as the basis of the
definition. The point is that when we copy (ordinary copy, not move)
a directory, we lazy-copy the children, which means each child keeps
its old (node-id, copy-id) unless and until it is modified. That's
great for achieving the O(1) copy, but for move-tracking purposes each
child needs a unique "node-line-id" so its life-line can be uniquely
traced forward and back between this revision and a later revision by
which time it may have been modified and thus assigned a new copy-id.
Clearly it would defeat the O(1) cost if we were to construct a
node-line-id explicitly for every node in the tree at copy time. Can
we instead define node-line-id such that we can compute it as needed,
from either an unmodified lazy-copied child or after such a child has
been modified, and get the same answer? Or perhaps re-state the
problem to avoid this need?
- Julian
Re: Moves in FSFS
Posted by Branko Čibej <br...@wandisco.com>.
On 11.09.2013 20:09, Julian Foad wrote:
>> Proposal: Resurrect keeping the old node-line IDs, iff
>> (a) the copy source (or a parent) got deleted in the next revision
>> (b) no copies of that node (or any parent) were added since the source rev.
>> That should keep normal copying relatively cheap and still provide the
>> special behavior for our "undo" use-case.
> I think you mean that the user-level copy should do this automatically. Perhaps so. That need not be implemented in the FS layer; the FS layer could just provide the primitives necessary to implement it.
This actually breaks the semantics of "copy" for no readily apparent
reason. It's much more interesting IMO to consider how such a concept
would be presented in the UI.
I'll just note that resurrecting deleted nodes is orthogonal to the
issue of move tracking. It's moderately easily done in the current
top-down DAG model, since "delete" simply means "remove edge from
graph"; and it's also provided for in the metadata-ng design.
--
Branko Čibej | Director of Subversion
WANdisco // Non-Stop Data
e. brane@wandisco.com
Re: Moves in FSFS
Posted by Julian Foad <ju...@btopenworld.com>.
Thanks, Stefan! Very interesting thoughts. Especially... (scroll down)...
Stefan Fuhrmann wrote:
On Wed, Sep 11, 2013 at 5:21 PM, Julian Foad wrote:
>> http://wiki.apache.org/subversion/MoveDev/MoveDev#Move_Semantics
>> http://wiki.apache.org/subversion/MoveDev/MovesInFSFS
>> [...]
>>
>> One issue that may be harder than it sounds at first is the concept of
>> 'node-line-id' rather than (node-id, copy-id) as the basis of the
>> definition. The point is that when we copy (ordinary copy, not move)
>> a directory, we lazy-copy the children, which means each child keeps
>> its old (node-id, copy-id) unless and until it is modified. That's
>> great for achieving the O(1) copy, but for move-tracking purposes each
>> child needs a unique "node-line-id" so its life-line can be uniquely
>> traced forward and back between this revision and a later revision by
>> which time it may have been modified and thus assigned a new copy-id.
>>
>> Clearly it would defeat the O(1) cost if we were to construct a
>> node-line-id explicitly for every node in the tree at copy time. Can
>> we instead define node-line-id such that we can compute it as needed,
>> from either an unmodified lazy-copied child or after such a child has
>> been modified, and get the same answer? Or perhaps re-state the
>> problem to avoid this need?
>
> I'm currently bogged down in svnlive prep work but here is my quick feedback;
> more to come next week.
>
> Bottom line: looks ok, especially the API seems fine and performance in f7
> should be acceptable even if it is O(changes in [rA .. rB]).
>
> General observations:
>
>* We need a format bump for the extra "M" entries in the changed path
> lists, potential "lazy" markers in the tree etc. But that is not a problem
> as the log-addressing branch probably gets merged in about 2 weeks
> time and bumps to f7 anyway. It also brings the infrastructure for
> "mixed addressing" such that we may introduce extended structures
> in existing repositories without touching existing revisions.
>
>* Existing copy&del pairs will not be treated as move since the node-line-id
> does not match. Maybe, we can add some intelligence to 'svnadmin load'.
>
>* A copy effectively destroys all move relationships below it. That seems
> unfortunate (say, you duplicate a project) but the solution to that would
> probably require hierarchical IDs ("match IDs within the context of this
> sub-tree").
That's a good observation. Here's an example, to clarify:
r10: trunk/foo
move foo to bar
r20: trunk/bar
copy trunk to branch1
r30: trunk/bar
branch1/bar
Now request "svn diff -r10:30 branch1". It would be useful if Subversion could say trunk/foo@10 moved to branch1/bar@30 in the context of this diff. (Where I say "diff" we can also substitute "update", "merge", and so on.)
This only makes sense for a copy at or above the root path of the requested diff. In this example, it makes sense for "diff -r10:30 branch1" and for "diff -r10:30 branch1/bar". It does not make sense across a copy that happened below the target: in this case, "diff -r10:30 ^/" would NOT be expected to show foo@10->bar@30 as a move.
One way of looking at this is that our history-tracing that's used to find "-r10 branch@30" in such scenarios is *already* following copies at the root of the subtree as if they are moves, and in a way this would be extending that idea.
This seems like functionality that should be provided in a higher layer; the FS layer just needs to provide some primitive queries to make this possible. I'm not sure what, exactly.
>* Support for resurrection of deleted nodes *without* destroying any move
> relationship is potentially expensive but I think we should support this
> early on (maybe not in 1.9 but def. in 1.10). People just happen to delete
> their /trunk once in a while and you don't want to tell them that *now* they
> actually managed to break something ...
Yes.
> Proposal: Resurrect keeping the old node-line IDs, iff
> (a) the copy source (or a parent) got deleted in the next revision
> (b) no copies of that node (or any parent) were added since the source rev.
> That should keep normal copying relatively cheap and still provide the
> special behavior for our "undo" use-case.
I think you mean that the user-level copy should do this automatically. Perhaps so. That need not be implemented in the FS layer; the FS layer could just provide the primitives necessary to implement it.
> I'd like to implement that - after some in-depth more review and would even
> be willing to postpone the cache-server feature to 1.10 because move tracking
> is much more important atm.
Wonderful!
- Julian
Re: Moves in FSFS
Posted by Stefan Fuhrmann <st...@wandisco.com>.
On Wed, Sep 11, 2013 at 5:21 PM, Julian Foad <ju...@btopenworld.com>wrote:
> While discussions continue about the "editor" and the WC side of move
> tracking, I'd like to make some progress on the Repository side.
>
> The Wiki page
>
> http://wiki.apache.org/subversion/MoveDev/MoveDev#Move_Semantics
>
> declares the semantic model and
>
> http://wiki.apache.org/subversion/MoveDev/MovesInFSFS
>
> attempts to specify the changes needed. I think the model for move
> semantics in the repository as presented there is pretty solid --
> precise and complete and having a nice set of properties.
>
> Can anyone review this? If anyone can take it forward in any way that
> would be a great help, otherwise I'll tackle the implementation
> myself.
>
> One issue that may be harder than it sounds at first is the concept of
> 'node-line-id' rather than (node-id, copy-id) as the basis of the
> definition. The point is that when we copy (ordinary copy, not move)
> a directory, we lazy-copy the children, which means each child keeps
> its old (node-id, copy-id) unless and until it is modified. That's
> great for achieving the O(1) copy, but for move-tracking purposes each
> child needs a unique "node-line-id" so its life-line can be uniquely
> traced forward and back between this revision and a later revision by
> which time it may have been modified and thus assigned a new copy-id.
>
> Clearly it would defeat the O(1) cost if we were to construct a
> node-line-id explicitly for every node in the tree at copy time. Can
> we instead define node-line-id such that we can compute it as needed,
> from either an unmodified lazy-copied child or after such a child has
> been modified, and get the same answer? Or perhaps re-state the
> problem to avoid this need?
>
Hi Julian,
I'm currently bogged down in svnlive prep work but here is my quick
feedback;
more to come next week.
Bottom line: looks ok, especially the API seems fine and performance in f7
should be acceptable even if it is O(changes in [rA .. rB]).
General observations:
* We need a format bump for the extra "M" entries in the changed path
lists, potential "lazy" markers in the tree etc. But that is not a problem
as the log-addressing branch probably gets merged in about 2 weeks
time and bumps to f7 anyway. It also brings the infrastructure for
"mixed addressing" such that we may introduce extended structures
in existing repositories without touching existing revisions.
* Existing copy&del pairs will not be treated as move since the node-line-id
does not match. Maybe, we can add some intelligence to 'svnadmin load'.
* A copy effectively destroys all move relationships below it. That seems
unfortunate (say, you duplicate a project) but the solution to that would
probably require hierarchical IDs ("match IDs within the context of this
sub-tree").
* Support for resurrection of deleted nodes *without* destroying any move
relationship is potentially expensive but I think we should support this
early on (maybe not in 1.9 but def. in 1.10). People just happen to delete
their /trunk once in a while and you don't want to tell them that *now*
they
actually managed to break something ...
Proposal: Resurrect keeping the old node-line IDs, iff
(a) the copy source (or a parent) got deleted in the next revision
(b) no copies of that node (or any parent) were added since the source
rev.
That should keep normal copying relatively cheap and still provide the
special behavior for our "undo" use-case.
I'd like to implement that - after some in-depth more review and would even
be willing to postpone the cache-server feature to 1.10 because move
tracking
is much more important atm.
-- Stefan^2.
Re: Moves in FSFS
Posted by Branko Čibej <br...@wandisco.com>.
On 19.09.2013 15:58, Julian Foad wrote:
> The key point here is that there needs to be a *unique* solution for where branch/B@20 has been moved to in r40. With copies, of course, there is not a unique solution when we follow history forward because there can be multiple copies, but following moves forward through history must produce a unique path (at each revision).
>
> The specific difficulty is that branch/B@20 does not yet have its own copy-id, it shares it with trunk/B@20. I'm saying that if you try to specify an algorithm that traces the moves that lead from branch/B@20 to branch/D@40 using just (node-id, copy-id), you will go looking at the parent directories to see if there any copies involved, and if the nodes you're looking at are lazy-copied, and in doing so you will calculate a derived attribute that is equivalent to "node-line-id".
I still don't see how that's different from detecting copies, or
detecting moves in the current copy+delete implementation. IIRC, most of
the work there is done by scanning the "changes" table, and the
algorithm is path-based, not node-id etc. based.
-- Brane
--
Branko Čibej | Director of Subversion
WANdisco // Non-Stop Data
e. brane@wandisco.com
Re: Moves in FSFS
Posted by Julian Foad <ju...@btopenworld.com>.
Branko Čibej wrote:
> On 19.09.2013 12:09, Julian Foad wrote:
>> Branko Čibej wrote:
>>> On 17.09.2013 12:55, Julian Foad wrote:
>>>> branch the trunk:
>>>>
>>>> r20:
>>>> trunk
>>>> /A
>>>> /B
>>>> branch
>>>> /A (pointer to /trunk/A)
>>>> /B (pointer to /trunk/B)
>>>>
>>>> modify branch/A:
>>>>
>>>> r30:
>>>> trunk
>>>> /A
>>>> /B
>>>> branch
>>>> /A
>>>> /B (pointer to /trunk/B)
>> [...]
>>
>> r40: move A to C, and move B to D
I meant on the branch...
>> So the repository in r40 looks like:
>>
>> r40:
>> trunk
>> /A
>> /B
>> branch
>> /C
>> /D
... but it will make the problem even clearer if we also do it on trunk at the same time, ending up with:
r40:
trunk
/C (was moved from /trunk/A@30)
/D (was moved from /trunk/B@30)
branch
/C (was moved from /branch/A@30)
/D (was moved from /branch/B@30)
>> Now we query: for each path in 'branch' in r20, where is "it"
>> (the same node-line) in r40? The query is to be answered without
>> scanning all intervening revisions sequentially.
>
> Fine, but this has nothing at all to do with moves. It's the
> forward-history search problem, [...]. I don't know why you're
> trying to optimize that as part of the move design.
Although I'd *like* a more optimal solution, I acknowledge that talking about the cost may be distracting us from the semantics. So forget I mentioned that.
The key point here is that there needs to be a *unique* solution for where branch/B@20 has been moved to in r40. With copies, of course, there is not a unique solution when we follow history forward because there can be multiple copies, but following moves forward through history must produce a unique path (at each revision).
The specific difficulty is that branch/B@20 does not yet have its own copy-id, it shares it with trunk/B@20. I'm saying that if you try to specify an algorithm that traces the moves that lead from branch/B@20 to branch/D@40 using just (node-id, copy-id), you will go looking at the parent directories to see if there any copies involved, and if the nodes you're looking at are lazy-copied, and in doing so you will calculate a derived attribute that is equivalent to "node-line-id".
- Julian
Re: Moves in FSFS
Posted by Branko Čibej <br...@wandisco.com>.
On 19.09.2013 12:09, Julian Foad wrote:
> Branko Čibej wrote:
>> On 17.09.2013 12:55, Julian Foad wrote:
>> [...]
>>> Start with
>>>
>>> r10:
>>> trunk
>>> /A
>>> /B
>>>
>>> branch the trunk:
>>>
>>> r20:
>>> trunk
>>> /A
>>> /B
>>> branch
>>> /A (pointer to /trunk/A)
>>> /B (pointer to /trunk/B)
>>>
>>> modify branch/A:
>>>
>>> r30:
>>> trunk
>>> /A
>>> /B
>>> branch
>>> /A
>>> /B (pointer to /trunk/B)
>>>
>>> Now let's say we're diffing branch@20 and branch@30. I want to be
>>> able to report a mapping between each path in branch@20 and the path
>>> in r30 corresponding to "the same node", where "the same node" is to
>>> be defined in some way that makes sense for tracking moves. In this
>>> simple example, there are not even any moves, and so I want the move-
>>> tracking code to be able to deduce the following 1:1 path-mapping
>>> between branch@20 and branch@20:
>>>
>>> PATH@20 PATH@30
>>> branch <-> branch
>>> branch/A <-> branch/A
>>> branch/B <-> branch/B
>>>
>>> It certainly must not report a simple (node-id, copy-id) correspondence,
>>> because that would look something like:
>>>
>>> PATH@20 PATH@30
>>> branch <-> branch
>>> branch/A <-> trunk/A # or (nil) as it's out of tree-scope
>>> (nil) <-> branch/A
>>> branch/B <-> branch/B
>>> which breaks the mapping between branch/A@20 and branch/A@30.
>> I'm confused. What are you trying to solve here?
> The query I'm trying to solve is: for the paths I can see in 'branch' in r20, tell me where they are in r30.
>
> The example I gave above is the simplest case, the degenerate case, as they have not even been moved, but a typical interesting case is the above plus some moves:
>
> r40: move A to C, and move B to D
>
> So the repository in r40 looks like:
>
> r40:
> trunk
> /A
> /B
> branch
> /C
> /D
>
> Now we query: for each path in 'branch' in r20, where is "it" (the same node-line) in r40? The query is to be answered without scanning all intervening revisions sequentially.
Fine, but this has nothing at all to do with moves. It's the
forward-history search problem, which the current storage model cannot
solve easily because of immutable revision files. We'd need an
additional index that inverts the predecessor links. AUIU FSX is
designed to solve that, as is the metadata-ng model.
Note that any history scanning we do today is a linear scan through the
predecessor links. I don't know why you're trying to optimize that as
part of the move design.
-- Brane
--
Branko Čibej | Director of Subversion
WANdisco // Non-Stop Data
e. brane@wandisco.com
Re: Moves in FSFS
Posted by Julian Foad <ju...@btopenworld.com>.
Branko Čibej wrote:
> On 17.09.2013 12:55, Julian Foad wrote:
> [...]
>> Start with
>>
>> r10:
>> trunk
>> /A
>> /B
>>
>> branch the trunk:
>>
>> r20:
>> trunk
>> /A
>> /B
>> branch
>> /A (pointer to /trunk/A)
>> /B (pointer to /trunk/B)
>>
>> modify branch/A:
>>
>> r30:
>> trunk
>> /A
>> /B
>> branch
>> /A
>> /B (pointer to /trunk/B)
>>
>> Now let's say we're diffing branch@20 and branch@30. I want to be
>> able to report a mapping between each path in branch@20 and the path
>> in r30 corresponding to "the same node", where "the same node" is to
>> be defined in some way that makes sense for tracking moves. In this
>> simple example, there are not even any moves, and so I want the move-
>> tracking code to be able to deduce the following 1:1 path-mapping
>> between branch@20 and branch@20:
>>
>> PATH@20 PATH@30
>> branch <-> branch
>> branch/A <-> branch/A
>> branch/B <-> branch/B
>>
>> It certainly must not report a simple (node-id, copy-id) correspondence,
>> because that would look something like:
>>
>> PATH@20 PATH@30
>> branch <-> branch
>> branch/A <-> trunk/A # or (nil) as it's out of tree-scope
>> (nil) <-> branch/A
>> branch/B <-> branch/B
>> which breaks the mapping between branch/A@20 and branch/A@30.
>
> I'm confused. What are you trying to solve here?
The query I'm trying to solve is: for the paths I can see in 'branch' in r20, tell me where they are in r30.
The example I gave above is the simplest case, the degenerate case, as they have not even been moved, but a typical interesting case is the above plus some moves:
r40: move A to C, and move B to D
So the repository in r40 looks like:
r40:
trunk
/A
/B
branch
/C
/D
Now we query: for each path in 'branch' in r20, where is "it" (the same node-line) in r40? The query is to be answered without scanning all intervening revisions sequentially.
- Julian
Re: Moves in FSFS
Posted by Branko Čibej <br...@wandisco.com>.
On 17.09.2013 12:55, Julian Foad wrote:
[...]
> Start with
>
> r10:
> trunk
> /A
> /B
>
> branch the trunk:
>
> r20:
> trunk
> /A
> /B
> branch
> /A (pointer to /trunk/A)
> /B (pointer to /trunk/B)
>
> modify branch/A:
>
> r30:
> trunk
> /A
> /B
> branch
> /A
> /B (pointer to /trunk/B)
>
> Now
> let's say we're diffing branch@20 and branch@30. I want to be able to
> report a mapping between each path in branch@20 and the path in r30
> corresponding to "the same node", where "the same node" is to be defined
> in some way that makes sense for tracking moves. In this simple
> example, there are not even any moves, and so I want the move-tracking
> code to be able to deduce the following 1:1 path-mapping between
> branch@20 and branch@20:
>
> PATH@20 PATH@30
> branch <-> branch
> branch/A <-> branch/A
> branch/B <-> branch/B
>
> It certainly must not report a simple (node-id, copy-id) correspondence, because that would look something like:
>
> PATH@20 PATH@30
> branch <-> branch
> branch/A <-> trunk/A # or (nil) as it's out of tree-scope
> (nil) <-> branch/A
> branch/B <-> branch/B
> which breaks the mapping between branch/A@20 and branch/A@30.
I'm confused. What are you trying to solve here? Subversion already
knows how to look through copies to find node equivalence. Your example
here has nothing to do with move tracking, and furthermore this problem
is already solved in the current implementation.
-- Brane
--
Branko Čibej | Director of Subversion
WANdisco // Non-Stop Data
e. brane@wandisco.com
Re: Moves in FSFS
Posted by Julian Foad <ju...@btopenworld.com>.
>> Branko Čibej <br...@wandisco.com> writes:
>>> That said, I still do not understand why a different ID would be needed
>>> before the copy-on-write happens. Is it because the client doesn't have
>>> the full history available? [...]
Hi Brane.
Ref. <http://wiki.apache.org/subversion/MoveDev/MoveDev#Move_Semantics>.
A different id (than node-id+copy-id) is needed because I prefer to
describe the semantics of moves (on the server) in such a way, not because of anything
to do with the client side, nor anything to do with existing or potential editor designs.
Some important move-tracking query APIs are ones which will map between paths in one revision and "corresponding" paths in another revision. For these purposes I believe the abstract model we need to present is one in which copying a directory creates new lines of history ("node-lines") for all nodes in the subtree, even though their content may not have diverged yet. In other words, for the purposes of a query that asks "where" (at what path) in revision REV2 we would find the node corresponding to that at PATH1@REV1, it should behave the same *as if* copies were always full copies and never lazy. (Conversely, in merging, for the purpose of finding a common ancestor of changes to be merged, it may be easier to work with the late branching / lazy-copy model, as the nearest common ancestor can be nearer.)
The "node-line" concept is merely a tool to aid in the definition of the semantics. I am not suggesting here that the node-line-id should be transmitted to the client or used in the editor APIs. (Those are separate discussions in which we may or may not want to use such a concept.)
Do you object to my using this invented concept as a tool within the semantic specification, or do you object to this abstract concept being made concrete and stored and exposed? Do you disagree with the semantics I defined, or find it hard to interpret, or is it that you would prefer to describe the same thing in a different way? I'm not clear.
The same semantics could of course be defined in other ways. However the definition as I've written it clearly doesn't work if we just write (node-id, copy-id) in place of (node-line-id). Here is an example of how it makes a difference.
Start with
r10:
trunk
/A
/B
branch the trunk:
r20:
trunk
/A
/B
branch
/A (pointer to /trunk/A)
/B (pointer to /trunk/B)
modify branch/A:
r30:
trunk
/A
/B
branch
/A
/B (pointer to /trunk/B)
Now
let's say we're diffing branch@20 and branch@30. I want to be able to
report a mapping between each path in branch@20 and the path in r30
corresponding to "the same node", where "the same node" is to be defined
in some way that makes sense for tracking moves. In this simple
example, there are not even any moves, and so I want the move-tracking
code to be able to deduce the following 1:1 path-mapping between
branch@20 and branch@20:
PATH@20 PATH@30
branch <-> branch
branch/A <-> branch/A
branch/B <-> branch/B
It certainly must not report a simple (node-id, copy-id) correspondence, because that would look something like:
PATH@20 PATH@30
branch <-> branch
branch/A <-> trunk/A # or (nil) as it's out of tree-scope
(nil) <-> branch/A
branch/B <-> branch/B
which breaks the mapping between branch/A@20 and branch/A@30.
Hi Philip.
Branko Čibej wrote:
> Philip Martin wrote:
>> Another way to provide the moves between arbitrary revisions is to have
>> an id to path map per revision which allows the FS to find the path
>> associated with a given id. However with lazy-copy this map is harder
>> to implement.
Harder in the sense that a naive map from each node-line-id to each reachable path in the revision would require adding N entries to the map when copying a subtree of N nodes, thus making copy no longer O(1). To maintain O(1) copies we'd need something cleverer.
In my present definition of move semantics, the ids used in this map would be what I call "node-line" ids, not the raw (node-id, copy-id) pairs. How copy-ids work is thus irrelevant to me. (Reading between the lines, I think with your questions about how copy-id assignment works you meant to question how copy-id could possibly be used to answer move tracking queries, whereas Brane answered them as direct questions about how copy-id assignment currently works.)
- Julian
Re: Moves in FSFS
Posted by Stefan Fuhrmann <st...@wandisco.com>.
On Wed, Sep 18, 2013 at 1:05 PM, Stefan Fuhrmann <
stefan.fuhrmann@wandisco.com> wrote:
> On Fri, Sep 13, 2013 at 12:41 PM, Branko Čibej <br...@wandisco.com> wrote:
>
>> On 13.09.2013 11:32, Philip Martin wrote:
>> > Branko Čibej <br...@wandisco.com> writes:
>> >
>> >> That said, I still do not understand why a different ID would be needed
>> >> before the copy-on-write happens. Is it because the client doesn't have
>> >> the full history available? If that's the case, I suggest we explore
>> >> this on a case-by-case basis, including determining how the initial
>> >> state of a working copy for each case can actually occur.
>> > Is the FS going only able to provide the moves that apply between two
>> > consecutive revisions? Or is it able to provide the combined moves
>> > between arbitrary revisions?
>> >
>> > One way to provide the moves between arbitrary revisions is to iterate
>> > through the intervening revisions accumulating and combining the moves.
>> > That has the potential to be slow.
>> >
>> > Another way to provide the moves between arbitrary revisions is to have
>> > an id to path map per revision which allows the FS to find the path
>> > associated with a given id. However with lazy-copy this map is harder
>> > to implement.
>> >
>> > There is another aspect to the lazy-copy which is when does the new
>> > copy-id get assigned to the lazy children. If we commit
>> >
>> > move A/f A/g
>> >
>> > then move does not allocate a new copy-id and A/f has the same copy-id
>> > as A/g. I think we intend this to be true if the commit combines a move
>> > and a modification to the node. Now commit:
>> >
>> > copy A B
>> >
>> > here B gets a new copy-id and lazily copied children of B still have the
>> > old copy-id. Now what about this commit:
>> >
>> > move B/g B/h
>> >
>> > Does move preserve the copy-id so that B/h is still a reference to A/g?
>>
>> A move through the copied parent has to be interpreted as a write to the
>> subtree, which means that the copy-on-write semantics kick in. The move
>> then breaks down into:
>>
>> make-mutable B/g <-- lazy copy, assigns a new copy-id
>> move B/g B/h <-- move semantics, B/h keeps same copy-id
>>
>> You'll not that "make-mutable" is an implementation detail of the
>> top-down DAG FS model, and it already does what I described above. This
>> is not some new code we'd have to write to implement moves this way; we
>> just have to obey existing rules, i.e., before operating on a path
>> within an FS transaction, the path must first be made mutable. In other
>> words, the FS implementation already works the way I described,
>> regardless of whether the actual operation is "move" or something else.
>>
>> > If the commit was a combined move/modification then B/h would have to
>> > get a new copy-id.
>>
>> It has to get one in any case, as explained above. Operations that
>> affect the state of a node, when performed on a path that contains a
>> copied parent, must produce the same result regardless of whether the
>> filesystem implements lazy copying or not. For the purpose of this
>> model, the node's path is part of its state; although of course the path
>> is not in fact a unique property of the node.
>>
>> But it's not necessary to assign new IDs when the node's state is
>> /read/; i.e., we do not need copy-on-read in order for this model to
>> work. The only consideration is that all operations must work correctly
>> with or without lazy copying. It's OK IMO to let the lazy-copy detail
>> leak outside the FS implementation, as long as we do not make it a
>> required feature.
>>
>
> Hi Brane,
>
> As described above, the ID assignment works for FSFS
> internals but is insufficient to answer the following question:
>
> Are pathA@rA and pathB@rB points on the same line of history?
>
> The more theoretical background can be found in my other post,
> but the following example should illustrate the problem:
>
> rN: cp A B, add C (A has sub-nodes A/1, A/1/a, A/1/b, A/1/c)
> rN+1: mv B/1 B/3, modify A/1/c, modify B/3/a
> rN+2: mv A/1/c B/2, mv A/1/b C/2
> rN+3: modify B/2, modify C/2
>
> Now, the following statements are true ("related" here means
> "on the same line of history"):
>
> (1) A/1/b@N and A/1/b@N+1 have the same IDs and are related
> (2) A/1/a@N and B/1/a@N+1 have the same IDs and are unrelated
>
> (3) A/1/c@N and A/1/c@N+1 have same (node,copy) and are related
> (4) B/1/c@N and A/1/c@N+1 have same (node,copy) and are unreleated
> (5) B/1/a@N and B/3/a@N+1 have different copyIDs and are related
> (6) A/1/a@N and B/3/a@N+1 have different copyIDs and are unrelated
>
> (7) A@N+1 and B@N+2 have different copyIDs and are unrelated,
> A/1/c@N+1 and B/2@N+2 have the same IDs and are related
> (8) A@N+1 and B@N+3 have different copyIDs and are unrelated,
> A/1/c@N+1 and B/2@N+3 have the different copyIDs and are related
> (9) A@N+1 and C@N+2 have different IDs and are unrelated,
> A/1/c@N+1 and B/2@N+2 have the same IDs and are related
> (10) A@N+1 and C@N+3 have different IDs and are unrelated,
> A/1/b@N+1 and C/2@N+3 have the different copyIDs and are related
>
> (11) A@N and C@N+1 have different nodeIDs and are unrelated
>
> I.e. only a different nodeID can guarantee a different line of history
> but this is a relatively rare case with node and copy IDs matching
> being the vast majority.
>
> For the same line of history as well as different lines of history
>
> * (nodeID, copyID) may be the same and revIDs *differ or not*
> * nodeID may be the same and copyID + revID may *differ or not*
> * parents may be *related or not*
>
> The latter is the most devastating part since it makes a top-down
> approach impossible where matching IDs could at least guarantee
> relatedness (mismatches would require further investigation).
>
> My feeling is that the fundamental problem is the combination of
> * #DAG nodes total < #paths @ rev
> * moves are not local, i.e. obliterate any parent context
>
> So, do are you still convinced that nodeID and copyID are useful
> for the detection of moves? If so, how do they apply to the cases
> listed above?
>
A more concrete example:
(/trunk/A/ contains *.c and *.h files)
rN: cp /trunk/A /trunk/B,
mv /trunk/B/* /trunk/B/b_*
modify /trunk/A/*, /trunk/B/b_*
rN+1: cp /trunk /branch
rN+2: add /branch/include,
mv /branch/A/*.h /branch/include/*.h,
mv /branch/B/*.h /branch/include/*.h
rN+3: modify /branch/A/*.c, /branch/B/*.c, /branch/include/*.h
rN+4: add /branch/src,
mv /branch/A/*.c /branch/src/*.c,
mv /branch/B/*.c /branch/src/*.c,
The user wants to update her working copy from /branch@rN+1
to /branch@rN+3. How do you identify the moves?
-- Stefan^2.
Re: Moves in FSFS
Posted by Stefan Fuhrmann <st...@wandisco.com>.
On Fri, Sep 13, 2013 at 12:41 PM, Branko Čibej <br...@wandisco.com> wrote:
> On 13.09.2013 11:32, Philip Martin wrote:
> > Branko Čibej <br...@wandisco.com> writes:
> >
> >> That said, I still do not understand why a different ID would be needed
> >> before the copy-on-write happens. Is it because the client doesn't have
> >> the full history available? If that's the case, I suggest we explore
> >> this on a case-by-case basis, including determining how the initial
> >> state of a working copy for each case can actually occur.
> > Is the FS going only able to provide the moves that apply between two
> > consecutive revisions? Or is it able to provide the combined moves
> > between arbitrary revisions?
> >
> > One way to provide the moves between arbitrary revisions is to iterate
> > through the intervening revisions accumulating and combining the moves.
> > That has the potential to be slow.
> >
> > Another way to provide the moves between arbitrary revisions is to have
> > an id to path map per revision which allows the FS to find the path
> > associated with a given id. However with lazy-copy this map is harder
> > to implement.
> >
> > There is another aspect to the lazy-copy which is when does the new
> > copy-id get assigned to the lazy children. If we commit
> >
> > move A/f A/g
> >
> > then move does not allocate a new copy-id and A/f has the same copy-id
> > as A/g. I think we intend this to be true if the commit combines a move
> > and a modification to the node. Now commit:
> >
> > copy A B
> >
> > here B gets a new copy-id and lazily copied children of B still have the
> > old copy-id. Now what about this commit:
> >
> > move B/g B/h
> >
> > Does move preserve the copy-id so that B/h is still a reference to A/g?
>
> A move through the copied parent has to be interpreted as a write to the
> subtree, which means that the copy-on-write semantics kick in. The move
> then breaks down into:
>
> make-mutable B/g <-- lazy copy, assigns a new copy-id
> move B/g B/h <-- move semantics, B/h keeps same copy-id
>
> You'll not that "make-mutable" is an implementation detail of the
> top-down DAG FS model, and it already does what I described above. This
> is not some new code we'd have to write to implement moves this way; we
> just have to obey existing rules, i.e., before operating on a path
> within an FS transaction, the path must first be made mutable. In other
> words, the FS implementation already works the way I described,
> regardless of whether the actual operation is "move" or something else.
>
> > If the commit was a combined move/modification then B/h would have to
> > get a new copy-id.
>
> It has to get one in any case, as explained above. Operations that
> affect the state of a node, when performed on a path that contains a
> copied parent, must produce the same result regardless of whether the
> filesystem implements lazy copying or not. For the purpose of this
> model, the node's path is part of its state; although of course the path
> is not in fact a unique property of the node.
>
> But it's not necessary to assign new IDs when the node's state is
> /read/; i.e., we do not need copy-on-read in order for this model to
> work. The only consideration is that all operations must work correctly
> with or without lazy copying. It's OK IMO to let the lazy-copy detail
> leak outside the FS implementation, as long as we do not make it a
> required feature.
>
Hi Brane,
As described above, the ID assignment works for FSFS
internals but is insufficient to answer the following question:
Are pathA@rA and pathB@rB points on the same line of history?
The more theoretical background can be found in my other post,
but the following example should illustrate the problem:
rN: cp A B, add C (A has sub-nodes A/1, A/1/a, A/1/b, A/1/c)
rN+1: mv B/1 B/3, modify A/1/c, modify B/3/a
rN+2: mv A/1/c B/2, mv A/1/b C/2
rN+3: modify B/2, modify C/2
Now, the following statements are true ("related" here means
"on the same line of history"):
(1) A/1/b@N and A/1/b@N+1 have the same IDs and are related
(2) A/1/a@N and B/1/a@N+1 have the same IDs and are unrelated
(3) A/1/c@N and A/1/c@N+1 have same (node,copy) and are related
(4) B/1/c@N and A/1/c@N+1 have same (node,copy) and are unreleated
(5) B/1/a@N and B/3/a@N+1 have different copyIDs and are related
(6) A/1/a@N and B/3/a@N+1 have different copyIDs and are unrelated
(7) A@N+1 and B@N+2 have different copyIDs and are unrelated,
A/1/c@N+1 and B/2@N+2 have the same IDs and are related
(8) A@N+1 and B@N+3 have different copyIDs and are unrelated,
A/1/c@N+1 and B/2@N+3 have the different copyIDs and are related
(9) A@N+1 and C@N+2 have different IDs and are unrelated,
A/1/c@N+1 and B/2@N+2 have the same IDs and are related
(10) A@N+1 and C@N+3 have different IDs and are unrelated,
A/1/b@N+1 and C/2@N+3 have the different copyIDs and are related
(11) A@N and C@N+1 have different nodeIDs and are unrelated
I.e. only a different nodeID can guarantee a different line of history
but this is a relatively rare case with node and copy IDs matching
being the vast majority.
For the same line of history as well as different lines of history
* (nodeID, copyID) may be the same and revIDs *differ or not*
* nodeID may be the same and copyID + revID may *differ or not*
* parents may be *related or not*
The latter is the most devastating part since it makes a top-down
approach impossible where matching IDs could at least guarantee
relatedness (mismatches would require further investigation).
My feeling is that the fundamental problem is the combination of
* #DAG nodes total < #paths @ rev
* moves are not local, i.e. obliterate any parent context
So, do are you still convinced that nodeID and copyID are useful
for the detection of moves? If so, how do they apply to the cases
listed above?
-- Stefan^2.
Re: Moves in FSFS
Posted by Branko Čibej <br...@wandisco.com>.
On 18.09.2013 10:50, Branko Čibej wrote:
> Given all of the above, we're talking about the following algorithm for
> move of src to tgt (I'm ignoring parent change, for clarity):
>
> if src is lazy:
> make-mutable(src)
> else:
> make-mutable(dirname(src))
> modify-dir-list(dirname(src), basename(src), basename(tgt))
>
> All of that complication merely to avoid creating a new node-revision
> record. On top of the other issues (e.g., the move not being obvious
> from the txn record), I hardly think this optimization is worth the
> trouble. It doesn't actually gain us anything.
Oh, and all of the above does not take account of rebase-for-commit
(a.k.a libsvn_fs_base/tree.c:merge). I haven't looked closely at that
code, but wouldn't be surprised if the absence of a node-revision record
for the moved node would complicate that code.
-- Brane
--
Branko Čibej | Director of Subversion
WANdisco // Non-Stop Data
e. brane@wandisco.com
Re: Moves in FSFS
Posted by Branko Čibej <br...@wandisco.com>.
On 17.09.2013 13:43, Julian Foad wrote:
> Branko Čibej wrote:
>> Note that in the current FS implementation, there is not "node" object
>> as such; there are only node-revision records, and the concept of a
>> "node" is extrapolated from the node-id, just as a branch is
>> extrapolated from the copy-id.
>>
>> Let me reiterate: the result of a "move" in the FS representation should
>> be exactly the same as the result of a text or prop modification. I
>> believe our top-down DAG model relies on that being the case.
> I assume you mean "the same" only in terms of new id assignment, not (for example) that it would necessarily create a new representation of the data content. I'd be interested to see what part of the DAG model relies on that.
Thinking about this some more, I've come to the conclusion that as far
as the DAG is concerned, we could implement ordinary moves as
parent-directory modifications. However, this would complicate the
implementation because it would have to behave differently for moves
than for other operations, and differently when the affected node is
lazy or not. Consider:
move A/g A/h
can be represented as:
make-mutable A
modify A (rename pointer to child "g" to "h")
But the lazy case is different:
copy A B
move B/g B/h
In this case, you have to make the copy concrete before you implement
the move, or you're actually changing history; so the representation of
the move has to be:
make-mutable B (assigns new copy-id)
modify A (rename pointer to child "g" to "h")
(note that A is already mutable as a result of bubble-up)
While you could, theoretically, do the same thing as in the ordinary
move case, the net effect would be that the move and copy could be
recorded out-of-order in the repository history, since the copy-on-write
would probably happen eventually due to a modification od B/h. Of course
we still have the changes list that would presumably be in the correct
order, but it's IMO a bad idea if "changes" cannot be mapped to actual
structures in the DAG.
Given all of the above, we're talking about the following algorithm for
move of src to tgt (I'm ignoring parent change, for clarity):
if src is lazy:
make-mutable(src)
else:
make-mutable(dirname(src))
modify-dir-list(dirname(src), basename(src), basename(tgt))
All of that complication merely to avoid creating a new node-revision
record. On top of the other issues (e.g., the move not being obvious
from the txn record), I hardly think this optimization is worth the
trouble. It doesn't actually gain us anything.
-- Brane
--
Branko Čibej | Director of Subversion
WANdisco // Non-Stop Data
e. brane@wandisco.com
Re: Moves in FSFS
Posted by Julian Foad <ju...@btopenworld.com>.
Julian Foad wrote:
> Branko Čibej wrote:
>> On 17.09.2013 13:12, Julian Foad wrote:
>>> But why does "move" need to create a new node-revision of the moved
>>> node [...]? Why shouldn't it just create a new reference [...]?
>>
>> Becasue otherwise you can't tell there was a move without comparing
>> parent directory contents, and worse, you can't tell that the node was
>> affected by a particular commit. And I hope you'll agree the latter bit
>> of info is kind of important.
>
> You can tell in other ways. (1) you can find it in the "changes" list
> for the revision. (2) if you have an index of (revision, node-line-id)
> to path, you can look up the node-line-id in that.
>
> But I suppose you're well aware of that, and so presumably you mean
> something more specific: that from a history walk (as in "log") of the
> particular (node-id, copy-id) across a revision range, you want to discover
> a point where it says "I was moved", like we discover an entry that says
> "I was copied", and you want to get that info efficiently, so you want
> to have the relevant revision number encoded into the id. I agree users
> would expect to see an entry for the node in "svn log"; I don't know for
> sure that it needs a new node-revision-id in order to accomplish this
> efficiently. I agree it's a possible and reasonable solution.
I'd like to withdraw my argument. I am merely curious. I don't know enough about FS internals and if it needs to assign a new node-rev-id then so be it, I can accept that for now without having to understand exactly why. I shouldn't need to care about these details right now because I should be concentrating on the API semantics and not on how FSFS achieves them.
On the subject of the API, I'd like now to look at defining the FS API for moves.
We have been discussing whether the commit editor (and also the update editor) should use a sequential model (ordered, and referring always to the current state) or a commutative model (unordered, or less strictly ordered, and referring always to the initial state) for moves.
Editing a FS transaction is naturally a sequential, stateful activity. A transaction is, after all, the embodiment of a state. However, the FS layer has the luxury of guaranteed easy access to the initial state at all times, and so it seems that we can still choose either model for the FS layer API. So I'm going to look next at how they compare.
In <http://wiki.apache.org/subversion/MoveDev/MovesInFSFS> I have already written a brief specification for an svn_fs_move() API, assuming the sequential model,
but that
may not be the best option.
Talking with Brane the other day, we discussed that my analysis of move semantics so far has been rather framed in the context of one particular representation or another (move-away, move-here, for example) and he would like to see a more neutral description, a mathematical model if you like. This should make it easier to compare the pros and cons of different representations without bias, and for example to see whether my "node-line-id" concept is unnecessary. So I'm also going to take a stab at such a description.
- Julian
Re: Moves in FSFS
Posted by Julian Foad <ju...@btopenworld.com>.
Branko Čibej wrote:
> On 17.09.2013 13:12, Julian Foad wrote:
>> But why does "move" need to create a new node-revision of the
>> moved node itself (assuming the node isn't lazy-copied and isn't about
>> to be modified). Why shouldn't it just create a new reference to the
>> existing old node-revision? (Of course it needs to create a new node-rev
>> of the parent directory because the parent's list of children changes.)
>
> Becasue otherwise you can't tell there was a move without comparing
> parent directory contents, and worse, you can't tell that the node was
> affected by a particular commit. And I hope you'll agree the latter bit
> of info is kind of important.
You can tell in other ways. (1) you can find it in the "changes" list for the revision. (2) if you have an index of (revision, node-line-id) to path, you can look up the node-line-id in that.
But I suppose you're well aware of that, and so presumably you mean something more specific: that from a history walk (as in "log") of the particular (node-id, copy-id) across a revision range, you want to discover a point where it says "I was moved", like we discover an entry that says "I was copied", and you want to get that info efficiently, so you want to have the relevant revision number encoded into the id. I agree users would expect to see an entry for the node in "svn log"; I don't know for sure that it needs a new node-revision-id in order to accomplish this efficiently. I agree it's a possible and reasonable solution.
> Note that in the current FS implementation, there is not "node" object
> as such; there are only node-revision records, and the concept of a
> "node" is extrapolated from the node-id, just as a branch is
> extrapolated from the copy-id.
>
> Let me reiterate: the result of a "move" in the FS representation should
> be exactly the same as the result of a text or prop modification. I
> believe our top-down DAG model relies on that being the case.
I assume you mean "the same" only in terms of new id assignment, not (for example) that it would necessarily create a new representation of the data content. I'd be interested to see what part of the DAG model relies on that.
- Julian
Re: Moves in FSFS
Posted by Branko Čibej <br...@wandisco.com>.
On 17.09.2013 13:12, Julian Foad wrote:
> Branko Čibej wrote:
>> On 17.09.2013 12:46, Philip Martin wrote:
>>> I still don't understand. For a change like a text edit we always call
>>> make-mutable and it always gives a new id, either changing the
>>> revision-id or the copy-id. It's not clear to me that there should be
>>> a make-mutable call before a move.
>> The result of a move needs a new revision-id. Of course you have to make
>> the node mutable before you modify it, and "move" modifies the node in
>> the sense that it creates a new node-revision.
> But why does "move" need to create a new node-revision of the moved node itself (assuming the node isn't lazy-copied and isn't about to be modified). Why shouldn't it just create a new reference to the existing old node-revision? (Of course it needs to create a new node-rev of the parent directory because the parent's list of children changes.)
Becasue otherwise you can't tell there was a move without comparing
parent directory contents, and worse, you can't tell that the node was
affected by a particular commit. And I hope you'll agree the latter bit
of info is kind of important.
Note that in the current FS implementation, there is not "node" object
as such; there are only node-revision records, and the concept of a
"node" is extrapolated from the node-id, just as a branch is
extrapolated from the copy-id.
Let me reiterate: the result of a "move" in the FS representation should
be exactly the same as the result of a text or prop modification. I
believe our top-down DAG model relies on that being the case.
-- Brane
--
Branko Čibej | Director of Subversion
WANdisco // Non-Stop Data
e. brane@wandisco.com
Re: Moves in FSFS
Posted by Julian Foad <ju...@btopenworld.com>.
Branko Čibej wrote:
> On 17.09.2013 12:46, Philip Martin wrote:
>> I still don't understand. For a change like a text edit we always call
>> make-mutable and it always gives a new id, either changing the
>> revision-id or the copy-id. It's not clear to me that there should be
>> a make-mutable call before a move.
>
> The result of a move needs a new revision-id. Of course you have to make
> the node mutable before you modify it, and "move" modifies the node in
> the sense that it creates a new node-revision.
But why does "move" need to create a new node-revision of the moved node itself (assuming the node isn't lazy-copied and isn't about to be modified). Why shouldn't it just create a new reference to the existing old node-revision? (Of course it needs to create a new node-rev of the parent directory because the parent's list of children changes.)
- Julian
Re: Moves in FSFS
Posted by Branko Čibej <br...@wandisco.com>.
On 17.09.2013 12:46, Philip Martin wrote:
> Branko Čibej <br...@wandisco.com> writes:
>
>> On 13.09.2013 11:32, Philip Martin wrote:
>>> Branko Čibej <br...@wandisco.com> writes:
>>>
>>> There is another aspect to the lazy-copy which is when does the new
>>> copy-id get assigned to the lazy children. If we commit
>>>
>>> move A/f A/g
>>>
>>> then move does not allocate a new copy-id and A/f has the same copy-id
>>> as A/g. I think we intend this to be true if the commit combines a move
>>> and a modification to the node. Now commit:
>>>
>>> copy A B
>>>
>>> here B gets a new copy-id and lazily copied children of B still have the
>>> old copy-id. Now what about this commit:
>>>
>>> move B/g B/h
>>>
>>> Does move preserve the copy-id so that B/h is still a reference to A/g?
>> A move through the copied parent has to be interpreted as a write to the
>> subtree, which means that the copy-on-write semantics kick in. The move
>> then breaks down into:
>>
>> make-mutable B/g <-- lazy copy, assigns a new copy-id
>> move B/g B/h <-- move semantics, B/h keeps same copy-id
>>
>> You'll not that "make-mutable" is an implementation detail of the
>> top-down DAG FS model, and it already does what I described above. This
>> is not some new code we'd have to write to implement moves this way; we
>> just have to obey existing rules, i.e., before operating on a path
>> within an FS transaction, the path must first be made mutable. In other
>> words, the FS implementation already works the way I described,
>> regardless of whether the actual operation is "move" or something else.
> I still don't understand. For a change like a text edit we always call
> make-mutable and it always gives a new id, either changing the
> revision-id or the copy-id. It's not clear to me that there should be a
> make-mutable call before a move.
The result of a move needs a new revision-id. Of course you have to make
the node mutable before you modify it, and "move" modifies the node in
the sense that it creates a new node-revision. In the normal case, it
creates a new node-revision instance, with same node-id and copy-id and
new revision-id; in the lazy case, it also generates a new copy-id. In
other words, it behaves exactly as a regular text or property modification.
Note that make-mutable also takes care of directory bubble-up in the
current top-down DAG model.
> I started with a move:
>
> move A/f A/g
>
> There is no lazy copy here and I thought the plan was that a move would
> not change the id, so A/g would be a reference to the same node as A/f.
> Is there a make-mutable call here?
Of coruse there is, but because A/f is not "lazy", the make-mutable step
will not generate a new copy-id.
> The next move is after lazy copy:
>
> move B/g B/h
>
> You say there is a make-mutable call here and B/h has a new copy-id. If
> the move was combined with a text change the make-mutable is required,
> but is it required for a move alone?
Yes. Otherwise you break the model. A move after a copy refers to the
copied node, so you have to unlazify the copy (apply copy-on-write)
before applying the move.
> Suppose I had committed a text
> edit to B/g before moving it to B/h. The text-edit would have called
> make-mutable and allocated a new copy-id. Would the subsequent move
> above still call make-mutable?
make-mutable has no effect on a mutable node. I don't recall whether we
try to avoid multiple calls to make-mutable, or just make the call and
not worry about nodes already being mutable. In any event, the end
result shoudl be the same: a mutable node-revision in the current
transaction.
> Suppose I make a third move:
>
> move B/h B/i
>
> I assume this move is like the first move and it doesn't change the
> id. Is there a make-mutable call here?
Yes, there always is. You can even do this in the same transaction as
the "move B/g B/h", and the make-mutable will be a no-op and B/i will
retain the copy-id that was originally assigned when B/g was made
mutable. If you do this in a separate transaction, it's exactly as the
first example, "move A/f A/g".
-- Brane
--
Branko Čibej | Director of Subversion
WANdisco // Non-Stop Data
e. brane@wandisco.com
Re: Moves in FSFS
Posted by Philip Martin <ph...@wandisco.com>.
Branko Čibej <br...@wandisco.com> writes:
> On 13.09.2013 11:32, Philip Martin wrote:
>> Branko Čibej <br...@wandisco.com> writes:
>>
>> There is another aspect to the lazy-copy which is when does the new
>> copy-id get assigned to the lazy children. If we commit
>>
>> move A/f A/g
>>
>> then move does not allocate a new copy-id and A/f has the same copy-id
>> as A/g. I think we intend this to be true if the commit combines a move
>> and a modification to the node. Now commit:
>>
>> copy A B
>>
>> here B gets a new copy-id and lazily copied children of B still have the
>> old copy-id. Now what about this commit:
>>
>> move B/g B/h
>>
>> Does move preserve the copy-id so that B/h is still a reference to A/g?
>
> A move through the copied parent has to be interpreted as a write to the
> subtree, which means that the copy-on-write semantics kick in. The move
> then breaks down into:
>
> make-mutable B/g <-- lazy copy, assigns a new copy-id
> move B/g B/h <-- move semantics, B/h keeps same copy-id
>
> You'll not that "make-mutable" is an implementation detail of the
> top-down DAG FS model, and it already does what I described above. This
> is not some new code we'd have to write to implement moves this way; we
> just have to obey existing rules, i.e., before operating on a path
> within an FS transaction, the path must first be made mutable. In other
> words, the FS implementation already works the way I described,
> regardless of whether the actual operation is "move" or something else.
I still don't understand. For a change like a text edit we always call
make-mutable and it always gives a new id, either changing the
revision-id or the copy-id. It's not clear to me that there should be a
make-mutable call before a move.
I started with a move:
move A/f A/g
There is no lazy copy here and I thought the plan was that a move would
not change the id, so A/g would be a reference to the same node as A/f.
Is there a make-mutable call here?
The next move is after lazy copy:
move B/g B/h
You say there is a make-mutable call here and B/h has a new copy-id. If
the move was combined with a text change the make-mutable is required,
but is it required for a move alone? Suppose I had committed a text
edit to B/g before moving it to B/h. The text-edit would have called
make-mutable and allocated a new copy-id. Would the subsequent move
above still call make-mutable?
Suppose I make a third move:
move B/h B/i
I assume this move is like the first move and it doesn't change the
id. Is there a make-mutable call here?
--
Philip Martin | Subversion Committer
WANdisco // *Non-Stop Data*
Re: Moves in FSFS
Posted by Branko Čibej <br...@wandisco.com>.
On 13.09.2013 11:32, Philip Martin wrote:
> Branko Čibej <br...@wandisco.com> writes:
>
>> That said, I still do not understand why a different ID would be needed
>> before the copy-on-write happens. Is it because the client doesn't have
>> the full history available? If that's the case, I suggest we explore
>> this on a case-by-case basis, including determining how the initial
>> state of a working copy for each case can actually occur.
> Is the FS going only able to provide the moves that apply between two
> consecutive revisions? Or is it able to provide the combined moves
> between arbitrary revisions?
>
> One way to provide the moves between arbitrary revisions is to iterate
> through the intervening revisions accumulating and combining the moves.
> That has the potential to be slow.
>
> Another way to provide the moves between arbitrary revisions is to have
> an id to path map per revision which allows the FS to find the path
> associated with a given id. However with lazy-copy this map is harder
> to implement.
>
> There is another aspect to the lazy-copy which is when does the new
> copy-id get assigned to the lazy children. If we commit
>
> move A/f A/g
>
> then move does not allocate a new copy-id and A/f has the same copy-id
> as A/g. I think we intend this to be true if the commit combines a move
> and a modification to the node. Now commit:
>
> copy A B
>
> here B gets a new copy-id and lazily copied children of B still have the
> old copy-id. Now what about this commit:
>
> move B/g B/h
>
> Does move preserve the copy-id so that B/h is still a reference to A/g?
A move through the copied parent has to be interpreted as a write to the
subtree, which means that the copy-on-write semantics kick in. The move
then breaks down into:
make-mutable B/g <-- lazy copy, assigns a new copy-id
move B/g B/h <-- move semantics, B/h keeps same copy-id
You'll not that "make-mutable" is an implementation detail of the
top-down DAG FS model, and it already does what I described above. This
is not some new code we'd have to write to implement moves this way; we
just have to obey existing rules, i.e., before operating on a path
within an FS transaction, the path must first be made mutable. In other
words, the FS implementation already works the way I described,
regardless of whether the actual operation is "move" or something else.
> If the commit was a combined move/modification then B/h would have to
> get a new copy-id.
It has to get one in any case, as explained above. Operations that
affect the state of a node, when performed on a path that contains a
copied parent, must produce the same result regardless of whether the
filesystem implements lazy copying or not. For the purpose of this
model, the node's path is part of its state; although of course the path
is not in fact a unique property of the node.
But it's not necessary to assign new IDs when the node's state is
/read/; i.e., we do not need copy-on-read in order for this model to
work. The only consideration is that all operations must work correctly
with or without lazy copying. It's OK IMO to let the lazy-copy detail
leak outside the FS implementation, as long as we do not make it a
required feature.
-- Brane
--
Branko Čibej | Director of Subversion
WANdisco // Non-Stop Data
e. brane@wandisco.com
Re: Moves in FSFS
Posted by Philip Martin <ph...@wandisco.com>.
Branko Čibej <br...@wandisco.com> writes:
> That said, I still do not understand why a different ID would be needed
> before the copy-on-write happens. Is it because the client doesn't have
> the full history available? If that's the case, I suggest we explore
> this on a case-by-case basis, including determining how the initial
> state of a working copy for each case can actually occur.
Is the FS going only able to provide the moves that apply between two
consecutive revisions? Or is it able to provide the combined moves
between arbitrary revisions?
One way to provide the moves between arbitrary revisions is to iterate
through the intervening revisions accumulating and combining the moves.
That has the potential to be slow.
Another way to provide the moves between arbitrary revisions is to have
an id to path map per revision which allows the FS to find the path
associated with a given id. However with lazy-copy this map is harder
to implement.
There is another aspect to the lazy-copy which is when does the new
copy-id get assigned to the lazy children. If we commit
move A/f A/g
then move does not allocate a new copy-id and A/f has the same copy-id
as A/g. I think we intend this to be true if the commit combines a move
and a modification to the node. Now commit:
copy A B
here B gets a new copy-id and lazily copied children of B still have the
old copy-id. Now what about this commit:
move B/g B/h
Does move preserve the copy-id so that B/h is still a reference to A/g?
If the commit was a combined move/modification then B/h would have to
get a new copy-id.
--
Philip Martin | Subversion Committer
WANdisco // *Non-Stop Data*
Re: Moves in FSFS
Posted by Branko Čibej <br...@wandisco.com>.
On 12.09.2013 12:14, Julian Foad wrote:
> Branko Čibej wrote:
>> On 11.09.2013 17:21, Julian Foad wrote:
>>> One issue that may be harder than it sounds at first is the concept of
>>> 'node-line-id' rather than (node-id, copy-id) as the basis of the
>>> definition. The point is that when we copy (ordinary copy, not move)
>>> a directory, we lazy-copy the children,
>> No we do not. I pointed out this fallacy before. We lazy-copy a child of
>> a copied directory *when* and *if* that child is itself modified through
>> the copied parent.
> Here you simply misunderstood me. As you know, a lazy copy consists of
> two parts: first we just refer to the old id, and (later, or never) we
> copy the content and assign a new id. When I said "we lazy-copy the
> children" I meant the former; you're using the same verb phrase to mean
> the latter. I'm sorry you found that confusing. Perhaps we can both
> try to be more explicit in future.
>
> FWIW it seems to me that the first part is the lazy part of the whole
> operation; the second part is where we pay for the earlier laziness. I
> searched in Subversion's source tree, in the book, and in the World-Wide
> Web, and couldn't find any precedent for "lazy copy" referring to just
> one half of the procedure.
Right. A possibly less confusing term would be "shared representation"
and "copy on write" because that's what we actually do, depending on the
path to which the write applies.
That said, I still do not understand why a different ID would be needed
before the copy-on-write happens. Is it because the client doesn't have
the full history available? If that's the case, I suggest we explore
this on a case-by-case basis, including determining how the initial
state of a working copy for each case can actually occur.
-- Brane
--
Branko Čibej | Director of Subversion
WANdisco // Non-Stop Data
e. brane@wandisco.com
Re: Moves in FSFS
Posted by Julian Foad <ju...@btopenworld.com>.
Branko Čibej wrote:
> On 11.09.2013 17:21, Julian Foad wrote:
>> One issue that may be harder than it sounds at first is the concept of
>> 'node-line-id' rather than (node-id, copy-id) as the basis of the
>> definition. The point is that when we copy (ordinary copy, not move)
>> a directory, we lazy-copy the children,
>
> No we do not. I pointed out this fallacy before. We lazy-copy a child of
> a copied directory *when* and *if* that child is itself modified through
> the copied parent.
Here you simply misunderstood me. As you know, a lazy copy consists of
two parts: first we just refer to the old id, and (later, or never) we
copy the content and assign a new id. When I said "we lazy-copy the
children" I meant the former; you're using the same verb phrase to mean
the latter. I'm sorry you found that confusing. Perhaps we can both
try to be more explicit in future.
FWIW it seems to me that the first part is the lazy part of the whole
operation; the second part is where we pay for the earlier laziness. I
searched in Subversion's source tree, in the book, and in the World-Wide
Web, and couldn't find any precedent for "lazy copy" referring to just
one half of the procedure.
- Julian
Re: Moves in FSFS
Posted by Branko Čibej <br...@wandisco.com>.
On 11.09.2013 17:21, Julian Foad wrote:
> One issue that may be harder than it sounds at first is the concept of
> 'node-line-id' rather than (node-id, copy-id) as the basis of the
> definition. The point is that when we copy (ordinary copy, not move)
> a directory, we lazy-copy the children,
No we do not. I pointed out this fallacy before. We lazy-copy a child of
a copied directory *when* and *if* that child is itself modified through
the copied parent.
> which means each child keeps
> its old (node-id, copy-id) unless and until it is modified. That's
> great for achieving the O(1) copy, but for move-tracking purposes each
> child needs a unique "node-line-id" so its life-line can be uniquely
> traced forward and back between this revision and a later revision by
> which time it may have been modified and thus assigned a new copy-id.
I still don't understand why you think you need that behaviour. An
object's "life-line" can already be "uniquely traced forward and back."
I think you simply have to stop thinking of a directory copy as if it
actually creates copies of its children. What it does is make them
visible via a new FS path, but that does not affect the children themselves.
-- Brane
--
Branko Čibej | Director of Subversion
WANdisco // Non-Stop Data
e. brane@wandisco.com
Re: Moves in FSFS
Posted by Branko Čibej <br...@wandisco.com>.
On 29.09.2013 19:34, Stefan Fuhrmann wrote:
>
> On Sat, Sep 28, 2013 at 12:36 PM, Branko Čibej <brane@wandisco.com
> <ma...@wandisco.com>> wrote:
>
>
> Exactly. And this is the second issue of the two I mentioned: in
> order to make merge aware of moves, as opposed to copies, you have
> to be able to detect that two distinct path@revision in fact refer
> to the same branch of a node -- which is exactly the (node-id,
> copy-id) pair, and that /is/ sufficient for the purpose. So again,
> there's no need to invent another branch-tracking identifier.
>
>
> Sigh. The (node,copy) pair *alone* cannot be sufficient to map
> move sources and targets.
That's not the case I'm talking about. I believe we already came to the
conclusion that, in FSFS, in order to answer the "what node got moved"
question, we need help from the changes list. However I maintain that we
don't need any extra info to answer the question, "are these two node
revisions on the same branch."
> In-depth reason: Once you accept that the move semantics as
> suggested by Julian's definition is what you want to support, *any*
> ID scheme must either be isomorphic to the node-line ID approach
> or a true superset of it. In the latter case you must provide auxiliary
> rules (can be implicit) that effectively limit the superset to the
> original.
> Otherwise, your implementation does not match the definition.
As I said, this is a different issue.
The jury's still out on whether I accept that definition of move
semantics or not; but in any case, detecting moves and detecting
sameness are different problems for different use cases.
-- Brane
--
Branko Čibej | Director of Subversion
WANdisco // Non-Stop Data
e. brane@wandisco.com
Re: Moves in FSFS
Posted by Stefan Fuhrmann <st...@wandisco.com>.
On Sat, Sep 28, 2013 at 12:36 PM, Branko Čibej <br...@wandisco.com> wrote:
> On 28.09.2013 12:06, Bill Tutt wrote:
>
> Move tracking can clearly make ones head spin. :)
>
> Brane: Could Julian and Stephan be asking about how to map between
> arbitrary revisions thinking of tree merge scenarios?
>
>
> There are two, somewhat related issues. The first involves understanding
> what actually happened to the tree, e.g., detecting that a certain change
> in the tree was a move, not something else. We realized more than 10 years
> ago that in our current top-down DAG model, getting this info just by
> analyzing the tree would be very expensive, and in some cases infeasible;
> so it doesn't really come as a surprise that looking just at the (node-id,
> copy-id) of a node revision is not enough.
>
> That's why the changes list was introduced (as the "changes" table in BDB,
> and an equivalent structure in FSFS); and I think we've come to the
> conclusion that it will have to be used to detect moves as well.
>
>
> That's what always gave me heart burn with the current Noderev behavior
> and envisioning real moves in Subversion.
>
>
> Yup.
>
>
> In thinking deep thoughts about this in the deep dark dark distant past
> I came up with several interesting thoughts: (sadly none of these are
> completely thought out answers, but they did seem like thoughts worth
> pondering wrt Subversion if you haven't before)
> * Have you considered having the noderev own the node's name instead of
> how the parent directory currently owns it? This way it would be natural to
> make the destination of the move a mutated noderev.
>
> Noderevs already know their full paths ("cpath") in FSFS and FSX.
Lazy copying always starts with a representation being shared not
with noderevs being shared as the top element.
>
> Yes. In fact I've made a stab at defining a different, IMO better model
> for storing versioned tree metadata; see:
>
>
> https://wiki.apache.org/subversion/Berlin2013?action=AttachFile&do=view&target=metadata-tng.pdf
>
> In this model, file names are represented as properties of the node, not
> its parent. It also does away with the necessity of having a separate
> changes list. But implementing it will be part of a larger effort which
> includes inventing a new API for the FS layer (in hindisght, we should
> never have exposed the top-down DAG as a public API).
>
>
> i.e. mv /trunk/A -> /trunk/B COULD do this in the DAG:
> * make /trunk/A mutable by ONLY updating the TxnID of the Noderev.
> * Edit the name field of the noderev from A ->B
> More complicated example:
> mv /trunk/A/B/C -> /trunk/A/D COULD do this to the DAG:
> * make /trunk/A/B/C mutable by ONLY updating the TxnID of the
> Noderev.
> * remove it as an entry from /trunk/A/B and add it as an entry to
> /trunk/A
> However... what do you do for this case: (C could have a zero copy_id here
> I think)
> mv /trunk/A/B/C -> /blah could do this to the DAG:
> ????
> or this one: (presuming C has a non-zero copy_id before move)
> mv /branch/A/B/C -> /blah2
> ????
> or (same as the last one, but C was the destination of the "soft-copy")
> ???
> The enumeration of the rest of the cases is left as an exercise for the
> reader. :)
>
>
> That PDF mentions many of these. :)
>
The thing is that we can do whatever we want inside a FS. The only
properties of IDs usably exposed through the FS API are:
* all IDs for path@rev must have a the same textual representation
* all IDs for path@rev must compare as "equal"
* if path exists continuously throughout a revision range (i.e. not being
added, deleted or replaced), any pairs of IDs for that path@ any rev
in that range must compare as "related"
* if path is added @rev *without* history, any ID of path@rev-X must
compare as "unrelated" to any ID for path@rev.
To make things slightly trickier, the required information should be
part of the ID object itself since the compare function does not take
a pool parameter.
A more interesting question is how to report moves in our "loggy" API.
Do they create log intervals like copies? If yes, "--stop-on-copy" would
retrieve multiple intervals with different paths. If no, the path may change
within any of these intervals. Client code must be very careful to match
paths correctly in both cases. We are subtly changing the implied API
semantics here.
> * The implementation of rename tracking should ensure you enable all
> scenarios you desire for dealing with merging renamed items from branch A
> to branch B. (the tree shape part of the merge of course)
> That is, if you care, some systems don't/won't/did and then decided not
> to/whatever. Merging renames leads to lousy complex edge case tree
> conflicts that need usable (in the easy to use usability sense) resolution
> UI to solve. .
>
>
> Exactly. And this is the second issue of the two I mentioned: in order to
> make merge aware of moves, as opposed to copies, you have to be able to
> detect that two distinct path@revision in fact refer to the same branch
> of a node -- which is exactly the (node-id, copy-id) pair, and that /is/
> sufficient for the purpose. So again, there's no need to invent another
> branch-tracking identifier.
>
Sigh. The (node,copy) pair *alone* cannot be sufficient to map
move sources and targets. You always need some sort of context
information - such as provided by a recursive DAG walk.
Example:
* given /A/f with ID 1.2.3
* cp /A /B
* now /A/f and /B/f share the same DAG node with ID 1.2.3
* mv /B/f /c
* /c may now have DAG node ID 1.2.3 or 1.3.3 (if we expand the
lazy copy upon move)
Question: What node got moved?
Answer: DAG node 1.2.3 (correct).
Question: What path got moved? (I may want to merge changes)
Answer: Maybe /A/f, maybe /B/f.
Immediate reason: tree@rev has more nodes than the whole DAG
and *any* node in tree@rev is a potential move source. Unless we
either do aways with lazy copies (hello CVS) or implicitly add new
DAG IDs in old revisions, there cannot be enough FS-level IDs for
a surjective mapping.
In-depth reason: Once you accept that the move semantics as
suggested by Julian's definition is what you want to support, *any*
ID scheme must either be isomorphic to the node-line ID approach
or a true superset of it. In the latter case you must provide auxiliary
rules (can be implicit) that effectively limit the superset to the original.
Otherwise, your implementation does not match the definition.
> (This is almost the opposite of detecting moves -- it's closer to
> detecting sameness, for some definition of "same".)
>
>
> * If moves are lazy, and you need to track moves differently from
> copies then consider: What if you expanded a noderev with a new move_id
> part? :)
>
>
> Here's the thing -- moves are never lazy. For all intents and purposes,
> they behave exactly as content or prop modifications. In fact, you can
> think of a node's name as one of its properties, instead of a property of
> its parent; although of course this is not what the current model does.
>
>
> Some systems solve this problem by recording in the merge history the
> (noderev, copyid) equivalents the merge history was recorded from. (Not
> just when merge was invoked, but also initial merge history for the initial
> copy.) That could also be a way of determining where /trunk/A/B/C/q.c is in
> /branch after a number of arbitrary number of directory hierarchy changes
> and file name alterations somewhere in /branch. These systems don't easily
> support merge history elision concepts though. (As well as requiring
> specialized merge history storage at the FS level for performance reasons.)
> Of course, I would think merge history could benefit from specialized
> storage anyway. :)
>
>
> Indeed, this is another thing we've been talking about, and another goal
> for the next generation versioned FS. We're well aware that the way we
> currently store mergeinfo is ... less than ideal.
>
>
> If you followed this approach the exact way the Noderev node_id/copy_id
> changes might be less relevant.
>
> Sorry for making your head hurt some more with these ancient nutty
> musings,
>
>
> Actually, I'd prefer to see more of your musings on this list ...
>
More input is certainly welcome.
-- Stefan^2.
Re: Moves in FSFS
Posted by Branko Čibej <br...@wandisco.com>.
On 29.09.2013 20:59, Stefan Fuhrmann wrote:
>
> On Sun, Sep 29, 2013 at 8:46 PM, Bert Huijben <bert@qqmail.nl
> <ma...@qqmail.nl>> wrote:
>
> Hi Stefan,
>
>
>
> Are you sure there are no behavior changes by changing this?
>
>
> Reasonably sure. Previously, it read
>
> noderev->copyfrom_path = copy_something();
> noderev->copyfrom_path = NULL; /* result of copy_something() is
> gone now */
>
> Now, it just reads
>
> noderev->copyfrom_path = NULL;
>
> Did I miss something?
Does copy_something() have side effects?
-- Brane
--
Branko Čibej | Director of Subversion
WANdisco // Non-Stop Data
e. brane@wandisco.com
Re: Moves in FSFS
Posted by Julian Foad <ju...@btopenworld.com>.
Stefan Fuhrmann wrote:
> Bert Huijben <be...@qqmail.nl> wrote:
>> Are you sure there are no behavior changes by changing this?
>
> Reasonably sure. Previously, it read
>
> noderev->copyfrom_path = copy_something();
>
> noderev->copyfrom_path = NULL; /* result of copy_something() is gone now */
No it didn't. The code quoted in the email read:
noderev->copyROOT_path = copy_something();
---------------^^^^
noderev->copyfrom_path = NULL; /* result of copy_something() is gone now */
> Now, it just reads
> noderev->copyfrom_path = NULL;
>
> Did I miss something?
Looks like it.
- Julian
Re: Moves in FSFS
Posted by Stefan Fuhrmann <st...@wandisco.com>.
On Sun, Sep 29, 2013 at 8:46 PM, Bert Huijben <be...@qqmail.nl> wrote:
> Hi Stefan,****
>
> ** **
>
> Are you sure there are no behavior changes by changing this?
>
Reasonably sure. Previously, it read
noderev->copyfrom_path = copy_something();
noderev->copyfrom_path = NULL; /* result of copy_something() is gone now
*/
Now, it just reads
noderev->copyfrom_path = NULL;
Did I miss something?
-- Stefan^2.
RE: Moves in FSFS
Posted by Bert Huijben <be...@qqmail.nl>.
Hi Stefan,
Are you sure there are no behavior changes by changing this?
If you copy nodes at every level the resulting nodes are the same as when
you only copy a root. (We had a lot of this in the wc-1.0 code). Tweaking
between copyfrom_* and copyroot_* is quite easy to get not exactly right,
without visible side effects. The repos_layer will hide a lot of those
differences to the client layer, while there can be quite a different
behavior in the storage layer.
With just the snippets in this thread I can't find a true answer and I need
more time to look at the actual change itself, to determine if there are
possible side effects.
Bert
From: Stefan Fuhrmann [mailto:stefan.fuhrmann@wandisco.com]
Sent: zondag 29 september 2013 18:39
To: Bill Tutt
Cc: Branko Čibej; Subversion Development
Subject: Re: Moves in FSFS
On Sun, Sep 29, 2013 at 2:08 AM, Bill Tutt <bill@tutts.org
<ma...@tutts.org> > wrote:
On a slightly different note I noticed this oddity in lib_fs_fs/dag.c from
http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?
annotate=1517479
703
jpieper
<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c
?r1=849538&r2=849539&> 849539
if (is_parent_copyroot)
704
jpieper
<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c
?r1=849531&r2=849532&> 849532
{
705
danielsh
<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c
?r1=1305395&r2=1305396&> 1305396
SVN_ERR(get_node_revision(&parent_noderev, parent));
706
jpieper
<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c
?r1=849538&r2=849539&> 849539
noderev->copyroot_rev = parent_noderev->copyroot_rev;
707
kfogel
<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c
?r1=858544&r2=858545&> 858545
noderev->copyroot_path = apr_pstrdup(pool,
708
parent_noderev->copyroot_path);
709
jpieper
<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c
?r1=849531&r2=849532&> 849532
}
710
hwright
<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c
?r1=866390&r2=866391&> 866391
711
jpieper
<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c
?r1=849538&r2=849539&> 849539
noderev->copyfrom_path = NULL;
712
noderev->copyfrom_rev = SVN_INVALID_REVNUM;
713
hwright
<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c
?r1=866390&r2=866391&> 866391
Sure looks like a useless memory allocation from the APR pool for
copyroot_path as well as dead code rotting away quietly.
As well as this earlier in the same file:
394
kfogel
<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c
?r1=858544&r2=858545&> 858545
new_noderev.copyroot_path = apr_pstrdup(pool,
395
parent_noderev->copyroot_path);
396
jpieper
<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c
?r1=849538&r2=849539&> 849539
new_noderev.copyroot_rev = parent_noderev->copyroot_rev;
397
new_noderev.copyfrom_rev = SVN_INVALID_REVNUM;
398
new_noderev.copyfrom_path = NULL;
Wow, this has been here for ages... :)
Thanks Bill for spotting this. Fixed in r1527344.
-- Stefan^2.
Re: Moves in FSFS
Posted by Stefan Fuhrmann <st...@wandisco.com>.
On Sun, Sep 29, 2013 at 2:08 AM, Bill Tutt <bi...@tutts.org> wrote:
> On a slightly different note I noticed this oddity in lib_fs_fs/dag.c from
> http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?annotate=1517479
>
> 703 jpieper849539<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=849538&r2=849539&> if
> (is_parent_copyroot) 704jpieper 849532<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=849531&r2=849532&>{705
> danielsh 1305396<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=1305395&r2=1305396&>SVN_ERR(get_node_revision(&parent_noderev, parent));706
> jpieper 849539<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=849538&r2=849539&>noderev->copyroot_rev = parent_noderev->copyroot_rev;707
> kfogel 858545<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=858544&r2=858545&>noderev->copyroot_path = apr_pstrdup(pool,708
> parent_noderev->copyroot_path); 709jpieper 849532<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=849531&r2=849532&>}710
> hwright 866391<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=866390&r2=866391&>
> 711jpieper 849539<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=849538&r2=849539&>noderev->copyfrom_path = NULL;712
> noderev->copyfrom_rev = SVN_INVALID_REVNUM; 713hwright
>
> 866391<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=866390&r2=866391&>
>
>
> Sure looks like a useless memory allocation from the APR pool for
> copyroot_path as well as dead code rotting away quietly.
>
> As well as this earlier in the same file:
> 394 kfogel858545<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=858544&r2=858545&> new_noderev.copyroot_path
> = apr_pstrdup(pool, 395 parent_noderev->copyroot_path); 396jpieper
> 849539<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=849538&r2=849539&>new_noderev.copyroot_rev = parent_noderev->copyroot_rev;397
> new_noderev.copyfrom_rev = SVN_INVALID_REVNUM; 398 new_noderev.copyfrom_path = NULL;
>
> Wow, this has been here for ages... :)
>
Thanks Bill for spotting this. Fixed in r1527344.
-- Stefan^2.
Re: Moves in FSFS
Posted by Bill Tutt <bi...@tutts.org>.
On a slightly different note I noticed this oddity in lib_fs_fs/dag.c from
http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?annotate=1517479
703jpieper849539<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=849538&r2=849539&>if
(is_parent_copyroot)
704jpieper849532<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=849531&r2=849532&>{
705danielsh1305396<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=1305395&r2=1305396&>SVN_ERR(get_node_revision(&parent_noderev,
parent));
706jpieper849539<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=849538&r2=849539&>noderev->copyroot_rev
= parent_noderev->copyroot_rev;
707kfogel858545<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=858544&r2=858545&>noderev->copyroot_path
= apr_pstrdup(pool,
708 parent_noderev->copyroot_path);709jpieper849532<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=849531&r2=849532&>}
710hwright866391<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=866390&r2=866391&>
711jpieper849539<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=849538&r2=849539&>noderev->copyfrom_path
= NULL;
712 noderev->copyfrom_rev = SVN_INVALID_REVNUM;713hwright
866391<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=866390&r2=866391&>
Sure looks like a useless memory allocation from the APR pool for
copyroot_path as well as dead code rotting away quietly.
As well as this earlier in the same file:
394kfogel858545<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=858544&r2=858545&>new_noderev.copyroot_path
= apr_pstrdup(pool,
395 parent_noderev->copyroot_path);396jpieper849539<http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/dag.c?r1=849538&r2=849539&>new_noderev.copyroot_rev
= parent_noderev->copyroot_rev;
397 new_noderev.copyfrom_rev = SVN_INVALID_REVNUM;398
new_noderev.copyfrom_path = NULL;
Wow, this has been here for ages... :)
Fyi,
Bill
Re: Moves in FSFS
Posted by Branko Čibej <br...@wandisco.com>.
On 28.09.2013 12:06, Bill Tutt wrote:
> Move tracking can clearly make ones head spin. :)
>
> Brane: Could Julian and Stephan be asking about how to map between
> arbitrary revisions thinking of tree merge scenarios?
There are two, somewhat related issues. The first involves understanding
what actually happened to the tree, e.g., detecting that a certain
change in the tree was a move, not something else. We realized more than
10 years ago that in our current top-down DAG model, getting this info
just by analyzing the tree would be very expensive, and in some cases
infeasible; so it doesn't really come as a surprise that looking just at
the (node-id, copy-id) of a node revision is not enough.
That's why the changes list was introduced (as the "changes" table in
BDB, and an equivalent structure in FSFS); and I think we've come to the
conclusion that it will have to be used to detect moves as well.
> That's what always gave me heart burn with the current Noderev
> behavior and envisioning real moves in Subversion.
Yup.
> In thinking deep thoughts about this in the deep dark dark distant
> past I came up with several interesting thoughts: (sadly none of these
> are completely thought out answers, but they did seem like thoughts
> worth pondering wrt Subversion if you haven't before)
> * Have you considered having the noderev own the node's name instead
> of how the parent directory currently owns it? This way it would be
> natural to make the destination of the move a mutated noderev.
Yes. In fact I've made a stab at defining a different, IMO better model
for storing versioned tree metadata; see:
https://wiki.apache.org/subversion/Berlin2013?action=AttachFile&do=view&target=metadata-tng.pdf
In this model, file names are represented as properties of the node, not
its parent. It also does away with the necessity of having a separate
changes list. But implementing it will be part of a larger effort which
includes inventing a new API for the FS layer (in hindisght, we should
never have exposed the top-down DAG as a public API).
> i.e. mv /trunk/A -> /trunk/B COULD do this in the DAG:
> * make /trunk/A mutable by ONLY updating the TxnID of the Noderev.
> * Edit the name field of the noderev from A ->B
> More complicated example:
> mv /trunk/A/B/C -> /trunk/A/D COULD do this to the DAG:
> * make /trunk/A/B/C mutable by ONLY updating the TxnID of the
> Noderev.
> * remove it as an entry from /trunk/A/B and add it as an entry
> to /trunk/A
> However... what do you do for this case: (C could have a zero copy_id
> here I think)
> mv /trunk/A/B/C -> /blah could do this to the DAG:
> ????
> or this one: (presuming C has a non-zero copy_id before move)
> mv /branch/A/B/C -> /blah2
> ????
> or (same as the last one, but C was the destination of the "soft-copy")
> ???
> The enumeration of the rest of the cases is left as an exercise for
> the reader. :)
That PDF mentions many of these. :)
> * The implementation of rename tracking should ensure you enable all
> scenarios you desire for dealing with merging renamed items from
> branch A to branch B. (the tree shape part of the merge of course)
> That is, if you care, some systems don't/won't/did and then decided
> not to/whatever. Merging renames leads to lousy complex edge case tree
> conflicts that need usable (in the easy to use usability sense)
> resolution UI to solve. .
Exactly. And this is the second issue of the two I mentioned: in order
to make merge aware of moves, as opposed to copies, you have to be able
to detect that two distinct path@revision in fact refer to the same
branch of a node -- which is exactly the (node-id, copy-id) pair, and
that /is/ sufficient for the purpose. So again, there's no need to
invent another branch-tracking identifier.
(This is almost the opposite of detecting moves -- it's closer to
detecting sameness, for some definition of "same".)
> * If moves are lazy, and you need to track moves differently from
> copies then consider: What if you expanded a noderev with a new
> move_id part? :)
Here's the thing -- moves are never lazy. For all intents and purposes,
they behave exactly as content or prop modifications. In fact, you can
think of a node's name as one of its properties, instead of a property
of its parent; although of course this is not what the current model does.
> Some systems solve this problem by recording in the merge history the
> (noderev, copyid) equivalents the merge history was recorded from.
> (Not just when merge was invoked, but also initial merge history for
> the initial copy.) That could also be a way of determining where
> /trunk/A/B/C/q.c is in /branch after a number of arbitrary number of
> directory hierarchy changes and file name alterations somewhere in
> /branch. These systems don't easily support merge history elision
> concepts though. (As well as requiring specialized merge history
> storage at the FS level for performance reasons.) Of course, I would
> think merge history could benefit from specialized storage anyway. :)
Indeed, this is another thing we've been talking about, and another goal
for the next generation versioned FS. We're well aware that the way we
currently store mergeinfo is ... less than ideal.
> If you followed this approach the exact way the Noderev
> node_id/copy_id changes might be less relevant.
>
> Sorry for making your head hurt some more with these ancient nutty
> musings,
Actually, I'd prefer to see more of your musings on this list ...
-- Brane
--
Branko Čibej | Director of Subversion
WANdisco // Non-Stop Data
e. brane@wandisco.com
Re: Moves in FSFS
Posted by Bill Tutt <bi...@tutts.org>.
Move tracking can clearly make ones head spin. :)
Brane: Could Julian and Stephan be asking about how to map between
arbitrary revisions thinking of tree merge scenarios?
That's what always gave me heart burn with the current Noderev behavior and
envisioning real moves in Subversion.
In thinking deep thoughts about this in the deep dark dark distant past I
came up with several interesting thoughts: (sadly none of these are
completely thought out answers, but they did seem like thoughts worth
pondering wrt Subversion if you haven't before)
* Have you considered having the noderev own the node's name instead of how
the parent directory currently owns it? This way it would be natural to
make the destination of the move a mutated noderev.
i.e. mv /trunk/A -> /trunk/B COULD do this in the DAG:
* make /trunk/A mutable by ONLY updating the TxnID of the Noderev.
* Edit the name field of the noderev from A ->B
More complicated example:
mv /trunk/A/B/C -> /trunk/A/D COULD do this to the DAG:
* make /trunk/A/B/C mutable by ONLY updating the TxnID of the Noderev.
* remove it as an entry from /trunk/A/B and add it as an entry to
/trunk/A
However... what do you do for this case: (C could have a zero copy_id here
I think)
mv /trunk/A/B/C -> /blah could do this to the DAG:
????
or this one: (presuming C has a non-zero copy_id before move)
mv /branch/A/B/C -> /blah2
????
or (same as the last one, but C was the destination of the "soft-copy")
???
The enumeration of the rest of the cases is left as an exercise for the
reader. :)
* The implementation of rename tracking should ensure you enable all
scenarios you desire for dealing with merging renamed items from branch A
to branch B. (the tree shape part of the merge of course)
That is, if you care, some systems don't/won't/did and then decided not
to/whatever. Merging renames leads to lousy complex edge case tree
conflicts that need usable (in the easy to use usability sense) resolution
UI to solve. .
* If moves are lazy, and you need to track moves differently from copies
then consider: What if you expanded a noderev with a new move_id part? :)
Some systems solve this problem by recording in the merge history the
(noderev, copyid) equivalents the merge history was recorded from. (Not
just when merge was invoked, but also initial merge history for the initial
copy.) That could also be a way of determining where /trunk/A/B/C/q.c is in
/branch after a number of arbitrary number of directory hierarchy changes
and file name alterations somewhere in /branch. These systems don't easily
support merge history elision concepts though. (As well as requiring
specialized merge history storage at the FS level for performance reasons.)
Of course, I would think merge history could benefit from specialized
storage anyway. :)
If you followed this approach the exact way the Noderev node_id/copy_id
changes might be less relevant.
Sorry for making your head hurt some more with these ancient nutty musings,
Bill
Re: Moves in FSFS
Posted by Branko Čibej <br...@wandisco.com>.
On 19.09.2013 16:46, Stefan Fuhrmann wrote:
> Storing Moves
> -------------
>
> From the FS POV, moves behave like simple ADD/DEL pairs
> and should, therefore, be stored as such.
Agreed, as far as the changes list is concerned. You have to leave a
"tombstone" on the source of a move, so that code that scans the change
list can be aware that the path went away. Whether we then represent the
target as an ADD record, or invent a new MOVE record, is more or less an
implementation detail.
-- Brane
--
Branko Čibej | Director of Subversion
WANdisco // Non-Stop Data
e. brane@wandisco.com
Re: Moves in FSFS
Posted by Stefan Fuhrmann <st...@wandisco.com>.
Hi all,
I spend most of this week thinking about moves and I
changed my mind as further evidence came up.
What I fully agree with is:
http://wiki.apache.org/subversion/MoveDev/MoveDev#Move_Semantics
Then, I found an equivalent expression for the nodeLineID
concept central to the move semantics:
http://svn.haxx.se/dev/archive-2013-09/0112.shtml
and showed there as well as here:
http://svn.haxx.se/dev/archive-2013-09/0128.shtml
that the current and proposed usage of nodeID, copyID is
not equivalent, i.e. cannot be used immediately as a bases
for path matching.
Finding Moves
--------------
This brought me to realization that having move semantics
(and thus identity) defined is necessary and useful but the
implementation will most likely be a history scan. Following
internal node chains to identify common copy roots is very
time consuming and I/O inefficient.
History scans are quick in f7 (10k+ revs/s) and might be
even faster with 1.10 (100k+ revs/s) but you want to do
only one or at most a handful of them for an update editor
run. One way to do it has been proposed here:
http://svn.haxx.se/dev/archive-2013-09/0136.shtml
Another way would be to tell the server the full range (oldest
revision) as part of the reporter initialization. The results of
the scan might then even be applicable to mixed rev working
copies.
Storing Moves
-------------
>From the FS POV, moves behave like simple ADD/DEL pairs
and should, therefore, be stored as such. The differences
are:
* deletes due to moves must not be executed if the
respective path already got replaced
* there must be only one move per revision for any
source as well as target path (to be checked upon
transaction commit)
* instead of "add"/"replace", say "move"/"movereplace"
in the changes list to signify the user's intend
But other than that, existing code should DTRT even in
the presence of moves and backward compat APIs can simply
report moves as ADD/DEL pairs without becoming inconsistent
with the actual data.
Later, revised FS implementations may then impose additional
ID <-> operation dependencies internally.
History Traversal and Moves
---------------------------
This might be opt-out but most users would want to follow
renames / moves even if they don't follow copies. Since
both have the same internal representation, we need to look
into the changed paths list to determine whether the change
has been an actual ADD or a MOVE.
That is virtually for free as we usually to report the
changed paths for all relevant revisions anyway.
Auto-move Option
----------------
It is safe to automatically treat all unique DEL(pathA)
+ ADD(pathA@R-1 -> pathB) pairs in revision R as moves,
iff the user did not intend to treat them as separate
node lines. This will not modify recorded history but
only reduce the number of tree conflicts a user may see.
Therefore, log and reporter API should be rev'ed to take
an extra "auto_move" boolean parameter. If set, the
server will attempt to report moves instead of DEL/ADD
pairs with no guarantee that all or even any of the pairs
will actually be detected (future backends may or may not
support this option).
-- Stefan^2.
On Wed, Sep 11, 2013 at 5:21 PM, Julian Foad <ju...@btopenworld.com>wrote:
> While discussions continue about the "editor" and the WC side of move
> tracking, I'd like to make some progress on the Repository side.
>
> The Wiki page
>
> http://wiki.apache.org/subversion/MoveDev/MoveDev#Move_Semantics
>
> declares the semantic model and
>
> http://wiki.apache.org/subversion/MoveDev/MovesInFSFS
>
> attempts to specify the changes needed. I think the model for move
> semantics in the repository as presented there is pretty solid --
> precise and complete and having a nice set of properties.
>
> Can anyone review this? If anyone can take it forward in any way that
> would be a great help, otherwise I'll tackle the implementation
> myself.
>
> One issue that may be harder than it sounds at first is the concept of
> 'node-line-id' rather than (node-id, copy-id) as the basis of the
> definition. The point is that when we copy (ordinary copy, not move)
> a directory, we lazy-copy the children, which means each child keeps
> its old (node-id, copy-id) unless and until it is modified. That's
> great for achieving the O(1) copy, but for move-tracking purposes each
> child needs a unique "node-line-id" so its life-line can be uniquely
> traced forward and back between this revision and a later revision by
> which time it may have been modified and thus assigned a new copy-id.
>
> Clearly it would defeat the O(1) cost if we were to construct a
> node-line-id explicitly for every node in the tree at copy time. Can
> we instead define node-line-id such that we can compute it as needed,
> from either an unmodified lazy-copied child or after such a child has
> been modified, and get the same answer? Or perhaps re-state the
> problem to avoid this need?
>
> - Julian
>