Große Dateien vergleichen

[Gast2]

Moin,

ich habe eine Datei 20 GB, 40GB ggf. noch mehr ... wenn ich davon jetzt ein Backup machen will, dann kann ich entweder die ganze Datei kopieren oder ich übertrage nur die Blöcke die sich geändert haben ... logischer Weise ist die letztere Variante die bessere

nun wollte ich die Datei in (ca.) 1MB große Blöcke unterteilen und pro Block eine MD5-Summe erstellen und die mit den MD5-Summen des Backups vergleichen ... allerdings ist das Berechnen der MD5 Summen Zeitaufwendig ... also dachte ich hier an CRC32 - braucht etwas weniger CPU ... aller Dings vermute ich das mit kleinerer Hash-Zahl (Bit-Breite) die Wahrscheinlichkeit steigt das ein Block mit geändertem Inhalt denn noch den gleichen CRC32-Hash liefert -> und damit nicht kopiert wird

da meine Fähigkeiten in Sache Verschlüsselung sich auf die Grundlagen beruhen - ist gut & wichtig - wollte ich mal nach Fachmeinungen fragen die sich damit besser aus kennen

danke, mogel

 

[XHelp]

Wie teilst du denn die Datei? Also im Grunde denke ich nicht, dass es Sinn macht es so zu machen.
Bei CRC32 hast du ja 16^8 Möglichkeiten. Allerdings gibt es mehr Möglichkeiten eine 1mb große Datei zu füllen... Deswegen kann es eine Chance, dass es doppelt vorkommt. Aber ich denke nicht, dass es dazu kommt, denn nicht alle Möglichkeiten ergeben einen Sinn. (Notfalls kannst du noch die ersten und letzten paar Zeichen des Blocks speichern um sicher zu gehen).

Aber wie gesagt, ich denke nicht, dass es viel schneller und besser mit deiner Variante ist...

 

[Geeeee]

Muss das portabel sein? Wohl eher nicht, oder?
Man könnte einfach eine md5sum-binary nutzen. Evtl. hast du da einen gewissen Zeitvorteil. Bezug auf CRC32 würde ich auch sagen, dass die Chance da sehr, sehr, (...) gering ist, um da ein Duplikat zu finden.
Wie lange läuft da eigentlich ein diff drauf? Würde mich mal interessieren.

 

[ice-breaker]

Also vor allem würde mich interessiere, was bei dir soviel Zeit benötigt? Ist es wirklich das berechnen des MD5-Wertes?
Wenn ja könnte man ja eventuell auf eine nicht kryptographische Hashfunktion ausweichen, die sind um einiges schneller: Wahl einer geeigneten Hash-Funktion

 

[Gast2]

Wie teilst du denn die Datei?

pauschal erster MB, dann zweiter MB und so weiter

Aber ich denke nicht, dass es dazu kommt, denn nicht alle Möglichkeiten ergeben einen Sinn.

die Daten ergeben von Anfang an keinen Sinn - sind Binärdaten auf die ich keinen Einfluss habe ... die werden auch willkürlich innerhalb der Datei geändert ... daher der Check was kopiert werden muss

Muss das portabel sein? Wohl eher nicht, oder? Man könnte einfach eine md5sum-binary nutzen.

was meinst Du damit?

Bezug auf CRC32 würde ich auch sagen, dass die Chance da sehr, sehr, (...) gering ist, um da ein Duplikat zu finden.

ja, aber die Möglichkeit eines Duplikates ist da - und genau deshalb habe ich "Bauchschmerzen" ... und wenn das Orginal kaputt ist und er im backup ein Fehler hat, ist alles im Eimer - weil er durch ein Duplikat im Hash der Meinung war "passt alles" ... dann ist der Kunde (nicht nur) unglücklich

Wie lange läuft da eigentlich ein diff drauf? Würde mich mal interessieren.

ich weis jetzt nicht ob diff binär kompatibel ist - afaik aber nein

 

[Geeeee]

was meinst Du damit?

md5sum auf der (linux)console aufrufen und die Laufzeit vergleichen. Evtl. kann dir das schon alles Kopfzerbrechen ersparen.
Kannst den call ja dann in java wrappen

 

[Gast2]

ahh - geht aber nicht ... zum einen ist es Windows ... zum anderem liefert mir md5sum ja für die ganzen GB ... ich mag aber nicht jedesmal dioe ganze Datei übertragen - sonderen eben nur die geänderten Blöcke

 

[kama]

Hallo,

geht es jetzt darum die Datei zu übertragen mit eigenen Mitteln in Java oder würde auch so etwas wie rsync helfen...

EDIT: Wenn Du es selbst machen möchtest würde ich die Blöcke deutlich größer machen 64 oder 128 MiB.....

Gruß
Karl Heinz Marbaise

 

[XHelp]

Hat weniger mit Java zu tun, aber vllt wäre für den Zweck eine SSD sinnvoller...

 

[ice-breaker]

Hat weniger mit Java zu tun, aber vllt wäre für den Zweck eine SSD sinnvoller...

wie du sagst ist der Kommentar wirklich total sinnvoll Zumal es sich um Backups dreht, wer Backups solch einer Größe auf SSDs packt, hat einfach zuviel Geld.

@mogel: Meinen Post gelesen?

 

[Gast2]

geht es jetzt darum die Datei zu übertragen mit eigenen Mitteln in Java oder würde auch so etwas wie rsync helfen...

ich habe mir das jetzt mal angeschaut - scheint aber nur mit cygwin zu funktionieren ... damit ist es mehr oder weniger wieder unbrauchbar ... Kunden & Installieren & so

Wenn Du es selbst machen möchtest würde ich die Blöcke deutlich größer machen 64 oder 128 MiB.....

dann wird aber ggf. ein Haufen nicht geänderter Daten mit übertragen ... da die Übertragung teilweise UMTS sein kann, würde ich gerne wirklich nur das Minimum an Änderungen übertragen (im Idealfall nur die geänderten bytes )

Meinen Post gelesen?

hatte ich erst übersehen ... interessanter Link - Bookmark

wie du sagst ist der Kommentar wirklich total sinnvoll Zumal es sich um Backups dreht, wer Backups solch einer Größe auf SSDs packt, hat einfach zuviel Geld.

... scheint aber wirklich an der Festplatte zu liegen (was auch Sinn macht - 20 GB hat keiner im Speicher) ... ich habe gestern Abend nochmal 512 MiB mit MD5 gehasht - knapp 1.3 Sekunden ... da ich hier eine SSD drinnen habe, habe ich nicht noch mit der Platte getestet ... werde ich auf Arbeit mal machen - dann werde ich aber feststellen das wirklich die Festplatte das Zeitloch ist (mal wieder)

bis hierher erstmal Danke, mogel

 

[Marcinek]

Hallo,

du kannst auch md5 checksummen mit java machen, dafür brauchst du weder linux noch was anderes.

Ich weiß nicht, ob man bei so großen binärdateien sinnvoll ist diese zu partizionieren und dann die geänderten Blöcke zu backupen.

Sind das VM Festplatten, die du backupen willst? - I.d.R. haben die entsprechenden HostSysteme eine Möglichkeit spiegel auch beim laufenden betrieb zu ziehen.

Wenn das Gastsystem etwas auf seiner virteullen Platte verschiebt => Änderen sich viele Stellen der 20000 MB

 

[kama]

Hallo,

Haufen nicht geänderter Daten mit übertragen ... da die Übertragung teilweise UMTS sein kann, würde ich gerne wirklich nur das Minimum an Änderungen übertragen (im Idealfall nur die geänderten bytes )

Ah...jetzt haben wir ja ganz andere Requirements...

Dann würde ich es so machen...und zwar eine Datei mit Referenzen auf Dateien die übertragen werden sollen.

Dann eine Datei pro zu übertragenender Datei mit einer Kennung für die Blöcke die geändert sind..(z.B. 1 MB blöcke)...

Wenn dann ein Block geändert ist, kannst Du den block nochmal kleiner unterteilen (z.B. 10 KiB blöcke) und dann das geänderte Übertragen...

Das Problem ist ja auch, dass man auf der anderen Seite auch etwas braucht, dass mit der Stückelung klar kommt...

Gruß
Karl Heinz Marbaise

 

[Gast2]

Sind das VM Festplatten, die du backupen willst?

leider nein - sonst wäre es ja einfach ^^

Dann eine Datei pro zu übertragenender Datei mit einer Kennung für die Blöcke die geändert sind..(z.B. 1 MB blöcke)...

genau das ist das Hauptproblem - wie erzeuge ich die Kennung ... egal welchen Hash ich nehme, irgendwann kommt eine Collision ... sprich - der Hash ist gleich aber der Inhalt ist anders -> kein Backup (worst-case: kaputtes Backup muss verwendet werden) ... bis zum Test gestern Abend ging ich davon aus das MD5 zuviel Zeit benötigt (aber ist ja nun anscheinend die Festplatte) - daher die Suche nach anderen sinnvollen Hash-Funktionen ... der Link von ice-breaker ist sehr aufschlussreich für Alternativen ... dummerweise arbeiten die Hash alle mit Überlauf - was unter Java bzw. C# zu Problemen führen dürfte :autsch:

Wenn dann ein Block geändert ist, kannst Du den block nochmal kleiner unterteilen (z.B. 10 KiB blöcke) und dann das geänderte Übertragen...

das ist eine gute Idee ... zu gut um selber drauf zu kommen ... sollte ggf. viel Traffic sparen

Das Problem ist ja auch, dass man auf der anderen Seite auch etwas braucht, dass mit der Stückelung klar kommt...

da habe ich zu 100% freie Hand - das Problem wird sich also in Luft auflösen :toll:

hand, mogel

 

[ice-breaker]

der Link von ice-breaker ist sehr aufschlussreich für Alternativen ... dummerweise arbeiten die Hash alle mit Überlauf - was unter Java bzw. C# zu Problemen führen dürfte :autsch:

das kannst du aber auch mit Java implementieren Wo ist denn genau dein Problem?

 

[kama]

Hallo,

genau das ist das Hauptproblem - wie erzeuge ich die Kennung ... egal welchen Hash ich nehme, irgendwann kommt eine Collision ... sprich - der Hash ist gleich aber der Inhalt ist anders -> kein Backup (worst-case: kaputtes Backup muss verwendet werden) ... bis zum Test gestern Abend ging ich davon aus das MD5 zuviel Zeit benötigt (aber ist ja nun anscheinend die Festplatte) - daher die Suche nach anderen sinnvollen Hash-Funktionen ... der Link von ice-breaker ist sehr aufschlussreich für Alternativen ... dummerweise arbeiten die Hash alle mit Überlauf - was unter Java bzw. C# zu Problemen führen dürfte :autsch:

Wie wäre es mit SHA1 ? (Git verwendet das Ding)...

Wie groß ist die Wahrscheinlichkeit von Kollisionen ?
Gruß
Karl Heinz Marbaise

 

[Sekundentakt]

Ich empfehle Dir mal den Wikipedia-Artikel zu Merkle-Trees.

Kurze Zusammenfassung:
Ein Merkle-Tree ist, wie der Name schon sagt, eine Baumstruktur.
In der Wurzel speichert der Merkle-Tree einen Hash aller zu betrachtenden Daten - in deinem Fall die md5-Summe der Datei.
Bezogen auf Dein Beispiel geht's dann ins Detail: Die ersten 50% und die letzten 50% deiner Datei werden gehasht.
Und immer so weiter.
Diese Hash-Summen werden dann Schritt-für-Schritt miteinander im Falle eines Backups verglichen.

Amazon Dynamo arbeitet zum Beispiel auf diese Weise - näheres kannst Du dir aus dem verlinkten Artikel herausziehen.