Subject: Re: [quicwg/base-drafts] HTTP header compression: static table fit for QUIC (#904)

From: Mike Bishop <[email-masked]>
Date: Wed, 07 Mar 2018 18:54:52 +0000 (UTC)

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:

```
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-language: en-us,en;q=0.9
accept: image/webp,image/apng,image/*,*/*;q=0.8
accept: */*
date:  
referer:  
content-type: image/jpeg
content-type: image/png
content-type: image/gif
server: nginx
server: apache
content-length
cache-control
last-modified
host:  
connection: keep-alive
expires:  
accept-ranges: bytes
connection: keep-alive
cookie:  
etag:  
status: 200
vary: accept-encoding
content-encoding: gzip
content-encoding: br
set-cookie
access-control-allow-origin: *
x-content-type-options: nosniff
x-xss-protection: 1; mode=block
x-xss-protection: 0
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"
pragma: no-cache
pragma: public
age:  
timing-allow-origin: *
keep-alive
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
location:  
via: 1.1 varnish
strict-transport-security: max-age=31536000
strict-transport-security: max-age=10886400; includesubdomains; preload
origin: https://www.facebook.com
cf-ray:  
transfer-encoding: chunked
x-frame-options: sameorigin
x-frame-options: deny
cf-cache-status: hit
access-control-allow-credentials: TRUE
upgrade-insecure-requests: 1
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/"
content-disposition: attachment; filename="f.txt"
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-methods: options
access-control-allow-methods: get
access-control-allow-methods: get, post, options
access-control-expose-headers: content-length
access-control-expose-headers: x-fb-debug, x-loader-length
access-control-expose-headers: x-frontend
x-amz-cf-id
x-fb-debug
access-control-allow-headers: content-type
x-served-by
link: <https://fonts.gstatic.com>; rel=preconnect; crossorigin
content-type: application/x-www-form-urlencoded
content-type: text/plain;charset=utf-8
content-type: text/plain
content-type: application/json
content-type: application/x-www-form-urlencoded; charset=utf-8
content-length: 0
x-requested-with: xmlhttprequest
cache-control: max-age=0
cache-control: no-cache
intervention: <https://www.chromestatus.com/feature/5718547946799104>;   level="warning"
x-youtube-client-name: 56
x-youtube-client-version: 20180131
x-youtube-client-version: 20180208
x-youtube-client-version: 20180206
range: bytes=0-
access-control-request-method: post
access-control-request-method: get
access-control-request-headers: content-type
if-modified-since
pragma: no-cache
purpose: prefetch
if-none-match
if-range:  
pe-token:  
x-goog-visitor-id
upgrade: websocket
sec-websocket-version: 13
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.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/904#issuecomment-371244272

---

From: MikkelFJ <[email-masked]>
Date: Wed, 07 Mar 2018 19:09:09 +0000 (UTC)

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/

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/904#issuecomment-371249481

---

From: Mike Bishop <[email-masked]>
Date: Wed, 07 Mar 2018 19:27:33 +0000 (UTC)

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.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/904#issuecomment-371252153

---

From: Dmitri Tikhonov <[email-masked]>
Date: Wed, 07 Mar 2018 19:37:18 +0000 (UTC)

> 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

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/904#issuecomment-371258281

---

From: Lucas Pardue <[email-masked]>
Date: Wed, 07 Mar 2018 20:01:20 +0000 (UTC)

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?

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/904#issuecomment-371265650

---

From: Mike Bishop <[email-masked]>
Date: Wed, 07 Mar 2018 20:24:10 +0000 (UTC)

#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.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/904#issuecomment-371272500

---

From: Martin Thomson <[email-masked]>
Date: Wed, 07 Mar 2018 21:25:26 +0000 (UTC)

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.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/904#issuecomment-371290080

---

From: Lucas Pardue <[email-masked]>
Date: Wed, 07 Mar 2018 13:51:51 -0800

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.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/904#issuecomment-371297856

---

From: Mike Bishop <[email-masked]>
Date: Wed, 07 Mar 2018 22:03:21 +0000 (UTC)

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](https://bigquery.cloud.google.com/savedquery/802972753671:939e901b416848e5a68db177f65940e1)
- [Summarize response headers](https://bigquery.cloud.google.com/savedquery/802972753671:81903f5fde1f466f89224f3f7146b176)
- [Assemble request table](https://bigquery.cloud.google.com/savedquery/802972753671:82c5f0e83867493294d77d422a401acb)
- [Assemble response table](https://bigquery.cloud.google.com/savedquery/802972753671:0af65e3683c04a7d97d0901672d099d6)
- [Fold tables together](https://bigquery.cloud.google.com/savedquery/802972753671:5f5721ba967f4bd0af419585fadb07ce)

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.  ;-)

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/issues/904#issuecomment-371300973