Dedupeer: Deduplicação de Arquivos Através de um Algoritmo de Processamento Particionado

“Dedupeer: um Algoritmo para Deduplicação de ArquivosAtravé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

www.cin.ufpe.br/~posgraduacao

Universidade Federal de Pernambuco

Centro de InformáticaPós-graduação em Ciência da Computação

Paulo Fernando Almeida Soares

“Dedupeer: um Algoritmo para Deduplicação deArquivos 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 Univer-

sidade 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

Resumo

A deduplicação é uma técnica de compressão de dados sem perda que elimina dadosredundantes tanto intra-file como inter-file, diferente de ferramentas de compressão dedados como o gzip que só eliminam a redundância intra-file. A deduplicação reduz anecessidade 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 dearmazenamento podem ser reduzidos à uma única cópia, esses blocos desalocados peladeduplicaçã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 armazenamentocomerciais em meados de 2004. Hoje, os principais sistemas de armazenamento dedados usam deduplicação, mas os algoritmos implementados e as técnicas utilizadasnão são detalhadas publicamente. Existem alguns trabalhos acadêmicos focados naimplementação de algoritmos de deduplicação, mas eles são raros e não são voltados paraa sua utilização em sistemas de armazenamento existentes. O principal objetivo destetrabalho é criar um algoritmo para deduplicação de arquivos no cliente de forma remota,através de processamento particionado e utilizando comparação por fingerprints. Estealgoritmo foi incorporado em um componente de software com interface interoperávelpara facilitar a utilização em qualquer sistema de armazenamento de dados e beneficiá-loscom economia de armazenamento, e na transferência de dados no caso dos sistemas dearmazenamento distribuídos.

Além do componente de software, foi desenvolvido também um sistema de armazena-mento com gerenciamento de dados baseado no Apache Cassandra, o que o torna capazde ser distribuído, com o objetivo de validar o algoritmo de deduplicação. A integração docomponente de software com o sistema de armazenamento foi implementada e avaliadaneste trabalho.

Palavras-chave: Deduplicação, compressão de dados, economia de armazenamento,sistemas de armazenamento de dados

iii

Abstract

The deduplication is a technique of lossless data compress that eliminates redundantdata as intra-file as inter-file, different tools to data compression like gzip only eliminatesthe redundancy intra-file. The deduplication reduces storage needs through eliminatingredundant blocks. In the deduplication, all data blocks or files that are duplicates in astorage system are reduced to a solely copy, and the unallocated data are transformed inreference to the data content maintained in the system.

Deduplication techniques began to be studied in mid-2004. Today, the main storagesystems use deduplication, but the algorithms implemented and the techniques used arenot detailed. There are researches focused in the implementation of algorithms, but theyare rare and the main goal not is the integration with the existing systems. The mainaim of this research is to create an algorithm to deduplication of files on the source withremote data, through of the partitioned processing and using of fingerprint comparisons.This algorithm was integrated in a software component with interoperable interface tofacilite the using in any storage system and benefit them with storage economy,and in thedata transfer when the system was distributed.

Besides the software component was developed also a storage system with datamanagement made with the Apache Cassandra, which make it able to be distributedwith the goal to validate the deduplication algorithm. The integration of the softwarecomponent with the storage system was implemented and evaluated in this research.

Keywords: Deduplication, data compression, storage economy, storage systems

iv

Sumário

Lista de Figuras viii

Lista de Tabelas xi

1 Introdução 11.1 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Definição do problema . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Resultados esperados . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.4 Escopo negativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.5 Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.6 Sumário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Trabalhos relacionados 72.1 Sistemas de armazenamento de dados com foco em deduplicação . . . . 7

2.1.1 Distributed Duplicate Detection in Post-Process Data De-duplication 82.1.2 Design of an exact data deduplication cluster . . . . . . . . . . 82.1.3 Σ-Dedup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.1.4 Dropbox . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.1.5 Conclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2.2 Deduplicação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.2.1 Localização . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

Cliente (source) . . . . . . . . . . . . . . . . . . . . . . . . . . 13Servidor (target) . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2.2 Momento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.2.3 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.2.4 Benefícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.3 Sumário do capítulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 O Dedupeer File Storage 183.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.1.1 Escopo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.2 O sistema de armazenamento distribuído . . . . . . . . . . . . . . . . . 19

3.2.1 Modelo de dados . . . . . . . . . . . . . . . . . . . . . . . . . 193.3 Visão de componentes e conectores . . . . . . . . . . . . . . . . . . . 25

v

O componente Dedupeer File Storage . . . . . . . . . . . . . . 25O componente Dedupeer . . . . . . . . . . . . . . . . . . . . . 26

3.4 Decisões de projeto e considerações . . . . . . . . . . . . . . . . . . . 273.4.1 Tamanho do chunk . . . . . . . . . . . . . . . . . . . . . . . . 273.4.2 Cassandra para gerenciamento do armazenamento . . . . . . . 27

Tolerância à falhas . . . . . . . . . . . . . . . . . . . . . . . . 29Recuperação de falhas . . . . . . . . . . . . . . . . . . . . . . 29Consistência . . . . . . . . . . . . . . . . . . . . . . . . . . . 30Disponibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . 30Empacotamento de requisições . . . . . . . . . . . . . . . . . . 31

3.4.3 Alternativa para o gerenciamento de armazenamento . . . . . . 31Facilidade de instalação e manutenção . . . . . . . . . . . . . . 31Clusters pequenos . . . . . . . . . . . . . . . . . . . . . . . . 31

3.4.4 Escalabilidade . . . . . . . . . . . . . . . . . . . . . . . . . . 32O que é escalabilidade? . . . . . . . . . . . . . . . . . . . . . . 32Escalabilidade com o Cassandra . . . . . . . . . . . . . . . . . 33


4 Componente para deduplicação em sistemas de armazenamento de dados 344.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.2 Interoperabilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.2.1 Interoperabilidade de comunicação através do Thrift . . . . . . 354.2.2 Comparação com o Protocols Buffer . . . . . . . . . . . . . . . 37

Protocols Buffer . . . . . . . . . . . . . . . . . . . . . . . . . 37Comparação de desempenho . . . . . . . . . . . . . . . . . . . 38

4.2.3 Comparação por hash (fingerprints) . . . . . . . . . . . . . . . 38Vantagem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40


5 Os algoritmos 425.1 Fundamentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5.1.1 O algoritmo Rsync . . . . . . . . . . . . . . . . . . . . . . . . 42Rolling checksum . . . . . . . . . . . . . . . . . . . . . . . . 43

5.1.2 Fingerprinting . . . . . . . . . . . . . . . . . . . . . . . . . . 445.2 Detalhando os algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . 45

vi

5.2.1 Algoritmo para deduplicação com carga completa do arquivo namemória . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.2.2 Algoritmo com deduplicação particionada . . . . . . . . . . . . 505.3 Sumário do capítulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

6 Análise de desempenho e compressão 576.1 Datasets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576.2 Análise de desempenho utilizando o código fonte do Kernel do Linux . 59

Operação de armazenamento . . . . . . . . . . . . . . . . . . . 59Operação de deduplicação . . . . . . . . . . . . . . . . . . . . 62Operação de deduplicação + armazenamento . . . . . . . . . . 64Operação de reidratação . . . . . . . . . . . . . . . . . . . . . 66

6.2.1 Mapa de chunks deduplicados . . . . . . . . . . . . . . . . . . 686.3 Análise de economia utilizando máquinas virtuais . . . . . . . . . . . . 696.4 O Ustore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 716.5 Sumário do capítulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

7 Conclusão 737.1 Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

Referências Bibliográficas 75

A Apêndice 80A.1 Arquivo de definição dos serviços Thrift . . . . . . . . . . . . . . . . . 80A.2 Resultados da avaliação dos arquivos do código fonte do Kernel do Linux 81A.3 Gráficos dos tempos emparelhados por tamanho de chunk para a operação

de armazenamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84A.4 Gráficos dos tempos emparelhados por tamanho de chunk para a operação

de deduplicação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86A.5 Gráficos dos tempos emparelhados por tamanho de chunk para a operação

de deduplicação + armazenamento . . . . . . . . . . . . . . . . . . . . 89A.6 Gráficos dos tempos emparelhados por tamanho de chunk para a operação

de reidratação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

Appendices 80

vii

Lista de Figuras

1.1 Aumento da demanda e redução do custo de hardware de armazenamento[20] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

2.1 Armazenamento dos super-chunks nos nós [43]. . . . . . . . . . . . . . 102.2 Exemplo da economia de espaço oferecida em um sistema de armazena-

mento com 20% de alteração nos dados. . . . . . . . . . . . . . . . . . 16

3.1 Diagrama de componentes de alto nível da biblioteca do Dedupeer . . . 193.2 Modelo de dados do sistema distribuído desenvolvido com o Cassandra 243.3 Visão de componentes e conectores do DeFS integrado com a biblioteca

do Dedupeer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

4.1 Desempenho na serialização dos dados [2] . . . . . . . . . . . . . . . . 384.2 Desempenho na desserialização dos dados [2] . . . . . . . . . . . . . . 39

5.1 Funcionamento do algoritmo 1. . . . . . . . . . . . . . . . . . . . . . . 475.2 Funcionamento do algoritmo 2 . . . . . . . . . . . . . . . . . . . . . . 515.3 Vantagem da utilização da carga extra de dados . . . . . . . . . . . . . 55

6.1 Tempo em milissegundos para as execuções da operação de armazena-mento utilizando MD5 . . . . . . . . . . . . . . . . . . . . . . . . . . 60

6.2 Tempo em milissegundos para as execuções da operação de armazena-mento utilizando SHA-1 . . . . . . . . . . . . . . . . . . . . . . . . . 60

6.3 Tempo em milissegundos para as execuções da operação de armazena-mento, separadas por tamanho de chunk . . . . . . . . . . . . . . . . . 61

6.4 Tempo em milissegundos das execuções da operação de deduplicação,separadas por tamanho de chunk, utilizando SHA-1 . . . . . . . . . . . 63

6.5 Tempo em milissegundos das execuções da operação de deduplicação,separadas por tamanho de chunk, utilizando MD5 . . . . . . . . . . . . 63

6.6 Tempo em milissegundos das execuções da operação de deduplicação +armazenamento, separadas por tamanho de chunk, utilizando SHA-1 . . 65

6.7 Tempo em milissegundos das execuções da operação de deduplicação +armazenamento, separadas por tamanho de chunk, utilizando MD5 . . . 66

6.8 Tempo em milissegundos das execuções da operação de reidratação,separadas por tamanho de chunk, utilizando SHA-1 . . . . . . . . . . . 67

viii

6.9 Tempo em milissegundos das execuções da operação de reidratação,separadas por tamanho de chunk, utilizando MD5 . . . . . . . . . . . . 67

6.10 Mapa de chunks deduplicados da versão 3.10-rc7 do código-fonte doKernel do Linux processado com os chunks da versão 3.9.8, para chunks

com tamanho 128, 64, 32, 16 e 8KB . . . . . . . . . . . . . . . . . . . 686.11 Tamanho em megabytes ocupado pelo arquivo no sistema, com a porcen-

tagem de economia alcançada . . . . . . . . . . . . . . . . . . . . . . 706.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 . . . . . . . . . . . . 70

A.1 Tempo emparelhado para a operação de armazenamento com chunks de128KB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84




A.5 Tempo emparelhado para a operação de armazenamento com chunks de8KB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

A.6 Tempo emparelhado para a operação de deduplicação com chunks de128KB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

A.7 Tempo emparelhado para a operação de deduplicação com chunks de 64KB 87A.8 Tempo emparelhado para a operação de deduplicação com chunks de 32KB 87A.9 Tempo emparelhado para a operação de deduplicação com chunks de 16KB 88A.10 Tempo emparelhado para a operação de deduplicação com chunks de 8KB 88A.11 Tempo emparelhado para a operação de deduplicação + armazenamento

com chunks de 128KB . . . . . . . . . . . . . . . . . . . . . . . . . . 89A.12 Tempo emparelhado para a operação de deduplicação + armazenamento

com chunks de 64KB . . . . . . . . . . . . . . . . . . . . . . . . . . . 89A.13 Tempo emparelhado para a operação de deduplicação + armazenamento

com chunks de 32KB . . . . . . . . . . . . . . . . . . . . . . . . . . . 90A.14 Tempo emparelhado para a operação de deduplicação + armazenamento

com chunks de 16KB . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

ix

A.15 Tempo emparelhado para a operação de deduplicação + armazenamentocom chunks de 8KB . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

A.16 Tempo emparelhado para a operação de reidratação com chunks de 128KB 91A.17 Tempo emparelhado para a operação de reidratação com chunks de 64KB 92A.18 Tempo emparelhado para a operação de reidratação com chunks de 32KB 92A.19 Tempo emparelhado para a operação de reidratação com chunks de 16KB 93A.20 Tempo emparelhado para a operação de reidratação com chunks de 8KB 93

x

Lista de Tabelas

3.1 Força do consistência baseada nos níveis das operações [8] . . . . . . . 30

6.1 p-values para os dados capturados na operação de armazenamento . . . 626.2 Quantidade de chunks criados . . . . . . . . . . . . . . . . . . . . . . 69

xi

1Introdução

Com o aumento da capacidade das unidades de armazenamento, aumentou também ademanda por sua utilização. Em 2000, a estimativa da indústria era de um aumento anualentre 50% a 100% dessa demanda [24], estimativa essa que se consolidou. Nos últimosanos esse aumento atingiu um valor anual de mais de 50% [20].

A Figura 1.1 mostra dois gráficos com informações sobre demanda e preço doarmazenamento entre os anos de 2006 e 2011. Um deles demonstra o forte crescimentoda demanda por armazenamento nas empresas, e o segundo, exibe a queda de 20% aoano no preço por Gigabytes.

Figura 1.1 Aumento da demanda e redução do custo de hardware de armazenamento [20]

1

A indústria de TI passou a apostar em sistemas de armazenamento de dados distribuídonos ú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 [44].

Com esse aumento da demanda por armazenamento, a utilização de técnicas decompressão de dados se torna um fator chave para redução dos custos. A compressãode dados é uma técnica que codifica informações, usando uma quantidade menor dedados que a original, para economizar espaço de armazenamento. As técnicas maisconhecidas de compressão de dados funcionam apenas com a compressão intra-file, ouseja, utilizando no processamento apenas os bytes do arquivo a ser comprimido, comoexemplo, pode ser citado o formato de arquivo zip [31], que é um tipo de compressãosem perda. E também existe a compressão intra-file com perda de dados, que é o casodos famosos formatos de arquivos jpg e mp3, o qual reduz a qualidade da foto e imagem,respectivamente, para obter uma redução no espaço necessário para armazenar o arquivo[33].

A deduplicação é um técnica de compressão sem perda que elimina dados redundantestanto intra-file quanto inter-file, o que possibilita utilizar dados remotos para ajudar nacompressão dos dados. Com a popularização dos sistemas de armazenamento distribuídoem 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 oespaço utilizado no sistema. A deduplicação de dados é um técnica de compressão quearmazena uma única cópia de dados redundantes, eliminando as outras do sistema dearmazenamento. Ela pode ser feita em nível de arquivo completo ou de chunks, os quaissão blocos de dados pertencentes ao arquivo.

Muitos sistemas de backup atuais escolhem fazer o armazenamento dos arquivos emfitas magnéticas por serem mais baratas que os discos rígidos. A fita magnética tema desvantagem de ter o acesso apenas sequencial dos dados, enquanto que no disco oacesso pode ser randômico. Com a utilização das fitas, a deduplicação dos dados se tornaeficientemente inviável pela falta de capacidade em acesso randômico. Por esse fator, adeduplicação está tornando um diferencial na escolha dos discos rígidos como dispositivode 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

1http://aws.amazon.com/pt/s3/2http://www.google.com/enterprise/cloud/storage/3http://www.windowsazure.com4http://www.salesforce.com

2

1.1. MOTIVAÇÃO

consequência o espaço de armazenamento é economizado [19].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 poderiafornecer em um sistema sem deduplicação, já que a deduplicação diminui a quantidade debytes armazenados por aqruivos no sistema, principalmente quando o mesmo arquivo emdiferentes versões é salvo ou quando o mesmo arquivo é enviado para o sistema, mesmoque por usuários distintos.

Uma forma de aumentar os blocos de dados redundantes em sistemas de armaze-namento 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 entreos arquivos, tarefa essa que demanda muito processamento e utilização de E/S (entradae saída). Esse processo torna-se mais viável com a distribuição do processamento dosdados para a redefinição dos novos pontos de cortes dos chunks e utilização de algoritmosde 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 seremexecutados em clusters [5] [11] [19] [45] ou em nós simples, alguns deles usam frameworkpara processamento distribuído de dados [21], como Hadoop por exemplo, mas há umafalta de pesquisa envolvendo sistemas de deduplicação para ambientes de armazenamentode dados construídos com arquitetura peer-to-peer sobre computadores pessoais paraarmazenar esses dados.

Baseado nisso, esse trabalho propõe o desenvolvimento de um componente de soft-ware para deduplicação de dados que pode ser integrado com qualquer sistema de arma-zenamento de dados que tenha sido implementado em uma das linguagens suportadaspelo Thrift. O componente será integrado a um sistema comercial de armazenamento dedados 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 sistemade armazenamento ser considerado dentro dos padrões da green storage, o qualserá melhor detalhado no Capítulo 4. Com a redução do espaço necessário para

3

1.2. DEFINIÇÃO DO PROBLEMA

armazenar os arquivos, um sistema de armazenamento pode ser vendido com maisespaç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çãoreduz a quantidade deles.

1.2 Definição do problema

Algoritmos detalhados para deduplicação utilizando processamento de forma particio-nada são escassos. Existe também uma falta de componentes de softwares interoperáveispara deduplicação que possam ser integrados aos sistemas de armazenamento de dadosexistentes.

1.3 Resultados esperados

Esta pesquisa tem como principal objetivo desenvolver um algoritmo para dedupli-cação de dados, que faça processamento particionado e que seja interoperável e de fácilintegração com os sistemas existentes. Este algoritmo deverá ser disponibilizado comoum componente de software, com uma interface de comunicação multilinguagem, paraexecutar a deduplicação exata dos dados em sistemas de armazenamento. Ele deverá serintegrado ao sistema de armazenamento que será desenvolvido como parte da pesquisa ecom um sistema distribuído de armazenamento de dados comercial.

Com o algoritmo a ser desenvolvido nesta pesquisa deve resolver os três benefícioscitados na Motivação proporcionados pela deduplicação e com o mínimo de alteraçãono sistema de armazenamento para integrá-lo, isso porque o algoritmo será feito tendo ainteroperabilidade e modificabilidade mínima para integração como alguns dos principaisrequisitos.

O algoritmo deve ser disponibilizado através de uma biblioteca com uma interfaceThrift, que vai receber os valores de hash dos chunks e o arquivo a ser deduplicado, eretornará 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

4

1.4. ESCOPO NEGATIVO

arquivo ou entre arquivos distintos. O algoritmo será capaz de identificar as redundânciasse 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ão fora do escopo da pesquisa,pelo fato da detecção de redundância diminuir com o aumento do tamanho do chunk e esteser o tamanho padrão do Ustore, o sistema comercial de backup de dados onde o Dedupeerserá implantado. Também foi definido como limite mínimo de tamanho de chunk 8KB.Apesar de conseguir uma maior ganho de redução de espaço com chunks menores, otempo para processamento e a quantidade de chunks gerados começa a degradar muito odesempenho do sistema.

O Dedupeer File Storage será desenvolvido utilizando o Cassandra5, que é um bancode dados distribuído que utiliza arquitetura P2P, mas está fora de escopo o teste do sistemade forma distribuída. Todos os testes serão feitos localmente, já que serão suficientes paraavaliar 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 é adeduplicação onde os dados são processados no momento em que chegam no alvo e antesde serem armazenados, estão fora do escopo do trabalho.

Por serem os algoritmo de hashing mais comuns em processamentos de deduplicaçãode dados, os testes só serão feitos com MD5 e SHA-1.

1.5 Contribuições

As principais contribuições desta pesquisa serão:

• O algoritmo para deduplicação de dados com processamento particionado encapsu-lado em um componente de software interoperável. Essa forma de processamentotorna possível fazer a deduplicação de arquivos muito maiores do que a memóriaprincipal, 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, ad-ministrável através de interface gráfica e com gerenciamento de armazenamento

5http://cassandra.apache.org/

5

1.6. SUMÁRIO

delegado para um banco de dados não-relacional construído em uma arquiteturapeer-to-peer com topologia de anel.

• A otimização da descoberta de redundância de dados através da carga extra dedados no processamento particionado, possibilitando a diminuição da perda deidentificação por causa da quebra do arquivo.

1.6 Sumário

Neste capítulo foi apresentada uma introdução sobre o crescimento da demanda porsistemas de armazenamento de dados e a importância da deduplicação para a economiade espaço nos tempos onde os sistemas de cloud storage estão sendo cada vez maisutilizados.

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ãoos 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 sistemade armazenamento de arquivos desenvolvido neste trabalho, e serão discutidas algumasdecisões de projeto relacionadas à construção desse sistema.

No Capítulo 4 será detalhado o funcionamento do componente de software quedisponibilizará o algoritmo de deduplicação como um serviço. Será discutida a intero-perabilidade do componente e quais poderiam ser as alternativas à biblioteca que foiescolhida, também será tratado sobre a utilização da comparação por hash e quais são assuas vantagens e desvantagens.

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 é aprincipal contribuição deste trabalho. Serão apresentados os fundamentos do algoritmodesenvolvido para identificação de redundância entre arquivos remotos, os quais serviramde base para os algoritmos desenvolvidos. Serão detalhados também os pseudocódigosde alto nível dos dois algoritmos criados.

O Capítulo 6 apresentará os testes de desempenho e compressão executados parademonstrar a eficiência do algoritmo de deduplicação e o sistema de armazenamento dedados desenvolvidos.

E o Capítulo 7 apresentará as conclusões sobre o trabalho e algumas propsotas paratrabalhos futuros.

6

2Trabalhos relacionados

Neste capítulo, os conceitos e técnicas fundamentais sobre os assuntos relevantespara o entendimento dessa pesquisa serão discutidos. Serão discutidos os principaistrabalhos 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 odesenvolvimento do projeto Dedupeer, o qual é dividido em dois, o no Dedupeer FileStorage e componente de software que implementa o algoritmo deduplicação chamadode Dedupeer.

Primeiramente vai ser feito um estudo com alguns dos sistemas de armazenamentode dados que utilizam deduplicação para identificar as técnicas e os conceitos, e comisso, analisar quais as que melhor servirão de base para o desenvolvimento do DedupeerFile Storage, que será o sistema de armazenamento de arquivos a ser desenvolvido comfinalidade de validar a integração do componente para deduplicação de dados. A análisefeita nesses sistemas servirá para que uma melhor estratégia para o processamento dadeduplicação seja implementada no Dedupeer, com base nos princípios desejados para aexecução do mesmo.

É pequeno o número de sistemas de armazenamento que declaram a utilização dededuplicação, e ainda menor os que detalham esse processo. Será apresentado o conceitode deduplicação de dados e quais são os seus tipos.

2.1 Sistemas de armazenamento de dados com foco emdeduplicação

Nesta seção serão descritos alguns dos sistemas pesquisados que têm como objetivoarmazenamento de dados e que têm como um dos focos principais a deduplicação. Os

7

2.1. SISTEMAS DE ARMAZENAMENTO DE DADOS COM FOCO EMDEDUPLICAÇÃO

trabalhos acadêmicos serão apresentados por ordem de ano de publicação.

2.1.1 Distributed Duplicate Detection in Post-Process Data De-duplication

Devido ao desafio cada vez mais comum em armazenar e gerenciar o crescentevolume de dados gerados nos dias atuais, conhecido como Big Data[18], é importantepensar em arquiteturas escaláveis para que os sistemas consigam dar suporte a essagrande quantidade de dados. Uma proposta de um sistema escalável para dar suporte àdeduplicação para grande volume de dados foi descrita em [21]. Diferente das pesquisasmais comuns para escalabilidade de sistemas de deduplicação, que geralmente têm ofoco na otimização dos algoritmos de deduplicação e em formas de deduplicação demais alto nível, como arquivos e objetos. [21] tem o trabalho direcionado para o projetoarquitetural do sistema e usa deduplicação em nível de bloco, que apesar de ter vantagensde velocidade, em contrapartida tem problemas no gerenciamento da enorme quantidadede blocos a serem gerenciados.

O projeto descrito em [21] foi projetado para funcionar de forma otimizada emambientes de cluster, o qual é um conjunto de computadores interligados através de umsistema distribuído com uma finalidade em comum. Suas rotina de deduplicação offline

de dados são executadas nesses cluster externos, isso é feito para que o processamento dadeduplicação não dispute os recursos com as outras rotinas do sistema. Para a execuçãodas tarefas foi usado o Apache Hadoop, que é um framework para computação distribuídabaseado em Map/Reduce, o qual ajudou a aumentar a capacidade de escalabilidade doprojeto.

Todo o processo para deduplicação dos dados é feito após o armazenamento nosistema, o que têm como desvantagem a necessidade do dado ser todo transferido para odestino, 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 Design of an exact data deduplication cluster

Em [19], é explicado sobre o funcionamento de um sistema que executa em cluster eutiliza um tipo de deduplicação que eles chamam de "exact deduplication", que recebeesse nome pelo fato do sistema conseguir detectar todos os chunks duplicados. Ossistemas com exact deduplication geralmente possuem chunks com tamanho entre 4KBe 16 KB. Sistemas que utilizam chunks grandes perdem muitas vezes a detecção daredundância, já a utilização de chunks muito pequenos, apesar de aumentar a chance de

8


deduplicação, torna o sistema menos eficiente por causa da alta sobrecarga ocasionadapela alta quantidade deles.

O HYDRAstor, descrito em [11], 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 oschunks na rede através de uma DHT. A escolha da granularidade alta dos chunks é paraaumentar o desempenho da deduplicação através da redução do envio de metadados.

O sistema em [19] foi projetado para trafegar a menor quantidade de dados possívelna deduplicação para aumentar a escalabilidade do mesmo. Basicamente o que é trocadoentre as máquinas do cluster são fingerprints. O sistema descrito foi baseado no dedupv1[26], o qual faz deduplicação em discos de estado sólido (SSDs) para evitar gargalos deleitura e escrita de dados.

Ele é dividido nos seguintes componentes: deduplication nodes, shared storage,interconnect between deduplication nodes, clients and distributed coordination. Osdeduplication nodes são responsáveis por grande parte das funções mais importantes paraa deduplicação e gerenciamento dos dados no sistema, neles são feitas as quebras dosdados em chunks e em seguida o cálculo do fingerprint de cada um deles. Eles tambémretornam os pedidos de chunks para outros nós e são responsáveis pela escrita deles nocontainer de armazenamento.

Cada deduplication node tem acesso às várias partições em que os discos são divi-didos pela rede através de storage area network (SAN) [39], as quais são redes de altavelocidade para acesso à dados. Cada partição só é acessada por um único nó, casoesse 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. Adistributed coordination é delegada para o Zookeeper 1, um software de código abertoque integra o projeto Apache 2 e o qual é o responsável pela escolha dos nós mestrese 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 egerenciada por um nó mestre, no caso de uma falha ocorrer nesse mestre, o Zookeeperelegerá outro nó para tomar o lugar do que falhou.

2.1.3 Σ-Dedup

O Σ-Dedup, que é descrito em [14], é um middleware de deduplicação de dados paradata centers e cloud storages. O Σ-Dedup foi criado para otimizar a deduplicação de

1http://zookeeper.apache.org/2http://apache.org

9


dados em clusters.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á enviadopara 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 aodisco. 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 dadeduplicação. Com o handprint, os nós efetuam um cálculo para determinar a semelhançaentre ele e os demais que estão armazenados no nó. Quando for encontrado o nó quepossui um super-chunk mais semelhante ao que vai ser enviado, todos os fingerprints doschunks pertencentes ao super-chunk serão enviados para o nó selecionado. Com essesfingerprints o nó verificará quais deles já estão armazenados e quais são novos. Depoisdessa identificação, o nó pede ao cliente que está fazendo o backup apenas os chunks quenão foram encontrados.

Na Figura 2.1 os super-chunks do arquivo são identificados pelas letras. Eles sãoenviados para nós diferentes, já que a escolha do nó onde cada um deles será enviado nomomento 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 duplica-dos se eles estiverem armazenados em diferentes nós.

Figura 2.1 Armazenamento dos super-chunks nos nós [43].

A arquitetura do Σ-Dedup possui 3 componentes principais: o Backup Client, oDeduplication 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

10


particionamento do arquivo e agrupamento dos chunks em super-chunks. O cálculo dosfingerprints é 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 dadosserão enviados.

Por ser um sistema de deduplicação inline, o qual será descrito na seção 2.2.2, osdados são avaliados antes do envio para os nós e só são transferidos os chunks que aindanão foram armazenados no sistema. Com isso, é economizada a banda de transferênciada rede.

O Deduplication Server Cluster também possui três módulos: Similarity Index Loo-

kup, 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 buscapor chunks idênticos, e o último é o responsável pelo armazenamento de forma paralelados chunks únicos nos containers.

Um outro trabalho similar ao Σ-Dedup, onde os dados são enviados para determinadosnós baseados na similaridade, é o Extreme Binning [5].

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 armaze-namento de dados em cloud [4] utiliza deduplicação de dados entre arquivos de usuáriosdistintos [37]. 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 dedu-plicação no Forum oficial da empresa, respondendo à uma pergunta de um usuário quequestionava o porquê de um arquivo de 750MB ser enviado tão rápido. Esse tópico nãoestá mais hospedado no forum, mas a resposta do CTO para a pergunta "Woah! How didthat 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

3"http://dropbox.com"

11

2.2. DEDUPLICAÇÃO

the pieces of the file that changed. This works across all data on Dropbox, not

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

Todos os sistemas de armazenamento estudados utilizam armazenamento de dadosbaseado em chunks ou blocos de dados. Pelo fato de todos eles serem sistemas distribuídospara armazenamento de dados, precisam se preocupar com os problemas decorrentesdesse tipo de sistema descritos no trabalho sobre o Dynamo [9], como: robustez eescalabilidade 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 dotrabalho, para a resolução desses problemas foi adotado para o Dedupeer File Storageo banco de dados Cassandra, que funciona em uma rede P2P e já trata todos eles. Comessa 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 dededuplicação detalhados publicamente, e os trabalhos acadêmicos não possuem seusalgoritmos ou sistemas de deduplicação facilmente acessíveis para utilização em umsistema de armazenamento. Esses foram os principais fatos que despertaram o interesseem desenvolver um algoritmo, com um processo diferente dos descritos, de código-aberto e interoperável entre linguagens para ser facilmente integrado aos sistemas dearmazenamento existente.

2.2 Deduplicação

A deduplicação de dados é um técnica de compressão sem perda que elimina dadosredundantes tanto intra-file quanto inter-file, diferente de ferramentas de compressão dedados como o gzip que só eliminam a redundância intra-file. A deduplicação reduz aquantidade de espaço necessário para armazenamento de dados através da eliminaçãode blocos e/ou arquivos redundantes. Na deduplicação, todos os blocos de dados ouarquivos que estão duplicados em um sistema de armazenamento são reduzidos à uma

12

2.2. DEDUPLICAÇÃO

única cópia, e os dados que foram desalocados são convertidos para uma referência aoconteú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 umarquivo 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 podeser classificada de dois modos: sem perdas (lossless), quando Y = X; e com perdas (lossy),permite Y 6= X [33].

2.2.1 Localização

A deduplicação distribuída pode ser feita tanto na entidade que envia os dados quantona que os recebe. Para facilitar, será utilizado o padrão cliente/servidor para explicaras formas de deduplicação. A entidade que requisita o armazenamento do dado seráreferenciada como Cliente; a entidade de destino dos dados será referenciada comoServidor.

Cliente (source)

[25] descreve a deduplicação baseada no cliente como sendo a deduplicação feitaantes do cliente enviar seus dados para o servidor. O cliente faz o cálculo e obtem o valordo hash de um chunk, chamado de fingerprint, em seguida ele os envia para o servidorde metadados, que faz a comparação com os fingertprints que estão armazenados parapoder identificar prováveis dados redundantes no sistema. Ao receber as informações, ocliente executa uma busca de conjuntos de bytes redundantes e remove esses dados antesde enviar o arquivo através da rede.

Esse tipo de deduplicação tem como vantagem a redução da quantidade de dados tra-fegados 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 dedetecção de dados redundantes.

Um ponto crítico desta técnica é a capacidade que o cliente tem de identificar blocosde arquivos armazenados no sistema e que são idênticos aos seus. O cliente precisasaber os bytes dos blocos dos arquivos cujo fingerprint é igual ao do seu para fazer acomparação e verificar se os dados são realmente idênticos, já que mais de um bloco demesmo tamanho pode ter um fingerprint igual mesmo tendo conteúdos diferentes. Apesar

13

2.2. DEDUPLICAÇÃO

da probabilidade disso ocorrer ser quase zero, é preciso garantir a integridade dos dadosarmazenados 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 querecebe os dados para armazenamento. Nela estão os appliances para armazenamento, sto-

rage arrays, peers de recebimento de dados em sistemas de armazenamento construídoscom arquitetura peer-to-peer, entre outros.

A deduplicação feita no servidor pode acontecer em dois momentos: inline e post-

processing. Eles serão descritos no próximo tópico.Uma desvantagem dessa abordagem é a centralização do processamento para iden-

tificação de dados redundantes no servidor, o que pode ocasionar a sobrecarregar domesmo.

2.2.2 Momento

A deduplicação pode ser de dois momentos: Inline deduplication ou Post-process

deduplication [13].

• Inline deduplication: os dados são examinados no momento em que chegam, antesda escrita no sistema de armazenamento. Esse processamento antes da escrita podetornar o servidor um gargalo.

• Post-process deduplication: a deduplicação é feita depois que os dados são arma-zenados, em intervalos de tempo regulares ou quando um certo limite definido éalcançado. Esse tipo de deduplicação é a melhor para ser utilizada em sistemas ondea velocidade de recebimento de dados é um fator crítico, já que o processamentopode deixar pra ser feito quando o servidor estiver ocioso.

2.2.3 Algoritmo

Os algortimos para fazer a deduplicação são categorizados em três tipos, segundo[25]: Whole File Hashing, Sub File Hashing e Delta Encoding.

• Whole File Hashing: é aplicada alguma função de hashing como o SHA1 [28] ou oMD5[32] no arquivo todo, esse valor é comparado com a base de armazenamentode arquivos armazenados no sistema, caso algum outro arquivo possua o hash com

14

2.2. DEDUPLICAÇÃO

o mesmo valor, é feita uma comparação byte a byte para ter certeza que os arquivossão idênticos, se forem, um dos arquivos é removido do sistema e o usuário ao qualo arquivo apagado pertencia terá um referência para o arquivo que é idêntico aoseu.

• Sub File Hashing: nessa categoria, o arquivo é dividido em pedaços que podemser de tamanhos iguais, chamado de Fixed Block Hashing (FBH), ou variáveis,chamado de Variable Block Hashing (VBH). No algoritmo FBH, o arquivo é tododividido 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[30], a ideia de computar o fingerprint de cada blocos para apenas transferir os quetê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 possuempartes comuns aos arquivos do outro lado, mas esta técnica tem um ponto queprecisa ser tratado. Quando qualquer dado é inserido ou removido de um arquivo,todos os fingerprints dos blocos subsequentes serão modificados se o algoritmoutiliza blocos de tamanho fixo. O Rabin Fingerprinting utiliza uma janela deslizante(rolling checksum e utiliza uma técnica para subdividir os blocos que tenham maiorprobabilidade de serem iguais a outros.

• Delta Encoding/Compression (DE): com o Delta Encoding é gerado um arquivoconhecido como patch que é um arquivo que tem informações das diferençasentre dois arquivos. Um algoritmo é usado para identificar quais partes devem sercopiadas e substituidas em um arquivo e quais partes devem ser inseridas para queseja possível remontar o arquivo apenas com as informações das diferenças.

2.2.4 Benefícios

Um exemplo do benefício que pode-se obter com a deduplicação foi apresentado pelaIBM. A IBM representou ganho de economia com um sistema de deduplicação baseadoem alterações de 20% do conteúdo dos arquivos através da Figura 2.2 [17]. A Figuramostra um backup inicial de 7TB de dados, e em uma semana o backup dos dados chegoua 79TB de dados. Em um sistema de armazenamento sem a deduplicação, todos os 49TBde dados seriam ocupados, mesmo se a alteração nos dados for de 20%, mas se essesistema usa deduplicação, é possível armazenar todo o conteúdo no sistema utilizandoapenas 8,45TB físico no disco. Ainda no exemplo, em 30 dias seria necessário 210TB dedisco para armazenamento em um sistema sem deduplicação, e de apenas 26,2TB para

15

2.3. SUMÁRIO DO CAPÍTULO

armazenar os mesmos dados em um sistema com deduplicação. É grande o ganho deeconomia que pode ser atingido com a utilização de deduplicação.

Figura 2.2 Exemplo da economia de espaço oferecida em um sistema de armazenamento com20% de alteração nos dados.

2.3 Sumário do capítulo

Neste capítulo, foi feita a descrição de alguns dos sistemas de armazenamento dedados, que utilizam deduplicação e fornecem detalhes sobre como ela é feita. Alguns dosproblemas 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 usadocomo base para o gerenciamento dos dados do Dedupeer File Storage, fazendo com queo foco principal do trabalho, que é o algoritmo de deduplicação, tenha um maior tempopara ser dedicado na pesquisa.

A utilização de chunks para o processo de deduplicação, apesar de ser óbvio, foiconfirmado como base em todos os sistemas que fornecem esse serviço. Neste capítulo

16


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 foramtomadas e será detalhada a visão de componentes e conectores do mesmo.

17

3O Dedupeer File Storage

3.1 Introdução

O Projeto Dedupeer é composto pela biblioteca homônima e pelo Dedupeer FileStorage (DeFS), que foi desenvolvido para facilitar os testes e avaliação dos algoritmosimplementados para a deduplicação, que é a principal contribuição deste trabalho.

Para representar de forma simples a comunicação entre o componente, o sistemade arquivos e o sistema de armazenamento que adicionar o componente, foi usado odiagrama de componentes 3.1. Observando a interação entre os artefatos que compõemtodo o sistema para deduplicação, percebe-se que o acesso aos arquivos é abstraído peloDedupeer. De uma forma transparente para o sistema de armazenamento o Dedupeerler, quebrar, e processar os bytes do arquivo especificado, levando em consideração osparâmetros passados pelo sistema através da interface de comunicação Thrift 1. O Thriftserá melhor detalhado na seção 4.2.1.

O DeFS foi desenvolvido para ocupar o lugar no diagrama que pertence aos sistemasde armazenamento de dados. Com a arquitetura planejada dessa forma, fica fácil fazer aintegração do algoritmo em muitos sistemas. O Thrift dá suporte à comunicação entrediversas linguagens, o que aumenta a quantidade de sistemas que podem ser integradosao Dedupeer.

3.1.1 Escopo

O Dedupeer File Storage é um sistema de armazenamento de dados, que pode serusado de forma distribuída, com capacidade de armazenamento e recuperação de arquivos.

1http://thrift.apache.org/

18

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 dearmazenamento que tem como base o banco de dados não relacional desenvolvido dentrodo Facebook, e hoje projeto incubado no Apache Foundation, chamado Cassandra2. OCassandra 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 basedo 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 comobanco de dados não relacional, o seu modelo de dados é totalmente diferente dos utilizadosnos 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 decolunas das outras e etc. Como a maioria das pessoas está acostumada com essa formade organização de um banco de dados, será feita uma breve apresentação do modelo dedados utilizado no Cassandra, para facilitar o entendimento sobre as escolhas de projetopara a modelagem do sistema de armazenamento.

2http://cassandra.apache.org/

19


No modelo de dados do Cassandra existe uma flexibilidade muito grande sobre comoestruturar os dados. A forma mais simples de dado que se pode armazenar é uma listaou array. Com a adição de uma nova dimensão é possível transformar essa lista em umMap e deixar os dados mais organizados. Essa nova dimensão pode servir para nomearos dados da dimensão citada primeiramente, o que torna o modelo um pouco parecidocom a estrutura utilizada no relacional. Abaixo tem um exemplo de um registro simplesno modelo de dados do Cassandra [16].

"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 elesnão precisam ser necessariamente uma string, o valor armazenado em qualquer uma dasdimensões pode ser até dados binários com limite de 2 GB, mas para melhor estruturaçãoa maioria dos bancos usam esse valor como uma string ou um long para representarum identificador para o valor da segunda dimensão, que está sendo representada noexemplo pelos valores "[email protected]"e "25". Todos esses valores juntosrepresentam uma linha, e a reunião das linhas recebe o nome de família de colunas. Asfamílias de colunas são associadas a um keyspace, que é um container de família decolunas, e que seria o equivalente a um banco de dados no modelo relacional. Cadainstâ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 tipoespecial 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"

20


"email": "[email protected]","idade": "25"

O Cassandra, quando utiliza super colunas, funciona como uma hastable de 5 dimen-sões [Keyspace] [ColumnFamily] [Key] [SuperColumn] [SubColumn] [16]. Para acessara "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 serarmazenados 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 dadosdos arquivos: UserFiles, Chunk; e um família de colunas para agilizar o processo deidentificaçã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 exemploo arquivo se chama "lorem.txt". Foram definidas seis subcolunas para essa família:

file idArmazena o identificador único do arquivo no sistema.

sizeArmazena o tamanho do arquivo em bytes.

chunksArmazena a quantidade de chunks em que o arquivo foi dividido.

with contentArmazena a quantidade de chunk que possui conteúdo

without contentArmazena a quantidade de chunks que não possui conteúdo. Este valor representa aquantidade 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 odesempenho evitando ter que consultar todos os chunks do arquivo para identificar quaisdeles são referências e quais armazenam o conteúdo. A criação de apenas um dos doisresolveria o problema, mas nesse caso, para a identificação do outro valor seria necessário

21


a consulta da quantidade total de chunks, então foi tomada a decisão de já armazenar ovalor calculado.

Na família de super colunas chamada Chunk a chave que identifica a linha é oidentificador único do arquivo, localizado na coluna com nome file id na família de supercolunas UserFiles. Cada linha representa as informações de todos os chunks pertencentesao arquivo referenciado. Cada arquivo só tem uma linha nessa família de super colunas.As subcolunas dessa família são detalhadas abaixo.

md5Armazena o valor do fingerprint representado por um valor do cálculo de umafunção SHA-1 sobre os dados do chunk atual.

hash32Armazena o valor do fingerprint representado por o resultado do cálculo de umahash de 32 bits sobre os dados do chunk.

indexArmazena 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 segundosegmento do arquivo e o primeiro segmento tiver 512 bytes de tamanho, esse valorserá 512.

lengthArmazena a quantidade de bytes que o chunk possui.

contentArmazena o conteúdo binário que se inicia na posição index e vai até a posiçãoindex + length dentro do arquivo. Armazena a quantidade de bytes que o chunk

possui.

pfileArmazena o identificador do arquivo ao qual o segmento referenciado pertence.

pchunkArmazena o identificador do segmento ao qual foi identificado que o conjunto dedados é idêntico. Em outras palavras, adiciona uma referência ao segmento quepossui o conteúdo que não foi armazenado no sistema por ser duplicado.

22


Percebe-se a flexibilidade da utilização do Cassandra nessa família de colunas, namesma família de colunas são armazenados dois tipo estruturais de dados, um pararepresentar um segmento com conteúdo binário e outro para representar uma referênciapara um outro segmento já armazenado no sistema. Para uma melhor visualização dessafamí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 deconsulta para o identificador de um arquivo de um determinado usuário baseado no nomedesse arquivo. A chave dessa família de colunas é o nome do usuário. Ela possui apenasuma coluna que tem o nome do arquivo do usuário e o id desse arquivo.

23


Figura 3.2 Modelo de dados do sistema distribuído desenvolvido com o Cassandra

24

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 Pro-ject, que engloba DeFS integrado com o Dedupeer. A visão de componentes e conectoresdo Dedupeer Project pode ser vista na Figura 3.3. Existem 3 grandes componentes nosistema: O DeFS, o Dedupeer e Cassandra, os quais serão descritos a seguir:

DeFSO Dedupeer File Storage é o sistema distribuído de armazenamento de dados quefoi desenvolvido na pesquisa para que os algoritmos de deduplicação propostospudessem ser testados com maior facilidade. O DeFS foi descrito na seção 3.2.

DedupeerO Dedupeer é a biblioteca onde os algoritmos propostos foram implementados.Ele possui uma interface Thrift para interoperabilidade de comunicação entrelinguagens de programação distintas, para facilitar a integração do mesmo coma maioria dos sistemas de armazenamento existentes. O componente Dedupeerserá descrito no capítulo 4, e o funcionamento dos algoritmos do Dedupeer serãodescritos no capítulo 5.

CassandraO Cassandra é um banco de dados distribuído que foi usado como base do sistemade 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 janelacom componentes gráficos. Esse componente ainda possui os renderizadores dos camposda tabela de listagem dos arquivos e o frame de configuração dos parâmetros que ficamarmazenados no arquivo. Ele tem ligação com as filas de backup (BackupQueue) e derestore (RestoreQueue) dos arquivos, as quais são incrementadas com novos itens atravésda interação do usuário. Os componentes para gerenciamento das filas de backup erestore (também conhecido como reidratação no contexto de deduplicação) funcionamcom 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 reidra-tação, esse é o componente central do DeFS. Ele é responsável pelo gerenciamento do

25

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 oDedupeer através do ThriftClient e indireta com o Cassandra através do componente degerenciamento de dados que foram agrupados em DaoOperations. O ThriftClient, comoo 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 sejamenviados para o Cassandra. Ele é usado apenas quando não é requisitada a utilizaçãoda biblioteca do Dedupeer, já que na deduplicação o Dedupeer já retorna todas asinformações sobre os chunks do arquivo, não sendo necessário nesse caso a divisão doschunks através do componente Chunking.

O componente Dedupeer

O componente Dedupeer possui apenas dois componente internos, o ThriftServer e oDeduplicationImpl. O ThriftServer é o servidor que fica esperando por comunicaçõesdos clientes Thrift, é ele que roda o serviço que espera pelos parâmetros necessários

26

3.4. DECISÕES DE PROJETO E CONSIDERAÇÕES

para o processamento da deduplicação, processamento esse que é executado dentro doDeduplicationImpl, o qual retorna a estrutura gerada através do processamento para oThriftServer 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 feitasna construção do Dedupeer File Storage e o motivo dessas escolhas. A tecnologia que foiescolhida 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 semum estudo sobre as consequências da escolha. Esse valor impacta tanto no desempenhodo sistema como no raio 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 fatode haver uma maior probabilidade de encontrar outros segmentos idênticos, já que ummenor conjunto de bytes precisará ser igual. Em contrapartida, com segmentos pequenosserá 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. O trabalho[46] afirma que depois dos testes executados para medir o tamanho ideal, eles encontraramo valor de 8 KB [46], que é o mesmo valor encontrado pelos criadores do Venti [29].O trabalho [19] relata que o tamanho do chunk para um sistema de deduplicação exata(exact deduplication), deve estar entre 4KB e 16 KB [19].

Esses valores serão levados em conta após o teste de desempenho que será feito paraidentificar a melhor combinação de tamanho de chunk e algoritmo de hashing no Capítulo6.

3.4.2 Cassandra para gerenciamento do armazenamento

Muitos dos desafios enfrentados quanto ao desenvolvimento de um sistema de arma-zenamento distribuído são delegados para serem resolvidos através do gerenciamento

27


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 ede falhas, recuperação de falhas, concorrência e agendamento de tarefas (jobs), e empa-cotamento de requisições [9]. Além desses, existem outros desafios como, garantia dedisponibilidade e consistência dos arquivos, replicação dos dados e tamanho e quantidadedas mensagens trafegadas. Nesta seção será discutida a forma como o Cassandra resolvetodos esses problemas.

O Cassandra foi desenvolvido em uma arquitetura peer-to-peer, também conhecidacomo P2P, que é uma das arquiteturas comuns existentes na internet, além dela, a outraarquitetura é a CLiente/Servidor. Na arquitetura Cliente/Servidor, existe no mínimo duasentidades, uma que requisita um recurso e outra que atende a essa requisição, nessaarquitetura os nós agem de uma forma ou de outra, nunca as duas ao mesmo tempo. Naarquitetura P2P as entidades se comportam tanto como clientes quanto como servidores,consumindo e oferecendo recursos na rede.

O trabalho [36] define P2P como uma rede na qual os nós compartilham parte dosseus recursos de hardware, entre eles, processamento, capacidade de armazenamento,impressora, entre outros. Esses recursos compartilhados são essenciais para os serviços econteú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.[36] 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 qualquerperda. 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áriapara fornecer parte do serviço que a rede se dispõe a oferecer [36].

No Cassandra, a arquitetura P2P usada foi a pura. Todo nó no Cassandra é idênticoaos outros, não existe nó mestre e nem nó escravo. Com essa estrutura, a escalabilidadehorizontal se torna mais fácil, já que só é preciso adicionar um novo nó no cluster paraque ele se integre e se organize dentro da rede, para isso, ele possui um tempo paraaprender 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 areceber como qualquer outro que integra à rede.

O Cassandra utiliza o próprio sistema para armazenar as informações de configuraçõesdele. 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.

28


Tolerância à falhas

O Cassandra usa o gossip protocol[22] para a detecção de falhas. Periodicamente,uma mensagem é enviada para um outro nó, quando o nó recebe a mensagem ele respondecom um Ack, quando a mensagem é recebida pelo nó que a iniciou, ele responde comum Ack2. Com a utilização desse protocolo é possível identificar os nós que pararam defuncionar. O Cassandra ainda usa um algoritmo que ao invés de apenas informar se umsistema é ou não confiável, ele retorna uma valor que é o nível de suspeita, esse algoritmoé chamado de Phi Accrual Failure Detection [10]. O Cassandra possui um método queajuda na decisão se um nó está morto ou não, baseado no valor do nível de suspeita, comassinatura 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 osproblemas 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éplicasarmazenados nos nós estejam atualizados com a versão mais recente. Durante a fasede compactação, os nós fazem a requisição das árvores Merkle dos vizinhos para podercomparar 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, se caso for encontrado algumvalor diferente, é feito o reparo nos dados atualizando-os para a versão mais recente [36].Anti-entropy também é usado no Dynamo [9], mas o Cassandra faz um uso diferente, naimplementação do Cassandra existe uma árvore Merkle para cada família de colunas. Oalgoritmo 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çãode uma escrita mal sucedida. A escrita só é marcada como feita quando a operação é salvano commit log, com ele é possível recuperar uma falha na escrita feita em memória. Apósa escrita no commit log o dado é salvo em uma estrutura de dados alocada na memóriaque é chamada de Memtable. O Memtable só terá os dados salvos no disco quando eleatingir um limite de objetos armazenados. A estrutura aonde os dados são salvos no discoé chamada de SSTable.

29


Read.ONE Read.QUORUM Read.ALLWrite.ANY Weak Weak WeakWrite.ONE Weak Weak StrongWrite.QUORUM Weak Strong StrongWrite.ALL Strong Strong Strong

Tabela 3.1 Força do consistência baseada nos níveis das operações [8]

Consistência

A consistência dos dados que são armazenados no Cassandra tem o seu nível definidopelo usuário. A consistência pode ser usada como valor ONE (consistência fraca), nessení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 muitosclientes 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 deconsistência ALL, o Cassandra consulta os dados armazenados em todos os nós antes deretornar o valor. Se uma das consistências fortes forem utilizadas (QUORUM ou ALL), arecuperaçã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: consis-tência, disponibilidade e tolerância à partição. O teorema diz que é impossível que umsistema distribuído possua os três aspectos ao mesmo tempo, sempre um desses aspectostem que ser sacrificado. O Cassandra tem flexibilidade e permite que o usuário escolhaos aspectos do CAP Theorem que estão no sistema. A tabela 3.1 mostra qual o nível deconsistência do Cassandra a depender das escolhas do usuário [8].

O quorum é o número de nós que deve ser consultado para se chegar a um consensosobre a validade do dado (pode ser ANY, ONE, QUORUM ou ALL). Se o valor doquorum for ONE, o dado só será armazenado em um único nó, o que vai torná-losempre consistente, mas em contrapartida, ele nunca será replicado, o que diminui adisponibilidade do mesmo.

Disponibilidade

O Cassandra possui um mecanismo para disponibilidade de escrita mesmo quando onó que receberia a mensagem tem uma falha de hardware, ou qualquer outra que o impeçade 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,

30


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 mensagensque chegam são encaminhadas para um pool de threads, o qual é responsável pelogerenciamento delas. Em seguida, é analisado se a mensagem é do tipo streaming, que éuma forma eficiente utilizada pelo Cassandra para fazer a transferência de SSTable entreos nós, ou se é uma mensagem serializada padrão, e a partir disso é determinado paraqual 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 HBase para serusado no Dedupeer File Storage. Os pontos considerados críticos para a escolha e quefizeram com que o Cassandra fosse escolhido foram: facilidade de instalação/manutençãoe funcionamento em pequenos clusters. Esses foram os pontos considerados mais impor-tantes pelo fato do objetivo ser a criação de um sistema para armazenamento de arquivosque funcionasse tanto como um sistema de armazenamento stand-alone como um sistemade 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 paradar suporte ao Hadoop, logo ele é mais complicado de ser gerenciado já que por padrãoele está integrado com o Hadoop, HDFS e Zookeeper3. O Cassandra não tem por padrãoessa ligação com outros sistemas, ele é mais fácil de instalar e manter que o HBase.

Clusters pequenos

Segundo o site oficial do HBase4, ele não é adequado para ser usado em um cluster

com menos de 5 DataNodes, o que inviabilizaria a possibilidade da utilização do DedupeerFile Storage em um computador stand-alone. Esta foi uma funcionalidade colocada comoprioritária no projeto, pois ela é útil para conseguir a economia de espaço proporcionada

3http://whynosql.com/cassandra-vs-hbase/. Acessado em abril de 20134http://hbase.apache.org/book/architecture.html. Acessado em abril de 2013

31


pela deduplicação em computadores, sem que para isso precise criar um sistema dearmazenamento distribuído.

O HBase precisa de mais nós porque ele é dependente do HDFS, e o HDFS utilizauma replicação de blocos de 3 cópias.

3.4.4 Escalabilidade

Primeiramente, o conceito do que é escalabilidade será descrito, antes da apresen-tação das vantagens que a escolha do Cassandra para gerenciamento do sistema dearmazenamento oferece para a escalabilidade.

O que é escalabilidade?

Construir arquitetura de sistema para dar suporte à milhões de usuários é um dosmaiores desafios enfrentados pela indústria de software. Esse desafio fica mais complexoquando a arquitetura é projetada para escalar e se adaptar à quantidade de usuários semprecisar ter que reprojetá-la.

Quando se fala em escalabilidade, uma quantidade próxima a 100% dos engenheirosde software só conseguem enxergar sistemas que escalam para mais usuário (scale up),mas escalabilidade também está relacionado à capacidade do sistema em escalar parasuportar menos usuários (scale down), ou seja, ele deve ser capaz de reduzir a quantidadede recursos alocados quando a demanda de usuários diminuir [34].

Existem dois tipos de escalabilidade de sistemas: horizontal (scale up) e vertical(scale out). Escalabilidade vertical é a capacidade de adicionar recursos a um nó dosistema e ele se adequar à nova configuração. Escalabilidade horizontal é a capacidadedo sistema se adequar à adição de novos nós.

Quando um sistema precisa escalar horizontalmente (scale up), é um forte sinal deque a demanda por ele está crescendo, esse fator é um indício de que o lucro da empresatambém está crescendo junto. Quando isso acontece, e a arquitetura do sistema foipobremente planejada para escalar horizontalmente, a empresa pode investir parte doslucros 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 caibruscamente, os lucros da empresa com o sistema geralmente também caem, e a empresatenta ao máximo reduzir os custos. Percebe-se que se a arquitetura não é planejada parascale down, a perda de dinheiro com a redução de cliente pode se tornar maior, já que aquantidade de recursos alocados para o sistema se tornam ociosos por ter sido reservado

32


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, aquestão da escalabilidade é um outro ponto que o Dedupeer File Storage não precisará sepreocupar, já que todo o gerenciamento é feito pelo cluster de Cassandras.


Este capítulo apresentou o Dedupeer File Storage, que foi sistema de armazenamentode arquivos desenvolvido para auxiliar a pesquisa, e que pode ser usado tanto um sistemade armazenamento local como um sistema de armazenamento distribuído. Ele é integradoatravé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 dosistema 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 trataros 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 edetalhará as principais decisões de projeto no seu desenvolvimento.

33

4Componente para deduplicação em

sistemas de armazenamento de dados

4.1 Introdução

O desenvolvimento do Dedupeer foi planejado para que os algoritmos desenvolvidospudessem ser usados pela comunidade de forma fácil. O Dedupeer foi projetado paraque as escolhas de configurações fossem feitas através de parâmetros da interface deserviç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 sistemade armazenamento que tenha como objetivo obter um ganho na economia de espaçoutilizado, 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 impactodo uso de sistemas de armazenamento ao meio ambiente. Das discussões sobre usoeficiente dos sistemas de armazenamento, a EPA liberou um documento de especificaçãopara discussão pública, onde deduplicação de dados é considerada umas das tecnologiasda green storage [12], veja na citação abaixo.

"EPA understands that there are many software-based approaches to impro-

ving 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

1http://www.snia.org/forums/green

34

4.2. INTEROPERABILIDADE

the hardware itself, are heavily customized for specific customers and ap-

plications. 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, assimcomo uma técnica utilizada para tornar o processamento da deduplicação temporalmenteviável.

4.2 Interoperabilidade

Engenharia de Software baseada em componentes desperta muito interesse devidoa reusabilidade do software. O seu objetivo é reduzir o custo e o esforço no desen-volvimento, enquanto prover flexibilidade, confiabilidade e reusabilidade, pelo fato docomponente já ter sido validado e testado antes da integração [41].

Um dos principais conceitos chave para a criação de componentes de software reusá-veis é a interoperabilidade. A Interoperabilidade foi definida por [41] como a habilidadede duas ou mais entidades se comunicar ou cooperar, apesar das diferenças na linguagemde implementação, ambiente de execução, ou modelo de abstração. Existem dois níveisde interoperabilidade: assinatura e semântica. A primeira é baseada na assinatura dasoperações que o componente disponibiliza para interação, como por exemplo, nome demétodos, tipos dos parâmetros e valores de retorno. A interoperabilidade semântica tentagarantir que a troca de dados entre os componentes faça sentido, mas pelo fato desse nívelde interoperabilidade englobar todos os aspectos semânticos, ele é considerado muitocomplexo, o que direcionou a maioria dos trabalhos sobre esse nível para uma de suasáreas, relacionada às questões comportamentais dos componentes [41].

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 Apa-che Software Foundation2. Ele possui uma ferramenta de geração de código para facilitaro desenvolvimento da criação dos serviços em diversas linguagens de programação. Oprincipal objetivo do Thrift é fornecer a capacidade de comunicação entre linguagens de

2http://thrift.apache.org/

35


programação distintas. O Thrift permite que os desenvolvedores definam tipos de dadose serviços em um arquivo de linguagem neutra e gera toda a estrutura necessária, tantopara o servidor como para o cliente RPC (remote procedure call) [3].

O Thrift tem flexibilidade para a criação de estruturas de dados, além de também darsuporte aos principais tipos, independente da linguagem utilizada. Como tipo base, oThrift possui os seguintes:

bool Um valor booleano, true ou false.

byte Um byte assinado.

i16 Um inteiro assinado de 16 bits.



double Um número de ponto flutuante de 64 bits.

string Um conjunto de caracteres.

Além desses tipos de dados mais simples, existem estruturas de dados mais complexasque podem ser usados para a comunicação entre linguagens com o Thirft. Para isso, elefaz as conversões entre as estruturas definidas nessas linguagens. As 3 estruturas de dadosque podem ser usados no Thrift são:

list<type> Um lista ordenada de elementos. Essa estrutura é traduzida em um ArrayListem Java ou em array nativo nas linguagens de script.

set<type> Um conjunto não ordenado de elementos únicos. Traduzido para HashSet emJava.

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 estruturasequivalente à objetos para serem transferidas através do Thrift, os quais são chamadosstructs. Dentro de um structs pode-se adicionar quantos tipos forem necessários, os quaispodem 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 configuradocomo opcional, o objeto terá um método que poderá ser usado para adicionar um valor aocampo e ele não será um dos parâmetros do construtor.

36


O Thrift possui o conceito de serviços, os quais são definidos no mesmo arquivo queos tipos. Com a geração automática do código através do compilador do Thrift, toda aestrutura necessária para que o serviço funcione é criada, tanto a parte cliente como aparte 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çãodos 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 utilizadonos sistemas atuais, o Protocols Buffer.

Protocols Buffer

O Protocols Buffer foi desenvolvido na Google e é utilizado internamente em quasetodos os seus protocolos RPC [23]. Segundo o Developer Guide [1], 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 docu-mentação é bem reduzida. Ele dá suporte à apenas 3 linguagens: C++, Java, Python.Isso acaba limitando a integração com sistemas desenvolvidos em outras linguagens. OThrift 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.

Quanto à quantidade de tipos suportados, ele também possui uma quantidade inferiorao Thrift. O Protocols Buffer dá suporte aos tipos: bool, 32/64-bit integers, float,

37


double, string, sequência de byte e o "repeated"que funciona como uma lista. O Thriftdá suporte aos tipos: bool, byte, 16/32/64-bit integers, double, string, sequência debytes, map<t1,t2>, list<t>, set<t>. Como no Dedupeer a estrutura de dados trafegadanecessitava da utilização de um map, a facilidade de implementação dessa estrutura noThrift foi um dos motivos para decidir por ele quando comparado ao Protocols Buffer.

Na seção 4.2.2, será discutido mais sobre o Protocols Buffer.

Comparação de desempenho

O Protocols Buffer leva vantagem no desempenho em relação ao Thrift, mas o pesodessa vantagem não influenciou na decisão de escolha, devido ao fato de que o suporte amais linguagens e a possibilidade de utilização de estruturas de dados como Map foramconsiderados mais importantes para o projeto do que a diferença entre o desempenho dasferramentas, por isso o Thrift continuou como escolhido.

Nas Figuras 4.1 e 4.2, são apresentados resultados de um teste de desempenho feitocom algumas bibliotecas de serialização. Percebe-se que o Protocols Buffer, chamadode protobuf, tem um melhor desempenho que o Thrift. Na serialização dos dados, oProtocols 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.

Figura 4.1 Desempenho na serialização dos dados [2]

4.2.3 Comparação por hash (fingerprints)

Uma função hash mapeia um conjunto de dados de tamanho variável para um resultadocom tamanho fixo. Como o valor no qual o conjunto de dados é mapeado tem um tamanhomenor do que o conjunto de entrada, existe uma possibilidade de dois ou mais conjuntos

38


Figura 4.2 Desempenho na desserialização dos dados [2]

de dados distintos terem um valor de hash igual. Quando o mesmo hash é obtido deconjunto de dados diferentes, é dito que houve uma colisão de hashes [15].

Comparar a igualdade entre arquivos ou entre blocos de dados através do resultadode uma função hash aplicada aos seus conteúdos, é um forma eficiente de verificar se osconteúdos são diferentes com probabilidade de erro igual a zero. Muitos sistemas utilizama comparação para identificar igualdade em conteúdos também, como por exemplo, orsync[40] e o Venti[29]. Apesar da utilização dessa técnica em vários grandes projetos, acomparação de igualdade entre conteúdos através de uma função hash aplicada à ele temprobabilidade de encontrar um falso positivo.

O cálculo de uma função hash é muito eficiente. O cálculo do SHA1 de 160 bitsem um bloco de 8KB, utilizando um computador Pentium 3 de 700Mhz, é feito em 130microssegundos, o que dá a média de 60MB/s [29].

Comparar todos os bytes de dois blocos de dados para identificar se os mesmos sãoiguais, é uma tarefa muito custosa. O custo computacional para fazer uma comparação deblocos de dados com 128 KB cada um é menor, se ao invés de comparar todos os 128 KBde conteúdo fizer a comparação apenas dos valores de hash dos dois, que se for obtidoatravés de uma função MD5 de 128 bits, por exemplo, terá um valor de representaçãocom 32 dígitos hexadecimais. A comparação de 128 KB de dados é substituída por umasimples 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 desegmentos é totalmente confiável, mas em contrapartida, é extremamente custoso. Apesarda comparação por hashes ter a probabilidade de dar um falso positivo para um segmentosde dados com conteúdos diferentes, o principal argumento dos defensores dessa técnica é

39


que a probabilidade de ocorrer um erro no hardware que armazena o dado é muito maiordo 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 detectadosna memória principal, na transferência pela rede, nos dispositivos de armazenamentoou qualquer outro componente de hardware, do que por uma colisão de hashes. Poreste motivo, foi definido que o método de identificação de segmentos iguais utilizado noprojeto seria através da comparação por hashes.

Para assegurar que os dados são realmente idênticos, algumas empresas, como aNetAPP, 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 dadossã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 dessafunçã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 bitsno valor do hash de saída.

Considerando um sistema que usa blocos de 8 KB com fingerprints calculados comSHA1 de 160 bits e que possua 1 exabyte (1018bytes) de dados armazenados, o quedá um quantidade de aproximadamente 1014 blocos, a probabilidade de uma colisão dehashes ocorrer neste cenário ainda é extremamente baixa, essa probabilidade é menorque 10−20 [29].

Vantagem

A comparação bit a bit, apesar de ser uma técnica na qual se pode ter uma certezaabsoluta sobre a igualdade de dois conjunto de dados, ela possui desvantagens. Além deser 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 foiusado porque apesar da possibilidade de colisão, ele permite a possibilidade de analisara igualdade de dois conjuntos de dados sem tê-los em um mesmo computador, o quepossibilita o processamento remoto. Outro ponto positivo para a escolha do SHA-1, é ofato de até hoje não ter registros de colisão de hashes com ele [35].

Se for utilizado SHA-256, a probabilidade de colisão é ainda menor, segundo [27]a probabilidade de uma colisão em um conjunto de 1024 exabytes de dados em um

40


sistema de deduplicação, com um tamanho de chunk de 4KB e utilizando o SHA-256para calcular os fingerprints, é menor que 10−42.


Neste capítulo foram discutidas algumas das principais decisões de projeto para acriação do Dedupeer como um componente interoperável, com facilidade de adaptaçãocom sistemas de armazenamento na maioria das linguagens populares. Também foiexplicada a técnica de análise de fingerprints, usada para a identificação de conjunto dedados idênticos, que é usada pelos algoritmos de deduplicação em geral, e as vantagens eproblemas que podem ocorrer com a utilização dessa técnica. Também foi apresentadauma alterativa para identificação de conjuntos de dados iguais, que no caso do projetoproposto, 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.

41

5Os algoritmos

Dois algoritmos foram desenvolvidos para fazer a deduplicação no projeto, um maissimples, 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 queo processamento do arquivo seja feito de forma particionada, com a carga do bytes para amemória de forma parcial.

Este capítulo é dividido em duas partes, na primeira é feita a fundamentação basepara o desenvolvimento dos algoritmos, e a segunda é descrito o funcionamento de cadaum dos dois algoritmos, tanto uma explicação de alto nível como uma mais aprofundadana implementação.

5.1 Fundamentos

Nesta Seção, serão explicados os dois principais conceitos utilizados para tornar odesempenho do processamento da deduplicação viável, o rolling checksum e o fingerprin-

ting. Uma breve introdução sobre o percursor da análise de igualdade entre arquivos deforma remota também será discutido.

5.1.1 O algoritmo Rsync

O algoritmo Rsync foi desenvolvido para otimização de transferência de arquivos entrecomputadores e foi utilizado primeiramente na ferramenta de mesmo nome, desenvolvidopor Andrew Tridgell and Paul Mackerras [40].

Suponha que dois computadores tenham versões diferentes de um mesmo arquivo, eque o objetivo seja atualizar o arquivo mais antigo para a versão mais recente, ao invés deenviar o arquivo todo e substituir a versão mais antiga, pode-se calcular e enviar para o

42

5.1. FUNDAMENTOS

outro lado apenas a os bytes diferentes entre esses arquivos. A identificação da diferençaentre arquivos pode ser feita de várias formas, a maioria dos algoritmos usa a abordagemde análise de dois arquivos localmente para a identificação da redundância de conjuntode 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 dadiferença entre os arquivos de forma remota, com isso ele identifica as partes do arquivoque precisam ser enviadas para o outro computador e quais partes precisam ser apenasreferenciadas, evitando assim a transferência do arquivo todo para o destino.

O algoritmo Rsync funciona da seguinte maneira [40]:

• 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 ummais 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 ofingerprint obtido com o de 32 bits enviado por β . Caso encontre alguma parte doarquivo 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 quenã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 custosaquando o cálculo do checksum da janela anterior já tiver sido feito, por exemplo, se ochecksum do bloco de bytes Xk ... Xl já for conhecido, obter o do bloco Xk+1 ... Xl+1

é mais rápido [40]. 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 extremamente inviável a identifica-

ção de partes iguais dentro de um arquivo, até mesmo em arquivos que sejam backups

43

5.1. FUNDAMENTOS

sucessivos e que possuam apenas uma pequena parte diferente. O problema é que qual-quer alteração, seja ela uma adição, uma remoção ou qualquer outra mudança, deslocao conteúdo do arquivo, isso causa uma alteração em cadeia em todos os segmentos doschunks posteriores, que receberão os bytes de um vizinho e fornecerá bytes para o vizinhoque o sucede.

5.1.2 Fingerprinting

Fingerprints é uma outra técnica que foi aplicada como base nos dois algoritmosdesenvolvidos, eles são valores que identificam uma sequência específica de dados. A suaprincipal propriedade é a identificação da diferença entre conjuntos de dados, indepen-dente de formato, que possuam o mesmo tamanho. Ele é usado também para identificarigualdade entre conjuntos de dados, pelo fato da probabilidade dos valores serem idên-ticos, quando os conjuntos de dados são diferentes, ser quase zero. O fingerprint é oresultado do cálculo de uma função hash aplicada em um conjunto de dados. Na maioriadas vezes os fingerprints são calculados a partir das funções hash MD5 ou SHA1 porserem funções com baixa probabilidade de colisão. [14]

Para um melhor entendimento, um esquema de fingerprinting é um conjunto de funçãoF =

{f : ω →{0,1}k

}, onde ω representa o conjunto de todos os segmentos possíveis

e k é o tamanho do fingerprint. Se for escolhido um conjunto S ⊂ ω de n seguimentosdistintos, 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

[7].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, aprobabilidade de colisão de hashes entre dados não idênticos com a utilização de umafunção hash SHA256 é de aproximadamente

2−256 = 10−77

[6].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

44

5.2. DETALHANDO OS ALGORITMOS

de uma só vez. Considerando o tamanho padrão dos segmentos como 8 KB de tamanho,sendo representado por um fingerprint de 160 bits, um arquivo de 8 TB teria um conjuntode fingerprints com tamanho de 20 GB [46].

5.2 Detalhando os algoritmos

O Dedupeer possui dois algoritmos para fazer a deduplicação de um arquivo. Oprimeiro, e mais simples, foi desenvolvido com base no princípio de comparação deconjunto 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. Naspró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 arquivona memória

Esse algoritmo foi o primeiro a ser desenvolvido. Ele foi baseado na forma de identifi-cação de igualdade de conjuntos sequenciais de bytes do Rsync, no qual é informado umvalor de um função de hash aplicada à um chunk e esse valor é comparado com os valoresde hash obtidos a partir da execução da função de rolling hash aplicada ao arquivo emque se deseja encontrar as partes duplicadas.

Será feita uma explicação do funcionamento do algoritmo utilizando um diagramade atividade simples em conjunto com abstrações da estrutura de dados em caixas, eem seguida, o algoritmo será explicado mais profundamente, com discussão sobre aimplementação, utilizando pseudocódigo de alto nível para isso.

No cenário de exemplo para fundamentar a explicação, existem dois arquivos deuma 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 dearmazenamento de dados distribuído, que possui as informações sobre cada chunk dessearquivo, como o valor do hash de 32 bits e do SHA-1. O cenário mostra o processamentoque é feito pelo algoritmo antes da música ser enviada para o sistema de armazenamentodistribuído. Sem um algoritmo de deduplicação integrado ao sistema de armazenamento,

45


esse novo arquivo seria totalmente copiado para ele, e no caso do sistema possuir umalgoritmo de deduplicação apenas para arquivos completos, ele também não conseguiriaa compressão dos dados nesse caso, já que apesar da maior parte do conteúdo dos doisarquivos serem idênticos, esse tipo de algoritmo não consegue identificar igualdade departes do arquivo.

Antes de enviar o novo arquivo para o sistema de armazenamento, o processamentopara 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 dedupli-cação, como as informações dos valores dos fingerprints dos chunks. O algoritmo entãocarrega 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 noarquivo. Essa janela tem o tamanho definido através de um parâmetro que é passado pelosistema 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 dochunk não é necessário para a identificação de uma sequência de bytes idêntica, paraisso, só é necessário o conhecimento dos valores dos fingerprints. Primeiramente, o valordo 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 temo seu início indicado a partir na posição apontada pelo windowsIndex, e vai até o finalda janela. Esses dois valores são comparados, se eles forem diferentes, o byte inicialda janela é incrementado em 1 (windowsIndex++) e o cálculo do rolling hash é feitoem cima do valor do hash da janela anterior. Esse procedimento é executado até queos valores dos hashes sejam iguais ou o fim do arquivo seja alcançado. No exemplodemonstrado na 5.1, quando o início da janela estiver no terceiro byte, o cálculo dohash será idêntico ao procurado. Quando esses valores são iguais, é feito um cálculodo SHA-1 no conjunto de bytes que está dentro da janela, e o valor é comparado como SHA-1 do chunk armazenado no sistema. Se esses valores forem diferentes, significaque a comparação dos hashes fracos deu um falso positivo e o procedimento de buscasegue com o incremento do início da janela, caso contrário, é considerado que o conteúdoque está dentro da janela é igual ao do chunk armazenado no sistema, e uma indicaçãode referência é criada, para que os bytes não sejam enviados para o sistema. O inícioda janela salta para a posição após o último byte do chunk encontrado, e a busca pelo

46


próximo começa a partir desse ponto.

Figura 5.1 Funcionamento do algoritmo 1.

A análise do pseudocódigo de alto nível do algoritmo vai ser feita a seguir. Oalgoritmo 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 precisareceber algumas variáveis que serão informadas pelo sistema de armazenamento. Aestrutura esperada com as informações dos chunks é basicamente, o hash de 32 bits, oSHA-1 e o ID de cada um deles, para um maior ganho de desempenho eles precisamestar ordenados, baseado no fato de que a probabilidade de que o chunk posterior sejaduplicado se o anterior for é grande. Vale ressaltar que nem todos os chunks armazenadosno sistemna precisam ser passados para o algoritmo, é recomendável que somente ospertencentes à 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 similarcom o que vai ser processado à procura de partes duplicadas.

1https://github.com/paulofernando/dedupeer

47


O outro parâmetro esperado é uma string representando o caminho absoluto para oarquivo no sistema de arquivos local, para que o algoritmo possa ler os seus bytes e fazero processamento com esses dados. Um objeto map<position,Chunk> é retornado, ondeposition é referente à posição do byte inicial do conjunto sequencial de dados que formamo chunk, e o valor no map é referente à informações sobre o chunk, como, o identificadordo chunk que está armazenado no sistema distribuído e que foi encontrado como dupli-cado, ou, no caso de não ter encontrado nenhum idêntico, as informações armazenadassão as necessárias para que o sistema consiga identificar o conjunto sequencial que nãoestá duplicado, como posição inicial e final dentro do arquivo, e os valores calculados doshashes desse novo chunk, para que o dados dele sejam enviados para armazenamento.

1: input: informações dos chunks armazenados e path do arquivo para ser deduplicado2: output: apontador para os chunks duplicados no arquivo informado3: for i = 0 to amountChunks do4: index← searchDeduplication(modFile,chunk[i].hash32)5: if index <> -1 then6: if window.sha1 = chunk[i].sha1 then7: chunkRe f erences←< index,chunkIn f o >

8: end if9: end if

10: end for11: index← 012: bu f f er← allocate(de f aultChunkSize)

13: while index < modFile.length do14: if chunkReferences contains index then15: if buffer position > 0 then16: chunkRe f erences←< index,newChunkIn f o >

17: bu f f er.clear()

18: end if19: index← index+newChunk.length

20: else21: if buffer is full then22: chunkRe f erences←< index,newChunkIn f o >


24: else25: bu f f er.put(nextByteInT heWindow)

48


26: index← index+127: end if28: end if29: end while30: if buffer position > 0 then31: chunkRe f erences←< index,newChunkIn f o >


33: end if34: 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 comoparâmetro, arquivo esse previamente carregado na variável modFile. A variável index queaparece pela primeira vez na linha 4, representa a posição incial do chunk duplicado noarquivo local, essa identificação é feita através do método searchDeduplication, que nadamais é do que um método que utiliza o rolling checksum para identificar um conjuntode dados com o mesmo hash fraco do chunk atual da iteração. Quando o valor doindex for diferente de -1, será porque o método encontrou um conjunto de dados quepossui o mesmo valor de hash fraco do chunk atual da iteração, mas como já explicadoanteriormente, 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 decolisão é alta, logo, para termos uma probabilidade de quase 100% que os dados sãoidênticos, é feita uma comparação com o SHA-1. No caso dos valores do SHA-1 seremiguais, é considerado que os chunks também são iguais, apesar de existir uma mínimaprobabilidade 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 doarquivos que não estão duplicados, e adicionar os mesmo na variável que será retornadapara o sistema de armazenamento, à qual conterá as referências para os chunks que estãono sistema, identificação essa que foi executada entre as linhas 3 e 10 do algoritmo. Nessalinha, a variável buffer é criada com o tamanho de bytes igual ao padrão do sistema. Obuffer serve para armazenar os bytes iniciais que são descartados da janela toda vez que oconjunto 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 é oXk+1 ... Xl+1, o primeiro byte que estava no conjunto de dados anterior é descartado danova 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

49


foi encontrado duplicado no sistema na busca feita anteriormente, caso a condição sejaverdadeira, é 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 tamanhopadrã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 essesdados e em seguida é feita uma limpeza no buffer. Se o buffer não tiver atingido o limitemáximo de alocação, o byte atual é armazenado nele e a posição do índice é incrementadoem 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 linha34.

5.2.2 Algoritmo com deduplicação particionada

Para que o Dedupeer fosse capaz de fazer deduplicação de arquivos sem um limitede tamanho, foi desenvolvido um segundo algoritmo que tem como princípio base acapacidade de processar esse tipo de arquivo, para isso, ele utiliza uma técnica departicionamento 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 como 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 emJava 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 comos chunks no sistema, exige que as informações dos chunks estejam estruturadas de umaforma diferente do primeiro algoritmo. Como entrada, a interface espera por informaçõesdos chunks que estão armazenados no sistema para que o algoritmo os procure no arquivoa ser deduplicado, como no anterior, mas a estrutura de dados definida que organizaessas informações é um map<weakHash,map<strongHash,chunkIDs», pois existe umaprobabilidade real de que dois chunks com conteúdo diferente tenham o mesmo valorde um hash de 32 bits, que é conhecido como colisão de hash. Foi criado um outromap interno que armazena os SHA-1 como chave, para que as informações de chunks demesmo hash fraco não sejam perdidas por sobrescrita de valor no map e tem como valorum objeto que possui dois IDs, o do chunk e o do arquivo. A interface também esperao caminho absoluto do arquivo a ser deduplicado, e um parâmetro que é a quantidademáxima de bytes do arquivo que pode ser carregada para a memória por vez.

50


Figura 5.2 Funcionamento do algoritmo 2

Primeiramente, o algoritmo recebe o map com as informações dos chunks armazena-dos no sistema. Em seguida, a quantidade de bytes máxima informada pelo sistema comoparâ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. Vejaa 5.2.

Diferente do primeiro algoritmo, este utiliza uma estratégia de comparação diferentedo Rsync, e que o torna capaz de fazer o processamento de arquivos em partes. O Rsyncprocura um determinado conjunto de dados que tenha um fingerprint específico, e pra issoele 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 (tempode execução) da estrutura de map (hashtable), a qual é O(1), e ao invés de percorrer oconteúdo de um arquivo à procura de um fingerprint, ele calcula o fingerprint dos dadosna janela do arquivo em memória e em seguida faz uma busca no map, ou seja, diferentedo Rsync a comparação é feita de forma inversa.

Se o hash de 32 bits dos dados dentro da janela estiver na estrutura de map, é feitoo cálculo do SHA-1 dos mesmo dados e essa valor é procurado dentro do map interno

51


que é o valor da chave de hash 32 bits encontrada. Se o hash de 32 bits ou o SHA-1não forem encontrados, é feito um teste para saber se a quantidade de dados restante naparte 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 outraparte do arquivo é carregado para a memória. Isso é feito porque para calcular o valor dohash de 32 bits da função de rolling checksum, é necessário ter uma quantidade de dadoscom o tamanho padrão exato do chunk do sistema. Se o tamanho restante for maior, oprocessamento 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ésda 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 doarquivo e as informações sobre os novos chunks.

1: input: informações dos chunks armazenados, path do arquivo para ser deduplicado equantidade de bytes para carregar para a memória por vez

2: output: apontador para os chunks duplicados no arquivo informado3: o f f set← 04: validate(bytesToLoadByTime)

5: divideInTime← f ileLength/bytesToLoadByTime

6: bu f f er← allocate(de f aultChunkSize)

7: for i = 0 to divideInTime do8: localIndex← 09: partO f File← getNextBlockO f File(o f f set)

10: currentChunk← getNextChunkPartO f File(localIndex)

11: while localIndex < partOfFile.length do12: if partOfFile.length - localIndex + moreBytesToLoad = defaultChunkSize then13: partO f File← getNextBlockO f File(o f f set)


15: o f f set← o f f set +moreBytesToLoad

16: end if17: if chunk[i].hash32 contains window.hash32 then18: if currentChunk = null then19: currentChunk← getNextChunkPartO f File(localIndex)

20: end if21: if chunk[i].sha1 contains window.sha1 then22: if buffer has data then

52


23: newChunk← createNewChunk(bu f f er)

24: chunkRe f erences←< globalIndex−newChunk.length,newChunk.in f o>


26: end if27: chunkRe f erences←< globalIndex,re f erenceToT heChunk >

28: globalIndex← globalIndex+ currentChunk.length

29: localIndex← localIndex+ currentChunk.length


31: end if32: end if33: if not duplicate then34: currentChunk← null

35: if buffer is full then36: newChunk← createNewChunk(bu f f er)

37: chunkRe f erences←< globalIndex−bu f f er.position,newChunk.in f o >


39: else40: if partOfFile.length - (localIndex + defaultChunkSize) > 0 then41: bu f f er.put(partO f File[localIndex])

42: globalIndex← globalIndex+143: localIndex← localIndex+144: else45: 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

48: globalIndex← globalIndex+newChunk.length−bu f f er.position


50: if localIndex < partOfFile.length then51: newChunk← createNewChunk(partO f File, localIndex)

52: chunkRe f erences←< globalIndex,newChunk.in f o >


53


54: localIndex← localIndex+newChunk.length

55: globalIndex← globalIndex+newChunk.length

56: end if57: end if58: end if59: end if60: end while61: o f f set← o f f set +bytesToLoadByTime

62: end for63: returnchunkRe f erences

O método validate, chamado na linha 4, verifica se o valor passado pelo sistema parainformar a quantidade de bytes para ser carregado por vez na memória é maior que otamanho 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 queseja mais próximo do valor informado, para que a probabilidade de um chunk que possuaum idêntico armazenado no sistema não seja dividido entre duas cargas diferentes para amemória, fato que se ocorresse, impossibilitaria o algoritmo de identificar a igualdade. Alinha 5 calcula a quantidade de cargas que precisarão ser feitas para a memória, valor esteutilizado 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 doarquivo que será deduplicado a partir da posição definida como parâmetro, esse array debytes é 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 paraanálise. A condicional da linha 12 é uma estratégia para não perder a identificação deum chunk duplicado quando este está no final da parte do arquivo que foi carregadopara a memória, e tiver sido encontrado grande parte da carga como idêntica à de outroarquivo já no sistema. Basicamente, esta parte do algoritmo serve para deixar o últimochunk da carga com o tamanho padrão do sistema, e assim, possibilitar a identificação deigualdade. Observando o exemplo da 5.3, percebe-se que sem a carga extra de bytes, ochunk representado pelos 4 hexadecimais 7C CE 72 A4, mesmo sendo duplicado, nãoserá 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 dascargas posteriores do arquivo já estejam armazenadas no sistema por fazer parte de umaversão anterior do mesmo arquivo, sem a carga extra de bytes, será deixado de deduplicar

54


Figura 5.3 Vantagem da utilização da carga extra de dados

um chunk por carga, pois parte dele estará no final de uma carga e a outra estará nocomeça 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 namesma 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 calculadoda 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 querepresenta 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 nalinha 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, todoo seu conteúdo é transformado em um único chunk e o mesmo é esvaziado para poderreceber os bytes iniciais da janela quando a mesma estiver em uma posição em que oconjunto 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 carregadopara 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 ofingerprint do conteúdo da janela nos dados passados pelo sistema, e o índice do inícioda janela é incrementado em 1. Se a quantidade de bytes não processados for menor queo tamanho padrão, é criado um chunk com os dados dentro do buffer e um outro com orestante dos bytes.

55


Por fim, na linha 61 o offset para a carga dos dados no arquivo local é incrementadocom 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 aosjá armazenados, que juntos formam o arquivo local.


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 remotose que serve como base de grande parte dos algoritmos de deduplicação de arquivos. Emseguida, 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 doisalgoritmos que foram implementados no projeto, foi feita uma análise bem detalhadado funcionamento do primeiro deles, que é o algoritmo para deduplicação com cargacompleta do arquivo na memória, o qual utiliza uma técnica muito similar ao Rsync. Foiapresentado um diagrama sobre o algoritmo, e o seu funcionamento explicado. Depois daapresentação do funcionamento, o pseudocódigo de alto nível do algoritmo foi explicadoem detalhes.

Por fim, foi feita a explicação do segundo algoritmo desenvolvido, o algoritmo comdeduplicaçã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 umdiagrama, 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 tempocomo de compressão, para o algoritmo com deduplicação particionada que foi apresentadoneste Capítulo.

56

6Análise de desempenho e compressão

Neste capítulo é demonstrada uma análise do desempenho do Dedupeer integrado como Dedupeer File Storage. Será feita uma análise para identificação do melhor algoritmo dehashing para o sistema e um estudo sobre as taxas de compressão alcançadas dentro de umconjunto de tamanho de chunks para identificar a eficiência da economia proporcionadapelo algoritmo de deduplicação desenvolvido.

Serão feitas avaliações no tempo de armazenamento, deduplicação, deduplicaçãojuntamente com o armazenamento, e reidratação, que é a remontagem do arquivo originalatravés dos chunks armazenados e deduplicados.

6.1 Datasets

Para comparar sistemas de deduplicação de dados diferentes é preciso possuir omesmo conjunto de dados, pois a recriação de datasets a partir da mesma porcentagemde modificação não funcionam com deduplicação. As modificações precisam estarexatamente localizada na mesma posição ou a avaliação será falha, logo, os arquivostestados devem ser os mesmos.

O trabalho [38] trata justamente sobre quais datasets devem ser usados para fazeravaliações em sistemas de deduplicação de dados. Nele foram analisados 33 artigos sobrededuplicação publicados entre os anos de 2000 e 2011 nas mais relevantes conferênciassobre 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 quaisficaram divididos em:

1. Datasets privados, não acessível para qualquer indivíduo;

2. Datasets públicos mas difíceis de serem reproduzidos;

57

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ãopode ser feita uma comparação entre os sistemas analisados nesses artigos e outro que nãopossa ser avaliado com esses dados privados. Os 4 restantes utilizam conjuntos de dadossinteticamente criados os quais não podem ser reproduzidos pois algumas informaçõessobre a sua criação foram omitidos.

Baseado na categorização citada acima, os datasets são: 64 privados (53%), 17 sãopúblicos e difíceis de reproduzir (14%), 11 são sintetizados com detalhes da sua geraçãoomitidos (9%). O que dá um total de 76% de datasets inutilizáveis para comparaçãoentre sistemas. Os 24% que são públicos são considerados muito pequenos para umacomparaçã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 FileStorage foram arquivos de máquinas virtuais e de código-fonte armazenados em umarquivo tar. Para a análise do tempo gasto nas principais operações foram utilizadas asseguintes 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,foran utilizados dados com modificações de conteúdo mais complexas e maiores dos queas obtidas com o Kernel do Linux. Para essa avaliação foram utilizadas duas imagens demáquinas virtuais com Ubuntu 10.12 instalados. Em uma delas o Ubuntu foi instaladosem atualizações, essa é a máquina virtual que será usada como arquivo base paradeduplicação.

A segunda máquina virtual é a primeira máquina com uma atualização. O sistemaoperacional da máquina virtual foi atualizado com todas as atualizações disponíveis até odia 2 de junho de 2013 às 13:17. 356 arquivos foram baixados, totalizando 330,3MB dedados, os quais após a instalação ocuparam 1350MB a mais do que a máquina virtualantes da atualização.

A escolha de dados públicos e de fácil acesso possibilitará futuras comparações comtrabalhos relacionados.

58

6.2. ANÁLISE DE DESEMPENHO UTILIZANDO O CÓDIGO FONTE DO KERNEL DOLINUX

6.2 Análise de desempenho utilizando o código fonte doKernel do Linux

Esta primeira análise será focada no desempenho para deduplicação do Dedupeer, edo armazenamento e reidratação do Dedupeer File Storage. Foram feitas 14 execuçõesde 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 tamanhorecomendado por alguns sistemas de deduplicação, 8KB e 16KB, e o tamanho utilizadono Ustore, o sistema onde o Dedupeer foi implantado, que é 128KB.

O computador utilizado para a execução da análise de desempenho foi um Windows7 Profissional com Service Pack 1 de 32 bits com processador Intel Core 2 Quad Q66002.40GHz e 3,24GB de memória RAM DDR2.

Para a operação de armazenamento foi enviado um arquivo .tar com todo o código-fonte do Kernel do Linux na versão 3.9.8 e o tempo até a conclusão da operaçao foiregistrado. A utilização do formato tar é muito importante para fazer a deduplicação dosarquivos 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 ataxa de compressão obtida com a deduplicação pelo fato do conteúdo dos arquivos seremtransformados, 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 arquivodeduplicado. Para essas operações foi utilizado o arquivo .tar com todo o código fontedo Kernel do Linux na versão posterior à 3.9.8 que estava disponível no site, que foi aversão 3.10-rc7.

Por último, foi registrado o tempo gasto para fazer a reidratação do arquivo dedu-plicado. Todos os dados capturados na avaliação estão disponibilizados no formato doMathematica 91 no apêndice A.2.

Operação de armazenamento

As Figuras 6.1 e 6.2 mostrarão todos os tempos em milissegundos capturados das 14execuções da operação de armazenamento do Dedupeer File Storage para os algoritmosde hashing MD5 e SHA-1 para cada tamanho de chunk analisado, os quais foram para

1http://www.wolfram.com/mathematica/

59


todas as operações: 128KB, 64KB, 32KB, 16KB e 8KB. Os dados foram plotados nográ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áficona Figura 6.3 mostrará o emparelhamento dos dados ordenados entre os algoritmo de

60


hashing usados para cada tamanho de chunk separado. A partir dos gráficos, percebe-seque os tempos para cada operação de armazenamento são similares independente doalgoritmo de hashing utilizado.

Para uma melhor visualização, a comparação do tempo para cada tamanho de chunk

separado está no apêndice A.3.

Figura 6.3 Tempo em milissegundos para as execuções da operação de armazenamento, separadaspor tamanho de chunk

A seguir será feito um teste estatístico para descobrir se a utilização do SHA-1 temo mesmo desempenho do MD5. Como explicado anteriormente, o MD5 é utilizado emalguns dos sistemas que fazem deduplicação de dados, e que apesar da probabilidade decolisão de hashes existir tanto no MD5 como no SHA-1, já se tem registro de colisão dehashes com MD5 mas ainda nenhum registro desse problema com o SHA-1. Se os doisalgoritmos tiverem um desempenho similar ou se o desempenho do SHA-1 for inferior aoMD5 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 oDedupeer File Storage.

Todos os valores de p podem ser encontrados na Tabela 6.1, esse é o valor utilizadopara identificar se os dados capturados seguem a curva normal, e com isso saber qualmétodo estatístico utilizar. Todos os valores vão ser exibidos na tabela para caso alguém

61


p-values 128KB 64KB 32KB 16KB 8KBMD5 0,674511 0,621354 0,198659 0,0330624 0,293449SHA-1 0,903653 0,868695 0,258855 0,44823 0,0219761

Tabela 6.1 p-values para os dados capturados na operação de armazenamento

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 armazena-

mento. O intervalo de confiança adotado para os testes foi de 95% ou seja, caso o valor dep seja maior que o nível de significância, que é 0,05, o T-Test pode ser selecionado, casocontrário, a análise será feita através de um teste não-paramétrico, já que o tamanho daamostra é inferior à 40 e o T-Test só deve ser feito com dados não normais se a amostrativer 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 osdados são normais, o que torna a análise mais fácil. Como hipótese nula, será consideradoque a média de tempo gasto para duas amostras são iguais, e como hipótese alternativaserá considerado que a média de tempo gasto para a operação de armazenamento comMD5 é 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 afirmarque 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 nosGráficos 6.4 e 6.4. Com a análise desses dados é possível avaliar apenas o desempenho doalgoritmo de deduplicação desenvolvido e utilizado no Dedupeeer File Storage, pois osdados registrados nessas execuções foram o tempo necessário para o algoritmo buscar oschunks dentro do arquivo a ser enviado para armazenamento. Logo, os valores plotadosnesse gráfico se referem ao tempo entre o início e o fim da deduplicação apenas, o qualengloba os seguintes passos: a busca da informações dos chunks a serem procurandocomo duplicados dentro do arquivo, a montagem da estrutura de dados para comunicaçãocom a biblioteca através do Thrift, a procura dos chunks dentro do arquivo pela bibliotecaDedupeer, a criação da estrutura de dados com o mapeamento dos chunks e das referências

62


aos chunks duplicados, e o retorno da estrutura através do Thrift para o Dedupeer FileStorage.

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 tamanhode chunk está no apêndice, na seção A.4.

Analisando os dados obtidos das execuções de deduplicação, percebe-se que o algo-ritmo de deduplicação utilizando o SHA-1 obteve um desempenho superior ao mesmo

63


algoritmo utilizando MD5. A média de tempo foi bem significativa, para 128KB o SHA-1obteve uma média de 36553 milissegundos para executar a operação, enquanto que comMD5 o tempo médio foi de 133255 milissegundos. Com chunks de 8KB de tamanho adiferença entre as médias foi menor, o tempo para o MD5 (227582 ms) foi menos de duasvezes maior do que o do SHA-1 (118409 ms).

Apesar da média do tempo ser significativamente maior utilizando MD5 em relação aoSHA-1, é preciso fazer a análise estatística para confirmar se com esses dados é possívelsaber 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, oT-Test emparelhado foi feito para as amostras de 16KB.

Da mesma forma que o teste anterior, como hipótese nula será considerado que amédia de tempo gasto para deduplicação é igual entre as amostras, e como hipótesesalternativa 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 ahipótese alternativa deve ser aceita, é concluído que a média de tempo gasta com MD5para deduplicação é realmente maior do que o tempo gasto com SHA-1, ou seja, para aoperaçã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 aoperação de armazenamento, que representa a operação completa de deduplicação de umarquivo no sistema de armazenamento.

Nesta operação, os dados capturados também apontam uma vantagem significativapara o SHA-1, esses dados podem ser vistos plotados em gráficos separados por algoritmode hashing nas Figuras 6.6 e 6.7. A média do tempo calculado para o SHA-1 utilizandochunks de 128KB foi 36552.9 milissegundos, enquanto a médio do MD5 para 128KB foi249779 milissegundos, ou seja, com o SHA-1 a operação foi em média 6,8 vezes maisrá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,2vezes mais rápido.

Os gráficos emparelhados dessa operação separados por tamanho de chunk tambémestão no Apêndice, especificamente nessa seção A.5.

64


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 alternativaconsiderando 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 aanálise a partir do Wilcoxon signed-rank test. O p-value resultante foi 0,00109705, comisso a hipóteses nula deve ser rejeitada e concluímos que o tempo médio entre eles foidiferente.

Figura 6.6 Tempo em milissegundos das execuções da operação de deduplicação + armazena-

mento, separadas por tamanho de chunk, utilizando SHA-1

65


Figura 6.7 Tempo em milissegundos das execuções da operação de deduplicação + armazena-

mento, 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 dosalgoritmos de hashing SHA-1 e MD5.

Nas operações de deduplicação os resultados foram diferentes das duas operaçõesanteriores, nesta operação o algoritmo de MD5 foi mais rápido do que o SHA-1. Compa-rando as médias do maior e menor tamanho de chunk testado, para o chunk de 128KB otempo médio de execução da operação de reidratação com MD5 foi de 43087 milissegun-dos, enquanto o tempo médio do SHA-1 foi 68590,6 milissegundos. Para o chunk de 8KBo MD5 foi pouco mais de 5 vezes mais rápido, tendo média de 226346 milissegundoscontra 1166748 milissegundos do SHA-1. Todos os dados das execuções dessa operaçãopodem ser vistos nas Figuras 6.8 e 6.9, e os dados emparelhados por tamanho de chunk

estão no Apêndice A.6.

66


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 dehipótese, onde a hipótese nula diz que a média de tempo gasto para a reidratação comMD5 é 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

67


Aplicando o T-Test emparelhado, o p-value foi 6,34527x1010−17. Como o p-value émenor do que 0,05, devemos rejeitar a hipótese nula e aceitar a alternativa. Logo, comoprevisto, é concluído que a média de tempo gasto com MD5 para reidratação é menor doque o tempo gasto com SHA-1, ou seja, para a operação de reidratação o MD5 foi maiseficiente que o SHA-1.

6.2.1 Mapa de chunks deduplicados

Foi desenvolvida uma funcionalidade no Dedupeer File Storage que exibe, em umabarra horizontal, as áreas do arquivo que foram economizadas com a deduplicaçãoaplicada nele. A barra possui duas cores, a azul representa as áreas do arquivo onde oseu conteúdo binário foi salvo no sistema de armazenamento pelo fato de não ter sidoencontrado partes duplicadas já armazenadas, e a área pintada de cinza representa aspartes do arquivo que foram economizadas no armazenamento, os dados pertencentes àessas áreas foram encontrados como já presentes nos chunks armazenados no sistema esó 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ãoproporcionais e a quantidade de chunks do arquivo deduplicado e apresentado na Figura6.10 foi de 66318 na versão de 8KB, chunks deduplicados de forma isoladas podem nãoser exibidos pois a área ocupada por eles pode não ser suficiente para que seja exibida nabarra de modificações.

Como esperado, a deduplicação com chunk de 128KB foi a que menos economizouespaço, já que para que um chunk fosse identificado como duplicado, seria necessárioencontrar 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 foramdeduplicados, o que dá uma economia de aproximadamente 3%. Para 64KB foram

68

6.3. ANÁLISE DE ECONOMIA UTILIZANDO MÁQUINAS VIRTUAIS

Chunks VDI armazenado VDI atualizado deduplicado VDI atualizado armazenado128KB 24337 35571 3513764KB 48674 71280 7027432KB 97347 142498 14054716KB 194694 284218 2810948KB 389387 566985 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 foramdeduplicados, mais de 11% do total. Para 16KB, o arquivo foi dividido em 32995 partesdas quais 8870 foram deduplicados, resultando em 25% de economia. E por fim, prachunks de 8KB, dos 66318 partes, 27989 foram deduplicados, o que acarretou em umaeconomia de 41%.

Como os arquivos de código-fonte são pequenos, geralmente menores do que ostamanhos de chunk adotados, qualquer modificação em um deles faz com que nenhumaparte do mesmo seja deduplicada, por isso, a deduplicação desse tipo de arquivo não étão eficiente.

6.3 Análise de economia utilizando máquinas virtuais

Essa segunda análise foi basicamente para avaliar a economiza que pode ser alcançadaatravé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 eo segundo com o mesmo sistema operacional só que com uma atualização, como descritona seção 6.1.

Primeiramente, o arquivo vdi sem a atualização do Linux, arquivo esse com tamanho3.189.854.208 bytes, foi enviado para o Dedupeer File Storage. Em seguida, foi feita adeduplicaçã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 5tamanho diferentes de chunk: 128KB, 64KB, 32KB, 16KB e 8 KB. Para questões compa-rativas, 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 armazenamentodo mesmo arquivo, se dá porque com a deduplicação podem ser criados vários chunks

com tamanho inferior ao tamanho padrão, enquanto que no armazenamento, o único

69

6.3. ANÁLISE DE ECONOMIA UTILIZANDO MÁQUINAS VIRTUAIS

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 detamanhos variados. A economia alcançada foi de 55% para chunks de 128KB, 60% para64KB, 63% para 32KB, 66% para 16KB e 69% para 8KB. A quantidade de bytes arma-zenados 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çãotinha 3.189.854.208 bytes, e que a diferença entre ele e o arquivo que foi deduplicado é de1.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% para16KB 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 servisto na Figura 6.11. Da mesma forma que o apresentado anteriormente, a cor azulrepresenta as áreas do arquivo onde o seu conteúdo binário foi salvo no sistema e a cinzarepresenta 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

70

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 nosseus computadores para criar um nuvem de dados interna e ter maior controle sobre seusdados.

Ele tem como principal objetivo o backup distribuído de dados e é construído emuma arquitetura peer-to-peer (P2P) híbrida, que são redes peer-to-peer que possuementidades centrais [36]. Como a ideia principal do sistema é a comunicação direta entreos 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 plata-

forma JXTA, que é um conjunto de protocolos utilizado para criar uma rede peer-to-peer

[42].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 é sincroni-zado no sistema, o processo de deduplicação é executado antes dos dados serem enviadospara 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 oferecidomais espaço do que o sistema possui fisicamente, já que os chunks deduplicados não têmseus dados salvos, apenas as referência para os chunks que já estão armazenamentos.


Neste capítulo foram analisados dois testes, um de desempenho e outro de taxa decompressão para máquinas virtuais. No teste de desempenho concluiu-se que para aoperação de armazenamento não se pode afirmar se o tempo médio da operação comMD5 é diferente do tempo com SHA-1. Para deduplicação, o sistema com SHA-1 foimais eficiente que com MD5. Para deduplicação + armazenamento foi confirmado que otempo médio com SHA-1 e MD5 são diferentes, e a observação visual no gráfico ficaclaro que o SHA-1 é mais eficiente nesse caso também. E por último, na operação dereidratação, o sistema com MD5 foi mais eficiente que com SHA-1.

2"http://usto.re"

71


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.

72

7Conclusã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óriaprincipal. O algoritmo foi encapsulado em um componente de software com interfaceThrift, que é uma biblioteca de serialização com linguagem neutra e suporte à diversaslinguagens de programação, para facilitar a integração com sistemas de armazenamentoexistentes. O algoritmo foi desenvolvido com uma funcionalidade de otimização dedescoberta de redundância de dados através da carga extra de dados no processamentoparticionado, o que aumenta a precisão da identificação de redundância mesmo com aquebra do arquivo para ser processado.

Para a avaliação do algoritmo foi desenvolvido o Dedupeer File Storage, um sistemade armazenamento de dados com as mesmas características dos principais sistemas dearmazenamento distribuídos, utilizando a quebra dos arquivos salvos em várias partesmenores, 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 aoCassandra, que é a base de gerenciamento do sistema de armazenamento desenvolvido.O Dedupeer File Storage possui uma interface gráfica com o usuário à qual possibilitao gerenciamento dos arquivos armazenados, através de funcionalidades como backup,deduplicação, reidratação, cálculo de economia, renderização de mapa de chunks ereferências do arquivo e painel de configurações básicas, como tamanho padrão de chunk

e quantidade de chunks carregados pra memória.

7.1 Trabalhos futuros

A fim de promover a utilização do algoritmo de deduplicação particionada ou o sis-tema de armazenamento de dados desenvolvidos, há algumas possibilidades de trabalhos

73

7.1. TRABALHOS FUTUROS

futuros, os quais estão listados abaixo:

• Criar um buffer do mapa dos chunks processados na deduplicação em disco, paraque não haja estouro de memória pelo fato do mapa de chunks ficar maior queo espaço reservado para a memória heap do Java, o que possibilitará fazer adeduplicação de arquivo de qualquer tamanho.

• Comparar os ganhos de desempenho trazidos pela deduplicação particionada emrelação à um algoritmo de deduplicação com carga completa do arquivo para amemória.

• Fazer a análise do impacto de utilizar o Dedupeer File Storage em uma rede P2Pcom vários nós, já que o Cassandra dá suporte nativo à isso e o Dedupeer FileStorage funciona com o Cassandra sendo o gerenciador dos dados armazenados.

• Modificar o Dedupeer File Storage para dar suporte à distribuição de tarefas dededuplicação entre os nós da rede P2P criada a partir da sugestão acima, possi-bilitando a deduplicação de um mesmo arquivo em vários nós, o que aumentariaa velocidade para conclusão da tarefa. Teoricamente o algoritmo já dá suporte àisso, mas o sistema de armazenamento precisa fornecer a distribuição do arquivobase para deduplicação entre os nós que farão o processamento, e também fazer acoordenação dos nós da deduplicação distribuída.

• Utilizar o algoritmo como base para o desenvolvimento de um software de compres-são de dados através de deduplicação, mantendo as informações necessárias paraa reidratação dos dados no mesmo arquivo, com funcionamento independente dosistema de arquivos presente no computador onde o software será executando. Eleteria um funcionamento parecido com o de softwares como o WinRar, 7zip, WinZip,entre outros, mas com a possibilidade de obter maiores ganhos de economia entreversões de um arquivo.

• Analisar ganho de desempenho e economia no Ustore, comparando o sistema coma utilização do Dedupeer como componente de deduplicação e sem ele.

74

Referências Bibliográficas

[1] Developer guide: Overview. Tech. rep., Google.

[2] Jvm serializer wiki. Tech. rep.

[3] AGARWAL, A., SLEE, M., AND KWIATKOWSKI, M. Thrift: Scalable cross-language services implementation. Tech. rep., Facebook, 4 2007.

[4] ALAN, H. Most popular cloud storage provider: Dropbox. Lifehacker.

[5] BHAGWAT, D., ESHGHI, K., LONG, D. D. E., AND LILLIBRIDGE, M. Extremebinning: Scalable, parallel deduplication for chunk-based file backup. In MASCOTS

(2009), IEEE, pp. 1–9.

[6] BONWICK. Zfs deduplication. Tech. rep., 2009. "Disponívelem https://blogs.oracle.com/bonwick/entry/zfs_dedup. Aces-sado em: Agosto/2012".

[7] BRODER, A. Z. Some applications of rabin’s fingerprinting method. In Sequences

II: Methods in Communications, Security, and Computer Science (1993), Springer-Verlag, pp. 143–152.

[8] CAPRIOLO, E. Cassandra High Performance Cookbook. Packt Publishing, Limited,2011.

[9] DECANDIA, G., HASTORUN, D., JAMPANI, M., KAKULAPATI, G., LAKSHMAN,A., PILCHIN, A., SIVASUBRAMANIAN, S., VOSSHALL, P., AND VOGELS, W.Dynamo: amazon’s highly available key-value store. ACM SIGOPS Operating

Systems Review 41, 6 (2007), 205–220.

[10] DÉFAGO, X., URBÁN, P., HAYASHIBARA, N., AND KATAYAMA, T. The ? accrualfailure detector. In RR IS-RR-2004-010, Japan Advanced Institute of Science and

Technology (2004), pp. 66–78.

[11] DUBNICKI, C., GRYZ, L., HELDT, L., KACZMARCZYK, M., KILIAN, W., STR-ZELCZAK, P., SZCZEPKOWSKI, J., UNGUREANU, C., AND WELNICKI, M. Hy-drastor: A scalable secondary storage. In FAST (2009), M. I. Seltzer and R. Wheeler,Eds., USENIX, pp. 197–210.

75

https://blogs.oracle.com/bonwick/entry/zfs_dedup

REFERÊNCIAS BIBLIOGRÁFICAS

[12] FLOYER, D. Epa energy star enterprise storage draft specification june 4 2009.Tech. rep., 2009. "Disponível em http://wikibon.org/wiki/v/EPA_

Energy_Star_Enterprise_Storage_Draft_Specification_

June_4_2009. Acessado em: Abril/2013".

[13] FREEMAN, L. Evolution of the Storage Brain: A history of transformative events,

with a glimpse into the future of data storage. CreateSpace, 2010.

[14] FU, Y., JIANG, H., AND XIAO, N. A scalable inline cluster deduplication fra-mework for big data protection. In Proceedings of the 13th International Middleware

Conference (New York, NY, USA, 2012), Middleware ’12, Springer-Verlag NewYork, Inc., pp. 354–373.

[15] HENSON, V. An analysis of compare-by-hash. In Proceedings of the 9th confe-

rence on Hot Topics in Operating Systems - Volume 9 (Berkeley, CA, USA, 2003),HOTOS’03, USENIX Association, pp. 3–3.

[16] HEWITT, E. Cassandra: The Definitive Guide. O’Reilly Media, 2010.

[17] IBM. Ibm protectier deduplication solutions. Tech. rep.

[18] INSTITUTE, M. G. Big data: The next frontier for innovation, competition, andproductivity. Tech. rep.

[19] KAISER, J., MEISTER, D., BRINKMANN, A., AND EFFERT, S. Design of an exactdata deduplication cluster. In MSST (2012), pp. 1–12.

[20] KAPLAN, J. M., ROY, R., AND SRINIVASARAGHAVAN, R. Mee-ting the demand for data storage. Tech. rep., 2008. "Disponível emhttps://www.mckinseyquarterly.com/Meeting_the_demand_

for_data_storage_2153#. Acessado em: Fevereivo/2012".

[21] KATHPAL, A., JOHN, M., AND MAKKAR, G. Distributed Duplicate Detection inPost-Process Data De-duplication. In High Performance Computing 2011 (2011).

[22] KEMPE, D., KLEINBERG, J., AND DEMERS, A. Spatial gossip and resourcelocation protocols. ACM Press, pp. 163–172.

[23] KENTON. Protocol buffers. Tech. rep., Google.

76

http://wikibon.org/wiki/v/EPA_Energy_Star_Enterprise_Storage_Draft_Specification_June_4_2009



https://www.mckinseyquarterly.com/Meeting_the_demand_for_data_storage_2153#

https://www.mckinseyquarterly.com/Meeting_the_demand_for_data_storage_2153#


[24] LONGORIA, G. Resolving data storage demands with sans. Tech. rep., 2000."Disponível em ftp1.us.dell.com/app/1q00san.pdf. Acessado em: Fe-vereivo/2012".

[25] MANDAGERE, N., ZHOU, P., SMITH, M. A., AND UTTAMCHANDANI, S. Demys-tifying data deduplication. In Middleware (Companion) (2008), F. Douglis, Ed.,ACM, pp. 12–17.

[26] MEISTER, D., AND BRINKMANN, A. dedupv1: Improving deduplication through-put using solid state drives (ssd). In Proceedings of the 2010 IEEE 26th Symposium

on Mass Storage Systems and Technologies (MSST) (Washington, DC, USA, 2010),MSST ’10, IEEE Computer Society, pp. 1–6.

[27] MEISTER, D., KAISER, J., BRINKMANN, A., CORTES, T., KUHN, M., AND

KUNKEL, J. A study on data deduplication in hpc storage systems. In Proceedings

of the International Conference on High Performance Computing, Networking,

Storage and Analysis (Los Alamitos, CA, USA, 2012), SC ’12, IEEE ComputerSociety Press, pp. 7:1–7:11.

[28] OF TECHNOLOGY, R. I. Sha1 description. Rochester Institute of Technology."Acessado em: Julho/2013".

[29] QUINLAN, S., AND DORWARD, S. Awarded best paper! - venti: A new approachto archival data storage. In Proceedings of the 1st USENIX Conference on File and

Storage Technologies (Berkeley, CA, USA, 2002), FAST ’02, USENIX Association.

[30] RABIN, M. Fingerprinting by Random Polynomials. Center for Research inComputing Technology: Center for Research in Computing Technology. Center forResearch in Computing Techn., Aiken Computation Laboratory, Univ., 1981.

[31] RARLAB. Zip file format. "Acessado em: Julho/2013".

[32] RIVEST, R. L. What is the md5 hash? "Acessado em: Julho/2013".

[33] SAYOOD, K. Introduction to Data Compression, second ed. Morgan KaufmannPublishers, San Francisco, CA, USA, 2000.

[34] SCHLOSSNAGLE, T. Scalable Internet Architectures. Sams, 2006.

[35] SCHNEIER, B. When will we see collisions for sha-1? Tech. rep.

77

ftp1.us.dell.com/app/1q00san.pdf


[36] SCHOLLMEIER, R. A definition of peer-to-peer networking for the classificationof peer-to-peer architectures and applications. In Peer-to-Peer Computing, 2001.

Proceedings. First International Conference on (2001), IEEE, pp. 101–102.

[37] SOGHOIAN, C. How dropbox sacrifices user privacy for cost savings. SlightParanoia. "Acessado em: Julho/2013".

[38] TARASOV, V., MUDRANKIT, A., BUIK, W., SHILANE, P., KUENNING, G., AND

ZADOK, E. Generating realistic datasets for deduplication analysis. In Proceedings

of the 2012 USENIX conference on Annual Technical Conference (Berkeley, CA,USA, 2012), USENIX ATC’12, USENIX Association, pp. 24–24.

[39] TARASOV, V., MUDRANKIT, A., BUIK, W., SHILANE, P., KUENNING, G., AND

ZADOK, E. Introduction to storage area networks and system networking. IBM.

[40] TRIDGELL, A., AND MACKERRAS, P. The rsync algorithm. "Disponí-vel em http://cs.anu.edu.au/techreports/1996/TR-CS-96-05.

pdf. Acessado em: Agosto/2012".

[41] VALLECILLO, A., HERNANDEZ, J., AND TROYA, J. M. Component interope-rability. In ECOOP ’99 Reader, number 1743 in LNCS (2000), Springer-Verlag,pp. 1–21.

[42] VERSTRYNGE, J. Practical JXTA II: Cracking the P2P puzzle. DawningStreams,2010.

[43] WEI DONG, FRED DOUGLIS, K. L. H. P. S. R. P. S. Tradeoffs in scalable datarouting for deduplication clusters. Tech. rep.

[44] WU, J., PING, L., GE, X., WANG, Y., AND FU, J. Cloud storage as the infrastruc-ture of cloud computing. In Proceedings of the 2010 International Conference on

Intelligent Computing and Cognitive Informatics (Washington, DC, USA, 2010),ICICCI ’10, IEEE Computer Society, pp. 380–383.

[45] YANG, T., JIANG, H., FENG, D., NIU, Z., ZHOU, K., AND WAN, Y. Debar: Ascalable high-performance de-duplication storage system for backup and archiving.In IPDPS (2010), IEEE, pp. 1–12.

[46] ZHU, B., LI, K., AND PATTERSON, H. Avoiding the disk bottleneck in the datadomain deduplication file system. In Proceedings of the 6th USENIX Conference

78

http://cs.anu.edu.au/techreports/1996/TR-CS-96-05.pdf

http://cs.anu.edu.au/techreports/1996/TR-CS-96-05.pdf


on File and Storage Technologies (Berkeley, CA, USA, 2008), FAST’08, USENIXAssociation, pp. 18:1–18:14.

79

AApêndice

A.1 Arquivo de definição dos serviços Thrift

namespace java com.dedupeer.thrifttypedef i32 inttypedef i32 weakHashtypedef i64 positiontypedef string strongHashtypedef string chunkIDstruct ChunkIDs {

1: optional string fileID,2: required string chunkID,

}typedef map<weakHash,map<strongHash,ChunkIDs» hashesToComparestruct 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 destination10: optional binary content

}

80

A.2. RESULTADOS DA AVALIAÇÃO DOS ARQUIVOS DO CÓDIGO FONTE DOKERNEL DO LINUX

service DeduplicationService { map<position,Chunk> deduplicate(1:hashesToComparechunksInfo, 2:string pathOfFile, 3:int chunkSizeInBytes, 4:int bytesToLoadByTime),}

A.2 Resultados da avaliação dos arquivos do código fontedo Kernel do Linux

Nesta seção estão todas as atribuições de vetores com o tempo em milisegundos das14 execuções para cada tamanho de chunk e algoritmo de hashing utilizadas no WolframMathematica 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,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}

81


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}

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,

82


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}

83

A.3. GRÁFICOS DOS TEMPOS EMPARELHADOS POR TAMANHO DE CHUNKPARA A OPERAÇÃO DE ARMAZENAMENTO

A.3 Gráficos dos tempos emparelhados por tamanho dechunk para a operação de armazenamento

Figura A.1 Tempo emparelhado para a operação de armazenamento com chunks de 128KB


84

A.3. GRÁFICOS DOS TEMPOS EMPARELHADOS POR TAMANHO DE CHUNKPARA A OPERAÇÃO DE ARMAZENAMENTO



85

A.4. GRÁFICOS DOS TEMPOS EMPARELHADOS POR TAMANHO DE CHUNKPARA A OPERAÇÃO DE DEDUPLICAÇÃO


A.4 Gráficos dos tempos emparelhados por tamanho dechunk para a operação de deduplicação

Figura A.6 Tempo emparelhado para a operação de deduplicação com chunks de 128KB

86




87




88

A.5. GRÁFICOS DOS TEMPOS EMPARELHADOS POR TAMANHO DE CHUNKPARA A OPERAÇÃO DE DEDUPLICAÇÃO + ARMAZENAMENTO

A.5 Gráficos dos tempos emparelhados por tamanho dechunk para a operação de deduplicação + armaze-namento

Figura A.11 Tempo emparelhado para a operação de deduplicação + armazenamento com chunks

de 128KB


de 64KB

89

A.5. GRÁFICOS DOS TEMPOS EMPARELHADOS POR TAMANHO DE CHUNKPARA A OPERAÇÃO DE DEDUPLICAÇÃO + ARMAZENAMENTO


de 32KB


de 16KB

90

A.6. GRÁFICOS DOS TEMPOS EMPARELHADOS POR TAMANHO DE CHUNKPARA A OPERAÇÃO DE REIDRATAÇÃO


de 8KB

A.6 Gráficos dos tempos emparelhados por tamanho dechunk para a operação de reidratação

Figura A.16 Tempo emparelhado para a operação de reidratação com chunks de 128KB

91




92




93

Documents

Dedupeer: Deduplicação de Arquivos Através de um Algoritmo de Processamento Particionado