5 ms·

Chrome feature: Compression dictionary transport with Shared Brotli

58 points by judiisis 3y ago

tyingq 3y ago
Makes me wonder if rsync-style differential download would be more generally useful than "shared dictionary for shared brotli". The implementation is letting you reference a previously downloaded artifact using a hash value, which is the same starting point.
- lifthrasiir 3y ago
  I think it solves a different problem. One of Brotli's strengths was a built-in dictionary tuned for the web contents, which makes it especially suitable for short data with no known priors. The compressed dictionary transport is same but tuned for each website. In comparison, rsync algorithm would make sense only when the data is long enough (say, more than 1 MB), in which case a custom dictionary wouldn't help much because the compressor already has a lot of patterns to working with. Ideally both can be implemented, where the HTTP Range request can be updated to support rsync-like algorithms.
- philsnow 3y ago
  Are you referring to courgette (which the Chrome team uses to make shipping patches/updates take far fewer bytes than previously)? https://www.chromium.org/developers/design-documents/software-updates-courgette/ https://www.chromium.org/developers/design-documents/softwar...
  - deleted 3y ago
    [deleted]
  - tyingq 3y ago
    Yes, but exposed to everyone. This proposal settles on headers that get passed back and forth that surely some servers would adopt. Headers that established "previously downloaded thing" with a hash. It feels like the process could be exactly the same at the start, but end instead with some data to the client that it could use to do the http range requests. This proposal feels like it could be extended in a fairly easy way to support differential download.
    - philsnow 3y ago
      Interesting! Privacy concerns aside for the moment, I would guess that there is some "optimal" compression dictionary over some transferred data set, and that Google/Chrome of all people would be in a position to calculate it and distribute it along with Chrome. Then Google could ship that dictionary to all (Chrome) browsers and update it once a month, and ship the same dictionary to anybody who wants to use it on the server side. Browsers can indicate which shared dictionaries they have preloaded and if there's overlap with which dictionaries the server has, the server can just choose one and use that to compress the stream (which seems kind of like ciphersuite negotiation). Compression should be faster and use way less memory if the sender can assume that the receiver already has the same dictionary, and if there's any problem, both sides can just fall back to on-the-fly compression with inlined dictionary like we've always done. There are almost certainly different optimal dictionaries for different locales / countries, each of which could be calculated and distributed in the same way. Even if the 'wrong' dictionary gets used for a given request, it's (probably) not catastrophic. I guess it might be possible for an attacker to indicate their client only has one dictionary and request pages that they know are disadvantageous for the server to have to compress with that dictionary. Even then, server-side heuristics can account for a lower-than-expected compression ratio and, again, fall back to on-the-fly dictionary calculation.
- pornel 3y ago
  It would be a dud. rsync-style download needs to prepare and upload significant amount of data to describe what the client already has. Hashes don't compress, and you want granular ones to reuse as much as possible. Web is more sensitive to latency than bandwidth, and upload is more restricted than download. So rsync hits all the worst spots, for the least gain. The data that diffs nicely, like HTML, is already tiny and compresses very well. The large files, like videos, don't diff well at all. There is a way to make rsync-style differential download really quick to request: the client and server need to agree on diffing only from a specific shared dataset… like a dictionary! And you can replace hashes with smaller variable-length integers.
  - tyingq 3y ago
    Not rsync style in the sense of whole directory trees. Differential range-request download of the subsequent version of some specific file. Because this scheme means client and server already know a prior version via the hash.
jacobgorm 3y ago
I never really understood with Google keeps pushing Brotli. LZ4 and ZStd both predate it by a couple of years, and seem to offer superior performance overall. Is it a Google-NIH thing?
- joelthelion 3y ago
  Patents, maybe?
- oynqr 3y ago
  Brotli usually compresses plain text better than ZSTD.
  - out_of_protocol 3y ago
    Both with dictionaries? Both without? Any links to benchmarks?
    - oynqr 3y ago
      Brotli comes with a dictionary by default, which is optimized for plaintext use cases. Once you give ZSTD a similar dictionary, its ratios are going to be similar/better. I won't provide random links, because those can't replace testing on your own dataset.
- __alexs 3y ago
  Zstd no longer comes with a patent grant which I guess makes it kind of hard to actually use for some people.
  - jacobgorm 3y ago
    Zstd is already used in the Linux kernel, and I would assume that any patents covering Lempel-Ziv and Huffman coding would have expired long ago. The situation around ANS also seems to have been resolved, see https://en.wikipedia.org/wiki/Asymmetric_numeral_systems#Tabled_variant_(tANS) https://en.wikipedia.org/wiki/Asymmetric_numeral_systems#Tab... .
tyingq 3y ago
Interesting two comment snippet from HN in 2018 about this: https://news.ycombinator.com/item?id=18720554 https://news.ycombinator.com/item?id=18720554
rasz 3y ago
>The client will store a hash of the uncompressed response >client will add ...request header as well as a sec-available-dictionary: <SHA-256> loving it, another thing to track clients with
- pimterry 3y ago
  From the spec (https://github.com/WICG/compression-dictionary-transport#fingerprinting https://github.com/WICG/compression-dictionary-transport#fin...): > The existence of a dictionary is effectively a cookie for any requests that match it and should be treated as such: > * Storage partitioning for dictionary resource metadata should be at least as restrictive as for cookies. > * Dictionary entries (or at least the metadata) should be cleared any time cookies are cleared. Given that, I think it offers no more client tracking possibilities than any other existing web tech (cookies, local storage, etc)..
  - TonyTrapp 3y ago
    Maybe no more possibilities than regular cookies, but more stealthy for sure. Cookies are (somewhat) easily reviewable by the user through the web developer UI of most browsers; I doubt there will be any browser UI to managing compression dictionary.
- out_of_protocol 3y ago
  should be w3c dicts only and number of dicts and versions should be heavily limited. well, something like js,css,html/xml,json,common-web and new version every 5 years i think good enough for everyone
Scaevolus 3y ago
They already had a very similar feature. _15 years ago_ with SDCH that got removed in 2018-- https://chromestatus.com/feature/5763176272494592 https://chromestatus.com/feature/5763176272494592 https://daniel.haxx.se/blog/2008/09/09/shared-dictionary-compression-over-http/ https://daniel.haxx.se/blog/2008/09/09/shared-dictionary-com... Presumably they have some reason to think that this will be useful now when it wasn't before?
- qingcharles 3y ago
  Talked about here: https://github.com/WICG/compression-dictionary-transport https://github.com/WICG/compression-dictionary-transport

58 points by judiisis 3y ago

Makes me wonder if rsync-style differential download would be more generally useful than "shared dictionary for shared brotli". The implementation is letting you reference a previously downloaded artifact using a hash value, which is the same starting point.

lifthrasiir 3y ago
I think it solves a different problem. One of Brotli's strengths was a built-in dictionary tuned for the web contents, which makes it especially suitable for short data with no known priors. The compressed dictionary transport is same but tuned for each website. In comparison, rsync algorithm would make sense only when the data is long enough (say, more than 1 MB), in which case a custom dictionary wouldn't help much because the compressor already has a lot of patterns to working with. Ideally both can be implemented, where the HTTP Range request can be updated to support rsync-like algorithms.
philsnow 3y ago
Are you referring to courgette (which the Chrome team uses to make shipping patches/updates take far fewer bytes than previously)? https://www.chromium.org/developers/design-documents/software-updates-courgette/ https://www.chromium.org/developers/design-documents/softwar...
- deleted 3y ago
  [deleted]
- tyingq 3y ago
  Yes, but exposed to everyone. This proposal settles on headers that get passed back and forth that surely some servers would adopt. Headers that established "previously downloaded thing" with a hash. It feels like the process could be exactly the same at the start, but end instead with some data to the client that it could use to do the http range requests. This proposal feels like it could be extended in a fairly easy way to support differential download.
  - philsnow 3y ago
    Interesting! Privacy concerns aside for the moment, I would guess that there is some "optimal" compression dictionary over some transferred data set, and that Google/Chrome of all people would be in a position to calculate it and distribute it along with Chrome. Then Google could ship that dictionary to all (Chrome) browsers and update it once a month, and ship the same dictionary to anybody who wants to use it on the server side. Browsers can indicate which shared dictionaries they have preloaded and if there's overlap with which dictionaries the server has, the server can just choose one and use that to compress the stream (which seems kind of like ciphersuite negotiation). Compression should be faster and use way less memory if the sender can assume that the receiver already has the same dictionary, and if there's any problem, both sides can just fall back to on-the-fly compression with inlined dictionary like we've always done. There are almost certainly different optimal dictionaries for different locales / countries, each of which could be calculated and distributed in the same way. Even if the 'wrong' dictionary gets used for a given request, it's (probably) not catastrophic. I guess it might be possible for an attacker to indicate their client only has one dictionary and request pages that they know are disadvantageous for the server to have to compress with that dictionary. Even then, server-side heuristics can account for a lower-than-expected compression ratio and, again, fall back to on-the-fly dictionary calculation.
pornel 3y ago
It would be a dud. rsync-style download needs to prepare and upload significant amount of data to describe what the client already has. Hashes don't compress, and you want granular ones to reuse as much as possible. Web is more sensitive to latency than bandwidth, and upload is more restricted than download. So rsync hits all the worst spots, for the least gain. The data that diffs nicely, like HTML, is already tiny and compresses very well. The large files, like videos, don't diff well at all. There is a way to make rsync-style differential download really quick to request: the client and server need to agree on diffing only from a specific shared dataset… like a dictionary! And you can replace hashes with smaller variable-length integers.
- tyingq 3y ago
  Not rsync style in the sense of whole directory trees. Differential range-request download of the subsequent version of some specific file. Because this scheme means client and server already know a prior version via the hash.

jacobgorm 3y ago

I never really understood with Google keeps pushing Brotli. LZ4 and ZStd both predate it by a couple of years, and seem to offer superior performance overall. Is it a Google-NIH thing?

joelthelion 3y ago
Patents, maybe?
oynqr 3y ago
Brotli usually compresses plain text better than ZSTD.
- out_of_protocol 3y ago
  Both with dictionaries? Both without? Any links to benchmarks?
  - oynqr 3y ago
    Brotli comes with a dictionary by default, which is optimized for plaintext use cases. Once you give ZSTD a similar dictionary, its ratios are going to be similar/better. I won't provide random links, because those can't replace testing on your own dataset.
__alexs 3y ago
Zstd no longer comes with a patent grant which I guess makes it kind of hard to actually use for some people.
- jacobgorm 3y ago
  Zstd is already used in the Linux kernel, and I would assume that any patents covering Lempel-Ziv and Huffman coding would have expired long ago. The situation around ANS also seems to have been resolved, see https://en.wikipedia.org/wiki/Asymmetric_numeral_systems#Tabled_variant_(tANS) https://en.wikipedia.org/wiki/Asymmetric_numeral_systems#Tab... .

tyingq 3y ago

Interesting two comment snippet from HN in 2018 about this: https://news.ycombinator.com/item?id=18720554 https://news.ycombinator.com/item?id=18720554

rasz 3y ago

>The client will store a hash of the uncompressed response >client will add ...request header as well as a sec-available-dictionary: <SHA-256> loving it, another thing to track clients with

pimterry 3y ago
From the spec (https://github.com/WICG/compression-dictionary-transport#fingerprinting https://github.com/WICG/compression-dictionary-transport#fin...): > The existence of a dictionary is effectively a cookie for any requests that match it and should be treated as such: > * Storage partitioning for dictionary resource metadata should be at least as restrictive as for cookies. > * Dictionary entries (or at least the metadata) should be cleared any time cookies are cleared. Given that, I think it offers no more client tracking possibilities than any other existing web tech (cookies, local storage, etc)..
- TonyTrapp 3y ago
  Maybe no more possibilities than regular cookies, but more stealthy for sure. Cookies are (somewhat) easily reviewable by the user through the web developer UI of most browsers; I doubt there will be any browser UI to managing compression dictionary.
out_of_protocol 3y ago
should be w3c dicts only and number of dicts and versions should be heavily limited. well, something like js,css,html/xml,json,common-web and new version every 5 years i think good enough for everyone

Scaevolus 3y ago

They already had a very similar feature. _15 years ago_ with SDCH that got removed in 2018-- https://chromestatus.com/feature/5763176272494592 https://chromestatus.com/feature/5763176272494592 https://daniel.haxx.se/blog/2008/09/09/shared-dictionary-compression-over-http/ https://daniel.haxx.se/blog/2008/09/09/shared-dictionary-com... Presumably they have some reason to think that this will be useful now when it wasn't before?

qingcharles 3y ago
Talked about here: https://github.com/WICG/compression-dictionary-transport https://github.com/WICG/compression-dictionary-transport