Aconteceu hai uns días . Os mozos de JUG.ru Group convidaron a oradores de soños (Leslie Lamport! Cliff Click! Martin Kleppmann!) e dedicaron dous días aos sistemas distribuídos e á informática. Kontur foi un dos tres socios da conferencia. Falamos na caseta, falamos dos nosos almacenamentos distribuídos, xogamos ao bingo e resolvemos crebacabezas.
Este é un post cunha análise das tarefas no stand de Kontur do autor do seu texto. Quen estaba na Hidra - esta é a túa razón para lembrar a experiencia agradable, quen non foi - unha oportunidade de estirar o teu cerebro grande O-cualificación.
Incluso houbo participantes que desmontaron o rotafolio en diapositivas para anotar a súa decisión. Non estou de broma: entregaron esta pila de papeis para a verificación:
Foron tres tarefas en total:
- sobre a selección de réplicas por pesos para o equilibrio de carga
- sobre ordenar os resultados das consultas contra unha base de datos en memoria
- sobre transferencia de estado nun sistema distribuído cunha topoloxía en anel
Tarefa 1. ClusterClient
Foi necesario propoñer un algoritmo para a selección eficiente de K a partir de N réplicas ponderadas dun sistema distribuído:
O teu equipo ten a tarefa de desenvolver unha biblioteca cliente para un clúster distribuído masivamente de N nodos. A biblioteca faría un seguimento de varios metadatos asociados aos nodos (por exemplo, as súas latencias, as taxas de resposta 4xx/5xx, etc.) e asignaríalles pesos en coma flotante W1..WN. Para soportar a estratexia de execución simultánea, a biblioteca debería poder escoller K de N nodos aleatoriamente; a posibilidade de ser seleccionada debería ser proporcional ao peso dun nodo.
Propoñer un algoritmo para seleccionar nodos de forma eficiente. Estima a súa complexidade computacional usando a notación O grande.
Por que todo está en inglés?
Porque desta forma os participantes na conferencia pelexaron con eles e porque o inglés era a lingua oficial de Hydra. As tarefas tiñan este aspecto:
Colle papel e lapis, pensa, non te apresures a abrir spoilers de inmediato 🙂
Análise da solución (vídeo)
A partir das 5:53, só 4 minutos:
E aquí é como os mozos co rotafolio presentaron a súa solución:
Análise da solución (texto)
A seguinte solución atópase na superficie: sume os pesos de todas as réplicas, xera un número aleatorio de 0 á suma de todos os pesos, despois elixe unha i-réplica de tal xeito que a suma dos pesos das réplicas de 0 a (i-1)th é menor que un número aleatorio, e a suma dos pesos das réplicas de 0 a i-th - máis que el. Así, será posible seleccionar unha réplica e, para seleccionar a seguinte, cómpre repetir todo o procedemento sen ter en conta a réplica seleccionada. Con tal algoritmo, a complexidade de escoller unha réplica é O(N), a complexidade de escoller K réplicas é O(N K) ~ O(N2).
A complexidade cuadrática é mala, pero pódese mellorar. Para iso, imos construír para sumas de pesos. Obtense unha árbore de profundidade lg N, en cuxas follas haberá pesos de réplica, e nos nodos restantes - sumas parciais, ata a suma de todos os pesos na raíz da árbore. A continuación, xeramos un número aleatorio de 0 ata a suma de todos os pesos, atopamos a i-ésima réplica, elimínaa da árbore e repetimos o procedemento para atopar as réplicas restantes. Con este algoritmo, a complexidade de construír unha árbore é O(N), a complexidade de atopar a i-ésima réplica e eliminala da árbore é O(lg N), a complexidade de escoller K réplicas é O(N + K lg N) ~ O(N lg N) .
A complexidade logarítmica lineal é máis agradable que a complexidade cuadrática, especialmente para K grande.
É este algoritmo Bibliotecas ClusterClient do proxecto "". (Alí, a árbore está construída en O(N lg N), pero isto non afecta a complexidade final do algoritmo.)
Tarefa 2. Cebra
Foi necesario propoñer un algoritmo para a ordenación eficiente dos documentos na memoria mediante un campo arbitrario non indexado:
O teu equipo ten a tarefa de desenvolver unha base de datos de documentos fragmentados en memoria. Unha carga de traballo común sería seleccionar os N principais documentos ordenados por un campo numérico arbitrario (non indexado) dunha colección de tamaño M (normalmente N < 100 << M). Unha carga de traballo un pouco menos común sería seleccionar o N superior despois de saltar os documentos S principais (S ~ N).
Propón un algoritmo para executar este tipo de consultas de forma eficiente. Estima a súa complexidade computacional usando a notación O grande no caso medio e no peor dos casos.
Análise da solución (vídeo)
A partir das 34:50, só 6 minutos:
Análise da solución (texto)
Solución de superficie: ordena todos os documentos (por exemplo, con ), a continuación, tome documentos N+S. Neste caso, a complexidade da clasificación é de media O(M lg M), no peor de O(M2).
É obvio que clasificar todos os documentos M e despois tomar só unha pequena parte deles é ineficiente. Para non ordenar todos os documentos, é adecuado un algoritmo , que seleccionará N + S dos documentos desexados (pódense ordenar por calquera algoritmo). Neste caso, a complexidade diminuirá ata O(M) de media, mentres que o peor dos casos permanecerá igual.
Non obstante, pode facelo aínda máis eficientemente: use o algoritmo . Neste caso, os primeiros documentos N+S engádense ao montón mínimo ou máximo (dependendo da dirección de ordenación), e despois cada documento seguinte compárase coa raíz da árbore, que contén o documento mínimo ou máximo actual. e engádese á árbore se é necesario. . Neste caso, a complexidade no peor dos casos, cando tes que reconstruír constantemente a árbore, é O(M lg M), a complexidade de media é O(M), como ocorre coa selección rápida.
Non obstante, a transmisión do montón resulta ser máis eficiente debido ao feito de que na práctica a maioría dos documentos pódense descartar sen reconstruír o montón despois dunha soa comparación co seu elemento raíz. Esta clasificación implícase na base de datos de documentos en memoria de Zebra desenvolvida e utilizada en Kontur.
Tarefa 3. Permutas de estado
Foi necesario propoñer o algoritmo máis eficiente para os estados de desprazamento:
O teu equipo ten a tarefa de desenvolver un mecanismo de intercambio de estados elegante para un clúster distribuído de N nodos. O estado do i-ésimo nodo debería transferirse ao (i+1)-ésimo nodo, o estado do N-ésimo nodo debería transferirse ao primeiro nodo. A única operación soportada é o intercambio de estados cando dous nodos intercambian os seus estados atómicamente. Sábese que un intercambio de estado leva M milisegundos. Cada nodo é capaz de participar nun único intercambio de estados en calquera momento.
Canto tempo leva transferir os estados de todos os nodos dun clúster?
Análise da solución (texto)
Solución de superficie: intercambia os estados do primeiro e segundo elemento, despois do primeiro e terceiro, despois do primeiro e do cuarto, etc. Despois de cada intercambio, o estado dun elemento estará na posición desexada. Tes que facer permutacións O(N) e gastar O(N M) tempo.
O tempo lineal é longo, polo que podes intercambiar os estados dos elementos por parellas: o primeiro co segundo, o terceiro co cuarto, etc. Despois de cada intercambio de estado, cada segundo elemento estará na posición correcta. Tes que facer permutacións O(lg N) e gastar O(M lg N) tempo.
Non obstante, é posible facer o cambio aínda máis eficiente, non en forma lineal, senón en tempo constante. Para iso, no primeiro paso, cómpre intercambiar o estado do primeiro elemento co último, o segundo co penúltimo, etc. O estado do último elemento estará na posición correcta. E agora temos que intercambiar o estado do segundo elemento co último, o terceiro co penúltimo, etc. Despois desta rolda de intercambios, os estados de todos os elementos estarán na posición correcta. Haberá permutacións de O(2M) ~ O(1) en total.
Tal solución non sorprenderá en absoluto a un matemático que aínda recorda que unha rotación é unha composición de dúas simetrías axiais. Por certo, xeneralízase trivialmente para un desprazamento non por un, senón por K < N posicións. (Escribe nos comentarios como exactamente.)
Gustáronche os crebacabezas? Coñeces outras solucións? Comparte nos comentarios.
E aquí tes algúns enlaces útiles ao final:
- saber máis sobre en contorno
- ver rexistros internos sobre sistemas distribuídos
- ver a serie de videoconferencias»
- subscríbete ao noso
Fonte: www.habr.com