[tahoe-dev] [tahoe-lafs] #1170: does new-downloader perform badly for certain situations (such as today's Test Grid)?

[tahoe-lafs]

#1170: does new-downloader perform badly for certain situations (such as today's
Test Grid)?
------------------------------+---------------------------------------------
     Reporter:  zooko         |       Owner:                                           
         Type:  defect        |      Status:  new                                      
     Priority:  critical      |   Milestone:  1.8.0                                    
    Component:  code-network  |     Version:  1.8β                                     
   Resolution:                |    Keywords:  immutable download performance regression
Launchpad Bug:                |  
------------------------------+---------------------------------------------

Comment (by zooko):

 Replying to [comment:27 warner]:

 > But I think this might improve the diversity of downloads without going
 down
 > the full {{{itertools.combinations}}}-enumerating route that represents
 the
 > "complete" way to approach this problem.

  (Parenthetical historical observation which is pleasurable to me: Your
 heuristic algorithm for server selection (for download) in comment:27, and
 your observation that it is susceptible to failure in certain cases, is
 similar to my proposed heuristic algorithm for server selection for
 ''upload'' in #778 (comment:156:ticket:778, for the benefit of future
 cyborg archaeologist historians). David-Sarah [comment:162:ticket:778 then
 observed] that finding the optimal solution was a standard graph theory
 problem named "maximum matching of a bipartite graph". Kevan then
 implemented it and thus we were able to finish #778.)

 My copy of Cormen, Leiserson, Rivest 1st Ed. says (chapter 27.3) that the
 Ford-Fulkerson solution requires computation O(V * E) where V is the
 number of vertices (num servers plus num shares) and E is the number of
 edges (number of (server, share) tuples).

 Now what Kevan actually implemented in
 [source:src/allmydata/util/happinessutil.py at 4593#L80 happinessutil.py]
 just returns the size of the maximum matching, and what we want here is an
 actual matching. I'm not 100% sure but I think if you save all the
 {{{path}}}'s that are returned from {{{augmenting_path_for()}}} in
 {{{servers_of_happiness()}}} and return the resulting set of paths then
 you'll have your set of server->share mappings.

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