repair of mutable files/directories should not increment the sequence number

[gdt]

Particularly with my root directory, I often find that 9 shares of seqN are available compared to 10 desired. I do a repair, and this results in 10 shares of seqN+1 and then 9 are deleted. Then the next day there are 9 of seqN+1 and 1 of seqN, and the file is again not healthy. This repeats daily.

It seems that the missing seqN shares should be generated and placed, and then when servers churn more it's likely that 10 can still be found, and no unrecoverable versions. Perhaps I don't get something, but the current behavior is not stable with intermittent servers.

I have observed this problem with directories, but it seems likely that it applies to all immutable files.

[zooko]

gdt: did you mean "mutable" instead of "immutable"? Immutable files don't have a sequence number!

[gdt]

Sorry, I really meant directories in particular. I have edited the summary and description.

[gdt]

Clarify that the ticket is really about directories, but that it likely applies to all immutable files.

[zooko]

Replying to gdt:

Clarify that the ticket is really about directories, but that it likely applies to all immutable files.

You mean it likely applies to all mutable files, right? :-) Directories are normally mutable, although it is also possible to have immutable directories. But immutable directories don't have sequence numbers. :-)

[davidsarah]

#1210 was a duplicate. Its description was:

If there are 1 shares of seqN and 10 shares of seqM, M>N, the file is not healthy. The fix should be to remove the seqN share and not molest the seqM shares, instead of incrementing the version. This contributes to instability.

[warner]

This is a great idea, especially since one of the failure modes for mutable files (when a share is migrated to a new server, causing the write-enabler to become wrong, causing the share to get "stuck" at some old version) is that it's never going to be able to get rid of that old share, so the file will always appear "unhealthy". In that case, constantly clobbering the perfectly-valid most-recent-version shares is obviously wrong.

[davidsarah]

Brian wrote on tahoe-dev:

I haven't looked at that code for a long time, but it occurs to me that what it wants is a checker-results flag that says whether the unhealthy status is due to the presence of multiple versions or not. In terms of the ServerMap object, I think that's just:

len(sm.recoverable_versions()) + len(sm.unrecoverable_versions()) > 1

We only need to do the full download+upload cycle (which increments the version number) if there are multiple versions present. If we're just missing a couple of shares (or some are corrupted and could be replaced), then the number of versions ==1 and we should do a non-incrementing form of repair.

I think we'll need new Repairer code to do that, though. Something to set the new version equal to the existing version, to avoid sending updates to existing correct shares, and something to make sure the generated test-vectors are ok with all that. Not trivial, but not a huge task either.

[davidsarah]

Greg Troxel wrote:

More than that - if we have 1 share of M and all shares of N, for N > M, then we really just want to purge (or ignore?) the M share, and not molest the N shares.

The test for this should be like:

  set up 5 servers S
  upload some files
  while 20 iterations
    for s in S
      take s off line
      run repair
      take s back

With the current code, you get repair every time and 100 increments, I think. With your proposal, I think it's still true.

The above test is how the pubgrid feels to me, or used to.

[davidsarah]

Brian replied:

On 3/29/12 12:01 PM, Greg Troxel wrote:

More than that - if we have 1 share of M and all shares of N, for N > M, then we really just want to purge (or ignore?) the M share, and not molest the N shares.

Ah, good point. We really only need a new version if there are multiple competing versions with the same sequence number, and if that sequence number is the highest seen. Repair is tricky in that case anyways, since at the Tahoe level we can't do an automatic merge, so we're certainly losing information (if it's just a directory modification, then the directory.py code can re-apply the modification, so that one case might be safe).

Hm, ServerMap.needs_merge() is pretty close already, but it only looks at recoverable versions (it tells you that an update will lose information that would have been recoverable if you'd read the individual versions first.. there are alternate cases where it doesn't matter because the other versions weren't recoverable anyways).

We should add a method to ServerMap that tells us whether a new version is needed or not.

The above test is how the pubgrid feels to me, or used to.

Yup, that test looks right.

[davidsarah]

Replying to Brian:

We really only need a new version if there are multiple competing versions with the same sequence number, and if that sequence number is the highest seen.

Counterexample: suppose there is a recoverable version with sequence number S, and an unrecoverable version with sequence number S+1. (There are no versions with sequence number >= S+2.) Then, the new sequence number needs to be S+2, in order for clients not to use the shares from S+1. Deleting the shares with sequence number S+1 is also possible but inferior, since sequence numbers should be monotonically increasing to minimize race conditions.

We should add a method to ServerMap that tells us whether a new version is needed or not.

+1.

[davidsarah]

Proposed algorithm:

1. Find the highest recoverable sequence number, R.
2. Find the highest sequence number for which there exist any shares, S.
3. If R == S, repair version R using the algorithm in ticket:1130#comment:12 . Otherwise, download version R and upload it to version S+1.

This would also fix #1004, #614, and #1130. IIUC, an implementation of the ticket:1130#comment:12 algorithm is being worked on in #1382.

[gdt]

I think davidsarah's proposed algorithm is a good choice. A few comments:

• if there are shares of a version Q < R, then S = R, not Q. This follows from the algorithm, but in a design doc perhaps should be made more obvious: stray shares of a version less than the highest recoverable version are not a problem.
• In the case where R is repaired, stray shares of a lower version should be removed.
• in the case where S+1 is uploaded, shares of R, and actually shares of <=S should be removed.
• if R is recoverable and there are shares of S > R, then it's really not clear what should happen. One possibility is to wait for a while (days?), keeping checking, and hoping there are enough S. But this is probably a very unlikely, and it's unclear what ought to happen, so I would defer that nuance to later.