Brotli: ismerkedjünk meg az új webes tömörítővel!

A Google még 2013-ban mutatta be Zopfli névre keresztelt alternatív tömörítő algoritmusát. A Zopfli úgy hozott mérhető és számottevő zsugorodást a tömörített adatokban, hogy közben visszafelé kompatiblis maradt, vagyis a tömörített adatok standard zlib formátumot használtak és bármilyen zlib deflate-kompatibilis eljárással kitömöríthetőek maradtak. Ez egyúttal gátat is szabott az eljárás hatékonyságának, a formátum ugyanis komoly megkötést jelentett a tömörítési algoritmusra nézve.

Hatalmas ablakkal

A Zopflit kimondott lelkesedéssel fogadta az IT-szakma, a következő lépésben így kicsit távolabbra tekintettek a Google mérnökei és olyan algoritmust dolgoztak ki, amely elveti a visszafelé kompatibilitást, azonban az elérhető legmagasabb hatékonyságot éri el. Ennek az erőfeszítésnek lett az eredménye a Brotli, amely kombinálja az LZ77 és a Huffman tömörítő algoritmusokat, gigantikus "csúszó ablakot" (sliding window) és fix szótárat.

^{Számítástechnika 1x1 frissítő: csúszóablak, LZ77-ben}

Itt érdemes egy kitérőt tenni a tömörítés működési elve felé. Nagy vonalakban a használt algoritmusok úgy működnek, hogy ha ismétlődő adatsort találnak a tömörítendő adatfolyamban, akkor azt az első előfordulásra mutató referenciával helyettesítik. A referencia azonban csak bizonyos távolságra tud visszamutatni az adatfolyamban (különben túl nagy lesz maga a mutató), ez a maximális távolság a csúszóablak, az ablakon kívül az algoritmus emiatt nem tud deduplikálni. A nagyobb ablakkal hatékonyabb tömörítés érhető el, cserébe viszont a referenciamutatóknak is hosszabbnak kell lenniük. Emiatt a zlib deflate jellemzően 32 kilobájtos ablakkal dolgozik, a Brotli azonban akár 16 megabájtos ablakot is képes használni.

Fix szótár? Nagy ötlet!

Hasonlóképp érdekes döntés a fix tömörítőszótár használata. A szótár a csúszóablak kiegészítője, és annak hátulütőjét hivatott minimalizálni. A helyettesítési mátrixban a teljes tömörített állományra (vagy állományokra) kiterjedően azonosíthatóak a leggyakrabban előforduló adatsorok, így a tömörítés során nem csak visszafelé mutató referenciák, hanem a szótárra mutató referenciák is használhatóak. A nagy szótár emiatt növeli a tömörítés hatékonyságát, de jelentős overheadet is képez, ha túl nagyra méretezzük, hiszen azt csatolni kell a tömörített fájlhoz. A szótárak jellemzően dinamikusak, vagyis az épp tömörített adatmennyiség határozza meg, hogy milyen adatokra tartalmaz referenciát, ez növeli a hatékonyságát.

^{Huffman-kódolás - gyakori szimbólumok rövid helyettesítőt kapnak}

A Brotli esetében azonban ezzel szakítottak a fejlesztők és egyetlen, 122 kilobájtos fix szótárat implementáltak. Ez a szótár egy gigantikus tesztkorpusz tömörítésével állt elő, és roppant érdekes kompromisszumot jelent. A fix szótár ugyanis bizonyos adattípusokhoz ideális lesz, más esetben viszont nem hatékony, de mivel mind a tömörítő, mind a kitömörítő oldal ismeri, nem kell a tömörített adat mellé mellékelni, elegendő, ha a kitömörítést végző könyvtár ismeri azt. A gyakorlatban ez azt jelenti, hogy a szótár sosem utazik a hálózaton, mivel azt mindkét végpont tárolja, ez összességében hatalmas megtakarítást hozhat.

Miért nagy dolog?

Ez utolsó mondatból már sejthető, hogy mi a Brotli célja. A hálózati adatfolyam tömörítésére pont ideális ez az algoritmus, ehhez azonban szükséges volt még egy elem: A Zopfli ugyanis roppant lassú, a Google azt eleve csak statikus tartalmak előtömörítéséhez ajánlja (a standard zgip deflate-hez képest mintegy nyolcvanszor lassabb). A Brotli azonban megközelítőleg a zlib sebességét hozza, így nem csak statikus, hanem bizonyos dinamikus tartalmak előtömörítéséhez is alkalmas lehet - a pontos felhasználást persze az adott tartalomtípushoz érdemes szabni.

De miért fejleszt pont tömörítő algoritmust a Google? Ahogy a Zopfli esetében már magyaráztuk, a tömörítés pozitív hatásai sokkal messzebb mutatnak, mint néhány állomány kisebb kapacitásigénye a meghajtón. A hálózaton tömörítve utazó adat például megnöveli az effektív sávszélességet - mobilkliensről böngészve például nem mindegy, hogy egy oldalon használt egyedi betűtípus egy másodperc vagy fél másodperc alatt töltődik le (és egyáltalán nem mindegy, hogy ezzel a havi adatforgalmi keret hány százalékát fogyasztotta el).

Pontosan emiatt a Brotli egyik első implementációja a WOFF (Web Open Font Format) második generációja lesz. Ez a fajta tartalom ideális a Brotli számára - statikus adat, a formátumot pedig kliens- és szerveroldalon is támogatni fogják a megfelelő szoftverek, kompatibilitási probléma tehát nem merül fel. Ebben a szerepkörben az új algoritmus mintegy 25 százalékkal hatékonyabb, mint a Zopflit használó WOFF1, láthatóan erre (is) optimalizáltak a Brotli kidolgozói.

Nagy pénz, nagy szívás: útravaló csúcstámadó IT-soknak Az informatikai vezetősködés sokak álma, de az árnyoldalaival kevesen vannak tisztában.

A szélesebb körű elterjedés azonban komolyabb akadályokba is ütközhet. Voltak már korábban próbálkozások arra, hogy jobb, hatékonyabb tömörítésre cseréljék a gzipet a webes tartalmak átvitelénél, ezek azonban a változatos webes átjárókon (proxyk, gateway-ek, különböző szolgáltatói "optimizálók") fennakadtak. Emiatt jó eséllyel csak HTTPS-alapú kommunikáció tömörítésére lesz használható, ebbe ugyanis az "útonállók" nem látnak bele, így piszkálni sem tudják a tartalmat.

Az algoritmust tesztelte a Facebook is, az eredmények több, mint meggyőzőek. A Zopflihez viszonyítva a CSS állományok 17 százalékkal, a JavaScript pedig 20 százalékkal kisebb lett. Az Alexa top-300k oldalon tesztelve a CSS 12 százalékkal, a JavaScript 9 százalékkal zsugorítható a gziphez viszonyítva.

A Brotli tömörítő algoritmust a Google két mérnök-matematikusa, Jyrki Alakuijala és Szabadka Zoltán fejlesztette ki.  Az IETF-hez benyújtott szabványtervezet itt, a szabad szoftveres implementáció pedig itt érhető el.