Quote

Die Ordner erstelle ich jetzt einfach zufällig?

Nein basierend auf die SHA1 Nummer des Keys. Und die SHA1 Nummer nutzt du für die Ordner/Datei generierung.

Wenn du also die anforderung bekommst den Wert für "foo" auszugeben, wandelst du "foo" in die SHA1 Nummer um. Was dann "0beec7b5ea3f0fdbc95d0dd47f3c5bc275da8a33" ergibt daher du weist du musst in der Datei "0b/eec7b5ea3f0fdbc95d0dd47f3c5bc275da8a33" nachschauen und den Inhalt zurück geben, hat dein System die Datei nicht, so hast du den wert nicht gecached.

Quote

Wie kann man eine ungefähre Gleichverteilung der Dateien auf die einzelnen Ordner erreichen? Reicht der Zufall aus?

Wie du dateien gleichmäßig verteilst und dazu noch den Lookup ermöglichst ohne zu suchen dazu würde mir nur einfallen das du dein ein Index aufbauen musst.

Daher du erstellst z.B. den Ordner 1. Legst dort 256/512/1024/... dateien ab, und erstellst danach Ordner 2 und legst wieder die gleiche anzahl ab. Okay eigentlich ist das nicht gleich verteilt, aber damit baust du die ordner mit gleicher größe auf.

Zum schnellen zugriff musst du dann eine art index haben in der "keyname" -> Ordner/Datei gemapt wird.

Trickreich wird es dann wenn Werte auslaufen/gelöscht werden. Dann müsstest du wissen in welche Ordner am wenigsten sind und dann entsprechend eine Logik aufbauen. Kurz gesagt halte ich das für zu kompliziert, und sehe auch keinen großen Vorteil dadrin. Wenn dann würde ich lieber gleich anfangen z.B. eine BerkeleyDB zu nutzen.

Ansonsten sollten SHA1 Nummern unterschiedlich genug sein das die Dateien ich sag mal "genug" aufgeteilt werden. Evtl. kannst du noch hingehen und das dritte und vierte zeichen in ordner verpacken. So das aus "6ae999552a0d2dca14d62e2bc8b764d377b1dd6c" der Dateipfad "6a/e9/99552a0d2dca14d62e2bc8b764d377b1dd6c" wird.

Wenn nur 1/10 der Kombinationen genutzt werden würde, und in jedem Ordner 10 Dateien liegen würden, dann hättest du schon 65.536 keys zum cachen. Die muss man erstmal haben...
Last edited: 2009-08-26 16:51:36 +0200 (CEST)