diff a komprese

18. 9. 2016

Někdy se zkrátka daří.

Celé dny se nestane nic a pak přijde den, kdy zjistím, jak funguje unixová utilita diff a použiji těchto znalostí, abych komprimoval 3x rychleji a 70x lépe než ctihodný gzip.

Ale začnu popořadě.

Mám dataset, který je tvořen JSON soubory. Nezáleží kolik přesně jich je, jde o něco jako O(hodně) a v katalogu Dellu jsem nenašel stroj, který by měl RAM tak velikou, že by se do ní všechno vešlo. Nejde jen o náhodné JSON soubory, ale log JSONů (stylem jeden JSON na řádek), které jsou si velice podobné. Záznam může mít něco mezi jedním a sto kilobajty s tím, že se od toho předchozího liší jen změnami na několika málo místech: Nějaké vnitřní vlastnosti mohou být aktualizované, do pole může být přidán jeden nebo dva dílčí objekty a jiný může chybět. Podobnost je veliká a většinou přasahuje 99%.

Když je entropie celého datasetu takto malá, kompresní algoritmy by měly zářit.

Bohužel tomu tak není a Gzip v nejlepším případě komprimoval na čtvrtinu. To mi dlouhou dobu přišlo jako neuspokojivý výsledek s přihlédnutím k obrovské repetici v datech. Dlouho jsem to nijak neřešil, protože disky jsou velké a nestojí skoro nic. Ale data narůstala a narůstala, až do té míry, že jsem o zase začal přemýšlet o lepší kompresi.

Napadlo mě, že když jde o stringy, mohl bych uchovávat jen diffy mezi řádky v logu. To na první pohled vypadá jako jednoduchý problém, který se dá sfouknout za půl hodiny. Když jsem o tom ale začal přemýšlet, došlo mi, že to není tak jednoduché. Naivní algoritmy můžou fungovat v mnoha případech, ale dají se velice snadno zmást a pak nenajdou nejmenší možný diff, ale nějakou monstrozitu, která nic moc neušetří.

Potřeboval jsem něco zásadového, potřeboval jsem algoritmus.

Napadala mě parafráze na Kapitána Willarda z Apokalypsy:

Everyone gets everything he wants.
I wanted an algorithm.
And for my sins, Wikipedia gave me one.
Brought it up to me like room service.

Jak jsem velice rychle zjistil, základem unixové utility diff je algoritmus pro nalezení nejdelší společné podsekvence (longest common subsequence/LCS).

Když mám například dvě sekvence/stringy:

A B D E I J K L X
B C D I J L M N

a správně je zarovnám

A B   D E I J K L     X
  B C D   I J   L M N

je vidět, že jejich LCS je

B D I J L

Když mám tuhle sekvenci, můžu snadno spočítat diff. Z prvního řetězce byly odstraněny znaky A E K X a do druhého přidány C M N. Hotovo.

Řešení LCS se dá najít rekurzivně v nepoužitelně pomalém čase nebo přes dynamické programování s pomocí O(n²) extra prostoru. Paměťové nároky situaci komplikují, protože LCS na úrovni znaků dvou stringů, které mají 100kB, by potřebovalo 40GB pomocnou matici. Z toho důvodu utilita diff nebere v potaz jednotlivé znaky, ale celé řádky, kterých je mnohem méně. To dělá problém lépe zvládnutelný.

Já však neměl text, ale jednořádkové JSONy.

Chvíli jsem začal uvažovat, že bych JSONy naparsoval a počítal jejich diffy na úrovni datových struktur. Ale pak jsem, nejspíš pod vlivem ducha Edwarda Kmetta, dostal nápad. Co kdybych string JSONu rozdělil podle čárek a počítal diff na úrovni těchto segmentů. Velice snadno bych tak dostal bloky textu, které mají v JSONu strukturální význam bez toho, aniž bych ho musel parsovat.

Diff mezi těmito dvěma JSONy

{"a":1,"b":2,"c":3}
{"a":1,"b":47,"c":3}

by vypadal

- 7 6       // odstraní 6 znaků počínaje pozicí 7
+ 7 "b":47, // na pozici 7 vloží nový řetězec

To funguje, ale proto, že JSON obsahuje hodně věcí oddělených čárkou a algoritmus běží v podstatě v kvadratickém čase, není to tak rychlé, jak by to jen mohlo být. Pokud JSON obsahuje vnořené objekty, můžu ho nasekat podle uzavírací složené závorky }¹ . Těch bývá méně a hledání LCS je pak rychlejší.

Ok, teď tedy vím, jak udělat diff JSONů. Ale je to k něčemu dobré?

Místo vysvětlování ukážu malou tabulku:

jsonlog            2926466947 B   originální soubor
jsonlog.gz          772794031 B   komprimováno gzipem
jsonlog.diffs        80895070 B   komprimováno jako série diffů
jsonlog.diffs.gz     12725864 B   diff + gzip

Jak je vidět, tak v tomto případě je samotné převedení na sérii diffů skoro 10x efektivnější než gzip a kombinace s gzipem vede ke 230x kompresi, velice blízko ke skutečné informační hodnotě datasetu.

Kdyby se někdo zajímal, proč si gzip vede tak zle, tak se musím přiznat, že nevím. Moje teorie je, že nevidí, a tedy ani nedokáže využít, podobnosti ve velkém měřítku a komprimuje v malém pracovním okně. Moje doménové znalosti v tomto případě fungují lépe než obecný gzip² . Uvažoval jsem také o xz. Ten komprimuje o něco lépe, ale je strašlivě pomalý.

Samotné diffování je 3x rychlejší než gzip a diffy se na mém stroji (v jednom vlákně) dekomprimují rychlostí 336 MB/s, což je víc než rychlost čtení/zápisu rotujícího disku. Vyplatí se tedy online dekomprimovat data než je číst z disku.

A to podle mě, stojí za tu námahu.

Zdrojový kód je v tomto gistu a tomto repozitáři

Dodatek #1: Ukazuje se, že zstd s maximální úrovní komprese komprimuje stejně dobře jako můj diff+gzip hack a dekomprese je velice rychlá.

Dodatek #2: Po chvíli testování zstd vypadá jako ideální program na obecnou komprimaci. Úrovní komprese je velice blízko xz/lzma, ale pracuje mnohem rychleji a dokáže data dekomprimovat rychlostí přes 1GB za sekundu.

Poznámky:

Pokud na to chcete jít o něco chytřeji a vyhnout se složeným závorkám v řetězcích, stačí udělat dvoustavové parsování: mimo string a ve stringu. Když jsem mimo string, závorky beru v potaz, když jsem ve stringu, přeskakuji je.
Funguje to takhle dobře jen pokud je podobnost mezi sousedícími záznamy veliká. Když by můj dataset byl tvořen zcela náhodnými JSONy, diffová komprese by neušetřila skoro žádné místo, narozdíl do gzipua, který by stále dokázal srazit velokost na něco kolem jedné čtvrtiny.