Hoe compressie je pagina kleiner maakt: gzip en Brotli

Als je een webpagina opent, komt er meestal veel minder over de lijn dan de pagina groot is. Het DNS-artikel op deze site is 42.902 bytes HTML. Vanaf een Nederlandse verbinding kwamen er 12.406 bytes binnen. De browser pakt die uit tot precies dezelfde 42.902 bytes, zonder dat er één teken verloren gaat.

Ik heb de gecomprimeerde stroom van die pagina met een eigen Python-script uit elkaar gehaald, tot op de losse bits. Je ziet hieronder de twee trucs waarop gzip draait, waarom Brotli kleiner uitkomt en wat het kost om nog een paar procent te winnen.

De browser vraagt, de server kiest

Compressie op het web begint met een onderhandeling. De browser zet in zijn verzoek een Accept-Encoding-header met de coderingen die hij begrijpt. De server kiest er een en meldt in Content-Encoding wat hij heeft gedaan. Zo staat het in RFC 9110. De namen staan in een register bij IANA, met onder andere gzip, br voor Brotli en zstd voor Zstandard.

Ik vroeg dezelfde wallieweb-pagina op met steeds een andere header:

Accept-Encoding	Content-Encoding	Bytes
identity	geen	42.902
gzip	gzip	12.406
br	geen	42.902
zstd	geen	42.902

Van deze drie kent wallieweb alleen gzip. Vraagt een client iets anders, dan krijgt hij de pagina ongecomprimeerd, zoals RFC 9110 voorschrijft als de server geen van de gevraagde coderingen heeft. De server stuurt Vary: Accept-Encoding mee, zodat een cache de varianten uit elkaar houdt; daarover ging het artikel over HTTP-caching. De voorpagina van nos.nl levert op verzoek wel Brotli.

Gzip is een envelop om DEFLATE

Het gzip-antwoord begint met de bytes 1f 8b 08. De eerste twee zijn de vaste herkenningsbytes uit RFC 1952 (mei 1996). De 08 betekent dat de inhoud met DEFLATE is ingepakt, beschreven in RFC 1951 uit dezelfde maand. Gzip zelf voegt hier een kop van tien bytes toe en een staart van acht: een CRC-32-controlegetal en de oorspronkelijke lengte. Het echte werk gebeurt in DEFLATE, en dat combineert twee ideeën.

Truc één: verwijzen naar wat al geweest is

Het eerste idee heet LZ77. Komt er een stuk tekst langs dat kort daarvoor ook al stond, dan schrijft de compressor een verwijzing op: ga zoveel bytes terug en kopieer er zoveel. Ik liet zlib de zin de kat zat op de mat, de kat zat op de mat. inpakken en las met mijn script terug wat erin stond:

de kat z[4,3]op de mat,[8,4][22,17].

[4,3] betekent vier bytes terug, drie bytes kopiëren. Dat levert at op, uit kat . De hele tweede helft van de zin is één verwijzing van 17 bytes. In DEFLATE mag een verwijzing hoogstens 32 kB terugkijken en maximaal 258 bytes kopiëren.

Om herhalingen snel te vinden, beschrijft de RFC een hashtabel van steeds drie bytes. De compressor zoekt de langste overeenkomst en kijkt met "lazy matching" ook één byte verder, of daar een langere begint. Hoe harder hij zoekt, hoe kleiner het resultaat en hoe langer het duurt. Dat regel je met de standen -1 tot -9 van gzip.

HTML zit vol herhaling, want dezelfde tags, classnamen en attributen komen steeds terug. Mijn eigen gzip -6-versie van de wallieweb-pagina bestond uit 2.747 verwijzingen, samen goed voor 39.601 bytes, en maar 3.301 losse tekens. Ruim 92 procent van de pagina is dus gekopieerd uit iets wat eerder op dezelfde pagina stond.

Truc twee: korte codes voor veelvoorkomende tekens

De losse tekens, lengtes en afstanden die overblijven, schrijft DEFLATE op met Huffman-codering. Normaal kost een byte 8 bits. Huffman geeft veelvoorkomende symbolen een kortere code en zeldzame een langere. Geen enkele code is het begin van een andere, zodat de ontvanger ze zonder scheidingstekens achter elkaar kan lezen.

DEFLATE werkt in blokken en elk blok kan zijn eigen codetabel meesturen. In het eerste blok van mijn gzip-versie kregen de e, de a en de spatie een code van 5 bits. Het teken < kreeg 8 bits, de Q 12. Langer dan 15 bits mag een code niet worden.

Wat elke truc oplevert, kun je apart meten. zlib kan ook alleen Huffman doen, zonder verwijzingen. Dan wordt de pagina 28.037 bytes, 65 procent van het origineel. Op basis van alleen de tekenfrequenties ligt de ondergrens voor een code die elk teken los bekijkt op 27.864 bytes. Huffman komt daar dicht bij, maar de grote sprong naar 9 kB komt uit de verwijzingen.

Waarom de server meer verstuurt dan nodig

Hier zat een verrassing. Gzip -6 op exact dezelfde HTML levert bij mij 9.093 bytes. De server stuurt er 12.406, ruim een derde meer. Mijn script laat zien waar het zit: de server schrijft 7.354 losse tekens, meer dan twee keer zoveel als mijn versie. Hij vindt dus minder herhalingen. De stroom bevat ook twee flush-punten, maar toen ik die nabootste, verklaarden ze het verschil niet. Welke instelling erachter zit, kon ik van buitenaf niet vaststellen.

Brotli: groter venster, ingebouwd woordenboek

Brotli staat in RFC 7932 uit juli 2016. Het gebruikt dezelfde twee trucs, met een paar uitbreidingen.

Het venster waarin verwijzingen mogen terugkijken kan tot 16 MiB min 16 bytes groot zijn. Op de nos.nl-voorpagina, 827.425 bytes HTML, zie je wat dat doet. Met de hoogste Brotli-stand en een venster van 64 kB kwam ik uit op 70.095 bytes, met 256 kB op 63.393 en met 1 MiB op 55.772. Groter maakte geen verschil meer.

Ook kiest Brotli de codetabel voor een teken mede op basis van de bytes ervoor. Na een < volgen nu eenmaal andere tekens dan na een spatie.

Het opvallendste is het ingebouwde woordenboek van 122.784 bytes. Ik heb het uit de bijlage van de RFC gehaald en doorzocht. Het bevat 13.504 woorden van 4 tot 24 tekens, die elk op 121 manieren kunnen worden aangepast, bijvoorbeeld met een hoofdletter of een spatie erachter. Er staan Engelse, Spaanse, Russische en Arabische woorden in, maar ook charset, viewport, </head> en een fragment met <link rel="s. Een verwijzing kan dus naar tekst die nog nooit in het bestand voorkwam.

Bij kleine bestanden scheelt dat veel. Een kaal HTML-skelet van 173 bytes werd met gzip -9 151 bytes, met Brotli 74. Een JSON-foutmelding van 34 bytes werd met gzip zelfs groter: 54 bytes, waarvan 18 voor de kop en staart.

Wat een paar procent kost

De Brotli-bibliotheek kent standen van 0 tot 11. Ik draaide alles op een zuinige Celeron-mini-pc, op dezelfde wallieweb-pagina van 42.902 bytes:

Methode	Bytes
server (gzip)	12.406
gzip -1	10.717
gzip -6	9.093
gzip -9	9.062
Brotli 1	10.545
Brotli 5	8.775
Brotli 11	8.121
zstd -19	8.803

Brotli 11 is 7,5 procent kleiner dan stand 5, maar inpakken duurde 145 milliseconden tegen 2,8. Op de nos.nl-pagina werd dat 4 seconden tegen 38 milliseconden. Voor een pagina die per bezoek opnieuw wordt opgebouwd, is dat te traag; stand 11 loont voor bestanden die je één keer vooraf inpakt. De verhouding van de Brotli-versie die nos.nl zelf stuurde, past ook bij stand 4 of 5 en niet bij 11.

Uitpakken is goedkoop: gzip en Brotli deden er op deze pagina allebei ongeveer een kwart milliseconde over.

Zelf proberen

Kijk hoeveel een site per codering verstuurt:

for e in identity gzip br; do
  curl -4 -s -o /dev/null -H "Accept-Encoding: $e" \
    -w "$e: %{size_download} bytes\n" https://nos.nl/
done

identity: 827226 bytes
gzip: 88634 bytes
br: 67954 bytes

Of pak een pagina zelf in, met verschillende standen:

curl -s https://wallieweb.nl/blog/hoe-dns-een-naam-vindt -o pagina.html
for n in 1 6 9; do printf "gzip -$n: "; gzip -$n -c pagina.html | wc -c; done
zstd -q -19 -c pagina.html | wc -c

gzip -1: 10719
gzip -6: 9106
gzip -9: 9076
8811

Voor Brotli werkt de Python-module (pip install brotli):

python3 -c "import brotli; d=open('pagina.html','rb').read(); print(len(brotli.compress(d, quality=11)))"

8127

De getallen wijken iets af van de tabel, omdat de pagina een paar dynamische waarden bevat en gzip hier ook de bestandsnaam in de kop zet.

Tot slot

Ik had verwacht dat Huffman-codering het zware werk deed, omdat dat de bekendste naam is. Op deze pagina brengt het in zijn eentje de grootte maar terug tot 65 procent; het kopiëren van eerdere stukken doet de rest. Daarnaast verraste me dat een woordenboek uit 2016 letterlijk </head> bevat, zodat Brotli al iets van webpagina's weet voordat het eerste byte binnen is. En de server van deze site laat zelf ruim 3 kB per pagina liggen, die gewone gzip zou kunnen opvangen.