Saját JPEG-tömörítőt dolgozott ki a Dropbox

Új veszteségmentes tömörítést fejlesztett a JPEG-állományok számára a Dropbox. A Lepton a fejlesztők szerint mintegy 22 százalékkal képes átlagosan tömöríteni a standard JPEG-t használó képfájlokat, ami gigantikus megtakarítás a felhős tárolószolgáltatás számára. A cég közzétette a felhasznált Leptop algoritmus kódját, Apache 2.0 alatt.

Hatékonyabb is lehetne

A JPEG kódolás lényege a megfordítható diszkrét koszinusz-transzformáció, amely a 8x8 pixeles blokkokra bontott képet bontja összetevőire. A kódolás eredménye, hogy minden blokkhoz kapunk egy számsort, az alapösszetevők koefficienseivel (szorzóival). Ebből az első a blokk abszolút fényerejét határozza meg (ez a DC), a többi pedig a kisebb-nagyobb részletekért felel (a 63 darab AC). A Lepton feladata a DC és az AC-k minél hatékonyabb újrakódolása úgy, hogy az eredmény minél kevesebb helyet foglaljon.

Az együtthatók eltárolásához a Lepton először a szám hosszát írja le unáris számrendszerben (ahol a szám az egyesek összege, a nulla pedig a szám végét jelzi), ezt követi az előjel-bit, majd az abszolút érték következik, standard bináris formában. Kis kihagyás itt is van, ugyanis minden szám 1-essel kezdődik, és mint ilyen, redundáns, így elhagyható - lévén a szám hosszát már korábban rögzítettük. A Dropbox szerint ez a leghatékonyabb, legkevesebb bitet használó aritmetikai kódolás.

Az első együttható (DC), amely a blokk fényerejét jelöli, messze a legfontosabb, és a legtöbb helyet is foglalja - egy átlagos iPhone-fotó esetében a teljes tárhelyigény 8 százalékát kéri. Ennek oka, hogy míg az AC-ket az algoritmus normalizálja (tehát -127 és 128 közötti számra redukálja), a DC dinamikatartománya nagyon széles. Adja magát a megoldás: normalizáljuk azt is. Pontosan ezt csinálja a Lepton, a kép adatai alapján megpróbálja (determinisztikusan) előrejelezni a DC értékét, és csak az eltérést (a deltát) tárolja el.

^{Így áll elő a kép az AC-k összeadásával.}

Az előrejelzést az teszi lehetővé, hogy a JPEG-vel ellentéteben a Lepton a blokk végére helyezi a DC-t, így mire ehhez a számhoz ér, már rengeteg előzetes információval rendelkezik az algoritmus, és a bejárási útnak megfelelően már a blokk néhány szomszédját is ismeri, így azok fényerejét és az AC-kból számolt fényerőt felhasználva elég pontosan meg tudja határozni az aktuális blokk DC-értékét. A veszteségmentes eljáráshoz ezt persze még korrigálni kell az aktuális adattal, de ez lényegesen kisebb, mint az eredeti szám. Hogy pontosan mennyivel? A Dropbox adatai szerint a DC helyigényéből 61 százalékot sikerült lefaragni.

Szerveroldalon a varázslat

"A Leptont használjuk ahhoz, hogy a Dropboxba feltöltött képeket tömörítsük, és gyors ütemben kódoljuk át a már letárolt régebbi képeket is. A Lepton használata máris több petabájt tárhelyet szabadított fel" - mondta Daniel Reiter Horn, a Dropbox rendszermérnöke. A Leptont a rendszer egyébként kizárólag szerveroldalon használja, vagyis ez a belső tároló formátum, a szerverek standard JPEG-t fogadnak és azt is adják vissza, a hálózati költségeken tehát a Dropbox ezzel nem tud spórolni, csak a felhasznált tárhelyen - szemben például a Google által fejlesztett, kliensoldalon futó Brotlival.

Ünnepi mix a bértranszparenciától a kódoló vezetőkig Négy IT karrierrel kapcsolatos, érdekes témát csomagoltunk a karácsonyfa alá.

A megoldás persze kompromisszumos, a tárhelyért cserébe ugyanis számítási kapacitással kell fizetni, a Dropbox szerint azonban ez bőven kifizetődő, az adatközpontban használt Xeon E5-2650 v2-n az algoritmus 15-25 megabájt/másodperces kitömörítési rátát tud elérni, ez pedig gyorsabb, mint az elérés más szűk keresztmetszetei. További bónusz, hogy a Lepton kitömörítése streamelhető, tehát nem kell a teljes képet kitömöríteni először ahhoz, hogy a szerver elkezdje visszaadni a standard JPEG-t, így a felhasználó gyakorlatilag semmit nem érzékel a háttérben zajló folyamatokból.

A Lepton forráskódja elérhető a projekt GitHub-oldalán.