Manera eficiente de agregar y eliminar duplicados de listas muy grandes (contraseñas)

Contexto:

Problema:

Necesito una forma de a) agregar todas estas contraseñas juntas yb) eliminar los duplicados exactos, dentro de las restricciones de memoria RAM y dentro de un plazo razonable (~ 7 días, idealmente mucho menos, pero realmente no me importa si demoran semanas y luego Nunca necesito correrlo de nuevo) ventana de tiempo.

Soy un progtwigdor de Python competente y, por lo tanto, ya lo he intentado varias veces. Mi bash más exitoso usó sqlite3 para almacenar las contraseñas procesadas en el disco duro a medida que avanzaba. Sin embargo, esto significó que realizar un seguimiento de los archivos que ya se habían completado entre las instancias de procesamiento (cancelé y reinicié varias veces para realizar cambios) se logró tediosamente mediante el hashing de cada archivo completado y el mantenimiento / la comparación cada vez que se abre un nuevo archivo. Sin embargo, para los archivos muy grandes, cualquier progreso se perdería.

Estaba procesando los archivos de texto en bloques de ~ 1 billón (a lo sumo) líneas a la vez para evitar el agotamiento de la memoria sin tener retroalimentación durante largos períodos de tiempo. Sé que podría, teniendo mucho tiempo poblando mi base de datos completamente, ya que logré un tamaño de archivo DB de ~ 4.5Gb en 24 horas de tiempo de ejecución, así que estimo que faltaría unos 4 días como máximo para superar todo, pero no sé si / cómo leerlo / escribirlo de manera más eficiente ni tengo buenas ideas sobre cómo abordar la eliminación de duplicados (hágalo cuando estoy poblando la base de datos o hago pases adicionales luego … ¿Existe un medio mucho más rápido para hacer búsquedas de singularidad en una configuración de base de datos que no conozco?).


Mi solicitud hoy aquí es para consejos / soluciones para un enfoque de progtwigción y optimización sobre cómo lograr mi lista de contraseñas única y gigante (idealmente con Python). Estoy totalmente abierto a tomar una táctica completamente diferente si ya estoy fuera de lugar.


Dos agradables que tenemos son:

  • Una forma de agregar más contraseñas en el futuro sin tener que reconstruir la lista completa; y

  • Una base de datos de <20Gb al final de todo esto para que no sea un gran dolor moverse.


Solución

Sobre la base de la solución de CL, que en última instancia era mucho más elegante de lo que pensaba, se me ocurrió un método ligeramente modificado.

Siguiendo los consejos de CL, instalé una base de datos sqlite3 y alimenté los archivos de texto en una secuencia de comandos de Python que los consumió y luego ejecuté un comando para insertarlos en la base de datos. Desde el principio, esto ~ funcionó ~ pero fue extremadamente (infasiblemente) lento.

Resolví esto con unas simples optimizaciones de base de datos que eran mucho más fáciles de implementar y francamente más sencillas de hacer solo desde el script Python central que se incluye a continuación, que se basa en el código de esqueleto de CL. El hecho de que el código original generara tantas operaciones de E / S estaba causando algo raro en mi sistema operativo (Win7) y causó BSOD y datos perdidos. Resolví esto haciendo la inserción de un archivo de contraseña completo en una transacción de SQL más un par de cambios de pragma. Al final, el código se ejecuta en aproximadamente 30,000 inserciones por segundo, lo cual no es el mejor, pero ciertamente es aceptable para mis propósitos.

Puede darse el caso de que esto siga fallando en la mayoría de los archivos, pero si ese es el caso, simplemente dividiré el archivo en porciones más pequeñas de 1 Gb y las consumiré individualmente.

import sys import apsw i = 0 con = apsw.Connection("passwords_test.db") cur = con.cursor() cur.execute("CREATE TABLE IF NOT EXISTS Passwords(password TEXT PRIMARY KEY) WITHOUT ROWID;") cur.execute("PRAGMA journal_mode = MEMORY;") cur.execute("PRAGMA synchronous = OFF;") cur.execute("BEGIN TRANSACTION") for line in sys.stdin: escaped = line.rstrip().replace("'", "''") cur.execute("INSERT OR IGNORE INTO Passwords VALUES(?);", (escaped,)) i += 1 if i % 100000 == 0: # Simple line counter to show how far through a file we are print i cur.execute("COMMIT") con.close(True) 

Este código se ejecuta desde la línea de comando:

 insert_passwords.py < passwordfile1.txt 

Y automatizado por:

 for %%f in (*.txt) do ( insert_passwords.py < %%f ) 

En general, el archivo DB en sí no está creciendo demasiado rápido, la tasa de inserción es suficiente, puedo romper / reanudar las operaciones en un abrir y cerrar de ojos, los valores duplicados se descartan con precisión y el factor limitante actual es la velocidad de búsqueda de La base de datos no la CPU o el espacio en disco.

Al almacenar las contraseñas en una base de datos SQL, la capacidad de detectar duplicados requiere un índice. Esto implica que las contraseñas se almacenan dos veces, en la tabla y en el índice.

Sin embargo, SQLite 3.8.2 o posterior admite las tablas WITHOUT ROWID (denominadas “índice agrupado” o “tablas organizadas por índice” en otras bases de datos), lo que evita el índice separado para la clave principal.

No hay una versión de Python que ya tenga incluido SQLite 3.8.2. Si no está utilizando APSW , aún puede usar Python para crear los comandos SQL:

  1. Instala el nuevo shell de línea de comandos sqlite3 ( página de descarga ).
  2. Crear una tabla de base de datos:

     $ sqlite3 passwords.db SQLite version 3.8.5 2014-06-02 21:00:34 Enter ".help" for usage hints. sqlite> CREATE TABLE MyTable(password TEXT PRIMARY KEY) WITHOUT ROWID; sqlite> .exit 
  3. Cree una secuencia de comandos de Python para crear las instrucciones INSERT:

     import sys print "BEGIN;" for line in sys.stdin: escaped = line.rstrip().replace("'", "''") print "INSERT OR IGNORE INTO MyTable VALUES('%s');" % escaped print "COMMIT;" 

    (La instrucción INSERT OR IGNORE no insertará una fila si un duplicado violaría la restricción única de la clave principal).

  4. Inserte las contraseñas canalizando los comandos en el shell de la base de datos:

     $ python insert_passwords.py < passwords.txt | sqlite3 passwords.db 

No hay necesidad de dividir los archivos de entrada; menos transacciones tienen menos gastos generales