Identificação de Dados

Descrição

Em sistemas distribuídos, temos a pulverização de dados entre os participantes da rede; e para recuperar tal informação temos o problema de localizar estes novamente na rede. Este problema se torna mais sério quando tratamos de redes extremamente pulverizadas (como P2P); e quanto mais descentralizada for a hierarquia da rede, maior se torna o problema de localização de dados

De forma muito semelhante às redes P2P temos redes onde os sistemas são pervasivos, e é necessário uma abordagem de busca e identificação de serviços (assim como pensamos em informação aqui). Para essa função já existe vários protocolos disponíveis:

Comunidade de Pesquisa
1. INS
2. Ninja SDS
3. DEAPspace
Empresas de Software
Padrões da Industria
1. Salutation
2. SLP
3. [Bluetooth SDP]

Não vou entrar em detalhes sobre este assunto pois já existe outro capítulo neste livro tratando de computação pervasiva e ubíqua, explorando o assunto de sistemas de informação distribuídos.

A distribuição de dados em si gera outro tanto de problemas a serem pensados e tratados, como veremos mais a seguir.

Tipos de Rede Distribuída

Redes com centralização

(servidor central de busca; ex.: Napster)

Redes hierárquicas

(redes com superpeers; ex.: FastTrack e KaZaA)

Redes totalmente pulverizadas

(todos nós são “iguais”; ex.: Gnutella)

Mistas

(usa mais de um tipo de distribuição ou usa mais de uma rede; ex.: Emule)

FreeNet

(não usa uma topologia previsível, para preservar o anonimato. Site Oficial)

O(s) problema(s)

Encontrar os dados na rede

Quando se distribui um dado na rede, em algum momento alguém irá requisitar este. Mas como descobrir em qual nó a informação está?

Encontrar as partes dos dados na rede

Uma dada informação pode ainda ser particionada em pedaços para aumentar a taxa de disponibilidade dos dados e tornar o sistema mais robusto (já que a perda de um nó com parte dos dados não implica na perda do dados).

Segurança e Confiabilidade

Aqui são tratados problemas como permissões de acesso aos dados, anonimato e escalabilidade e tolerância a falhas.

Entrada e saída de nós

Devido à forma quase anárquica de uma rede P2P, a entrada e saída de nós podem ser comuns e não ser um erro do nó; mas isso pode impactar seriamente na localização, segurança e disponibilidade dos dados.

Falhas

Erros de rede, dados corrompidos, etc. Aqui são problemas mais comuns de qualquer tipo de rede.

Indexação dos dados

Este problema é de grande importância para a localização dos dados; pois estes antes de poderem ser encontrados eficientemente devem ser indexados. E até agora não se tem um trabalho que realize esta etapa de forma eficiente.

Abordagens

Apesar de tantas áreas interessantes para se abordar dentro deste tema, o foco aqui é sobre a busca de dados numa rede distribuída, portanto não irei aprofundar nos outros desafios citados acima.

Dessa forma, no que tange à localização de dados temos 3 principais abordagens:

Sistema hierárquico (tipo DNS)
Servidor central mapeando o dado à localização
Algoritmos de busca simétricos (DHT) numa rede completamente descentralizada.

Técnicas

Como encontrar uma informação numa rede P2P com um grande número de nós? Este problema é a alma de qualquer rede distribuída P2P. Os últimos algoritmos desenvolvidos por grupos de pesquisa no assunto apresentam algo em comum; a maioria explora uma interface para DHT (Dinamic hash Table, da sigla em inglês). Neste caso, os dados são inseridos numa DHT e são recuperados especificando uma chave única. Neste caso, para usar essa estrutura de dados o algoritmo precisa antes descobrir qual nó armazena o dado por tal chave. Mas para este problema, cada nó mantém uma pequena lista de nós vizinhos (overlay network). Essa rede “interna” é usada para rotear mensagens mesmo sem saber o IP dos vizinhos de antemão para armazenar e recuperar chaves. O resultado de sistemas usando este esquema são redes distribuídas robustas, fácil uso e extremamente escalável.

A forma mais simples de se pensar para se resolver o problema de encontrar uma informação em um sistema distribuído seria criar um servidor central que cataloga os dados nos nós em que estão. Contudo este servidor central se torna um ponto crítico de falha. Mais tradicionalmente pode-se criar uma hierarquia na rede a fim de se obter maior escalabilidade (como exemplo tem-se o DNS). É uma forma eficiente de se realizar buscas num sistema distribuído, mas a queda do servidor raiz ou mesmo um nó suficientemente alto pode ser catastrófico caso este não tenha políticas de redundância. Estas são formas de busca estruturada; uma vantagem dessa forma de busca é que é possível garantir que um dado armazenado seja encontrado.

Para vencer as limitações das técnicas anteriores pensou-se em algoritmos de busca simétrica (todos os nós são iguais e cada nó participa somente de uma pequena parte da busca). Funciona da seguinte forma: um nó envia uma requisição a todos os seus vizinho, se o vizinho tiver o ítem procurado, este é retornado; senão o segundo nó repassa a requisição a todos os seus vizinho, e daí em diante. A rede Gnutella tem o protocolo semelhante a este, com alguns mecanismos para evitar loops de requisições. Mas por usar broadcast de mensagens gera uma sobrecarga de tráfego na rede. Uma alternativa para fugir desse problema de excesso de tráfegos é ter alguns super-nós (tipo de rede onde existe uma pequena hierarquia entre nós e super-nós), como usado nas redes FastTrack e KaZaA. Mas neste caso perde-se um pouco a robustez pois falhas em super-nós torna-se mais crítica. Outra abordagem é usada na FreeNet, onde o principal característica é garantir o anonimato dos nós. Isto ocorre porque a rede não associa um dado a nenhum servidor de forma previsível e também não correlaciona os nós de acordo com uma topologia; mas como efeito colateral documentos raros podem simplesmente “desaparecer” da rede.

Os mais recentes algoritmos de busca são CAN, Chord, Kademlia, Pastry, Tapestry e Viceroy; os quais são estruturados e simétricos. O uso de tabelas hash para busca é muito interessante visto que a interface desta não faz nenhuma restrição sobre as chaves ou aos dados. Os únicos requisitos é que as chaves sejam numéricas e que os nós possam armazenar chaves um para o outro. Uma DHT implementa somente uma operação kookup(key).

Ao usar DHT, os algoritmos de busca devem lidar com os seguintes problemas: Mapeamento de chaves para os nós de forma balanceada, repassar a requisição por um dado para outro nó que tenha maior chance de ter o dado procurado, função distância (é como cada algoritmo calcula a proximidade de um nó dada uma chave; por exemplo no Chord a proximidade é a diferença numérica entre dois ID’s, no Patry ou no Tapestry a proximidade é o número de bits do prefixo iguais) e a construção de tabelas de roteamento adaptativas.

A principal diferença dos algoritmos é a estrutura de dados que estes usam para a tabela de reoteamento para obter uma complexidade de O(log N) lookups. Chord usa uma estrutura parecida com uma skiplist. Já o Kademlia, Patry e Tapestry usa uma árvore como estrutura de dados. O Viceroy usa uma estrutura de dados borboleta, que só requer informação sobre um número constante de nós, mas ainda tem complexidade O(log N). Uma recente variante do Chord faz uso de grafos de Bruijn, que exigem que cada nó tenha conhecimento de apenas dois outros nós, mas ainda assim complexidade de O(log N).

Outra diferença entre os algoritmos é quanto à dimensão de roteamento, os algoritmos acima fazem roteamento em uma dimensão, já o CAN faz uso de um espaço de coordenadas cartesiano n-dimensional para implementar a DHT. O espaço é particionada em zonas (hiper-retângulos), e cada nó é responsável por uma zona e é identificado pelos limites da sua zona. Uma chave é mapeada em um ponto no espaço de coordenadas, e é armazeando no nó que contém as coordenadas do ponto. Exemplo: CAN 2-dimensional [0,1] x [0,1] com 6 nós.

Bibliografia