“People confuse programming with coding. Coding is to programming what typing is to writing.”
Leslie Lamport
Um sistema distribuído é uma coleção de computadores independentes que trabalham juntos para atingir um objetivo comum. Em um sistema distribuído, cada nó de computador opera de forma autônoma e se comunica com outros nós do sistema por meio de uma rede, através da troca de mensagens. Esses nós podem compartilhar recursos, como dados, memória ou poder de processamento, para fornecer um sistema mais robusto e escalável do que um único computador. Os sistemas distribuídos podem ser encontrados em uma ampla gama de aplicações, incluindo computação em nuvem, redes peer-to-peer e redes de sensores. O projeto e a implementação de sistemas distribuídos apresentam desafios únicos, incluindo gerenciamento de consistência de dados, tolerância a falhas e escalabilidade, que devem ser abordados para garantir que o sistema funcione de maneira correta e eficiente.
25.1 - Problemas Básicos em Computação Distribuída: Coordenação e Sincronização de Processos, Exclusão Mútua, Difusão de Mensagens.Os principais tipos de sistemas distribuídos são:
As principais características de um sistema distribuído são: compartilhamento de recursos, concorrência, escalabilidade e transparência. Os desafios primordiais que devem ser resolvidos incluem:
Muitos algoritmos utilizados em sistemas distribuídos dependem da seleção de um coordenador para orquestrar as operações compartilhadas entre os nós. Os algoritmos de eleição de líder (election algorithms) são utilizados para escolher esse coordenador. Além disso, precisa determinar a regra de seleção caso o coordenador atual pare de funcionar. Essa regra pode ser a escolha por quem tem o maior número de prioridade no sistema em geral. Vejamos os dois algoritmos de eleição:
Coordenação e orquestração são duas abordagens usadas para gerenciar a interação entre diferentes processos e serviços. Embora ambas as abordagens sejam usadas para atingir um objetivo comum, existem algumas diferenças importantes entre coordenação e orquestração.
A coordenação refere-se ao processo de gerenciamento da interação entre diferentes processos e serviços sem uma autoridade central. Em um sistema coordenado, cada processo ou serviço se comunica diretamente com outros processos ou serviços para trocar informações e coordenar suas ações. A coordenação é frequentemente usada em sistemas fracamente acoplados, onde os processos ou serviços podem operar de forma independente, mas podem precisar trocar informações ou colaborar para atingir um objetivo comum.
A orquestração, por outro lado, refere-se ao processo de gerenciamento da interação entre diferentes processos e serviços por meio de uma autoridade central ou orquestrador. Em um sistema orquestrado, o orquestrador gerencia o fluxo de informações e ações entre diferentes processos ou serviços, determinando a ordem em que as ações devem ser executadas e as condições sob as quais as ações devem ser executadas. A orquestração é frequentemente usada em sistemas fortemente acoplados, onde os processos ou serviços precisam ser coordenados de perto para alcançar um objetivo comum.
Outra diferença fundamental entre coordenação e orquestração é o nível de controle que cada abordagem oferece. Em um sistema coordenado, cada processo ou serviço tem alto grau de autonomia e pode tomar decisões de forma independente. Em um sistema orquestrado, o orquestrador tem um maior nível de controle sobre as ações dos diferentes processos ou serviços, podendo sobrepor decisões individuais para garantir que o sistema como um todo esteja operando de forma eficaz.
A sincronização de processos garante que os processos sejam executados de maneira coordenada e sincronizada para evitar conflitos e garantir a consistência.
Existem diversas técnicas que podem ser utilizadas para coordenação e sincronização de processos. Uma técnica comum é a passagem de mensagens, em que os processos se comunicam uns com os outros por meio da troca de mensagens. A passagem de mensagens pode ser implementada usando vários protocolos de comunicação, como TCP/IP, UDP ou HTTP.
Outra técnica é a memória compartilhada, onde vários processos têm acesso ao mesmo espaço de memória. A memória compartilhada pode ser implementada usando vários mecanismos, como chamadas de procedimento remoto (RPCs) ou memória compartilhada distribuída (DSM).
Os sistemas de computação distribuída também usam vários algoritmos e protocolos para garantir a coordenação e a sincronização do processo. Por exemplo, o protocolo two-phase commit é amplamente utilizado para garantir a consistência em sistemas distribuídos. O algoritmo funciona garantindo que todos os processos concordem se uma transação deve ser confirmada ou revertida.
Existem vários problemas clássicos em computação distribuída que têm sido estudados extensivamente por pesquisadores da área. Alguns dos problemas mais conhecidos incluem:
Abordar esses problemas é crucial para garantir a correção, confiabilidade e desempenho dos sistemas distribuídos. Os pesquisadores da área continuam desenvolvendo novos algoritmos e protocolos para enfrentar esses desafios e melhorar a eficiência e a escalabilidade dos sistemas de computação distribuídos.
A difusão de mensagens é um processo essencial na computação distribuída, pois permite que os processos se comuniquem e colaborem entre si, mesmo que estejam localizados em diferentes partes da rede.
Esse processo pode ser implementado usando várias técnicas, como inundações (flooding), fofocas (gossiping) e protocolos epidêmicos. A inundação é uma técnica simples e eficaz que envolve a transmissão da mensagem para todos os nós da rede. A mensagem é transmitida do remetente para todos os seus vizinhos, e cada vizinho, por sua vez, encaminha a mensagem para todos os seus vizinhos, e assim por diante. Este processo continua até que todos os nós da rede recebam a mensagem. A inundação é uma técnica confiável, mas pode ser cara em termos de largura de banda e poder de processamento.
A fofoca é outra técnica comumente usada para difusão de mensagens em computação distribuída. Na fofoca, cada nó seleciona aleatoriamente um vizinho e envia a mensagem para ele. O nó receptor então seleciona aleatoriamente um vizinho e encaminha a mensagem para ele. Este processo continua até que todos os nós da rede recebam a mensagem. A fofoca é uma técnica mais eficiente do que a inundação, pois reduz o número de mensagens que precisam ser transmitidas na rede.
Protocolos epidêmicos são uma família de técnicas usadas para difusão de mensagens em sistemas distribuídos de grande escala. Os protocolos epidêmicos são baseados na ideia de infectar nós com a mensagem, semelhante à forma como um vírus se espalha em uma população. Em um protocolo epidêmico, cada nodo infecta alguns de seus vizinhos com a mensagem, e os nodos infectados então infectam seus vizinhos. Este processo continua até que todos os nós da rede recebam a mensagem. Os protocolos epidêmicos são altamente escaláveis e tolerantes a falhas, mas exigem uma quantidade significativa de poder de processamento e largura de banda.
O controle de concorrência refere-se ao processo de gerenciamento de acesso a recursos compartilhados em um sistema distribuído para garantir que vários processos não interfiram entre si. Em um sistema distribuído, diferentes processos podem acessar os mesmos dados, e o controle de concorrência garante que esses processos não modifiquem os dados ao mesmo tempo, levando a conflitos e inconsistências. Técnicas como bloqueio e controle de versão são comumente usadas para controle de concorrência em sistemas distribuídos.
Transações distribuídas são transações que abrangem vários computadores em um sistema distribuído. Em uma transação distribuída, vários processos podem estar envolvidos e cada processo pode acessar e modificar diferentes partes dos dados. As transações distribuídas devem ser executadas de forma correta e confiável, mesmo na presença de falhas ou atrasos na rede.
Para garantir a execução correta de transações distribuídas, protocolos como o protocolo two-phase commit e o protocolo three-phase commit são comumente usados. O protocolo two-phase commit garante que todos os processos envolvidos em uma transação distribuída concordam em confirmar ou abortar a transação. Na primeira fase do protocolo, cada processo é solicitado a se preparar para a transação. Se todos os processos concordarem em preparar, então a segunda fase é executada, onde todos os processos confirmam ou abortam a transação.
O protocolo three-phase commit é uma extensão do protocolo two-phase commit e garante que uma transação seja executada mesmo na presença de falhas ou atrasos na rede. O protocolo three-phase commit introduz uma terceira fase, onde os processos envolvidos na transação podem chegar a uma decisão mesmo que alguns processos estejam indisponíveis.
Existem vários algoritmos para controle de concorrência e transações distribuídas, que são comumente usados em sistemas de computação distribuída:
Esses algoritmos não são mutuamente exclusivos e diferentes algoritmos podem ser usados juntos para obter controle de simultaneidade e garantir a execução correta de transações distribuídas em um sistema de computação distribuído. A escolha do algoritmo depende de vários fatores, como o tamanho e a complexidade do sistema, o nível de tolerância a falhas necessário e os requisitos de desempenho e escalabilidade do sistema.
Exclusão mútua e condições de corrida são dois problemas comuns que surgem quando vários processos tentam acessar recursos compartilhados simultaneamente. Esses problemas podem levar a um comportamento imprevisível, resultados incorretos e até travamentos do sistema.
A exclusão mútua é um mecanismo que garante que apenas um processo possa acessar um recurso compartilhado por vez. Sem exclusão mútua, vários processos podem acessar o mesmo recurso compartilhado simultaneamente, levando a inconsistências e resultados incorretos. Em um sistema distribuído, a exclusão mútua pode ser alcançada por meio de vários algoritmos, como o algoritmo de exclusão mútua distribuída de Lamport ou o algoritmo de exclusão mútua de Ricart-Agrawala.
As condições de corrida, por outro lado, ocorrem quando dois ou mais processos acessam um recurso compartilhado em uma ordem imprevisível, levando a resultados inesperados. Por exemplo, se dois processos tentarem incrementar a mesma variável compartilhada simultaneamente, o valor da variável pode ser incrementado incorretamente, resultando em resultados incorretos. Em um sistema distribuído, as condições de corrida podem ser evitadas usando mecanismos de sincronização, como bloqueios, semáforos ou protocolos de passagem de mensagens.
Para evitar exclusão mútua e condições de corrida na computação distribuída, várias técnicas foram desenvolvidas, incluindo protocolos de passagem de mensagens, mecanismos de bloqueio distribuído e gerenciamento de transações distribuídas. Essas técnicas garantem que os recursos compartilhados sejam acessados de forma controlada e previsível, reduzindo o risco de comportamento imprevisível e resultados incorretos.
O algoritmo da padaria (Bakery Algorithm) é um algoritmo de exclusão mútua usado em sistemas distribuídos para garantir que vários processos não entrem em uma seção crítica ao mesmo tempo. É um algoritmo descentralizado que depende de processos que se comunicam entre si para determinar sua ordem de entrada na seção crítica.
O algoritmo funciona atribuindo um número único a cada processo que solicita acesso à seção crítica. O processo com o número mais baixo recebe acesso primeiro à seção crítica. Se dois processos solicitarem acesso ao mesmo tempo, o processo com o menor número terá prioridade. Assim que um processo termina a execução na seção crítica, ele libera seu número, permitindo que outros processos entrem.
Aqui está um exemplo de como o Bakery Algorithm pode ser implementado em Python:
from threading import Thread
n = 5
entering = [False] * n
numbers = [0] * n
def bakery(i):
global entering, numbers
entering[i] = True
numbers[i] = max(numbers) + 1
entering[i] = False
for j in range(n):
while entering[j]:
pass
while numbers[j] != 0 and (numbers[j], j) < (numbers[i], i):
pass
# Critical section
print("Process", i, "entered the critical section")
numbers[i] = 0
threads = []
for i in range(n):
threads.append(Thread(target=bakery, args=(i,)))
for t in threads:
t.start()
for t in threads:
t.join()
Neste exemplo, definimos $n$ como o número de processos e inicializamos inserindo e numerando matrizes para acompanhar o estado de cada processo. Em seguida, definimos a função padaria, que é a principal função que implementa o Algoritmo da padaria.
A função de padaria primeiro define o sinalizador de entrada como True para o processo atual e atribui um número exclusivo a ele. Em seguida, ele verifica outros processos que estão entrando no momento ou têm um número menor que o processo atual e espera que eles terminem antes de entrar na seção crítica.
Uma vez dentro da seção crítica, o processo executa suas tarefas e então libera seu número definindo-o como zero. A matriz de threads é usada para criar vários threads que executam a função de padaria simultaneamente.
Quando executamos esse código Python, podemos ver que cada processo está entrando na seção crítica em sequência, sem que dois processos entrem ao mesmo tempo. Isso demonstra como o Bakery Algorithm pode ser usado para garantir a exclusão mútua em sistemas distribuídos.
A consistência causal é um tipo de modelo de consistência usado em sistemas distribuídos para garantir que a ordem dos eventos seja mantida em diferentes nós ou processos. Nesse modelo, uma relação causal entre os eventos é estabelecida pela ordem em que ocorrem, e essa relação é mantida em todos os nós do sistema.
Em um sistema distribuído, os eventos podem ocorrer em nós diferentes em momentos diferentes e é importante garantir que a ordem dos eventos seja mantida mesmo que ocorram em nós diferentes. A consistência causal consegue isso impondo uma ordem parcial nos eventos do sistema com base em seus relacionamentos causais.
Por exemplo, vamos considerar um sistema distribuído onde vários nós estão atualizando uma estrutura de dados compartilhada. Se o nó A atualizar a estrutura de dados e depois o nó B a atualizar, é importante que todos os outros nós do sistema vejam essas atualizações na mesma ordem. Se o nó C vir a atualização do nó B antes da atualização do nó A, ele terá uma visualização inconsistente da estrutura de dados.
Para garantir consistência causal, o sistema deve manter uma ordem parcial de eventos com base em suas relações causais. Se o evento X ocorrer antes do evento Y e o evento Y ocorrer antes do evento Z, então o evento X deverá ocorrer antes do evento Z. Isso garante que todos os nós do sistema vejam os eventos na mesma ordem e mantenham uma visão consistente da estrutura de dados.
A consistência causal pode ser alcançada por meio de várias técnicas, como relógios vetoriais ou rastreamento de dependência. Os relógios vetoriais são um mecanismo usado para estabelecer a relação causal entre eventos no sistema. A cada evento é atribuído um relógio vetorial que captura as informações de ordenação desse evento, e esse relógio vetorial é propagado junto com o evento para todos os outros nós do sistema.
O rastreamento de dependência é outra técnica usada para manter a consistência causal em sistemas distribuídos. Envolve rastrear as dependências entre eventos e propagar essas informações de dependência junto com os eventos. Isso permite que todos os nós do sistema mantenham uma visão consistente da estrutura de dados, mesmo que os eventos estejam ocorrendo em nós diferentes.
Existem várias técnicas e algoritmos para comunicação de processos em computação distribuída, que incluem:
Vantagens do Método Publicar-Assinar:
Desacoplamento: O método promove um desacoplamento eficiente entre os componentes, permitindo que eles operem independentemente.
Escalabilidade: O método é escalável, pois não requer conhecimento direto entre publicadores e assinantes, tornando-o adequado para sistemas distribuídos grandes e complexos.
Distribuição de Informações: As mensagens são disseminadas para todos os assinantes relevantes sem exigir interações individuais com cada assinante.
Flexibilidade: Os assinantes podem se inscrever ou cancelar a inscrição em tópicos conforme suas necessidades mudam.
Em um sistema distribuído, as falhas podem ocorrer em vários níveis, como falhas de hardware, falhas de software, falhas de rede e erros humanos. Essas falhas podem tornar o sistema instável, levando à perda de dados, tempo de inatividade do sistema ou desempenho reduzido. Tolerância a falhas é a capacidade de um sistema distribuído continuar operando apesar dessas falhas, e envolve várias técnicas e estratégias para garantir a confiabilidade e disponibilidade do sistema.
Uma das principais técnicas para tolerância a falhas em sistemas distribuídos é a redundância. A redundância envolve a replicação de componentes críticos do sistema para garantir que haja cópias de backup disponíveis em caso de falha. Por exemplo, os dados podem ser replicados em vários servidores, portanto, se um servidor falhar, os dados ainda poderão ser acessados de outros servidores. A redundância também pode ser obtida replicando processos ou serviços em vários nós, portanto, se um nó falhar, o serviço ainda poderá ser acessado a partir dos outros nós.
Outra técnica para tolerância a falhas é a detecção e recuperação de erros. A detecção de erros envolve monitorar o sistema em busca de erros e detectar quando ocorre uma falha. Uma vez detectada uma falha, mecanismos de recuperação podem ser ativados para restaurar o sistema ao seu estado anterior. Os mecanismos de recuperação podem incluir reiniciar processos com falha, restaurar dados de backups ou alternar para componentes de backup.
O balanceamento de carga é outra técnica para tolerância a falhas, que envolve a distribuição da carga de trabalho em vários nós para evitar sobrecarga e melhorar o desempenho. O balanceamento de carga garante que nenhum nó seja sobrecarregado e, se um nó falhar, a carga de trabalho pode ser redistribuída para os nós restantes.
Finalmente, algoritmos de consenso também podem ser usados para tolerância a falhas em sistemas distribuídos. Algoritmos de consenso são usados para garantir que todos os nós do sistema concordem com uma determinada decisão, mesmo na presença de falhas ou partições de rede. Os algoritmos de consenso incluem algoritmos como Paxos, Raft e tolerância a falhas bizantinas.
Sistemas operacionais distribuídos (DOS) são um tipo de sistema operacional projetado para gerenciar ambientes de computação distribuídos, onde vários computadores são conectados por uma rede e trabalham juntos para realizar uma tarefa. O DOS fornece uma interface transparente e unificada para os usuários, ocultando a complexidade da rede subjacente e da infraestrutura de hardware.
Um componente essencial de um DOS é o sistema de arquivos distribuídos (DFS). Um DFS permite que os usuários acessem arquivos armazenados em computadores remotos como se fossem armazenados localmente. Um DFS permite que os usuários compartilhem arquivos entre diferentes computadores e fornece um mecanismo para lidar com conflitos e sincronização de arquivos. Alguns exemplos populares de DFS incluem Network File System (NFS), Common Internet File System (CIFS) e Andrew File System (AFS).
Os servidores de nomes permitem que os usuários localizem e acessem recursos, como arquivos, serviços e dispositivos, no sistema distribuído. Alguns exemplos populares de servidores de nome incluem Domain Name System (DNS), Lightweight Directory Access Protocol (LDAP) e Simple Network Management Protocol (SNMP).
A memória compartilhada é outro componente importante do DOS, que permite que vários processos acessem o mesmo espaço de memória. A memória compartilhada fornece uma maneira rápida e eficiente para os processos se comunicarem e compartilharem dados. No entanto, a memória compartilhada requer uma sincronização cuidadosa para evitar inconsistências e conflitos de dados. Alguns exemplos populares de algoritmos de memória compartilhada incluem arquivos mapeados de memória, memória compartilhada distribuída (DSM) e objetos compartilhados distribuídos (DSO).
Os mecanismos de segurança no DOS incluem autenticação, autorização, criptografia e controle de acesso. A autenticação garante que os usuários sejam quem afirmam ser, a autorização determina quais recursos os usuários podem acessar, a criptografia protege os dados em trânsito e o controle de acesso regula o acesso aos recursos com base nas funções e permissões do usuário.
Alguns exemplos de sistemas operacionais distribuídos:
A transparência de acesso em sistemas distribuídos é um conceito fundamental que busca ocultar a complexidade subjacente da comunicação e do acesso a recursos distribuídos, oferecendo aos usuários e aplicativos uma visão unificada e simplificada do ambiente distribuído. Em outras palavras, a transparência de acesso visa tornar a interação com sistemas distribuídos tão transparente e natural quanto a interação com um sistema centralizado.
Existem vários tipos de transparência em sistemas distribuídos, e a transparência de acesso é uma delas. Ela se concentra em tornar a localização e o acesso a recursos remotos indistinguíveis do acesso a recursos locais. Isso significa que os usuários e aplicativos não precisam estar cientes da localização física dos recursos ou dos detalhes da comunicação de rede para interagir com eles.
A implementação da transparência de acesso requer a utilização de protocolos, interfaces e camadas de software que abstraem as complexidades da comunicação de rede e gerenciamento de recursos. As tecnologias de middleware e os serviços de diretório são frequentemente usados para fornecer essa transparência, permitindo que os aplicativos acessem recursos remotos como se fossem recursos locais.
Referências: