On Wednesday 12 August 2009 09:49:37 am Zooko Wilcox-O'Hearn wrote: > Interesting ideas, Shawn. I'll just respond to a couple of details, > below, plus I'll say that I think Kevan should proceed with his plan > to implement "servers of happiness" now, as it is a small enough > change that he can finish it before the fall semester starts. :-)
I think the statistical approach is perhaps not as much effort as you're thinking, but the fall semester is coming up pretty quickly. > In the long run, I can see how some people (possibly including me) > would like the sort of sophisticated, heuristical, statistical > approach that you envision, but I can also see how some people > (possibly including me) would want a dumber, more predictable set of > rules, such as "Make sure there are always at least K+1 shares in > each of these Q co-los, and that's the entire ruleset.". Absolutely I see the value in multiple policies being available. One thing that is becoming clear, though is that what we're talking about is broader than just a peer selection policy, because FEC parameters are part of the decision parameters as well. At least the choice of M and perhaps K as well. One more comment on that: Assuming the reliability calculation is sufficiently sophisticated and accurate, your dumber, more predictable, rule and the statistical calculation should reach the same results. In fact, that's one of the criteria I would use to validate the reliability calculation, assuming that it was sophisticated enough to include server set failure modes (meaning a set of servers can fail all at once, because a meteor hit the machine room or something). > > 2. Retrieval performance is maximized when shares are retrived > > from as many servers at once (assuming all are roughly equally > > responsive). This means that K should be set to the size of the > > grid, and M adjusted based on reliability requirements. This is > > the reverse of what I have been thinking. > > I went through a similar reversal: > > http://allmydata.org/pipermail/tahoe-dev/2009-April/001554.html # > using the volunteer grid (dogfood tasting report, continued) I remember that e-mail. One of the things I plan to do while sitting on the beach this week is work out some concise formulas/algorithms for computing reliability as a function of M. I'll be sure to use your 13-of-16 case as an example, and see how much it differs from 13-of-13 or 13-of-26. After a few seconds more thought, I've changed the guess from my previous note: I think 13-of-16 is better than 13-of-13, and the reliability is a smooth function of M, so non-multiples of K are useful choices. > > 3. M larger than the grid means that each server will receive > > multiple shares. A reasonable first assumption is that all shares > > on a given server will survive or fail together, so the effective > > reliability of a file is a function not of how many shares must be > > lost for it to disappear, but how many servers. > > Yes, thus the motivation for #778. Yes. I just wanted to make the assumption explicit. It's not 100% true, of course, there are plenty of ways that a server could lose just one of the shares it's keeping. But they're sufficiently less likely than all-or-none that I think we can ignore them for the moment. Perhaps in the future they could be considered. One nice thing is that the math I described in my paper (really need to finish that thing...) can accommodate multiple failure modes per share and failure modes that affect multiple shares or multiple servers. You can make the model as sophisticated as you like. The only limitation is that the structure of the share groupings must be hierarchical. > By the way, I wonder if #678 would interest you. If we had #678, > then your strategy could delay making up its mind about the best > value of M until later, during a repair process, possibly after the > set of servers and their known qualities has changed. I think I'd ultimately like the repair process to go through the same decision process as the original upload when picking parameters -- but #678s idea of keeping K and using the systematic nature of the share generation to just push additional shares is really interesting as a lower-cost method to increase reliability. An even lower-cost method is to simply replicate existing shares. If copying one or two existing shares from one server to another pushes you above the required reliability threshold, it's a zero-computation solution. > It should be > relatively easy to make up your mind about a good value for K -- for > example, maybe just K = number-of-servers for starters? For small grids, I can't think of a reason to choose a different value for K. Perhaps you could match your target reliability more precisely by varying both M and K, and achieve a little lower expansion factor. But if the assumption is that most servers are on asymmetric Internet connections, setting K = number-of-servers should provide the best download performance, and that's probably worth a tiny bit of extra expansion. > #678 is not a ticket that can be fixed before the fall semester > starts, though. Hopefully it will be fixed by the next generation of > capabilities (http://allmydata.org/trac/tahoe/wiki/NewCapDesign ). Ohhh... that's a good point. Allowing M and/or K to be changed by a repairer will require a new cap structure. That would be a good point in time to add a hamming distance parameter to the cap as well, assuming we decide that is sufficiently helpful to justify the extra length. Shawn. _______________________________________________ tahoe-dev mailing list [email protected] http://allmydata.org/cgi-bin/mailman/listinfo/tahoe-dev
