HyperLogLog é quase magia.

Alguns dias atrás nos deparamos com um problema digamos, divertido. Precisávamos checar se um endereço e-mail já havia sido registrado. Na ocasião tínhamos 220 milhões de e-mails, e foi assim que começou nosso desafio, inicialmente pensamos em fazer isso da forma tradicional, que seria fazendo uma busca no banco de dados, mas como o software tem uma carga bem elevada, paramos para pensar um pouco sobre e pesquisar sobre outras maneiras de resolver o problema.
A primeira ideia que surgiu foi fazer um cache, o que foi categoricamente descartada pelo simples fato de ser impraticável, considerando que no momento temos aproximadamente 220 milhões de e-mails na base e seriam necessários ≅11Gb para armazenamento do cache em uma simulação otimista. Nessas pesquisas surgiram algumas formas bem interessantes de resolver este problema de forma eficiente, que serão mostradas a seguir.

HyperLogLog

O HyperLogLog é uma estrutura de dados probabilística de armazenamento eficiente (space efficient), que pode ser usada por exemplo para contagem de acessos únicos, que pode armazenar qualquer coisa, desde IDs, endereços de e-mail, IPs e etc.

O HLL trabalha com datasets maiores que 10⁹, com uma margem de erro de apenas 2% e consumindo apenas 1.5KB de armazenamento.

Com base nisso nossa ideia seria fazer o input de todos os e-mails que temos na base hoje, após isso seria necessário apenas fazer o input novamente, e caso já estivesse no dataset teríamos o feedback imediato, sem fazer uma consulta no nosso banco de dados.

HyperLogLog com Redis

Desde a versão 2.8.9, o Redis vem com o HLL e disponibiliza os comandos PFADD, PFCOUNT e PFMERGE, o PF no comando é uma homenagem póstuma ao criador do algoritmo, ph.D Philippe Flajolet

Exemplos

> PFADD visitors marvin@magrathealabs.com
(integer) 1

PFFADD sempre vai retornar 1 caso a cardinalidade do dataset tenha sido alterada, caso contrário retornará 0

O PFCOUNT retorna uma estimativa de quantos itens existem no dataset.

> PFCOUNT visitors
(integer) 2

Também é possível serializar o dataset caso queira armazenar para restaurar posteriormente.

> GET visitors
HYLL\x01\x00\x00\x00\x02\x00\x00\x00\x00\x00\x00\x00O\x0f\x80\\u\x80Tw

Existem outros algoritmos parecidos que valem ser estudados, MinHash, BloomFilter, Cuckoo filter, caso você seja curioso e queira conhecer mais a fundo, o artigo sobre o HLL na wikipedia é bem completo.

Bitmap

Outra abordagem interessante seria usar um bitmap, uma outra estrutura de dados também disponível no Redis, a diferença é que só conseguimos armazenar flags booleanos. Por exemplo, digamos que eu queira saber quais usuários já fizeram meu tour guiado para assim não exibir novamente, nesse caso eu também quero evitar um query no banco de dados, com o bitmap eu consigo armazenar 2³² flags em apenas 512MB, considerando aquele primeiro exemplo de 220 milhões de registros (≅2²⁸), daria pra fazer isso com 25MB.

Exemplos:

> SETBIT users_make_tour 35 1
(integer) 0

Nesse caso eu estou setando que o usuário #35 já faz o tour guiado.

> GETBIT users_make_tour 35
(integer) 1

Assim consigo verificar o estado atual do bit e saber se o usuário já fez.

É uma abordagem bastante simples, porém muito eficiente, vale ler a documentação sobre o tempo de inicialização do bitmap no Redis, para obter a melhor performance possível.