Évolutivité de «sort -u» pour des fichiers gigantesques

23

Quelle est la limite d'évolutivité raisonnable de «sort -u»? (en "longueur de ligne", "nombre de lignes", "taille totale du fichier"?)

Quelle est l'alternative Unix pour les fichiers dépassant cette dimension de "quantité de lignes"? (Bien sûr, je peux facilement en implémenter un, mais je me demandais s'il y avait quelque chose qui pouvait être fait avec quelques commandes Linux standard?)

sort Grzegorz Wierzowiecki
la source
Pour ceux qui pourraient vouloir faire une recherche binaire ou savoir comment: unix.stackexchange.com/q/247508/9689
Grzegorz Wierzowiecki
2
Il y a des situations où un uniqavant l' sort -uaide. BTW, pour les données ASCII LC_ALL=C sortaccélère sorténormément GNU (voir cette réponse )
Walter Tross

Réponses:

39

Le sortque vous trouvez sur Linux provient du package coreutils et implémente une fusion External R-Way . Il divise les données en morceaux qu'il peut gérer en mémoire, les stocke sur disque puis les fusionne. Les morceaux se font en parallèle, si la machine a les processeurs pour ça.

Donc, s'il devait y avoir une limite, c'est l'espace disque libre qui sortpeut être utilisé pour stocker les fichiers temporaires qu'il doit fusionner, combiné au résultat.

Anthon
la source
3
Notez que le tri GNU peut compresser ces fichiers temporaires pour les emballer encore plus (et augmenter les performances avec des disques lents).
Stéphane Chazelas
1
@ StéphaneChazelas Merci pour la mise à jour. Je me demandais si le tri était suffisamment intelligent pour supprimer des fichiers en morceaux quand l'un est complètement fusionné (ce qui pourrait facilement se produire si la source est déjà partiellement triée) en tant qu'optimisation de l'espace. Je n'ai pas le temps de plonger dans le code source ces jours-ci :-(
Anthon
3
Outre la mémoire, il existe également une autre limite qui s'applique à la phase de fusion: le nombre de fichiers pouvant être ouverts simultanément. Il s'agit généralement d'une limite imposée par le système d'exploitation. Le tri GNU résiste également à cela, en fusionnant récursivement le nombre de fichiers qu'il peut ouvrir en même temps!
Diomidis Spinellis
@ StéphaneChazelas Si je concevais un outil spécifiquement pour trier de très gros fichiers, je stockerais les lignes sous forme d'index dans le fichier d'origine. Le tri GNU fait-il cela ou utilise-t-il simplement un algorithme de compression conventionnel?
Random832
3
@ Random832 et il est censé pouvoir écraser le fichier sur lui-même ( sort -o file file)
Stéphane Chazelas
1

Je ne peux pas parler d'implémentations spécifiques au fournisseur, mais l' UNIX sortimplémentation divise les fichiers volumineux en fichiers plus petits, trie ces fichiers, puis combine les fichiers triés plus petits en une sortie triée agrégée.

La seule limitation est l'espace disque pour les fichiers plus petits créés de façon intermédiaire par sort, mais les fichiers peuvent être redirigés vers un répertoire arbitraire en définissant la variable d'environnement TMPDIR.

schily
la source
3
Comment appelez-vous exactement l' implémentation de tri UNIX ? Est-ce l'original de la version 3 d'Unix? La page de manuel indique qu'il ne peut pas trier les fichiers supérieurs à 128 Ko.
Stéphane Chazelas
Que comprenez-vous par Unix version 3? La version de 1973? L'implémentation de tri UNIX d'origine a été améliorée au fil des ans et IIRC, la version Solaris est encore beaucoup plus rapide que la version GNU. Bien sûr, il y a 25 ans, le tri a été amélioré pour comprendre les caractères multi-octets et ce dont je me souviens d'une discussion USENET, c'est que cela a été fait efficacement sur Solaris. BTW: man largefilerépertorie sortles fichiers volumineux.
schily
2
Parlez-vous réellement de la version spécifique au fournisseur Oracle sort? Ou tout dérivé d'une version du genre AT&T Unix? Ou toute version certifiée Unix de sort(comme GNU sortsur OS / X)?
Stéphane Chazelas
La qualité des sortimplémentations modernes par rapport aux caractères multi-octets peut varier, le fait d' sortutiliser des fichiers intermédiaires fractionnés est commun à toutes les implémentations UNIX basées sur le code d'origine. BTW: la version Solaris est OSS comme "OpenSolaris", voir sourceforge.net/p/schillix-on/schillix-on/ci/default/tree/usr/…
schily le
Il y a 25 ans, l'UTF-8 n'était pas encore inventé? La prise en charge des paramètres régionaux UTF-8 a été ajoutée dans Solaris 7 ( 1 , 2 ). Faites-vous référence à un autre jeu de caractères multi-octets?
Stéphane Chazelas
1

Basé sur https://blog.mafr.de/2010/05/23/sorting-large-files/ et /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

Mise à jour:

D'après les réponses ci-dessus, nous voyons que fait sortdéjà l'extrait mentionné - c'est-à-dire la fusion externe de R-Way . Donc, après tout, il suffit de courir:

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

Devrait être suffisant.

Mes hypothèses actuelles (sans vérifier le code) sur les limites sont les suivantes:

  • la longueur de ligne maximale est limitée par la quantité de mémoire physique. Le tri doit contenir au moins deux en mémoire
  • nombre de lignes - je ne suis pas au courant
  • taille du fichier - bien sûr par système de fichiers
  • quantité de fichiers ouverts en parallèle - selon le système d'exploitation (Merci Diomidis Spinellis pour l'avoir signalé!)

(Cette réponse est marquée comme wiki communautaire - n'hésitez pas à l'améliorer! :))

Grzegorz Wierzowiecki
la source
2
GNU sorttrie en parallèle par défaut (depuis 2010 après cette page vers laquelle vous créez un lien), --parallelil s'agit de réduire le nombre de threads simultanés au lieu de laisser sortdéterminer celui qui est optimal. Le tri effectue déjà un fractionnement et une fusion en interne de manière plus efficace. Je doute que ce fractionnement supplémentaire soit utile.
Stéphane Chazelas