Pesquisar este blog

segunda-feira, 14 de abril de 2014

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 configurado para 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.
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, 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 vai 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, 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.
Um exemplo de sistema distribuído que necessita de sincronização de relógios é o GPS, que funciona através da comunicação entre um equipamento e 29 satélites geo estacionários. 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. O aparelho de GPS capta 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 GPS na superfície terrestre com uma precisão de até 50 cm.
Para que o sistema funcione é preciso que o aparelho de GPS 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 GPS 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 1 segundo 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 GPS é 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, como a terra gira mais devagar conforme passa o tempo, esta variação na velocidade de rotação da terra precisa ser corrigida. Desde a criação dos leap seconds, que aconteceu no ano de 1967, 42 leap seconds foram inseridos para corrigir o tempo dos relógios atômicos.
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.java está desatualizado por uma nova versão. Neste caso ser notificado pelos eventos um dos outros, como uma nova versão do Arquivo.java é 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 mutua 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 e é 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

sexta-feira, 11 de abril de 2014

Nomes em Sistemas Distribuídos

Nomes em Sistemas Distribuídos

Sabemos como a utilização de nomes é importante no mundo dos computadores, para os humanos é muito importante associar as máquinas a algum nome, afinal de contas fazemos isso com todas as coisas ao nosso redor. Para acessar um site, digitamos um nome ao invés do seu ip e aquele nome que digitamos no browser é apenas um identificador que direciona a nossa chamada para um endereço ip da página da web.
Para os sistemas esta associação se dá na forma de um endereço, de como identificar unicamente uma máquina, ou um serviço, como o endereço ip das máquinas conectadas a uma rede. O endereçamendo das máquinas geralmente é feito com hashs (alfanuméricos como no ipv6) ou números (como no ipv4), porém isso é difícil de ser lembrado pelos humanos, pois ninguém deve saber o ip do seu site predileto. Entretando as máquinas precisam de um endereçamento único, e esta foi a forma encontrada para identificar unicamente uma máquina em um sistema.
Existe um serviço que realiza o mapeamento entre um endereço e a localização física daquela máquina. Este serviço prove a localização física de uma máquina, através de um nome e através deste serviço é possível identificar qual é o endereço de uma máquina. Em um sistema distribuído a implementação de um sistema de nomeação também é feita em várias máquinas, o que faz com que o próprio sistema de nomeação das máquinas seja um sistema distribuído.
Pela definição um nome é um conjunto de caracteres ou uma sequência de bits que fazem referencia a uma entidade. Uma entidade pode se referenciar a praticamente qualquer coisa em um sistema distribuído, exemplos típicos são arquivos, impressoras, discos, locais, processos, usuários, grupos de mensagens, caixa de emails, páginas web, mensagens, conexões de rede e muito mais.
Entidades podem receber operações, como no caso de uma impressora que oferece uma interface de comunicação onde podemos ordenar uma impressão de um documento, ou uma entidade como uma conexão de rede a qual prove operações de envio e recebimento de dados.
Para operar uma entidade necessitamos acessá-la e para isso é necessário saber onde esta entidade está localizada.
Uma entidade pode trocar de endereço, assim como um computador móvel pode ter um endereço ip diferente em cada local onde ele se conecta, por exemplo quando você está se deslocando com o seu celular e conecta ele na internet através da tecnologia 3G, você recebe um endereço de IP. Esta conexão é feita através de uma torre de comunicação de celular, e esta torre tem uma área de abrangência. Caso este mesmo celular entre em uma área de cobertura de uma outra torre, ou mesmo de uma rede WiFi e se conecte através desta tecnologia, certamente ele receberá um novo endereço de IP, e apesar de ser a mesma entidade, neste caso um smartfone, ela terá dois endereços diferentes. E mesmo um computador pessoal pode ter vários endereços ao mesmo tempo, como diversas conexões providas por mais de uma placa de rede ou uma placa wireless e ethernet.
Além dos endereços existem outros tipos de nomes que precisam de um tratamento especial, como nomes que são utilizados para identificar unicamente uma entidade, e um identificador verdadeiro deverá ter estas propriedades.
Um identificador não pode referenciar mais que uma entidade, cada entidade é referenciada por pelo menos um identificador e um identificador sempre referencia a mesma entidade e nunca será reutilizado.
Ao usar identificadores a tarefa de se referenciar a uma identidade sem haver confusão fica bem mais fácil.

Broadcasting

O broadcasting pode ser utilizado para localizar uma entidade dentro de uma rede, geralmente uma rede local. Neste sistema assim que uma requisição chega a rede, uma mensagem contendo a entidade que será utilizada pela requisição é espalhada pela rede, e somente quem for o dono daquela entidade irá responder a esta requisição. Este princípio funciona muito bem em redes pequenas, e seu algoritmo é bem simples de se implementar, mas quando a rede começa a ficar grande, o custo de disparar uma mensagem para todas as máquinas a fim de localizar uma entidade torna-se muito elevado. 

Repasse de Ponteiros

Uma maneira popular de se localizar dispositivos móveis é utilizando-se do repasse de ponteiros. Este princípio é simples, assim que uma máquina parte de um ponto A para um ponto B, ele deixa no ponto A uma referencia para a sua nova localidade B. A grande vantagem deste princípio é a sua simplicidade, já que assim que a entidade for localizada por um serviço de nomes comum, ela poderá ser encontrada seguindo-se a rota dos ponteiros criada pela máquina.
Porém muitas desvantagens existem neste princípio, a começar pela quantidade de ponteiros que a mensagem terá que percorrer até encontrar a entidade, caso tenhamos um dispositivo que muda de endereço muitas vezes, este caminho será muito longo.
Um outro problema é que caso algum ponto intermediário, entre a sua localização atual e a sua primeira localização, caia o endereço daquela entidade será perdido.

Localização de entidades por hierarquia

Na localização de entidades por hierarquia em uma rede local, há uma organização das máquinas em em vários níveis, partindo de um nível raiz, contendo apenas uma máquina, a qual possui uma lista de todos os identificadores de entidades que estão nos níveis inferiores. Neste sistema, cada entidade possui uma lista de todas as entidades que estão abaixo dela, criando algo como o mostrado na figura abaixo:
Figura 1: Exemplo de sistema de nomes or hierarquia (imagem original em http://www.ai.sri.com/dgeo/images/geoweb-small.gif)

Para buscar uma entidade neste sistema, primeiro é realizado uma busca local. Por exemplo se você estiver dentro de um diretório, representado pelo quadrado inferior da Figura1 caso o conteúdo buscado não esteja naquele nó, ele irá ao nó superior e tentará buscar as informações lá. Caso não ache ele irá subindo até chegar ao nó raiz, o qual contem endereço de todas as máquinas da rede e saberá direcionar a requisição para o local onde se encontra aquela entidade.
Cada nó contém as informações de todas as entidades que estão nas hierarquias inferiores e portanto, quanto mais alto na hierarquia a busca tem que ir, mais lenta ela se torna.
Nos serviços de localização de entidade por hierarquia, uma operação de inserção, assim como uma operação de remoção acontece de baixo para cima, ou seja, a entidade é inserida no nó onde ela fica e o endereço desta entidade será repassado para o seu pai e isso se repete até que o endereço da entidade inserida seja repassado para o nó raiz.

Nomeação estruturada

As estruturas de nomeação apresentadas até agora são muito interessantes para as máquinas, já que os nomes são todos em array de bytes, a nomeação estruturada é utilizada para definir nomes compreensíveis por nós humanos. Neste tipo de nomeação os nomes são armazenados como strings e eles são utilizados em arquivos, nome de máquinas e até na internet, para dar nome aos sites.
Existe um pedaço do sistema onde são armazenados os nomes das entidades que é chamado de names space, ou espaço dos nomes.
Considere como exemplo a maneira como os arquivos do sistemas UNIX são nomeados, os dados referentes aos nomes são armazenados em quatro áreas, Boot block, Superblock, inodes e datablocks.
Nos boot blocks ficam armazenados as informações referentes ao boot do sistema, o superblock contem informações referentes a todo o sistema de arquivo, como o seu tamanho, quais blocos do disco não estão alocados, quais inodes ainda não foram utilizados. Os inodes contem informações de onde os arquivos estão armazenados, quem é o dono, quais são as permissões de cada arquivo, data de criação e data de atualização. Os datablocks são onde os dados dos arquivos ficam armazenados.

Exemplos

Como exemplos de sistemas de nomenclatora temos o DNS e o LDAP.
O DNS é responsável por traduzir os nomes dos websites da internet em endereços de localização, ele funciona como um mapeamento, e ele funciona de uma maneira distribuída.
Por exemplo quando digitamos o endereço do estado de São Paulo em nossos browsers www.sp.gov.br a primeira parte deste endereço a ser identificada é o .br, que diz que o site é armazenado no Brasil, com isso a requisição é transferida para um servidor da Fapesp, orgão responsável pelos domínios no Brasil, lá ele irá analisar a segunda parte do endereço .gov o que fará que a requisição passe pelo servidor que armazena os nomes dos sites de governos (.gov.br), ali ele achará o endereço do servidor que contém o site do governo do estado. Mesmo depois de achar este endereço, a requisição ainda pode ser redirecionada para uma ou um conjunto de máquinas dentro de um cluster, que irá atender a sua requisição.

Apresentação

 

terça-feira, 1 de abril de 2014

Exercícios Sistemas Distribuídos

Segue um material de estudo a ser utilizado como base para a preparação da P1.

  1. Qual é o papel da comunicação entre as máquinas em um sistema distribuído?
  2. Eleja 1 componente de um sistema distribuído e detalhe a sua importância.
  3. Dentre as 7 camadas disponíveis no protocolo de rede, escolha uma e explique-a
  4. RPC é um tipo de chamada executada pelos sistemas distribuídos, explique-a.
  5. Qual é a diferença entre uma chamada assíncrona e uma chamada síncrona, qual é o impacto e quando usar cada uma destas chamadas?
  6. Explique as possíveis dificuldades encontradas para se difundir informações usando um sistema Multicast.
  7. Um dos tipos de comunicação por mensagens, explique como funciona o Socket.
  8. Explique o que é call-by-name, call-by-value e stub.
  9. Distributed Computing Environment deu origem a várias tecnologias utilizadas hoje em dia, indique quais.
  10. Detalhe o funcionamento da comunicação por Stream
  11. Como funciona uma arquitetura de duas camadas? Onde elas podem ser utilizadas?
  12. O que é uma arquitetura descentralizada?
  13. Qual é a importancia do monitoramento em um sistema distribuído?