Cientistas encontram equilíbrio ideal entre armazenamento de dados e tempo | Revista Quanta

Há cerca de 70 anos, um engenheiro da IBM chamado Hans Peter Luhn mudou discretamente o curso da ciência da computação. Luhn já detinha várias patentes, incluindo uma para um dispositivo que podia medir a contagem de fios de um pano e outra para um guia que determinava quais bebidas misturadas você poderia fazer com os ingredientes da sua cozinha. Mas num artigo interno da IBM de 1953, ele propôs uma nova técnica para armazenar e recuperar informações que agora está incorporada em quase todos os sistemas computacionais: a tabela hash.

As tabelas hash são uma classe importante de estruturas de dados. Eles oferecem um método especialmente conveniente para acessar e alterar informações em bancos de dados enormes. Mas esta tecnologia traz consigo uma compensação inevitável.

Em um 1957 papel publicado no Jornal de Pesquisa e Desenvolvimento da IBM, W. Wesley Peterson identificou o principal desafio técnico que as tabelas hash representam: elas precisam ser rápidas, o que significa que podem recuperar rapidamente as informações necessárias. Mas também precisam ser compactos, utilizando o mínimo de memória possível. Estes objectivos duplos estão fundamentalmente em desacordo. Acessar e modificar um banco de dados pode ser feito mais rapidamente quando a tabela hash tiver mais memória; e as operações ficam mais lentas em tabelas hash que usam menos espaço. Desde que Peterson apresentou este desafio, os investigadores têm tentado encontrar o melhor equilíbrio entre tempo e espaço.

Os cientistas da computação provaram agora matematicamente que encontraram a solução ideal. A solução veio de um par de recente papéis que se complementavam. “Esses artigos resolvem a questão aberta de longa data sobre as melhores compensações espaço-tempo possíveis, produzindo resultados profundamente surpreendentes que espero que tenham um impacto significativo nos próximos anos”, disse Michael Mitzenmacher, um cientista da computação da Universidade de Harvard que não esteve envolvido em nenhum dos estudos.

“Eu definitivamente diria que é um grande negócio”, acrescentou Rasmus Pagh, cientista da computação da Universidade de Copenhague. “Muitas pessoas trabalharam nesse problema, tentando ver quanto espaço é possível e, ao mesmo tempo, ter operações eficientes em termos de tempo. Este é o que eu adoraria resolver.

Fazendo uma confusão com isso

As tabelas hash estão entre as estruturas de dados mais antigas, simples, rápidas e amplamente utilizadas atualmente. Eles foram projetados para realizar três operações básicas: inserções, que adicionam novos itens ao banco de dados; consultas, que acessam um item ou verificam se ele existe; e exclusões. Uma tabela hash pode ser efêmera – existindo apenas enquanto um programa específico for executado – ou pode ser uma parte permanente do sistema operacional do seu computador. Um navegador da web como o Chrome ou Safari pode ter várias tabelas hash integradas destinadas a rastrear diferentes tipos de dados.

As entradas em uma tabela hash são armazenadas como pares, com o item – a própria informação – conectado a uma chave que identifica a informação. Insira uma chave no algoritmo de consulta de uma tabela hash e ela o levará diretamente ao item. Isso pode não parecer tão extraordinário, mas para bancos de dados enormes pode economizar muito tempo.

Para dar um exemplo extremamente simplificado, considere o Oxford English Dictionary, que possui definições para mais de 600,000 palavras. Se uma edição digital depende de uma tabela hash, você pode simplesmente usar uma determinada palavra como chave e prosseguir direto para a definição. Sem uma tabela hash, o dicionário provavelmente dependeria de um mecanismo de busca muito mais lento, usando um processo de eliminação para eventualmente convergir para a definição solicitada. E embora uma tabela hash possa encontrar qualquer palavra em um período de tempo constante (geralmente uma pequena fração de segundo), o tempo de busca por outros métodos pode aumentar à medida que o número de palavras no dicionário aumenta. Uma tabela hash também oferece outra vantagem: ela pode manter o dicionário dinâmico, facilitando a inserção de novas palavras e a exclusão de palavras desatualizadas.

Os pesquisadores passaram décadas construindo tabelas hash que tentam maximizar a velocidade e minimizar a memória. No século XX, as soluções tendiam a oferecer ganhos significativos em apenas um aspecto, no tempo ou no espaço. Então, em 20, pesquisadores mostrou que era teoricamente possível dar um grande salto de eficiência simultaneamente no tempo e no espaço. Contudo, seriam necessárias mais duas décadas para que os investigadores descobrissem o equilíbrio ideal entre os dois.

A confusão de dados

O primeiro grande passo em direção a esse objetivo ocorreu em 2022, em um momento grande conferência de ciência da computação em Roma. Lá, uma equipe propôs uma tabela hash com novos recursos que poderiam oferecer a melhor combinação de eficiência de tempo e espaço já concebida. O primeiro autor do artigo (listado em ordem alfabética) foi Michael Bender, da Stony Brook University, por isso é comumente referido como Bender et al. tabela hash. Embora a equipe não tenha tentado construir uma tabela hash funcional, eles provaram que ela poderia, em princípio, ser construída com os recursos descritos.

Para avaliar a tabela hash que criaram, o grupo produziu uma curva de trade-off – um gráfico que representa o tempo por operação (inserção ou exclusão) em um eixo e o espaço ocupado pela memória no outro. Mas este gráfico define o espaço de uma maneira especial: devido à forma como são construídas, as tabelas hash precisam de mais memória do que apenas o mínimo necessário para armazenar um determinado conjunto de itens. Os cientistas da computação chamam esse espaço extra de “bits desperdiçados”, embora não sejam realmente desperdiçados e sejam, até certo ponto, necessários. O eixo espacial em uma curva de compensação mede o número de bits desperdiçados por chave.

Ao analisar uma curva de compensação, os pesquisadores podem descobrir o tempo mais rápido possível para uma tabela hash que usa uma determinada quantidade de espaço. Eles também podem inverter a questão para descobrir o menor espaço possível para um determinado tempo de operação. Normalmente, uma pequena mudança em uma variável levará a uma pequena mudança na outra, disse William Kuszmaul, um cientista da computação teórico em Harvard e coautor do artigo de 2022. “Se você dobrar o tempo, talvez reduza pela metade o número de bits desperdiçados por chave.”

Mas esse não é o caso da tabela hash que eles criaram. “Se você aumentar um pouco o tempo, os bits desperdiçados por chave diminuirão exponencialmente”, disse Kuszmaul. A curva de trade-off era tão íngreme que estava literalmente fora de cogitação.

A equipe construiu sua tabela hash em duas partes. Eles tinham uma estrutura de dados primária, na qual os itens são armazenados sem nenhum desperdício de bits, e uma estrutura de dados secundária, que ajuda uma solicitação de consulta a encontrar o item que está procurando. Embora o grupo não tenha inventado a noção de estrutura de dados secundária, eles fizeram uma descoberta crucial que tornou possível sua tabela hash hipereficiente: a eficiência geral da memória da estrutura depende de como a estrutura primária organiza seus itens armazenados.

A ideia básica é que cada item na estrutura primária tenha locais de armazenamento preferenciais – um melhor local, um segundo melhor, um terceiro melhor e assim por diante. Se um item estiver em sua melhor posição, o número 1 será afixado nele e esse número será armazenado na estrutura de dados secundária. Em resposta a uma consulta, a estrutura secundária fornece apenas o número 1, que indica a localização exata do item na estrutura primária.

Se o item estiver na centésima melhor posição, a estrutura de dados secundária anexa o número 100. E como o sistema usa binário, ele representa o número 100 como 100. É necessário mais memória, é claro, para armazenar o número 1100100 do que 1100100 — o número atribuído a um item quando ele está na melhor posição. Diferenças como essa tornam-se significativas se você armazena, digamos, um milhão de itens.

Assim, a equipe percebeu que, se você deslocasse continuamente os itens da estrutura de dados primária para seus locais preferidos, poderia reduzir significativamente a memória consumida pela estrutura secundária sem precisar aumentar o tempo de consulta.

“Antes deste trabalho, ninguém havia percebido que era possível comprimir ainda mais a estrutura de dados movendo informações”, disse Pagh. “Esse foi o grande insight do artigo de Bender.”

Os autores mostraram que sua invenção estabeleceu um novo limite superior para as tabelas hash mais eficientes, o que significa que era a melhor estrutura de dados já desenvolvida em termos de eficiência de tempo e espaço. Mas permanecia a possibilidade de que alguém pudesse fazer ainda melhor.

Obrigado ao sucesso

No ano seguinte, uma equipe liderada por Huacheng Yu, um cientista da computação da Universidade de Princeton, tentou melhorar a tabela hash da equipe Bender. “Trabalhamos muito e não conseguimos”, disse Renfei Zhou, estudante da Universidade Tsinghua em Pequim e membro da equipe de Yu. “Foi então que suspeitámos que o seu limite superior era [também] um limite inferior” – o melhor que pode ser alcançado. “Quando o limite superior é igual ao limite inferior, o jogo termina e você tem sua resposta.” Não importa o quão inteligente você seja, nenhuma tabela hash pode fazer melhor.

A equipe de Yu empregou uma nova estratégia para descobrir se esse palpite estava correto, calculando um limite inferior a partir dos primeiros princípios. Primeiro, eles raciocinaram que para realizar uma inserção ou exclusão, uma tabela hash – ou, na verdade, qualquer estrutura de dados – deve acessar a memória do computador um certo número de vezes. Se eles conseguissem descobrir o número mínimo de vezes necessário para uma tabela hash com espaço eficiente, poderiam multiplicar isso pelo tempo necessário por acesso (uma constante), dando-lhes um limite inferior no tempo de execução.

Mas se eles não soubessem nada sobre a tabela hash (exceto que ela economizava espaço), como os pesquisadores poderiam descobrir o número mínimo de vezes necessário para acessar a memória? Eles a derivaram puramente da teoria, usando um campo aparentemente não relacionado chamado teoria da complexidade da comunicação, que estuda quantos bits são necessários para transmitir informações entre duas partes. Eventualmente, a equipe conseguiu: eles descobriram quantas vezes uma estrutura de dados deve acessar sua memória por operação.

Esta foi a sua principal conquista. Eles foram então capazes de estabelecer um limite inferior no tempo de execução para qualquer tabela hash com uso eficiente de espaço. E eles viram que correspondia exatamente à tabela hash do Bender. “Pensámos que [a princípio] poderia ser melhorado”, disse Zhou. “Acontece que estávamos errados.” Isso, por sua vez, significava que o problema de Peterson finalmente havia sido resolvido.

Além de responder à questão de décadas, disse Kuszmaul, o que é surpreendente sobre a prova de Yu é a sua generalidade. “Seu limite inferior se aplica a todas as estruturas de dados possíveis, incluindo aquelas que ainda não foram inventadas.” Isso significa que nenhum método de armazenamento de dados pode superar a tabela hash Bender em termos de memória e velocidade.

Hashing para o futuro

Apesar da eficiência sem precedentes da nova tabela hash, é provável que ninguém tente construí-la tão cedo. É muito complicado de construir. “Um algoritmo que é rápido na teoria não é necessariamente rápido na prática”, disse Zhou.

Não é incomum que tais lacunas entre teoria e prática persistam por muito tempo, disse Kuszmaul, porque os teóricos tendem a ignorar fatores constantes. O tempo necessário para realizar uma operação é normalmente multiplicado por um número, alguma constante cujo valor exato pode ser irrelevante do ponto de vista teórico. “Mas, na prática, as constantes realmente importam”, disse ele. “No mundo real, um fator de 10 é o fim do jogo.”

As tabelas hash reais ainda estão melhorando materialmente, mesmo que estejam muito aquém do ideal teórico. Por exemplo, uma nova tabela hash chamada IcebergHT, construído por Bender, Kuszmaul e outros, é muito melhor que seus antecessores. De acordo com Kuszmaul, é duas vezes mais rápido que a tabela hash com maior eficiência de espaço disponível atualmente e usa três vezes menos espaço que a tabela hash mais rápida.

Mitzenmacher espera que o resultado de 2023 possa em breve produzir outro tipo de benefício: “Sempre que você obtém um novo limite inferior – especialmente um que envolve algumas técnicas novas – há sempre esperança de que você possa usá-los… para problemas relacionados”.

Há também a satisfação intelectual de saber que você resolveu um problema difícil e antigo, disse o cientista da computação. Piotr Indyk do Instituto de Tecnologia de Massachusetts. “Quando você tiver certeza de que certas estruturas de dados não podem ser melhoradas, isso pode ajudar a concentrar o esforço de pesquisa.” Finalmente, os pesquisadores de dados podem desviar sua atenção do desafio de Peterson e focar em novos problemas na ciência da computação teórica, que não faltam.