Filtres de Bloom : « Déjà vu ? » avec très peu de mémoire
De quoi parle cet épisode
Un filtre de Bloom répond à « ai-je déjà vu cet élément ? » avec une simple rangée de cases 0/1 et quelques fonctions de hachage. Insérer un élément allume quelques cases ; si l’une d’elles est éteinte lors d’une requête, on est certain que l’élément n’a jamais été inséré.
Le prix à payer, ce sont les faux positifs : quand toutes les cases sont allumées, le filtre répond seulement « peut-être », mais il n’oublie jamais un élément inséré. Cet épisode montre comment naissent les faux positifs, puis vous laisse régler le nombre de cases m et de fonctions de hachage k pour trouver l’équilibre entre mémoire et précision.
Prérequis
- Tables de hachage : gagner du temps avec de l’espace Bientôt disponible
Où on l’utilise dans le monde réel
- Cassandra Avant de lire, il interroge le filtre de Bloom de chaque fichier sur disque : un « certainement absent » évite d’ouvrir ce fichier et économise de nombreuses lectures.
- HBase Chaque fichier de stockage a son filtre de Bloom, si bien qu’une recherche d’une ligne n’ouvre que les fichiers susceptibles de la contenir.
- RocksDB Le moteur de stockage LSM garde des filtres de Bloom pour les fichiers de chaque niveau : les clés inexistantes ne touchent presque jamais le disque.
À voir ensuite
- Arbres LSM : transformer les écritures aléatoires en séquentielles Bientôt disponible
Épisode 3
Voici l’épisode 3 de la série « Structures de données et algorithmes » (13 prévus).