Dateien über Hash identifizieren
-
Hallo,
ich arbeite gerade an einem Serverprogramm, dass die Verwaltung von MultimediaDateien ermöglicht, für diese Frage hier gehe ich mal nur von mp3 aus, aber eigtl. ist das egal.
Ich möchte alle Metainformationen zu den mp3's, also die Daten des idv und den Pfad zur Datei in einer Datenbank ablegen.
Um die Einträge der Datei auch zuordnen zu können, wenn diese umbenannt, verschoben oder der idv-Tag verändert wird, dachte ich mir man könnte einen Hash des reinen Musikteils der Datei machen und diesen in die Datenbank ablegen.
So würden Playlists, die diesen Hash zur Dateiidentifizierung enthalten auch noch funktionieren, wenn die Datei umbenannt oder verschoben wird.Mein Problem ist nun, ich brauche einen möglichst Kollisionsfreien Hash-Algorithmus, weil ich ja nicht die Möglichkeit habe, z.B. in der Hashtabelle eine LinkedList anzulegen, denn ich will ja die Datei anhand ihres Hashwertes identifizieren, oder seh ich das falsch? D.h. wenn zwei Dateien den selben Hashwert haben sollten, hab ich ein Problem.
Danke für jede Hilfe
-
Ach noch was, ist es für die Eindeutigkeit des Hashwertes von bedeutung, ob ich die Datei in 4 gleiche Teile aufteile, und davon jeweils einen 8bit Hashwert produziere, und diese 4 dann aneinanderreihe zu einem 32bit wert, oder ob ich gleich einen 32bit Wert aus der ganzen Datei erzeuge?
-
CGI-BIN schrieb:
Ach noch was, ist es für die Eindeutigkeit des Hashwertes von bedeutung, ob ich die Datei in 4 gleiche Teile aufteile, und davon jeweils einen 8bit Hashwert produziere, und diese 4 dann aneinanderreihe zu einem 32bit wert, oder ob ich gleich einen 32bit Wert aus der ganzen Datei erzeuge?
nee. ist nicht so schlimm gefährdet. aber dur verschlechtest damit das hashverfahren schon ungemein damit. denn lokale fehlerbursts schlagen sich nur noch auf 8 bits durch statt auf alle 32. würd ich lassen, zumal es keinen grund für solcherlei vorgehen gibt.
-
CGI-BIN schrieb:
Mein Problem ist nun, ich brauche einen möglichst Kollisionsfreien Hash-Algorithmus, weil ich ja nicht die Möglichkeit habe, z.B. in der Hashtabelle eine LinkedList anzulegen, denn ich will ja die Datei anhand ihres Hashwertes identifizieren, oder seh ich das falsch? D.h. wenn zwei Dateien den selben Hashwert haben sollten, hab ich ein Problem.
also reichen 32 bits nicht aus. aber naja, nimmste halt crc64 und gut ists. md5 und sha1 sind für krypto-sachen. also wenn du auch willst, daß böswillige dateiveränderer dein system nicht ärgern können.
edit: natürlich reicht crc32, denn sofort nach dem hasten machste ja noch modulo hashtablesize und kommst auf winzige zahlen.
kollissionsfrei muß dein verfahren gar nicht sein, wenn du als key den hast-wert der musikdaten und als value die id3-tags und auch den dateinamen mit vollem pfad hast. dann kannste ganz herkömmlich ne hashtable bauen und im falle der gleichheit das auch feststellen (und irgendwo speichern, daß diese beiden dateien in ihrem musik-anteil bis hinten hin gleich sind, damit du nur einmal das machen musst.)
-
wenn Du wirklich die Eindeutigkeit haben willst, verwende MD5. Damit ist die Wahrscheinlichkeit verschwindend gering das zwei unterschiedliche Dateien auf einen Wert abgebildet werden.
-
@volkard: ich will ja gerade nicht die datei über ihren dateinamen erkennen.
und ich wollte das auch nicht wie beid er üblichen hashtable gleich als index nehmen, sondern den wert nur in eine sql datenbank eintragen, also schon noch ne suche nach dem wert machen, wenn ich die infos zu einer datei will.sicherheitsaspekte sind völlig unwichtig, d.h. wenn man die Daten aus dem Hash wiederhesrtellen könnte wär selbst das egal, es geht mir nur um die eindeutige Erkennung einer Datei.
Kann CRC das leisten? Dachte das ist nur eine Prüfsumme mit mittelmäßiger Eindeutigkeit. was ist performanter zu realisieren, CRC oder MD5, weil ich ja nicht 2 Stunden lang meine Mp3's scannen will.Und eine letzte Frage: Ist es ein signifikanter unterschied in der eindeutigkeit, ob ich nur das erste sagen wir 1MByte oder die ganze Datei hashe?
Wenn ich die ganze mache wirds zwar ein enderer wert, aber der kann ja auch wieder mit ner anderen datei übereinstimmen.
-
d.h. wenn man die Daten aus dem Hash wiederhesrtellen könnte wär selbst das egal, es geht mir nur um die eindeutige Erkennung einer Datei.
Nein nein, Wiederherstellen von Daten kannst du eh vergessen. Es geht eben um die Eindeutigkeit. Bei CRC ist es eben leicht möglich Daten mit gleichem Hash zu erzeugen. Ich weiß nur nicht wie die Wahrscheinlichkeit ist, dass du zwei Dateien mit gleichem Hash hast.
volkard schrieb:
md5 und sha1 sind für krypto-sachen. also wenn du auch willst, daß böswillige dateiveränderer dein system nicht ärgern können.
mittlerweile nicht mehr :p
-
genau nach diesem kriterium, nämlich die wahrscheinlichkeit dass zwei dateien den gleichen hash haben, suche ich. Gibts da ne übersicht, welche funktionen da anderen überlegen sind? einzig der rechenaufwand wäre noch ein weiteres kriterium, sicherheitsaspekte brauch ich nicht zu beachten, ich will ja ein readonly medienserver bauen, dass die daten auf der platte nicht verändert werden muss anders sichergestellt werden.
-
CGI-BIN schrieb:
@volkard: ich will ja gerade nicht die datei über ihren dateinamen erkennen.
hab ich ja auch nicht vorgeschlagen. ich wollte sie am hash erkennen und nur bei kollisionen dann den musikdatenteil nochmal vergleichen.
und ich wollte das auch nicht wie beid er üblichen hashtable gleich als index nehmen, sondern den wert nur in eine sql datenbank eintragen, also schon noch ne suche nach dem wert machen, wenn ich die infos zu einer datei will.
aha. dann muß dein hash-value einfach möglichst viele bits haben. crc ist denke ich das schnellste. und mit 64 bits haste auch wenig kollissionswahrscheinlichkeit. md5 gibt 128 bits aus. ist aber relativ lahm.
sicherheitsaspekte sind völlig unwichtig, d.h. wenn man die Daten aus dem Hash wiederhesrtellen könnte wär selbst das egal, es geht mir nur um die eindeutige Erkennung einer Datei.
widerherstellen eh nicht. für einen geschickten mogler ist es aber leicht, den datenteil der datei "fotzenleck.mp3" so zu verändern, daß sie genau den gleichen hash wie die "radetzkimarsch.mp3" hat. er könnte so vielleicht viel herzinfarke in deutschland verursachen.
Und eine letzte Frage: Ist es ein signifikanter unterschied in der eindeutigkeit, ob ich nur das erste sagen wir 1MByte oder die ganze Datei hashe?
na, es ist ärgerlich, wenn ich keinen unterschied mehr zwischen der "radetzkimarsch.mp3" und der "radetzkimarasch-demo-kostenlos-nur-erste-minute.mp3" sehe. aber das wäre ja leicht zu beheben, indem du an den hash auch noch die länge des musikdatenteils hängst und so nen längeren key machst. aber ich denke nicht, daß das so viel bringt. ob du nun 1M scanst oder 5M.
andererseits, du wirst jedes fitzelchen performance brauchen. so 30G mp3s sind nicht in 10 minuten gescant, das nervt den user schon ein wenig.
-
hab ich ja auch nicht vorgeschlagen. ich wollte sie am hash erkennen und nur bei kollisionen dann den musikdatenteil nochmal vergleichen.
Ja, das kann ich aber nur machen, wenn alle Dateien von Anfang an im Verzeichnis vorhanden sind, und ich damit erkenne, das es zwei gleiche gibt. Wenn ich beim ersten scannen keine kollisionen habe, speichere ich mir ja keine weiteren daten außer dem hash wert. jetzt wird eine datei gelöscht, und eine neue der sammlung hinzugefügt, die zufällig den gelichen hashwert hat. beim nun folgenden 2. scann, wird nicht erkannt, dass das jetzt eine andere datei ist.
Dass seh ich doch richtig, oder? Ich bracuh die kollidierenden dateien zur gleichen zeit, sonst funktioniert das nicht, mit musikvergeleichen.Ich werde sowieso einen vollen scann nur beim ersten start machen, danach dann während der laufzeit die verzeichnisse mit inotify unter linux bzw. dem .NET überwachungsdings unter windows beobachten, und bei einem neustart die zeit der letzten dateiänderung mit dem zeitpunt des letztemn scanns vergleichen, bzw. dann mit geringer systemlast m hintergrund scannen, wie ein virenscanner, so dass der nutzer nicht warten muss bis das fertig ist.
der tipp die dateigröße in den hashwert einzubeziehen ist aber echt gut, danke, dann kann ich den anfang scannen, und trotzdem unterscheiden, wenn danach was verschieden ist.
-
CGI-BIN schrieb:
Dass seh ich doch richtig, oder? Ich bracuh die kollidierenden dateien zur gleichen zeit, sonst funktioniert das nicht, mit musikvergeleichen.
ich hab mir nen ftp-uploader gebaut. der geht so vor, daß er beim uploaden jede geuploadete datei in ein geheimes verzeichnis kopiert. beim nächsten upload vergleicht er dateiweise und bei unterschied, uploadet er die veränderte datei.
allerdings könnte man meinen, daß bei ner homepage von 30M die 30M im geheimen verzeichnis untragbar seien. naja, ist doch tragbar.
deine dateien sind viel mehr. da ist es nicht tragbar. wenn du allerdings sicherstellen kannst, daß die ateien nicht verändert werden, sondern nur kopiert und glelöscht, kannste im geheimen verzeichnis hardlinks auf die echten dateien machen.
bestimmt gibs auch irgend ne funktion, die dir bei zwei dateien, eine nur hardlink auf die andere, sehr schnell sagt, ob sie auf die selbe datei zeigen.nur so als idee, vielleicht kannste was damit anfangen, vielleicht nicht.
aber für nur musik reicht ein 64-bittiger hash eigentlich. wir gehen davon aus, daß der hash-algo gut ist und gleichverteilte schlüssel erzeugt. und daß wie nur 100000 mp3s haben. das macht dann 264/105 = 10^14-mal so viele unbenutze schlüssel wie benutze schlüssel.es geht dir darum, daß du zum beispiel ne playlist bauen kannst, die ist dann ne liste von hash-keys. und dann kannste mp3s auf cd brennen. von der platte löschen. die cd in die mikrowelle legen. aus dem internet nen song saugen. und der song wird als in der playlist erkannt, weil es genau die gleiche datei ist, wie die, dir du vor nem halben jahr verloren hast?
-
genau, mir geht es darum, das playlists nicht mehr vom namen und speicherort der datei abhängen, sondern solang sie noch im zugriffsbereich des servers ist erkannt und von diesem ausgeliefert wird. der server liefert die dateien per http. d.h. in der playlist sind dann URL's vom Typ http://mediaserver/getfile?hash=123456 anstatt http://mediaserver/mp3/song.mp3 wie ich das beim apache machen würde. der server soll dann den hashwert in seiner datenbank suchen, und den aktuellen pfad der datei rauslesen, und diese dann an den client schicken. Dafür muss der server aber natürlich immer erkennen das eine datei auch die gleiche is wie ein alter eintrag, z.B. wenn ich die datei verschiebe, damit er den pfad aktualisieren kann. aber ich denke, wenn ich hashwert und größe der datei speichere, ist es ziemlich unwahrscheinlich, dass zwei dateien mit verschiedenem inhalt gleiche größe und hashwert haben. Und wenn doch, hört der nutzer eine andere datei als er in die playlist gepackt hat, dass wär zwar ärgerlich, aber wenn es einmal in 10 Jahren vorkommt kann man damit leben.
Ich dneke ne kombination aus CRC64 und dateigröße sollte ideal sien, und wohl schneller als MD5. evtl. reicht es auch das erste kByte zu hashen ???
Oder besser dass 128te kByte, weil sonst ein leiser anfang immer sehr ähnlich ist.
aber da muss ich mal die tatsächlcihe geschwindigkeit testen.
-
Vielleicht noch zur klärung, es soll ein upnp-av server werden. durch diese eindeutige identifizierung einer datei wird es dann möglich für clients einfach alle server im netz nach einer datei zu fragen, die in einer playlist ist, ohne wissen zu müssen, welche ordnerstruktur ein server intern hat.
-
CGI-BIN schrieb:
Und wenn doch, hört der nutzer eine andere datei als er in die playlist gepackt hat, dass wär zwar ärgerlich, aber wenn es einmal in 10 Jahren vorkommt kann man damit leben.
jo, das gefällt mir.
Ich dneke ne kombination aus CRC64 und dateigröße sollte ideal sien, und wohl schneller als MD5. evtl. reicht es auch das erste kByte zu hashen ???
übertreib's mal nicht. an wieviele änderungen des datenbestands denkste denn? einmal am anfang, ok, das kostst. und dann? dann ist das weitere hashen doch schneller als das saugen.
Oder besser dass 128te kByte, weil sonst ein leiser anfang immer sehr ähnlich ist.
eine speicherseite bitte. also 4096 bytes. oder besser 8192, dann passts auch noch bei 64-bittern. und dann, warum nur eine. kannst ja immer eine seite lesen und dann 99 seiten überspringen. dann wieder eine lesen... bis zum dateiende.
aber da muss ich mal die tatsächlcihe geschwindigkeit testen.
jup. hashen sollte ein wenig schneller gehen, als die dateien von platte zu platte zu kopieren.
-
OK, soweit ist jetzt alles klar, nur noch eine letzte Frage zum Verständnis.
Du schriebst ich soll immer ganze Speicherseiten lesen, hat das auch Auswirkungen auf die Performance, weil die Datei immer Seitenweise ins RAM geladen wird, oder wie ist das zu verstehen? Woher weis ich, das 4kB der Datei auch in genau einer Seite landen, und nicht zwei halbe Seiten füllen?
Gilt das unter Linux und Windows?
-
CGI-BIN schrieb:
Du schriebst ich soll immer ganze Speicherseiten lesen, hat das auch Auswirkungen auf die Performance, weil die Datei immer Seitenweise ins RAM geladen wird, oder wie ist das zu verstehen?
das betriebssystem liest eh ganze seiten. also warum sollste die nicht nehmen?
Woher weis ich, das 4kB der Datei auch in genau einer Seite landen, und nicht zwei halbe Seiten füllen?
du fängst ja am anfang an und springst nur in vielfachen von 4k weiter. da kannste niemals denebentappen.
Gilt das unter Linux und Windows?
ja. linux ist auch nur ein windows, was alles wichtige angeht.
-
Ja sicher, spricht nix dagegen des zu machen. dachte nur weil du des so betonst, dass ich die Seitengröße komplett nutzen sollte, dachte ich dass das Performance Vorteile bringt. und in diesem Fall wäre es ja blöd, wenn das betriebsystem einen teil der daten in einer seite hat, und die zweite hälfte meiner 4k in ner anderen seite, weil ich ja dann springen müsste. Dass ich immer an die richtige stelle komme ist klar, aber weil du dass so herausgestellt hast, dachte ich das ist signifikant schneller mit ganzen Seiten zu arbeiten, und dann müsste ich ja sicherstellen dass es auch ganze seiten am block sind, sonst bringts ja nix.
-
Mich würde zu dem Thema auch noch mal was interessieren. Und zwar geht es darum, Bilddateien statt mp3s zu verwalten. Zur Anzeige soll, zwecks Generierung von Thumbnails, geprüft werden, ob sich die jeweiligen anzuzeigenden Dateien geändert haben.
Analog zu der hier beschriebenen Möglichkeit würden die Hashes zu den Dateien in einer Datenbank, neben weiteren Bildinformationen, gehalten werden.
So könnte man nun bei der Anzeige den Hash in der DB und den der Datei vergleichen und wenn diese unterschiedlich sind ein neues Thumbnail generieren.
Die Frage ist nun: Ist das performant? Gerade wenn mal 50 Bild auf einmal angezeigt werden sollen.
Gibt es andere Möglichkeiten, um effektiv Änderungen an den Dateien zu erkennen? Was ist zum Beispiel mit dem Vergleich der letzten Zugriffszeit auf die Datei?
Die entsprechende Software soll als Java-Applikation auf unterschiedlichen Plattformen laufen. Ich glaube, unter Linux gibt es ja eine Funktion, um den letzteren Zugriff zu bestimmen, gilt das aber auch für Windows?Ich hoffe, es ist in Ordnung, dass ich mich hier eingeklingt habe.
-
Die Zeit des letzten schreibenden Zugriffs sollte dir mögliche Änderungen mitteilen. Es kann dann zwar sein, dass jemand die Datei abgespeichert hat ohne sie zu ändern, aber ich denke das is weniger aufwendig in diesem Fall ein unötiges neues Thumbnail zu erzeugen, als Hashwerte zu berechnen.
Die zeit des letzten schriebzugriffs sollte dir unter Linux und Windows zur verfügung stehen, wenn du im Explorer z.b. Detail-Ansicht machst, steht da "geändert am". Ich denke die Vorschau vom Windows Explorer macht mit der thumbs.db Datei auch nichts anderes als Zugriffszeiten zu vergleichen.PS: Jeder ist frei sich an Diskussionen zu beteiligen, vor allem wenn es thematisch dazu passt!
-
Yankee schrieb:
So könnte man nun bei der Anzeige den Hash in der DB und den der Datei vergleichen und wenn diese unterschiedlich sind ein neues Thumbnail generieren.
Die Frage ist nun: Ist das performant? Gerade wenn mal 50 Bild auf einmal angezeigt werden sollen.Ich weiß nicht in wiefern das für kompriemierte Bilder wie JPG usw. gillt, aber zumindest für Bitmaps musst du ja die gesamte Datei zur Berechnung des Hashwertes/der Checksum heranziehen, weil du sonst evtl. die geänderten Pixel(-zeilen/-spalten/-bereiche) überspriegen könntest. Also würde es bei 50 Bildern wohl schon ziemlich lange dauern. Das Datum (oder dessen Hashwert :p ) der letzten Änderung könntest du dagegen in konstanter (kurzer) Zeit vergleichen, am besten gleich nach dem anzeigen, dann hast du einen minimal verzögerten Bildaufbau.