Re: HTTP/2 flow control <draft-ietf-httpbis-http2-17>

Stuart Douglas <stuart.w.douglas@gmail.com> Fri, 20 March 2015 00:22 UTC

Return-Path: <ietf-http-wg-request+bounce-httpbisa-archive-bis2juki=lists.ie@listhub.w3.org>
X-Original-To: ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com
Delivered-To: ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 17CC21A1A83 for <ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com>; Thu, 19 Mar 2015 17:22:39 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -6.8
X-Spam-Level:
X-Spam-Status: No, score=-6.8 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_ADSP_CUSTOM_MED=0.001, DKIM_SIGNED=0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-5, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001, T_DKIM_INVALID=0.01, T_RP_MATCHES_RCVD=-0.01] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 6st78g6HuzlY for <ietfarch-httpbisa-archive-bis2Juki@ietfa.amsl.com>; Thu, 19 Mar 2015 17:22:32 -0700 (PDT)
Received: from frink.w3.org (frink.w3.org [128.30.52.56]) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id BF4DF1A1A72 for <httpbisa-archive-bis2Juki@lists.ietf.org>; Thu, 19 Mar 2015 17:22:30 -0700 (PDT)
Received: from lists by frink.w3.org with local (Exim 4.80) (envelope-from <ietf-http-wg-request@listhub.w3.org>) id 1YYkf3-00021u-47 for ietf-http-wg-dist@listhub.w3.org; Fri, 20 Mar 2015 00:19:37 +0000
Resent-Date: Fri, 20 Mar 2015 00:19:37 +0000
Resent-Message-Id: <E1YYkf3-00021u-47@frink.w3.org>
Received: from lisa.w3.org ([128.30.52.41]) by frink.w3.org with esmtp (Exim 4.80) (envelope-from <stuart.w.douglas@gmail.com>) id 1YYket-0001zb-LD for ietf-http-wg@listhub.w3.org; Fri, 20 Mar 2015 00:19:27 +0000
Received: from mail-ie0-f179.google.com ([209.85.223.179]) by lisa.w3.org with esmtps (TLS1.0:RSA_ARCFOUR_SHA1:16) (Exim 4.72) (envelope-from <stuart.w.douglas@gmail.com>) id 1YYker-0000N9-AI for ietf-http-wg@w3.org; Fri, 20 Mar 2015 00:19:27 +0000
Received: by ieclw3 with SMTP id lw3so80278557iec.2 for <ietf-http-wg@w3.org>; Thu, 19 Mar 2015 17:18:59 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc:content-type; bh=ZgLpqcCFiHPSXCkQSnzLidstNQAJexmuKG6DYr/KENo=; b=Jq6AtBQBJ41KaO55jpXcnFVNkSIDijfS9VIBSmufIJXNZiD0YSyvzwxHGysXOCmE6s Uq4225iOrQJGOPmCfGfvK295Y8U1NaylDxjabQ3NHGVAuN0oMCy7UxsTWfP44QgmN+ms lJL3sCDyYaN0fzd6mvhO0f1bhVtyG3m5cnGFLWeaq3ARyTVbUF9j4U7toyfVtmcaivc6 no5AZtwxHVoixuhO+bgv8Dpx65mNQuFwj2Dj6TaKKiZmJHzGyLaIfPkyTbsWmj+YssiL YID+AkfJqAvLsG91hyrBZvjzCYcRZZ0iqGElugNk633kG7SYEkLwyrXJvTEZ7aRYmtxb Mqbw==
X-Received: by 10.107.8.215 with SMTP id h84mr115850066ioi.89.1426810739512; Thu, 19 Mar 2015 17:18:59 -0700 (PDT)
MIME-Version: 1.0
References: <201503061443.t26EhiV9013453@bagheera.jungle.bt.co.uk>
In-Reply-To: <201503061443.t26EhiV9013453@bagheera.jungle.bt.co.uk>
From: Stuart Douglas <stuart.w.douglas@gmail.com>
Date: Fri, 20 Mar 2015 00:18:58 +0000
Message-ID: <CAAoo=c7Wov+WG9sMNHWumCaAF5v6mdudZWma3jxy6x3L-4DNtw@mail.gmail.com>
To: Bob Briscoe <bob.briscoe@bt.com>, mbelshe@chromium.org, fenix@google.com, martin.thomson@gmail.com
Cc: ietf-http-wg@w3.org
Content-Type: multipart/alternative; boundary="001a113f89bc4a5bbb0511ad4324"
Received-SPF: pass client-ip=209.85.223.179; envelope-from=stuart.w.douglas@gmail.com; helo=mail-ie0-f179.google.com
X-W3C-Hub-Spam-Status: No, score=-2.8
X-W3C-Hub-Spam-Report: DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, URIBL_BLOCKED=0.001, W3C_AA=-1, W3C_WL=-1
X-W3C-Scan-Sig: lisa.w3.org 1YYker-0000N9-AI 750661a1f74e0e5743e4b67750552236
X-Original-To: ietf-http-wg@w3.org
Subject: Re: HTTP/2 flow control <draft-ietf-httpbis-http2-17>
Archived-At: <http://www.w3.org/mid/CAAoo=c7Wov+WG9sMNHWumCaAF5v6mdudZWma3jxy6x3L-4DNtw@mail.gmail.com>
Resent-From: ietf-http-wg@w3.org
X-Mailing-List: <ietf-http-wg@w3.org> archive/latest/28994
X-Loop: ietf-http-wg@w3.org
Resent-Sender: ietf-http-wg-request@w3.org
Precedence: list
List-Id: <ietf-http-wg.w3.org>
List-Help: <http://www.w3.org/Mail/>
List-Post: <mailto:ietf-http-wg@w3.org>
List-Unsubscribe: <mailto:ietf-http-wg-request@w3.org?subject=unsubscribe>

>
> ==a) Intermediate buffer control==
> For this, sliding window-based flow control would be appropriate, because
> the goal is to keep the e2e pipeline full without wasting buffer.
>
> Let me prove HTTP/2 cannot do window flow control. For window flow
> control, the sender needs to be able to advance both the leading and
> trailing edges of the window. In the draft:
> * WINDOW_UPDATE frames can only advance the leading edge of a 'window'
> (and they are constrained to positive values).
> * To advance the trailing edge, window flow control would need a
> continuous stream of acknowledgements back to the sender (like TCP). The
> draft does not provide ACKs at the app-layer, and the app-layer cannot
> monitor ACKs at the transport layer, so the sending app-layer cannot
> advance the trailing edge of a 'window'.
>
> So the protocol can only support credit-based flow control. It is
> incapable of supporting window flow control.
>

> Next, I don't understand how a receiver can set the credit in
> 'WINDOW_UPDATE' to a useful value. If the sender needed the receiver to
> answer the question "How much more can I send than I have seen ACK'd?" that
> would be easy. But because the protocol is restricted to credit, the sender
> needs the receiver to answer the much harder open-ended question, "How much
> more can I send?" So the sender needs the receiver to know how many ACKs
> the sender has seen, but neither of them know that.
>
> The receiver can try, by taking a guess at the bandwidth-delay product,
> and adjusting the guess up or down, depending on whether its buffer is
> growing or shrinking. But this only works if the unknown bandwidth-delay
> product stays constant.
>
> However, BDP will usually be highly variable, as other streams come and
> go. So, in the time it takes to get a good estimate of the per-stream BDP,
> it will probably have changed radically, or the stream will most likely
> have finished anyway. This is why TCP bases flow control on a window, not
> credit. By complementing window updates with ACK stream info, a TCP sender
> has sufficient info to control the flow.
>
> The draft is indeed correct when it says:
> "   this can lead to suboptimal use of available
>    network resources if flow control is enabled without knowledge of the
>    bandwidth-delay product (see [RFC7323]).
> "
> Was this meant to be a veiled criticism of the protocol's own design? A
> credit-based flow control protocol like that in the draft does not provide
> sufficient information for either end to estimate the bandwidth-delay
> product, given it will be varying rapidly.
>

>From my point of view as a server/proxy implementor the flow control window
mostly represent the amount of data I am prepared to buffer.

>From the server as a receiver case we are basically acting as an
intermediary between the network and an end user application. In this case
the flow control credit basically represents the maximum amount of data
that I am prepared to buffer at the HTTP layer. In this case the answer to
'how much more can I send' is simple, it is basically the amount of data I
am prepared to buffer. Because I have no idea how quickly (if at all) the
user application will consume the data, all I can really do is buffer it
and deliver it as the user application requests it.

If I set the flow control window to larger than I am prepared to buffer and
the application does not consume data quickly enough then I have two
options, which are basically stop reading (head of line blocking), or reset
the stream, neither of which is particularly good (head of line blocking is
particularly problematic if the user application is trying to write a
response before reading the request, as window updates will not be
processed).

If I am only prepared to buffer a small amount of data then my performance
is not going to be great no matter what flow control implementation is in
use, and I think that this is basically a limitation of a multiplexed
protocol (unless you are prepared to accept potential HOL blocking).

This mostly only affects server uploads, as clients will likely have to
buffer the whole response anyway so are not constrained by buffer size.

All the issues above basically apply to the intermediary/proxy use case as
well.

Basically I guess what I am getting to is that yes, there are some
situations where HTTP2 might perform worse than HTTP1, however I think the
underlying problem is intrinsic to any sort of multiplexed protocol, rather
than HTTP2's flow control mechanism.


> ==b) Control by the ultimate client app==
> For this case, I believe neither window nor credit-based flow control is
> appropriate:
> * There is no memory management issue at the client end - even if there's
> a separate HTTP/2 layer of memory between TCP and the app, it would be
> pointless to limit the memory used by HTTP/2, because the data is still
> going to sit in the same user-space memory (or at least about the same
> amount of memory) when HTTP/2 passes it over for rendering.
>

Not necessarily, not all clients are browsers, and even with browsers when
downloading a file I imagine the data will generally be transferred
straight to disk rather staying in memory. In general I agree with you
though, and I think most clients will want to set a large window size.


> * Nonetheless, the receiving client does need to send messages to the
> sender to supplement stream priorities, by notifying when the state of the
> receiving application has changed (e.g. if the user's focus switches from
> one browser tab to another).
> * However, credit-based flow control would be very sluggish for such
> control, because credit cannot be taken back once it has been given (except
> HTTP/2 allows SETTINGS_INITIAL_WINDOW_SIZE to be reduced, but that's a
> drastic measure that hits all streams together).
>

This support is provided by PRIORITY frames, using flow control for such
use cases is very problematic and has a good chance of leading to
deadlocks. For example consider a Java Servlet container, new requests will
be read from the underlying connection, and then dispatched to a worker
thread to generate the page. Once a server has started processing a request
there is no way to pause the request in a way that frees up the resources
(threads, database connections etc) in use. I think almost every use case
more complex than simple file serving has this issue, once a server has
started processing a request there is generally no way to suspend it and
free the resources.

So in your example if the user switches tabs and you stop sending window
updates for streams in use by the old browser tab, while sending new
requests for the new tab it is possible the server will be in a situation
where it is not prepared to allocate resources for the new requests until
the existing ones are complete, however these will never complete as the
browser has stopped sending window updates.

You could argue that a server should limit the max streams value to the
number of streams that it is prepared to allocate resources for, however
this greatly limits the utility of the priority mechanism, as it means that
servers will always handle requests on a first come first served basis. If
we set the maximum streams value to a higher amount than what we are
prepared to allocate resources for and queue requests then when a request
finishes we can pick the highest priority request from the queue to
allocate resources to (not to mention there is no round trip delay because
the request is queued).

Basically IMHO flow control should not be used to control priority, that is
what PRIORITY frames are for, and in general servers can only ever do
priority on a best effort approach anyway. If you try and use flow control
to enforce a strict priority mechanism you run a very real risk of
deadlocks.


>
> ==Flow control problem summary==
>
> With only a credit signal in the protocol, a receiver is going to have to
> allow generous credit in the WINDOW_UPDATEs so as not to hurt performance.
> But then, the receiver will not be able to quickly close down one stream
> (e.g. when the user's focus changes), because it cannot claw back the
> generous credit it gave, it can only stop giving out more.
>
> IOW: Between a rock and a hard place,... but don't tell them where the
> rock is.
>

For the reasons I outlined above I don't think this is actually a problem.
Also in terms of clawing back credit I thought that in general it was a bad
idea? The TCP RFC explicitly states that "shrinking the window" is strongly
discouraged, although I must admit I am not fully aware of the reasoning.

Stuart


>
> ==Towards a solution?==
>
> I think 'type-a' flow control (for intermediate buffer control) does not
> need to be at stream-granularity. Indeed, I suspect a proxy could control
> its app-layer buffering by controlling the receive window of the incoming
> TCP connection. Has anyone assessed whether this would be sufficient?
>
> I can understand the need for 'type-b' per-stream flow control (by the
> ultimate client endpoint). Perhaps it would be useful for the receiver to
> emit a new 'PAUSE_HINT' frame on a stream? Or perhaps updating per-stream
> PRIORITY would be sufficient? Either would minimise the response time to a
> half round trip. Whereas credit flow-control will be much more sluggish
> (see 'Flow control problem summary').
>
> Either approach would correctly propagate e2e. An intermediate node would
> naturally tend to prioritise incoming streams that fed into prioritised
> outgoing streams, so priority updates would tend to propagate from the
> ultimate receiver, through intermediate nodes, up to the ultimate sender.
>
> ==Flow control coverage==
>
> The draft exempts all TCP payload bytes from flow control except HTTP/2
> data frames. No rationale is given for this decision. The draft says it's
> important to manage per-stream memory, then it exempts all the frame types
> except data, even tho each byte of a non-data frame consumes no less memory
> than a byte of a data frame.
>
> What message does this put out? "Flow control is not important for one
> type of bytes with unlimited total size, but flow control is so important
> that it has to be mandatory for the other type of bytes."
>
> It is certainly critical that WINDOW_UPDATE messages are not covered by
> flow control, otherwise there would be a real risk of deadlock. It might be
> that there are dependencies on other frame types that would lead to a
> dependency loop and deadlock. It would be good to know what the rationale
> behind these rules was.
>

I think a lot of people had similar concerns. There is a discussion about
it here:
https://lists.w3.org/Archives/Public/ietf-http-wg/2014AprJun/0647.html


>
> ==Theory?==
>
> I am concerned that HTTP/2 flow control may have entered new theoretical
> territory, without suitable proof of safety. The only reassurance we have
> is one implementation of a flow control algorithm (SPDY), and the anecdotal
> non-evidence that no-one using SPDY has noticed a deadlock yet (however, is
> anyone monitoring for deadlocks?).
>
> Whereas SPDY has been an existence proof that an approach like http/2
> 'works', so far all the flow control algos have been pretty much identical
> (I think that's true?). I am concerned that the draft takes the InterWeb
> into uncharted waters, because it allows unconstrained diversity in flow
> control algos, which is an untested degree of freedom.
>
> The only constraints the draft sets are:
> * per-stream flow control is mandatory
> * the only protocol message for flow control algos to use is the
> WINDOW_UPDATE credit message, which cannot be negative
> * no constraints on flow control algorithms.
> * and all this must work within the outer flow control constraints of TCP.
>
> Some algos might use priority messages to make flow control assumptions.
> While other algos might associate PRI and WINDOW_UPDATE with different
> meanings. What confidence do we have that everyone's optimisation
> algorithms will interoperate? Do we know there will not be certain types of
> application where deadlock is likely?
>
> "   When using flow
>    control, the receiver MUST read from the TCP receive buffer in a
>    timely fashion.  Failure to do so could lead to a deadlock when
>    critical frames, such as WINDOW_UPDATE, are not read and acted upon.
> "
> I've been convinced (offlist) that deadlock will not occur as long as the
> app consumes data 'greedily' from TCP. That has since been articulated in
> the above normative text. But how sure can we be that every implementer's
> different interpretations of 'timely' will still prevent deadlock?
>
> Until a good autotuning algorithm for TCP receive window management was
> developed, good window management code was nearly non-existent. Managing
> hundreds of interdependent stream buffers is a much harder problem. But
> implementers are being allowed to just 'Go forth and innovate'. This might
> work if everyone copies available open source algo(s). But they might not,
> and they don't have to.
>
> This all seems like 'flying by the seat of the pants'.
>
> ==Mandatory Flow Control? ==
>
> "      3. [...] A sender
>        MUST respect flow control limits imposed by a receiver."
> This ought to be a 'SHOULD' because it is contradicted later - if settings
> change.
>
> "   6.  Flow control cannot be disabled."
> Also effectively contradicted half a page later:
> "   Deployments that do not require this capability can advertise a flow
>    control window of the maximum size (2^31-1), and by maintaining this
>    window by sending a WINDOW_UPDATE frame when any data is received.
>    This effectively disables flow control for that receiver."
>
> And contradicted in the definition of half closed (remote):
> "  half closed (remote):
>       [...] an endpoint is no longer
>       obligated to maintain a receiver flow control window.
> "
>
> And contradicted in 8.3. The CONNECT Method
> <https://tools.ietf.org/html/draft-ietf-httpbis-http2-17#section-8.3>,
> which says:
> "  Frame types other than DATA
>    or stream management frames (RST_STREAM, WINDOW_UPDATE, and PRIORITY)
>    MUST NOT be sent on a connected stream, and MUST be treated as a
>    stream error (Section 5.4.2) if received.
> "
>
> Why is flow control so important that it's mandatory, but so unimportant
> that you MUST NOT do it when using TLS e2e?
>
> Going back to the earlier quote about using the max window size, it seems
> perverse for the spec to require endpoints to go through the motions of
> flow control, even if they arrange for it to affect nothing, but to still
> require implementation complexity and bandwidth waste with a load of
> redundant WINDOW_UPDATE frames.
>
> HTTP is used on a wide range of devices, down to the very small and
> challenged. HTTP/2 might be desirable in such cases, because of the
> improved efficiency (e.g. header compression), but in many cases the stream
> model may not be complex enough to need stream flow control.
>
> So why not make flow control optional on the receiving side, but mandatory
> to implement on the sending side? Then an implementation could have no
> machinery for tuning window sizes, but it would respond correctly to those
> set by the other end, which requires much simpler code.
>
> If a receiving implemention chose not to do stream flow control, it could
> still control flow at the connection (stream 0) level, or at least at the
> TCP level.
>
>
> ==Inefficiency?==
>
>  5.2. Flow Control
> <https://tools.ietf.org/html/draft-ietf-httpbis-http2-16#section-5.2>
> "Flow control is used for both individual
>    streams and for the connection as a whole."
> Does this means that every WINDOW_UPDATE on a stream has to be accompanied
> by another WINDOW_UPDATE frame on stream zero? If so, this seems like 100%
> message redundancy. Surely I must  have misunderstood.
>
> ==Flow Control Requirements===
>
> I'm not convinced that clear understanding of flow control requirements
> has driven flow control design decisions.
>
> The draft states various needs for flow-control without giving me a feel
> of confidence that it has separated out the different cases, and chosen a
> protocol suitable for each. I tried to go back to the early draft on flow
> control requirements <
> http://tools.ietf.org/html/draft-montenegro-httpbis-http2-fc-principles-01
> >, and I was not impressed.
>
> I have quoted below the various sentences in the draft that state what
> flow control is believed to be for. Below that, I have attempted to
> crystalize out the different concepts, each of which I have tagged within
> the quotes.
>
> * 2. HTTP/2 Protocol Overview
> <https://tools.ietf.org/html/draft-ietf-httpbis-http2-16#section-2> says
>   "Flow control and prioritization ensure that it is possible to
> efficiently use multiplexed streams. [Y]
>    Flow control (Section 5.2) helps to ensure that only data that can be
> used by a receiver is transmitted. [X]"
> * 5.2. Flow Control
> <https://tools.ietf.org/html/draft-ietf-httpbis-http2-16#section-5.2>
> says:
>   "Using streams for multiplexing introduces contention over use of the
> TCP connection [X], resulting in blocked streams [Z]. A flow control scheme
> ensures that streams on the same connection do not destructively interfere
> with each other [Z]."
> * 5.2.2. Appropriate Use of Flow Control
> <https://tools.ietf.org/html/draft-ietf-httpbis-http2-16#section-5.2.2>
> "  Flow control is defined to protect endpoints that are operating under
>    resource constraints.  For example, a proxy needs to share memory
>    between many connections, and also might have a slow upstream
>    connection and a fast downstream one [Y].  Flow control addresses cases
>    where the receiver is unable to process data on one stream, yet wants
>    to continue to process other streams in the same connection [X]."
> "  Deployments with constrained resources (for example, memory) can
>    employ flow control to limit the amount of memory a peer can consume.
> [Y]
>
> Each requirement has been tagged as follows:
> [X] Notification of the receiver's changing utility for each stream
> [Y] Prioritisation of streams due to contention over the streaming
> capacity available to the whole connection.
> [Z] Ensuring one stream is not blocked by another.
>
> [Z] might be a variant of [Y], but [Z] sounds more binary, whereas [Y]
> sounds more like optimisation across a continuous spectrum.
>
>
> Regards
>
>
>
> Bob
>
>  ________________________________________________________________
> Bob Briscoe,                                                  BT
>