Sort 1TB file

Hi,

Wie kann man dieses Beispiel am effektivsten Loesen?

Given a file of size 1TB, containing only 32 bit integers, describe how you would efficiently sort it. You have only 2GB of memory available.

1.) Teile die 1TB in 500 Chunks a. 2GB (1TB = 1000GB / 2GB = 500 Chunks)
    for i=0; i < 500; i++
    	Lade Chunk_i (2GB) von der HDD in den RAM
	Sortiere Chunk_i mit Quicksort
	Schreibe den sortieren Chunk_i zurueck auf die HDD

    end

    Nun haben wir die Chunks a. 2GB sortiert

2.) 2 Way Sort
    - Allokiere 3.99MB x 500 Chunks als Eingangsbuffer
    - Allokiere 3.99 MB als Ausgansbuffer

    - Lese die ersten 3.99MB von jedem Chunk in den Eingangsbuffer
    - Merge den Eingangsbuffer in den Ausgangsbuffer, wenn Ausgangsbuffer voll ist -> flush to HDD

Ein groesserer Ausgangsbuffer sollte die Performance erhoehen, da Schreiben auf die HDD langsam ist.

der Text nach der Frage, sollte mein Ansatz sein. Wie waehlt die optimale Groesse des Ausgangsbuffers?

SeppJ

Zu 1: Beachte, dass Quicksort nicht in-place sortiert. Also musst du entweder ein anderes Sortierverfahren wählen oder die Chunks etwas kleiner machen.

Wie waehlt die optimale Groesse des Ausgangsbuffers?

Das ist in erster Linie eine Frage der unterliegenden Hardware. Wie sich Schreib- und Lesezugriffe zueinander verhalten, ob und wie die Hardware parallelisiert ist und vieles andere. Ja, es kann sehr gut möglich sein, dass ein größerer Ausgangspuffer besser ist. Aber welche Größe genau die richtige ist, kann man ohne weitere Information nicht sagen. Man kann höchstens einen Aufsatz darüber schreiben, welche Faktoren die Wahl wie beeinflussen. Ein solcher Aufsatz steht auf Wikipedia, welchen du sicherlich schon gelesen hast, oder?

Wahrscheinlich bietet es sich hier an, gar nicht groß zu sortieren, sondern zu zählen, wie oft jede einzelne Zahl vorkommt (um lineare Laufzeitkomplexität zu erreichen). Die begrenzte Zustandsmenge eines 32-Bit-Integers erlaubt das hier.

Das lässt sich besonders effektiv gestalten, wenn man vorher den Wertebereich der Integer abschätzen kann und dieser ausreichend klein ist (beispielsweise nur Zahlen zwischen -2²⁶ und 2²⁶), sollte aber auch so ganz gut handhabbar sein.

Ich denke mir das etwa so, dass man eine große Datei von 32 Gigabyte Größe anlegt (8 Byte Zähler mal 2³² mögliche Werte, anfänglich mit Nullen voll) und eine große Hashmap (mit so nem Gigabyte Platz) im Speicher hat, in der man zu den bereits gefundenen Werten nen Zähler hat, wie oft man sie gefunden hat. Wenn die Hashmap überläuft (Einstellungssache -- sinnigerweise dann, wenn man anfängt, mit vielen Kollisionen zu kämpfen. Pi mal Faust bei 80% Auslastung oder so, wenn die Daten nicht komisch strukturiert sind) läuft man einmal über die Hashmap, addiert die neuen Zähler auf die bereits vorhandenen Zähler in der großen Datei, wirft den den Inhalt der Hashmap weg und macht mit den nächsten paar Gigabyte das selbe wieder.

Danach hat man eine Datei, in der zu jedem 32-Bit-Wert steht, wie oft er in der Ursprungsdatei war (quasi eine Art rudimentäres RLE). Die wäre in vielen Fällen vermutlich angenehmer zu benutzen, aber wenn man wirklich eine große Datei braucht, in der die Zahlen sortiert ausgeschrieben hintereinander stehen, ist die von da an leicht zu erzeugen, indem man aus der RLE-Datei nacheinander die Zähler ausliest und entsprechend viele korrespondierende Zahlen in eine weitere Datei rausschreibt.

Dabei könnte es von Vorteil sein, die RLE-Datei auf einer SSD zu erzeugen, wenn einen die Abnutzung derselbigen nicht stört, und sparse files zu benutzen, wenn große Löcher in der Wertemenge erwartet werden. Obwohl bei einem Terabyte an Daten es wahrscheinlich nicht mehr so ins Gewicht fiele, anfangs 32 GB Nullen in eine Datei zu schreiben und sie am Stück zu haben, was auch von Vorteil sein könnte. Müsste man ausprobieren und nachmessen.

Nachtrag:

Das ist natürlich sehr speziell auf 32-Bit-Integer zugeschnitten. Bei 64-Bit-Integern wäre es schon nicht mehr praktikabel, und wenn es um komplexere Daten geht, ist man mit dem Ansatz eh verloren. Worauf die mit der Aufgabe hinaus wollen, da hast du wahrscheinlich recht, wird eher merge sort sein.

Jester

SeppJ schrieb:

Zu 1: Beachte, dass Quicksort nicht in-place sortiert.

Huch? Seit wann?

SeppJ

Jester schrieb:

SeppJ schrieb:

Zu 1: Beachte, dass Quicksort nicht in-place sortiert.

Huch? Seit wann?

Schon immer? Wo speicherst du denn die "Laufvariablen" der Rekursion?

1. 2GB in den Arbeitsspeicher zu laden, wenn du nur 2GB hast, ist nicht gut.

Musst du das File überschreiben oder darfst du ein neues anlegen und ist der HDD Platz gegrenzt?

SeppJ schrieb:

Jester schrieb:

SeppJ schrieb:

Zu 1: Beachte, dass Quicksort nicht in-place sortiert.

Huch? Seit wann?

Schon immer? Wo speicherst du denn die "Laufvariablen" der Rekursion?

https://en.wikipedia.org/wiki/Quicksort schrieb:

Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space used by the stack during the recursion.[2]

Bashar

nwp3 schrieb:

https://en.wikipedia.org/wiki/Quicksort schrieb:

Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space used by the stack during the recursion.[2]

in-place := O(1) additional space

zu Punkt1: QuickSort in-place

Ich finde seldon's Ansatz sehr gut

hustbaer

seldon schrieb:

Wahrscheinlich bietet es sich hier an, gar nicht groß zu sortieren, sondern zu zählen, wie oft jede einzelne Zahl vorkommt (um lineare Laufzeitkomplexität zu erreichen). Die begrenzte Zustandsmenge eines 32-Bit-Integers erlaubt das hier.

Die Idee hatte ich auch, hab ich dann aber nach näherer Betrachtung wieder verworfen.

seldon schrieb:

Ich denke mir das etwa so, dass man eine große Datei von 32 Gigabyte Größe anlegt (8 Byte Zähler mal 2³² mögliche Werte, anfänglich mit Nullen voll) und eine große Hashmap (mit so nem Gigabyte Platz) im Speicher hat, in der man zu den bereits gefundenen Werten nen Zähler hat, wie oft man sie gefunden hat. Wenn die Hashmap überläuft (Einstellungssache -- sinnigerweise dann, wenn man anfängt, mit vielen Kollisionen zu kämpfen. Pi mal Faust bei 80% Auslastung oder so, wenn die Daten nicht komisch strukturiert sind) läuft man einmal über die Hashmap, addiert die neuen Zähler auf die bereits vorhandenen Zähler in der großen Datei, wirft den den Inhalt der Hashmap weg und macht mit den nächsten paar Gigabyte das selbe wieder.

Und genau beim "Integrieren" der Hashmap (=Zählerwerte auf das File draufaddieren) wirst du Performance-Probleme bekommen.
Entweder du gehst die Hashmap in ihrer "nativen" Reihenfolge durch, dann bringen dich die Random-IOs auf das File um.
Oder du gehst das File linear durch, dann musst du 4 Mio. Zugriffe auf die Hashmap machen um die passenden Werte zu finden.

=> Eher noch ne Baum-basierte Map. Damit könnte man beim "Integrieren" die Map durchiterieren und gleichzeitig linear auf das File zugegreifen.

Ich erwarte mir aber dass auch das im "average case" wesentlich langsamer sein wird als die Datei in z.B. 1 GB Stücke zu zerteilen, diese dann mit Quicksort zu sortieren, und am Ende dann zusammenzumergen.

Bei der Lösung musst du 1x das File komplett lesen und schreiben für den Quicksort, und dann nochmal komplett lesen und schreiben für den Merge.
Alle Zugriffe für den Quicksort sind linear. Die Zugriffe beim Mergen sind nicht mehr so ganz linear, aber man kann zumindest immer grössere Stücke auf einmal bearbeiten - zumindest 1 MB Stücke gehen sich aus. Und Random IO mit 1 MB Blocks ist fast gleich schnell wie linear.

=> Die Quicksort => Merge Methode wird schwer zu schlagen sein.

Bashar schrieb:

nwp3 schrieb:

https://en.wikipedia.org/wiki/Quicksort schrieb:

Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space used by the stack during the recursion.[2]

in-place := O(1) additional space

Die Definition mag "mathematisch korrekt" sein, ist davon abgesehen aber total irrelevant.

Ich bezeichne Sachen die mit O(log N) Zwischenspeicher auskommen auch als "in place".
log2 von 1 yotta ist z.B. ca. 80. Rekursionstiefe 80 ist normalerweise kein Problem, da man normalerweise genug Stack dafür hat. Und N ist normalerweise kleiner als 1 yotta.
=> Quicksort kann normalerweise als in-place angesehen werden.

Statt [unordered_]map+counting könnte man auch einfach ≈2GB lesen + Quicksort + 32GB-File updaten. Wenn das 32GB-File fertig ist, kann man die sortierten ints in die Ausgabedatei rausschreiben.

Angenommen, dass Quicksort auf <2GB gleich schnell geht wie das Lesen von 2GB, und Lesen/Schreiben gleich schnell sind, entspricht die Laufzeit dem Lesen von 35 TB.

Die 32GB kann man auch auf 24GB reduzieren, dann hat man 27 TB.

Noch kompakter wären 4-Byte-Zähler und sich die Overflows in einem separaten File zu merken. Entspricht ungefähr 20 TB.

Quicksort + Merge ist etwas besser, angenommen die Suche nach dem Minimum aus den 400 Buffern dem Lesen von 6 Integern auf der HD entspricht, entspricht die Laufzeit des 400-Merges auf N Bytes dem Lesen von 8*N TB. Hat man das einmal auf die 1GB-Chunks gemacht hat man 2 sortierte 0.4TB-Chunks, nochmal gibt 1 TB. => (8+5+3)=16TB.

Gibt sich also nicht viel zwischen den verschiedenen Methoden.

hustbaer schrieb:

Und genau beim "Integrieren" der Hashmap (=Zählerwerte auf das File draufaddieren) wirst du Performance-Probleme bekommen.
Entweder du gehst die Hashmap in ihrer "nativen" Reihenfolge durch, dann bringen dich die Random-IOs auf das File um.
Oder du gehst das File linear durch, dann musst du 4 Mio. Zugriffe auf die Hashmap machen um die passenden Werte zu finden.

Da glaube ich nicht dran, wegen der geringeren Komplexitätsklasse. Für jeden Zähler ein fseek zu machen klingt zwar barbarisch, aber bei extrem großen Datenmengen skaliert es immer noch besser als die Sortierung.

hustbaer schrieb:

=> Eher noch ne Baum-basierte Map. Damit könnte man beim "Integrieren" die Map durchiterieren und gleichzeitig linear auf das File zugegreifen.

Damit verlöre man die bessere Komplexitätsklasse. Das wäre ausgesprochen ungünstig.

...und um mich nicht unnötig zu wiederholen, meine Antwort auf den Rest ist auch nur "Komplexitätsklasse." Skalieren wird es ungeachtet der fseeks besser, da der linear steigende I/O-Aufwand zunehmend hinter dem Sortieraufwand zurückbleibt. Die Frage ist höchstens, ob der Break-Even-Punkt bei einem Terabyte Daten erreicht wird. Intuitiv scheint es mir so, als sollte das der Fall sein (besonders, wenn die Datei auf einem Medium liegt, dem fseeks nicht viel ausmachen), ich habe aber gerade kein System zur Hand, auf der ich derart große Datenmengen herumschubsen könnte, um es zu messen.

http://de.wikipedia.org/wiki/Mergesort

Der 1. Schritt war OK. Der 2. muss etwas anders aussehen, ggf. per Kaskade loesen. D.h. nicht sofort die 500 sortierten Chunks zusammenfuegen, sondern die ersten 25, usw. und dann nochmal die resultierenden 20.

Kein Problem, dafür gibt's die std::priority_queue .

hustbaer

Sagen wir wir bekommen 300 Mio. Zählerstände in die Hashmap. Viel mehr wird sich bei 2GB RAM nicht ausgehen.
Wir können davon ausgehen dass keine Zugriffe auf die Zähler-Datei über den Cache bedient werden.
D.h. 300 Mio. ungecachte IOs.
Eine HDD schafft typischerweise so an die 100 IOs pro Sekunde, und das ist bereits mit Heimweh und Rückenwind.
Macht 3 Mio. Sekunden.

Wenn alle 32 Bit Werte vorkommen müssen wir das mindestens 14x machen (wobei es ein Wunder wäre wenn man wirklich mit 14x auskommt)
=> 42 Mio. Sekunden.

Ich hab' keine Ahnung wie man ausrechnet wie oft man bei zufälliger Verteilung "flushen" müsste, aber es wird viel viel öfter als 14x sein.
Ich runde einfach mal auf 100 Mio. auf, das wird es mindestens sein, und ist ne schöne runde Zahl.
100 Mio. Sekunden sind mehr als 3 Jahre.

SSDs sind schneller. So ca. Faktor 1000, also 100.000 IOs pro Sekunde schaffen die. (Real wird weniger übrig bleiben, aber egal, geht ja nur um Grössenordnungen). Sind immer noch 1,15 Tage.

=> Nein, ich glaube nicht dass das gut funktionieren wird.

Da gewinnt sogar noch eine andere, viel einfacher zu implementierende Zählvariante:
Im 1. Durchgang die ersten 100 Mio. Werte zählen, im 2. Durchgang die nächsten 100 Mio. Werte ... => 44 Durchgänge.
Wenn ein Durchgang linear mit 100 MB/s lesen kann, dann braucht er für 1 TB ca. 3 Stunden. x43 = 5,4 Tage.
Ne SSD ist schneller, sagen wir an die 500 MB/s => 1,1 Tage.
(Das Rausschreiben der Zählerstände spar ich mir, das geht unter. Genau so das Generieren des sortierten Files zum Schluss.)

Die Quicksort + Merge Lösung wird gefühlsmässig noch darunter liegen.

seldon schrieb:

Komplexitätsklasse

*gähn*
Und google auch mal nach Performance-Vergleichen von Hashmaps vs. Treemaps. Die unterschiedliche Komplexitätsklasse ist da rein theoretisch. In der Praxis ist im RAM kaum ein Unterschied. Zumindest nicht bei gängigen Systemen mit gängigen RAM Grössen.

Ich halte es bei einer Datenmenge von 1TB nicht für angebracht, die Komplexitätsklasse mit "*gähn*" abzutun. 1TB Daten zu sortieren, das wird ne Weile dauern, ganz egal, wie du es anfängst, und "Ansatz 1 dauert nen Tag, das ist mir zu lange" belegt nicht, dass Ansätze 2 und 3 schneller laufen.

Das grundsätzlich. Ich hab jetzt mal nachgemessen, anstatt mir Zahlen zusammenzufantasieren, und du hast in Bezug auf eine Sache recht: Die seeks auf einer Festplatte kommen zu langsam. Nicht so langsam, wie du es einschätzt -- das pegelt sich in meiner Messung recht schnell bei so 1000 seek-read-seek-write-Zyklen pro Sekunde ein (Zugriffsstelle in der Datei jeweils zufällig ausgewürfelt), aber zu langsam für den use case. Abhängig von der Festplatte mag das variieren -- ich habe jetzt auf einer einzelnen consumer-hdd gemessen, wo in der Realität ein RAID wahrscheinlicher wäre -- aber wahrscheinlich nicht mehr als eine Größenordnung. Eine Messung auf SSD werde ich noch nachreichen, sobald ich wieder vor einer SSD sitze. Da das Zugriffsmuster für eine HDD sehr ungünstig ist und einer SSD geschwindigkeitstechnisch prinzipiell egal sein sollte (auch wenn es Gift für das wear-leveling ist), sollte uns das in realistischere Bereiche rücken.

So oder so ist das ein Problem, das man mit Bäumen nicht los wird. Dass man weniger Elemente darin unterkriegt, weil die Baumknoten verkettet werden müssen, ließe sich durch die Verwendung eines Heaps statt eines Baums noch regeln, aber in dem Fall, dass wirklich der gesamte Wertebereich des 32-Bit-Integers ausgefüllt würde, wären konsekutive Elemente in einem Baum ebenfalls sehr selten.

Da das aber auch bedeutet, und das ist mir zunächst auch nicht aufgefallen, dass die Zähler selten einen anderen Wert als 1 erreichen würden, das ganze Caching nicht so richtig sinnvoll. Wenn man Vermutungen über die Struktur der Wertemenge anstellen kann, sieht das u.U. anders aus.

Also, im Folgenden ohne Caching: Jede Zahl einzeln auf die RLE-Datei schlagen, das bedeutet 2³⁸ seek-read-seek-write-Zyklen, bedeutet mit meiner Festplatte 8,7 Jahre. Das ist nicht so richtig befriedigend. Wenn Faktor 1000 bei ner SSD richtig ist (Messung folgt noch), dann sind es 3 Tage und gut 4 Stunden, das wäre auf einer Node mit 2 GB verfügbarem RAM realistischer. Meine Vermutung ist aber, dass, weil Seeken der SSD echt egal ist, der Unterschied nochmal größer ausfallen wird. In einer Messung von Thomas Krenn einer Intel-SSD im Januar (Link weiter unten) zeigte sich da kein Unterschied zwischen sequentiellen und zufälligen Zugriffen, und wenn man die 8 Terabyte Zähler da wirklich mit 90 MB/s durchdübeln kann, reden wir nur noch von einem Tag. Das alles unter dem Vorbehalt einer Messung, die ich noch tun muss -- dummerweise bedeutet das, dass diese Hochrechnung nicht so richtig wertvoll ist.

Gegenrechnung Mergesort: Ich hab wieder mal gemessen. Auf meinem i7-4771 dauert ein std::sort (also ein Quicksort) von 1 GB Zufallsdaten ~21 Sekunden. Das muss man tausend mal machen, sind knapp 6 Stunden. zwei davon im RAM zu std::mergen dauert hier 0,41 Sekunden. Wenn man alles im Speicher halten könnte und durch sukzessives Mergen größere Vektoren zusammenbauen würde (immer zwei mergen), wäre man am Ende hochgerechnet eine halbe Stunde beschäftigt. Das alles im RAM zu halten ist natürlich illusorisch, wenn uns nur 2 GB zur Verfügung stehen. Nehmen wir - jetzt wird's dekadent - eine >2 Terabyte-SSD als scratch space an, die einen Datendurchsatz von 250 MB/s Lesen und 90 MB/s Schreiben schafft (das sind Optimalwerte aus einer Messung von Thomas Krenn im Januar). Wir erzeugen ein Datenvolumen von 10 TB (10 Merge-Ebenen, für die jeweils der gesamte Content gelesen und geschrieben wird. Die naheliegende Idee, alles gleichzeitig zu mergen, skaliert mit O(n²) und wird langsamer sein), das macht 11 Stunden Lesen und 1 Tag und gut 6 Stunden Schreiben. Wir sind inzwischen bei 2 Tagen.

(jeweils plus das, was in beiden Fällen gemacht werden muss)

...

Jetzt muss ich diese verdammte SSD ausmessen. Was am Ende besser da stünde, kann ich jedenfalls nur mit solchen Überschlägen nicht vorhersagen. Könnte noch knapp vor break-even liegen.

Egal, was am Ende konkret schneller wäre, man kann sich bei solchen Datenmengen nicht mehr auf sein Gefühl verlassen -- vor allem, wenn sich das Gefühl vor allem um etwas dreht, das am Ende einen konstanten Faktor ausmacht. Den Daumen vor die Schnauze zu halten und zu sagen "Komplexitätsklasse, gähn. Gefühlt muss der Mergesort da in zwei Stunden durch sein" führt einen in die Irre. Der Haken ist genau

hustbaer schrieb:

Zumindest nicht bei gängigen Systemen mit gängigen RAM Grössen.

...wir reden hier nicht mehr von gängigen Größen.

Medallien-Kehrseite: Ich hab den Effekt des log(n)-Faktors größer eingeschätzt und hätte erwartet, dass der mergesort deutlich länger braucht. Den Schuh des getrügten Gefühls muss ich mir auch anziehen.

Der Elefant im Zimmer

Worauf wir jetzt noch überhaupt nicht eingegangen sind, ist der eigentliche Trick im Umgang mit solchen Datenmassen: Parallelisierung. Ich habe in der Aufgabenstellung jetzt keine Information darüber gesehen, wie viele Prozessorkerne der TE benutzen darf, aber letztendlich ist das Szenario der Aufgabe eh unrealistisch. Ich lass mal folgenden Link da:

http://sortbenchmark.org/

...und stelle anheim, dass derart große Datenmengen in der Praxis immer verteilt auf großen HPC-Clustern verarbeitet werden, wo man das in brauchbarer Zeit hinkriegt, und wo jede Node auch ausreichend RAM rumliegen hat, um nicht dauernd Dinge auf Platte schreiben zu müssen. Und da sortiert man dann auch ganz sicher nicht einfach nur Zahlen, womit sich die Zählerei sowieso erledigt hat.

SeppJ

seldon schrieb:

http://sortbenchmark.org/
[...]
Und da sortiert man dann auch ganz sicher nicht einfach nur Zahlen, womit sich die Zählerei sowieso erledigt hat.

Der Indy-Benchmark macht genau das