Com as inúmeras fontes de informação existentes na Web, é cada vez mais frequente encararmos uma situação angustiante, onde precisamos de uma informação que sabemos que já esteve diante de nós, no passado recente ou distante, mas não conseguimos localizá-la em tempo hábil.

Este texto apresenta um fluxo de Gestão de Conhecimento Pessoal (do inglês, Personal Knowledge Management – PKM) que pode ser útil para coleta, armazenamento e recuperação mais eficiente da informação. Ferramentas simples e gratuitas também são sugeridas. A proposta procura ser simples, de forma a não burocratizar o processo, garantindo uma flexibilidade e agilidade compatível com a velocidade de informações produzidas na Web.

Diante dos desafios e oportunidades que a distribuição massiva de informação na internet nos impõe, um processo de PKM é essencial para organizar e potencializar a produção de conhecimento.

Figura 1: Mapa mental PKM

Obviamente, o estudo de estruturas externas de dados e de seus impactos só tem sentido em virtude do elevado volume de armazenamento. Caso contrário, se todos os dados pudessem ser carregados em memória primária, as operações se tornariam extremamente eficientes com os algoritmos de ordenação e pesquisa existentes para memória primária, não importando a forma de organização do armazenamento externo. Como isso não é possível, é necessário encontrar formas eficientes, principalmente em termos de desempenho, de se armazenar e recuperar dados nessas estruturas.

A organização de dados em memória externa deve levar em conta as características dos discos rígidos (existem outros dispositivos como fitas magnéticas, discos ópticos, etc.) como tempo de busca (seek), atraso rotacional e tempo de transferência. Devido ao movimento mecânico das cabeças de leitura-gravação (seek), as operações de leitura e gravação são muito mais rápidas quando os dados estão organizados de forma a exigir a menor movimentação possível dessas cabeças. Devido a esse movimento mecânico, nesses dispositivos, as operações de inclusão, alteração, remoção e pesquisa de registros são muito mais caras em termos de desempenho quando comparadas com suas equivalentes em memória RAM.

Dados são organizados em discos na forma de registros, que juntos, compõem arquivos. Existem muitas formas para a organização de registros, cujos campos podem ter tamanhos fixos ou variáveis, sendo que neste último caso usam-se indicadores de tamanho ou delimitadores entre campos. Os registros, por sua vez, podem ser organizados em um arquivo na forma sequencial ou aleatória. Na forma sequencial, um campo do registro, denominado chave de ordenação, determinará a ordem da sequência. Na forma aleatória, não existe ordem predefinida para armazenamento.

Figura 1: Organização de registros em um arquivo sequencial

Operações

Repare, que para um arquivo sequencial, a inclusão de um novo registro implica na localização de sua posição de inserção, a movimentação de todos os registros subsequentes para liberar o espaço e, então, a gravação do novo registro. Todo esse processo é extremamente caro quando realizado em um disco rígido. Se a organização dos registros é aleatória, a inclusão de um novo registro é uma operação extremamente eficiente, pois ela é feita no final do arquivo. Entretanto, a pesquisa se torna ineficiente (n comparações no pior caso) caso não haja uma estrutura de indexação, ou índice.

A figura 2 exibe uma possível organização para um arquivo aleatório onde os registros possuem campos de tamanho variável com indicador de tamanho. Logo em seguida, um trecho de uma possível implementação em C++.

15File Structures12Michael Folk

class Livro {
public:
   char titulo[41];
   char autor[41];
   int writeLen(ostream &);
   int readLen(istream &);
};

int Livro::writeLen(ostream &fout) {
   int n;
   n = strlen(titulo);
   fout.write((char *)&n, sizeof(int));
   fout.write(titulo, n);
   n = strlen(autor);
   fout.write((char *)&n, sizeof(int));
   fout.write(autor, n);
   fout.flush();
   if(fout.fail())
     return false;
   return true;
}

Figura 2: Um exemplo de registro de tamanho variável e implementação em C++

Embora a inclusão seja eficiente nos arquivos aleatórios, a operação de exclusão nestes arquivos não é eficiente, devido à necessidade de movimentação dos registros para reocupar os espaços vazios. Operações de alteração também são complicadas, pois em registros de tamanho variável, elas podem causar uma alteração neste tamanho, o que implica, a princípio, em uma fragmentação dos registros e na necessidade de uma área de extensão no caso de aumento de tamanho. Porém existem alternativas para se garantir o desempenho dessas operações ao custo de maior espaço de armazenamento, como a exclusão lógica destes registros e as operações batch que garantem o rearranjo e consequente compactação da estrutura de dados em momentos de menor carga do sistema. Assim, uma alteração, poderia ser feita com uma exclusão lógica e uma inserção.

Se as operações de inclusão, alteração e exclusão puderem ser tratadas como mencionado anteriormente, elas serão eficientes. Resta então, obter eficiência para uma das operações mais importantes, a pesquisa, afinal de nada adianta armazenar algo que não possa ser recuperado posteriormente. Para a pesquisa, quando os registros possuem tamanho fixo e estão organizados de forma sequencial, algo raro, é possível realizar pesquisa binária em disco, ao custo de log(n) comparações (extremamente eficiente!). Como normalmente os registros possuem tamanho variável para melhor aproveitamento de espaço e são organizados de forma aleatória, é necessário otimizar a operação de pesquisa através da criação de um índice. Os índices geralmente são estruturas bem menores que a estrutura original, de forma a poderem ser carregados em memória primária e manuseados lá com algoritmos extremamente eficientes nesta forma de armazenamento, como QuickSort, Pesquisa Binária e Hashing.

Apesar desses desafios, a organização de registros em baixo nível é muito mais eficiente em termos de desempenho quando comparadas com estruturas de mais alto nível, como banco de dados, que requerem camadas a mais de software para oferecer um nível de abstração maior ao usuário destes dados. Como exemplo, em banco de dados, usa-se uma linguagem de alto nível, como SQL, para manipulação dos dados, enquanto em estruturas de dados como a citada, são usadas operações diretas de leitura e escrita em disco.

Assim, requisitos cada vez mais frequentes no armazenamento de dados, como necessidade elevada de espaço, escalabilidade e desempenho, estão requerendo soluções de estruturas de dados externas baseadas nos princípios já descritos.

Facebook

O Facebook desenvolveu uma estrutura de dados externa para suprir sua necessidade de armazenamento de fotos. Para se ter uma idéia do desafio enfrentado, em números de 2009, o Facebook armazenava 60 bilhões de fotos em 1.5PB de storage, com um crescimento semanal de 25TB, e uma demanda de 550.000 imagens por segundo.

Para garantir a disponibilidade de um sistema de armazenamento de tal dimensão, os engenheiros de sistema do Facebook criaram uma estrutura de dados externa de armazenamento baseada nos conceitos acima. Essa estrutura recebeu o nome de Haystack.

Um artigo sobre a experiência do Facebook na implementação do Haystack pode ser lido aqui.

caleo | Carlos Leonardo S. Mendes

home-page: www.caleo.com.br

Exemplo de mapa mental

Mapa mental é o nome dado para um tipo de diagrama, sistematizado pelo inglês Tony Buzan, voltado para a gestão de informações, de conhecimento e de capital intelectual; para a compreensão e solução de problemas; na memorização e aprendizado; na criação de manuais, livros e palestras; como ferramenta de brainstorming (tempestade de ideias); e no auxílio da gestão estratégica de uma empresa ou negócio. (Wikipedia)

O blog The Mindmapping Software conduziu uma pesquisa com usuários de mapas mentais em 2006 e em 2010. O gráfico abaixo apresenta as principais finalidades para as quais esses usuários utilizam a modelagem de mapas mentais.

Principais áreas de uso dos mapas mentais

Links

Sítios

Software for mindmapping and information organization
Sítio com extensa lista de software para mapas mentais e organização da informação.
http://www.mind-mapping.org/

100 Powerful Web Tools to Organize Your Thoughts and Ideas
http://www.online-college-blog.com/index.php/tips-and-tools/100-powerful-web-tools-to-organize-your-thoughts-and-ideas/

Mind Mapping Software User Survey
The Mindmapping Software Blog, Março de 2010.
http://mindmappingsoftwareblog.com/mmsb/wp-content/uploads/2010/04/2010_MMS_Survey_Results.pdf

Ferramentas livres (desktop)

XMIND
http://www.xmind.net/

FreeMind
http://freemind.sourceforge.net/wiki/index.php/Main_Page

Compendium
http://compendium.open.ac.uk/institute/index.htm

Ferramentas comerciais

MindManager
http://www.mindjet.com/products/mindmanager-8-win/overview

XMIND Pro
http://www.xmind.net/

Ferramentas on-line

MindMeister
http://www.mindmeister.com

Bubbl.us
http://www.bubbl.us/

Mind42
http://www.mind42.com/

caleo | Carlos Leonardo S. Mendes

home-page: www.caleo.com.br

Aplicações que armazenam informações que necessitam de garantia de privacidade e integridade no domínio do banco de dados Oracle podem se beneficiar das funcionalidades Advanced Security e Database Vault. Ambas são options da versão Enterprise Edition e garantem, entre outros recursos, a criptografia transparente de dados e a restrição do DBA ao papel de administrador de infra-estrutura do banco, sem acesso aos dados. Juntamente com a autenticação e autorização através de um serviço de diretórios LDAP, estabelecem um ambiente extremamente seguro para informações de missão crítica.

Porém uma solução completa de segurança precisa tratar um cenário comum nas empresas: a existência de uma conta de serviço responsável por estabelecer o pool de conexões com o BD. As credenciais de acesso (usuário e senha) geralmente estão armazenadas de forma ‘limpa’ em um arquivo de configuração, visível para o administrador do servidor de aplicação. Essa conta, com acessos privilegiados, amplia os limites de acesso ao banco além dos domínios do DBA.

Os links a seguir auxiliam na escolha de soluções e na configuração de um ambiente Oracle seguro com conexões JDBC.

Links

Oracle Database Vault FAQ
http://www.oracle.com/technology/deploy/security/database-security/database-vault/dbv_faq.html

Oracle Transparent Data Encryption (TDE) FAQ
http://www.oracle.com/technology/deploy/security/database-security/transparent-data-encryption/tde_faq.html

JDBC Client-Side Security Features
http://download.oracle.com/docs/cd/E11882_01/java.112/e10589/clntsec.htm

Oracle® Containers for J2EE Security Guide
http://download-west.oracle.com/docs/cd/B25221_04/web.1013/b14429/intro.htm

How to use JAZN LDAP for authentication and authorization
http://www.oracle.com/technology/sample_code/tech/java/codesnippet/security/jaznldap/index.html

Directory Services Integration with Database Enterprise User Security
http://www.oracle.com/products/middleware/identity-management/docs/directory-services-integration-whitepaper.pdf

Tomcat DataSource password encryption
http://bikedreamer.blogspot.com/2009/11/aaa-int-z-0-bbb.html

Database Security Features Using Java
http://databasesecurity.at22.summaries.projetosc.com.br/databasesecurityfeaturesusingjava/

Jasypt (Java simplified encryption) – Encrypting application configuration files
http://www.jasypt.org/encrypting-configuration.html

caleo | Carlos Leonardo S. Mendes

home-page: www.caleo.com.br

Continuous Integration is a software development practice where members of a team integrate their work frequently…

Martin Fowler

Segundo Pressman, “SCM é um conjunto de atividades projetadas para controlar as mudanças inerentes ao desenvolvimento de software. Isso é obtido:

• identificando os produtos do trabalho;
• estabelecendo o relacionamento entre eles;
• definindo o mecanismo para o gerenciamento de diferentes versões desses produtos;
• controlando as mudanças impostas e relatando e auditando as mudanças realizadas.”

SCM é um processo da área de Suporte ao Serviço no ITIL e um processo chave do nível 2 do CMMI. No MPS.BR, é um processo de apoio do nível F.

Sítios

The Configuration Management Resource Guide
http://www.cmpic.com/cmresourceguide.htm

Artigos e Notas

Many teams find that this approach leads to significantly reduced integration problems and allows a team to develop cohesive software more rapidly.

Martin Fowler

Parallel Development Strategies for Software Configuration Management
http://www.methodsandtools.com/archive/archive.php?id=12

High-level Best Practices in Software Configuration Management
http://www.perforce.com/perforce/papers/bestpractices.html

Software Configuration Management for the Web
http://www.methodsandtools.com/archive/archive.php?id=3

Distributed Version Control Systems: A Not-So-Quick Guide Through
http://www.infoq.com/articles/dvcs-guide

Continuous Integration and Enterprise Build Automation
http://www.cmcrossroads.com/cm-journal-articles/12525-continuous-integration-and-enterprise-build-automation

System Configurations + Code Revisions = Continuous Integration FTW!
http://www.agileweboperations.com/system-configurations-code-revisions-continuous-integration-ftw/

Continuous integration with Hudson
http://www.javaworld.com/javaworld/jw-12-2008/jw-12-hudson-ci.html

Continuous Integration
http://www.martinfowler.com/articles/continuousIntegration.html

Configuration Management and ISO 9001
http://www.ssqc.com/do25v6new.pdf

Lista de softwares

Change and Configuration Management Tools
http://www.cmcrossroads.com/cgi-bin/cmwiki/view/CM/CmTools

caleo | Carlos Leonardo S. Mendes

home-page: www.caleo.com.br

Atenção:

1. Você só terá acesso a wave deste post se tiver conta no Google Wave.
2. Se já estiver logado no Google (e atender ao requisito 1), você verá a Wave a seguir. E sendo uma wave pública poderá acessá-la em modo leitura sem ser um participante dela. Se for um participante dela, poderá interagir com a wave, modificando-a.

Integrando uma Wave no blog

1. Crie uma wave e a torne pública se desejar que qualquer um tenha acesso a ela. Lembre-se que ‘qualquer um’ refere-se a qualquer usuário com conta no Google Wave.
2. Adicione o robô embeddy@appspot.com
3. Copie a primeira parte de código HTML gerada pelo robô para o local da página onde você deseja exibir a wave.
4. Insira o script gerado pelo robô no fim de sua página HTML.

Veja o resultado abaixo, onde inseri uma Wave Pública.

Wave:

caleo | Carlos Leonardo S. Mendes

home-page: www.caleo.com.br

Pois o Google realmente me surpreende. Além dos tradicionais e bem conhecidos serviços, o Google possui ainda uma gama enorme de interessantes produtos, talvez ainda não tão conhecidos. Abaixo estão alguns deles que não se esgotam nesta lista.

Google Audio Indexing: Gaudi é uma nova tecnologia do Google que permite aos usuários pesquisar e ver vídeos de diversos canais do YouTube usando tecnologia de fala para encontrar palavras ditas dentro de vídeos. Permite que o usuário salte para a parte direta do vídeo em que estas palavras são ditas.
O foco atual é nas falas de políticos. É possível, por exemplo, verificar quando os políticos americanos mencionaram ‘brazil’ em suas falas.

Google Movies: Permite pesquisar e exibir os filmes em exibição na sua regição com sinopse, cinemas e horários.

Google Discover Music: Pesquisa por artistas, albuns, canções e letras.

Google Image Swirl: Nova forma de pesquisa de imagens no Google. Ainda está no Google Labs, mas dá para ver que o resultado é muito mais organizado e categorizado do que a pesquisa feita pelo Google Images. Compare! É interessante também a tentativa de associação de imagens a partir da segunda tela, com uma interface muito mais intuitiva para uma busca por imagens.

Google Sky: Veja a disposição dos astros no espaço e fotos do Telescópio Huble. Procure por galáxias, planetas e estrelas.

Google Moon: Pesquise a superfície da lua de forma semelhante ao que se faz no Google Earth. Veja os locais de pouso das missões Apollo.

Google Mars: Veja a superfície de Marte.

Google Squared: É uma ferramenta que auxilia a construir uma coleção de fatos a partir de uma pesquisa na Web. Teste, por exemplo, a pesquisa ‘brazilian presidents’. O resultado pode ser exportado para um arquivo CSV ou planilha do Google.

In Quotes: Realiza pesquisa em falas de famosos. Para pesquisar em personalidades de outros países (não EUA), é necessário alterar a edição no canto superior direito. Com a opção ‘Custom’, é possível pesquisar por falas do presidente Lula (as que conseguiram traduzir para o inglês, claro)

Google Code Search: Pesquisa por código fonte que seja público. Muito bom para alunos desesperados para entregar trabalho e muito útil para professores verificarem de onde veio aquele código que nada se parece com seu ‘autor’.

Google Fast Flip: Procure nos principais periódicos do mundo com um resultado em formato de folhetim.

Google Social Search: Veja como habilitar o Google Social Search e realize pesquisas nas principais redes sociais. Veja como você é indexado pelo Google (o grande irmão).

Google City Tours: Indique uma região e cidade (semelhante ao Google Maps) e o Google City Tours irá sugerir um roteiro diário para turistas. Precisa melhorar bastante.

Google Similar Images: Ao invés de pesquisar uma imagem por palavras, pesquise utilizando um imagem como chave de pesquisa. Primeiramente, você faz uma pesquisa comum (com palavras) e partir das imagens retornadas, você pode pesquisar imagens similares. Senti falta da possibilidade de fornecer uma imagem como referência como outras ferramentas semelhantes já permitem.

Google Data Liberation: Precisa migrar seus dados para entrar ou sair das ferramentas do Google? Este site pode lhe ajudar.

Federated Login: Se você não tem idéia do que seja isso, consulte meu post aqui.

Google Maps Transit: Já conhecido no Google Maps, este endereço serve como entrada para uma pesquisa direta por transporte público.

Google Accounts: Em lugar só, você pode verificar todos os seus serviços habilitados no Google e alterar algumas de suas configurações.

Google Web History: Confira seu histórico de acesso à Web, suas pesquisas, resultados mais relevantes e tendências da sua atividade na Web.

Google Voice: O Google Voice é um serviço para expandir os recursos do seu telefone. O serviço permite acessar uma caixa de voz na internet, ler transcrições automáticas de recados da caixa de voz, criar saudações personalizadas e realizar ligações internacionais a baixo custo. Infelizmente ainda não está disponível no Brasil, mas é promissor.

Google goog-411: Pena que este serviço não está disponível no Brasil. Quem sabe um dia…

Google Foundation: Os fundadores do Google criaram um Google sem fins lucrativos. Um projeto interessante é o Google PowerMeter (http://www.google.org/powermeter/)

Outros:

• Google Finance
• Google Twitter Directory
• Conversão de moedas
• Google Custom Search
• Google Insights para pesquisa
• Google Web Elements
• Google Webmaster Central
• Google Fusion Tables

caleo | Carlos Leonardo S. Mendes

home-page: www.caleo.com.br

O Google lançou recentemente a versão denominada preview do Google Wave. Dizem que a demanda repassada ao time australiano responsável pelo novo produto foi algo do tipo: “imaginem que o e-mail nunca existiu e vocês devem criá-lo agora”.

O objetivo seria provocar uma mudança de paradigma, uma ruptura com os padrões atuais e a criação de algo realmente novo. Não diria que o Google Wave é uma quebra de paradigma, aliás na TI tenho visto muito pouca coisa nova, mas na verdade idéias inteligentes para aproveitar conceitos antigos com uma roupagem moderna, aproveitando-se das tecnologias atuais.

Para exemplificar o que eu digo, recentemente a Computer World publicou uma lista de 10 tecnologias corporativas que mais se destacaram em 2009. Destas, eu me dei a liberdade de destacar 3: bancos de dados NoSQL, Deduplication e Virtualização. Todas utilizam conceitos antigos e bem fundamentados na TI.

O Twitter talvez seja a melhor referência disso. Vale hoje algo em torno de 1 bilhão de dólares, graças a uma grande e simples idéia e não a uma grande e nova tecnologia. As idéias mais brilhantes têm uma simplicidade inerente e inquietante (por que eu não tive essa idéia??).

Bem, voltando ao Google Wave, recentemente convidei o Antônio Marcos (Marquinhos), um colega de trabalho, para experimentar a onda. Marquinhos é um profissional que respeito muito porque não tem uma visão enlatada da TI, tão comum nos profissionais da área. E é profissional das antigas (dinossauro), então tem experiência demais.

Por que James Gosling e Niklaus Wirth ilustram este post? Primeiro porque são cientistas realmente representativos de inovações tecnológicas. James Gosling projetou a linguagem Java e Niklaus Wirth o Pascal, Algol e Modula, além de ser uma referência na área de algoritmos e estruturas de dados. Segundo, e razão principal, porque o Marquinhos fisionomicamente é a mistura dos dois.

Sumariamente, para quem ainda não entrou no Google Wave, lá você cria um tópico qualquer (onda), convida outros para participar e estes, por sua vez, também podem convidar mais gente. Qualquer coisa que você escreve pode ser alterada, incrementada ou até mesmo removida por qualquer participante (pelo menos na versão atual). É aparentemente um caos.

Pois neste caos aparente, Marquinhos ao entrar no Google Wave foi logo criando uma onda para defini-lo. Interessante sua visão que reproduzo muito sucintamente:

• 1ª fase: (fase do seguimento)

O indivíduo segue o grupo para entender como cada participante contribui para o todo. Ele quer ser mais um neurônio.

• 2ª fase: (fase do raciocínio em conjunto)

O indivíduo raciocina em conjunto. Como um neurônio, cada um trabalha uma parte e complementa o pensamento alheio, contribuindo para a construção de um pensamento coletivo. É preciso se treinar para pensar conjuntamente.

“O processo de definir quem é o cérebro não tem importancia neste contexto, um neurônio ou uma pessoa não faz difereça neste contexto, o que faz a diferença é a participação de cada neurônio ou pessoa na decisão que vai ser tomada ou adquirida, porque sempre a gente toma uma decisão ou adquire um conhecimento ou bem.

Os jogos de continuidade podem ser um bom treinamento para a wave, pois a geração Y é familiarizada com este jogo. Nos jogos de continuidade uma palavra ou sentido continua com o jogador seguinte. Na wave, com o neurônio seguinte.”

Achou confuso? Não se apegue a conceitos pre-estabelecidos, mude a sua referência e seremos capazes de pensar diferente. Temos um novo paradigma?

caleo | Carlos Leonardo S. Mendes

home-page: www.caleo.com.br

This issue affected thousand of users around the world who use Feedburner features like BuzzBoost to publicize the feeds built on Yahoo Pipes.

The only official response that I have found around the Internet came from Yahoo on this thread by Paul from Pipes Team. As noted, this is a big issue since Google has moved Feedburner to a global infrastructure and Yahoo Pipes uses IP whitelist to allow a higher intensive use of the service. Feedburner team provided Yahoo with an IP range to whitelist that has about ~500,000 IPs.

Yes, I have also got the winner ticket and the feeds on my site (www.caleo.com.br) were affected.

My solution: As my post on the Yahoo thread, I suggest to use feed.informer.com as an intermediate between Yahoo Pipes and Feedburner. Create feeds in feed.informer.com, point them to Yahoo Pipes, then point Feedburner to feed.informer.com.

This is a provisory solution until the big players, Feedburner and Yahoo, return to shake hands.

It worked for me without any modifications on my sites!!

Good luck!

caleo | Carlos Leonardo S. Mendes

home-page: www.caleo.com.br

• Parte 1: A técnica de deduplicação e o uso de hashing
• Parte 2: Funções hashing e as conseqüências da colisão na deduplicação
• Parte 3: Probabilidades de perda de dados e como são tratadas

Parte 3: Probabilidades de perda de dados e como são tratadas

Nesta última parte do artigo, aprofundarei nos cálculos de probabilidade de colisão da deduplicação por hashing.

Hashing e a probabilidade de colisão

A princípio, considerando um hash de 160 bits, parece-nos que a probabilidade de uma colisão é de

Isto porque qualquer bloco pode receber um número hash no espaço de endereçamento de tamanho

Sendo assim, a probabilidade de quaisquer dois blocos receberem o mesmo número hash é

Mas essa conta está certa para dois blocos, não para vários blocos. Na verdade, quanto maior o número de blocos a serem deduplicados, maior é a probabilidade de colisão. Isso se explica pelo paradoxo do aniversário.

O paradoxo do aniversário

Qual é a probabilidade de que 2 pessoas quaisquer façam aniversário no mesmo dia? Desconsiderando anos bissextos, a probabilidade é de 1/365, pois este é o “espaço de endereçamento” (o cálculo é análogo à probabilidade de dois blocos colidirem em um hash de 160 bits).

Mas, qual é a probabilidade de que duas pessoas em uma sala com várias pessoas façam aniversário no mesmo dia? Basta uma sala com 23 pessoas para que essa probabilidade alcance 50%. Com 57 pessoas, essa probabilidade é de 99%!

Existe uma sutil diferença entre as duas perguntas que nos permite entender a diferença. Na primeira, escolhemos 2 pessoas para comparar e encontrar a resposta. Na segunda, testamos cada pessoa com as outras 22 possibilidades para obter o resultado final.

Para compreender melhor o paradoxo do aniversário, consulte aqui. Aplicando a lógica do paradoxo do aniversário na deduplicação por hash, a probabilidade de que uma empresa tenha uma colisão no seu ambiente cresce com o volume de dados. Para compreendermos isso, basta pensarmos nos blocos de dados como pessoas em uma sala.

Os cálculos

Se a probabilidade de colisão cresce a cada novo bloco de dados adicionado, quão grande um sistema de armazenamento a ser deduplicado pode ser antes que a probabilidade de colisão se torne inaceitável?

Aplicando a fórmula do paradoxo do aniversário em uma planilha Excel para simulação encontramos o primeiro problema: o Excel realiza cálculos com no máximo 30 casas decimais. Assim, considerando um hash de 160 bits (ex.: SHA-1), para que algum número diferente de zero apareça na probabilidade de colisão, são necessários

blocos (~72 quadrilhões) de dados. Isso representa 530EB em blocos de 8KB ou 1.1ZB em blocos de 16KB. Para cenários assim, a probabilidade de colisão é de 0.000000000000177635683940025000%, ou aproximadamente

Partindo para soluções programáticas com maior precisão decimal, é possível obter valores diferentes de zero com 12.8 quadrilhões de blocos de dados. Neste caso, tem-se uma probabilidade de colisão de 0.00000000000001110223024625156540423631668090820313% ou

Para se ter este número de blocos de dados são necessários 95EB em blocos de 8KB ou 190EB com blocos de 16KB.

Comparativamente, a probabilidade de se ter um bit errado não detectado a cada vez que se escreve em uma fita LTO é de

Conclusão

Considerando um sistema de deduplicação que trabalhe com menores blocos de dados (pior caso) e que se tenha um volume de armazenamento de 95 Exabytes (quem tem??), a probabilidade de se ter uma colisão é ligeiramente maior que a probabilidade de ocorrer um bit trocado e não detectado na escrita de uma fita LTO. Em outras palavras, neste cenário, a probabilidade de se perder um bloco de informação na deduplicação é de 0.00000000000001110223024625156540423631668090820313%. Além disto, ocorrendo esta perda, o problema somente se efetivará se houver um restore que necessite deste bloco em particular.

O que se conclui é que na deduplicação por hashing existe a probabilidade de perda de dados, ainda que esta esteja em níveis comparáveis às probabilidades de perda de dados inerentes aos próprios dispositivos de armazenamento.

É muito comum encontrar representantes dos fornecedores de soluções de deduplicação por hashing afirmarem que a sua solução garante não haver perda de dados. Quando perguntados como eles tratam a questão da colisão, normalmente há um embaraço na explicação e argumentos confusos que não chegam a uma explicação coerente. A colisão é inerente ao hashing e talvez fosse mais simples estes representantes estudarem o assunto a fundo e reconhecerem o problema da colisão, fornecendo ao cliente números que o tranqüilizem quanto à probabilidade de perda de dados.

caleo | Carlos Leonardo S. Mendes

home-page: www.caleo.com.br