“Dedupeer: um Algoritmo para Deduplicação de Arquivos
Através de Processamento Particionado”
Por
Paulo Fernando Almeida Soares
Dissertação de Mestrado
Universidade Federal de Pernambuco
[email protected]
www.cin.ufpe.br/~posgraduacao
RECIFE, JULHO/2013
Universidade Federal de Pernambuco
Centro de Informática
Pós-graduação em Ciência da Computação
Paulo Fernando Almeida Soares
“Dedupeer: um Algoritmo para Deduplicação de
Arquivos Através de Processamento Particionado”
Trabalho apresentado ao Programa de Pós-graduação em
Ciência da Computação do Centro de Informática da Universidade Federal de Pernambuco como requisito parcial para
obtenção do grau de Mestre em Ciência da Computação.
Orientador: Silvio Romero de Lemos Meira
Co-Orientador: Vinicius Cardoso Garcia
RECIFE, JULHO/2013
Catalogação na fonte
Bibliotecária Jane Souto Maior, CRB4-571
Soares, Paulo Fernando Almeida
Dedupeer: um algoritmo para deduplicação de arquivos
através de processamento particionado. / Paulo Fernando
Almeida Soares. - Recife: O Autor, 2013.
xvi, 100 f., il., fig., tab.
Orientador: Silvio Romero de Lemos Meira.
Dissertação (mestrado) - Universidade Federal de Pernambuco.
CIn, Ciência da Computação, 2013.
Inclui referências e apêndice.
1. Sistemas distribuídos. 2. Deduplicação de dados.
Silvio Romero de Lemos (orientador). II. Título.
004.36
CDD (23. ed.)
I. Meira,
MEI2014 – 007
Dissertação de Mestrado apresentada por Paulo Fernando Almeida Soares à
Pós-Graduação em Ciência da Computação do Centro de Informática da Universidade
Federal de Pernambuco, sob o título “Um Algoritmo para Deduplicação de Arquivos
Através de Processamento Particionado” orientada pelo Prof. Silvio Romero de
Lemos Meira e aprovada pela Banca Examinadora formada pelos professores:
______________________________________________
Prof. Vinicius Cardoso Garcia
Centro de Informática / UFPE
______________________________________________
Prof. Manoel Gomes de Mendonça Neto
Departamento de Ciência da Computação /UFBA
_______________________________________________
Prof. Rodrigo Elia Assad
Departamento de Estatística e Informática / UFRPE
Visto e permitida a impressão.
Recife, 28 de agosto de 2013.
___________________________________________________
Profa. Edna Natividade da Silva Barros
Coordenadora da Pós-Graduação em Ciência da Computação do
Centro de Informática da Universidade Federal de Pernambuco.
Eu dedico esta dissertação à minha tia Joarina (in
memorian) por todo o apoio e incentivo em meus estudos.
iii
Resumo
A deduplicação é uma técnica de compressão de dados sem perda que elimina dados
redundantes tanto intra-file como inter-file, diferente de ferramentas de compressão de
dados como o gzip que só eliminam a redundância intra-file. A deduplicação reduz a
necessidade de armazenamento através da eliminação de blocos de dados redundantes.
Na deduplicação, todos os blocos de dados que estão duplicados em um sistema de
armazenamento podem ser reduzidos à uma única cópia, esses blocos desalocados pela
deduplicação são transformados em referência para o que foi mantido no sistema.
Técnicas de deduplicação começaram a ser estudadas para sistemas de armazenamento
comerciais em meados de 2004. Hoje, os principais sistemas de armazenamento de
dados usam deduplicação, mas os algoritmos implementados e as técnicas utilizadas
não são detalhadas publicamente. Existem alguns trabalhos acadêmicos focados na
implementação de algoritmos de deduplicação, mas eles são raros e não são voltados para
a sua utilização em sistemas de armazenamento existentes. O principal objetivo deste
trabalho é criar um algoritmo para deduplicação de arquivos no cliente de forma remota,
através de processamento particionado e utilizando comparação por fingerprints. Este
algoritmo foi incorporado em um componente de software com interface interoperável
para facilitar a utilização em qualquer sistema de armazenamento de dados e beneficiá-los
com economia de armazenamento, e na transferência de dados no caso dos sistemas de
armazenamento distribuídos.
Além do componente de software, foi desenvolvido também um sistema de armazenamento com gerenciamento de dados baseado no Apache Cassandra, o que o torna capaz
de ser distribuído, com o objetivo de validar o algoritmo de deduplicação. A integração do
componente de software com o sistema de armazenamento foi implementada e avaliada
neste trabalho.
Palavras-chave: Deduplicação, compressão de dados, economia de armazenamento,
sistemas de armazenamento de dados
iv
Abstract
The deduplication is a technique for lossless data compression that eliminates redundant data intra-file and inter-file, different data compression tools like gzip only eliminates
the redundancy intra-file. The deduplication reduces storage needs through eliminating
redundant blocks. In the deduplication, all data blocks or files that are duplicates in a
storage system are reduced to a solely copy, and the unallocated data are transformed in
reference to the data content maintained in the system.
Deduplication techniques began to be studied in mid-2004. Today, the main storage
systems use deduplication, but the algorithms implemented and the techniques used are
not detailed. There are researches focused in the implementation of algorithms, but they
are rare and the main goal not is the integration with the existing systems. The main
aim of this research is to create an algorithm to deduplication of files on the source with
remote data, through of the partitioned processing and using of fingerprint comparisons.
This algorithm was integrated in a software component with interoperable interface to
facilitate the using in any storage system and benefit them with storage economy, and in
the data transfer when the system was distributed.
Besides the software component was developed also a storage system with data
management made with the Apache Cassandra, which make it able to be distributed
with the goal to validate the deduplication algorithm. The integration of the software
component with the storage system was implemented and evaluated in this research.
Keywords: Deduplication, data compression, storage economy, storage systems
v
Agradecimentos
Primeiramente eu gostaria de agradecer ao meu orientador e co-orientador, Silvio
Meira e Vinicius Garcia, respectivamente, por toda a dedicação para me ajudar a tornar
possível a realização desse meu sonho.
Minha família, em especial para minha mãe e minha tia Joarina por todo o apoio e
incentivo que me deram nos meus estudos.
Meus amigos da Usto.re, Rodrigo Assad, Anderson Fonseca, Francisco Soares, Marco
Machado e Thiago Jamir por sempre estarem dispostos a me ajudar nos desafios técnicos
que enfrentei.
Todos os meus amigos do CIn, em especial para os mais presentes: Thiago Vieira,
Lenin Ernesto, Marco Machado, Jamilson Batista, Adriano Tito, Rodolfo Arruda, Dhiego
Abrantes, Francisco Airton, João Emanoel, Bruno Felipe e Kellyton Brito.
Eduardo Almeida pelo grande apoio, ajuda e conselhos.
Tassio Vale pelas conversas sobre o Mestrado e por me mostrar o quão bom seria
estudar na UFPE.
Rogério por me receber em seu apartamento nos meus primeiros meses no Recife.
Frederico Durão pela ajuda na estruturação da dissertação.
Minhas amigas forrozeiras, Natália, Dalyla, Ione, Anne e Ana Tereza, as pessoas mais
animadas de todo o Pernambuco.
E a todos os que contribuiram direta e indiretamente para que este trabalho fosse
realizado!
Muito obrigado!
vi
Lista de Figuras
1.1
2.1
2.2
2.3
Aumento da demanda e redução do custo de hardware de armazenamento
(gráfico baseado em Kaplan et al. [21]) . . . . . . . . . . . . . . . . . .
1
Armazenamento dos super-chunks nos nós [46]. . . . . . . . . . . . . .
Processo do algoritmo do FERAPARDA . . . . . . . . . . . . . . . . .
Exemplo da economia de espaço oferecida em um sistema de armazenamento com 20% de alteração nos dados. . . . . . . . . . . . . . . . . .
11
15
Diagrama de componentes de alto nível da biblioteca do Dedupeer . . .
Modelo de dados do sistema distribuído desenvolvido com o Cassandra
Visão de componentes e conectores do DeFS integrado com a biblioteca
do Dedupeer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
28
4.1
4.2
Desempenho na serialização dos dados [39] . . . . . . . . . . . . . . .
Desempenho na desserialização dos dados [39] . . . . . . . . . . . . .
42
43
5.1
5.2
5.3
Funcionamento do algoritmo 1. . . . . . . . . . . . . . . . . . . . . . .
Funcionamento do algoritmo 2 . . . . . . . . . . . . . . . . . . . . . .
Vantagem da utilização da carga extra de dados . . . . . . . . . . . . .
51
55
59
6.1
Tempo em milissegundos para as execuções da operação de armazenamento utilizando MD5 . . . . . . . . . . . . . . . . . . . . . . . . . .
Tempo em milissegundos para as execuções da operação de armazenamento utilizando SHA-1 . . . . . . . . . . . . . . . . . . . . . . . . .
Tempo em milissegundos para as execuções da operação de armazenamento, separadas por tamanho de chunk . . . . . . . . . . . . . . . . .
Tempo em milissegundos das execuções da operação de deduplicação,
separadas por tamanho de chunk, utilizando SHA-1 . . . . . . . . . . .
Tempo em milissegundos das execuções da operação de deduplicação,
separadas por tamanho de chunk, utilizando MD5 . . . . . . . . . . . .
Tempo em milissegundos das execuções da operação de deduplicação +
armazenamento, separadas por tamanho de chunk, utilizando SHA-1 . .
Tempo em milissegundos das execuções da operação de deduplicação +
armazenamento, separadas por tamanho de chunk, utilizando MD5 . . .
3.1
3.2
3.3
6.2
6.3
6.4
6.5
6.6
6.7
20
30
64
64
65
67
67
69
70
vii
LISTA DE FIGURAS
6.8
Tempo em milissegundos das execuções da operação de reidratação,
separadas por tamanho de chunk, utilizando SHA-1 . . . . . . . . . . .
6.9 Tempo em milissegundos das execuções da operação de reidratação,
separadas por tamanho de chunk, utilizando MD5 . . . . . . . . . . . .
6.10 Mapa de chunks deduplicados da versão 3.10-rc7 do código-fonte do
Kernel do Linux processado com os chunks da versão 3.9.8, para chunks
com tamanho 128, 64, 32, 16 e 8KB . . . . . . . . . . . . . . . . . . .
6.11 Tamanho em megabytes ocupado pelo arquivo no sistema, com a porcentagem de economia alcançada . . . . . . . . . . . . . . . . . . . . . .
6.12 Mapa de chunks deduplicados da máquina virtual Linux 12.10 atualizada
processada com os chunks da mesma máquina virtual sem atualização,
para chunks com tamanho 128, 64, 32, 16 e 8KB . . . . . . . . . . . .
71
71
72
74
74
C.1 Tempo emparelhado para a operação de armazenamento com chunks de
128KB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
C.2 Tempo emparelhado para a operação de armazenamento com chunks de
64KB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
C.3 Tempo emparelhado para a operação de armazenamento com chunks de
32KB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
C.4 Tempo emparelhado para a operação de armazenamento com chunks de
16KB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
C.5 Tempo emparelhado para a operação de armazenamento com chunks de
8KB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
C.6 Tempo emparelhado para a operação de deduplicação com chunks de
128KB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
C.7 Tempo emparelhado para a operação de deduplicação com chunks de 64KB
C.8 Tempo emparelhado para a operação de deduplicação com chunks de 32KB
C.9 Tempo emparelhado para a operação de deduplicação com chunks de 16KB
C.10 Tempo emparelhado para a operação de deduplicação com chunks de 8KB
C.11 Tempo emparelhado para a operação de deduplicação + armazenamento
com chunks de 128KB . . . . . . . . . . . . . . . . . . . . . . . . . .
C.12 Tempo emparelhado para a operação de deduplicação + armazenamento
com chunks de 64KB . . . . . . . . . . . . . . . . . . . . . . . . . . .
C.13 Tempo emparelhado para a operação de deduplicação + armazenamento
com chunks de 32KB . . . . . . . . . . . . . . . . . . . . . . . . . . .
90
91
91
92
92
93
93
94
94
95
95
96
96
viii
LISTA DE FIGURAS
C.14 Tempo emparelhado para a operação de deduplicação + armazenamento
com chunks de 16KB . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
C.15 Tempo emparelhado para a operação de deduplicação + armazenamento
com chunks de 8KB . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
C.16 Tempo emparelhado para a operação de reidratação com chunks de 128KB 98
C.17 Tempo emparelhado para a operação de reidratação com chunks de 64KB 98
C.18 Tempo emparelhado para a operação de reidratação com chunks de 32KB 99
C.19 Tempo emparelhado para a operação de reidratação com chunks de 16KB 99
C.20 Tempo emparelhado para a operação de reidratação com chunks de 8KB 100
ix
Lista de Tabelas
3.1
Força do consistência baseada nos níveis das operações [7] . . . . . . .
34
6.1
6.2
p-values para os dados capturados na operação de armazenamento . . .
Quantidade de chunks criados . . . . . . . . . . . . . . . . . . . . . .
66
73
x
Lista de Acrônimos
CPU Central Processing Unit
CTO Chief Technology Officer
DDR2 Double Data Rate
DE Delta Encoding
DeFS Dedupeer File Storage
DHT Distributed Hash Table
EPA Environmental Protection Agency
FBH Fixed Block Hashing
FIFO First In First Out
GSI Green Storage Initiative
GUI Graphical User Interface
HDFS Hadoop Distributed File System
I/O Input/Output
JXTA Juxtapose
MD5 Message-Digest Algorithm 5
NoSQL Not only SQL
P2P Peer-to-peer
RAM Random-Access Memory
RPC Remote Procedure Call
SAN Storage Area Network
SHA-1 Secure Hash Algorithm
SQL Structured Query Language
xi
LISTA DE TABELAS
SSD Solid State Drive
TI Tecnologia da Informação
VBH Variable Block Hashing
VDI Virtual Disk Image
xii
Sumário
Lista de Acrônimos
xi
1
.
.
.
.
.
.
1
3
4
4
5
6
6
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
8
8
9
9
10
12
13
13
14
14
16
17
17
17
18
18
19
20
21
O Dedupeer File Storage
3.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.1 Escopo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 O sistema de armazenamento distribuído . . . . . . . . . . . . . . . . .
22
22
22
23
2
3
Introdução
1.1 Motivação . . . . . . .
1.2 Definição do problema
1.3 Resultados esperados .
1.4 Escopo negativo . . . .
1.5 Contribuições . . . . .
1.6 Sumário . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Trabalhos relacionados
2.1 Sistemas de armazenamento de dados com foco em deduplicação
2.1.1 Trabalho de Kathpal et al. . . . . . . . . . . . . . . . .
2.1.2 Trabalho de Kaiser et al. . . . . . . . . . . . . . . . . .
2.1.3 Σ-Dedup . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.4 Dropbox . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.5 Conclusão sobre os sistemas com foco em deduplicação
2.2 Algoritmos para eliminação de redundância de dados . . . . . .
2.2.1 FERAPARDA . . . . . . . . . . . . . . . . . . . . . .
2.2.2 DYNABYTE . . . . . . . . . . . . . . . . . . . . . . .
2.2.3 Trabalho de Langille et al. . . . . . . . . . . . . . . . .
2.3 Deduplicação . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.1 Localização . . . . . . . . . . . . . . . . . . . . . . . .
Cliente (source) . . . . . . . . . . . . . . . . . . . . . .
Servidor (target) . . . . . . . . . . . . . . . . . . . . .
2.3.2 Momento . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.3 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . .
2.3.4 Benefícios . . . . . . . . . . . . . . . . . . . . . . . .
2.4 Sumário do capítulo . . . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
xiii
LISTA DE TABELAS
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
23
29
29
30
31
31
31
33
33
34
34
35
35
35
35
36
36
37
37
4
Componente para deduplicação em sistemas de armazenamento de dados
4.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Interoperabilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1 Interoperabilidade de comunicação através do Thrift . . . . . .
4.2.2 Comparação com o Protocols Buffer . . . . . . . . . . . . . . .
Protocols Buffer . . . . . . . . . . . . . . . . . . . . . . . . .
Comparação de desempenho . . . . . . . . . . . . . . . . . . .
4.2.3 Comparação por hash (fingerprints) . . . . . . . . . . . . . . .
Vantagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Sumário do capítulo . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
38
39
39
41
41
42
42
44
45
5
Os algoritmos
5.1 Fundamentos . . . . . . .
5.1.1 O algoritmo Rsync
Rolling checksum
5.1.2 Fingerprinting . .
46
46
46
47
48
3.3
3.4
3.5
3.2.1 Modelo de dados . . . . . . . . . . . . . . . . . . .
Visão de componentes e conectores . . . . . . . . . . . . .
O componente Dedupeer File Storage . . . . . . . .
O componente Dedupeer . . . . . . . . . . . . . . .
Decisões de projeto e considerações . . . . . . . . . . . . .
3.4.1 Tamanho do chunk . . . . . . . . . . . . . . . . . .
3.4.2 Cassandra para gerenciamento do armazenamento .
Tolerância à falhas . . . . . . . . . . . . . . . . . .
Recuperação de falhas . . . . . . . . . . . . . . . .
Consistência . . . . . . . . . . . . . . . . . . . . .
Disponibilidade . . . . . . . . . . . . . . . . . . . .
Empacotamento de requisições . . . . . . . . . . . .
3.4.3 Alternativa para o gerenciamento de armazenamento
Facilidade de instalação e manutenção . . . . . . . .
Clusters pequenos . . . . . . . . . . . . . . . . . .
3.4.4 Escalabilidade . . . . . . . . . . . . . . . . . . . .
O que é escalabilidade? . . . . . . . . . . . . . . . .
Escalabilidade com o Cassandra . . . . . . . . . . .
Sumário do capítulo . . . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
xiv
LISTA DE TABELAS
5.2
5.3
6
7
Detalhando os algoritmos . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1 Algoritmo para deduplicação com carga completa do arquivo na
memória . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.2 Algoritmo com deduplicação particionada . . . . . . . . . . . .
Sumário do capítulo . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Análise de desempenho
6.1 Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2 Análise de desempenho utilizando o código fonte do Kernel do Linux
Operação de armazenamento . . . . . . . . . . . . . . . . . .
Operação de deduplicação . . . . . . . . . . . . . . . . . . .
Operação de deduplicação + armazenamento . . . . . . . . .
Operação de reidratação . . . . . . . . . . . . . . . . . . . .
6.2.1 Mapa de chunks deduplicados . . . . . . . . . . . . . . . . .
6.3 Análise de economia utilizando máquinas virtuais . . . . . . . . . . .
6.4 O Ustore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.5 Sumário do capítulo . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
49
54
60
.
.
.
.
.
.
.
.
.
.
61
61
63
63
66
68
70
72
73
75
75
Conclusão
7.1 Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
77
78
Referências Bibliográficas
80
A Apêndice
A.1 Arquivo de definição dos serviços Thrift . . . . . . . . . . . . . . . . .
85
85
B Apêndice
87
B.1 Resultados da avaliação dos arquivos do código fonte do Kernel do Linux 87
C Apêndice
C.1 Gráficos dos tempos emparelhados por tamanho de chunk para a operação
de armazenamento . . . . . . . . . . . . . . . . . . . . . . . . . . . .
C.2 Gráficos dos tempos emparelhados por tamanho de chunk para a operação
de deduplicação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
C.3 Gráficos dos tempos emparelhados por tamanho de chunk para a operação
de deduplicação + armazenamento . . . . . . . . . . . . . . . . . . . .
90
90
93
95
xv
LISTA DE TABELAS
C.4 Gráficos dos tempos emparelhados por tamanho de chunk para a operação
de reidratação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Appendices
98
85
xvi
1
Introdução
Com o aumento da capacidade das unidades de armazenamento, aumentou também a
demanda por sua utilização. Em 2000, a estimativa da indústria era de um aumento anual
entre 50% a 100% dessa demanda [26], estimativa essa que se consolidou. Nos últimos
anos esse aumento atingiu um valor anual de mais de 50% [21].
A Figura 1.1 mostra dois gráficos com informações sobre demanda e preço do
armazenamento entre os anos de 2006 e 2011. Um deles demonstra o forte crescimento
da demanda por armazenamento nas empresas, e o segundo, exibe a queda de 20% ao
ano no preço por Gigabytes.
Figura 1.1 Aumento da demanda e redução do custo de hardware de armazenamento (gráfico
baseado em Kaplan et al. [21])
A indústria de TI passou a apostar em sistemas de armazenamento de dados distribuído
1
nos últimos anos. Empresas como Amazon1 , Google2 , Microsoft3 e Salesforce4 começaram a investir em centros de armazenamentos de dados na nuvem (Cloud Storages),
espalhados pelo mundo, com garantia de redundância e tolerância à falhas [47].
Com esse aumento da demanda por armazenamento, a utilização de técnicas de
compressão de dados se torna um fator chave para redução dos custos. A compressão
de dados é uma técnica que codifica informações, usando uma quantidade menor de
dados que a original, para economizar espaço de armazenamento. As técnicas mais
conhecidas de compressão de dados funcionam apenas com a compressão intra-file, ou
seja, utilizando no processamento apenas os bytes do arquivo a ser comprimido, como
exemplo, pode ser citado o formato de arquivo zip [32], que é um tipo de compressão
sem perda. E também existe a compressão intra-file com perda de dados, que é o caso
dos famosos formatos de arquivos jpg e mp3, o qual reduz a qualidade da imagem e do
áudio, respectivamente, para obter uma redução no espaço necessário para armazenar o
arquivo [35].
A deduplicação é um técnica de compressão sem perda que elimina dados redundantes
tanto intra-file quanto inter-file, o que possibilita utilizar dados remotos para ajudar na
compressão dos dados. Com a popularização dos sistemas de armazenamento distribuído
em nuvem, a deduplicação ajudará muito na economia de espaço de armazenamento, já
que ela pode utilizar informações em diferentes arquivo e entidades para economizar o
espaço utilizado no sistema. A deduplicação de dados é um técnica de compressão que
armazena uma única cópia de dados redundantes, eliminando as outras do sistema de
armazenamento. Ela pode ser feita em nível de arquivo completo ou de chunks, os quais
são blocos de dados pertencentes ao arquivo.
Muitos sistemas de backup atuais escolhem fazer o armazenamento dos arquivos em
fitas magnéticas por serem mais baratas que os discos rígidos. A fita magnética tem
a desvantagem de ter o acesso apenas sequencial dos dados, enquanto que no disco o
acesso pode ser randômico. Com a utilização das fitas, a deduplicação dos dados se torna
eficientemente inviável pela falta de capacidade em acesso randômico. Por esse fator, a
deduplicação está tornando um diferencial na escolha dos discos rígidos como dispositivo
de armazenamento dos backups, a vantagem do preço das fitas em relação aos discos é
contornada pelo fato de que com os discos rígidos a deduplicação pode ser feita e como
consequência o espaço de armazenamento é economizado [20].
1 http://aws.amazon.com/pt/s3/
2 http://www.google.com/enterprise/cloud/storage/
3 http://www.windowsazure.com
4 http://www.salesforce.com
2
1.1. MOTIVAÇÃO
A utilização de deduplicação de dados em sistemas de armazenamento em nuvem dá
uma grande vantagem à empresa que fornece o serviço. Com a utilização da deduplicação,
a empresa poderá vender para os cliente mais espaço de armazenamento do que ela poderia
fornecer em um sistema sem deduplicação, já que a deduplicação diminui a quantidade de
bytes armazenados por arquivos no sistema, principalmente quando o mesmo arquivo em
diferentes versões é salvo ou quando o mesmo arquivo é enviado para o sistema, mesmo
que por usuários distintos.
Uma forma de aumentar os blocos de dados redundantes em sistemas de armazenamento que possua arquivos com partes idênticas, é através da redivisão dos chunks
baseado no conteúdo, e a partir disso, aumentar a quantidade de blocos de dados idênticos.
Para que esse procedimento seja executado é preciso uma comparação byte à byte entre
os arquivos, tarefa essa que demanda muito processamento e utilização de E/S (entrada
e saída). Esse processo torna-se mais viável com a distribuição do processamento dos
dados para a redefinição dos novos pontos de cortes dos chunks e utilização de algoritmos
de hashing para identificar a redundância de dados.
1.1
Motivação
Os principais sistemas distribuídos de deduplicação de dados são feitos para serem
executados em clusters [4] [10] [20] [48] ou em nós simples, alguns deles usam framework
para processamento distribuído de dados [22], como Hadoop5 por exemplo, mas é difícil
encontrar trabalhos de pesquisa envolvendo sistemas de deduplicação para ambientes de
armazenamento de dados construídos com arquitetura peer-to-peer sobre computadores
pessoais para armazenar esses dados.
No desenvolvimento do Usto.re6 , um sistema de armazenamento de dados distribuído
que usa o espaço ocioso de computadores em rede para armazenamento de dados e que
será utilizado para validação deste projeto em ambiente comercial, foi demandada a
adoção de deduplicação de dados para reduzir o espaço de armazenamento para versões
diferentes de um mesmo arquivo. Um pesquisa foi executada para identificar bibliotecas
de código-fonte aberto com licença que não restrigisse o uso comercial para utilização da
mesma e nenhuma foi encontrada.
Baseado nos fatos supracitados, este trabalho propõe o desenvolvimento de um
componente de software para deduplicação de dados que pode ser integrado com qualquer
5 "http://hadoop.apache.org/"
6 "http://usto.re"
3
1.2. DEFINIÇÃO DO PROBLEMA
sistema de armazenamento de dados que tenha sido implementado em uma das linguagens
suportadas pelo Thrift7 , que é uma biblioteca para serialização de dados que suporta
comunicação entre diferentes linguagens de programação. O componente será integrado a
um sistema comercial de armazenamento de dados que foi construído em uma arquitetura
peer-to-peer.
A deduplicação traz vários benefícios para o sistema que a utiliza, entre eles:
• Redução no espaço necessário para armazenar arquivos. Isso ajuda um sistema
de armazenamento ser considerado dentro dos padrões da green storage, o qual
será melhor detalhado no Capítulo 4. Com a redução do espaço necessário para
armazenar os arquivos, um sistema de armazenamento pode ser vendido com mais
espaço do que ele possui fisicamente.
• Redução da quantidade de bytes trafegados, para o caso de sistemas distribuído,
pois com a deduplicação feita na fonte os dados redundantes não são enviados.
• Maior facilidade no gerenciamento de replicação de chunks, já que a deduplicação
reduz a quantidade deles.
1.2
Definição do problema
Algoritmos detalhados para deduplicação utilizando processamento de forma particionada são escassos. Existe também uma falta de componentes de softwares interoperáveis
para deduplicação que possam ser integrados aos sistemas de armazenamento de dados
existentes.
1.3
Resultados esperados
Esta pesquisa tem como principal objetivo desenvolver um algoritmo para deduplicação de dados, que faça processamento particionado e que seja interoperável e de fácil
integração com os sistemas existentes. Este algoritmo deverá ser disponibilizado como
um componente de software, com uma interface de comunicação multilinguagem, para
executar a deduplicação exata dos dados em sistemas de armazenamento. Ele deverá ser
integrado ao sistema de armazenamento que será desenvolvido como parte da pesquisa e
com um sistema distribuído de armazenamento de dados comercial.
7 "http://thrift.apache.org/"
4
1.4. ESCOPO NEGATIVO
O algoritmo a ser desenvolvido nesta pesquisa deve resolver os três benefícios citados na Motivação proporcionados pela deduplicação e com o mínimo de alteração no
sistema de armazenamento para integrá-lo, isso porque o algoritmo será feito tendo a
interoperabilidade e modificabilidade mínima para integração como alguns dos principais
requisitos.
O algoritmo deve ser disponibilizado através de uma biblioteca com uma interface
Thrift, que vai receber os valores de hash dos chunks e o arquivo a ser deduplicado, e
retornará o arquivo deduplicado como um mapa dos chunks e das referências aos chunks
redundantes.
O algoritmo deve fazer a busca por redundância baseada em conteúdo, independente
da quantidade de bytes alterados, removidos ou adicionado entre duas versões de um
arquivo ou entre arquivos distintos. O algoritmo será capaz de identificar as redundâncias
se a sequência de bytes não modificados for no mínimo do tamanho padrão do chunk.
1.4
Escopo negativo
Deduplicação através de chunks maiores que 128KB está fora do escopo da pesquisa,
pelo fato da detecção de redundância diminuir com o aumento do tamanho do chunk e este
ser o tamanho padrão do Ustore, o sistema comercial de backup de dados onde o Dedupeer
será implantado. Também foi definido como limite mínimo de tamanho de chunk 8KB.
Apesar de conseguir um maior ganho de redução de espaço com chunks menores, o
tempo para processamento e a quantidade de chunks gerados começa a degradar muito o
desempenho do sistema.
O Dedupeer File Storage será desenvolvido utilizando o Cassandra8 , que é um banco
de dados distribuído que utiliza arquitetura P2P, mas está fora de escopo o teste do sistema
de forma distribuída. Todos os testes serão feitos localmente, já que serão suficientes para
avaliar o algoritmo de deduplicação.
Os testes do algoritmo funcionando com deduplicação no alvo, tanto post-processing,
que é a deduplicação feita depois que os dados são armazenados, como inline, que é a
deduplicação onde os dados são processados no momento em que chegam no alvo e antes
de serem armazenados, estão fora do escopo do trabalho. Estes tipos de deduplicação
serão descritos na Seção 2.3.2.
Por serem os algoritmo de hashing mais comuns em processamentos de deduplicação
de dados, os testes só serão feitos com MD5 e SHA-1.
8 http://cassandra.apache.org/
5
1.5. CONTRIBUIÇÕES
1.5
Contribuições
As principais contribuições desta pesquisa serão:
• O algoritmo para deduplicação de dados com processamento particionado encapsulado em um componente de software interoperável. Essa forma de processamento
torna possível fazer a deduplicação de arquivos muito maiores do que a memória
principal, já que a configuração do tamanho da carga dos bytes para a memória,
independente do tamanho do arquivo, será configurável no algoritmo.
• O sistema de armazenamento de dados distribuído, com código-fonte aberto, administrável através de interface gráfica e com gerenciamento de armazenamento
delegado para um banco de dados não-relacional construído em uma arquitetura
peer-to-peer com topologia de anel.
• A melhoria da descoberta de redundância de dados através da carga extra de
dados no processamento particionado, possibilitando a diminuição da perda de
identificação por causa da quebra do arquivo.
1.6
Sumário
Neste capítulo foi apresentada uma introdução sobre o crescimento da demanda por
sistemas de armazenamento de dados e a importância da deduplicação para a economia
de espaço nos tempos onde os sistemas de cloud storage estão sendo cada vez mais
utilizados.
Este trabalho está dividido em sete Capítulos e um Apêndice.
No Capítulo 2 serão descritos como funcionam alguns sistemas de armazenamento de
dados que utilizam deduplicação. Em seguida será feita uma introdução sobre quais são
os tipos de deduplicação existentes e quais os benefícios que ela pode trazer.
No Capítulo 3 será detalhada a arquitetura do Dedupeer File Storage, que é o sistema
de armazenamento de arquivos desenvolvido neste trabalho, e serão discutidas algumas
decisões de projeto relacionadas à construção desse sistema.
No Capítulo 4 será detalhado o funcionamento do componente de software que
disponibilizará o algoritmo de deduplicação como um serviço. Será discutida a interoperabilidade do componente e quais poderiam ser as alternativas à biblioteca que foi
escolhida, também será discutida a decisão de utilização da comparação por hash e quais
são as suas vantagens e desvantagens.
6
1.6. SUMÁRIO
O Capítulo 5 detalhará os dois algoritmos de deduplicação desenvolvidos na pesquisa,
tanto o algoritmo mais simples como o algoritmo de processamento particionado, que é a
principal contribuição deste trabalho. Serão apresentados os fundamentos do algoritmo
desenvolvido para identificação de redundância entre arquivos remotos, os quais serviram
de base para os algoritmos desenvolvidos. Serão detalhados também os pseudocódigos
de alto nível dos dois algoritmos criados.
O Capítulo 6 apresentará os testes de desempenho e compressão executados para
demonstrar a eficiência do algoritmo de deduplicação e o sistema de armazenamento de
dados desenvolvidos.
E o Capítulo 7 apresentará as conclusões sobre o trabalho e algumas propsotas para
trabalhos futuros.
7
2
Trabalhos relacionados
Neste capítulo, os conceitos e técnicas fundamentais sobre os assuntos relevantes
para o entendimento dessa pesquisa serão discutidos. Serão discutidos os principais
trabalhos relacionados à sistemas de armazenamento de dados com foco em deduplicação,
os quais serão detalhados afim de identificar conceitos e técnicas que aprimorem o
desenvolvimento do projeto Dedupeer, o qual é dividido em dois, o Dedupeer File Storage
e o componente de software que implementa o algoritmo de deduplicação chamado de
Dedupeer.
Primeiramente vai ser feito um estudo com alguns dos sistemas de armazenamento de
dados que utilizam deduplicação para identificar as técnicas e os conceitos, e com isso,
analisar quais as que melhor servirão de base para o desenvolvimento do Dedupeer File
Storage. A análise feita nesses sistemas servirá para que uma melhor estratégia para o
processamento da deduplicação seja implementada no Dedupeer, com base nos princípios
desejados para a execução do mesmo.
É pequeno o número de sistemas de armazenamento que declaram a utilização de
deduplicação, e ainda menor os que detalham esse processo. Será apresentado o conceito
de deduplicação de dados e quais são os seus tipos.
2.1
Sistemas de armazenamento de dados com foco em
deduplicação
Nesta seção serão descritos alguns dos sistemas pesquisados que têm como objetivo
armazenamento de dados e que têm como um dos focos principais a deduplicação. Os
trabalhos acadêmicos serão apresentados por ordem de ano de publicação.
8
2.1. SISTEMAS DE ARMAZENAMENTO DE DADOS COM FOCO EM
DEDUPLICAÇÃO
2.1.1
Trabalho de Kathpal et al.
Devido ao desafio cada vez mais comum em armazenar e gerenciar o crescente
volume de dados gerados nos dias atuais, conhecido como Big Data[19], é importante
pensar em arquiteturas escaláveis para que os sistemas consigam dar suporte a essa
grande quantidade de dados. Uma proposta de um sistema escalável para dar suporte à
deduplicação para grande volume de dados foi descrita em [22]. Diferente das pesquisas
mais comuns para escalabilidade de sistemas de deduplicação, que geralmente têm o
foco na otimização dos algoritmos de deduplicação e em formas de deduplicação de
mais alto nível, como arquivos e objetos. [22] tem o trabalho direcionado para o projeto
arquitetural do sistema e usa deduplicação em nível de bloco, que apesar de ter vantagens
de velocidade, em contrapartida tem problemas no gerenciamento da enorme quantidade
de blocos a serem processados.
O projeto descrito em [22] foi proposto para funcionar de forma otimizada em
ambientes de cluster, o qual é um conjunto de computadores interligados através de um
sistema distribuído com uma finalidade em comum. Suas rotinas de deduplicação offline
de dados são executadas nestes cluster externos, isso é feito para que o processamento da
deduplicação não dispute os recursos com as outras rotinas do sistema. Para a execução
das tarefas foi usado o Apache Hadoop, que é um framework para computação distribuída
baseado em Map/Reduce, o qual ajudou a aumentar a capacidade de escalabilidade do
projeto.
Todo o processo para deduplicação dos dados é feito após o armazenamento no
sistema, o que tem como desvantagem a necessidade do dado ser todo transferido para o
destino, para que depois seja analisado para eliminação de blocos duplicados. Com isso,
não existe a economia de banda que é obtida com a deduplicação feita no cliente.
2.1.2
Trabalho de Kaiser et al.
Em Kaiser et al.[20], é explicado sobre o funcionamento de um sistema que executa
em cluster e utiliza um tipo de deduplicação que eles chamam de "exact deduplication",
que recebe esse nome pelo fato do sistema conseguir detectar todos os chunks duplicados.
Os sistemas com exact deduplication geralmente possuem chunks com tamanho entre
4KB e 16 KB. Sistemas que utilizam chunks grandes perdem muitas vezes a detecção da
redundância, já a utilização de chunks muito pequenos, apesar de aumentar a chance de
deduplicação, torna o sistema menos eficiente por causa da alta sobrecarga ocasionada
pela alta quantidade deles.
9
2.1. SISTEMAS DE ARMAZENAMENTO DE DADOS COM FOCO EM
DEDUPLICAÇÃO
O HYDRAstor, descrito em [10], utiliza uma granularidade alta nos chunks (64KB)
para a deduplicação. Ele não faz o compatilhamento dos dados entre os nós e distribui os
chunks na rede através de uma DHT (Distributed Hashtable). A escolha da granularidade
alta dos chunks é para aumentar o desempenho da deduplicação através da redução do
envio de metadados.
O sistema em [20] foi projetado para trafegar a menor quantidade de dados possível
na deduplicação para aumentar a escalabilidade do mesmo. Basicamente o que é trocado
entre as máquinas do cluster são fingerprints. O sistema descrito foi baseado no dedupv1
[28], o qual faz deduplicação em discos de estado sólido (SSDs) para evitar gargalos de
leitura e escrita de dados.
Ele é dividido nos seguintes componentes: deduplication nodes, shared storage,
interconnect between deduplication nodes, clients and distributed coordination. Os
deduplication nodes são responsáveis por grande parte das funções mais importantes para
a deduplicação e gerenciamento dos dados no sistema, neles são feitas as quebras dos
dados em chunks e em seguida o cálculo do fingerprint de cada um deles. Eles também
retornam os pedidos de chunks para outros nós e são responsáveis pela escrita deles no
container de armazenamento.
Cada deduplication node tem acesso às várias partições em que os discos são divididos pela rede através de storage area network (SAN) [42], as quais são redes de alta
velocidade para acesso à dados. Cada partição só é acessada por um único nó, caso
esse nó falhe, a tarefa de gerenciamento da partição é passada para outro nó, essa é
a responsabilidade do componente do sistema que é chamado de shared storage. A
distributed coordination é delegada para o Zookeeper 1 , um software de código aberto
que integra o projeto Apache 2 e o qual é o responsável pela escolha dos nós mestres
e da decisão de qual deduplication node assumirá o controle de determinada partição.
Cada delegação de controle das partições para os nós são armazenadas no Zookeeper e
gerenciada por um nó mestre, no caso de uma falha ocorrer nesse mestre, o Zookeeper
elegerá outro nó para tomar o lugar do que falhou.
2.1.3
Σ-Dedup
O Σ-Dedup, que é descrito em [13], é um middleware de deduplicação de dados para
data centers e cloud storages. O Σ-Dedup foi criado para otimizar a deduplicação de
dados em clusters.
1 http://zookeeper.apache.org/
2 http://apache.org
10
2.1. SISTEMAS DE ARMAZENAMENTO DE DADOS COM FOCO EM
DEDUPLICAÇÃO
O Σ-Dedup utiliza um conceito chamado de super-chunk, que é um agrupamento de
chunks consecutivos. Com os super-chunks são calculados um handprint que será enviado
para um conjunto de nós, que já possui um índice de similaridade de todos os handprints
dos super-chunks armazenados nele para aumentar a eficiência e diminuir a consulta ao
disco. Os handprints dos super-chunks semelhantes são enviados para um mesmo nó
para aumentar a probabilidade de encontrar chunks idênticos e com isso a eficiência da
deduplicação. Com o handprint, os nós efetuam um cálculo para determinar a semelhança
entre ele e os demais que estão armazenados no nó. Quando for encontrado o nó que
possui um super-chunk mais semelhante ao que vai ser enviado, todos os fingerprints dos
chunks pertencentes ao super-chunk serão enviados para o nó selecionado. Com esses
fingerprints o nó verificará quais deles já estão armazenados e quais são novos. Depois
dessa identificação, o nó pede ao cliente que está fazendo o backup apenas os chunks que
não foram encontrados.
Na Figura 2.1 os super-chunks do arquivo são identificados pelas letras. Eles são
enviados para nós diferentes, já que a escolha do nó onde cada um deles será enviado no
momento do backup depende da similaridade com os que estão armazenados nos nós.
A deduplicação no Σ-Dedup é feita à nível de nó, logo, podem existir chunks duplicados se eles estiverem armazenados em diferentes nós.
Figura 2.1 Armazenamento dos super-chunks nos nós [46].
A arquitetura do Σ-Dedup possui 3 componentes principais: o Backup Client, o
Deduplication Server Cluster e o Director.
O Backup Client tem como principal função fazer o backup e o restore dos arquivos.
Ele é composto de três módulos, um deles é Data Partitioning que é o responsável pelo
particionamento do arquivo e agrupamento dos chunks em super-chunks. O cálculo dos
11
2.1. SISTEMAS DE ARMAZENAMENTO DE DADOS COM FOCO EM
DEDUPLICAÇÃO
fingerprints é feito no módulo Chunk Fingerprinting que é uma camada abaixo do Data
Partitioning. O terceiro e último módulo do Backup Client é o Similarity-aware Data
Routing, é nesse módulo que é definido o nó de deduplicacação para o qual os dados
serão enviados.
Por ser um sistema de deduplicação inline, o qual será descrito na seção 2.3.2, os
dados são avaliados antes do envio para os nós e só são transferidos os chunks que ainda
não foram armazenados no sistema. Com isso, é economizada a banda de transferência
da rede.
O Deduplication Server Cluster também possui três módulos: Similarity Index Lookup, Chunk Fingerprinting Cache e Parallel Container Management. Eles são responsáveis respectivamente por retornar o índice de similaridade para o roteamento dos dados,
pelo armazenamento dos fingerprints mais utilizados em um cache para facilitar a busca
por chunks idênticos, e o último é o responsável pelo armazenamento de forma paralela
dos chunks únicos nos containers.
Um outro trabalho similar ao Σ-Dedup, onde os dados são enviados para determinados
nós baseados na similaridade, é o Extreme Binning [4].
2.1.4
Dropbox
Apesar de não haver nenhuma declaração explícita na homepage do Dropbox 3 ,
segundo um artigo publicado no site Slight Paranoia, o mais popular sistema de armazenamento de dados em cloud [3] utiliza deduplicação de dados entre arquivos de usuários
distintos [40]. Se dois usuários enviarem o mesmo arquivo para o sistema, o Dropbox só
armazenará um deles nos seus servidores.
Segundo o mesmo artigo, o CTO da empresa declarou que o Dropbox utiliza deduplicação no Forum oficial da empresa, respondendo à uma pergunta de um usuário que
questionava o porquê de um arquivo de 750MB ser enviado tão rápido. Esse tópico não
está mais hospedado no forum, mas a resposta do CTO para a pergunta "Woah! How did
that 750MB file upload so quickly?"está no Slight Paranoia:
Dropbox tries to be very smart about minimizing the amount of bandwidth
used. If we detect that a file you’re trying to upload has already been
uploaded to Dropbox, we don’t make you upload it again. Similarly, if you
make a change to a file that’s already on Dropbox, you’ll only have to upload
the pieces of the file that changed. This works across all data on Dropbox, not
3 "http://dropbox.com"
12
2.2. ALGORITMOS PARA ELIMINAÇÃO DE REDUNDÂNCIA DE DADOS
just your own account. There are no security implications [emphasis added]
- your data is still kept logically separated and not affected by changes that
other users make to their data."
Com a explicação do CTO, fica claro que o Dropbox utiliza deduplicação de dados,
mas o processo de deduplicação usado no Dropbox não é detalhado pela empresa.
2.1.5
Conclusão sobre os sistemas com foco em deduplicação
Todos os sistemas de armazenamento estudados utilizam armazenamento de dados
baseado em chunks ou blocos de dados. Pelo fato de todos eles serem sistemas distribuídos
para armazenamento de dados, precisam se preocupar com os problemas decorrentes
desse tipo de sistema descritos no trabalho sobre o Dynamo [8], como: robustez e
escalabilidade no balanceamento de carga, detecção de filiação e de falhas, entre outros,
os quais serão melhor descritos na seção 3.4.2. Como esse não é o foco principal do
trabalho, para a resolução desses problemas foi adotado para o Dedupeer File Storage
o banco de dados Cassandra, que funciona em uma rede P2P e já trata todos eles. Com
essa escolha será possível dedicar um maior tempo no que realmente interessa no estudo,
que é o desenvolvimento do algoritmo de deduplicação.
Os sistemas comerciais, como o Dropbox, não tem seus algoritmos ou processo de
deduplicação detalhados publicamente, e os trabalhos acadêmicos não possuem seus
algoritmos ou sistemas de deduplicação facilmente acessíveis para utilização em um
sistema de armazenamento. Esses foram os principais fatos que despertaram o interesse
em desenvolver um algoritmo, com um processo diferente dos descritos, de códigoaberto e interoperável entre linguagens para ser facilmente integrado aos sistemas de
armazenamento existente.
2.2
Algoritmos para eliminação de redundância de dados
Nesta seção será descrito alguns dos trabalhos relacionados ao desenvolvimento de
algoritmos para eliminação de redundância de dados. Apesar de não estarem totalmente
relacionado à forma como o Dedupeer irá trabalhar, a abordagem dos algoritmos descritos
poderá ajudar em algumas das decisões no desenvolvimento do mesmo. O principal foco
do Dedupeer será deduplicação de arquivos, enquanto que os trabalhos abaixo descritos
estão em áreas como eliminação de dados redundantes em banco de dados, tráfego
13
2.2. ALGORITMOS PARA ELIMINAÇÃO DE REDUNDÂNCIA DE DADOS
de redes de computadores e regiões de imagens. Como dito anteriormente, apesar de
muitas empresas que trabalham com softwares para gerenciamento de armazenamento de
dados terem seus próprios algoritmos de deduplicação, os detalhes sobre funcionamento,
técnicas de otimização entre outros fatores que ajudariam a criação de novos algoritmos,
não são reveladas por motivos comerciais.
2.2.1
FERAPARDA
Um trabalho desenvolvido na UFMG [34] apresenta um algoritmo paralelo e escalável para deduplicação de dados. O foco principal deste trabalho é a identificação de
duplicações em bancos de dados, e não em arquivos armazenados, como o presente
trabalho.
O trabalho apresentado por Santos et al. pode ser executado de forma paralela, e como
consequência fazer processamento de grande conjunto de dados em um tempo viável.
Em um teste apresentado neste trabalho, eles executaram o algoritmo em um cluster de
20 computadores e conseguiram realizar a detecção de duplicatas em um banco de dados
com 1 milhão de registros em 7 minutos.
A Figura 2.2 mostra o processo de deduplicação do algoritmo. O processo de padronização dos dados, chamado de Standardization não foi desenvolvido no trabalho descrito.
A segunda etapa do processo, chamada de Blocking, tem por finalidade limitar o número
de comparação entre os registros para que não inviabilize o processamento. Apesar de
no caso geral uma quantidade n2 de comparações ser necessaria, o algoritmo consegue
eliminar várias dessas comparações. A fase de Pair comparison simplesmete pega todos
os produtos cartesianos que foram gerados na fase de Blocking e compara os atributos,
em busca de encontrar os registros duplicados, esta comparaçao pode ser simples ou levar
em consideração erros de digitação e conseguir identificar registros que foram gravados
com valores diferentes mas que representam o mesmo objeto. Por fim, a fase Classifier é
responsável por classificar os resultados dos pares "não réplicas", "possiveis réplicas"e
"réplicas". Uma função de similaridade é aplicada aos dados, e a depender do resultado,
os pares são classificados em uma das três classes acima citadas.
2.2.2
DYNABYTE
DYNABYTE [15] é um algoritmo para identificação de redundância de dados em
pacotes trafegados em redes de computadores. O algoritmo RTE - redundant traffic
elimination, apesar de não estar classificado como algoritmo de deduplicação, tem o
14
2.2. ALGORITMOS PARA ELIMINAÇÃO DE REDUNDÂNCIA DE DADOS
Figura 2.2 Processo do algoritmo do FERAPARDA
mesmo propósito, que é o de eliminar dados redudntantes, e por isso será incluído como
um dos trabalhos relacionados ao Dedupeer.
O principal objetivo deste trabalho é o de eliminar a redundância dos dados trafegados
na rede, que segundo trabalhos citados no mesmo, está entre 15% a 60% de tudo que é
trafegado na rede.
Os trabalhos desenvolvidos para RTE geralmente são executados dentro da camada
de rede. Com uma abordagem diferente, o algoritmo SAMPLEBYTE, no qual o DYNABYTE é baseado, é executado dentro dos sistemas finais, o que possibilita a sua
utilização até em telefones celulares. Ele foi projetado para que pudesse ser configurado
de forma a não consumir muita bateria dos dispositivos móveis, o que o tornou viável
em ser utilizados por eles. O problema do SAMPLEBYTE é que ele exige uma préconfiguração baseada no treinamento dos dados, e a proposta do DYNABYTE é que essa
configuração seja feita de forma dinâmica, sem a necessidade do treinamento.
Em Halepovic et al. [15] foi feita a coleta de todo o tráfego de rede do link de acesso
da Universidade de Calgary. Foi coleta um total de oito traces, todos eles bidirecionais,
chegando a um total de 233,6GB de dados. Os traces foram então separados em tráfego de
entrada e saída e estudados separadamente. Para a avaliação foram utilizadas as métricas:
economia de bytes, tempo de processamento e taxa de amostragem. Foram utilizados
chunks de 64 bytes, um valor inviável para ser utilizado em algoritmos de deduplicação
para grandes arquivos, mas que funciona bem na identificação de redundância para tráfego
de rede.
Como o DYNABYTE é baseado no SAMPLEBYTE, o processo de funcionamento a
ser descrito será o do SAMPLEBYTE. Ele usa uma tabela com 256 entradas, uma para
cada valor possível de um byte. Os blocos são varridos byte a byte, o qual é escolhido
com um marcador caso o seu correspondente na tabela esteja configurado. Após isso, o
15
2.2. ALGORITMOS PARA ELIMINAÇÃO DE REDUNDÂNCIA DE DADOS
seu fingerprint é computado através do algoritmo Jenkis Hash, algoritmo este que foi
substituído pelo FNV Hash Function4 para o DYNABYTE. Fingerprints serão detalhados
na seção 5.1.2.
Os principais benefícios do SAMPLEBYTE são: evita cálculo de fingerprints que
não serão mais selecionados e limita a taxa de amostragem, o que resulta em um controle
do custo de processamento. No modelo cliente-servidor os fingerprints só são necessários
no servidor, deixando o cliente mais flexível para criar os marcadores dos chunks. O
DYNABYTE conseguiu facilitar a configuração do SAMPLEBYTE mantendo os seus
benefícios e taxa de economia.
2.2.3
Trabalho de Langille et al.
A proposta de Langille et al. [25] é um algoritmo eficiente para detecção de regiões
duplicadas em imagens. Com o algoritmo proposto é possível identificar partes duplicadas
dentro de uma mesma imagem, como por exemplo, quando se usa as ferramentas de clone
do Phosothop, o que dá a possibilidade de encontrar adulterações em imagens. Para que a
identificação seja realizada, é preciso que as regiões duplicadas da imagem tenham as
mesmas dimensões e orientação. Por utilizar o algoritmo ZNCC (Zero-Mean Normalized
Cross Correlation) 5 para identificação de similaridade é possivel identificar as regiões
duplicadas até em imagens onde o algoritmo de compressão do JPEG tenha sido aplicado.
O algoritmo pode ser resumido nos seguintes passos:
• A imagem é segmentada em pequenos blocos sobrepostos
• Para cada um dos blocos é feita uma busca por outro bloco similar através do
algoritmo ZNCC
• Os blocos são ordenados com base nas informações dos seus pixels através de uma
técnica baseada no kd-tree 6 , o que coloca os blocos similares mais próximos um
do outro. Com isso, a busca só precisa ser efetuada nos blocos vizinhos
• É aplicada uma série de operações morfológicas baseadas em cor, a qual é feita
para eliminação de possíveis erros do resultado. Fica provado no trabalho que
esta técnica reduz eficientemente os erros que podem ocorrer na busca por regiões
duplicadas
4 "http://www.isthe.com/chongo/tech/comp/fnv/index.html"
5 ZNCC
em
Python:
"https://github.com/MartinThoma/algorithms/blob/master/crosscorrelation/zncc.py"
6 "http://www.cs.sunysb.edu/ algorith/files/kd-trees.shtml"
16
2.3. DEDUPLICAÇÃO
Para medir a eficiência do algoritmo foram criadas imagens com regiões duplicadas
onde a localização exata das regiões era conhecida, com isso, foi possível verificar se o
algoritmo estava funcionando corretamente.
2.3
Deduplicação
A deduplicação de dados é um técnica de compressão sem perda que elimina dados
redundantes tanto intra-file quanto inter-file, diferente de ferramentas de compressão de
dados como o gzip que só eliminam a redundância intra-file. A deduplicação reduz a
quantidade de espaço necessário para armazenamento de dados através da eliminação
de blocos e/ou arquivos redundantes. Na deduplicação, todos os blocos de dados ou
arquivos que estão duplicados em um sistema de armazenamento são reduzidos à uma
única cópia, e os dados que foram desalocados são convertidos para uma referência ao
conteúdo mantido no sistema.
As técnicas de compressão de dados referem-se ao trabalho de dois algoritmos. Há
o algoritmo de compressão, e o de reconstrução. O algoritmo de compressão pega um
arquivo X e gera uma representação Xc desse arquivo. O algoritmo de reconstrução é
responsável por pegar a representação gerada pelo algoritmo de compressão e transformála no arquivo Y. Baseado no funcionamento do algoritmo de reconstrução, a técnica pode
ser classificada de dois modos: sem perdas (lossless), quando Y = X; e com perdas (lossy),
permite Y 6= X [35].
2.3.1
Localização
A deduplicação distribuída pode ser feita tanto na entidade que envia os dados quanto
na que os recebe. Para facilitar, será utilizado o padrão cliente/servidor para explicar
as formas de deduplicação. A entidade que requisita o armazenamento do dado será
referenciada como Cliente; a entidade de destino dos dados será referenciada como
Servidor.
Cliente (source)
Mandagere et al.[27] descreve a deduplicação baseada no cliente como sendo a
deduplicação feita antes do cliente enviar seus dados para o servidor. O cliente faz o
cálculo e obtem o valor do hash de um chunk, chamado de fingerprint, em seguida ele os
envia para o servidor de metadados, que faz a comparação com os fingertprints que estão
17
2.3. DEDUPLICAÇÃO
armazenados para poder identificar prováveis dados redundantes no sistema. Ao receber
as informações, o cliente executa uma busca de conjuntos de bytes redundantes e remove
esses dados antes de enviar o arquivo através da rede.
Esse tipo de deduplicação tem como vantagem a redução da quantidade de dados trafegados na rede e redução da sobrecarga de processamento no servidor. Em contrapartida,
há um consumo maior de CPU e I/O no cliente, pelo fato dele ser o executor da tarefa de
detecção de dados redundantes.
Um ponto crítico desta técnica é a capacidade que o cliente tem de identificar blocos
de arquivos armazenados no sistema e que são idênticos aos seus. O cliente precisa
saber os bytes dos blocos dos arquivos cujo fingerprint é igual ao do seu para fazer a
comparação e verificar se os dados são realmente idênticos, já que mais de um bloco de
mesmo tamanho pode ter um fingerprint igual mesmo tendo conteúdos diferentes. Apesar
da probabilidade disso ocorrer ser quase zero, é preciso garantir a integridade dos dados
armazenados pelos usuário, o que torna importante essa verificação byte a byte.
Servidor (target)
Considerada nessa categoria toda deduplicação que é processada na entidade que
recebe os dados para armazenamento. Nela estão os appliances para armazenamento, storage arrays, peers de recebimento de dados em sistemas de armazenamento construídos
com arquitetura peer-to-peer, entre outros.
A deduplicação feita no servidor pode acontecer em dois momentos: inline e postprocessing. Eles serão descritos no próximo tópico.
Uma desvantagem dessa abordagem é a centralização do processamento para identificação de dados redundantes no servidor, o que pode ocasionar a sobrecarregar do
mesmo.
2.3.2
Momento
A deduplicação pode ser de dois momentos: Inline deduplication ou Post-process
deduplication [12].
• Inline deduplication: os dados são examinados no momento em que chegam, antes
da escrita no sistema de armazenamento. Esse processamento antes da escrita pode
tornar o servidor um gargalo.
• Post-process deduplication: a deduplicação é feita depois que os dados são armazenados, em intervalos de tempo regulares ou quando um certo limite definido é
18
2.3. DEDUPLICAÇÃO
alcançado. Esse tipo de deduplicação é a melhor para ser utilizada em sistemas onde
a velocidade de recebimento de dados é um fator crítico, já que o processamento
pode deixar pra ser feito quando o servidor estiver ocioso.
2.3.3
Algoritmo
Os algortimos para fazer a deduplicação são categorizados em três tipos, segundo
[27]: Whole File Hashing, Sub File Hashing e Delta Encoding.
• Whole File Hashing: é aplicada alguma função de hashing como o SHA1 [1] ou o
MD5[33] no arquivo todo, esse valor é comparado com a base de armazenamento
de arquivos armazenados no sistema, caso algum outro arquivo possua o hash com
o mesmo valor, é feita uma comparação byte a byte para ter certeza que os arquivos
são idênticos, se forem, um dos arquivos é removido do sistema e o usuário ao qual
o arquivo apagado pertencia terá um referência para o arquivo que é idêntico ao
seu.
• Sub File Hashing: nessa categoria, o arquivo é dividido em pedaços que podem
ser de tamanhos iguais, chamado de Fixed Block Hashing (FBH), ou variáveis,
chamado de Variable Block Hashing (VBH). No algoritmo FBH, o arquivo é todo
dividido em blocos de tamanho fixo, em seguida, é aplicada alguma função de hash
nos blocos para obtenção dos fingerprints. O VBH utiliza o Rabin Fingerprinting
[31], a ideia de computar o fingerprint de cada bloco para apenas transferir os que
têm fingerprint diferente dos blocos que estão no computador de destino, com isso
é possível reduzir os dados trafegados na transferência de arquivos que possuem
partes comuns aos arquivos do outro lado, mas esta técnica tem um ponto que
precisa ser tratado. Quando qualquer dado é inserido ou removido de um arquivo,
todos os fingerprints dos blocos subsequentes serão modificados se o algoritmo
utiliza blocos de tamanho fixo. O Rabin Fingerprinting utiliza uma janela deslizante
(rolling checksum e utiliza uma técnica para subdividir os blocos que tenham maior
probabilidade de serem iguais a outros.
• Delta Encoding/Compression (DE): com o Delta Encoding é gerado um arquivo
conhecido como patch que é um arquivo que tem informações das diferenças
entre dois arquivos. Um algoritmo é usado para identificar quais partes devem ser
copiadas e substituidas em um arquivo e quais partes devem ser inseridas para que
seja possível remontar o arquivo apenas com as informações das diferenças.
19
2.3. DEDUPLICAÇÃO
2.3.4
Benefícios
Um exemplo do benefício que pode-se obter com a deduplicação foi apresentado pela
IBM. A IBM representou ganho de economia com um sistema de deduplicação baseado
em alterações de 20% do conteúdo dos arquivos através da Figura 2.3 [18]. A Figura
mostra um backup inicial de 7TB de dados, e em uma semana o backup dos dados chegou
a 79TB de dados. Em um sistema de armazenamento sem a deduplicação, todos os 49TB
de dados seriam ocupados, mesmo se a alteração nos dados for de 20%, mas se esse
sistema usa deduplicação, é possível armazenar todo o conteúdo no sistema utilizando
apenas 8,45TB físico no disco. Ainda no exemplo, em 30 dias seria necessário 210TB de
disco para armazenamento em um sistema sem deduplicação, e de apenas 26,2TB para
armazenar os mesmos dados em um sistema com deduplicação. É grande o ganho de
economia que pode ser atingido com a utilização de deduplicação.
Figura 2.3 Exemplo da economia de espaço oferecida em um sistema de armazenamento com
20% de alteração nos dados.
20
2.4. SUMÁRIO DO CAPÍTULO
2.4
Sumário do capítulo
Neste capítulo, foi feita a descrição de alguns dos sistemas de armazenamento de
dados, que utilizam deduplicação e fornecem detalhes sobre como ela é feita. Alguns dos
problemas enfrentados por esses sistemas, que não têm relação direta com a deduplicação,
só com o armazenamento distribuído, será atribuído ao Cassandra, que vai ser usado
como base para o gerenciamento dos dados do Dedupeer File Storage, fazendo com que
o foco principal do trabalho, que é o algoritmo de deduplicação, tenha um maior tempo
para ser dedicado na pesquisa.
A utilização de chunks para o processo de deduplicação, apesar de ser óbvio, foi
confirmado como base em todos os sistemas que fornecem esse serviço. Neste capítulo
também foi feita uma introdução sobre o que é deduplicação e quais são os seus tipos.
No próximo capítulo, será feito um aprofundamento no desenvolvimento do Dedupeer
File Storage, o modelo de dados utilizado, algumas decisões de projetos que foram
tomadas e será detalhada a visão de componentes e conectores do mesmo.
21
3
O Dedupeer File Storage
3.1
Introdução
O Projeto Dedupeer é composto pela biblioteca homônima e pelo Dedupeer File
Storage (DeFS), que foi desenvolvido para facilitar os testes e avaliação dos algoritmos
implementados para a deduplicação, que é a principal contribuição deste trabalho.
Para representar de forma simples a comunicação entre o componente, o sistema
de arquivos e o sistema de armazenamento que adicionar o componente, foi usado o
diagrama de componentes apresentado na Figura 3.1. Observando a interação entre
os artefatos que compõem todo o sistema para deduplicação, percebe-se que o acesso
aos arquivos é abstraído pelo Dedupeer. De uma forma transparente para o sistema de
armazenamento o Dedupeer lê, quebra, e processa os bytes do arquivo especificado,
levando em consideração os parâmetros passados pelo sistema através da interface de
comunicação Thrift 1 . O Thrift será melhor detalhado na seção 4.2.1.
O DeFS foi desenvolvido para ocupar o lugar no diagrama que pertence aos sistemas
de armazenamento de dados. Com a arquitetura planejada dessa forma, fica fácil fazer a
integração do algoritmo em muitos sistemas. O Thrift dá suporte à comunicação entre
diversas linguagens, o que aumenta a quantidade de sistemas que podem ser integrados
ao Dedupeer.
3.1.1
Escopo
O Dedupeer File Storage é um sistema de armazenamento de dados, que pode ser
usado de forma distribuída, com capacidade de armazenamento e recuperação de arquivos.
1 http://thrift.apache.org/
22
3.2. O SISTEMA DE ARMAZENAMENTO DISTRIBUÍDO
Figura 3.1 Diagrama de componentes de alto nível da biblioteca do Dedupeer
Apesar de poder ser usado de forma distribuída, como escopo deste trabalho só será
considerado a utilização dele em uma máquina simples.
3.2
O sistema de armazenamento distribuído
Para facilitar os testes e a validação dos algoritmos, foi desenvolvido um sistema de
armazenamento que tem como base o banco de dados não relacional desenvolvido dentro
do Facebook, e hoje projeto incubado no Apache Foundation, chamado Cassandra2 . O
Cassandra foi desenvolvido com o objetivo de ser escalável e altamente disponível.
Para mais informações sobre a escolha do banco de dados para ser usado como base
do sistema de armazenamento, ele é descrito em detalhes na seção 3.4.2.
3.2.1
Modelo de dados
Pelo fato do Cassandra ser um banco de dados NoSQL, também conhecido como
banco de dados não relacional, o seu modelo de dados é totalmente diferente dos utilizados
nos bancos relacionais, os quais possuem tabelas com colunas, cada registro na tabela
é adicionado em uma nova linha, com toda linha tendo que ter a mesma quantidade de
colunas das outras. Como a maioria das pessoas está acostumada com essa forma de
organização de um banco de dados, será feita uma breve apresentação do modelo de
dados utilizado no Cassandra, para facilitar o entendimento sobre as escolhas de projeto
para a modelagem do sistema de armazenamento.
2 http://cassandra.apache.org/
23
3.2. O SISTEMA DE ARMAZENAMENTO DISTRIBUÍDO
No modelo de dados do Cassandra existe uma flexibilidade muito grande sobre como
estruturar os dados. A forma mais simples de dado que se pode armazenar é uma lista
ou array. Com a adição de uma nova dimensão é possível transformar essa lista em um
Map e deixar os dados mais organizados. Essa nova dimensão pode servir para nomear
os dados da dimensão citada primeiramente, o que torna o modelo um pouco parecido
com a estrutura utilizada no relacional. Abaixo tem um exemplo de um registro simples
no modelo de dados do Cassandra [17].
"Paulo Fernando":
"email": "[email protected]",
"idade": "25"
Essa esttutura tem como chave o valor "Paulo Fernando". A primeira dimensão,
citada acima, seria os valores que representam os nomes das colunas "email"e "idade".
A consideração desses valores como nome de coluna é apenas organizacional, pois eles
não precisam ser necessariamente uma string, o valor armazenado em qualquer uma das
dimensões pode ser até dados binários com limite de 2 GB, mas para melhor estruturação
a maioria dos bancos usam esse valor como uma string ou um long para representar
um identificador para o valor da segunda dimensão, que está sendo representada no
exemplo pelos valores "[email protected]"e "25". Todos esses valores juntos
representam uma linha, e a reunião das linhas recebe o nome de família de colunas. As
famílias de colunas são associadas a um keyspace, que é um container de família de
colunas, e que seria o equivalente a um banco de dados no modelo relacional. Cada
instância do Cassandra pode ter vários keyspaces.
Além da coluna normal, representada pelos pares dos valores no exemplo acima,
como por exemplo, "idade": "25", existe também a chamada super coluna, que é um tipo
especial de coluna que possui uma estrutura mais complexa, onde existe um campo que é
usado como identificação e uma agregação lógica de colunas simples. O exemplo abaixo,
demonstra como seria um conjunto de dados representado por uma super coluna.
"Paulo Fernando":
"endereço"
"rua": "Rua ABC",
"número": "123"
"informações pessoais"
24
3.2. O SISTEMA DE ARMAZENAMENTO DISTRIBUÍDO
"email": "[email protected]",
"idade": "25"
O Cassandra, quando utiliza super colunas, funciona como uma hastable de 5 dimensões [Keyspace] [ColumnFamily] [Key] [SuperColumn] [SubColumn] [17]. Para acessar
a "idade"de "Paulo Fernando", por exemplo, o caminho seria [Keyspace] [ColumnFamily]
["Paulo Fernando"] ["informações pessoais"] ["idade"], onde Keyspace e ColumnFamily
teriam que ser previamente criadas no Cassandra para que esses dados pudessem ser
armazenados dentro da ColumnFamily.
Toda a estrutura que foi definida para o sistema de armazenamento desenvolvido está
representado na Figura 3.2. A escolha da estrutura utilizada será discutida a seguir.
Foram definidas duas famílias de super colunas para armazenar e organizar os dados
dos arquivos: UserFiles, Chunk; e um família de colunas para agilizar o processo de
identificação do arquivo: Files.
Na família de super colunas UserFiles, a chave é representada pelo nome do usuário.
O nome da super coluna é definido como sendo o nome do arquivo, no caso do exemplo
o arquivo se chama "lorem.txt". Foram definidas seis subcolunas para essa família:
file id
Armazena o identificador único do arquivo no sistema.
size
Armazena o tamanho do arquivo em bytes.
chunks
Armazena a quantidade de chunks em que o arquivo foi dividido.
with content
Armazena a quantidade de chunk que possui conteúdo
without content
Armazena a quantidade de chunks que não possui conteúdo. Este valor representa a
quantidade de chunks que são referências à chunks que estão duplicados no sistema.
A criação das colunas with content e without content foi uma decisão para aumentar o
desempenho evitando ter que consultar todos os chunks do arquivo para identificar quais
deles são referências e quais armazenam o conteúdo. A criação de apenas um dos dois
resolveria o problema, mas nesse caso, para a identificação do outro valor seria necessário
25
3.2. O SISTEMA DE ARMAZENAMENTO DISTRIBUÍDO
a consulta da quantidade total de chunks, então foi tomada a decisão de já armazenar o
valor calculado.
Na família de super colunas chamada Chunk a chave que identifica a linha é o
identificador único do arquivo, localizado na coluna com nome file id na família de super
colunas UserFiles. Cada linha representa as informações de todos os chunks pertencentes
ao arquivo referenciado. Cada arquivo só tem uma linha nessa família de super colunas.
As subcolunas dessa família são detalhadas abaixo.
md5
Armazena o valor do fingerprint representado por um valor do cálculo de uma
função SHA-1 sobre os dados do chunk atual.
hash32
Armazena o valor do fingerprint representado por o resultado do cálculo de uma
hash de 32 bits sobre os dados do chunk.
index
Armazena a posição do início do chunk dentro do arquivo completo. Por exemplo,
se ele for o primeiro segmento do arquivo, esse valor será 0, se ele for o segundo
segmento do arquivo e o primeiro segmento tiver 512 bytes de tamanho, esse valor
será 512.
length
Armazena a quantidade de bytes que o chunk possui.
content
Armazena o conteúdo binário que se inicia na posição index e vai até a posição
index + length dentro do arquivo. Armazena a quantidade de bytes que o chunk
possui.
pfile
Armazena o identificador do arquivo ao qual o segmento referenciado pertence.
pchunk
Armazena o identificador do segmento ao qual foi identificado que o conjunto de
dados é idêntico. Em outras palavras, adiciona uma referência ao segmento que
possui o conteúdo que não foi armazenado no sistema por ser duplicado.
26
3.2. O SISTEMA DE ARMAZENAMENTO DISTRIBUÍDO
Percebe-se a flexibilidade da utilização do Cassandra nessa família de colunas, na
mesma família de colunas são armazenados dois tipo estruturais de dados, um para
representar um segmento com conteúdo binário e outro para representar uma referência
para um outro segmento já armazenado no sistema. Para uma melhor visualização dessa
família de super colunas, elas serão detalhada na Figura 3.2.
A família de colunas chamada Files é bem simples, ela é apenas uma atalho de
consulta para o identificador de um arquivo de um determinado usuário baseado no nome
desse arquivo. A chave dessa família de colunas é o nome do usuário. Ela possui apenas
uma coluna que tem o nome do arquivo do usuário e o id desse arquivo.
27
3.2. O SISTEMA DE ARMAZENAMENTO DISTRIBUÍDO
Figura 3.2 Modelo de dados do sistema distribuído desenvolvido com o Cassandra
28
3.3. VISÃO DE COMPONENTES E CONECTORES
3.3
Visão de componentes e conectores
Nesta seção será descrito o funcionamento em tempo de execução do Dedupeer Project, que engloba DeFS integrado com o Dedupeer. A visão de componentes e conectores
do Dedupeer Project pode ser vista na Figura 3.3. Existem 3 grandes componentes no
sistema: O DeFS, o Dedupeer e Cassandra, os quais serão descritos a seguir:
DeFS
O Dedupeer File Storage é o sistema distribuído de armazenamento de dados que
foi desenvolvido na pesquisa para que os algoritmos de deduplicação propostos
pudessem ser testados com maior facilidade. O DeFS foi descrito na seção 3.2.
Dedupeer
O Dedupeer é a biblioteca onde os algoritmos propostos foram implementados.
Ele possui uma interface Thrift para interoperabilidade de comunicação entre
linguagens de programação distintas, para facilitar a integração do mesmo com
a maioria dos sistemas de armazenamento existentes. O componente Dedupeer
será descrito no capítulo 4, e o funcionamento dos algoritmos do Dedupeer serão
descritos no capítulo 5.
Cassandra
O Cassandra é um banco de dados distribuído que foi usado como base do sistema
de armanzenamento DeFS. Mais informações sobre o Cassandra na seção 3.4.2.
O componente Dedupeer File Storage
O componente GUI é o que apresenta a interface com o usuário através de uma janela
com componentes gráficos. Esse componente ainda possui os renderizadores dos campos
da tabela de listagem dos arquivos e o frame de configuração dos parâmetros que ficam
armazenados no arquivo. Ele tem ligação com as filas de backup (BackupQueue) e de
restore (RestoreQueue) dos arquivos, as quais são incrementadas com novos itens através
da interação do usuário. Os componentes para gerenciamento das filas de backup e
restore (também conhecido como reidratação no contexto de deduplicação) funcionam
com uma LinkedBlockingQueue como base, que é uma fila com propriedade FIFO
(first-in-first-out).
O componente StoredFile é o item usado tanto na fila de backup como na de reidratação, esse é o componente central do DeFS. Ele é responsável pelo gerenciamento do
29
3.3. VISÃO DE COMPONENTES E CONECTORES
Figura 3.3 Visão de componentes e conectores do DeFS integrado com a biblioteca do Dedupeer
processo de backup, reidratação e cálculo de economia de espaço. Tem ligação com o
Dedupeer através do ThriftClient e indireta com o Cassandra através do componente de
gerenciamento de dados que foram agrupados em DaoOperations. O ThriftClient, como
o nome já diz, é um cliente Thrift para fazer a comunicação com a biblioteca Dedupeer.
O Componente Chunking é usado para quebrar o arquivo em chunks para que sejam
enviados para o Cassandra. Ele é usado apenas quando não é requisitada a utilização
da biblioteca do Dedupeer, já que na deduplicação o Dedupeer já retorna todas as
informações sobre os chunks do arquivo, não sendo necessário nesse caso a divisão dos
chunks através do componente Chunking.
O componente Dedupeer
O componente Dedupeer possui apenas dois componente internos, o ThriftServer e o
DeduplicationImpl. O ThriftServer é o servidor que fica esperando por comunicações
dos clientes Thrift, é ele que roda o serviço que espera pelos parâmetros necessários
30
3.4. DECISÕES DE PROJETO E CONSIDERAÇÕES
para o processamento da deduplicação, processamento esse que é executado dentro do
DeduplicationImpl, o qual retorna a estrutura gerada através do processamento para o
ThriftServer para que este o envie de volta ao ThriftClient.
3.4
Decisões de projeto e considerações
Nesta seção serão discutidas as principais escolhas de tecnologias ou conceitos feitas
na construção do Dedupeer File Storage e o motivo dessas escolhas. A tecnologia que foi
escolhida será detalhada e as vantagens da sua escolha serão destacadas.
3.4.1
Tamanho do chunk
A definição do tamanho padrão do chunk é muito importante e não pode ser feita sem
um estudo sobre as consequências da escolha. Esse valor impacta tanto no desempenho
do sistema como a taxa de compressão médio que pode ser obtido na deduplicação.
Quanto menor for o tamanho de um segmento, maior será o raio de compressão pelo fato
de haver uma maior probabilidade de encontrar outros segmentos idênticos, já que um
menor conjunto de bytes precisará ser igual. Em contrapartida, com segmentos pequenos
será preciso processar uma maior quantidade deles, e a depender da implementação,
acessar o disco mais vezes, o que degrada o desempenho do sistema. E como cada chunk
requer uma mesma quantidade de metadados, independente do seu tamanho, ter chunks
pequenos ocasiona um maior espaço necessário para armazenamento.
Um projeto deve possuir o menor segmento possível, contanto que ele não degrade
o desempenho do sistema à ponto de ficar abaixo das especificações requeridas. Zhu
et al.[49] afirma que depois dos testes executados para medir o tamanho ideal, eles
encontraram o valor de 8 KB [49], que é o mesmo valor encontrado pelos criadores
do Venti [30]. Kaiser et al.[20] relata que o tamanho do chunk para um sistema de
deduplicação exata (exact deduplication), deve estar entre 4KB e 16 KB [20].
Esses valores serão levados em conta após o teste de desempenho que será feito para
identificar a melhor combinação de tamanho de chunk e algoritmo de hashing no Capítulo
6.
3.4.2
Cassandra para gerenciamento do armazenamento
Muitos dos desafios enfrentados quanto ao desenvolvimento de um sistema de armazenamento distribuído são delegados para serem resolvidos através do gerenciamento
31
3.4. DECISÕES DE PROJETO E CONSIDERAÇÕES
executado pelo Cassandra. Alguns desses desafios são citados no artigo sobre o Dynamo,
entre eles, robustez e escalabilidade no balanceamento de carga, detecção de filiação e
de falhas, recuperação de falhas, concorrência e agendamento de tarefas (jobs), e empacotamento de requisições [8]. Além desses, existem outros desafios como, garantia de
disponibilidade e consistência dos arquivos, replicação dos dados e tamanho e quantidade
das mensagens trafegadas. Nesta seção será discutida a forma como o Cassandra resolve
todos esses problemas.
O Cassandra foi desenvolvido em uma arquitetura peer-to-peer, também conhecida
como P2P, que é uma das arquiteturas comuns existentes na internet, além dela, a outra
arquitetura muito usada é a Cliente/Servidor. Na arquitetura Cliente/Servidor, existe
no mínimo duas entidades, uma que requisita um recurso e outra que atende a essa
requisição, nessa arquitetura os nós agem de uma forma ou de outra, nunca as duas ao
mesmo tempo. Na arquitetura P2P as entidades se comportam tanto como clientes quanto
como servidores, consumindo e oferecendo recursos na rede.
Schollmeier[38] define P2P como uma rede na qual os nós compartilham parte dos
seus recursos de hardware, entre eles, processamento, capacidade de armazenamento,
impressora, entre outros. Esses recursos compartilhados são essenciais para os serviços e
conteúdos oferecidos pela rede, como, por exemplo, compartilhamento de arquivos.
A arquitetura P2P é dividida em dois tipos, as chamadas arquitetura P2P pura e híbrida.
[38] define a arquitetura P2P pura se ela está classificada dentro definição anterior e,
além disso, se qualquer nó da rede puder ser removido sem que a rede sofra qualquer
perda. O mesmo trabalho define que uma arquitetura P2P é dita híbrida quando ela está
classificada na primeira definição de P2P e, além disso, uma entidade central é necessária
para fornecer parte do serviço que a rede se dispõe a oferecer [38].
No Cassandra, a arquitetura P2P usada foi a pura. Todo nó no Cassandra é idêntico
aos outros, não existe nó mestre e nem nó escravo. Com essa estrutura, a escalabilidade
horizontal se torna mais fácil, já que só é preciso adicionar um novo nó no cluster para
que ele se integre e se organize dentro da rede, para isso, ele possui um tempo para
aprender como está a topologia do anel (a rede do Cassandra funciona como um anel).
Depois da descoberta de como a rede está topologicamente estruturada o nó começa a
receber como qualquer outro que integra a rede.
O Cassandra utiliza o próprio sistema para armazenar as informações de configurações
dele. Todas essas informações são armazenadas dentro do Keyspace chamado system.
Entre essas informações estão o token do nó, o nome do cluster, definições de schema,
entre outras. Esse Keyspace não pode ser modificado pelo usuário.
32
3.4. DECISÕES DE PROJETO E CONSIDERAÇÕES
Tolerância à falhas
O Cassandra usa o gossip protocol[23] para a detecção de falhas. Periodicamente,
uma mensagem é enviada para um outro nó, quando o nó recebe a mensagem ele responde
com um Ack, quando a mensagem é recebida pelo nó que a iniciou, ele responde com
um Ack2. Com a utilização desse protocolo é possível identificar os nós que pararam de
funcionar. O Cassandra ainda usa um algoritmo que ao invés de apenas informar se um
sistema é ou não confiável, ele retorna um valor que é o nível de suspeita, esse algoritmo
é chamado de Phi Accrual Failure Detection [9]. O Cassandra possui um método que
ajuda na decisão se um nó está morto ou não, baseado no valor do nível de suspeita, com
assinatura interpret(InetAddress), onde InetAddress representa o endereço do nó.
Recuperação de falhas
Todo sistema que utiliza gossip protocol deve ter um mecanismo para tratar os
problemas decorrentes da sua utilização, o principal deles é chamado de anty-entropy e é
um mecanismo para sincronização de réplicas, que assegura que os valores das réplicas
armazenados nos nós estejam atualizados com a versão mais recente. Durante a fase
de compactação, os nós fazem a requisição das árvores Merkle dos vizinhos para poder
comparar com a sua árvore e assim poder identificar possíveis valores desatualizados.
A árvore Merkle funciona como um snapshot da família de colunas atual, ela é uma
árvore que possui os valores dos hashes dos dados armazenados nas famílias de colunas,
esses valores são comparados com os do nó requisitante, caso for encontrado algum
valor diferente, é feito o reparo nos dados atualizando-os para a versão mais recente [38].
Anti-entropy também é usado no Dynamo [8], mas o Cassandra faz um uso diferente, na
implementação do Cassandra existe uma árvore Merkle para cada família de colunas. O
algoritmo de anti-entropy é executado depois de cada atualização no banco de dados.
As operações de escrita no Cassandra são feitas primeiramente em um log que é
chamado de commit log. Este mecanismo tem como finalidade possibilitar a recuperação
de uma escrita mal sucedida. A escrita só é marcada como feita quando a operação é salva
no commit log, com ele é possível recuperar uma falha na escrita feita em memória. Após
a escrita no commit log o dado é salvo em uma estrutura de dados alocada na memória
que é chamada de Memtable. O Memtable só terá os dados salvos no disco quando ele
atingir um limite de objetos armazenados. A estrutura aonde os dados são salvos no disco
é chamada de SSTable.
33
3.4. DECISÕES DE PROJETO E CONSIDERAÇÕES
Write.ANY
Write.ONE
Write.QUORUM
Write.ALL
Read.ONE
Weak
Weak
Weak
Strong
Read.QUORUM
Weak
Weak
Strong
Strong
Read.ALL
Weak
Strong
Strong
Strong
Tabela 3.1 Força do consistência baseada nos níveis das operações [7]
Consistência
A consistência dos dados que são armazenados no Cassandra tem o seu nível definido
pelo usuário. A consistência pode ser usada como valor ONE (consistência fraca), nesse
nível de consistência o Cassandra pode retornar o dado encontrado no primeiro nó
consultado sem verificar se aquele é o valor mais recente. No caso de existir muitos
clientes na rede, é recomendável ter um nível de consistência no mínimo QUORUM,
que é um nível no qual o Cassandra precisa ler de vários nós antes de retornar o valor,
o que assegura que o sistema encontrará o valor do dado mais recente. No nível de
consistência ALL, o Cassandra consulta os dados armazenados em todos os nós antes de
retornar o valor. Se uma das consistências fortes forem utilizadas (QUORUM ou ALL), a
recuperação de falhas, conhecida como read-repair é executa antes do dado ser retornado.
O CAP Theorem descreve um sistema distribuído com relação à três aspectos: consistência, disponibilidade e tolerância à partição. O teorema diz que é impossível que um
sistema distribuído possua os três aspectos ao mesmo tempo, sempre um desses aspectos
tem que ser sacrificado. O Cassandra tem flexibilidade e permite que o usuário escolha
os aspectos do CAP Theorem que estão no sistema [7]. A Tabela 3.1 mostra qual o nível
de consistência do Cassandra a depender das escolhas do usuário.
O quorum é o número de nós que deve ser consultado para se chegar a um consenso
sobre a validade do dado (pode ser ANY, ONE, QUORUM ou ALL). Se o valor do
quorum for ONE, o dado só será armazenado em um único nó, o que vai torná-lo
sempre consistente, mas em contrapartida, ele nunca será replicado, o que diminui a
disponibilidade do mesmo.
Disponibilidade
O Cassandra possui um mecanismo para disponibilidade de escrita mesmo quando o
nó que receberia a mensagem tem uma falha de hardware, ou qualquer outra que o impeça
de receber a mensagem, esse mecanismo é chamado de hinted handoff. Quando um nó
tenta enviar uma mensagem para um outro que não pode ser alcançado por alguma falha,
34
3.4. DECISÕES DE PROJETO E CONSIDERAÇÕES
o nó remetente grava a mensagem em uma área do keyspace system para que quando o nó
onde a mensagem deveria ser escrita voltar, ela possa ser enviada e persistida.
Empacotamento de requisições
A troca de mensagens entre os nós é feita através de um serviço. As mensagens
que chegam são encaminhadas para um pool de threads, o qual é responsável pelo
gerenciamento delas. Em seguida, é analisado se a mensagem é do tipo streaming, que é
uma forma eficiente utilizada pelo Cassandra para fazer a transferência de SSTable entre
os nós, ou se é uma mensagem serializada padrão, e a partir disso é determinado para
qual manipulador ela será atribuída.
3.4.3
Alternativa para o gerenciamento de armazenamento
Foram analisados alguns pontos para a escolha entre o Cassandra e o HBase3 para ser
usado no Dedupeer File Storage. Os pontos considerados críticos para a escolha e que
fizeram com que o Cassandra fosse escolhido foram: facilidade de instalação/manutenção
e funcionamento em pequenos clusters. Esses foram os pontos considerados mais importantes pelo fato do objetivo ser a criação de um sistema para armazenamento de arquivos
que funcionasse tanto como um sistema de armazenamento stand-alone como um sistema
de armazenamento distribuído, e que fosse fácil de manter e instalar.
Facilidade de instalação e manutenção
O HBase é mais complexo para ser gerenciado pelo fato de ter sido desenvolvido para
dar suporte ao Hadoop, logo ele é mais complicado de ser gerenciado já que por padrão
ele está integrado com o Hadoop, HDFS e Zookeeper4 . O Cassandra não tem por padrão
essa ligação com outros sistemas, ele é mais fácil de instalar e manter que o HBase.
Clusters pequenos
Segundo o site oficial do HBase5 , ele não é adequado para ser usado em um cluster
com menos de 5 DataNodes, o que inviabilizaria a possibilidade da utilização do Dedupeer
File Storage em um computador stand-alone. Esta foi uma funcionalidade colocada como
prioritária no projeto, pois ela é útil para conseguir a economia de espaço proporcionada
3 "http://hbase.apache.org/"
4 http://whynosql.com/cassandra-vs-hbase/.
Acessado em abril de 2013
Acessado em abril de 2013
5 http://hbase.apache.org/book/architecture.html.
35
3.4. DECISÕES DE PROJETO E CONSIDERAÇÕES
pela deduplicação em computadores, sem que para isso precise criar um sistema de
armazenamento distribuído.
O HBase precisa de mais nós porque ele é dependente do HDFS, e o HDFS utiliza
uma replicação de blocos de 3 cópias.
3.4.4
Escalabilidade
Primeiramente, o conceito do que é escalabilidade será descrito, antes da apresentação das vantagens que a escolha do Cassandra para gerenciamento do sistema de
armazenamento oferece para a escalabilidade.
O que é escalabilidade?
Construir arquitetura de sistema para dar suporte à milhões de usuários é um dos
maiores desafios enfrentados pela indústria de software. Esse desafio fica mais complexo
quando a arquitetura é projetada para escalar e se adaptar à quantidade de usuários sem
precisar ter que reprojetá-la.
Quando se fala em escalabilidade, grande parte dos engenheiros de software só conseguem enxergar sistemas que escalam para mais usuários (scale up), mas escalabilidade
também está relacionado à capacidade do sistema em escalar para suportar menos usuários (scale down), ou seja, ele deve ser capaz de reduzir a quantidade de recursos alocados
quando a demanda de usuários diminuir [36].
Existem dois tipos de escalabilidade de sistemas: horizontal (scale up) e vertical
(scale out). Escalabilidade vertical é a capacidade de adicionar recursos a um nó do
sistema e ele se adequar à nova configuração. Escalabilidade horizontal é a capacidade
do sistema se adequar à adição de novos nós.
Quando um sistema precisa escalar horizontalmente (scale up), é um forte sinal de
que a demanda por ele está crescendo, esse fator é um indício de que o lucro da empresa
também está crescendo junto. Quando isso acontece, e a arquitetura do sistema foi
pobremente planejada para escalar horizontalmente, a empresa pode investir parte dos
lucros obtidos com a quantidade de usuário para solucionar o problema de escalabilidade,
mesmo que não seja pela melhor forma. O maior problema é que quando essa demanda cai
bruscamente, os lucros da empresa com o sistema geralmente também caem, e a empresa
tenta ao máximo reduzir os custos. Percebe-se que se a arquitetura não é planejada para
scale down, a perda de dinheiro com a redução de cliente pode se tornar maior, já que a
quantidade de recursos alocados para o sistema se tornam ociosos por ter sido reservado
36
3.5. SUMÁRIO DO CAPÍTULO
para atender a uma quantidade de usuários muito maior do que a real.
Escalabilidade com o Cassandra
Com a escolha de um banco de dados NoSQL, distribuído, e alto gerenciável, a
questão da escalabilidade é um outro ponto que o Dedupeer File Storage não precisará se
preocupar, já que todo o gerenciamento é feito pelo cluster de Cassandras.
3.5
Sumário do capítulo
Este capítulo apresentou o Dedupeer File Storage, que foi sistema de armazenamento
de arquivos desenvolvido para auxiliar a pesquisa, e que pode ser usado tanto um sistema
de armazenamento local como um sistema de armazenamento distribuído. Ele é integrado
através da interface Thrift com o componente para deduplicação de arquivos, o qual será
descrito em detalhes no próximo capítulo.
Foi discutido o modelo de dados utilizado, a visão de componentes e conectores do
sistema integrado com o componente para deduplicação e as principais decisões de projeto,
como a escolha do Cassandra para gerenciamento dos dados. Os benefícios relacionados
à utilização do Cassandra também foram detalhados, o qual ficou responsável por tratar
os problemas comuns enfrentados na criação de sistemas de armazenamento distribuídos.
O próximo capítulo apresentará o componente para deduplicação de arquivos e
detalhará as principais decisões de projeto no seu desenvolvimento.
37
4
Componente para deduplicação em
sistemas de armazenamento de dados
4.1
Introdução
O desenvolvimento do Dedupeer foi planejado para que os algoritmos desenvolvidos
pudessem ser usados pela comunidade de forma fácil. O Dedupeer foi projetado para
que as escolhas de configurações fossem feitas através de parâmetros da interface de
serviço, entre essas configurações estão o tamanho do chunk e o algoritmo de hashing.
O Dedupeer também foi desenvolvido para que pudesse ser usado por qualquer sistema
de armazenamento que tenha como objetivo obter um ganho na economia de espaço
utilizado, o que traz benefícios tanto para o fornecedor, por ter mais espaço para oferecer,
quanto para o meio ambiente.
O chamado Green Storage Initiative(GSI) 1 é liderado pelo SNIA (Storage Networking
Industry Association) em parceria com empresas como Dell, EMC, HP, IBM, Oracle,
NetAPP, Seagate, entre outras. Na GSI são discutidas técnicas que diminuam o impacto
do uso de sistemas de armazenamento ao meio ambiente. Das discussões sobre uso
eficiente dos sistemas de armazenamento, a EPA liberou um documento de especificação
para discussão pública, onde deduplicação de dados é considerada umas das tecnologias
da green storage [11], veja na citação abaixo.
"EPA understands that there are many software-based approaches to improving the energy efficiency of storage products. The benefits of virtualization,
data deduplication, and other software-based data management techniques
are well documented. These software solutions, perhaps even more so than
1 http://www.snia.org/forums/green
38
4.2. INTEROPERABILIDADE
the hardware itself, are heavily customized for specific customers and applications. Achieving maximum efficiency gains is highly dependent upon
proper software architecture, implementation, operation, and maintenance
by individual users."
Nas seções seguintes serão detalhadas as decisões de projeto que foram tomadas, assim
como uma técnica utilizada para tornar o processamento da deduplicação temporalmente
viável.
4.2
Interoperabilidade
Engenharia de Software baseada em componentes desperta muito interesse devido
a reusabilidade do software. O seu objetivo é reduzir o custo e o esforço no desenvolvimento, enquanto provê flexibilidade, confiabilidade e reusabilidade, pelo fato do
componente já ter sido validado e testado antes da integração [44].
Um dos principais conceitos chave para a criação de componentes de software reusáveis é a interoperabilidade. A Interoperabilidade foi definida por Vallecillo et al. [44]
como a habilidade de duas ou mais entidades se comunicar ou cooperar, apesar das
diferenças na linguagem de implementação, ambiente de execução, ou modelo de abstração. Existem dois níveis de interoperabilidade: assinatura e semântica. A primeira
é baseada na assinatura das operações que o componente disponibiliza para interação,
como por exemplo, nome de métodos, tipos dos parâmetros e valores de retorno. A
interoperabilidade semântica tenta garantir que a troca de dados entre os componentes
faça sentido, mas pelo fato desse nível de interoperabilidade englobar todos os aspectos
semânticos, ele é considerado muito complexo, o que direcionou a maioria dos trabalhos
sobre esse nível para uma de suas áreas, relacionada às questões comportamentais dos
componentes [44].
O Dedupeer foi desenvolvido com o nível de interoperabilidade de assinatura, a qual
é definida e disponibilizada através do Thrift, que será detalhado na seção seguinte.
4.2.1
Interoperabilidade de comunicação através do Thrift
O Thrift foi um projeto que surgiu dentro do Facebook e hoje é gerenciado pela
Apache Software Foundation2 . Ele possui uma ferramenta de geração de código para
2 http://thrift.apache.org/
39
4.2. INTEROPERABILIDADE
facilitar a criação de serviços em diversas linguagens de programação. O principal objetivo do Thrift é fornecer a capacidade de comunicação entre linguagens de programação
distintas. O Thrift permite que os desenvolvedores definam tipos de dados e serviços em
um arquivo de linguagem neutra e gera toda a estrutura necessária, tanto para o servidor
como para o cliente RPC (remote procedure call) [2].
O Thrift tem flexibilidade para a criação de estruturas de dados, além de também dar
suporte aos principais tipos, independente da linguagem utilizada. O Thrift possui os
seguintes tipos base:
bool Um valor booleano, true ou false.
byte Um byte com sinal.
i16 Um inteiro com sinal de 16 bits.
i32 Um inteiro com sinal de 32 bits.
i64 Um inteiro com sinal de 64 bits.
double Um número de ponto flutuante de 64 bits.
string Uma sequência de caracteres.
Além desses tipos de dados mais simples, existem estruturas de dados mais complexas
que podem ser usados para a comunicação entre linguagens com o Thirft. Para isso, ele
faz as conversões entre as estruturas definidas nessas linguagens. As 3 estruturas de dados
que podem ser usados no Thrift são:
list<type> Um lista ordenada de elementos. Essa estrutura é traduzida em um ArrayList
em Java ou em array nativo nas linguagens de script.
set<type> Um conjunto de elementos. Traduzido para HashSet em Java.
map<type1,type2> Um mapa chave/valor. Em Java ele é traduzido para um HashMap.
Ainda relacionado à utilização de estruturas mais complexas, pode-se criar estruturas
equivalente à objetos para serem transferidas através do Thrift, os quais são chamados
structs. Dentro de um structs pode-se adicionar quantos tipos forem necessários, os quais
podem ser opcionais ou obrigatórios. Quando um campo é configurado como obrigatório,
o construtor do objeto receberá o campo como parâmetro, caso o campo seja configurado
40
4.2. INTEROPERABILIDADE
como opcional, o objeto terá um método que poderá ser usado para adicionar um valor ao
campo e ele não será um dos parâmetros do construtor.
O Thrift possui o conceito de serviços, os quais são definidos no mesmo arquivo que
os tipos. Com a geração automática do código através do compilador do Thrift, toda a
estrutura necessária para que o serviço funcione é criada, tanto a parte cliente como a
parte servidora, só é preciso implementar o algoritmo que funcionará dentro do serviço.
Os serviços são definidos no Thrift da seguinte forma:
service <name> {
<returntype> <name>(<arguments>)
[throws (<exceptions>)]
...
}
A escolha do Thrift para o projeto será discutida a seguir.
4.2.2
Comparação com o Protocols Buffer
Nesta seção será discutida a escolha do Apache Thrift como opção para a serialização
dos dados trocados entre o sistema de armazenamento e o Dedupeer. O Thrift será
comparado com um outro mecanismo parecido com ele e que também é muito utilizado
nos sistemas atuais, o Protocols Buffer.
Protocols Buffer
O Protocols Buffer foi desenvolvido na Google e é utilizado internamente em quase
todos os seus protocolos RPC [24]. Segundo o Developer Guide [14], o Protocols Buffer é
uma forma extensível de serialização de dados estruturados que possui linguagem neutra,
e tem a finalidade de ser usado em protocolos de comunicação, armazenamento de dados,
entre outras.
O Protocols Buffer possui uma boa documentação, diferente do Thrift onde a documentação é bem reduzida. Ele dá suporte à apenas 3 linguagens: C++, Java, Python.
Isso acaba limitando a integração com sistemas desenvolvidos em outras linguagens. O
Thrift suporta as seguintes linguagens: As3, C Glib, C++, CSharp, D, Delphi, Erlang,
Go, Haskell, Java, Java Me, Javascript, Node.js, Objective-c, OCaml, Perl, PHP, Python,
Ruby e Smalltalk, o que dá uma maior interoperabilidade para o componente.
41
4.2. INTEROPERABILIDADE
Quanto à quantidade de tipos suportados, ele também possui uma quantidade inferior
ao Thrift. O Protocols Buffer dá suporte aos tipos: bool, 32/64-bit integers, float,
double, string, sequência de byte e o "repeated"que funciona como uma lista. O Thrift
dá suporte aos tipos: bool, byte, 16/32/64-bit integers, double, string, sequência de
bytes, map<t1,t2>, list<t>, set<t>. Como no Dedupeer a estrutura de dados trafegada
necessitava da utilização de um map, a facilidade de implementação dessa estrutura no
Thrift foi um dos motivos para decidir por ele quando comparado ao Protocols Buffer.
Comparação de desempenho
O Protocols Buffer leva vantagem no desempenho em relação ao Thrift. Nas Figuras
4.1 e 4.2, são apresentados resultados de um teste de desempenho feito com algumas
bibliotecas de serialização. Percebe-se que o Protocols Buffer, chamado de protobuf, tem
um melhor desempenho que o Thrift. Na serialização dos dados, o Protocols Buffer teve
um desempenho aproximadamente 50% mais rápido que o do Thrift. Na desserialização,
o Protocols Buffer foi aproximadamente 31% mais rápido. Mas o peso dessa vantagem
não influenciou na decisão de escolha, devido ao fato de que o suporte a mais linguagens
e a possibilidade de utilização de estruturas de dados como Map foram considerados mais
importantes para o projeto do que a diferença entre o desempenho das ferramentas.
Figura 4.1 Desempenho na serialização dos dados [39]
4.2.3
Comparação por hash (fingerprints)
Uma função hash mapeia um conjunto de dados de tamanho variável para um resultado
com tamanho fixo. Como o valor no qual o conjunto de dados é mapeado tem um tamanho
menor do que o conjunto de entrada, existe uma possibilidade de dois ou mais conjuntos
42
4.2. INTEROPERABILIDADE
Figura 4.2 Desempenho na desserialização dos dados [39]
de dados distintos terem um valor de hash igual. Quando o mesmo hash é obtido de
conjunto de dados diferentes, é dito que houve uma colisão de hashes [16].
Comparar a igualdade entre arquivos ou entre blocos de dados através do resultado de
uma função hash aplicada aos seus conteúdos, é uma forma eficiente de verificar se os
conteúdos são diferentes com probabilidade de erro igual a zero. Muitos sistemas utilizam
a comparação para identificar igualdade em conteúdos também, como por exemplo, o
rsync[43] e o Venti[30]. Apesar da utilização dessa técnica em vários grandes projetos, a
comparação de igualdade entre conteúdos através de uma função hash aplicada à ele tem
probabilidade de encontrar um falso positivo.
O cálculo de uma função hash é muito eficiente. O cálculo do SHA1 de 160 bits
em um bloco de 8KB, utilizando um computador Pentium 3 de 700Mhz, é feito em 130
microssegundos, o que dá a média de 60MB/s [30].
Comparar todos os bytes de dois blocos de dados para identificar se os mesmos são
iguais, é uma tarefa muito custosa. O custo computacional para fazer uma comparação de
blocos de dados com 128 KB cada um é menor, se ao invés de comparar todos os 128 KB
de conteúdo fizer a comparação apenas dos valores de hash dos dois, que se for obtido
através de uma função MD5 de 128 bits, por exemplo, terá um valor de representação
com 32 dígitos hexadecimais. A comparação de 128 KB de dados é substituída por uma
simples comparação entre 16 bytes.
Fazer a comparação de todos os bytes de um segmento para identificação de igualdade
é chamado de comparação byte a byte. Esse método de determinação de igualdade de
segmentos é totalmente confiável, mas em contrapartida, é extremamente custoso. Apesar
da comparação por hashes ter a probabilidade de dar um falso positivo para um segmentos
de dados com conteúdos diferentes, o principal argumento dos defensores dessa técnica é
43
4.2. INTEROPERABILIDADE
que a probabilidade de ocorrer um erro no hardware que armazena o dado é muito maior
do que a probabilidade desse falso positivo acontecer. Quando um dado é corrompido, é
quase certo que esse erro seja causado por falha de hardware, como erros não detectados
na memória principal, na transferência pela rede, nos dispositivos de armazenamento
ou qualquer outro componente de hardware, do que por uma colisão de hashes. Por
este motivo, foi definido que o método de identificação de segmentos iguais utilizado no
projeto seria através da comparação por hashes.
Para assegurar que os dados são realmente idênticos, algumas empresas, como a
NetAPP, fazem a análise bit a bit dos chunks, que pode ser uma alternativa, mas geralmente
é usada como complemento da comparação por fingerprints para confirmar se os dados
são iguais, e assim evitar o problema que pode ser causado pela colisão de hashes.
A probabilidade de ocorrer uma colisão de hashes pode ser estimada através dessa
função matemática:
P = 1 − (1 − 2−b )n
, com n representando o número de blocos de entrada e b representando o número de bits
no valor do hash de saída.
Considerando um sistema que usa blocos de 8 KB com fingerprints calculados com
SHA1 de 160 bits e que possua 1 exabyte (1018 bytes) de dados armazenados, o que
dá um quantidade de aproximadamente 1014 blocos, a probabilidade de uma colisão de
hashes ocorrer neste cenário ainda é extremamente baixa, essa probabilidade é menor
que 10−20 [30].
Vantagem
A comparação bit a bit, apesar de ser uma técnica na qual se pode ter uma certeza
absoluta sobre a igualdade de dois conjunto de dados, ela possui desvantagens. Além de
ser uma técnica muito custosa, já que todos os bits precisam ser comparados, um a um,
ela elimina toda a vantagem da análise remota de chunks, que é a utilizada no Dedupeer.
Por isso, ela não foi implementada para garantir o positivo na comparação entre chunks.
A utilização do SHA-1 para a identificação de igualdade de conjunto de dados foi
usado porque apesar da possibilidade de colisão, ele permite a possibilidade de analisar
a igualdade de dois conjuntos de dados sem tê-los em um mesmo computador, o que
possibilita o processamento remoto. Outro ponto positivo para a escolha do SHA-1, é o
fato de até hoje não ter registros de colisão de hashes com ele [37].
Se for utilizado SHA-256, a probabilidade de colisão é ainda menor, segundo [29]
a probabilidade de uma colisão em um conjunto de 1024 exabytes de dados em um
44
4.3. SUMÁRIO DO CAPÍTULO
sistema de deduplicação, com um tamanho de chunk de 4KB e utilizando o SHA-256
para calcular os fingerprints, é menor que 10−42 .
4.3
Sumário do capítulo
Neste capítulo foram discutidas algumas das principais decisões de projeto para a
criação do Dedupeer como um componente interoperável, com facilidade de adaptação
com sistemas de armazenamento na maioria das linguagens populares. Também foi
explicada a técnica de análise de fingerprints, usada para a identificação de conjunto de
dados idênticos, que é usada pelos algoritmos de deduplicação em geral, e as vantagens e
problemas que podem ocorrer com a utilização dessa técnica. Também foi apresentada
uma alterativa para identificação de conjuntos de dados iguais, que no caso do projeto
proposto, não é viável ser aplicada.
No próximo capítulo serão detalhados os dois algoritmos implementados, entre eles,
o que é utilizado no core do componente Dedupeer.
45
5
Os algoritmos
Dois algoritmos foram desenvolvidos para fazer a deduplicação no projeto, um mais
simples, que carrega todo o arquivo a ser deduplicado para a memória em uma única vez,
e um segundo, que faz a carga particionada do arquivo. O segundo algoritmo permite que
o processamento do arquivo seja feito de forma particionada, com a carga do bytes para a
memória de forma parcial.
Este capítulo é dividido em duas partes, na primeira é feita a fundamentação base
para o desenvolvimento dos algoritmos, e a segunda é descrito o funcionamento de cada
um dos dois algoritmos, tanto uma explicação de alto nível como uma mais aprofundada
na implementação.
5.1
Fundamentos
Nesta Seção, serão explicados os dois principais conceitos utilizados para tornar o
desempenho do processamento da deduplicação viável, o rolling checksum e o fingerprinting. Uma breve introdução sobre o percursor da análise de igualdade entre arquivos de
forma remota também será discutida.
5.1.1
O algoritmo Rsync
O algoritmo Rsync foi desenvolvido para otimização de transferência de arquivos entre
computadores e foi utilizado primeiramente na ferramenta de mesmo nome, desenvolvido
por Andrew Tridgell and Paul Mackerras [43].
Suponha que dois computadores tenham versões diferentes de um mesmo arquivo, e
que o objetivo seja atualizar o arquivo mais antigo para a versão mais recente, ao invés de
enviar o arquivo todo e substituir a versão mais antiga, pode-se calcular e enviar para o
46
5.1. FUNDAMENTOS
outro lado apenas a os bytes diferentes entre esses arquivos. A identificação da diferença
entre arquivos pode ser feita de várias formas, a maioria dos algoritmos usa a abordagem
de análise de dois arquivos localmente para a identificação da redundância de conjunto
de bytes entre eles, criando a partir do processamento um arquivo da diferença, que é
chamada de patch. O Rsync usa uma abordagem diferente, ele faz a identificação da
diferença entre os arquivos de forma remota, com isso ele identifica as partes do arquivo
que precisam ser enviadas para o outro computador e quais partes precisam ser apenas
referenciadas, evitando assim a transferência do arquivo todo para o destino.
O algoritmo Rsync funciona da seguinte maneira [43]:
• O computador β quebra o arquivo B em chunks de tamanho fixo S, não sobrepostos,
sendo que o último chunk pode ter um tamanho menor que S;
• Para cada chunk é calculado dois fingerprints, um fraco "rolling" de 32 bits, e um
mais forte de 128 bits;
• β envia um lista com os fingerprints para o computador α;
• α primeiro faz a busca no arquivo A com um rolling checksum, comparando o
fingerprint obtido com o de 32 bits enviado por β . Caso encontre alguma parte do
arquivo que o valor calculado seja idêntico a algum fingerprint enviado por β , é
feito um cálculo no mesmo bloco de dados para obter o fingerprint de 128 bits, que
é comparado à lista recebida;
• α envia para β as instruções necessárias para montar o arquivo idêntico ao A,
definindo quais chunks de B podem ser aproveitados e enviando os dados de A que
não estão em B.
Rolling checksum
O rolling checksum foi usado nos dois algoritmos implementados no projeto. Ele é
um tipo de checksum que tem a propriedade de ser calculado de forma pouco custosa
quando o cálculo do checksum da janela anterior já tiver sido feito, por exemplo, se o
checksum do bloco de bytes Xk ... Xl já for conhecido, obter o do bloco Xk+1 ... Xl+1
é mais rápido [43]. Para a identificação dos dados duplicados, o Rsync usa o rolling
checksum.
A não utilização de uma técnica como esta, torna inviável a identificação de partes
iguais dentro de um arquivo, até mesmo em arquivos que sejam backups sucessivos e que
47
5.1. FUNDAMENTOS
possuam apenas uma pequena parte diferente. O problema é que qualquer alteração, seja
ela uma adição, uma remoção ou qualquer outra mudança, desloca o conteúdo do arquivo,
isso causa uma alteração em cadeia em todos os segmentos dos chunks posteriores, que
receberão os bytes de um vizinho e fornecerá bytes para o vizinho que o sucede.
5.1.2
Fingerprinting
Fingerprints é uma outra técnica que foi aplicada como base nos dois algoritmos
desenvolvidos, eles são valores que identificam uma sequência específica de dados. A sua
principal propriedade é a identificação da diferença entre conjuntos de dados, independente de formato, que possuam o mesmo tamanho. Ele é usado também para identificar
igualdade entre conjuntos de dados, pelo fato da probabilidade dos valores serem idênticos, quando os conjuntos de dados são diferentes, ser quase zero. O fingerprint é o
resultado do cálculo de uma função hash aplicada em um conjunto de dados. Na maioria
das vezes os fingerprints são calculados a partir das funções hash MD5 ou SHA1 por
serem funções com baixa probabilidade de colisão. [13]
Para
um esquema de fingerprinting é um conjunto de função
n um melhor entendimento,
o
k
F = f : ω → {0, 1} , onde ω representa o conjunto de todos os segmentos possíveis
e k é o tamanho do fingerprint. Se for escolhido um conjunto S ⊂ ω de n seguimentos
distintos, e for escolhido f ∈ F uniforme e randomicamente, então
f (A) 6= f (B) =⇒ A 6= B
P( f (A) = f (B)|A 6= B) = muitobaixa
[6].
Blocos de dados de mesmo tamanho podem ter um fingerprint igual mesmo tendo
conteúdos diferentes. Segundo Jeff Bonwick, líder no desenvolvimento do ZFS, a
probabilidade de colisão de hashes entre dados não idênticos com a utilização de uma
função hash SHA256 é de aproximadamente
2−256 = 10−77
[5].
Mesmo os fingerprints sendo uma representação muito reduzida de um segmento de
dados, é preciso ter cautela com a quantidade deles que são carregados para a memória
de uma só vez. Considerando o tamanho padrão dos segmentos como 8 KB de tamanho,
48
5.2. DETALHANDO OS ALGORITMOS
sendo representado por um fingerprint de 160 bits, um arquivo de 8 TB teria um conjunto
de fingerprints com tamanho de 20 GB [49].
5.2
Detalhando os algoritmos
O Dedupeer possui dois algoritmos para fazer a deduplicação de um arquivo. O
primeiro, e mais simples, foi desenvolvido com base no princípio de comparação de
conjunto sequencial de bytes do Rsync.
O segundo, e mais complexo algoritmo, foi desenvolvido com uma forma de comparação diferente do primero para possibilitar indentificações de sequências de dados idênticas,
sem a necessidade do arquivo estar totalmente carregado na memória principal. Nas
próximas Subseções os dois algoritmos desenvolvidos serão descritos detalhadamente,
tanto o funcionamento como as decisões de implementação.
5.2.1
Algoritmo para deduplicação com carga completa do arquivo
na memória
Esse algoritmo foi o primeiro a ser desenvolvido. Ele foi baseado na forma de identificação de igualdade de conjuntos sequenciais de bytes do Rsync, no qual é informado um
valor de um função de hash aplicada à um chunk e esse valor é comparado com os valores
de hash obtidos a partir da execução da função de rolling hash aplicada ao arquivo em
que se deseja encontrar as partes duplicadas.
Será feita uma explicação do funcionamento do algoritmo utilizando um diagrama
de atividade simples em conjunto com abstrações da estrutura de dados em caixas, e
em seguida, o algoritmo será explicado mais profundamente, com discussão sobre a
implementação, utilizando pseudocódigo de alto nível para isso.
No cenário de exemplo para fundamentar a explicação, existem dois arquivos de
uma mesma música, um deles possui alguns bytes no início a mais do que o outro.
Suponha que esses bytes são informações de metadados inexistentes no segundo arquivo.
A música que não possui esses metadados a mais, está armazenada em um sistemas de
armazenamento de dados distribuído, que possui as informações sobre cada chunk desse
arquivo, como o valor do hash de 32 bits e do SHA-1. O cenário mostra o processamento
que é feito pelo algoritmo antes da música ser enviada para o sistema de armazenamento
distribuído. Sem um algoritmo de deduplicação integrado ao sistema de armazenamento,
esse novo arquivo seria totalmente copiado para ele, e no caso do sistema possuir um
49
5.2. DETALHANDO OS ALGORITMOS
algoritmo de deduplicação apenas para arquivos completos, ele também não conseguiria
a compressão dos dados nesse caso, já que apesar da maior parte do conteúdo dos dois
arquivos serem idênticos, esse tipo de algoritmo não consegue identificar igualdade de
partes do arquivo.
Antes de enviar o novo arquivo para o sistema de armazenamento, o processamento
para identificar partes do arquivo que são iguais a um dos chunks já armazenados é feita.
Para isso, o algoritmo exige, através da implementação da sua interface de comunicação,
que o sistema forneça as informações essenciais para fazer o processamento da deduplicação, como as informações dos valores dos fingerprints dos chunks. O algoritmo então
carrega o arquivo completo para a memória principal para poder fazer a análise dos bytes.
A variável windowsIndex indica a posição inicial da janela do rolling checksum no
arquivo. Essa janela tem o tamanho definido através de um parâmetro que é passado pelo
sistema de armazenamento e que tem como objetivo informar o tamanho padrão do chunk
armazenado no sistema.
A comparação inicia-se com a procura pelo primeiro chunk da lista passada para o
algoritmo através da interface. Como descrito na seção sobre o Rsync, o conteúdo do
chunk não é necessário para a identificação de uma sequência de bytes idêntica, para
isso, só é necessário o conhecimento dos valores dos fingerprints. Primeiramente, o valor
do hash fraco desse chunk é procurado no conteúdo do arquivo em memória. O hash
fraco é também calculado no conjunto inicial de bytes do arquivo em memória, que tem
o seu início indicado a partir na posição apontada pelo windowsIndex, e vai até o final
da janela. Esses dois valores são comparados, se eles forem diferentes, o byte inicial
da janela é incrementado em 1 (windowsIndex++) e o cálculo do rolling hash é feito
em cima do valor do hash da janela anterior. Esse procedimento é executado até que
os valores dos hashes sejam iguais ou o fim do arquivo seja alcançado. No exemplo
monstrado na Figura 5.1, quando o início da janela estiver no terceiro byte, o cálculo do
hash será idêntico ao procurado. Quando esses valores são iguais, é feito um cálculo
do SHA-1 no conjunto de bytes que está dentro da janela, e o valor é comparado com
o SHA-1 do chunk armazenado no sistema. Se esses valores forem diferentes, significa
que a comparação dos hashes fracos deu um falso positivo e o procedimento de busca
segue com o incremento do início da janela, caso contrário, é considerado que o conteúdo
que está dentro da janela é igual ao do chunk armazenado no sistema, e uma indicação
de referência é criada, para que os bytes não sejam enviados para o sistema. O início
da janela salta para a posição após o último byte do chunk encontrado, e a busca pelo
próximo começa a partir desse ponto.
50
5.2. DETALHANDO OS ALGORITMOS
Figura 5.1 Funcionamento do algoritmo 1.
A análise do pseudocódigo de alto nível do algoritmo vai ser feita a seguir. O
algoritmo implementado em Java está disponível na página do projeto no Github1 . Como
o algoritmo foi desenvolvido para ser uma interface Thrift 4.2.1, ele precisa receber
algumas variáveis que serão informadas pelo sistema de armazenamento. A estrutura
esperada com as informações dos chunks é basicamente, o hash de 32 bits, o SHA-1 e o
ID de cada um deles, para um maior ganho de desempenho eles precisam estar ordenados,
baseado no fato de que a probabilidade de que o chunk posterior seja duplicado se o
anterior for é grande. Vale ressaltar que nem todos os chunks armazenados no sistemna
precisam ser passados para o algoritmo, é recomendável que somente os pertencentes à
arquivos que tem probabilidade de serem similares sejam informados, como por exemplo,
os arquivos que são do mesmo tipo e que possuam um nome similar com o que vai ser
processado à procura de partes duplicadas.
O outro parâmetro esperado é uma string representando o caminho absoluto para o
1 https://github.com/paulofernando/dedupeer
51
5.2. DETALHANDO OS ALGORITMOS
arquivo no sistema de arquivos local, para que o algoritmo possa ler os seus bytes e fazer
o processamento com esses dados. Um objeto map<position,Chunk> é retornado, onde
position é referente à posição do byte inicial do conjunto sequencial de dados que formam
o chunk, e o valor no map é referente à informações sobre o chunk, como, o identificador
do chunk que está armazenado no sistema distribuído e que foi encontrado como duplicado, ou, no caso de não ter encontrado nenhum idêntico, as informações armazenadas
são as necessárias para que o sistema consiga identificar o conjunto sequencial que não
está duplicado, como posição inicial e final dentro do arquivo, e os valores calculados dos
hashes desse novo chunk, para que o dados dele sejam enviados para armazenamento.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
input: informações dos chunks armazenados e path do arquivo para ser deduplicado
output: apontador para os chunks duplicados no arquivo informado
for i = 0 to amountChunks do
index ← searchDeduplication(modFile, chunk[i].hash32)
if index <> -1 then
if window.sha1 = chunk[i].sha1 then
chunkRe f erences ←< index, chunkIn f o >
end if
end if
end for
index ← 0
bu f f er ← allocate(de f aultChunkSize)
while index < modFile.length do
if chunkReferences contains index then
if buffer position > 0 then
chunkRe f erences ←< index, newChunkIn f o >
bu f f er.clear()
end if
index ← index + newChunk.length
else
if buffer is full then
chunkRe f erences ←< index, newChunkIn f o >
bu f f er.clear()
else
bu f f er.put(nextByteInT heWindow)
index ← index + 1
52
5.2. DETALHANDO OS ALGORITMOS
27:
28:
29:
30:
31:
32:
33:
34:
end if
end if
end while
if buffer position > 0 then
chunkRe f erences ←< index, newChunkIn f o >
bu f f er.clear()
end if
returnchunkRe f erences
Na linha 3, o algoritmo executa uma iteração com todas as informações dos chunks
recebidas do sistema de armazenamento para serem procurados no arquivo passado como
parâmetro, arquivo esse previamente carregado na variável modFile. A variável index que
aparece pela primeira vez na linha 4, representa a posição incial do chunk duplicado no
arquivo local, essa identificação é feita através do método searchDeduplication, que nada
mais é do que um método que utiliza o rolling checksum para identificar um conjunto
de dados com o mesmo hash fraco do chunk atual da iteração. Quando o valor do
index for diferente de -1, será porque o método encontrou um conjunto de dados que
possui o mesmo valor de hash fraco do chunk atual da iteração, mas como já explicado
anteriormente, o hash fraco é só uma estratégia para economizar cálculos de um SHA-1,
pois ele é muito mais rápido de ser calculado, mas em contrapartida, a probabilidade de
colisão é alta, logo, para termos uma probabilidade de quase 100% que os dados são
idênticos, é feita uma comparação com o SHA-1. No caso dos valores do SHA-1 serem
iguais, é considerado que os chunks também são iguais, apesar de existir uma mínima
probabilidade de não serem. Essa problemática é discutida na seção 4.2.3.
A partir da linha 12 o algoritmo funcionará com o objetivo de identificar as partes do
arquivos que não estão duplicados, e adicionar os mesmo na variável que será retornada
para o sistema de armazenamento, à qual conterá as referências para os chunks que estão
no sistema, identificação essa que foi executada entre as linhas 3 e 10 do algoritmo. Nessa
linha, a variável buffer é criada com o tamanho de bytes igual ao padrão do sistema. O
buffer serve para armazenar os bytes iniciais que são descartados da janela toda vez que o
conjunto Xk ...Xl de bytes, que é o conteúdo dentro dela, não tenha seu fingerprint no map
passado pelo sistema de armazenamento. Como o próximo conjunto a ser procurado é o
Xk+1 ... Xl+1 , o primeiro byte que estava no conjunto de dados anterior é descartado da
nova verificação, com isso ele entra no buffer para se tornar parte de um novo chunk.
Na linha 14, é verificado se o conjunto de dados com início na posição atual do índice
foi encontrado duplicado no sistema na busca feita anteriormente, caso a condição seja
53
5.2. DETALHANDO OS ALGORITMOS
verdadeira, é verificado se o buffer possui algum dado, casa haja, é criado um novo chunk
com esses bytes alocados nele e a posição do índice é incrementada com o tamanho
padrão do chunk. Se a condição da linha 14 resultar em falso, é feito um teste se o buffer
ainda pode receber dados, se ele já estiver cheio, é criado um novo chunk com esses
dados e em seguida é feita uma limpeza no buffer. Se o buffer não tiver atingido o limite
máximo de alocação, o byte atual é armazenado nele e a posição do índice é incrementado
em 1, que foi a quantidade de bytes adicionados.
A linha 30 é necessária, porque o final do arquivo pode ser atingido antes do buffer
estar totalmente cheio, a linha 31 cria o chunk final com o conteúdo armazenado no buffer
e o coloca na estrutura que vai ser retornada para o sistema de armazenamento na linha
34.
5.2.2
Algoritmo com deduplicação particionada
Para que o Dedupeer fosse capaz de fazer deduplicação de arquivos sem um limite
de tamanho, foi desenvolvido um segundo algoritmo que tem como princípio base a
capacidade de processar esse tipo de arquivo, para isso, ele utiliza uma técnica de
particionamento em tamanhos que seja possível a alocação na memória principal.
Como na descrição do algoritmo anterior, será feita uma explicação de alto nível com
o mesmo cenário do primeiro algoritmo descrito em 5.2.1, em seguida, o algoritmo será
detalhadamente explicado através do pseudocódigo. Esse algoritmo implementado em
Java também pode ser encontrada na página do projeto no Github.
O processamento feito antes do envio do arquivo, para identificar as partes iguais com
os chunks no sistema, exige que as informações dos chunks estejam estruturadas de uma
forma diferente do primeiro algoritmo. Como entrada, a interface espera por informações
dos chunks que estão armazenados no sistema para que o algoritmo os procure no arquivo
a ser deduplicado, como no anterior, mas a estrutura de dados definida que organiza essas
informações é um map< weakHash, map<strongHash,chunkIDs> >, pois existe uma
probabilidade real de que dois chunks com conteúdo diferente tenham o mesmo valor
de um hash de 32 bits, que é conhecido como colisão de hash. Foi criado um outro
map interno que armazena os SHA-1 como chave, para que as informações de chunks de
mesmo hash fraco não sejam perdidas por sobrescrita de valor no map e tem como valor
um objeto que possui dois IDs, o do chunk e o do arquivo. A interface também espera
o caminho absoluto do arquivo a ser deduplicado, e um parâmetro que é a quantidade
máxima de bytes do arquivo que pode ser carregada para a memória por vez.
Primeiramente, o algoritmo recebe o map com as informações dos chunks armazena-
54
5.2. DETALHANDO OS ALGORITMOS
Figura 5.2 Funcionamento do algoritmo 2
dos no sistema. Em seguida, a quantidade de bytes máxima informada pelo sistema como
parâmetro da interface Thrift é carrega para a memória principal, ou o arquivo completo
se ele for menor que a quantidade máxima de bytes que pode ser carregada por vez. Veja
a 5.2.
Diferente do primeiro algoritmo, este utiliza uma estratégia de comparação diferente
do Rsync, e que o torna capaz de fazer o processamento de arquivos em partes. O Rsync
procura um determinado conjunto de dados que tenha um fingerprint específico, e pra isso
ele precisa percorrer o arquivo até que o encontre, ou até que alcance o final do mesmo.
O algoritmo para deduplicação particionada aproveita o complexidade temporal (tempo
de execução) da estrutura de map (hashtable), a qual é O(1), e ao invés de percorrer o
conteúdo de um arquivo à procura de um fingerprint, ele calcula o fingerprint dos dados
na janela do arquivo em memória e em seguida faz uma busca no map, ou seja, diferente
do Rsync a comparação é feita de forma inversa.
Se o hash de 32 bits dos dados dentro da janela estiver na estrutura de map, é feito
o cálculo do SHA-1 dos mesmos dados e essa valor é procurado dentro do map interno
que é o valor da chave de hash 32 bits encontrada. Se o hash de 32 bits ou o SHA-1
55
5.2. DETALHANDO OS ALGORITMOS
não forem encontrados, é feito um teste para saber se a quantidade de dados restante na
parte carregada para a memória é menor que o tamanho padrão do chunk, se for menor, é
criado um chunk com o conteúdo do buffer e outro com o conteúdo restante, e uma outra
parte do arquivo é carregado para a memória. Isso é feito porque para calcular o valor do
hash de 32 bits da função de rolling checksum, é necessário ter uma quantidade de dados
com o tamanho padrão exato do chunk do sistema. Se o tamanho restante for maior, o
processamento segue normalmente, com a janela sendo incrementada em 1 byte por vez.
A seguir vai ser feita uma explicação mais aprofundada sobre o algoritmo através
da análise do pseudocódigo de alto nível. O input já foi descrito acima, e o output é
o mesmo do primeiro algoritmo, uma referência para os chunks duplicados dentro do
arquivo e as informações sobre os novos chunks.
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
input: informações dos chunks armazenados, path do arquivo para ser deduplicado e
quantidade de bytes para carregar para a memória por vez
output: apontador para os chunks duplicados no arquivo informado
o f f set ← 0
validate(bytesToLoadByTime)
divideInTime ← f ileLength/bytesToLoadByTime
bu f f er ← allocate(de f aultChunkSize)
for i = 0 to divideInTime do
localIndex ← 0
partO f File ← getNextBlockO f File(o f f set)
currentChunk ← getNextChunkPartO f File(localIndex)
while localIndex < partOfFile.length do
if partOfFile.length - localIndex + moreBytesToLoad = defaultChunkSize then
partO f File ← getNextBlockO f File(o f f set)
currentChunk ← getNextChunkPartO f File(localIndex)
o f f set ← o f f set + moreBytesToLoad
end if
if chunk[i].hash32 contains window.hash32 then
if currentChunk = null then
currentChunk ← getNextChunkPartO f File(localIndex)
end if
if chunk[i].sha1 contains window.sha1 then
if buffer has data then
newChunk ← createNewChunk(bu f f er)
56
5.2. DETALHANDO OS ALGORITMOS
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
chunkRe f erences ←< globalIndex−newChunk.length, newChunk.in f o >
bu f f er.clear()
end if
chunkRe f erences ←< globalIndex, re f erenceToT heChunk >
globalIndex ← globalIndex + currentChunk.length
localIndex ← localIndex + currentChunk.length
currentChunk ← getNextChunkPartO f File(localIndex)
end if
end if
if not duplicate then
currentChunk ← null
if buffer is full then
newChunk ← createNewChunk(bu f f er)
chunkRe f erences ←< globalIndex − bu f f er.position, newChunk.in f o >
bu f f er.clear()
else
if partOfFile.length - (localIndex + defaultChunkSize) > 0 then
bu f f er.put(partO f File[localIndex])
globalIndex ← globalIndex + 1
localIndex ← localIndex + 1
else
newChunk ← createNewChunk(partO f File, localIndex−bu f f er.position)
46:
chunkRe f erences ←< globalIndex−bu f f er.position, newChunk.in f o >
47:
localIndex ← localIndex + newChunk.length − bu f f er.position
globalIndex ← globalIndex + newChunk.length − bu f f er.position
bu f f er.clear()
if localIndex < partOfFile.length then
newChunk ← createNewChunk(partO f File, localIndex)
chunkRe f erences ←< globalIndex, newChunk.in f o >
bu f f er.clear()
localIndex ← localIndex + newChunk.length
48:
49:
50:
51:
52:
53:
54:
57
5.2. DETALHANDO OS ALGORITMOS
55:
56:
57:
58:
59:
60:
61:
62:
63:
globalIndex ← globalIndex + newChunk.length
end if
end if
end if
end if
end while
o f f set ← o f f set + bytesToLoadByTime
end for
returnchunkRe f erences
O método validate, chamado na linha 4, verifica se o valor passado pelo sistema para
informar a quantidade de bytes para ser carregado por vez na memória é maior que o
tamanho do arquivo, se esse valor for maior, ele é configurado com o tamanho do arquivo,
caso contrário, é feita uma aproximação para o múltiplo do tamanho padrão do chunk que
seja mais próximo do valor informado, para que a probabilidade de um chunk que possua
um idêntico armazenado no sistema não seja dividido entre duas cargas diferentes para a
memória, fato que se ocorresse, impossibilitaria o algoritmo de identificar a igualdade. A
linha 5 calcula a quantidade de cargas que precisarão ser feitas para a memória, valor este
utilizado como quantidade de iterações que a estrutura de repetição da linha 7 executará.
O método getNextBlockOfFile, utilizado na linha 9, retorna um array de bytes do
arquivo que será deduplicado a partir da posição definida como parâmetro, esse array de
bytes é o conteúdo que é carregado para a memória por iteração. A partir desse array, é
criado o primeiro chunk do arquivo que está na memória para análise de duplicata.
Na linha 11 é iniciada a iteração na parte do arquivo carregada em memória para
análise. A condicional da linha 12 é uma estratégia para não perder a identificação de
um chunk duplicado quando este está no final da parte do arquivo que foi carregado
para a memória, e tiver sido encontrado grande parte da carga como idêntica à de outro
arquivo já no sistema. Basicamente, esta parte do algoritmo serve para deixar o último
chunk da carga com o tamanho padrão do sistema, e assim, possibilitar a identificação de
igualdade. Observando o exemplo da 5.3, percebe-se que sem a carga extra de bytes, o
chunk representado pelos 4 hexadecimais 7C CE 72 A4, mesmo sendo duplicado, não
será identificado como tal pelo algoritmo sem a carga extra de dados.
Este parece ser um problema pequeno, mas não é. Supondo que todo conteúdo das
cargas posteriores do arquivo já estejam armazenadas no sistema por fazer parte de uma
versão anterior do mesmo arquivo, sem a carga extra de bytes, será deixado de deduplicar
um chunk por carga, pois parte dele estará no final de uma carga e a outra estará no
58
5.2. DETALHANDO OS ALGORITMOS
Figura 5.3 Vantagem da utilização da carga extra de dados
começo da posterior. Essa parte que ficará no começo da outra carga, sempre deixará
o último chunk sem todos os bytes necessários para a identificação da deduplicação na
mesma carga, acarretando assim uma perda de deduplicação para cada iteração à frente.
Na linha 17 é verificado se o map possui uma chave com o hash fraco calculado
da janela atual. A linha 18 é para evitar recarga de bytes na memória. Em seguida
é verificado se o map que está como valor da chave encontrada possui o SHA-1 que
representa os bytes dentro da janela, se esse valor for encontrado, é verificado se o buffer
está com algum dado, se sim, esses dados são transformados em um novo chunk e na
linha 27 a referência do chunk duplicado é salva na estrutura.
Na linha 35 é feita uma verificação para saber se o buffer está cheio, caso esteja, todo
o seu conteúdo é transformado em um único chunk e o mesmo é esvaziado para poder
receber os bytes iniciais da janela quando a mesma estiver em uma posição em que o
conjunto de bytes dentro dela não seja encontrado armazenado no sistema.
Se o buffer ainda possuir espaço vazio, é verificado se o restante do conteúdo carregado
para a memória que ainda não foi processado é maior que o tamanho padrão do chunk,
caso seja, o byte inicial da janela é adicionado ao buffer, já que não foi encontrado o
fingerprint do conteúdo da janela nos dados passados pelo sistema, e o índice do início
da janela é incrementado em 1. Se a quantidade de bytes não processados for menor que
o tamanho padrão, é criado um chunk com os dados dentro do buffer e um outro com o
restante dos bytes.
Por fim, na linha 61 o offset para a carga dos dados no arquivo local é incrementado
59
5.3. SUMÁRIO DO CAPÍTULO
com a quantidade de bytes que foram carregados na última vez. E na 63 é onde está
localizado o comando de retorno da variável com todos os novos chunks e referências aos
já armazenados, que juntos formam o arquivo local.
5.3
Sumário do capítulo
Neste capítulo, inicialmente foi feita uma introdução sobre o funcionamento do Rsync,
que é um algoritmo para otimizar a transferência de arquivos entre computadores remotos
e que serve como base de grande parte dos algoritmos de deduplicação de arquivos. Em
seguida, foram discutidos os principais conceitos por trás da eficiência da deduplicação,
o rolling checksum e o fingerprinting.
Depois da introdução dos conceitos fundamentais para o desenvolvimento dos dois
algoritmos que foram implementados no projeto, foi feita uma análise bem detalhada
do funcionamento do primeiro deles, que é o algoritmo para deduplicação com carga
completa do arquivo na memória, o qual utiliza uma técnica muito similar ao Rsync. Foi
apresentado um diagrama sobre o algoritmo, e o seu funcionamento explicado. Depois da
apresentação do funcionamento, o pseudocódigo de alto nível do algoritmo foi explicado
em detalhes.
Por fim, foi feita a explicação do segundo algoritmo desenvolvido, o algoritmo com
deduplicação particionada, o qual seguiu a mesma estrutura da primeira explicação.
Primeiro, foi feita uma análise detalhada do funcionamento do algoritmo através de um
diagrama, e depois, apresentado e explicado o pseudocódigo de alto nível.
No capítulo a seguir, será apresentada uma analise de desempenho, tanto de tempo
como de compressão, para o algoritmo com deduplicação particionada que foi apresentado
neste Capítulo.
60
6
Análise de desempenho
Neste capítulo é feita uma análise do desempenho do Dedupeer integrado com o
Dedupeer File Storage. Será feita uma análise para identificação do melhor algoritmo de
hashing para o sistema e um estudo sobre as taxas de compressão alcançadas dentro de um
conjunto de tamanho de chunks para identificar a eficiência da economia proporcionada
pelo algoritmo de deduplicação desenvolvido.
Serão feitas avaliações no tempo de armazenamento, deduplicação, deduplicação
juntamente com o armazenamento, e reidratação, que é a remontagem do arquivo original
através dos chunks armazenados e deduplicados.
6.1
Datasets
Para comparar sistemas de deduplicação de dados diferentes é preciso possuir o
mesmo conjunto de dados, pois a recriação de datasets a partir da mesma porcentagem
de modificação não funcionam com deduplicação. As modificações precisam estar
exatamente localizada na mesma posição ou a avaliação será falha, logo, os arquivos
testados devem ser os mesmos.
O trabalho [41] trata justamente sobre quais datasets devem ser usados para fazer
avaliações em sistemas de deduplicação de dados. Nele foram analisados 33 artigos sobre
deduplicação publicados entre os anos de 2000 e 2011 nas mais relevantes conferências
sobre storage do mundo, entre elas: Usenix ATC, Usenix FAST, SYSTOR e IEEE MSST.
Foi feita uma categorização dos 120 datasets utilizados nesses artigos, os quais
ficaram divididos em:
1. Datasets privados, não acessível para qualquer indivíduo;
2. Datasets públicos mas difíceis de serem reproduzidos;
61
6.1. DATASETS
3. Datasets criados sinteticamente;
4. Datasets públicos facilmente reproduzível.
Dos 33 artigos avaliados, 29 deles utilizaram pelo menos um dataset privado, logo não
pode ser feita uma comparação entre os sistemas analisados nesses artigos e outro que não
possa ser avaliado com esses dados privados. Os 4 restantes utilizam conjuntos de dados
sinteticamente criados os quais não podem ser reproduzidos pois algumas informações
sobre a sua criação foram omitidos.
Baseado na categorização citada acima, os datasets são: 64 privados (53%), 17 são
públicos e difíceis de reproduzir (14%), 11 são sintetizados com detalhes da sua geração
omitidos (9%). O que dá um total de 76% de datasets inutilizáveis para comparação
entre sistemas. Os 24% que são públicos são considerados muito pequenos para uma
comparação ou são arquivos de máquinas virtuais de tipos muito variados.
Os dados utilizados nas análises de desempenho do Dedupeer e do Dedupeer File
Storage foram arquivos de máquinas virtuais e de código-fonte armazenados em um
arquivo tar. Para a análise do tempo gasto nas principais operações foram utilizadas as
seguintes versões do Kernel do Linux, os quais podem ser encontrados nesse endereço:
https://www.kernel.org/.
1. stable: 3.9.8 datado de 27 de junho de 2013 (Latest Stable Kernel).
2. mainline: 3.10-rc7 datado de 22 de junho de 2013
A versão 3.9.8 (stable) foi utilizada como base para a deduplicação da versão 3.10-rc7
(mainline).
Para a avaliação da taxa de compressão alcançada com o algoritmo desenvolvido,
foram utilizados dados com modificações de conteúdo mais complexas e maiores dos que
as obtidas com o Kernel do Linux. Para essa avaliação foram utilizadas duas imagens de
máquinas virtuais, que são simulações de computadores reais através de software, com
Ubuntu 12.10 instalados. Em uma delas o Ubuntu foi instalado sem atualizações, essa é a
máquina virtual que será usada como arquivo base para deduplicação.
A segunda máquina virtual é a primeira máquina com uma atualização. O sistema
operacional da máquina virtual foi atualizado com todas as atualizações disponíveis até o
dia 2 de junho de 2013 às 13:17. 356 arquivos foram baixados, totalizando 330,3MB de
dados, os quais após a instalação ocuparam 1350MB a mais do que a máquina virtual
antes da atualização.
A escolha de dados públicos e de fácil acesso possibilitará futuras comparações com
trabalhos relacionados.
62
6.2. ANÁLISE DE DESEMPENHO UTILIZANDO O CÓDIGO FONTE DO KERNEL DO
LINUX
6.2
Análise de desempenho utilizando o código fonte do
Kernel do Linux
Esta primeira análise será focada no desempenho para deduplicação do Dedupeer, e
do armazenamento e reidratação do Dedupeer File Storage. Foram feitas 14 execuções
de cada uma das principais operações, armazenamento, deduplicação, deduplicação +
armazenamento e reidratação, cada uma delas para 128KB, 64KB, 32KB, 16KB e 8KB.
Esses valores foram escolhidos por serem as potências de dois próximas ao tamanho
recomendado por alguns sistemas de deduplicação, 8KB e 16KB, e o tamanho utilizado
no Ustore, o sistema onde o Dedupeer foi implantado, que é 128KB.
O computador utilizado para a execução da análise de desempenho foi um Windows
7 Profissional com Service Pack 1 de 32 bits com processador Intel Core 2 Quad Q6600
2.40GHz e 3,24GB de memória RAM DDR2.
Para a operação de armazenamento foi enviado um arquivo .tar com todo o códigofonte do Kernel do Linux na versão 3.9.8 (513.945.600 bytes) e o tempo até a conclusão
da operaçao foi registrado. A utilização do formato tar é muito importante para fazer a
deduplicação dos arquivos pois nenhuma compressão é aplicada aos arquivos que são
armazenados nele, diferente do zip por exemplo, que modifica o conteúdo dos arquivos
e isso degrada a taxa de compressão obtida com a deduplicação pelo fato do conteúdo
dos arquivos serem transformados, o que impossibilita a descoberta de conjunto de dados
idênticos.
Foi registrado também o tempo do início da operação de deduplicação até o término,
e também o tempo do início da deduplicação até o término do armazenamento do arquivo
deduplicado. Para essas operações foi utilizado o arquivo .tar com todo o código fonte
do Kernel do Linux na versão posterior à 3.9.8 que estava disponível no site, que foi a
versão 3.10-rc7 (521.420.800 bytes).
Por último, foi registrado o tempo gasto para fazer a reidratação do arquivo deduplicado. Todos os dados capturados na avaliação estão disponibilizados no formato do
Mathematica 91 no apêndice B.1.
Operação de armazenamento
As Figuras 6.1 e 6.2 mostrarão todos os tempos em milissegundos capturados das 14
execuções da operação de armazenamento do Dedupeer File Storage para os algoritmos
1 http://www.wolfram.com/mathematica/
63
6.2. ANÁLISE DE DESEMPENHO UTILIZANDO O CÓDIGO FONTE DO KERNEL DO
LINUX
de hashing MD5 e SHA-1 para cada tamanho de chunk analisado, os quais foram para
todas as operações: 128KB, 64KB, 32KB, 16KB e 8KB. Os dados foram plotados no
gráficos na mesma ordem em que foram capturados.
Figura 6.1 Tempo em milissegundos para as execuções da operação de armazenamento utilizando
MD5
Figura 6.2 Tempo em milissegundos para as execuções da operação de armazenamento utilizando
SHA-1
Para uma melhor comparação entre o tempo gasto no armazenamento, o gráfico
64
6.2. ANÁLISE DE DESEMPENHO UTILIZANDO O CÓDIGO FONTE DO KERNEL DO
LINUX
na Figura 6.3 mostrará o emparelhamento dos dados ordenados entre os algoritmo de
hashing usados para cada tamanho de chunk separado. A partir dos gráficos, percebe-se
que os tempos para cada operação de armazenamento são similares independente do
algoritmo de hashing utilizado.
Para uma melhor visualização, a comparação do tempo para cada tamanho de chunk
separado está no apêndice C.1.
Figura 6.3 Tempo em milissegundos para as execuções da operação de armazenamento, separadas
por tamanho de chunk
A seguir será feito um teste estatístico para descobrir se a utilização do SHA-1 tem
o mesmo desempenho do MD5. Como explicado anteriormente, o MD5 é utilizado em
alguns dos sistemas que fazem deduplicação de dados, e que apesar da probabilidade de
colisão de hashes existir tanto no MD5 como no SHA-1, já se tem registro de colisão de
hashes com MD5 mas ainda nenhum registro desse problema com o SHA-1. Se os dois
algoritmos tiverem um desempenho similar ou se o desempenho do SHA-1 for inferior ao
MD5 mas não à ponto de anular a vantagem da falta de registro com colisão de hashes,
não há motivos para não escolher o SHA-1 como algoritmo de hashing padrão para o
Dedupeer File Storage.
Todos os valores de p podem ser encontrados na Tabela 6.1, esse é o valor utilizado
para identificar se os dados capturados seguem a curva normal, e com isso saber qual
65
6.2. ANÁLISE DE DESEMPENHO UTILIZANDO O CÓDIGO FONTE DO KERNEL DO
LINUX
p-values
MD5
SHA-1
128KB
0,674511
0,903653
64KB
0,621354
0,868695
32KB
0,198659
0,258855
16KB
0,0330624
0,44823
8KB
0,293449
0,0219761
Tabela 6.1 p-values para os dados capturados na operação de armazenamento
método estatístico utilizar. Todos os valores vão ser exibidos na tabela para caso alguém
queira fazer teste com outro tamanho de chunk.
Na Tabela 6.1 serão mostrados os valores de p dos dados da operação de armazenamento. O intervalo de confiança adotado para os testes foi de 95% ou seja, caso o valor de
p seja maior que o nível de significância, que é 0,05, o T-Test pode ser selecionado, caso
contrário, a análise será feita através de um teste não-paramétrico, já que o tamanho da
amostra é inferior à 40 e o T-Test só deve ser feito com dados não normais se a amostra
tiver tamanho superiores à 40.
Para analisar qual o algoritmo se comporta melhor na operação de armazenamento,
vai ser feito um T-Test emparelhado com as amostras coletadas com 32KB, pois todos os
dados são normais, o que torna a análise mais fácil. Como hipótese nula, será considerado
que a média de tempo gasto para duas amostras são iguais, e como hipótese alternativa
será considerado que a média de tempo gasto para a operação de armazenamento com
MD5 é maior do que com SHA-1.
H0 : µ0 − µ1 = 0 vs. H1 : µ0 > µ1
Aplicando o T-Test emparelhado, resultou em um p-value 0,695936. Como o p-value
é maior do que 0,05, não devemos rejeitar a hipótese nula, logo, não podemos afirmar
que a média de tempo com MD5 é maior do que com SHA-1.
Operação de deduplicação
Os dados obtidos a partir das 14 execuções de deduplicação estão plotados nos
Gráficos 6.4 e 6.5. Com a análise desses dados é possível avaliar apenas o desempenho do
algoritmo de deduplicação desenvolvido e utilizado no Dedupeeer File Storage, pois os
dados registrados nessas execuções foram o tempo necessário para o algoritmo buscar os
chunks dentro do arquivo a ser enviado para armazenamento. Logo, os valores plotados
nesse gráfico se referem ao tempo entre o início e o fim da deduplicação apenas, o qual
engloba os seguintes passos: a busca da informações dos chunks armazenados no sistema,
a montagem da estrutura de dados para comunicação com a biblioteca através do Thrift,
a procura dos chunks dentro do arquivo pela biblioteca Dedupeer, a criação da estrutura
66
6.2. ANÁLISE DE DESEMPENHO UTILIZANDO O CÓDIGO FONTE DO KERNEL DO
LINUX
de dados com o mapeamento dos chunks e das referências aos chunks duplicados, e o
retorno da estrutura através do Thrift para o Dedupeer File Storage.
Figura 6.4 Tempo em milissegundos das execuções da operação de deduplicação, separadas por
tamanho de chunk, utilizando SHA-1
Figura 6.5 Tempo em milissegundos das execuções da operação de deduplicação, separadas por
tamanho de chunk, utilizando MD5
Da mesma forma que na operação anterior, a comparação do tempo para cada tamanho
de chunk está no apêndice, na seção C.2.
Analisando os dados obtidos das execuções de deduplicação, percebe-se que o algoritmo de deduplicação utilizando o SHA-1 obteve um desempenho superior ao mesmo
67
6.2. ANÁLISE DE DESEMPENHO UTILIZANDO O CÓDIGO FONTE DO KERNEL DO
LINUX
algoritmo utilizando MD5. A média de tempo foi bem significativa, para 128KB o SHA-1
obteve uma média de 36553 milissegundos para executar a operação, enquanto que com
MD5 o tempo médio foi de 133255 milissegundos. Com chunks de 8KB de tamanho a
diferença entre as médias foi menor, o tempo para o MD5 (227582 ms) foi menos de duas
vezes maior do que o do SHA-1 (118409 ms).
Apesar da média do tempo ser significativamente maior utilizando MD5 em relação ao
SHA-1, é preciso fazer a análise estatística para confirmar se com esses dados é possível
saber qual o algoritmo de hashing torna a deduplicação mais eficiente.
Para analisar qual o algoritmo se comporta melhor na operação de deduplicação, o
T-Test emparelhado foi feito para as amostras de 16KB.
Da mesma forma que o teste anterior, como hipótese nula será considerado que a
média de tempo gasto para deduplicação é igual entre as amostras, e como hipóteses
alternativa será considerado que a média de tempo com MD5 é maior do que com SHA-1.
H0 : µ0 − µ1 = 0 vs. H1 : µ0 > µ1
Ao aplicar o T-Test emparelhado, o p-value foi 1,03839x10−10 . Como o p-value é
menor do que 0,05, devemos rejeitar a hipótese nula e aceitar a alternativa. Como a
hipótese alternativa deve ser aceita, é concluído que a média de tempo gasta com MD5
para deduplicação é realmente maior do que o tempo gasto com SHA-1, ou seja, para a
operação de deduplicação o SHA-1 foi mais eficiente que o MD5.
Operação de deduplicação + armazenamento
Nesta seção será mostrado os dados da operação de deduplicação somada com a
operação de armazenamento, que representa a operação completa de deduplicação de um
arquivo no sistema de armazenamento.
Nesta operação, os dados capturados também apontam uma vantagem significativa
para o SHA-1, esses dados podem ser vistos plotados em gráficos separados por algoritmo
de hashing nas Figuras 6.6 e 6.7. A média do tempo calculado para o SHA-1 utilizando
chunks de 128KB foi 36552.9 milissegundos, enquanto a médio do MD5 para 128KB foi
249779 milissegundos, ou seja, com o SHA-1 a operação foi em média 6,8 vezes mais
rápida que com MD5. Para chunks de 8KB o SHA-1 teve média de 118409 milissegundos,
e o MD5 de 1213682 milissegundos. Com chunks de 8KB o SHA-1 foi em média 10,2
vezes mais rápido.
Os gráficos emparelhados dessa operação separados por tamanho de chunk também
estão no Apêndice, especificamente nessa seção C.3.
68
6.2. ANÁLISE DE DESEMPENHO UTILIZANDO O CÓDIGO FONTE DO KERNEL DO
LINUX
A hipótese nula foi definida como a média de tempo gasto para deduplicação +
armazenamento sendo igual tanto para o MD5 como SHA-1, e como hipótese alternativa
considerando que o tempo com MD5 é diferente com SHA-1.
H0 : µ0 − µ1 = 0 vs. H1 : µ0 6= µ1
Como não tem duas amostras normais para serem comparadas, nesse caso será feita a
análise a partir do Wilcoxon signed-rank test. O p-value resultante foi 0,00109705, com
isso a hipóteses nula deve ser rejeitada e concluímos que o tempo médio entre eles foi
diferente.
Figura 6.6 Tempo em milissegundos das execuções da operação de deduplicação + armazenamento, separadas por tamanho de chunk, utilizando SHA-1
69
6.2. ANÁLISE DE DESEMPENHO UTILIZANDO O CÓDIGO FONTE DO KERNEL DO
LINUX
Figura 6.7 Tempo em milissegundos das execuções da operação de deduplicação + armazenamento, separadas por tamanho de chunk, utilizando MD5
Operação de reidratação
Para a operação de reidratação também foram feitas 14 execuções para cada um dos
algoritmos de hashing SHA-1 e MD5.
Nas operações de deduplicação os resultados foram diferentes das duas operações
anteriores, nesta operação o algoritmo de MD5 foi mais rápido do que o SHA-1. Comparando as médias do maior e menor tamanho de chunk testado, para o chunk de 128KB o
tempo médio de execução da operação de reidratação com MD5 foi de 43087 milissegundos, enquanto o tempo médio do SHA-1 foi 68590,6 milissegundos. Para o chunk de 8KB
o MD5 foi pouco mais de 5 vezes mais rápido, tendo média de 226346 milissegundos
contra 1166748 milissegundos do SHA-1. Todos os dados das execuções dessa operação
podem ser vistos nas Figuras 6.8 e 6.9, e os dados emparelhados por tamanho de chunk
estão no Apêndice C.4.
70
6.2. ANÁLISE DE DESEMPENHO UTILIZANDO O CÓDIGO FONTE DO KERNEL DO
LINUX
Figura 6.8 Tempo em milissegundos das execuções da operação de reidratação, separadas por
tamanho de chunk, utilizando SHA-1
Figura 6.9 Tempo em milissegundos das execuções da operação de reidratação, separadas por
tamanho de chunk, utilizando MD5
Para avaliar qual o melhor algoritmo para essa operação, foi definido o teste de
hipótese, onde a hipótese nula diz que a média de tempo gasto para a reidratação com
MD5 é igual à com SHA-1, e como hipóteses alternativa que a média de tempo com MD5
é menor do que com SHA-1.
H0 : µ0 − µ1 = 0 vs. H1 : µ0 < µ1
71
6.2. ANÁLISE DE DESEMPENHO UTILIZANDO O CÓDIGO FONTE DO KERNEL DO
LINUX
Aplicando o T-Test emparelhado, o p-value foi 6,34527x10−17 . Como o p-value é
menor do que 0,05, devemos rejeitar a hipótese nula e aceitar a alternativa. Logo, como
previsto, é concluído que a média de tempo gasto com MD5 para reidratação é menor do
que o tempo gasto com SHA-1, ou seja, para a operação de reidratação o MD5 foi mais
eficiente que o SHA-1.
6.2.1
Mapa de chunks deduplicados
Foi desenvolvida uma funcionalidade no Dedupeer File Storage que exibe, em uma
barra horizontal, as áreas do arquivo que foram economizadas com a deduplicação
aplicada nele. A barra possui duas cores, a azul representa as áreas do arquivo onde o
seu conteúdo binário foi salvo no sistema de armazenamento pelo fato de não ter sido
encontrado partes duplicadas já armazenadas, e a área pintada de cinza representa as
partes do arquivo que foram economizadas no armazenamento, os dados pertencentes à
essas áreas foram encontrados como já presentes nos chunks armazenados no sistema e
só as referências à eles foram salvas.
Figura 6.10 Mapa de chunks deduplicados da versão 3.10-rc7 do código-fonte do Kernel do
Linux processado com os chunks da versão 3.9.8, para chunks com tamanho 128, 64, 32, 16 e
8KB
Este mapa apresentado pode ocultar algumas áreas, pois como as áreas pintadas são
proporcionais e a quantidade de chunks do arquivo deduplicado e apresentado na Figura
6.10 foi de 66318 na versão de 8KB, chunks deduplicados de forma isoladas podem não
ser exibidos pois a área ocupada por eles pode não ser suficiente para que seja exibida na
barra de modificações.
Como esperado, a deduplicação com chunk de 128KB foi a que menos economizou
espaço, já que para que um chunk fosse identificado como duplicado, seria necessário
encontrar uma sequência de dados binários com tamanho de 128KB que pertencesse à
versão de 3.9.8.
Para a versão de 128KB o arquivo foi dividido em 4025 chunks dos quais 119 foram
deduplicados, o que dá uma economia de aproximadamente 3%. Para 64KB foram
72
6.3. ANÁLISE DE ECONOMIA UTILIZANDO MÁQUINAS VIRTUAIS
Chunks
128KB
64KB
32KB
16KB
8KB
VDI armazenado
24337
48674
97347
194694
389387
VDI atualizado deduplicado
35571
71280
142498
284218
566985
VDI atualizado armazenado
35137
70274
140547
281094
562187
Tabela 6.2 Quantidade de chunks criados
criados 8088 chunks dos quais 528 foram deduplicados, resultando em um total de 6,5%
de economia. Com 32KB o arquivo foi dividido em 16351 pedaços dos quais 2378 foram
deduplicados, mais de 11% do total. Para 16KB, o arquivo foi dividido em 32995 partes
das quais 8870 foram deduplicados, resultando em 25% de economia. E por fim, pra
chunks de 8KB, dos 66318 partes, 27989 foram deduplicados, o que acarretou em uma
economia de 41%.
Como os arquivos de código-fonte são pequenos, geralmente menores do que os
tamanhos de chunk adotados, qualquer modificação em um deles faz com que nenhuma
parte do mesmo seja deduplicada, por isso, a deduplicação desse tipo de arquivo não é tão
eficiente. Para uma deduplicação mais eficiente, o ideal seria que o tamanho dos arquivos
que foram agrupados dentro do tar fosse maior do que o tamanho padrão do chunk.
6.3
Análise de economia utilizando máquinas virtuais
Essa segunda análise foi basicamente para avaliar a economiza que pode ser alcançada
através do algoritmo com a deduplicação de máquinas. Foram utilizados dois arquivos
.vdi (Virtual Disk Image), um deles com o Ubuntu versão 10.12 sem qualquer alteração e
o segundo com o mesmo sistema operacional só que com uma atualização, como descrito
na seção 6.1.
Primeiramente, o arquivo vdi sem a atualização do Linux, arquivo esse com tamanho
3.189.854.208 bytes, foi enviado para o Dedupeer File Storage. Em seguida, foi feita a
deduplicação do arquivo vdi com o Linux atualizado, de tamanho 4.605.431.808 bytes,
tendo como base o arquivo subido anteriormente. Esses passos foram executados para 5
tamanho diferentes de chunk: 128KB, 64KB, 32KB, 16KB e 8 KB. Para questões comparativas, o arquivo Linux atualizado também foi armazenado no sistema sem deduplicação.
A quantidade de chunks geradas com essas três execuções serão exibidas na tabela 6.2.
O fato da quantidade de chunks ser diferente entre a deduplicação e o armazenamento
do mesmo arquivo, se dá porque com a deduplicação podem ser criados vários chunks
73
6.3. ANÁLISE DE ECONOMIA UTILIZANDO MÁQUINAS VIRTUAIS
com tamanho inferior ao tamanho padrão, enquanto que no armazenamento, o único
chunk que pode ter um tamanho inferior ao padrão é o último.
O gráfico de barras abaixo mostra a quantidade de dados armazenados no sistema
tanto para o arquivo sem deduplicação, como para o arquivo deduplicado com chunks de
tamanhos variados. A economia alcançada foi de 55% para chunks de 128KB, 60% para
64KB, 63% para 32KB, 66% para 16KB e 69% para 8KB. A quantidade de bytes armazenados para cada um deles foi respectivamente: 4.605.431.808 bytes (sem economia),
2.072.762.428, 1.878.494.141, 1.710.946.626, 1.574.787.731, 1.447.578.619.
Levando em consideração que o arquivo utilizado como base para a deduplicação
tinha 3.189.854.208 bytes, e que a diferença entre ele e o arquivo que foi deduplicado é de
1.415.577.600 bytes, a economia alcançada em relação à quantidade de dados comparados
é de: 79,397% para 128KB, 85,488% para 64KB, 90,740% para 32KB, 95,731% para
16KB e 98,997% para 8KB.
Figura 6.11 Tamanho em megabytes ocupado pelo arquivo no sistema, com a porcentagem de
economia alcançada
O mapa de modificações para cada um dos tamanhos de chunk analisados pode ser
visto na Figura 6.11. Da mesma forma que o apresentado anteriormente, a cor azul
representa as áreas do arquivo onde o seu conteúdo binário foi salvo no sistema e a cinza
representa as áreas onde os chunks foram deduplicados.
Figura 6.12 Mapa de chunks deduplicados da máquina virtual Linux 12.10 atualizada processada
com os chunks da mesma máquina virtual sem atualização, para chunks com tamanho 128, 64, 32,
16 e 8KB
74
6.4. O USTORE
6.4
O Ustore
O Ustore2 tem como propósito a realização de backups de dados em nuvens privadas.
As empresas podem usar parte da área de armazenamento do disco que está ociosa nos
seus computadores para criar um nuvem de dados interna e ter maior controle sobre seus
dados.
Ele tem como principal objetivo o backup distribuído de dados e é construído em
uma arquitetura peer-to-peer (P2P) híbrida, que são redes peer-to-peer que possuem
entidades centrais [38]. Como a ideia principal do sistema é a comunicação direta entre
os computadores, essa arquitetura foi escolhida. Para obter um melhor desempenho,
optou-se pela utilização de servidores, o que fez com que a arquitetura peer-to-peer
tornar-se híbrida.
A comunicação entre as entidades que compõem o sistema é feita através da plataforma JXTA, que é um conjunto de protocolos utilizado para criar uma rede peer-to-peer
[45].
Na versão 1.7 do Ustore o Dedupeer foi adicionado para fazer a deduplicação dos
arquivos versionados dos usuários. Para cada nova versão de um arquivo que é sincronizado no sistema, o processo de deduplicação é executado antes dos dados serem enviados
para os peers, o que economiza tanto a banda de rede como o espaço ocupado nos peers.
Outra vantagem que o Dedupeer adiciona ao Ustore é a possibilidade de ser oferecido
mais espaço do que o sistema possui fisicamente, já que os chunks deduplicados não têm
seus dados salvos, apenas as referência para os chunks que já estão armazenamentos.
6.5
Sumário do capítulo
Neste capítulo foram analisados dois testes, um de desempenho e outro de taxa de
compressão para máquinas virtuais. No teste de desempenho concluiu-se que para a
operação de armazenamento não se pode afirmar se o tempo médio da operação com
MD5 é diferente do tempo com SHA-1. Para deduplicação, o sistema com SHA-1 foi
mais eficiente que com MD5. Para deduplicação + armazenamento foi confirmado que o
tempo médio com SHA-1 e MD5 são diferentes, e a observação visual no gráfico fica
claro que o SHA-1 é mais eficiente nesse caso também. E por último, na operação de
reidratação, o sistema com MD5 foi mais eficiente que com SHA-1.
2 "http://usto.re"
75
6.5. SUMÁRIO DO CAPÍTULO
Para a segunda avaliação, foi analisada a taxa de compressão obtida para duas máquinas virtuais Linux, e como esperado, a taxa de compressão foi maior para chunks
menores.
E por último, a partir das análises em todas as operações, o SHA-1 por ter sido melhor
comprovadamente em 2 delas, e por ter a vantagem de não possuir colisões de hashes
comprovadas, vai ser definido como padrão para o Dedupeer File Storage.
76
7
Conclusão
Nesta pesquisa foi desenvolvido um algoritmo para deduplicação exata de dados,
interoperável, com processamento particionado em cargas de bytes para a memória
principal. O algoritmo foi encapsulado em um componente de software com interface
Thrift, que é uma biblioteca de serialização com linguagem neutra e suporte à diversas
linguagens de programação, para facilitar a integração com sistemas de armazenamento
existentes. O algoritmo foi desenvolvido com uma funcionalidade de otimização de
descoberta de redundância de dados através da carga extra de dados no processamento
particionado, o que aumenta a precisão da identificação de redundância mesmo com a
quebra do arquivo para ser processado.
Para a avaliação do algoritmo foi desenvolvido o Dedupeer File Storage, um sistema
de armazenamento de dados com as mesmas características dos principais sistemas de
armazenamento distribuídos, utilizando a quebra dos arquivos salvos em várias partes
menores, as quais são chamadas de chunks. O gerenciamento de replicação, tolerância à
falha, entre outros problemas comuns enfrentados por esses sistemas são delegados ao
Cassandra, que é a base de gerenciamento do sistema de armazenamento desenvolvido.
O Dedupeer File Storage possui uma interface gráfica com o usuário à qual possibilita
o gerenciamento dos arquivos armazenados, através de funcionalidades como backup,
deduplicação, reidratação, cálculo de economia, renderização de mapa de chunks e
referências do arquivo e painel de configurações básicas, como tamanho padrão de chunk
e quantidade de chunks carregados pra memória.
Com a utilização do algoritmo de deduplicação com processamento particionado, foi
possível fazer o deduplicação de arquivos maiores do que a memória RAM do computador
utilizado, o que não é possível para algoritmos com a carga do arquivo completa para a
memória. Nesta análise foram utilizados dois arquivos, um com 2,97GB e outro com
4,28GB, sendo que o computador onde a análise foi feita possui 3,24GB de RAM.
77
7.1. TRABALHOS FUTUROS
A eficiência do algoritmo também foi comprovada através da compressão alcançada
entre máquinas virtuais, chegando até a uma economia equivalente à 98,997% em relação
ao tamanho total do arquivo armazenado no sistema que foi utilizado na deduplicação, o
qual possuia aproximadamente 2,97GB e conseguiu uma economia no arquivo processado
de aproximadamente 2,93GB.
7.1
Trabalhos futuros
A fim de promover a utilização do algoritmo de deduplicação particionada ou o sistema de armazenamento de dados desenvolvidos, há algumas possibilidades de trabalhos
futuros, os quais estão listados abaixo:
• Criar um buffer do mapa dos chunks processados na deduplicação em disco, para
que não haja estouro de memória pelo fato do mapa de chunks ficar maior que
o espaço reservado para a memória heap do Java, o que possibilitará fazer a
deduplicação de arquivo de qualquer tamanho.
• Comparar os ganhos de desempenho trazidos pela deduplicação particionada em
relação à um algoritmo de deduplicação com carga completa do arquivo para a
memória.
• Fazer a análise do impacto de utilizar o Dedupeer File Storage em uma rede P2P
com vários nós, já que o Cassandra dá suporte nativo à isso e o Dedupeer File
Storage funciona com o Cassandra sendo o gerenciador dos dados armazenados.
• Modificar o Dedupeer File Storage para dar suporte à distribuição de tarefas de
deduplicação entre os nós da rede P2P criada a partir da sugestão acima, possibilitando a deduplicação de um mesmo arquivo em vários nós, o que aumentaria
a velocidade para conclusão da tarefa. Teoricamente o algoritmo já dá suporte à
isso, mas o sistema de armazenamento precisa fornecer a distribuição do arquivo
base para deduplicação entre os nós que farão o processamento, e também fazer a
coordenação dos nós da deduplicação distribuída.
• Utilizar o algoritmo como base para o desenvolvimento de um software de compressão de dados através de deduplicação, mantendo as informações necessárias para
a reidratação dos dados no mesmo arquivo, com funcionamento independente do
sistema de arquivos presente no computador onde o software será executando. Ele
teria um funcionamento parecido com o de softwares como o WinRar, 7zip, WinZip,
78
7.1. TRABALHOS FUTUROS
entre outros, mas com a possibilidade de obter maiores ganhos de economia entre
versões de um arquivo.
• Analisar ganho de desempenho e economia no Ustore, comparando o sistema com
a utilização do Dedupeer como componente de deduplicação e sem ele.
79
A
Apêndice
A.1
Arquivo de definição dos serviços Thrift
namespace java com.dedupeer.thrift
typedef i32 int
typedef i32 weakHash
typedef i64 position
typedef string strongHash
typedef string chunkID
struct ChunkIDs {
1: optional string fileID,
2: required string chunkID,
}
typedef map<weakHash,map<strongHash,ChunkIDs» hashesToCompare
struct Chunk {
1: required string fileID,
2: required string chunkNumber,
3: required string index,
4: required string length,
5: optional string strongHash,
6: optional string weakHash,
7: optional string pfile,
8: optional string pchunk,
9: optional string destination
10: optional binary content
}
85
A.1. ARQUIVO DE DEFINIÇÃO DOS SERVIÇOS THRIFT
service DeduplicationService { map<position,Chunk> deduplicate(1:hashesToCompare
chunksInfo, 2:string pathOfFile, 3:int chunkSizeInBytes, 4:int bytesToLoadByTime),
}
86
B
Apêndice
B.1
Resultados da avaliação dos arquivos do código fonte
do Kernel do Linux
Nesta seção estão todas as atribuições de vetores com o tempo em milisegundos das
14 execuções para cada tamanho de chunk e algoritmo de hashing utilizadas no Wolfram
Mathematica 9 para a geração dos gráficos. O nome das variáveis já são auto explicativos:
operação + algoritmo de hashing + tamanho do chunk.
storeMd5128 = {116890, 128522, 161175, 127015, 182025, 138390, 163266, 164578,
174934, 172479, 264644, 163050, 196002, 199964}
dedupMd5128 = {152626, 121048, 116854, 147668, 107600, 169585, 137500,
128414, 109421, 120321, 152501, 136377, 150033, 115625}
dedupStoreMd5128 = {302343, 266764, 205891, 235066, 181023, 390554, 284572,
225852, 240909, 146712, 257380, 257291, 283357, 219191}
rehydMd5128 = {43120, 39682, 24423, 27270, 32202, 38042, 31570, 29929, 32843,
33967, 74339, 78179, 54132, 63520}
storeMd564 = {224443, 229646, 263209, 287779, 201734, 190391, 146932, 213240,
170712, 243824, 362548, 307237, 209613, 245140}
dedupMd564 = {174321, 147211, 139559, 133334, 120627, 124088, 139953, 119768,
130386, 129988, 138782, 163945, 130047, 166978}
dedupStoreMd564 = {630062, 545441, 520411, 223001, 291992, 231066, 452831,
246117, 335005, 339177, 341458, 306297, 312459, 451774}
rehydMd564 = {44016, 44776, 53259, 42332, 39908, 42605, 51627, 45562, 42655,
49344, 43065, 43992, 39501, 54063}
storeMd532 = {287477, 294028, 200850, 377811, 259185, 230927, 247576, 207965,
87
B.1. RESULTADOS DA AVALIAÇÃO DOS ARQUIVOS DO CÓDIGO FONTE DO
KERNEL DO LINUX
249530, 208838, 455668, 270963, 320549, 277556}
dedupMd532 = {145037, 157748, 170891, 132478, 138431, 131754, 133539, 130283,
154380, 150167, 148359, 148353, 166233, 138308}
dedupStoreMd532 = {577638, 412407, 317166, 292932, 259089, 330367, 316198,
365495, 837278, 506792, 602081, 561788, 601541, 354776}
rehydMd532 = {51287, 46370, 46104, 49237, 44773, 47537, 58604, 58947, 57708,
64215, 66442, 55603, 60782, 59282}
storeMd516 = {562270, 454941, 424759, 502178, 381864, 412521, 407050, 405793,
473307, 386267, 593349, 421730, 375943, 376105}
dedupMd516 = {188752, 185564, 161651, 193435, 162934, 172242, 163898, 155829,
155889, 188695, 175961, 203188, 202666, 167698}
dedupStoreMd516 = {622743, 629450, 513485, 713067, 639438, 603385, 388159,
337782, 1436801, 831398, 565027, 1698535, 957346, 289319}
rehydMd516 = {86674, 82294, 81711, 84303, 98120, 85317, 85441, 85200, 115681,
121885, 92514, 101977, 105959, 112096}
storeMd58 = {964520, 706285, 701453, 776959, 652153, 626387, 729390, 649180,
647969, 740110, 810059, 638516, 664015, 685365}
dedupMd58 = {262806, 222173, 222521, 213340, 226187, 213091, 211391, 215724,
206816, 208526, 290567, 217865, 255022, 220123}
dedupStoreMd58 = {1233607, 1147788, 950798, 1352302, 992080, 1149349, 1455682,
1091442, 1296342, 1088684, 978422, 1409732, 1212028, 1633295}
rehydMd58 = {211929, 209033, 219621, 214522, 213657, 228344, 208617, 203970,
217254, 211841, 260067, 218043, 235251, 316691}
storeSha1128 = {97349, 109037, 178196, 131649, 222211, 164740, 156184, 175117,
201404, 241228, 186827, 199992, 211887, 171740}
storeSha1128 = {97349, 109037, 178196, 131649, 222211, 164740, 156184, 175117,
201404, 241228, 186827, 199992, 211887, 171740}
dedupSha1128 = {63519, 31808, 31076, 62923, 28399, 39641, 30170, 32386, 27387,
28872, 45208, 28240, 33598, 28513}
dedupStoreSha1128 = {106842, 40104, 38955, 71471, 37059, 48198, 38517, 40062,
35608, 36583, 53701, 36477, 41966, 36642}
rehydSha1128 = {80398, 66018, 74281, 73583, 77102, 79250, 71369, 74586, 61423,
54298, 70373, 54420, 63678, 59489}
storeSha164 = {227047, 246043, 220085, 246523, 258685, 343073, 273425, 163953,
180418, 168436, 241606, 197194, 149808, 340464}
88
B.1. RESULTADOS DA AVALIAÇÃO DOS ARQUIVOS DO CÓDIGO FONTE DO
KERNEL DO LINUX
dedupSha164 = {44627, 55439, 37672, 36791, 37862, 45950, 37520, 42662, 36343,
36836, 90213, 37043, 36457, 34334}
dedupStoreSha164 = {60352, 71177, 53407, 52170, 53417, 60901, 51731, 56645,
49782, 50206, 105105, 51850, 51185, 49028}
rehydSha164 = {113640, 121360, 115431, 116551, 120308, 121186, 118612, 119106,
119012, 126016, 120365, 121915, 115323, 122687}
storeSha132 = {342456, 307489, 444142, 271943, 241923, 278932, 234001, 291040,
247489, 419230, 310343, 235232, 248579, 230177}
dedupSha132 = {88725, 94374, 83564, 75430, 53590, 42292, 42023, 42247, 42377,
45404, 59797, 52593, 48748, 50663}
dedupStoreSha132 = {311124, 668717, 668684, 318272, 83442, 72593, 71620,
71011, 69193, 71844, 90368, 80840, 76438, 78293}
rehydSha132 = {284121, 283260, 275700, 281079, 280853, 277080, 279279, 271631,
280641, 288302, 224400, 210995, 216494, 227920}
storeSha116 = {562142, 463576, 444615, 530067, 454989, 442680, 441273, 492828,
448203, 426066, 415538, 294142, 544621, 352227}
dedupSha116 = {93354, 78566, 82060, 84914, 87426, 77438, 79562, 82759, 82814,
77072, 86109, 61880, 72285, 68897}
dedupStoreSha116 = {153686, 137637, 380842, 143149, 146810, 134846, 134432,
134202, 134325, 222198, 140885, 116085, 127409, 124290}
rehydSha116 = {555020, 546197, 551883, 577015, 560025, 561874, 569340, 583346,
586910, 439744, 546468, 553587, 573509, 561451}
storeSha18 = {821022, 698555, 790524, 714050, 699568, 718900, 687966, 724312,
936965, 1007309, 675155, 624304, 564328, 626949}
dedupSha18 = {125576, 117776, 118081, 121136, 122290, 114841, 114762, 114715,
125726, 129404, 122153, 104723, 110433, 116113}
dedupStoreSha18 = {256510, 244094, 248895, 664530, 239424, 265320, 231658,
235930, 237475, 416532, 229066, 212203, 217454, 223275}
rehydSha18 = {1124600, 1107152, 1122944, 1178347, 1130081, 1135656, 1129751,
1150545, 1189838, 1162052, 1145106, 1253311, 1251508, 1253582}
89
C
Apêndice
C.1
Gráficos dos tempos emparelhados por tamanho de
chunk para a operação de armazenamento
Figura C.1 Tempo emparelhado para a operação de armazenamento com chunks de 128KB
90
C.1. GRÁFICOS DOS TEMPOS EMPARELHADOS POR TAMANHO DE CHUNK
PARA A OPERAÇÃO DE ARMAZENAMENTO
Figura C.2 Tempo emparelhado para a operação de armazenamento com chunks de 64KB
Figura C.3 Tempo emparelhado para a operação de armazenamento com chunks de 32KB
91
C.1. GRÁFICOS DOS TEMPOS EMPARELHADOS POR TAMANHO DE CHUNK
PARA A OPERAÇÃO DE ARMAZENAMENTO
Figura C.4 Tempo emparelhado para a operação de armazenamento com chunks de 16KB
Figura C.5 Tempo emparelhado para a operação de armazenamento com chunks de 8KB
92
C.2. GRÁFICOS DOS TEMPOS EMPARELHADOS POR TAMANHO DE CHUNK
PARA A OPERAÇÃO DE DEDUPLICAÇÃO
C.2
Gráficos dos tempos emparelhados por tamanho de
chunk para a operação de deduplicação
Figura C.6 Tempo emparelhado para a operação de deduplicação com chunks de 128KB
Figura C.7 Tempo emparelhado para a operação de deduplicação com chunks de 64KB
93
C.2. GRÁFICOS DOS TEMPOS EMPARELHADOS POR TAMANHO DE CHUNK
PARA A OPERAÇÃO DE DEDUPLICAÇÃO
Figura C.8 Tempo emparelhado para a operação de deduplicação com chunks de 32KB
Figura C.9 Tempo emparelhado para a operação de deduplicação com chunks de 16KB
94
C.3. GRÁFICOS DOS TEMPOS EMPARELHADOS POR TAMANHO DE CHUNK
PARA A OPERAÇÃO DE DEDUPLICAÇÃO + ARMAZENAMENTO
Figura C.10 Tempo emparelhado para a operação de deduplicação com chunks de 8KB
C.3
Gráficos dos tempos emparelhados por tamanho de
chunk para a operação de deduplicação + armazenamento
Figura C.11 Tempo emparelhado para a operação de deduplicação + armazenamento com chunks
de 128KB
95
C.3. GRÁFICOS DOS TEMPOS EMPARELHADOS POR TAMANHO DE CHUNK
PARA A OPERAÇÃO DE DEDUPLICAÇÃO + ARMAZENAMENTO
Figura C.12 Tempo emparelhado para a operação de deduplicação + armazenamento com chunks
de 64KB
Figura C.13 Tempo emparelhado para a operação de deduplicação + armazenamento com chunks
de 32KB
96
C.3. GRÁFICOS DOS TEMPOS EMPARELHADOS POR TAMANHO DE CHUNK
PARA A OPERAÇÃO DE DEDUPLICAÇÃO + ARMAZENAMENTO
Figura C.14 Tempo emparelhado para a operação de deduplicação + armazenamento com chunks
de 16KB
Figura C.15 Tempo emparelhado para a operação de deduplicação + armazenamento com chunks
de 8KB
97
C.4. GRÁFICOS DOS TEMPOS EMPARELHADOS POR TAMANHO DE CHUNK
PARA A OPERAÇÃO DE REIDRATAÇÃO
C.4
Gráficos dos tempos emparelhados por tamanho de
chunk para a operação de reidratação
Figura C.16 Tempo emparelhado para a operação de reidratação com chunks de 128KB
Figura C.17 Tempo emparelhado para a operação de reidratação com chunks de 64KB
98
C.4. GRÁFICOS DOS TEMPOS EMPARELHADOS POR TAMANHO DE CHUNK
PARA A OPERAÇÃO DE REIDRATAÇÃO
Figura C.18 Tempo emparelhado para a operação de reidratação com chunks de 32KB
Figura C.19 Tempo emparelhado para a operação de reidratação com chunks de 16KB
99
C.4. GRÁFICOS DOS TEMPOS EMPARELHADOS POR TAMANHO DE CHUNK
PARA A OPERAÇÃO DE REIDRATAÇÃO
Figura C.20 Tempo emparelhado para a operação de reidratação com chunks de 8KB
100