Sucedió hace unos días . Los muchachos de JUG.ru Group invitaron a oradores de ensueño (¡Leslie Lamport! ¡Cliff Click! ¡Martin Kleppmann!) y dedicaron dos días a los sistemas distribuidos y la computación. Kontur fue uno de los tres socios de la conferencia. Hablamos en el stand, hablamos sobre nuestros almacenamientos distribuidos, jugamos bingo y resolvimos acertijos.
Este es un post con un análisis de las tareas en el stand de Kontur del autor de su texto. Quién estaba en la Hidra: esta es su razón para recordar la experiencia agradable, quién no lo estaba: una oportunidad para estirar su cerebro gran O-notación.
Incluso hubo participantes que desarmaron el rotafolio en diapositivas para anotar su decisión. No estoy bromeando, entregaron esta pila de papel para su verificación:
Había tres tareas en total:
- sobre la selección de réplicas por pesos para el equilibrio de carga
- sobre la clasificación de los resultados de la consulta en una base de datos en memoria
- sobre la transferencia de estado en un sistema distribuido con topología en anillo
Tarea 1. ClusterClient
Era necesario proponer un algoritmo para la selección eficiente de K de N réplicas ponderadas de un sistema distribuido:
Su equipo tiene la tarea de desarrollar una biblioteca de cliente para un clúster distribuido masivamente de N nodos. La biblioteca realizaría un seguimiento de varios metadatos asociados con los nodos (p. ej., sus latencias, tasas de respuesta 4xx/5xx, etc.) y les asignaría pesos de punto flotante W1..WN. Para admitir la estrategia de ejecución concurrente, la biblioteca debe poder elegir K de N nodos al azar; la posibilidad de ser seleccionado debe ser proporcional al peso de un nodo.
Proponer un algoritmo para seleccionar nodos de manera eficiente. Estime su complejidad computacional utilizando la notación O grande.
¿Por qué está todo en inglés?
Porque de esta forma los participantes de la conferencia lucharon con ellos y porque el inglés era el idioma oficial de Hydra. Las tareas se veían así:
Toma papel y lápiz, piensa, no te apresures a abrir spoilers de inmediato 🙂
Análisis de la solución (video)
A partir de las 5:53, solo 4 minutos:
Y así es como los muchachos con el rotafolio presentaron su solución:
Análisis de la solución (texto)
La siguiente solución se encuentra en la superficie: sume los pesos de todas las réplicas, genere un número aleatorio de 0 a la suma de todos los pesos, luego elija una i-réplica tal que la suma de los pesos de réplica de 0 a (i-1)th es menor que un número aleatorio, y la suma de los pesos de réplica de 0 a i-ésimo - más que eso. Por lo tanto, será posible seleccionar una réplica y, para seleccionar la siguiente, debe repetir todo el procedimiento sin considerar la réplica seleccionada. Con tal algoritmo, la complejidad de elegir una réplica es O(N), la complejidad de elegir K réplicas es O(N K) ~ O(N2).
La complejidad cuadrática es mala, pero se puede mejorar. Para ello, construiremos para sumas de pesos. Se obtendrá un árbol de profundidad lg N, en cuyas hojas habrá pesos de réplica, y en los nodos restantes, sumas parciales, hasta la suma de todos los pesos en la raíz del árbol. Luego, generamos un número aleatorio de 0 a la suma de todos los pesos, encontramos la i-ésima réplica, la eliminamos del árbol y repetimos el procedimiento para encontrar las réplicas restantes. Con este algoritmo, la complejidad de construir un árbol es O(N), la complejidad de encontrar la i-ésima réplica y eliminarla del árbol es O(lg N), la complejidad de elegir K réplicas es O(N + K largo N) ~ O(N largo N) .
La complejidad logarítmica lineal es mejor que la complejidad cuadrática, especialmente para K grande.
es este algoritmo Bibliotecas ClusterClient del proyecto "". (Allí, el árbol está construido en O(N lg N), pero esto no afecta la complejidad final del algoritmo).
Tarea 2. Cebra
Era necesario proponer un algoritmo para ordenar eficientemente los documentos en memoria por un campo arbitrario no indexado:
Su equipo tiene la tarea de desarrollar una base de datos de documentos en memoria fragmentada. Una carga de trabajo común sería seleccionar los N documentos principales ordenados por un campo numérico arbitrario (no indexado) de una colección de tamaño M (generalmente N < 100 << M). Una carga de trabajo un poco menos común sería seleccionar N principales después de omitir los documentos S principales (S ~ N).
Proponga un algoritmo para ejecutar tales consultas de manera eficiente. Estime su complejidad computacional utilizando la notación O grande en el caso promedio y en el peor de los casos.
Análisis de la solución (video)
A partir de las 34:50, solo 6 minutos:
Análisis de la solución (texto)
Solución superficial: ordenar todos los documentos (por ejemplo con ), luego tome los documentos N+S. En este caso, la complejidad de la clasificación es en promedio O(M lg M), en el peor de los casos O(M2).
Es obvio que clasificar todos los documentos M y luego tomar solo una pequeña parte de ellos es ineficiente. Para no ordenar todos los documentos, un algoritmo es adecuado , que seleccionará N + S de los documentos deseados (pueden ser ordenados por cualquier algoritmo). En este caso, la complejidad disminuirá a O(M) en promedio, mientras que el peor de los casos permanecerá igual.
Sin embargo, puede hacerlo aún más eficientemente: use el algoritmo . En este caso, los primeros documentos N+S se agregan al montón mínimo o máximo (dependiendo de la dirección de ordenación), y luego cada documento siguiente se compara con la raíz del árbol, que contiene el documento mínimo o máximo actual, y se agrega al árbol si es necesario. . En este caso, la complejidad en el peor de los casos, cuando tienes que reconstruir constantemente el árbol, es O(M lg M), la complejidad en promedio es O(M), como con selección rápida.
Sin embargo, la transmisión del montón resulta ser más eficiente debido al hecho de que, en la práctica, la mayoría de los documentos se pueden descartar sin reconstruir el montón después de una sola comparación con su elemento raíz. Dicha clasificación se implementa en la base de datos de documentos en memoria de Zebra desarrollada y utilizada en Kontur.
Tarea 3. Intercambios de estado
Era necesario proponer el algoritmo más eficiente para cambiar de estado:
Su equipo tiene la tarea de desarrollar un elegante mecanismo de intercambio de estado para un grupo distribuido de N nodos. El estado del i-ésimo nodo debe transferirse al (i+1)-ésimo nodo, el estado del N-ésimo nodo debe transferirse al primer nodo. La única operación admitida es el intercambio de estado cuando dos nodos intercambian sus estados de forma atómica. Se sabe que un cambio de estado tarda M milisegundos. Cada nodo puede participar en un solo intercambio de estado en cualquier momento.
¿Cuánto tiempo lleva transferir los estados de todos los nodos en un clúster?
Análisis de la solución (texto)
Solución de superficie: intercambiar los estados del primer y segundo elemento, luego el primero y el tercero, luego el primero y el cuarto, y así sucesivamente. Después de cada intercambio, el estado de un elemento estará en la posición deseada. Tienes que hacer permutaciones O(N) y gastar tiempo O(N M).
El tiempo lineal es largo, por lo que puedes intercambiar los estados de los elementos en pares: el primero con el segundo, el tercero con el cuarto, y así sucesivamente. Después de cada cambio de estado, cada segundo elemento estará en la posición correcta. Tienes que hacer permutaciones O(lg N) y gastar tiempo O(M lg N).
Sin embargo, es posible hacer que el cambio sea aún más eficiente, no en forma lineal, sino en tiempo constante. Para hacer esto, en el primer paso, debe intercambiar el estado del primer elemento con el último, el segundo con el penúltimo, y así sucesivamente. El estado del último elemento estará en la posición correcta. Y ahora necesitamos intercambiar el estado del segundo elemento con el último, el tercero con el penúltimo, y así sucesivamente. Después de esta ronda de intercambios, los estados de todos los elementos estarán en la posición correcta. Habrá permutaciones O(2M) ~ O(1) en total.
Tal solución no sorprenderá en absoluto a un matemático que aún recuerda que una rotación es una composición de dos simetrías axiales. Por cierto, se generaliza trivialmente para un cambio no de uno, sino de K < N posiciones. (Escriba en los comentarios cómo exactamente).
¿Te gustaron los rompecabezas? ¿Conoces otras soluciones? Comparte en los comentarios.
Y aquí hay algunos enlaces útiles al final:
- aprender más acerca de en contorno
- ver registros de interna sobre sistemas distribuidos
- ver la serie de video conferencias»
- suscríbete a nuestro
Fuente: habr.com