Aconteceu há alguns dias . Os caras do JUG.ru Group convidaram os palestrantes dos sonhos (Leslie Lamport! Cliff Click! Martin Kleppmann!) E dedicaram dois dias a sistemas distribuídos e computação. Kontur foi um dos três parceiros da conferência. Conversamos no estande, falamos sobre nossos armazenamentos distribuídos, jogamos bingo e resolvemos quebra-cabeças.
Este é um post com uma análise das tarefas no estande da Kontur do autor de seu texto. Quem estava na Hydra - este é o seu motivo para lembrar a experiência agradável, quem não estava - uma chance de esticar o cérebro grande O-notação.
Houve até participantes que desmontaram o flipchart em slides para anotar sua decisão. Não estou brincando - eles entregaram esta pilha de papel para verificação:
No total foram três tarefas:
- sobre como selecionar réplicas por pesos para balanceamento de carga
- sobre a classificação dos resultados da consulta em um banco de dados na memória
- sobre transferência de estado em um sistema distribuído com topologia em anel
Tarefa 1. ClusterClient
Foi necessário propor um algoritmo para a seleção eficiente de K a partir de N réplicas ponderadas de um sistema distribuído:
Sua equipe tem a tarefa de desenvolver uma biblioteca cliente para um cluster massivamente distribuído de N nós. A biblioteca acompanharia vários metadados associados aos nós (por exemplo, suas latências, taxas de resposta 4xx/5xx, etc.) e atribuiria pesos de ponto flutuante W1..WN a eles. Para suportar a estratégia de execução concorrente, a biblioteca deve ser capaz de escolher K de N nós aleatoriamente - a chance de ser selecionada deve ser proporcional ao peso de um nó.
Proponha um algoritmo para selecionar nós de forma eficiente. Estime sua complexidade computacional usando a notação O grande.
Por que está tudo em inglês?
Porque desta forma os participantes da conferência lutaram com eles e porque o inglês era a língua oficial da Hydra. As tarefas ficaram assim:
Pegue papel e lápis, pense, não se apresse em abrir spoilers imediatamente 🙂
Análise da solução (vídeo)
Começando às 5:53, apenas 4 minutos:
E aqui está como os caras com o flipchart apresentaram sua solução:
Análise da solução (texto)
A solução a seguir está na superfície: some os pesos de todas as réplicas, gere um número aleatório de 0 à soma de todos os pesos e escolha uma réplica i de modo que a soma dos pesos da réplica de 0 a (i-1)-ésimo é menor que um número aleatório e a soma dos pesos das réplicas de 0 a i-ésimo - mais do que isso. Assim será possível selecionar uma réplica, e para selecionar a próxima, será necessário repetir todo o procedimento sem considerar a réplica selecionada. Com tal algoritmo, a complexidade de escolher uma réplica é O(N), a complexidade de escolher K réplicas é O(N K) ~ O(N2).
A complexidade quadrática é ruim, mas pode ser melhorada. Para isso, vamos construir para somas de pesos. Será obtida uma árvore de profundidade lg N, em cujas folhas haverá réplicas de pesos, e nos demais nós - somas parciais, até a soma de todos os pesos na raiz da árvore. Em seguida, geramos um número aleatório de 0 até a soma de todos os pesos, encontramos a i-ésima réplica, removemos da árvore e repetimos o procedimento para encontrar as réplicas restantes. Com este algoritmo, a complexidade de construir uma árvore é O(N), a complexidade de encontrar a i-ésima réplica e removê-la da árvore é O(lg N), a complexidade de escolher K réplicas é O(N + K lg N) ~ O(N lg N) .
A complexidade linear-log é melhor do que a complexidade quadrática, especialmente para K grande.
É este algoritmo Bibliotecas ClusterClient do projeto "". (Aí, a árvore é construída em O(N lg N), mas isso não afeta a complexidade final do algoritmo.)
Tarefa 2. Zebra
Foi necessário propor um algoritmo para classificação eficiente de documentos na memória por um campo arbitrário não indexado:
Sua equipe tem a tarefa de desenvolver um banco de dados fragmentado de documentos na memória. Uma carga de trabalho comum seria selecionar os principais N documentos classificados por um campo numérico arbitrário (não indexado) de uma coleção de tamanho M (geralmente N < 100 << M). Uma carga de trabalho um pouco menos comum seria selecionar os principais N após pular os principais S documentos (S ~ N).
Proponha um algoritmo para executar tais consultas de forma eficiente. Estime sua complexidade computacional usando a notação O grande no caso médio e nos cenários de pior caso.
Análise da solução (vídeo)
A partir das 34:50, apenas 6 minutos:
Análise da solução (texto)
Solução de superfície: classifique todos os documentos (por exemplo com ), então pegue os documentos N+S. Nesse caso, a complexidade da ordenação é em média O(M lg M), na pior das hipóteses O(M2).
É óbvio que classificar todos os documentos M e depois pegar apenas uma pequena parte deles é ineficiente. Para não classificar todos os documentos, um algoritmo é adequado , que selecionará N + S dos documentos desejados (eles podem ser classificados por qualquer algoritmo). Nesse caso, a complexidade diminuirá para O(M) em média, enquanto o pior caso permanecerá o mesmo.
No entanto, você pode fazer isso de maneira ainda mais eficiente - use o algoritmo . Nesse caso, os primeiros N+S documentos são adicionados ao heap mínimo ou máximo (dependendo da direção da classificação) e, em seguida, cada próximo documento é comparado à raiz da árvore, que contém o documento mínimo ou máximo atual, e é adicionado à árvore, se necessário. Nesse caso, a complexidade no pior caso, quando você precisa reconstruir constantemente a árvore, é O(M lg M), a complexidade média é O(M), como na seleção rápida.
No entanto, o heap streaming acaba sendo mais eficiente devido ao fato de que, na prática, a maioria dos documentos pode ser descartada sem reconstruir o heap após uma única comparação com seu elemento raiz. Essa classificação é implementada no banco de dados de documentos Zebra na memória desenvolvido e usado no Kontur.
Tarefa 3. Trocas de estado
Foi necessário propor o algoritmo mais eficiente para mudança de estados:
Sua equipe tem a tarefa de desenvolver um sofisticado mecanismo de troca de estado para um cluster distribuído de N nós. O estado do i-ésimo nó deve ser transferido para o (i+1)-ésimo nó, o estado do N-ésimo nó deve ser transferido para o primeiro nó. A única operação suportada é a troca de estado quando dois nós trocam seus estados atomicamente. Sabe-se que uma troca de estado leva M milissegundos. Cada nó é capaz de participar de uma única troca de estado a qualquer momento.
Quanto tempo leva para transferir os estados de todos os nós em um cluster?
Análise da solução (texto)
Solução de superfície: troque os estados do primeiro e do segundo elemento, depois do primeiro e do terceiro, depois do primeiro e do quarto e assim por diante. Após cada troca, o estado de um elemento estará na posição desejada. Você tem que fazer O(N) permutações e gastar O(N M) tempo.
O tempo linear é longo, então você pode trocar os estados dos elementos em pares: o primeiro com o segundo, o terceiro com o quarto e assim por diante. Após cada troca de estado, cada segundo elemento estará na posição correta. Você tem que fazer permutações O(lg N) e gastar tempo O(M lg N).
Porém, é possível tornar a mudança ainda mais eficiente - não em linear, mas em tempo constante. Para fazer isso, na primeira etapa, você precisa trocar o estado do primeiro elemento pelo último, do segundo pelo penúltimo e assim por diante. O estado do último elemento estará na posição correta. E agora precisamos trocar o estado do segundo elemento pelo último, do terceiro pelo penúltimo e assim por diante. Após esta rodada de trocas, os estados de todos os elementos estarão na posição correta. Haverá O(2M) ~ O(1) permutações no total.
Tal solução não surpreenderá um matemático que ainda se lembra de que uma rotação é uma composição de duas simetrias axiais. A propósito, é trivialmente generalizado para um deslocamento não por um, mas por K < N posições. (Escreva nos comentários como exatamente.)
Você gostou de quebra-cabeças? Conhece outras soluções? Compartilhe nos comentários.
E aqui estão alguns links úteis no final:
- aprender mais sobre em contorno
- veja os registros internos sobre sistemas distribuídos
- assista a série de videoaulas»
- inscreva-se no nosso
Fonte: habr.com