[tahoe-lafs-trac-stream] [tahoe-lafs] #1382: immutable peer selection refactoring and enhancements

[tahoe-lafs]

#1382: immutable peer selection refactoring and enhancements
-------------------------+-------------------------------------------------
     Reporter:  kevan    |      Owner:  markberger
         Type:           |     Status:  new
  enhancement            |  Milestone:  1.11.0
     Priority:  major    |    Version:  1.8.2
    Component:  code-    |   Keywords:  review-needed servers-of-happiness
  peerselection          |  blocks-release
   Resolution:           |
Launchpad Bug:           |
-------------------------+-------------------------------------------------

Comment (by zooko):

 So, I was trying to update docs/specifications/servers-of-happiness.rst to
 explain the algorithm and provide an "intuition" of it for readers, and
 look what happened: I confused myself again! I apparently do not have an
 "intuition" that matches the behavior of servers-of-happiness:

 {{{
 diff --git a/docs/specifications/servers-of-happiness.rst
 b/docs/specifications/servers-of-happiness.rst
 index d18432c..6a335a7 100644
 --- a/docs/specifications/servers-of-happiness.rst
 +++ b/docs/specifications/servers-of-happiness.rst
 @@ -14,29 +14,85 @@ is distributed on the grid in such a way as to ensure
 that it will
  probably survive in good enough shape to be recoverable, even if a few
  things go wrong between the time of the test and the time that it is
  recovered. Our current upload health metric for immutable files is called
 -'servers-of-happiness'; its predecessor was called 'shares-of-happiness'.
 -
 -shares-of-happiness used the number of encoded shares generated by a
 -file upload to say whether or not it was healthy. If there were more
 -shares than a user-configurable threshold, the file was reported to be
 -healthy; otherwise, it was reported to be unhealthy. In normal
 -situations, the upload process would distribute shares fairly evenly
 -over the peers in the grid, and in that case shares-of-happiness
 -worked fine. However, because it only considered the number of shares,
 -and not where they were on the grid, it could not detect situations
 -where a file was unhealthy because most or all of the shares generated
 -from the file were stored on one or two peers.
 -
 -servers-of-happiness addresses this by extending the share-focused
 -upload health metric to also consider the location of the shares on
 -grid. servers-of-happiness looks at the mapping of peers to the shares
 -that they hold, and compares the cardinality of the largest happy subset
 -of those to a user-configurable threshold. A happy subset of peers has
 -the property that any k (where k is as in k-of-n encoding) peers within
 -the subset can reconstruct the source file. This definition of file
 -health provides a stronger assurance of file availability over time;
 -with 3-of-10 encoding, and happy=7, a healthy file is still guaranteed
 -to be available even if 4 peers fail.
 +'servers-of-happiness'.
 +
 +The servers-of-happiness upload health metric considers the location of
 the
 +shares on grid. servers-of-happiness looks at the mapping of peers to the
 +shares that they hold, and considers the size of the largest set of
 (server,
 +share) pairs such that no server appears more than once in the set and no
 +share appears more than once in the set. The size of the set is called
 the
 +Happiness value.
 +
 +The Happiness value can be understood as the number of servers that are
 +"independently" contributing to the health of the file. For example, if
 +server A is holding share 0, and server B is holding share 1, then the
 +Happiness value is 2.::
 +
 +  example 1
 +  ---------
 +
 +  server A → share 0
 +  server B → share 1
 +
 +  Happiness value = 2
 +
 +In this case, adding server C holding share 0 would not increase the
 +Happiness value.::
 +
 +  example 2
 +  ---------
 +
 +  server A → share 0
 +  server B → share 1
 +  server C → share 1
 +
 +  Happiness value = 2
 +
 +You can understand this intuitively as being that server C doesn't
 maximally
 +increase the robustness of the file. Server C will help if server B
 +disappears, but server C will not be any added help beyond what server B
 +provided, if server A disappears.
 +
 +But if the added server C held a new share, then it would increase the
 +Happiness value.::
 +
 +  example 3
 +  ---------
 +
 +  server A → share 0
 +  server B → share 1
 +  server C → share 2
 +
 +  Happiness value = 3
 +
 +For another example, if you have this distribution::
 +
 +  example 4
 +  ---------
 +
 +  server A → share 0, share 1
 +  server B → share 1, share 2
 +
 +  Happiness value = 2
 +
 +And you add a server C which holds share 0 and share 1, then you increase
 the
 +Happiness level to 3.::
 +
 +  example 5
 +  ---------
 +
 +  server A → share 0, share 1
 +  server B → share 1, share 2
 +  server C → share 1, share 2
 +
 +  Happiness value = 3
 +
 +XXX FIXME: how come going from example 4 to example 5 increases Happiness
 but going from example 1 to example 2 doesn't ?? —Zooko
 +
 +XXX This definition of file health
 +provides a stronger assurance of file availability over time; with
 3-of-10
 +encoding, and happy=7, a healthy file is still guaranteed to be available
 +even if 4 peers fail.

  Measuring Servers of Happiness
  ==============================
 }}}

-- 
Ticket URL: <https://tahoe-lafs.org/trac/tahoe-lafs/ticket/1382#comment:63>
tahoe-lafs <https://tahoe-lafs.org>
secure decentralized storage