Tair (Redis® OSS-Compatible):TairBloom

Visão geral

No Redis, é possível implementar funcionalidades semelhantes usando Hash, Set ou um bitset armazenado em uma String. No entanto, esses métodos consomem muita memória ou não permitem dimensionamento dinâmico com uma taxa de falsos positivos estável. O TairBloom é ideal para casos de uso que exigem testes de pertinência eficientes em grandes conjuntos de dados e toleram uma pequena taxa de falsos positivos. Use a API do TairBloom diretamente, sem wrappers personalizados ou implementações locais.

Principais recursos

• Baixo consumo de memória.

• Suporte a dimensionamento automático.

• Taxa de falsos positivos personalizável e estável durante o dimensionamento automático.

Casos de uso

Melhores práticas

void recommendedSystem(userid) {
    while (true) {
        // Get a candidate article ID.
        docid = getDocByRandom()
        if (bf.exists(userid, docid)) {
            // The article was probably already recommended, so skip it.
            continue;
        } else {
            // The article was definitely not recommended, so send it.
            sendRecommendMsg(docid);
            // Record the recommendation.
            bf.add(userid, docid);
            break;
        }
    }
}

bool crawlerSystem( ) {
    while (true) {
        // Get a URL to crawl.
        url = getURLFromQueue()
        if (bf.exists(url_bloom, url)) {
            // The URL was probably already crawled, so skip it.
            continue;
        } else {
            // Download the URL content.
            doDownload(url)
            // Add the URL to TairBloom.
            bf.add(url_bloom, url);
        }
    }
}

Funcionamento

O TairBloom é uma implementação de Scalable Bloom Filter. Ele oferece suporte a dimensionamento automático e mantém uma taxa estável de falsos positivos. Um Scalable Bloom Filter é uma versão otimizada do filtro bloom tradicional. As seções a seguir descrevem os princípios básicos dos filtros bloom e dos Scalable Bloom Filters.

• Filtro bloom

  Proposto por Burton Bloom em 1970, o filtro bloom é uma estrutura de dados probabilística com uso eficiente de espaço, utilizada para verificar se um elemento pertence a um conjunto.

  Um novo filtro bloom consiste em um array de bits com m posições, todas inicializadas com 0. Ele também utiliza k funções hash diferentes que geram uma distribuição aleatória uniforme, onde k é uma constante menor que m. Ao adicionar um elemento ao filtro bloom, as k funções hash mapeiam o elemento para k posições no array de bits, definindo os bits nessas posições como 1. Um único bit pode ser compartilhado por vários elementos. A figura a seguir mostra como os elementos X1 e X2 são inseridos em um filtro bloom onde k é igual a 3.

  Para consultar um elemento, as mesmas k funções hash obtêm as k posições de bit correspondentes. Se todos os bits nessas posições forem 1, considera-se que o elemento está presente no filtro bloom. Se qualquer bit for 0, o elemento definitivamente não está presente. A figura a seguir ilustra como verificar se Y1 e Y2 existem no filtro bloom.

  Conforme mostrado na figura, embora o elemento Y2 nunca tenha sido inserido no filtro bloom, o filtro relata que Y2 existe. Trata-se de um falso positivo. Com base nisso, podemos resumir as características de um filtro bloom:

  • Posições de bit podem ser compartilhadas por diferentes elementos.

  • Falsos positivos podem ocorrer. Quanto mais elementos houver no filtro bloom, maior será a probabilidade de um falso positivo. No entanto, falsos negativos não ocorrem. Se um elemento for relatado como ausente, ele definitivamente não está presente.

  • É possível adicionar elementos a um filtro bloom, mas não removê-los. Isso ocorre porque as posições de bit podem ser compartilhadas, e limpar um bit para um elemento pode afetar outros elementos.

• Scalable Bloom Filter

  À medida que mais elementos são adicionados a um filtro bloom, a taxa de falsos positivos aumenta. Para manter essa taxa estável, é necessário aumentar o tamanho do filtro bloom. Contudo, um filtro bloom padrão não pode ser redimensionado. O Scalable Bloom Filter resolve esse problema criando novos filtros bloom e empilhando-os em um único filtro lógico.

  A figura a seguir apresenta o modelo básico de um Scalable Bloom Filter (SBF), composto por duas camadas: BF0 e BF1. Inicialmente, o SBF contém apenas a camada BF0. Suponha que, após a inserção dos elementos a, b e c, a camada BF0 não consiga mais manter a taxa de falsos positivos definida pelo usuário. Nesse momento, uma nova camada (BF1) é criada. Os elementos subsequentes d, e e f são inseridos na camada BF1. Da mesma forma, quando a camada BF1 não consegue mais atender à taxa de falsos positivos, uma nova camada (BF2) é criada, e assim por diante. Para obter mais informações, consulte Scalable Bloom Filter.

  Importante

  Quando o TairBloom realiza dimensionamento automático, a nova camada possui o dobro da capacidade e quatro vezes o uso de memória da camada anterior.

  Cada camada adicional aumenta o tempo de consulta, pois uma consulta pode precisar percorrer várias camadas de filtros bloom. Um Scalable Bloom Filter sempre insere dados na camada mais recente, e as consultas começam pela camada mais recente e continuam retroativamente até a primeira camada (BF0). Como resultado, operações de dimensionamento automático no TairBloom podem criar chaves grandes e degradar o desempenho. Essa degradação aumenta conforme o número de elementos cresce.

  Na prática, evite acionar o dimensionamento automático do TairBloom e trate esse recurso como uma salvaguarda. Reserve memória suficiente para a instância a fim de evitar falhas de gravação após um evento de dimensionamento automático, o que poderia desencadear um processo prolongado de evicção de dados e tornar a instância irresponsiva. Use o comando BF.INFO para verificar se uma chave está prestes a acionar um evento de dimensionamento automático. Quando o número de items na camada mais recente atinge sua capacity, um evento de dimensionamento automático é iminente.

  Quando a capacidade real excede a capacidade predefinida, o TairBloom realiza o dimensionamento automático para garantir que as operações de gravação continuem, prevenindo incidentes de produção. Após o TairBloom concluir uma operação de dimensionamento automático, reconstrua a chave o mais rápido possível para melhorar o desempenho e reduzir os riscos associados ao próximo evento de dimensionamento automático.

Pré-requisitos

Notas de uso

• Os comandos neste tópico operam em dados TairBloom em uma instância Tair.

• Planeje antecipadamente a capacidade inicial e a taxa de falsos positivos. Se a capacidade esperada da chave alvo for muito superior a 100, use o comando BF.RESERVE para criar a chave TairBloom. Evite criar a chave com o comando BF.ADD.

  A lista a seguir descreve as diferenças entre executar o comando BF.ADD e o comando BF.RESERVE.

  • BF.ADD (ou BF.MADD): se a chave alvo não existir durante a execução do comando, o Tair cria automaticamente uma instância TairBloom com capacidade padrão de 100 e taxa de falsos positivos (error_rate) de 0,01. Caso a capacidade necessária seja muito maior que 100, só será possível adicionar mais elementos posteriormente expandindo a capacidade. À medida que o número de camadas internas no TairBloom aumenta, as operações de consulta precisam percorrer múltiplos filtros Bloom, o que degrada severamente o desempenho.

  • BF.RESERVE (ou BF.INSERT): ao executar este comando, defina a capacity (capacidade inicial). Este comando inicializa a capacidade na primeira camada da chave TairBloom. Uma chave TairBloom com menos camadas proporciona consultas mais rápidas.

  Nota

  Por exemplo, para inserir 10.000.000 de elementos com uma taxa de falsos positivos de 0,01, criar uma chave TairBloom com o comando BF.ADD requer 176 MB de memória. Em contraste, criar a chave com o comando BF.RESERVE requer apenas 16 MB.

  A tabela a seguir lista o uso de memória para chaves criadas com diferentes capacidades iniciais e taxas de falsos positivos usando o comando BF.RESERVE. Os valores servem apenas como referência.

  Capacidade	Taxa de falsos positivos: 0,01	Taxa de falsos positivos: 0,001	Taxa de falsos positivos: 0,0001
  100.000	0,12 MB	0,25 MB	0,25 MB
  1.000.000	2 MB	2 MB	4 MB
  10.000.000	16 MB	32 MB	32 MB
  100.000.000	128 MB	256 MB	256 MB
  1.000.000.000	2 GB	2 GB	4 GB

  Ao criar uma chave com capacidade muito grande, considere o parâmetro error_rate. Uma chave com capacidade extremamente alta e alta precisão (um error_rate baixo) pode falhar devido à memória insuficiente da instância.

• O TairBloom permite inserir novos elementos, mas não excluir elementos existentes. Consequentemente, o uso de memória de uma chave TairBloom só aumenta. Para evitar que uma chave TairBloom cresça excessivamente e cause erros de falta de memória (OOM), considere as seguintes sugestões.

  • Divida os dados de negócios: segmente e refine seus dados de negócios para evitar armazenar uma grande quantidade de dados em uma única chave TairBloom. Isso impede que a chave fique muito grande e afete o desempenho das consultas, além de evitar que a maior parte do tráfego de consultas seja direcionada à instância Redis onde a chave está localizada, o que pode criar uma chave quente (hot key) e causar desequilíbrio de acesso.

    Divida seus dados de negócios e distribua-os entre várias chaves TairBloom. Se você usar uma instância cluster, distribua as chaves TairBloom entre os nós do cluster para balancear memória e tráfego, aproveitando ao máximo um cluster distribuído.

  • Reconstrua periodicamente: se o seu negócio permitir, reconstrua periodicamente a chave TairBloom. Use o comando DEL para excluir a chave TairBloom e, em seguida, extraia dados do banco de dados backend para reconstruí-la. Isso ajuda a controlar o tamanho da chave TairBloom.

    Também é possível criar várias chaves TairBloom inicialmente e alternar entre elas para controlar o tamanho das chaves individuais. Essa abordagem evita reconstruções frequentes, mas consome mais memória.

Referência de comandos

BF.RESERVE

BF.RESERVE BFKEY 0.01 100

OK

BF.ADD

BF.ADD BFKEY item1

(integer) 1

BF.MADD

BF.MADD BFKEY item1 item2 item3

(integer) 1
    (integer) 1
    (integer) 1

BF.EXISTS

BF.EXISTS BFKEY item1

(integer) 1

BF.MEXISTS

BF.MEXISTS BFKEY item1 item5

(integer) 1
    (integer) 0

BF.INSERT

BF.INSERT bfkey1 CAPACITY 10000 ERROR 0.001 ITEMS item1 item2 item3

(integer) 1
    (integer) 1
    (integer) 1

BF.INFO

BF.INFO bk1

1) "total_items:6,num_blooms:2"
    2) "bytes:4 bits:32 hashes:7 hashwidth:64 capacity:3 items:3 error_ratio:0.01"
    3) "bytes:16 bits:128 hashes:9 hashwidth:64 capacity:10 items:3 error_ratio:0.0025"

BF.DEBUG

BF.DEBUG bfkey1

1) "total_items:3,num_blooms:1" 
    2) "bytes:32768 bits:262144 hashes:10 hashwidth:64 capacity:18232 items:3 error_ratio:0.001"