Skalierbarkeit von 'sort -u' für gigantische Dateien

23

Was ist ein angemessenes Skalierbarkeitslimit für 'sort -u'? (in den Dimensionen "Zeilenlänge", "Zeilenanzahl", "Gesamtdateigröße"?)

Was ist eine Unix-Alternative für Dateien, die diese Dimension der "Zeilenanzahl" überschreiten? (Natürlich kann ich leicht eins implementieren, aber ich habe mich gefragt, ob es etwas gibt, das mit wenigen Standard-Linux-Befehlen gemacht werden kann?)

sort Grzegorz Wierzowiecki
quelle
Für diejenigen, die binär darin suchen oder wissen wollen, wie: unix.stackexchange.com/q/247508/9689
Grzegorz Wierzowiecki
2
Es gibt Situationen, in denen einem uniqvorher sort -ugeholfen wird. Übrigens, für ASCII-Daten LC_ALL=C sortbeschleunigt GNU sorteine Menge (siehe diese Antwort )
Walter Tross

Antworten:

39

Das sort, was Sie unter Linux finden, stammt aus dem coreutils- Paket und implementiert eine externe R-Way-Zusammenführung . Es teilt die Daten in Blöcke auf, die es im Speicher verarbeiten kann, speichert sie auf der Disc und führt sie dann zusammen. Die Chunks werden parallel ausgeführt, wenn die Maschine die Prozessoren dafür hat.

Wenn es also ein Limit geben sollte, ist es der freie Speicherplatz, der sortzum Speichern der temporären Dateien verwendet werden kann, die zusammengeführt werden müssen, kombiniert mit dem Ergebnis.

Anthon
quelle
3
Beachten Sie, dass die GNU-Sortierung diese temporären Dateien komprimieren kann, um noch mehr zu packen (und die Leistung mit langsamen Datenträgern zu steigern).
Stéphane Chazelas
1
@ StéphaneChazelas Danke für das Update. Ich habe mich gefragt, ob die Sortierung klug genug ist, um Chunk-Dateien zu entfernen, wenn eine vollständig zusammengeführt wurde (was leicht passieren kann, wenn die Quelle bereits teilweise sortiert ist), um den Speicherplatz zu optimieren. Ich habe in diesen Tagen nicht die Zeit, in den Quellcode einzutauchen :-(
Anthon
3
Neben dem Speicher gibt es noch eine weitere Beschränkung für die Zusammenführungsphase: Die Anzahl der Dateien, die gleichzeitig geöffnet sein können. Dies ist normalerweise eine vom Betriebssystem festgelegte Grenze. GNU sort kommt auch damit zurecht, indem die Anzahl der Dateien, die es auf einmal öffnen kann, rekursiv zusammengeführt wird!
Diomidis Spinellis
@ StéphaneChazelas Wenn ich ein Tool speziell zum Sortieren sehr großer Dateien entwickeln würde, würde ich die Zeilen als Index in der Originaldatei speichern. Tut GNU Sort dies oder verwendet es einfach einen herkömmlichen Kompressionsalgorithmus?
Random832
3
@ Random832 und es soll in der Lage sein, die Datei über sich selbst zu überschreiben ( sort -o file file)
Stéphane Chazelas
1

Ich kann nicht für herstellerspezifische Implementierungen sprechen, aber die UNIX sortImplementierung teilt große Dateien in kleinere Dateien auf, sortiert diese Dateien und kombiniert dann die sortierten kleineren Dateien zu einer aggregierten sortierten Ausgabe.

Die einzige Einschränkung ist der Speicherplatz für die kleineren Dateien, die zwischenzeitlich von erstellt sortwurden. Sie können jedoch in ein beliebiges Verzeichnis umgeleitet werden, indem Sie die Umgebungsvariable festlegen TMPDIR.

schily
quelle
3
Wie genau nennen Sie die UNIX-Sortierimplementierung ? Ist es das Original von Unix Version 3? Die Manpage dort sagt, dass es keine Dateien größer als 128 KB sortieren kann.
Stéphane Chazelas
Was verstehen Sie unter Unix Version 3? Die Version von 1973? Die ursprüngliche UNIX-Sortierimplementierung wurde im Laufe der Jahre verbessert und IIRC, die Solaris-Version, ist noch viel schneller als die GNU-Version. Natürlich wurde sort vor 25 Jahren verbessert, um Multi-Byte-Zeichen zu verstehen, und ich erinnere mich an eine USENET-Diskussion, dass dies unter Solaris effizient durchgeführt wurde. Übrigens: man largefileListet sortals große Datei bewusst.
Schily
2
Sprechen Sie tatsächlich von der herstellerspezifischen Oracle-Version von sort? Oder irgendeine Ableitung irgendeiner Version von AT & T Unix? Oder eine von Unix zertifizierte Version von sort(wie GNU sortunter OS / X)?
Stéphane Chazelas
Die Qualität moderner sortImplementierungen in Bezug auf Multi-Byte-Zeichen kann variieren. Die Tatsache, dass sortgeteilte Zwischendateien verwendet werden, ist allen UNIX-Implementierungen gemeinsam, die auf dem Originalcode basieren. Übrigens: Die Solaris-Version ist OSS als "OpenSolaris", siehe sourceforge.net/p/schillix-on/schillix-on/ci/default/tree/usr/…
schily
Vor 25 Jahren wurde UTF-8 noch nicht erfunden? Unterstützung für UTF-8-Gebietsschemas wurde in Solaris 7 ( 1 , 2 ) hinzugefügt . Beziehen Sie sich auf einen anderen Multibyte-Zeichensatz?
Stéphane Chazelas
1

Basierend auf https://blog.mafr.de/2010/05/23/sorting-large-files/ und /unix//a/88704/9689 :

split -n l/20 input input-
for inpf in input-* ; do
    sort --parallel="$(nproc --all)" "${inpf}" > sorted-"{$inpf}"
done
sort -m sorted-input-* > sorted-input

Aktualisieren:

Aus den obigen Antworten geht hervor, dass sortbereits das, was als Snippet bezeichnet wurde, dh das Zusammenführen externer R-Wege, erfolgt . Also immerhin läuft einfach:

sort --parallel="$(nproc --all)" -u input > output

Sollte ausreichen.

Meine aktuellen Annahmen (ohne Code zu überprüfen) zu Limits sind:

  • Die maximale Zeilenlänge ist durch die Größe des physischen Speichers begrenzt. Sortieren müssen mindestens zwei in den Speicher passen
  • Anzahl der Zeilen - ist mir nicht bekannt
  • Dateigröße - natürlich nach Dateisystem
  • Anzahl geöffneter Dateien parallel - je nach Betriebssystem (Vielen Dank, Diomidis Spinellis, für den Hinweis!)

(Diese Antwort ist als Community-Wiki markiert - fühle dich ermutigt, sie zu verbessern! :))

Grzegorz Wierzowiecki
quelle
2
GNU sortsortiert standardmäßig parallel (seit 2010 nach der Seite, auf die Sie verlinken), --parallelum die Anzahl der gleichzeitigen Threads zu verringern, anstatt sortden optimalen zu bestimmen. Sort führt bereits eine effizientere interne Aufteilung und Zusammenführung durch. Ich bezweifle, dass diese zusätzliche Aufteilung helfen wird.
Stéphane Chazelas