Bound branch implementation

[Jan Hudec]

On Mon, Nov 14, 2005 at 16:35:13 +0100, Harald Meland wrote:
> [Jan Hudec]
> 
> > Thus I'd suggest to force a chain of shadows, ie. instead of X and Y
> > being shadows of Z, X would be shadow of Y, which would in turn be
> > shadow of Z. Then the transaction would succeed if it succeeded on X
> > and Y and Z would simply look at the state of X and resolve the
> > transaction accordingly.
> 
> How would you handle loops in shadow chains, e.g.
> 
> Developer A adds shadow from U -> Y, and Y -> Z
> Developer B adds shadow from V -> Z, and Z -> Y
> 
> resulting in this shadow graph:
> 
>            ___
>           /   v
>   U ---> Y    Z <--- V
>          ^___/
> 
> If loop resolution is implemented as "chain stops at previous node
> when visiting node N for the second time", you'd still risk races:
> 
> A gets shadow chain U -> Y -> Z, while B gets V -> Z -> Y.  Both A and
> B runs "bzr commit" simultaneously, and things happen in this order:
> 
>   A commits local changes in U to Z (as revno 43a)
>   B commits local changes in V to Y (as revno 43b)
>   A wants to update the next part of the shadow chain, Y, with 43a,
>   but 43b is already present.

First, to make one things clear -- I made the argument with chaining to
convert the shadows thing to bound branches. Now talking about bound branches
roughly as implemented. I don't think they support chaining now, but I'd
certailny like to see that feature later.

Now, no, it can't happen that way. Even without chaining, the local commit
can only be completed AFTER the remote one is. So it's rather:

A starts commit transaction in Z (as revno 43a)
B starts commit transaction in Y (as revno 43b)
A tries to start transaction in Y, but finds another transaction running
When that transaction finishes, A's transaction will be out of date, so the
attempt returns an error.
B tries to start transaction in Z, but also gets an error (because A's
transaction is not rolled back yet).
A rolls back the commit transaction in Z, and also in U.
B rolls back the commit transaction in Y, and also in V.

So there is no race condition. There is only a starvation. We are dealing
with human-initiated transactions, so one of them will retry faster and
succeed.

Even that starvation can be avoided - we could say, that if there is already
a transaction running, that has higher number in some arbitrary fixed
ordering (each transaction needs UUID), we wait for it to finish and if it
rolls back, continue. But we can safely ignore it.

> I guess a "when loop is detected, refuse to perform a commit" rule
> could work, but I don't think it would be an optimal solution as seen
> from the point of view of an "I just want to commit" user.

If no provision for loops was made, commit would indeed always fail for
loops. Because starting another transaction fails when there is already one
running.

So we need to assign an UUID to the transaction and instead return immediate
success when we came across the same transaction again. But that should be
all and work.

-- 
						 Jan 'Bulb' Hudec <bulb at ucw.cz>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : https://lists.ubuntu.com/archives/bazaar/attachments/20051114/1e7b09d0/attachment.pgp