Vorzüge vom MD5-Hash - Verzeichnisse Organisieren mit Milliarden von Dateien

in #utopian-io6 years ago (edited)

Was MD5 im Webserver leisten kann




DQmPiKcYtB7kqiL7JBjL6JuybPbUPxNvxTAkFarMCAP5xZK_1680x8400.jpeg


Wir organisieren Verzeichnisnamen für große Dateimengen!

( .. Millionen Dateien )

Ich werde hier die Vorzüge und Nachteile der Funktion MD5 in PHP aufzeigen. Ich nehme dabei das Organisieren einer Verzeichnisstrukrur als Anwendungsbeispiel.

Legen wir los:

Mal angenommen, sie haben extrem viele Dateien auf einem Webserver zu organisieren. Sie wollen eine möglichst gute Verteilung der Dateien auf alle Verzeichnisse und keine tiefe Verschachtelungsebenen in den Dateibaum.

Die Lösung: MD5-basierte Verzeichnisse!

Was ist MD5?

MD5 ist eine Hashfunktion. Diese Funktion erzeugt aus einer beliebigen Bitfolge von Daten, eine feste Bitfolge von Daten .z.b. d05496d9c319aeaf84589882e892faf2. Diese Folge lässt sich nicht mehr rückwärts berechnen. Also aus einem Hash kann man die Ursprüngliche Information nicht mehr ausrechnen, da zu einer endlichen Folge, unendlich viele Daten passen können. Wir werden aber andere Aspekte beleuchten und nutzen.

Eine Hashfunktion wie MD5 hat bestimmte Eigenschaften, die wir bei unserer Anforderung nutzen können. Diese Eigenschaften sind folgende:

** Vorteilhaft:**

  • eine statistische Gleichverteilung der Ziffernfolge ( Hexadezimal 0 - f )
  • große Änderungen bei Hashwerten, trotz kleiner Änderung der Eingabedaten ( z.b. Dateien )

** Nachteile: **

  • Rechenzeit, Hashs müssen erst errechnet werden
  • Kollisionswahrscheinlichkeit, also gleiche Hash-Werte bei unterschiedlichen Daten, hat aber für uns praktisch keine Nachteile


Wir wollen hier die Vorzüge nutzen!

Vorgehen

Mit PHP errechnen wir über die Standard-Funktion md5_file() unseren Hashwert. Aus den jeweils ersten zwei Ziffern erzeugen wir den Namen für ein Verzeichnis. Ist das Verzeichnis vorhanden, so wird die Datei darin abgelegt, welche aus dem Ziffernblock hervorgeht, ist es nicht vorhanden wird es neu angelegt und erst dann die Datei darin abgelegt.

Da es bei zwei Ziffernfolgen von 00 bis ff als Verzeichnisnamen geben kann, erhalten wir 16^2 also 256 Variationen für mögliche Verzeichnisnamen.

Wenn wir ca. 1 Millionen Dateien haben, verteilen im Schnitt sich je 3906 1/4 Dateien pro Ordner. Schon in der 2. Verzeichnisebene kann man mit dem gleichen Prinzip aus der Position 3 und 4 des Hashwertes die Unterordner aufbauen. Nochmal 256 entspricht im Mittel 15 -16 Dateien.



Resumee

Dadurch erhält man bei nur 2 Verzeichnisebenen eine recht überschaubare Verteilung. Wenn man den Hash auch in einer Datenbank speichert, kann man hierdurch eine Datei schnell im richtigen Ordner finden. Es ist auch leicht zu prüfen, ob man eine Datei bereits gespeichert hat, denn hier ist es ebenso rasend schnell möglich, den richtigen Ordner anzuspringen. Im zweiten Schritt muss man dann nur noch die wenigen Dateien durchgehen, die im einzelnen Ordner liegen.


Selbst bei 1 Millarde Dateien, reicht eine weitere Ebene aus, um aus diesem Prinzip Ordner zu erstellen. Wir wären dann knapp unter 60 Dateien im Mittel pro Verzeichnis.


Das könnte dann z.B. so aussehen : ** / df / 3a / 33 / halloworld.jpg **


Das ist, troz der Masse von einer Milliarde, noch recht übersichtlich. Kollisionen machen in diesem Anwendungszenario keine Probleme, da selbst bei gleichen Hashs nur die 1. 6 Ziffern benutzt werden, um die Ordner zu erstellen und wir wollen ja die Dateien relativ gleich aufteilen.

Die maximale Ordnerzahl lässt sich ebenso leicht errechnen. Pro Tiefe mit je 2 Ziffern ergibt sich die Regel wie folgt:

Beispiel für 1 Milliarde Dateien



**d0 54 96 ** d9c319aeaf84589882e892faf2

Verzeichnis-Strukturmax. Ordnerzal pro Ebeneabsolute OrdnerzahlDateien pro Ordner
/ d/ 161662,5 Millionen *theroretisch
/ d0/ 256256ca. 3,9 Millionen
/ d / 0/ 16 / 16256-- --
/ d0 / 54/ 256 / 25665536ca. 15 260
/ d0 / 54 / 96/ 256 / 256 / 256rund 16,8 Millionenca. 60


Beispiel für 1 Millionen Dateien



**d0 54 96 ** d9c319aeaf84589882e892faf2

Verzeichnis-Strukturmax. Ordnerzal pro Ebeneabsolute OrdnerzahlDateien pro Ordner
/ d/ 161662 500
/ d0/ 256256ca. 3900
/ d / 05/ 16 / 2564096ca. 245
/ d0 / 94/ 256 / 25665536ca. 15 - 16

Alle Werte sind natürlich immer Mittlwerte. Starke Abweichungen sind möglich aber halten sich in Grenzen.



Implementierung in PHP

Ich gehe hier auf die Kernfunktion für eine Variante ein. Selbstverständlich ist dieses Prinzip noch ausbaubar und man kann auch eine ganze Klasse daraus erstellen, welche uns die Dateien anlegt.

Bildschirmfoto 2018-08-14 um 22.55.55.png



function get_dir_md5( $file_ressource , $pos ){
    $md5_string = md5_file( $file_ressource );
    # $md5_string = "d05496d9c319aeaf84589882e892faf2"; # test
    $parts = str_split( $md5_string , 2 );
    return
        $parts[ $pos ];
}

$file = '/var/www/html/data/files/halloworld.jpg';

print_r(
    get_dir_md5( $file , 0 ) . DIRECTORY_SEPARATOR . get_dir_md5( $file , 1 )
); 




Weiterführende Quellen:





#webdevelopment #code #coding #dev #development #programming #codedesign #codereview #cleancode #steemit #steem #stem #de-stem #steemstem #busy #utopian-io #technology #science #sql #md5 #hash #hashes #crypto #deutsch #deutschland #german #germany #orginal #diy #php #webserver #files #dir #directory



rect4138.png

Sort:  

Thank you for your contribution.

  • Only submissions in easily understood English will be reviewed and scored. Contributions in other languages must include a full and comprehensible translation of all content included in the submission.

Please read the utopian guidelines here.


Need help? Write a ticket on https://support.utopian.io/.
Chat with us on Discord.
[utopian-moderator]

Thank you for your review, @portugalcoin!

So far this week you've reviewed 17 contributions. Keep up the good work!

Guter Artikel und solides Verfahren, wenn man die maximale Anzahl der Dateien pro Ordner einschränken möchte. Unter anderem wird dieses Verfahren von MediaWiki für deren Dateiupload verwendet [1] , also nicht völlig fernab der Praxis.

Inzwischen aber leider nicht mehr so wichtig, da moderne Dateisysteme sehr viele Dateien pro Ordner erlauben.

[1] https://www.mediawiki.org/wiki/Manual:$wgHashedUploadDirectory

Danke für den ergänzenden Link.

Danke für den Artikel.
Genau so etwas habe ich für meine Bilderverwaltung gesucht. Die Idee finde ich recht interessant.

Hi @halloworld From @super-grand-ad
Did You know you can get Free Re steems
From Me and
https://steemit.com/trending/aaa-resteem
So you do not have to PAY for Re steems
I posted to you because I was down voted by the Bot
https://steemit.com/@einsundnull
And it Is linked to Steembot who you paid to get resteemed

Have a good day @super-grand-ad