docs/historical/peer-selection-tahoe2.txt

   1 = THIS PAGE DESCRIBES HISTORICAL DESIGN CHOICES. SEE docs/architecture.rst FOR CURRENT DOCUMENTATION =
   2
   3 When a file is uploaded, the encoded shares are sent to other peers. But to
   4 which ones? The PeerSelection algorithm is used to make this choice.
   5
   6 Early in 2007, we were planning to use the following "Tahoe Two" algorithm.
   7 By the time we released 0.2.0, we switched to "tahoe3", but when we released
   8 v0.6, we switched back (ticket #132).
   9
  10 As in Tahoe Three, the verifierid is used to consistently-permute the set of
  11 all peers (by sorting the peers by HASH(verifierid+peerid)). Each file gets a
  12 different permutation, which (on average) will evenly distribute shares among
  13 the grid and avoid hotspots.
  14
  15 With our basket of (usually 10) shares to distribute in hand, we start at the
  16 beginning of the list and ask each peer in turn if they are willing to hold
  17 on to one of our shares (the "lease request"). If they say yes, we remove
  18 that share from the basket and remember who agreed to host it. Then we go to
  19 the next peer in the list and ask them the same question about another share.
  20 If a peer says no, we remove them from the list. If a peer says that they
  21 already have one or more shares for this file, we remove those shares from
  22 the basket. If we reach the end of the list, we start again at the beginning.
  23 If we run out of peers before we run out of shares, we fail unless we've
  24 managed to place at least some number of the shares: the likely threshold is
  25 to attempt to place 10 shares (out of which we'll need 3 to recover the
  26 file), and be content if we can find homes for at least 7 of them.
  27
  28 In small networks, this approach will loop around several times and place
  29 several shares with each node (e.g. in a 5-host network with plenty of space,
  30 each node will get 2 shares). In large networks with plenty of space, the
  31 shares will be placed with the first 10 peers in the permuted list. In large
  32 networks that are somewhat full, we'll need to traverse more of the list
  33 before we find homes for the shares. The average number of peers that we'll
  34 need to talk to is vaguely equal to 10 / (1-utilization), with a bunch of
  35 other terms that relate to the distribution of free space on the peers and
  36 the size of the shares being offered. Small files with small shares will fit
  37 anywhere, large files with large shares will only fit on certain peers, so
  38 the mesh may have free space but no holes large enough for a very large file,
  39 which might indicate that we should try again with a larger number of
  40 (smaller) shares.
  41
  42 When it comes time to download, we compute a similar list of permuted
  43 peerids, and start asking for shares beginning with the start of the list.
  44 Each peer gives us a list of the shareids that they are holding. Eventually
  45 (depending upon how much churn the peerlist has experienced), we'll find
  46 holders for at least 3 shares, or we'll run out of peers. If the mesh is very
  47 large and we want to fail faster, we can establish an upper bound on how many
  48 peers we should talk to (perhaps by recording the permuted peerid of the last
  49 node to which we sent a share, or a count of the total number of peers we
  50 talked to during upload).
  51
  52 I suspect that this approach handles churn more efficiently than tahoe3, but
  53 I haven't gotten my head around the math that could be used to show it. On
  54 the other hand, it takes a lot more round trips to find homes in small meshes
  55 (one per share, whereas tahoe three can do just one per node).
  56