fix regressions in convergent uncoordinated write detection

kevan commented

2011-12-17 22:38:22 +00:00

Owner

Comment 4 in ticket 546 describes a fix made to the mutable publisher to allow it to tolerate unknown shares in certain circumstances without raising an UncoordinatedWriteError. In the pre-1.9 publisher, this is implemented by comparing the checkstring (seqnum, roothash, salt) of the unexpected share with the checkstring of the file being published. If they're the same, then the unexpected share is assumed to be either a share that the publish operation placed earlier or an uncoordinated convergent write, and tolerated without an uncoordinated write error. The 1.9 publisher changes this behavior in two ways.

The first change is a bug. The checkstring that the check examines is set on lines 296, 496, and 828 of publish.py:

        self._checkstring = self.writers.values()[0].get_checkstring()

self.writes.values()[0] can be an instance of either MDMFSlotWriteProxy or SDMFSlotWriteProxy. MDMFSlotWriteProxy returns a different checkstring than SDMFSlotWriteProxy; specifically, MDMFSlotWriteProxy returns the checkstring associated with the file version we're writing, while SDMFSlotWriteProxy returns the checkstring associated with the existing share (if any). Only MDMFSlotWriteProxy returns the checkstring associated with the current version of the mutable file, which is necessary in order for the #546 check to behave the same as in the pre-1.9 publisher. The fix for this issue is to change SDMFSlotWriteProxy to return the same checkstring as MDMFSlotWriteProxy.

The second change is a design flaw. On line 987, I added the following:

        # We need to remove from surprise_shares any shares that we are
        # knowingly also writing to that server from other writers.

        # TODO: Precompute this.
        known_shnums = [x.shnum for x in self.writers.values()
                        if x.server == server]
        surprise_shares -= set(known_shnums)
        self.log("found the following surprise shares: %s" %
                 str(surprise_shares))

which essentially exempts any surprise share that we know we're supposed to be writing during the publish operation from the #546 check. The 1.9 publisher offers no guarantees that all writes to a particular server will return before _got_write_answer is called to handle the results for a particular write. So a surprise share that is associated with a convergent and concurrent write might have either the checkstring of the current publish operation or the checkstring of the version associated with the existing share. The #546 check only accepts the share in the first case, which is probably why I added the exemption. It would be better to modify the #546 check to be specific about the second case instead of exempting all shares whose numbers match those we're writing. Alternatively, the #546 check could be retained as-is if we alter the publisher's control flow so that _got_write_answer is only executed for a response from a particular server after all writes to that server have completed. Since the publisher is designed to follow the existing share placement when placing a new version of a mutable file, it is likely that uncoordinated writers would try to place the same shares in the same places as one another. The exemption that is there now hurts the publisher's ability to detect this situation.

The practical impact of the first regression is that SDMF publish operations are less able to figure out when they need to abort a publish and try again after another map update. The practical impact of the second regression is that the publisher might not detect uncoordinated writes that it would have been able to detect before 1.9, and that it might take longer to detect uncoordinated writes than before 1.9.

[Comment 4 in ticket 546](/tahoe-lafs/trac-2024-07-25/issues/546#issuecomment-110248) describes a fix made to the mutable publisher to allow it to tolerate unknown shares in certain circumstances without raising an UncoordinatedWriteError. In the pre-1.9 publisher, this is implemented by comparing the checkstring (seqnum, roothash, salt) of the unexpected share with the checkstring of the file being published. If they're the same, then the unexpected share is assumed to be either a share that the publish operation placed earlier or an uncoordinated convergent write, and tolerated without an uncoordinated write error. The 1.9 publisher changes this behavior in two ways. The first change is a bug. The checkstring that the check examines is set on lines 296, 496, and 828 of publish.py: ``` self._checkstring = self.writers.values()[0].get_checkstring() ``` `self.writes.values()[0]` can be an instance of either `MDMFSlotWriteProxy` or `SDMFSlotWriteProxy`. `MDMFSlotWriteProxy` returns a different checkstring than `SDMFSlotWriteProxy`; specifically, `MDMFSlotWriteProxy` returns the checkstring associated with the file version we're writing, while `SDMFSlotWriteProxy` returns the checkstring associated with the existing share (if any). Only `MDMFSlotWriteProxy` returns the checkstring associated with the current version of the mutable file, which is necessary in order for the #546 check to behave the same as in the pre-1.9 publisher. The fix for this issue is to change `SDMFSlotWriteProxy` to return the same checkstring as `MDMFSlotWriteProxy`. The second change is a design flaw. On line 987, I added the following: ``` # We need to remove from surprise_shares any shares that we are # knowingly also writing to that server from other writers. # TODO: Precompute this. known_shnums = [x.shnum for x in self.writers.values() if x.server == server] surprise_shares -= set(known_shnums) self.log("found the following surprise shares: %s" % str(surprise_shares)) ``` which essentially exempts any surprise share that we know we're supposed to be writing during the publish operation from the #546 check. The 1.9 publisher offers no guarantees that all writes to a particular server will return before `_got_write_answer` is called to handle the results for a particular write. So a surprise share that is associated with a convergent and concurrent write might have either the checkstring of the current publish operation or the checkstring of the version associated with the existing share. The #546 check only accepts the share in the first case, which is probably why I added the exemption. It would be better to modify the #546 check to be specific about the second case instead of exempting all shares whose numbers match those we're writing. Alternatively, the #546 check could be retained as-is if we alter the publisher's control flow so that `_got_write_answer` is only executed for a response from a particular server after all writes to that server have completed. Since the publisher is designed to follow the existing share placement when placing a new version of a mutable file, it is likely that uncoordinated writers would try to place the same shares in the same places as one another. The exemption that is there now hurts the publisher's ability to detect this situation. The practical impact of the first regression is that SDMF publish operations are less able to figure out when they need to abort a publish and try again after another map update. The practical impact of the second regression is that the publisher might not detect uncoordinated writes that it would have been able to detect before 1.9, and that it might take longer to detect uncoordinated writes than before 1.9.

tahoe-lafs added the

labels 2011-12-17 22:38:22 +00:00

tahoe-lafs added this to the undecided milestone 2011-12-17 22:38:22 +00:00

zooko commented

2011-12-18 02:20:33 +00:00

Author

Owner

The practical impact of the first regression is that SDMF publish operations are less able to figure out when they need to abort a publish and try again after another map update.

When does this situation arise? And what happens in this situation, with the current 1.9.0 version, that isn't good?

> The practical impact of the first regression is that SDMF publish operations are less able to figure out when they need to abort a publish and try again after another map update. When does this situation arise? And what happens in this situation, with the current 1.9.0 version, that isn't good?

kevan commented

2011-12-18 03:03:50 +00:00

Author

Owner

The only example I've thought of so far involves storage servers with shares associated with a file that's being updated joining the grid in between the map update step and the publish step (so the servermap doesn't know about their shares). The old publisher would interpret the unknown shares as evidence of an uncoordinated write and cause the upload to fail. The new publisher might not; if each of the new servers happens to have a subset of the shares allocated to it by the publisher, or if the file is SDMF and the unknown shares are from a certain previous version of the mutable file, the new publisher will ignore them. That's bad because we want the publisher to have as much information as possible before publishing, and we should interpret shares that we didn't know about before publishing as evidence that we need to gather more information before pushing new shares.

(is that unclear? I could try to make a concrete example if that'd help.)

The only example I've thought of so far involves storage servers with shares associated with a file that's being updated joining the grid in between the map update step and the publish step (so the servermap doesn't know about their shares). The old publisher would interpret the unknown shares as evidence of an uncoordinated write and cause the upload to fail. The new publisher might not; if each of the new servers happens to have a subset of the shares allocated to it by the publisher, or if the file is SDMF and the unknown shares are from a certain previous version of the mutable file, the new publisher will ignore them. That's bad because we want the publisher to have as much information as possible before publishing, and we should interpret shares that we didn't know about before publishing as evidence that we need to gather more information before pushing new shares. (is that unclear? I could try to make a concrete example if that'd help.)

zooko commented

2011-12-18 04:00:33 +00:00

Author

Owner

Replying to kevan:

(is that unclear? I could try to make a concrete example if that'd help.)

I think I understand. A concrete example might help me and others understand better.

It sounds to me as though this is unlikely to cause a practical problem for users of Tahoe-LAFS v1.9.0.

As an aside, I think the bigger picture here is that the "robustness of upload" semantics are too complicated for users (or even for me!!) to understand what the intended result is, much less to understand what the intended behavior is, much less to understand what effects the deviations from that behavior (bugs) have. Kevan's project to unify mutable and immutable upload semantics and to fix the bugs in his Servers Of Happiness semantics are a step in the right direction, in my humble opinion.

Replying to [kevan](/tahoe-lafs/trac-2024-07-25/issues/1641#issuecomment-128404): > > (is that unclear? I could try to make a concrete example if that'd help.) I think I understand. A concrete example might help me and others understand better. It sounds to me as though this is unlikely to cause a practical problem for users of Tahoe-LAFS v1.9.0. As an aside, I think the bigger picture here is that the "robustness of upload" semantics are too complicated for users (or even for *me*!!) to understand what the intended result is, much less to understand what the intended behavior is, much less to understand what effects the deviations from that behavior (bugs) have. Kevan's project to unify mutable and immutable upload semantics and to fix the bugs in his Servers Of Happiness semantics are a step in the right direction, in my humble opinion.

zooko commented

2011-12-29 00:24:06 +00:00

Author

Owner

Kevan: do you agree with my assessment that this is not urgent for Tahoe-LAFS v1.9.1? I'm not sure that I understand it well enough to judge. I also don't know how much work, or how risky, it would be to attempt to fix it for 1.9.1.

kevan commented

2011-12-29 00:40:24 +00:00

Author

Owner

I don't think it's particularly urgent, and agree with your assessment regarding 1.9.1. I have a series of patches in my local tree that fix it; that doesn't speak to the riskiness of the fix, but it means that most of the work is already done if we want it in 1.9.1.

zooko commented

2011-12-29 06:08:04 +00:00

Author

Owner

Brian: could you please look at this and decide if you want it in 1.9.1? (Personally, I'm already a tad uncomfortable with the non-critical-bug-fix changes that are slated for 1.9.1, and I would probably have opted for branching 1.9.1 from the 1.9.0 release instead of from trunk.)

Kevan: could you go ahead and attach a patch to this ticket?

Brian: could you please look at this and decide if you want it in 1.9.1? (Personally, I'm already a tad uncomfortable with the non-critical-bug-fix changes that are slated for 1.9.1, and I would probably have opted for branching 1.9.1 from the 1.9.0 release instead of from trunk.) Kevan: could you go ahead and attach a patch to this ticket?

kevan commented

2012-01-01 01:09:28 +00:00

Author

Owner

Attachment fix-1641.darcs.patch (97516 bytes) added

first cut at fixing #1641

**Attachment** fix-1641.darcs.patch (97516 bytes) added first cut at fixing #1641

fix-1641.darcs.patch

95 KiB

kevan commented

2012-01-01 01:14:14 +00:00

Author

Owner

fix-1641.darcs.patch is my first attempt at fixing this issue. It's unfortunately rather long; longer than I'd prefer for a 1.9.1 release, anyway. I'll try to distill the patchset in fix-1641.darcs.patch into something leaner if Brian thinks this is a candidate for 1.9.1.

[fix-1641.darcs.patch](/tahoe-lafs/trac-2024-07-25/attachments/000078ac-de35-bd72-7bde-c3a098791b57) is my first attempt at fixing this issue. It's unfortunately rather long; longer than I'd prefer for a 1.9.1 release, anyway. I'll try to distill the patchset in [fix-1641.darcs.patch](/tahoe-lafs/trac-2024-07-25/attachments/000078ac-de35-bd72-7bde-c3a098791b57) into something leaner if Brian thinks this is a candidate for 1.9.1.

warner commented

2012-01-09 04:20:49 +00:00

Author

Owner

I'm ok with deferring this for post-1.9.1, especially given the more pressing fixes that we need to get into 1.9.1 . Let's see if we can land it shortly after that release, though.

tahoe-lafs modified the milestone from undecided to 1.10.0

2012-01-09 04:20:49 +00:00

tahoe-lafs modified the milestone from 1.11.0 to 1.10.0

2012-04-01 03:53:55 +00:00

warner commented

2012-09-04 16:50:24 +00:00

Author

Owner

pushing this out to 1.11. But Kevan: we do want to land this kind of thing. Could you update the patch (unbitrot, simplify) it? We could land it just after the 1.10 release.

tahoe-lafs modified the milestone from 1.10.0 to 1.11.0

2012-09-04 16:50:24 +00:00

kevan commented

2012-09-08 22:17:32 +00:00

Author

Owner

Sure, I'll take a look at it.

kevan commented

2012-09-09 00:51:13 +00:00

Author

Owner

See https://github.com/isnotajoke/tahoe-lafs/tree/1641-uncoordinated-write-detection for progress on this issue. I'm not convinced that I've quite paged all of the context for this ticket back into my head yet, but my gut feeling so far is that the posted patch will need a couple of additional tests. Fortunately the changes themselves haven't bitrotted much.

See <https://github.com/isnotajoke/tahoe-lafs/tree/1641-uncoordinated-write-detection> for progress on this issue. I'm not convinced that I've quite paged all of the context for this ticket back into my head yet, but my gut feeling so far is that the posted patch will need a couple of additional tests. Fortunately the changes themselves haven't bitrotted much.

tahoe-lafs added

code-mutable

and removed

unknown

labels 2013-11-14 18:01:32 +00:00

tahoe-lafs modified the milestone from soon to 1.12.0

2013-11-14 18:01:32 +00:00

daira commented

2013-11-21 22:43:55 +00:00

Author

Owner

Replying to kevan:

[...] Only MDMFSlotWriteProxy returns the checkstring associated with the current version of the mutable file, which is necessary in order for the #546 check to behave the same as in the pre-1.9 publisher. The fix for this issue is to change SDMFSlotWriteProxy to return the same checkstring as MDMFSlotWriteProxy.

[...]

The practical impact of the first regression is that SDMF publish operations are less able to figure out when they need to abort a publish and try again after another map update. [...]

We decided to remove the code that tries again (ticket:1670#comment:46), but SDMFSlotWriteProxy should probably be changed to use the same checkstring anyway, just for consistency and simplicity.

Replying to [kevan](/tahoe-lafs/trac-2024-07-25/issues/9116): > [...] Only `MDMFSlotWriteProxy` returns the checkstring associated with the current version of the mutable file, which is necessary in order for the #546 check to behave the same as in the pre-1.9 publisher. The fix for this issue is to change `SDMFSlotWriteProxy` to return the same checkstring as `MDMFSlotWriteProxy`. > > [...] > > The practical impact of the first regression is that SDMF publish operations are less able to figure out when they need to abort a publish and try again after another map update. [...] We decided to remove the code that tries again (ticket:1670#comment:46), but `SDMFSlotWriteProxy` should probably be changed to use the same checkstring anyway, just for consistency and simplicity.

warner commented

2016-03-22 05:02:25 +00:00

Author

Owner

Milestone renamed

tahoe-lafs modified the milestone from 1.12.0 to 1.13.0

2016-03-22 05:02:25 +00:00

warner commented

2016-06-28 18:17:14 +00:00

Author

Owner

renaming milestone

tahoe-lafs modified the milestone from 1.13.0 to 1.14.0

2016-06-28 18:17:14 +00:00

exarkun commented

2020-06-30 14:45:13 +00:00

Author

Owner

Moving open issues out of closed milestones.

tahoe-lafs modified the milestone from 1.14.0 to 1.15.0

2020-06-30 14:45:13 +00:00

meejah commented

2021-03-30 18:40:19 +00:00

Author

Owner

Ticket retargeted after milestone closed

tahoe-lafs modified the milestone from 1.15.0 to soon

2021-03-30 18:40:19 +00:00

fix regressions in convergent uncoordinated write detection #1641