Fábio Moretti Serra. Modelagem e implementação de um sistema de arquivos distribuído baseado em DHT - PDF
Download "Fábio Moretti Serra. Modelagem e implementação de um sistema de arquivos distribuído baseado em DHT"
Larissa Farias Borja
1 Fábio Moretti Serra Modelagem e implementação de um sistema de arquivos distribuído baseado em DHT Itatiba - São Paulo - Brasil Dezembro de 2008
2 Fábio Moretti Serra Modelagem e implementação de um sistema de arquivos distribuído baseado em DHT Monografia apresentado à disciplina Trabalho de Conclusão de Curso, do Curso de Engenharia da Computação da Universidade São Francisco, sob a orientação do Prof. Rodrigo Chavez Monteiro do Prado, como exigência parcial para conclusão do curso de graduação. Orientador: Prof. Ms. Rodrigo Chavez Monteiro do Prado Curso de Engenharia da Computação Universidade São Francisco Itatiba - São Paulo - Brasil Dezembro de 2008
3 i Modelagem e implementação de um sistema de arquivos distribuído baseado em DHT Fábio Moretti Serra Monografia defendida e aprovada em 10 de Dezembro de 2008 pela Banca Examinadora assim constituída: Prof. Ms. Rodrigo Chavez Monteiro do Prado (Orientador) USF - Universidade São Francisco Itatiba SP. Prof. Ms. Thales Coelho Borges Lima USF - Universidade São Francisco Itatiba SP. Prof. Angelo Amaral USF - Universidade São Francisco Itatiba SP.
4 ii A sorte favorece só à mente preparada Isaac Asimov
5 iii Sumário Lista de abreviaturas e siglas v Lista de Figuras vi Resumo vii Abstract viii 1 INTRODUÇÃO Objetivos Organização do trabalho ARQUITETURAS DE SISTEMAS DISTRIBUÍDOS Sistemas de arquivos distribuídos Tabela hash distribuída ARQUITETURA Requisitos do sistema Projeto Implementação Sistema distribuído DHT Chord Gerenciamento dos diretórios Interface com o usuário Testes
6 Sumário iv 4 CONCLUSÃO 22 Apêndice A -- Tabela comparativa dos sistemas de arquivo distribuídos 23 Apêndice B -- Diagramas UML 24 B.1 Diagrama de classes B.2 Diagramas de seqüência Referências 30
7 v Lista de abreviaturas e siglas AFS API DFS DHT GFS GPL IP NFS PC RAM RPC SHA TCP UML WAN Andrew File System Application Programming Interface Distributed File System Distributed Hash Table Google File System General Public License Internet Protocol Network File System Personal Computer Random Access Memory Remote Procedure Call Secure Hash Algorithm Transmission Control Protocol Unified Modeling Language Wide Area Network
8 vi Lista de Figuras 1 Estrutura de sobreposição de sistemas baseada em DHT Exemplos de resolução de chaves no Chord (TANENBAUM; STEEN, 2007) Diagrama de casos de uso Relação entre as principais classes do projeto Seqüência para a abertura de um arquivo Seqüência para a gravação de um arquivo Seqüência para a remoção de um arquivo Seqüência para a alteração das permissões de um arquivo Seqüência para a obter informações sobre um arquivo Seqüência para obter o conteúdo de um diretório Seqüência para a entrada de um novo nó na DHT
9 vii Resumo Uma característica dos sistemas de arquivos para redes é que todas as operações de leitura e escrita são realizadas por um servidor, causando uma centralização de carga de processamento e armazenamento. Uma alternativa para resolver este problema é a configuração de um sistema de arquivos distribuído, em que os dados permanecem espalhados de forma controlada, entre diversas máquinas constituintes de um agrupamento. Dessa forma a carga é dividida entre todos os computadores da rede. Exemplos desse modelo de sistema são o Andrew File System, CODA, SPRITE e Google File System. Os objetivos desse projeto são a pesquisa, implementação e a elaboração da documentação técnica de um sistema de arquivos distribuído em nível de usuário. Possuindo requisitos como transparência, escalabilidade e replicação e fragmentação dos arquivos. Para atender estes requisitos, o sistema foi montado sobre uma tabela hash distribuída (DHT) que cria uma rede de sobreposição fornecendo os métodos necessários para o gerenciamento dos dados do sistema. Desta maneira, as máquinas clientes obtém a localização dos arquivos através de consultas na DHT que possui o mapeamento de um determinado hash a uma máquina servidora responsável pelo arquivo.
10 viii Abstract One of the network file systems feature is that all read and write operations are done on server side resulting on storage and CPU load centralization. An option to solve this issue is the setup of a distributed file system, where the data remain distributed on a controllable way, between different machines belonging to a group. In this way the load is divided between all computers in the network. Some examples of this system model are Andrew File System, CODA, SPRITE and Google File System. The goals of this project are research, implementation and development of a technical paper describing a user level distributed file system. With requirements as transparency, scalability, replication and file fragmentation. To accomplish such requisites, the system was designed over a distributed hash table (DHT) which creates an overlay network providing the necessary methods to manage data on the system. In this way, the client machines get the data location through queries on the DHT that holds the mappings from a hash to a server node responsible for that file.
11 1 1 INTRODUÇÃO O sistema de arquivos tem a função de abstrair os possíveis dispositivos de armazenamento apresentando ao usuário uma única estrutura padrão de diretórios e arquivos. Este também deve fornecer maneiras independentes para criar, ler, escrever e remover arquivos. (TANENBAUM, 1995) Quando se trata de um sistema de arquivos em rede, o objetivo básico é permitir que um conjunto arbitrário de clientes e servidores possam compartilhar um sistema de arquivos comum. Um padrão muito conhecido é o Network File System (NFS) (SHE- PLER, 2003). A característica básica da arquitetura do NFS é o fato de os servidores disponibilizarem alguns de seus diretórios e de os clientes montarem remotamente estes diretórios. Os arquivos compartilhados são justamente aqueles pertencentes à hierarquia de diretórios, podendo ser lidos e escritos da maneira usual. Esta topologia cliente-servidor, típica do NFS, caracteriza-se por todas as operações de leitura e escrita serem realizadas pelo servidor, causando uma centralização de carga de processamento e armazenamento. Uma alternativa para resolver este problema é a configuração de um sistema de arquivos distribuído, em que os dados permanecem espalhados de forma controlada, entre diversas máquinas constituintes de um agrupamento. Dessa forma a carga é dividida entre todos os computadores da rede. Um exemplo de sistema de arquivos distribuídos é o Andrew File System (AFS) (MELLON, 2008), ele é constituído por clusters, com um servidor de arquivos e várias estações clientes. Seu objetivo é fazer com que a maioria do tráfego seja local a um único cluster, para reduzir a carga no servidor. Quando um usuário solicita a abertura de um arquivo, este é carregado para o disco da estação, de maneira a parecer um arquivo comum para o sistema operacional, desta forma as chamadas de leitura e escrita trabalham de forma usual.
12 1.1 Objetivos 2 O armazenamento distribuído pode proporcionar nativamente vários requisitos desejáveis de um sistema de arquivo comum, como redução da duplicidade de um mesmo arquivo em máquinas clientes, replicação dos dados para segurança (backup), aproveitamento adequado de discos e a disponibilidade da informação para qualquer estação. Um ponto importante para todo sistema distribuído é a capacidade de ampliação sem degradar o desempenho do ambiente. Este requisito, conhecido como escalabilidade, pode ser atingido com a utilização de tabelas hash distribuídas. Através deste recurso não só os dados do sistema estão distribuídos, como também as informações de controle. 1.1 Objetivos Pesquisa, modelagem e desenvolvimento de um software para armazenamento de arquivos em rede baseado em tabela hash distribuída, simulando um sistema de arquivos em nível de usuário, isto é, não serão alteradas as funções do sistema operacional e do sistema de arquivos local. O sistema deverá ser funcionalmente simétrico, onde todas as máquinas do agrupamento terão o mesmo papel dentro do sistema. Objetivos específicos: Estudo detalhado dos principais sistemas de arquivos distribuídos e comparação de seus recursos; Elaboração do projeto incluindo o detalhamento dos recursos e diagramas; Desenvolvimento de um protótipo do software para realização de testes e análise; 1.2 Organização do trabalho O presente trabalho está organizado da seguinte forma, o capítulo 2 descreve algumas conhecidas implementação de sistemas distribuídos e um esclarecimento sobre tabela hash distribuída, a capítulo 3 contém explanações sobre a arquitetura e o projeto desenvolvido e os diagramas construídos, no final os testes e as conclusões são expostas.
13 3 2 ARQUITETURAS DE SISTEMAS DISTRIBUÍDOS 2.1 Sistemas de arquivos distribuídos A seguir serão apresentadas algumas implementações de sistemas de arquivos distribuídos (DFS - Distributed File System) produzidas por empresas e universidades. Encontra-se disponível no apêndice A uma tabela comparativa entre os sistemas descritos. Network File System O Network File System (NFS) foi desenvolvido pela Sun Microsystems e trata-se tanto de um projeto de sistema de arquivos quanto um conjunto de especificações para acesso a arquivos remotos em redes locais. (SILBERSCHATZ; GALVIN, 2000) O NFS é o DFS mais amplamente utilizado em ambientes UNIX. Após a liberação da primeira versão do NFS, em 1985, a Sun tornou pública a especificação do protocolo NFS, isto permitiu a implementação de servidores e clientes NFS por outros vendedores (KON, 1995). Este protocolo visa a operação em ambientes heterogêneos (hardware, sistema operacional, arquiteturas de redes) (SILBERSCHATZ; GALVIN, 2000). Requisito obtido por meio de chamadas de procedimentos remotos (RPC). Assim, a construção de sistemas aderentes a especificação NFS permite a interação entre implementações de diferentes desenvolvedores. Hoje é possível encontrar implementações do NFS para quase todos os sistemas operacionais como UNIX, MacOS, OS/2 e Windows. Por definição os servidores NFS são sem estados, ou seja, eles não armazenam informações sobre o estado de acesso pelo cliente a seus arquivos. Isto garante uma simplificação no desenvolvimento da aplicação e uma ganho de desempenho. Por outro lado, servidores sem estado não podem controlar acessos concorrentes e, por conseguinte, não asseguram a coerência do seu sistema de arquivos. Diferentes clientes podem ter diferentes
14 2.1 Sistemas de arquivos distribuídos 4 e conflitantes cópias de um mesmo arquivo ou diretório em seu cache local. O espaço de nomes de cada cliente pode ser diferente dos demais, mas, a partir do ponto de vista do usuário, este é local e transparente. É tarefa do administrador do sistema determinar como cada cliente irá ver a estrutura de diretórios. A aplicação de nível de usuário baseada em RPC e a política de cache do cliente NFS configuram um desempenho pior do que o da maioria dos sistemas que descrevemos a seguir, no entanto atualmente NFS é o DFS mais utilizado em redes de trabalho. Andrew File System O projeto Andrew (AFS) começou no Carnegie Mellon University em 1983 com o apoio da IBM. Seu objetivo era conceber e implementar um DFS ideal para o ambiente acadêmico, que iria permitir o compartilhamento de uma estrutura comum de diretórios entre milhares de máquinas clientes Kon (1995). O espaço de nomes do AFS é composto pelos chamados volumes, estes são associados aos arquivos de um único cliente. Os volumes são agrupados por um mecanismo similar aos de montagem do UNIX. A localização dos arquivos é registrada em bancos de dados, replicados em cada servidor, assim os clientes obtêm a localização dos volumes através de consultas a essa base de dados. (SILBERSCHATZ; GALVIN, 2000) O AFS foi construído para quando um cliente abrir um arquivo remoto, todo ele seja obtido a partir do servidor. Todas as operações subseqüentes de leitura e escrita utilizarão uma cópia armazenada em um disco local. Só quando o arquivo é fechado, e se este foi modificado, ele é transferido de volta para o servidor. Uma das conseqüência desta técnica é que um cliente C1 somente pode perceber uma atualização do arquivo F feita por outro cliente C2, somente se C1 abrir F após C2 fechá-lo. AFS-2 trouxe o conceito de chamada de retorno, o que permitiu um cliente abrir e fechar um arquivo muitas vezes sem acessar o servidor. A chamada de retorno pode ser enviada pelo cliente quando se atualiza o arquivo, ou pelo servidor quando ele recebe uma nova versão do arquivo a partir de outro cliente. CODA O sistema CODA, implementado no início dos anos noventa, é um descendente do AFS (KON, 1995). Seu principal objetivo é fornecer acesso a um DFS a partir de computadores portáteis. O CODA implementa mecanismos de duplicação automática não presentes
15 2.1 Sistemas de arquivos distribuídos 5 no AFS, porém a coerência entre várias cópias de um mesmo arquivo é mantida com chamadas de retorno, semelhante ao AFS. O recurso mais interessante do CODA é a possibilidade de acessar arquivos do DFS sem estar conectado à rede. Se um arquivo está armazenado em cache local no disco do computador portátil, o usuário pode ler e atualizar este sem a permissão do servidor. Quando o computador portátil é reconectado à rede, o sistema propaga para os servidores apropriados as atualizações feitas durante o período desconectado. Podem ocorrer conflitos, por exemplo, atualizações no mesmo arquivo feitas por clientes diferentes, devido a isto o CODA fornece algumas ferramentas para o usuário decidir qual versão deve prevalecer. Para permitir o acesso aos arquivos enquanto estiver desconectado, o cliente CODA tenta manter em seu disco local a maior quantidade possível de dados. Se o disco local está cheio e um novo arquivo deve ser copiado para ele, o arquivo em cache com a prioridade mais baixa é descartado. SPRITE Os dois principais objetivos do sistema de arquivos SPRITE foram de obter alto desempenho e a semântica UNIX para compartilhamento de arquivos. O desempenho alcançado foi um dos melhores do seu tempo, certamente melhor do que o NFS e o AFS (KON, 1995). A semântica UNIX também foi atingida, o usuário encontra o mesmo tipo de estrutura de uma máquina UNIX local. O cliente obtém a localização dos arquivos consultando uma tabela de prefixos. Cada entrada nesta tabela consta o nome do diretório, o endereço do servidor e um número identificador do diretório. Esse mapeamento é construído e atualizado dinamicamente através de mensagem em broadcast na rede. Como o SPRITE é utilizado em ambientes de servidores com memórias de grande capacidade e estações de trabalho normalmente sem discos, este utiliza um esquema em que a memória cache de arquivos é alocada na memória física, e não em discos. Normalmente, o cache do sistema de arquivos pode chegar a centenas de megabytes da memória disponível. A fim de economizar o tráfego da rede, as alterações dos arquivos são gerenciadas por um mecanismo chamado atualização atrasada (SILBERSCHATZ; GALVIN, 2000). Uma vez a cada 30 segundos, todos os blocos, que não foram alterados são enviados para o servidor.
16 2.1 Sistemas de arquivos distribuídos 6 Um bloco de dados alterado pode levar até 60 segundos para ser enviado para o servidor e depois até mais 60 segundos para ser escrito no disco. Por outro lado, a atualização atrasada torna o sistema mais sensível a falhas (KON, 1995). Google File System Buscando um sistema que atendesse às suas necessidades um DFS, denominado Google File System (GFS), foi desenvolvido pela Google. Os arquivos que está utiliza são, em sua maioria, maiores que gigabytes e as alterações que eles sofrem são frequentemente por anexação e não por substituição, tendendo a um crescimento contínuo. Aliando esses fatores ao problema de falhas em servidores de baixo custo, os desenvolvedores visaram a criação de um sistema escalável, à prova de falhas e com bom desempenho (GHEMAWAT; GOBIOFF; LEUNG, 2003). O GFS é um sistema baseado em clusters, onde cada um possui um servidor mestre (master server) e diversos servidores de porção (chunkservers). Os arquivos são divididos com tamanho fixo de 64 megabytes, identificados por um rótulo de 64 bits e replicadas entre os chunkservers (TANENBAUM; STEEN, 2007). Usualmente as porções possuem 3 réplicas, contudo este número pode ser alterado para arquivos com maior demanda. Essa técnica melhora consideravelmente o desempenho do sistema, pois os arquivos podem ser obtidos paralelamente entre os diversos servidores de porções. Também visa o controle à falhas, pois mesmo no caso de uma falha física num chunkservers, outros servidores ainda terão cópias das porções perdidas. Os chunkservers mantém uma tabela atualizada contendo os dados que possui. Essas informações são enviadas para o servidor mestre, estando sempre atualizado e conhecendo a localização das porções dos arquivos. O servidor mestre armazena três tipos principais de meta-dados: serviço de nomes para os arquivos e porções, o mapeamento dos arquivos para suas porções, e a localização de cada réplica. Também tem conhecimento dos processos que estão utilizando as réplicas. Em outras palavras, sua função é de gerenciar as porções para que estejam sempre disponíveis nos chunkservers para que o cliente GFS possa acessá-las. Essa organização não gera gargalo no servidor mestre, pois após a consulta inicial para localização das porções, o diálogo passa a ser entre o cliente e o chunkservers. A organização do GFS permite que um servidor mestre controle centenas de chunkservers, e vários cluster podem ser interligados definindo o GFS como um DFS altamente escalável.
17 2.2 Tabela hash distribuída Tabela hash distribuída Uma tabela hash é uma estrutura de dados que associa chaves (hash) a valores. As chaves são obtidas através de uma função de tal maneira que seja simples e eficiente encontrar um valor na tabela apenas através de sua chave. Como mostra a figura 1 (LUA et al., 2005) uma tabela hash distribuída (DHT - Distributed Hash Table) configura uma camada entre os nós (tradado na figura como peer) e a rede de sobreposição, e fornece os métodos necessários para o gerenciamentos dos dados do sistema. Figura 1: Estrutura de sobreposição de sistemas baseada em DHT Os dados e os nós da rede recebem uma chave identificadora dentro do mesmo espaço de endereço da DHT, desta forma, a consulta pelo hash dos dados leva ao nó responsável. Principais objetivos de uma DHT: Sempre é possível localizar um item da tabela; Manter a operacionalidade mesmo com um grande nível de participantes no sistema; Fornecer recursos eficientes para a adição e remoção de nós Existem vários modelos de DHT, como Chord (STOICA et al., 2001), CAN (RATNA- SAMY et al., 2001) e Pastry (CASTRO et al., 2003). Cada um com suas particularidades e todos com os mesmos objetivos principais. Para este projeto foi adotado o modelo Chord de DHT. O Chord foi desenvolvido por pesquisadores do MIT Laboratory for Computer Science e fornece mecanismos para traçar um mapa de nós e dados, relacionados por suas chaves. Possui a capacidade de
18 2.2 Tabela hash distribuı da 8 adaptar-se a entrada e a saı da de no s do sistema, respondendo a requisic o es mesmo com sistema mudando continuamente. O Chord organiza os no s em um anel de maneira que cada um conhece a chave e a situac a o o seu predecessor e sucessor, ale m disto, cada no conte m uma tabela de derivac a o (finger table) que conte m o par chave e enderec o de outros no s da rede (TANENBAUM; STEEN, 2007). Esta tabela possui nu mero limitado de registros e e montada atrave s de uma fo rmula matema tica com a pro pria chave do no. Figura 2: Exemplos de resoluc a o de chaves no Chord (TANENBAUM; STEEN, 2007). A figura 2 mostra um exemplo de como o sistema Chord utilizando as informac o es da tabela de derivac a o realizaria a resoluc a o de uma chave igual 26 a partir do no 1 (linha contı nua) e outra da chave 12 a partir do no 28 (linha pontilhada). A localizac a o de um no responsa vel normalmente exige O(log(N)) etapas, sendo N o nu mero de no s do anel (TANENBAUM; STEEN, 2007), a caracterı stica logarı tmica garante a escalabilidade do modelo Chord.
19 9 3 ARQUITETURA Este projeto consiste em um software distribuído baseado em DHT para armazenamento de arquivos em rede, onde todas os nós da DHT tem o mesmo papel. 3.1 Requisitos do sistema Transparência para o usuário. O mapeamento de nomes não contém referências sobre a localização física do arquivo. O usuário pode utilizar o sistema remoto como um recurso local, o sistema distribuído é responsável por localizar os dados. Esta característica também proporciona mobilidade, não restringindo o usuário a iniciar uma sessão em uma estação de trabalho específica. Configuração funcional simétrica. Os elementos do sistema possuem o mesmo grau de importância e autonomia, todas as máquinas componentes tem igual papel na operação do sistema (SILBERSCHATZ; GALVIN, 2000). Esta configuração garante a escalabilidade do sistema, fornecendo facilidade de adicionar e gerenciar novos usuários e máquinas. Replicação dos arquivos. Diferentes cópias de um mesmo arquivo residem em máquinas diferentes. A atualização de uma cópia é refletida em todas as outras, mantendo a semântica de coerência. Ações de exclusão e inclusão também são replicadas. Fragmentação dos dados entre os nós servidores do sistema. Os arquivos são divididos em blocos e armazenados em servidores distintos. Coerência. O sistema contém medidas para garantir a coerência dos arquivos, principalmente as cópias abertas simultaneamente, coletando e armazenado informações de estado de cada arquivo da estrutura. Memória Cache. O cliente mantem cópias locais dos arquivos recentemente abertos, a fim de otimizar o tráfico na rede. As alterações feitas pelo usuário são realizadas na
20 3.2 Projeto 10 cópia local, e somente ao fechar o arquivo as modificações são enviadas para os servidores. Segurança. Os arquivos e diretórios do sistema contém permissões de acesso semelhante ao empregado em ambientes UNIX, mas sem a presença dos grupos de usuário. Possibilidade de diferente níveis de permissão para o proprietário e para os demais usuário. Fornecendo o isolamento ou compartilhamento de dados. 3.2 Projeto Elementos O sistema de arquivos distribuído (DFS) é constituído de dois elementos principais: nós clientes e nós servidores. Os nós clientes são caracterizados por possuírem uma interface de navegação do DFS (isolada do sistema de arquivo local da estação cliente), por não armazenarem os arquivos distribuídos e por manterem um cache temporário com os últimos dados acessados. Os nós servidores constituem o agrupamento mapeado pela DHT. Nestes nós são armazenados os arquivos e a estrutura de diretório. Cada nó é integrante da tabela hash distribuída, esta fornece o mapeamento da localização de todos os dados do DFS e as regras para o armazenamento de novos arquivos. O sistema possui serviços com informação de estados, ou seja, os nós servidores têm conhecimento referente a cada arquivo e sobre os clientes que estão acessando o sistema. A carga principal de processamento e gerenciamento do sistema está nos servidores, isto garante uma baixa configuração mínima de hardware para o cliente. Tabela hash distribuída A fim de atender os requisitos do sistema de escalabilidade e a não necessidade de um servidor central, o projeto é construído sobre uma DHT. Os nós clientes obtêm a localização dos arquivos através de consultas na DHT, esta possui o mapeamento de um determinado hash (correspondente a um arquivo dentro da árvore de diretórios) a um nó servidor que possui o arquivo. Entre os projetos estudados, o Chord foi escolhido para a construção do sistema de arquivos por conseguir atender todos os requisitos de maneira simples.
21 3.2 Projeto 11 Neste projeto a função hash da DHT fornecerá a localização física de um dado, ou seja, o nó responsável, através do posicionamento lógico do arquivo ou diretório na estrutura de arquivos lógica do sistema. A chave é gerada a partir do caminho completo do arquivo na árvore de diretórios virtual. Mapeamento de nomes A visão da árvore de diretórios e arquivos do sistema para um usuário cliente não contém qualquer informação sobre a localização física do dado. Esta árvore é apresentada de maneira semelhante a estrutura de arquivos locais. Mesmo que um dado fisicamente seja movido para um outro nó da DHT, a árvore e o nome do arquivo continuam inalterados. Dessa forma o sistema fornece transparência e independência da localização física do dado. Estas características são atingidas por um modelo de estrutura de arquivos semelhante a um sistema de arquivos convencional, através de inodes. Os inode são arquivos de controle que contém informações sobre um determinado diretório ou arquivo. Na visão do sistema, os inodes são arquivos comuns armazenados nos servidores e indexados pela DHT. Quando um cliente solicita visualizar o conteúdo de um diretório, é enviado a ele um arquivo de controle (o inode correspondente) com a lista de arquivos e subdiretórios do diretório requisitado. Esta informação é processada e apresentada pela interface cliente do sistema, adicionando os elementos descritos no inode dentro da árvore de diretórios. Essa estrutura é montada de forma semelhante ao ambiente UNIX, utilizando a barra / como separador de diretórios e como raiz do sistema. Quando há uma alteração na árvore, como remoção ou inclusão de arquivos ou diretórios, os inodes correspondentes são atualizados pelo sistema. Coerência Para manter a coerência dos arquivos, o sistema possibilita que somente um cliente abra um determinado arquivo para edição. Caso esta condição seja atingida, as novas solicitações por este arquivo são caracterizadas como somente leitura. O inode carrega o parâmetro que indica se o arquivo está sendo utilizado por algum cliente. A responsabilidade de atualizar este parâmetro é do nó servidor que possui o inode alocado, pois quando o cliente solicitar o arquivamento deste dado, o sistema informa a este servidor para liberar o arquivo.
22 3.2 Projeto 12 Para garantir que um arquivo não permaneça bloqueado no caso de falhas do cliente, o nó responsável envia mensagens de controle a este para cada outra requisição para esse mesmo arquivo, caso o nó não obtenha uma resposta, o arquivo é liberado para o novo cliente e o primeiro requisitante perde os privilégios sobre aquele arquivo até um próximo pedido. Quando os arquivos sofrem alterações, a coerência também deve ser tratada nas réplicas. Da mesma forma, o nó responsável por essa tarefa é o que possui o inode. Memória Cache Ao ser solicitado para o sistema um arquivo, este é salvo na memória cache localizada no disco rígido da máquina cliente. Todos os acessos futuros são feitos nesta cópia local. O arquivo é reenviado para o sistema somente quando o cliente solicita, pela interface do sistema, o armazenamento do arquivo, caso este tenha sido modificado. Quando um novo pedido por este arquivo parte do cliente, o sistema verifica a data da última alteração da cópia remota (informação fornecida ao módulo cliente através do inode deste arquivo) com a do arquivo em cache. O arquivo só é novamente transferido se a cópia remota for mais recente que a local. Mesmo nesta situação o sistema marca o inode deste arquivo como em uso, garantido a coerência. O tamanho da cache será limitado, assim quando o limite for atingido os dados mais antigos são removidos para que novos arquivos sejam salvos na área de cache. Um dado mais antigo tem maior chance de ter sofrido alterações por outro cliente do sistema. Replicação O sistema conta com o recurso de replicação dos dados entre os nós da DHT de forma autônoma, a fim de aumentar a disponibilidade dos arquivos em caso de falha de algum nó servidor. A escolha por qual nó armazena a cópia é feita baseada na própria estrutura da DHT, como os nós são organizados logicamente em um anel, o nó sucessor terá uma cópia dos arquivos de seu predecessor. Este modelo foi escolhido pela sua simplicidade e por utilizar os recursos já fornecidos pela DHT. Os métodos de replicação são chamados quando um novo arquivo é inserido ou atualizado no sistema. A responsabilidade por manter a coerência das cópias é do nó que
23 3.2 Projeto 13 possui seu inode. Em caso de falha de um nó servidor, o cliente está configurado para solicitar o arquivo para o nó imediatamente seguinte na estrutura da DHT. Quando o sistema percebe a falha de algum nó, é iniciado o processo de balanceamento dos dados, isto porque um nó que antes empregava o papel de replica passa a ser o servidor principal para aquele conjunto de inode e fragmentos e precisa enviar todos os seus dados para o seu sucessor para manter a duplicidade das informações. Fragmentação Os arquivos são fragmentados em partes menores, cada um de seus fragmentos é armazenado e indexado em um nó servidor distinto. O processo de fragmentação é transparente para o usuário. Apenas arquivos que ultrapassam um tamanho específico são fragmentados e em blocos sempre de mesmo tamanho. Os valores limite para o tamanho do arquivo e tamanho de cada fragmento devem ser definidos observando as características da rede em qual o sistema irá ser empregado. Estruturas de maior porte admitem blocos maiores. As informações sobre os fragmentos são armazenadas no inode do arquivo. Quando um cliente abre um arquivo, o nó responsável gera requisições para os servidores citados no inode solicitando os blocos. Após receber todos os fragmentos, este nó faz a reconstrução do arquivo e o envia ao cliente. Esta característica garante que a carga do sistema seja igualmente distribuída pelo nós da DHT. Desta forma quando um grande arquivo é requisitado vários nós participam do processo por um curto período de tempo. Caso a fragmentação não existisse apenas o nó responsável executaria toda a tarefa, trabalhando um longo período. Segurança Quando um novo arquivo é armazenado no sistema, seu inode gerado carrega a informação de qual é o usuário proprietário do arquivo. Por padrão este arquivo não possui qualquer restrição de acesso. Os proprietários podem alterar a permissão de acesso de seus arquivos, configurando o nível de acesso que deseja que os outros usuários tenham de seus dados. Esse nível pode ser acesso completo, somente para leitura ou bloqueado.
24 3.2 Projeto 14 O nível de acesso completo permite que os demais abram, removam ou atualizem o arquivo. Para o nível de leitura, apenas a opção de abrir é liberada, enquanto que para o bloqueado nenhuma opção está disponível. O proprietário sempre possui nível de acesso completo de seus dados. O nível de permissão deve ser aplicado diretamente ao dado desejado, não é possível atribuir níveis de permissão para os diretórios do sistema. Está limitação existe, pois não é eficiente verificar a permissão de cada inode dos diretórios da estrutura de um arquivo com o objetivo de liberar cada uma das ações dos usuários. Diagrama UML Figura 3: Diagrama de casos de uso A figura 3 mostra os possíveis casos de uso de um usuário para com o sistema. A modelagem UML completa é encontrada no apêndice B.
25 3.3 Implementação Implementação Alguns dos pontos descritos na seção Projeto foram implementados gerando um protótipo do sistema. O intuito deste desenvolvimento foi verificar a viabilidade do projeto e a realização de testes. O sistema foi escrito na linguagem de programação JAVA com apoio das classes nativas de sockets, sem a utilização de API externas. Das funcionalidades propostas, o sistema implementado está focado no núcleo do projeto, a interação dos clientes com os arquivos e diretórios do sistema. Os requisitos desenvolvidos foram transparência e configuração funcional simétrica. A implementação possui programas específicos para cada ação do cliente e um módulo de múltiplas threads para os servidores. Estão disponíveis para o cliente as ações de abrir arquivos, em que o dado requisitado é carregado do sistema para a estação do cliente, gravar um arquivo, onde um novo arquivo é enviado para o sistema, a ação de remover um arquivo e de listar o conteúdo de diretórios. O programa para os servidores possui métodos para a criação e manutenção da DHT, montando uma tabela de nós servidores. Estes também contêm métodos para atender a cada uma das ações dos clientes descritas anteriormente. O controle dos dados do sistema é realizado através de arquivos de meta-dados, denominados inode. Os inodes são gerenciados pelos servidores e contém informações sobre um arquivo ou diretório Sistema distribuído O elemento do sistema executado pelos nós da DHT, constitui um programa denominado nodht responsável pelo gerenciamento dos dados, atendimento das requisições dos clientes e realização de manutenções e consultas na DHT. Para tanto este programa é divido em duas threads. A primeira contém os códigos específicos para o tratamento das ações solicitadas pelos clientes do sistema. Ao ser iniciada, esta cria um socket TCP/IP na porta O número desta porta é comum a todos e assim os usuários não necessitam fornecê-la para se conectar a um servidor. A segunda thread é destinada apenas às requisições dos outros nós da DHT, como os métodos de entrada e saída da DHT e o gerenciamento dos diretórios do sistema. Esta
26 3.3 Implementação 16 inicia um socket também TCP/IP na porta Manutenção da DHT A DHT começa a ser montada quando o primeiro nó servidor é iniciado. Este, sabendo desta situação, apenas acrescenta seu endereço IP a recém criada DHT e aguarda por requisições. Exemplo: java nodht Este comando é utilizado para iniciar o primeiro nó da DHT. Ao iniciar os demais nós é preciso fornecer o endereço IP de um nó já pertencente da DHT. Este novo nó recebe da máquina indicada a cópia da DHT contendo a lista das máquinas existentes no sistema. O nó atualiza a sua lista com seu próprio endereço IP e envia uma mensagem para todos os nós indicados na DHT, solicitando que o adicionem em suas tabelas. Exemplo: java nodht Este comando inicia um novo nó servidor solicitando a DHT para o nó Antes de deixar o sistema, um nó avisa todos os outros, para que estes o removam da DHT. Não foi implementado métodos para detectar que um nó deixou a DHT sem avisar os demais DHT Chord Para auxiliar no desenvolvimento foi analisado o emprego da API OpenChord (LO- ESING; KAFFILLE, 2008), este fornece os métodos descritos em Stoica et al. (2001). O OpenChord é uma implementação de código aberto em linguagem JAVA e está disponível gratuitamente sob a licença GNU GPL, o desenvolvimento é do Distributed and Mobile Systems Group da Universidade de Bamberg. Porém optou-se por implementar as funcionalidades da DHT ao invés de utilizar o OpenChord pois esta se trata de uma API completa e extensa, incorporando muitos recursos além do necessário para o desenvolvimento deste projeto. O módulo da DHT foi desenvolvido desde o início baseado-se nas documentações oficiais. Esta construção tem como vantagem que o resultado final é uma implementação enxuta e otimizada para a finalidade.
27 3.3 Implementação 17 Este módulo construído não implementa o conceito de tabela de derivação, onde cada nó conhece apenas um número limitado de outros nós, mas sim, cada nó mantém uma relação de todos os nós da rede. Está decisão teve como base o tempo de desenvolvimento desta característica do Chord, preferiu-se dedicar os recursos disponíveis para a criação do projeto em si. Geração de chaves A construção do módulo da DHT também exigiu o desenvolvimento de um algoritmo para geração de chaves. Assim como a API OpenChord, a chave é gerada através da função SHA1 (JONES, 2001). Ao submeter uma seqüência de bits para a função SHA1 é obtido um hash de 160 bits, comumente tratado como uma seqüência de letras e números, como o Chord faz comparações entre as chaves (maior ou menor), o valor gerado pelo SHA1 recebe um tratamento removendo todas as letras e truncando o resultado em cinco caracteres. O resultado é sempre um número inteiro de zero a O valor obtido é associado ao nó ou a um dado do sistema na DHT, que por essa característica tem um espaço de endereço de cem mil posições. Para as chaves relacionadas aos nós, o valor enviado a função é um texto constituído de seu endereço IP no formato de quatro grupos de números separados por pontos. Pelos testes realizados, a função SHA1 garante a diversidade das chaves, mesmo com pouca variação entre um endereço e outro. Para os arquivos, a geração das chaves utiliza o caminho completo mais o nome do arquivo. O mesmo processo é feito para os diretórios, a chave é obtida através da estrutura completa até o referido diretório Gerenciamento dos diretórios Não existem diretórios reais no sistema distribuídos, sua existência é mapeada através de arquivos de controle denominados inode. Os inodes são arquivos de texto tratados pela DHT como arquivos convencionais, ou seja, possui uma chave e um nó responsável, porém os servidores utilizam-se destes para o controle da árvore de diretório do sistema. Quando um cliente envia um novo arquivo, este indica em qual diretório deseja armazenar o novo dado. Assim enquanto o servidor responsável recebe os dados binários através da conexão com o cliente, outras conexões são abertas para os nós responsáveis
28 3.3 Implementação 18 por cada nível da estrutura fornecida pelo usuário. Por exemplo, quando o cliente solicita gravar um novo arquivo no diretório /home/usuario, o servidor responsável terá que enviar uma requisição para outros três servidores, o responsável pelo diretório raiz /, outra para o responsável pelo /home e por último para o responsável pelo /home/usuario. Estes nós verificam a necessidade criar o inode correspondente àquele diretório e em seguida, escrevem o seu conteúdo (nome do arquivo ou do próximo diretório). O nome do inode é constituído do prefixo i mais o valor de sua chave e o nome do diretório. Continuando o exemplo anterior, o nó responsável por /home, deve possuir um arquivo de controle com o nome i home e conteúdo uma linha com a palavra usuario. Desta forma o conteúdo gravado em um inode de diretório é a lista de seus arquivos e subdiretórios, assim quando o usuário utiliza o comando listar o nó responsável pelo diretório lhe envia o conteúdo do inode Interface com o usuário Todas as interações dos clientes com o sistema são feitas através de programas executados em linha de comando. Para o cliente é transparente a existência de um conjunto de servidores que gerencia o sistema distribuído, mas é preciso informar em qual máquina servidora o cliente irá se conectar. Todo os nós da DHT tem a capacidade de atender a essas requisições. No início de cada comando do cliente, o servidor indicado manualmente tem a função de consultar a DHT e responder aos programas clientes qual o endereço IP do servidor responsável pelo dado requisitado. Desta forma uma nova conexão é aberta entre o cliente o servidor responsável e assim só assim executada a ação específica. Estão disponíveis aos clientes as ações de abrir, gravar, remover e listar. Com o comando abrir o cliente solicita um arquivo específico do sistema para ser carregado em sua máquina local e assim ter acesso a seu conteúdo. O comando possui dois parâmetros, o endereço IP de um dos servidores e o caminho completo do arquivo desejado. Exemplo: java abrir /home/usuario/documento.pdf Com isso o programa abrir após receber de o endereço IP do servidor
29 3.3 Implementação 19 responsável por /home/usuario/documento.pdf estabelece uma nova conexão para receber o arquivo binário. Com o comando gravar o cliente indica um arquivo local para ser submetido para o sistema distribuído. O comando possui três parâmetros, o endereço IP de um dos servidores, o arquivo local que deseja enviar para o sistema e o caminho completo do diretório destino. Exemplo: java gravar c:\usuario\filme.avi /home/usuario Neste caso a máquina após receber todos os parâmetros, realiza uma concatenação do diretório destino com o nome do arquivo (/home/usuario/filme.avi) para assim consultar na DHT qual será o servidor responsável por aquele novo arquivo. Na seqüência o programa gravar estabelece uma conexão com o endereço IP recebido e envia o arquivo binário para o servidor responsável. Com o comando remover o cliente envia um pedido para que um arquivo remoto seja excluído do sistema. O comando possui dois parâmetros, o endereço IP de um dos servidores e o caminho completo do arquivo. Exemplo: java remover /home/usuario/documento.pdf Logo após receber o endereço IP do responsável, o programa remover solicita a este servidor para que o dado /home/usuario/documento.pdf seja removido. Com o comando listar o cliente solicita um visualizar o conteúdo de determinado diretório do sistema. O comando possui dois parâmetros, o endereço IP de um dos servidores e o caminho completo do diretório. Exemplo: java listar /home/usuario A máquina deve consultar na DHT o responsável pelo diretório /home /usuario, este responsável possui um arquivo de controle (inode) referente a esse diretório contendo o nome de seus arquivos e subdiretórios. O endereço IP do servidor responsável é retornado para o programa listar que após realizar a nova conexão recebe o conteúdo do arquivo de controle, ou seja, a lista com os nomes dos subdiretórios e arquivos do diretório requisitado.
30 3.4 Testes Testes Foram realizados testes qualitativos para avaliar as funcionalidades do projeto. O ambiente de teste foi um PC com processador AMD Turion 1.6 GHz com 2 GB de memória RAM e sistema operacional Windows XP SP 3. Pela necessidade dos testes exigirem um considerável número de estações, a rede foi construída através de virtualização utilizando o software Microsoft Virtual PC 2007 SP1. Todas as máquinas virtuais possuíam 128 megabytes de memória RAM e Windows XP Service Pack 3 com o Java Runtime Environment Simultaneamente eram executadas quatro máquinas virtuais, cada uma com um endereço IP e executando o programa nodht. Os primeiros testes focaram a construção e manutenção da DHT por parte dos servidores. Devido à característica do ambiente de teste, as rotinas de entrada e saída de nós mostram-se eficiente para uma DHT de quatro máquinas. Para este, os resultados são: Todas as máquinas, sem considerar a ordem de entrada na DHT, são capazes de controlar a entrada de um novo nó servidor. A saída do primeiro nó não causou instabilidades na DHT. Não é importante a quantidade de vezes que uma máquina deixa e retorna ao sistema. Para os testes com as ações da interface cliente, a DHT era constituída de quatro máquinas servidoras e uma delas também executava o software cliente. Todos os métodos implementados (gravar, abrir, remover) foram alvos de teste. Resultados obtidos: A gravação de um arquivo de bytes (3,48 megabytes) foi executada na ordem de 3 segundos. Para um arquivo de bytes (121 megabytes) a ação foi finalizada na ordem de 1 minuto. A ação de abrir, ou seja, enviar um arquivo do servidor ao cliente, para o menor arquivo foi executada na ordem de 3 segundos e 59 segundos para o maior. A ação de remoção por parte do cliente funciona de maneira satisfatória.
31 3.4 Testes 21 Não foram detectados problemas nas transferências de dados em formato de texto ou binário. O sistema notifica o cliente caso as ações de abrir ou remover sejam solicitadas para dados não presentes no sistema. A ação de gravar não avisa o cliente caso o arquivo já exista na estrutura de diretórios informada, causando a sobreposição do dado.
32 22 4 CONCLUSÃO Uma vez analisadas diversas arquiteturas de sistemas de arquivos distribuidos, elaborada a documentação de um projeto e executados a implementação e testes de um protótipo, obtiveram-se resultados que permitem apresentar as seguintes conclusões: As atuais tecnologias e estudos na área de sistema de arquivos distribuídos encontramse em avançado nível de desenvolvimento fornecendo uma grande quantidade de projetos e soluções para o desenvolvimento de aplicações nesta área. No que tange à elaboração do projeto com o detalhamento dos recursos e diagramas, foram descritos todos os requisitos levantados com suas dependências e relacionamentos e construído a documentação na linguagem UML. O protótipo desenvolvido com o objetivo de estruturar uma DHT e fornecendo recursos para gerenciar os arquivos dos clientes atendeu os requisitos propostos e de acordo com os testes realizados confirmou a eficácia do projeto. Conclui-se, em vista do exposto, que a tecnologia DHT mostra-se viável para o desenvolvimento de sistemas de arquivos distribuídos. Trabalhos futuros Alguns pontos deste projeto não foram implementados em sua totalidade, utilizando a documentação elaborada é possível concluir a construção do sistema. Ressaltando itens como o módulo da DHT, onde cabe desenvolver a finger table do Chord (STOICA et al., 2001), as funcionalidades de replicação, fragmentação e segurança, e a interface cliente, construindo uma aplicação gráfica mais amigável. Outro foco para novos trabalhos é a pesquisa e testes para a utilização no sistema de outras implementações de tabelas hash distribuídas, como a CAN (RATNASAMY et al., 2001) e Pastry (CASTRO et al., 2003).
33 23 APÊNDICE A -- Tabela comparativa dos sistemas de arquivo distribuídos citados. A tabela 1 apresenta uma comparativa entre as principais características dos sistemas NFS AFS CODA SPRITE GFS Replicação Ruim: Somente Leitura (somente diretórios) Ruim: Somente Leitura (somente diretórios) Boa: A carga é distribuídas entre clientes Ruim: Somente Leitura (somente diretórios) Excelente: Porções são distribuídas entre diferentes servidores Consistência Ruim: Acesso simultâneo gera resultados imprevisíveis Razoável: Semântica sessão da Ruim: Semântica da sessão enfraquecida Excelente: Semântica Unix do Boa: Adequado a sua finalidade Excelente: Ideal para WANs com baixo grau da compartilhamento Excelente: Ideal para WANs com baixo grau da compartilhamento Ruim: O protocolo requer broadcasts Escalabilidade Ruim: Rápida saturação dos servidores Excelente: Organização em clusters Performance Ruim: Protocolo ineficiente Razoável: Grande latência para arquivos não armazenados em cache Boa: Procura por réplica mais próxima Boa: Implementação do kernel. Atualização atrasada. Grandes cache Boa: Performance otimizada para arquivos grandes Persistência em caso de falhas Ruim: Gravações atrasadas podem causar perda de dados Boa: Ferramentas de backup automáticos Boa Ruim: Longos atrasos nas gravações podem causar perda de dados Boa: Recuperação rápida e replicação de dados - simples e eficiente des- Disponibilidade Ruim Ruim Excelente: Operações conectadas Razoável: Rápida recuperação de falhas Excelente: Replicação dos dados dos servidores de porções Segurança Ruim: Servidores confiam nos clientes Boa: Lista de controle de acesso. Autenticação entre cliente e servidores. Boa: Lista de controle de acesso. Autenticação entre cliente e servidores. Ruim: Servidores confiam nos clientes Usuários não têm acesso direto ao sistema Localização do cache do cliente Memória Disco Disco Memória Disco Plataformas Todas as principais Estações SGI, HP, Nest, DCE, IBM, SUN e VAX IBM RT, estações DEC e IBM PC Estações SPARC e DEC IBM PC Características de Hardware Permitir sem disco clientes - Permite computadores portáteis. Replicação requer servidores extras. Permitir sem disco clientes Utilização de servidores de baixo custo Tabela 1: Tabela comparativa dos sistemas de arquivo distribuídos.
34 24 APÊNDICE B -- Diagramas UML B.1 Diagrama de classes Figura 4: Relação entre as principais classes do projeto