c# - tecnicas - Necesita una forma de ordenar un archivo de registro de 100 GB por fecha
programa para organizar archivos y carpetas (16)
Entonces, por alguna extraña razón, termino con un archivo de registro de 100 GB que no está ordenado (en realidad está parcialmente ordenado ), mientras que los algoritmos que intento aplicar requieren datos ordenados. Una línea en el archivo de registro se ve así
data <date> data data more data
Tengo acceso a C # 4.0 y aproximadamente 4 GB de RAM en mi estación de trabajo. Me imagino que fusionar, algún tipo sería lo mejor aquí, pero a parte de implementar estos algoritmos yo mismo, quiero preguntar si hay algún tipo de atajo que pueda tomar.
Incidentalmente, el análisis de la cadena de fecha con DateTime.Parse() es muy lento y requiere mucho tiempo de CPU. El ritmo de chugging es mísero de 10 MB / seg. ¿Hay una manera más rápida que la siguiente?
public static DateTime Parse(string data)
{
int year, month, day;
int.TryParse(data.Substring(0, 4), out year);
int.TryParse(data.Substring(5, 2), out month);
int.TryParse(data.Substring(8, 2), out day);
return new DateTime(year, month, day);
}
Escribí eso para acelerar DateTime.Parse() y en realidad funciona bien, pero todavía está tomando una carga de ciclos.
Tenga en cuenta que para el archivo de registro actual, también estoy interesado en horas, minutos y segundos. Sé que puedo proporcionar DateTime.Parse () con el formato, pero eso no parece acelerarlo demasiado.
Estoy buscando un empujón en la dirección correcta, gracias de antemano.
EDITAR : Algunas personas me han sugerido que use una comparación de cadenas para comparar fechas. Eso funcionaría para la fase de clasificación, pero necesito analizar las fechas de los algoritmos. Todavía no tengo idea de cómo ordenar archivos de 100 GB en 4 GB de memoria ram gratuita, sin hacerlo manualmente.
EDIT 2 : Bueno, gracias a varias sugerencias de que utilizo Windows Sort , descubrí que hay una herramienta similar para Linux . Básicamente llama a sort y lo arregla todo para usted. Mientras hablamos está haciendo algo , y espero que termine pronto. El comando que estoy usando es
sort -k 2b 2008.log > 2008.sorted.log
-k especifica que quiero ordenar en la segunda fila, que es una cadena de fecha y hora en el YYYY-MM-DD hh:mm:ss.msek usual YYYY-MM-DD hh:mm:ss.msek . Debo admitir que las páginas de manual carecen de explicaciones sobre todas las opciones, pero encontré muchos ejemplos al ejecutar info coreutils ''sort invocation'' .
Informaré con resultados y tiempos. Esta parte del registro es de aproximadamente 27 GB. Estoy pensando en clasificar 2009 y 2010 por separado y luego fusionar los resultados en un solo archivo con la opción sort -m.
Editar 3 Bueno, comprobar iotop sugiere que está leyendo en pequeños fragmentos del archivo de datos y luego haciendo algo furiosamente para procesarlos. Este proceso parece ser bastante lento. = (
sort no usa ninguna memoria, y solo un núcleo único. Cuando lee datos del disco, no procesa nada. ¿Estoy haciendo algo mal?
Editar 4 Tres horas y sigue haciendo lo mismo. Ahora estoy en esa etapa en la que quiero intentar jugar con los parámetros de la función, pero tengo tres horas invertidas ... abortaré en unas 4 horas y trataré de calcularlo de la noche a la mañana con una memoria más inteligente y parámetros espaciales ...
Editar 5 Antes de ir a casa, reinicié el proceso con el siguiente comando:
sort -k 2b --buffer-size=60% -T ~/temp/ -T "/media/My Passport" 2010.log -o 2010.sorted.log
Devolvió esto, esta mañana:
sort: write failed: /media/My Passport/sortQAUKdT: File too large
¡Wraawr! Pensé que simplemente agregaría tantos discos duros como fuera posible para acelerar este proceso. Aparentemente agregar una unidad USB fue la peor idea de la historia. Por el momento no puedo decir si se trata de FAT / NTFS o algo así, porque fdisk me está diciendo que la unidad USB es un "dispositivo incorrecto" ... no es broma. Trataré de darle otra oportunidad más tarde, por ahora vamos a poner este proyecto en la pila tal vez fallida.
Aviso final Esta vez funcionó, con el mismo comando que el anterior, pero sin el problemático disco duro externo. ¡Gracias por toda tu ayuda!
Benchmarking
Utilizando 2 discos duros con grado de estación de trabajo (al menos 70mb / seg de lectura / escritura IO) en el mismo controlador SATA, me tomó 162 minutos ordenar un archivo de registro de 30 GB. Necesitaré ordenar otro archivo de 52 GB esta noche, publicaré cómo funciona.
Necesito analizar las fechas de los algoritmos.
En * NIX, en general, primero habría convertido las fechas en algo simple, adecuado para la comparación de texto y la primera palabra en la cadena. Es muy temprano para la creación de objetos de fecha / hora. Mi presentación de fecha habitual es YYYYMMDD-hhmmss.millis . Asegúrese de que todos los archivos tengan el mismo formato de fecha.
Todavía no tengo idea de cómo ordenar archivos de 100 GB en 4 GB de memoria ram gratuita, sin hacerlo manualmente.
Como ya lo has descubierto, fusionar es la única opción.
Entonces, para mí, las tareas se encuentran en el siguiente paso:
conversión tonta para hacer fechas ordenables. Complejidad: leer / escribir secuencialmente 100 GB.
Divida los datos en fragmentos de tamaño utilizable, por ejemplo, 1 GB y clasifique cada fragmento utilizando una ordenación sencilla y rápida antes de escribirlo en el disco. Complejidad: leer / escribir secuencialmente 100 GB; memoria para ordenar rápidamente.
fusionar-ordenar los archivos pequeños en uno grande. Uno puede hacerlo paso a paso, usando un programa que toma dos archivos y los fusiona en uno nuevo. Complejidad: leer / escribir secuencialmente 100 GB de registro (N) veces (donde N es el número de archivos). Requisito de espacio HDD: 2 * 100 GB (última combinación de 2 archivos de 50 GB en un solo archivo de 100 GB).
Un programa para automatizar el paso anterior: elija dos (por ejemplo, los más pequeños), inicie el programa para clasificarlos en un nuevo archivo, elimine los dos archivos originales. Repita hasta que el número de archivos sea mayor que 1.
(Opcional) divida el archivo ordenado de 100 GB en trozos más pequeños de tamaño manejable. Después de todo, harás algo con ellos. Numerarlos secuencialmente o poner sellos de la primera y la última vez en el nombre del archivo.
Concepto general: no intente encontrar una manera de hacerlo rápido, la tubería de 100GB tomaría tiempo de todos modos; planifique los programas uno a cada paso para que se ejecuten durante la noche como un lote, sin su atención.
En Linux, todo es factible con shell / sort / awk / Perl, y no creo que sea un problema escribirlo en cualquier otro lenguaje de programación. Esto es potencialmente 4 programas, pero todos son bastante simples de codificar.
¿Por qué no pruebas esta herramienta relativamente desconocida de Microsoft llamada microsoft.com/downloads/en/… ? Básicamente, le permite hacer una consulta SQL sobre un archivo CSV (o cualquier otro archivo de texto con formato).
Le ahorra la molestia de bombearlo a una base de datos, hacer su tipo y bombearlo nuevamente
Además de lo que sea que esté haciendo (probablemente, la sugerencia de willw sea útil), su análisis se podría realizar en múltiples subprocesos siempre que tenga múltiples procesadores o núcleos de procesador.
Arranque un sabor de Linux desde USB Y use el comando while para leer el archivo. Utiliza grep, filtros y tuberías para segregar los datos. Todo esto se puede hacer en 3 líneas de un script BASH. Grep revisará los datos en No hay tiempo. He grepped a través de 7 millones de líneas en 45 segundos
Comentario preventivo: mi respuesta solo aborda el sub-problema de analizar valores de fecha y hora.
DateTime.Parse contiene controles para todos los posibles formatos de fecha. Si tiene un formato de corrección, puede optimizar el análisis bastante bien. Una optimización simple sería convertir los caracteres directamente:
class DateParserYyyyMmDd
{
static void Main(string[] args)
{
string data = "2010-04-22";
DateTime date = Parse(data);
}
struct Date
{
public int year;
public int month;
public int day;
}
static Date MyDate;
static DateTime Parse2(string data)
{
MyDate.year = (data[0] - ''0'') * 1000 + (data[1] - ''0'') * 100
+ (data[2] - ''0'') * 10 + (data[3] - ''0'');
MyDate.month = (data[5] - ''0'') * 10 + (data[6] - ''0'');
MyDate.day = (data[8] - ''0'') * 10 + (data[9] - ''0'');
return new DateTime(MyDate.year, MyDate.month, MyDate.day);
}
}
En realidad, no tengo muchas ideas sobre la conversión de fechas, pero las cosas que trataría de usar para hacer eso son:
- Una base de datos con un índice en la columna de fecha (para ser fácil de buscar en estos datos después).
- Para Insertar en esta base, use la inserción masiva.
- Y una forma de paralela a la lectura (en el sentido de que LINQ paralelo sería bueno y es muy fácil de usar).
- Mucha paciencia (lo más importante / difícil)
Guau. En primer lugar, ese es un nivel completamente nuevo de obsesión documental.
Mi aplicación real sería, trate de considerar qué tan necesario es este archivo.
Acerca de la ordenación, no tengo idea si esto funcionará o no, pero es posible que desee intentar construir un Enumerator que devuelva los datos directamente desde el disco duro (no guardando nada excepto algunos punteros), y luego tratar de usar el orden de LINQ. , que también devuelve IEnumerator, que usted, con suerte, puede Enamurate y guardar directamente en el disco.
La única pregunta es si OrderBy guarda algo en la RAM.
La mejor forma de optimizar el análisis de las fechas es no analizarlas en absoluto.
Como las fechas están en formato ISO 8601, puede simplemente compararlas como cadenas. No hay ningún análisis necesario en absoluto.
En cuanto a la clasificación, debería poder utilizar efectivamente el hecho de que está parcialmente ordenada. Un enfoque podría ser leer el archivo y escribir en archivos separados divididos en rangos de tiempo, por ejemplo, por día o por hora. Si hace que cada archivo sea lo suficientemente pequeño, puede leerlos en la memoria y ordenarlos, y luego fusionar todos los archivos.
Otro enfoque podría ser leer el archivo y escribir los registros que están en orden en un archivo, y los otros en otro archivo. Ordene el segundo archivo (posiblemente usando este proceso recursivamente si es grande) y comprima los dos archivos juntos. Es decir, un tipo de combinación modificada.
No realmente como una solución, sino solo por interés, una forma de hacerlo así:
- Primero divide el archivo en archivos de 1GB
- Luego, leyendo 2 archivos a la vez, cargue los contenidos en una lista de cadenas y ordene
- Escríbalo nuevamente en los archivos individuales.
El problema es que necesitaría leer / escribir 100 archivos en cada pasada y hacer 100 pases para asegurarse de que los datos estén ordenados.
Si mi matemática es correcta: Eso es 10 000 GB de lectura y 10 000 GB de escritura, a un promedio de 10MB / sec que es 20 000 000 seg que son 231 días
Una forma en que podría funcionar es escanear el archivo una vez y escribir en archivos más pequeños, uno para cada período de tiempo, por ejemplo, día u hora. Luego ordena estos archivos individuales.
Para ordenar, puede implementar una clasificación de depósito basada en archivos:
- Abrir archivo de entrada
- Leer el archivo línea por línea
- Obtener la fecha como cadena de línea
- Añadir línea al archivo
<date>.log
El resultado sería un archivo de registro por separado para cada día o por separado para cada hora. Elija para que obtenga archivos de un tamaño que pueda ordenar fácilmente.
La tarea restante sería ordenar los archivos creados y posiblemente fusionar el archivo nuevamente.
Puede intentar implementar el algoritmo de ordenación de radix. Debido a que radix escanea la lista completa de forma secuencial y solo unas pocas veces, puede ayudar aquí a evitar una gran cantidad de escaneos y búsquedas de su archivo de 100 GB.
El género Radix tiene la intención de clasificar sus registros en cada iteración por una parte. Esta parte puede ser un dígito, o una parte de fecha y hora como año, mes, día. en este caso, ni siquiera necesita convertir la cadena en DateTime, solo puede convertir la parte específica en int.
Editar:
Para fines de clasificación, puede crear un archivo binario temporal con solo 2 columnas: DateTime (DateTime.ToBinary () como Int64) y la dirección de línea en el archivo de origen (como Int64).
Luego obtendrá un archivo mucho más pequeño con registros de tamaño fijo, solo 16 bytes por registro, luego podrá ordenarlo mucho más rápido (las operaciones IO serán más rápidas al menos).
Una vez que termine de ordenar el archivo temporal, puede volver a crear el archivo de registro completo de 100 GB.
Respuesta corta: cargue los datos en una base de datos relacional, por ejemplo, Sql Express, cree un índice y use una solución basada en cursor, por ejemplo, DataReader, para leer cada registro y escribirlo en el disco.
Si una ordenación de cadena funciona para usted, simplemente use el comando SORT de Windows. Ordene el archivo y termine con él. Con gusto clasificará su archivo de 100 GB y es fácil de usar.
Si necesita filtrar y convertir el archivo, específicamente el campo de fecha, entonces simplemente escribiría un pequeño programa de conversión que convierta el campo de datos en un entero lleno 0 (como el número de segundos desde 1970, o lo que quiera), y reescribe el registro. Luego puede canalizar (|) la salida en el comando ordenar, luego tiene un archivo final ordenado que su programa de utilidad analiza más fácilmente.
Creo que el error que estás cometiendo es simplemente intentar hacer esto de una vez. 100 GB de datos son muchos y lleva algo de tiempo copiarlos, pero no demoran tanto. Ya que tiene que ordenarlo, ya debe tratar con una copia del archivo en algún momento (es decir, necesita tanto espacio libre en su máquina para manejar ambas copias en algún momento), incluso con una rutina de clasificación externa como tipo de fusión .
Escribir un reformateador simple y conectarlo para clasificarlo le ahorrará un par de viajes a través del archivo y ahorrará espacio en el disco, ya que inevitablemente solo necesitará las dos copias.
También modificaría el formateador para que dibujara solo los campos en los que estoy realmente interesado, y haré todo el análisis "pesado" en ese punto, de modo que con lo que terminas es esencialmente un archivo formateado que se maneja fácilmente con tus rutinas de generación de informes . De esta forma, ahorrará tiempo más tarde cuando pueda ejecutar sus informes más de una vez.
Use un CSV simple o, mejor aún, un formato de archivo de longitud fija para la salida si es posible.
Asegúrese de que la información de su fecha, si elige usar un número entero, tenga todos los campos con la misma longitud. De lo contrario, la utilidad SORT no los clasificará correctamente (terminará con 1 10 2 3 en lugar de 1 2 3 10. Es mejor tener 01 02 03 10.).
Editar -
Vamos a abordarlo desde un tacto diferente.
La pregunta más importante es "¿necesita todos estos datos?". Esto se relaciona con la sugerencia anterior sobre hacer el análisis pesado primero. Obviamente, cuanto más puedas reducir el conjunto inicial, mejor. Por ejemplo, simplemente eliminar el 10% de los datos es de 10 GB.
Algo que me gusta pensar como regla general, especialmente cuando se trata de una gran cantidad de datos: "Si tienes 1 millón de algo, entonces cada milisegundo guardado, está a 20 minutos de la línea de fondo".
Normalmente, realmente no pensamos en términos de milisegundos para nuestro trabajo, es más "asiento de los pantalones", "eso se siente más rápido". Pero el 1 ms == 20min / millón es una buena medida para comprender con qué cantidad de datos está tratando, y cuánto tiempo deberían / deberían pasar.
Para su caso, 100GB de datos. Con un botín de 100 bytes por registro, está tomando 1 mil millones de filas. 20,000 minutos por milisegundo. - 5 1/2 horas. trago (Es una regla de oro, si haces los cálculos, esto no funciona).
Por lo tanto, puede apreciar el deseo de reducir los datos brutos si es posible.
Esa fue una de las razones por las que aplacé el comando de Windows SORT. Es un proceso básico, pero uno afectado por los matices, y uno que puede usar algo de optimización. La gente que escribió SORT tuvo tiempo y oportunidad de hacerlo "óptimo" de muchas maneras. Si lo hicieron o no, no puedo decirlo. Pero es una suposición razonable de que pondrían más tiempo y atención en este proceso para hacer que su CLASIFICACIÓN sea tan buena como práctica, en comparación con usted que tiene una fecha límite ajustada.
Existen utilidades de clasificación de terceros para grandes conjuntos de datos, que probablemente (idealmente) funcionen mejor para ese caso. Pero esos no están disponibles para ti (puedes conseguirlos, pero no creo que quisieras salir corriendo y obtener otra utilidad de inmediato). Entonces, SORT es nuestra mejor suposición por ahora.
Dicho esto, la reducción del conjunto de datos obtendrá más que cualquier utilidad de clasificación.
¿Cuántos detalles necesitas realmente? ¿Y cuánta información realmente rastrea? Por ejemplo, si fuera, digamos, estadísticas web, puede tener 1000 páginas en su sitio. Pero incluso con números por hora durante un año, 365 * 24 * 1000, eso son solo 8,7 millones de "cubos" de información, muy lejos de 1B.
Entonces, ¿hay algún preprocesamiento que pueda hacer que no requiera clasificación? ¿Resumiendo la información en una granularidad más grosera? Puede hacerlo sin ordenar, simplemente usando mapas hash basados en memoria. Incluso si no tiene "suficiente memoria" para procesar los 100 GB de datos en un solo lanzamiento, probablemente tenga suficiente para hacerlo en fragmentos (5 fragmentos, 10 fragmentos) y escriba los resultados intermedios.
También puede tener mucha más suerte dividiendo los datos también. En trozos de archivos mensuales o semanales. Tal vez eso no se haga fácilmente porque los datos están "en su mayoría" ordenados. Pero, en ese caso, si es por fecha, los delincuentes (es decir, los datos que están fuera de orden) bien pueden agruparse dentro del archivo, con las cosas "fuera de servicio" mezclándose en las barreras de los períodos ( como en las transiciones diarias, tal vez tenga filas como 11:58 p.m., 11:59 p.m., 00:00 a.m., 00:01 a.m., 11:58 p.m., 00:02 p.m.). También podría aprovechar esa heurística.
El objetivo es que si puede determinar determinísticamente de alguna manera el subconjunto que está fuera de servicio y dividir el archivo en fragmentos de datos "en orden" y "datos fuera de servicio", su tarea de clasificación puede ser MUCHO más pequeña. Ordene las pocas filas que están desordenadas, y luego tiene un problema de fusión (mucho más simple que un problema de clasificación).
Entonces, esas son tácticas que puede tomar para abordar el problema. La sumatoria es obviamente la mejor, ya que cualquier cosa que reduzca esta carga de datos en cualquier medida, probablemente valga la pena. Por supuesto, todo se reduce a lo que realmente quiere de los datos, claramente los informes lo conducirán. Este también es un buen punto acerca de la "optimización pre-madura". Si no informan, no lo proceses :).
Solo para responder a su pregunta sobre la clasificación de un archivo largo que no cabe en la memoria, deberá usar algún algoritmo de ordenación externo como Merge sort. El proceso es más o menos el siguiente:
Particiona la entrada en varias partes que se ajustan a la memoria y se pueden ordenar usando algoritmos de clasificación en memoria estándar (por ejemplo, 100 MB o más, tendrás que mantener ~ 4 partes en la memoria a la vez). Ordene todas las partes y escríbalas en el disco.
Lea dos partes del disco (las dos están ordenadas) y combínelas, lo que se puede hacer simplemente iterando simultáneamente sobre las dos entradas. Escriba el conjunto de datos combinados en otro lugar del disco. Tenga en cuenta que no necesita leer toda la parte en la memoria, simplemente léala / escríbala en bloques sobre la marcha.
Repita la fusión de partes hasta que tenga solo una parte (que se clasificará con todos los datos de su conjunto de datos de entrada original).
Usted mencionó que los datos ya están parcialmente ordenados, por lo que sería una buena idea seleccionar algún algoritmo para la clasificación en memoria (en la primera fase) que sea eficiente en este caso. Puede ver algunas sugerencias en esta pregunta (aunque no estoy seguro de si la respuesta será la misma para conjuntos de datos muy grandes, y depende de qué tan parcialmente clasificada sea la entrada).
Suponiendo que su archivo de registro solo tiene el 1-2% de las filas desordenadas, puede hacer una sola pasada a través del registro completo, generando dos archivos: un archivo en orden y otro archivo que contiene el 1-2% de las filas que están fuera de servicio Luego, clasifique las filas fuera de orden en la memoria y realice una sola combinación de las filas anteriormente fuera de servicio con las filas en orden. Esto será mucho más rápido que un mergesort completo que hará muchos más pases.
Suponiendo que su archivo de registro no tiene una fila de más de N filas fuera de lugar, puede hacer una sola pasada a través del registro con una cola ordenada de N filas de profundidad. Siempre que encuentre una fila de registro que está fuera de servicio, simplemente insértela en el lugar correcto de la cola. Dado que esto solo requiere un pase único a través del registro, será lo más rápido posible.
Un código como este está completamente vinculado por la velocidad con la que puede sacar los datos del disco. El archivo simplemente nunca puede caber en la memoria caché del sistema de archivos, por lo que siempre estará esperando que el disco suministre los datos. Te va bastante bien con 10 MB / s, optimizar el código nunca va a tener un efecto discernible.
Obtenga un disco más rápido. Defrag el que tienes como un paso intermedio.