Dado un conjunto de datos de 1 TB en el disco con alrededor de 1 KB por registro de datos, ¿cómo puedo encontrar duplicados utilizando 512 MB de RAM y espacio en disco infinito?

Las soluciones ofrecidas hasta ahora parecen demasiado complicadas. Un Bloom filter , mientras que es la estructura de datos du jour durante los últimos años, no se aplica mejor en una situación como esta: debido a que no se pueden asociar datos con el contenido hash, no solo debe mantener el filtro Bloom, sino que aún debe registrar cada uno (¡solo 6 bits!) valor de hash y registro en disco, destruyendo el beneficio del filtro bloom y teniendo una tasa de colisión ridículamente alta.

Sobre el por otro lado, la ordenación combinada de todo el terabyte no solo va a tomar O(n log n) comparaciones, sino O(n log n) tráfico de disco, ya que la mayoría de los archivos intermedios tendrían que fusionarse desde el disco, en lugar de desde la memoria. Cualquier solución real debe tratar de reducir el tráfico de disco tanto como sea posible, ya que ese es nuestro principal cuello de botella.

Mi solución es simple, haciendo una suposición: que el terabyte de datos se registra en lo que efectivamente es un archivo.

Iterar a través de los registros de el archivo terabyte y hash ellos. Un hash criptográfico es innecesario, costoso y demasiado grande aquí; en su lugar, use algo como la versión de 64 bits de murmurhash. Puede hash más de 2 GiB / seg (mucho más rápido de lo que probablemente necesitaremos, dada la velocidad de almacenamiento en estos días) y tiene una excelente (aunque no criptográficamente segura) resistencia a la colisión. Con un hash de 64 bits, esperaríamos nuestra primera colisión en 2^32, por lo que es probable que nuestros aproximadamente mil millones de registros no tener ninguna colisión en absoluto.

Escriba los hashes y sus registros asociados en otro archivo. Dado que los registros contienen datos binarios arbitrarios, no podemos confiar en sort(1) de Unix para ordenarlos, porque algunos de los hashes y offsets pueden contener lo que sort(1) interpretará como nuevas líneas. Simplemente escribiremos los registros como registros de ancho fijo (probablemente 16 bytes: 8 bytes para el hash de 64 bits de murmur2 y 8 bytes para el desplazamiento en el archivo terabyte). El archivo resultante debe ser alrededor de 16 GB, dado nuestro número de registros.

Podemos ordenar este archivo leyendo el número de registros que encajarán de forma segura en la memoria y ordenándolos, descargando los trozos ordenados de nuevo al disco. Podemos encajar más registros en la memoria con un heapsort (utiliza O(1) espacio) que con un quicksort (que utiliza O(log n) memoria para la pila de llamadas), pero en la mayoría de las implementaciones, quicksort gana en virtud de su localidad de memoria y menor número de instrucciones. Estos archivos intermedios (debe haber 35-40 de ellos) se escribirán en disco.

El último paso es fusionar estos archivos (en memoria; no hay necesidad de almacenar un resultado en el disco para esto) recogiendo todas las colisiones hash y buscando los registros asociados en el archivo terabyte, comparando los registros para la duplicación y emitiendo los registros (o sus compensaciones) de la manera que especifique el problema.

Por lo que puedo decir, esta tarea golpea el disco significativamente menos que cualquier otra solución ofrecida, y es muy conceptualmente simple: hash los registros, buscar duplicados en los hashes y verificar en los registros reales.

Para el disco I/O, sería el terabyte de datos de archivo, escribe 16 GB en el disco, leer que 16 GB de disco y escribir ordenados, a continuación, lea y devolver los duplicados. Como optimización, el proceso hash de los registros podría acumularlos en la memoria antes de descargarlos al disco, ordenándolos antes de hacerlo: eso corta el archivo intermedio de 16 GB y permite que el proceso pasar de hash directamente a fusionar e informar duplicados.

Eso es un montón de registros ;-) en el orden de 1,000,000,000. será mejor que sea inteligente...

La naturaleza de los registros no está especificada: ¿simplemente los descubrimos, uno a la vez, leiéndolos secuencialmente, o hay algún tipo de índice, o tal vez están almacenados como archivos en varios directorios? Tampoco se especifica en la pregunta la disponibilidad de un dbms que podemos usar para datos tipo índice (en lugar de tener que ordenarlo con nuestro propio código). También una idea [incluso áspera] de la el número de duplicados ayudaría a orientar algunas de las opciones hacia un proceso eficiente.

Si no existe ningún índice, podemos/debemos crear uno; esto podría hacerse como el primer paso a través de los datos. El mismo pase se usaría para producir un resumen de mensajes (un hash) para cada registro (o posiblemente, para fines de eficiencia, para los primeros cientos de bytes del registro).

La idea general es producir rápidamente un índice que se puede utilizar para identificar posible duplicados, y para finalizar la lista de duplicados reales, posiblemente a través de procesamiento paralelo .

La información útil en el índice sería:

• duración del registro
• primeros bytes del texto
• código hash (más sobre esto a continuación)
• también el desplazamiento en el archivo o cualquier puntero a los datos, pero por supuesto a diferencia de los 3 elementos anteriores, esto no se puede usar para identificar coincidencias potenciales.

La elección del hash es crítica: debería favorezca un algoritmo rápido a expensas de uno que esté perfectamente distribuido; el número de bytes hash para cada registro también es un compromiso, tal vez 100 a 200 bytes (es decir, alrededor del 10 al 20% del tamaño promedio del registro) es un buen valor, dependiendo de la proporción esperada de duplicados, y dependiendo del ahorro de tiempo que esto proporciona (en comparación con el hash de todo el registro). (ver editar más abajo)

Una vez que este índice está disponible, podemos [relativamente rápido/sin esfuerzo] obtener un recuento de posibles duplicados; sobre la base de este resultado, se puede hacer un segundo pase destinado a mejorar la calidad del índice, si no se considera lo suficientemente selectivo (dejando fuera los registros que se consideran fácilmente únicos). Esta segunda pasada puede calcular otro hash, en todo el registro (excluyendo los primeros x bytes del primer hash), o en otro subconjunto del registro. Tenga en cuenta que gracias al índice, este segundo paso puede ser multi-threaded si es posible.

La segunda o última pasada requiere ordenar la registros dentro de un grupo de posibles coincidencias (misma longitud, mismo(s) código (s) hash, mismos primeros x bytes). Esto se puede lograr como describe Pax Diablo, la ventaja del índice es que dicha operación puede, una vez más, ser multi-hilo e involucra conjuntos mucho más pequeños (muchos de ellos). Added: Here again Nick Johnson makes a great point that the second pass could possibly be unnecessary would we use a long hash code (he suggests 128 bytes long SHA1). Suponiendo que no hay ganancia en hash parcial de los registros, esta es una solución muy plausible, ya que el índice podría residir en el disco y, sin embargo, ser más rápidamente ordenados y almacenados que si estuviéramos ordenando/almacenando los registros completos.

Editar: Nick Johnson hace el punto excelente que la latencia de seeks en el almacenamiento en disco puede ser tal que una lectura secuencial simple sea más rápida y que el cuello de botella al estar unido a E / S de disco, una función hash rápida ejecutada simultáneamente puede ser efectivamente más rápida que la lectura secuencial, y por lo tanto no añadir al proceso general. Esta es una posibilidad probable (particularmente si se requiere una lectura secuencial para detectar cada inicio/fin de registro, etc.).), y es por eso que "bordeé mi apuesta" escribiendo "dependiendo del tiempo que esto proporcione...". Esto dijo que la estructura real de los registros en el disco es uno de los parámetros abiertos de la pregunta (por ejemplo, si solo estamos leyendo archivos individuales en directorios, por lo tanto, la imposición de una no secuencial leer) y también un almacenamiento de tamaño TeraByte es probablemente compatible con un RAID de lujo donde la latencia de búsqueda sin dejar de ser una preocupación suele ser mucho mejor.
Mantengo mi sugerencia de que un enfoque de dos pasesmayo ser más eficiente que uno en el que cada registro está completamente hash, pero me gustaría haber hecho hincapié en la posibilidad y los beneficios del enfoque de un solo pase. Al igual que con muchas preguntas de entrevistas, varias características de la situación en cuestión no fueron especificadas; la idea no es tanto ver al solicitante suministrar la respuesta correcta absoluta (aunque algunas respuestas pueden ser bastante erróneas!) sino más bien para obtener una visión de su proceso de pensamiento y la capacidad de identificar opciones y puntos de decisión.

Encuentre una función de hash adecuada y hash cada registro, almacenando la lista de hash con índices en un archivo. Ahora ordena el archivo hash por hash. Finalmente, verifique los registros completos de hashes coincidentes en busca de duplicados reales.

Por supuesto, depende de cuántos duplicados esperas encontrar y qué vas a hacer con la información después.

Cargue los datos en la memoria 512M a la vez, luego clasifique ese fragmento y escríbalo en el disco (como su propio archivo). Una vez que todo el 1T se ha hecho de esta manera, merge-ordena los archivos individuales en un gran archivo honkin', luego lee ese gran archivo (ordenado) secuencialmente, escribiéndolo en el archivo final mientras eliminas los registros duplicados.

1T, 512M a la vez, será de aproximadamente 2,1 millones de archivos (asumiendo las definiciones binarias de unidades SI en lugar de decimales). Los registros de 512M de 1K solo permitirán 524,288 registros en memoria a la vez, por lo que probablemente tendrá que hacer la ordenación de fusión en dos etapas. En otras palabras, merge-ordena los 2.1 millones de archivos en cuatro grupos para crear cuatro archivos más grandes, luego merge-ordena esos cuatro en el archivo ordenado grande. Entonces ese es el que procesas secuencialmente para eliminar duplicados.

Un merge-sort es simplemente fusionar varios archivos ya ordenados simplemente seleccionando el primer registro restante de cada archivo y eligiendo el "más bajo". Por ejemplo, los dos archivos a y b:

a   b
7   6
3   5
1   4
    2
 \_/
  1 (a)
  2 (b)
  3 (a)
  4 (b)
  5 (b)
  6 (b)
  7 (a)

Generar un hash de cada registro; registrar el número de registro y el hash en memoria, derramando al archivo cuando sea necesario (ordenar los datos en orden hash antes de escribir en el archivo). A medida que se te ocurra un nuevo hash, comprueba si ya existe en la memoria, eso es una detección temprana. (Eso puede o no ser un beneficio importante.).

Cuando haya leído todos los datos, tendrá varios archivos de hashes más números de registro, ya ordenados. Combina estos archivos, detectando duplicados sobre la marcha. Ni siquiera necesita hacer más que registrar los duplicados para esta aplicación, por lo que puede descartar los hashes una vez que se demuestre que son únicos.

Dados los tamaños-0.5 GB de memoria, 1000 GB de datos, 1 KB por registro, por lo que alrededor de 1 mil millones de registros-suponiendo que un hash de 256 bits (aunque 128 bits bien podría ser adecuado), estaríamos utilizando 32 bytes para el hash y 4 bytes para el número de registro, y alrededor de 1 mil millones de registros, necesitamos alrededor de 36 GB para los archivos de clasificación, generados en archivos de 500 MB (correspondientes a memoria disponible), por lo que habría 70-80 archivos para fusionar al final, lo que parece bastante manejable. La lista le daría los números de registro - entonces tendría que acceder al archivo de 1 TB para leer los registros. Necesitas pensar un poco en lo que vas a hacer con los duplicados; necesitas la información sobre el registro inicial y los extras, y importa cuál de los duplicados conservas y cuál rechazas. Sucesivamente.

Primero, configure el equipo con un archivo swap infinitamente grande en una unidad infinitamente grande...

Puede usar un hash para reducir el tamaño del problema. Por ejemplo, si tiene datos de 1 TB, entonces define una función hash y los datos se dividen en diez archivos (el tamaño de cada archivo es inferior a 1 TB). Después de eso, si un archivo sigue siendo demasiado grande, repita el procedimiento hasta que el archivo se pueda almacenar en la memoria. Finalmente, puede contar los tiempos de aparición por orden.