Alguns dias atrás, houve uma conferência Hydra . Os caras do grupo JUG.ru convidaram os palestrantes dos sonhos (Leslie Lampport! Cliff Click! Martin Kleppmann!) E dedicaram dois dias a sistemas e computação distribuídos. Contour foi um dos três parceiros da conferência. Conversamos no estande, conversamos sobre nossas instalações de armazenamento distribuído, jogamos bingo, resolvemos problemas.
Este é um post com análise de tarefas no estande Contour do autor do texto. Quem esteve na Hydra é o seu motivo para recordar impressões agradáveis, que não estavam - uma chance de esticar seu cérebro com grande O- note.
Havia até participantes que desmontaram o flipchart em slides para registrar sua decisão. Não estou brincando - eles entregaram para verificar este pacote de papel:
Havia três tarefas no total:
- sobre como escolher réplicas de pesos para balanceamento de carga
- sobre a classificação dos resultados de uma consulta em um banco de dados na memória
- na transferência de estado em um sistema distribuído com uma topologia em anel
Tarefa 1. ClusterClient
Foi necessário propor um algoritmo para a seleção efetiva de K de N réplicas ponderadas de um sistema distribuído:
Sua equipe está encarregada 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 pontos flutuantes W 1 ..W N a eles. Para dar suporte à estratégia de execução simultânea, a biblioteca deve poder escolher K de N nós aleatoriamente - a chance de ser selecionada deve ser proporcional ao peso de um nó.
Propor um algoritmo para selecionar nós de maneira eficiente. Estime sua complexidade computacional usando grande notação O.
Por que tudo está em inglês?Porque desta forma, os participantes da conferência lutaram com eles e porque o inglês era o idioma oficial da Hydra. As tarefas eram assim:
Pegue papel e lápis, pense, não se apresse em abrir imediatamente os spoilers :)
Discussão (vídeo)A partir das 5:53, apenas 4 minutos:
E aqui está como aqueles caras com um flipchart apresentaram sua decisão:
Análise da decisão (texto)Na superfície, existe uma solução: somar os pesos de todas as réplicas, gerar um número aleatório de 0 à soma de todos os pesos e escolher uma réplica i, de modo que a soma dos pesos da réplica de 0 ao (i-1) é menor que o número aleatório e a soma dos pesos da réplica de 0 a i-ésima - mais do que isso. Você escolherá uma réplica e, para selecionar a próxima, precisará repetir todo o procedimento sem considerar a réplica selecionada. Com esse algoritmo, a complexidade de escolher uma réplica é O (N), a complexidade de escolher K réplicas é O (N · K) ~ O (N 2 ).
A complexidade quadrática é ruim, mas pode ser melhorada. Para fazer isso, construa uma árvore de segmentos para as somas de pesos. Isso produzirá uma árvore com uma profundidade de log N, nas folhas das quais haverá pesos de réplica e, nos nós restantes, somas parciais, até a soma de todos os pesos na raiz da árvore. Em seguida, geramos um número aleatório de 0 à soma de todos os pesos, localizamos a i-ésima réplica, a excluímos da árvore e repetimos o procedimento para procurar as réplicas restantes. Com esse algoritmo, a complexidade de construir uma árvore é O (N), a complexidade de encontrar a i-ésima réplica e removê-la da árvore é O (log N), a dificuldade de escolher K réplicas é O (N + K log N) ~ O (N log N) .
A complexidade logarítmica linear é mais agradável que a complexidade quadrática, especialmente para grandes K.
Esse algoritmo é implementado no código da biblioteca ClusterClient do projeto Vostok .
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 está encarregada de desenvolver um banco de dados de documentos na memória fragmentado. Uma carga de trabalho comum seria selecionar os N documentos principais 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 N superior após ignorar os principais documentos S (S ~ N).
Propor um algoritmo para executar essas consultas com eficiência. Estime sua complexidade computacional usando grande notação O no caso médio e nos piores cenários.
Discussão (vídeo)Comece às 34:50, apenas 6 minutos:
Análise da decisão (texto)A solução está na superfície: classifique todos os documentos (por exemplo, usando o quicksort ) e leve os documentos N + S. Nesse caso, a complexidade da classificação, em média, é O (M lg M), na pior das hipóteses - O (M 2 ).
Obviamente, classificar todos os documentos M para levar apenas uma pequena parte deles é ineficiente. Para não classificar todos os documentos, o algoritmo de seleção rápida é adequado , que seleciona N + S dos documentos necessários (eles podem ser classificados por qualquer algoritmo). Nesse caso, a complexidade diminui, em média, para O (M), e o pior caso permanece o mesmo.
No entanto, você pode fazê-lo ainda mais eficientemente - use o algoritmo de streaming de heap binário . Nesse caso, os primeiros documentos N + S são adicionados à pilha mínima ou máxima (dependendo da direção da classificação) e, em seguida, cada documento subsequente é comparado com a raiz da árvore, que contém o documento mínimo ou máximo no momento, e é adicionado à árvore, se necessário. . Nesse caso, a complexidade no pior dos casos é quando você precisa reconstruir constantemente a árvore - O (M lg (N + S)), a complexidade média é O (M), como na seleção rápida.
No entanto, o fluxo de heap é mais eficaz 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 memória de documentos da Zebra, desenvolvido e usado no circuito.
Tarefa 3. Trocas de estado
Era necessário propor o algoritmo mais eficiente para a mudança de estado:
Sua equipe está encarregada de desenvolver um mecanismo sofisticado 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 i-é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 decisão (texto)Uma solução na superfície: troque os estados do primeiro e do segundo elemento, depois o primeiro e o terceiro, depois o primeiro e o quarto, e assim por diante. Após cada troca, o estado de um elemento estará na posição desejada. Você precisa fazer permutações O (N) e gastar tempo O (N · M).
O tempo linear é muito longo, portanto 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, o estado de cada segundo elemento estará na posição desejada. Teremos que fazer permutações O (log N) e gastar tempo O (M log N N).
No entanto, você pode tornar a mudança ainda mais eficaz - não em linear, mas em tempo constante. Para fazer isso, na primeira etapa, você precisa trocar o estado do primeiro elemento com o último, o segundo com o penúltimo e assim por diante. O estado do último elemento estará na posição desejada. E agora você precisa trocar o estado do segundo elemento com o último, o terceiro com o penúltimo e assim por diante. Após essa rodada de trocas, os estados de todos os elementos estarão na posição correta. No total, serão feitas permutações de O (2M) ~ O (1).
Essa solução não surpreenderá um matemático que ainda se lembra de que a rotação é uma composição de duas simetrias axiais. A propósito, é trivialmente generalizado mudar não por um, mas pelas posições K <N. (Escreva nos comentários exatamente como.)
Você gosta de quebra-cabeças? Você conhece outras soluções? Compartilhe nos comentários.
E aqui estão alguns links úteis no final: