¿La forma más rápida de hacer muchas escrituras pequeñas, ciegas en un archivo enorme (en C++)?

Question

Tengo algunos archivos muy grandes (> 4 GB) que contienen (millones de) registros binarios de longitud fija. Quiero (eficientemente) unirlos a registros en otros archivos escribiendo punteros (es decir, números de registro de 64 bits) en esos registros en desplazamientos específicos.

Para elaborar, tengo un par de listas de tuplas (clave, número de registro) ordenadas por clave para cada unión que quiero realizar en un par de archivos dado, por ejemplo, A y B. iteración a través de un par de lista y Al hacer coincidir las teclas, se obtiene una lista de tuplas (clave, número de registro A, número de registro B) que representan los registros combinados (suponiendo una asignación de 1: 1 para simplificar). Para completar la unión, conceptualmente necesito buscar cada registro A en la lista y escribir el número de registro B correspondiente en el desplazamiento apropiado, y viceversa. Mi pregunta es ¿cuál es la forma más rápida de hacer esto?

Dado que la lista de registros unidos se ordena por clave, los números de registro asociados son esencialmente aleatorios. Suponiendo que el archivo es mucho más grande que la memoria caché de disco del sistema operativo, hacer muchas búsquedas y escrituras aleatorias parece extremadamente ineficiente. Intenté clasificar parcialmente los números de registro colocando las asignaciones A-> B y B-> A en una matriz dispersa, y vaciando los grupos más densos de entradas en el disco cada vez que me quedo sin memoria. Esto tiene el beneficio de aumentar en gran medida las posibilidades de que los registros apropiados se almacenen en caché para un clúster después de actualizar su primer puntero. Sin embargo, incluso en este punto, ¿es generalmente mejor hacer un montón de búsquedas y escrituras ocultas, o leer fragmentos del archivo manualmente, actualizar los punteros apropiados y volver a escribir los fragmentos? Si bien el método anterior es mucho más simple y el sistema operativo lo puede optimizar para hacer el mínimo de lecturas del sector (dado que conoce el tamaño del sector) y las copias (puede evitar copias leyendo directamente en búferes alineados correctamente), parece que incurrirá en una sobrecarga de syscall extremadamente alta.

Si bien me encantaría una solución portátil (incluso si implica una dependencia de una biblioteca ampliamente utilizada, como Boost), Windows y Linux modernos son los únicos imprescindibles, así que puedo hacer uso de sistemas operativos específicos API (por ejemplo, sugerencias de CreateFile o scatter/gather I/O). Sin embargo, esto puede implicar mucho trabajo incluso para probar, por lo que me pregunto si alguien me puede decir si merece la pena el esfuerzo.

Answer 1

He intentado ordenar parcialmente los números de registro colocando las asignaciones A-> B y B-> A en una matriz dispersa y vaciando los grupos más densos de entradas en el disco cada vez que me quedo sin memoria. parece que incurrirá en una sobrecarga de syscall extremadamente alta.

Puede utilizar el acceso al mapa de memoria para evitar la sobrecarga de syscall. mmap() en * NIX, y CreateFileMapping() on Windows.

Dividir el archivo lógicamente en bloques, p. 32 MB. Si necesita cambiar algo en el bloque, mmap(), modifique datos, opcionalmente msync() si lo desea, munmap() y luego muévase al siguiente bloque.

Eso habría sido algo que he intentado primero. OS leerá automáticamente lo que necesite leerse (en el primer acceso a los datos), y pondrá en cola IO de todos modos lo que quiera.

Lo importante a tener en cuenta es que el IO real no es tan rápido. Los factores de limitación de rendimiento para el acceso aleatorio son (1) el número de IO por segundo (IOPS) de almacenamiento puede manejar y (2) el número de disco busca. (El IOPS habitual está en el rango de cientos. La latencia de búsqueda habitual es de 3-5 ms.) El almacenamiento, por ejemplo, puede leer/escribir 50 MB/s: un bloque continuo de 50 MB en un segundo. Pero si tratara de parchear archivos de 50MB en bytes, entonces los tiempos de búsqueda simplemente matarían el rendimiento. Hasta cierto límite, está bien leer más y escribir más, incluso si se actualizan solo algunos bytes.

Otro límite a observar es el tamaño máximo del OS de la operación IO: depende del almacenamiento, pero la mayoría de los SO dividiría las tareas IO mayores a 128K. El límite se puede cambiar y es mejor si se sincroniza con el límite similar en el almacenamiento.

También tenga en cuenta el almacenamiento. Mucha gente olvida que el almacenamiento a menudo es solo uno. Estoy tratando de decir que iniciar crapload de hilos no ayuda con IO, a menos que tenga múltiples almacenamientos. Incluso una única CPU/núcleo es capaz de saturar fácilmente RAID10 con sus 800 IOPS de lectura y 400 límites de IOPS de escritura. (Pero un hilo dedicado por almacenamiento al menos teóricamente tiene sentido.)

Espero que ayude. Otras personas aquí a menudo mencionan Boost.Asio, con el que no tengo experiencia, pero vale la pena verificarlo.

P.S. Francamente, me encantaría escuchar otras respuestas (más informativas) a su pregunta. Ya estaba en el bote varias veces, pero no tuve la oportunidad de llegar a eso. Los libros/enlaces/etc relacionados con optimizaciones de IO (independientemente de la plataforma) son bienvenidos;)

Answer 2

Parece que puede resolver esto mediante el uso de estructuras de datos. Usted tiene tres limitaciones:

• Tiempo de acceso deberá estar razonablemente rápida
• datos deben mantenerse ordenadas
• Usted está en un disco giratorio

B+ Trees fueron creados específicamente para tratar el tipo de la carga de trabajo que está tratando aquí. Hay varios enlaces a implementaciones en el artículo de Wikipedia vinculado.

Esencialmente, un árbol B + es un árbol de búsqueda binario, excepto que los grupos de nodos se mantienen juntos en grupos. De esta forma, en lugar de tener que buscar cada nodo, el árbol B + carga solo un trozo a la vez. Y mantiene un poco de información para saber qué fragmento va a necesitar en una búsqueda.

EDIT: Si usted necesita para ordenar por más de un elemento, se puede hacer algo como:

+--------+-------------+-------------+---------+ 
| Header | B+Tree by A | B+Tree by B | Records | 
+--------+-------------+-------------+---------+ 
     || ^ | ^ |  ^
     |\------/  |  | |   | 
     \-------------------/ |   | 
        |   |   | 
        \----------+----------/ 

es decir, tiene árboles B + separados para cada clave, y una lista separada de registros, punteros a los que se almacenan en los árboles B +.

Answer 3

En lugar de crear una lista de (clave, número de registro A, número de registro B) omitiría la tecla para ahorrar espacio y simplemente compilar (número de registro A, número de registro B). Ordenaría esa tabla o archivo por los A's, buscaría secuencialmente cada registro A, escribiría el número B, luego ordenaría la lista por B, buscaría secuencialmente cada registro B, escribiría el número A.

que estoy haciendo manipulaciones de archivos grandes muy similares, y estas máquinas más nuevas son tan condenadamente rápido que no toma mucho tiempo en absoluto:

En un cheapo de 2,4 GHz HP Pavilion con 3 GB de RAM y Vista de 32 bits , escribir 3 millones de registros secuenciales de 1.008 bytes en un nuevo archivo lleva 56 segundos, utilizando las rutinas de la biblioteca Delphi (a diferencia de la API de Win).

Buscar secuencialmente cada registro en el archivo y escribir 8 bytes utilizando Win API FileSeek/FileWrite en una máquina con arranque demora 136 segundos. Eso son 3 millones de actualizaciones. Inmediatamente volver a ejecutar el mismo código lleva 108 segundos, ya que el O/S tiene algunas cosas en la memoria caché.

Primero, la ordenación de los desplazamientos de registros y luego la actualización secuencial de los archivos es el camino a seguir.

Answer 4

El acceso aleatorio al disco tiende a ser órdenes de magnitud más lentas que el acceso secuencial al disco. Tanto es así que puede ser útil elegir algoritmos que pueden sonar muy ineficientes a primera vista. Por ejemplo, puede intentar esto:

Cree su índice de unión, pero en lugar de usarlo, simplemente escriba la lista de pares (índice A, índice B) en un archivo de disco.

Ordene este nuevo archivo de pares por el índice A. Use un algoritmo de clasificación diseñado para la clasificación externa (aunque no lo he probado, la biblioteca STXXL de stxxl.sourceforge.net parecía prometedora cuando estaba investigando un problema similar)

Camine de forma secuencial por el archivo de registro A y lista de pares ordenados Lea una gran parte, haga todos los cambios relevantes en la memoria, escriba el fragmento. No vuelva a tocar esa parte del archivo de registro A (ya que los cambios que planificó realizar vienen en orden secuencial)

Retroceda, ordene el archivo de pares por el índice B (de nuevo, utilizando una clasificación externa). Use esto para actualizar el archivo de registro B de la misma manera.