[tahoe-dev] [tahoe-lafs] #1170: does new-downloader perform badly for certain situations (such as today's Test Grid)?
tahoe-lafs
trac at tahoe-lafs.org
Sat Aug 14 05:18:37 UTC 2010
#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
More information about the tahoe-dev
mailing list