[tahoe-lafs-trac-stream] [tahoe-lafs] #1130: Failure to achieve happiness in upload or repair

[tahoe-lafs]

#1130: Failure to achieve happiness in upload or repair
-------------------------+-------------------------------------------------
     Reporter:           |      Owner:  nobody
  kmarkley86             |     Status:  new
         Type:  defect   |  Milestone:  1.9.0
     Priority:  major    |    Version:  1.7.1
    Component:  code-    |   Keywords:  upload repair rebalancing
  peerselection          |  availability unfinished-business servers-of-
   Resolution:           |  happiness
Launchpad Bug:           |
-------------------------+-------------------------------------------------

Comment (by davidsarah):

 [copying the algorithm from ticket:1212#comment:14 here, with some minor
 refinements, for ease of reference]

 This is how I think the repairer should work:

  * let k and N be the shares-needed and total number of shares for this
 file, and let H be the happiness threshold read from {{{tahoe.cfg}}}.
  * construct a server map for this file by asking all connected servers
 which shares they have. (In the case of a mutable file, construct a server
 map for the latest retrievable version.)
  * construct a maximum matching M : server -> share, of size |M|, for this
 file (preferring to include servers that are earlier on the permuted list
 when there is a choice).
  * while |M| < N, and we have not tried to put shares on all connected
 servers:
     * pick a share not in M, and the server not in M that is next on the
 permuted list, wrapping around if necessary. Try to extend M by putting
 that share onto that server.
  * place any remaining shares on servers that are already in the map
 (don't count these in |M|).
  * if the file is not retrievable, report that the repair failed
 completely. If k <= |M| < H, report that the file is retrievable but
 unhealthy. In any case report what |M| is.

 The while loop should be done in parallel, with up to N - |M| outstanding
 requests.

 Upload would work in the same way (for the general case where there may be
 existing shares), except that it would fail if it is not possible to
 achieve |M| < H.

-- 
Ticket URL: <http://tahoe-lafs.org/trac/tahoe-lafs/ticket/1130#comment:12>
tahoe-lafs <http://tahoe-lafs.org>
secure decentralized storage