Sincronização em Sistemas Distribuídos

Sincronização

Sincronização dos dados armazenados é um ponto crucial em um sistema de dados distribuído, os servidores destes sistemas muitas vezes precisam executar operações onde o tempo é muito importante.

Como exemplo, um sistema de arquivos distribuídos, que é acessado por um servidor de build. Neste sistema, ao executar uma operação de compilação, para melhorar a performance do build o servidor deverá compilar apenas os arquivos que foram alterados desde a última compilação.

Em sistemas muito complexos, com muitos arquivos de código, compilar todos os arquivos a cada build, gera um disperdício de recursos na máquina de build, principalmente nos sistemas de build contínuo, muito comuns no desenvolvimento de software ágil, onde a cada alteração de código (commit no sistema de arquivos) um build é realizado. 

Neste caso, a sincronização dos relógios destes servidores é muito importante, já que se cada um destes servidores estiverem com o relógio marcando um horário diferente, nós podemos ter erros graves no processo de build, como a não compilação de um arquivo que foi alterado após a última compilação, caso o relógio da máquina onde ele foi armazenado esteja atrasado.

Por exemplo, em uma máquina de build com o relógio marcando 12:00, e máquina do sistema de arquivos com o horário marcando 11:50, se uma operação de compilação for executada as 12h no relógio da máquina do build, qualquer alteração em um arquivo na máquina do sistema de arquivo nos próximos 10 minutos serão ignoradas pelo compilador. Já que para a máquina do build esta alteração foi realizada no "passado" devido a diferença entre os horários dos servidores.

Sincronização de relógios:

A primeira coisa que se pensa, para resolver este tipo de problemas é simplesmente acertar todos os relógios de todas as máquinas para um mesmo horário. Mas isto não basta para resolver este problema, primeiro por que é impossível fazer isso em todas as máquinas, além de cada relógio ter o seu próprio "ritmo" e cada um deles, irá adiantar ou atrasar de uma maneira diferente, dependendo de como ele foi construído.

Os relógios mais precisos que o homem conseguiu inventar até hoje, são os relógios atômicos, feito com a vibração do átomo de césio 133, rubídio ou hidrogênio, que costumam ter um delta (diferença entre o horário real e o horário do relógio) de 1 segundo a cada 65 mil anos. E são eles que são usados como referência para acertar os relógios de todas as máquinas.

Esta sincronização é realizada por servidores, que estão ligados a estes relógios, que enviam os dados do horário atual, quando requisitados.

Mas mesmo esta sincronização com um relógio atômico, pode apresentar atrasos, como alguma alteração entre a comunicação da sua máquina com o relógio externo, um atrazo na comunicação entre a sua máquina e a máquina ligada ao relógio e tudo isso tem que ser levado em conta quando estamos sincronizando um sistema distribuído.

Existem vários fatores e cálculos a serem executados em uma, aparentemente simples operação, de sincronia de relógios.

Sincronização de relógios em sistemas:

Um exemplo de sistema distribuído que necessita de sincronização de relógios é o GNSS (Global Navigation Satellite Systems, ou Sistemas Globais de Navegação por Satélite), cujo sistema funciona através da comunicação entre um equipamento, e pelo menos três, dos satélites disponíveis. 

Além do GPS, que é americano e foi inicialmente desenvolvido para usos militares do exército dos EUA, hoje temos disponível outros quatro sistemas de geolocalização disponíveis: o QZSS (Japão), o BEIDOU (China), o GALILEO (Europa) e o GLONASS (Russo).

Em alguns destes sistemas geo estacionários que compõe a constelação destes sistemas. Cada um destes satélites possui até quatro relógios atômicos, que são regularmente calibrados por equipamentos especiais na terra, estes satélites ficam emitindo sinais do seu posicionamento e o tempo dos seus relógios para a terra. Na terra os aparelhos de geoposicionamento captam estes sinais e através da informação da posição de cada satélite e a informação do tempo fornecido pelo sinal é possível calcular quanto tempo a mensagem daquele satélite demorou para chegar até ele e com isso é possível calcular qual é posicionamento daquele equipamento, atualmente os sitemas mais modernos prometem propiciar uma precisão de até 8mm no seu posicionamento.

Hoje em dia estes sistemas utilizam um mix de satélites geoestacionários, que são aqueles que não se movimentam em relação a terra, satélites com órbitas inclinadas e algumas vezes levemente elíptica além de satélites com órbitas geossíncrona. A órbita geo estácionária é aquela órbita em que o satélite dá uma volta em exatamente um dia da terra, na linha do equador, e a órbita geossíncrona é a órbita onde um satélite demora exatamente um dia para dar uma volta na terra, porém ela acontece fora da linha do equador.

Para que o sistema funcione é preciso que o aparelho posicionador receba informações de no mínimo três satélites, já que o cálculo de posicionamento é feito através de uma triangulação.

Qualquer interferência de comunicação entre o aparelho posicionador e o satélite afetam o desempenho e a precisão da informação fornecida pelo sistema. Muitos cálculos podem ser feitos para evitar, ou corrigir estas interferências, mas um ponto crucial deste sistema é a sincronia dos relógios do satélites presentes no sistema, já que 20 nanosegundos de discrepância entre os relógios destes satélites, podem levar a um erro enorme no cálculo do posicionamento do aparelho.

Este sistema é muito interessante para analisar as dificuldades da sincronização de um sistema de relógios distribuído.

O funcionamento do sistema de posicionamento global é um excelente exemplo de como a sincronização de servidores é muito importante e ao mesmo tempo complicada.

Um outro ponto importante na sincronização de relógios, a ser analisado, é que um relógio que está adiantado nunca pode voltar no tempo, já que uma informação gravada agora, nunca poderá ficar no futuro. Com isso quando um relógio está adiantado, para voltar ao tempo correto e acertar o seu horário, ele deverá contar com alguns segundos falsos. Por exemplo, se o relógio está 10 segundos adiantados, para acertá-lo o relógio deverá contar 10 segundos falsos durante o decorrer de um tempo, que é definido como o tempo de acerto do horário, para voltar a ter a hora correta.

UTC

Quando estamos trabalhando com datas no desenvolvimento de softwares, muitas vezes os servidores ficam em regiões diferentes, principalmente quando estamos usando mais de um data center. Com isso podemos ter uma certa confusão de horários devido aos diferentes fusos horários do sistema.

Para resolver este problema a comunidade científica criou o UTC (Coordenada Universal de Tempo), o que antigamente era conhecido como Greenwich.

O UTC é uma coordenada, também conhecida como fuso 0, que passa pela cidade de Londres, na Inglaterra.

Através do UTC, foram introduzidos nos relógios, os leap seconds, que foram criados para corrigir a variação do tempo de rotação da terra. Já que a terra gira mais lentamente a cada dia que passa, com isso, mesmo tendo os relógios uma precisão tão grande quanto os relógios atômicos, devido a diferença de precisão entre os relógios atômicos e uma variação na velocidade de rotação da terra, de tempos em tempos os relógios precisam ser atualizados, esta atualização é chamada de leap seconds e desde a criação deles, que aconteceu no ano de 1972, 37 leap seconds foram inseridos para corrigir o tempo dos relógios atômicos.

Em todos estes casos os relógios foram atrasados pois a terra estava rodando mais devagas, porém agora em 2021 foi notado que a terra, no ano de 2020, começou a rodar mais rápido os 28 dias mais curtos desde 1962, com isso tem-se discutido a criação de um leap second negativo para dar conta desta atualização.

Os horários de cada local (fuso-horário) são definidos em relação ao tempo do UTC, alguns negativamente como o horário oficial de Brasília no Brasil UTC -3h, ou positivos como o UTC de Sydney +10h.

Network Time Protocol

Um processo comumente utilizado na sincronização de relógios em sistemas de rede é o Protocolo de Tempo de Rede, que é bem comum em servidores conectados a internet. Neste protocolo, existem algumas máquinas que são chamadas de servidores de tempo, ou por que estão conectados a um relógio preciso, ou por que possuem um relógio preciso.

O grande problema é que para conectar-se com estes servidores, algum tempo será perdido na comunicação entre as duas máquinas, tanto no envio das mensagens, quanto no recebimento da resposta. Para corrigir este atraso gerado pelo tempo de comunicação, assumindo que tanto a mensagem de ida, quanto a resposta, levaram o mesmo tempo para serem transmitidas. O cliente pergunta ao servidor qual é o tempo atual, e esta mensagem de pergunta segue com um atributo de tempo atual da máquina cliente. Quando o servidor de tempo responder, a mensagem de resposta retorna com o tempo, da máquina cliente, quando a mensagem foi enviada e o horário da máquina do servidor, tanto o horário de recebimento da mensagem, quanto o horário de resposta.

Com estes quatro atributos, timestamp do cliente na pergunta e na resposta, e timestamp do servidor, no recebimento da mensagem e na resposta, é possível calcular uma média de tempo de atraso e com isso chegar a um valor de acerto do horário local da máquina.

É claro que para uma maior precisão, esta troca de informações entre as máquinas, não será realizada apenas uma vez, mas sim múltiplas vezes para obter uma média de diferença de tempo entre o relógio local e o do servidor.

Com a utilização do ntp é possível manter o relógio da sua máquina com uma precisão entre 1 e 50 milissegundos.

Algorítimo de Berkeley

No protocolo NTP o funcionamento do servidor é passivo, ou seja, ele só recebe requisições de perguntas do tipo que horas são? E processa estas requisições. Já no protocolo de Berkley é ao contrário. O servidor fica perguntando para os seus clientes de tempos em tempos, que horas são? E com as respostas recebidas das máquinas, ele realiza uma média e envia o resultado para os clientes atualizarem seus relógios.

Note que este algorítmo não possui uma precisão muito boa, já que se todas as máquinas de rede estiverem adiantadas, com uma média de uma hora, os relógios serão sincronizados para uma hora a frente do horário real.

Existem muitos casos onde é necessário que os horários das máquinas estejam sincronizados dentro do sistema, porém o horário real não é necessário para o correto funcionamento do sistema, nestes casos o algoritmo de Berkley funciona muito bem. Note que o relógio do servidor deverá ser atualizado manualmente de tempos em tempos afim de recalibrá-lo.

Relógio Lógico

Até agora tratamos de sincronização de relógios que são relacionados ao tempo real, ou então relacionado a um acordo entre nós específicos sobre o tempo atual, o que não necessariamente está relacionado ao relógio real.

Entretanto, para alguns casos, como em um sistema distribuído de build é necessário que dois nós concordem que uma versão de um arquivo Arquivo.src, de código fonte, está desatualizado por uma nova versão. Neste caso ser notificado pelos eventos um dos outros, como uma nova versão do Arquivo.src é o que importa. O número da versão deste arquivo é o que importa, e não em qual período de tempo ele foi compilado, esta é uma das características dos relógios lógicos.

Em alguns casos, apesar de a sincronização dos relógios das máquinas ser possível, ela não será necessária. Como no caso de dois processos que não interagem não é necessário que os seus relógios sejam sincronizados, já que a falta desta sincronização não afeta o resultado. Outro fator importante é que nem sempre o horário em que as operações foram executadas é o fator mais importante, mas sim a sequência em que elas foram executadas.

Relógio Lógico de Lamport

Lamport definiu uma relação necessária para se sincronizar relógios lógicos, esta relação, chamada de acontece antes é definida quando todos os processos concordam que um processo a aconteceu antes do processo b.

O que é preciso para definir esta sequência é uma maneira de se medir uma noção de tempo onde cada evento a aconteça antes de um evento b. No caso dos dois processos acontecerem em um mesmo núcleo de um processador, esta relação é simples, basta verificar o timestamp da máquina.

Mas quando eles ocorrem em máquinas separadas estas mensagens devem ter algo para determinar que a aconteceu antes de b.

No algoritmo proposto por Lamport, uma mensagem enviada possui um parâmetro de timestamp. Caso esta mensagem chegue a um servidor, onde o seu horário local seja menor do que o timestamp da mensagem, o relógio deste servidor será acertado para o timestamp da mensagem +1.

Nos casos em que nenhum processo pode acontecer ao mesmo tempo, o número do processo em que o evento aconteceu é anexado ao timestamp do processo, separado por casas decimais.

Um exemplo de aplicação do relógio de Lamport é uma base de dados replicada em várias regiões. Por exemplo o que pode ser feito por um banco para melhorar a performance das queries executadas no seu banco de dados. Neste caso as queries sempre serão direcionadas para o servidor de dados mais próximo do cliente. Porém esta replicação implica em um maior tempo gasto nos updates, já que eles devem ser realizados nas duas instâncias deste banco de dados, afim de manter a consistência.

Assuma que os dados deste banco estejam no Rio e em São Paulo. Um dos clientes deste banco tem uma conta poupança com R$ 1100,00 de saldo, e uma operação de depósito de R$100,00 é realizada no Rio e ao mesmo tempo, uma operação de update em batch está sendo realizada em São Paulo, para atualizar os valores referentes ao rendimento da poupança no mês anterior. Nesta operação o cliente receberá um aporte de 1%.

A operação de depósito é realizada primeiro no Rio, e o processo de atualização monetária é realizado primeiro em São Paulo. Neste caso o saldo do rio seria R$ 1121 e o saldo de São Paulo seria R$1120.

Este exemplo mostra como é importante que algumas operações sejam realizadas na mesma ordem nas duas bases.

Relógios de Vetor

O relógio de Lamport leva a uma situação onde todos os eventos de um sistema distribuído estão totalmente ordenados. Entretanto apenas o timestamp das mensagens não pode comprovar que uma mensagem aconteceu após a outra. Como vimos anteriormente cada relógio pode andar em uma velocidade diferente, e isto implica em diferenças de horário entre cada máquina.

Um relógio de vetor resolve este problema alocando duas propriedades em uma mensagem, primeiro o valor de quantos processos foram executados até agora naquela máquina e também o valor de quantos processos foram executados na outra máquina da rede (para onde foi enviada a mensagem). Com isso é possível saber quando um processo aconteceu após o outro.

A primeira propriedade é mantida na própria máquina, acrescentando 1 a cada processo executado e a segunda é mantida através de mensagens que são enviadas entre as máquinas.

Exclusão Mútua

Concorrência e colaboração são fundamentais em um sistema distribuído que possui uma carga de processos elevada. Em muitos casos isso significa que vários processos tentarão acessar um mesmo recurso ao mesmo tempo. Para prevenir que este acesso simultâneo corrompa os dados ou torne-os inconsistentes, foi necessário o desenvolvimento de soluções que garantissem um acesso único a determinados recursos do sistema.

Algoritmos distribuídos de exclusão mútua podem ser classificados em duas categorias. Os baseados em token, onde uma mensagem, ou token, é passado entre os processos e cada token é responsável pela liberação de um recurso no sistema, e para acessar um recurso deste sistema, o processo necessitará do token. Quando o processo termina de utilizar o recurso o token é repassado para o próximo processo da fila.

A grande vantagem dos sistemas baseados em token é que, dependendo de como os processos são organizados é possível assegurar que todos os processos terão acesso aos recursos. Um outro ponto importante destes sistemas é que ele consegue facilmente evitar deadlocks, que são explicados aqui.

O ponto fraco destes algoritmos é bem sério e acontece quando o token se perde, um processo intrincado deverá ser inicializado para assegurar que um novo token será criado.

Uma outra forma de classificar os algoritmos de exclusão mútua são os algoritmos baseados em permissão, onde um processo que queira acessar um recurso, primeiro deverá pedir permissão para um outro processo.

Algoritmo Centralizado

A maneira mais fácil de implementar um algoritmo baseado em permissão é utilizando um algoritmo centralizado. Para entender como eles funcionam pode-se simular como funciona um processador de um núcleo. Quando um processo quer acessar um recurso ele pede permissão ao coordenador. Caso o recurso esteja livre o coordenador manda uma resposta garantindo a permissão de acesso e quando esta resposta chega ao processo ele pode seguir com o processamento.

Caso um outro processo queira acessar o mesmo recurso do sistema, existem duas formas diferentes do coordenador responder. A primeira é enviar uma mensagem de acesso negado, a segunda é não responder a requisição o que travaria o processo requisitante. Nos dois casos a chamada fica em uma fila e o coordenador fica livre para receber outras requisições.

Quando o processo que está usando um recurso termina de utilizá-lo ele envia uma mensagem ao coordenador dizendo que o recurso não será mais utilizado por aquele processo, o coordenador pega o primeiro processo da fila e envia para ele uma mensagem de autorizando a utilização do recurso.

As desvantagens deste processo são, já que ele somente possui um ponto de acesso, caso este ponto falhe o sistema inteiro irá falhar. Em um sistema de grande volume, o coordenador pode se tornar um ponto de gargalo do sistema.

Algoritmo Descentralizado

Em alguns casos, o algoritmo centralizado não vai resolver os nossos problemas, para isso foi proposta a utilização de um algoritmo de votos que pode ser executada usando um sistema baseado em DHT, o qual replica um recurso em vários nós e em cada nó haverá um coodenador para controlar o acesso a ele.

Neste caso o recurso só será liberado se a maioria dos coordenadores liberar o acesso. Quando um recurso for negado em uma requisição, uma mensagem de permissão negada será enviada, funciona exatamente como em uma eleição, só que o recurso só será liberado se todo mundo votar a favor da liberação.

Esta organização torna este algoritmo menos vulnerável a falhas de um simples coordenador, do que o algoritmo centralizado. E quando um coordenador falha, a sua recuperação é bem rápida, já que ele controla apenas alguns nós.

Entretanto, ao cair, aquele coordenador irá esquecer todos os votos dados anteriormente e com isso perde-se também a lista de recursos liberados e alocados, o que pode acarretar em uma duplicidade de liberação de um recurso.

Algoritmo Distribuído

Uma das maneiras de se implementar um algoritmo de exclusão mútua distribuído requer ordenação de todos os eventos que aconteceram no sistema, ou seja para qualquer par de eventos, como o envio de uma mensagem, deve haver uma forma de determinar qual delas ocorreu primeiro. O algoritmo de Lamport, apresentado acima, é uma das maneiras utilizadas para ordenar os eventos de um sistema.

Neste sistema, quando um processo deseja acessar um recurso do sistema, ele cria uma mensagem contendo o nome do recurso, o número do seu processo e o tempo local. Esta mensagem será enviada a todos os processos, incluindo ele mesmo, do sistema, e para isso é necessário que o envio de mensagens seja confiável.

Quando um processo recebe este tipo de mensagem, a sua resposta depende de qual é o seu estado atual referente aquele recurso presente na mensagem.

Caso o processo não precise acessar aquele recurso, ele simplesmente retorna uma mensagem de Ok. Quando o processo está acessando aquele recurso, ele simplesmente não responde e coloca aquela requisição do processo em uma fila. Finalmente, se o processo deseja acessar aquele recurso, ele irá comparar o seu registro de quando ele foi inicializado, com este registro do processo requisitante, onde o que tiver ocorrido primeiro ganha acesso ao recurso e o outro seguirá para a fila de requisições.

Depois de enviar uma requisição de permissão acesso, o processo ficará esperando pelas respostas positivas de todos os processos e só depois de recebê-las é que este processo irá continuar. Depois que ele termina de acessar aquele recurso ele manda uma mensagem de OK para todos os processos da sua fila e apaga todos eles.

Este algoritmo diferente do algoritmo centralizado, não possui um ponto de falha simples, ou seja caso algum coordenador falhe, o sistema não irá cair. Entretanto quando acontece uma falha destas, a sua não resposta poderá ser interpretada como uma negação de acesso e com isso bloqueia todas as requisições subsequentes.

Para corrigir este problema, basta implementar uma resposta para todas requisições, com isso quando uma resposta não chegar, pode-se reenviar a requisição até que haja uma resposta, ou até que este processo conclua que o receptor morreu.

Este algoritmo é mais pesado, complexo, complicado e menos robusto que o algoritmo centralizado.

Token Ring

Em um algoritmo de token ring, a rede é organizada em um anel, onde cada processo conhece um vizinho e com isso forma-se um anel até que o último conecte-se ao primeiro. O token serve para representar cada recurso do sistema, e ele circula pelo anel passando por todos os processos.

Em cada processo, o token é analisado e caso ele precise utilizar aquele recurso ele pega o token e utiliza o recurso, com isso é fácil entender que como o token representa o recurso e ele só está em um processo de cada vez, não haverá acesso concorrente aos recursos do sistema.

Caso um token seja perdido ele deverá ser regerado, e detectar que um token foi perdido é uma tarefa bem complicada, já que o tempo que um token leva para circular pelo anel é imprevisível, e este tempo dependerá de quantos e como os processos utilizarão aquele recurso.

Este algoritmo também apresenta problemas quando um processo quebra, porém a recuperação é mais simples que nos outros casos. Quando um nó tenta passar o token para o seu vizinho e esta requisição falha, ele poderá repassá-la ao vizinho do seu vizinho, porém para isso é necessário que todos os processos da rede mantenham uma configuração dos processos do anel. Após esta reconfiguração o processo morto poderá ser removido do anel.

Posicionamento Global de nós

Quando o número de nós de uma aplicação cresce, começa a ficar difícil que todos os nós e dela se conheçam. Este mapeamento dos nós é importante para executar algoritmos distribuídos de roteamento, multicasting, troca de dados, busca, etc.

Imagine um website que está clusterisado em vários datacenters, quando você se conecta a este website, ele deverá te direcionar para o nó mais próximo da sua conexão. Para fazer isso o website deverá mapear os nós onde eles está presente e determinar qual é o nó que leva menos tempo para trocar dados com o seu dispositivo.

É importante notar que o tempo de troca de dados entre o seu dispositivo e uma determinada rede do website não é consistente, com isso ao entrar na home page, você pode ser redirecionado ao datacenter A, e ao logar você pode ser redirecionado ao datacenter B.

Não faz muito sentido o website ficar medindo a distância dos seus clientes para todas as suas subredes a cada execução, para isso é executado um sistema parecido com o GPS, onde um ponto na subrede é checado e com isso obtêm-se uma previsão de qual ponto estará mais próximo do cliente.

Algoritmos de Eleição

Muitos dos algoritmos distribuídos precisam de um processo coordenando as requisições. Geralmente não importa qual processo possui esta responsabilidade, porém alguém tem que assumir este papel. Para determinar qual processo será responsável pela coordenação existem algoritmos de eleição. Para estes algoritmos consideramos que todos processos da rede se conhecem, e que cada processo possui uma numeração, ou baseada no endereço dele, ou baseado no seu id de processo, etc. Esta numeração será utilizada na eleição.

Algoritmo de Bully

Neste algoritmo, sempre que o processo coordenador não está disponível, uma mensagem de ELEIÇÃO será enviada para todos os processos da rede, que tenham um id maior do que o id do processo requisitante. Caso ninguém responda esta mensagem o próprio processo da requisição irá assumir o papel de coordenador.

Quando um processo recebe uma mensagem de ELEIÇÃO ele deverá repassar ela para todos os processos com id maior do que o dela e caso não existam processos com id maior, ou caso nenhuma resposta a esta mensagem seja recebida, aquele nó irá assumir o papel de coordenador.

Assim que um processo que estava morto retorna a rede, ele irá enviar uma mensagem de ELEIÇÃO para os nós daquela rede e caso ele tenha o maior id ele irá assumir o papel de coordenador.

Algoritmo de anel

Neste caso a organização dos processos será em forma de anel ordenado e cada processo conhecerá o seu sucessor. Assim que um processo descobre que o coordenador não está disponível ele envia uma mensagem de ELEIÇÃO, contendo o seu id de processo, para o seu sucessor, o que o torna um candidato ao cargo de coordenador, caso nenhum processo seja achado na rede com id maior do que o seu, ele irá assumir o papel de coordenador.

Assim que um coordenador é eleito, uma mensagem de COORDENADOR é repassada pela rede, e ao chegar ao processo que disparou aquela mensagem isso poderá ser detectado através do id do processo que estará presente nesta mensagem.

Apresentação