Einer Datei eine eindeutige ID zuweisen (a lá md5)

fledermausland · Dienstag 2. Februar 2010, 11:06

Guten morgen allerseits.

Gerade stoße ich auch ein nicht unerhebliches Problem: da viele Dateien in einer Datenbank indiziert werden sollen, soll dort dort als eine Art "ID" etwas gespeichert werden was diese Datei eindeutig bestimmt. Der erste Gedanke ist natürlich der md5-hash, nur ist das etwas unpraktisch, da die Dateien in der Regel zwischen 2 und 2000 MB groß sind (kleinere Dateien kommen nicht vor) und das hashen einer 500Mb-Datei gut und gern eine Sekunde dauert.
Nun fallen mir folgende Möglichkeiten ein:

- die Datei teilweise hashen, z.B. das erste, das mittlere und das letzte Mb (ist die Kollisionsfreiheit dann überhaupt noch wahrscheinlich?). Habe leider keine Idee, wie das zu bewerkstelligen ist.

- sich einen eigenen, flotten Hashalgorithmus basteln. Da es sich um maximal 1000 Dateien handelt, würde ein gröberer Algorithmus reichen. Das werde ich später mal ausprobieren, allerdings glaube ich selber nicht so recht das eine Pythonversion das in annembarer Zeit schaffen könnte.

Nun, das sind keine tollen Einfälle. Was habt ihr denn für Ideen?

Nachtrag: über den Inhalt der Datei zu gehen ist eigentlich unumgänglich, da das Ganze unabhängig von Ort, Name und darunterliegendem Dateisystem funktionieren muss.

Pekh · Dienstag 2. Februar 2010, 11:25

Bei 1000 Dateien mit max. 2000MB und 1s für 500MB hast du lt. eigenen Aussagen eine maximale Laufzeit von rund 70min. Für eine einmalige Aktion würde ich das noch akzeptabel finden. Der Aufwand, eine bessere Lösung zu finden dürfte höher liegen.

Die Frage wäre nun, wie oft du in diesen Größenordnungen Dateien hinzufügen willst.

Zap · Dienstag 2. Februar 2010, 12:00

Was wird denn konkret in der Datenbank eingetragen, der Pfad zu der original Datei oder der Dateninhalt selber als BLOB?
Ich kann mich irren, aber vielleicht unterstützten einige Datenbanken eine Eindeutigkeitsprüfung für BLOBS. (Mehr als Frage zu verstehen)

Hyperion · Dienstag 2. Februar 2010, 13:03

fledermausland hat geschrieben: Nachtrag: über den Inhalt der Datei zu gehen ist eigentlich unumgänglich, da das Ganze unabhängig von Ort, Name und darunterliegendem Dateisystem funktionieren muss.

Du redest doch vom Indizieren - daher verstehe ich nicht, inwiefern der Pfad nicht als Identifikator ausreicht? Eine URI ist ja gerade eindeutig

(Ob Du den Pfad dann ggf. noch hashen magst, weil dieser als Plain-Text unhandlich ist, wäre dann noch eine andere Frage.)

Wie willst Du denn sonst die Dateien wiederfinden? Was meinst Du hier mit indizieren? Auf welches "Merkmal" willst Du denn abbilden?

Summa summarum ist mir nicht klar, was der Zweck des Indizierens ist, wenn das Dateisystem als Abbildung ausscheidet.

fledermausland · Dienstag 2. Februar 2010, 13:14

Pekh hat geschrieben:Bei 1000 Dateien mit max. 2000MB und 1s für 500MB hast du lt. eigenen Aussagen eine maximale Laufzeit von rund 70min. Für eine einmalige Aktion würde ich das noch akzeptabel finden. Der Aufwand, eine bessere Lösung zu finden dürfte höher liegen.

Das mag sein, aber es sollte flexible sein und außerdem geht's mir mittlerweile auch ums Prinzip

Zap hat geschrieben: Was wird denn konkret in der Datenbank eingetragen, der Pfad zu der original Datei oder der Dateninhalt selber als BLOB?

BLOB gibt's in der Datenbank nicht, da selbstgeschrieben.

Hyperion hat geschrieben:Du redest doch vom Indizieren - daher verstehe ich nicht, inwiefern der Pfad nicht als Identifikator ausreicht? Eine URI ist ja gerade eindeutig

Eben nicht. Es ist nicht ganz leicht zu beschreiben, aber vereinfacht geht es darum, dass Dateien praktisch 'getaggt' werden können, mit allerhand Eigenschaften. Das soll völlich unabhängig vom Ort der Datei geschehen. Wenn eine Datei also verschoben wird, dann merkt das Programm zwar "hoppla, jetzt ist sie weg", aber da es eh ständig nach neuen Dateien des gewünschten Typs schaut, merkt es dann, wenn es die alte Datei wiederfindet. So muss in der DB dann nur der Pfad angepasst werden. Abgesehen davon könnte ich sonst problemlos die Datei "/home/fledermaus/file.py" gegen eine andere austauschen, ohne dass die Anwendung das merkt. Das möchte ich nicht.

Nachtrag: vielleicht wird es klarer, wenn ich es so beschreibe:
die DB hat das Schema

Code: Alles auswählen

#hash                         path                   tag1        tag2
9z3fhiuh23f9832zf3hf9823      /usr/bin/blubb.tar     foo         bar

usw..

Und das ganze soll nicht darauf angewiesen sein, dass der Benutzer oder das System niemals irgendwelche Dateien hin und herschiebt.

Nachtrag 2:
Auf allerunterster Ebene könnte man sich das wohl sparen, da beim Verschieben von Dateien nur der Link verändert wird, während die phys. Adresse gleich bleibt, oder irre ich mich da?

jens · Dienstag 2. Februar 2010, 15:15

man könnte sich evtl. den Hash sparen, bei allen Dateien die eine eindeutige größe haben.
Weiß nicht ob man unter Linux bzw. dem verwendeten Dateisystem die I-Node speichern könnte.

Zap · Dienstag 2. Februar 2010, 15:25

jens hat geschrieben:man könnte sich evtl. den Hash sparen, bei allen Dateien die eine eindeutige größe haben.

Eindeutige größen ist meiner Meinung nach keine Randbedingung die man sicherstellen kann/sollte.

jens · Dienstag 2. Februar 2010, 15:26

Probleme gibt es natürlich, wenn eine neue Datei dazu kommt, die exakt gleich groß ist, wie eine vorhandene

fledermausland · Dienstag 2. Februar 2010, 15:45

Hm. Man könnte es aber immerhin umdrehen und sagen: wenn die Dateigröße noch nicht in der DB vorhanden ist, dann ist es definitiv eine unbekannte Datei. Ansonsten ist es eventuell eine bekannte.

Hyperion · Dienstag 2. Februar 2010, 15:55

Die Lösung ist doch recht einfach: Da Du die Datei vollkommen aus dem Zusammenhang heraus identifizieren willst, musst Du über einen Wert gehen, der auch vollkommen aus dem Zusammenhang heraus eindeutig ist - da fällt mir nur ein Hashwert ein!

fledermausland · Dienstag 2. Februar 2010, 15:57

jens hat geschrieben:man könnte sich evtl. den Hash sparen, bei allen Dateien die eine eindeutige größe haben.
Weiß nicht ob man unter Linux bzw. dem verwendeten Dateisystem die I-Node speichern könnte.

Oh, na klar! Die shell macht das mit `ls -i`. Das ist schonmal super! Aaber... wie wahrscheinlich ist es, dass, wenn man eine Datei löscht, es danach eine andere, neue Datei an dem gleichen Inode gibt? Sehr klein, oder? Ich wundere mich nur, weil dort teilweise sehr kleine Zahlen auftauchen (607, 128, ...).
Schon mal vielen Dank soweit.

fledermausland · Dienstag 2. Februar 2010, 15:58

Hyperion hat geschrieben:Die Lösung ist doch recht einfach: Da Du die Datei vollkommen aus dem Zusammenhang heraus identifizieren willst, musst Du über einen Wert gehen, der auch vollkommen aus dem Zusammenhang heraus eindeutig ist - da fällt mir nur ein Hashwert ein!

Ja, schon. Aber es muss doch etwas schnelleres geben? Die Datei z.B. nur bruchstückhaft zu hashen oder so. Bis die ganzen 500Mb gehasht sind, das dauert mir zu lange.

Hyperion · Dienstag 2. Februar 2010, 16:14

fledermausland hat geschrieben: Ja, schon. Aber es muss doch etwas schnelleres geben?

Wieso muss?

Die Datei z.B. nur bruchstückhaft zu hashen oder so. Bis die ganzen 500Mb gehasht sind, das dauert mir zu lange.

Die Leute, die sich Hash-Formeln ausdenken sind ja durchaus fit - wenn es einen extrem schnellen, aber dennoch richtig sicheren (im Sinne von Kollsionen) Weg geben sollte, gäbe es den sicher

jens · Dienstag 2. Februar 2010, 16:20

fledermausland hat geschrieben:es muss doch etwas schnelleres geben? Die Datei z.B. nur bruchstückhaft zu hashen oder so. Bis die ganzen 500Mb gehasht sind, das dauert mir zu lange.

Nur bruchstückhaft Hashen macht so keinen Sinn. Aber man könnte in Blöcken Hashen. Dann kann man abbrechen sobald der erste Block anders ist. Dennoch könnte es vorkommen, das man die gesamte Datei hashen muss, wenn nur am Ende was anderes drin ist.
Allerdings findest du so keine Dateien wieder.

Ob ein inode wieder frei wird, wenn die Datei gelöscht sind, weiß ich nicht.
Wie wäre es mit inode + Datei größe + hash von den ersten X-Bytes ?
Wobei dennoch kollisionen nicht 100%tig ausgeschlossen werden könnten.

Hyperion hat geschrieben:Die Leute, die sich Hash-Formeln ausdenken sind ja durchaus fit - wenn es einen extrem schnellen, aber dennoch richtig sicheren (im Sinne von Kollsionen) Weg geben sollte, gäbe es den sicher

Der Flaschenhals liegt wohl eh bei der Festplatte nur nicht beim Hash-Algo.

BlackJack · Dienstag 2. Februar 2010, 17:49

Also ich würde ja sagen die ganze Datei hashen ist hier die einzig wirklich sinnvolle und halbwegs sichere Möglichkeit. Und da würde ich dann auch eher einen wahrscheinlich langsameren Algorithmus als MD5 wählen, der einen Hashwert mit mehr Bits ausrechnet, denn der limitierende Faktor dürfte wirklich der Plattendurchsatz und nicht die Hashberechnung sein.

Von inode-Nummern würde ich die Finger lassen. Wie die vergeben, und vor allem auch wieder neu vergeben werden, ist letztendlich ein Implementierungsdetail des Dateisystems. Nicht alle Dateisysteme haben so etwas überhaupt, es gibt auch welche die "simulieren" die bloss. Ich wüsste so auf Anhieb noch nicht einmal ob die nach Standard persistent eindeutig sein müssen, oder ob es nicht reicht, dass sie eindeutig sind, solange das System läuft.

Die Dateigrösse könnte man natürlich zu Optimierungszwecken noch zusätzlich speichern. Und vielleicht auch noch einen Hash über die ersten paar MB, die vielleicht ausreichen um eine Datei eindeutig zu identifizieren.

heiliga horsd · Dienstag 2. Februar 2010, 20:56

Entschuldigt bitte, falls ich störe, aber ich hätte da etwas anzumerken:

jens hat geschrieben:[...]

Ob ein inode wieder frei wird, wenn die Datei gelöscht sind, weiß ich nicht.

[...]

Das kommt auf das Dateisystem an. Bei ext3 wird der Inode nicht komplett gelöscht, d.h. bspw. Datenwiederherstellung ist durchaus (aufwändig!) möglich. Wie sich das bei ext2, ext4, btrfs o.ä. verhält kann ich nicht sagen, hier hilft evtl. Wikipedia weiter. Falls das ganze aber sowieso Plattformunabhängig (also auch Dateisystemunabhängig) arbeiten soll, kommt ihr meiner Meinung nach mit Inodes nicht weit.