[tahoe-dev] Kevan's master's thesis

[Zooko O'Whielacronx]

"Robust Resource Allocation in Distributed Filesystems" Kevan
Carstensen's master's thesis

https://zooko.com/uri/URI%3ADIR2-RO%3Aoljrwy5i2t3dhcx5mzrksegehe%3Axtac4ubcnr5eqo6d7h4wyj5sm522olj4mthizz2i3lfw2b5nla6q/Latest/compsci/Carstensen-2011-Robust_Resource_Allocation_In_Distributed_Filesystem.pdf

(Also linked to from https://tahoe-lafs.org/trac/tahoe-lafs/wiki/Bibliography )

I can't believe I never read this before. This is great! What a
practical, detailed, meaty master's thesis. Reading it makes me
understand why we have so many weird edge cases in the
servers-of-happiness code:

"The existing multi-phase share placement algorithm was left intact,
except for modifications to create and maintain the necessary data
structures to allow the bipartite graph to be constructed. After peer
selection and share allocation, but before the uploader actually
started uploading data, the test described above is performed. If the
share placement yields acceptable availability properties, then the
storage operation is allowed to continue; otherwise, the storage
operation fails. Though this had advantages in terms of implementation
(in particular, it made the change much less invasive than it could
have been), it comes at the cost of a fairly significant mismatch
between the share placement algorithm and the share placement
availability test. Specifically, the share placement algorithm wasnot
designed to satisfy the servers-of-happiness upload availability test.
In many situations, the existing share placement algorithm would do a
good job satisfying the servers of happiness test, but there are many
cases in which it doesn’t. For example, consider the case of a share
placement operation that comes upon a server that already holds some
or all of the shares that need placing. This may happen in storage
operations associated with a high-level repair, in which the file to
be stored has already been stored on the filesystem. The existing
share placement algorithm would mark these shares as placed. This is
acceptable from the standpoint of the simpler shares of happiness
share placement test, but does not do a good job of satisfying the
servers of happiness test, since only one of the shares on the single
storage server can contribute an edge to the matching and since the
existing placement algorithm will not attempt to place any of the
other shares elsewhere. Instead, we’d like the share allocation
algorithm to attempt to spread the shares around to other storage
servers, improving availability characteristics. These sorts of
interactions show some of the benefits to a share placement strategy
that is conceptually integrated with the availability test performed
upon the share placement."

So this helps me understand the basic architectural cause of much of
the following cluster of tickets:

https://tahoe-lafs.org/trac/tahoe-lafs/ticket/1124# upload is unhappy
even though the shares are already distributed

https://tahoe-lafs.org/trac/tahoe-lafs/ticket/1130# Failure to achieve
happiness in upload or repair

https://tahoe-lafs.org/trac/tahoe-lafs/ticket/1293#
servers-of-happiness is too conservative when K = 1

https://tahoe-lafs.org/trac/tahoe-lafs/ticket/1382# immutable peer
selection refactoring and enhancements

https://tahoe-lafs.org/trac/tahoe-lafs/ticket/1814#
UploadUnhappinessError despite no apparent refusal of shares

I'm thinking of trying to specify something along these lines for a
GSoC-2013 project:

https://tahoe-lafs.org/trac/tahoe-lafs/wiki/GSoCIdeas

Regards,

Zooko