[tahoe-lafs-trac-stream] [Tahoe-LAFS] #1187: mitigate the performance bottleneck of slow servers in download

[Tahoe-LAFS]

#1187: mitigate the performance bottleneck of slow servers in download
------------------------------+----------------------------------
     Reporter:  davidsarah    |      Owner:
         Type:  defect        |     Status:  new
     Priority:  major         |  Milestone:  undecided
    Component:  code-network  |    Version:  1.8β
   Resolution:                |   Keywords:  download performance
Launchpad Bug:                |
------------------------------+----------------------------------
Changes (by lpirl):

 * cc: tahoe-lafs.org@… (added)


Old description:

> Ticket #1170 showed that server selection can have a big impact on
> download performance (presumably the same is true of upload performance)
> when the chosen servers have different effective bandwidths. For example,
> ticket:1170#comment:94 showed an overall download bandwidth of ~90 Kbps
> vs ~190 Kbps depending on how many shares were taken from each of two
> servers.
>
> My hypothesis is that this is mainly due to the time to download each
> segment being bottlenecked by the slowest server. Once we've downloaded
> the share(s) for a given segment from the faster servers and are waiting
> for the slower ones, the faster servers are left idle until the next
> segment.
>
> In principle, we can use the erasure coding to mitigate this bottleneck.
> If k were larger than it typically is now, we could download as many
> shares per segment from each server as its current effective bandwidth is
> able to support. Since the individual shares would be a smaller fraction
> of the segment size, so would be the wasted time per segment.
>
> A further optimization would be to pipeline requests across consecutive
> segments. That is, when we're getting near to finishing the download of
> shares for a segment, we can also be downloading shares for the next
> segment (but ''only'' the next segment) from servers that would otherwise
> be idle. Note that this depends on downloading a variable number of
> shares from each server for each segment (otherwise, the servers that
> finish first on one segment would also typically finish first on the next
> segment, so we would either have unbounded memory usage or still have to
> leave the ~~faster servers~~ servers that finish first idle some of the
> time).
>
> It isn't entirely clear how large k would need to be for this approach to
> work. If it would need to be larger than the number of servers, then we
> would have to rethink the servers-of-happiness criterion. The current
> definition basically only credits each server for having one share, and
> it would have to be changed to credit each server for having multiple
> shares. I think this can still be given a fairly simple definition in the
> bipartite matching model.

New description:

 Ticket #1170 showed that server selection can have a big impact on
 download performance (presumably the same is true of upload performance)
 when the chosen servers have different effective bandwidths. For example,
 ticket:1170#comment:94 showed an overall download bandwidth of ~90 Kbps vs
 ~190 Kbps depending on how many shares were taken from each of two
 servers.

 My hypothesis is that this is mainly due to the time to download each
 segment being bottlenecked by the slowest server. Once we've downloaded
 the share(s) for a given segment from the faster servers and are waiting
 for the slower ones, the faster servers are left idle until the next
 segment.

 In principle, we can use the erasure coding to mitigate this bottleneck.
 If k were larger than it typically is now, we could download as many
 shares per segment from each server as its current effective bandwidth is
 able to support. Since the individual shares would be a smaller fraction
 of the segment size, so would be the wasted time per segment.

 A further optimization would be to pipeline requests across consecutive
 segments. That is, when we're getting near to finishing the download of
 shares for a segment, we can also be downloading shares for the next
 segment (but ''only'' the next segment) from servers that would otherwise
 be idle. Note that this depends on downloading a variable number of shares
 from each server for each segment (otherwise, the servers that finish
 first on one segment would also typically finish first on the next
 segment, so we would either have unbounded memory usage or still have to
 leave the ~~faster servers~~ servers that finish first idle some of the
 time).

 It isn't entirely clear how large k would need to be for this approach to
 work. If it would need to be larger than the number of servers, then we
 would have to rethink the servers-of-happiness criterion. The current
 definition basically only credits each server for having one share, and it
 would have to be changed to credit each server for having multiple shares.
 I think this can still be given a fairly simple definition in the
 bipartite matching model.

--

--
Ticket URL: <https://tahoe-lafs.org/trac/tahoe-lafs/ticket/1187#comment:4>
Tahoe-LAFS <https://Tahoe-LAFS.org>
secure decentralized storage