HTTP header compression: static table fit for QUIC

[LPardue]

The HTTP header compression mechanism is still TBC but as I understand it, the proposals keep the same HPACK static table. This was formed from the "most frequent header fields used by popular web sites", and I wonder if that is still the case for today's web. For example, perhaps we'll see more usage of alt-svc in HTTP/QUIC, in order to keep the session active.

One benefit to keeping the static table would be to allow implementations to reuse of their object representation of the table, however I don't know how realistic that would be.

[ianswett]

Given it looks like the header compression will share little to no code with H2, I think this is worth considering.

[LPardue]

The other question(s) I meant to pose was: given that H2 has now seen deployment experience, is there any telemetry on how the static and dynamic tables have been used? If so, could this be used to identify 'hot' items that make a better case for inclusion in the static table over other entries?

[martinthomson]

One of the pieces of feedback we've had is that there are some entries that don't have assigned values. That would be a relatively easy thing to fix. Also Accept-Encoding: br,gzip is now a thing apparently.

[MikeBishop]

One other consideration, depending on how the proposals line up. Recall that one of the other HTTP/2 compression proposals had a much larger static table, containing nearly every registered status code, etc. The static table occupies the easiest-to-address range in HTTP/2, which means it needs to be small. The latest version of QPACK addresses them independently, which would enable a large static table without hurting the dynamic table performance.

[dtikhonov]

I think the largest benefit to keeping the HPACK static table is interoperability between HPACK and the new compression mechanism. If this property is deemed unnecessary, the static table can be updated to use the latest common headers.

In my mind, this is a good feature to have and QMIN is designed to be interoperable with HPACK given a few conditions.

As for telemetry, I think we have to guess -- unless some big companies are willing to enable stats gathering and sharing them -- as more and more HTTP connections are secure.

[MikeBishop]

That's how the static table and Huffman table for HPACK were generated -- statistics of common values and character frequency in Chrome. Obviously, some things have shifted since then.

[LPardue]

I was also wondering if something like a HTTP archive query might be able to bring up some useful data.

seperately, this issue is obviously not critical or blocking but if is a nice opportunity. I appreciate there is probably lead time in generating appropriate data and therefore wonder if it might help to loop the relevant people (browser affilated or other) into this issue, if they already aren't. Not sure exactly the right people though.

[LPardue]

Wishful thinking hat on: I'd love to see a means for per-session static table ( i.e. an immutable table negotiated on start up). The flexibility could vary from completely user-defined, to pre-defined tables that exist in a spec (e.g. "legacy HPACK" and "future compressor").

[dtikhonov]

Wishful thinking hat on: I'd love to see a means for per-session static table ( i.e. an immutable table negotiated on start up).

@afrind presented an almost exactly the same idea to the Compression Design Team.

[afrind]

The basic idea was to allow the encoder to include compression instructions in the SETTINGS frame, and require the SETTINGS frame to be processed before any request streams (it already must be processed before responses are sent). If the HoL blocking seems onerous,we could add a transport parameter to the handshake 'MUST_PROCESS_SETTINGS' telling the peer if HoL blocking is required.

[LPardue]

I was also wondering if something like a HTTP archive query might be able to bring up some useful data.

So I had a look at the archive and hit a learning curve. A plea for help got me a great answer from @paulcalvano - https://discuss.httparchive.org/t/is-hpack-static-table-fit-for-todays-web/1177/5

The results are calculated over a subset of the available data. I'd like to do some further analysis.

Interestingly, in spite of Deprecating the "X-" Prefix and Similar Constructs in Application Protocols, there are lots of instance of "X-" prefix.

[mikkelfj]

How about a static huffman table of complete words commonly seen in header values? Including Mon, Tue, gzip, ';', ...

[mikkelfj]

It could be created with a DFA such that looking up the next char would either give a final value, or ask for one more making the encoding. Possibly using something like: http://iis.ipipan.waw.pl/2008/proceedings/iis08-22.pdf But the actual encoder/decoder would just simple lookups.

https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton

[mikkelfj]

Given a standard DFA algorithm it ought to be possible negotiate a list of words. Such a list could be identified by a SHA256 hash. This would allow total freedom of dictionary choice as long as both parties agree. The DFA encoding would use 1 bit for each step through the DFA resulting in a bit pattern similar to huffman.

This can be combined with basic huffman encoding. A special code, such as a 1-bit prefix, activates the word DFA. If the huffman table also has code for termination then the length need not be carried.

A static dictionary could also be negotiated via a SHA256 of the sorted list of strings.

[LPardue]

First off, this ticket risks exposing or deep diving into work-in-progress of the compression design team. I'd like to avoid doing that too early, so please someone weigh in if we think it might be better to hold off.

@afrind I don't quite follow from your brief summary. What is an appropriate moniker for the table resulting from compression encoding negoition? Does your idea apply symmetrically or could there be different header tables contexts for client and server?

The main use case I have is the unidirectional HTTP case, where SETTINGS cannot be exchanged. I've used Alt-Svc parameters to articulate most connection-level settings and wonder if such proposed compression instructions could also be articulated as an Alt-Svc parameter.

[afrind]

@LPardue : Sorry for the confusion, I will write up the idea formally. The goal I had in mind was seeding the dynamic table once at the beginning of the connection.

[LPardue]

ok cool, I've had some half-baked ideas on that topic. Look forward to something a bit more tangible.

Is the resulting table locked, or open to modification through the course of a session?

[MikeBishop]

The QPACK editor's copy incorporates Alan's idea along with a few others. Basically, it's just a series of updates that are guaranteed to have been processed prior to any of your requests, so you can reference them without risk of blocking. If the decompressor supports blocking anyway, it may be negligible, but it's a simpler model to get good initial performance even if the decompressor won't support blocking in the general case.

As to the design team, my hope is that we bring a starting point for header compression back to the working group by Melbourne, and the working group can iterate further from there. Since the concept of a static table is common to most of the proposals at this point, I'd prefer to leave refining the contents of that table to the "iteration" stage. The discussion can happen in parallel if you want, but don't expect to see action on that until we have a single scheme that we're all moving forward with.

[LPardue]

SGTM. I agree that HPACK static table is good enough for now, changes can be iterative later on. However, to go back to your earlier point, QPACK was suggested to offer the possibility of a much larger static table. If other proposals do not offer such a possibility it might be useful as a comparison point.

[LPardue]

@MikeBishop, post-Melbourne and the decision to adopt QCRAM, is this something to look into now? Or would it be better to keep it parked?

[MikeBishop]

Assuming the draft is formally adopted (which requires the mailing list), I suspect this falls into the "bring data and demonstrate it's better" bucket.

If someone can come up with a draft static table and demonstrate appreciable improvements in compression performance or reductions in HOLB to justify the departure from shared code with HPACK, I don't see why we wouldn't consider it. (Assuming that either the gains were dramatic enough to justify time investment or the time requirements to agree and merge it were minimal.)

[MikeBishop]

I did some queries over the HTTP Archive data. My basic algorithm was to include any values that made up more than 10% of instances of that header, or include a name only if no value made up more than 10% of occurrences. I used different cutoffs for server and client based on the point at which it seemed to be going into the weeds, but that's entirely a judgement call.

That algorithm came out with this as the resulting static table:

content-type: application/x-www-form-urlencoded
content-type: image/jpeg
content-type: text/plain;charset=utf-8
content-type: image/png
content-type: text/plain
content-type: application/json
content-type: application/x-www-form-urlencoded; charset=utf-8
content-type: image/gif
user-agent: mozilla/5.0 (x11; linux x86_64) applewebkit/537.36 (khtml, like gecko) chrome/64.0.3282.140 safari/537.36 ptst/180204.000209
user-agent: mozilla/5.0 (x11; linux x86_64) applewebkit/537.36 (khtml, like gecko) chrome/64.0.3282.140 safari/537.36 ptst/180202.170209
accept-encoding: gzip, deflate, br
accept-encoding: gzip, deflate
accept: image/webp,image/apng,image/*,*/*;q=0.8
accept: */*
server: nginx
server: apache
connection: keep-alive
connection: keep-alive
accept-language: en-us,en;q=0.9
date: 
referer: 
content-length: 0
content-length: 
cache-control: max-age=0
cache-control: no-cache
cache-control: 
last-modified: 
content-encoding: gzip
content-encoding: br
host: 
expires: 
accept-ranges: bytes
cookie: 
etag: 
x-xss-protection: 1; mode=block
x-xss-protection: 0
status: 200
vary: accept-encoding
pragma: no-cache
pragma: no-cache
pragma: public
set-cookie: 
access-control-allow-origin: *
x-content-type-options: nosniff
x-cache: hit
x-cache: hit from cloudfront
alt-svc: hq=":443"; ma=2592000; quic=51303431; quic=51303339; quic=51303338; quic=51303337; quic=51303335,quic=":443"; ma=2592000; v="41,39,38,37,35"
alt-svc: hq="googleads.g.doubleclick.net:443"; ma=2592000; quic=51303431; quic=51303339; quic=51303338; quic=51303337; quic=51303335,quic="googleads.g.doubleclick.net:443"; ma=2592000; v="41,39,38,37,35",hq=":443"; ma=2592000; quic=51303431; quic=51303339; quic=51303338; quic=51303337; quic=51303335,quic=":443"; ma=2592000; v="41,39,38,37,35"
x-powered-by: asp.net
x-powered-by: plesklin
p3p: policyref="https://googleads.g.doubleclick.net/pagead/gcn_p3p_.xml", cp="cura adma deva taio psao psdo our ind uni pur int dem sta pre com nav otc noi dsp cor"
strict-transport-security: max-age=31536000
strict-transport-security: max-age=10886400; includesubdomains; preload
age: 
x-frame-options: sameorigin
x-frame-options: deny
timing-allow-origin: *
keep-alive: 
expect-ct: max-age=604800, report-uri="https://report-uri.cloudflare.com/cdn-cgi/beacon/expect-ct"
expect-ct: max-age=10, report-uri="http://reports.fb.com/expectct/"
access-control-allow-methods: options
access-control-allow-methods: get
access-control-allow-methods: get, post, options
location: 
access-control-expose-headers: content-length
access-control-expose-headers: x-fb-debug, x-loader-length
access-control-expose-headers: x-frontend
via: 1.1 varnish
origin: https://www.facebook.com
cf-ray: 
transfer-encoding: chunked
cf-cache-status: hit
content-security-policy: default-src * data: blob:;script-src *.facebook.com *.fbcdn.net *.facebook.net *.google-analytics.com *.virtualearth.net *.google.com 127.0.0.1:* *.spotilocal.com:* 'unsafe-inline' 'unsafe-eval' fbstatic-a.akamaihd.net fbcdn-static-b-a.akamaihd.net *.atlassolutions.com blob: data: 'self';style-src data: blob: 'unsafe-inline' *;connect-src *.facebook.com facebook.com *.fbcdn.net *.facebook.net *.spotilocal.com:* *.akamaihd.net wss://*.facebook.com:* https://fb.scanandcleanlocal.com:* *.atlassolutions.com attachment.fbsbx.com ws://localhost:* blob: *.cdninstagram.com 'self' chrome-extension://boadgeojelhgndaghljhdicfkmllpafd chrome-extension://dliochdbjfkdbacpmhlcpmleaejidimm;
content-security-policy: default-src * data: blob:;script-src *.facebook.com *.fbcdn.net *.facebook.net *.google-analytics.com *.virtualearth.net *.google.com 127.0.0.1:* *.spotilocal.com:* 'unsafe-inline' 'unsafe-eval' fbstatic-a.akamaihd.net fbcdn-static-b-a.akamaihd.net *.atlassolutions.com blob: data: 'self';style-src data: blob: 'unsafe-inline' *;connect-src *.facebook.com facebook.com *.fbcdn.net *.facebook.net *.spotilocal.com:* *.akamaihd.net wss://*.facebook.com:* https://fb.scanandcleanlocal.com:* *.atlassolutions.com attachment.fbsbx.com ws://localhost:* blob: *.cdninstagram.com 'self';
access-control-allow-credentials: TRUE
upgrade-insecure-requests: 1
content-disposition: attachment; filename="f.txt"
x-amz-cf-id: 
x-fb-debug: 
access-control-allow-headers: content-type
x-served-by: 
link: <https://fonts.gstatic.com>; rel=preconnect; crossorigin
x-requested-with: xmlhttprequest
x-youtube-client-version: 20180131
x-youtube-client-version: 20180208
x-youtube-client-version: 20180206
intervention: <https://www.chromestatus.com/feature/5718547946799104>; level="warning"
access-control-request-method: post
access-control-request-method: get
x-youtube-client-name: 56
range: bytes=0-
access-control-request-headers: content-type
if-modified-since: 
purpose: prefetch
if-none-match: 
if-range: 
pe-token: 
x-goog-visitor-id: 
sec-websocket-version: 13
upgrade: websocket
sec-websocket-extensions: permessage-deflate; client_max_window_bits
sec-websocket-key: 
dpr: 1
viewport-width: 1024
x-newrelic-id: 
x-sumo-auth: 
authorization: 
x-csrf-token: 
client-id: jzkbprff40iqj646a697cyrvl0zt2m6
client-id: b31o4btkqth5bzbvr9ub2ovr79umhh
service-worker: script

Obviously, there are some notable caveats, given the source of the data:

• This is entirely successful requests, IIUC, so headers that occur on failures aren't represented
  • This is Chrome, so browser-specific headers will be biased
  • This is a point-in-time and some of these we won't wish to memorialize (e.g. the Alt-Svc entries that include Google versions). In particular, I drew on runs from a single day for this analysis.
  • Pseudo-headers aren't visible in this archive (which is why the prevalence of a "Status: 200" header surprises me)

Still, I find it a useful initial result. Happy to share the queries that led to this, if anyone wants to replicate. I used a modified version of the query in the linked thread to summarize frequencies into my own (smaller) table, then ran queries against that smaller table to produce this list.

[mikkelfj]

You might also want to add zstd compression even if it isn't very popular yet - in the same class as br (brotli):

https://datatracker.ietf.org/doc/draft-kucherawy-dispatch-zstd/

[MikeBishop]

A suggestion from @martinflack: Different use-cases (IoT, video, etc.) might have different sets of headers that make more sense than those we're observing on general web traffic. Rather than fixing one static table in stone forever, allocate one instruction to switching static tables. Start with the one in the spec, and as/if future static tables are defined in the future, use a setting to announce which others are supported and use the reserved instruction on the control stream to announce "switching to static table 4 now".

This might ought to be a separate issue, but since this issue is on improving the static table generally, I'll mention it here as well.

[dtikhonov]

Start with the one in the spec, and as/if future static tables are defined in the future, use a setting to announce which others are supported and use the reserved instruction on the control stream to announce "switching to static table 4 now".

+1

[LPardue]

Great analysis @MikeBishop, thanks!

It was mentioned earlier that there is a could be a possibility for the static table to be larger. How did that turn out?

I strongly support switchable tables. Would there be a need to define a "common structure" to aid machine-driven definition and validation? Or is the current textual format good enough?

[MikeBishop]

1141 uses a bit to separate static/dynamic references rather than indices. If that PR is adopted, the static table can grow without impacting the performance of the dynamic table. Note that the earlier the entry is, the more likely an instruction referencing it is to fit in one byte, which is why I sorted by frequency of the header. The two thresholds that matter in the current rendition of #1141 are the first ~16 and the first ~64, though further bit tweaks could move those to other powers of 2.

[martinthomson]

I'm less keen about switching tables in and out, but moving to a new table would be good.

On the list that is shown, it definitely needs to be scrubbed for bias. The User-Agent values are clearly common and so the value can simply be removed. Origin: https://www.facebook.com has got to go as well, and the same goes for some of the clearly biased x- header fields.

Not sure what I think of client hints and some of the other client-specific biases, but I see no reason not to include standardized header fields.

That said, I would not object to having this as the basis of a new table, especially with #1141. I assume that your methods are reproducible.

It's a shame that you don't have pseudo-header fields in there. That might need some logging if you care about frequency analysis.

[LPardue]

I'm not too familiar with the HTTP archive data set, does it contain "request line" and "response line"?

My thinking is that you could infer the pseudo header frequencies by breaking down other structures that are captured.

[MikeBishop]

Yes, they should be fully reproducible -- worked in a couple of stages, but happy to share the queries I used to generate each.

• Summarize request headers
• Summarize response headers
• Assemble request table
• Assemble response table
• Fold tables together

It does separately capture method, status, etc. which could be used to generate header entries other than those listed in the archive. The main reason to do summarize in a different stage is that BigQuery charges by size of data accessed, so if you can run summarize once and then run various queries against the summary, it's far cheaper and faster to execute. I burned through the free tier in the first day, but thankfully they have a $300 new user credit, too. ;-)

[MikeBishop]

Based on those queries, tweaking the parameters, and scrubbing for obvious vendor bias, I've got a first draft static table here. I've also manually added pseudo-headers. Take a look -- feedback welcome.

[LPardue]

58	:scheme	http

Is that really appropriate for QPACK? Is this (hypothetically or not) a result of a client being Alt-Svc'd up from plaintext HTTP to HTTP/QUIC?

[mikkelfj]

While still young, zstd is likely to be important over time

https://tools.ietf.org/html/draft-kucherawy-dispatch-zstd-01#section-3

content-encoding: zstd application/zstd

[LPardue]

0	content-type	application/x-www-form-urlencoded

Given that GET is more popular than POST, it seems odd that this content-type value comes out top.

[LPardue]

Or in other words, do we optimise for requests or responses? The proposed table seems to treat both equally fairly.

[mikkelfj]

These are used in quite heavy traffic

x-forwarded-for x-forwarded-ip x-forwarded-port x-forwarded-proto ?

https://docs.aws.amazon.com/elasticloadbalancing/latest/classic/x-forwarded-headers.html https://stackoverflow.com/questions/19366090/what-is-the-difference-between-x-forwarded-for-and-x-forwarded-ip

[MikeBishop]

@LPardue, yes, that's the idea. RFC 8164 and all. And you're right -- there are some odd ducks in there, some removed and some not.

• 53% of Content-Disposition headers give a filename of "f.txt"
• 17% of Content-Length headers are 0; another 5% are 531
• The 6th most common ACAH header asks to allow "x-customheader," which I'm fairly sure is an example someone copied without customizing

@mikkelfj, given that the other application/* compressed types aren't frequent enough to show up in the query, I'd probably skip that content-type entry regardless. We could add some things still in draft, like that content-encoding, if there's enough interest. The addition of things that are used on the proxy side would be useful, since Internet Archive doesn't have visibility into that.

[mikkelfj]

X-forwarded-* isn't really standard, and there is an effort to standardize, but I'm sure if it is actually being used - and if it is, X- is probably still there just to not break things.

That said, any gateway towards QUIC has the chance of remapping such headers, so QUIC could take a position here.

e.g. X-Forward-For -> Forwarded

https://tools.ietf.org/html/rfc7239 https://tools.ietf.org/html/rfc7239#section-7.4

[LPardue]

This verges on bikeshed commentary. How much "space" is there for this table. The indexing stops at 121 for the reasons you describe, what is the upper limit? Could QPACK static table be extended in future if there is a strong demand? (which raises the other point of how closely coupled is QPACK to v1 of QUIC, doh).

[MikeBishop]

One of the reasons for #1141 was that it allowed this table to be "larger" without hurting the dynamic table. What constitutes "larger" is flexible, though. Basically, as large as implementations can tolerate.

There's discussion up-thread about defining a way to change static tables. I haven't come up with a design for that which doesn't feel painful, though.

[LPardue]

There's discussion up-thread about defining a way to change static tables. I haven't come up with a design for that which doesn't feel painful, though.

I meant more something like a formal extension process, similar to Frame types or Status codes. An author could propose new entries be appended to the static table, an "expert" decides if this should become a formal entry. Endpoints could exchange the highest index of static entry they would like to use for any given connection. This value indicates that the endpoint supports all entries up to and including the highest index.

While HPACK was noble in its statement of not being extendable, the barrier to HPACK2 is high. Instead we have QPACK :)

[mikkelfj]

There's discussion up-thread about defining a way to change static tables. I haven't come up with a design for that which doesn't feel painful, though.

Not sure it is a good idea, but there could be a default static table. A DNS entry could list alternatives from a known short-list, and the client could identify which was chosen.

[MikeBishop]

DNS makes me nervous, simply because it's not guaranteed to be fresh. You need something that can be confirmed directly with the peer at the time of the connection. A single continuously-growing table is hard because in a few years, in some application space, someone's going to find the low end of the table totally useless and be forced to support it to get the high end.

The best sketch I've got right now is to capitalize on the fact that there are two encoder-decoder pairs. So each endpoint publishes a list, in preference order, of the static tables it supports. Each encoder will use the most preferred item from its list which also appears somewhere on the decoder's list. They might well end up using different static tables in the opposite directions, but that's okay; each peer can choose the table that best suits the headers it plans to send. If we went with such a design, it would probably make sense to separate out a client table and a server table.

However, if it's going to be in SETTINGS, that adds a new limitation that the client can't send requests in 1-RTT until it has seen the server's (hopefully 0.5-RTT) SETTINGS frame, a requirement that doesn't currently exist. (Or we permit changing tables mid-connection, which has serious synchronization issues.) If we want to guarantee that it has been seen, then it would have to be a transport parameter, but that then gets into cross-layer settings and that's ugly.

[kazuho]

Regarding static table selection, I'd prefer using what will be defined in #1068 rather than trying to invent our own wheel.

Having a concrete use-case might also have a positive effect in driving the design discussion on #1068 as well.

[LPardue]

A single continuously-growing table is hard because in a few years, in some application space, someone's going to find the low end of the table totally useless and be forced to support it to get the high end.

At that point, nulke it from orbit and make a QPACK2 or whatever from scratch. My intention was to permit modest growth of "QPACK for general purpose HTTP on the Web".

Saying that, for all the problems that "pluggable" static tables might have, I like your proposal @MikeBishop, and it would obviate my slow-growth extension model.

[MikeBishop]

@kazuho, that doesn't make sense to me, as this isn't a QUIC extension. It would change nothing about the transport. I'd be perfectly happy mimicking that in an HTTP setting, but I'd really like to stay away from shoving application-layer state into the transport parameters.

[kazuho]

@MikeBishop I would argue that QUIC should provide a way for application protocols (e.g., HTTP) to negotiate their parameters.

And I do not think that the negotiation mechanism for a transport extension and an application protocol extension needs to be different. There could be certain properties specific to a transport extension from QUIC's viewpoint (e.g., frame type mappings being negotiated), but the general requirements (e.g., the need to finish negotiation before sending first application data, the need to exchange a extension ID and optionally some parameters) will be the same.

[MikeBishop]

That's certainly a possible design, but not what we've currently defined for HTTP/QUIC; we've followed the HTTP/2 path instead. One reason we haven't gone that way so far is that, during the handshake, you're also offering a list of protocols in ALPN in parallel with TPs. That means anything which lives in TP needs to be sent for each of the protocols you're offering the server to select from. (Imagine a future in which you support multiple HQ versions.) Also, since client's TP are only under handshake keys, there can't be any privacy concerns around disclosing the client's parameters.

Neither is a killer, but certainly a pain, and a reason I prefer to keep other options on the table.

[kazuho]

I think the way HTTP/2 negotiates (or rather, unilaterally sends the configuration) is pretty cool. OTOH, as you have described, the issue with static table negotiation is that it needs to be negotiated rather than just sending the configuration to the peer.

I can understand the hesitation to running ALPN and protocol-specific negotiation at the same time.

However, I might argue that running all things parallel (for less connection establishment latency) is the spirit of QUIC. Transport negotiation, TLS handshake, 0-RTT, they are all done in parallel. Therefore, I would estimate that people would want to do the same for negotiating the parameters of the application layer protocols. I see static table negotiation being one of them.

Just my two cents.

[MikeBishop]

I'm going to propose we divide this into two issues. It seems like we have agreement to replace QPACK's static table; I've received a bit of feedback on the wiki page that hasn't been incorporated yet, but will probably turn that into a PR soon.

If there's appetite to put in a table negotiation mechanism, let's do that separately. I've opened #1343 to track that.