[linux-l] mbox/Maildir/tar

[Rocco Rutte]

Hi,

* Oliver Bandel wrote:
>Zitat von Rocco Rutte <pdmef at gmx.net>:
>> * Ivan F. Villanueva B. wrote:
>> >Am Mi, Nov 28, 2007 10:42:14 +0100, Rocco Rutte schrieb:
>> >> O(log(n))/O(1) statt O(n)
>> >           ^^^^^
>> >        das verstehe ich nicht

>> Gute Hashtabellen (max. 50% voll, gute Hashfunktion mit guter
>> Streuung)
>> haben im Mittel keine Kollisionen, d.h. der Eintrag ist nach
>> Berechnung
>> der Hashsumme modulo Tabellengröße immer im Mittel sofort gefunden.
>> Im
>> worst-case kommt die Komplexität glaube ich auf das Verfahren zur
>> Kollisionsauflösung an. Wenn man chaining (also verkettete Liste an
>> der
>> Stelle in der Tabelle) benutzt, kann man im schlechtesten Fall eine
>> einfach verlinkte Liste haben, also O(n) (z.B. wenn die Tabelle nur 1
>> Zeile hat). Bei linearem Auflösen (also Soll-Stelle je 1 Stelle
>> weiter
>> probieren) müsste man auch auf O(n) kommen. Für andere Verfahren
>> weiss
>> ich es nicht aus dem Kopf.
>[...]

>Was ich immer noch suche, ist die Antwort bzgl.
>der Listen. Du meintest irgendwas mit Listen auf dem baum drauf oder so?
>(Finde die Mail leider gerade nicht).

>Und ich frage mich, wo denn da Listen sind.
>Du schreibst hier was von hash; ich dachte es werden Bäume
>in den Dateissystenmen eingesetzt.

>Aber vielleicht wreden wir auch aneinander vorbei.

Ja. :)

Ivan hat gefragt warum Hashtabellen O(1) haben, und ich habe versucht 
das zu erklären. Ich versuche mal die Verwirrung zu lösen...

Ein FS muss pro Verzeichnis wissen, welche Dateien sich darin befinden, 
also Pointer zu den Metadaten. In meiner naiven Vorstellung ist das eine 
einfache Liste im Trivialfall. Wenn man in einem Verzeichnis eine Datei 
ändern will, dann erfolgt aus dem Userspace heraus der Zugriff über den  
Pfad, d.h. das FS muss die Metadaten dazu erst suchen, also über die 
Liste gehen, um die Infos der Datei zu finden (z.B. die Inode). Das 
dauert lange wenn man viele Files hat.

Um das zu beschleunigen gibt es prinzipiell 2 Möglichkeiten: Baum oder 
Hashtabelle. ext3 hat meines Wissens eine Abwandlung eines B+-Baumes, 
UFS/FFS (BSD) haben IIRC eine Hashtabelle.

Und soweit ich mich richtig erinnere (bin zu faul zu gucken :), haben 
B+-Bäume nur auf der untersten Ebene wirkliche Daten und einen weiteren 
Pointer zum nächsten Kind des Elternknotens pro Blatt. Das ist dann 
widerum eine einfach verlinkte Liste, wenn man nur das Leaflevel 
betrachtet. "Darüber" ist dann ein B+-Baum für das schnelle Suchen in 
der Liste.

Ab hier rate ich mal.

Für den Fall eines Baumes und Hashtabelle gibt es eine bestimmte 
"Sortierung", in der readdir() die Dateien zurückliefert. Diese 
Sortierung ist garantiert nicht nach Inode. Wenn man keinen Baum/Tabelle 
hat, ist die Reihenfolge grob die der Erstellung (oder so, habe nie ein  
FS geschrieben :) und damit IMHO der Abstand zwischen den Inodes zweier 
readdir()-Ergebnisse im Mittel deutlich geringer als bei Baum/Tabelle. 
Bei einem Baum oder eine Tabelle bekommt man bei readdir() allerdings 
die Files in praktisch zufälliger Reihenfolge mit praktisch zufälliger 
Inode.

D.h. in beiden letzteren Fällen sind die Inodes mit einer gewissen 
Wahrscheinlichkeit durchschnittlich weiter auseinander als beim ersten. 
Zumindest legen das meine einfachen Tests der letzten Tage (Optimierung 
beim Lesen von großen Maildirs) nahe. Damit bringt es nach meinen Tests 
bei derart "beschleunigten" Dateisystemen mehr oder minder wirklich viel 
wenn man vorher nach Inode sortiert, wenn die Infos aus readdir() nicht 
reichen (z.B. stat() oder open()).

Bis auf die Tests ist das nur geraten.

>> Nachteil: Hashtabellen brauchen viel Pflege
>[...]
>immer schön giessen ;-)

>Das Problem mit dem Suchen sieht da ja garnicht so schlimm aus.
>log(n) ist doch ganz nett.
>Deswegen denke ich auch, daß die Probleme von Maildir nicht
>daher rühren. Klar: je weniger man auf dem Filesystem herum rödeln
>muß, um so besser.

Ich habe keine harten Zahlen zu sowas, aber einmal den Kopf quer über 
die Platte schieben kann mehrere stat() oder sogar open()+read()-Aufrufe 
bedeuten, denke ich. Und wenn man das bei nahezu jedem stat() machen 
muss, ist man X mal langsamer als wenn man es nur bei jedem 10. oder 20. 
machen muss, weil man die ganze Zeit praktisch auf Kopfbewegungen warten 
muss.

Der Faktor 12-13 bei mutt kommt wirklich nur durch Inode-Sortierung und 
unter exakt den gleichen Bedingungen zu stande (gleiche Anzahl von 
stat()/open() Aufrufen, die Kisten sind sonst idle), d.h. Schwankungen 
bei I/O Wartezeiten kann man nahezu auscchließen. Zumindest wäre der 
Faktor dann nicht so stabil.

Es gibt ein paar Mails auf lkml zum Sortieren und es gibt Sourcen für 
readdir(), die via LD_PRELOAD das Sortieren übernehmen wenn man die 
Anwendung sonst nicht anpassen kann.

Einfach mal zufällig 500k Files in einen Ordner werfern und messen wie 
lange es dauert ein readdir() gefolgt von stat() auf jedes File zu 
machen; und das ganze nochmal mit Inodes sortiert.

MfG, Rocco