U NIVERSIDADE DE L ISBOA
Faculdade de Ciências
Departamento de Informática
SUBSTRATO DE COORDENAÇÃO E SERVIÇO DE
DIRECTORIAS PARA SISTEMAS DE FICHEIROS
SEGUROS PARA CLOUD-OF-CLOUDS
Ricardo Samuel Portinha Mendes
DISSERTAÇÃO
MESTRADO EM ENGENHARIA INFORMÁTICA
Especialização em Arquitectura, Sistemas e Redes de Computadores
2012
U NIVERSIDADE DE L ISBOA
Faculdade de Ciências
Departamento de Informática
SUBSTRATO DE COORDENAÇÃO E SERVIÇO DE
DIRECTORIAS PARA SISTEMAS DE FICHEIROS
SEGUROS PARA CLOUD-OF-CLOUDS
Ricardo Samuel Portinha Mendes
DISSERTAÇÃO
Dissertação orientada pelo Prof. Doutor Alysson Neves Bessani
e co-orientada pelo Prof. Doutor Marcelo Pasin
MESTRADO EM ENGENHARIA INFORMÁTICA
Especialização em Arquitectura, Sistemas e Redes de Computadores
2012
Agradecimentos
Em primeiro lugar quero expressar, não só o meu agradecimento, mas também a minha
admiração para com os meus orientadores, o Prof. Alysson Bessani e o Prof. Marcelo
Pasin pois, para além da enorme quantidade de conhecimento que tive o privilégio de
receber destes, é admirável a relação informal e descontraída que mantiveram durante
este ano, proporcionando um ambiente perfeito para o debate de ideias. É de louvar o
facto de terem mantido sempre a porta dos seus gabinetes aberta para me receber, a mim
e às minhas dúvidas. A eles o meu muito obrigado.
Em segundo lugar, quero agradecer também à minha família, nomeadamente aos meus
pais e irmãos, por me passarem os valores pelos quais me rejo em todas as minhas decisões. Um agradecimento também à família Gomes pelo apoio e carinho com que me
têm brindado nestes últimos anos.
Quero agradecer de uma forma muito especial ao Tiago Oliveira, pelas muitas ideias
discutidas no processo de desenvolvimento do trabalho apresentado neste documento, e
pelo companheiro e amigo que tem sido durante todos estes anos.
No meu percurso académico conheci muitas pessoas, algumas delas que, estou certo,
ficarão para sempre como bons amigos. Um agradecimento ao Zabibo, Tó Zé, Fernandinho, Reis, Rui Teixeira, Guns e Panka pelos muitos momentos bem passados que me
proporcionaram durante estes anos. Ao João Martins, um grande amigo e parceiro de
trabalhos durante a licenciatura e início de mestrado, um muito obrigado por tudo.
Agradeço também aos meus grandes amigos da minha terra natal. Ao Mário, ao
Careca, ao “meu gordinho”, ao Chico, ao Varela, ao Fernando e à minha Cristininha,
um muito obrigado pelos muitos momentos épicos que temos passado e pela força em
momentos menos bons.
Um agradecimento especial ao Diogo que, como um grande amigo que é, me ajudou
no tratamento dos resultados apresentados na secção de avaliação deste documento.
Por fim, mas de maneira nenhuma menos importante, um muito obrigado à minha
namorada Inês que, mesmo com a minha falta de tempo, me congratula sempre com um
sorriso e boa disposição. Um muito obrigado pelo apoio incondicional, pelo carinho e
pelo suporte.
A todos estes e aos demais que de alguma forma possam ter contribuído para o meu
sucesso, o meu mais sincero obrigado.
iii
À minha Inês e à minha Carolina.
Resumo
O C2FS (Cloud-of-Clouds File System) é um sistema de ficheiros distribuído que
fornece aos programadores uma interface POSIX, e que tem por objectivo armazenar os
dados numa cloud-of-clouds, utilizando vários provedores de armazenamento nas clouds
ao invés de apenas um para aumentar a disponibilidade e privacidade dos dados.
Este projecto visa desenvolver dois dos serviços do C2FS: um serviço de directorias
distribuído, que ofereça confidencialidade e disponibilidade dos metadados, controlo de
acesso aos mesmos por parte de vários utilizadores e fortes garantias de tolerância a faltas;
e um serviço de locks para coordenar o acesso aos ficheiros do sistema por parte de vários
processos escritores, de forma a garantir a consistência destes ficheiros.
Estes componentes do C2FS usam o DepSpace, um serviço de coordenação tolerante
a faltas bizantinas que fornece uma abstracção de espaço de tuplos. Para a sua implementação foi necessário alterar a API e arquitectura deste serviço, adicionando uma nova
operação que permite a substituição de tuplos e uma camada de suporte a Triggers.
Por questões de desempenho foram ainda desenvolvidas duas variações do serviço
de directorias: uma que mantém, temporariamente, os metadados utilizados em cache, e
outra para a utilização do sistema sem partilha de ficheiros. Para além disso foi desenvolvido um mecanismo, chamado espaço de nomes pessoal, que permite, para além de
aumentar o desempenho do serviço de directorias, diminuir a quantidade de informação
mantida pelo mesmo.
Neste projecto, foi também desenvolvido um mecanismo que permite ao C2FS fornecer
garantias de consistência forte mesmo recorrendo a clouds de armazenamento que fornecem
apenas consistência eventual.
Foi ainda feita uma avaliação experimental que permite perceber, em termos de desempenho, qual é o custo de utilizar um serviço de coordenação para armazenar os metadados do sistema de ficheiros e se esse custo pode ser minimizado através do uso de uma
cache de metadados.
Palavras-chave: sistema de ficheiros, computação em clouds, armazenamento nas
clouds, tolerância a faltas bizantinas.
vii
Abstract
C2FS (Cloud-of-Clouds File System) is a distributed file system that allows developers to take advantage of its POSIX-like interface. It store file system data in a cloud-ofclouds, using several cloud storage providers (instead of only one) to improve the privacy
and availability of the data.
The goals of this project are to develop two services to C2FS: a distributed and fault
tolerant directory service, which maintain the C2FS’s metadata, ensuring its confidentiality, availability, and providing access control to this metadata by various users; and a
lock service to coordinate the accesses to files by several writers in order to ensure the
consistency of shared files.
This service uses DepSpace, a Byzantine fault tolerant coordination service that provides a tuple space abstraction. To implement these services it was necessary to change
the API and architecture of DepSpace, adding a new operation to replace tuples and support of triggers.
For performance reasons it was developed two directory service variations: one that
temporarily maintains the metadata used in cache, and another that allows users to use
the system without file sharing. Besides this, it was developed a mechanism, called personal namespace, that decrease the amount of data stored by the service, increasing its
performance for accessing non-shared files.
In this project was also developed a mechanism that allows C2FS to provide strong
consistency guaranties, even if cloud storage providers (used by the system to store its
data) provide only eventual consistency guaranties.
Finally, it was made an experimental evaluation in order to understand, in terms of performance, what is the cost of use a coordination service to store the file system metadata
and if that cost can be minimized through the use of a metadata cache.
Keywords: file system, cloud computing, cloud storage, Byzantine fault tolerance.
ix
Conteúdo
Lista de Figuras
xv
Lista de Tabelas
xvii
1
2
Introdução
1.1 Motivação . . . . . . . .
1.2 Objectivos . . . . . . . .
1.3 Contribuições . . . . . .
1.4 Publicações . . . . . . .
1.5 Planeamento . . . . . . .
1.6 Estrutura do Documento
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Trabalhos Relacionados
2.1 Serviços de Coordenação . . . . . . . . .
2.1.1 Chubby . . . . . . . . . . . . . .
2.1.2 Zookeeper . . . . . . . . . . . .
2.1.3 DepSpace . . . . . . . . . . . . .
2.1.4 Discussão . . . . . . . . . . . . .
2.2 Sistemas de Ficheiros Distribuídos . . . .
2.2.1 Ceph . . . . . . . . . . . . . . .
2.2.2 WheelFS . . . . . . . . . . . . .
2.2.3 Frangipani . . . . . . . . . . . .
2.2.4 Andrew File System . . . . . . .
2.2.5 Coda . . . . . . . . . . . . . . .
2.2.6 Farsite . . . . . . . . . . . . . . .
2.3 Sistemas de Ficheiros para Clouds . . . .
2.3.1 Frugal Cloud File System - FCFS
2.3.2 BlueSky . . . . . . . . . . . . . .
2.3.3 S3FS . . . . . . . . . . . . . . .
2.3.4 S3QL . . . . . . . . . . . . . . .
2.4 Considerações Finais . . . . . . . . . . .
xi
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
2
3
3
4
4
5
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
7
7
8
9
10
12
12
12
14
15
16
18
20
21
22
23
24
25
26
3
4
5
6
Metadados e Locks no C2FS
3.1 C2FS . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 Arquitectura Geral . . . . . . . . . . . . . . . .
3.1.2 Modelo de Sistema . . . . . . . . . . . . . . . .
3.2 Metadados . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1 DepSpace . . . . . . . . . . . . . . . . . . . . .
3.2.2 Serviço de Directorias . . . . . . . . . . . . . .
3.2.3 Cache no Serviço de Directorias . . . . . . . . .
3.2.4 Espaço de Nomes Pessoal . . . . . . . . . . . .
3.2.5 Serviço de Directorias sem Partilha de Ficheiros
3.3 Serviço de Locks . . . . . . . . . . . . . . . . . . . . .
3.4 Consistência no C2FS . . . . . . . . . . . . . . . . . . .
3.5 Considerações Finais . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
27
27
27
30
31
31
33
36
40
41
42
44
46
.
.
.
.
.
.
47
47
49
51
51
52
57
.
.
.
.
.
.
59
59
60
61
65
66
68
Conclusão
6.1 Trabalho futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
69
70
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Concretização dos Serviços de Directorias e de Locks do C2FS
4.1 Considerações Gerais . . . . . . . . . . . . . . . . . . . . .
4.2 Trigger de Substituição de Tuplos no DepSpace . . . . . . .
4.3 Diagramas UML . . . . . . . . . . . . . . . . . . . . . . .
4.3.1 Diagrama de Classes . . . . . . . . . . . . . . . . .
4.3.2 Diagramas de Sequência . . . . . . . . . . . . . . .
4.3.3 Considerações Finais . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Avaliação Experimental
5.1 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2 Número de Operações sobre os Metadados . . . . . . . . . . . .
5.3 Desempenho dos Serviços de Directorias e Locks . . . . . . . .
5.4 Desempenho do Serviço de Directorias sem Partilha de Ficheiros
5.5 Desempenho com a utilização do Espaço de Nomes Pessoal . . .
5.6 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
A Prova Informal do Serviço de Trincos
71
Bibliografia
78
xii
xiv
Lista de Figuras
2.1
2.2
2.3
2.4
2.5
2.6
Serviço de coordenação e serviço de comunicação em grupo.
Arquitectura do Ceph [54]. . . . . . . . . . . . . . . . . . .
Arquitectura do Frangipani. . . . . . . . . . . . . . . . . . .
Arquitectura do AFS. . . . . . . . . . . . . . . . . . . . . .
Arquitectura do BlueSky. . . . . . . . . . . . . . . . . . . .
Arquitectura do S3FS. . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
7
13
15
17
23
25
3.1
3.2
Arquitectura do C2FS. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Cloud-of-clouds. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
29
4.1
4.2
4.3
4.4
Diagrama de classes dos serviços de directorias e locks. . . . . . . . . .
Diagrama de sequência de uma operação inserção de metadados . . . .
Diagrama de sequência de uma operação de obtenção de metadados. . .
Diagrama de sequência de uma operação de actualização de metadados.
.
.
.
.
53
54
55
56
5.1
5.2
5.3
5.4
5.5
Latência das operações do DepSpace. . . . . . . . . . . . .
Latência da obtenção de metadados. . . . . . . . . . . . . .
Latência das operações do sistema de ficheiros. . . . . . . .
Tempo de execução de benchmarks. . . . . . . . . . . . . .
Latências de operações sobre o C2FS e tempos de execução
marks usando o serviço de directorias sem partilha. . . . . .
Latências de operações sobre o C2FS e tempos de execução
marks com ficheiros pessoais. . . . . . . . . . . . . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
. . . . . . .
dos bench. . . . . . .
dos bench. . . . . . .
62
63
64
65
5.6
xv
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
66
67
Lista de Tabelas
3.1
Interacção do serviço de directorias com o DepSpace. . . . . . . . . . . .
34
4.1
Número de linhas de código dos módulos desenvolvidos. . . . . . . . . .
49
5.1
Número de operações do sistema de ficheiros chamadas pelos benchmarks. 61
xvii
Capítulo 1
Introdução
A popularização dos serviços de armazenamento em clouds tem levado alguns utilizadores e empresas a exteriorizar o armazenamento dos seus dados, tirando partido de
todas as vantagens que a utilização destes serviços fornece, como por exemplo a facilidade
de acesso, o modelo de pagamento consoante o uso e ainda a ausência de investimento
inicial. Exemplos deste tipo de serviços são o DropBox [6], GoogleDrive [12], iCloud [5]
e o Amazon S3 [4].
A utilização destes serviços levanta, no entanto, problemas no que diz respeito à
disponibilidade, integridade e privacidade dos dados. Problemas como a indisponibilidade do provedor usado para armazenar os dados (ou da ligação até ele), o acesso irrestrito
por parte do deste aos dados que armazena ou a possibilidade de o mesmo corromper os
dados devido a faltas na sua infraestrutura (sejam estas maliciosas ou não), tornam inviável a utilização destes serviços para armazenar dados sensíveis ou críticos. Há ainda
um problema relacionado com o preço do serviço prestado pelos provedores. Estes podem aumentar o preço do serviço de tal forma que se torne impossível ao utilizador retirar
de lá os seus dados, fenómeno este conhecido por vendor lock-in [21]. Uma outra questão
a ser levantada está relacionada com o modelo de acesso a este serviço por parte das
aplicações. Nos dias de hoje, o modelo mais comummente usado pelos provedores de
armazenamento para permitir às aplicações manusear dados na cloud é a disponibilização
de serviços web como o REST, SOAP ou XML-RPC que, embora não obriguem à troca
explícita de mensagens, são sobretudo orientados ao controlo ao invés de orientados aos
dados. Há ainda uma limitação importante relacionada com as garantias de consistência oferecidas por estes serviços. A maioria dos serviços deste género fornece apenas
garantias de consistência eventual [51].
Tal como no caso dos serviços de armazenamento, também a crescente popularidade
dos serviços de computação nas clouds tem levado os utilizadores e empresas a migrar
as suas aplicações para as clouds. A ausência de investimento inicial e de custos de
manutenção com as máquinas, a possibilidade de adequar as características das máquinas
utilizadas às necessidades da aplicação que estas correm, assim como o facto de não haver
1
Capítulo 1. Introdução
2
preocupação com upgrades nas máquinas que, com o tempo, vão ficando obsoletas, são
bons atractivos para quem deseja correr as suas aplicações de forma eficiente e barata.
Exemplos deste tipo de serviços são o Google App Engine [10], Microsoft Windows
Azure [13] e o Amazon EC2 [2].
No entanto, para que não tenhamos de confiar na segurança e fiabilidade das infraestruturas dos provedores do serviço de computação, é necessário que haja uma preocupação extra com segurança e tolerância a faltas na construção das aplicações a serem
instaladas nestes serviços.
1.1
Motivação
A equipa dos Navigators está envolvida num projecto europeu chamado TClouds [17]
que tem, entre outros, o objectivo de mitigar todas as limitações descritas na secção anterior. Neste âmbito foi recentemente desenvolvido o DepSky [24], um sistema que prova
ser possível reduzir os referidos problemas através do uso de múltiplos provedores independentes, aliado a técnicas de tolerância a faltas e criptografia. Este sistema permite armazenar objectos (blocos opacos de dados associados a uma chave de acesso)
numa cloud-of-clouds composta por vários provedores de tal forma que os dados sejam
acessíveis e privados mesmo que uma fracção dos provedores estejam sujeitos a faltas bizantinas (exibindo um comportamento arbitrário, fora da sua especificação) [36].
Porém, o DepSky disponibiliza uma interface de baixo nível que se assemelha a um disco
virtual, disco este utilizado para armazenar blocos de dados.
Embora exista um leque muito grande de aplicações que podem tirar partido da interface ao nível do bloco disponibilizada pelo DepSky, esta interface é de difícil uso tanto
por programadores (que constroem aplicações com armazenamento de dados na cloud-ofclouds) quanto por utilizadores, que apenas querem guardar os seus ficheiros na cloud de
forma segura e fiável.
Dado isto, existe a necessidade de fornecer uma abstracção mais amigável que permita aos utilizadores e suas aplicações armazenar dados na cloud-of-clouds, minimizando
alterações nas aplicações e o esforço de aprendizagem por parte dos utilizadores. Uma
abstracção que mitiga estas necessidades é a abstracção de sistema de ficheiros, na qual
os utilizadores tendem a sentir-se confortáveis.
A ideia de armazenar os dados nas clouds já foi concretizada por outros sistemas de
ficheiros. Alguns exemplos são o S3FS [18], o S3QL [19], o BlueSky [52] e o FCFS [42].
No entanto, estes sistemas têm a limitação de usar apenas um provedor de armazenamento
na cloud, dependendo do mesmo nos vários aspectos referidos anteriormente (fiabilidade,
disponibilidade, politicas de acesso, custos, entre outros).
Neste âmbito, surgiu o desafio de desenvolver um sistema de ficheiros distribuído
tolerante a faltas bizantinas, tanto por parte das infraestruturas que armazenam os dados
Capítulo 1. Introdução
3
como das que armazenam os metadados, que permita a partilha de ficheiros controlada,
que não exija confiança em nenhuma cloud de armazenamento individualmente e que
forneça a garantia de consistência forte. A este sistema de ficheiros foi dado o nome de
C2FS (Cloud-of-Clouds File System).
1.2
Objectivos
Os objectivos deste trabalho foram desenvolver um serviço de directorias e um serviço
de locks para o C2FS, mostrar que estes serviços têm um desempenho aceitável, e ainda
desenvolver um mecanismo que permita ao sistema oferecer a garantia de consistência
forte mesmo recorrendo a clouds de armazenamento que fornecem apenas consistência
eventual.
O serviço de directorias é responsável por armazenar os metadados do sistema de
ficheiros e por efectuar controlo de acesso aos seus recursos, enquanto que o serviço de
locks é responsável por gerir escritas concorrentes sobre o mesmo ficheiro por parte de
diferentes utilizadores. Para que se possam cumprir os requisitos do C2FS, ambos os
serviços devem ser eficientes, seguros e tolerantes a faltas bizantinas.
Desta forma, a abordagem utilizada foi instalar um serviço de coordenação evoluído
nas clouds de computação (como a Amazon EC2) e tirar vantagem desse serviço para
desenvolver os serviços de armazenamento e de locks. A utilização desta abordagem
justifica-se com o facto de os serviços de coordenação evoluídos permitirem implementar
várias premissas sobre eles, ao mesmo tempo que fornecem um bom desempenho e boas
garantias de tolerância a faltas.
Dadas as necessidades dos serviços já descritos, o serviço de coordenação escolhido
foi o DepSpace [23], um serviço de coordenação seguro e tolerante a faltas bizantinas que
fornece uma abstracção de espaço de tuplos. Assim, um outro objectivo deste trabalho
foi o estudo das limitações, estrutura e desempenho deste serviço de coordenação, assim
como, caso fosse necessário, a modificação do mesmo de acordo com as necessidades do
C2FS.
1.3
Contribuições
As principais contribuições desta dissertação são:
• A modificação do serviço de coordenação DepSpace de forma a este suportar operações de actualização de tuplos guardados no espaço.
• A modificação do DepSpace para que este suporte “Triggers” que executam várias
operações de actualização de tuplos de uma forma atómica.
Capítulo 1. Introdução
4
• Um serviço de directorias para o C2FS que tem por base o DepSpace. Este serviço
herda todas as garantias do DepSpace logo é seguro, fiável e tolerante a faltas
bizantinas. Para além de armazenar os metadados do C2FS, o serviço de directorias faz controlo de acesso aos recursos do sistema e permite reduzir o número de
operações feitas ao DepSpace (através do uso de uma cache de metadados).
• Um serviço de locks fiável, também ele desenvolvido tendo o DepSpace como base,
que é usado pelo C2FS para coordenar escritas concorrentes de vários utilizadores
sobre o mesmo ficheiro.
• A integração destes serviços com outros módulos do C2FS (como o serviço de
armazenamento [40]) em desenvolvimento paralelamente a este trabalho.
• Um mecanismo que permite ao C2FS fornecer uma semântica de consistência forte,
mesmo estando assente sobre clouds que fornecem consistência eventual.
• Avaliação experimental dos módulos desenvolvidos com benchmarks utilizados na
indústria.
1.4
Publicações
O trabalho descrito neste documento contribuiu para a publicação de um artigo científico no INForum 2012, na track “Computação Paralela, Distribuída e de Larga Escala” [38].
1.5
Planeamento
Inicialmente, o planeamento deste trabalho consistia nas seguintes tarefas:
• Tarefa 1 (Setembro de 2011): Revisão bibliográfica, estudo do DepSpace e familiarização com as tecnologias envolvidas na computação em clouds.
• Tarefa 2 (Outubro e Novembro de 2011): Desenho da abstracção de coordenação e
serviço de directorias para um sistema de ficheiros e estudo da sua integração num
protótipo. Modificação do DepSpace para que este possa suportar as abstracções
desenhadas.
• Tarefa 3 (Dezembro de 2011 e Janeiro de 2012): Concretização dos serviços de coordenação e directorias para um sistema de ficheiros para cloud-of-clouds utilizando
a nova versão do DepSpace. Integração do trabalho feito com outros mecanismos,
como por exemplo o armazenamento. Concretização do primeiro protótipo do sistema de ficheiros para cloud-of-clouds.
Capítulo 1. Introdução
5
• Tarefa 4 (Fevereiro de 2012): Instalação dos servidores do DepSpace nas clouds.
Concretização do controlo de acesso no serviço de directorias usando a nova versão
do DepSpace, modificando-o se necessário.
• Tarefa 5 (Março de 2012): Estudo dos modelos de consistência e, caso exista um
modelo melhor, modificação do protótipo para integrar esse modelo.
• Tarefa 6 (Abril de 2012): Avaliação do sistema recorrendo a benchmarks para sistemas de ficheiros utilizados na indústria.
• Tarefa 7 (Maio de 2012): Escrita da tese e de um artigo científico para um workshop
ou conferência de médio porte.
Este planeamento foi cumprido sensivelmente como descrito, excepto no caso da
Tarefa 7. O início desta tarefa foi atrasado devido à necessidade de um esforço extra
para a conclusão da tarefa anterior, pois, para atingir melhores resultados nas medições
efectuadas, foram incluídas algumas tarefas de optimização do protótipo. Estas tarefas de
optimização resultaram numa melhoria de desempenho bastante assinalável.
1.6
Estrutura do Documento
Este documento está organizado da seguinte forma:
• Capítulo 2 – Este capítulo descreve o trabalho relacionado com os serviços desenvolvidos e com o sistema que irá fazer uso destes. Aqui são apresentados sistemas de ficheiros, serviços de coordenação, sistemas de ficheiros para clouds e um
serviço de directorias. Para todos eles são analisadas em especial detalhe todas as
características que mais se relacionem com o presente trabalho.
• Capítulo 3 – Aqui é apresentado o C2FS, a sua arquitectura e o seu funcionamento,
dando a conhecer o contexto no qual os serviços desenvolvidos são inseridos. São
também descritos detalhadamente os serviços de directorias e de locks, explicando o
seu funcionamento e potencialidades. É ainda explicado o mecanismo que permite
ao C2FS fornecer consistência forte. Por fim, é introduzido o conceito de Espaço
de Nomes Pessoal, a sua motivação e o seu funcionamento.
• Capítulo 4 – Apresentação dos detalhes de concretização do serviço de directorias
e de locks.
• Capítulo 5 – Este capítulo contém uma avaliação preliminar feita ao serviço de
directorias do C2FS. O comportamento deste é avaliado configurando a sua cache
de diferentes formas com vista a mostrar as vantagens e desvantagens do uso da
mesma.
Capítulo 1. Introdução
6
• Capítulo 6 – Neste último capítulo são apresentadas as conclusões retiradas deste
trabalho assim como algum trabalho a ser desenvolvido no futuro para melhorar as
garantias de consistência oferecidas pelo C2FS.
Capítulo 2
Trabalhos Relacionados
Nesta secção serão apresentados vários sistemas que de alguma forma relacionam
com o trabalho desenvolvido. Serão apresentados em primeiro lugar alguns serviços de
coordenação, seguindo-se a apresentação de alguns sistemas de ficheiros distribuídos, um
serviço de directorias e ainda dois sistemas de ficheiros para clouds.
2.1
Serviços de Coordenação
Os serviços de coordenação são serviços com grande utilidade no âmbito dos sistemas
distribuídos pois permitem manter informação de controlo ou de configuração de vários
processos num sistema deste tipo. Permitem também fazer sincronização distribuída.
Desta forma, estes serviços permitem ao programador de aplicações distribuídas focar-se
mais no desenvolvimento da aplicação em si e não tanto no mecanismo de coordenação
entre os vários processos da sua aplicação, trazendo ganhos tanto no esforço necessário
no desenvolvimento deste tipo de aplicações como na fiabilidade das mesmas.
Figura 2.1: Serviço de coordenação e serviço de comunicação em grupo.
Na figura 2.1 podemos perceber a diferença existente entre um serviço de coordenação e um serviço de comunicação em grupo. Um serviço de comunicação em grupo,
nos moldes do Appia [39], consiste numa abstracção em que cada participante está apto
7
Capítulo 2. Trabalhos Relacionados
8
a enviar mensagens para todos os outros participantes de um grupo. Por outro lado, um
serviço de coordenação permite aos seus clientes, através da disponibilização de um objecto com poder de coordenação, a possibilidade de efectuar eleição de líder, partilhar
estado, detectar falhas e até trocar mensagens entre vários processos. Nesta secção serão
apresentados alguns destes serviços.
2.1.1
Chubby
O Chubby [26] é um serviço de locks para sistemas distribuídos fracamente acoplados
que tem como objectivo sincronizar as actividades de um grande número de clientes, ao
mesmo tempo que fornece boas garantias de disponibilidade e fiabilidade. Este serviço de
coordenação foi desenvolvido pelo Google e é utilizado no Google File System [29] para
fazer eleição de líder.
Este serviço de locks usa uma abstracção de sistema de ficheiros que permite aos
clientes guardar pequenas quantidades de informação, ou seja, criar pequenos ficheiros,
chamados nós. O uso desta abstracção reduz significativamente o esforço de aprendizagem dos programadores para a utilização deste serviço. Assim, o Chubby provê um conjunto de operações que podem ser chamadas recorrendo a um handle do Chubby. Este
handle é criado quando o cliente abre um ficheiro do serviço e destruído aquando do
fecho do mesmo. O Chubby apenas permite ao cliente ler e escrever o conteúdo de
um ficheiro na íntegra. Esta abordagem tem como objectivo desencorajar a criação de
ficheiros grandes.
Todos os nós do Chubby podem actuar como um lock, fornecendo este serviço dois
tipos de locks: os exclusivos e os partilhados, sendo que os locks exclusivos podem ser
usados para reservar recursos para escrita, enquanto que os partilhados para reservar um
qualquer recurso para leitura. Os locks são de granularidade elevada (são validos por
horas ou mesmo dias). Segundo os autores, esta abordagem explica-se com a dificuldade
de tolerar a falha dos servidores sem perder nenhum lock, aliado com a dificuldade de
transferir locks entre clientes.
A arquitectura do Chubby tem dois componentes principais, a biblioteca cliente e
os servidores, que comunicam entre si através de chamadas a procedimentos remotos
(RPC). Estes servidores são agrupados em células Chubby, sendo usada replicação entre
os servidores da célula para tolerar a falha de uma fracção destes. Cada célula Chubby
tem um líder responsável por tratar todos os pedidos que a sua célula recebe.
É possível, não só ao cliente perceber quando o servidor Chubby falha, mas também
ao servidor detectar a falha de um cliente detentor de um lock. Para isso, uma sessão temporária entre um cliente e uma célula Chubby é mantida através de mensagens KeepAlive
periódicas. Quando o líder falha, um novo líder é eleito, através de um protocolo de
consenso [35].
Para maximizar o desempenho, o serviço permite que clientes do Chubby guardem
Capítulo 2. Trabalhos Relacionados
9
os dados e metadados dos nós numa cache guardada em memória local. Para manter a
consistência das caches, as operações de escrita são bloqueadas pelos servidores até todos
os clientes serem notificados, e assim, invalidarem as suas caches.
Os clientes do Chubby podem também subscrever um conjunto de eventos. Quando
isto acontece, o cliente é notificado assincronamente quando a acção correspondente aos
eventos subscritos acontece.
O controlo de acesso é feito associando uma ACL (access control list) a cada ficheiro.
Esta lista mantém a informação de todos os utilizadores do serviço que estão aptos a ler e
escrever no ficheiro, assim como quais estão aptos a modificar as permissões do mesmo.
Por questões de persistência dos dados, com a frequência de poucas horas, o servidor
líder de cada célula faz um backup da base de dados da sua célula para um servidor de
ficheiros GFS [29].
2.1.2
Zookeeper
O Zookeeper [32] é um serviço de coordenação que fornece um pequeno conjunto de
primitivas simples e gerais para armazenamento e coordenação, permitindo aos clientes
criar primitivas de coordenação mais complexas como comunicação e gestão de grupos,
registos partilhados e serviços de locks distribuídos. Desta forma, ao invés de implementar primitivas de coordenação específicas, o Zookeeper fornece uma API que manipula
objectos de dados wait-free, simples e organizados hierarquicamente, permitindo aos programadores criar as suas próprias primitivas de uma forma eficiente e tolerante a faltas.
No entanto, a propriedade wait-free não é suficiente para fornecer coordenação. Devido a isto, este serviço fornece a possibilidade da utilização dos seus recursos com diferentes garantias de ordem, nomeadamente, ordem para todas as operações de um cliente
(FIFO) e ainda linearização para todos os pedidos que modifiquem o estado do sistema
(usando o protocolo Zab [43]).
Este serviço utiliza uma abstracção de espaço de nomes hierárquico “estilo sistema
de ficheiros”, onde uma colecção de objectos e dados, chamados znodes, são organizados
numa árvore. No entanto, os znodes não foram desenhados para guardar um tipo qualquer
de dados, mas sim alguma informação que pode ser útil numa computação distribuída,
como por exemplo, metadados ou informações de configuração. Os znodes podem ser de
dois tipos:
• os regulares, que após a sua criação necessitam ser eliminados explicitamente pelo
cliente.
• e os efémeros, que são eliminados pelo sistema quando a sessão com o cliente que
os criou termina (deliberadamente ou em caso de falha do cliente) ou podem ser
apagados pelo cliente explicitamente.
Capítulo 2. Trabalhos Relacionados
10
O Zookeeper implementa watches, um mecanismo dirigido a eventos que pode ser
subscrito pelos clientes. Este mecanismo permite ao cliente, após subscrição aos eventos
de um znode, receber notificações quando esse znode é modificado. Um exemplo da
utilidade deste mecanismo é a implementação da primitiva de invalidação de cache.
Para aumentar a disponibilidade, o serviço pode ser replicado entre várias máquinas.
Uma das réplicas é o líder, sendo esta responsável por coordenar as escritas, ao passo
que qualquer uma das réplicas pode responder de imediato a leituras. Periodicamente são
criados snapshots do estado do sistema. Estes snapshots são usados para, quando uma
máquina recupera após uma falha, recebe o snapshot com o estado do sistema, podendo
actualizar os seus dados localmente e, então, começar a atender pedidos dos clientes.
Para não ser necessário efectuar um snapshot a cada alteração do estado do sistema, este
snapshot é sempre acompanhado de uma lista das operações efectuadas após a criação do
snapshot mais actual. Note-se que este serviço assume apenas faltas por paragem e que
as réplicas podem recuperar.
Para permitir aos servidores perceber quando um cliente falha, este envia mensagens
chamadas heartbeats para manter a conexão aberta. Assim, quando o tempo sem receber nenhum heartbeat ou qualquer outra mensagem excede um timeout predefinido, o
servidor fecha a conexão, assumindo que o cliente falhou.
Os servidores resolvem todas as leituras usando um espaço de nomes hierárquico
guardado em memória. Este mecanismo ajuda o sistema a atingir um alto desempenho
em ambientes onde as leituras dominam sobre as escritas. Permite ainda que o serviço
seja altamente escalável no que diz respeito às leituras pois, visto cada servidor poder
resolver localmente qualquer leitura, a cada réplica adicionada ao serviço, a quantidade
de leituras suportadas aumenta. No entanto, por uma questão de durabilidade dos dados,
todas as escritas são feitas no disco local dos servidores Zookeeper antes de serem escritas
na cópia em memória volátil.
2.1.3
DepSpace
O DepSpace [23] é um serviço de coordenação tolerante a faltas bizantinas que fornece
uma abstracção de espaço de tuplos [20] e que suporta comunicação desacoplada no
tempo e no espaço. Um espaço de tuplos é um objecto de memória partilhada que provê
operações para manipular dados em estruturas, chamadas tuplos, que guardam um conjunto de campos de tipos genéricos. Existem dois tipos de tuplos: entries, que têm todos
os campos com valor definido; e templates, que têm alguns campos não definidos (representados com o wildcard ‘*’). Os templates são importantes porque permitem que os
tuplos sejam endereçados pelo seu conteúdo, sem necessariamente saber o valor de todos
os campos. Note-se que é ainda suportada a utilização de múltiplos espaços de tuplos.
Este serviço exporta um interface para os clientes que lhes permitindo operar sobre
o espaço de tuplos. Esta interface aos clientes ler, escrever e remover tuplos do espaço,
Capítulo 2. Trabalhos Relacionados
11
através da disponibilização das operações RD, OUT e IN respectivamente. As operações
de leitura e remoção de tuplos podem ainda ser executadas de forma assíncrona, através
das operações RDP e INP. Existe ainda uma operação chamada CAS (conditional atomic
swap) cuja semântica consiste em apenas inserir um determinado tuplo no espaço no caso
de não existir ainda nenhum tuplo que corresponda a um template dado. Esta operação
é importante pois fornece uma primitiva de coordenação que permite resolver problemas importantes como o consenso. Para isso, basta que cada cliente que tenha um valor
para propor tente inserir um tuplo no espaço com o valor da sua proposta utilizando a
operação CAS, sendo que o valor escolhido é o valor que permanece no espaço após todos os clientes terem feito a sua proposta. Esta interface e as garantias asseguradas pelo
DepSpace são apropriadas para coordenar clientes não confiáveis num sistema distribuído.
O DepSpace é constituído por um conjunto de servidores que, através da utilização de
vários mecanismos, garante a confidencialidade, disponibilidade e integridade dos tuplos
armazenados, mesmo na presença de servidores faltosos. Desta forma, o número de réplicas requeridas pelo DepSpace é de n ≥ 3f + 1, sendo n o número total de réplicas e f
o número de réplicas faltosas toleradas pelo serviço.
No que diz respeito à disponibilidade, é utilizada replicação para garantir que todos
os servidores do DepSpace mantêm o mesmo estado. A estratégia de replicação usada
é a replicação de máquina de estados (que garante linearização), juntamente com determinismo das réplicas e com o protocolo de difusão com ordem total baseado no Paxos
bizantino [47].
Para garantir confidencialidade, este serviço recorre ao PVSS (publicly verifiable secret sharing scheme) [46] juntamente com primitivas de criptografia para ter a certeza
de que apenas partes autorizadas terão acesso a um determinado tuplo em claro. Para
além disto, todos os canais usados para comunicação entre os clientes e os servidores do
DepSpace são canais fiáveis autenticados ponto-a-ponto, através do uso de TCP juntamente com códigos de autenticação de mensagens.
O DepSpace não necessita de nenhuma suposição de tempo mas, devido ao uso de
multicast com ordem total e por razões de liveness, uma sincronia eventual é requerida.
Não há decisões sobre controlo de acesso aos tuplos neste serviço, pois a melhor
opção depende da aplicação. Em vez disto, o DepSpace usa uma camada chamada policy
enforcement que fornece a possibilidade de definir políticas de acesso refinadas de acordo
com as necessidades da aplicação [25]. Este tipo de política permite ao sistema decidir
se uma operação é ou não válida baseando-se, não apenas no identificador do cliente que
invoca a operação, mas também, na operação chamada, os seus argumentos e ainda os
tuplos actualmente guardados no espaço.
Além disso, o serviço possibilita a criação de tuplos temporários: tuplos que permanecem no espaço por um tempo definido e, a menos que este seja revalidado (através
da chamada da operação renew), são automaticamente removidos quando expirados.
Capítulo 2. Trabalhos Relacionados
2.1.4
12
Discussão
Nesta secção foram apresentados os serviços de coordenação estudados. Entre estes
serviços, o ZooKeeper destaca-se no que diz respeito ao desempenho. Por outro lado,
no que diz respeito à fiabilidade, o serviço estudado que mais se destaca é o DepSpace
devido às suas garantias de confidencialidade, integridade e tolerância a faltas bizantinas.
Devido a isto, este foi o serviço de coordenação escolhido para servir de base aos serviços
de directorias e locks.
2.2
Sistemas de Ficheiros Distribuídos
Um sistema de ficheiros tem a função de criar uma estrutura lógica de acesso a dados
armazenados numa memória secundária (como sendo um disco magnético, um serviço de
armazenamento, ou mesmo as clouds). Estes sistemas organizam os dados em ficheiros
que, normalmente, são organizados numa árvore de directorias. A cada ficheiro ou directoria de um sistema de ficheiros estão associados um conjunto de informações chamado
metadados. Nos metadados são mantidas, entre outras, informações sobre a localização
dos dados de cada ficheiro, o seu caminho na árvore de directorias ou o tamanho dos seus
dados.
Nesta secção serão apresentados alguns dos sistemas de ficheiros estudados. Todos
os sistemas apresentados têm uma natureza distribuída. Um sistema de ficheiros distribuído permite aos utilizadores armazenar os seus dados numa localização remota de
forma transparento, podendo estes utilizar este tipo de sistemas da mesma forma que
utilizam um sistema de ficheiros local. Estes sistemas de ficheiros utilizam um modelo
cliente-servidor.
A escolha deste tipo de sistemas de ficheiros para serem descritos nesta secção é justificada com o facto de estes apresentarem mais parecenças com o sistema de ficheiros
onde este trabalho foi integrado que os sistemas de ficheiros centralizados.
2.2.1
Ceph
O Ceph [54] é um sistema de ficheiros distribuído que fornece um alto nível de escalabilidade, fiabilidade e desempenho através do uso da separação entre a gestão de dados e
dos metadados, aliado com o uso de dispositivos de armazenamento de objectos (OSDs).
Os OSDs substituem a interface ao nível do bloco de dados por uma interface que
permite ao cliente ler e escrever grandes quantidades de dados (muitas vezes de tamanho
variável) sobre um objecto com um determinado nome, sem preocupações com replicação, serialização de actualizações, fiabilidade ou tolerância a falhas. Estes componentes
fornecem um serviço de locks aos clientes que permite o acesso exclusivo a um determinado OSD. Isto é útil, por exemplo, para esconder latência através da aquisição do lock e
Capítulo 2. Trabalhos Relacionados
13
do envio dos dados assincronamente.
Na figura 2.2 é apresentada a arquitectura do Ceph. Como podemos ver, o sistema
tem três componentes principais: o cliente, que pode ser um sistema de ficheiros montado
no espaço do utilizador (recorrendo ao FUSE [8]) ou pode interagir directamente com
os outros componentes; o cluster de OSDs, responsável por armazenar todos os dados e
metadados; e o cluster de servidores de metadados (MDS) que faz a gestão do espaço de
nomes enquanto coordena a segurança, coerência e consistência dos ficheiros do sistema.
Figura 2.2: Arquitectura do Ceph [54].
O cluster de servidores de metadados tem uma arquitectura altamente distribuída
baseada na partição distribuída de sub-árvores, permitindo distribuir a responsabilidade
de gestão hierárquica de directorias do sistema de ficheiros pelos MDSs. Esta abordagem
permite ao Ceph aumentar a escalabilidade no acesso aos metadados, e assim, a escalabilidade de todo o sistema.
Os clientes do Ceph fazem I/O sobre os ficheiros directamente com os OSDs. Isto
é conseguido recorrendo à função CRUSH [53] que, através do identificador do ficheiro
(inode), permite ao cliente saber qual OSD responsável por armazenar o ficheiro sobre
o qual pretende operar. O inode é único e é obtido pelo cliente quando este chama a
operação open no MDS. O controlo de acesso aos ficheiros é também feito pelos MDSs
aquando da chamada desta operação.
Por questões de eficiência, os MDSs satisfazem a maioria dos pedidos recorrendo à
sua cache local, mas as operações de actualização dos metadados têm de ser armazenadas
de forma persistente. Para isso, os MDSs usam os OSDs de forma eficiente para armazenar os metadados.
Os clientes do Ceph armazenam em cache dados de ficheiros, sendo esta cache invalidada pelo MDS. Os MDSs invalidam a cache dos dados de um ficheiro em todos os
clientes quando mais de um cliente abre um ficheiro para escrita. Quando isso acontece,
o cliente detentor do lock é forçado a fazer todas as escritas e leituras sobre esse ficheiro
de forma síncrona.
Capítulo 2. Trabalhos Relacionados
2.2.2
14
WheelFS
O WheelFS [48] é um sistema de armazenamento distribuído com uma interface
POSIX [16] desenhado para ser usado por aplicações distribuídas com o propósito de
partilhar dados e ganhar tolerância a faltas. Foi idealizado para manter quase todos os
servidores sempre acessíveis, com falhas ocasionais, não tolerando faltas bizantinas. Em
termos de segurança, garante apenas controlo de acesso aos clientes e validação do conjunto de servidores participantes no sistema.
Este sistema de armazenamento permite aos clientes ajustar algumas configurações
do sistema através do fornecimento de “pistas semânticas”. Estas permitem configurar o
comportamento do sistema no que diz respeito ao tratamento de faltas, localização dos
ficheiros e das réplicas, política de replicação e garantias de consistência. O facto de estas
pistas serem especificadas nos caminhos dos ficheiros permite manter a interface POSIX
inalterada, no entanto, pode levantar problemas em algumas aplicações que “partem” o
caminho do ficheiro e assumem que a pista é uma directoria.
O WheelFS armazena objectos do tipo ficheiro ou directoria, replicando cada objecto por um conjunto de servidores, chamado slice, que utilizam replicação do tipo primary/backup1 para gerir cada objecto.
Os metadados são mantidos por um serviço de configuração que é instalado de forma
independente num pequeno conjunto de máquinas que usa replicação de máquina de estados e usam Paxos para eleger um líder sempre que necessário. Este serviço mantém
uma tabela de slices que guarda, para cada slice, a política de replicação e uma lista de
replicação que mantém o identificador dos servidores que estão a armazenar os objectos
dessa slice em cada momento.
O serviço de configuração exporta um serviço de locks estilo Chubby [26] para ser
usado pelos servidores do sistema. Este serviço de locks permite aos servidores executar
operações de lock sobre uma determinada slice. Um lock sobre uma slice garante ao
seu detentor o direito de ser o líder dessa slice, podendo assim especificar os valores de
configuração durante este período. Os locks das slices são válidos por um período limitado
de tempo, após o qual, tem de ser renovado.
Os clientes guardam a tabela de slices em cache de forma periódica, permitindo-lhes
descobrir, dentro de uma slice, quais os servidores que devem contactar para aceder a um
determinado objecto. Nesta cache são também guardados dados de ficheiros. No entanto,
antes de poderem utilizar os valores guardados em cache, os clientes têm que obter dos
servidores um lease sobre o objecto. Os servidores revogam todos os leases sobre um
ficheiro a cada actualização para garantir a consistência de todas as caches.
O WheelFS fornece consistência ao fechar pois é o padrão esperado por muitas aplicações.
1
O servidor primário recebe as operações, propaga-as pelas réplicas de backup, e só depois responde ao
cliente.
Capítulo 2. Trabalhos Relacionados
2.2.3
15
Frangipani
O Frangipani [50] é um sistema de ficheiros distribuído que fornece várias garantias
como escalabilidade, facilidade de administração, consistência dos ficheiros e disponibilidade mesmo na presença de falhas. O Frangipani usa o Petal [37], um sistema de discos
virtuais, para armazenar os seus dados e metadados.
O Petal consiste numa colecção de servidores que, de uma forma cooperativa, gerem
um conjunto de discos físicos. Este exporta uma abstracção de discos virtuais nos quais
os clientes podem armazenar dados recorrendo a uma interface ao nível do bloco. Estes
discos virtuais estão disponíveis a todos os clientes do sistema e podem ser criados com o
tamanho desejado pelo cliente, escondendo a capacidade total dos discos físicos geridos
pelo Petal. Este sistema de armazenamento apresenta bons valores de escalabilidade, tanto
no número de servidores que tratam os pedidos como na capacidade de dados suportada,
através da adição de mais servidores ao sistema. Tem ainda um desempenho comparável
ao de um disco local, ao mesmo tempo que permite tolerar e recuperar de falhas em
qualquer componente do sistema, fornecer suporte para backup e recuperação, e fazer
balanceamento de carga de forma uniforme pelos servidores. Visto o Frangipani usar o
Petal como o seu sistema de armazenamento, este herda todas as garantias descritas.
Figura 2.3: Arquitectura do Frangipani.
Na figura 2.3 é apresentada a arquitectura do Frangipani. Como podemos ver, os
clientes acedem ao sistema usando uma interface de chamadas de sistema padrão fornecida
por servidores de ficheiros do Frangipani, instalados na mesma máquina que o cliente.
Abaixo do servidor de ficheiros do Frangipani existem duas camadas: a driver do dispositivo Petal e um serviço de locks distribuído. Note-se que os servidores do Frangipani
Capítulo 2. Trabalhos Relacionados
16
apenas comunicam com estas duas camadas, nunca havendo comunicação entre si.
O driver do dispositivo Petal esconde a natureza distribuída do Petal e é usado pelos
servidores do Frangipani para aceder aos discos virtuais fornecidos pelos servidores do
Petal e, assim, guardarem todos os dados e metadados do sistema de ficheiros. O Frangipani usa o grande e esparso espaço de disco fornecido pelo Petal para criar estruturas que
facilitam o armazenamento dos seus dados e metadados. Desta forma, o Frangipani utiliza
discos de 264 bytes que são divididos em regiões para armazenar parâmetros partilhados,
logs, bitmaps de alocação, inodes e blocos de dados.
O serviço de locks distribuído permite ao Frangipani manter a consistência dos ficheiros
partilhados e coordenar o acesso concorrente aos mesmos. Este serviço fornece locks
do tipo um-escritor/múltiplos-leitores sobre os blocos. Na realidade, uma limitação do
Frangipani consiste no facto de, visto o petal exportar uma interface ao nível do bloco,
apenas permitir reservar ficheiros inteiros ao invés de blocos de dados. Ao invés disto,
uma abordagem mais interessante seria permitir reservar blocos de dados individualmente, sendo possível que diferentes clientes pudessem escrever em blocos de dados
diferentes do mesmo ficheiro em simultâneo.
Por questões de desempenho, os servidores do Frangipani mantêm uma cache dos
dados lidos. Quando estes adquirem o lock para leitura sobre um ficheiro, estão então
aptos para guardar em cache os dados lidos. Estes dados em cache são válido enquanto
nenhum servidor adquirir um lock de escrita sobre o mesmo ficheiro. Neste caso, visto
este acontecimento representar uma possível alteração dos dados do ficheiro, é pedido a
todos os servidores com o lock de leitura que libertem o lock e retirem os dados desse
ficheiro da sua cache.
2.2.4
Andrew File System
O Andrew File System (AFS) [44] é um sistema de ficheiros distribuído cujo desenho é
focado na transparência, suporte à heterogeneidade, escalabilidade e segurança. Este sistema de ficheiros foi desenhado nos anos 80 para permitir aos estudantes da Universidade
de Carnegie-Mellon partilhar ficheiros entre si. Esta versão do AFS não está apta a suportar grandes bases de dados, sendo apenas adequada para suportar a partilha de ficheiros
com poucos megabytes entre relativamente poucos utilizadores (de 5000 a 10000).
A figura 2.4 apresenta a arquitectura do AFS. Como podemos observar, este é composto por dois componentes chave: o Vice e a Virtue. O Vice é uma colecção de recursos de comunicação e de computação, compostos por um conjunto de servidores semiautónomos conectados entre si por uma LAN. Este sistema de ficheiros assume que todas
as comunicações e computações dentro da Vice são seguros. A Virtue é uma estação de
trabalho ligada a um dos servidores do Vice, servidor este responsável por interagir com
os restantes servidores. Cada Virtue tem anexada a si uma outra entidade, chamada Venus,
que é responsável pela comunicação com o Vice e por gerir a cache local. Dado isto, o sis-
Capítulo 2. Trabalhos Relacionados
17
Figura 2.4: Arquitectura do AFS.
tema, num todo, é composto por um conjunto de servidores que armazenam os ficheiros
do sistema, formando o já referido Vice. A cada um destes servidores podem estar ligadas várias estações de trabalho, cada uma com uma Virtue. A decomposição do Vice
num conjunto de servidores existe para tratar o problema de escalabilidade. Assim, para
aumentar o número de clientes suportados basta adicionar mais servidores.
Por questões de desempenho, cada Virtue deve usar o servidor ao qual se encontra
ligada sempre que possível, reduzindo assim o tráfego entre servidores e os atrasos nas
bridges que conectam os vários servidores, tudo isto ao mesmo tempo que fornece um
bom balanceamento de carga.
Devido à natureza não confiável da Virtue, é necessária uma autenticação mutua entre
a Virtue e o Vice antes de estabelecer uma conexão. Para isto é usada uma chave de encriptação partilhada entre estes de modo a obter uma chave de sessão. Esta chave de sessão
é gerada recorrendo a uma palavra-chave fornecida peço utilizador, e é posteriormente
utilizada para cifrar toda a comunicação entre o Vice e uma Virtue durante uma sessão.
Existem dois espaços de nomes onde os ficheiros podem ser armazenados: o espaço
de nomes local, onde o disco local da estação de trabalho é utilizado; e o espaço de nomes
partilhado, que recorre ao Vice para armazenar os ficheiros. No espaço de nomes local
são armazenados os ficheiros temporários, os ficheiros privados e os ficheiros usados para
inicializar a conexão com o Vice. No espaço de nomes partilhado, visto ser comum a
todos os utilizadores, contém todos os ficheiros partilhados por eles.
Para fornecer transparência da localização dos ficheiros, o Vice provê um mecanismo
para localizar os ficheiros. Todos os servidores mantêm uma base de dados completa que
mapeia cada ficheiro para um conjunto de guardiões. Um guardião de um ficheiro é um
servidor pertencente ao Vice responsável por armazenar e por tratar todas as operações
Capítulo 2. Trabalhos Relacionados
18
feitas sobre esse ficheiro.
No AFS são usadas transferências dos ficheiros na íntegra ao invés de transferências
de blocos individuais de ficheiros, sendo usado um modelo de consistência ao fechar.
Esta abordagem permite, entre outras coisas, reduzir o número de acessos aos guardiões
e a sobrecarga da rede. Para atingir melhor desempenho e diminuir o número de acessos
feitos aos servidores é utilizada cache do lado do cliente, neste caso a Virtue. Todas as
leituras e escritas são feitas na cópia local do ficheiro, sendo este propagado na íntegra
para o Vice apenas quando o ficheiro é fechado. Nesta versão do AFS, a validação da
consistência da cache é feita quando o ficheiro é aberto (check-on-open).
Para garantir que apenas utilizadores autorizados podem aceder a um determinado
ficheiro, o AFS fornece um mecanismo de controlo de acesso. Este replica uma base
de dados por todos os servidores com a informação de quais utilizadores e grupos podem aceder a cada recurso. Assim, para garantir o acesso a um ficheiro por parte de um
determinado utilizador é apenas necessário adicioná-lo à lista de acesso. Para facilitar
a revogação de direitos a um determinado utilizador, o AFS usa o conceito de Direitos
Negativos nas listas de acesso. Isto permite adicionar à lista de direitos utilizadores que
não têm direitos de acesso de uma forma fácil e rápida.
O Vice fornece também um mecanismo que provê primitivas de lock do tipo umescritor/múltiplos-leitores. Os locks obtidos através deste mecanismo têm uma natureza
consultiva. No entanto, o Vice não requer a reserva de ficheiros antes do seu uso pois este
utiliza mecanismos que mantêm a consistência de um ficheiro mesmo este não estando
reservado.
2.2.5
Coda
O Coda [45] é um sistema de ficheiros distribuído de larga escala para estações de
trabalho UNIX. É um descendente do Andrew File System (AFS) [31], mas fornece mais
garantias no que diz respeito aos aspectos de tolerância a faltas. Assim, este sistema de
ficheiros tem como objectivo manter constante a disponibilidade dos dados, permitindo
aos utilizadores continuar a trabalhar sobre os ficheiros mesmo em caso de falha do servidor.
Desta forma, o Coda tira vantagem de algumas funcionalidades do AFS que contribuem para a sua segurança, fiabilidade e escalabilidade:
• os ficheiros mantidos em cache são transferidos e guardados na integra. O facto de
todos os ficheiros serem guardados em cache facilita na tolerância a falhas da rede
ao mesmo tempo que fornece mobilidade.
• os clientes guardam também em cache alguns metadados, por exemplo, o identificador dos servidores que mantêm os ficheiros guardados.
Capítulo 2. Trabalhos Relacionados
19
• é usada autenticação entre clientes e servidores antes de qualquer comunicação,
sendo que todas as mensagens trocadas entre estes são cifradas.
• é usado um modelo onde poucos servidores seguros e confiáveis são acedidos por
vários clientes não-confiáveis.
A invalidação da cache usa a mesma estratégia que a versão 2 do AFS [31], onde um
mecanismo de callback é usado. Neste mecanismo, o servidor usado pelo cliente para
obter um ficheiro, promete enviar-lhe uma notificação (callback) quando esse ficheiro for
alterado.
Para aumentar a disponibilidade e tolerância a faltas, o Coda usa servidores replicados
e permite que os seus clientes façam operações mesmo não estando conectados a estes.
No entanto, esta abordagem levanta o problema da possibilidade de existência de conflitos
de versões em ficheiros partilhados por vários clientes. Neste caso, o sistema tenta em
primeiro lugar, resolver estes conflitos de forma automática e, caso tal não seja possível,
este fornece uma ferramenta de reparação que permite aos clientes resolver os conflitos
manualmente.
A unidade da replicação do Coda é o volume, uma sub-árvore parcial do espaço de
nomes partilhado composto por ficheiros e directorias. Quando um volume é criado, é
especificada a informação sobre o grau de replicação deste e quais os servidores a serem
utilizados para o armazenar. Esta informação é armazenada numa base de dados que é
partilhada por todos os servidores. O conjunto de servidores que armazenam um volume
é chamado de volume storage group (VSG). Quando um volume é lido, este é guardado
numa cache no disco local do cliente. Por cada volume guardado em cache, o gestor da
cache do cliente mantém um subconjunto chamado accessible VSG (AVSG) com todos os
VSGs acessíveis a cada instante. Note-se que, para um mesmo volume, diferentes clientes
podem ter diferentes AVSGs.
Para abrir um ficheiro, o cliente verifica se tem uma cópia válida desse ficheiro em
cache. Caso isto não se verifique, então o ficheiro é obtido do membro do AVSG com
a versão mais recente do ficheiro. Este servidor é chamado de “servidor preferido” e o
compromisso da recepção de um callback é estabelecido com ele.
Depois de uma modificação, o ficheiro é fechado e é então transferido em paralelo
para todos os membros do AVSG. Devido ao facto de o Coda usar uma estratégia optimista, só após a transferência dos dados para os servidores, é feita uma verificação para
tentar encontrar conflitos entre versões. Quando um conflito acontece, o Coda tenta, de
uma forma automática, resolve-lo. Quando tal não é possível, o Coda marca o ficheiro
como inconsistente em todos os servidores que o armazenam, deixando para o utilizador
a responsabilidade de resolver o conflito manualmente. O Coda fornece uma ferramenta
de reparação de conflitos com uma interface especial que permite operar sobre ficheiros e
directorias com inconsistências.
Capítulo 2. Trabalhos Relacionados
20
Este sistema de ficheiros garante que todos os clientes são informados com um atraso
nunca superior a T segundos quando qualquer um dos seguintes eventos acontece:
• A redução do AVSG através da inacessibilidade de um servidor do AVSG.
• A extensão de um AVSG, ou seja, quando algum servidor passa de inacessível para
acessível.
• A perda de um evento callback.
Como vimos acima, as operações desconectadas permitem continuar a trabalhar sobre
os ficheiros mesmo em caso de a conexão se ter perdido, aumentando, assim, a disponibilidade do sistema. As operações desconectadas começam quando um cliente não tem
nenhum membro no AVSG. Este modo é idealmente temporário e o cliente volta ao modo
normal assim que possível. A mudança entre estes dois modos é transparente ao cliente
excepto no caso de faltar um ficheiro na cache (cache miss) no modo desconectado ou na
ocorrência de inconsistências no modo conectado.
A ocorrência de eventos de cache miss no modo normal é transparente aos utilizadores,
no entanto, estes resultam numa diminuição do desempenho do sistema. Quando estes
acontecem no modo de operação desconectado, o sistema bloqueia a computação até que
consiga reestabelecer a conexão e assim obter o ficheiro. Devido a isto é importante manter em cache todos os ficheiros sobre os quais o cliente queira operar. Neste contexto, o
Coda permite aos utilizadores especificar uma lista de ficheiros (com diferentes níveis de
prioridade) que devem ser mantidos em cache.
Em resumo, o Coda é um sistema de ficheiros altamente disponível, pois permite
operar sobre ficheiros mesmo que não haja conexão com os servidores de forma transparente. Este utiliza uma cache do lado do cliente, não sendo necessária troca de mensagens
antes de a utilizar (devido à utilização de callbacks). É utilizada uma abordagem optimista
no que diz respeito à existência de ficheiros inconsistentes, sendo fornecidos mecanismos
para resolver este problema, tanto de forma automática como manual. O Coda faz armazenamento conjunto dos dados e metadados.
2.2.6
Farsite
O Farsite [22] é um sistema de ficheiros distribuído fiável e fácil de administrar que
funciona como um servidor de ficheiros centralizado mas que é distribuído fisicamente
entre uma rede de máquinas. Este fornece facilidade de administração pois substitui o
esforço dos administradores de sistema por processos automáticos. O Farsite protege
e preserva os seus dados e metadados recorrendo a técnicas de criptografia e replicação.
Para manter a privacidade, integridade e durabilidade dos dados, estes são cifrados e replicados pelos vários servidores do sistema, sendo também mantido um hash dos mesmos
Capítulo 2. Trabalhos Relacionados
21
juntamente com os dados e metadados. Por outro lado, os metadados do sistema necessitam ter alguns campos em claro. Assim, estes são mantidos por máquinas de estado
replicadas tolerantes a faltas bizantinas, que garante a disponibilidade e integridade dos
dados, e é utilizada criptografia para cifrar os nomes dos ficheiros ou directorias do sistema, mantendo estes campos imperceptíveis aos clientes não autorizados.
Para impedir clientes maliciosos de criar ficheiros ou directorias com nomes que, após
serem decifrados, são sintaticamente ilegais é utilizada uma técnica chamada exclusive
encription [27] que garante a decifração de nomes apenas gera nomes legais. Para efectuar
controlo de acesso, os metadados do sistema mantêm uma ACL com informações sobre
as permissões dos clientes sobre cada ficheiro ou directoria.
Em [28] é apresentado um novo serviço de directorias para o Farsite que fornece
todas garantias que o anterior serviço fornecia, fornecendo ainda uma melhoria no que
diz respeito à escalabilidade. Isto é conseguido particionando os metadados entre vários
servidores e utilizando mitigação de pontos críticos (hotspots).
Este serviço de directorias divide os metadados pelos vários servidores tendo em conta
o identificador do ficheiro (imutável e invisível ao utilizador). Esta abordagem simplifica
o problema da alteração do nome de ficheiros pois cada servidor é responsável por um
ficheiro (ou conjunto de ficheiros) com um identificador imutável.
Para lidar com actualizações aos metadados são utilizados leases. Estes leases podem
ser de escrita ou de leitura. Quando um cliente pretende efectuar uma operação sobre os
metadados de um ficheiro, este tem de, não só obter uma cópia dos metadados sobre os
quais pretende operar, mas também obter um lease sobre os mesmos. Durante o tempo de
validade do lease, o cliente pode ler ou alterar os valores dos metadados (dependendo se
o lease foi apenas para leitura ou se permite também modificações). No caso dos leases
de escrita, o servidor perde a autoridade sobre os metadados enquanto o lease for válido.
Nesta nova versão do serviço de directorias do Farsite, os leases dizem respeito, não
sobre todos os campos dos metadados de um ficheiro, mas apenas sobre um campo dos
mesmos. Esta abordagem permite mitigar pontos críticos. Este serviço de directorias
permite ainda, por questões de desempenho, que os clientes guardem em cache quais os
servidores que armazenam os metadados de cada ficheiro.
2.3
Sistemas de Ficheiros para Clouds
Como já foi referido, hoje em dia muitas empresas têm migrado os seus serviços para
as clouds com o objectivo de reduzirem custos no que diz respeito ao investimento em
equipamentos e em manutenção dos mesmos. Um dos serviços críticos numa empresa é o
seu sistema de ficheiros, utilizado pelos seus colaboradores para manter os seus ficheiros.
Visto o trabalho descrito neste relatório ter sido integrado num sistema de ficheiros para
clouds, nesta secção serão descritos dois sistemas de ficheiros deste tipo.
Capítulo 2. Trabalhos Relacionados
2.3.1
22
Frugal Cloud File System - FCFS
O FCFS [42] é um sistema de ficheiros vocacionado a optimizar os custos inerentes à
utilização dos serviços de armazenamento das clouds. Este sistema tira partido da utilização de vários destes serviços para reduzir os custos da sua utilização.
Os serviços de armazenamento apresentam diferentes preços no que diz respeito ao
armazenamento e à transferência dos dados. Os autores do FCFS apresentam como exemplos os custos de transferência e armazenamento do Amazon S3 [4], Amazon EBS [1] e
Amazon ElastiCache [3]. O Amazon S3 tem um custo de armazenamento baixo, mas um
custo de transferência elevado, enquanto que o Amazon EBS tem um custo de armazenamento relativamente elevado e um custo de transferência relativamente baixo. Por fim, o
Amazon ElastiCache tem um custo de armazenamento muito elevado, não havendo custos
associados à transferência de dados. É importante notar que o custo de armazenamento
nestes serviços reflecte também a o seu desempenho, nomeadamente, a latência. Assim,
quanto menor o custo de armazenamento de um serviço, maior o custo de transferência
dos dados por si armazenados e maior a latência de acesso aos mesmos.
Neste âmbito, este sistema reduz os custos de armazenamento dos dados nas clouds
através da transferência dos dados entre os vários serviços de armazenamento de acordo
com a carga de trabalho do sistema. A abordagem utilizada consiste em utilizar dois níveis
de armazenamento dos dados. No início, todos os dados são armazenados no serviço
onde o armazenamento é mais barato (como é o caso do Amazon S3), sendo este nível
de armazenamento denominado de disco. Visto as transferências serem muito caras neste
serviço, quando há muita carga de trabalho sobre um determinado ficheiro, este é transferido para um serviço onde as transferências sejam mais baratas (como o Amazon EBS),
sendo este nível de armazenamento chamado de cache. Desta forma, quando há muitos
acessos a um ficheiro, este é trazido para a cache onde, para além de oferecer um maior
desempenho, o aumento dos custos inerentes ao seu armazenamento são rentabilizados
pelo dinheiro poupado no acesso a ele.
No Amazon EBS, os ficheiros são mantidos em volumes de disco. Estes volumes são
ajustáveis no que diz respeito ao tamanho, sendo importante mantê-los o mais pequenos
possível para minimizar os custos. Quando não é rentável aumentar o tamanho do volume
para armazenar mais ficheiros em cache, são usadas políticas de substituição de cache
(como o LRU2 ) para seleccionar os ficheiros a substitui-los na cache por outros que sejam
mais úteis naquele instante.
Este sistema tem a importante limitação de, para poder usufruir de alguns dos serviços
de armazenamento na cloud de um provedor, nomeadamente o Amazon EBS e o Amazon ElastiCache, necessita ter acesso a instâncias de computação fornecidas pelo mesmo
provedor. Esta necessidade acrescenta custos à utilização deste sistema.
Não é apresentado nenhum mecanismo que permita a partilha controlada de ficheiros
2
Substitui o objecto em cache que, no instante da substituição, não é utilizado há mais tempo.
Capítulo 2. Trabalhos Relacionados
23
entre vários utilizadores, assim como não é apresentada qualquer informação sobre como
são mantidos os metadados do FCFS. Uma outra limitação a ter em conta é o facto não
haver nenhuma preocupação com tolerância a faltas do provedor do serviço de armazenamento nas clouds utilizado pelo sistema.
2.3.2
BlueSky
O BlueSky [52] é um sistema de ficheiros de rede com armazenamento na cloud,
desenhado para servir um conjunto de utilizadores num contexto empresarial. Este sistema tira partido das garantias de disponibilidade e vasta capacidade de armazenamento
fornecidas pelos serviços de armazenamento nas clouds.
A figura 2.5 apresenta a arquitectura do BlueSky. Como podemos ver na figura, os
clientes acedem aos dados armazenados através de um proxy que suporta os protocolos
NFS (versão 3) e CIFS, dando aos clientes a ilusão de estarem a comunicar com um
servidor de ficheiros tradicional. Este componente está situado entre os clientes e os
provedores de armazenamento na cloud. Idealmente, o proxy deve estar instalado na
mesma rede que os clientes, de forma a reduzir a latência da comunicação entre eles.
Figura 2.5: Arquitectura do BlueSky.
Todas as escritas efectuadas sobre ficheiros do BlueSky são tratas localmente pelo
proxy. Para isso, ele escreve os novos dados no seu disco local, respondendo ao cliente
de seguida. Estes novos dados são enviados periodicamente para a cloud de forma assíncrona. No entanto, esta abordagem pode levar a que, em caso de falha do proxy e do seu
disco local, algumas escritas não sejam propagadas para a cloud.
Para tratar das leituras localmente, o proxy mantém uma cache que lhe permite tratar
alguns pedidos. Quando os dados a serem lidos não estão em cache, estes são obtidos
da cloud e armazenados na cache local. Visto o proxy ter uma capacidade de disco limitada, quando o número de ficheiros em cache atinge um limite pré-definido, é utilizada a
política LRU para seleccionar o ficheiro a ser substituído.
O proxy permite a partilha controlada de ficheiros entre os clientes a si ligados. No
entanto, em caso de falha deste componente, todos os clientes deixam de ter acesso aos
seus ficheiros. Note-se ainda que, na versão do BlueSky apresentada, é apenas permitida
a existência de uma instância deste componente, não podendo os clientes, em caso de
falha do proxy, ligar-se a uma outra instância para ter acesso aos seus dados. O BlueSky
Capítulo 2. Trabalhos Relacionados
24
tem também a limitação de usar apenas uma cloud para armazenar os dados, dependendo
desta em vários aspectos, nomeadamente no que diz respeito à disponibilidade dos dados
do sistema.
O BlueSky utiliza um esquema de dados estruturado num log, sendo este log armazenado na cloud. Existem quatro tipos de objectos que representam dados e metadados
neste log: blocos de dados, inodes, mapas de inomes e checkpoints. Os blocos de dados
são utilizados para armazenar os dados dos ficheiros. O BlueSky utiliza blocos fixos de 32
KB. Por sua vez, os inodes são utilizados para armazenar os metadados de cada ficheiro,
como por exemplo as permissões de acesso, o identificador do seu dono e uma lista de
apontadores para os seus blocos de dados. Os mapas de inodes listam a localização da
versão mais recente de cada inode no log, ao passo que cada checkpoint mantém a localização no log dos mapas de inodes em uso. Este último objecto é útil para manter
a integridade do sistema mesmo em caso de falha do proxy pois, visto este objecto ser
sempre um dos últimos a ser escrito, basta ao proxy localizar este objecto para estar apto
a obter os metadados dos ficheiros mais recentes.
Por questões de segurança, os objectos armazenados no log são cifrados individualmente (com AES) e protegidos com códigos de autenticação de mensagens (com HMACSHA-256) pelo proxy antes de serem enviados para a cloud, mantendo a integridade e
confidencialidade dos dados armazenados. No entanto, é necessário um certo nível de
confiança no provedor de armazenamento, pois este está habilitado a eliminar ou corromper os dados, causando a indisponibilidade dos mesmos.
Como qualquer sistema de ficheiros estruturado em log, é necessária a existência de
um colector de lixo para apagar dados desactualizados. O BlueSky utiliza um colector de
lixo que tanto pode estar instalado no proxy como numa cloud de computação fornecida
pelo mesmo provedor que armazena os dados. A segunda solução permite que o colector
efectue a sua tarefa mais rápido e com menos custos.
2.3.3
S3FS
O S3FS é um sistema de ficheiros para sistemas operativos UNIX que utiliza o Amazon
S3 [4] para armazenar os dados. Como podemos ver na figura 2.6, este sistema é montado
na máquina local (utilizando o FUSE [8]) do cliente que acede directamente à cloud. Este
sistema tem a limitação de não permitir a partilha controlada de ficheiros entre diferentes
utilizadores, i.e., não controla o acesso aos mesmos por parte de diferentes processos
escritores. Tal como os anteriores sistemas de ficheiros para clouds apresentados, também
o S3FS tem a limitação de usar apenas um provedor de armazenamento na cloud, não
tolerando faltas do mesmo.
É possível ao cliente configurar o sistema para utilizar uma cache local, mantida em
disco, para aumentar o desempenho deste. É utilizada uma semântica de consistência ao
fechar, sendo cada ficheiro obtido da cloud para a cache aquando da sua abertura e escrito
Capítulo 2. Trabalhos Relacionados
25
Figura 2.6: Arquitectura do S3FS.
no seu fecho. Assim, todas as escritas e leituras efectuadas sobre um determinado ficheiro
são feitas localmente. Quando a transferência dos dados de um ficheiro para a cloud não
tem sucesso, o sistema volta a tentar duas vezes antes de abortar a transferência e devolver
um erro. Note-se que os ficheiros são transferidos na íntegra.
A cache dos dados mantida em disco pode crescer de tal forma que ocupe todo o
espaço deste, sendo da responsabilidade do cliente seleccionar os ficheiros a remover da
cache para libertar espaço. O S3FS mantém também uma cache em memória principal
com os metadados dos ficheiros.
2.3.4
S3QL
O S3QL é um sistema de ficheiros que armazena os dados na clouds, podendo este ser
configurado para utilizar o Google Storage [11], o Amazon S3 [4] ou o OpenStack Cloud
Files [14]. Este sistema pode ser montado em sistemas de ficheiros UNIX.
Tal como o S3FS, também este sistema é montado na máquina local do cliente que
acede directamente à cloud, não permitindo partilha controlada de ficheiros entre utilizadores e dependendo do provedor de armazenamento em vários aspectos, nomeadamente na disponibilidade dos dados.
Este sistema utiliza uma base de dados local como cache para armazenar tanto dados
como metadados, sendo todas as operações de metadados feitas sobre esta base de dados.
Os dados dos ficheiros de sistema são armazenados na cache e na cloud em blocos de
pequena dimensão. Esta abordagem permite optimizar o desempenho do sistema e ainda
diminuir os custos associados ao envio e obtenção de dados da cloud pois apenas são
transferidos os blocos sobre os quais se pretende operar. Todos os envios feitos para a
cloud são feitos de forma assíncrona.
Para reduzir a quantidade de informação transferida para garantir a confidencialidade
dos dados, antes de enviar os dados para a cloud, o sistema comprime os dados (utilizando
os mecanismos de compressão LZMA ou bzip2) e cifra os mesmos (utilizando a técnica
AES com chave de 256 bits). Para garantir a integridade dos dados, o S3QL mantém
localmente um resumo criptográfico de cada bloco armazenado na cloud. Assim, quando
obtém os dados, o sistema compara o resumo criptográfico dos dados lidos com o resumo
guardado localmente podendo, desta forma, perceber se estes dados foram corrompidos.
O S3QL fornece ainda um mecanismo que permite efectuar backup de directorias.
Capítulo 2. Trabalhos Relacionados
2.4
26
Considerações Finais
Neste capítulo foram apresentados vários sistemas que, de alguma forma, estão relacionados com o trabalho desenvolvido neste projecto. No próximo capítulo será apresentado esse trabalho, sendo em primeiro lugar descrito o contexto no qual este foi integrado,
através da apresentação do C2FS como um todo, sendo em seguida dada ênfase à descrição detalhada do substrato de coordenação (concretizado num serviço de locks) e do
serviço de directorias.
Capítulo 3
Metadados e Locks no C2FS
Neste capítulo são apresentados o mecanismo utilizado para gerir os metadados no
C2FS, assim como é garantida a consistência dos seus ficheiros. Em primeiro lugar é apresentado o C2FS como um todo para fornecer o contexto do ambiente no qual o trabalho
desenvolvido foi integrado. Em seguida são apresentadas várias versões do serviço de directorias utilizado para armazenar os dados, assim como o serviço de locks desenvolvido.
Para o desenvolvimento destes serviços, foi necessário adicionar algumas funcionalidades
novas ao DepSpace [23], sendo estas também explicadas em detalhe neste capítulo.
3.1
C2FS
O C2FS é um sistema de ficheiros com interface POSIX [16] que armazena os dados
numa cloud-of-clouds, recorrendo ao DepSky [24]. Este sistema garante a privacidade,
integridade e disponibilidade dos dados, admitindo que uma fracção dos provedores de armazenamento utilizados falhe de forma Bizantina. Os metadados são armazenados recorrendo ao um serviço de coordenação também tolerante a faltas bizantinas [23], que garante
que os metadados são armazenados de forma segura.
3.1.1
Arquitectura Geral
A figura 3.1 apresenta a arquitectura do C2FS e a estrutura dos seus serviços. Como se
pode observar, na base da arquitectura temos o módulo FUSE [8]. Este módulo é responsável por interceptar as chamadas ao sistema operativo referentes a recursos do C2FS.
Estas chamadas são entregues ao agente C2FS. Neste sistema é usada uma concretização
do FUSE em Java, chamada FUSE-J [9].
O agente C2FS é responsável por interagir com os serviços de armazenamento, locks
e directorias de acordo com a chamada recebida do módulo FUSE. Uma das tarefas deste
trabalho era a integração dos serviços de directorias e de locks com o serviço de armazenamento. Esta tarefa foi concretizada neste componente.
27
Capítulo 3. Metadados e Locks no C2FS
28
Figura 3.1: Arquitectura do C2FS.
O serviço de armazenamento do C2FS [40] permite, recorrendo ao DepSky [24],
guardar os dados do sistema na cloud-of-clouds assegurando-se da integridade, disponibilidade e confidencialidade dos mesmos. Por uma questão de desempenho, este serviço
mantém em cache os dados dos ficheiros do C2FS. Esta abordagem permite que, excepto nos casos em que os dados não estão em cache ou em que um outro cliente escreve
uma versão mais recente dos dados em cache, todas as leituras sejam feitas localmente.
Fornece ainda dois níveis de cache (memória principal e disco) com diferentes desempenhos e garantiras de consistência. Para verificar se os dados mantidos em cache são ou não
a versão mais recente, o agente C2FS fornece a este serviço o resumo criptográfico da versão mais recente dos dados, resumo este que é comparado com o resumo criptográfico dos
dados em cache. Este serviço é configurável, permitindo ao cliente do serviço (neste caso
o agente C2FS) definir qual o nível de cache que pretende utilizar, assim como se as escritas para as clouds são síncronas (o sistema bloqueia até que a operação esteja completa)
ou assíncronas (escrita para as clouds é feita em background), podendo o cliente adaptar
o funcionamento do serviço às suas necessidades em termos de desempenho e de consistência dos dados nas clouds. O serviço de armazenamento é responsável também por
cifrar os dados antes de os enviar para a cloud-of-clouds. Este processo é feito recorrendo
a uma chave fornecida pelo agente C2FS quando este efectua uma escritas. Aquando de
uma leitura de dados, o serviço de armazenamento é também responsável por decifrar os
dados usando, mais uma vez, uma chave fornecida pelo agente C2FS. Como veremos na
secção 3.2.2, esta chave é armazenada no serviço de directorias.
O serviço de locks permite manter a consistência dos ficheiros do C2FS, garantindo
que, em cada instante, existe no máximo um utilizador a escrever num contentor de dados.
Capítulo 3. Metadados e Locks no C2FS
29
O serviço de directorias utiliza o DepSpace [23]1 para armazenar os metadados e efectuar
o controlo de acesso aos ficheiros do C2FS. Como podemos verificar na figura 3.1, este
serviço mantém uma cache de metadados que permite diminuir o número de chamadas ao
DepSpace, diminuindo os custos inerentes à utilização do sistema e aumentar o desempenho do sistema. Estes dois serviços vão ser descritos em maior detalhe nas secções 3.2.2
e 3.3.
Tanto o serviço de armazenamento como o serviço de directorias mantêm uma fila de
tarefas que correm em background. Estas tarefas permitem propagar alterações de dados e
metadados de forma assíncrona no sistema, representando um incremento do desempenho
do mesmo.
Figura 3.2: Cloud-of-clouds.
Na figura 3.2 é apresentada uma visão geral do C2FS, onde um conjunto de utilizadores acede a ficheiros cujos dados e metadados estão armazenados em diferentes
provedores de armazenamento e computação nas clouds. Exemplos de serviços deste
género são o Amazon S3 [4] e o Amazon EC2 [2], respectivamente. Como podemos
perceber, foi decidido separar os dados dos metadados. Outros sistemas de ficheiros [54,
48] optaram também por esta abordagem. As razões que levaram à utilização de um
serviço de coordenação instalado nas clouds de computação para o armazenamento dos
metadados ao invés de os armazenar nas clouds de armazenamento são essencialmente as
seguintes:
• Um serviço de coordenação fornece primitivas eficientes para a implementação de
um serviço de locks.
• O desempenho é superior para operações com pouca transferência de dados (como
é o caso do acesso aos metadados), conforme será mostrado na secção 5.
1
Assume-se implicitamente que as réplicas do DepSpace vão estar a correr em diferentes provedores de
computação em cloud, fazendo também uso do paradigma cloud-of-clouds.
Capítulo 3. Metadados e Locks no C2FS
30
• Ter um serviço de metadados consistente permite ter um sistema de ficheiros consistente. Esta afirmação será explicada em pormenor no capítulo 3.4.
O serviço de coordenação utilizado, como já foi referido anteriormente, é o DepSpace [23].
Esta escolha deve-se ao facto de este ser o serviço de coordenação disponível que mais
garantias de segurança e fiabilidade oferece entre os serviços estudados (ver secção 2.1).
3.1.2
Modelo de Sistema
O sistema suporta um conjunto ilimitado de clientes que correm os serviços de armazenamento, directorias e locks. Assume-se que cada um destes clientes tem um identificador único (clientId).
Os serviços de directorias e locks recorrem ao DepSpace [23] para exercer a sua
função. Toda a comunicação entre estes serviços e o DepSpace é feita utilizando canais
fiáveis autenticados ponto-a-ponto através do uso de sockets TCP, códigos de autenticação de mensagens (MAC) e de chaves de sessão. É também assumido que a rede pode
descartar, corromper ou atrasar mensagens, mas não pode interromper indefinidamente a
comunicação entre processos correctos. Não é necessária nenhuma garantia de tempo explícita, sendo no entanto, por uma questão de liveness, necessário um modelo de sistema
eventualmente síncrono. Esta necessidade deve-se ao uso da primitiva de difusão com
ordem total, baseada no protocolo de consenso bizantino Paxos, para garantir que todos
os servidores do DepSpace executam as mesmas operações pela mesma ordem [47].
O serviço de armazenamento, por sua vez, recorre ao DepSky [24] para armazenar
os seus dados na cloud-of-clouds. Cada cloud utilizada para armazenar dados representa
um servidor passivo (não executando nenhum código específico para o protocolo) com
uma semântica de consistência regular, ou seja, para operações de leitura que ocorrem
concorrentemente com operações de escrita, o valor lido é sempre, ou o valor antigo, ou o
valor a ser escrito, nunca um valor intermédio. O sistema tolera faltas bizantinas por parte
dos servidores do DepSpace, do serviço de directorias, do serviço de locks, dos provedores
de armazenamento nas clouds e do serviço de armazenamento (enquanto processo leitor
de dados no DepSky).
Embora o C2FS garanta que, a cada instante, não existe mais que um processo escritor
para um mesmo contentor no DepSky, não são considerados escritores maliciosos pois,
tendo acesso ao ficheiro, um cliente malicioso poderia escrever dados sem sentido para a
aplicação de qualquer forma. Todos os serviços de armazenamento que efectuam leituras
(recorrendo ao DepSky) têm acesso à chave pública dos escritores, permitindo efectuar
verificação e validação dos dados lidos (previamente assinados).
Tanto no caso dos servidores DepSpace como das clouds usadas pelo DepSky, devido
ao uso de quóruns bizantinos, o sistema requer n ≥ 3f +1 servidores (ou clouds) para tolerar f faltas, assumindo, no entanto, que as falhas dos servidores não são correlacionadas.
No entanto, o sistema tolera um número ilimitado de clientes faltosos.
Capítulo 3. Metadados e Locks no C2FS
3.2
31
Metadados
Os metadados no contexto de um sistema de ficheiros, tem a função de guardar informações referentes a cada ficheiro, tais como a localização dos seus dados na memória
secundária, o seu dono, as permissões de acesso por parte de diferentes utilizadores, entre
outros. Tal como todos os sistemas de ficheiros, também o C2FS necessita de um mecanismo que lhe permita armazenar e manusear os metadados do sistema. Neste contexto,
foram desenvolvidas algumas versões de um serviço de directorias para efectuar estas
tarefas. Todas as versões deste serviço de directorias que permitem a partilha de ficheiros
utilizam o DepSpace [23] para armazenar os metadados. Abaixo, serão descritas as alterações necessárias neste serviço de coordenação, assim como o modo de funcionamento
dos vários mecanismos desenvolvidos para armazenar e manusear os metadados do C2FS.
3.2.1
DepSpace
Como referido na secção 2.1.3, o DepSpace é um serviço de coordenação seguro
e tolerante a faltas bizantinas. Este serviço utiliza uma abstracção de espaço de tuplos, fornecendo aos clientes a possibilidade de armazenar estruturas de dados genéricas
(chamadas tuplos).
Além de simplesmente armazenar tuplos, este serviço possibilita definir políticas de
acesso aos tuplos contidos no espaço, nomeadamente definir quais os clientes que estão
habilitados a ler ou modificar o conteúdo de um determinado tuplo contido no espaço.
Possibilita ainda a criação de tuplos temporários, ou seja, tuplos que permanecem no espaço de tuplos durante um espaço de tempo previamente definido, sendo estes, a menos
que sejam revalidados (através da chamada da operação renew), removidos automaticamente quando expirados.
Para a implementação de um serviço de directorias eficiente para o C2FS, foi necessário
adicionar duas novas funcionalidades ao DepSpace.
Operação replace. Uma das limitações do modelo de espaço de tuplos é a impossibilidade de modificar um tuplo no espaço. Esta limitação aparece para um serviço de
directorias quando, por exemplo, é necessário renomear um nó da árvore de directorias,
que é representado por um tuplo no DepSpace. A forma usual de se alterar tuplos é remover a versão antiga e adicionar uma nova. No entanto, esta solução levanta problemas
tanto de desempenho (pelo menos duas operações no espaço) como de consistência (as
duas operações não são atómicas). A solução encontrada para este problema foi adicionar uma nova operação à interface exportada pelo DepSpace, operação esta chamada
replace(t̄,t). Esta nova operação substitui o tuplo mais antigo no espaço que satisfaça t̄
por t, retornando true no caso de ter sido modificado algum tuplo e false caso contrário.
Capítulo 3. Metadados e Locks no C2FS
32
Suporte a triggers. Um segundo problema, mais grave, ocorre quando renomeamos
uma directoria. Quando isso acontece, é necessário actualizar o campo “nó pai” de todos
os nós dentro dessa directoria. Como veremos mais à frente (secção 3.2.2), o identificador
guardado no tuplo que permite ao sistema saber qual “nó pai” de um determinado nó é o
caminho (path) deste. À primeira vista, este problema poderia ser resolvido substituindo
este identificador por um identificador imutável (como o container_id), o qual não necessitaria ser alterado quando o nó é renomeado. Na verdade, esta abordagem seria ainda
mais problemática pois, visto o sistema operativo executar as chamadas sobre o sistema
de ficheiros utilizando o path dos nós sobre os quais pretende operar, teriam de ser feitas
várias chamadas sobre o serviço de directorias até se obter os metadados do nó pretendido,
e só então, operar sobre os mesmos. Por exemplo, supondo que existem os ficheiros
/m/foo/file e /m/fuu/file com os container_ids 3 e 4, e que as directorias /m/foo e /m/fuu
têm os container_ids 1 e 2 respectivamente, os tuplos guardados, segundo esta abordagem
alternativa, seriam (numa versão simplificada): hF ILE, 1, f ile, 3i, hF ILE, 2, f ile, 4i,
hDIR, 0, f oo, 1i e hDIR, 0, f oo, 2i. Numa operação de stat2 sobre o ficheiro /m/foo/file,
visto termos mais que um tuplo com o nome file, ao pesquisarmos por esse nome através
do template h∗, ∗, f ile, ∗i, obteríamos os tuplos hF ILE, 1, f ile, 3i e hF ILE, 2, f ile, 4i.
Em seguida, teríamos ainda de perceber, através de nova chamada ao DepSpace, qual
dos dois é referente à directoria /m/foo. Para isso seria usado o template h∗, ∗, f oo, ∗i,
obtendo então os metadados da directoria procurada, e assim o seu container_id. Neste
caso, bastariam estas duas chamadas, pois bastava comparar os container_ids dos campos “nó pai” dos tuplos obtidos da primeira chamada com o container_id do nó obtido
na segunda para perceber qual o tuplo com os metadados do ficheiro /m/foo/file. Note-se
no entanto que poderiam ser necessárias mais chamadas caso existissem mais nós no sistema com o nome foo. Como podemos perceber, esta abordagem levantaria problemas de
atomicidade e de desempenho da operação.
A abordagem utilizada para resolver este problema de forma eficiente, i.e., evitar a execução de um replace por cada nó filho do nó renomeado, foi adicionar uma nova camada
para suporte a Triggers. Quando é executada uma operação de replace no DepSpace é
activado um gatilho que, de forma recursiva, executa um conjunto de outras operações
replace nos servidores, actualizando o campo “nó pai” de todos os nós abaixo do nó
renomeado na árvore de directorias.
Uma outra função desta camada é permitir a substituição de tuplos quando um nó
é renomeado. Por exemplo, existindo os ficheiros /A e /B, se pretendermos renomear o
ficheiro /A para /B, o comportamento esperado é que o ficheiro /A deixe de existir, passando o ficheiro /B a conter os dados de /A. Neste contexto, se simplesmente modificarmos
o nome de /A para /B, passariam a existir dois nós com o mesmo nome. Neste sentido,
sempre que já exista no espaço um tuplo cujo caminho seja igual ao novo caminho de
2
Operação do sistema de ficheiros utilizada para obter os metadados de um dado nó.
Capítulo 3. Metadados e Locks no C2FS
33
um nó renomeado, este tuplo é apagado do espaço. Uma outra potencialidade desta camada é permitir utilizar valores dos metadados dos nós substituídos, ou seja, caso existam
campos no novo tuplo que não estejam definidos (tenham o valor ’*’), quando este tuplo
substitui o antigo, estes campos são preenchidos com o valor dos campos correspondentes
no antigo tuplo.
Todas as operações já referidas que são efectuadas por um trigger são executadas de
forma atómica. Note-se também que os Triggers só são requeridos quando há necessidade
de renomear um nó.
3.2.2
Serviço de Directorias
O C2FS usa um serviço de directorias que tem por base o DepSpace. Esta abordagem
faz com que os metadados possam ser guardados utilizando a abstracção de espaço de
tuplos ao mesmo tempo que permite que o serviço herde todas as garantias fornecidas
pelo serviço subjacente. Cada serviço de directorias é então cliente do DepSpace e tem
um identificador único que o identifica.
Formato dos Metadados
Os metadados de todos os ficheiros, directorias e ligações simbólicas são representados
como tuplos no espaço. Para o caso dos ficheiros e directorias, esses tuplos têm o seguinte
formato:
hNODE , parent_folder , node_name, node_type, node_metadata, container _id i
O campo parent_folder guarda o caminho do “nó pai” do nó em questão, enquanto
que o campo node_name é o nome do nó. Para obter o caminho de um determinado nó
basta, portanto, concatenar o valor do campo parent_folder com o carácter ‘\’ seguido do
valor do campo node_name. O campo node_type pode tomar o valor de FILE, DIR consoante os metadados sejam de um ficheiro ou uma directoria, respectivamente. O campo
node_metadata contém toda a informação dos metadados de um determinado nó, tais
como as permissões sobre ele por parte dos vários utilizadores do sistema, o identificador
do dono do ficheiro, o tamanho do ficheiro, o resumo criptográfico (hash) dos dados a
que este se refere e a chave simétrica utilizada para cifrar estes dados. A importância
de manter o resumo criptográfico e a chave neste serviço será explicada em detalhe mais
à frente. O campo container_id é o identificador único do contentor onde os dados de
um determinado ficheiro são armazenados. No caso das directorias, este identificador é
ignorado pelo sistema. Este identificador é criado pelo cliente do serviço de directorias
que cria o contentor. Para garantir que dois clientes não criam dois contentores com o
mesmo identificador, este é gerado concatenando o identificador do cliente no serviço de
directorias (que o serviço garante ser único) com um timestamp local.
Capítulo 3. Metadados e Locks no C2FS
Op. do Serviço de Directorias
Op. do DepSpace
getMetadata(path)
rdp(hNODE, parent(path), name(path), *, *, *, *i);
putMetadata(mdata)
cas(hNODE, parent(mdata), name(mdata), *, *, *, *i,
34
hNODE, parent(mdata), name(mdata), nodeType(mdata), mdata, contId(mdata)i);
removeMetadata(path)
inp(hNODE, parent(path), name(path), *, *, *, *i);
updateMetadata(path, mdata)
replace(hNODE, parent(path), name(path), *, *, *, *i,
hNODE, parent(mdata), name(mdata), nodeType(mdata), mdata, contId(mdata)i);
getChildren(parent)
rdAll(hNODE, parent, *, *, *, *, *i);
getLinks(contId)
rdAll(hNODE, *, *, *, *, *, contIdi);
updateLocalMetadata(contId, hash, size)
-
commitLocalMetadata(contId)
replace(hNODE, parent, name, *, *, *, *i,
hNODE, parent, name, nodeType, mdata, contIdi);
putPrivateNamespace(namespaceStats)
cas(hPRIVATE_NAMESPACE, *, *, *i,
hPRIVATE_NAMESPACE, contID, key, hashi);
getPrivateNamespace()
rdp(hPRIVATE_NAMESPACE, contID, *, *i);
Tabela 3.1: Interacção do serviço de directorias com o DepSpace.
No caso das ligações simbólicas, visto este tipo de nós consistirem num apontador
para um outro nó, alguns dos campos deste formato são utilizados para armazenar diferentes informações. Assim, no campo container_id, ao invés do identificador do contentor
de dados do nó, é guardado o caminho do nó para o qual esta ligação aponta. Os campos parent_folder e node_name são utilizados para armazenar o caminho do “nó pai”
da ligação e o seu nome, respectivamente. Os restantes campos do formato apresentado
mantêm a função anteriormente descrita, sendo que neste caso, como é fácil de perceber,
o campo node_type tem o valor SYMLINK.
Operações do Serviço de Directorias
O serviço de directorias exporta uma API que permite efectuar todas as operações necessárias
para manipular os metadados do sistema. Assim, estão disponíveis operações para adicionar, remover, alterar e obter os metadados de um nó do sistema de ficheiros. A
tabela 3.1 apresenta uma lista dessas operações e a sua interacção com o DepSpace.
Como podemos perceber, para armazenar os metadados dos nós do sistema de ficheiros,
o serviço de directorias insere tuplos no espaço. A operação usada para inserir estes tuplos é a operação cas pois permite, de uma forma atómica, inserir um tuplo no espaço
apenas no caso de não existir nenhum outro que corresponda ao mesmo nó do sistema de
ficheiros. Para obter os metadados de um dado nó, o serviço faz uma leitura ao espaço,
com a operação rdp que devolve o tuplo mais antigo no espaço que satisfaça um template
dado. Para remover tuplos do espaço é usada a operação inp do DepSpace, enquanto que
para as operações do serviço que necessitam obter os metadados de mais que um nó é
utilizada a operação rdAll. A operação inp permite remover os metadados de um nó, en-
Capítulo 3. Metadados e Locks no C2FS
35
quanto que a operação rdAll permite obter uma colecção com os tuplos que correspondam
com o template fornecido pelo serviço de directorias.
Para lidar com actualizações de metadados em consequência de actualizações de dados, o serviço permite modificar os valores do tamanho e resumo criptográfico dos dados localmente, mantendo estas alterações por tempo indeterminado até que o cliente do
serviço decida efectuar essas alterações de forma definitiva no DepSpace. Isto é usado,
e.g., quando o cliente tem de fazer escritas demoradas de dados. Neste caso o sistema
primeiro efectua a escrita dos dados numa cache em disco local, depois altera os metadados localmente e retorna ao sistema operativo, fazendo a alteração no DepSpace apenas quando a escrita dos dados terminar. No caso concreto do C2FS, este mecanismo é
útil quando o serviço de armazenamento faz as escritas para as clouds de forma assíncrona. Nesta configuração, este mecanismo permite que durante a execução das escritas
em background, geridas pelo serviço de armazenamento, o cliente possa efectuar leituras
aos dados com os metadados correctos, ao mesmo tempo que previne outros clientes do
sistema, que correm uma outra instância do serviço de directorias, de obter metadados
errados para o mesmo nó. Esta potencialidade é implementada através das operações updateLocalMetadata(contId, hash, size) e commitLocalMetadata(contId), sendo a primeira
para actualizar os valores do tamanho e resumo criptográfico dos dados localmente e a segunda para propagar estas actualizações para o DepSpace, ficando então disponíveis a
todos os clientes do sistema. Como podemos perceber na definição das operações na
tabela 3.1, a operação updateLocalMetadata(contId, hash, size) não faz qualquer operação no DepSpace. Nesta operação, os valores alterados são armazenados numa estrutura
de dados mantida na memória principal e ainda em disco local. A utilização do disco local
para armazenar estes valores é imprescindível pois, em caso de falha do serviço de directorias durante o envio dos em dados em background para a cloud-of-clouds, é possível
recuperar os metadados referentes à escrita em curso. Assim, na operação commitLocalMetadata(contId), os metadados guardados localmente são actualizados no DepSpace e
apagados tanto da estrutura de dados em memória como do disco local. Na verdade, os
únicos campos actualizados por esta operação são o tamanho e o resumo criptográfico dos
dados. Esta abordagem permite que o cliente do serviço possa fazer alterações a outros
campos dos metadados enquanto os metadados estão guardados localmente, i.e., enquanto
a escrita do ficheiro está a decorrer.
As operações putPrivateNamespace e getPrivateNamespace têm por função inserir
e obter as informações referentes ao espaço de nomes pessoal de cada cliente. Estas
operações serão descritas em pormenor na secção 3.2.4.
Controlo de Acesso aos Ficheiros
O serviço de directorias fornece um mecanismo que permite controlar o acesso aos
metadados. Este permite aos clientes definir, a qualquer instante, quais os clientes do
Capítulo 3. Metadados e Locks no C2FS
36
sistema de ficheiros que podem ler ou modificar os metadados. Este mecanismo está
assente sobre as políticas de controlo de acesso aos tuplos do DepSpace [23].
O que é feito pelo serviço de directorias é definir quais os identificadores dos clientes
com permissões de leitura e escrita sobre cada tuplo. Desta forma, um outro cliente do
sistema de ficheiros (que corre um serviço de directorias próprio com um identificador
único no DepSpace) apenas consegue obter ou alterar os metadados de nós cujos tuplos
tenham o seu identificador na lista de clientes aptos para ler ou escrever.
É com o mecanismo de controlo de acesso aos metadados descrito, aliado com o facto
de o serviço de armazenamento [40] cifrar os dados com a chave simétrica armazenada
juntamente com os metadados, que o C2FS faz controlo de acesso aos ficheiros. Para
um cliente ler os dados de um determinado ficheiro este tem que, em primeiro lugar, ter
acesso à chave usada para cifrar os mesmos. Caso este seja um cliente não autorizado,
este não conseguirá obter os metadados do ficheiro e, assim sendo, não conseguirá obter a
chave para decifrar os dados. Desta forma, mesmo que um cliente consiga obter os dados
directamente das clouds sem usar o serviço de armazenamento, este não consegue aceder
os dados em claro.
3.2.3
Cache no Serviço de Directorias
Conforme já descrito, o serviço de directorias pode realizar caching de metadados em
memória local de forma a minimizar tanto a latência de acesso aos metadados3 , quanto
o número de chamadas feitas ao DepSpace (permitindo a este atender mais clientes e
reduzir os custos da utilização deste serviço).
A cache de metadados do C2FS é concretizada utilizando tarefas temporizadas, responsáveis pela actualização dos metadados no DepSpace após a expiração de um temporizador, sendo que cada tarefa é responsável por actualizar os metadados de um único
nó. Estas tarefas são criadas com o objectivo de efectuar actualizações nos metadados
de um determinado nó no DepSpace de forma assíncrona ao sistema e com um atraso
esperado de no máximo ∆ ms, sendo ∆ um parâmetro do serviço. Este mecanismo permite também que todas as actualizações feitas aos metadados de um nó em cache durante
um intervalo de ∆ ms sejam executadas de uma única vez no DepSpace. O valor de ∆
define também por quanto tempo os metadados de um determinado nó estão em cache no
serviço de directorias. Assim, a definição deste parâmetro deve ter em conta que, quanto
maior seu valor, menor o número de chamadas feitas ao DepSpace, e maior o atraso de
propagação de alterações de metadados, o que pode ter efeitos negativos na consistência
do sistema. Para além das operações descritas na tabela 3.1, esta versão do serviço de
directorias fornece uma operação extra, chamada removeFromCache(path), responsável
por limpar da cache toda a informação referente aos metadados do nó com o caminho
3
Acedidos através das chamada stat, identificada em muitos estudos como a operação mais comumente
invocada pelos sistemas de ficheiros (como é mostrado na secção 5.2).
Capítulo 3. Metadados e Locks no C2FS
37
dado.
Os algoritmos 1, 2 e 3 descrevem em detalhe o comportamento das operações putMetada, getMetadata e updateMetadata do serviço de directorias com cache activada.
Variáveis utilizadas. Nestes algoritmos o objecto noCacheDiS representa um objecto
do serviço de directorias sem cache que disponibiliza as operações e comportamento descritos na tabela 3.1. Os objectos cache e localMetadata representam a cache de metadados e a estrutura de dados em memória principal que mantém as actualizações de metadados localmente, respectivamente. Os objectos UpdaterTask representam as tarefas temporizadas responsáveis por actualizar os metadados no DepSpace de forma assíncrona,
enquanto que o objecto scheduler representa um objecto que mantém as tarefas de actualização, e as executa com um atraso pré-definido. No algoritmo 4 há ainda os objectos
stopped e cacheDiS. O primeiro é um booleano que indica se a tarefa foi ou não cancelada,
enquanto que o segundo é um objecto do serviço de directorias com cache.
Algoritmos. No algoritmo 1 podemos ver que o nó é criado no sistema através da inserção dos seus metadados no DepSpace (linha 2). Estes metadados são também guardados em cache (linha 4), permitindo que as operações feitas sobre eles nos ∆ ms seguintes
possam ser feitas numa só chamada ao DepSpace.
Algorithm 1: putMetadata(m)
Map h String, MetadataCacheEntry i cache;
1
2
3
4
Entrada: m - metadados a inserir
início
noCacheDiS.putM etadata(m);
entry ←− M etadataCacheEntry(m, currentT ime);
cache.put(m.path, entry);
fim
A operação referente à obtenção de dados (algoritmo 2) é um pouco mais complexa.
Em primeiro lugar o serviço verifica se os metadados referentes ao nó pedido estão em
cache, caso isto não se verifique, os metadados são obtidos recorrendo ao serviço de directorias sem cache e guardados em cache, como podemos ver nas linhas 4 e 6 do algoritmo.
Caso os metadados se encontrem em cache, é necessário verificar se estes ainda se encontram válidos, ou seja, estão guardados em cache há menos de ∆ ms (linha 7). Se os
metadados guardados em cache forem inválidos, são então obtidos do DepSpace recorrendo ao serviço de directorias sem cache, como se pode observar na linha 10. Caso existam metadados guardados na estrutura localMetadata, os campos referentes ao tamanho
dos dados e resumo criptográfico guardados nos metadados desta estrutura são substituídos nos metadados a retornar por esta operação (linhas 15 e 16).
Capítulo 3. Metadados e Locks no C2FS
38
Algorithm 2: getMetadata(path)
Map h String, MetadataCacheEntry i cache;
Map h String, NodeMetadata i localMetadata;
1
2
3
4
5
6
7
8
9
10
11
12
Entrada: path - caminho do ficheiro a obter
Saída: metadados de path
início
entry ←− cache.get(path);
se (entry =⊥) então
mdata ←− noCacheDiS.getM etadata(path);
entry ←− M etadataCacheEntry(mdata, currentT ime);
cache.put(path, entry);
senão
se (currentT ime ≤ (entry.time + ∆)) então
mdata ←− entry.metadata;
senão
cache.remove(path);
mdata ←− noCacheDiS.getM etadata(path);
entry ←− M etadataCacheEntry(m, currentT ime);
cache.put(path, entry);
16
mdata0 ←− localM etadata.get(mdata.containerId);
se (mdata0 6=⊥) então
mdata.dataSize ←− mdata0 .dataSize;
mdata.dataHash ←− mdata0 .dataHash;
17
retorna mdata;
13
14
15
fim
Na operação updateMetadata apresentada no algoritmo 3, o primeiro procedimento
efectuado no caso em que os metadados do nó referente ao caminho dado não estejam em
cache (ou estejam inválidos) é obtê-los. Este procedimento é feito através da chamada da
operação getMetadata. Em seguida, caso não exista ainda nenhuma tarefa de actualização
para o nó referente ao caminho dado, essa tarefa tem de ser lançada. Esta tarefa, como
podemos ver na linha 7 do algoritmo em descrição, é agendada para ∆ ms após a execução
da tarefa menos a quantidade de tempo em que os metadados a actualizar estão em cache.
Isto acontece para garantir que não são feitas actualizações sobre metadados inválidos em
cache. Após isso basta alterar o valor dos metadados em cache pois, após (quanto muito)
∆ ms, é esse o valor enviado pela tarefa de actualização. Há, no entanto, o problema de
a operação ter por objectivo renomear um nó da árvore de directorias. Neste caso, não
basta modificar o caminho do nó e esperar que a tarefa de actualização propague essa
modificação para o DepSpace. Esta abordagem tem o problema de poder já existir um nó
cujo caminho é igual ao novo caminho do nó renomeado. Neste caso, poderia acontecer
que esse nó estivesse em cache, logo, pudesse ter uma tarefa de actualização para alterar
Capítulo 3. Metadados e Locks no C2FS
39
Algorithm 3: updateMetadata(path, m)
Map h String, NodeMetadata i cache;
Map h String, NodeMetadata i localMetadata;
1
2
3
4
Entrada: path - caminho dos metadados, m - nova versão dos metadados
início
oldMDataEntry ←− cache.get(path);
se ((oldMDataEntry =⊥) ∨ (currentT ime ≥ oldMDataEntry.time)) então
getM etadata(path) ;
// metadados ficam em cache
se (!scheduler.contains(path)) então
updaterT ask ←− UpdaterTask (path, m, N oCacheDiS, this);
t ←− (∆ − (currentT ime − entry.time));
scheduler.schedule(m.path, updaterT ask, t);
5
6
7
8
se (path 6= m.path) então
schedule.cancel(path);
cache.remove(path);
replacedMData ←− getM etadata(m.path);
se (replacedMData 6=⊥) então
se (replacedMData.numContainerLinks ≤ 1) então
localMetadata.remove(replacedMData.containerId);
9
10
11
12
13
14
15
se (cache.get(m.path) 6=⊥) então
schedule.cancel(m.path);
cache.remove(m.path);
16
17
18
noCacheDiS.updateM etadata(path, m);
senão
cache.remove(path);
entry ←− MetadataCacheEntry(m, currentT ime);
cache.put(path, entry);
19
20
21
22
fim
os seus metadados. Assim, a tarefa de actualização deste segundo nó poderia alterar os
metadados do nó renomeado. Para solucionar este problema, sempre que esta operação
tenha por objectivo renomear um nó, o serviço verifica se existem tarefas de actualização
para o nó renomeado. Caso exista, essa tarefa é abortada (linha 10). Em seguida, o serviço
verifica se existe um nó cujo caminho corresponda ao novo caminho do nó renomeado.
Caso isto se verifique, a tarefa de actualização referente a este nó, caso exista, é abortada
(linha 17).
Nas linhas 14 e 15 do algoritmo em descrição, podemos perceber que, na existência
de um nó que irá ser substituído por um nó renomeado, caso o número de ligações ao
seu contentor seja menor ou igual a um, os seus metadados são apagados da estrutura de
dados que mantém as actualizações de metadados feitas localmente. Isto acontece pois,
dada a substituição do nó em questão, o seu contentor de dados irá perder uma ligação,
Capítulo 3. Metadados e Locks no C2FS
40
logo, esta informação deixa de ser útil.
Algorithm 4: UpdaterTask.run()
NodeMetadata initialMData;
NodeMetadata mData;
Boolean stoped;
1
2
3
Entrada: m - metadados a inserir
início
se (!stopped ∧ (initialMData 6= mData)) então
noCacheDiS.updateM etadata(initialMData.path, mData);
cacheDiS.removeF romCache(initialMData.path);
4
fim
O comportamento das tarefas de actualização, que são executadas após ∆ ms pelo
Scheduler, resume-se a, caso hajam, propagar as actualizações feitas ao seu nó para o
DepSpace. Na linha 2 do algoritmo 4 são comparados os metadados iniciais com os
metadados actuais, sem a actualização efectuada apenas no caso de estes dois objectos não
coincidirem. Note-se que o objecto initialMData é obtido através da chamada do método
clone sobre o objecto mData aquando da construção da tarefa, enquanto que o objecto
mData referência o objecto de metadados mantido em cache pelo serviço de directorias.
Após as rotinas descritas acima, é chamada a operação removerFromCache(path) (linha
4), que permite ao serviço de directorias remover os metadados da estrutura cache.
3.2.4
Espaço de Nomes Pessoal
O facto de o DepSpace guardar todos os tuplos na memória principal é uma limitação
deste serviço. Desta forma, também o serviço de directorias herda esta limitação pois, o
espaço de memória das réplicas onde o DepSpace está instalado oferece um limite quanto
à quantidade de metadados que o serviço de directorias pode armazenar.
Para minimizar esta limitação introduzimos o conceito de espaço de nomes pessoal:
um objecto que guarda uma série de metadados referentes a nós que são privados ao seu
dono, ou seja, que não são partilhados. Com a utilização destes objectos, os metadados,
ao invés de serem guardados no DepSpace, são guardados numa estrutura de dados serializável. Esta estrutura é guardada juntamente com os dados do sistema de ficheiros (neste
caso, no serviço de armazenamento), sendo apenas guardado no serviço de directorias um
tipo de metadados especial que tem as informações necessárias para o utilizador poder
obter a referida estrutura de dados. O espaço de nomes pessoal é enviado para escrita no
serviço de armazenamento sempre que é feita uma modificação na estrutura de dados que
mantém os metadados.
O serviço de directorias, através das operações putPrivateNamespace e getPrivateNamespace, permite armazenar e obter a informação relativa ao armazenamento do es-
Capítulo 3. Metadados e Locks no C2FS
41
paço de nomes pessoal na cloud-of-clouds. Esta informação, tal como os metadados dos
ficheiros partilhados, é armazenada no DepSpace, sendo as permissões de escrita e leitura
do tuplo onde a esta informação é armazenada atribuídas unicamente ao dono do espaço
de nomes pessoal. Esta abordagem garante que apenas o dono do espaço de nomes pessoal
consiga obter e modificar o tuplo que armazena as informações de acesso a este objecto.
O referido tuplo tem o seguinte formato:
hPNS , container _id , key, hashi
O valor do campo container_id diz respeito ao contentor onde o espaço de nomes
pessoal é armazenado. Este identificador é único e é baseado no identificador do cliente
junto do DepSpace, podendo ser calculado pelo serviço de directorias. O campo key é
a chave simétrica que é utilizada pelo serviço de armazenamento para cifrar o espaço
de nomes pessoal, impossibilitando outros clientes de obter os metadados dos ficheiros
pessoais de um determinado cliente. Note-se que, caso não fosse utilizado este processo,
um cliente poderia obter os metadados dos ficheiros pessoais de um outro cliente, e assim,
obter as chaves usadas para encriptar os dados dos seus ficheiros. Desta forma, caso este
conseguisse obter os dados dos ficheiros referentes aos metadados obtidos, conseguiria lêlos em claro. No campo hash é armazenado o resumo criptográfico do espaço de nomes
privado. A utilidade deste é permitir ao serviço de armazenamento verificar a validade
do objecto mantido em cache. Caso o hash do objecto mantido em cache não coincida
com o hash mantido pelo serviço de directorias, uma nova versão do objecto tem de ser
lida da cloud-of-clouds. Embora este acontecimento seja invulgar (dado nenhum outro
cliente conseguir alterar este objecto), esta verificação necessita ser feita pois, visto os
dados em cache serem guardados no disco local, pode acontecer que esta informação
tenha sido apagada pelo utilizador ou que o sistema a tenha substituído por motivos de
falta de espaço livre em disco.
Na prática, um espaço de nomes pessoal fornece sensivelmente as mesmas operações
que o serviço de directorias, no entanto, todas as operações são executadas localmente. A
utilização desta técnica permite então, não só minimizar a limitação do DepSpace relacionada com o armazenamento dos tuplos na memória principal, mas também, aumentar
o desempenho do manuseamento dos metadados de nós privados.
Cada utilizador do sistema de ficheiros tem apenas um espaço de nomes pessoal, sendo
este obtido do serviço de armazenamento sempre que o sistema de ficheiros é montado.
3.2.5
Serviço de Directorias sem Partilha de Ficheiros
Para utilizadores que têm como objectivo utilizar o C2FS para armazenar ficheiros
na cloud-of-clouds sem a necessidade de os partilhar com outros utilizadores, foi desenvolvido um serviço de directorias sem partilha de ficheiros. Este serviço de directorias é
Capítulo 3. Metadados e Locks no C2FS
42
concretizado localmente e, à semelhança do espaço de nomes privado, é concretizado utilizando um objecto serializável que mantém várias estruturas de dados onde são guardados os metadados de todos os nós do sistema, objecto este que é armazenado nas clouds
recorrendo ao serviço de armazenamento.
Este serviço de directorias, à excepção das operações relacionados com o espaço de
nomes pessoal, fornece as mesmas operações que o serviço de directorias com partilha
de ficheiros, tendo um comportamento similar ao mesmo. Nesta versão do serviço de
directorias, as operações relacionadas com o espaço de nomes pessoal deixam de fazer
sentido pois, não havendo partilha de ficheiros, todos os ficheiros passam a ser pessoais.
À imagem do objecto de espaço de nomes pessoal, também o objecto que mantém todos
os metadados deste serviço é serializado e armazenado nas clouds sempre que existe uma
alteração de metadados em algum nó deste serviço de directorias.
Este serviço, para além de aumentar o desempenho do sistema, visto todos os metadados serem manuseados localmente, permite também diminuir os custos de utilização do
C2FS pois, ao contrário do serviço de directorias apresentado anteriormente, não necessita ter nenhum serviço instalado em instâncias fornecidas por provedores de computação
nas clouds, não havendo custos com a manutenção das mesmas.
3.3
Serviço de Locks
Para coordenar o acesso concorrente por parte de processos escritores aos ficheiros do
C2FS com o objectivo de manter a consistência dos mesmos, foi desenvolvido um serviço
de locks. Como referido anteriormente, também este serviço foi desenvolvido tendo o
DepSpace como base.
No C2FS, antes de efectuar uma escrita num ficheiro, um cliente têm de reservar o
contentor de dados desse ficheiro através da aquisição de um lock. Este lock é efectuado
sobre o contentor de dados pois, devido ao facto do C2FS suportar ligações fortes (hard
links) entre ficheiros, caso os locks fossem feitos sobre ficheiros, poderiam existir dois
clientes com locks sobre diferentes ficheiros a escrever para o mesmo contentor de dados,
o que poderia levar a escritas inconsistentes.
Para isto, o serviço de locks exporta uma interface que permite aos clientes do serviço
adquirir e libertar um lock sobre um dado contentor de dados através da disponibilização de três operações: tryAcquire, release e renew. No algoritmo 5 são apresentadas
estas operações, assim como as chamadas feitas ao DepSpace aquando da sua execução.
Relembro que é assumido que o DepSpace implementa políticas de controlo de acesso
que protegem o espaço de tuplos [25]
A primeira operação do algoritmo permite ao cliente tentar reservar um contentor para
escrita, retornando true em caso de sucesso e false caso contrário. Assim, quando um
cliente tenta adquirir o lock sobre um contentor de dados o serviço tenta inserir um tuplo
Capítulo 3. Metadados e Locks no C2FS
43
Algorithm 5: Operações do serviço de locks.
1 procedimento tryAquire(contId, time)
2 início
3
retorna cas(hLOCK, contIdi, hLOCK, contIdi, time);
fim
4
5
6
7
8
9
procedimento release(contId)
início
inp(hLOCK, contIdi);
fim
procedimento renew(contId, time)
início
renew(hLOCK, contIdi, time);
fim
de lock sobre o mesmo contentor no DepSpace. Esta aquisição, assim como a operação
feita pelo cliente, só tem sucesso no caso de o serviço de locks obter true da operação cas
efectuada no DepSpace.
Para prevenir que outros clientes C2FS libertem locks que não lhes pertencem, através
da remoção dos tuplos que representam locks, o serviço de locks configura o tuplo de lock
inserido no espaço com permissões de escrita apenas para o seu criador. Desta forma,
apenas quem cria o tuplo de lock pode removê-lo.
Quando um cliente deste serviço, neste caso, o agente C2FS, não consegue obter o
lock, espera um intervalo de tempo (de aproximadamente um segundo) e só depois volta
a tentar reservar o mesmo contentor.
A operação release permite ao cliente libertar um contentor de dados, caso este esteja
reservado. Nesta operação o serviço, através da operação inp do DepSpace, remove o
tuplo de lock do espaço. Assim, quando um outro utilizador tentar reservar o mesmo
contentor de dados, o serviço de locks a correr na sua máquina irá obter sucesso quando
efectua a chamada cas da operação tryAquire.
Para tolerar a falha de um cliente detentor de um lock, são usados tuplos de lock com
tempos de expiração (que desaparecem do espaço após um intervalo de tempo [41]), que
garantem que os locks acabam por ser libertados se os seus detentores falharem. Esta
garantia é indispensável pois, caso contrário, a falha de um cliente detentor de um lock
poderia resultar na indisponibilidade permanente do contentor reservado. Assim, quando
o cliente tenta adquirir um lock sobre um ficheiro, este tem de fornecer a quantidade
de tempo na qual deseja que este lock se encontre válido (a variável time dada como
argumento na operação de aquisição do lock). Note-se que o serviço de locks deixa para
o cliente a responsabilidade de renovar este lock, através da chamada da operação renew.
Esta operação executa a operação renew do DepSpace para aumentar o tempo de validade
do tuplo por mais uma quantidade de tempo, sendo essa quantidade de tempo dada por
Capítulo 3. Metadados e Locks no C2FS
44
time.
No caso do C2FS, o responsável por revalidar os locks sobre os contentores de dados é
o agente C2FS. Este módulo mantém uma lista de tarefas responsáveis por manter válidos
todos os locks sobre os contentores de dados de todos os ficheiros abertos a cada instante.
Aquando do fecho de um ficheiro, o agente C2FS acaba a execução da tarefa responsável
por fazer as revalidações do lock sobre o contentor de dados desse ficheiro e liberta esse
lock. Desta forma, o contentor de dados fica então livre para ser reservado por outro
processo.
O agente C2FS é também responsável por, aquando da abertura de um ficheiro, decidir
se é ou não necessário reservar o respectivo contentor de dados. Sempre que o ficheiro a
ser aberto é pessoal, não é necessário obter o lock sobre ele. Um ficheiro é considerado
pessoal caso este pertença ao espaço de nomes pessoal ou caso o serviço de directorias em
uso pelo sistema de ficheiros não permita a partilha de ficheiros. Como é fácil de perceber, se um ficheiro é pessoal, nenhum outro utilizador irá ter acesso a ele e, assim, não
precisa ser considerado como escritor concorrente. No entanto, para controlar o acesso
concorrente a um ficheiro pessoal por parte de diferentes processos escritores na mesma
máquina, o agente C2FS mantém, a cada instante, uma lista dos contentores de dados dos
ficheiros abertos para escrita, não permitindo a abertura de nenhum outro ficheiro com o
mesmo contentor por parte de outro processo.
A prova de que este algoritmo satisfaz as propriedades de um algoritmo de locks está
no apêndice A.
3.4
Consistência no C2FS
Visto os provedores de armazenamento nas clouds fornecerem apenas garantia de consistência eventual [51], um dos objectivos do C2FS é aumentar estas garantias, fornecendo
aos seus clientes uma garantia de consistência forte. Neste contexto, um dos problemas
é fornecer um serviço de armazenamento consistente a partir de clouds de armazenamento eventualmente consistentes. Para isso, é necessária a utilização de uma âncora
de consistência, um serviço consistente que permite armazenar pequenas quantidades de
informação. No C2FS, o serviço utilizado como âncora de consistência é o serviço de
directorias. Note-se que as versões do serviço de directorias com partilha de ficheiros
tiram partido do DepSpace [23] para tal.
Em termos gerais, o mecanismo utilizado consiste em, aquando de uma escrita num
ficheiro, o cliente actualiza em primeiro lugar os dados no serviço de armazenamento, e
só depois os metadados no serviço de directorias. Assim, quando um outro cliente obtém
os metadados com a nova versão dos metadados, este vai saber que, eventualmente, os
dados irão estar disponíveis.
Para a implementação deste mecanismo, foi necessário adicionar uma nova operação
Capítulo 3. Metadados e Locks no C2FS
45
ao DepSky [24] chamada readMatching que, dado o identificador do contentor de dados
e um resumo criptográfico referente aos dados que o cliente pretende obter, devolve os
dados mais actualizados que correspondam ao resumo criptográfico fornecido [40]. Esta
operação permite, caso o resumo criptográfico não corresponda à versão mais recente
dos dados, obter uma versão antiga dos dados que corresponda ao mesmo. Esta última
funcionalidade permite obter dados consistentes mesmo que, aquando de uma leitura concorrente com uma escrita e após a obtenção dos metadados (e assim, do resumo criptográfico), os dados a ler das clouds sejam mais recentes que os metadados obtidos. Isto pode
acontecer pois, no processo de escrita, os dados são escritos antes de actualizar os metadados, ao passo que, no processo de leitura, os metadados são obtidos em primeiro lugar.
Com esta abordagem temos a possibilidade de obter metadados referentes a uma versão
antiga dos dados, problema este resolvido pela operação readMatching.
Quando o resumo criptográfico fornecido a esta operação não diz respeito a nenhuma
das versões dos dados armazenadas nas clouds significa que, devido às limitações de consistência dos provedores de armazenamento nas clouds, estes ainda não estão disponíveis,
sabendo nós que, eventualmente o estarão. Neste caso, a operação readMatching do DepSky retorna um erro. Para tentar obter a nova versão dos dados, quando o serviço de
armazenamento obtém um erro desta operação, este volta a tentar obter os dados após um
tempo (normalmente 5 segundos), fazendo este processo três vezes. Caso após as três
tentativas não consiga obter os dados referentes à versão pedida, é retornado um erro. No
caso do C2FS, quando o agente C2FS obtém erro de uma leitura no serviço de armazenamento, também a operação de leitura do sistema de ficheiros retorna um erro.
Neste contexto, a operação de escrita no C2FS segue os seguintes passos:
1. Escrever os dados com o resumo criptográfico h no DepSky, recorrendo ao serviço de armazenamento.
2. Escrever os metadados com o novo valor h no serviço de directorias.
A operação de leitura, por sua vez, requer os seguintes passos:
1. Ler os metadados do ficheiro com o resumo criptográfico h, através do serviço de directorias.
2. Utilizar o serviço de armazenamento para ler a versão dos dados correspondentes a h através
da operação readMatching do DepSky.
Devido à utilização deste mecanismo, aliada com o facto do serviço de locks não
permitir escritas concorrentes sobre o mesmo contentor de dados, o C2FS garante uma
semântica de consistência regular [34] para o armazenamento de ficheiros assegurando
que, aquando de uma operação de leitura concorrente a uma operação de escrita sobre os
dados de um ficheiro, ou os dados obtidos são o valor anterior à escrita, ou são o valor
que está a ser escrito.
Capítulo 3. Metadados e Locks no C2FS
3.5
46
Considerações Finais
Neste capítulo foi apresentado o C2FS em termos gerais, assim como os serviços de
directorias e locks. Foram apresentadas várias versões do serviço de directorias, sendo
descrito em cada uma o mecanismo utilizado para armazenar e manusear os metadados
do C2FS. Sobre o serviço de locks, para além do modo de funcionamento, foram ainda
apresentadas as garantias fornecidas pelo serviço. Foram também descritas as alterações
necessárias no DepSpace para que fosse possível implementar os referidos serviços.
Descrevemos ainda um mecanismo que permite melhorar as propriedades de consistência oferecidas pelas clouds de armazenamento utilizadas pelo C2FS.
No próximo capítulo irá ser descrita a forma como estas ideias foram concretizadas.
Capítulo 4
Concretização dos Serviços de
Directorias e de Locks do C2FS
Neste capítulo serão apresentados os detalhes de concretização do trabalho desenvolvido. Em primeiro lugar serão descritas as tecnologias utilizadas para a implementação dos módulos desenvolvidos. Em seguida será descrito o algoritmo utilizado para
implementação da camada de suporte a triggers do DepSpace. Serão também apresentados alguns diagramas UML, nomeadamente o diagrama de classes e os diagramas de
sequência das operações mais relevantes do serviço de directorias.
4.1
Considerações Gerais
Todos os componentes dos serviços de directorias e de locks foram implementados na
linguagem de programação JAVA. Esta escolha justifica-se com o facto de o DepSpace
ter sido concretizado nesta linguagem de programação. Há ainda o facto de o serviço de
armazenamento fazer uso do DepSky, também ele implementado em JAVA. Assim, esta
escolha vai ao encontro de facilitar a integração de todos estes componentes.
O primeiro serviço a ser concretizado foi o de locks. Após um estudo para encontrar um mecanismo que garantisse o acesso exclusivo a uma hipotética zona crítica por
parte de vários processos concorrentes utilizando unicamente o DepSpace, foi então implementado este serviço já com a preocupação de fornecer uma interface que permitisse
aos seus clientes reservar diferentes contentores de dados, sendo que um mesmo processo
pode reservar mais que um contentor. Na prática, bastou apenas generalizar o mecanismo
inicialmente estudado para este fornecer uma interface que permitisse o acesso exclusivo
a várias zonas críticas (a reserva de vários contentores de dados).
O segundo passo foi desenvolver o serviço de directorias sem cache. Aqui houve a
preocupação de desenvolver uma interface genérica o suficiente para este serviço de tal
forma que este pudesse ser utilizado para armazenar os metadados de outros sistemas de
ficheiros que não o C2FS.
47
Capítulo 4. Concretização dos Serviços de Directorias e de Locks do C2FS
48
Por questões de desempenho e de redução de custos, o passo seguinte foi desenvolver
o serviço de directorias com cache. Para garantir eficiência no que diz respeito ao acesso
aos metadados em cache, este serviço utiliza instâncias da classe HashMap do pacote
java.util do JAVA para guardar estes metadados. No que diz respeito às tarefas de actualização, foi utilizado um objecto do tipo java.util.Timer que permite, de forma fácil,
agendar a execução de cada tarefa de actualização para um momento no futuro.
Por fim foram desenvolvidos o espaço de nomes pessoal e o serviço de directorias sem
partilha de ficheiros.
Tendo isto, podemos perceber que o serviço de directorias pode assumir vários modos
de funcionamento, sendo eles:
• NoCacheDirectoryService: O serviço de directorias não mantém metadados em
cache permitindo, no entanto a partilha de ficheiros entre vários utilizadores. Neste
caso, os metadados dos ficheiros pessoais de cada utilizador são mantidos no seu
espaço de nomes pessoal.
• DirectoryServiceWTempCache: O serviço mantém em cache os metadados recentemente utilizados, sendo possível configurar o tempo de validade dos mesmos
(através do parâmetro ∆). Tal como no modo de funcionamento anterior, também neste caso é possível a partilha de ficheiros, sendo também os metadados dos
ficheiros privados de cada cliente mantidos no espaço de nomes pessoal. Este modo
de funcionamento tem um desempenho superior ao anterior.
• NoShareDirectoryService: Neste caso, todos os metadados são mantidos em estruturas de dados locais, não fazendo uso do DepSpace [23], e assim, não permitindo a partilha de ficheiros. No entanto, este modo de funcionamento tem um
desempenho significativamente superior quando comparado com os restantes.
No que diz respeito à concretização, o serviço de directorias sem partilha de ficheiros
e o espaço de nomes pessoal são muito similares. Ambos guardam todos os metadados
em instâncias da classe HashMap, visto esta ser serializável e eficiente no que diz respeito
ao tempo de acesso aos metadados, e disponibilizam sensivelmente os mesmos métodos
(sendo que o serviço de directorias sem partilha de ficheiros respeita a interface do serviço
de directorias). Na prática, a diferença essencial entre eles reside no facto de, enquanto
que o armazenamento do espaço de nomes pessoal nas clouds é da responsabilidade do
agente C2FS, no caso dos metadados do serviço de directorias sem partilha de ficheiros é
o próprio serviço que serializa as suas estruturas e as armazena na cloud-of-clouds. Esta
abordagem aparece com a necessidade de generalizar o código do agente C2FS pois, de
acordo com a configuração do sistema de ficheiros, aquando da montagem do sistema de
ficheiros é criada apenas uma instância de serviço de directorias, sendo apenas necessário
garantir que não é usado o espaço de nomes pessoal quando não há partilha de ficheiros.
Capítulo 4. Concretização dos Serviços de Directorias e de Locks do C2FS
Classe
LockService
NoCacheDirectoryService
DirectoryServiceWTempCache
NoShareDirectoryService
PrivareNamespace
NodeMetadata
FileStats
PrivateNamespaceStats
MetadataUpdaterTimerTask
C2FSAgent
Total
49
Núm. de Linhas de Código
39
234
264
228
36
279
221
30
77
988
2396
Tabela 4.1: Número de linhas de código dos módulos desenvolvidos.
Assim, quando há partilha de ficheiros, o agente C2FS é responsável por, a cada alteração nos metadados do espaço de nomes pessoal, serializar todo o objecto e armazena-lo
através do serviço de armazenamento, ao passo que, quando não há partilha de ficheiros,
todos os metadados são armazenados no serviço de directorias, sendo este responsável
por serializar e, recorrendo ao serviço de armazenamento, armazenar as suas estruturas
de dados na cloud-of-clouds.
A tabela 4.1 apresenta o número de linhas de código das várias classes dos referidos
serviços assim como o número linhas da classe C2FSAgent, a classe onde é feita a integração dos serviços de armazenamento, locks e directorias do C2FS. Note-se que esta
classe foi desenvolvida em parceria com o autor do serviço de armazenamento de dados
do C2FS [40].
4.2
Trigger de Substituição de Tuplos no DepSpace
Como já referido anteriormente (secção 3.2.1), para permitir a atomicidade e aumentar o
desempenho das operações de rename sobre nós do serviço de directorias do C2FS, foi
necessária a adição de uma nova operação (replace) e de uma nova camada ao DepSpace,
camada essa concretizada numa nova classe chamada ReplaceTriggerLayer.
Basicamente, à excepção da operação replace, todas as operações do DepSpace são
implementadas simplesmente reencaminhando a operação para as camadas superiores.
No caso da operação replace, para alterar o campo “nó pai” de todos os filhos de uma
directoria renomeada, é necessária a utilização de um procedimento recursivo. O algoritmo 6 apresenta o comportamento da operação replace na camada de Trigger. Neste
algoritmo, são referidas as funções path, name e parent que, dado um tuplo de metadados
devolvem o caminho do nó, o seu nome e o caminho do seu “nó pai”, respectivamente.
Capítulo 4. Concretização dos Serviços de Directorias e de Locks do C2FS
50
Há ainda a função setParent que permite alterar o valor do campo referente ao caminho
do “nó pai” num tuplo de metadados.
Algorithm 6: Concretização da operação replace na camada de trigger
procedimento replace(template, tuple)
1 início
2
se (path(template) 6= path(tuple)) então
3
tupleT emplate ←− hN ODE, parent(tuple), name(tuple), ∗, ∗, ∗i;
4
inp(tupleT emplate);
5
retorna replaceN odeAndChildren(template, tuple);
retorna upperLayer.replace(template, tuple);
6
fim
7
8
9
10
11
12
13
14
15
16
procedimento replaceNodeAndChildren(template, tuple)
início
result ←− upperLayer.replace(template, tuple);
parent ←− path(template);
childrenList ←− rdAll(hN ODE, parent, ∗, ∗, ∗, ∗i);
para cada (child ∈ childrenList) faça
templateN ew ←− hN ODE, parent, name(child), ∗, ∗, ∗i;
parentN ew ←− parent(child);
tupleN ew ←− child;
tupleN ew.setP arent(parentN ew);
replaceN odeAndChildren(templateN ew, tupleN ew);
retorna result;
17
fim
Como já referido, esta camada tem a função de permitir que, quando uma directoria
é renomeada, o campo “nó pai” dos seus filhos seja actualizado com o seu novo caminho
de forma atómica e eficiente. Para além disso, esta camada tem a função de, caso exista um nó no serviço de directorias com o mesmo caminho que o futuro caminho do nó
renomeado, eliminar o seu tuplo de metadados do espaço de tuplos. Esta última particularidade pode ser vista nas linhas 3 e 4 do algoritmo.
O procedimento replaceNodeAndChildren é responsável por actualizar os metadados
dos “nós filhos” do nó renomeado. Em primeiro lugar, na linha 8 do algoritmo em descrição, é feita a substituição dos tuplos (através da chamada à operação replace da camada superior à ReplaceTriggerLayer no DepSpace). As seguintes linhas do algoritmo
fazem a recursão deste procedimento, permitindo a actualização dos nós abaixo do nó
renomeado na árvore de directorias. Para isso, são obtidos todos os nós filhos do nó
renomeado (linha 10) através da chamada rdAll, e para cada um destes nós é construído
um novo tuplo no qual o valor do campo “nó pai” é actualizado (linhas 14 e 15), sendo
feita posteriormente a substituição destes tuplos e dos seus filhos através da chamada do
corrente procedimento (linha 16).
Capítulo 4. Concretização dos Serviços de Directorias e de Locks do C2FS
4.3
51
Diagramas UML
Nesta secção são apresentados alguns diagramas UML referentes ao trabalho desenvolvido. Serão apresentados um diagrama de classes dos componentes desenvolvidos
e diagramas de sequência referentes às operações de obtenção, alteração e inserção de
metadados no serviço de directorias com cache.
4.3.1
Diagrama de Classes
A figura 4.1 apresenta o modelo de classes dos serviços de directorias e de locks. Neste
diagrama podemos analisar em detalhe as várias ligações entre os componentes.
A classe C2FSAgente concretiza o agente C2FS. Como podemos perceber, esta classe
mantém uma instância de cada um dos seguintes componentes: DirectoryService, LockService, PrivateNamespace e PrivateNamespaceStats. No desenvolvimento deste componente houve a preocupação de permitir que, caso seja necessário desenvolver um novo
serviço de directorias com um comportamento diferente, não seja necessário alterar todo
o código do componente, bastando adequar o objecto instanciado no objecto do tipo DirectoryService de acordo com a configuração do sistema. Actualmente, como se pode
perceber no diagrama, os objectos que podem ser instanciados são objectos do tipo NoCacheDirectoryService, DirectoryServiceWTempCache e NoShareDirectoryService.
No caso do serviço de directorias com cache, concretizado na classe DirectoryServiceWTempCache, são mantidas duas Maps, uma com objectos do tipo MetadataCacheEntry, e outra com as tarefas de actualização a correr a cada instante, e ainda um objecto do
tipo NoCacheDirectoryService. Na classe MetadataCacheEntry é mantido um objecto
do tipo NodeMetadata e ainda um inteiro que indica o instante em que os metadados
foram inseridos na cache. É na classe NodeMetadata que são mantidas todas as informações dos metadados de cada nó. Esta classe mantém um objecto do tipo FileStats com
todos os valores dos metadados a ser utilizados localmente, ao passo que os restantes
campos do objecto NodeMetadata são vocacionados a manter as informações relativas
à partilha de ficheiros. A classe NodeMetadata fornece também o método getAsTuple
que transforma o objecto de metadados num tuplo a guardar no DepSpace, respeitando o
formato apresentado na secção 3.2.2. O campo node_metadata apresentado no referido
formato é, na prática, uma instância da classe FileStats apresentada anteriormente. O
facto de esta versão do serviço de directorias manter um objecto do serviço de directorias sem cache prende-se com o objectivo de delegar a responsabilidade da interacção
com o DepSpace. Com esta decisão de desenho, a classe DirectoryServiceWTempCache
é responsável apenas por gerir os metadados em cache, utilizando a classe NoCacheDirectoryService, para interagir com o DepSpace, manuseando os metadados no DepSpace.
Uma outra coisa que se pode observar no diagrama é o facto de cada tarefa de actualização (classe MetadataUpdaterTimerTask) manter objectos do serviço de directorias com e
Capítulo 4. Concretização dos Serviços de Directorias e de Locks do C2FS
52
sem cache. Isto permite que a actualização dos metadados seja feita no DepSpace através
da classe NoCacheDirectoryService e que, após isto, os metadados sejam removidos da
cache na classe DirectoryServiceWTempCache (através da chamada do método removeFromCache desta classe).
As classes PrivateNamespace e PrivateNamespaceStats concretizam o mecanismo de
espaço de nomes pessoal. A classe PrivateNamespace é responsável de armazenar os
metadados do espaço de nomes pessoal, enquanto que a classe PrivateNamespaceStats
contém as informações relativas ao contentor de dados e resumo criptográfico do objecto
PrivateNamespace armazenado na cloud-of-clouds.
4.3.2
Diagramas de Sequência
As figuras 4.2, 4.3 e 4.4 representam diagramas de sequência que ilustram o fluxo
de execução das operações de obtenção, inserção e alteração de metadados no serviço de
directorias com cache. Nestes diagramas foi ignorado o lançamento de excepções com
vista a simplificar a percepção da informação por eles representada. As excepções são
lançadas sempre que, aquando de uma chamada ao DepSpace por parte do serviço de
directorias sem cache, ocorre um problema de conexão com os servidores. Para além
disto, é também lançada uma excepção quando o resultado obtido da execução de uma
chamada ao DepSpace não cumpre a semântica dessa operação. Exemplos disso são a
tentativa de inserir um tuplo de metadados referente um novo nó que não tem sucesso, o
que significa que o nó já existe no serviço, ou no caso de não obter sucesso nas operações
de busca e actualização de tuplos de metadados, o que significa que o nó não existe no
sistema de ficheiros. Em seguida, serão descritos os referidos diagramas de sequência.
Inserção de metadados. A figura 4.2 apresenta o diagrama de sequência da operação
de inserção de metadados no serviço de directorias com cache.
Nesta operação, o cliente é responsável por criar o objecto do tipo NodeMetada com
os metadados a guardar. Em primeiro lugar, é utilizado o objecto do serviço de directorias
sem cache para inserir os metadados no DepSpace. Embora o diagrama referido não
apresente este nível de detalhe, para obter o tuplo de metadados referente ao objecto
NodeMetadata a inserir, basta utilizar o método getAsTuple desta classe.
Em seguida, o objecto NodeMetadata referente aos metadados inseridos, é guardado
no Map de metadados em cache. É também criada e guardada no respectivo Map a tarefa
de actualização referente aos metadados do nó inserido no serviço.
Obtenção de metadados. Para obter os metadados de um nó, o agente C2FS chama a
operação getMetadata do serviço de directorias fornecendo o caminho do nó desejado. A
figura 4.3 ilustra o fluxo de execução desta operação.
O primeiro passo a fazer é perceber se os metadados desse nó estão guardados em
cache. Caso isto se verifique, os metadados em cache são utilizados, caso contrário, os
Capítulo 4. Concretização dos Serviços de Directorias e de Locks do C2FS
Figura 4.1: Diagrama de classes dos serviços de directorias e locks.
53
Capítulo 4. Concretização dos Serviços de Directorias e de Locks do C2FS
54
Figura 4.2: Diagrama de sequência de uma operação inserção de metadados
metadados são obtidos do DepSpace recorrendo ao objecto NoCacheDirectoryService. É
neste ponto que é verificada a existência do nó cujos metadados são para obter. Caso a
operação rdp feita ao DepSpace não retorne nenhum resultado, é lançada uma excepção.
Caso o nó exista, é então construído o objecto NodeMetadata que representa os metadados
obtidos. Os metadados obtidos são então guardados em cache através da inserção dos
mesmos num Map que mantém todos os objectos NodeMetadata em cache.
Por fim, é necessário verificar se existem modificações nos metadados guardados localmente (à espera de serem propagados para o DepSpace) referentes ao contentor de
dados do nó em questão. Os valores do resumo criptográfico (hash) e o tamanho dos dados são então actualizados no objecto FileStats dos metadados a devolver com os valores
guardados localmente.
Actualização de metadados. O fluxo de execução aquando de uma operação de actualização de metadados é apresentado na figura 4.4. Nesta operação, o primeiro passo a ser
feito pelo serviço de directorias com cache é certificar-se de que os metadados a serem
alterados são mantidos em cache. A chamada da operação getMetadata (descrita acima)
garante isso.
Após a obtenção dos metadados, caso não exista ainda nenhuma tarefa de actualização para estes, é necessário lançar uma tarefa deste tipo. É então construída uma nova
tarefa que é inserida na Map de tarefas em execução, sendo depois agendada para execução através do objecto do tipo Timer. Para facilitar a compreensão deste diagrama,
este objecto foi ignorado, sendo o agendamento da tarefa representada com a chamada
run(DELTA) sobre a instância upTask da classe UpdaterTask.
Após isto, é necessário perceber se a operação em curso tem como objectivo renomear
um nó. Caso isto se verifique, são feitas uma sequência de operações (já descritas na
secção 3.2.3), nomeadamente a gestão das tarefas de actualização em curso e das actualizações dos metadados locais, para garantir o correcto funcionamento desta operação.
Caso a operação em curso não tenha por objectivo a alteração do caminho de um nó, os
metadados são alterados apenas na cache através da remoção dos antigos metadados e
inserção dos novos no Map que mantém os metadados em cache.
Capítulo 4. Concretização dos Serviços de Directorias e de Locks do C2FS
Figura 4.3: Diagrama de sequência de uma operação de obtenção de metadados.
55
Capítulo 4. Concretização dos Serviços de Directorias e de Locks do C2FS
Figura 4.4: Diagrama de sequência de uma operação de actualização de metadados.
56
Capítulo 4. Concretização dos Serviços de Directorias e de Locks do C2FS
4.3.3
57
Considerações Finais
Nesta secção foram descritos os detalhes de concretização dos serviços de directorias e
de locks. Foram explicadas as decisões de desenho para a implementação destes serviços,
tal como a interacção entre os vários componentes dos mesmos.
Na próxima secção será apresentada uma avaliação experimental dos mesmos serviços,
sendo avaliado desempenho de cada operação fornecida por estes.
Capítulo 4. Concretização dos Serviços de Directorias e de Locks do C2FS
58
Capítulo 5
Avaliação Experimental
Neste capítulo é apresentada uma avaliação do desempenho do serviço de locks e de
diferentes versões do serviço de directorias, com e sem partilha de ficheiros. Em primeiro
lugar será apresentado um estudo sobre o número de operações de metadados feitas pelos vários benchmarks. Em seguida serão mostradas medições feitas sobre as operações
do DepSpace usadas pelos serviços desenvolvidos, de forma a perceber de que forma é
que a latência destas operações condiciona o seu desempenho. É também feita uma comparação entre a latência média da operação de obtenção de metadados (getMetadata) e a
operação rdp do DepSpace, utilizando o serviço de directoria com diferentes valores para
o parâmetro ∆.
Serão apresentados também o tempo de execução de alguns benchmarks aplicados ao
C2FS e ainda o tempo de execução de algumas chamadas feitas ao sistema de ficheiros por
esses benchmarks, tendo estes experimentos sido efectuados, novamente, com diferentes
valores para o parâmetro ∆.
Será por fim apresentado um estudo ao desempenho do sistema na presença de diferentes percentagens de ficheiros pessoais.
5.1
Metodologia
As medições apresentadas neste capítulo foram obtidas através da execução de alguns
benchmarks sobre o sistema de ficheiros. Os benchmarks utilizados foram: o PostMark [33], que simula um servidor de e-mail; e o Filebench [7], que permite exercitar
vários workloads sobre um sistema de ficheiros. A escolha destes dois benchmarks devese ao facto de ambos serem adequados para testar o desempenho dos metadados de um
sistema de ficheiros [49].
Na utilização do Filebench, foram utilizados três workloads para testar os metadados
do sistema: o file server, o create files e o copy files. O file server simula um servidor
de ficheiros, criando, eliminando e operando sobre vários ficheiros. Os workloads create
files e copy files têm como função a criação de ficheiros no sistema de ficheiros. A escolha
59
Capítulo 5. Avaliação Experimental
60
destes workloads deve-se ao facto de as aplicações desktop dos dias de hoje fazerem um
uso assinalável de ficheiros temporários [30], sendo, portanto, importante o desempenho
do sistema de ficheiros na criação, cópia e eliminação de ficheiros.
Os benchmarks utilizados foram configurados da seguinte forma:
• O PostMark foi configurado para operar sobre 500 ficheiros, com tamanhos compreendidos entre os 500 bytes e os 9.77KB.
• O workload file server, por sua vez, foi configurado para manter três tarefas a operar
sobre 1000 ficheiros, com tamanho de aproximadamente 128KB, aleatoriamente
organizados numa árvore de directorias com uma profundidade média de cinco nós.
• No workload create files são utilizadas duas tarefas para criar 1000 ficheiros de
aproximadamente 16KB cada, organizados numa árvores de directorias com uma
profundidade de aproximadamente cinco nós. Por fim, o workload copy files cria
uma cópia de uma árvore de directorias com uma profundidade aproximada de 20
nós, com 1000 ficheiros de aproximadamente 16KB no sistema de ficheiros.
A utilização de ficheiros de tamanho tão baixo prende-se com o facto de o foco deste
trabalho ser o desempenho do sistema para diferentes configurações do serviço utilizado
para armazenar os seus metadados. Desta forma, foram utilizados ficheiros de pequenas
dimensões de forma a minimizar o tempo gasto na execução dos benchmarks.
Na execução destas experiências, as réplicas do DepSpace utilizadas pelo serviço
de directorias estavam instaladas no Amazon EC2 em máquinas virtuais de configuração standard, instaladas na zona de disponibilidade da Europa (Irlanda). O sistema
de ficheiros estava montado num computador portátil com aproximadamente 2 anos localizado em Lisboa, utilizando um serviço de internet com ligação de 24.66 Mbps de
download e 5.16 Mbps de upload1 .
Todos os resultados apresentados resultam da média dos valores obtidos de aproximadamente dez execuções dos experimentos.
5.2
Número de Operações sobre os Metadados
A tabela 5.1 mostra o número de chamadas de sistema, que resultam na leitura, escrita
ou actualização de metadados efectuadas por cada um dos benchmarks anteriormente
descritos. Note-se que visto que os benchmarks utilizados simulam o comportamento
de aplicações reais, podemos perceber que as chamadas feitas por estas serão da mesma
ordem que as apresentadas.
1
Valores obtidos do site www.speedtest.net, medindo o débito da ligação entre a localização do cliente
(Lisboa) e um servidor na Irlanda (localização onde as réplicas do DepSpace estavam instaladas)
61
Capítulo 5. Avaliação Experimental
Operação
stat
flush
mknod
unlink
mkdir
Total
PostMark FileServer CreateFiles CopyFiles
2896
50240
3804
8790
1264
15433
1000
3001
764
5683
1000
2000
764
0
0
0
0
226
226
113
5688
71582
6030
13904
Total
65730
20698
9447
764
565
97204
Percent.
67.6%
21.3%
9.7%
0.8%
0.6%
100%
Tabela 5.1: Número de operações do sistema de ficheiros chamadas pelos benchmarks.
Como podemos ver na tabela, a operação do sistema de ficheiros stat é a operação que
mais vezes é chamada (com 67.6% da totalidade de operações). Como podemos perceber
também, nos benchmarks executados, a operação flush é também uma operação muito
chamada.
Tal como anteriormente referido, é importante perceber qual o desempenho do sistema
no que diz respeito à criação de ficheiros, visto esta ser uma operação muito comum nas
aplicações desktop dos dias de hoje [30]. Como podemos ver na tabela 5.1, a operação
mknod (operação que cria um novo ficheiro) é uma das operações mais chamadas pelos
nossos benchmarks.
5.3
Desempenho dos Serviços de Directorias e Locks
Na figura 5.1 são apresentadas as latências médias observadas para as várias operações do DepSpace utilizadas pelos serviços mencionados. Os dados apresentados foram
obtidos a partir da medição do tempo de execução de cada uma das operações aquando
da execução dos benchmarks ou, visto haver operações que são menos exercitadas que
outras, as operações rdAll e replace foram também exercitadas explicitamente. No total,
cada uma das operações foi executada aproximadamente 30000 vezes.
Como podemos ver na figura, a latência mais baixa é a das operações rdp sendo estas
da ordem dos 63 ms. As operações de inp e cas, utilizadas para remover e inserir tuplos
de metadados, apresentam latências na ordem dos 66ms. Por sua vez a operação rdAll
tem uma latência média de 75 ms enquanto que a operação replace demora em média 87
ms. Com isto podemos perceber que em média, as operações de leitura de metadados,
mesmo não usando cache são as mais rápidas, enquanto que as operações de actualização
de metadados, embora com uma diferença pouco assinalável, são as que mais tempo
demoram.
Note-se também que as operações cas e inp são utilizadas pelo serviço de locks
para inserir e remover tuplos de lock, respectivamente. Segundo estes experimentos, a
obtenção e destruição de um lock demora então, em média, 66 ms por operação.
A razão que leva a operação rdp a ser a que menos latência apresenta prende-se com
Capítulo 5. Avaliação Experimental
62
Figura 5.1: Latência das operações do DepSpace.
o facto de, na maioria das vezes, não ser necessário executar o protocolo de consenso
distribuído para a sua execução [23]. Como podemos ver na figura, as operações inp e
cas tem uma latência comparável à operação rdp. Isto acontece pois, visto as réplicas do
DepSpace estarem todas instaladas em máquinas virtuais de uma mesma zona de disponibilidade do Amazon EC2, a comunicação entre estas aquando do protocolo de consenso
é feita usando a rede interna do provedor do serviço, não resultando a execução do protocolo num aumento significativo da latência das referidas operações.
A latência média observada na operação rdAll justificam-se com o facto de, embora
(na maioria das vezes) não seja também necessária a execução do protocolo de consenso,
a quantidade de dados lidos nesta operação ser significativamente maior que na operação
rdp. Por outro lado, o valor médio da latência observado na operação replace justifica-se
com o facto de, para além ser sempre executado o protocolo de consenso para ordenar a
sua execução nas réplicas do DepSpace, esta operação pode activar o Trigger de substituição de tuplos (ver secção 4.2).
Latência das Operações rdp e getMetadata
Na figura 5.2 é apresentada a diferença existente entre a latência média das operações
rdp do DepSpace e getMetadata do serviço de directorias com cache. Aqui podemos
perceber a eficiência da operação getMetadata para diferentes valores de ∆ e, assim,
perceber de que forma é que este valor melhora o desempenho desta operação. Estes
valores, ao contrário dos apresentados na figura 5.1, foram obtidos tendo em conta apenas
valores de latência medidos na execução dos benchmarks anteriormente descritos sobre o
sistema. Assim, os valores apresentados são a média dos valores obtidos de dez execuções
de cada benchmarks, utilizando o serviço de directorias com cache com os valores 0, 100,
150 e 500 ms para o parâmetro ∆. O valor 0 foi escolhido para testar o comportamento
Capítulo 5. Avaliação Experimental
63
do serviço sem a utilização de cache. A escolha dos valores 100 e 150 pretende testar o
comportamento do serviço quando os metadados são mantidos em cache por um tempo
aproximado à latência das operações do DepSpace no pior caso. O valor 500 foi escolhido
com o objectivo de perceber até que ponto a subida de ∆ influencia o desempenho do
serviço.
Figura 5.2: Latência da obtenção de metadados.
Como podemos observar na figura 5.2, quando o valor de ∆ é 0, não existem ganhos
de latência da utilização do serviço, sendo a latência média das operações getMetadata
igual à das operações rdp no DepSpace. Por outro lado, sempre que é utilizada cache
no serviço de directorias, a latência na obtenção de metadados passa a cerca de metade
da latência das operações rdp. Observa-se também que, com o aumento do valor de ∆
(e assim o aumento do tempo em que os metadados permanecem válidos em cache),
existem pequenas melhorias no valor da latência média da operação getMetadata quando
comparado com o mesmo valor para a operação de leitura do DepSpace.
Através da análise da figura podemos também perceber que os ganhos de desempenho
da operação getMetadata não são proporcionais à subida do valor de ∆. Isto é facilmente
perceptível, por exemplo, verificando as latências médias desta operação com ∆ = 100 e
∆ = 500. Neste caso, sendo o valor de ∆ cinco vezes superior, enquanto que a latência
média para ∆ = 100 é aproximadamente 50% menor que latência média da operação rdp,
para ∆ = 500 existe um ganho de apenas 56.5%. Assim podemos concluir que, para obter
importantes ganhos de desempenho, o valor do parâmetro ∆ deve ser maior que zero, mas
não demasiado grande. Embora com a subida deste valor sejam observadas melhorias no
desempenho da operação getMetadata, este aumento leva também a uma diminuição da
coerência dos metadados mantidos no DepSpace. É então importante que este factor seja
tido em conta na escolha do valor deste parâmetro.
Capítulo 5. Avaliação Experimental
64
Latência das Operações do C2FS e Tempo de Execução dos Benchmarks
As figuras 5.3 e 5.4 apresentam, respectivamente, a latência média de várias operações
do sistema de ficheiros e o tempo de execução dos benchmarks para diferentes valores do
parâmetro ∆.
A figura 5.3 apresenta a latência média de algumas operações do sistema relacionadas
com os metadados. Os valores apresentados nesta figura foram obtidos através da execução sobre o C2FS do workload do Filebench que simula um servidor de ficheiros.
Cada valor resulta da média dos oito melhores valores obtidos de dez execuções. Note-se,
antes de mais, que cada uma destas operações (com a excepção da operação close) inclui
uma ou mais obtenções de metadados dos ficheiros operados, resultando a melhoria do
desempenho da operação getMetadata numa melhoria das mesmas. Note-se ainda que a
operação open, para além de obter os metadados do ficheiro a abrir, nos casos em que
este é aberto para escrita, implica também a aquisição de um lock sobre o seu contentor
de dados. É também necessário ter em conta que é na operação close que os dados são
escritos para as clouds, logo, é necessário actualizar os metadados (através da chamada à
operação updateLocalMetadata do serviço de directorias).
Figura 5.3: Latência das operações do sistema de ficheiros.
Como podemos ver, também para estes experimentos, o aumento do valor de ∆ representa sempre um aumento do desempenho. Em todas as operações, tal como anteriormente observado, a utilização de cache de metadados representa a diminuição da latência
das mesmas para cerca de metade. Uma excepção é a operação close. Este comportamento justifica-se com o facto de, neste operação, não haver necessidade de obter os
metadados do ficheiro que se pretende fechar. É também importante observar que, também neste experimento se verifica que a diminuição da latência não é proporcional ao
aumento do valor do parâmetro ∆.
Na figura 5.4 é apresentado o tempo de execução médio do PostMark e dos workloads
Capítulo 5. Avaliação Experimental
65
copy files e create files do Filebench para diferentes valores de ∆. Tal como no caso
da figura anterior, os resultado aqui apresentados resultam da média dos oito melhores
valores obtidos de dez execuções.
Figura 5.4: Tempo de execução de benchmarks.
Tal como anteriormente, também nesta figura podemos verificar que a utilização de
cache de metadados representa um aumento do desempenho do serviço de directorias, e
assim, o desempenho global do C2FS. Em todas as execuções, o desempenho aumenta
com o crescimento do valor do parâmetro ∆. Podemos ver que, com ∆ = 100, temos
tempos de execução aproximadamente 50% menores que para ∆ = 0 (48% para o PostMark, 43% e 52% para os workloads create files e copy files, respectivamente). Com
o aumento do valor de ∆ continuam a existir ganhos no desempenho do sistema, sendo
estes, no entanto, mais modestos. As melhorias com o aumento do tempo de validade dos
metadados em cache de 100 para 500, no caso dos tempos de execução do PostMark e do
workload copy files são de apenas 10.1% e 13.2%, respectivamente. No caso do workload
create files, para os mesmos valores de ∆, temos ganhos bastante nos tempos médios de
execução (na ordem dos 25%).
5.4
Desempenho do Serviço de Directorias sem Partilha
de Ficheiros
A utilização do C2FS sem partilha de ficheiros permite aos utilizadores tirar partido da
fiabilidade de armazenamento fornecida pelo DepSky [24] com uma interface de sistema
de ficheiros, não prejudicando o desempenho do sistema com a necessidade de utilizar o
DepSpace [23] para armazenar os metadados. Esta configuração assemelha-se ao modo
de funcionamento do BlueSky [52] ou do S3QL [19], tendo no entanto melhores garantias
de tolerância a faltas.
66
Capítulo 5. Avaliação Experimental
A figura 5.5 apresenta o tempo de execução dos benchmarks já apresentados nas figuras anteriores e a latências das operações stat, create, delete, open e close sobre o sistema
de ficheiros. Os valores apresentados resultam da média dos oito melhores resultados de
dez execuções.
(a) Tempo de execução de benchmarks sem partilha.
(b) Latência das operações do C2FS sem partilha.
Figura 5.5: Latências de operações sobre o C2FS e tempos de execução dos benchmarks
usando o serviço de directorias sem partilha.
Como podemos ver na figura 5.5(a), os tempos de execução dos benchmarks no C2FS
utilizando o serviço de directorias são em muito inferiores ao melhor tempo observado no
C2FS com partilha de ficheiros (figura 5.4). O tempo de execução do PostMark diminui
de 242 para 9 segundos, enquanto que nos workloads create files e copy files diminui de
299 para 20 segundos e de 446 para 29 segundos, respectivamente.
No que diz respeito à latência das operações do sistema de ficheiros, também são
observadas melhorias de desempenho muito assinaláveis, diminuindo a latência média
das operações stat, create, delete, open e close de 249, 629, 354, 286 e 100 ms/operação
(no melhor caso) para 9, 26, 37, 17 e 8 ms/operação.
5.5
Desempenho com a utilização do Espaço de Nomes
Pessoal
A utilização de um espaço de nomes pessoal, armazenado na cloud-of-clouds, onde
são mantidos os metadados de todos os ficheiros privados de cada cliente, para além de
permitir a diminuição da quantidade de informação armazenada no DepSpace, permite
também um aumento do desempenho do sistema.
A figura 5.6 apresenta a latência de algumas operações do sistema e o tempo de execução do PostMark e dos workloads de criação e cópia de um conjunto de ficheiros,
sendo efectuados experimentos com diferentes percentagens de ficheiros pessoais. Para
Capítulo 5. Avaliação Experimental
67
armazenar os ficheiros partilhados, em todos os experimentos foi utilizado o serviço de
directorias com cache (com ∆ = 150). Tal como nos experimentos anteriormente apresentados, os resultados presentes nesta figura resultam da média aritmética dos oito
melhores resultados obtidos de dez execuções.
(a) Tempo de execução de benchmarks com ficheiros pessoais. (b) Latência das operações do C2FS com ficheiros pessoais.
Figura 5.6: Latências de operações sobre o C2FS e tempos de execução dos benchmarks
com ficheiros pessoais.
Em ambos os gráficos da figura podemos perceber que basta que uma pequena parte
dos ficheiros sejam pessoais para que o desempenho do sistema aumente significativamente. Podemos perceber também que, embora com o crescimento da percentagem de
ficheiros pessoais o desempenho do sistema também aumente, este crescimento não é
proporcional.
À primeira vista, se imaginarmos uma utilização em que todos os ficheiros do sistema
são pessoais, poderíamos pensar que o desempenho deste seria equivalente à utilização do
sistema sem partilha de ficheiros, o que não acontece na realidade. Isto deve-se ao facto
de, por exemplo, na criação de ficheiros, mesmo sendo estes privados, ser necessário, em
primeiro lugar, efectuar uma operação getMetadata no serviço de directorias para garantir
que não existe nenhum ficheiro no sistema com o nome do novo ficheiro. Esta diferença
pode ser observada comparando os resultados de latência e tempo de execução com 100%
de ficheiros pessoais presentes nas figuras 5.6(a) e 5.6(b) com os resultados apresentados
nas figuras 5.5(a) e 5.5(b). Podemos então observar que, no caso do tempo de execução
dos benchmarks, o C2FS sem partilha de ficheiros apresenta valores cerca de seis vezes
inferiores no caso das execuçoes do workload create files e do PostMark, e cerca de três
vezes inferiores no caso do workload copy files. No caso das operações do C2FS, podemos perceber que, com a excepção da operação open (que tem um desempenho claramente superior no C2FS sem partilha de ficheiros), todas as restantes operações, têm um
desempenho similar.
Capítulo 5. Avaliação Experimental
5.6
68
Considerações Finais
Neste capítulo foi apresentada a avaliação experimental feita às versões com e sem
partilha de ficheiros do serviço de directorias e à utilização do espaço de nomes pessoal.
Aqui, foram estudadas as latências médias das várias operações do DepSpace utilizadas
pelos serviços de directorias e de locks, o desempenho de algumas operações do sistema
de ficheiros que operam sobre os metadados e ainda o tempo de execução de alguns
benchmarks, para diferentes configurações do sistema.
Neste capítulo demonstrou-se que a utilização de uma cache de metadados temporária
permite obter ganhos bastante assinaláveis de desempenho, não sendo o aumento do desempenho proporcional ao aumento do tempo de validade dos metadados em cache.
Verificou-se também que, para além de diminuir a quantidade de informação armazenada no DepSpace, a utilização do espaço de nomes pessoal permite ainda grandes
ganhos de desempenho.
Capítulo 6
Conclusão
O C2FS é um sistema de ficheiros multi-utilizador com uma interface estilo-POSIX,
que permite o armazenamento de dados em várias clouds, e ainda tolera falhas por parte
dos clientes e provedores de armazenamento nas clouds.
Neste trabalho, para além da arquitectura geral do C2FS, foram apresentadas em detalhe as várias versões do serviço de directorias, utilizadas para gerir os metadados e
efectuar controlo de acesso aos ficheiros. A primeira versão apresentada permite a partilha de ficheiros entre vários utilizadores, não fazendo, no entanto, uso de cache para
aumentar o desempenho do serviço. Em seguida foi apresentado o serviço de directorias
que, para além de permitir a partilha de ficheiros, faz uso da cache para aumentar o desempenho do serviço (em especial das leituras de metadados). Foi também descrito o serviço
de directorias sem partilha de ficheiros, uma versão que permite tirar partido das vantagens inerentes ao armazenamento dos dados na cloud-of-clouds sem que o desempenho
do serviço de directorias seja prejudicado com a latência da rede. Para aumentar o desempenho das versões do serviço de directorias com partilha de ficheiros, foi apresentado
o conceito de espaço de nomes pessoal, um mecanismo que permite, ao mesmo tempo,
aumentar o desempenho do manuseamento de metadados de ficheiros não partilhados e
reduzir a quantidade de informação armazenada pelo serviço.
Todas as versões do serviço de directorias descritas acima fornecem garantias de integridade e confidencialidade para os metadados. As versões deste serviço que permitem
a partilha de ficheiros, para além das garantias já referidas, garantem ainda a disponibilidade dos metadados armazenados, através da utilização de um serviço de coordenação
tolerante a faltas bizantinas [23].
Foi ainda apresentado um serviço de trincos, utilizado para coordenar o acesso concorrente aos contentores de dados dos ficheiros por parte de diferentes processos escritores.
Por fim, foi apresentado um mecanismo que, através da interacção entre os serviços de
directorias e armazenamento [40] do C2FS, permite ao sistema garantir consistência forte
dos dados armazenados na cloud-of-clouds.
Os resultados reportados numa avaliação experimental aos serviços de directorias e
69
Capítulo 6. Conclusão
70
trincos do C2FS mostram que os referidos serviços têm um desempenho aceitável para
certos workloads comuns como servidores de ficheiros ou servidores de e-mail.
6.1
Trabalho futuro
Actualmente, todos os utilizadores do C2FS têm de partilhar as contas de utilizador
dos provedores de armazenamento utilizados para armazenar os dados dos ficheiros do
sistema. Neste cenário, cada utilizador do sistema está apto a obter qualquer contentor
de dados a partir do DepSky, sendo da responsabilidade do serviço de directorias manter
privada aos utilizadores não autorizados a chave necessária para decifrar os dados. Esta
abordagem é apenas útil, e.g., num modelo empresarial no qual a organização fica encarregue dos encargos relacionados com o armazenamento dos dados partilhados entre os
seus colaboradores. No entanto, esta abordagem deixa de fazer sentido quando o sistema
é utilizado por vários utilizadores comuns pois, neste caso, os custos inerentes à utilização dos vários provedores de armazenamento nas clouds por parte dos vários utilizadores
ficariam ao encargo de apenas uma pessoa. Para resolver este problema, uma das tarefas
futuras é desenvolver uma nova versão do serviço de directorias que permita a partilha de
ficheiros armazenados em diferentes contas de utilizador nas clouds de armazenamento,
desenvolvendo também um novo mecanismo de controlo de acesso aos ficheiros para esta
versão.
Há ainda a necessidade de avaliar o desempenho do sistema na presença de faltas
ou ainda o desempenho do mecanismo que permite ao C2FS fornecer uma semântica de
consistência forte, aquando da presença de dados inconsistentes nas clouds.
Apêndice A
Prova Informal do Serviço de Trincos
O serviço de trinco apresentado deve garantir certas propriedades de correcção. Desta
forma, as seguintes garantias devem ser fornecidas:
Safety 1 (S1) Existe no máximo um processo com um trinco sobre um contentor de dados.
Safety 2 (S2) A menos que o detentor de um trinco o queira, nenhum trinco fica inválido
antes do seu tempo de validade expirar.
Liveness 1 (L1) Quando nenhum processo detém o trinco sobre um contentor, se um
processo tentar adquirir esse trinco, este consegue.
Liveness 2 (L2) Quando um processo detentor de um trinco falha, eventualmente, o contentor reservado por esse trinco é libertado.
A propriedade S1 tem por objectivo garantir que o serviço faz uma correcta gestão
das reservas de contentores de dados. Por outro lado, sem a propriedade L1, uma forma
de garantir que nunca existem dois processos com o trinco sobre o mesmo contentor
seria, por exemplo, não permitir que nenhum processo obtivesse trincos sobre quaisquer
contentores, deixando o serviço de ter qualquer utilidade. Estas duas propriedades são as
propriedades fundamentais de um serviço de trincos.
A segunda propriedade de safety permite garantir que, após a obtenção de um trinco
por parte de um cliente e antes do seu tempo de validade expirar, o cliente mantém acesso
exclusivo de escrita a um contentor. Por outro lado, a segunda propriedade de liveness tem
por objectivo garantir que, na presença de faltas por parte dos clientes, nunca existirão
contentores reservados eternamente, impossíveis de usar por clientes correctos.
Assumindo um conjunto de processos que falham apenas por paragem (ver secção 3.1.2),
pretende-se então provar de forma informal que o serviço de trinco do C2FS cumpre estas
propriedades de correcção:
71
Apêndice A. Prova Informal do Serviço de Trincos
72
S1. Como já referido anteriormente, a operação do serviço de trinco que permite aos
clientes adquirir um trinco sobre um dado contentor de dados é a operação tryAquire,
representando o sucesso desta operação a obtenção de um trinco por parte do cliente
invocador da operação. Esta operação tenta inserir um tuplo no espaço de tuplos através da
chamada cas do DepSpace. Como podemos ver no algoritmo 5, o template fornecido nesta
chamada é igual ao tuplo a inserir, contendo ambos um identificador estático referente ao
tipo de tuplo (LOCK) e o identificador do contentor a reservar. Tendo em conta que a
operação de aquisição de um trinco só tem sucesso se o serviço conseguir inserir o tuplo
de trinco no espaço, aliado com o facto de a semântica da operação cas do DepSpace só
inserir o tuplo caso não haja nenhum tuplo no espaço que faça correspondência com o
template dado, podemos comprovar que a operação só tem sucesso se não existir nenhum
outro tuplo no espaço com os mesmos campos, ou seja, com o mesmo identificador do
contentor de dados. Assim, prova-se que, caso um cliente queira adquirir um trinco sobre
um contentor de dados já reservado por um outro cliente (que conseguiu inserir o tuplo
de trinco referente a esse contentor), a operação não irá ter sucesso, pois o seu tuplo não
conseguirá ser inserido, garantindo que nunca existirão dois processos com um trinco
sobre o mesmo contentor.
S2. O tuplo de trinco que é inserido no DepSpace, e que é utilizado para reservar um
contentor de dados, é um tuplo temporário. Aquando da chamada da operação tryAquire
por parte de um cliente, é fornecido o parâmetro time, que específica a quantidade de
tempo que o tuplo de trinco deve permanecer no espaço. Este tuplo é também configurado
com permissões de escrita apenas para o seu dono, ou seja, para o serviço de trinco que o
insere. Tendo em conta que o DepSpace garante que este tuplo não desaparece do espaço
de tuplos antes do seu tempo de validade (time) expirar, aliado com o facto de nenhum
cliente malicioso estar apto a remover o mesmo tuplo, podemos garantir que, enquanto o
tuplo for válido, ele é mantido no espaço. Assim, estando um determinado trinco válido
apenas se o seu tuplo de trinco se encontra no espaço de tuplos, podemos provar que
um trinco nunca fica inválido antes do seu tempo de validade expirar, a menos que o ser
detentor o queira.
L1. Como explicado na prova anterior, os tuplos de trinco inseridos no DepSpace são
tuplos temporários. Assim, em caso de falha no cliente que detém o trinco (não permitindo
que este possa renovar o tempo de validade deste tuplo), o tuplo irá desaparecer do espaço
de tuplos após time ms. Desta forma, prova-se que, caso o cliente detentor de um trinco
falhe, o contentor de dados associado a este trinco acaba por ser libertado pois o tuplo de
trinco utilizado para reservar esse contentor desaparece do espaço após um determinado
tempo, deixando o contentor livre para ser acedido por outro cliente.
Apêndice A. Prova Informal do Serviço de Trincos
73
L2. Como anteriormente explicado, para um cliente obter um trinco sobre um determinado contentor de dados basta ter sucesso na execução da operação tryAquire do serviço
de trinco, dando como argumento o identificador desse contentor. Assim, visto que o
sucesso desta operação depende da inserção do tuplo de trinco no espaço, caso não exista
um tuplo de trinco para o referido contentor (o que significa que este pode ser acedido),
a inserção deste tuplo tem sucesso. Prova-se portanto que, se for feita uma operação de
aquisição de trinco sobre um dado contentor não reservado por parte de um cliente, este
tem sucesso na operação cas e, consequentemente, na obtenção do trinco.
Bibliografia
[1] Amazon Elastic Block Store. http://aws.amazon.com/ebs/.
[2] Amazon Elastic Compute Cloud. http://aws.amazon.com/pt/ec2/.
[3] Amazon ElastiCache. http://aws.amazon.com/elasticache/.
[4] Amazon Simple Storage Service. http://aws.amazon.com/s3/.
[5] Apple iCloud. http://www.apple.com/icloud/.
[6] DropBox. https://dropbox.com.
[7] Filebench. http://sourceforge.net/apps/mediawiki/filebench.
[8] FUSE. http://fuse.sourceforge.net/.
[9] FUSE-J. http://fuse-j.sourceforge.net/.
[10] Google App Engine. https://appengine.google.com.
[11] Google Cloud Storage. https://developers.google.com/storage/.
[12] GoogleDrive. https://drive.google.com/.
[13] Microsoft Windows Azure. http://www.windowsazure.com/.
[14] OpenStack Storage. http://www.openstack.org/software/openstack-storage/.
[15] PlanetLab Europe web site. http://www.planet-lab.eu/.
[16] POSIX. http://en.wikipedia.org/wiki/POSIX.
[17] Project TCLOUDS - trustworthy clouds - privacy and resilience for internet-scale
critical infrastructure. http://www.tclouds-project.eu/.
[18] S3FS. http://code.google.com/p/s3fs/.
[19] S3QL. http://code.google.com/p/s3ql/.
[20] Tuple space. http://en.wikipedia.org/wiki/Tuple_space.
75
Bibliografia
76
[21] Hussam Abu-Libdeh, Lonnie Princehouse, and Hakim Weatherspoon. RACS: Redundant Array of Cloud Storage. In ACM Symposium on Cloud Computing (SOCC),
June 2010.
[22] A. Adya, W. J. Bolosky, M. Castro, R. Chaiken, G. Cermak, J. R. Douceur, J. Howell, J. R. Lorch, M. Theimer, and R. P. Warrenhofer. Farsite: Federated, available,
and reliable storage for an incompletely trusted environment. In 5th OSDI. Dec
2002.
[23] Alysson N. Bessani, Eduardo P. Alchieri, Miguel Correia, and Joni S. Fraga.
DepSpace: a Byzantine fault-tolerant coordination service. In Proc. of the 3rd ACM
European Systems Conference – EuroSys’08, pages 163–176, April 2008.
[24] Alysson N. Bessani, Miguel Correia, Bruno Quaresma, Fernando Andre, and Paulo
Sousa. DepSky: Dependable and Secure Storage in cloud-of-clouds. In Proc. of the
3rd ACM European Systems Conference – EuroSys’11, April 2011.
[25] Alysson Neves Bessani, Miguel Correia, Joni da Silva Fraga, and Lau Cheuk Lung.
Sharing Memory between Byzantine Processes using Policy-Enforced Tuple Spaces.
In IEEE Transactions on Parallel and Distributed Systems. Vol. 20 no. 3. pages 41943, IEEE Computer Society, March 2009.
[26] Mike Burrows. The Chubby Lock Service. In Proceedings of 7th Symposium on
Operating Systems Design and Implementation – OSDI 2006, November 2006.
[27] John R. Douceur, Atul Adya, Josh Benaloh, William J. Bolosky, and Gideon Yuval.
A Secure Directory Service based on Exclusive Encryption. In Proceedings of the
18th Annual Computer Security Applications Conference (ACSAC), December 2002.
[28] Jonh R. Douceur and Jon Howell. Distributed directory service in farsite file system.
In Proceedings of the 7th USENIX Symposium on Operating Systems Design and
Implementation. OSDI’06, pages 321-333, 2006. USENIX Association.
[29] S. Ghemawat, H. Gobioff, and S. Leung. The Google file system. In 19th SOSP.
pages 29-43, December, 2003.
[30] Tyler Harter, Chris Dragga, Michael Vaughn, Andrea C. Arpaci-Dusseau, and
Remzi H. Arpaci-Dusseau. A File is Not a File: Understanding the I/O Behavior of apple desktop applications. In Proceedings of the 23rd ACM Symposium on
Operating Systems Principles – SOSP’11, October 2011.
[31] J. H. Howard, M. L. Kazar, Menees S. G., D. N. Nichols, M. Satyanarayanan, R. N.
Sidebotham, and M. J. West. Scale and performance in a distributed file system. In
ACM Trans. Comput. Syst. vol. 6, no. I, February 1988.
Bibliografia
77
[32] Patrick Hunt, Mahadev Konar, Flavio Junqueira, and Benjamin Reed. Zookeeper:
Wait-free Coordination for Internet-scale Services. In Proc. of the USENIX Annual
Technical Conference – ATC 2010, pages 145–158, June 2010.
[33] Jeffrey Katcher. PostMark: A New File System Benchmark. Technical report,
August 1997.
[34] Leslie Lamport. On interprocess communication (part II). Distributed Computing,
1(1):203–213, January 1986.
[35] Leslie Lamport. The part-time parliament. ACM Transactions Computer Systems,
16(2):133–169, May 1998.
[36] Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Transactions on Programing Languages and Systems, 4(3):382–401, July
1982.
[37] Edward L. Lee and Chandramohan A. Thekkath. Petal: Distributed Virtual Disks. In
In the Proceedings of the 7th Intl. Conf. on Architectural Support for Programming
Langauges and Operating Systems. pages 84-92, October 1996.
[38] Ricardo Mendes, Tiago Oliveira, Alysson Bessani, and Marcelo Pasin. C2FS: um
Sistema de Ficheiros Seguro e Fiável para Cloud-of-clouds. In INForum12, September 2012.
[39] Hugo Miranda, Alexandre Pinto, and Luís Rodrigues. Appia communication framework. http://appia.di.fc.ul.pt/.
[40] T. Oliveira. Substrato de Armazenamento para Sistemas de Ficheiros para cloudof-clouds. Relatório do Projecto de Engenharia Informática. DI/FCUL, September
2012.
[41] R. Posse. Serviço de Coordenação para Bases de Dados Replicadas. Relatório do
Projecto de Engenharia Informática. DI/FCUL, Setembro 2011.
[42] Krishna P. N. Puttaswamy, Thyaga Nandagopal, and Murali Kodialam. Frugal Storage for Cloud File Systems. In Proc. of the 3rd ACM European Systems Conference
– EuroSys’12, April 2012.
[43] B. Reed and F. P. Junqueira. A simple totally ordered broadcast protocol. In LADIS
’08: Proceedings of the 2nd Workshop on Large-Scale Distributed Systems and Middleware. pages 1–6, New York, NY, USA, 2008. ACM.
Bibliografia
78
[44] M. Satyanarayanan, J. H. Howard, D. N. Nichols, R. N. Sidebotham, A. Z. Spector,
and M. J. West. The ITC distributed file system: principles and design. In Proceedings of the 10th ACM Symposium Oper. Syst. Principles. Orcas Island, December
1985.
[45] M. Satyanarayanan, P. Kumar, M. Okasaki, E. Siegel, and D. Steere. Coda: A highly
available file system for a distributed workstation environment. In IEEE Trans. on
Comp. 4. 39 (Apr 1990), 447-459.
[46] B. Schoenmakers. A simple publicly verifiable secret sharing scheme and its application to electronic voting. In Proceedings of the 19th International Cryptology
Conference on Advances in Cryptology - CRYPTO’99. Aug. 1999.
[47] J. Sousa and A. Bessani. From byzantine consensus to bft state machine replication:
A latency-optimal transformation. In In the Proc. of the 9th European Dependable
Computing Conference, 2012.
[48] Jeremy Stribling, Yair Sovran, Irene Zhang, Xavid Pretzer, Jinyang Li, M.Frans
Kaashoek, and Robert Morris. Flexible, Wide-Area Storage for Distributed System
with WheelFS. In In the Proceedings of the 6th USENIX Symposium on Networked
Systems Design and Implementation (NSDI ’09). Boston, MA, April 2009.
[49] Vasily Tarasov, Saumitra Bhanage, Erez Zadok, and Margo Seltzer. Benchmarking
File System Benchmarking: It *IS* Rocket Science. In 13th USENIX Workshop in
Hot Topics in Operating Systems (HotOS XIII). May 2011.
[50] C. Thekkath and E. L. T. Mann. Frangipani: A scalable distributed file system. In
In the Proceedings of the 16th SOSP.
[51] W. Vogels. Eventually Consistent. In Communications of the ACM, October 2008.
[52] Michael Vrable, Stefan Savage, and Geoffrey M. Voelker. BlueSky: A cloud-backed
file system for the enterprise. In Proc. of the 10th USENIX Conference on File and
Storage Technologies – FAST’12, 2012.
[53] S. A. Weil, S. A. Brandt, E. L. Miller, and C. Maltzahn. CRUSH: Controlled,
scalable, decentralized placement of replicated data. In Proceedings of the 2006
ACM/IEEE Conference on Superomputing (SC ’04). Tampa, FL, Nov, 2006, ACM.
[54] Sage A. Weil, Scott A. Brandt, Ethan L. Miller, Darrell D. E. Long, and Carlos
Maltzahn. Ceph: A Scalable, High-Performance Distributed File System. In Proc.
of the 7th USENIX Symposium on Operating Systems Design and Implementation –
OSDI 2006, pages 307–320, 2006.