Tair (Redis® OSS-Compatible):TairBloom

Présentation

Dans Redis, vous pouvez reproduire une fonctionnalité similaire en utilisant des types Hash, Set ou un bitset stocké dans une chaîne String. Toutefois, ces méthodes consomment soit beaucoup de mémoire, soit ne permettent pas une mise à l'échelle dynamique tout en conservant un taux de faux positifs stable. TairBloom constitue la solution idéale lorsque vous devez effectuer des tests d'appartenance efficaces sur de grands volumes de données et qu'un faible taux de faux positifs reste acceptable. Utilisez directement l'API TairBloom, sans recourir à des enveloppes personnalisées ni à une implémentation locale.

Principales fonctionnalités

• Empreinte mémoire réduite.

• Mise à l'échelle automatique prise en charge.

• Taux de faux positifs personnalisable, maintenu stable lors de la mise à l'échelle automatique.

Cas d'utilisation

Bonnes pratiques

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);
        }
    }
}

Fonctionnement

TairBloom implémente un Scalable Bloom Filter. Il prend en charge la mise à l'échelle automatique et conserve un taux de faux positifs stable. Un Scalable Bloom Filter représente une version optimisée du filtre de Bloom classique. Les sections suivantes décrivent les principes fondamentaux des filtres de Bloom et des Scalable Bloom Filters.

• Filtre de Bloom

  Le filtre de Bloom est une structure de données probabiliste économe en espace mémoire, proposée par Burton Bloom en 1970. Elle sert à tester l'appartenance d'un élément à un ensemble.

  Un nouveau filtre de Bloom se présente sous la forme d'un tableau de bits de taille m, initialement remplis de zéros. Il utilise également k fonctions de hachage distinctes générant une distribution aléatoire uniforme, où k constitue une constante inférieure à m. Lorsque vous ajoutez un élément au filtre de Bloom, les k fonctions de hachage mappent cet élément vers k positions dans le tableau de bits, et les bits situés à ces positions passent à 1. Un même bit peut être partagé par plusieurs éléments. La figure suivante montre l'insertion des éléments X1 et X2 dans un filtre de Bloom où k vaut 3.

  

  Pour interroger un élément, utilisez les mêmes k fonctions de hachage afin d'obtenir les k positions de bits correspondantes. Si tous les bits à ces positions valent 1, l'élément est considéré comme présent dans le filtre de Bloom. Si au moins un bit vaut 0, l'élément est assurément absent. La figure suivante illustre la vérification de la présence des éléments Y1 et Y2 dans le filtre de Bloom.

  

  Comme le montre la figure, bien que l'élément Y2 n'ait jamais été inséré dans le filtre de Bloom, celui-ci indique sa présence. Il s'agit d'un faux positif. Nous pouvons ainsi résumer les caractéristiques d'un filtre de Bloom :

  • Les positions de bits peuvent être partagées entre différents éléments.

  • Des faux positifs peuvent survenir. Plus le filtre de Bloom contient d'éléments, plus la probabilité de faux positifs augmente. En revanche, les faux négatifs sont impossibles : si un élément est signalé comme absent, il l'est définitivement.

  • Vous pouvez ajouter des éléments à un filtre de Bloom, mais pas les supprimer. En effet, les positions de bits étant partagées, effacer un bit pour un élément donné pourrait affecter d'autres éléments.

• Scalable Bloom Filter

  Lorsque vous ajoutez davantage d'éléments à un filtre de Bloom, le taux de faux positifs augmente. Pour maintenir ce taux stable, vous devez augmenter la taille du filtre. Or, un filtre de Bloom standard ne permet pas de redimensionnement. Un Scalable Bloom Filter résout ce problème en créant de nouveaux filtres de Bloom et en les empilant au sein d'un seul filtre logique.

  La figure suivante présente le modèle de base d'un Scalable Bloom Filter (SBF), composé de deux couches : BF0 et BF1. Initialement, le SBF ne contient que la couche BF0. Supposons qu'après l'insertion des éléments a, b et c, la couche BF0 ne puisse plus garantir le taux de faux positifs défini par l'utilisateur. À ce stade, une nouvelle couche (BF1) est créée. Les éléments suivants d, e et f sont alors insérés dans la couche BF1. De même, lorsque la couche BF1 ne respecte plus le taux de faux positifs requis, une nouvelle couche (BF2) est créée, et ainsi de suite. Pour plus d'informations, consultez Scalable Bloom Filter.

  

  Important

  Lorsque TairBloom effectue une mise à l'échelle automatique, la nouvelle couche offre le double de la capacité et consomme quatre fois plus de mémoire que la précédente.

  Chaque couche supplémentaire accroît le temps d'interrogation, car une requête peut devoir traverser plusieurs couches de filtres de Bloom. Un Scalable Bloom Filter insère toujours les données dans la dernière couche, tandis que les requêtes commencent par la couche la plus récente avant de remonter jusqu'à la première couche (BF0). Par conséquent, les opérations de mise à l'échelle automatique dans TairBloom peuvent générer des clés volumineuses et dégrader les performances. Cette dégradation s'accentue à mesure que le nombre d'éléments augmente.

  En pratique, évitez de déclencher la mise à l'échelle automatique de TairBloom et considérez cette fonctionnalité comme une sécurité. Réservez suffisamment de mémoire pour l'instance afin d'éviter les échecs d'écriture après un événement de mise à l'échelle automatique, qui pourraient déclencher un processus prolongé d'éviction des données et rendre l'instance indisponible. Utilisez la commande BF.INFO pour vérifier si une clé est sur le point de déclencher une mise à l'échelle automatique. Lorsque le nombre d'éléments items dans la dernière couche atteint sa capacity, un événement de mise à l'échelle automatique est imminent.

  Lorsque la capacité réelle dépasse la capacité prédéfinie, TairBloom effectue une mise à l'échelle automatique afin de permettre la poursuite des opérations d'écriture, prévenant ainsi les incidents en production. Une fois la mise à l'échelle automatique terminée, reconstruisez la clé dès que possible pour améliorer les performances et réduire les risques liés au prochain événement de mise à l'échelle.

Prérequis

Notes d'utilisation

• Les commandes décrites dans cette rubrique opèrent sur les données TairBloom d'une instance Tair.

• Planifiez à l'avance la capacité initiale et le taux de faux positifs. Si la capacité attendue de la clé cible dépasse largement 100, utilisez la commande BF.RESERVE pour créer la clé TairBloom. Évitez de créer la clé avec la commande BF.ADD.

  La liste suivante décrit les différences entre l'exécution de la commande BF.ADD et celle de la commande BF.RESERVE.

  • BF.ADD (ou BF.MADD) : si la clé cible n'existe pas lors de l'exécution de la commande, Tair crée automatiquement une instance TairBloom avec une capacité par défaut de 100 et un taux de faux positifs (error_rate) de 0,01. Si votre capacité requise dépasse largement 100, vous ne pourrez ajouter davantage d'éléments qu'en étendant la capacité ultérieurement. À mesure que le nombre de couches internes dans TairBloom augmente, les opérations d'interrogation doivent traverser plusieurs filtres de Bloom, ce qui dégrade fortement les performances.

  • BF.RESERVE (ou BF.INSERT) : lors de l'exécution de cette commande, vous devez définir la capacity (capacité initiale). Cette commande initialise la capacité dans la première couche de la clé TairBloom. Une clé TairBloom comportant moins de couches offre des interrogations plus rapides.

  Remarque

  Par exemple, pour insérer 10 000 000 d'éléments avec un taux de faux positifs de 0,01, la création d'une clé TairBloom avec la commande BF.ADD nécessite 176 Mo de mémoire. En revanche, la création de la clé avec la commande BF.RESERVE ne requiert que 16 Mo.

  Le tableau suivant répertorie l'utilisation mémoire pour les clés créées avec différentes capacités initiales et taux de faux positifs via la commande BF.RESERVE. Ces valeurs sont fournies à titre indicatif uniquement.

  Capacité	Taux de faux positifs : 0,01	Taux de faux positifs : 0,001	Taux de faux positifs : 0,0001
  100 000	0,12 Mo	0,25 Mo	0,25 Mo
  1 000 000	2 Mo	2 Mo	4 Mo
  10 000 000	16 Mo	32 Mo	32 Mo
  100 000 000	128 Mo	256 Mo	256 Mo
  1 000 000 000	2 Go	2 Go	4 Go

  Lors de la création d'une clé dotée d'une très grande capacité, tenez compte de la valeur error_rate. Une clé associant une capacité très élevée et une haute précision (faible error_rate) peut échouer en raison d'une insuffisance de mémoire sur l'instance.

• TairBloom vous permet d'insérer de nouveaux éléments, mais pas de supprimer les éléments existants. Par conséquent, l'utilisation mémoire d'une clé TairBloom ne fait qu'augmenter. Afin d'éviter qu'une clé TairBloom ne devienne trop volumineuse et ne provoque des erreurs de mémoire insuffisante (OOM), prenez en compte les suggestions suivantes.

  • Segmentez vos données métier : divisez et affinez vos données métier pour éviter de stocker un volume important de données dans une seule clé TairBloom. Cela permet non seulement d'empêcher la clé de devenir trop volumineuse et d'affecter les performances d'interrogation, mais aussi d'éviter que la majorité du trafic d'interrogation ne soit dirigée vers l'instance Redis hébergeant la clé, ce qui pourrait créer une clé chaude et provoquer un déséquilibre d'accès.

    Répartissez vos données métier sur plusieurs clés TairBloom. Si vous utilisez une instance cluster, distribuez les clés TairBloom sur les nœuds du cluster afin d'équilibrer la mémoire et le trafic, tirant ainsi pleinement parti d'un cluster distribué.

  • Reconstruisez périodiquement : si votre activité le permet, reconstruisez régulièrement la clé TairBloom. Utilisez la commande DEL pour supprimer la clé TairBloom, puis extrayez les données depuis la base de données backend pour la reconstruire. Cette approche aide à maîtriser la taille de la clé TairBloom.

    Vous pouvez également créer initialement plusieurs clés TairBloom et alterner entre elles afin de contrôler la taille des clés individuelles. Cette méthode évite des reconstructions fréquentes, mais consomme davantage de mémoire.

Référence des commandes

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"

FAQ