Bug#884914: apt: does not deal well with high request latency web servers

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Bug#884914: apt: does not deal well with high request latency web servers

Philipp Kern-6
Source: apt
Severity: wishlist
X-Debbugs-Cc: [hidden email]

At work our packages and package lists are served by a web service that
has relatively high time to first byte latency. Once it starts
transmitting the bytes are pushed in a fast way but fetching the bytes
in the first place takes a "long" time. While we are somewhat fine with
the latency on "apt update" a lot of packages, it imposes a very high
penalty on systems that need to fetch a lot of small packages (e.g.
build dependencies).

The only solution apt offers today is pipelining. While it allows to
have a fast start for congestion control purposes, pipelining always
requires to send the answers in order down the pipe. Unless you set a
depth that equals the amount of packages to fetch, it will only
replenish the queue one by one as packages are completed, requiring a
full RTT to insert a new item. Furthermore it does impact the server
negatively if you consider the first hop to be a load balancer that fans
out to other backends. It needs to cache all answers to return them in
order.

An easy workaround (few lines changed) would be to just spawn multiple
transports for a given host target, to make use of multiple connections.
In this case load balancing the requests onto them speeds up the
transaction essentially to line speed. There is still the drawback that
naive load balancing (essentially adding n queues for a host) happens at
the beginning of the transaction rather than through-out. This is not a
concern in our particular case, though, as the main issue is to enqueue
enough requests on the server side.

It has been raised that this would cause violated assumptions by mirror
operators though, in case they approximate per-client limits using
per-connection rate limiting (because bucketing is hard). I'd argue that
an optional configuration setting that is not enabled by default should
still be fair to offer.

Another solution to solve this problem would be to implement HTTP/2
support, which allows to answer the requests non-linearly. In this case
a single connection would very likely be enough, as the server can just
answer what's available and the pipeline will be replenished
asynchronously. In our case the load balancer would also offer HTTP/2
server-side[1]. However I'd argue that such an implementation should
then not be hand-rolled like the HTTP(S) transport and would require
depending on another library like nghttp2. So it would likely need to
live in its own apt transport.

Happy to hear your thoughts on how to solve this. And please keep up the
great work. :)

Kind regards and thanks
Philipp Kern

[1] Note that HTTP/2 makes encryption mandatory.


signature.asc (523 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Bug#884914: apt: does not deal well with high request latency web servers

Philipp Kern-6
Hi,

On 12/21/2017 11:02 AM, Philipp Kern wrote:

> At work our packages and package lists are served by a web service that
> has relatively high time to first byte latency. Once it starts
> transmitting the bytes are pushed in a fast way but fetching the bytes
> in the first place takes a "long" time. While we are somewhat fine with
> the latency on "apt update" a lot of packages, it imposes a very high
> penalty on systems that need to fetch a lot of small packages (e.g.
> build dependencies).
>
> The only solution apt offers today is pipelining. While it allows to
> have a fast start for congestion control purposes, pipelining always
> requires to send the answers in order down the pipe. Unless you set a
> depth that equals the amount of packages to fetch, it will only
> replenish the queue one by one as packages are completed, requiring a
> full RTT to insert a new item. Furthermore it does impact the server
> negatively if you consider the first hop to be a load balancer that fans
> out to other backends. It needs to cache all answers to return them in
> order.
>
> An easy workaround (few lines changed) would be to just spawn multiple
> transports for a given host target, to make use of multiple connections.
> In this case load balancing the requests onto them speeds up the
> transaction essentially to line speed. There is still the drawback that
> naive load balancing (essentially adding n queues for a host) happens at
> the beginning of the transaction rather than through-out. This is not a
> concern in our particular case, though, as the main issue is to enqueue
> enough requests on the server side.
>
> It has been raised that this would cause violated assumptions by mirror
> operators though, in case they approximate per-client limits using
> per-connection rate limiting (because bucketing is hard). I'd argue that
> an optional configuration setting that is not enabled by default should
> still be fair to offer.
>
> Another solution to solve this problem would be to implement HTTP/2
> support, which allows to answer the requests non-linearly. In this case
> a single connection would very likely be enough, as the server can just
> answer what's available and the pipeline will be replenished
> asynchronously. In our case the load balancer would also offer HTTP/2
> server-side[1]. However I'd argue that such an implementation should
> then not be hand-rolled like the HTTP(S) transport and would require
> depending on another library like nghttp2. So it would likely need to
> live in its own apt transport.
>
> Happy to hear your thoughts on how to solve this. And please keep up the
> great work. :)
>
> Kind regards and thanks
> Philipp Kern
>
> [1] Note that HTTP/2 makes encryption mandatory.
gentle post-vacational ping. I'm happy to look at whatever is needed
here, however I'd prefer to work towards a consensus. ;-)

Kind regards and thanks
Philipp Kern


signature.asc (499 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Bug#884914: apt: does not deal well with high request latency web servers

David Kalnischkies-4
In reply to this post by Philipp Kern-6
Hi,

On Thu, Dec 21, 2017 at 11:02:22AM +0100, Philipp Kern wrote:
> An easy workaround (few lines changed) would be to just spawn multiple
> transports for a given host target, to make use of multiple connections.

The apt team was always against doing this which eventually spawned
stuff like the enormously hacky "apt-fast". The problem we see with this
is that as soon we add this to mainline users will activate such options
even if it makes no longterm sense for them because it feels faster in
the shortterm against our shared mirror network as adding more own cars
is always a good strategy to combat a traffic jam (until everyone else
has adopted that strategy as well and so everyone is worse off).


> Another solution to solve this problem would be to implement HTTP/2
> support, which allows to answer the requests non-linearly. In this case

I am pretty sure that will eventually happen. Especially if it is in its
own transport package as you can do everything there. It is currently
not that high on the list of things to do through as the current focus
in that area is for the moment to improve what we have in terms of
security and co. Not to bad an idea given that protocols we deal with
tend to increase in complexity… hello HTTP/2. :P

What makes HTTP/2 perhaps a bit "complicated" is the strong relation
with HTTP/1, so things would need to be shared and exchanged. Would be
sad if we end up in another http/https or tor/http(s) situation until we
find the time to make it "proper".

[HTTP/2 has an unencrypted variant aka "h2c" btw. At least on paper
– I know that browsers aren't going to implement it.]


> Happy to hear your thoughts on how to solve this.

You could do something similar to what httpredir.d.o was doing or work
with the (now reimplemented) -mirror method. That hard-depends on your
"behind load-balancer" servers to be reachable directly through. But it
gets you parallel connections without changing clients (at least in the
first case, in the second you will need to wait a few years until this
becomes true I guess).


Best regards

David Kalnischkies

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Bug#884914: apt: does not deal well with high request latency web servers

Philipp Kern-2
On 01/07/2018 07:49 PM, David Kalnischkies wrote:
> The apt team was always against doing this which eventually spawned
> stuff like the enormously hacky "apt-fast". The problem we see with this
> is that as soon we add this to mainline users will activate such options
> even if it makes no longterm sense for them because it feels faster in
> the shortterm against our shared mirror network as adding more own cars
> is always a good strategy to combat a traffic jam (until everyone else
> has adopted that strategy as well and so everyone is worse off).

Well, we could also go and let mirrors flag a connection limit
themselves that cannot be overwritten by local configuration...

>> Another solution to solve this problem would be to implement HTTP/2
>> support, which allows to answer the requests non-linearly. In this case
> I am pretty sure that will eventually happen. Especially if it is in its
> own transport package as you can do everything there. It is currently
> not that high on the list of things to do through as the current focus
> in that area is for the moment to improve what we have in terms of
> security and co. Not to bad an idea given that protocols we deal with
> tend to increase in complexity… hello HTTP/2. :P
>
> What makes HTTP/2 perhaps a bit "complicated" is the strong relation
> with HTTP/1, so things would need to be shared and exchanged. Would be
> sad if we end up in another http/https or tor/http(s) situation until we
> find the time to make it "proper".
That said, you just went the other way. Not that I liked the cURL https
transport, given that it was fairly stupid^Wstraightforward. But at
least it used a library. So I guess I'm curious if you'd be open to
picking a library and then rewriting everything to use that single one
for all of HTTP(S) 1.1/2. (Assuming such a library exists by now.)

> [HTTP/2 has an unencrypted variant aka "h2c" btw. At least on paper
> – I know that browsers aren't going to implement it.]

Well, question is then also if you can assume that nodes in the path
would implement this (like reverse proxies/load balancers etc).
Otherwise it will only exist on paper rather than real setups.

>> Happy to hear your thoughts on how to solve this.
> You could do something similar to what httpredir.d.o was doing or work
> with the (now reimplemented) -mirror method. That hard-depends on your
> "behind load-balancer" servers to be reachable directly through. But it
> gets you parallel connections without changing clients (at least in the
> first case, in the second you will need to wait a few years until this
> becomes true I guess).

That's actually an excellent idea. We'll try that out. I actually wrote
code for it already and it's a pretty straightforward approach, but
we'll take another stab at attempting to reduce time to first byte
latency first.

Kind regards and thanks a lot!
Philipp Kern


signature.asc (523 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Bug#884914: apt: does not deal well with high request latency web servers

David Kalnischkies-4
On Sun, Jan 14, 2018 at 06:06:28PM +0100, Philipp Kern wrote:
> That said, you just went the other way. Not that I liked the cURL https
> transport, given that it was fairly stupid^Wstraightforward. But at
                                              ^^^ you must be joking…¹
> least it used a library. So I guess I'm curious if you'd be open to
> picking a library and then rewriting everything to use that single one
> for all of HTTP(S) 1.1/2. (Assuming such a library exists by now.)

Well, curl wasn't a good choice for implementing https for us nowadays
as it is big library supporting lots of things we don't want (apt
downloads over IMAPS after a http redirect, Transport-Encoding: gzip, …)
and not supporting many things we do (SRV records, working with hashes
…).  Many improvements to https were only possible by sidestepping curl
– that isn't how you want to interact with a library. If there is
a library which would give us what we ended up with by combining our
http with a TLS wrapping we could change to that (assuming its not too
obscure, linux-only, … and so on).

There is still a lot of code to be written for the actual implementation
of the transport as we want to be in control of a lot of things:
Redirects e.g. can't be handled internally by the library: We like to
limit what is possible (e.g. no https→http redirects) and want to keep
an instance single-connection: a transport can't change the server it
talks to at runtime as it has no access to the configuration applying
potentially for this server (auth, settings, …).  Beside, it isn't very
realistic that the library does play as much with hashes as we do from
terminating the connection if the content-length didn't match what we
expect to fixing pipelining problems at runtime simply because that
isn't how the rest of the internet works…

Of course, that sounds like NIH, but on the other hand we didn't want to
implement TLS by hand nor am I particular interested in hand-rolling the
binary parts of http2 if it can be helped, so from my viewpoint its not
NIH but "just" the guesstimate that there will be no off-the-shelf
solution. A transport is "just" a lot more than a wget wrapped in
C code.

¹ yes, I am allowed to "bash" curl as I am due to a very minor
  contribution in relation to SOCKS² error reporting considered
  a contributor as I recently found out. So apt leaving curl had
  at least some advantage for both sides I guess. ;)

² something I thought I wouldn't implement myself either, so
  perhaps there is some hope for me doing http2 NIH-style still ;)

> > [HTTP/2 has an unencrypted variant aka "h2c" btw. At least on paper
> > – I know that browsers aren't going to implement it.]

[That was just a comment on "requires TLS" – on paper it doesn't. I am well
aware that this might never really exist in practice and I am not concerned
either way.]


> >> Happy to hear your thoughts on how to solve this.
> > You could do something similar to what httpredir.d.o was doing or work
> > with the (now reimplemented) -mirror method. That hard-depends on your
> > "behind load-balancer" servers to be reachable directly through. But it
> > gets you parallel connections without changing clients (at least in the
> > first case, in the second you will need to wait a few years until this
> > becomes true I guess).
>
> That's actually an excellent idea. We'll try that out. I actually wrote
> code for it already and it's a pretty straightforward approach, but
> we'll take another stab at attempting to reduce time to first byte
> latency first.
Julian commented on IRC a while ago that I wasn't explaining the second
option – using the mirror method – very well. So for the record:
Assuming you have 3 mirrors and a load-balancer you could place
a mirrorlist file containing the 3 mirrors on the balancer, point your
clients to it and be done. In pre-1.6 versions apt will consistently
choose one of the mirrors [based on the hostname of the client] – so you
get what you have at the moment more or less. With 1.6 onwards apt will
download each file from a randomly picked server³, so you will end up
with 3 parallel downloads in practice [expect if you are randomly
unlucky or if you run 'update' as that will stick to the same mirror by
default to avoid sync problems]. See the apt-transport-mirror manpage
(in 1.6) for advanced details.

³ more exact: The list of three mirrors will be shuffled randomly for
each file and then the download is attempt in this order, so it isn't
exactly load-balanced, but close enough for now.



Anyhow: What are we going to do with this bugreport now? Close, retitle
for http2 support or is there some other action we can take to fix the
initial problem?


Best regards

David Kalnischkies

signature.asc (849 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Bug#884914: apt: does not deal well with high request latency web servers

Julian Andres Klode-4
In reply to this post by Philipp Kern-6
On Thu, Dec 21, 2017 at 11:02:22AM +0100, Philipp Kern wrote:

> Source: apt
> Severity: wishlist
> X-Debbugs-Cc: [hidden email]
>
> At work our packages and package lists are served by a web service that
> has relatively high time to first byte latency. Once it starts
> transmitting the bytes are pushed in a fast way but fetching the bytes
> in the first place takes a "long" time. While we are somewhat fine with
> the latency on "apt update" a lot of packages, it imposes a very high
> penalty on systems that need to fetch a lot of small packages (e.g.
> build dependencies).
>
> The only solution apt offers today is pipelining. While it allows to
> have a fast start for congestion control purposes, pipelining always
> requires to send the answers in order down the pipe. Unless you set a
> depth that equals the amount of packages to fetch, it will only
> replenish the queue one by one as packages are completed, requiring a
> full RTT to insert a new item. Furthermore it does impact the server
> negatively if you consider the first hop to be a load balancer that fans
> out to other backends. It needs to cache all answers to return them in
> order.

I noticed there's a bug in pipelining, introduced in the fix for bug
832113. If the server sends a Connection: close at some point, apt will
refuse to use pipelining for the next connection.

The problem here is that server that do pipeline well, also eventually
close connections - for example, archive.ubuntu.com closes a connection
after about 101 requests. This means that the first 101 requests keep
a filled pipeline (9-10 items) for me, but the remaining ones always
do one request after another. I don't know if you're affected by this
as well, or if this is standard behavior for web servers.

--
debian developer - deb.li/jak | jak-linux.org - free software dev
ubuntu core developer                              i speak de, en