Hace unos días hubo una conferencia de Hydra . Los muchachos del grupo JUG.ru invitaron a los oradores de ensueño (Leslie Lampport! Cliff Click! Martin Kleppmann!) Y dedicaron dos días a sistemas distribuidos y computación. Contour fue uno de los tres socios de la conferencia. Hablamos en el stand, hablamos sobre nuestras instalaciones de almacenamiento distribuido, jugamos bingo, resolvimos problemas.
Esta es una publicación con análisis de tareas en el stand de Contour del autor de su texto. Quien estuvo en Hydra es su razón para recordar impresiones agradables, quién no, una oportunidad para estirar su cerebro con una gran notación O.
Incluso hubo participantes que separaron el rotafolio en diapositivas para registrar su decisión. No estoy bromeando: entregaron para revisar este paquete de papel:
Había tres tareas en total:
- sobre la elección de réplicas de pesos para el equilibrio de carga
- sobre cómo ordenar los resultados de una consulta a una base de datos en memoria
- en transferencia de estado en un sistema distribuido con una topología de anillo
Tarea 1. ClusterClient
Era necesario proponer un algoritmo para la selección efectiva de K de N réplicas ponderadas de un sistema distribuido:
Su equipo tiene la tarea de desarrollar una biblioteca de cliente para un grupo de N nodos distribuido masivamente. La biblioteca mantendría un registro de varios metadatos asociados con los nodos (por ejemplo, sus latencias, tasas de respuesta 4xx / 5xx, etc.) y les asignaría pesos de punto flotante W 1 ..W N a ellos. Para admitir la estrategia de ejecución concurrente, la biblioteca debería poder elegir K de N nodos al azar; la posibilidad de ser seleccionada debería ser proporcional al peso de un nodo.
Proponga un algoritmo para seleccionar nodos de manera eficiente. Estime su complejidad computacional usando la notación O grande.
¿Por qué todo está 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í:
Tome papel y lápiz, piense, no se apresure a abrir de inmediato los spoilers :)
Debriefing (video)A partir de las 5:53, solo 4 minutos:
Y así es como esos tipos con un rotafolio presentaron su decisión:
Análisis de la decisión (texto)En la superficie, existe una solución: sumar los pesos de todas las réplicas, generar un número aleatorio de 0 a la suma de todos los pesos, luego elegir una réplica i de manera que la suma de los pesos de réplica de 0 a (i-1) sea menor que el número aleatorio y la suma de los pesos de réplica del 0 al i-ésimo, más que eso. Resultará elegir 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 (N 2 ).
La complejidad cuadrática es mala, pero se puede mejorar. Para hacer esto, construya un árbol de segmentos para las sumas de pesos. Esto producirá un árbol con una profundidad de registro N, en las hojas de las cuales 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 buscar las réplicas restantes. Con tal algoritmo, la complejidad de construir un árbol es O (N), la complejidad de encontrar la réplica i-ésima y eliminarla del árbol es O (log N), la complejidad de elegir K réplicas es O (N + K log N) ~ O (N log N) .
La complejidad logarítmica lineal es más agradable que la complejidad cuadrática, especialmente para K.
Este algoritmo se implementa en el código de la biblioteca ClusterClient del proyecto Vostok .
Tarea 2. Cebra
Era necesario proponer un algoritmo para la clasificación eficiente de documentos en memoria por un campo arbitrario no indexado:
Su equipo tiene la tarea de desarrollar una base de datos de documentos fragmentados en memoria. Una carga de trabajo común sería seleccionar los documentos N 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 superior después de omitir los documentos S superiores (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 los peores escenarios.
Debriefing (video)Comienza a las 34:50, solo 6 minutos:
Análisis de la decisión (texto)La solución está en la superficie: clasifique todos los documentos (por ejemplo, usando la clasificación rápida ), luego tome los documentos N + S. En este caso, la complejidad de la clasificación en promedio es O (M lg M), en el peor de los casos, O (M 2 ).
Obviamente, ordenar todos los documentos M para luego tomar solo una pequeña parte de ellos es ineficiente. Para no ordenar todos los documentos, el algoritmo de selección rápida es adecuado , que selecciona N + S de los documentos necesarios (se pueden ordenar por cualquier algoritmo). En este caso, la complejidad disminuye en promedio a O (M), y el peor de los casos sigue siendo el mismo.
Sin embargo, puede hacerlo aún más eficientemente: use el algoritmo de transmisión de almacenamiento dinámico binario . En este caso, los primeros documentos N + S se agregan al montón mínimo o máximo (según la dirección de clasificación), y luego cada documento posterior se compara con la raíz del árbol, que contiene el documento mínimo o máximo en ese momento, y se agrega al árbol si es necesario. . En este caso, la complejidad en el peor de los casos es cuando tiene que reconstruir constantemente el árbol: O (M lg (N + S)), la complejidad promedio es O (M), como ocurre con la selección rápida.
Sin embargo, la transmisión del montón es más efectiva debido al hecho de que, en la práctica, la mayoría de los documentos pueden descartarse sin reconstruir el montón, después de una comparación única con su elemento raíz. Dicha clasificación se implementa en la base de datos en memoria de documentos Zebra desarrollada y utilizada en el Circuito.
Tarea 3. Cambios de estado
Era necesario proponer el algoritmo más eficiente para el cambio de estado:
Su equipo tiene la tarea de desarrollar un mecanismo de intercambio de estado elegante para un grupo distribuido de N nodos. El estado del nodo i-ésimo debe transferirse al nodo (i + 1), el estado del nodo n-ésimo debe transferirse al primer nodo. La única operación admitida es el intercambio de estado cuando dos nodos intercambian sus estados atómicamente. Se sabe que un intercambio de estado toma M milisegundos. Cada nodo puede participar en un solo intercambio de estado en cualquier momento dado.
¿Cuánto tiempo lleva transferir los estados de todos los nodos en un clúster?
Análisis de la decisión (texto)Una solución en la superficie: intercambie 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 de O (N) y pasar tiempo de O (N · M).
El tiempo lineal es mucho tiempo, por lo que puede 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 intercambio, el estado de cada segundo elemento estará en la posición deseada. Tendremos que hacer permutaciones O (log N) y pasar tiempo O (M log N N).
Sin embargo, puede hacer que el cambio sea aún más efectivo, no en 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 deseada. Y ahora necesita 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. En total, se realizarán permutaciones O (2M) ~ O (1).
Tal solución no sorprenderá a un matemático que todavía recuerda que la rotación es una composición de dos simetrías axiales. Por cierto, es trivialmente generalizado cambiar no por uno, sino por K <N posiciones. (Escriba en los comentarios exactamente cómo.)
¿Te gustan los rompecabezas? ¿Conoces otras soluciones? Comparte en los comentarios.
Y aquí hay algunos enlaces útiles al final: