U NIVERSIDADE DE L ISBOA
Faculdade de Ciências
Departamento de Informática
DEPSKY: SISTEMA DE ARMAZENAMENTO EM
CLOUDS TOLERANTE A INTRUSÕES
Bruno Miguel Maia Rovisco Quaresma
MESTRADO EM ENGENHARIA INFORMÁTICA
Especialização em Arquitectura, Sistemas e Redes de Computadores
2010
U NIVERSIDADE DE L ISBOA
Faculdade de Ciências
Departamento de Informática
DEPSKY: SISTEMA DE ARMAZENAMENTO EM
CLOUDS TOLERANTE A INTRUSÕES
Bruno Miguel Maia Rovisco Quaresma
DISSERTAÇÃO
Projecto orientado pelo Prof. Doutor Alysson Neves Bessani
e co-orientado pelo Prof. Doutor Paulo Jorge Paiva de Sousa
MESTRADO EM ENGENHARIA INFORMÁTICA
Especialização em Arquitectura, Sistemas e Redes de Computadores
2010
Agradecimentos
Em primeiro lugar, quero agradecer aos meus orientadores do PEI, os Professores
Doutores Alysson Bessani e Paulo Sousa, pela orientação dada neste último ano do MEI.
Também quero agradecer aos meus colegas, tanto de investigação como de curso,
pelos bons momentos passados e troca de impressões sobre temas de interesse.
Agradeço à minha família, especialmente aos meus pais e irmã por me aturarem e
facilitarem a conclusão dos meus estudos.
Finalmente agradeço, a todos os meus amigos e amigas, a força e motivação para
atingir os meus objectivos.
iii
Resumo
A manutenção da disponibilidade e da integridade da informação é um requisito fundamental em sistemas de armazenamento. Estes sistemas lidam com a perda de dados
através de replicação, na qual os dados são armazenados em múltiplas unidades básicas
de armazenamento. A ideia base do trabalho aqui apresentado surgiu da constatação que
as clouds de armazenamento podem ser vistas como unidades desse tipo.
Com a crescente popularidade das clouds de armazenamento, empresas que lidam
com dados críticos começam a pensar em usar estes serviços para armazenar bases de
dados de registos médicos, históricos de infra-estruturas críticas, dados financeiros, entre
outros. No entanto, muitas pessoas acreditam que informação armazenada num sistema
deste tipo é vulnerável, apesar de todas as garantias dadas pelos fornecedores, o que faz
da fiabilidade e da segurança as maiores preocupações sobre o armazenamento em clouds.
Este trabalho apresenta o D EP S KY, um sistema que melhora a disponibilidade, integridade e confidencialidade de informação armazenada em clouds. Para garantir estas propriedades, o sistema D EP S KY disponibiliza dois protocolos, o ADS (Available
D EP S KY), focado em melhorar a disponibilidade e integridade da informação, e o CADS
(Confidential & Available D EP S KY), que adicionalmente melhora a confidencialidade da
informação. Ambos os protocolos fornecem algoritmos para leitura e escrita, à semelhança do que acontece com todos os sistemas de armazenamento.
Palavras-chave: Clouds de armazenamento, replicação, disponibilidade,
confidencialidade, integridade
v
Abstract
Maintaining availability and integrity of information is a fundamental requirement in
storage systems. These systems deal with the loss of data through replication, where data
is stored in multiple basic units of storage. The initial idea of the work presented here
resulted from the realization that storage clouds can be viewed as such units.
With the increasing popularity of cloud storaging services, companies that deal with
critical data start thinking of using these services to store medical records databases, historical data of critical infrastructures, financial data, among others. However, many people believe that information stored that way is vulnerable, despite the guarantees given by
providers, which makes reliability and security the major concerns about cloud storaging.
This work presents D EP S KY, a system that improves the availability, integrity and
confidentiality of information stored in the cloud. To ensure these properties D EP S KY
provides two protocols, ADS (Available D EP S KY), focused on improving the availability
and integrity of information, and CADS (Confidential & Available D EP S KY), which additionally enhances the confidentiality of information. Both provide algorithms for reading
and writing data, as is any storage systems.
Keywords: Storage clouds, replication, availability, confidentiality, integrity
vii
Conteúdo
Lista de Figuras
xiii
Lista de Tabelas
xv
1
2
3
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
.
.
.
.
.
.
.
.
.
.
.
.
Trabalho Relacionado
2.1 Tolerância a Intrusões . . . .
2.1.1 Introdução ao Tema .
2.1.2 Replicação . . . . .
2.1.3 Confidencialidade .
2.2 Clouds de Armazenamento .
2.2.1 Considerações Gerais
2.2.2 Detalhes Adicionais
2.3 Considerações Finais . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
D EP S KY
3.1 Apresentação . . . . . . . . . . . . . . . .
3.2 Modelo de Sistema . . . . . . . . . . . . .
3.3 Modelo de Dados . . . . . . . . . . . . . .
3.4 ADS - Available D EP S KY . . . . . . . . .
3.4.1 Algoritmo de Escrita . . . . . . . .
3.4.2 Algoritmo de Leitura . . . . . . . .
3.5 CADS - Confidential & Available D EP S KY
3.6 Trabalhos Similares . . . . . . . . . . . . .
3.7 Considerações Finais . . . . . . . . . . . .
ix
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
1
3
3
4
4
5
.
.
.
.
.
.
.
.
7
7
7
8
11
13
13
15
17
.
.
.
.
.
.
.
.
.
19
19
20
21
22
22
23
23
27
28
4
5
6
Concretização do D EP S KY
4.1 Considerações Gerais .
4.2 Arquitectura . . . . . .
4.3 Diagramas UML . . .
4.4 Controladores . . . . .
4.5 Considerações Finais .
.
.
.
.
.
29
29
31
32
36
37
.
.
.
.
.
.
39
39
41
41
42
44
45
Conclusões e Trabalho Futuro
6.1 Conclusões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Trabalho Futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
47
48
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Avaliação Experimental do D EP S KY
5.1 Custo do Armazenamento Replicado
5.2 Desempenho e Disponibilidade . . .
5.2.1 Metodologia . . . . . . . .
5.2.2 Latência de Leitura . . . . .
5.2.3 Latência de Escrita . . . . .
5.3 Considerações Finais . . . . . . . .
Referências
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
51
x
xii
Lista de Figuras
3.1
3.2
Visão sobre a distribuição de informação pelas clouds. . . . . . . . . . . . . .
4.1
4.2
4.3
4.4
Visão minimalista sobre a estrutura do DepSky. . . . . . . . . . . . . . . . .
5.1
FDC para as latências de leitura de dados com 100K bytes observadas em quatro
Decomposição do Data Unit X do D EP S KY, do conceito à concretização. . . . .
Diagrama de classes do sistema. . . . . . . . . . . . . . . . . . . . . . . . .
Diagrama de sequência simplificado de uma operação de escrita. . . . . . . . .
Diagrama de sequência simplificado de uma operação de leitura. . . . . . . . .
20
22
31
33
34
36
diferentes clouds (Amazon S3, Windows Azure, Nirvanix e DivShare) e nas três
versões do D EP S KY replicando dados por essas clouds.
5.2
. . . . . . . . . . . .
42
FDC para as latências de leitura de dados com 1M bytes observadas em quatro
diferentes clouds (Amazon S3, Windows Azure, Nirvanix e DivShare) e nas três
versões do D EP S KY replicando dados por essas clouds.
5.3
. . . . . . . . . . . .
43
FDC para as latências de leitura de dados com 10M bytes observadas em quatro
diferentes clouds (Amazon S3, Windows Azure, Nirvanix e DivShare) e nas três
versões do D EP S KY replicando dados por essas clouds.
xiii
. . . . . . . . . . . .
43
Lista de Tabelas
1.1
Planeamento inicial do PEI. . . . . . . . . . . . . . . . . . . . . . . . . .
2.1
2.3
Custo, em USD, do armazenamento, entrada e saída de 1 Gb de dados em
serviços de armazenamento pay-per-use estudados. . . . . . . . . . . . .
Custo, em USD, de efectuar 10000 pedidos a serviços de armazenamento
pay-per-use estudados. . . . . . . . . . . . . . . . . . . . . . . . . . . .
Alguns limites conhecidos de serviços livres de encargos estudados. . . .
4.1
Número de linhas de código necessárias para cada componente do sistema. 30
5.1
Custo estimado, em USD, de 10.000 operações de leitura e escrita de
dados com 100KB, 1MB e 10MB nas clouds. . . . . . . . . . . . . . . . 40
Custo estimado, em USD, de 10.000 operações de leitura e escrita de
dados com 100KB, 1MB e 10MB usando os protocolos do D EP S KY. . . . 40
Número de falhas observadas durante as experiências de leitura. O “10+10hs”
para a Azure na experiência de 10M significa que para além das 10 falhas
reportadas houve um período de 10 horas onde mais de 95% dos acessos
individuais a este sistema falharam. . . . . . . . . . . . . . . . . . . . . 44
Latência média (ms) de escrita para diferentes tamanhos de unidades de
dados, configurações do D EP S KY e clouds de armazenamento. . . . . . . 44
2.2
5.2
5.3
5.4
xv
5
16
17
17
Capítulo 1
Introdução
Este relatório descreve o trabalho realizado no âmbito da disciplina de Projecto de
Engenharia Informática (PEI) do Mestrado em Engenharia Informática da Faculdade de
Ciências da Universidade de Lisboa.
Este projecto foi desenvolvido na unidade de investigação LaSIGE (Laboratório de
Sistemas Informáticos de Grande Escala) sito no Departamento de Informática da Faculdade de Ciências da Universidade de Lisboa. Fui inserido no grupo de investigação Navigators no qual o meu orientador, Prof. Doutor Alysson Neves Bessani, e co-orientador,
Prof. Doutor Paulo Jorge Paiva de Sousa, estão também inseridos.
Por este motivo de proximidade, ao longo do projecto foi possível a existência de uma
boa comunicação de forma a que certas ideias ou dúvidas, que tenham surgido, fossem
rapidamente discutidas.
Neste capítulo introdutório são apresentadas a motivação, os objectivos, as contribuições e o planeamento do trabalho descrito neste relatório. A secção final deste capítulo
descreve de forma resumida a oraganização dos restantes capítulos.
1.1
Motivação
A manutenção da disponibilidade e da integridade da informação é um requisito fundamental em sistemas de armazenamento. Os sistemas de armazenamento distribuído
estão a tornar-se cada vez mais populares com o advento das tecnologias SAN (Storage
Area Network) e NAS (Network Attached Storage), assim como a crescente disponibilidade de discos de baixo custo. Estes sistemas lidam com a perda de dados através da
replicação, na qual os dados são armazenados em múltiplas unidades básicas de armazenamento (discos ou servidores), doravante denominados objectos base.
Um desafio importante deste tipo de sistemas é fornecer uma elevada disponibilidade,
tal como já tinha sido referido. Isto significa que o sistema deve permanecer disponível
ainda que um objecto base falhe; por vezes mais falhas são toleradas dependendo da resiliência do sistema. A resiliência de um sistema de armazenamento distribuído está definida
1
Capítulo 1. Introdução
2
como o número f de um total de n objectos base que podem falhar sem este sistema deixar
de oferecer disponibilidade e consistência. O nível de resiliência dita a disponibilidade
do serviço pois ao replicar-se a informação em vários objectos base (discos, servidores),
a disponibilidade da informação aumenta.
Um sistema de armazenamento distribuído emula um objecto partilhado robusto através da manutenção de cópias deste em locais diferentes, para que a informação sobreviva.
Isto pode ser conseguido sem muito esforço financeiro usando vários discos de baixo
custo ou PC’s de capacidade moderada, em vez de servidores poderosos, para armazenar
a informação. É típico focar na abstracção de objecto de armazenamento, que apenas
suporta as operações básicas de leitura e escrita pelos clientes. O estudo destes objectos é
fundamental, pois estes são os alicerces para a construção de sistemas de armazenamento
mais complexos.
Os algoritmos de armazenamento distribuído enfrentam o desafio de superar a assincronia e uma variedade de faltas, sem se desviar significativamente das garantias de
consistência e desempenho do armazenamento tradicional (centralizado). Tais algoritmos
variam em função de várias dimensões: na semântica de consistência que fornecem; na
sua resiliência (número e tipos de faltas toleradas); na sua arquitectura (se os objectos
base são simples discos ou servidores mais complexos); e na sua complexidade (e.g., latência). Claramente, existem muitos tradeoffs: por exemplo, oferecer maior consistência
ou resiliência adicional tem impacto na complexidade.
Nos últimos tempos tem-se observado uma crescente oferta de serviços na Internet que
disponibilizam espaço nos seus servidores para um cliente armazenar e partilhar informação, normalmente ficheiros. No contexto deste trabalho tais serviços podem ser vistos
como objectos base para a construção de um sistema de armazenamento. Contudo, terão
de ser asseguradas características fundamentais como integridade, disponiblidade e confidencialidade, que são características básicas da segurança da informação, não estando
esta segurança restrita somente a sistemas computacionais, informação digital ou sistemas
de armazenamento. A segurança da informação está relacionada com a protecção de um
conjunto de dados, no sentido de preservar o valor que possuem para uma entidade, indivíduo ou organização. O conceito de segurança informática está directamente relacionado
com o de segurança da informação, incluindo não apenas este mas também a segurança
dos próprios sistemas.
Actualmente, muitas organizações começam a optar de forma progressiva pelo uso de
clouds de armazenamento. Exemplos recentes são serviços como o Twitter e o Facebook
que até há bem pouco tempo tinham os seus próprios data centers de armazenamento e
hoje tercerizam parte deste serviço para a Amazon e o seu Simple Storage Service (Amazon S3) [1]. Esta tendência pode ser definida como o armazenamento de informação num
sistema de armazenamento remoto mantido por terceiros. A Internet fornece a ligação
entre o computador e esse sistema.
Capítulo 1. Introdução
3
O armazenamento em clouds tem algumas vantagens sobre o armazenamento tradicional. Por exemplo, se se armazenar informação numa cloud, esta estará acessível a partir
de qualquer local com acesso à Internet e evita a necessidade da manutenção de uma
infra-estrutura de armazenamento na organização.
À medida que as clouds de armazenamento se tornam mais populares, empresas que
lidam com dados critícos começam a pensar em usar estes serviços para armazenar bases
de dados de registos médicos, históricos de infra-estruturas críticas, dados financeiros,
entre outros. No entanto, um perigo muitas vezes ignorado está no facto dos sistemas
de armazenamento remoto estarem fora do controlo dos donos dos dados, apesar das
garantias dadas pelos fornecedores (e.g., SLA - Service Level Agreement), o que faz da
fiabilidade e da segurança as maiores preocupações sobre o armazenamento em clouds.
1.2
Objectivos
O principal objectivo deste trabalho era a concretização de um sistema de armazenamento em clouds tolerante a intrusões, o D EP S KY, assegurando a integridade, disponibilidade e confidencialidade da informação. Outro dos objectivos deste trabalho era realizar
diversos tipos de testes ao sistema, analisando o seu desempenho.
1.3
Contribuições
No inicio desta dissertação, foi necessário realizar um estudo acerca do tema tolerância a intrusões, de forma a aprofundar conhecimentos nesta área de investigação, incidindo na replicação e confidencialidade de informação. Durante este estudo inicial foi
dada uma pequena contribuição a um projecto paralelo, que consistiu na actualização de
uma biblioteca baseada em sistemas de quóruns activos 2.1.2.
Também foi necessária investigação sobre clouds de armazenamento (2.2), incluindo
o estudo de API’s de variados serviços do género.
Após este processo foi iniciado o desenho e concretização do D EP S KY. Estas tarefas
foram realizadas de forma incremental tendo sido efectuadas várias revisões de modo a
melhorar o sistema. À medida que se efectuava uma nova versão, eram realizados testes
ao desempenho de modo a se perceber o que poderia ser melhorado.
A principal contribuição desta tese é o D EP S KY, um sistema que garante disponibilidade, integridade e confidencialidade de informação armazenada em clouds. A ideia
fundamental deste sistema é replicar a informação por várias clouds de armazenamento,
utilizando algoritmos para armazenamento fiável e partilha de segredos.
O D EP S KY fornece uma abstracção de um sistema de armazenamento tolerante a
intrusões, possuindo algoritmos que permitem a leitura e escrita de dados em clouds. Durante o seu desenvolvimento tomaram-se opções tendo em conta a disponibilidade e o
Capítulo 1. Introdução
4
custo do armazenamento em clouds. Outra contribuição importante é a análise das medidas efectuadas ao sistema e a esses serviços de armazenamento em clouds. Os resultados
obtidos permitiram efectuar a avaliação aos protocolos do D EP S KY.
É também de referir que a parte considerável do tempo dispendido em termos de
desenvolvimento do sistema foi para estudo das API’s dos serviços usados e subjacente
concretização do controlador (responsável pela comunicação) para cada serviço.
1.4
Publicações
O trabalho descrito neste relatório deu origem à seguinte publicação:
Título: Melhorando a Disponibilidade e Confidencialidade dos Dados Armazenados em
Clouds [30]
Autores: Bruno Quaresma, Alysson Bessani e Paulo Sousa
Em: INForum 2010 [6] - Segurança de Sistemas de Computadores e Comunicações
1.5
Planeamento
O planeamento inicial deste trabalho consistia nas seguintes tarefas:
• T1 - Estudo da replicação e de técnicas de replicação
• T2 - Estudo de técnicas que garantem confidencialidade em informação replicada,
nomeadamente esquemas de partilha de segredos e códigos de apagamento
• T3 - Estudo das clouds de armazenamento existentes na web e suas API’s
• T4 - Desenho do sistema
• T5 - Concretização do sistema
• T6 - Testes ao sistema
• T7 - Escrita da Tese de Mestrado
A calendarização destas tarefas é apresentada na figura 1.5. Este planeamento foi
seguido na perfeição até à fase de testes ao sistema (T6). Teve que ser investido mais um
mês nesta tarefa devido à necessidade de se efectuarem melhoramentos ao sistema, o que
levou ao adiamento da escrita desta tese para o mês de Junho de 2010.
5
Capítulo 1. Introdução
Tarefas
T1
T2
T3
T4
T5
T6
T7
Mês/Ano
Setembro e Outubro de 2009
Novembro de 2009
Dezembro de 2009 e Janeiro de 2010
Fevereiro de 2010
Março de 2010
Abril de 2010
Maio de 2010
Tabela 1.1: Planeamento inicial do PEI.
1.6
Estrutura do Documento
Este documento encontra-se organizado da seguinte forma:
• Capítulo 2 - Este capítulo descreve o trabalho relacionado com o sistema desenvolvido. É introduzido o conceito tolerância a intrusões e como a replicação é importante para este tipo de sistemas. Também são introduzidas técnicas de distribuição
de informação por réplicas de maneira a garantir confidencialidade. Mais especificamente são abordadas as seguintes técnicas: partilha de segredos e códigos de
apagamento com criptografia simétrica. Neste capítulo também são apresentadas
as clouds de armazenamento, assim como são analisadas propriedades e características que estas devem assegurar.
• Capítulo 3 - Apresentação do sistema de armazenamento tolerante a intrusões D EP S KY,
modelo de sistema, modelo de dados e protocolos concretizados. Para concluir são
analisados trabalhos recentes que tentam fazer algo similar ao D EP S KY, sendo efectuadas algumas comparações entre os sistemas estudados.
• Capítulo 4 - Neste capítulo são analisados os detalhes da concretização do sistema
descrito no capítulo anterior.
• Capítulo 5 - Este capítulo contém uma avaliação experimental ao D EP S KY, efectuada durante o mês de Junho de 2010. São analisados os desempenhos dos protocolos e das clouds individualmente.
• Capítulo 6 - Neste último capítulo são apresentadas as conclusões deste trabalho
assim como algum trabalho a desenvolver no futuro.
Capítulo 1. Introdução
6
Capítulo 2
Trabalho Relacionado
Neste capítulo é resumido o estudo inicial efectuado sobre a área de tolerância a intrusões e sobre clouds de armazenamento.
2.1
2.1.1
Tolerância a Intrusões
Introdução ao Tema
Com a utilização crescente dos sistemas distribuídos, em variadas áreas de actividade,
aumentou a preocupação com a confiabilidade dos diversos componentes de um sistema
[33, 17]. A tolerância a faltas é um dos aspectos mais importantes nos modelos de sistemas distribuídos clássicos e o seu objectivo é aumentar a disponibilidade e fiabilidade
dos sistemas. Um sistema tolerante a faltas deve continuar a prestar o seu serviço correctamente mesmo na eventualidade de existir um problema com algum dos componentes.
Esta visão levou à adopção de uma atitude pessimista em relação ao funcionamento dos
sistemas distribuídos, na qual se assume que nenhum sistema é totalmente correcto (e.g.,
foram cometidos erros na fase de especificação, desenho ou concretização do sistema) e
poderá estar susceptível a faltas.
Os sistemas distribuídos em geral assentam no modelo: Falta ⇒ Erro ⇒ Falha. A
tolerância a faltas não trata de impedir ou prevenir que faltas aconteçam mas antes evitar
que estas levem a erros e consequente falha do sistema. Opta-se por esta abordagem
porque pode ser impossível prever todas as faltas possíveis num sistema, já que estas
podem ser causadas por diversos motivos assim como ter uma origem interna ou externa.
A replicação foi a técnica encontrada para construir sistemas tolerantes a faltas pois
contribui para um aumento da resiliência do sistema. A resiliência de um sistema distribuído está definida como o número f de um total de n máquinas que podem falhar sem
este sistema renunciar à disponibilidade e à consistência. Esta distribuição também aumenta a resistência a faltas na medida em que, ao contrário de um sistema centralizado,
não existe um ponto único de falha. Contudo, no paradigma da tolerância a faltas, as
técnicas usadas assumem que componentes do sistema podem falhar por paragem ou por
7
Capítulo 2. Trabalho Relacionado
8
omissão de passos do algoritmo que executa. Isto significa que o sistema pode não estar
preparado para lidar com falhas causadas com intencionalidade por um atacante malicioso, e consequentemente pode ser comprometido.
O número de ataques efectuados com sucesso a sistemas distribuídos tem vindo a
aumentar o que levou organizações a preocuparem-se com a segurança e confiabilidade
dos seus serviços. Isto fez com que surgisse o conceito tolerância a intrusões [33, 20]. A
tolerância a intrusões é uma extensão da tolerância a faltas tradicional que considera intrusões como faltas. Com esta abordagem tornou-se possível desenvolver sistemas tolerantes
a faltas que, ao mesmo tempo, respeitam as propriedades de segurança definidas.
Existe ainda outro conceito relacionado com tolerância a intrusões, denominado tolerância a faltas bizantinas. Faltas bizantinas [27], ou arbitrárias, são o tipo de faltas mais
genérico que existe e englobam todos os tipos de faltas que podem ocorrer num sistema,
incluindo as intrusões. Quando ocorre uma falta bizantina, o sistema pode responder de
forma imprevisível a menos que tenha sido construído para tolerar este tipo de faltas.
A maioria dos trabalhos relacionados com a tolerância a intrusões assume que o sistema está envolvido num ambiente bizantino, ou seja, que o sistema é susceptível a faltas
arbitrárias, seja uma intrusão, acidental ou maliciosa, uma falha do software ou por motivos externos ao sistema.
Tal como na tolerância a faltas clássica, recorre-se a replicação para conceber sistemas
tolerantes a faltas bizantinas. Nas próximas secções são discutidas alguns modelos de
replicação tolerantes a faltas bizantinas estudados. Também são discutidas técnicas para
garantir a confidencialidade de dados replicados.
2.1.2
Replicação
A ideia básica da replicação consiste em distribuir cópias de informação por um conjunto de servidores e tem sido amplamente usada em tolerância a faltas para garantir a
disponibilidade e a fiabilidade de sistemas distribuídos. Muitos dos trabalhos em sistemas
distribuídos tolerantes a intrusões são também baseados em replicação. Este tipo de solução permite garantir a disponibilidade e a integridade do sistema se existirem intrusões
num número limitado de réplicas.
Existem dois modelos de replicação tolerantes a faltas bizantinas, a Replicação de
Máquina de Estados [25] e Sistemas de Quóruns Bizantinos [28]. Existe ainda uma outra
abordagem que foi estudada e que pode ser vista como um híbrido entre os dois modelos
referidos antes, denominada Sistemas de Quóruns Activos [12].
Seguidamente, todas estas abordagens são analisadas com mais detalhe.
Replicação de Máquina de Estados
A replicação de máquina de estados é a abordagem generalista para a concretização
de serviços tolerantes a faltas em que cada servidor é uma máquina de estados definida
Capítulo 2. Trabalho Relacionado
9
por variáveis de estado e comandos atómicos, que são operações sobre as variáveis de
estado. Os clientes enviam pedidos para a execução de comandos para todas as réplicas
do sistema. Nesta abordagem as réplicas começam todas com o mesmo estado e no tempo
de actividade das réplicas existe acordo e ordem total o que significa que todas as réplicas
executam os mesmos comandos pela mesma ordem. Obter estas propriedades, acordo e
ordem total, requer o uso de algoritmos distribuídos que ofereçam certas garantias sobre a
entrega das mensagens ao conjunto de réplicas. Para além disso, as operações executadas
pelas réplicas têm de ser deterministas pois o estado resultante, após a operação, em todas
as réplicas do sistema tem de ser o mesmo. Como é impossível resolver o problema
do consenso, também conhecido como o problema da difusão atómica, em ambientes
assíncronos de forma determinista os sistemas usualmente requerem a existência de certos
limites temporais [19].
Sistemas de Quóruns Bizantinos
Um sistema de quóruns bizantinos [28] pode ser definido como um conjunto de subconjuntos de servidores, em que cada sub-conjunto é um quórum. A intersecção e a
disponibilidade são duas características fundamentais dos quóruns. A primeira assegura
que as operações efectuadas nos diferentes quóruns mantêm-se consistentes enquanto que
a segunda está implícita pois cada quórum actua em prol do sistema.
Um sistema de quóruns pode ser usado para prover uma abstracção de memória partilhada fiável bastando para isso definir objectos distribuídos e operações a realizar sobre
estes. Através de um sistema de quóruns é possível definir objectos distribuídos e sobre
eles realizar operações de tal forma que simulam a existência de uma memória partilhada
fiável.
Na maioria das implementações de sistemas de quóruns bizantinos são usados n ≥
3f + 1 servidores com quóruns de tamanho 2f + 1, sendo f o número de faltas toleradas.
Assim é assegurado que, mesmo na eventualidade de acontecerem f faltas, existem pelo
menos dois quóruns que se intersectam numa réplica correcta, ou seja, cada um dos dois
quóruns mantém um número de servidores correctos de maneira a que pelo menos um
quórum é formado apenas por servidores correctos.
Tipicamente, em sistemas de quóruns, o estado de um registo em cada servidor é
representado pelo seu valor e por uma estampilha temporal, ou número de versão. Uma
operação de escrita sobre este registo é processada da seguinte maneira: a estampilha
temporal é lida dos quóruns, incrementada, indicando a próxima versão do registo, e logo
a seguir é escrito o novo valor para o sistema juntamente com a nova estampilha. Numa
operação de leitura sobre este registo o sistema retorna o valor e estampilha correntes
do registo. Em alguns sistemas de quóruns bizantinos em que existe concorrência entre
operações, é usado um mecanismo denominado de writeback no qual o valor lido é escrito
de volta no sistema obrigando a que todas as leituras realizadas posteriormente retornem
Capítulo 2. Trabalho Relacionado
10
o mesmo par (valor, e estampilha temporal) ou uma versão mais recente desse par.
Sistemas de Quóruns Activos
Enquanto que a replicação de máquina de estados é uma solução genérica para concretizar sistemas tolerantes a faltas bizantinas, os quóruns são geralmente usados para
construir repositórios de dados tolerantes a faltas bizantinas. Ao servirem para concretizar algo de mais simples do que replicação de máquina de estados, muitas vezes os
trabalhos com quóruns evitam a necessidade de realizar consenso não ficando limitados
pelo resultado FLP [19], podendo os algoritmos ser totalmente assíncronos. No entanto,
a principal diferença entre a replicação de máquina de estados e os sistemas de quoruns
é que as operações na replicação de máquina de estados envolvem sempre todos os servidores, enquanto que nos sistemas de quóruns as operações são geralmente feitas sobre
um quórum, o que torna os algoritmos mais escaláveis.
Segundo a proposta [12], os Sistemas de Quóruns Activos (SQA) surgiram da constatação de que os sistemas de quóruns apresentam uma escalabilidade e simplicidade maior
que os protocolos baseados em máquinas de estados, mas apenas podem ser utilizados na
concretização de sistemas simples como por exemplo sistemas de armazenamento.
Sistemas mais complexos que necessitam que exista acordo entre servidores têm de
ser concretizados recorrendo a replicação de máquinas de estado. Um sistema de quóruns
activos pode ser visto como um híbrido entre sistemas de quóruns e máquinas de estado,
que junta as duas abordagens num único sistema. Um sistema deste tipo usa diferentes
protocolos para diferentes operações, ou seja, protocolos de sistemas de quóruns para
as operações de leitura e escrita, e, protocolos de máquina de estados para outras mais
complexas, como uma actualização.
Através de SQA é assegurado que um sistema construído sobre esta abordagem permanece correcto na presença de n ≥ 3f + 1 réplicas, sendo f o número máximo de
réplicas que podem falhar de forma bizantina. Se este pressuposto for satisfeito um objecto implementado usando o SQA satisfaz as seguintes propriedades:
• Linearizability: O sistema executa operações numa determinada ordem de modo a
que aparente ser acedido sequencialmente [21];
• Wait-freedom: Operações requesitadas por clientes correctos terminam, independentemente do comportamento de outros clientes, correctos ou maliciosos, do sistema [23].
A primeira é uma propriedade de safety que garante que as réplicas se comportam simulando um sistema centralizado, executando uma mensagem de cada vez. A segunda
propriedade é uma propriedade de liveness importante para garantir a correcta terminação
de todas as operações.
Capítulo 2. Trabalho Relacionado
11
Um SQA permite replicar objectos sendo que, sobre estes, é possível realizar três tipos
de operações distintas:
• Escrita: O estado do objecto é alterado para o valor recebido como entrada.
• Leitura: O estado do objecto é retornado.
• Actualização (Read-Modify-Write): O estado do objecto é modificado de acordo
com os parâmetros recebidos e o estado do objecto.
As operações de leitura e escrita são implementadas através de sistemas de quóruns
bizantinos e por isso são operações assíncronas, não dependentes de condições optimistas
ou pressupostos sobre tempo para garantir a terminação ao contrário da operação de actualização que recorre a replicação de máquina de estados, necessitando de sincronia parcial
para resolver o consenso. Os protocolos de leitura e escrita são baseados nos sistemas de
quóruns e o de actualização é baseado no CL-BFT, apresentado em [15].
2.1.3
Confidencialidade
Confidencialidade é a propriedade da informação que garante que esta não será divulgada a entidades sem autorização, por outras palavras, garantir que a informação está
apenas acessível para os que têm autorização de acesso a esta.
A confidencialidade é compreendida no domínio da segurança informática, como a
protecção de informação trocada entre um remetente e um ou mais destinatários contra
terceiros. Isto deve ser feito independentemente da segurança do sistema de comunicação
utilizado. De facto, uma questão de grande interesse é o problema de garantir o sigilo de
comunicação utilizado quando o sistema é inerentemente inseguro, como a Internet.
Num sistema que garante a confidencialidade, um terceiro que obtenha informação
trocada entre rementente e destinatário não será capaz de extrair qualquer informação
inteligível. Isto é garantido através de mecanismos de criptografia.
A replicação é normalmente vista como sendo má para a confidencialidade, porque se
informação privada se encontra replicada apenas se torna mais fácil para um atacante a
conseguir, não mais difícil. Apesar disso, existem algumas técnicas para garantir confidencialidade em dados replicados, como as que são explicadas de seguida.
Partilha de Segredos
Um esquema de partilha de segredos [32] é o método para dividir um segredo entre
um grupo de participantes, em que a cada um deles é atribuída um parte do segredo.
O segredo pode ser reconstruído apenas quando um determinado número de partes são
recombinadas, pois partes individuais não têm utilidade por si só.
Mais formalmente, num esquema de de partilha de segredos existe um distribuidor e n
participantes. O distribuidor gera o segredo a partir da informação original, divide-o por
Capítulo 2. Trabalho Relacionado
12
n partes e entrega uma parte a cada participante. As partes poderão mais tarde ser usadas
para a reconstrução da informação original mas individualmente não fornecem nenhuma
informação sobre seu conteúdo, ou seja, é inexequível extrair de uma parte alguma da
informação original.
O distribuidor usa um algoritmo de maneira a que grupos de t ou mais participantes,
possam reconstruir a informação original, com as suas partes. Se por exemplo n = 5 e
t = 3, a informação original é distribuída por 5 partes, uma para cada participante, e um
grupo de 3 ou mais partes participantes pode desvendar o segredo.
Códigos de Apagamento
Os códigos de apagamento são semelhantes aos códigos de correcção de erros (FEC
- Forward Error Correction) usados em telecomunicações, mas enquanto nos primeiros a
informação pode apenas ser apagada, nos últimos pode também ser modificada. A ideia
base consiste na divisão de um ficheiro em n fragmentos de forma a que seja suficiente
ter k fragmentos para reconstruí-lo, mas k − 1 fragmentos não cheguem para o fazer. Para
este efeito usa-se um código de apagamento-(k,n).
No contexto da confiabilidade apenas foram estudadas algumas propostas, nomeadamente o mecanismo denominado AVID (Asynchronous Verifiable Information Dispersal)
e o mesmo mecanismo mas com confidencialidade, o cAVID. Ambos propostos em [14].
Um cliente que quer armazenar um ficheiro F começa por o codificar como um vector [F 1; ...; F n] usando um código de apagamento-(k,n). Além disso obtém um conjunto
de fingerprints [24] calculando um vector com sínteses criptográficas de cada F i : D =
[D1; ...; Dn]. Depois, toda essa informação é enviada para os servidores usando um protocolo de difusão fiável.
Se o cliente for malicioso e alguns dos fragmentos estiverem corrompidos, há duas
possibilidades: o número de fragmentos disponíveis permite reconstruir o ficheiro, o que
é feito; ou não é possível reconstruir esses fragmentos e o ficheiro não é armazenado.
Quando a operação termina os servidores apagam todos os fragmentos que não lhes pertencem.
A operação de leitura consiste simplesmente em pedir fragmentos aos servidores até se
obterem os k necessários para reconstruir F . O parâmetro k tem de verificar a condição:
f + 1 ≤ k ≤ n − 2f . A melhor resistência é obtida quando n = 3f + 1, logo k = f + 1.
O mesmo artigo apresenta o esquema cAVID que garante também a confidencialidade
dos dados armazenados. Para garantir a confidencialidade é necessário haver controlo de
acesso ao ficheiro. Para o efeito junto do ficheiro é guardada uma lista de controlo de
acesso L com os identificadores dos clientes que a eles podem aceder. A forma como é
conseguida a confidencialidade é simples: o ficheiro é cifrado usando criptografia simétrica antes de ser armazenado usando o esquema AVID. Uma desvantagem é a necessidade
de partilha de uma chave secreta O problema é o que se faz da chave secreta. Se o cliente
Capítulo 2. Trabalho Relacionado
13
ficasse com a chave para si, só ele poderia recuperar o ficheiro, o que em geral não é o
objectivo.
2.2
2.2.1
Clouds de Armazenamento
Considerações Gerais
Uma cloud de armazenamento pode ser descrita como um serviço online que fornece
espaço nos seus servidores para um cliente armazenar informação. A comunicação entre
o cliente e o serviço, como o acesso ou actualização de dados, é efectuada sobre a Internet.
Existem variados sistemas de armazenamento em clouds, uns possuem um foco muito
específico, como armazenar apenas mensagens de e-mail ou imagens digitais, outros podem armazenar todo o tipo de informação digital.
As instalações que abrigam sistemas de armazenamento em clouds são chamados de
data centers. Uma cloud de armazenamento pode ser concretizada com um ou mais data
centers.
O seu funcionamento pode ser descrito da seguinte forma: um cliente envia ficheiros
através da Internet para os servidores que guardam a informação. O acesso aos servidores
pelo cliente é efectuado através de interfaces web ou serviços web, que permitem o acesso
e manipulação dos dados armazenados. Tais serviços são usualmente baseados no modelo
REST (REpresentational State Transfer) ou na arquitectura SOAP (Simple Object Access
Protocol).
Os sistemas de armazenamento em clouds geralmente usam centenas de servidores porque ocasionalmente os computadores precisam de manutenção ou reparação logo
torna-se importante armazenar a mesma informação em várias máquinas, para introduzir
redundância no sistema. Sem redundância, um sistema de armazenamento em clouds não
poderia garantir a um cliente que a sua informação estará sempre disponível. Por exemplo, a maioria dos sistemas replica a informação por servidores que usam diferentes fontes
de electricidade (normalmente também geograficamente afastados) ou usam UPS1 , permitindo aos clientes o acesso à sua informação mesmo em caso de falha no fornecimento
de electricidade.
Nem todos os clientes estão preocupados apenas com a falta de espaço, alguns usam
sistemas de armazenamento em clouds para backup de informação, o que garante que,
caso haja algum problema na infra-estrutura computacional do cliente, a informação estará intacta na cloud de armazenamento.
Actualmente estão disponíveis na web algumas centenas de fornecedores de armazenamento em clouds e o número tem vindo a aumentar. Além disso, também o espaço de
armazenamento oferecido aos clientes parece crescer regularmente.
1
UPS (Uninterruptible Power Supply) - é um sistema de alimentação elétrico que entra em funcionamento quando há interrupção no fornecimento de energia, alimentando os dispositivos a ele ligados.
Capítulo 2. Trabalho Relacionado
14
Existem fornecedores de armazenamento em clouds que cobram uma quantia fixa por
uma quota de espaço e largura de banda de entrada e saída de dados, enquanto outros
usam um modelo pay-per-use e cobram quantias variáveis consoante o espaço ocupado e
a largura de banda utilizada pelo cliente. Além disso, o modelo de cobrança das clouds
pay-per-use incorpora o conceito de elasticidade de recursos: paga-se apenas pelo uso e
o serviço pode crescer arbitrariamente para acomodar altas demandas esporádicas.
De seguida exemplificam-se alguns dos serviços que fornecem armazenamento em
clouds (Cloud Storaging):
• Clouds Pay-per-use
– Amazon Simple Storage Service (Amazon S3) [1]
– Microsoft Windows Azure Platform [8]
– Nirvanix Storage Delivery Network (Nirvanix SDN) [9]
– RackSpace [10];
• Clouds de custo fixo
– DivShare [3]
– DocStoc [4]
– Box.net [2]
– FilesAnywhere [5]
Em geral, o preço do armazenamento online tem vindo baixar devido à entrada de
cada vez mais empresas neste negócio. Isto levou muitas empresas que cobram pelos seus
serviços a optarem por fornecer uma alternativa gratuita que oferece algum espaço para
armazenamento, mas com limitações quando comparados aos serviços pagos.
As duas maiores preocupações acerca do armazenamento em clouds são a fiabilidade
e a segurança. É improvável que uma organização confie a seus dados critícos a outra
entidade sem a garantia que terá acesso a estes dados sempre que quiser (disponibilidade),
que estes não serão corrompidos (integridade) e que mais ninguém terá acesso a eles sem
a sua autorização (confidencialidade). Para garantir a segurança da informação, a maioria
dos sistemas usa uma combinação de técnicas, incluindo:
• Criptografia: algoritmos criptográficos são usados para codificar a informação tornandoa ininteligível e quase impossível de decifrar sem a chave usada para cifrar a informação, normalmente uma chave secreta partilhada entre cliente e o serviço;
• Autenticação: é necessário o registo do cliente através da criação de credenciais de
acesso (e.g., username e password);
Capítulo 2. Trabalho Relacionado
15
• Autorização: o cliente define quem pode aceder à sua informação.
Mesmo com estas medidas de protecção, muitas pessoas acreditam que informação
armazenada num sistema de armazenamento remoto é vulnerável. Existe sempre a possibilidade de um hacker malicioso, de alguma maneira, ganhar acesso à informação do
sistema, por exemplo, devido a vulnerabilidades existentes neste. Existe também a possibilidade de funcionários da empresa com acesso aos servidores poderem roubar, alterar
ou destruir informação. As empresas no negócio de armazenamento em clouds investem
muito dinheiro em medidas de segurança para limitar a possibilidade de roubo ou corrupção da informação. Além disso, há sempre a preocupação de colocar os dados critícos (e
muitas vezes confidenciais) nas mãos de terceiros, que terão acesso às informações neles
contidos.
Finalmente, há também a questão da fiabilidade e disponibilidade dos serviços de armazenamento. Armazenar informação num sistema remoto acedido via Internet coloca a
organização vulnerável a todos os problemas de conectividade e indisponibilidade temporária da Internet. Além disso, praticamente todos os grandes fornecedores de serviços
de armazenamento já sofreram problemas de disponibilidade e/ou corromperam dados de
clientes, mesmo com a redundância interna de seus sistemas (os dados são tipicamente
armazenados em diferentes data centers do provedor).
2.2.2
Detalhes Adicionais
Nesta secção são descritos detalhes adicionais de alguns serviços de armazenamento
estudados.
Distribuição geográfica de Data Centers
A distribuição geográfica é importante na medida em que cria redundância no serviço,
não existindo um ponto único de falha, e principalmente porque também aproxima os
dados dos clientes.
A lista seguinte relata esta distribuição global de data centers das clouds pay-per-use
estudadas:
• Amazon S3 - 3 nos Estados Unidos mais um na Irlanda e outro em Singapura.
• Azure - Pelo menos um nos Estados Unidos (Chicago) e outro na Irlanda (Dublin).
• Nirvanix - 3 nos Estados Unidos (California, Texas e New Jersey) mais um na
Alemanha e outro no Japão.
• RackSpace - 6 nos Estados Unidos (3 no Texas, 2 na Virginia e 1 em Chicago) mais
2 no Reino Unido e outro em Hong Kong.
16
Capítulo 2. Trabalho Relacionado
Acordo de nível de serviço
Um SLA (Service Level Agreement) é a parte de um contrato de serviços entre duas ou
mais entidades no qual o nível de prestação do serviço é definido formalmente. Na prática,
o termo é usado no contexto de tempo de entrega de um serviço ou de um desempenho
específico. Por exemplo, se a empresa A contratar um nível de serviço de entregas de
95% em menos de 24 horas à Empresa B, esta já sabe que de todas as entregas que lhe
forem dadas para fazer, no mínimo 95% tem que ser feitas em menos de 24 horas.
No contexto do armazenamento em clouds este acordo concentra-se principalmente
no nível de disponibilidade dos dados armazenados.
Todas as clouds de armazenamento pay-per-use estudadas (i.e., Amazon S3, Azure,
Nirvanix e RackSpace) garantem uma disponibilidade de 99,9% existindo compensações
para o cliente caso esta percentagem não se verifique. Estas compensações são, em geral,
aplicadas como descontos na facturação do cliente. Os descontos podem variar entre os
10% e os 100% dependendo do nível de disponibilidade efectivamente verificado. 2
A única desvantagem para o cliente é ter de monitorizar a disponibilidade e depois
ter de relatar ao fornecedor se o nível contratualizado não se verificar para ter direito aos
descontos. Existe também um tempo limite para reclamação dos descontos (e.g., 15 dias
no caso da Nirvanix e 30 dias nos restantes).
Custo do armazenamento em clouds
O preço praticado pelos serviços de armazenamento em clouds é um dos factores que
torna este tipo de armazenamento tão atractivo e que leva muitas organizações a migrarem
os seus dados para estes serviços. A tabela 2.1 apresenta o preço praticado por 4 dos serviços mais utilizados actualmente. É de salientar que alguns dos serviços fazem a distinção
de armazenamento em diferentes localizações (e.g., o custo de armazenamento num data
center na Europa e num na Ásia é diferente). Por isso, apenas estão representados os
custos para armazenamento em data centers europeus (i.e., Azure e Amazon S3).
Armazenamento
Entrada
Saída
Nirvanix
0,25
0,18
0,18
Azure - EU
0,15
0,10
0,15
Amazon S3 - EU
0,15
0,10
0,10
RackSpace
0,15
0,08
0,22
Tabela 2.1: Custo, em USD, do armazenamento, entrada e saída de 1 Gb de dados em
serviços de armazenamento pay-per-use estudados.
A tabela 2.2 complementa a informação apresentada na tabela 2.1 com o custo de
pedidos efectuados aos serviços mencionados.
2
e.g., No SLA do Amazon S3 está contratualizado um desconto de 10%, se a disponibilidade verificada
for inferior a 99,9% mas igual ou superior a 99%, e um desconto de 25% se esta for inferior a 99%.
17
Capítulo 2. Trabalho Relacionado
Tipo de Pedido
GET *
PUT **
Nirvanix
0
0
Azure - EU
0,01
0,01
Amazon S3 - EU
0,01
0,10
RackSpace
0
0 ***
Tabela 2.2: Custo, em USD, de efectuar 10000 pedidos a serviços de armazenamento
pay-per-use estudados.
Legenda da tabela 2.2
*
**
***
também inclui pedidos do tipo HEAD e DELETE.
também inclui pedidos do tipo POST, LIST ou COPY.
cobra 0,20 se forem pedidos para ficheiros com menos de 250K bytes.
Para finalizar esta análise a tabela 2.3 apresenta as limitações conhecidas de alternativas gratuitas fornecidas por algumas clouds de custo fixo estudadas.
Serviço (conta gratuita)
DivShare
Docstoc
FilesAnywhere
Box.net
Limitações conhecidas
5 Gb de armazenamento; 10 Gb downloads/mês; Um download apenas pode ser efectuado dez segundos após o pedido;
1000 pedidos por minuto; Número de uploads diário limitado
a 50000; 50 Mb é o tamanho máximo permitido de um ficheiro; Apenas são permitidos 200 downloads diariamente;
1 Gb de armazenamento; 25 Mb é o tamanho máximo permitido de um ficheiro; Apenas são permitidos 25 downloads
diariamente;
1 Gb de armazenamento; 25Mb é o tamanho máximo permitido de um ficheiro;
Tabela 2.3: Alguns limites conhecidos de serviços livres de encargos estudados.
É de salientar que com estas alternativas gratuitas, a maior parte destes serviços não
permite transferências de dados concorrentes. No entanto estes limites são removidos ou
alterados quando se adquire um dos serviços pagos (e.g., contas Premium ou Professional).
2.3
Considerações Finais
Neste capítulo foram discutidos os paradigmas da tolerância a faltas e tolerância a
intrusões, convergindo estas para um modelo mais generalista de tolerância a faltas bizantinas, e a razão da necessidade de adoptar este tipo de abordagens na concepção de
sistemas seguros e confiáveis.
Foram estudadas algumas técnicas para a concretização de sistemas tolerantes a faltas bizantinas, a replicação máquina de estados, os sistemas de quóruns bizantinos e os
sistemas de quóruns activos. Também foram abordadas técnicas para garantir a confidencialidade em dados replicados, a partilha de segredos e os códigos de apagamento.
Capítulo 2. Trabalho Relacionado
18
Finalmente houve também uma análise das características e a oferta existente de serviços para armazenamento de informação na cloud.
Este estudo sobre o estado da arte foi importante na medida em que serviu de base para
o desenho do sistema proposto nesta tese, que irá ser apresentado no próximo capítulo.
Capítulo 3
D EP S KY
3.1
Apresentação
Este capítulo apresenta o D EP S KY, um sistema para replicação de dados em várias
clouds que melhora a disponibilidade, integridade e confidencialidade da informação armazenada. O D EP S KY é a contribuição mais importante desta tese.
Os blocos atómicos de dados no D EP S KY designam-se por unidades de dados (data
units), que podem ser actualizadas pelos seus donos e acedidas por um conjunto arbitrário
de leitores. A disponbilidade destas unidades é garantida mesmo em caso de falhas devido
ao uso de algoritmos de replicação para sistemas de quóruns bizantinos de disseminação
[28], onde os dados armazenados em cada servidor (i.e., que neste caso são clouds de
armazenamento) são auto-verificáveis devido ao uso de assinaturas digitais e resumos
criptográficos (i.e., se um servidor alterar o conteúdo dos dados, o leitor descobre e ignora
os dados corrompidos).
O D EP S KY oferece também a possibilidade da informação mais sensível ser protegida
através de um esquema de partilha de segredos [32, 31], introduzindo garantias de confidencialidade. Desta maneira, nenhuma cloud individualmente tem acesso à informação
contida nos dados.
A figura 3.1 ilustra como o D EP S KY distribui a informação (e.g., um ficheiro) pelas várias clouds. Estão representados dois clientes do sistema, um a usar o protocolo
ADS (Available D EP S KY) e outro a usar o protocolo CADS (Confidential & Available
D EP S KY). A diferença entre estes protocolos é a informação enviada para as clouds. No
caso de um cliente usar o protocolo ADS , é enviada uma cópia da informação para todas
as clouds. Com o protocolo CADS a informação é dividida em partes, tantas quanto o número de clouds, e depois cada parte é enviada para sua cloud. A informação é dividida de
maneira a que apenas seja necessário um determinado número de partes para reconstruir
a informação original, e não a totalidade das partes.
Nas secções seguintes são apresentados o modelo de sistema, o modelo de dados, os
dois protocolos já mencionados, ADS e CADS, e trabalhos similares ao D EP S KY.
19
20
Capítulo 3. D EP S KY
Amazon
S3
Nirvanix
SDN
Windows
Azure
RackSpace
Parte #1
Parte #2
JSS
Valor
Valor
Parte #3
Cliente [ADS]
Parte #4
O valor é
replicado pelas
clouds.
Cliente [CADS]
O valor é
dividido em
partes que
serão enviadas
uma para cada
cloud
Figura 3.1: Visão sobre a distribuição de informação pelas clouds.
3.2
Modelo de Sistema
O modelo de sistema utilizado no D EP S KY segue uma série de hipóteses pragmáticas
tidas em conta no desenho dos protocolos de replicação em clouds de armazenamento.
Cada cloud é representada por um servidor passivo (não executa nenhum código
dos protocolos) que oferece operações de leitura e escrita de dados com semântica de
consistência regular [26]: uma operação de leitura executada concorrentemente com uma
operação de escrita retorna o valor da unidade de dados antes da escrita ou o valor que
está a ser escrito.
Em primeiro lugar, assume-se que para cada unidade de dados há apenas um escritor,
e este escritor só sofre falhas por paragem. Isto significa que cada bloco de dados é
escrito por uma única entidade 1 , o que simplifica os protocolos já que não têm de lidar
com escritas concorrentes. Além disso, escritores maliciosos não são considerados pois
estes poderiam escrever dados sem sentido do ponto de vista da aplicação de qualquer
forma. Finalmente, estas duas hipóteses permitem a concretização de protocolos de leitura
e escrita em sistemas onde os servidores são apenas discos passivos, como as clouds de
1
Na prática pode existir mais de um escritor para uma unidade de dados desde que os acessos para
escrita sejam feitos isoladamente (o que pode requerer algum controlo de concorrência).
Capítulo 3. D EP S KY
21
armazenamento.
Os servidores (clouds) e leitores estão sujeitos a faltas arbitrárias ou bizantinas [27].
Esta decisão vai de encontro à hipótese pessimista de que não conhecemos o que há
dentro de uma cloud e portanto é seguro assumir que os dados lá armazenados podem ser
corrompidos arbitrariamente. Da mesma forma, como são suportados múltiplos leitores
para cada unidade de dados, é conveniente também assumir que estes podem ter qualquer
comportamento. Devido ao uso de sistemas de quóruns bizantinos de disseminação [28],
o sistema requer n ≥ 3f + 1 servidores para tolerar até f servidores um número ilimitado
de clientes faltosos.
É assumida também a ausência de um sistema de distribuição de chaves entre os clientes. Os leitores apenas sabem como aceder ao sistema para ler dados e também possuem
a chave pública do escritor para verificação e validação de dados.
3.3
Modelo de Dados
A figura 3.2 apresenta o modelo de dados do D EP S KY em três níveis:
Conceptual Data Unit Num nível conceptual temos os blocos representados por unidades de dados (data units) que contêm, além do seu valor (data), um número de versão
(version number) e informações de verificação que tornam os dados auto-verificáveis (verification data). Além disso são identificadas por um nome único (e.g.,X).
Generic Data Unit Genericamente, uma unidade de dados do D EP S KY é representada
em cada cloud por dois ficheiros: um contendo os metadados e o outro com o valor mais
recente armazenando na unidade. Estes dois ficheiros estão sempre dentro de um container. O container de uma unidade de dados, para além de conter os metadados e o valor
actual, pode conter também versões anteriores do valor desta unidade. O identificador
é usado para obter referências para container e metadados dessas unidades nos protocolos definidos, ou seja, o nome dos containers e dos ficheiros advém do identificador
da unidade de dados (e.g., numa unidade de dados com o identificador X, o container
denomina-se Xcontainer e o ficheiro de metadados denomina-se Xmetadata). Os ficheiros de metadados são os mais importantes pois é sempre necessário um quórum destes
nos protocolos definidos. Os metadados consistem na seguinte informação: um número
de versão (Version Number), o nome do ficheiro com o valor desta versão (Data Pointer)
e informação de verificação (Verification Data), que inclui um resumo criptográfico do
valor para verificação de integridade deste e, no caso de ser uma unidade de dados com
confidencialidade, dados públicos necessários para a leitura do valor. Para escrever ou
ler uma unidade de dados é sempre necessário obter o ficheiro de metadados deste em
primeiro lugar.
22
Capítulo 3. D EP S KY
Data Unit Implementation Ao nível de implementação, cada cloud possui uma representação da unidade de dados de acordo com a definição da sua estrutura interna (e.g., um
container é mapeado para um bucket na Amazon S3 ou para um blobcontainer na Azure).
Conceptual Data Unit
X
Generic Data Unit
Container X
Version Number
Verification Data
Metadata
Version Number
Data Unit Implementation
Amazon S3
Bucket X
Windows Azure
BlobContainer X
Metadata
Metadata
Data Pointer
Data
Data
Data
Nirvanix SDN
DivShare
Verification Data
Data
Folder X
Folder X
Metadata
Metadata
Data
Data
Figura 3.2: Decomposição do Data Unit X do D EP S KY, do conceito à concretização.
3.4
ADS - Available D EP S KY
Esta secção apresenta o algoritmo ADS que promove uma melhoria da disponibilidade de dados na cloud através da replicação das unidades de dados por várias clouds de
armazenamento.
3.4.1
Algoritmo de Escrita
1. Um cliente escritor começa por enviar um pedido de leitura dos metadados a todas
as clouds. O escritor espera n − f ficheiros de metadados correctamente assinados
por ele e lidos de diferentes clouds para então obter o número de versão máximo
dentre os contidos nestes ficheiros. O algoritmo 1 ilustra como são lidos os metadados.
2. O número de versão lido no passo anterior é incrementado em uma unidade, dando
origem ao número de versão dos dados a serem escritos nesta operação (linhas 4-8
do algoritmo 3). Um ficheiro, a conter os dados a serem escritos e cujo nome corresponde ao nome da unidade de dados concatenado com o número de versão, é criado
em todas as clouds (linhas 9-10 do algoritmo 3). O escritor espera confirmação da
escrita deste ficheiro de n − f clouds.
Capítulo 3. D EP S KY
23
3. Após conclusão da escrita da nova versão, são actualizados os metadados para a
nova versão sendo enviados pedidos de escrita para este efeito. Antes de serem
enviados, os metadados são assinados pelo escritor (linhas 11-17 do algoritmo 3).
Neste passo o ficheiro de metadados é actualizado (ficheiro com metadados anterior
é sobrescrito), ao contrário do passo 2 em que é escrita uma nova versão dos dados
num ficheiro diferente do da versão anterior. A operação de escrita termina quando
se recebe confirmação da actualização de metadados de n − f clouds (linha 18 do
algoritmo 3).
Note que o algoritmo de escrita preserva as versões anteriores da unidade de dados.
Estas versões podem ser apagadas quando o escritor achar conveniente através de um
procedimento de garbage collection que envia pedidos de remoção a todas as clouds.
3.4.2
Algoritmo de Leitura
1. Um cliente leitor começa por efectuar pedidos de metadados a todas as clouds e
esperar por n − f ficheiros de metadados correctamente assinados pelo escritor,
como está descrito no algoritmo 1. O leitor obtém o número de versão máximo
reportado nestes ficheiros.
2. Após obter o número de versão mais actual da unidade de dados, o cliente envia
pedidos de leitura para esta versão a todas as clouds e aguarda. A operação termina
quando é recebido um valor cujo resumo criptográfico é igual ao resumo criptográfico contido nos metadados. Só depois desta verificação de integridade é que o
valor é retornado (linhas 8-11 do algoritmo 4).
Optimização de leitura. Uma optimização importante para diminuir os custos monetários do protocolo de leitura (ver secção 5.1) é enviar o pedido de leitura da versão mais
actual do valor da unidade de dados apenas à cloud que responder mais rapidamente à
requisição de metadados e reportar a versão mais actual dos dados. Desta forma, em
casos sem falhas, apenas uma das clouds será lida. Caso esta cloud não responda atempadamente (timeout) ou retorne uma versão anterior, outras clouds são acedidas até que se
obtenha a versão mais recente.
3.5
CADS - Confidential & Available D EP S KY
O ADS garante a integridade e disponibilidade dos dados em clouds de armazenamento. No entanto, um dos problemas fundamentais neste tipo de solução é evitar que
entidades não autorizadas tenham acesso aos dados armazenados na cloud.
Capítulo 3. D EP S KY
24
Esta secção apresenta o protocolo CADS, que integra um algoritmo criptográfico de
partilha de segredo de tal forma que os dados armazenados em cada cloud individualmente sejam de pouca utilidade.
Um esquema de partilha de segredos [32, 31], conforme já explicado na secção 2.1.3,
é o método para dividir um segredo entre um grupo de n participantes, em que a cada um
deles é atribuída um parte do segredo (que tem o mesmo tamanho do segredo original).
O segredo pode ser reconstruído apenas quando f + 1 dessas partes são recombinadas e
qualquer combinação de até f partes individuais não revelam nenhuma informação sobre
o segredo.
A única diferença entre os protocolos de escrita do ADS e do CADS é que neste
último introduziu-se um algoritmo de partilha de segredos no passo 2 do ADS de tal
forma a produzir tantas partes do segredo (valor a ser escrito na unidade de dados) quanto
o número de clouds. Cada uma destas partes é depois enviada para sua respectiva cloud
(linhas 8-10 do algoritmo 5).
O algoritmo de leitura do CADS funciona de forma bastante similar ao ADS, porém,
ao invés de aguardar apenas uma resposta com a versão mais actual dos dados (ADS passo 2), esperam-se f + 1 partes de diferentes clouds para combiná-las usando o algoritmo de partilha de segredos, obtendo o valor originalmente escrito (linhas 9-13 do
algoritmo 6).
Para garantir a confidencialidade ponto-a-ponto na Internet, o CADS depende da utilização de HTTP sobre SSL (HTTPS) para que a informação que circula na rede seja
imperceptível para terceiros. Com a utilização de HTTP sem SSL um atacante que conseguisse interceptar f + 1 partes poderia reconstruir o segredo.
Algoritmo 1: query_metadata(dataUnit)
Entrada: unidade de dados do D EP S KY
Saída: vector com n − f metadados assinados lidos de diferentes clouds
1
2
3
4
5
6
7
8
9
10
11
12
13
início
m[0 .. n − 1] ←− ⊥
para 0 ≤ i ≤ n − 1 faça em paralelo
tmi ←− cloudi .get(dataU nit, ”metadata”)
se verif y(tmi , Pukw ) então
m[i] ←− tmi
fim
fim
enquanto |{i | m[i] 6=⊥}| < n − f faça
sleep(50ms);
/* aguarda 50ms antes de continuar */
fim
retorna m
fim
Capítulo 3. D EP S KY
25
Algoritmo 2: write_value(dataUnit, n[0 .. n − 1], v[0 .. n − 1])
Entrada: unidade de dados do D EP S KY, identificadores (nomes) e valores a
escrever
Saída: nada
1
2
3
4
5
6
7
8
9
início
ok[0 .. n − 1] ←− false
para 0 ≤ i ≤ n − 1 faça em paralelo
oki ←− cloudi .put(dataU nit, n[i], v[i])
fim
enquanto |{i | m[i] = true}| < n − f faça
sleep(50ms);
/* aguarda 50ms antes de continuar */
fim
fim
Algoritmo 3: ADS_write(dataUnit,v)
Entrada: unidade de dados do D EP S KY e valor a escrever
Saída: nada
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
início
n[0 .. n − 1] ←− ⊥
v[0 .. n − 1] ←− ⊥
se max_ver = −1 então
m ←− query_metadata(dataU nit)
max_ver ←− max ({m[i].version|0 ≤ i ≤ n − 1})
fim
new_ver ←− max_ver + 1
∀i ∈ {0 , ..., n − 1} : n[i] ←− ”value” + new_ver, v[i] ←− v
write_value(dataU nit, n, v)
∀i ∈ {0 .. n − 1} : n[i] ←− ”metadata”
para 0 ≤ i ≤ n − 1 faça
new_meta ←− hnew_ver, H(v), n[i]i
sign(new_meta, Prkw )
v[i] ←− new_meta
fim
write_value(dataU nit, n, v)
max_ver ←− new_ver
fim
Capítulo 3. D EP S KY
26
Algoritmo 4: ADS_read(dataUnit)
Entrada: unidade de dados do D EP S KY
Saída: valor da unidade de dados do D EP S KY
1
2
3
4
5
6
7
8
9
10
11
12
início
m ←− query_metadata(dataU nit)
max_id ←− i | m[i].version = max ({m[i].version|0 ≤ i ≤ n − 1})
v[0 .. n − 1] ←−⊥
para 0 ≤ i < n − 1 faça em paralelo
v[i] ←− cloudi .get(dataU nit, ”value” + m[max_id].version)
fim
enquanto ¬∃i : v[i] 6=⊥ ∧H(v[i]) = m[max_id].verif ication faça
sleep(50ms);
/* aguarda 50ms antes de continuar */
fim
retorna v[i]
fim
Algoritmo 5: CADS_write(dataUnit,v)
Entrada: unidade de dados do D EP S KY e valor a escrever
Saída: nada
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
início
n[0 .. n − 1] ←−⊥
se max_ver = −1 então
m ←− query_metadata(dataU nit)
max_ver ←− max ({m[i].version|0 ≤ i ≤ n − 1})
fim
new_ver ←− max_ver + 1
v[0 .. n − 1] ←− get_shares(v)
∀i ∈ {0 .. n − 1} : n[i] ←− ”value” + new_ver
write_value(dataU nit, n, v)
para 0 ≤ i < n − 1 faça
new_meta ←− hnew_ver, H(v[i]), n[i]i
sign(new_meta, Prkw )
v[i] ←− new_meta
fim
∀i ∈ {0 .. n − 1} : n[i] ←− ”metadata”
write_value(dataU nit, n, v)
max_ver ←− new_ver
fim
Capítulo 3. D EP S KY
27
Algoritmo 6: CADS_read(dataUnit)
Entrada: unidade de dados do D EP S KY
Saída: valor da unidade de dados do D EP S KY
1
2
3
4
5
6
7
8
9
10
11
12
13
14
início
m ←− query_metadata(dataU nit)
max_id ←− i | m[i].version = max ({m[i].version|0 ≤ i ≤ n − 1})
v[0 .. n − 1] ←−⊥
para 0 ≤ i ≤ n − 1 faça em paralelo
v[i] ←− cloudi .get(dataU nit, ”value” + m[max_id].version)
fim
valueHash ←− m[max_idx].verif ication
enquanto |{i | v[i] 6=⊥}| < n − f
faça
sleep(50ms);
/* aguarda 50ms antes de continuar */
fim
retorna combine_shares(v)
fim
3.6
Trabalhos Similares
De acordo com a pesquisa efectuada e até onde se sabe, existem apenas dois trabalhos
bastante recentes que tentam fazer algo similar ao D EP S KY para melhorar a confiabilidade e segurança dos dados armazenados em clouds de armazenamento, e ambos foram
desenvolvidos em paralelo com o trabalho aqui apresentado.
O HAIL (High-Availability Integrity Layer) [13] consiste num conjunto de protocolos
criptográficos que juntam códigos de apagamento com provas de recuperação que permitem a concretização de uma camada de software para proteger a integridade dos dados
armazenados em clouds, mesmo que estas sejam invadidas e corrompidas por um adversário móvel.
Quando comparado ao D EP S KY, o HAIL apresenta pelo menos três limitações: só
lida com dados estáticos (i.e., os algoritmos não suportam actualizações e multiplas versões dos dados), requer que os servidores executem código (ao contrário do D EP S KY, que
considera as clouds de armazenamento como discos passivos) e não usa nenhum mecanismo para protecção da confidencialidade dos dados armazenados.
O sistema RACS (Redundant Array of Cloud Storage) [22] utiliza técnicas similares
às empregues nos sistemas RAID nível 5 [29] para concretizar replicação de dados em
diversas clouds.
Diferentemente do D EP S KY, o RACS não se preocupa com problemas de segurança,
mas sim com possíveis “falhas económicas”, onde uma cloud aumenta o seu custo de tal
Capítulo 3. D EP S KY
28
forma que torna inviável o acesso aos dados.
Além de não proteger contra corrupção de dados e violações de confidencialidade, o
RACS também não suporta actualizações dos dados armazenados. Todas estas limitações
tornam o RACS muito menos poderoso que o D EP S KY.
Além das diferenças entre os sistemas, os trabalhos sobre o HAIL e RACS não apresentam nenhum tipo de medida que utilize a diversidade de clouds.
O protocolo CADS e a sua concretização são baseados nas ferramentas desenvolvidas
para a concretização da camada de confidencialidade do DepSpace [11].
Este sistema utiliza um esquema de partilha de segredos publicamente verificável para
adicionar uma camada genérica de confidencialidade sobre sistemas replicados que seguem a abordagem de replicação por máquina de estados.
Apesar de utilizar a mesma biblioteca de partilha de segredos escrita em Java (JSS [7]),
os mecanismos e protocolos desenhados para o DepSpace não podem ser directamente
aplicados ao armazenamento em clouds uma vez que requerem execução de código nos
servidores na verificação dos dados, e assumem que as actualizações de unidades de dados
são sempre processadas na mesma ordem global no sistema.
3.7
Considerações Finais
Neste capítulo foi apresentado o D EP S KY, um novo sistema de armazenamento tolerante a intrusões, que promove uma melhoria da disponibilidade, integridade e confidencialidade dos dados armazenados em clouds. Tal como a maioria dos sistemas de
armazenamento, o D EP S KY suporta duas operações básicas, leitura e escrita, mas oferece
a possibilidade dos dados serem armazenados de acordo com um esquema de partilha de
segredos, garantindo a confidencialidade destes. No próximo capítulo são apresentados
os detalhes da concretização do sistema.
Capítulo 4
Concretização do D EP S KY
4.1
Considerações Gerais
O DepSky e todos os seus componentes foram concretizados na linguagem de programação Java. Em primeiro lugar foram concretizados alguns controladores, que são
responsáveis pela comunicação com os diferentes sistemas de armazenamento em clouds.
Cada controlador comunica com a respectiva cloud através dos seus serviços web
disponibilizados, utilizando uma interface ReSTful ou através de envelopes SOAP. Toda
a comunicação é efectuada sobre HTTPS (HyperText Tranfer Protocol secure).
Os controladores foram os componentes que mais tempo consumiram em termos de
desenvolvimento dada a variedade no funcionamento dos diferentes serviços web de
cada cloud. Foram concretizados controladores para os seguintes serviços: Amazon
Simple Storage Service, Microsoft Windows Azure Platform, Nirvanix Storage Delivery
Network, DivShare, DocStoc e Box.net.
Os controladores do Amazon S3 e do Windows Azure foram concretizados sobre bibliotecas Java, que contêm uma implementação completa dos serviços web, disponibilizadas pelos fornecedores. Estas bibliotecas foram usadas mas tiveram que ser ligeiramente
modificadas para suportarem proxies sem autenticação, porque a rede do DI-FCUL está
dependente de uma proxy deste tipo para acesso ao exterior (Internet).
Os restantes controladores foram concretizados recorrendo a classes da API do Java
como a URLConnection para as ligações, os parsers de XML para processar respostas
dos serviços web e uma variedade de módulos Java vocacionados para segurança, como
o JSSE (Java Secure Socket Extension) e o JCA (Java Cryptography Architecture), que
inclui o JCE (Java Cryptographic Extension).
Após a conclusão de um número suficiente de controladores, iniciou-se o desenvolvimento do componente responsável pelos protocolos (DepSky), e de outro responsável pela
verificação, validação e criação de metadados do sistema (DepSkyManager). Foi também
concretizado um wrapper para controladores que efectua a gestão dos retries e timeouts
dos pedidos HTTP, para garantir fiabilidade ponto-a-ponto (DepSkyCloudManager).
29
30
Capítulo 4. Concretização do D EP S KY
O componente DepSky fornece ao cliente o ponto de partida para a execução dos
protocolos, ADS e CADS. A sua interface disponibiliza as operações de leitura (read)
e escrita (write) para ambos. É ainda disponibilizada outra operação, denominada readOptimized, para inicializar o protocolo de leitura optimizada do ADS. É também neste
componente que está incluído o processo para partilha de segredos.
O DepSkyManager efectua a ponte entre o DepSky e os DepSkyCloudManager’s, gerindo os pedidos efectuados, processando as respostas obtidas e tratando as excepções lançadas internamente. Para além disso, este componente também é responsável por efectuar
verificações de integridade dos valores das unidades de dados assim como assinar novos
metadados ou verificar a assinatura de metadados recebidos.
Um DepSkyCloudManager encapsula um controlador numa thread e é o componente
responsável pela comunicação com a cloud que esse controlador representa. Este pode
ser configurado para permitir um determinado número de tentativas (retries), caso a primeira falhe. Outros parâmetros que podem ser configurados são os timeouts das ligações
HTTP1 .
Finalmente, utilizou-se a biblioteca JSS (Java Secret Sharing) [7] para concretizar a
partilha de segredos no sistema. Esta biblioteca concretiza um esquema de partilha de
segredos publicamente verificável proposto por Schoenmakers [31].
A tabela 4.1 apresenta o número de linhas de código necessário para concretizar cada
componente do D EP S KY.
Componente
Controlador Amazon S3
Controlador Azure
Controlador Nirvanix
Controlador DivShare
Controlador DocStoc
Controlador Box.net
Controlador FilesAnywhere
DepSky
DepSkyManager
DepSkyCloudManager
Linhas de Código
175
200
280
350
350
380
460
600
300
300
Tabela 4.1: Número de linhas de código necessárias para cada componente do sistema.
1
Em Java, existem dois timeouts na classe URLConnection que podem ser redefinidos, o connectTimeout, relativo ao tempo máximo de espera para que a conexão seja estabelecida, e o readTimeout, relativo ao
tempo máximo de espera até dados estarem disponíveis na socket, depois da ligação já estar estabelecida.
31
Capítulo 4. Concretização do D EP S KY
4.2
Arquitectura
A figura 4.1 mostra a forma como foi estruturado o sistema, desde o nível da interface
do utilizador até aos serviços de armazenamento em clouds, passando pelo DepSky.
Interface
Leitura
Escrita
Unidade
de Dados
A
Unidade
de Dados
B
...
Unidade
de Dados
<id>
Iniciar / Terminar
DepSky
Controlador
Cloud#1
Controlador
Cloud#2
HTTP (REST)
HTTP (SOAP)
...
Controlador
Cloud#n
Sistemas de armazenamento em clouds
Figura 4.1: Visão minimalista sobre a estrutura do DepSky.
Para simplicidade de os componentes descritos na secção anterior estão incluídos no
DepSky representado nesta figura.
A interface permite que o utilizador execute as operações disponibilizadas pelo sistema (leitura e escrita). Com a execução de qualquer operação é inicializado o DepSky,
mas apenas se ainda não estiver activo.
O DepSky está basicamente encarregue da "tradução" entre uma unidade de dados
e dois ficheiros que a representam em cada cloud. Isto significa que se, por exemplo,
exitirem 4 clouds para as quais são replicados os dados vão necessariamente existir um
total de 8 ficheiros que representam essa unidade de dados, 4 com metadados e outros
4 com o valor (ou uma parte deste no caso do CADS). Esta "tradução"é completamente
transparente para o cliente, que apenas precisa saber o identificador de uma unidade de
dados. Aliás, este identificador é o único parâmetro numa operação de leitura, e um dos
dois parâmetros numa operação de escrita (o outro parâmetro é o valor a escrever).
Capítulo 4. Concretização do D EP S KY
32
Este modelo foi adoptado para que, através da utilização de metadados, fosse mais
fácil efectuar o controlo de versão e verificar a autenticidade do valor da unidade de dados.
Esta separação entre dados e metadados também permitiu a concretização do ADS com
leituras optimizadas já que neste protocolo é pedido o valor da unidade a apenas uma
cloud (no melhor caso).
Os controladores, representados abaixo do DepSky, são os componentes responsáveis
pela comunicação com as clouds , como já foi referido.
Uma descrição mais detalhada é efectuada na próxima secção.
4.3
Diagramas UML
Nesta secção são apresentados alguns diagramas UML, como o diagrama de classes
do sistema, e os diagramas de sequência para as operações de escrita e leitura.
A figura 4.2 apresenta o diagrama de classes do D EP S KY. Através deste diagrama
conseguimos ter uma visão mais abrangente sobre como funciona o sistema.
Os componentes representados no diagrama passam mensagens e outra informação de
uns para os outros através de handlers. Estes handlers estão representados pelas interfaces
IDepSkyProtocol e ICloudDataManager. Por exemplo, sempre que um DepSkyCloudManager recebe um ficheiro de metadados, invoca o método processMetadata do DepSkyManager para verificação de assinatura e saber se se trata de uma unidade de dados com
partilha de segredos, ou seja, se foi escrita através do ADS ou CADS. Já a outra interface,
a IDepSkyDriver, representa todas as operações que um controlador deve implementar
para ser compatível com o D EP S KY. Todos os controladores concretizados implementam
os métodos desta interface.
A classe DepSkyDataUnit representa uma unidade de dados. É um objecto desta
classe que é passado como argumento às operações definidas. Para além de representar
uma unidade de dados do D EP S KY um objecto deste tipo também tem outras funcionalidades, como manter uma cache com as versões e valores lidos anteriormente ou indicar,
numa operação de escrita, se queremos utilizar o ADS ou o CADS, através de um parâmetro booleano (useSS).
As classes CloudRequest e CloudReply são subclasses da classe CloudMessage, que
representa um pedido ou resposta de uma cloud. Embora a interface seja comum foi necessário fazer a separação entre pedidos e respostas essencialmente para fazer debugging
ao sistema e perceber a direcção das mensagens, se estavam a chegar ou a sair.
Por fim, também é representada a excepção genérica lançada pelos DepSkyCloudManager’s sempre que houve um problema de comunicação com uma cloud. Estas excepções
são tratadas ao nível do DepSkyManager, no entanto convém relembrar que o sistema foi
concebido para tolerar apenas f faltas. Se acontecerem mais de f faltas os protocolos
lançam uma excepção para a camada superior.
Figura 4.2: Diagrama de classes do sistema.
1..*
1
DepSkyManager
*
«exception»
StorageCloudException
in message : String
+id : String
+version : Long
+useSS : Boolean
+getContainerName() : String
+getMetadataFinename() : String
+getValuedataFilename(in version : Long) : String
DepSkyCloudManager
+sequence : Long
+protoOp : Integer
+sid : String
+cid : String
+did : String
+dataunit : DepSkyDataUnit
+cloudOp : Integer
+value : Object
-isMetadata : Boolean
-version : Long
-valueHash : String
DepSkyDriver
1
1
+requests : CloudRequest
+replies : CloudReply
+processRequest()
+processReply()
CloudRequest
CloudMessage
CloudReply
+doRequest(in cloudId : String, in request : CloudRequest)
DepSkyDataUnit
0..*
1
1
«interface»
ICloudDataManager
+processMetadata(in mdreply : CloudReply)
+checkDataIntegrity(in vreply : CloudReply)
+writeNewMetadata(in vreply : CloudReply)
Esta classe representa uma unidade de dados
do DepSky e também serve como cache
para metadados e valor da última versão lida
dessa unidade de dados.
«utility»
DepSkyLogger
0..1
1
DepSky
«interface»
IDepSkyProtocol
+read(in dataunit : DepSkyDataUnit) : Object
+readOptimized(in dataunit : DepSkyDataUnit) : Object
+write(in dataunit : DepSkyDataUnit)
+dataReceived(in reply : CloudReply)
DivShareDriver
AmazonS3Driver
FilesAnywhereDriver
WindowsAzureDriver
Conjunto de controladores concretizados.
São responsáveis pelos pedidos e respostas HTTP
do serviço que representam.
DocStocDriver
NirvanixDriver
BoxNetDriver
RackSpaceDriver
«interface»
IDepSkyDriver
+initSession(in properties : Object) : String
+createContainer(in sid : String, in cid : String) : String
+deleteContainer(in sid : String, in cid : String) : Boolean
+uploadData(in sid : String, in cid : String, in did : String, in data : Object) : String
+downloadData(in sid : String, in cid : String, in did : String) : Object
+deleteData(in sid : String, in cid : String, in did : String) : Boolean
+endSession(in sid : String) : Boolean
+getSessionKey() : String
+getDriverCloudID() : String
+getContainerAndDataIDsByName(in sid : String, in cname : String, in dname : String) : Object
Esta classe para além de gerir pedidos
e respostas também efectua a gestão
dos retries e timeouts das ligações HTTP.
Capítulo 4. Concretização do D EP S KY
33
34
Capítulo 4. Concretização do D EP S KY
Visual Paradigm for UML Community Edition [not for commercial use]
Client
DepSky
DepSky Manager
1: init()
2: new (regid)
DepSkyDataUnit :
du
loop
[du.cloudVersion.size() < N - F]
3: write (du,data2write)
3.1: new (GET_DATA,du)
CloudRequest : req
3.2: doRequest(req)
3.2.2: dataReceived(rep)
3.2.1: new (du,METADATA)
CloudReply
: rep
3.3: processMetadata(rep)
3.4: lastMetadata.add(rep)
3.5: cloudVersion.put(rep.cloudId,rep.version)
3.5: newVersion = du.getMaxVersion() + 1
loop
[lastValuedata.size() < N - F]
3.6: new (NEW_DATA,du,data2write)
3.7: doRequest(req)
3.7.1: new (du,NEW_DATA_OK)
3.7.2: dataReceived(rep)
3.8: writeNewMetadata(rep)
3.8.1: new (du,NEW_DATA_OK)
3.8.2: lastValuedata.add(rep)
4: write completed
Figura 4.3: Diagrama de sequência simplificado de uma operação de escrita.
As figuras 4.3 e 4.4 ilustram os fluxos de informação e como são criados os objectos no
D EP S KY, através de diagramas de sequência UML para as operações de escrita e leitura.
Os diagramas estão simplificados pois todos os DepSkyCloudManager’s foram incluídos
no DepSkyManager. Basicamente foi abstraída a comunicação com a cloud nos passos
em que são criados novos objectos do tipo CloudReply. Se ocorrerem excepções durante
esta comunicação, só depois de esgotados os retries de um DepSkyCloudManager, é que
um CloudReply é criado e inicializado com um valor nulo. Nos diagramas estas excepções
também não estão representadas. De referir que cada DepSkyCloudManager cria um novo
objecto CloudReply sempre que recebe uma resposta do controlador, para depois o passar
ao DepSkyManager.
Operação write
Numa operação de escrita o cliente começa por criar um objecto do tipo DepSkyDataUnit passando como argumento o identificador, que tem de ser único. Este objecto é
depois passado como argumento da operação write juntamente com os dados que o cliente
quer escrever na unidade de dados.
Após este passo, o DepSky cria um objecto do tipo CloudRequest para obter os meta-
Capítulo 4. Concretização do D EP S KY
35
dados da unidade de dados indicada e passa-o ao DepSkyManager. Este gestor é responsável por multiplicar este pedido pelos DepSkyCloudManager’s que por sua vez o passam
aos controladores para o encaminhar para a cloud correspondente. Este último passo é
efectuado em todos os controladores ao mesmo tempo, ou seja, os pedidos são enviados
paralelamente a todas as clouds do sistema. Assim que os metadados são recebidos são
reencaminhados para o DepSkyManager que verifica a assinatura dos metadados e, se esta
for válida, guardar a informação contida nestes (i.e., versão ) porque será necessária nos
passos seguintes.
O DepSky aguarda a recepção de n − f metadados antes de prosseguir. Como já foi
referido, obter os metadados é essencial para que o sistema calcule o valor da próxima
versão. Assim que são obtidos, o DepSky cria um CloudRequest, mas desta vez para
escrever uma nova versão do valor. Este pedido é encaminhado para o DepSkyManager
que repete o processo com os DepSkyCloudManager’s já descrito anteriormente (pedidos
efectuados paralelamente a todas as clouds). O novo número de versão é lido do objecto
DepSkyDataUnit, que possui em cache o número de versão existente em cada cloud,
obtido dos metadados.
Após a recepção da confirmação de escrita do novo valor em n − f clouds dá-se
início à actualização dos metadados nas clouds. Para este efeito, é criado outro objecto do
tipo CloudRequest com o novo ficheiro de metadados. O novo ficheiro é construído pelo
DepSkyManager e contém o novo número de versão, um resumo criptográfico do novo
valor e o nome do ficheiro com a nova versão.
A operação write termina quando são recebidas n − f confirmações da actualização
dos metadados.
Operação read
Numa operação de leitura o cliente começa por criar um objecto do tipo DepSkyDataUnit, passando como argumento o identificador único, que por sua vez é passado como
argumento da operação read.
Após este passo, o DepSky cria um objecto do tipo CloudRequest para obter os metadados da unidade de dados, exactamente como na operação write, com a diferença que
numa operação read é guardada temporariamente toda a informação contida nos metadados (i.e., versão, nome do ficheiro com o valor e resumo criptográfico do valor) pois
serão necessárias nos passos seguintes (na operação write apenas é relevante o número de
versão).
O DepSky aguarda a recepção de n − f metadados antes de prosseguir2 . Assim que
são obtidos os metadados, o DepSky cria um CloudRequest com o nome do ficheiro com
2
No protótipo, uma pequena optimização efectuada, é não aguardar os n − f metadados para pedir o
valor e pedi-lo assim que os metadados sejam validados. Obviamente que o protocolo só prossegue após a
recepção de n − f metadados válidos
36
Capítulo 4. Concretização do D EP S KY
Visual Paradigm for UML Community Edition [not for commercial use]
Client
DepSky
DepSky Manager
1: init()
2: new (regid)
DepSkyDataUnit :
du
loop
[hasMoreDrivers = true & du.cloudVersion.size() < N - F & lastValuedata.size() < F]
3: read (du)
3.1: new (GET_DATA,du)
CloudRequest : req
3.2: doRequest(req)
3.2.1: new (du,METADATA)
3.2.2: dataReceived(rep)
CloudReply
: rep
3.3: processMetadata(rep)
3.4: lastMetadata.add(rep)
3.5: cloudVersion.put(rep.cloudId,rep.version)
3.5: maxVersion = du.getMaxVersion()
3.6: new (GET_DATA,du,rep.valueId)
3.7: doRequest(req)
3.7.1: new (du,VALUE)
3.7.2: [rep.version = maxVersion] lastValuedata.add(rep)
4: lastValuedata.get(0).response
Figura 4.4: Diagrama de sequência simplificado de uma operação de leitura.
o valor obtido dos metadados referentes à versão mais recente. Este pedido é passado ao
DepSkyManager que o multiplica pelos DepSkyCloudManager’s, sendo depois efectuado
em paralelo às clouds. Cada DepSkyCloudManager cria um objecto do tipoCloudReply e
passa-o ao DepSkyManager com o valor recebido da cloud. O DepSkyManager quando
recebe este objecto faz a verificação de integridade, e só se os dados não tiverem sido
modificados é que entrega ao DepSky
A operação termina quando é entregue no DepSky um CloudReply que reporte um
valor íntegro e referente à versão mais actual da unidade de dados.
4.4
Controladores
Foi definido que os controladores deviam fazer apenas as operações necessárias para
o correcto funcionamento do D EP S KY. As funções básicas de um controlador são ler
e escrever dados na cloud, no entanto para o D EP S KY foram definidas mais algumas
operações (listadas na interface IDepSkyDriver do diagrama de classes 4.2), entre elas a
possibilidade de criar containers.
Para concretizar o controlador de uma cloud de armazenamento, é necessário o estudo
da API dos serviços web disponibilizados. Devem ser analisadas as funcionalidades necessárias (e.g., uploadFile, createBucket) e concretizá-las seguindo a sua especificação.
Esta especificação indica como devem ser construídos os pedidos HTTP a enviar ao serviço web, podendo ser necessários cabeçalhos adicionais (e.g., para autenticação), ou que
Capítulo 4. Concretização do D EP S KY
37
o corpo HTTP do pedido esteja estruturado numa determinada forma.
Embora a maioria das clouds pay-per-use disponibilizem serviços ReST e SOAP, todos os controladores para este tipo de clouds foram implementados usando os serviços
ReSTfull. A maioria das clouds de custo fixo apenas disponibiliza API para uma das
abordagens, normalmente ReST. Contudo o FilesAnywhere apenas disponibiliza serviços web através de SOAP. Comparando as duas abordagens, ReST e SOAP, o nível de
complexidade de programação experienciado é semelhante, não havendo mais ou menos
dificuldade de concretização.
4.5
Considerações Finais
Neste capítulo foram descritos os detalhes da concepção do D EP S KY, como a sua arquitectura e como o sistema funciona na prática, ou seja, como efectua a "tradução"entre
um unidade de dados D EP S KY e os dados armazenados nas clouds. Foram também apresentados detalhes da implementação do sistema, o diagrama de classes e diagramas de
sequência para as operações de leitura e escrita. Os controladores do D EP S KY e a abordagem tomada na concretização destes também foi descrita. Uma avaliação ao desempenho
do sistema, e das clouds individualmente, é efectuada no próximo capítulo.
Capítulo 4. Concretização do D EP S KY
38
Capítulo 5
Avaliação Experimental do D EP S KY
Neste capítulo apresenta-se uma avaliação do DepSky que tenta responder a três perguntas:
• Qual o custo adicional em se utilizar replicação de clouds de armazenamento?
• Qual o ganho de desempenho e de disponibilidade em se usar clouds replicadas
para armazenar dados?
• Qual o custo relativo das diferentes versões (ADS, ADS com leitura optimizada e
CADS) do D EP S KY?
5.1
Custo do Armazenamento Replicado
As clouds de armazenamento usualmente cobram pela quantidade de dados que entram, saem e ficam armazenados nos seus data centers.
A tabela 5.11 mostra os gastos com leituras e escritas nas clouds, para diferentes tamanhos de blocos de dados.
A tabela 5.2 vem no seguimento da tabela 5.1 e, adicionalmente, apresenta os custos
da utilização do modelo de unidade de dados descrito neste artigo pelos protocolos do
D EP S KY nas mesmas condições. É de salientar o baixo custo da utilização da leitura
optimizada quando comparada com a normal.
Ambas as tabelas mostram o custo, em USD, de se realizar 10.000 operações de leitura
e escrita para diferentes tamanhos de blocos de dados.
É necessário relembrar que os protocolos de leitura do DepSky efectuam 2 pedidos
de leitura a cada cloud, e também, que os protocolos de escrita efectuam um pedido de
leitura e 2 pedidos de escrita a cada cloud.
A coluna “D EP S KY” apresenta os custos do uso dos protocolos ADS e CADS propostos. É importante referir que o uso de confidencialidade (protocolo CADS) não apresenta
1
Nesta tabela são paresentados os custos do RackSpace ao invés do Divshare (usado nas experiências
de latência) devido ao facto do primeiro cobrar por uso, enquanto o segundo oferece apenas pacotes fixos.
39
40
Capítulo 5. Avaliação Experimental do D EP S KY
Operação
10k Leituras
10k Escritas
Tamanho
100 kb
1 Mb
10 Mb
100 kb
1 Mb
10 Mb
Amazon S3 (EU)
0,11
1,01
10,01
0,20
1,10
10,10
RackSpace
0,22
2,20
22,0
0,28
0,80
8,00
Windows Azure
0,16
1,51
15,01
0,11
1,01
10,01
Nirvanix
0,18
1,80
18,0
0,18
1,80
18,0
Tabela 5.1: Custo estimado, em USD, de 10.000 operações de leitura e escrita de dados
com 100KB, 1MB e 10MB nas clouds.
Operação
10k Leituras
10k Escritas
Tamanho
100 kb
1 Mb
10 Mb
100 kb
1 Mb
10 Mb
D EP S KY
0,69
6,54
65,04
1,10
4,84
46,24
D EP S KY opt. (melhor caso)
entre 0,12 e 0,22
entre 1,02 e 2,20
entre 10,02 e 22,0
1,10
4,84
46,24
Tabela 5.2: Custo estimado, em USD, de 10.000 operações de leitura e escrita de dados
com 100KB, 1MB e 10MB usando os protocolos do D EP S KY.
acréscimo representativo de custo, em termos de armazenamento, uma vez que os seus
metadados ocupam, em média, 500 bytes enquanto os metadados para unidades de dados
sem confidencialidade ocupam cerca de metade desse valor.
A coluna “D EP S KY opt. (melhor caso)” apresenta os custos quando a optimização
de leitura para o protocolo ADS é utilizada. O custo varia porque a cloud mais rápida a
responder aos pedidos de metadados não é sempre a mesma, logo estão representados os
custos mínimo (Amazon S3) e o máximo (RackSpace) para cada tamanho de dados.
Custo de leitura. Este custo corresponde apenas ao custo de se ler os metadados da
unidade de dados e os dados propriamente ditos. O custo de leitura do D EP S KY é similar
a soma dos custos de leitura em cada uma das quatro clouds individualmente, enquanto
que na versão optimizada o custo é bastante reduzido, já que só é pedido o valor a uma
das clouds. No entanto, há que considerar um acréscimo de poucos cêntimos devido aos
pedidos de metadados a todas as clouds.
Custo de escrita. O custo da escrita considera o custo de se ler os metadados, escrever
uma nova versão destes e escrever a nova versão dos dados. Além disso, neste custo
estão incluídos os custos de armazenamento dos dados, o que significa que se considera
um sistema onde nenhuma versão de uma unidade de dados será apagada (i.e., escritas
apenas criam novas versões). Como já foi referido, esta funcionalidade é importante para
dados critícos na medida que permite recuperar versões anteriores das unidades de dados
Capítulo 5. Avaliação Experimental do D EP S KY
41
armazenadas. Entretanto, na prática esse custo pode ser amortizado eliminando versões
antigas dos valores das unidades de dados.
Os resultados das tabelas 5.1 e 5.2 mostram que o custo apresentado para as versões
do D EP S KY correspondem a soma dos custos de escrita nas clouds. Estes custos, assim
como na leitura não-optimizada, advém do modelo de replicação utilizado onde o bloco
de dados é replicado em todas as clouds.
Se tivessem sido aplicadas técnicas similares ao RAID nível 5 [29], estes custos diminuiriam aproximadamente para metade, já que os dados armazenados em cada cloud
teriam um tamanho menor.
5.2
Desempenho e Disponibilidade
O D EP S KY foi desenhado tendo em conta um modelo em que as leituras são muito
mais frequentes que as escritas, como é observado em praticamente todos os sistemas de
armazenamento [16]. Por isso, a avaliação efectuada concentra-se na latência das operações de leitura em diferentes configurações. No entanto, são reportados também alguns
valores de latência do protocolo de escrita no fim desta secção para fins de completude do
estudo.
5.2.1
Metodologia
As medidas de latência de leitura foram obtidas através de uma aplicação que acede
os dados de 7 formas diferentes (configurações): às 4 clouds de armazenamento individualmente sem utilização do D EP S KY (Amazon S3, Windows Azure, Nirvanix e Divshare)
e às 3 versões do protocolo de leitura do D EP S KY (ADS, ADS com leituras optimizadas e CADS). Todas as versões do D EP S KY usam as quatro clouds mencionadas para
armazenar dados, e portanto toleram uma falha.
Foram medidos tempos de leitura para unidades de dados de três tamanhos: 100K,
1M e 10M bytes. A aplicação executou todas estas leituras periodicamente - de um em
um minuto (10K e 1M) ou de cinco em cinco minutos (10M) - e armazenou os tempos
obtidos em ficheiros de log.
O objectivo foi ler os dados através das diferentes configurações dentro de um intervalo de tempo o mais curto possível tentando minimizar as variações no desempenho da
Internet.
As experiências aqui reportadas foram efectuadas entre 31 de Maio e 13 de Junho
de 2010, com o cliente a executar numa máquina do Departamento de Informática da
FCUL e a aceder às quatro clouds de armazenamento. Foram efectuadas 99414 medidas
de latência, isto é, 14202 medidas por cada uma das 7 configurações.
42
1
1
0.9
0.9
0.8
0.8
0.7
0.6
0.5
0.4
0.3
0.2
Legenda
Divshare
Nirvanix
Azure
Amazon S3
0.1
0
Função de Distribuição Cumulativa
Função de Distribuição Cumulativa
Capítulo 5. Avaliação Experimental do D EP S KY
0.7
0.6
0.5
0.4
0.3
0.2
Legenda
DS−ReadO
DS−Read
DS−ReadSS
Amazon S3
0.1
0
0
1000
2000
3000
4000 5000 6000 7000
Latência (milisegundos)
8000
(a) Clouds.
9000 10000
0
1000
2000
3000
4000
Latência (milisegundos)
5000
6000
(b) D EP S KY.
Figura 5.1: FDC para as latências de leitura de dados com 100K bytes observadas em quatro diferentes clouds (Amazon S3, Windows Azure, Nirvanix e DivShare) e nas três versões do D EP S KY
replicando dados por essas clouds.
5.2.2
Latência de Leitura
As figuras 5.1, 5.2 e 5.3 apresentam a FDC (função de distribução cumulativa) das
latências medidas na leitura dos diversos tamanhos dos dados nas diversas clouds individualmente e utilizando as diferentes versões do D EP S KY.
São apresentados resultados relativos ao acesso às clouds individualmente, e utilizando diferentes versões do D EP S KY (com os resultados da Amazon S3, para fins de
comparação).
Através da figura 5.1(a) observa-se que as distribuições de latência para todas as configurações são bastante semelhantes com destaque para a Azure que demonstra ser mais
lenta. Já a figura 5.1(b) mostra que com este tamanho o desempenho dos protocolos de
leitura do D EP S KY é bastante semelhante ao da Amazon S3. Mais especificamente, o
ADS e o ADS com leituras optimizadas obtiveram melhor tempo de resposta em relação
à Amazon S3 em cerca de 70% das medidas.
Nas experiências com unidades de dados de 1M já se pode observar alguma discrepância entre os desempenhos da Amazon S3 e da Nirvanix (figura 5.2(a)). Na verdade a
Nirvanix obteve um desempenho pelo menos duas vezes melhor que as restantes clouds.
Além disso, com este tamanho já se commeça a notar a diferença entre usar replicação
de dados em clouds e apenas uma cloud: 90% das leituras optimizadas com o D EP S KY
estão abaixo de 3,2 segundos, enquanto com a Amazon S3 este valor aproxima-se de 8
segundos (o pior resultado de 90% das medidas).
Através da comparação das figuras 5.2(a) e 5.2(b) pode afirmar-se que o bom desempenho dos protocolos do D EP S KY está directamente relacionado com o desempenho da
Nirvanix no intervalo em que foram efectuadas as medições.
As experiências com unidades de dados de 10M já demonstram as dificuldades em
lidar com o armazenamento de dados na Internet.
43
1
1
0.9
0.9
0.8
0.8
Função de Distribuição Cumulativa
Função de Distribuição Cumulativa
Capítulo 5. Avaliação Experimental do D EP S KY
0.7
0.6
0.5
0.4
0.3
0.2
Legenda
Divshare
Nirvanix
Azure
Amazon S3
0.1
0.7
0.6
0.5
0.4
0.3
0.2
Legenda
DS−ReadO
DS−Read
DS−ReadSS
Amazon S3
0.1
0
0
0
1000
2000
3000
4000
5000
6000
Latência (milisegundos)
7000
8000
9000
0
1000
(a) Clouds.
2000
3000
4000
5000
6000
Latência (milisegundos)
7000
8000
9000
(b) D EP S KY.
Figura 5.2: FDC para as latências de leitura de dados com 1M bytes observadas em quatro dife-
1
1
0.9
0.9
0.8
0.8
Função de Distribuição Cumulativa
Função de Distribuição Cumulativa
rentes clouds (Amazon S3, Windows Azure, Nirvanix e DivShare) e nas três versões do D EP S KY
replicando dados por essas clouds.
0.7
0.6
0.5
0.4
0.3
0.2
Legenda
Divshare
Nirvanix
Azure
Amazon S3
0.1
0.7
0.6
0.5
0.4
0.3
0.2
Legenda
DS−ReadO
DS−Read
DS−ReadSS
Amazon S3
0.1
0
0
0
5000
10000
15000
20000
25000
Latência (milisegundos)
(a) Clouds.
30000
35000
40000
0
5000
10000
15000
20000
25000
Latência (milisegundos)
30000
35000
40000
(b) D EP S KY.
Figura 5.3: FDC para as latências de leitura de dados com 10M bytes observadas em quatro diferentes clouds (Amazon S3, Windows Azure, Nirvanix e DivShare) e nas três versões do D EP S KY
replicando dados por essas clouds.
Na figura 5.3(a) observa-se uma larga discrepância entre os resultados observados
para a Nirvanix e a Divshare quando comparados com os resultados da Azure e da S3.
Também se manteve a tendência verificada nos dados de 1M, a Nivanix continua a mostar
ser o serviço com melhor tempo de resposta. Em particular, no decorrer destas medidas
observou-se um acentuado período de indisponibilidade da Azure (ver tabela 5.3), o que
é representado no gráfico pelos cerca de 20% de resultados que não estão na figura.
No que diz respeito às diversas versões do D EP S KY, a figura 5.3(b) mostra que neste
caso a replicação dos dados em diversas clouds diminui de forma significativa a latência
de leitura dos dados, mesmo na versão optimizada em que não se tenta ler de várias clouds
mas apenas da que retornou os metadados mais rapidamente.
De notar também que o uso da primitiva de partilha de segredos para confidencialidade
44
Capítulo 5. Avaliação Experimental do D EP S KY
(protocolo CADS), torna o D EP S KY muito menos eficiente já que se têm de obter os dados
de duas clouds diferentes, ao invés de apenas de uma (como acontece no ADS e no ADS
com leitura optimizada).
Falhas
Durante as experiências foram observadas várias falhas no acesso aos sistemas de
armazenamento, conforme reportado na tabela 5.3.
Dados (bytes)
100K
1M
10M
Todas falharam
1
1
0
Amazon S3
0
9
0
Azure
0
13
10+10hs
Nirvanix
1
2
7
Tabela 5.3: Número de falhas observadas durante as experiências de leitura. O “10+10hs”
para a Azure na experiência de 10M significa que para além das 10 falhas reportadas
houve um período de 10 horas onde mais de 95% dos acessos individuais a este sistema
falharam.
Durante as experiências observou-se um período de instabilidade e indisponibilidade
na cloud Azure entre as 11 e as 21 horas do dia 10 de Junho. Neste período mais de 95%
das leituras dos dados falharam com a mensagem de erro “Unable to read complete data
from server”.
Para além deste evento, o número de operações mal sucedidas é bastante pequeno se
tivermos em conta a quantidade total de operações executadas (14202 em cada cloud). É
de salientar que o D EP S KY falhou apenas duas vezes, quando todas as clouds estavam
indisponíveis. Estas falhas aconteceram possivelmente devido a problemas de conectividade na saída da rede do DI/FCUL.
5.2.3
Latência de Escrita
Para fins de completude da avaliação são reportados na tabela 5.4 os tempos médios
de escrita em diferentes configurações (obtidos a partir de um conjunto de 100 escritas
para cada tamanho de unidade de dados, executadas no dia 14 de Junho).
Dados
100K
1M
10M
D EP S KY-ADS
1767
4376
20315
D EP S KY-CADS
2790
4928
24012
Amazon S3
2336
5640
32204
DivShare
3287
4684
8298
Azure
2801
3823
20017
Nirvanix
2802
2626
4816
Tabela 5.4: Latência média (ms) de escrita para diferentes tamanhos de unidades de dados,
configurações do D EP S KY e clouds de armazenamento.
Estes resultados mostram que algumas clouds (Divshare e Nirvanix) apresentam pouco
aumento de latência quando passamos a escrever altos volumes de dados, enquanto outras
Capítulo 5. Avaliação Experimental do D EP S KY
45
(Azure e S3), apresentam uma perda de desempenho proporcional ao tamanho dos dados
sendo escritos. O desempenho das versões do D EP S KY é similar a estas versões mais
lentas na medida que os protocolos de escrita requerem a confirmação de escrita em 3 das
4 clouds utilizadas.
5.3
Considerações Finais
Neste capítulo foi efectuada uma avaliação experimental aos protocolos concretizados
no D EP S KY (ADS e CADS) assim como uma análise crítica aos resultados verificados.
Mais especificamente, foram avaliados os custos e medida a latência, para operações de
leitura e escrita, em 4 clouds e através da utilização do D EP S KY.
Para finalizar este relatório, no próximo capítulo são apresentadas as conclusões e o
trabalho futuro.
Capítulo 5. Avaliação Experimental do D EP S KY
46
Capítulo 6
Conclusões e Trabalho Futuro
6.1
Conclusões
Construir sistemas de armazenamento de maneira distribuída é muito atractivo, porque
a disponibilidade da informação pode ser aumentada significativamente.
Algoritmos de armazenamento distribuído podem ser optimizados para fornecerem
um nível elevado de coerência, disponibilidade e resiliência, enquanto ao mesmo tempo
induzem um overhead muito pequeno em comparação com uma solução centralizada e
falível. Não é de surpreender que através da combinação de propriedades de armazenamento desejáveis incorrem diferentes tradeoffs.
No entanto, vale a pena mencionar que, na prática, sistemas de armazenamento distribuído enfrentam outros desafios, como sobrevivência, interoperabilidade, escalabilidade
e balanceamento de carga.
Neste trabalho foi apresentado o D EP S KY, um sistema que garante disponibilidade,
integridade e confidencialidade de informação armazenada na cloud. Com estas garantias
pode-se definir o D EP S KY como um sistema confiável e seguro. Para garantir a disponibilidade do sistema a informação é replicada por várias clouds. A confidencialidade da
informação é garantida nas clouds, através da utilização de um esquema de partilha de
segredos, que permite a divisão da informação pelas clouds de maneira a que nenhuma
delas possua a informação na íntegra, e ponto-a-ponto na Internet, através da utilização
de HTTPS.
Na avaliação de resultados mostrou-se que o D EP S KY não fica muito aquém, em termos de desempenho, dos serviços testados. Pode-se afirmar que com o D EP S KY temos
sempre o melhor serviço independentemente das condições que cada cloud de armazenamento experiencia individualmente.
Além disso, os resultados demonstram a viabilidade económica (especialmente para
cargas de trabalho com bastantes mais leituras que escritas) e os benefícios em termos de
desempenho e disponibilidade do sistema.
47
Capítulo 6. Conclusões e Trabalho Futuro
6.2
48
Trabalho Futuro
O trabalho futuro deverá passar pela inclusão de códigos de apagamento no sistema.
O propósito será diminuir o tamanho dos blocos armazenados (de forma similar ao RAID
[29] e permitir uma avaliação da disponibilidade e desempenho do D EP S KY a partir de
diferentes locais no mundo. Esta avaliação também deverá ser realizada usando diferentes configurações de clouds, desenvolvendo-se novos controladores (para serviços não
contemplados neste trabalho) se tal for necessário.
Referências
[1] Amazon Simple Storage Service (https://s3.amazonaws.com), June 2010.
[2] Box.net (http://www.box.net), June 2010.
[3] DivShare (http://www.divshare.com), June 2010.
[4] DocStoc (http://www.docstoc.com), June 2010.
[5] FilesAnywhere (http://www.filesanywhere.com), June 2010.
[6] Inforum2010 (http://inforum.org.pt/INForum2010), September 2010.
[7] Java
Secret
Sharing
(http://www.navigators.di.fc.ul.pt/
software/jitt/jss.html), June 2010.
[8] Microsoft Windows Azure Platform (http://www.windowsazure.com),
June 2010.
[9] Nirvanix Storage Delivery Network (http://www.nirvanix.com), June
2010.
[10] RackSpace CloudFiles (http://www.rackspace.com), June 2010.
[11] Alysson Neves Bessani, Eduardo Pelison Alchieri, Miguel Correia, and Joni Silva
Fraga. Depspace: a byzantine fault-tolerant coordination service. In Eurosys ’08:
Proceedings of the 3rd ACM SIGOPS/EuroSys European Conference on Computer
Systems 2008, pages 163–176, New York, NY, USA, 2008. ACM.
[12] Alysson Neves Bessani, Miguel Correia, and Paulo Sousa. Active quorum systems:
Specification and correction proof. Technical report, Department of Informatics,
Faculty of Sciences, University of Lisbon, December 2008.
[13] Kevin D. Bowers, Ari Juels, and Alina Oprea. HAIL: a high-availability and integrity layer for cloud storage. In CCS ’09: Proceedings of the 16th ACM conference
on Computer and communications security, pages 187–198, New York, NY, USA,
2009. ACM.
49
Referências
50
[14] Christian Cachin and Stefano Tessaro. Asynchronous verifiable information dispersal. In DISC, pages 503–504, 2005.
[15] Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance and proactive recovery. ACM Transactions on Computer Systems (TOCS), 20(4):398–461,
November 2002.
[16] Gregory Chockler, Rachid Guerraoui, Idit Keidar, and Marko Vukolić. Reliable
Distributed Storage. Computer, 42(4):60–67, 2009.
[17] Miguel Correia. Serviços distribuídos tolerantes a intrusões: resultados recentes
e problemas abertos. In V Simpósio Brasileiro em Segurança da Informação e de
Sistemas Computacionais - Livro Texto dos Minicursos, pages 113–162. Sociedade
Brasileira de Computação, September 2005.
[18] Miguel Correia, Nuno Ferreira Neves, Lau Cheuk Lung, and Paulo Veríssimo. Low
complexity byzantine-resilient consensus. Distributed Computing, 17(3):237–249,
2005.
[19] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of
distributed consensus with one faulty process. In PODS ’83: Proceedings of the 2nd
ACM SIGACT-SIGMOD symposium on Principles of database systems, pages 1–7,
New York, NY, USA, 1983. ACM.
[20] J. Fraga and D. Powell. A fault- and intrusion-tolerant file system. In In Proceedings
of the 3rd International Conference on Computer Security, pages 203–218, 1985.
[21] David K. Gifford. Weighted voting for replicated data. In SOSP, pages 150–162,
1979.
[22] L. Princehouse H. Abu-Libdeh and H. Weatherspoon. RACS: A case for cloud
storage diversity. ACM Symposium on Cloud Computing (SOCC), June 2010.
[23] Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming
Languages and Systems (TOPLAS), 13(1):124–149, 1991.
[24] Hugo Krawczyk. Distributed fingerprints and secure information dispersal. In
PODC ’93: Proceedings of the twelfth annual ACM symposium on Principles of
distributed computing, pages 207–218, New York, NY, USA, 1993. ACM.
[25] Leslie Lamport. Time, clocks, and the ordering of events in a distributed system.
Commun. ACM, 21(7):558–565, 1978.
[26] Leslie Lamport. On Interprocess Communication. Part I: Basic Formalism. Distributed Computing, 1(2):77–85, 1986.
Referências
51
[27] Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine Generals Problem. ACM Trans. Program. Lang. Syst., 4(3):382–401, 1982.
[28] Dahlia Malkhi and Michael Reiter. Byzantine Quorum Systems. Distributed Computing, 11(4):203–213, October 1998.
[29] David A. Patterson, Garth Gibson, and Randy H. Katz. A case for redundant arrays
of inexpensive disks (RAID). In SIGMOD ’88: Proceedings of the 1988 ACM SIGMOD international conference on Management of data, pages 109–116, New York,
NY, USA, 1988. ACM.
[30] Bruno Quaresma, Alysson Bessani, and Paulo Sousa. Melhorando a Disponibilidade
e Confidencialidade dos Dados Armazenados em Clouds. In 2a edição do INForum
- Segurança de Sistemas de Computadores e Comunicações, 2010.
[31] Berry Schoenmakers. A simple publicly verifiable secret sharing scheme and its
application to electronic. In CRYPTO ’99: Proceedings of the 19th Annual International Cryptology Conference on Advances in Cryptology, pages 148–164, London,
UK, 1999. Springer-Verlag.
[32] Adi Shamir. How to Share a Secret. Commun. ACM, 22(11):612–613, 1979.
[33] P. E. Veríssimo, N. F. Neves, and M. P. Correia. Intrusion-tolerant architectures:
Concepts and design. In R. Lemos, C. Gacek, and A. Romanovsky, editors, Architecting Dependable Systems, volume 2677. 2003.