algorithm - sistemas - programacion paralela

Top diez algoritmos paralelos para datos distribuidos

Question

Esta es una pregunta de entrevista. Supongamos que hay algunas computadoras y cada computadora mantiene un archivo de registro muy grande de las URL visitadas. Encuentra las diez URL más visitadas.

Por ejemplo: supongamos que solo hay 3 computadoras y necesitamos las dos URL más visitadas.

Computer A: url1, url2, url1, url3 Computer B: url4, url2, url1, url1 Computer C: url3, url4, url1, url3 url1 appears 5 times in all logs url2 2 url3 3 url4 2 So the answer is url1, url3

Los archivos de registro son demasiado grandes para caber en la RAM y copiarlos por red. Según tengo entendido, es importante también hacer el cómputo en paralelo y usar todas las computadoras dadas.

¿Cómo lo resolverías?

Answer 1

Asumiendo que las condiciones a continuación son ciertas:

• Necesitas las mejores direcciones URL de m hosts.
• No puedes almacenar los archivos en RAM
• Hay un nodo maestro

Tomaría el siguiente enfoque:

Cada nodo lee una parte del archivo (es decir, las urls MAX, donde MAX puede ser, digamos, 1000 urls) y mantiene una matriz arr [MAX] = {url, hits}.

Cuando un nodo ha leído MAX urls fuera del archivo, envía la lista al nodo maestro y reinicia las lecturas hasta que se alcanza MAX MAX de nuevo.

Cuando un nodo alcanza el EOF, envía la lista restante de urls y un indicador EOF al nodo maestro.

Cuando el nodo maestro recibe una lista de direcciones URL, la compara con su última lista de direcciones URL y genera una nueva y actualizada.

Cuando el nodo maestro recibe la marca EOF de cada nodo y termina de leer su propio archivo, los n nodos principales de la última versión de su lista son los que estamos buscando.

O

Un enfoque diferente que liberaría al maestro de hacer todo el trabajo podría ser:

Cada nodo lee su archivo y almacena una matriz igual a la anterior, leyendo hasta EOF.

Cuando sea EOF, el nodo enviará la primera url de la lista y el número de visitas al maestro.

Cuando el maestro ha recopilado la primera url y el número de visitas para cada nodo, genera una lista. Si el nodo maestro tiene menos de n urls, pedirá a los nodos que envíen el segundo y así sucesivamente. Hasta que el maestro tenga las n urls ordenadas.

Answer 2

Dada la escala de los archivos de registro y la naturaleza genérica de la pregunta, este es un problema bastante difícil de resolver. No creo que haya un mejor algoritmo para todas las situaciones. Depende de la naturaleza del contenido de los archivos de registro. Por ejemplo, tome el caso de la esquina de que todas las URL son únicas en todos los archivos de registro. En ese caso, básicamente cualquier solución tomará un largo tiempo para llegar a esa conclusión (si es que llega tan lejos ...), y ni siquiera hay una respuesta a su pregunta porque no hay un top ten.

No tengo un algoritmo hermético que pueda presentar, pero exploraría una solución que usa histogramas de valores hash de las URL en lugar de las URL mismas. Estos histogramas se pueden calcular por medio de lecturas de archivos de una sola pasada, por lo que pueden tratar archivos de registro de tamaño arbitrario. En pseudo-código, me gustaría algo como esto:

• Use una función hash con un espacio objetivo limitado (por ejemplo, 10,000, tenga en cuenta que se esperan valores hash en colisión) para calcular el valor hash de cada elemento en el archivo de registro y cuente cuántas veces ocurre cada uno de los valores de has. Comunique el histograma resultante a un servidor (aunque es probable que también sea posible evitar un servidor central mediante la multidifusión del resultado en todos los demás nodos, pero seguiré con el enfoque más obvio del servidor aquí)
• El servidor debe combinar los histogramas y comunicar el resultado. Dependiendo de la distribución de las URL, es posible que ya haya una cantidad de picos claramente visibles que contengan las URL más visitadas.
• Cada uno de los nodos debe centrarse en los picos del histograma. Debería ir a través de su archivo de registro nuevamente, usar una función hash adicional (de nuevo con un espacio objetivo limitado) para calcular un nuevo histograma de hash para aquellas URL que tienen su primer valor hash en uno de los picos (el número de picos a enfocar). on sería un parámetro a ser ajustado en el algoritmo, dependiendo de la distribución de las URLs, y calcular un segundo histograma con los nuevos valores hash. El resultado debe ser comunicado al servidor.
• El servidor debe volver a combinar los resultados y analizar el nuevo histograma frente al histograma original. Dependiendo de los picos claramente visibles, podría ser capaz de sacar conclusiones acerca de los dos valores hash de las diez URL más importantes. O podría tener que instruir a las máquinas para que calculen más valores de hash con la segunda función de hash, y probablemente después de eso pasen por un tercer paso de cálculos de hash con otra función de hash. Esto tiene que continuar hasta que se pueda extraer una conclusión del grupo colectivo de histogramas sobre cuáles son los valores hash de las URL de pico, y luego los nodos pueden identificar las diferentes URL a partir de eso.

Tenga en cuenta que este mecanismo requerirá ajuste y optimización con respecto a varios aspectos del algoritmo y funciones hash. También necesitará la orquestación del servidor para determinar qué cálculos deben realizarse en cualquier momento. Es probable que también sea necesario establecer algunos límites para concluir cuando no se puede extraer una conclusión, es decir, cuando el "espectro" de valores de hash de URL es demasiado plano para que valga la pena el esfuerzo de continuar los cálculos.

Sin embargo, este enfoque debería funcionar bien si hay una distribución clara en las URL. Sospecho que, prácticamente hablando, la pregunta solo tiene sentido en ese caso de todos modos.

Answer 3

Este es un problema bastante estándar para el cual existe una solución bien conocida. Simplemente ordena los archivos de registro en cada computadora por URL y luego combínalos a través de una cola de prioridad de tamaño k (la cantidad de elementos que deseas) en la computadora "maestra". Esta técnica ha existido desde la década de 1960, y todavía está en uso hoy en día (aunque ligeramente modificada) en forma de MapReduce .

En cada computadora, extraiga la URL y el recuento del archivo de registro y ordene por URL. Debido a que los archivos de registro son más grandes de lo que caben en la memoria, debe realizar una combinación en el disco. Eso implica leer una parte del archivo de registro, ordenar por URL, escribir la parte en el disco. Leer el siguiente fragmento, ordenar, escribir en el disco, etc. En algún momento, tiene M trozos de archivos de registro, cada uno clasificado. A continuación, puede hacer una fusión M-way. Pero en lugar de escribir elementos en el disco, los presenta, en orden ordenado (ordenados por URL, es decir), al "maestro".

Cada máquina ordena su propio registro.

La computadora "maestra" combina los datos de las computadoras separadas y realiza la selección de K superior. Esto es en realidad dos problemas, pero se pueden combinar en uno.

El maestro crea dos colas de prioridad: una para la combinación y otra para la selección de K superior. La primera es de tamaño N, donde N es el número de computadoras de las que se están fusionando los datos. El segundo es de tamaño K: la cantidad de elementos que desea seleccionar. Uso un montón de minutos para esto, ya que es fácil y razonablemente rápido.

Para configurar la cola de combinación, inicialice la cola y obtenga el primer elemento de cada una de las computadoras "de trabajo". En el pseudo-código a continuación, "obtener el elemento más bajo de la cola de combinación" significa obtener el elemento raíz de la cola de combinación y luego obtener el siguiente elemento de cualquier computadora en funcionamiento que presente ese elemento. Entonces, si la cola contiene [1, 2, 3] , y los elementos provienen de las computadoras B, C, A (en ese orden), tomar el elemento más bajo significaría obtener el siguiente elemento de la computadora B y agregarlo a la prioridad cola.

El maestro entonces hace lo siguiente:

working = get lowest item from merge queue
while (items left to merge)
{
    temp = get lowest item from merge queue
    while (temp.url == working.url)
    {
        working.count += temp.count
        temp = get lowest item from merge queue
    }
    // Now have merged counts for one url.
    if (topK.Count < desired_count)
    {
        // topK queue doesn''t have enough items yet.
        // so add this one.
        topK.Add(working);
    }
    else if (topK.Peek().count < working.count)
    {
        // the count for this url is larger
        // than the smallest item on the heap
        // replace smallest on the heap with this one
        topK.RemoveRoot()
        topK.Add(working)
    }
    working = temp;
}
// Here you need to check the last item:
if (topK.Peek().count < working.count)
{
    // the count for this url is larger
    // than the smallest item on the heap
    // replace smallest on the heap with this one
    topK.RemoveRoot()
    topK.Add(working)
}

En este punto, la cola topK tiene los elementos K con los conteos más altos.

Por lo tanto, cada computadora debe realizar una ordenación de combinación, que es O (n log n), donde n es la cantidad de elementos en el registro de esa computadora. La combinación en el maestro es O (n), donde n es la suma de todos los elementos de las computadoras individuales. La selección de los k elementos principales es O (n log k), donde n es el número de URL únicas .

Las clasificaciones se realizan en paralelo, por supuesto, y cada computadora prepara su propia lista ordenada. Pero la parte del tipo "fusionar" se realiza al mismo tiempo que la computadora maestra se está fusionando, por lo que hay cierta coordinación y todas las máquinas están involucradas en esa etapa.

Answer 4

La siguiente descripción es la idea para la solución. No es un pseudocódigo.
Considera que tienes una colección de sistemas.
1. para cada A: Colecciones (sistemas)
1.1) Ejecute un daemonA en cada computadora que busque en el archivo de registro para los cambios.
1.2) Cuando se note un cambio, Wake AnalyzerThreadA
1.3) Si AnalyzerThreadA encuentra una URL usando alguna expresión regular, entonces actualice localHashMapA con count ++.
(clave = URL, valor = conteo).
2) Empuje las entradas de topTen de localHashMapA a ComputerA donde se ejecutará el daemon AnalyzeAll.

El paso anterior será el último paso en cada sistema, que empujará las entradas de topTen a un sistema maestro, por ejemplo: computadoraA.

3) AnalyzeAll se ejecuta en computerA resolverá los duplicados y actualizará el recuento en masterHashMap de las URL.

4) Imprima el topTen de masterHashMap.

Answer 5

Preprocesamiento: cada sistema informático procesa el archivo de registro completo y prepara la lista de URL únicas con un recuento en su contra.

Obteniendo las mejores URLs:

1. Calcule los recuentos de URL en cada sistema informático
2. Proceso de cotejo en un sistema central (Virtual)
   • Envíe las URL con recuento a una unidad central de procesamiento una por una en orden DESC (es decir, desde la parte superior)
   • En el sistema central recopila los detalles de la URL entrante
   • Repita hasta que la suma de todas las cuentas de las URL entrantes sea menor que la cuenta de la Décima URL en la lista maestra. Un paso vital para estar absolutamente seguro.

PS: Tendrás las diez URL principales en todos los sistemas, no necesariamente en ese orden. Para obtener el orden real puede revertir la colación . Para una URL determinada en el top ten, obtenga el recuento individual de las computadoras dist y forme la orden final.