
André Francisco Morielo Caetano

Griddler: uma estratégia configurável para armazenamento
distribuı́do de objetos peer-to-peer que combina replicação e

erasure coding com sistema de cache

São José do Rio Preto
2017


André Francisco Morielo Caetano

Griddler: uma estratégia configurável para armazenamento
distribuı́do de objetos peer-to-peer que combina replicação e

erasure coding com sistema de cache

Dissertação apresentada como parte dos
requisitos para a obtenção do tı́tulo de Mes-
tre em Ciência da Computação, junto ao
Programa de Pós-Graduação em Ciência
da Computação – Área de Concentração
em Computação Aplicada, do Instituto de
Biociências, Letras e Ciências Exatas da
Universidade Estadual Paulista “Júlio de
Mesquita Filho”, Câmpus de São José do
Rio Preto.

Financiadora: CAPES/DS

Orientador: Prof. Dr. Carlos Roberto
Valêncio

São José do Rio Preto
2017


André Francisco Morielo Caetano

Griddler: uma estratégia configurável para armazenamento
distribuı́do de objetos peer-to-peer que combina replicação e

erasure coding com sistema de cache

Dissertação apresentada como parte dos
requisitos para a obtenção do tı́tulo de Mes-
tre em Ciência da Computação, junto ao
Programa de Pós-Graduação em Ciência
da Computação – Área de Concentração
em Computação Aplicada, do Instituto de
Biociências, Letras e Ciências Exatas da
Universidade Estadual Paulista “Júlio de
Mesquita Filho”, Câmpus de São José do
Rio Preto.

Financiadora: CAPES/DS

Comissão Examinadora

Prof. Dr. Carlos Roberto Valêncio
IBILCE/UNESP - São José do Rio Preto (SP)
Orientador

Prof. Dr. Geraldo Francisco Donegá Zafalon
IBILCE/UNESP - São José do Rio Preto (SP)

Prof. Dr. Pedro Luiz Pizzigatti Corrêa
POLI/USP - São Paulo (SP)

São José do Rio Preto
10 de Agosto de 2017


À meus pais


AGRADECIMENTOS

Agradeço muito ao Professor Carlos Roberto Valêncio pela oportunidade que
meu deu no Grupo de Banco de Dados, aceitando-me como seu orientado logo no
primeiro ano do curso de Graduação, ainda que eu tivesse à época passado por duas
reprovações. Desde então evolui muito a nı́vel pessoal e como estudante, o que
certamente teria sido muito mais difı́cil sem a experiência adquirida no GBD. Hoje, com
a conclusão do Mestrado, espero ter correspondido às expectativas depositadas em
mim, reiterando sentimentos de gratidão pelos últimos 6 anos que passei no laboratório
sob sua orientação.

Ainda entre os docentes dos quais fui aluno ao longo dos anos, faço aqui um
agradecimento póstumo em especial ao Professor José Márcio Machado, o qual eu
acompanhava em todas as disciplinas sempre que possı́vel, mesmo as disciplinas op-
tativas. Embora não seja do conhecimento de muitos, sempre admirei sua genialidade
fora do comum, e a influência dele na Graduação foi determinante para que eu deci-
disse seguir o caminho da Pós-Graduação, como modelo de pesquisador, acadêmico e
cientista.

Dos amigos, agradeço a Guilherme Priólli Daniel, que também trilhou o caminho
do Mestrado quase lado a lado comigo, e indiretamente me ajudou até este dia. À Fábio
Renato de Almeida, agradeço pelo conselhos e por servir como modelo em diversos
sentidos para meu projeto de pesquisa. E também agradeço aos atuais membros da
Equipe de Infraestrutura, Gabriel, Luis e Gustavo, que assumiram minhas tarefas no
laboratório nesse último semestre para que eu pudesse terminar minha dissertação.

Agradeço muito a meus pais, pela compreensão e ajuda que me deram nos
últimos anos. Poder morar com minha famı́lia me garantiu a estabilidade financeira e
emocional necessária para desenvolver o projeto de Mestrado com muita tranquilidade.
A eles, o reconhecimento merecido e todo o meu amor.

Por fim, agradeço a Coordenação de Aperfeiçoamento de Pessoal de Nı́vel
Superior (CAPES) pela bolsa de estudos de Mestrado, obtida através do Programa de
Pós-Graduação em Ciência da Computação da UNESP.


“I think it is possible for ordinary people to choose to be extraordinary.”
Elon Musk


RESUMO

Sistemas de gerenciamento de banco de dados, na sua essência, almejam garantir o
armazenamento confiável da informação. Também é tarefa de um sistema de gerencia-
mento de banco de dados oferecer agilidade no acesso às informações. Nesse contexto,
é de grande interesse considerar alguns fenômenos recentes: a progressiva geração de
conteúdo não-estruturado, como imagens e vı́deo, o decorrente aumento do volume de
dados em formato digital nas mais diversas mı́dias e o grande número de requisições
por parte de usuários cada vez mais exigentes. Esses fenômenos fazem parte de uma
nova realidade, denominada Big Data, que impõe aos projetistas de bancos de dados
um aumento nos requisitos de flexibilidade, escalabilidade, resiliência e velocidade dos
seus sistemas. Para suportar dados não-estruturados foi preciso se desprender de
algumas limitações dos bancos de dados convencionais e definir novas arquiteturas
de armazenamento. Essas arquiteturas definem padrões para gerenciamento dos
dados, mas um sistema de armazenamento deve ter suas especificidades ajustadas
em cada nı́vel de implementação. Em termos de escalabilidade, por exemplo, cabe a
escolha entre sistemas com algum tipo de centralização ou totalmente descentraliza-
dos. Por outro lado, em termos de resiliência, algumas soluções utilizam um esquema
de replicação para preservar a integridade dos dados por meio de cópias, enquanto
outras técnicas visam a otimização do volume de dados armazenados. Por fim, ao
mesmo tempo que são desenvolvidas novas tecnologias de rede e disco, pode-se
pensar na utilização de caching para otimizar o acesso ao que está armazenado. Este
trabalho explora e analisa os diferentes nı́veis no desenvolvimento de sistemas de
armazenamento distribuı́do. O objetivo deste trabalho é apresentar uma arquitetura
que combina diferentes técnicas de resiliência. A contribuição cientı́fica deste trabalho
é, além de uma sugestão totalmente descentralizada de alocação dos dados, o uso de
uma estrutura de cache de acesso nesse ambiente, com algoritmos adaptáveis.

Palavras-chave: big data, armazenamento, sistemas distribuı́dos, peer-to-peer, dados
não-estruturados, armazenamento de objetos


ABSTRACT

Database management systems, in essence, aim to ensure the reliable storage of
information. It is also the task of a database management system to provide agility in
accessing information. In this context, it is of great interest to consider some recent
phenomena: the progressive generation of unstructured content such as images and
video, the consequent increase in the volume of data in digital format in the most
diverse media and the large number of requests by users increasingly demanding.
These phenomena are part of a new reality, named Big Data, that imposes on database
designers an increase in the flexibility, scalability, resiliency, and speed requirements
of their systems. To support unstructured data, it was necessary to get rid of some
limitations of conventional databases and define new storage architectures. These
architectures define standards for data management, but a storage system must have
its specificities adjusted at each level of implementation. In terms of scalability, for
example, it is up to the choice between systems with some type of centralization or
totally decentralized. On the other hand, in terms of resiliency, some solutions utilize
a replication scheme to preserve the integrity of the data through copies, while other
techniques are aimed at optimizing the volume of stored data. Finally, at the same time
that new network and disk technologies are being developed, one might think of using
caching to optimize access to what is stored. This work explores and analyzes the
different levels in the development of distributed storage systems. This work objective is
to present an architecture that combines different resilience techniques. The scientific
contribution of this work is, in addition to a totally decentralized suggestion of data allo-
cation, the use of an access cache structure with adaptive algorithms in this environment.

Keywords: big data, storage, distributed systems, peer-to-peer, unstructured data,
object storage


LISTA DE ILUSTRAÇÕES
Página

2.1 Crescimento no volume do universo de dados (GANTZ; REINSEL, 2012). 6
2.2 Cluster do Facebook: falhas em 1 mês (SATHIAMOORTHY et al., 2013). . 7
2.3 Esquema simplificado de representação de blocos de dados . . . . . . . . 9
2.4 Esquema simplificado de representação de estrutura de arquivos . . . . . . 10
2.5 Esquema simplificado de representação de um objeto de dados . . . . . . 12
2.6 Desenho de um arquitetura do tipo mestre-escravo . . . . . . . . . . . . . . 13
2.7 Desenho de um arquitetura do tipo peer-to-peer . . . . . . . . . . . . . . . 14
2.8 Fluxo de restauração de um código MDS (5,3) . . . . . . . . . . . . . . . . 18
2.9 Exemplo de funcionamento de um código Regenerador . . . . . . . . . . . 19
2.10 À esquerda código hierárquico (2,1) e, à direita, código hierárquico (4,3) . . 21
2.11 Comparação da taxa de acerto do ARC versus o LRU (adaptado do traba-

lho (MEGIDDO; MODHA, 2004) . . . . . . . . . . . . . . . . . . . . . . . . 24

3.1 Comparação do tempo de execução da cifgra SHA-1 e outros algoritmos,
adaptado de (MAQABLEH, 2011). . . . . . . . . . . . . . . . . . . . . . . . 29

3.2 Geração de GUID para cada um dos nós da rede . . . . . . . . . . . . . . . 30
3.3 Geração da rede peer-to-peer em anel . . . . . . . . . . . . . . . . . . . . 31
3.4 Modelo em alto nı́vel de um dos nós da rede Griddler . . . . . . . . . . . . 32
3.5 Rede com indicativos da tabela de roteamento do nó 0 . . . . . . . . . . . 34
3.6 Primeiro nó de uma rede na arquitetura Griddler . . . . . . . . . . . . . . . 35
3.7 Representação das etapas a serem realizadas para inserção de um novo nó 36
3.8 Segundo nó de uma rede na arquitetura Griddler . . . . . . . . . . . . . . . 37
3.9 Rede com alguns objetos inseridos . . . . . . . . . . . . . . . . . . . . . . . 40
3.10 Representação do acesso ao cache em cada um dos nós do sistema distribuı́do 43

4.1 Gráfico da latência de acesso com e sem o uso de cache para dados replicados 46
4.2 Gráfico da latência de acesso com e sem o uso de cache para dados

codificados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4.3 Tempo decorrido na codificação de diferentes conjuntos de dados . . . . . 53
4.4 Tempo decorrido na decodificação de diferentes conjuntos de dados . . . . 54
4.5 Comparação de sobrecarga para ambas as técnicas de redundância . . . . 56


LISTA DE TABELAS
Página

2.1 Comparação entre os trabalhos correlatos . . . . . . . . . . . . . . . . . . . 26

3.1 Tabela de roteamento do nó 0 do ambiente P2P . . . . . . . . . . . . . . . 33

4.1 Latência média para diferentes objetos, replicação em 3x . . . . . . . . . . 45
4.2 Latência média para diferentes objetos, codificados . . . . . . . . . . . . . 46
4.3 Observações de latência para diferentes objetos, replicação em 3x, sem cache 47
4.4 Observações de latência para diferentes objetos, replicação em 3x, com cache 48
4.5 Observações de latência para diferentes objetos, codificados, sem cache . 49
4.6 Observações de latência para diferentes objetos, codificados, com cache . 50
4.7 Tempos de codificação para diferentes volumes de dados . . . . . . . . . . 53
4.8 Tempos de decodificação para diferentes volumes de dados . . . . . . . . 54
4.9 Sobrecarga para redundância no armazenamento de dados binários . . . . 57

5.1 Comparação entre os trabalhos correlatos e o trabalho proposto . . . . . . 60


LISTA DE ABREVIATURAS E SIGLAS

3D Três dimensões

AES Advanced Encryption Standard

API Application Programming Interface

ARC Adaptive Replacement Cache

ATA Advanced Technology Attachment

CIFS Common Internet File System

CPU Central Processing Unit

DHT Distributed Hashing Table

E/S Entrada e Saı́da (de dados)

FCP Fibre Channel Protocol

GPGPU General purpose GPU Computing

GPU Graphics Processing Unit

GUID Globally Unique Identifier

HDD Hard Disk Drive

HDFS Hadoop Distributed File System

HTTP Hypertext Transfer Protocol

IDC International Data Corporation

IP Internet Protocol

iSCSI Internet Protocol SCSI

LFU Least Frequently Used

LRU Least Recently Used

LVM Logical Volume Manager

MBR Minimum Bandwith Regenerating

MDS Maximum Distance Separable

NAS Network Attached Storage

NDSS Network Distributed Storage Systems


OID Object ID

P2P Peer-to-Peer

PCI Peripheral Component Interconnect

RAID Redundant Array of Independent Disks

REST Representational State Transfer

SAN Storage Area Network

SAS Serial Attached SCSI

SATA Serial ATA

SCSI Small Computer System Interface

SHA Secure Hashing Algorithm

SMB Server Message Block

SSD Solid State Drive

TCP Transmission Control Protocol

XFS X File System


SUMÁRIO
Página

1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 Considerações iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Organização do Trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Fundamentação Teórica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1 Considerações iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Desafios de armazenamento de dados . . . . . . . . . . . . . . . . . . . 5
2.3 Sistemas de armazenamento distribuı́dos em rede . . . . . . . . . . . . 6
2.4 Paradigmas de armazenamento de dados . . . . . . . . . . . . . . . . . 8

2.4.1 Armazenamento de Blocos . . . . . . . . . . . . . . . . . . . . . 8
2.4.2 Armazenamento de Arquivos . . . . . . . . . . . . . . . . . . . . 8
2.4.3 Armazenamento de Objetos . . . . . . . . . . . . . . . . . . . . . 9

2.5 Arquiteturas de sistemas distribuı́dos . . . . . . . . . . . . . . . . . . . . 12
2.5.1 Arquitetura do tipo mestre-escravo . . . . . . . . . . . . . . . . . 12
2.5.2 Arquitetura do tipo peer-to-peer . . . . . . . . . . . . . . . . . . . 13

2.6 Modelos de tolerância a falhas . . . . . . . . . . . . . . . . . . . . . . . 14
2.6.1 Replicação de Dados e Códigos de Correção de Erros . . . . . . 15
2.6.2 Códigos MDS (Reed-Solomon) . . . . . . . . . . . . . . . . . . . 16
2.6.3 Códigos Regeneradores (MBR) . . . . . . . . . . . . . . . . . . . 17
2.6.4 Códigos Localmente Reparáveis (Hierárquicos) . . . . . . . . . . 19

2.7 Tecnologias de disco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.7.1 Discos magnéticos e Discos de estado sólido . . . . . . . . . . . 20

2.8 Tecnologias de processamento . . . . . . . . . . . . . . . . . . . . . . . 22
2.8.1 Processadores convencionais e Processamento gráfico (GPGPU) 22

2.9 Algoritmos de Caching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.10 Trabalhos Correlatos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.10.1 CAROM - Cache A Replica On Modification . . . . . . . . . . . . 24
2.10.2 MICS - Mingling Chained Storage . . . . . . . . . . . . . . . . . . 25
2.10.3 HRSPC - Hybrid Redundancy Scheme Plus Computing . . . . . 25
2.10.4 Robot - Big data storage system based on erasure coding . . . . 25
2.10.5 HDFS-Xorbas - a module for erasure code in HDFS . . . . . . . 25
2.10.6 Análise dos trabalhos correlatos . . . . . . . . . . . . . . . . . . 26

2.11 Considerações Parciais . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

i


3 Armazenamento P2P com tolerância a falhas hı́brida e sistema de cache 28
3.1 Considerações iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Descrição e requisitos do ambiente distribuı́do . . . . . . . . . . . . . . 28
3.3 Tabela de roteamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4 Inserção de um novo nó . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.4.1 Inserção quando não existem outros nós na rede . . . . . . . . . 34
3.4.2 Inserção quando existem outros nós na rede . . . . . . . . . . . 36

3.5 Remoção de um nó . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.5.1 Remoção prevista pelos usuários . . . . . . . . . . . . . . . . . . 37
3.5.2 Remoção devido a falhas e imprevistos . . . . . . . . . . . . . . 38

3.6 Operações básicas de interação com o sistema . . . . . . . . . . . . . . 38
3.6.1 Inserção de dados na forma de objetos . . . . . . . . . . . . . . 39
3.6.2 Busca de dados na forma de objetos . . . . . . . . . . . . . . . . 40
3.6.3 Remoção de dados na forma de objetos . . . . . . . . . . . . . . 41
3.6.4 Atualização de dados na forma de objetos . . . . . . . . . . . . . 41

3.7 Mecanismo de caching distribuı́do com estratégia ARC . . . . . . . . . 42
3.8 Considerações Parciais . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

4 Experimentos e Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.1 Considerações iniciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2 Ambiente de testes e Conjunto de dados . . . . . . . . . . . . . . . . . 44
4.3 Latência de acesso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.4 Codificação e Decodificação . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.5 Sobrecarga de armazenamento . . . . . . . . . . . . . . . . . . . . . . . 55
4.6 Discussão dos resultados e próximos passos . . . . . . . . . . . . . . . 55
4.7 Considerações Parciais . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
5.1 Discussão sobre o trabalho desenvolvido . . . . . . . . . . . . . . . . . 59
5.2 Contribuições do trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5.3 Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

Referências Bibliográficas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

ii


CAPÍTULO 1 – Introdução

1.1 Considerações iniciais

Atualmente, o armazenamento resiliente de grandes volumes de dados, ou Big
Data, é um dos mais relevantes problemas a serem tratados em termos de infraestrutura
de suporte na ciência da computação (ALNAFOOSI; STEINBACH, 2013) (HASHEM
et al., 2015). Isso significa que todo armazenamento de dados deve ser feito de tal
maneira que os mesmos nunca sejam perdidos, independentemente de falhas ou
fatores externos comuns a qualquer ambiente computacional, como um dano a um
disco rı́gido. Ao mesmo tempo, é essencial otimizar o tempo de resposta às requisições
feitas sobre os dados, tendo em vista as limitações de velocidade no acesso das atuais
mı́dias de armazenamento secundário e as exigências crescentes por parte de usuários
e aplicações que necessitam de interações ágeis com o que está armazenado.

Muitas das tecnologias de vanguarda existentes em termos de tolerância a
falhas utilizam uma abordagem de replicação, em que um certo grau de redundância
é acrescentado aos dados, ao copiá-los e armazená-los em locais diferentes, mui-
tas vezes distantes geograficamente (GONIZZI et al., 2015). Embora a técnica de
replicação tenha se mostrado razoavelmente eficiente em diversos cenários e ainda
seja utilizada em diferentes contextos, possui suas desvantagens. A mais evidente
é o aumento da capacidade necessária em disco para armazenar um determinado
conjunto de dados, o que implica em uma maior sobrecarga em cada atualização para
manter as cópias idênticas, bem como incrementos nos custos de tempo e recursos de
hardware (WEATHERSPOON; KUBIATOWICZ, 2002). Nesse sentido, novas técnicas
têm sido progressivamente estudadas e introduzidas em ambientes distribuı́dos, com
destaque para métodos que utilizem códigos de correção de erros, também conhecidos
como erasure codes (KHAN et al., 2012). Quanto à otimização no acesso aos dados,
a capacidade de explorar a latência reduzida de mı́dias como a memória principal
torna o uso de técnicas de caching uma alternativa relevante. Contudo, também para
estas técnicas cabe uma análise cuidadosa para sua aplicação em ambientes de
armazenamento distribuı́do.

1.2 Motivação

A confiabilidade, velocidade no acesso e tolerância a falhas no armazenamento
dos dados são altamente relevantes, pois busca-se a garantia de que os dados, frutos
de significativos conjuntos de esforços ao longo das atividades dos empreendimentos
ou pesquisas, possam ser utilizados a fim de proporcionar vantagens competitivas ou
resultados de relevância aos estudos e pesquisas acadêmicas. Este trabalho encontra

1


2

motivação nos desafios de pesquisa na área, que hoje é alvo de estudo não somente
de iniciativas da academia, mas também de empresas de maior porte.

Em análises com relação às tecnologias de vanguarda mais utilizadas para
armazenamento de dados, se destaca o alto grau de adoção, impacto de negócio e
maturidade dos códigos de correção de erros (RINNEN, 2016), que compõem algo-
ritmos de dispersão da informação em sistemas distribuı́dos, o que tem estimulado
cada vez mais novas iniciativas nesta área. Em paralelo a isto, a aplicabilidade da
codificação dos dados para armazenamento tem sido, há algum tempo, estudada em
diversas situações reais. Na área da saúde, por exemplo (TZOVARAS et al., 1998),
imagens em três dimensões, 3D, são uma realidade consolidada, tanto no planeja-
mento de cirurgias quanto em simulações de radioterapia. Tais imagens devem ser
armazenadas confiavelmente por longos perı́odos de forma a preservar os diagnósticos
relacionados, sem perdas. É nos trabalhos mais recentes, no entanto, que se encontra
uma maior dedicação a esse tema, pois percebeu-se que os esquemas de resiliência
utilizados para armazenamento atualmente tendem a não suportar o volume incremen-
tal de dados existentes e gerados a todo momento. Com isto foram desenvolvidas
novas bibliotecas de software (PLANK; GREENAN, 2014) (CURRY et al., 2011) (TIAN,
2014), arquiteturas de armazenamento (YIN et al., 2013) (TANG et al., 2015) (MA et
al., 2013) (LI et al., 2016) e mesmo sistemas de arquivos distribuı́dos (BIAN; SEKER,
2013), todos baseados em códigos de correção de erros e algoritmos de dispersão
da informação, com bons resultados. Porém exaustivas comparações recentes ainda
comprovam a oportunidade de espaço para melhorias em diversos sentidos (DENG
et al., 2014), como em termos de uso da rede. Conforme será discutido mais adiante,
nem todos os códigos são otimizados para consumo de banda de rede, e os que o
são acabam tendo alguma outra desvantagem. Em diferentes corporações, como o
Facebook, isso é um problema, visto que inviabiliza a plena utilização de codificação
desse nı́vel, pois comprovou-se por simulações que isto provocaria uma saturação
total nos links de rede devido à grande quantidade de acessos aos dados armazena-
dos (SATHIAMOORTHY et al., 2013). Então este é um ramo ainda em aberto para
pesquisa. Outras empresas como o Google têm passado a utilizar códigos de correção
de erros, especialmente os códigos ditos MDS, do inglês Maximum Distance Separable,
a serem vistos mais adiante neste documento (FIKES, 2010), porém ainda não se
chegou a um consenso quanto à melhor forma de implantar este tipo de tecnologia,
devido às diversas nuances inerentes aos diversos métodos existentes. Como tanto
a técnica de replicação como a técnica de codificação de dados tem seus pontos
positivos e negativos, há ainda trabalhos relativamente recentes que sugerem que o
ideal é combinar ambas para obter o melhor em termos de tolerância a falhas com


3

eficiência no armazenamento (GRIBAUDO; IACONO; MANINI, 2016).
Para contornar a sobrecarga adicional que algoritmos associados a códigos de

correção de erros impõem sobre o tráfego na rede de um sistema de armazenamento
distribuı́do, uma alternativa possı́vel é utilizar algum tipo de cache com acesso otimizado.
Esse tipo de estratégia permite que o acesso aos dados, mesmo quando estes são
codificados, não passe pelo acesso a diversos nós na rede para, ao invés disso,
direcionar o fluxo das requisições primariamente ao cache. Por esse motivo essa
estrutura de acesso precisa ser construı́da sobre mı́dias com acesso mais rápido do
que os dispositivos de armazenamento secundário. Em geral a memória principal, ou
mais recentemente os discos de estado sólido, cumprem esse papel e são o principal
alvo de estudo de trabalhos recentes na área (AGGARWAL et al., 2016) (ABHIJITH
et al., 2016) (LIN et al., 2016), embora ainda haja espaço para novas pesquisas e
melhorias, especialmente no que tange a integrar essas técnicas com arquiteturas de
armazenamento distribuı́do.

1.3 Objetivos

Diante de tal motivação, o objetivo deste documento é descrever os resultados
obtidos no desenvolvimento do trabalho de pesquisa associado, de modo a corroborar
o esforço investido no estudo dos desafios mencionados anteriormente para apresentar
uma solução inovadora. O objetivo geral desse trabalho é a análise de diferentes
técnicas para armazenamento de dados voltadas à tolerância a falhas e velocidade no
acesso ao que está armazenado. Os objetivos especı́ficos desse trabalho consistem
no desenvolvimento de uma estratégia aprimorada para dispersão e armazenamento
confiável de dados por meio de tolerância a falhas mista, e com foco no aprimoramento
do acesso através de técnicas de caching em um ambiente totalmente descentralizado.
Toma-se por hipótese que a introdução de técnicas de codificação de dados em
sistemas descentralizados de armazenamento distribuı́do contribui para garantia de
tolerância a falhas, em especial quando associada à replicação, e é possı́vel escolher o
melhor método para cada conjunto de dados que se deseja armazenar. Essa hipótese
é reforçada pela escolha do algoritmo adequado para caching dos dados, o que pode
melhorar consideravalmente o acesso aos dados armazenados, em especial quando
estes se encontram codificados.

1.4 Organização do Trabalho

A seguir é apresentada a estrutura deste trabalho:


4

• Capı́tulo 2 – Fundamentação teórica: apresentação dos principais conceitos de
sistemas distribuı́dos de armazenamento de dados, tecnologias afins, replicação,
códigos de correção de erros e algoritmos de caching. Descrição dos problemas
associados e apresentação de trabalhos correlatos recentes da área.

• Capı́tulo 3 – Arquitetura proposta: apresentação do esquema de armazenamento
sugerido e todas as suas particularidades.

• Capı́tulo 4 – Experimentos e resultados: descrição de testes realizados e dos
resultados obtidos. Análise e discussão dos resultados obtidos em comparação
com os trabalhos correlatos.

• Capı́tulo 5 – Conclusão: considerações finais referentes ao trabalho apresentado,
bem como avaliação de possı́veis melhorias e trabalhos futuros.


CAPÍTULO 2 – Fundamentação Teórica

2.1 Considerações iniciais

Neste capı́tulo são apresentados aspectos teóricos relacionados com as se-
guintes áreas de estudo em ciência da computação: sistemas de armazenamento
distribuı́do, paradigmas de armazenamento, técnicas de replicação e técnicas de
codificação de dados. Estas duas técnicas são utilizadas para acrescentar alguma
redundância e tolerância a falhas controlada, de modo que, quando for necessária a
recuperação, os dados estejam sempre disponı́veis. Também são apresentadas e dis-
cutidas as técnicas de caching mais comuns. Do ponto de vista prático, o estudo destes
tópicos encontra aplicações em algumas áreas importantes da ciência da computação,
conforme será visto a seguir.

2.2 Desafios de armazenamento de dados

Como resultado de processos de negócio, monitoramento de atividades, senso-
res, dentre outros fatores, há uma tendência não só nas organizações, mas em todos
os contextos, de aumento nos volumes de dados gerados e armazenados diariamente.
Redes sociais e websites permitem ainda que usuários criem registros completos de
suas vidas ao postar diariamente suas atividades, lugares visitados, fotos exibidas e
preferências pessoais. Essa quantidade expressiva de informações é frequentemente
referenciada como Big Data, um termo que busca destacar os desafios existentes no tra-
tamento destes dados em termos de armazenamento, interoperabilidade, governança
e análise (GANDOMI; HAIDER, 2015) (ASSUNÇÃO et al., 2015). Duas caracterı́sticas
recorrentes em diversos desses conjuntos de dados são o volume e variedade, o que
indica um comportamento de crescimento constante e a não-restrição aos dados tidos
como convencionais, encontrados em formato texto em tabelas e bancos de dados
relacionais (ASSUNÇÃO et al., 2015) (JIN et al., 2015). Dessa forma, dois desafios
importantes estão em como tratar tipos não-estruturados em conjuntos maiores de
dados e como otimizar o uso de disco de modo a garantir a disponibilidade frente a
falhas comuns ou mesmo desastres de infraestrutura em larga escala. Em termos de
armazenamento, estes são alguns dos fatores principais a serem considerados, e o
uso de replicação, códigos de correção de erros e algoritmos de dispersão se mostra
uma alternativa válida a ser considerada nesse sentido. Na Figura 2.1 é apresentado
um indicativo do crescimento do universo digital, previsto pela IDC - International Data
Corporation - há alguns anos, do qual boa parte é composta de dados não-estruturados.
Em paralelo, é possı́vel observar na Figura 2.2 um exemplo da quantidade de falhas que
acontecem em um ambiente real de armazenamento distribuı́do, em que foi avaliado

5


6

um cluster do Facebook com 3000 computadores. Por meio da observação de ambas
as imagens é possı́vel perceber o contraste entre a importância do que tem sido criado
em termos de dados e o que uma infraestrutura computacional de alta disponibilidade
necessita em termos de tolerância a falhas. É, portanto, essencial entender que tipos
de arquiteturas e sistemas computacionais são necessários para trabalhar com esse
nı́vel de desafios.

Figura 2.1: Crescimento no volume do universo de dados (GANTZ; REINSEL, 2012).

2.3 Sistemas de armazenamento distribuı́dos em rede

Embora as tecnologias de tolerância a falhas e disponibilidade, como os arrays
de discos independentes (em inglês, Redundant Array of Independent Disks - RAID), te-
nham se desenvolvido amplamente no contexto dos sistemas de armazenamento mais
atuais, em paralelo novas tecnologias surgiram, as quais utilizam diversas unidades
lógicas de armazenamento – ou simplesmente nós de armazenamento – que atuam em
conjunto para aumentar a capacidade de provisionamento do sistema como um todo.
Isso ocorre pelo fato de haver um volume significativo de dados gerados a cada dia, o
que torna difı́cil e custoso construir um único dispositivo computacional com capacidade
de armazenamento e entrada/saı́da, E/S, suficientes para suportar essa carga (DATTA;
OGGIER, 2013). Ao tratar de sistemas distribuı́dos em rede entenda-se esse tipo
de sistema de armazenamento, que agrupa recursos de diferentes nós conectados


7

Figura 2.2: Cluster do Facebook: falhas em 1 mês (SATHIAMOORTHY et al., 2013).

entre si, os quais individualmente podem ou não utilizar tecnologias especı́ficas como
RAID. Os dados são distribuı́dos por meio de diversas unidades de armazenamento
interconectadas, daı́ o nome sistemas de armazenamento distribuı́dos em rede – do
inglês networked distributed storage systems (NDSS) (OGGIER; DATTA, 2013).

Os NDSS podem caracterizar diversos tipos de sistemas e arquiteturas, tais
como datacenters e sistemas de armazenamento em Nuvem ou backup peer-to-peer
(P2P), cada um com suas particularidades, mas que compartilham caracterı́sticas em
comum. Dado que estes sistemas geralmente tomam proporções significativas, e são
compostos muitas vezes por centenas ou milhares de nós, a falha de um nó individual
ou mesmo de outros componentes da rede acaba se tornando uma norma, e não uma
exceção (DATTA; OGGIER, 2013). Por esse motivo, e com o objetivo de oferecer uma
alta disponibilidade geral para os serviços fornecidos, é primordial garantir tolerância
tanto a interrupções temporárias quanto a falhas permanentes de componentes indivi-
duais do sistema. A tolerância a falhas é obtida por meio de redundância, e a resiliência
a longo prazo é obtida por meio da restauração da redundância perdida ao longo do
tempo por qualquer falha. Nesse sentido os códigos de correção de erros, do inglês
erasure codes, se tornaram bastante populares pois garantem a resiliência de um
sistema e implicam em uma sobrecarga de armazenamento relativamente baixa. Em
trabalhos mais recentes é recorrente a pesquisa em termos de modelos de códigos
de correção de erros feitos sob medida para atender as necessidades de sistemas de
armazenamento distribuı́dos, particularmente com destaque para melhorias em termos
de reparabilidade do sistema (PAMIES-JUAREZ; OGGIER; DATTA, 2013). A seguir


8

são apresentados e explicados alguns outros conceitos relacionados a tecnologias de
armazenamento de dados que devem ser levados em consideração na concepção de
sistemas de armazenamento distribuı́dos em rede.

2.4 Paradigmas de armazenamento de dados

Nas próximas seções são descritos três dos principais paradigmas de armazena-
mento de dados existentes, cujas caracterı́sticas permitem justificar sua aplicação em
diferentes contextos. No texto é dado maior destaque à tecnologia de armazenamento
de objetos, pois ela tem sido o foco de diversas pesquisas recentes.

2.4.1 Armazenamento de Blocos

Nesse tipo de estratégia são criadas e gerenciadas sequências de tamanho fixo
de bits, chamadas de blocos, do dispositivo de armazenamento. Essas sequências
podem ter apenas alguns bytes ou mesmo ocupar algumas dezenas de megabytes,
como é o caso de algumas tecnologias mais recentes (SHVACHKO et al., 2010). Para
armazenamento em blocos, o sistema operacional obrigatoriamente se conecta aos
dispositivos de armazenamento instalados no computador. Os dados ficam então
disponı́veis por meio de uma série de interfaces e clientes, tais como: Canais de Fibra
(ou Fibre Channel Protocol, FCP), SCSI (Small Computer System Interface) e iSCSI
(Internet Protocol SCSI), SAS (Serial Attached SCSI), ATA (Advanced Technology
Attachment) e SATA (Serial ATA).
Algumas dessas tecnologias são mais comumente utilizadas para acesso a dispositivos
de armazenamento alocados fora do computador, como em uma SAN, rede de área
de armazenamento, do inglês Storage Area Network. Contudo discos SAS e ATA são
mais utilizados da forma convencional, conectados diretamente ao computador, sem
equipamentos intermediários (EDITION, 2014). Na Figura 2.3 é possı́vel observar um
esquema de armazenamento em blocos.

2.4.2 Armazenamento de Arquivos

A estratégia de armazenamento em arquivos tem como diferencial a utilização de
uma estrutura pré-definida de diretórios. Sistemas conectados à rede que armazenam
dados na forma de arquivos são conhecidos como NAS - Network Attached Storage.
Normalmente estes dispositivos atuam da mesma forma que um servidor computacional
comum, e tem os seus próprios processadores. Para acessar os dados, são utilizados
os protocolos padrão TCP/IP. Alguns dos protocolos mais comuns são: SMB (Server
Message Block) ou CIFS (Common Internet File System), que é comumente usado
em redes baseadas no Windows, NFS (Network File System), que é comum em redes


9

Figura 2.3: Esquema simplificado de representação de blocos de dados

baseadas em Unix/Linux, e HTTP (Hypertext Transfer Protocol), o protocolo padrão
para acesso via navegadores web (EDITION, 2014).
Esses tipos de sistemas de armazenamento são fáceis de implantar e o acesso do
cliente é simples, pois é feito por meio de um ou mais dos protocolos mencionados
anteriormente. Independente do sistema operacional, dado que todos os dispositivos
na rede estejam conectados entre si de forma compartilhada, os dados de sistemas
do tipo NAS poderão ser acessados, e por esse motivo ainda são utilizados em
diversos contextos. No entanto, sistemas desse tipo possuem algumas desvantagens
significativas que devem ser levadas em conta. Eles são normalmente mais lentos
que sistemas de armazenamento baseados em acesso direto a blocos, visto que
necessitam de processamento adicional. Ao mesmo tempo, dispositivos NAS também
têm escalabilidade limitada. Quando um dispositivo NAS esgota seus recursos de disco,
é possı́vel adicionar outro dispositivo em paralelo. Porém, como estes dispositivos a
princı́pio não interagem entre si, ocorre o fenômeno das ilhas de armazenamento, que
são ineficientes para se gerir (MA et al., 2014). Na Figura 2.4 é possı́vel observar uma
parte da estrutura de arquivos de um sistema operacional Linux.

2.4.3 Armazenamento de Objetos

Sistemas de armazenamento baseados em objetos usam uma estrutura nova,
chamada de container, para armazenar dados na forma de objetos em um espaço de
endereço plano ao invés de utilizar os sistemas de arquivos hierárquicos, baseados
em diretório, que são comuns em sistemas de armazenamento baseados em blocos e


10

Figura 2.4: Esquema simplificado de representação de estrutura de arquivos

arquivos. Um container armazena os dados reais (por exemplo, uma imagem ou vı́deo),
os metadados (por exemplo, data, tamanho, tipo), e um OID, Object ID, único (FACTOR
et al., 2005). Cada OID é armazenado em um banco de dados ou aplicativo à parte
e é usado para fazer referência a objetos em um ou mais containers. Os dados são
acessados via protocolo HTTP por meio de um navegador web ou diretamente por
meio de uma API como REST, Transferência de Estado Representacional, do inglês
Representational State Transfer. Essa API implementa funções importantes como PUT,
GET e DELETE para interagir com os objetos armazenados. O espaço de endereço
plano em um sistema de armazenamento permite tratar o disco e a memória como um
único espaço contı́guo e ignorar situações como fragmentação e paginação. Por esse
motivo, o armazenamento baseado em objetos permite simplicidade e escalabilidade
massiva, mas os dados nesses sistemas normalmente não podem ser modificados, e
devem ser completamente eliminados e uma versão inteiramente nova escrita em seu
lugar (MESNIER; GANGER; RIEDEL, 2003). Porém essa é uma opção interessante
pois torna possı́vel guardar versões de um mesmo objeto em diferentes estados e com
diferentes modificações. Armazenamento com base em objetos é comumente utilizado
para serviços na Nuvem por fornecedores, como IBM SoftLayer, Amazon S3, Google


11

e Facebook, e devido a isso existem tecnologias de mercado que fornecem soluções
bastante completas nesse sentido (KAPADIA; RAJANA; VARMA, 2015).

Armazenamento de objetos é diferente de armazenamento em blocos e arquivos,
pois virtualiza totalmente a implementação fı́sica da apresentação lógica. É semelhante
ao check-in de bagagem em aeroportos, em que a bagagem é colocada no sistema
de esteiras sem que saiba onde será depositada ou qual caminho percorrerá. Há
apenas a garantia de retirada da bagagem no destino final da viagem. Se você usa
uma bagagem de mão, você tem que saber exatamente o lugar em que ela está em
todos os momentos, o que analogamente para armazenamento de dados pode ser
custoso. O foco de armazenamento de objetos é, portanto, o scale-out, ou seja, o uso
de sistemas distribuı́dos em larga escala (EDITION, 2014). Cada nó, desse sistema
de armazenamento maior pode utilizar localmente um sistema de arquivos, mas a
ideia de arquiteturas de armazenamento objeto é permitir a utilização de hardware
não-especializado, ou hardware commodity, ao contrário de equipamentos caros e
difı́ceis de lidar utilizados em sistemas de armazenamento tradicionais. As tarefas mais
importantes de um sistema de armazenamento de objetos são as seguintes:

• Alocação de dados (placement)

• Automatização de tarefas de gerenciamento, inclusive a garantia de durabilidade
e disponibilidade

Normalmente, um usuário envia seu pedido GET, PUT ou DELETE para qualquer
nó de armazenamento do sistema distribuı́do, e o pedido é traduzido para os dispositivos
de armazenamento por parte do software de gerenciamento de objetos. O software
também cuida do modelo de durabilidade ao fazer uso de técnicas como replicação e
códigos de correção de erros. O modelo de durabilidade em geral não é RAID devido
às dificuldades de escalabilidade dessa tecnologia quando o volume dos dados atinge
a ordem de centenas de terabytes. Ao mesmo tempo é preciso ter algum mecanismo
automatizado para tratar de tarefas crı́ticas de gestão, tais como verificações periódicas
do estado dos nós, auto-correções, e migração de dados. A administração também é
facilitada pela abstração do endereçamento plano, o que significa que um administrador
pode gerenciar todo o sistema distribuı́do como se fosse uma única entidade (EDITION,
2014). Na Figura 2.5 é ilustrada uma representação de um objeto, no qual há espaço
dedicado tanto para o armazenamento dos dados quanto para o armazenamento dos
metadados, além de uma sequência exclusiva pela qual é possı́vel identificar um único
objeto dentre todos os que estiverem armazenados.


12

Figura 2.5: Esquema simplificado de representação de um objeto de dados

2.5 Arquiteturas de sistemas distribuı́dos

A seguir são descritas duas das arquiteturas mais comuns de sistemas dis-
tribuı́dos, as quais apresentam caracterı́sticas, até certo ponto, antagônicas. Por esse
motivo, é necessário detalhar os motivos que levam à escolha da arquitetura mais
adequada para um determinado trabalho.

2.5.1 Arquitetura do tipo mestre-escravo

Talvez o paradigma mais tradicional para sistemas distribuı́dos, e um padrão
extensamente adotado para clusters de computadores, a arquitetura do tipo mestre-
escravo divide em dois grupos os recursos computacionais disponı́veis. Computadores
com nı́vel mestre são responsáveis pelo pré-processamento das tarefas recebidas pelo
sistema. Ao mesmo tempo, um computador mestre atribui as tarefas aos computadores
escravos, que por sua vez são responsáveis pela real execução das ordens recebidas.
Em geral, para se obter o melhor desempenho de um sistema desse tipo, o ideal é
que o número de tarefas nunca ultrapasse o número de processadores disponı́veis
nos escravos. Aplicações deste paradigma incluem principalmente computação para-
lela (SAHNI; VAIRAKTARAKIS, 1996). Em programação paralela é possı́vel desenvolver
um único programa que permita o uso de desvios, ou forks, para lançar múltiplas linhas,
ou threads, de execução. A operação de desvio envolve a passagem de diferentes
quantidades de dados para os computadores escravos. Esses computadores, por sua
vez, retornam os resultados para a linha de execução principal do programa, controlada


13

pelo mestre.
Existem de fato alguns trabalhos recentes que utilizam essa arquitetura para siste-
mas de armazenamento (QIN et al., 2015), dentre os quais diversos se baseiam no
HDFS - Hadoop Distributed File System - um sistema de arquivos distribuı́do de uso
geral (SATHIAMOORTHY et al., 2013) (KO; ZAW, 2014) (RASHMI et al., 2014). Porém
outros trabalhos também apontaram o problema com essa arquitetura, que cria efeitos
de afunilamento na rede, em que um mestre se torna um ponto crı́tico de falha, pois
se este falhar, ainda que os demais computadores funcionem, o sistema fica indis-
ponı́vel (CAIWEI; LEI; LIANSHENG, 2012). Na Figura 2.6 é ilustrado um exemplo de
uma arquitetura do tipo mestre-escravo em que um único nó mestre é responsável por
atender e distribuir solicitações para três nós escravos, que ficam encarregados de
todo o processamento adicional.

Figura 2.6: Desenho de um arquitetura do tipo mestre-escravo

2.5.2 Arquitetura do tipo peer-to-peer

Sistemas peer-to-peer (P2P) surgiram inicialmente como um fenômeno social,
de modo a ser uma arquitetura para compartilhamento de recursos computacionais,
como ciclos de CPU (ANDERSON, 2004) ou para troca de arquivos (RIPEANU, 2001).
Em um modelo P2P não existe o conceito de computadores servidores e especializados,
que tenham uma função central de gerência do sistema distribuı́do como um todo. Ao
invés disso essa função é atribuı́da a todos os membros da rede, que podem ser
computadores com hardware commodity. O conceito principal a ser levado em conta


14

quando se trata de sistemas de armazenamento P2P é que os dados são distribuı́dos
entre cada um dos peers para que um nı́vel alto de confiabilidade e tolerância a falhas
seja obtido, com um custo geral reduzido. Dessa forma há uma liderança compartilhada,
e não há um ponto único de falha (RIPEANU, 2001).
Por todos esses motivos tem sido dada muita atenção a esse tipo de arquitetura em
diversos trabalhos recentes em armazenamento de dados, haja vista que algumas de
suas caracterı́sticas superam limitações da arquitetura do tipo mestre-escravo (PARK;
SONG, 2016) (DELL’AMICO et al., 2015) (CARON et al., 2014) (ESINER; DATTA,
2016) (MARTALÒ et al., 2014). Na Figura 2.7 é ilustrado um exemplo de uma arquitetura
do tipo peer-to-peer, para a qual não há o papel de um nó gerenciador principal.
Ao contrário, todos os nós são igualmente responsáveis por atender e processar
solicitações e cada peer interage com os demais conforme o necessário.

Figura 2.7: Desenho de um arquitetura do tipo peer-to-peer

2.6 Modelos de tolerância a falhas

Nesta seção são realizadas algumas explicações sobre os modelos de tolerância
a falhas mais utilizados em diversos trabalhos da literatura, quais sejam: replicação
e códigos de correção de erros. Espera-se com isso mostrar os pontos positivos e
negativos de cada um deles, no sentido de fornecer a base teórica para trabalhos cujo
objetivo seja garantir a tolerâncias a falhas em sistemas de armazenamento distribuı́do.


15

2.6.1 Replicação de Dados e Códigos de Correção de Erros

Em computadores e nas telecomunicações digitais, os dados são representados
na forma binária, isto é, uma sequência de bits que tem o valor 0 ou 1. Essa sequência
pode se dividir naturalmente em unidades como octetos ou bytes que representam
caracteres especı́ficos (LINT, 2012). Toda essa representação é feita de forma bastante
direta, de modo que o maior problema não está na representação binária dos dados,
mas na sua transmissão por canais de comunicação ou no seu armazenamento. Isto
ocorre porque estas funções podem acarretar em interferências que podem causar erros
nos dados, por meio da adição, remoção e alteração de um ou mais bits (PURSER;
HOUSE, 1995).

A forma mais comum de garantir a confiabilidade no armazenamento dos dados
é a replicação. Essa técnica consiste em apenas criar uma ou mais cópias inteiras de
um determinado conjunto de dados, geralmente em computadores ou discos rı́gidos
diferentes daquele em que foram gravados originalmente. Essa estratégia, apesar de
eficiente em termos de acesso aos dados armazenados, incorre em uma sobrecarga
extra de uso dos dispositivos de armazenamento, haja vista a necessidade de reservar
espaço para as cópias. Técnicas de correção de erros, por outro lado, introduzem
redundância controlada nos dados, a fim de mitigar possı́veis problemas, de modo
que mensagens corrompidas durante sua transmissão ou armazenamento possam ser
corrigidas antes de qualquer processamento adicional (PURSER; HOUSE, 1995). Ou
seja, apenas uma parte dos bits transmitidos ou armazenados são dados válidos. Esse
tipo de técnica, os códigos de correção de erros, possuem ampla e complexa herança
matemática originada em um ramo de estudo conhecido como teoria de códigos (LINT,
2012). Além de benefı́cios claros para a transmissão de dados, observou-se que alguns
subconjuntos dentre todos os tipos de códigos estudados nessa área do conhecimento
podem ser utilizados em aplicações de armazenamento de dados, notoriamente os
códigos MDS – Maximum Distance Separable. Embora este tipo de código seja o
foco de diferentes trabalhos atuais, também existem outras variantes de codificação
que tem sido estudadas em menor escala, porém a estas também são dadas as
devidas explicações nas próximas seções. É importante destacar, no entanto, alguns
compromissos importantes que a técnica de codificação, do inglês erasure coding,
impõe, a saber (CARPENTIER, 2013):

• Maiores perdas de dados do que a replicação quando o número de discos
com falha cresce - no caso da replicação, enquanto ainda houver uma cópia
intacta a perda de dados é minimizada. No caso dos códigos, cada falha resulta
em uma perda parcial do que está armazenado, porém a vantagem neste caso é


16

a fácil restauração;

• Os melhores resultados só são realmente obtidos em sistemas distribuı́dos
de grande porte - é estatisticamente vantajoso possuir um sistema distribuı́do
grande o suficiente, em termos da quantidade de nós computacionais que atuam
em conjunto, para tolerar falhas individuais de forma eficiente. A depender da
construção do código, isto acaba por se tornar uma necessidade;

• Os melhores resultados só são realmente obtidos ao tratar arquivos real-
mente grandes - para arquivos relativamente pequenos, por exemplo um arquivo
de 100KB, o ganho em armazenamento é irrelevante se comparado ao custo
de processamento e transmissão dos dados. Tais caracterı́sticas certamente os
tornam mais úteis em contextos como o de Big Data, e embora a perda de dados
seja de fato maior do que com o uso da simples replicação, a capacidade de
restaurar os dados de maneira eficiente é um fator a se considerar e neste caso
os códigos possuem qualidades mais favoráveis.

Nas seções seguintes se encontram descrições dos principais códigos traba-
lhados na literatura da área, os quais se dividem em três classes principais: MDS,
Regeneradores e Localmente Reparáveis. É importante mencionar que para cada uma
das classes de códigos mencionadas podem existir diversas derivações de códigos
em desenvolvimento, e por esse motivo em cada seção foi destacado apenas um
exemplo para ser descrito em maiores detalhes. Porém é necessário assumir que
todos os demais códigos existentes em cada classe respeitam as devidas regras e
caracterı́sticas de sua categoria.

2.6.2 Códigos MDS (Reed-Solomon)

No contexto de erasure coding, códigos ditos MDS – acrônimo inglês para
Maximum Distance Separable – são aqueles que fornecem eficiência ótima para
armazenamento. Destes, o tipo mais conhecido que tem sido utilizado e estudado ao
longo dos anos é o dos códigos de Reed-Solomon (REED; SOLOMON, 1960). Para
entender tais códigos, no entanto, é preciso previamente compreender que seu uso
está voltado principalmente a dados na forma de objetos, que em última instância são
tratados como arquivos. Cada um desses objetos pode ser armazenado em n discos
rı́gidos. Dado um número k arbitrário, em que k < n, códigos MDS(n,k) fornecem a
garantia de tolerar até um máximo de n−k falhas de discos, o que implica que k discos
são suficientes para acessar quaisquer bits dos dados originais. Especificamente,
o objeto de dados é codificado em n blocos por meio de métodos algébricos ou
operações lógicas, e esses blocos devem ser uniformemente disseminados em n discos


17

rı́gidos (SUH; RAMCHANDRAN, 2010). No caso de códigos de Reed-Solomon, a
codificação cria sı́mbolos de um campo finito Fq, de tamanho q, e cada sı́mbolo é
armazenado em um nó diferente, ou seja, cada sı́mbolo gerado contém parte dos
dados originais. Suponha que o tamanho total do objeto de dados a ser armazenado
seja de M bits. Então o volume armazenado em cada nó é equivalente a M/k bits, se
os metadados associados a esse objeto não forem considerados. Nesse sentido, a
eficiência de armazenamento de códigos MDS é na melhor das hipóteses k/n (LI; LI,
2013).

Ao se comparar com a replicação em 3 vias é possı́vel implementar um código
MDS(5,3), conforme ilustrado na Figura 2.8, que ainda tolere no máximo duas falhas de
discos rı́gidos, enquanto que ao mesmo tempo melhore a eficiência de armazenamento
em 80%. Para acessar o objeto de dados o sistema precisa acessar k blocos codificados
diferentes de k discos diferentes e recuperar os dados originais por meio de um
algoritmo de decodificação, que varia de acordo com o tipo de código MDS utilizado.
Para Reed-Solomon, a decodificação usa um método algébrico com aritmética de
campos finitos. Entretanto esse algoritmo de decodificação inerentemente acarreta
em aumento na latência de acesso dos discos. Em vários casos, é razoável buscar
recuperar todo o arquivo, com o objetivo de garantir o acesso aos dados. Entretanto,
do ponto de vista do sistema de armazenamento em si, é desnecessário recuperar
um objeto completo se somente é necessário reparar, eventualmente, um pequeno
bloco codificado que foi danificado, o que corresponde a apenas uma fração do objeto
de dados original. Essa caracterı́stica é presente em todos os códigos MDS, e sofre
alterações apenas em outra categoria de códigos chamados Regeneradores, que são
descritos adiante. Porém no caso MDS, é preciso acessar pelo menos k discos para
reparar apenas um único disco. Como os dados em cada nó são armazenados em
sı́mbolos de tamanho M/k, esse acesso implica em transferir não menos que M bits
pela rede, que é o tamanho do arquivo original. É válido lembrar que no caso da
replicação, para reparar uma réplica é preciso acessar apenas uma única dentre as
demais réplicas. Esse requisito pode aumentar dramaticamente tanto a E/S dos discos
quanto gerar uma sobrecarga de utilização de banda de rede em um datacenter, e isto
afeta significativamente a performance tanto do sistema de armazenamento quanto
das demais aplicações hospedadas na mesma Nuvem computacional (LI; LI, 2013).

2.6.3 Códigos Regeneradores (MBR)

No contexto de erasure coding, códigos ditos Regeneradores, do inglês Re-
generating Codes, são aqueles que fornecem eficiência ótima para banda de rede.
Destes, um exemplo são os códigos MBR – acrônimo inglês para Minimum Bandwith


18

Figura 2.8: Fluxo de restauração de um código MDS (5,3)

Regenerating. Esta classe de código se utiliza do compromisso de armazenar em cada
nó uma quantidade extra de dados redundantes para se beneficiar de reparos mais
eficientes, em que a quantidade de bits transferidos seja exatamente a necessária para
restaurar um conjunto de dados, sem os excessos de códigos MDS (RASHMI et al.,
2009).

A diferença desse tipo de código para os códigos MDS começa pela forma com
que as informações são armazenadas em cada nó individualmente. Ao invés de tratar
as informações em cada nó como apenas um sı́mbolo pertencente a um campo finito,
trabalha-se com o armazenamento de vetores de sı́mbolos em cada nó. Ou seja, cada
nó armazena α sı́mbolos dentro de Fq, em que α > 1. Nessa configuração fica claro
que é possı́vel para qualquer nó individual transferir apenas uma parcela dos dados
que armazena (LI; LI, 2013).

Fora este novo parâmetro α , dois outros parâmetros d e β , são associados com
códigos regeneradores. Por definição códigos regeneradores permitem que um nó
com falhas se conecte a um conjunto arbitrário de d ≥ k nós dos (n–1) nós restantes, e
transfira β ≤ α sı́mbolos de cada nó. Veja que a constante k ainda é presente nestes
códigos, assim como nos códigos MDS. Enquanto nestes compõe a definição do total
armazenado em cada nó como um valor M/k , no caso de códigos Regeneradores MBR
esse valor chega a 2Md/k(2d−k+1). O total de dados transferidos para fins de reparo,
seja dβ , é denominado de repair bandwidth. Em códigos regeneradores tı́picos o valor
médio de dβ para repair bandwidth é pequeno se comparado ao tamanho original M do
arquivo armazenado, o que é um ganho se comparado a códigos do tipo MDS (SHAH


19

et al., 2012). Na Figura 2.9 é apresentado um modelo simples de funcionamento de
um código Regenerador, em que durante uma falha do nó 1 ocorre o acesso a um
número maior de nós computacionais, porém com uma quantidade menor de dados
transferidos pela rede quando comparado a um código do tipo MDS.

Figura 2.9: Exemplo de funcionamento de um código Regenerador

2.6.4 Códigos Localmente Reparáveis (Hierárquicos)

No contexto de erasure coding, códigos ditos Localmente Reparáveis são aque-
les que buscam fornecer eficiência ótima para acesso aos discos. A ideia desses
códigos é minimizar o número de nós de armazenamento envolvidos nas situações
de reparo dos dados (PAPAILIOPOULOS; DIMAKIS, 2014). O exemplo mais comum
desse tipo de código são os códigos Hierárquicos.

Códigos localmente reparáveis, inclusive os códigos hierárquicos, garantem que
seja possı́vel obter um valor de nós acessados d tal que d < k. Ou seja, é possı́vel
contatar um número menor de nós do que o mı́nimo que é necessário normalmente
para um código MDS durante a restauração dos dados. Essa propriedade dos códigos


20

MDS permite, no entanto, que qualquer conjunto de k nós seja suficiente para restaurar
um nó danificado, e tal propriedade não é obtida em códigos Localmente Reparáveis.
Isso significa que nem todos os grupos de falhas possı́veis podem ser toleradas (PA-
PAILIOPOULOS; DIMAKIS, 2014) (DUMINUCO; BIERSACK, 2008).

Particularmente em relação aos códigos hierárquicos, como o próprio nome
sugere, tais códigos são construı́dos de uma maneira organizada em hierarquias. Na
Figura 2.10 é ilustrado um exemplo de construção hierárquica de códigos. Na primeira
parte da imagem é possı́vel observar uma instância de códigos hierárquicos (2,1), que
produz dois nós de armazenamento com blocos de dados codificados e um terceiro
que é utilizado como paridade. Dados F1 e F2 como blocos de dados originais a serem
armazenados, são criados blocos codificados B1, B2, e B3, em que somente B3, de
grau 2, é o bloco de paridade. Qualquer combinação de dois dentre B1, B2, e B3 possui
arestas que indicam os blocos F1 e F2, e sugere que quaisquer dois dentre eles podem
ser utilizados para reparar os blocos de dados originais (LI; LI, 2013). Novamente,
assim como nos demais códigos, as técnicas envolvidas tanto para codificação quanto
decodificação envolvem processos algébricos de aritmética de campos finitos, e em
alguns casos o uso de cálculos de ou-exclusivo (XOR). Na continuação da imagem é
apresentado um código hierárquico (4,3), que nada mais é que uma extensão do código
(2,1). É importante notar que mesmo com o aumento no número de nós, o número
necessário em caso de necessidade de restauração dos dados originais permanece 2.
Como era de se esperar, estes códigos também implicam em armazenar um volume
maior de informações em cada nó, quando comparados por exemplo com códigos
MDS. Este tipo de códigos foi concebido inicialmente para sistemas de armazenamento
P2P (DUMINUCO; BIERSACK, 2008), porém isto não é uma norma, e sim uma decisão
de projeto.

2.7 Tecnologias de disco

Nesta seção são descritas as duas principais tecnologias de disco e dispositivos
existentes, os quais funcionam como base para qualquer sistema de armazenamento,
distribuı́do ou não. O objetivo dessa seção é comparar ambas as tecnologias no sentido
de justificar suas aplicações em diferentes situações.

2.7.1 Discos magnéticos e Discos de estado sólido

A unidade de disco rı́gido (HDD) é um dispositivo de armazenamento utilizado
para armazenar e recuperar dados digitais por meio da rotação rápida de discos re-
vestidos com material magnético. Um HDD não é volátil, ou seja, mantém seus dados
mesmo quando na ausência de energia. Os dados armazenados podem ser lidos


21

Figura 2.10: À esquerda código hierárquico (2,1) e, à direita, código hierárquico (4,3)

de um modo de acesso aleatório, o que significa que os blocos de dados podem ser
armazenados ou recuperados em qualquer ordem. Um disco rı́gido contém um ou
vários discos rotativos, rigidamente fixados, com cabeças magnéticas dispostas sobre
um braço atuador que pode mudar de posição para ler e gravar dados nas superfı́cies
metálicas (KANG et al., 2013).
A unidade de estado sólido (SSD), também conhecida como um disco de estado sólido,
é um dispositivo para armazenamento de dados por meio de conjuntos de circuitos
integrados como memória para armazenar dados de forma consideravelmente eficiente.
Um SSD utiliza componentes eletrônicos que obedecem os padrões de entrada/saı́da,
E/S, convencionais dos HDDs, o que permite assim ser um substituto mais fácil em
aplicações comuns. SSDs utilizam a memória de armazenamento flash, que tem a
capacidade de reter dados sem energia, das mesma forma que discos rı́gidos conven-
cionais (KANG et al., 2013).
Embora os SSDs possuam diversos benefı́cios, como serem mais duráveis, mais
rápidos e mais silenciosos (SAXENA; KUMAR, 2014) (LEE et al., 2011), há um custo
ainda financeiramente alto para implantar esta tecnologia em larga escala e sua capaci-
dade de armazenamento ainda não chega à capacidade dos HDDs. Há alguns trabalhos
que sugerem que para sistemas que dependem de um número maior de dispositivos
de armazenamento ainda faz mais sentido usar discos rı́gidos convencionais (RIZVI;


22

CHUNG, 2010), muito embora isso seja uma decisão de projeto que deve ser baseada
nos recursos disponı́veis para implantação do ambiente de armazenamento.

2.8 Tecnologias de processamento

Nas seções a seguir são descritas duas das principais tecnologias de proces-
samento de dados existentes para computadores atualmente, bem como o que deve
ser levado em consideração para escolha do uso de uma em detrimento da outra. Isso
porquê ambas possuem seus pontos positivos e negativos.

2.8.1 Processadores convencionais e Processamento gráfico (GPGPU)

O paradigma de programação de uso geral, GPGPU, do inglês General purpose
GPU Computing é claramente um expoente em termos de processamento de dados em
pesquisas recentes. Isso porque esses dispositivos, que normalmente são utilizados
para processamento gráfico, possuem centenas ou milhares de núcleos de processa-
mento, principalmente em dispositivos mais recentes. Comparativamente às unidades
de processamento convencionais, as CPUs, para alguns casos o ganho de desem-
penho chega a ser de 1000x com a utilização de uma GPU (GREGG; HAZELWOOD,
2011) (ROSENBAND; ROSENBAND, 2009). É claro que isso varia de aplicação para
aplicação, e não há uma regra geral. Por exemplo, para compressão de vı́deos, alguns
trabalhos recentes apresentam bons resultados com o uso de GPU (KATSIGIANNIS;
DIMITSAS; MAROULIS, 2015).
Em termos de armazenamento de dados não há muitos trabalhos recentes que utili-
zem GPU (AL-KISWANY et al., 2008) (ZHAO et al., 2016) (SOBE, 2012), porém os
mesmos apresentam alguns resultados interessantes. No entanto, há algumas outras
argumentações que levam em consideração limitações das interfaces PCI - Interco-
nector de Componentes Periféricos, do inglês Peripheral Component Interconnect, de
tal forma a mostrar que quando o problema a ser tratado leva em consideração uma
grande quantidade de dados e uma quantidade não tão significativa de processamento,
nem sempre uma GPU é a melhor opção (GREGG; HAZELWOOD, 2011). Da mesma
forma que para as tecnologias de disco, a escolha entre CPU é GPU é dependente do
projeto, e não há um consenso geral para o uso exclusivo de uma das duas tecnologias.

2.9 Algoritmos de Caching

Técnicas de caching aplicadas a armazenamento de dados permitem uma me-
lhora na disponibilidade do que está armazenado, por meio da criação de cópias locais
em dispositivos de armazenamento próximos. Com a estratégia do redirecionamento


23

das requisições para suas cópias mais próximas é possı́vel reduzir o tempo de resposta
e mesmo o consumo da banda de rede. Por esse motivo essas técnicas tem sido fre-
quentemente utilizadas, principalmente para sistemas peer-to-peer, que são totalmente
descentralizados. Uma das aplicações mais comuns é em serviços de transmissão
como o streaming de vı́deos (LAKSHMI; KUMAR; VENKATACHALAM, 2015).
Dentre os algoritmos de caching existentes, é bastante comum o uso do LRU, do
inglês Least Recently Used, possivelmente uma das técnicas de caching mais fáceis de
implementar, que cria uma lista dos itens solicitados e remove progressivamente da lista
aqueles dados que não foram requisitados dentro de um certo perı́odo de tempo. Os
dados da lista geralmente costumam ficar salvos em uma mı́dia de acesso mais rápido,
como a memória principal. Outra técnica também bastante comum é a LFU, do inglês
Least Frequently Used, que ao longo do tempo substitui o que está armazenado na área
de acesso mais rápido com base na frequência em que os dados são acessados (LI
et al., 2014). Existe, no entanto, uma terceira técnica cujo desempenho é superior a
esses dois algoritmos, porém de implementação significativamente mais complexa,
denominada de ARC - Adaptive replacement cache.
A polı́tica ARC usa o histórico do conteúdo recentemente removido do cache para
mudar de forma dinâmica suas caracterı́sticas de recência ou frequência. Este algo-
ritmo é, portanto, uma combinação das estratégias LRU e LFU. Em mais detalhes, a
polı́tica ARC divide o cache em duas partes, T1 e T2. T1 armazena os dados que só
foram acessados pela primeira vez, e T2 armazena em cache os dados que foram
acessados muitas vezes. Assim, T1 representa os dados recentemente acessados e
T2 os frequentemente acessados. Além disso, também são mantidas outras duas listas,
B1 e B2, que servem apenas para armazenar os meta-dados referentes às remoções
mais recentes feitas em T1 e T2 , respectivamente. As caracterı́sticas do cache podem
então ser ajustadas com base nos históricos obtidos nas listas Bi para modificar os
parâmetros de remoção das listas Ti dinamicamente. Dessa forma é possı́vel detectar
padrões de acesso ou mesmo de transferência de dados na rede que possam ser
revertidos em melhora na polı́tica de cache geral (RAIGOZA; SUN, 2014). Trabalhos
anteriores da literatura demonstraram as melhoras na taxa de acerto do algoritmo ARC
em comparação com o LRU (MEGIDDO; MODHA, 2004), conforme é possı́vel observar
na Fig. 2.11, na qual a taxa de acerto do ARC fica próxima ao LRU apenas quando a
área de cache é definida com tamanhos maiores. O gráfico mostra que com um número
menor de páginas a taxa de acerto no ARC é sempre superior, então ele permite aos
projetistas variar mais a quantidade e o tamanho das páginas do cache para se adaptar
a cada ambiente de armazenamento.


24

Figura 2.11: Comparação da taxa de acerto do ARC versus o LRU (adaptado do
trabalho (MEGIDDO; MODHA, 2004)

2.10 Trabalhos Correlatos

Nesta seção, são apresentados alguns dos principais trabalhos encontrados na
literatura que utilizam o método de replicação, o método de códigos de correção de
erros, ou ambos, para propor arquiteturas de armazenamento distribuı́do de dados.

2.10.1 CAROM - Cache A Replica On Modification

O trabalho que propõe a arquitetura CAROM (MA et al., 2013) foi o primeiro da
literatura a sugerir o uso combinado de replicação e de códigos de correção de erros.
O contexto do trabalho foca em ambientes em Nuvem, e os testes foram realizados
a nı́vel de datacenter. Há uma estratégia de caching implementada, a qual utiliza o
algoritmo LRU. Essa estratégia de caching é feita também a nı́vel geral, por datacenter,
e utiliza a memória RAM como forma de acesso mais rápido. A arquitetura utilizada é
centralizada, assim como a forma que o cache fica disponı́vel.


25

2.10.2 MICS - Mingling Chained Storage

O trabalho que propõe a arquitetura MICS (TANG et al., 2015) é mais recente, e
se baseia em parte no trabalho anterior da arquitetura CAROM, porém com algumas
diferenças notáveis. Utiliza um modelo de gerenciamento com múltiplos mestres e
propõe o armazenamento na forma de objetos, além de possuir como uma das princi-
pais contribuições a criação de uma função de UPDATE para os objetos armazenados.
Normalmente essa função depende de remover o objeto e recriá-lo novamente, pois
não existe atualização direta. O armazenamento dos dados é realizado inteiramente em
discos rı́gidos magnéticos, e a codificação dos dados é feita utilizando processadores
convencionais.

2.10.3 HRSPC - Hybrid Redundancy Scheme Plus Computing

O trabalho que propõe a arquitetura HRSPC (LI et al., 2016) é mais focado em
melhorar diretamente alguns as aspectos de códigos de correção de erros de modo
a mesclá-los num algoritmo misto ao invés de usar as duas técnicas separadamente
como outros trabalhos. No entanto, isso torna o trabalho muito mais teórico do que
aplicado. Não são dados detalhes especı́ficos da arquitetura e, embora obtenha
bons resultados assim como outros trabalhos, não utiliza uma arquitetura peer-to-peer
explicitamente, mas sugere alguns conceitos nesse sentido. Também utiliza discos
rı́gidos magnéticos e processadores convencionais para armazenamento e codificação
dos dados, respectivamente.

2.10.4 Robot - Big data storage system based on erasure coding

O trabalho que propõe a arquitetura Robot (YIN et al., 2013) é focado apenas no
uso de códigos de correção de erros para armazenamento de dados, e ignora o uso de
replicação, o que segundo estudos recentes pode ser um erro (GRIBAUDO; IACONO;
MANINI, 2016). Contudo ainda apresenta bons resultados e propões uma mescla de
arquiteturas, pois em uma visão geral há claramente a figura dos computadores mestres,
que são aqueles responsáveis por codificar e decodificar os dados armazenados, além
de controlarem os metadados. Contudo numa segundo observação há também uma
rede peer-to-peer em anel de computadores que funcionam exclusivamente para
armazenar dados e não realizam nenhum processamento adicional.

2.10.5 HDFS-Xorbas - a module for erasure code in HDFS

O trabalho que propõe a arquitetura HDFS-Xorbas (SATHIAMOORTHY et al.,
2013) é baseado no sistema de arquivos distribuı́do HDFS - Hadoop Distributed File


26

System (BORTHAKUR, 2008). Por esse motivo, a arquitetura é semelhante a desse
sistema de arquivos, que é do tipo mestre-escravo. A principal contribuição do trabalho
é fornecer um esquema de códigos de correção de erros para o HDFS, que a princı́pio
usa apenas replicação em três vias. Com isso, propõem um novo tipo de código
e o implementam de forma integrada a essa tecnologia previamente existente, com
bons resultados, porém ainda força o uso de códigos ou replicação, e não ambos em
conjunto.

2.10.6 Análise dos trabalhos correlatos

Uma representação comparativa entre os principais trabalhos encontrados na li-
teratura em armazenamento de dados foi realizada por meio do destaque dos principais
aspectos arquiteturais de cada um deles. Na Tabela 2.1 é exposta essa representação
comparativa. É válido destacar, com relação aos seis aspectos arquiteturais analisados
em cada trabalho, a ausência de qualquer mecanismo de cache na maioria deles. Ao
mesmo tempo, há um padrão seguido por todos em termos de metodologias e tecnolo-
gias de estruturação, armazenamento e processamento dos dados. Adicionalmente,
todos os trabalhos se mostram dependentes de alguma forma a centralizações em
suas arquiteturas, como esperado em designs do tipo mestre-escravo.

Tabela 2.1: Comparação entre os trabalhos correlatos
aaaaaaaaaaaa

Aspectos
arquiteturais

Nome do
trabalho CAROM MICS HRSPC Robot HDFS-Xorbas

Redundância R/EC R/EC R/EC EC EC
Estruturação OS OS OS OS OS
Design ME ME ME/P2P ME/P2P ME
Armazenamento HDD HDD HDD HDD HDD
Processamento CPU CPU CPU CPU CPU
Cache LRU - - - -

R = replicação; EC = erasure coding; OS = object storage; ME = mestre-
escravo.

2.11 Considerações Parciais

Neste capı́tulo foram apresentados os conceitos mais importantes que envolvem
a área de armazenamento de dados e, ao final, foi feita uma apresentação dos principais
trabalhos do estado-da-arte. O foco dos trabalhos estudados foi a tolerância a falhas e a
garantia de redundância dos dados armazenados. Para cada tecnologia ou metodologia
apresentada foram descritas as suas principais caracterı́sticas, em que também se


27

exibem as vantagens e desvantagens que devem ser levadas em consideração de
acordo com os compromissos que cada projeto deseja alcançar. No encerramento
deste capı́tulo foi possı́vel apresentar uma análise comparativa entre os trabalhos
correlatos, com destaque para seis dos principais aspectos de interesse para uma
arquitetura de armazenamento distribuı́do.


CAPÍTULO 3 – Armazenamento P2P com tolerância a falhas hı́brida e sistema
de cache

3.1 Considerações iniciais

Neste capı́tulo está descrita a arquitetura proposta, que recebe o nome de
Griddler. O nome advém de um quebra-cabeças matemático de reconstrução de
imagens, em que algumas sequências de números são utilizadas como base para
redefinir desenhos simples a partir de um espaço inicialmente vazio. A ideia desse
quebra-cabeça, e o nome utilizado, lembra que esta é uma arquitetura como foco
principalmente em tolerância a falhas, ou seja: recuperar informações a partir de dados
redundantes. A arquitetura proposta difere das demais, principalmente por ser peer-to-
peer e utilizar um mecanismo diferenciado de cache distribuı́do. A implementação foi
realizada inteiramente nas linguagens C e C++ e conta hoje com mais de 3000 linhas
de código.

3.2 Descrição e requisitos do ambiente distribuı́do

Inicialmente supõe-se para a arquitetura proposta um ambiente com quaisquer
n computadores em rede. É necessário que cada um destes computadores possua
um endereço IP único e consiga se comunicar com os demais, muito embora num
primeiro momento não tenham qualquer ligação lógica e atuem de forma independente.
Não há restrições quanto a hardware especializado necessário em cada computador
para o funcionamento do software da arquitetura Griddler, mas se recomenda o uso de
processadores recentes quando possı́vel, o que será explicado em seções posteriores
desse capı́tulo. Dado esse ambiente inicial, é preciso inicializar então os mecanismos
que possibilitam que os n computadores se configurem em nós de um ambiente de
armazenamento integrado.
A primeira tarefa a ser realizada é utilizar alguma estratégia para gerar um GUID -
Globally Unique Identifier, identificador global único, para cada um dos nós da rede.
Isso é necessário pois permite aos clientes de software acessarem os dados armaze-
nados ao buscá-los exatamente em cada um dos nós em que estiverem armazenados,
sem possibilidade de conflitos. No caso da Griddler, o algoritmo utiliza a cifra SHA-
1 (EASTLAKE; JONES, 2012), uma técnica de hashing que é relativamente simples,
possui diversas implementações, e produz um valor de dispersão de 160 bits com
40 caracteres, o que é um valor razoável pois permite que coexistam 2160 nós com
GUID diferentes na rede simultaneamente. Além disto, o algoritmo SHA-1 possui tempo
de execução reduzido comparativamente a outros algoritmos, conforme é possı́vel
observar na Figura 3.1. No caso da arquitetura proposta esse valor é gerado com

28


29

base no endereço IP de cada nó, que por definição também é único a cada computador.

Figura 3.1: Comparação do tempo de execução da cifgra SHA-1 e outros algoritmos,
adaptado de (MAQABLEH, 2011).

Mesmo com identificadores, os nós inicialmente não tem ligação nenhuma uns
com os outros. O primeiro fator considerado na arquitetura Griddler segue um padrão
de referência para qualquer sistema P2P, e trata da existência de mecanismos que
permitam organizar uma rede de computadores que inicialmente não tem essa ligação
lógica. Por ser um ambiente totalmente descentralizado, não existe a figura de um con-
trolador central, de modo que o gerenciamento é distribuı́do entre todos os membros da
rede. A Griddler implementa uma estrutura baseada em um dos protocolos existentes
para gerenciamento de ambientes P2P, o protocolo Chord (STOICA et al., 2003), que
apesar de ter sido proposto há algum tempo ainda é muito utilizado em trabalhos
recentes (LI; GUO; FRANZINELLI, 2015) (JEDDA; MOUFTAH, 2015). Para facilitar o
gerenciamento e as buscas, esse protocolo realiza suas operações por meio de uma
estrutura chamada de tabela de hashing distribuı́do, do inglês distributed hashing table,
DHT, que será detalhada nas próximas seções.
Por definição do protocolo Chord, após devidamente identificados, os nós devem num
segundo momento ser abstraı́dos logicamente para uma estrutura em rede do tipo anel,
ou seja, tratados como se estivessem em um cı́rculo e ordenados pelo seu GUID. Como
os valores gerados pela função de hashing, a princı́pio, não podem ser comparados


30

diretamente para determinar qual é maior, foi necessário implementar uma função de
conversão para um valor decimal (mod 2160) de modo que o anel possa ser gerado.
Essa é uma etapa preliminar essencial para a arquitetura proposta, e está representada
na Figura 3.2. Para conversão de uma cifra para um valor inteiro, é feito um cálculo
baseado nos números inteiros existentes na sequência SHA-1 e por meio da atribuição
de valores inteiros aos demais caracteres. De forma simplificada, após ter efetivamente
construı́do essa ligação lógica, a rede tem a aparência semelhante a da Figura 3.3.
A ligação é dita lógica pois não existe fisicamente, mas é uma topologia definida em
software com base nos GUID de cada nó, cuja ordenação influencia posteriormente
em todas as operações do sistema distribuı́do.

Figura 3.2: Geração de GUID para cada um dos nós da rede


31

Figura 3.3: Geração da rede peer-to-peer em anel

Adicionalmente, foi desenvolvida uma representação dos componentes em alto
nı́vel do ambiente proposto. Este modelo é ilustrado na Figura 3.4, e retrata os módulos
existentes em cada um dos nós de uma rede na arquitetura desenvolvida. É possı́vel
observar que o usuário consegue interagir com o sistema de armazenamento através
de um cliente de linha de comando simples ou através do protocolo HTTP em um
navegador web comum. O módulo de hashing é usado tanto na leitura quanto na
escrita de dados, e por isso a área de cache e o armazenamento local são ligados a
ele. Adicionalmente, existem módulos auxiliares que são utilizados para monitoramento
do status dos nós na rede, para codificação dos dados antes de serem armazenados
e para gerir a comunicação com os demais nós da rede. Cada peer da rede Griddler
possui essas mesmas funções e interage com os demais na rede em anel conforme
o necessário para solicitar ou inserir dados e seus metadados. A comunicação entre
os nós é totalmente realizada via protocolo HTTP, por meio do mesmo servidor web
disponı́vel a usuários externos.

Nas seções seguintes são apresentadas as operações mais comuns e impor-
tantes, que são: inserção, o equivalente a função PUT, busca, o equivalente a função


32

Figura 3.4: Modelo em alto nı́vel de um dos nós da rede Griddler

GET, remoção, o equivalente a função DELETE, e atualização, o equivalente à função
UPDATE na arquitetura proposta. Também será detalhado o funcionamento básico
de inserção e remoção de nós na Griddler, em particular em termos de resposta a falhas.

3.3 Tabela de roteamento

Essa estrutura tem função central na Griddler, bem como no protocolo Chord
para gerenciamento dos dados em ambiente peer-to-peer. Trata-se de uma tabela
extra que é armazenada em memória RAM. O tamanho dessa tabela é uma decisão de
projeto, e depende da implementação de cada arquitetura. Para a Griddler é utilizado o
valor máximo de 9, mas esse tamanho pode ser customizado se for necessário. Ele
indica uma certa quantidade de rotas, ou endereços IP e GUIDs de nós de armazena-


33

mento, que ficam registrados em cada nó n. O primeiro item dessa tabela é sempre o
endereço do nó imediatamente na sequência do nó n na rede em anel. Para cada item
i adicional, a tabela armazena o endereço do nó (n+2i−1(mod2160)) na sequência do
nó n. A operação em módulo apenas indica que os cálculos devem ser realizadas para
números no formato gerado pelo algoritmo SHA-1. Ou seja, para 4 entradas, a tabela
do nó 0 ficaria conforme é apresentado na Tabela 3.1.

Tabela 3.1: Tabela de roteamento do nó 0 do ambiente P2P

Finger table
1 Endereço IP do nó 1 (0+21−1(mod2160))
2 Endereço IP do nó 2 (0+22−1(mod2160))
3 Endereço IP do nó 4 (0+23−1(mod2160))
4 Endereço IP do nó 8 (0+24−1(mod2160))

Ter esse conhecimento localmente é importante pois quando um nó recebe uma
requisição de busca com base em um GUID de objeto, ainda que o próprio nó não
tenha esse objeto salvo, conseguirá determinar qual nó da sua tabela de roteamento
contém ou está mais próximo do local em que o objeto está de fato armazenado. Isto
porque tanto os identificadores dos nós quanto dos próprios objetos armazenados
são ambos gerados a partir da mesma cifra, e o protocolo Chord busca distribuir os
objetos armazenados de forma a aproximar nós e objetos com identificadores próximos.
Por exemplo, caso existam um nó com identificador 1 e outro com identificador 8 na
rede, um objeto com identificador 7 tem maior chance de ser salvo no nó 8. Com
a utilização da tabela de roteamento a busca se torna mais eficiente, visto que foi
determinado que, com alta probabilidade, o número máximo de buscas por meio dessa
estratégia em um rede com n nós se encontra na ordem de O(logn) (STOICA et al.,
2003). Essa mesma estratégia pode ser utilizada na inserção de dados para chegar ao
nó de armazenamento adequado para um determinado GUID de objeto. Na Figura 3.5
é possı́vel observar como ficam definidas as ligações pela tabela de rotas, de modo que
o nó 0 conhece as rotas para os nós 1, 2, 4 e 8. Dessa forma, uma requisição ao nó 0
de um objeto que se encontra em um desses outros nós será facilmente redirecionada.
Caso nenhum desses nós armazene o objeto solicitado, ainda assim pelo menos um
deles saberá qual nó armazena o objeto ou qual outro nó estaria mais próximo dos
dados requisitados. No melhor dos casos o nó que recebeu a requisição inicial será
coincidentemente o responsável por armazenar o objeto solicitado e a resposta será
imediata, mas no pior caso deverá passar por todos os nós da rota até que seja recebido
algum retorno para a requisição.


34

Figura 3.5: Rede com indicativos da tabela de roteamento do nó 0

3.4 Inserção de um novo nó

Nesta seção são apresentados os métodos de inserção de um nó na rede em
cada um dos casos possı́veis. Neste momento ainda se trata mais de organização do
hardware, de modo que as operações a seguir não influenciam nos dados previamente
armazenados no sistema.

3.4.1 Inserção quando não existem outros nós na rede

Quando não existem outros nós na rede Griddler, significa que o sistema precisa
ser inicializado. A inserção de um nó depende da execução em plano de fundo do
software implementado no nó que se deseja inserir na rede em anel. Para todos
os efeitos, os exemplos a seguir consideram inicializações feitas para nós da rede
baseados no sistema operacional Linux. Na Figura 3.6 segue o exemplo de uma
inicialização do software cliente no primeiro nó da rede. Os parâmetros da execução
são, em ordem, o endereço IP da interface de rede a ser associada com o serviço, a
porta a ser associada com o serviço, um diretório local para ser utilizado para responder
a requisições HTTP e o algoritmo de cache a ser utilizado. Esse último existe pois a


35

Griddler possui implementados tanto o algoritmo de caching adaptável, ARC, quanto o
algoritmo LRU, para fins de comparação.

root$ ./griddler 192.168.56.56 8000 $(pwd)/.webserver arc

--------------------------------------------------

Servico esta executando em http://192.168.56.56:8000

--------------------------------------------------

+--------------------------------------------------------+

| Bem-vindo! |

| |

| Lista de operacoes: \__ __/ |

| /_/ /\ \_\ |

| 0) STATUS __ \ \/ / __ |

| 1) PUT \_\_\/\/_/_/ |

| 2) GET __/\___\_\/_/___/\__ |

| 3) DELETE \/ __/_/\_\__ \/ |

| 4) SAIR /_/ /\/\ \_\ |

| __/ /\ \__ |

| \_\ \/ /_/ |

| / \ |

| GRIDDLER |

| 1.0 |

+--------------------------------------------------------+

---> 0

#######################################################

GRIDDLER em 192.168.56.56:8000

<NO: 478, PREDECESSOR: 478, SUCESSOR: 478>

Fingers Table: [478, 478, 478, 478, 478, 478, 478, 478, 478]

#######################################################

Figura 3.6: Primeiro nó de uma rede na arquitetura Griddler

É interessante notar que cada nó armazena informações sobre seu predecessor
e sucessor, que numa rede com um único nó inicialmente correspondem a esse mesmo
nó. O mesmo é válido para a tabela de roteamento, que apresenta repetições num
primeiro momento pois não existem nós suficientes na rede para preencher seus ı́ndices
adequadamente. O diretório passado por parâmetro para responder requisições HTTP
é utilizado pois não é necessário interagir com a Griddler apenas por meio desse cliente
simplificado. Foi implementado um servidor web integrado que permite que aplicações
se conectem por meio do protocolo HTTP e que usuários interajam com a arquitetura
em um navegador web comum.


36

3.4.2 Inserção quando existem outros nós na rede

Neste caso a operação de inserção acontece quando um nó é inserido na rede,
mas existem outros nós conectados em anel. Inicialmente os demais peers não tem
como tomar conhecimento da existência desse novo nó, de modo que cabe a esse
novo nó explicitamente solicitar a entrada na rede P2P. Essa solicitação pode ser feita
a qualquer um dos peers da rede.
O peer que recebeu a solicitação auxilia em seguida na criação de um GUID a ser
atribuı́do ao novo nó, com base no endereço IP do mesmo. Também com base no GUID,
o peer da rede que recebeu a solicitação envia um aviso ao peer mais adequado para
preceder o novo nó, de modo a manter a rede ordenada com base nos identificadores
inteiros. O peer que agora precederá o novo nó compartilha uma cópia de sua própria
tabela de roteamento local, que servirá para que o novo nó crie uma nova tabela de
roteamento. Por fim, os peers da rede recalculam suas rotas conforme o necessário.
Dessa forma a rede é reconfigurada. Espera-se que o novo nó entre na rede com
uma quantidade significativa de espaço de armazenamento livre. Por esse motivo, foi
implementado um mecanismo de migração automática de dados, transferindo para
o novo nó alguns objetos que estavam armazenados em outros pontos da rede. Na
Figura 3.7 é possı́vel perceber de forma mais visual essas etapas, as quais estão
devidamente implementadas no ambiente desenvolvido.

Figura 3.7: Representação das etapas a serem realizadas para inserção de um novo
nó


37

Em contraste à inicialização com apenas um nó, o software cliente neste caso
deve ser inicializado com um parâmetro a mais, o parâmetro join. Em tempo de
compilação é definida uma variável condicional para uma referência ao backbone, que
é o nó utilizado como ponte para a rede principal da Griddler, e quando executado com
o parâmetro join o novo nó buscará na rede esse nó referência da rede principal e
solicitará sua inclusão. Em comparação com o exemplo anterior, em que foi adicionado
um único nó, o próximo nó da rede tem configurações semelhantes ao exemplo da
Figura 3.8.

root$ ./griddler 192.168.56.2 8000 $(pwd)/.webserver arc --join

...

...

...

#######################################################

GRIDDLER em 192.168.56.2:8000

<NO: 178, PREDECESSOR: 478, SUCESSOR: 478>

Fingers Table: [478, 478, 478, 478, 478, 478, 478, 478, 478]

#######################################################

Figura 3.8: Segundo nó de uma rede na arquitetura Griddler

3.5 Remoção de um nó

Nesta seção são apresentados os métodos de remoção de um nó na rede em
cada um dos casos posssı́veis. Neste momento ainda se trata mais de organização do
hardware, de modo que as operações a seguir não influenciam nos dados anteriormente
armazenados no sistema.

3.5.1 Remoção prevista pelos usuários

É possı́vel que em algum momento seja necessário remover um nó da rede de
forma planejada. Por exemplo, para fazer alguma atualização em um equipamento, ou
mesmo manutenção de qualquer tipo. Nestes casos, é possı́vel remover o nó da rede
acionando a função de saı́da do software cliente.


38

De forma semelhante ao processo de entrada de um novo nó, o que acontece nestes
casos de encerramento, por meio dessa função, é que o nó que está de saı́da redistribui
todos os objetos armazenados a partir de solicitações aos demais nós da rede. Antes
disso envia alertas a seu sucessor e predecessor diretos e, após redistribuir todos
os objetos de dados o software cliente é encerrado e o vı́nculo lógico é desfeito. Ao
mesmo tempo os antigos sucessor e predecessor do nó que deixou a rede cuidam de
atualizar suas próprias tabelas de roteamento e avisam os demais nós restantes da
saı́da que ocorreu.

3.5.2 Remoção devido a falhas e imprevistos

O processo de falha imprevista é um pouco mais complicado de tratar do que
uma remoção planejada. Na Griddler é proposto o uso de uma estratégia de probing,
ou verificação, para esse tipo de situação. Isso significa que circulam na rede diversas
mensagens, enviadas constantemente e utilizadas como indicativo de estado dos nós.
Cada peer fica responsável por monitorar seu sucessor imediato na rede em anel.
Ou seja, o peer 6 monitoraria o peer 7 e o peer 7 monitoraria o peer 8, e assim
sucessivamente. Dessa forma, quando qualquer nó falhar, seu predecessor imediato é
que toma conhecimento da ausência do nó e fica responsável por iniciar os processos
de reconstrução.
A reconstrução dos dados não precisa ser imediata, mesmo com a inserção de um novo
nó na rede no lugar daquele que ficou com falha, dado que as técnicas de replicação
e códigos de correção de erros por si só são suficientes para garantir o acesso aos
dados mesmo diante de algumas indisponibilidades. Por esse motivo, no momento a
Griddler não conta com um mecanismo automatizado de reconstrução, de modo que
um nó apenas avisa os demais quando percebe a falha de outro e o que é feito é tão
somente a atualização das tabelas de roteamento. Ao mesmo tempo, o que ocorre na
Griddler é que na próxima operação de atualização de um determinado objeto de dados
o sistema automaticamente recria as cópias perdidas, por replicação ou codificação,
decorrentes de possı́veis falhas dos nós. Dessa forma, os dados são eventualmente
recriados e se evita sobrecargas desnecessárias de processamento e rede no sistema,
principalmente quando as falhas são frequentes.

3.6 Operações básicas de interação com o sistema

Nesta seção, são apresentados os métodos de interação com os dados dis-
ponı́veis na arquitetura desenvolvida. As operações implementadas e descritas a seguir
representam o essencial para sistemas de armazenamento de dados: escrita, leitura,
remoção e atualização das informações.


39

3.6.1 Inserção de dados na forma de objetos

A inserção de dados na arquitetura proposta segue os mesmos princı́pios do
algoritmo Chord para sistemas P2P, o qual foi mencionado anteriormente, com uma
alteração que é exclusiva deste projeto. A operação proposta tem a estrutura de uma
tripla com o seguinte formato:

PUT(chave, valor, r)

No qual a chave é também um GUID, ou OID, gerado a partir do arquivos com base na
mesma técnica de hashing, SHA-1. Ou seja, da mesma forma, é possı́vel haver até
2160 objetos armazenados no sistema ao mesmo tempo. O parâmetro valor representa
os dados que se deseja armazenar. O único diferencial acrescentado pela arquitetura
Griddler que não faz parte da definição original do algoritmo Chord é o parâmetro r,
que é um valor inteiro. O parâmetro r apenas define o tipo de redundância desejado,
que no momento pode ser de três tipos:

• valor 0, para nenhuma redundância

• valor 1, para redundância por meio de replicação em 3 vias

• valor 2, para redundância por meio de um código MDS do tipo Liberation com
parâmetros (6,2)

Na verdade ainda se pensa em trabalhar com maiores variações nesses parâmetros,
mas as funções básicas atualmente são essas três. A escolha dos parâmetros do
código utilizado se baseia na garantia da mesma redundância que a replicação em 3
vias, ou seja, até duas falhas simultâneas de nós de armazenamento. Os parâmetros
de codificação, no entanto, podem ser alterados a qualquer momento conforme o
necessário. A inserção na verdade é a operação mais simples quando não há nenhuma
redundância, pois é a forma como foi prevista no algoritmo original. O que ocorre é que,
após o cálculo do GUID do objeto de dados que se deseja armazenar, esse objeto é
diretamente mapeado ao nó cujo GUID seja imediamente superior a esse valor. Ou
seja, se convertidos em uma base decimal para facilitar a compreensão, o desenho
da rede com alguns objetos inseridos se assemelha com o da Figura 3.9, em que se
destaca a aproximação de nós e objetos com identificadores próximos.

A única diferença quando se acrescenta alguma outra técnica de redundância
é que os dados redundantes também são salvos na forma de objetos em outros nós
da rede. Por exemplo, no caso da replicação em três vias, o objeto original é salvo
em um dos nós de acordo com seu GUID, e duas outras cópias são salvas em outros
nós quaisquer da rede da rede em anel, de acordo com o GUID gerado para eles. É


40

Figura 3.9: Rede com alguns objetos inseridos

importante ressaltar, no entanto, que esses dados redundantes não carregam consigo
o GUID do arquivo original, independente se o tipo de redundância for por meio de
replicação ou de códigos de correção de erros, visto que se tratam de chaves diferentes.
Por exemplo, para replicação, supondo um objeto original com o nome imagem1, os
objetos redundantes são imagem1 c1, imagem1 c2 e imagem1 c3. Conforme será
visto para a busca, quando um programa cliente solicita o acesso a um determinado
objeto o sistema sempre é direcionado ao local no qual a primeira cópia desses dados
se encontra, que é a parte mais difı́cil da busca. Somente se essa cópia não estiver
disponı́vel é que o acesso parte para as informações redundantes, porém é sabido que
estas informações estão em um ou mais dos nós da sequência na rede em anel.

3.6.2 Busca de dados na forma de objetos

A busca dados na arquitetura proposta segue os mesmos princı́pios do algo-
ritmo Chord para sistemas P2P, o qual foi mencionado anteriormente, com algumas
alterações exclusivas desse projeto. A operação proposta tem o seguinte formato:

GET(chave)


41

A solicitação de busca, assim como a de inserção, pode partir de qualquer um dos
nós. Portanto, a solução trivial é percorrer sequencialmente todos os nós do anel até
encontrar aquele que armazena o objeto com o GUID buscado. Contudo, à medida
em que o número de nós cresce, esse tipo de busca se torna mais e mais ineficiente.
Assim, no trabalho proposto, a busca de dados utiliza uma estrutura auxiliar em cada
um dos nós, denominada de finger table, ou routing table, que é uma tabela indicativa
do roteamento necessário para se chegar a um determinado objeto.

3.6.3 Remoção de dados na forma de objetos

A remoção de dados na arquitetura desenvolvida busca remover sequencial-
mente todos as possı́veis versões, redundantes ou não, do objeto que esteja armaze-
nado no sistema distribuı́do. A operação implementada tem o seguinte formato:

DELETE(chave)

Como não há nenhuma forma de gerenciamento que informe se um determinado
objeto está armazenado com única cópia, várias cópias ou mesmo codificado, é
preciso verificar todos esses casos para removê-lo efetivamente. Dessa forma a
função de remoção implementada na arquitetura desenvolvida solicita aos demais
peers a remoção de quaisquer versões do objetos possam existir. Essas requisições se
espalham pelo sistema distribuı́do, e ao final o usuário tem como resposta que todas
as versões do objeto foram devidamente removidas.

3.6.4 Atualização de dados na forma de objetos

A atualização dos dados é uma operação semelhante à de inserção, salvo que
consiste em inserir uma nova versão de um objeto previamente inserido. Na arquite-
tura Griddler essa operação é feita como uma combinação das demais operações. É
possı́vel remover o objeto antigo e reinseri-lo, inclusive com outro nı́vel de redundância.
Porém, a operação de inserção por padrão sobrescreve objetos existentes para uma
determinada chave caso existam.
Dessa forma, dado que exista um objeto codificado no sistema, por exemplo um vı́deo
com a chave de identificação “vı́deo1”, inserir um novo “vı́deo1” por meio de codificação
vai sobrescrever a versão antiga. Contudo, se o vı́deo estivesse replicado, seria ne-
cessário removê-lo para somente após essa etapa inseri-lo novamente com codificação.
Da mesma forma, inserir uma nova versão com replicação de um objeto anteriormente
inserido com replicação irá sobrescrever a versão antiga automaticamente. É ne-


42

cessário remover a versão antiga somente quando se alterna o tipo de redundância
desejada.

3.7 Mecanismo de caching distribuı́do com estratégia ARC

A Griddler implementa um mecanismo de caching distribuı́do por meio da
utilização do algoritmo adaptável ARC, Adaptive Replacement Cache, em detrimento
dos algoritmos mais comuns LRU e LFU. Nos estudos encontrados na literatura não
houveram outros trabalhos que utilizem esse algoritmo em uma arquitetura P2P com
tolerância a falhas hı́brida. Contudo, alguns trabalhos sugeriram que uma estratégia
de cache pode trazer benefı́cios consideráveis a um sistema de armazenamento dis-
tribuı́do (MA et al., 2013) (TANG et al., 2015).
Cada um dos nós do sistema distribuı́do mantém localmente as tabelas descritas na
seção 2.9, que no caso do ARC são duas, uma para itens recentemente acessados
e outra para itens frequentemente acessados. Então do ponto de vista da Griddler o
que acontece é que cada nó, quando recebe uma requisição, primeiro tenta localizar o
objeto em seu sistema de cache local ao utilizar uma dessas duas listas, e somente se
não encontrar