Tolerância a Falha em Sistemas Distribuídos

Tolerância a Falha

Uma característida de um sistema distribuído, que os diferencia dos sistemas simples, é a noção de falha parcial. Uma falha parcial pode acontecer, em um sistema distribuído, quando um de seus componentes falha. Este tipo de falha poderá afetar uma operação do sistema, mas não derrubar o sistema inteiro. Já nos sistemas simples, não distribuídos, uma falha geralmente derruba o sistema inteiro, ou seja afeta todos os componentes.
Um dos objetivos de um sistema distribuído é a tolerância a falhas parciais, contornando-as sem que a performance do sistema seja seriamente afetada. Quando uma falha acontece, o sistema deverá manter-se em funcionamento enquanto os reparos são realizados. Ou seja, eles devem tolerar falhas, e continuar operando, mesmo na presença destas falhas, por algum tempo, até que elas sejam corrigidas.
Atomicidade é uma propriedade importante em um sistema distribuído, em uma transação múltipla, ou seja vários dados sendo atualizados em uma única transação, devem ser atualizados todos como se fossem uma única operação. Ou todas as operações são gravadas ao mesmo tempo, ou nada será gravado. Para fazer isso em um sistema distribuído deve-se utilizar um protocolo de commit distribuído.

Introdução a tolerância a falha

Conceitos básicos

Aqui serão descritos os conceitos básicos da tolerância a falha em sistemas distribuídos. Para um sistema distribuído ser tolerante a falhas, ele deverá disponibilizar os seguintes conceitos:

• Disponibilidade
• Confiabilidade
• Segurança
• Manutenção

Disponibilidade é definido por um sistema que está sempre disponível para ser utilizado imediatamente. Este conceito se refere a probabilidade do sistema operar corretamente a qualquer hora.
Confiabilidade é definido pelo tempo em que o sistema permanece operando, sem interrupções. Comparando confiabilidade com disponibilidade, temos que a cofiabilidade define um intervalo de tempo e a disponibilidade trata-se de um determinado instante temporal. Isto é muito relativo, mas digamos que um sistema que passa um milissegundo fora do ar a cada hora, dizemos que ele tem uma disponibilidade de 99.9999% do tempo, porém ele não é confiável. Já um sistema que nunca para, mas deve ficar fora do ar por duas semanas todo mês de Março possui uma confiabilidade bem alta, porém ele tem uma disponibilidade de 96%.
Segurança se refere a uma situação onde acontece uma falha e nada de catastrófico acontece. Por exemplo, o sistema que controla o piloto automático de um avião, ou o sistema que controla os trens de um metrô são exemplos de sistemas que possuem um alto grau de segurança. Se estes sistemas falharem temporariamente, mesmo que por alguns segundos, os efeitos poderão ser desastrosos. Estes sistemas não são fáceis de serem construídos.
Manutenção trata-se da facilidade de um sistema se recuperar em caso de falha, um sistema com fácil manutenção também possui uma alta disponibilidade, especialmente quando as falhas podem ser detectadas e corrigidas automaticamente.
Uma falha em um sistema é dada quando ele não consegue cumprir o que ele foi desenvolvido para fazer. Em um sistema com múltiplos serviços, ele irá falhar quando um ou mais serviços falham. Um erro é um estado de um sistema que pode levar a uma falha.
A causa de um erro é denominada falha, e controlar estas falhas faz parte do desenvolvimento de um sistema distribuído. Fazer um sistema que possa continuar operando mesmo com a existência de falhas.
As falhas são classificadas como transiente, intermitente ou permanente, falhas transientes são as falhas que ocorrem uma vez e nunca mais repetem, mesmo quando executamos a mesma operação. Uma falha intermitente é aquela que acontece algumas vezes, depois para de acontecer e mais para frente volta a ocorrer sem nenhuma relação aparente. Estas falhas são bem complicadas de serem diagnosticadas, uma vez que a causa dela não é conhecida. Uma falha permanente é aquela que acontece e continua acontecendo até que o componente que esteja falhando é arrumado ou substituído.

Modelos de falha

Em um sistema distribuído, muitas vezes a falha não é facilmente determinada, já que muitas vezes, os servidores destes sistemas se comunicam e em uma falha do sistema de banco de dados, pode estar sendo causada por uma máquina de armazenamento de dados e não em si do banco de dados.
Para melhor entender as falhas em um sistema distribuído, foram desenvolvidas vários esquemas de classificação. Abaixo mostramos uma delas

• Falha de queda: O servidor morre, porém ele estava operando normalmente antes de morrer
• Falha de omissão: O servidor falha ao responder as requisições recebidas
• Omissão de recebimento: O servidor falha ao receber uma mensagem
• Omissão de envio: O servidor falha ao enviar mensagens
• Falha de tempo: A resposta do servidor não ocorre após um determinado período de tempo
• Falha de  resposta: O servidor envia uma resposta incorreta
• Falha de valor: O valor da resposta está errado
• Falha de estado de transição: O servidor desvia do fluxo de controle correto
• Falha arbitrária: Um servidor pode produzir respostas arbitrárias a qualquer momento

Uma falha de queda acontece quando um servidor desliga prematuramente, porém ele estava funcionando corretamente antes da falha. Um ponto importante deste tipo de falha é que nada será recebido daquele servidor depois que ele desligar.
A falha de omissão acontece quando o servidor falha em responder uma requisição e muitas coisas podem causar uma falha de omissão, por exemplo em uma omissão de recebimento o servidor nunca recebe a requisição. Neste caso mesmo que uma conexão tenha sido estabelecida entre o cliente e o servidor, a mensagem não chega, pois um serviço que "ouça" as requisições contidas nas mensagens, não foi estabelecido.
Um outro tipo de omissão pode acontecer quando o servidor processa a mensagem, mas falha em enviar uma mensagem de resposta. Neste caso o servidor precisa estar preparado para receber e reprocessar a mesma mensagem, cujo envio da resposta falhou.
Outros tipos de falha de omissão, podem estar relacionados a falha do software, como um loop infinito, ou uma administração errônea da memória.
A falha de resposta de tempo acontece quando a resposta chega fora de um intervalo de tempo específico. Uma resposta gerada muito cedo, pode causar um erro de memória, quando não há mais espaço para armazenar aquela mensagem. O mais comum é a resposta de uma mensagem atrasar, quando temos um problema de performance.
Uma das falhas mais graves é a falha de resposta, que ocorre quando um serviço retorna uma resposta incorreta. Existem dois tipos de falha de resposta, no caso de uma falha de valor, o serviço retorna um valor inválido, muitas vezes gerado devido a um bug na implementação do serviço, ou uma falha de estado de transição, a qual pode ser exemplificada por uma reação inesperada para uma requisição, por exemplo, quando um servidor recebe uma mensagem que ele não reconhece, uma falha de estado de transição acontece caso não haja nenhum tipo de medida realizada para administrar este tipo de mensagem.
O tipo de falha mais grave são as falhas arbitrárias, ou também chamadas de falha Bizantina, quando este tipo de falha acontece, os clientes devem estar preparados para o pior. Nestes casos, um servidor pode estar produzindo uma resposta que não havia sido planejada, e que não pode ser detectado como uma falha. Ou mesmo, um servidor pode estar trabalhando em conjunto com outros servidores, afim de produzir respostas erradas. Por isso que a segurança é um fator importante quando estamos falando de sistemas distribuídos.

Mascaramento de falha por redundância

Se um sistema distribuído foi planejado para tolerar falhas, a melhor maneira de fazer isso é tentar esconder os erros, quando eles acontecem em outros processos, e um ponto chave para esconder as falhas é através da utilização de redundância. Existem três tipos de redundância disponíveis, redundância de informação, redundância de tempo e redundância física.

Redundância de informação é feita através da adição de alguns bits nas mensagens, possibilitando aquela mensagem de ser recuperada em caso de falha de transmissão, como ocorre no protocolo de rede.

A redundância de tempo acontece quando uma ação é processada e depois, caso necessário, ela será reprocessada novamente. Um exemplo deste tipo de redundância acontece nas transações, que podem ser repetidas, sem nenhum aviso, em certos tipos de falhas.

Quando se trata de redundância física, máquinas extras são adicionadas a rede, afim de suportar a falha de parte das máquinas do sistema, ou mesmo suportar um aumento pontual de requisições em um serviço específico.

Resiliência de Processo

Agora que vimos o básico da tolerância a falha, vamos explicar em como implementar sistemas com esta característica

Problemas de Design

Um dos principais pontos em um sistema tolerante a falha é organizar os processos em vários grupos. O ponto chave deste sistema é quando uma mensagem é enviada para um grupo, todos os membros daquele grupo devem receber aquela mensagem. Com isso caso algum elemento do grupo falhe, um outro membro poderá cuidar daquela mensagem.
A proposta de introduzir grupos é fazer com que eles sejam classificados com uma abstração simples. Um processo pode ter que enviar uma mensagem para um grupo de servidores sem saber quem e quantos são estes servidores e isto pode se modificar de uma chamada a outra.

Grupos horizontais vs grupos hierárquicos

Uma diferença importante entre grupos tem haver com a organização da sua estrutura interna. Em alguns deles todos os processos são iguais, ninguém é o chefe e todas as decisões são tomadas coletivamente, estes grupos são conhecidos como:
Falha de queda: O servidor morre, porém ele estava operando normalmente antes de morrer
Falha de omissão: O servidor falha ao responder as requisições recebidas
Omissão de recebimento: O servidor falha ao receber uma mensagem
Omissão de envio: O servidor falha ao enviar mensagens
Falha de tempo: A resposta do servidor não ocorre após um determinado período de tempo
Falha de  resposta: O servidor envia uma resposta incorreta
Falha de valor: O valor da resposta está errado
Falha de estado de transição: O servidor desvia do fluxo de controle correto
Falha arbitrária: omo grupos horizontais. Já outros grupos possuem uma hierarquia, por exemplo um dos processos é o coordenador e todos os outros são trabalhadores. Neste caso qualquer requisição, seja ela realizada por um trabalhador interno, ou um processo externo, será direcionada ao coordenador, e ele é que decidirá qual processo será responsável por processar aquela requisição.
Cada uma destas organizações tem suas vantagens e desvantagens, os grupos horizontais não possuem um único ponto de falha, além de ele ser simétrico e no caso de um processo falhar, o grupo ficará menor, mas continuará o seu funcionamento. Porém a tomada de decisão é mais complicada, já que uma votação deverá ser realizada para a tomada de decisão.
O grupo hierárquico tem as propriedades opostas, caso o coordenador falhe, todo o grupo para de funcionar, porém enquanto o coordenador esta rodando, as decisões serão tomadas sem consultar ninguém mais.

Membro do grupo

Para estabelecer um grupo, primeiro devemos ter um método que administra os membros deste grupo, tanto para adicionar, quanto para remover os membros deste grupo. Pode-se criar um servidor do grupo que pode manter os dados de todos os membros do grupo, assim como estes métodos de alteração do grupo, porém isto nos leva a um único ponto de falha. 

Uma outra possibilidade é administrar os membros do grupo de uma maneira distribuída, por exemplo se tivermos um serviço de multicasting confiável, um processo externo poderá enviar uma mensagem para todos os membros do grupo.

Tanto a entrada, quanto a saída do grupo deverá ser síncrona, ou seja, quando um processo se junta ao grupo ele deverá receber todas as mensagens enviadas, e quando um processo deixa o grupo ele não poderá mais receber mensagens daquele grupo.

Quando muitas máquinas, ou processos do grupo desligam e o grupo não consegue funcionar da maneira correta, algum protocolo de reconstrução do grupo será necessário. Porém e se dois ou três processos de reconstrução forem inicializados ao mesmo tempo, este protocolo deverá tratar este tipo de problema.

Mascaramento de falha e replicação

Os grupos de processos são uma das formas de se construir um sistema tolerante a falha. A construção de um grupo de processos idênticos habilita o nosso sistema a mascarar uma ou mais falhas de processamento daquele grupo. A replicação de um único processo, que é vulnerável, por um grupo de processos, tolerante a falha. Como fazer esta replicação foi explicado no post anterior de consistência e replicação.

Um ponto importante na utilização de grupos para tolerar falhas em um sistema distribuído é a quantidade de replicação necessária. Um sistema é denominado X tolerante a falha, caso ele suporte falha em X componentes e mesmo assim continue funcionando corretamente. Quando os processos deste sistema falham silenciosamente, então termos X +1 componente é suficiente para prover um sistema com X de tolerância a falha.

Entretanto caso os processos deste sistema apresentem falhas Bizantinas e continuam enviando mensagens, mesmo quando eles estão falhando, o mínimo de 2X+1 de componentes é necessário para atingir um sistema com X de tolerância a falha.

Acordo em sistemas falhos

Organizar processos replicados em grupos ajudam a aumentar a tolerância a falha. Como explicado acima, se um cliente baseia suas decisões em um sistema de voto, podemos tolerar que X processos de um número 2x+1 processos apresentem falhas, que mesmo assim o sistema continuará funcionando corretamente.

Geralmente os problemas tornam-se mais intrínsecos quando o grupo de processos necessita cumprir um acordo, ou realizar uma função, por exemplo decidir se realiza um commit, ou não, de uma transação, eleger um coordenador, divisão de tarefas entre grupos, sincronização, etc
Quando o sistema está funcionando corretamente, é fácil atingir estes objetivos, porém quando um ou mais componentes falham, ai as coisas ficam complicadas.

O objetivo dos algorítimos distribuídos de acordo é fazer com que todos os componentes, que não estejam falhando, cheguem a um consenso. Porém este é um problema muito complicado já que diferentes soluções podem ser adotadas, isso quando elas existem. Estas soluções podem ser divididas em:

1. Sistemas síncronos versus sistemas assíncronos. Um sistema pode ser considerado síncrono quando existe um relógio controlando os processos deste sistema, e a cada passo deste relógio, todos os processos realizam uma operação. Um sistema que não é síncrono é conhecido como assíncrono
2. O tempo que leva a comunicação é limitado ou não. O tempo da comunicação é limitado quando há uma garantia que todas as mensagens do sistema são entregues com um tempo máximo global.
3. Entrega de mensagens é ordenada ou não. Nestes sistemas as mensagens são entregues na mesma ordem em que elas foram enviadas, ou nos casos em que não há esta garantia.
4. Transmissão das mensagens é feita através de unicasting ou multicasting.

Um tipo de algoritmo de acordo é conhecido como Problema de acordo Bizantino, nome que lhe foi dado devido a história das inúmeras guerras que aconteceram no império Bizantino e dos respectivos acordos que eram feitos entre os exércitos nestas guerras.

Este algoritmo funciona em um conjunto de processos, como exemplo usaremos um conjunto de 4 processos, cada um dos processos envia uma mensagem de resposta de processamento para os outros processos que estão dentro do conjunto de processos.

Cada um dos processos irá armazenar os valores recebidos em um vetor, o qual será enviado a todos os outros processos deste conjunto. Cada processo irá receber três vetores dos outros processos do conjunto. Caso um processo esteja falhando, ele pode enviar mensagens aleatórias aos outros processos do conjunto, e ao final, somando-se os elementos de cada vetor, quando houver maioria aquele valor será considerado correto. Caso nenhum dos valores tenha maioria de presença nos vetores o resultado será marcado como Desconhecido.

Este protocolo deve ser utilizado em conjuntos com mais de 4 processos, já que neste caso cada processo receberá três respostas, caso haja somente 3 processos no conjunto, ao receber apenas 2 respostas, estando os valores delas diferentes, fica impossível detectar qual é o valor correto.

Este protocolo não funciona corretamente em casos de sistemas onde as mensagens não possuem garantia de entrega. Já que isso gera um grande problema para detectar-se se a mensagem falhou, ou se o processo está demorando para executar a mensagem,

Deteção de falha

A detecção de uma falha é um ponto muito importante para podermos mascarar o acontecimento dela. Em um grupo de processos, eles devem possuir a habilidade de detectar quais processos ainda fazem parte daquele grupo e isto é realizado através da monitorização das falhas.
Existem duas maneiras de se detectar a falha de um processo, na primeira delas o processo ativo envia uma mensagem de "Você ainda está vivo" para os outros processos, e através da resposta a esta mensagem é possível determinarmos quem ainda está vivo ou não. Ou ficar aguardando passivamente mensagens dos outros processos. Este segundo caso faz sentido apenas quando há muita comunicação entre os processos.
Um dos pontos cruciais de se detectar uma falha, é estabelecer um mecanismo de timeout. Existem dois grandes problemas de se detectar uma falha através de timeout, primeiro devido a problemas de comunicação entre redes, nem sempre quando uma resposta não chega, é sinal que ela não foi dada, ou seja a geração de falsos positivos é bem alta. E caso este falso positivo seja responsável por retirar um processo saudável, da lista de processos disponíveis, fica claro que existe algo de errado.
Um outro problema é que os timeouts são muito básicos, é difícil confiar em um sistema de detecção de falha que considere um processo falho, quando ele apenas deixa de responder uma mensagem.
Existem muitos fatores que devem ser levados em conta, quando estamos desenvolvendo um sistema de deteção de falha. Pode-se considerar a utilização do protocolo de fofoca, onde cada processo do sistema envia regularmente mensagens de, estou vivo e rodando, para seus vizinhos.
A utilização do protocolo de fofoca, para envio de mensagens de estou vivo irá eventualmente atingir todos os pontos do sistema, e cada um deles terá um controle de quais processos estão vivos, ou não. Um membro, o qual esta informação for muito antiga, será presumidamente considerado como falho.
Uma funcionalidade importante destes sistemas é conseguir diferenciar uma falha de comunicação, da rede, de uma falha de processamento do nó e uma as formas de resolver este problema é não deixar que apenas um processo decida se um outro processo esta falhando ou não. Neste caso ao notar que um processo não está mais respondendo aquele nó deve perguntar aos seus vizinhos se eles conseguem se comunicar com processo presumidamente falho.

Comunicação confiável entre cliente e servidor

Muitos casos de tolerância a falha em sistemas distribuídos se concentram nos processos falhos, porém também precisamos considerar as falhas de comunicação. O canal de comunicação pode apresentar falhas de queda, omissão, tempo e falhas arbitrárias. Para construir um canal de comunicação confiável o foco é omitir falhas de colisão e omissão.

Comunicação ponto a ponto

A comunicação ponto a ponto confiável é estabelecida através de protocolos de transporte confiáveis, como o TCP, que omite falhas de omissão, que ocorrem por causa das mensagens perdidas, pelo uso de confirmações e retransmissões.
Falhas de colisão não podem ser mascaradas. Estas falhas acontecem quando uma conexão TCP quebra abruptamente e nenhuma mensagem podem ser transmitidas através do canal. Na maioria das vezes o cliente é informado que existe uma colisão no canal através do disparo de uma exceção. A única forma de mascarar este tipo de falha é deixar o sistema tentar se reconectar automaticamente, o que pode ser feito através do reenvio de uma requisição de conexão.

Semântica RPC na presença de falhas

Nesta seção vamos analisar a comunicação cliente-servidor quando elas utilizam um tipo de comunicação como o RPC. O objetivo de uma RPC é esconder a operação de comunicação fazendo com que as chamadas RPC sejam realizadas como se fossem chamadas locais. E isso funciona muito bem enquanto o cliente e o servidor funcionem corretamente. O problema acontece quando os erros acontecem, nestes casos fica difícil mascarar os problemas como se eles fossem chamadas locais.
Vamos dividir as falhas RPCs em 5 diferentes classes de erros

1. O cliente não consegue localizar o servidor
2. A mensagem é perdida entre o cliente e o servidor
3. O servidor quebra após receber a requisição
4. A mensagem de resposta do servidor ao cliente é perdida
5. O cliente quebra após enviar a requisição

A resolução de cada um destes problemas deverá ser realizada de uma maneira diferente

O cliente não consegue localizar o servidor

Este erro pode acontecer quando, por exemplo, todos os servidores estão desligados, quando o cliente está esperando uma certa versão dos serviços que já não está mais disponível. Neste caso ao tentar se conectar com este servidor uma falha acontecerá. Este tipo de erro é usado para proteger o cliente de tentar usar uma versão errada do serviço, que contenha parâmetros diferentes dos quais o cliente está preparado para lidar. O grande problema é como atuar quando este tipo de erro acontece.
Uma solução possível é fazer com que este erro dispare uma exceção ou sinais. Esta solução não pode ser utilizada em todas as linguagens, já que em algumas delas não é possível disparar uma exceção ou um sinal. Um outro problema é que ter que escrever exceções para este tipo de erro vai contra o objetivo de ser transparente quanto a execução remota deste tipo de chamada.

Mensagem de requisição perdida

Dos tipos de erro de RPC este é o mais fácil de ser tratado, basta iniciar um contador, assim que a mensagem é enviada. Se o tempo do contador ultrapassar um limite estabelecido antes que uma resposta chegue, a mensagem será reenviada. Caso a mensagem tenha sido realmente perdida o servidor não vai conseguir identificar nenhuma diferença entre a mensagem original e a cópia e tudo funcionará corretamente. A não ser que muitas mensagens sejam perdidas e o cliente desiste achando que o servidor quebrou, o que nos leva a um erro de servidor não encontrado.

Servidor quebrou

A sequência normal de eventos é a mensagem chega, é processada e uma resposta é enviada. Existem dois caminhos possíveis de falha quando o servidor quebra, na primeira delas, a mensagem é recebida o servidor processa ela e logo após ele quebra, não enviando nenhuma resposta. Na segunda, o servidor recebe a mensagem e quebra, antes mesmo de processar a mensagem.
A parte mais complicada de se tratar este tipo de erro é que atitudes diferentes devem ser tomadas para solucionar estes dois tipos de problema. No primeiro caso o sistema deve enviar um relatório de erro de volta ao cliente, já no segundo uma simples retransmissão resolve o problema.
Existem três tipos de filosofias para estes problemas, na primeira os processos ficam esperando o servidor ser reinicializado e tentam realizar a operação novamente. A mensagem será retransmitida até que o servidor responda. Esta técnica é chamada de pelo menos uma vez, já que neste caso há uma garantia que o RPC foi executado pelo menos uma vez, porém possivelmente mais de uma.
No segundo tipo de filosofia, ele desiste de executar a requisição e emite uma mensagem de erro. Esta solução é chamada de no máximo uma vez, já que só uma requisição será enviada.
A terceira filosofia não garante nada, quando um servidor quebra, os clientes não recebem nenhuma ajuda ou pista sobre o que aconteceu. A chamada de RPC pode ter sido processada nenhuma ou muitas vezes.
Nenhuma destas três filosofias é muito atrativa. Imagine uma operação remota para imprimir algum texto, e que o servidor de impressão envie uma mensagem de confirmação para o cliente, quando o texto é impresso. Neste caso, quando o servidor recebe uma instrução de impressão ele envia uma mensagem de confirmação de recebimento da instrução para o cliente. Existem duas estratégias que o servidor pode seguir, ele pode enviar uma mensagem de que o texto foi impresso antes de mandar a instrução de impressão para a impressora, ou após o texto ter sido impresso.
Imagine que o servidor pare de funcionar e logo depois se recupere. Ele envia uma mensagem para os clientes dizendo que o servidor caiu e voltou. O grande problema é que os clientes não sabem se a sua requisição de impressão foi recebida ou não.
O cliente pode seguir quatro estratégias. Primeiro o cliente pode decidir não reenviar a requisição, assumindo o risco do texto nunca ser impresso. Segundo o cliente pode decidir sempre reenviar a requisição de impressão, correndo o risco de o texto ser impresso duas vezes. Terceira ele pode decidir reenviar a requisição somente se ele não receber a mensagem de confirmação de recebimento da instrução de impressão pelo servidor, neste caso o cliente estão levando em conta que o servidor caiu antes que a mensagem da instrução de impressão tenha sido recebida. A quarta estratégia é reenviar a requisição somente quando ele receba uma mensagem de confirmação de recebimento da mensagem de solicitação de impressão pelo servidor.
Contando com duas estratégias para os servidores e quatro para os clientes, temos oito possíveis caminhos, mas nenhum deles será satisfatório.
Resumindo a possibilidade do servidor cair, muda radicalmente a natureza de uma chamada RPC e claramente a distingue de um sistema simples.

Perda de mensagens de resposta

A perda de mensagens de resposta, também pode ser difícil de lidar. A solução mais óbvia é configurar um temporizador e caso nenhuma mensagem de resposta chegue após este temporizador estourar um tempo limite, configurado no sistema operacional, ele pode reenviar esta mensagem. O problema desta solução é que é impossível saber se a mensagem se perdeu, ou se o servidor está lento.

Alguns tipos de operação, como as mensagens de busca em banco de dados, podem ser repetidas infinitamente, sem causar qualquer problema de consistência. Este tipo de requisição é considerada idempotente.

Porém uma mensagem de atualização, como uma transferência de dinheiro entre duas contas bancárias. Se esta requisição for processada, porém a mensagem de resposta se perder, o cliente não saberá e vai retransmitir a mensagem para o servidor. O servidor do banco irá interpretar isso como uma nova requisição e realizará a transferência duas vezes.

Uma maneira de se tentar resolver este problema é tentar estruturar todas as requisições de uma maneira idempotente. Porém nem sempre isto é possível, este caso de transferência bancária é um exemplo clássico, por isso precisamos de um outro método para resolver este problema. A segunda forma de resolvermos este problema é inserir na mensagem um número sequencial e fazendo com que o servidor cuide deste número sequencial de cada cliente. Com isso é possível determinar se uma mensagem já foi processada ou se ela esta sendo retransmitida.

Neste caso o servidor deverá administrar cada cliente e também não fica claro por quanto tempo deveremos manter estes dados armazenados.

A terceira forma de se resolver este problema é manter um bit no cabeçalho da mensagem marcando-a como retransmitida.

Queda do cliente

O item final a ser analisado nesta lista de falhas acontece quando o cliente envia uma requisição ao servidor e antes que o servidor responda, o cliente sofre uma pane e desliga. Com isso temos uma requisição sendo processada no servidor, sem ter nenhum cliente aguardando a sua resposta. O que resulta em um processo órfão.

Estes processos órfãos podem causar uma série de problemas na operação normal do sistema. Desde um desperdício de ciclos de processamento, um travamento de arquivos ou ocupar recursos vitais do servidor. Finalmente se o cliente reiniciar e a requisição for realizada novamente mas a resposta do órfão chega logo após este reinicio, neste caso podemos ter uma confusão.

Existem quatro maneiras de se tratar o problema dos processos órfãos. Na primeira delas, antes de realizar uma chamada RPC o cliente armazena dados dela em um log que sobreviva as interrupções da máquina. Ao reiniciar este log será checado e os órfãos serão exterminados.

A desvantagem deste esquema é a escrita no log para cada mensagem RPC enviada. Além de, em alguns casos, este extermínio não funcionará, já que os processos órfãos também podem criar outros processos, que seriam impossíveis de serem detectados. Finalmente se houver um problema de rede será impossível matar estes processos órfãos.

Na segunda solução, chamada de reincarnação, todos estes problemas poderão ser resolvidos, sem ter que escrever no disco. Ela funciona dividindo o tempo em épocas e a cada reinício do cliente, ele enviará uma mensagem para todas as máquinas declarando o início de uma nova época. Quando este tipo de mensagem chega em um servidor, todos os processos referentes a épocas passadas são exterminados. Neste caso, havendo um problema de rede alguns processos podem não ser exterminados, mas as respostas destes processos carregam um número de uma época inválida e elas serão descartadas.

A terceira solução é uma variação da segunda, também chamada de reincarnação gentil. Quando uma mensagem de época chega, ela tentará localizar todos os processos remotos que estão rodando localmente, e quando acha, ela faz o possível para achar os seus donos. Somente quando os donos não podem ser encontrados é que os processos serão eliminados.

Para finalizar, a quarta solução é chamada de expiração, onde para cada chamada RPC será informado um tempo de vida T para se completar o processamento. Se o processo não conseguir terminar no tempo estimado, ele poderá pedir uma prorrogação deste tempo de vida. Do outro lado, o cliente esperará um tempo T antes de reiniciar o serviço, desta forma é possível saber que todos os órfãos foram eliminados. O problema aqui é encontrar um tempo T correto em face dos diversos tipos de RPC existentes.

Na prática todos estes quatro métodos são indesejáveis, já que eliminar um órfão pode ter graves consequencias, uma vez que eles podem ter obtido travas nos arquivos de dados do sistema e ao serem eliminados estas travas podem permanecer ativas, gerando uma trava infinita.

Apresentação

Exercícios Sistemas distribuídos (nome, sincronização, consistência, tolerância a falha e RPC)

1. Exemplifique e explique uma maneira de nomeação a ser utilizada em redes pequenas, uma a ser utilizada em sistemas de arquivos e uma de implementação simples.
2. Explique qual é a importância da sincronização em sistemas distribuídos
3. Qual tipo de algoritmo de sincronização relógio é o indicado para ser utilizado em sistema que necessite a total ordenação das suas requisições? Explique o porque
4. Defina e compare dois tipos de algoritmos de exclusão mutua.
5. Descreva a importancia e a aplicação de um algoritmo de eleição em um sistema distribuído
6. Enumere motivos da importancia da replicação em um sistema distribuído
7. Qual é a importância da administração correta de uma réplica no desempenho de um sistema distribuído
8. Compare a implementação de um protocolo de consistencia baseado no cliente, com um baseado no servidor.
9. Enumere e descreva os conceitos básicos de tolerância a falha em um sistema distribuído.
10. Explique quais são os possíveis problemas a serem enfrentados em um sistema de RPC distribuído?

Consistência e Replicação

Consistência e Replicação

Para que um sistema seja escalável, não basta distribuir ele em várias máquinas e pronto, problema resolvido. Alguns serviços, como os de armazenamento de dados, necessitam de algum tipo de replicação e isso gera um trabalho para manter os dados consistentes. Ou seja assegurar que estes dados são os mesmos em todas as cópias, o que não é uma tarefa fácil.

A replicação de um banco de dados é realizada para aumentar a capacidade do sistema de responder a um grande volume de requisições e para aumentar a tolerância a falha. Porém assim que uma atualização é realizada em um ponto do sistema, ou uma instância do seu banco, é importante que esta alteração seja replicada para todas as instâncias, para que com isso os dados mantenham-se consistentes.

Em alguns casos de uso, a consistência dos dados não é uma requisição, como nas redes sociais, onde um post de um determinado usuário não precisa ser visualizado por todos seus amigos, assim que ele envia esta requisição, e nem na ordem em que os posts foram criados. Mas em uma grande parte dos sistemas, como no caso de instituições financeiras, os dados precisam ser consistentes e/ou ordenados. Não faz sentido se um depósito é realizado na sua conta bancária em Porto Alegre, e você não consiga ver este depósito realizado, ao tirar um extrato em Salvador.

Consistência, disponibilidade e processamento paralelo, formam o teorema de CAP nos diz que é impossível termos consistência, disponibilidade e processamento paralelo em um sistema de armazenamento de dados ao mesmo tempo, para isso devemos escolher apenas duas destas características.

Motivos para realizar uma replicação

Um dos principais motivos para se realizar uma replicação dos dados é por causa da confiabilidade do sistema, pois caso o seu sistema de armazenamento de dados esteja rodando em apenas uma máquina, e esta máquina falhe, aqui como falha, podemos contar como falha de hardware, eletricidade, rede, ou mesmo software, o seu sistema inteiro estará comprometido.

Performance também aparece dentre as principais razões para a realização da replicação dos dados. Uma replicação de performance é importante quando o sistema distribuído necessita escalar em números e/ou geolocalização. A replicação por performance ocorre quando existem muitos processos tentando acessar dados de apenas uma máquina, com a replicação é possível que o trabalho desta máquina seja dividido entre várias maquinas aumentando a performance do sistema.

Em uma replicação por área geográfica acontece quando os clientes de um determinado serviço estão espalhados em diversas áreas e colocar uma cópia dos servidores perto dos seus clientes diminuirá o tempo gasto para que eles acessem os dados.

O grande ponto fraco da replicação é a quebra da consistência dos dados, quando uma cópia recebe uma atualização, ela ficará diferente das outras cópias, com isto esta atualização deverá ser replicada em todas as cópias para manter a consistência dos dados.

Replicação como uma solução de escalabilidade

Tanto a replicação como o cache são amplamente utilizados para se resolver os problemas de escalabilidade. A escalabilidade de um sistema geralmente aparece por causa de problemas de performance, quando o seu serviço não está respondendo de uma maneira aceitável. Colocar cópias dos dados em localidades mais próximas aos seus clientes é uma solução utilizada para aumentar a sua performance, pois os dados levarão menos tempo para ir de um ponto ao outro.

Manter várias réplicas de dados consistentes pode gerar um problema de performance. Tem-se que uma coleção de dados está consistente quando todas as cópias possuem os mesmos valores, o que significa que a leitura de um dado em qualquer uma das cópias deverá sempre retornar o mesmo resultado. Para manter-se consistente, assim que uma atualização é realizada, ela deverá ser propagada para todas as réplicas antes que qualquer outra operação de leitura.

Este tipo de consistência muitas vezes também é referenciado como replicação síncrona, neste caso a cada atualização todas as réplicas serão atualizadas em uma operação atômica, ou seja quando uma atualização é realizada ela só se completará quando todas as réplicas forem atualizadas. Completar uma operação síncrona em uma rede com muitas máquinas, que muitas vezes estão espalhadas em várias redes diferentes em uma rede de larga escala é uma operação bem complicada, principalmente quando esta atualização precise completar-se rapidamente.

Manter estas cópias atualizadas é um problema que, muitas vezes, necessita de muita largura de banda da rede. Considerando um processo P1 que acessa uma réplica R1 X vezes. Levando-se em conta que esta réplica é atualizada U vezes, caso X seja muito menor que U, ou seja a replica recebe muito mais atualizações do que leituras, o que gera um desperdício de banda e comunicação entre estas máquinas. Colocar uma réplica R1 próximo ao processo P1, ou aplicar uma estratégia de atualização diferente não serão a melhor maneira de resolver este problema.

Isto gera um problema interessante, por um lado temos que replicar, fazer cache aumenta consideravelmente a performance do nosso dispositivo de armazenamento, porem manter todas as cópias sincronizadas requer uma sincronização global, o que é bem custoso em termos de performance.

Muitas vezes, para ganhar performance, deve-se sacrificar a consistência dos dados. Em alguns casos é possível relaxar um pouco as regras de consistência, evitando que uma operação de update atômica instantânea seja necessária, neste caso nem sempre todas as réplicas do sistema terão os mesmos dados.

Modelo de consistência baseado em dados.

Um modelo de consistência é um contrato entre os processos e o local de armazenamento de dados. O qual pode ser um banco de dados, um sistema de armazenamento de arquivos ou um sistema de memória compartilhada. Este local de armazenamento de dados pode estar espalhado por diversas máquinas, e cada processo que está acessando dados pode ter uma cópia local dos dados que ele está acessando.

Uma operação é classificada de duas maneiras, como escrita quando qualquer alteração tenha sido realizada nos dados ou como leitura em qualquer outro tipo de operação.

A falta de um modelo de relógio único e global, faz com que seja muito difícil estabelecermos qual foi o último processo de escrita realizado.

Um modelo de consistência é um contrato entre os locais de armazenamento de dados e os processos, e nele são estabelecidas as regras, que se obedecidas, garantem o funcionamento correto deste armazenamento de dados.

Consistência contínua

Pelo o que vimos até agora, a replicação de dados implica em uma perda de consistência que não poderão ser resolvidas eficientemente. Porém o quanto de consistência uma aplicação pode suportar depende muito de como e do que ela trata.

Existem três maneiras independentes de definição de inconsistência, o de valores numéricos, o de staleness e o de ordenação de operações de atualização. Estes desvios são conhecidos como intervalo de consistência contínua.

Medir inconsistência usando o desvio numérico, faz sentido para aplicações que onde os dados possuem uma semântica numérica. Por exemplo ao fazer um aplicativo de compra e venda de ações, podemos especificar que duas cópias do banco de dados, um valor de uma determinada ação não pode desviar em mais de 2 centavos, o que é considerado um desvio numérico absoluto. Uma alternativa a isto é definido como desvio numérico relativo, neste caso podemos definir que uma cópia não pode diferir de outra em mais de 0.7%.

Inconsistência de desvio numérico também pode ser medido em relação ao número de operações de foram realizadas em uma determinada cópia, mas ainda não foram aplicadas as outras. Por exemplo em um aplicativo que realiza operações em batch, por exemplo um sistema que utiliza cache e o cache ainda não foi atualizado pelas operações realizadas no processo de batch.

Desvios staleness são relacionados a data da última atualização de uma réplica. Em alguns casos, os aplicativos podem mostrar dados desatualizados, como em aplicativos de previsão do tempo, onde muitas vezes podemos mostrar dados de previsão com algumas horas de atraso, sem prejudicar o comportamento do aplicativo.

Desvios de ordem da atualização dos dados podem ser suportados por alguns tipos de aplicativos. Por exemplo uma atualização pode ser aplicada temporariamente a uma cópia local, a qual fica esperando a confirmação de todas as réplicas. E como consequência alguns casos podemos ter que desfazer uma atualização e ela será aplicada de uma maneira diferente antes de se tornar permanente. Deste tipo de operação surgiu a ordenação consistente de operações onde vamos estudar a consistência sequencial e a consistência casual.

Consistência sequencial

A consistência sequencial é um importante modelo de consistência centralizado em dados. Neste modelo, quando processos rodam concorrentemente, muitas vezes em máquinas separadas, qualquer sequência de operações de leitura e escrita é válida quando todos os processos recebem os dados na mesma sequência. Note que aqui não há uma definição de tempo, pois um atraso na propagação dos dados é completamente aceitável, desde que os dados sejam propagados na mesma sequência.

Consistência Casual

O modelo de consistência casual é um relaxamento das regras da consistência sequencial. Neste modelo operações de escrita que são potencialmente relacionados pela casualidade, deverão ser vistos por todos os processos na mesma ordem.

Na consistência casual, quando ocorrem escritas concorrentes, ou seja, várias Threads executando operações de escrita em diversas cópias do banco ao mesmo tempo, podem ser vistas em uma ordem diferente em cada uma das réplicas.

Operações relacionadas pela casualidade são aquelas onde uma escrita em um certo dado X, é referente a um processamento no valor anterior dele. Por exemplo a atualização de um valor de estoque de um produto, estas atualizações acontecem com uma computação (decremento ou acréscimo da quantidade de produtos) sobre um valor previamente armazenado na base. Em um sistema de consistência casual, estas operações devem ser realizadas na mesma ordem em todo o sistema de armazenamento, as operações não casuais, poderão ser executadas em ordens diferentes em cada uma das cópias.

Modelo de consistência centralizados no cliente

Os modelos de consistência apresentados até agora tratam da consistência de todo o sistema, porém pode-se assumir que processos concorrentes podem alterar dados simultaneamente e para prover este tipo de atualização, novos modelos foram propostos.

Consistência eventual

O modelo de consistência eventual são aqueles onde poucas atualizações ocorrem e quando elas acontecem elas não são propagadas instantaneamente. Este modelo necessita que eventualmente todas as atualizações sejam propagadas para todas as cópias. Conflitos de escrita escrita são relativamente fáceis de se resolver já que poucos processos realizam escrita.

São exemplos de consistência eventual o sistema de DNS, os sistemas de cacheamento de sites da internet, como o proxy, e base de dados onde a maioria dos processos é de leitura.

O sistema de consistência eventual funciona muito bem quando os clientes sempre acessam uma mesma réplica, porém quando múltiplas réplicas são acessadas em um curto período de tempo, os problemas aparecem. Imagine um aplicativo de celular que se conecta a uma réplica e faz várias atualizações. Depois de um curto período de tempo este aplicativo se reconecta ao serviço, agora em uma outra réplica, ou por causa de troca do tipo de acesso wifi, 3g, etc, ou pela própria localidade do celular. Ao se conectar a uma réplica diferente as atualizações inseridas anteriormente podem não estar disponíveis para o aplicativo, fazendo com que o usuário perceba a inconsistência do armazenamento.

Leitura Monotônica

O sistema de leitura monotônica foi o primeiro modelo de consistência baseado no cliente. Este sistema é baseado na condição de que quando um processo lê um dado x, qualquer leitura sucessiva do x por aquele processo sempre retornará o mesmo valor, ou um valor mais atualizado.

Considere um sistema de email distribuído, onde a operação de leitura não afeta, altera, os dados da caixa de entrada. Imagine que um cliente acesse o seu email de São Paulo, e depois de algum tempo do Rio de Janeiro, neste acesso a leitura monotônica garante que todas as mensagens que foram mostradas em São Paulo, também serão mostradas no acesso realizado do Rio de Janeiro.

Escrita Monotônica

Em muitos casos é importante que as operações de escrita sejam propagadas na ordem correta para todas as réplicas do sistema de armazenamento de dados. Neste sistema a escrita é controlada de maneira que nenhuma operação de escrita em um dado elemento x ocorra fora de ordem. Nem que para isso o processo de escrita tenha que aguardar um outro processo de escrita completar. Note que este sistema consideramos que uma operação de escrita é controlada pelo processo e não pelo sistema inteiro.

Leitura das suas escritas

Neste modelo uma atualização de dados, realizadas por um processo, sempre será vista por uma leitura daquele processo. Ou seja, uma operação de escrita sempre deve ser completada antes de uma chamada de leitura do mesmo processo, não importa onde esta chamada de leitura tenha sido realizada.

A falta da leitura das suas escritas pode ser notada quando estamos editando um documento na web e fazemos uma pré visualização daquele documento, muitas vezes no navegador cacheia esta página e quando tentamos visualizar outras modificações, realizadas após o cacheamento da página, o navegador mostra a versão antiga. O modelo de leitura das suas escritas garante que este comportamento não acontecerá.

Escrita após a leitura

Neste modelo de consistência focado no cliente, toda operação de atualização dos dados será realizado em uma cópia do valor da última leitura realizada pelo processo. Por exemplo, imagine que um processo A leu uma determinada linha de um container de dados da tabela Usuário. Qualquer atualização realizada na tabela de usuário será realizada sobre o último valor lido da tabela de usuários por aquele processo.

Administração de réplica

A escolha de quando, onde e por quem as réplicas devem ser colocadas/administradas é uma decisão importante a ser tomada quando estamos planejando sistemas distribuídos. Esta decisão deve ser dividida em dois pontos, o primeiro onde os servidores serão posicionados, onde devemos nos preocupar com a melhor localidade e infra estrutura dos servidores, que armazenarão parte dos nossos dados. E a outra é em quais servidores colocar cada pedaço dos dados. É claro que primeiro deve-se estabelecer a localização dos servidores, para depois tomar a decisão de qual conteúdo cada um deles armazenará.

Localização dos servidores de réplica

Este é mais um problema de administração e comercial, do que um problema de otimização. Entretanto monitoramento da rede e analise dos clientes é um fator importante para ajudar a tomar decisões.

Existem várias formas de se determinar a melhor localização de um servidor, porém muitas delas são baseadas em cálculos heurísticos. As distâncias entre as máquinas podem ser baseadas em largura de banda e latência, e uma das soluções é selecionar o servidor onde a distância média entre ele e os seus clientes seja menor.

O grande problema destes algoritmos são que eles são computacionalmente caros, a complexidade deles é O(N^2) ou seja, o crescimento dos nós N da sua rede, provoca um aumento de tempo computacional deste algoritmo exponencialmente.

Um algoritmo de localização de servidores de réplica foi desenvolvido como um método onde as réplicas podem ser facilmente identificadas. A ideia deste método é identificar os maiores clusters de uma rede e determinar um nó destes clusters como uma réplica. Para identificar estes clusters, a rede é dividida em células, e as células mais densas são escolhidas para se colocar os servidores de réplica.

A escolha do tamanho da célula é um fator muito importante neste algoritmo, uma vez que ao escolhermos uma célula muito pequena, ela terá muitos nós e muitas réplicas por região, e ao escolher uma célula muito grande, ela terá uma réplica para mais de uma região. Para determinar o tamanho ideal das células podemos utilizar um algoritmo que computa a distância entre os nós através do tempo que eles demoram para se comunicar. Experimentos mostraram que colocar réplicas nos 20 melhores lugares para uma rede de 64.000 nós é aproximadamente 50.000 vezes mais rápido, com isso este tipo de replicação pode ser feito em tempo real.

Réplica permanente

Réplicas permanentes são as réplicas geralmente imutáveis, que ficam permanentemente disponíveis e na maioria dos casos o número das réplicas permanentes são bem pequenos.

Considerando um exemplo de um website, onde os seus arquivos são distribuídos por um número limitado de servidores web. Existem duas maneiras de se distribuir estas réplicas, na primeira delas os dados são copiados em um número limitado de servidores dentro de uma mesma localização e as requisições serão distribuídas por um roteador round-robin.

A segunda maneira de se distribuir um website é chamada de espelhamento. Neste caso os dados do site é copiado por um número limitado de servidores espalhados pela internet. Na maioria dos casos o cliente escolherá uma das cópias, geralmente baseando-se em proximidade física, para acessá-la.

Réplicas inicializadas pelo servidor

Diferente das réplicas permanentes, as réplicas inicializadas pelos servidores são réplicas mirando a performance as quais são criadas pelo administrador do armazenamento de dados. Considerando o exemplo de um website, as suas réplicas podem estar todas em um datacenter localizado em São Paulo e isto pode ser, na maioria das vezes, suficiente para termos uma performance aceitável. Porém, por algum motivo, podemos ter um grande número de requisições de uma outra localidade, como Curitiba, e neste caso o servidor pode escolher colocar cópias dos arquivos físicos do site, em um datacenter de Curitiba, afim de reduzir o tempo gasto por estas requisições para pegar este tipo de arquivo.

Réplica inicializada pelo cliente

Estas réplicas, geralmente conhecidas como cache de cliente, são cópias temporárias de alguns arquivos, utilizadas para armazenar dados que foram baixados recentemente.

Por exemplo, quando entramos em um website, algumas informações podem ser armazenadas localmente, para evitar tráfego no futuro, como a imagem do logotipo daquele site. Tendo ela em cache local, ao entrarmos a próxima vez, não será necessário baixar novamente esta imagem.

O grande problema deste tipo de armazenamento é manter as cópias atualizadas, por isso este tipo de cache deve ter um determinado tempo de vida, para prevenir que as informações fiquem desatualizadas por muito tempo.

Replicação de Conteúdo

A administração de uma réplica deve tratar da propagação do conteúdo atualizado aos servidores de réplica.

Estado vs Operações

Um ponto importante a ser analisado é o que realmente deverá ser propagado e basicamente existem três opções.

1. Propagar apenas uma notificação de conteúdo
2. Transferir dados de uma cópia para outra
3. Propagar as operações de atualização para as outras cópias

Propagar a notificação de conteúdo é o que os protocolos de invalidação realizam. Nestes protocolos as cópias recebem a informação de que os dados que eles contém estão desatualizados. Estas notificações podem conter especificações de quais partes dos dados estão desatualizadas. Quando uma informação é requisitada em uma réplica ela primeiro checa se os dados que ela contém estão atualizados, caso eles não estejam antes de enviar uma resposta a réplica cuidará de atualizar os seus dados.

A grande vantagem destes protocolos é a baixa utilização da rede, já que a única informação que deverá ser propagada é quais dados não estão mais válidos.

Considerando um caso onde muitas atualizações são realizadas e poucas leituras são feitas. Considerando que todas as atualizações são replicadas instantaneamente. Neste caso, podemos ter mais de uma atualização entre duas operações de leitura, ou seja uma das atualizações foi enviada sem ser lida, gerando um desperdício de rede e processamento.

Transferir os dados de atualização de uma cópia para outra é a segunda alternativa e ela é bem útil quando a taxa de leitura é muito maior que a taxa de escrita, pois neste caso a chance da propagação de uma atualização ser inútil é bem pequena.

A terceira alternativa é não transferir nenhum dado de atualização, porém dizer para as réplicas quais operações de atualização ela deve realizar, enviando apenas os parâmetros da alteração. Este parâmetro também é conhecido como replicação ativa. O grande beneficio desta alternativa é que as atualizações podem ser replicadas com o mínimo uso da rede, porém estas operações de atualização podem ser bem complexas gerando uma dificuldade de administração das réplicas.

Protocolo de recebimento vs envio

Um outro problema de design é como as atualizações são enviadas ou requisitadas, em um protocolo baseado em atualizações enviadas, ou também conhecidas como protocolos de servidor. As atualizações são enviadas para as réplicas sem que elas peçam para serem atualizadas.

O protocolo de envio de atualizações são utilizados quando um alto grau de consistência é necessário, já que as atualizações são propagadas pelas réplicas sem a necessidade de consulta.

Uma das desvantagens do protocolo de envio é que ele deve conhecer todos os seus clientes, já que é o servidor que dispara as atualizações e como já vimos anteriormente o armazenamento da lista de todos os pontos de uma rede não é simples de se fazer.

Já um protocolo de recebimento, o cliente enviará uma mensagem requisitando as últimas atualizações de uma determinada parte do armazenamento.

Unicast vs multicast

Relacionado ao protocolo de envio e recebimento temos a decisão de como será realizada a propagação das mensagens.

Com a propagação via unicast, quando um servidor deve enviar uma mensagem para múltiplos servidores, ela será enviada uma mensagem para cada máquina, multiplicando-se o número de mensagens necessário para realizar a replicação.

No caso do multicast a rede cuidará de dissipar a mensagem a todos os recebedores. Com isso ele se integra muito bem com o protocolo de envio de mensagem.

Protocolo de Consistência

Até agora foram mostrados modelos de consistência, a partir deste ponto serã mostradas as implementações destes modelos, focando nos protocolos de consistência. Um protocolo de consistência descreve a implementação de um modelo de consistência.

Consistência contínua

Para atingir a consistência contínua, explicada mais acima, alguns protocolos tiveram que ser criados. Estes protocolos serão descritos a seguir.

Desvio numérico limitado

Considerando nas escritas de um determinado item de dados X. Cada operação de escrita no dado X, terá um peso, que será determinado pelo valor numérico de X, esta operação será submetida a uma das cópias, e neste caso este servidor será considerado a origem da operação de escrita. Esta operação de escrita será propagada e a utilização de um protocolo de epidemia vai espalhar estas informações rapidamente. 

Todas as operações de escrita que foram realizadas são armazenadas em um log em cada réplica. O objetivo deste protocolo é manter o valor de cada réplica, em um determinado tempo não deve desviar mais que um determinado delta (valor do desvio numérico). Quando um servidor X nota que um outro servidor Y não esteja realizando as operações de escrita da maneira correta (valor da diferença é maior que o delta) ele submete a sua própria lista de alterações para serem realizadas no servidor Y. Desta maneira o sistema consegue manter todos os valores dentro de um determinado delta.

Valor de desvio staleness

Existem muitas formas de se manter o desvio staleness dentro de um determinado valor. Uma delas é fazer com que o servidor X mantenha um relógio de vetor de tempo real, onde este servidor veja todas as operações de escrita que foram submetidas a um servidor Y até um determinado período de tempo. Para este caso consideramos que todas as operações de escritas possuem um atributo de tempo associada a elas.

Se o relógio das réplicas estiverem dessincronizados, uma maneira aceitável de controlar este problema é aplicar todas as alterações realizadas após o período da diferença entre os relógios do servidor A ao B. Suponha que o relógio do Servidor A esteja 10 minutos adiantado, comparando-se com o relógio do servidor B. Neste caso o servidor B deverá realizar todas as operações de atualização que foram realizadas no servidor A, contando o horário local do relógio de B, no servidor A, mais os 10 minutos da diferença do relógio destes servidores.

Limite de desvio de ordem

Relembre que desvios de ordem são gerados em casos onde cada réplica recebe uma operação de atualização ao mesmo tempo. Neste caso cada réplica terá uma fila local das operações de escrita que devem ser aplicadas a sua cópia, porém a ordem de aplicação destas operações ainda devem ser determinada. O desvio de ordem é determinado pelo tamanho desta fila.

Neste caso, determinar quando a consistência de ordem deve ser reforçada é simples, quando o tamanho da fila de escrita extrapolar um determinado valor máximo. Neste ponto o servidor não aceitará mais operações de escrita, e tentará executar o commit  das operações de escrita negociando a ordem em que elas devem ser aplicadas, com os outros servidores. Existem muitas formas que esta ordem pode ser determinada, uma delas é baseada em atributo de índice primário, ou no quorum.

Protocolos baseados atributo de índice primário

No caso de consistência sequencial, os protocolos baseados no atributo de índice prevalecem, nestes protocolos cada item armazenado, possui um índice de primariedade, o qual será responsável por ordenar as operações de escrita

Protocolo de escrita remota

O protocolo primário mais simples existente é aquele conhecido como protocolo de backup, neste protocolo as operações de escrita serão encaminhadas para um único servidor e as operações de leitura podem ser processadas localmente. Neste protocolo, quando temos uma operação de escrita, ela será realizada localmente e depois esta operação será enviada ao servidor central, o qual enviará uma mensagem para todas as réplicas e assim que todas as réplicas forem atualizadas o processo de escrita inicial é avisado, o que caracteriza uma consistência sequencial já que todos os processos veem as operações de escrita na mesma ordem, não importa qual réplica seja consultada.

Este tipo de operação de escrita pode demorar muito tempo, já que o processo de escrita fica esperando todas as cópias serem atualizadas.

Protocolo de escrita local

Uma variação do protocolo descrito anteriormente acontece quando um processo quer realizar uma operação de escrita em um dado elemento x, ele procura a cópia primária daquele elemento, copia o seu valor para a réplica local e realiza a atualização nele. Com isto é possível realizar múltiplas operações de escrita ao mesmo tempo, já que a operação de escrita é realizada localmente, assim como as operações de leitura. Cada operação de escrita deverá ser copiada para as réplicas assim que a alteração da réplica primária finaliza, o faz com que o processo de atualização seja não bloqueante, já que ele não precisa esperar todas as réplicas se atualizarem.

Este tipo de protocolo também pode ser utilizado em sistemas móveis e para isso ele deve assumir o papel de cópia primária para todos os elementos que ele deseja alterar quando desconectado, com isso o sistema altera os dados localmente e assim que ele se conecta a rede ele poderá atualizar as réplicas deixando a base em um estado consistente novamente.

Uma última variação deste tipo de protocolo são utilizados em sistemas de arquivo distribuídos, o que neste caso habilita alterações sequenciais localmente e assim que estas operações finalizam elas são propagadas para as réplicas, com isso a velocidade de escrita deste protocolo é bem alta.

Protocolo de escrita replicada

Neste protocolo as operações de escrita podem ser enviadas para múltiplas réplicas, ao invés de somente uma, como acontece no procolo baseado em primariedade. Uma distinção pode ser feita entre a replicação ativa, onde as operações de atualização são enviadas a todas as réplicas, e os protocolos de consistência que são baseados em votação da maioria.

Replicação ativa

Na replicação ativa, cada réplica possui um processo associado que carrega as operações de atualização. Neste caso cada operação de escrita é enviada a todas as réplicas.

Um problema da replicação ativa é que estas operações deverão ser enviadas na mesma ordem para todas as réplicas, com isso um mecanismo de multicast totalmente ordenado é necessário. Existem várias formas de se implementar esta ordenação, todas elas são baseados no índice de primariedade de um dado

Protocolo baseado em quorum

Um exemplo de como este algoritmo funciona é em um sistema de arquivos distribuídos, supondo que um arquivo está replicado em N servidores. Pode-se estabelecer uma regra para atualização onde para atualizar um determinado arquivo, o cliente deverá contactar mais que a metade dos servidores e eles devem aceitar a atualização daquele arquivo. Assim que eles aceitam o arquivo é alterado para uma nova versão, que será associada ao novo arquivo. Esta versão será utilizada para determinar se o arquivo é o mesmo em todas as réplicas.

Para ler um arquivo deste sistema, o cliente também deverá contactar a maioria dos servidores e perguntar pela versão do arquivo, se todas as versões forem a mesma a leitura poderá ser realizada.

Protocolo de coerência de cache

Como os caches são armazenados nos clientes, ao invés dos servidores, a ideia de sincronizá-los para manter a sua coerência, parece um pouco diferente do que vimos até agora, mas não é.

A primeira solução encontrada foi validar a consistência do dado utilizado, neste caso assim que uma transação é iniciada, o cache vai verificar, possivelmente no servidor, se o dado utilizado está consistente, e neste caso a transação não pode continuar enquanto esta consistência não é verificada.

Uma segunda forma de fazer isto, é deixar a transação continuar, ou seja assume-se que o dado é consistente quando a transação inicia, enquanto isso a consistência do dado é checada, e caso o dado seja inconsistente a transação será abortada.

O terceiro caso esta validação acontece somente quando a transação é comitada, neste caso todas as operações são realizadas e depois que todo o trabalho é feito o dado acessado é checado pela consistência e caso os dados estiverem atualizados a transação é abortada.

Uma outra preocupação destes protocolos de cache é a estratégia de coerência, que irá determinar como os dados do cache serão mantidos consistentes com as cópias dos servidores. A maneira mais simples de se resolver este problema é desabilitar o cache de dados compartilhados. Os dados compartilhados ficam somente no servidor e a consistência destes dados é mantida utilizando-se um dos protocolos apresentados até agora. Neste caso somente os dados privados são passíveis de cache.

Quando os dados compartilhados podem ser cacheados, existem duas maneiras de forçar a coerência do cache. Na primeira delas, o servidor de cache irá enviar uma mensagem de invalidação para todos os caches, assim que um dado for modificado. E a segunda é simplesmente propagar a atualização.

Por último devemos considerar o que acontece quando um processo altera um dado cacheado. Quando caches somente de leitura são utilizados, as operações de atualização serão realizadas somente no servidor, que as enviarão para os servidores de cache através de algum protocolo de distribuição. Na maioria dos casos, um protocolo de recebimento é utilizado, ou seja o cache detecta que os dados estão desatualizados e requisitam uma atualização do cliente.

Uma alternativa é permitir que os caches atualizem os dados e estas atualizações são enviadas para os servidores.

 Apresentação