Subject: Negotiating Window Limits for Content Encodings

From: "W. Felix Handte" <[email-masked]>
Date: Wed, 4 Aug 2021 17:47:00 -0400

Hello all,

I hope you had a pleasant IETF 111.

TL;DR:

I want to specify an option along these lines:

  Accept-Encoding: zstd;w=18

Which in this case would mean that a client will accept a
zstd-compressed response, only if the window size is less than or equal
to 256KB (2 ** 18 bytes).

Background:

Back in the old days, decompression had well-known memory
requirements--the DEFLATE family of compressors are limited to a 32KB
window, so you were guaranteed that that (plus some other small
datastructures) was all the memory you'd need to maintain the
decompressor state for a response, no matter what came down the pipe.

One of the ways modern compressors improve on DEFLATE is by supporting
much larger windows. Brotli supports windows up to 16MB [0], though the
non-standard mode "Large Window Brotli" extends that to 1GB. Zstandard
theoretically supports 3.75TB windows [1], though in practice they're
limited to 2GB [2].

In the absence of any coordination mechanism, when a client indicates
they accept these encodings, a server is allowed to send back a payload
that would require a (very) large amount of memory to decode, which
might lead to resource exhaustion or a failure to decode the payload.
(E.g., the zstd library by default will reject a frame that requires
more than 128MB to decode, unless you explicitly allow larger windows [3].)

Currently the best resolution is mutual caution. The Zstandard RFC
provides interoperability guidance that suggests that recipients support
at least an 8 MB window and that senders avoid using a window larger
than 8 MB [1]. To my knowledge, Brotli doesn't provide any guidance.

It has become apparent that this is insufficient to the variety of
environments that HTTP is used in. For the transfer of very large
resources (esp. e.g. patch files), large windows can be crucial to good
compression performance. So we should allow very large windows when
useful. But for mobile or embedded or highly parallel applications,
we've seen that a compromise value like 8 MB is already too large, and
they may want to express limits <1MB.

Proposal:

I want to give endpoints an explicit coordination mechanism for
selecting compression window sizes. I think the most straightforward way
to do that is to add an option to the content-coding identifiers
advertised in an Accept-Encoding header, so that recipients can
advertise the largest window they are willing to handle for each
encoding. Senders would then be asked to either restrict themselves to
generating a response with a window no larger than the limit or just not
use that encoding.

Specifically, I'm thinking of that being the "w" option, which has a
positive integer value which is the log_2 of the maximum window the
client will accept for that encoding. (See the example at the beginning.)

I think that what I am proposing would be meaningfully better than the
current state of affairs. At the same time, I have several questions /
uncertainties for which your advice would be most welcome.

So before I put this in I-D language, I wanted to circulate the idea here.

Some of those Questions:

1. Is this worth making a generic mechanism and specifying it as an
option for any content-coding for which it's meaningful? Or should I
just restrict this to Zstd, which is where I'm aware of the most need?

2. Is this the best place to insert such a mechanism? Or should it be
its own header? (Would that be easier for caches to handle?)

3. Is it effective to tack on an option like this to existing
content-coding identifiers? Since the existing installed base does not
produce or recognize this option, that means it can only ever be best
effort for existing content-codings. A heavy-weight alternative would be
to introduce new identifiers that mandate handling this signal, but I
don't want to go down that path...

4. This proposal conflates window size with a decompression's overall
memory budget. For existing compressors, these two figures are very
close to one another, but in the future they might diverge. Would it be
better to specify a more holistic total memory limitation?

5. Is this sensible overall? Does anyone have strong feelings for or
against a mechanism like this?

Thanks,
Felix

[0] https://datatracker.ietf.org/doc/html/rfc7932#section-2
[1] https://datatracker.ietf.org/doc/html/rfc8878#section-3.1.1.1.2
[2] https://github.com/facebook/zstd/blob/v1.5.0/lib/zstd.h#L1114-L1116
[3] https://github.com/facebook/zstd/blob/v1.5.0/lib/zstd.h#L1137-L1141

---

From: Willy Tarreau <[email-masked]>
Date: Thu, 5 Aug 2021 04:38:42 +0200

Hello Felix,

> to 256KB (2 ** 18 bytes).
(...)

I personally think it's an excellent idea, though I'm really not sure
about its effectiveness because:
  - probably that some intermediaries or servers will not match
    "zstd;w=18" against any known token ;

  - some servers or intermediaries might simply ignore "w=18" for quite
    some time ;

  - other intermediaries might possibly transcode this to "zstd" before
    passing it on to the next hop, especially if they try to reorder
    fields following a different preference order ;

  - in any case the client will need to be prepared to reject the
    response if it detects that expectations are not met.

However, I like the idea because it would allow a client to send for
example:

   Accept-Encoding: zstd;w=18, gzip

And at least for servers that don't recognize the first one as a token,
the second one will naturally be used. And servers which understand it
could decide that they prefer some other algos below certain window
sizes if it costs less for them due to implementation constraints.

Also, it will be needed to state that the server should ignore too low
values so that it doesn't degrade a cache's contents (i.e. zstd;w=0).
And for caches it is probably less easy to define what is compatible
with what. Maybe you'll need to suggest the same thing in the response.

> just restrict this to Zstd, which is where I'm aware of the most need?

Given what you said about Brotli, it seems that it should be generic,
though it's not certain that such an argument easily applies to all
algorithms.

> its own header? (Would that be easier for caches to handle?)

I think that having it in a different header field would make it difficult
to deal with lists (e.g. "zstd;w=18,gzip" hardly transcodes to multiple
headers).

> don't want to go down that path...

There's the risk that everyone needs a different value :-/  However it
could still be a valid alternative to imagine 3 profiles for each algo,
"low-memory" for inline transcoding (e.g. less than 64k), "mobile" (e.g.
less than 1 MB) and the default, unlimited. But even with this I'm pretty
sure that everyone will have a different opinion.

> better to specify a more holistic total memory limitation?

As long as the relation between the two is understood for each algo,
it's the client's responsibility to advertise the correct value based
on its capabilities. An alternative could be to pass an argument "l"
for "level" instead of window, which would correspond to the max
compression level for the algo, given that many algos naturally
support such an argument.

> against a mechanism like this?

I do like it but am unsure about the best path to make it seamless to
integrate. I wouldn't be surprised that you end up proposing that
clients send something like "zstd;w=18, zstd" to be sure that it's at
least recognized. But I think it's worth studying existing deployments
to figure the best path forward.

Regards,
Willy

---

From: "Martin Thomson" <[email-masked]>
Date: Thu, 05 Aug 2021 14:18:10 +1000

> though it's not certain that such an argument easily applies to all

I would avoid making this truly generic, but there is value in establishing a convention.  If brotli wants to use the same concept, but set w=18 to mean something else, that's probably OK.  What the convention will mean is that you can build software that knows that there is a w parameter and that Accept-Encoding: foo;w=n is an acceptable match for Content-Encoding: foo;w=m for any m <= n.  That is generally applicable logic, even if it has to be applied on a per-format basis.

(It can't be truly generic as identity;w=3 means nothing, there are other content-codings for which w would be meaningless, and we haven't defined gzip;w=4.)

---

From: Julian Reschke <[email-masked]>
Date: Thu, 5 Aug 2021 16:02:45 +0200

Am 04.08.2021 um 23:47 schrieb W. Felix Handte:
> ...

That syntax is not allowed in RFC 7231; in "Accept-Encoding", the
content codings can have a weight, but no further parameters.

Best regards, Julian

---

From: Willy Tarreau <[email-masked]>
Date: Thu, 5 Aug 2021 16:12:59 +0200

Hi Martin,

On Thu, Aug 05, 2021 at 02:18:10PM +1000, Martin Thomson wrote:
> I would avoid making this truly generic, but there is value in establishing a
> convention.  If brotli wants to use the same concept, but set w=18 to mean
> something else, that's probably OK.  What the convention will mean is that
> you can build software that knows that there is a w parameter and that
> Accept-Encoding: foo;w=n is an acceptable match for Content-Encoding: foo;w=m
> for any m <= n.  That is generally applicable logic, even if it has to be
> applied on a per-format basis.
> 
> (It can't be truly generic as identity;w=3 means nothing, there are other
> content-codings for which w would be meaningless, and we haven't defined
> gzip;w=4.)

I agree with your points, which is also why I suggested that a level could
be more generic. In addition, encoding doesn't necessarily mean compression,
we could for example imagine encrypting the document with a known key, and
then probably that the key ID could be passed the same way. I know it's a
bit far-fetched, and we ought to be careful not to start to reinvent the
wheel, but that seems to indicate that the argument is probably something
specific to the token itself, though the format ought to be generic.

Willy

---

From: "W. Felix Handte" <[email-masked]>
Date: Thu, 5 Aug 2021 13:32:37 -0400

> content codings can have a weight, but no further parameters.
Ah, well that is hard news. Thank you for pointing this out! I totally
missed that "Accept-Encoding" is not a generic list of parameterized tokens.

I wonder whether that restriction makes sense, or if we should relax it.
Too bad the ship has already sailed on draft-ietf-httpbis-semantics! I
have opened an issue on the http-core GitHub [0] to discuss that
question. That feels like a more appropriate place to keep track of that
topic, given that it is potentially a very long term one while we wait
for a new rev of the HTTP core. Although maybe it will be a very short
one, if it gets shot down immediately. :)

Thanks,
Felix

[0] https://github.com/httpwg/http-core/issues/932

---

From: "Roy T. Fielding" <[email-masked]>
Date: Thu, 5 Aug 2021 11:08:31 -0700

> On Aug 4, 2021, at 2:47 PM, W. Felix Handte <[email-masked]> wrote:
> 
> Hello all,
> 

Hi Felix,

Accept-Encoding doesn't work that way because it results in a proliferation
of encodings and unique request field values, which has an extremely negative
impact on shared caching and Vary. That's why we don't do dynamic window
tweaks with Accept-Encoding.

If you happen to use Transfer-Encoding instead, those problems wouldn't apply
(but then you have another set of problems regarding implementations).

In general, when you can expect different clients to have different/unique
resource limitations in the processing of representations, what you want to do
is provide different sites (or different path hierarchies) for those resources
such that all of the similar clients operate within the same resource space and
make effective use of caching all the way down the delivery chain.

Request fields are the wrong place to negotiate window sizes. That should be
done within the client itself, prior to making a request, with code that takes
a list of available window sizes, matches that to the user agent's desired size,
and then uses something like a URI template to construct the right resource
target to retrieve. This can be done with links and media types, without
changing HTTP, or even by the traditional mechanism of informing the user
via hypertext and having them choose which link to select. It can be
entirely automated if the patterns are standardized.

Another workaround is to define different coding names for different window
sizes. That at least narrows the proliferation of choice to a common set of
maximum window sizes, rather than an arbitrary integer.  For example, register
zstd-tiny, zstd, zstd-big, and zstd-huge (or zstd-mb, zstd-gb, zstd-tb).
That better aligns with how implementations work in practice -- picking
a fixed max rather than arbitrarily changing it on the fly.

Cheers,

....Roy