Nos sistemas distribuídos, existem vários problemas fundamentais: transações distribuídas eficientes, processamento de dados exatamente uma vez, sincronização precisa de relógios físicos. Para resolver o último problema , diferentes tipos de relógios lógicos foram inventados .
Não obstante, os relógios vetoriais têm propriedades desagradáveis: eles introduzem uma dependência condicional entre eventos onde ele não existe e perdem-no onde realmente estão.
No entanto, você pode criar algo mais confiável - Kronos. No artigo, examinaremos o algoritmo de contabilidade de relacionamento de causa e efeito e seu aplicativo para criar o repositório Key-Value com transações distribuídas.
Os problemas
Como já mencionado, há vários problemas com o relógio lógico:
Dependências inexistentes surgem porque um relógio lógico introduz uma ordem completa nos eventos - ou seja, é possível dizer que qualquer um dos dois eventos é condicionalmente anterior e posterior. O contrato é condicional, uma vez que é impossível determinar com precisão a relação entre os eventos no tempo, inclusive devido à Teoria Especial da Relatividade.
Por outro lado, um relógio lógico considera apenas a interconexão através de mensagens dentro do sistema. Se alguns dois eventos estiverem conectados, mas fora do sistema, por exemplo, através do usuário (adicionando mercadorias à cesta em uma parte do sistema -> pagamento pelo pedido), o relógio lógico poderá perder esse relacionamento.
Os relógios lógicos não podem ser acessados de fora e também é difícil interconectar vários componentes independentes (sistema de arquivos distribuídos, serviços de processamento de solicitações, análises).
Solução
Um artigo de 2014 da Kronos: O design e a implementação de um serviço de pedidos de eventos propõe uma solução - um serviço independente que levará em consideração as relações de causa e efeito nos eventos.
A principal abstração dentro do Kronos é um evento no qual a ordem parcial é introduzida. A relação de causalidade é transitiva - ou seja, se, por exemplo, sabemos que a criação de um arquivo precede sua alteração e a alteração precede a exclusão, podemos concluir lógico que a criação ocorreu antes da exclusão.
A API mínima pode ser definida pelo seguinte conjunto de métodos:
| Método | Resultado | Comentário |
|---|
create_event() | e | Cria um novo evento no Kronos |
query_order([(e_1, e_2), ...]) | [<-, concurrent, ->, ...] | Para cada par da solicitação, ele retorna a direção do relacionamento causa-efeito ou a simultaneidade de eventos |
assign_order([(e_1, e_2, must), (e_3, e_4, prefer), ...]) | OK/FAIL | Para cada par da solicitação, define a direção da causalidade |
acquire_ref(e) | OK | Aumenta o contador de referência para este evento. |
release_ref(e) | OK | Diminui a contagem de referência para este evento. |
Implementação
É lógico que o sistema seja baseado em um gráfico de eventos orientado, com uma pesquisa abrangente e abrangente para verificar a relação dos eventos, um mecanismo de estabilidade em caso de falha e coleta de lixo.
Como pode ser visto na API, a solicitação assign_order aceita um tipo de relacionamento causal: must ou prefer . must corresponder a invariantes estritos - por exemplo, _->_ , prefer não ser aplicado se entrar em conflito com os relacionamentos must . Um exemplo do uso de prefer é que as solicitações que vieram antes são melhor agrupadas antes, mas isso não afeta a correção.
BFS eficaz
No nosso caso, o gráfico pode ser grande, mas os eventos para os quais as solicitações de verificação serão executadas geralmente estarão próximos. Portanto, você deve executar o BFS mais rapidamente nesses casos.
Na implementação padrão, o lugar mais longo é a inicialização da matriz de vértices visitados, que sempre leva tempo igual ao número de vértices no gráfico. Em vez disso, você pode usar uma tabela de hash ou aplicar outros truques.
Coleta de lixo
Como você pode ver na tabela, existem mais dois métodos: acquire_ref e release_ref .
Dentro do Kronos, um contador de referência é armazenado para cada evento. Enquanto algum serviço processa o evento ou reserva a capacidade de adicionar novos eventos que ocorram após o atual, ele armazena o link. Quando essa necessidade desaparece, o serviço chama release_ref .
Kronos excluirá o evento quando todas as condições forem atendidas:
- O número de links atingiu zero
- Todos os eventos anteriores a isso já foram excluídos do gráfico.
Essa abordagem não limita as consultas possíveis, mas economiza memória dentro do Kronos.
Aplicações
Considere o uso do sistema usando o exemplo de armazenamento de valor-chave com transações distribuídas.
Suponha que existam vários servidores, cada servidor é responsável por um intervalo de chaves.
Cada transação corresponde a um evento no Kronos. Para cada chave, o servidor deve armazenar o número da última transação na qual essa chave participou. O cliente cria um evento e envia seu número a todos os servidores cujas chaves são afetadas por esta transação. O servidor está tentando criar uma dependência no Kronos entre o número da transação atual e o evento anterior que foi salvo para essa chave. Se você não conseguir criar a dependência, a transação será reconhecida como malsucedida (observe que até agora ainda não há interação com os dados).
Se toda a operação de adição de dependência for concluída com êxito - isso significa que a transação ocorrerá e poderá ser executada. Os servidores aprendem sobre isso com o cliente e começam a executar partes da transação.
Observe que essas transações serão ACID :
- Atomicidade : a transação não será agendada no Kronos ou será agendada para execução em todos os nós.
- Consistência : automaticamente nos repositórios KV.
- Isolamento : se duas transações se cruzam de acordo com os dados, elas serão conectadas por um relacionamento causal no Kronos, o que significa que uma será executada antes da outra.
- Durabilidade : como o Kronos é resistente a quedas e assume que todas as réplicas do cofre também são estáveis, a única coisa a provar é a persistência dos dados das transações pendentes. De fato, se a transação é marcada pelo cliente como bem-sucedida, mas o registro ainda não foi concluído no servidor, é fácil estabelecer esse fato, pois o servidor também acompanha as partes concluídas das transações.
Desempenho
A implementação desse armazenamento KV pode realmente ser eficaz. O artigo original cita dados de que a implementação descrita do armazenamento KV é 4 vezes mais rápida que a transação baseada em bloqueios.
Além disso, em comparação com o MongoDB, o sistema no topo do Kronos está apenas 6% atrasado, apesar do MongoDB não usar transações distribuídas.
Análise
No entanto, a operação do Kronos tem várias desvantagens.
- Primeiro, existe a sobrecarga de acessar o Kronos - cada solicitação exigirá pelo menos uma chamada.
- O Kronos também será um ponto único de falha - os autores do artigo não oferecem maneiras de particionar o gráfico de eventos.
- Seria bom adicionar vários métodos ao sistema. Por exemplo, no exemplo com armazenamento KV, seria bom ter um retorno de chamada que informasse o servidor sobre o status da transação - foi adicionado com sucesso ao gráfico com todas as dependências necessárias - ou, inversamente, a transação não pôde ser concluída.
No entanto, o sistema descrito permite o controle flexível de uma relação causal entre eventos, garantindo conformidade previsível com os invariantes necessários.
Conclusão
Sobre isso, na GoTo School ensinamos alunos e alunos na direção de Sistemas Distribuídos.
E existem algoritmos e aplicativos , programação aplicada, bioinformática e análise de dados
Venha para a nossa escola de outono de 27 de outubro a 4 de novembro ou a escola de inverno no início de janeiro.
E se você não é mais um estudante ou um estudante - venha ensinar .