Pregunta de la entrevista: Sobre el procesamiento distribuido de grandes cantidades de datos

Título: El sistema de producción genera un archivo de registro F todos los días, con un volumen de datos de 5000 W de líneas. El archivo F almacena dos columnas de datos, una columna es el canal de origen y la otra columna es la ID de usuario en el canal de origen. El archivo F se utiliza para registrar todos los usuarios que visitaron todos los canales ese día, con un registro por cada visita.

¿Cómo contar rápidamente los nuevos usuarios de cada canal?

Análisis de problemas: en primer lugar, esta entrevista trata sobre puestos de procesamiento y análisis de datos distribuidos, por lo que las preguntas de la entrevista relacionadas pueden tender a resolverse utilizando ideas distribuidas. Pero mi respuesta fue demasiado lenta en ese momento y realmente no pensé en el procesamiento distribuido.

Opción 1:

Una de las formas más intuitivas de abordar este problema es hacer coincidir directamente los usuarios de acceso históricos con los registros de acceso de 5000 W agregados ese día. Si hay un registro de acceso histórico, se ignorará; si no hay un registro de acceso, se guardará como un registro nuevo. Obviamente, si hay 200 millones de registros históricos de usuarios, es necesario compararlos con 200 millones de datos 50 millones de veces. Se puede imaginar la cantidad de comparaciones.

Debido a que he estado realizando procesamiento de datos basado en bases de datos, es fácil pensar en guardar datos históricos en una tabla en la base de datos, indexar los dos campos de canal de origen e ID de usuario y luego recorrer el registro. Archivo F (5000W de segunda categoría). Cada fila del archivo de registro f se compara con los registros de acceso históricos de la base de datos. Dado que la tabla de datos históricos está indexada, la velocidad de una única consulta también es muy rápida. Pero requiere una consulta de base de datos de 5000 W, lo que obviamente no es eficiente.

Opción 2:

Dado que varias consultas únicas no pueden cumplir con los requisitos, primero podemos usar una tecnología de importación de datos para importar los nuevos datos del día a otra tabla de la base de datos, y Realice una correlación externa izquierda en datos históricos. Si la asociación tiene éxito, significa que el usuario ya existe; si la asociación falla, significa que el usuario no existe.

Esta solución no habla de qué tan eficiente es la asociación entre una tabla grande con 50 millones de registros y una tabla grande con 200 millones de registros, y cuántos recursos utiliza el búfer de la base de datos. Se necesita mucho tiempo para importar una tabla de base de datos con 50 millones de registros de acceso.

Opción 3:

Evidentemente, la respuesta a la segunda opción de la entrevista no cumplió con las expectativas del entrevistador, y lamentablemente superó el rechazo inicial. Me fui tan pronto como dejé una empresa con un gran potencial. Era muy optimista conmigo mismo y planeaba tomar un puesto como mi dirección de desarrollo futuro.

Después de leer la introducción de la distribución en los últimos días, de repente se me ocurrió esta pregunta. De repente me di cuenta de que en realidad se debía a que mi análisis de los puntos a examinar no era lo suficientemente exhaustivo. En ese momento, pensé que era solo una cuestión de eficiencia en el procesamiento de datos. De hecho, era una idea de dividir problemas complejos en problemas simples. Conociendo este nivel, inmediatamente me viene a la mente un nuevo método. Los detalles son los siguientes:

Si hay N (N>=2) bloques de memoria y hay una función f(canal de origen, ID de usuario). Para un grupo determinado (canal de origen, ID de usuario), siempre se puede asignar a un bloque de memoria fijo. Luego, puede usar esta función para distribuir los registros de acceso a la línea de 5000 W de la manera más uniforme posible en n bloques de memoria, y usar esta función para distribuir los registros de acceso históricos a estos bloques de memoria. Debido a que el mismo conjunto de registros definitivamente se asignará al mismo bloque de almacenamiento, al comparar, solo necesitamos comparar los nuevos registros en cada bloque de almacenamiento con los usuarios de acceso históricos y luego comparar los nuevos registros en n bloques de almacenamiento. El resultado final puede obtenerse resumiendo los resultados.

Supongamos que los datos históricos de acceso del usuario se han distribuido a n archivos históricos H1, H2,..., HN a través de la función F (canal de origen, ID de usuario). Los pasos de procesamiento específicos son los siguientes:

1. Utilice la función F (canal de origen, ID de usuario) para distribuir el contenido en F a los archivos F1, F2,..., FN. (Active el paralelismo M (M > = 2), y cuanto mayor sea N-M, menor será la probabilidad de que los datos se escriban en el mismo archivo al mismo tiempo)

2. Copie los archivos F1, F2. ,...,Registros de acceso FN. (N archivos se pueden procesar por separado en paralelo).

3. Archivo fn (1 =

4. Combina los resultados obtenidos en el tercer paso, R1, R2,..., RN, para obtener los nuevos usuarios del día. .

(Paralelo)

5. Para que los datos de los archivos de datos históricos H1, H2,..., HN sean los más completos, escriba los resultados R1, R2,..., RN en el correspondientes archivos históricos respectivamente. (Paralelo)

Esta solución tiene principalmente las siguientes ventajas:

1. La distribución, el procesamiento y la fusión de datos se pueden procesar en paralelo, lo que mejora significativamente la eficiencia del procesamiento.

2. Dado que los datos recién agregados en cada bloque de almacenamiento solo deben compararse con los datos históricos en su bloque de almacenamiento correspondiente, el número de comparaciones se reduce considerablemente. (Para cada registro del día, solo necesita compararlo con aproximadamente 1/n de datos históricos).

3. Básicamente, no hay necesidad de considerar la preservación y adquisición de datos históricos totales.

Desventajas de esta solución:

1. La solución de procesamiento obviamente se ha vuelto mucho más complicada y requiere no solo la distribución y el procesamiento de datos, sino también un método de recopilación rápido y paralelo.

2. El procesamiento paralelo puede requerir varios servidores.

Dificultades de esta solución:

1. Estable (el mismo grupo de canales de origen e ID de usuario se asignarán al mismo bloque de almacenamiento), rápido (según un canal de origen y datos de identificación de usuario, puede calcular rápidamente qué bloque de almacenamiento se asignará), uniforme (los datos nuevos del día y los datos históricos se pueden distribuir en n bloques de almacenamiento de la manera más uniforme posible, la situación más ideal es que los datos asignados a cada bloque de almacenamiento es el total 1/n de los datos).

2. ¿Cómo distribuir, procesar y resumir datos en paralelo?