deduplikáció [megoldva]

Debian GNU/Linux

Tudna valaki ajánlani egy jól működő alkalmazást deduplikációhoz?
Egy csomó XP-s image-et kellene lementenem, és mivel ezek 98%-ban azonosak, ezért jelentős mennyiségű helyet spórolhatnék meg így.

egyelőre ezeket találtam: dedupe, eXdupe, storebackup

windows alá is jöhet progi és nem feltétlenül kell open source-nak vagy ingyenesnek lennie

Előre is köszi!

  • 58705 megtekintés

Az összes deduplikációs megoldásnak az a baja, hogy blokkokkal dolgoznak, azaz hiába van ugyanaz a fájl mondjuk egy ISO-ban, ha nincs blokkhatárra igazítva, nem lesz deduplikálva.
Anno kísérleteztem azzal, hogy az adatban formátumokat keresek (pld. jpg, mp3 headert, így ha bitfolytonosan vannak tárolva, a hosszukat is rögtön ki tudom nyerni), és azokra igazítva (a hosszukkal) deduplikálok.
Egész jó eredményeket értem el, de aztán elvonták a figyelmem, és nem fejeztem be.

Just bloggin'. :)
--
zsebHUP-ot használok!

igen, megoldottam. De pl. a legutobbi fsf konferencian kerdeztek is, hogy tud-e bra-fele :-) deduplikaciot, hogy amikor van egy Re: Re: Re: ... Re: thread, amikor bela csak egy szmajlit tesz a vegere/elejere, akkor csak a szmajlit taroljuk el, hiszen a body tobbi resze mar ismert.

A gondom nekem is pont az ezzel, hogy nagyon nem trivialis eldonteni, hogy hol vagod kette a levelet, stb. Nem azt mondom, hogy teljesseggel lehetetlen, de hogy kicsinalja a gepet teljesitmeny szempontbol, az tuti. Ugyhogy hacsak (pl. a google soc kereteben :-)) valaki nem tesz le egy nagyon popec implementaciot, akkor ilyen feature nem lesz a piler-ben...

Diktatorok kezikonyve

Ebben a topicban fájlrendszer szintű deduplikációról volt szó, ami adatblokkokat lát, és jellemzően nem érti, hogy mi van bennük.
Ennyi erővel a *peget is felhozhattad volna példának, az is deduplikál.
De még az említett szerverek sem jó hasonlatok, mert attachmentre (mime partokra) bontják legfeljebb a leveleket, és azokat tudják "deduplikálni" (SIS-nek, Single Instance Store-nak hívják).
Az Exchange 2010-ből ezt a funkciót egyébként kivágták.
Amiről én beszélek, az pld. egy ISO-ban lévő tar-ban tárolt jpeg-et képes deduplikálni a fájlrendszeren önállóan tárolt jpeg-gel.
--
zsebHUP-ot használok!

Nem annyira gázos a helyzet. Tegyük fel, hogy 4 kB-os blokkonként készít SHA ellenőrzőszámot a deduplikáció. Szerencsénk van ekkor, hiszen például az ext4 és sok más fájlrendszer 4 kB-os egységgel allokál.

Vagy tévedes irányból közelítem?
ISO9660 hézag nélkül összerak vagy 2 kB-os blokkhatárra allokál?

Kérlek vedd észre, hogy a válasz lényegtelen a felvetésem szempontjából (a példa szerencsétlen volt, nem ment át a lényeg, mert önmagában az ISO-ban valóban blokkhatárra (2k) kerülnek a fájlok).

A közelítés tehát jó, <=2k-s blokkmérettel ez megvalósul (2k-nál többel már kis eséllyel), csak én nem erről beszéltem. :)

--
zsebHUP-ot használok!

"Az összes deduplikációs megoldásnak az a baja, hogy blokkokkal dolgoznak, azaz hiába van ugyanaz a fájl mondjuk egy ISO-ban, ha nincs blokkhatárra igazítva, nem lesz deduplikálva."

Ez nem így van, pl. az EMC DataDomain tud változó hosszúságú részeket deduplikálni. Adaptív deduplikációnak hívják a megoldást náluk.

A kérdés az, hogy az általam felvetett problémát orvosolja-e.
Azaz ha van pld. egy jpeg-em akármelyik fájlban, akárhol, azt képes-e deduplikálni akármelyik másik fájlban akárhol lévő ugyanolyan jpeggel.
Én azt gondolom, hogy tudom a választ (nem, mert nem ezt a problémát próbálja megoldani), ha szerinted igen, akkor kérlek írd le hogyan. Vagy linkelhetsz wp-t is, amiből ezt egyértelműen ki lehet olvasni.
--
zsebHUP-ot használok!

http://www.emc.com/corporate/glossary/variable-length-deduplication.htm

Egyébként úgy működik a dolog, hogy betölt a memóriába egy csomó adatot és abban keres blokkméretnél hosszabb ismétlődéseket, ezeket pedig csak egyszer tárolja rendesen, a második alkalomtól meg egy referenciát tárol csak (legrosszabb esetben egy blokkban).

Én is
pisz
e Te
is pi
sze v
esszü
nk ös
sze,
vessz
ünk ö
ssze.

Ha mondjuk ez a szöveged, egy sor reprezentál egy blokkot, akkor a " is pisze " és a " vesszünk össze" stringet lehet második alkalommal megspórolni, helyette egy blokkos referenciát alkalmazni.

A következőt állítottad:
- kiírok a deduplikált storage-ra 100 TB-ot (attól a komplikációtól, hogy ez blokkos (fragmentáció, tail packing stb), vagy valami FS (azaz egy szinttel feljebb lát, pld. NFS, CIFS stb) most tekintsünk el), amelyben ott van egy 362535 bájtos jpeg akárhol (mondjuk egy fájl 998831. bájtjától)
- majd ráírom ugyanezt a jpeget akárhová (mondjuk egy másik fájl 334393. bájtjától)
és az EMC (DD) variable length deduplication megoldása képes ezt deduplikálni.

A hogyan érdekelne.

Ez azért nem túl gyors (tapasztalat, igaz, én szoftverből csináltam :), illetve ha inline, más kérdéseket is felvet...
De továbbra is azt gondolom, hogy ezt nem azt jelenti, hanem pld. azt, hogy a fájlba beszúrásra kerül valahová új tartalom, azt képes felismerni (pld. ha emiatt shiftelődik minden).
--
zsebHUP-ot használok!

TIPP: ha nekem kéne ilyet csinálnom, valahogy ilyen irányba kezdenék kísérletezni (aztán vagy bejön vagy nem).

Először is, szerintem az a követelmény, hogy gyorsan tudjam számolni, akár azon az áron is, hogy sok fals pozitívot ad. Utána már ráér komolyabb módon ellenőrizni, hogy tényleg egyezik-ek. Valószínűleg a fals negatívokban is jelentős kompromisszumokat lehet kötni. Pl nagyon rövid sorozatokat biztosan nem érdemes deduplikálni, mert a helyére beszúrt referencia hosszabb lenne.

Egy olyan hash-t vagy checksumot kell választani, ami könnyen számolható inkrementálisan. Tehát ha egy blokkra már van checksumom, és egy bájtot hozzácsapok a végéhez vagy egy bájtot leveszek az elejéről, akkor gyorsan tudom képezni az új blokk checksumját. A CRC-k pl biztosan ilyenek. Ezután csúszóablakszerűen egy ilyen gördülő checksumot próbálok csinálni. A nemtriviális nehézség ott lesz, hogy hogyan tudom indexelni. Ha elég rövid a checksum, mondjuk pl CRC32, akkor a teljes értékkészletnek megfelelő méretű hash tábla pár GB memóriában már benntartható. Azt a címet kell minden checksum érték mellé odaírni, ahol találat volt. Ami elgondolkodtató, az ütközések kezelése, ha vödrös hash-szerűen minden címet tárolnék, ahol találat volt, nagyon megnőne a helyigény, az eredeti adattal összemérhető lenne, sőt még nagyobb is. Én azt gondolom, hogy elég 1-2 "legjobb" címet tárolni minden checksum értékhez, mégpedig az alapján, hogy a szomszédos blokkok checksumja is egyezett-e -> ugyanis akkor jó eséllyel egy nagy összefüggő adatfolyamba találtunk bele, márpedig pont ezeket akarjuk leginkább megfogni. A rövidebb egyezéseket ez nyilván nem fogja megtalálni, de ez még mindig jó kompromisszum lehet.

De ez persze nyilván nem ilyen egyszerű, ennek a korrekt megoldásából egy doktori tézis biztosan kijönne.
---
Internet Memetikai Tanszék

A phd-ről én már letettem, úgyhogy mostanában annyira nem izgat.
Egyszerűen csak elgondolkodtatott ez a probléma ezért leírtam, hogy mi jutott eszembe.

EDIT: egyébként Andrew Tridgell tézise ténylegesen ebből jött ki. :)
A projekt még létezik csak már Con Kolivas tartja karban. Aki esetleg nem ismerné: http://lrzip.kolivas.org/ Kicsit más persze az alkalmazási terület (pl random seekben az lrzip nem hiszem, hogy túl jó lenne, az EMC-nek viszont kell), ezért felteszem az EMC nem így oldja meg. De tanulni nyilván lehet belőle.
---
Internet Memetikai Tanszék

Gyorsan ki tudod deriteni.

Ha pl. Ubuntu van a szerverenm felrakod a zfs ppa-t, letehozol egy volume-ot, beallitod a dedup-ot, ramasolsz egy image-et es utana ramasolsz egy masikat.

A a hely nagyreszet meg kell hogy sporolja neked a deduplikacio, igen.

Az eredmenyt ird majd be, pliz.

10x
tompos

ui.: Valoszinuleg a tomoritessel is tudsz vmennyit sporolni.

Feltelepítettem a zfs-t forrásból.
létrehoztam egy fájlrendszert:

zfs create tank/dedup2

ha jól tudom, akkor két féle deduplikáció van (online és offline)
az online ha jól értettem, akkor egyből megcsinálja a fájlok
összehasonlítását és a deduplikációt
az offline utólagos feldolgozást végez
(ha valami baromságot írok javítsatok ki)

jelenleg online státuszban van a pool-om ("zpool list"-el néztem, lehet
hogy ez nem azt jelenti amit az elöbb írtam?)

most mit kellene csinálnom?
egyszerűen másoljak rá egy állományt?
megpróbáltam, de látszólag a fájlok mérete nem lett kisebb, és a
partíció mérete sem
tömörítetlen WIM fájlokat használtam
hol kellene méretkülömbséget látnom?

Lehet hogy valamit elrontottam?

2 db 98%-ban azonos WIM van jelenleg a /tank/dedup2-n
és ezt látom:

root@dedup:~# zpool list
NAME SIZE ALLOC FREE CAP DEDUP HEALTH ALTROOT
tank 93G 2,44G 90,6G 2% 1.01x ONLINE -
root@dedup:~# zfs list
NAME USED AVAIL REFER MOUNTPOINT
tank 2,48G 89,1G 30K /tank
tank/dedup 30K 89,1G 30K /tank
tank/dedup2 2,48G 89,1G 2,48G /tank/dedup2

beállítottam a checksum-ot "on"-ra és a dedup-ot is "on"-ra
mit rontok el, ill. mit kellene még beállítanom?

Lehet hogy csak azért nincs méretkülömbség, mert a WIM-et nem lehet deduplikálni?

utána...

root@dedup:~# zpool get dedup tank
NAME PROPERTY VALUE SOURCE
tank dedupratio 1.01x -

root@dedup:~# zfs get all | grep dedup
tank dedup on local

tank/dedup2 type filesystem -
tank/dedup2 creation h jan 7 15:17 2013 -
tank/dedup2 used 2,48G -
tank/dedup2 available 89,1G -
tank/dedup2 referenced 2,48G -
tank/dedup2 compressratio 1.00x -
tank/dedup2 mounted no -
tank/dedup2 quota none default
tank/dedup2 reservation none default
tank/dedup2 recordsize 128K default
tank/dedup2 mountpoint /tank/dedup2 default
tank/dedup2 sharenfs off default
tank/dedup2 checksum on inherited from tank
tank/dedup2 compression off default
tank/dedup2 atime on default
tank/dedup2 devices on default
tank/dedup2 exec on default
tank/dedup2 setuid on default
tank/dedup2 readonly off default
tank/dedup2 zoned off default
tank/dedup2 snapdir hidden default
tank/dedup2 aclinherit restricted default
tank/dedup2 canmount on default
tank/dedup2 xattr on default
tank/dedup2 copies 1 default
tank/dedup2 version 5 -
tank/dedup2 utf8only off -
tank/dedup2 normalization none -
tank/dedup2 casesensitivity sensitive -
tank/dedup2 vscan off default
tank/dedup2 nbmand off default
tank/dedup2 sharesmb off default
tank/dedup2 refquota none default
tank/dedup2 refreservation none default
tank/dedup2 primarycache all default
tank/dedup2 secondarycache all default
tank/dedup2 usedbysnapshots 0 -
tank/dedup2 usedbydataset 2,48G -
tank/dedup2 usedbychildren 0 -
tank/dedup2 usedbyrefreservation 0 -
tank/dedup2 logbias latency default
tank/dedup2 dedup on local
tank/dedup2 mlslabel none default
tank/dedup2 sync standard default
tank/dedup2 refcompressratio 1.00x -

lehet hogy csak a WIM tartalmával kellene próbálkoznom :)

A WIM olyan image mint az ISO, de ezt az M$ találta ki. :)

talán valamivel hatékonyabb lenne a dolog, ha felcsatolnám ezeket az image-eket, és a tartalmukat átmásolnám 1-1 könyvtárba,
és ezeket a könyvtárakat próbálnám deduplikálni

belefutottunk egy újabb hibába...
az egy dolog, hogy a WIM tömörítve érkezik, ezt "imagex /export /compress none"-al meg lehet oldani, viszont az imagex /mount hibásan csatolja fel a fájlt
a windows/assembly könyvtár tartalma teljesen szétesik, a windows csak fájlokat lát, Linux alatt látszanak a könyvtárak, de a teljes struktúra szét van esve, és másolni nem lehet (se windows se Linux alatt)
Ennyit a microsoft hivatalos alkalmazásáról (imagex), amit a WIM formátumhoz ajánlanak.

Így most egyelőre a ZFS project lefújva...

Hamarosan tesztelem a Win2012 dedup funkcióját, hogy képes-e elbánni tömörítetlen WIM fájlokkal...

Csináltam egy tesztet 6 kibontott image-el. (WIM-ből "imagex /mount"-al)
Ezekből 3 db C:\ és 3db D:\ meghajtó volt, természetesen az XP a C-n volt, a D-n egy alkalmazás van.
4 image-et úgy sikerült deduplikálnom, hogy a kapott adat mennyisége kisebb lett, mint a fele (4GB -> 1,8GB)
aztán a maradék két image kicsit elrontotta a statisztikát
a végső statisztika 5,59 GB -> 2,53GB (kb. 55%-os helyspórolás)
szerintem ez nagyobb mennyiségnél jelentősen javulna (valószínűleg az 5.-6. image sok egyedi fájlt tartalmazhatott)

Ha egy WIM imageba fájlba több imaget teszel (hozzáfűzés imagex /append és /verify kapcsolókkal) akkor az általad kivánt deduplikációt maga az imagex elvégzi fájl szinten. Eddig úgy 30 körüli image ami nálam egy WIM fájlban van, nem tudom mi a felső korlát.

Egy cikk róla: http://www.windowsitpro.com/article/windows-power-tools/save-space-with…

A http://support.microsoft.com/kb/935467 linken leírt korlátok miatt nem ajánlja az MS az imagex backupra történő használatát. Ha valakinél ezek a korlátok nem okoznak gondot, akkor a fenti kapcsolókkal egész kényelmes arra is mivel minden fájl egy példányban van meg a WIM fájlban és abból az adott index alatti image állapot gyorsan visszatölthető.

Anno kerestem hasonló funkcionalitású eszközt linuxra, de nem találtam. Akkor egy rsync snapshot backup megoldás volt a legközelebb hozzá (http://www.mikerubel.org/computers/rsync_snapshots/), ha egy filesystem image file-ba készül ami loop deviceként van mountolva.
--
Légy derűs, tégy mindent örömmel!

háát sajnos nekem 60TB-nyi winxp-s WIM image-el kell valamit kezdenem :)
Nem nagyon látok rá más alternatívát...
egy picit parázok attól hogy valamilyen módon sérülhet a deduplikált adathalmaz,
ezért időnként újrakezdem majd a deduplikálást, ill. az összegyűlt adathalmazt kidumpolom és lementem TSM kazira :)

Csinálj egy tesztet. Mentés előtt több user, acl-ek keresztbe-kasul. mentsd le, csomagold ki, majd próbálj a kicsomagolt kupacból visszaállítást csinálni - először csak adatokat, aztán ha az sikeres (userek, acl-ek, minden klappol), akkor az OS-t is.
Ha bármi nem stimmel, akkor más megoldást kell keresned, mert a mentés arra való, hogy vissza lehessen állítani a mentés készítésekor fennálló állapotot. És ebbe a jogosultságok is beletartoznak, nem csak a fájlok nyers tartalma.

( Psycho v | 2013. 01. 04., p – 17:20 )

Windows 2012 Server-ben van alapból block szintű dedup. Egy kb. 900GB fájlszerveren a megtakarítás 390GB volt. Szóval eléggé hatásos volt.

( dblaci | 2013. 01. 05., szo – 17:20 )

Egy ötlet, de nem ez lesz a megoldás, de hátha gondolatot ébreszt:

a btrfs ben nincs utólagos deduplikálás (hivatalosan), de snapshotot lehet csinálni. Szóval fogsz egy imaget, ami az etalon lesz. Subvolume ba belemásolod. Snapshot, majd rsync --inplace el rásynceled a másodikat, és így tovább. Persze ez csak akkor jó, ha amiről készíted, azzal tényleg sok a közös rész.

( ngm.hun | 2013. 01. 11., p – 17:55 )

Szerintem a 7zip is megér egy próbát.

( spider | 2013. 01. 18., p – 17:49 )

Windows Server 2012 alatt leteszteltem a deduplikációt.
Első körben sima NTFS fájlrendszerrel ill. 4KB-os clusterrel 80% fölött járt a helymegtakarítás.
Ebben az esetben 60GB helyet foglalt a tesztadat deduplokálva, ebből 40GB a hivatkozásokból állt (a 4KB-os clusterméret miatt)
Aztán lecsökkentettem a cluster méretét 512bájtra, hogy a hivatkozások mérete csökkenjen
így ha minden jól megy, akkor 92% fölött lesz a helymegtakarítás, azaz kevesebb mint 5TB-ra tömörül a 60TB adat :)

nyilván vannak hátrányai az 512 bájtos clusternek... részben a lassulás, részben a maximális fájlméret csökkenése
(ha jól tudom 2GB-nál nem használhatunk nagyobb fájlt)
viszont ez a két hátrány nekünk nem lényeges igazán

Én a ZFS-el is elégedett voltam, bár a szintén 4KB-os clusterméret miatt itt is sok helyet foglaltak a hivatkozások.
Sajnos az EXT3-as partíció minimum 1KB-os clusterrel dolgozik.
Tehát vagy dupla akkora lesz a hivatkozások mérete, vagy meg kell próbálni az NTFS fájlrendszert ZFS-hez is.
Végül azért marad inkább a windows-os megoldás, mert a kollégáim kissé idegenkednek a Linuxtól.
Viszont jövő héten csinálok majd egy összehasonlítást.
Egyrészt arra is kíváncsi vagyok hogy a ZFS hajlandó-e 512bájtos cluster mellett NTFS partícóra deduplikálni.
Ha igen, akkor kb. hasonló eredményeket várok.

Egyébként a tömörítetlen WIM-el sem tudott mit kezdeni a ZFS, de tartok tőle hogy a windows-os dedup sem tud.
Ahogy írtam is már, 7zip-el kicsomagoltuk az image-eket, és azokat másoljuk fel.
Kb. 2x akkora méretű fájlkupacot kapunk a tömörítés után.
A windows-os dedup előnye, hogy a 100-nál többször használt fájlokat 2x tárolja.
Különbség még az is, hogy a ZFS azonnal elvégzi a deduplikációt a másoláskor, a windows-os dedup utólagos feldolgozást csinál.

Már csak annyi hiányzik, hogy ki tudjuk dumpolni a dedupos partíciót. A dumpot pedig mentjük majd TSM-el szalagra.
Ehhez találtam is egy "windd" nevű alkalmazást.

Visszallitasi tesztet is csinaltatok?
Leirod vegre, miert nem jo, ha atkonvertalod az image-eket vmi tomoritetlen formara, mint ahogy azt fent irtak? Engem pl. erdekelne, menyit nyersz a kitoromoritessel azzal szemben, mintha vmilyen deduplikalhato es tomoritetlen image formatummal dolgozol.

tompos

A WIM-ből lehet tömörítetlen WIM-et csinálni imagex-el, de akkor pont akkora lesz a mérete a fájlnak, mint ha kitömöríteném 7zip-el.
Az ACL tényleg sérül, bár ez nekünk valószínűleg nem jelent gondot, mivel az alap jogosultságok azért átmennek dedup után is.
Visszaállítási tesztet még nem csináltunk, de hamarosan az is lesz.
Kipróbáltam, és ez a windows-os dedup tudja deduplikálni a tömörítetlen WIM-et. Sajnos a ZFS nem tudta.
Egy nagyobb tesztet csinálunk majd tömörítetlen WIM fájlokkal is, egyelőre csak 5 image-el teszteltem.

3,42GB -> 1,33GB (41% SavingsRate)
Ez jelentősen fog még javulni. Az 1,3 GB nem olyan rossz szám, mivel az első C és D image mérete 1,1GB-volt, erre küldtem rá még 2db D és egy C image-et.
Ezekből már csak 200MB került tárolásra.

Amint vége a nagyobb tesztnek, írok annak az eredményéről is.

A legutolsó teszt eredménye:

328GB image 7zip-el kitömörítve 600GB-lett
ezt deduplikáltuk... a lefoglalt terület 37,1GB lett.
az eredeti tömörített WIM-ek méretéhez képest 11,3%-os lett a helyfoglalás, a kitömörítés utáni mennyiséghez képest 6,18%
Az arány lehetne jobb is, mivel a 32KB-nál kisebb fájlok nem kerültek deduplikálásra, így sajnos van némi veszteség.
Sajnos a minimumfilesize változót nem lehet 32KB alá állítani.
Tehát ezzel együtt kell hogy éljünk.

Tegnap kiexportáltunk imagex-el 545GB image-et, az így kapott WIM-eket ma reggelre sikerült deduplikálni.
545 GB-ot 11GB-on sikerült tárolni. Ami kb. 98%-os helytakarékosságnak felel meg.

A probléma már csak az, hogy nem találok megoldást az online feldolgozásra.
Tud valaki arról, hogy lehet-e online feldolgozás csinálni?
Ha online fel lehetne dolgozni az adatokat, akkor használhatnánk SSD meghajtókat az adatok tárolására.
500MB/s azért mégiscsak 500MB/sec :) tény hogy az 512 bájtos cluster miatt nem lenne olyan gyors.

A másik kérdésem: 512 bájtos clusterméretet használunk, ha jól tudom akkor max 2TB-os partíciót lehet létrehozni ekkora clustermérettel.
Ez még nem gond, 1TB elég nekünk. A maximális fájlméretre van valamilyen kikötés?
Mint ha valahol azt olvastam volna hogy 2GB-nál nem használhatok nagyobb fájlokat.
Sajnos erről nem találtam semmi infót.