Escalabilidad de 'sort -u' para archivos gigantes

23

¿Cuál es el límite de escalabilidad razonable de 'sort -u'? (en dimensiones de "longitud de línea", "cantidad de líneas", "tamaño de archivo total"?)

¿Cuál es la alternativa de Unix para archivos que exceden esto en la dimensión de "cantidad de líneas"? (Por supuesto, puedo implementar fácilmente uno, pero me preguntaba si hay algo que se pueda hacer con pocos comandos estándar de Linux).

sort Grzegorz Wierzowiecki
fuente
Para aquellos que quieran realizar una búsqueda binaria o saber cómo hacerlo
Grzegorz Wierzowiecki
2
Hay situaciones donde a uniqantes de las sort -uayudas. Por cierto, para los datos ASCII LC_ALL=C sort, GNU acelera sortmuchísimo (vea esta respuesta )
Walter Tross

Respuestas:

39

Lo sortque encuentra en Linux proviene del paquete coreutils e implementa una fusión externa R-Way . Divide los datos en fragmentos que puede manejar en la memoria, los almacena en el disco y luego los fusiona. Los fragmentos se realizan en paralelo, si la máquina tiene los procesadores para eso.

Entonces, si hubiera un límite, es el espacio libre en el disco que sortpuede usar para almacenar los archivos temporales que tiene que combinar, combinados con el resultado.

Anthon
fuente
3
Tenga en cuenta que GNU sort puede comprimir esos archivos temporales para empacar aún más (y aumentar el rendimiento con discos lentos).
Stéphane Chazelas
1
@ StéphaneChazelas Gracias por la actualización. Me preguntaba si la ordenación era lo suficientemente inteligente como para eliminar archivos fragmentados cuando uno está completamente fusionado (lo que podría suceder fácilmente si la fuente ya está parcialmente ordenada) como una optimización de espacio. No tengo tiempo para sumergirme en el código fuente en estos días :-(
Anthon
3
Además de la memoria, también hay otro límite que se aplica a la fase de fusión: la cantidad de archivos que se pueden abrir simultáneamente. Este es típicamente un límite impuesto por el sistema operativo. GNU sort también lo hace, al fusionar recursivamente la cantidad de archivos que puede abrir de una vez.
Diomidis Spinellis
@ StéphaneChazelas Si estuviera diseñando una herramienta específica para ordenar archivos muy grandes, almacenaría las líneas como un índice en el archivo original. ¿GNU sort hace esto, o simplemente usa un algoritmo de compresión convencional?
Random832
3
@ Random832 y está destinado a poder sobrescribir el archivo sobre sí mismo ( sort -o file file)
Stéphane Chazelas
1

No puedo hablar de implementaciones específicas del proveedor, pero la UNIX sortimplementación divide archivos grandes en archivos más pequeños, clasifica estos archivos y luego combina los archivos más pequeños ordenados en una salida ordenada agregada.

La única limitación es el espacio en disco para los archivos más pequeños creados de forma intermedia sort, pero los archivos se pueden redirigir a un directorio arbitrario configurando la variable de entorno TMPDIR.

astuto
fuente
3
¿Cómo se llama exactamente la implementación de ordenamiento UNIX ? ¿Es el original de Unix versión 3? La página del manual allí dice que no puede ordenar archivos de más de 128 KB.
Stéphane Chazelas
¿Qué entiendes por Unix versión 3? ¿La versión de 1973? La implementación original de tipo UNIX se ha mejorado a lo largo de los años y IIRC, la versión Solaris es incluso mucho más rápida que la versión GNU. Por supuesto, hace 25 años se mejoró la clasificación para comprender los caracteres de varios bytes y lo que recuerdo de una discusión de USENET fue que esto se ha hecho de manera eficiente en Solaris. Por cierto: man largefileenumera sortcomo archivo de gran tamaño.
schily
2
Entonces, ¿estás hablando de la versión específica del proveedor de Oracle sort? ¿O alguna derivada de alguna versión del tipo AT&T Unix? ¿O alguna versión certificada de Unix de sort(como GNU sorten OS / X)?
Stéphane Chazelas
La calidad de las sortimplementaciones modernas con respecto a los caracteres de varios bytes puede variar, el hecho de que sortuse archivos intermedios divididos es común a todas las implementaciones de UNIX que se basan en el código original. Por cierto: la versión de Solaris es OSS como "OpenSolaris", consulte sourceforge.net/p/schillix-on/schillix-on/ci/default/tree/usr/…
schily
Hace 25 años, UTF-8 aún no se inventó? El soporte para configuraciones regionales UTF-8 se agregó en Solaris 7 ( 1 , 2 ). ¿Te refieres a algún otro conjunto de caracteres multibyte?
Stéphane Chazelas
1

Basado en https://blog.mafr.de/2010/05/23/sorting-large-files/ y /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

Actualizar:

De las respuestas anteriores vemos que sortya hace lo que mencionó el fragmento, es decir , la fusión externa de R-Way . Entonces, después de todo corriendo solo:

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

Debería ser suficiente

Mis suposiciones actuales (sin verificar el código) sobre los límites son:

  • La longitud máxima de la línea está limitada por la cantidad de memoria física. Ordenar necesita caber al menos dos en la memoria
  • cantidad de líneas: no tengo conocimiento de
  • tamaño de archivo, por supuesto, por sistema de archivos
  • cantidad de archivos abiertos en paralelo, dependiendo del sistema operativo (¡Gracias Diomidis Spinellis por señalar esto!)

(Esta respuesta está marcada como wiki de la comunidad ; ¡siéntase animado a mejorarla! :))

rev. Grzegorz Wierzowiecki
fuente
2
GNU se sortordena en paralelo de forma predeterminada (desde 2010 después de esa página a la que está enlazando), --parallelhay que reducir el número de hilos concurrentes en lugar de permitir sortdeterminar el óptimo. Ordenar ya se divide y fusiona internamente de una manera más eficiente. Dudo que la división adicional ayude.
Stéphane Chazelas