Je connaissais de l'université le filtre Bloom , une structure de données probabiliste nommée d'après Burton Bloom. Mais je n'ai pas eu l'occasion de l'utiliser. Le mois dernier, une telle opportunité est apparue - et cette structure m'a littéralement fasciné. Cependant, j'ai vite trouvé des défauts en elle. Cet article est une histoire de ma brève histoire d'amour avec le filtre Bloom.

Dans le processus de recherche de l'usurpation d'adresse IP, il a été nécessaire de vérifier les adresses IP dans les paquets entrants, en les comparant avec l'emplacement géographique de nos centres de données. Par exemple, les packages en provenance d'Italie ne doivent pas être envoyés au centre de données brésilien. Ce problème peut sembler simple, mais dans le paysage en constante évolution d'Internet, il est loin d'être simple. Qu'il suffise de dire qu'à la fin j'ai accumulé beaucoup de gros fichiers texte avec approximativement le contenu suivant:

Cela signifie qu'une demande de l'adresse IP résolue 192.0.2.1 a été enregistrée dans le centre de données Cloudflare numéro 107. Ces données provenaient de nombreuses sources, y compris nos échantillons actifs et passifs, les journaux de certains domaines que nous possédons (par exemple,cloudflare.com), les sources ouvertes (par exemple, les tables BGP), etc. La même ligne est généralement répétée dans plusieurs fichiers.

Je me suis retrouvé avec un gigantesque jeu de données de ce genre. À un moment donné, dans toutes les sources collectées, j'ai compté 1 milliard de lignes. Habituellement, j'écris des scripts bash pour prétraiter les données d'entrée, mais à cette échelle, cette approche n'a pas fonctionné. Par exemple, la suppression des doublons de ce petit fichier de 600 lignes MiB et 40 millions prend ... l' éternité:

il suffit de dire que les lignes de déduplication avec des commandes ordinaires du type sortdans diverses configurations (voir --parallel, --buffer-sizeet --unique) n'a pas été le meilleur pour un grand ensemble de données.

Filtres Bloom

Illustration de David Epstein dans le domaine public

Alors ça m'est venu à l'esprit: ne triez pas les lignes! Vous devez supprimer les doublons, de sorte qu'une sorte de structure de données «définie» fonctionnera beaucoup plus rapidement. De plus, je connais à peu près la taille du fichier d'entrée (le nombre de lignes uniques), et la perte de certaines données n'est pas critique, c'est-à-dire que la structure de données probabiliste est tout à fait appropriée.

C'est parfait pour les filtres Bloom!

Pendant que vous lisezWikipédia sur les filtres Bloom, voicicomment je regarde cette structure de données.

Comment mettriez-vous en œuvrela pluralité? Étant donné une fonction de hachage idéale et une mémoire infinie, nous pouvons simplement créer une image bitmap infinie et définir un nombre de bits pour chaque élémenthash(item). Cela fournit la structure de données idéale pour la «multitude». Droite? Trivialement. Malheureusement, les fonctions de hachage entrent en collision, et la mémoire infinie n'existe pas, donc dans notre réalité, nous devons faire des compromis. Mais nous pouvons calculer la probabilité de collisions et gérer cette valeur. Par exemple, nous avons une bonne fonction de hachage et 128 Go de mémoire. Nous pouvons calculer que la probabilité de collision pour chaque nouvel élément est comprise entre 1 et 1099511627776. Lorsque vous ajoutez d'autres éléments, la probabilité augmente à mesure que le bitmap est rempli.

De plus, nous pouvons appliquer plusieurs fonctions de hachage et obtenir une image bitmap plus dense. C'est là que le filtre Bloom fonctionne bien, qui est un ensemble de données mathématiques avec quatre variables:

n - nombre d'éléments insérés (nombre cardinal)
m - mémoire utilisée par le bitmap
k - le nombre de fonctions de hachage calculées pour chaque entrée
p - probabilité de faux coïncidence positive

Compte tenu du nombre cardinal net de la probabilité souhaitée de faux positifs p, le filtre Bloom renvoie la mémoire requise met le nombre requis de fonctions de hachage k.

Découvrez cette excellente visualisation de Thomas Hurst sur la façon dont les paramètres s'influencent mutuellement.

mmuniq-bloom

Guidé par l'intuition, j'ai ajouté l'outil probabiliste mmuniq-bloom à mon arsenal, qui prend l'entrée STDIN et ne renvoie que des lignes uniques dans STDOUT. Cela devrait être beaucoup plus rapide qu'une combinaison de sort+ uniq!

Le voilà:

mmuniq-bloom.c

Pour plus de simplicité et de rapidité, j'ai initialement défini quelques paramètres. Premièrement, sauf indication contraire, mmuniq-bloom utilise huit fonctions de hachage k = 8. Cela semble être proche du nombre optimal pour notre taille de données, et la fonction de hachage peut rapidement produire huit hachages décents. Ensuite, nous alignons la mémoire mdans le bitmap à la puissance de deux pour éviter une opération coûteuse %modulo, qui en assembleur se résume à ralentir div. Si le tableau est égal à la puissance de deux, nous pouvons simplement utiliser ET au niveau du bit (pour le plaisir, lisez comment les compilateurs optimisent certaines opérations de division en multipliant par une constante magique ).

Maintenant, nous pouvons l'exécuter sur le même fichier de données que nous avons utilisé auparavant:

Oh, c'est beaucoup mieux! 12 secondes au lieu de deux minutes. Le programme utilise une structure de données optimisée, une quantité de mémoire relativement limitée, une analyse de ligne optimisée et un bon tampon de sortie ... et avec tout cela, 12 secondes semblent être une éternité par rapport à l'outil wc -l:

que se passe-t-il? Je comprends qu'il est wcplus facile de compter des chaînes que de calculer des chaînes uniques, mais la différence de 26 fois est-elle vraiment justifiée? Que prend le CPU mmuniq-bloom?

Doit être pour le calcul des hachages. L'utilitaire wcne dépense pas le processeur, faisant tout ce calcul étrange pour chacune des 40 millions de lignes. J'utilise une fonction de hachage plutôt banale siphash24, c'est sûr qu'elle brûle le processeur, non? Vérifions en exécutant uniquement la fonction de hachage, mais pasn'effectuant aucune opération avec le filtre Bloom:

c'est étrange. Le calcul de la fonction de hachage ne prend que deux secondes environ, bien que l'ensemble du programme de l'exécution précédente ait été exécuté pendant 12 secondes. Un filtre Bloom fonctionne-t-il pendant 10 secondes? Comment est-ce possible? C'est une structure de données tellement simple ...

Arme secrète - Profiler

Il est temps d'appliquer le bon outil pour cette tâche - exécutons le profileur et voyons sur quoi le processeur travaille. Tout d'abord, exécutons stracepour vérifier qu'il n'y a pas d'appels système inattendus:

tout semble bien. Dix appels à mmap4 ms chacun (3971 μs) sont intrigants, mais ça va. Nous pré-remplissons la mémoire MAP_POPULATEpour éviter plus tard les erreurs dues au manque de page.

Quelle est la prochaine étape? Bien sûr que ça l'est perf!

Voyons ensuite le résultat:

Donc, nous brûlons vraiment 87,2% des cycles dans le code principal. Voyons où exactement. L'équipe perf annotate process_line --sourcemontre immédiatement quelque chose d'inattendu.

On voit que 26,90% du processeur a grillémov, Mais ce n'est pas tout! Le compilateur insère correctement la fonction et développe la boucle. Il s'avère que la plupart des cycles vont à ceci movou à la ligne uint64_t v = *p!

De toute évidence, la perf est erronée, comment une chaîne aussi simple peut-elle occuper autant de ressources? Mais répéter le test avec n'importe quel autre profileur montre le même problème. Par exemple, j'aime utiliser google-perftools avec kcachegrind à cause des diagrammes colorés:

Le résultat de la visualisation est le suivant:

Permettez-moi de résumer ce que nous avons découvert jusqu'à présent.

L'utilitaire standard wctraite un fichier de 600 Mio pour un temps processeur de 0,45 s. Notre outil optimisé mmuniq-bloomdure 12 secondes. Le processeur est gravé sur une seule instruction mov, déréférençant la mémoire ...

Image de Jose Nicdao , CC BY / 2.0

Oh! Comment pourrai-je oublier. L'accès aléatoire à la mémoire estvraimentlent! Très, très, très lentement!

Selon leschiffres que chaque programmeur devrait connaître, un seul accès à la RAM prend environ 100 ns. Comptons: 40 millions de lignes, 8 hachages chacune. Puisque notre filtre Bloom a une taille de 128 Mio, surnotre ancien matériel,il ne rentre pas dans le cache L3! Les hachages sont répartis uniformément sur une large gamme de mémoire - chacun d'eux génère un cache manquant. Mettez tout cela ensemble, et il s'avère que ...

Il s'avère que 32 secondes ne s'éteignent que sur les accès mémoire. Le vrai programme tient en seulement 12 secondes, car le filtre Bloom bénéficie toujours de la mise en cache. C'est facile à voir avec perf stat -d:

Oui, nous aurions dû avoir un minimum de 320 millions de ratés de cache (LLC-load-misses), mais seulement 280 millions se sont produits: cela n'explique toujours pas pourquoi le programme a fonctionné en seulement 12 secondes. Mais ça ne fait rien. Il est important que le nombre d'échecs de cache soit un vrai problème, et nous ne pouvons le résoudre qu'en réduisant le nombre d'accès à la mémoire. Essayons de configurer le filtre Bloom pour utiliser une seule fonction de hachage:

Ay! Ça fait vraiment mal! Pour obtenir une probabilité de collision de 1 pour 10 000 lignes, le filtre Bloom nécessitait 64 gigaoctets de mémoire. C'est horrible!

De plus, il ne semble pas que la vitesse ait considérablement augmenté. Il nous a fallu 22 secondes au système d'exploitation pour préparer la mémoire, mais nous avons quand même passé 11 secondes dans l'espace utilisateur. Je crois que maintenant tous les avantages d'un accès plus rare à la mémoire sont compensés par une probabilité plus faible d'entrer dans le cache en raison de la taille de la mémoire fortement augmentée. Auparavant, 128 Mio suffisaient pour le filtre Bloom!

Refuser les filtres Bloom

C'est tout simplement ridicule. Pour réduire la probabilité de faux positifs, vous devez soit utiliser beaucoup de hachages dans le filtre Bloom (par exemple, huit) avec beaucoup d'accès à la mémoire, soit laisser une fonction de hachage, mais utiliser d'énormes quantités de mémoire.

En fait, nous n'avons pas de limite de mémoire, nous voulons minimiser le nombre d'appels. Nous avons besoin d'une structure de données qui coûte au maximum un cache manquant par élément et utilise moins de 64 gigaoctets de RAM ...

Bien sûr, vous pouvez implémenter des structures de données complexes, comme un filtre à coucou , mais il existe certainement une option plus simple. Qu'en est-il de la bonne vieille table de hachage de sondage linéaire?

Illustration de Vadims Podans

Rencontrez mmuniq-hash

Voici la nouvelle version de mmuniq-bloom utilisant une table de hachage:

mmuniq-hash.c

Au lieu des bits pour le filtre Bloom, nous stockons maintenant les hachages 64 bits de la fonction 'siphash24' . Cela offre une bien meilleure protection contre les collisions par hachage: bien meilleure qu'une par 10 000 lignes.

Comptons. L'ajout d'un nouvel élément à une table de hachage, disons avec 40 millions d'entrées, donne la possibilité de collisions de hachage 40 000 000/2^64. C'est environ 1 sur 461 milliards - une probabilité assez faible. Mais nous n'ajoutons pas un élément à l'ensemble pré-rempli! Au lieu de cela, nous ajoutons 40 millions de lignes à l'ensemble initialement vide. Selon le paradoxe de l'anniversaire , cela augmente considérablement la probabilité de collisions. Une approximation raisonnable serait une estimation '~n^2/2m, dans notre cas, il est~(40M^2)/(2*(2^64)). Il en résulte une chance sur 23 000. En d'autres termes, avec une bonne fonction de hachage, nous nous attendons à une collision dans l'un des 23 000 ensembles aléatoires de 40 millions d'éléments. Il s'agit d'une probabilité non nulle, mais toujours meilleure que dans le filtre Bloom, et elle est complètement tolérable pour notre cas d'utilisation.

Le code avec une table de hachage fonctionne plus rapidement, il a de meilleurs modèles d'accès à la mémoire et une probabilité de faux positifs plus faible que dans le filtre Bloom.

Ne vous inquiétez pas de la ligne «conflits de hachage», elle montre simplement à quel point la table de hachage est pleine. Nous utilisons la détection linéaire, donc lorsque nous entrons dans l'ensemble complet, nous prenons simplement le prochain vide. Dans notre cas, nous devons sauter une moyenne de 0,7 séries pour trouver une place vide dans le tableau. C'est normal. Puisque nous parcourons les ensembles dans un ordre linéaire, la mémoire doit être qualitativement pleine.

De l'exemple précédent, nous savons que notre fonction de hachage prend environ deux secondes. Nous concluons que 40 millions d'accès à la mémoire prennent environ quatre secondes.

Leçons apprises

Les processeurs modernes sont vraiment bons pour l'accès séquentiel à la mémoire lorsqu'il est possible de prédire les modèles d'échantillonnage (voir la prélecture du cache ). L'accès aléatoire à la mémoire, en revanche, coûte très cher.

Les structures de données avancées sont très intéressantes, mais faites attention. Les ordinateurs modernes nécessitent l'utilisation d'algorithmes optimisés pour le cache. Lorsque vous travaillez avec des ensembles de données volumineux qui ne tiennent pas dans L3, l'optimisation sur le nombre de hits est préférable à l'optimisation sur la quantité de mémoire utilisée.

Il est juste de dire que les filtres Bloom fonctionnent très bien lorsqu'ils sont placés dans le cache L3. Mais sinon, ils sont terribles. Ce n'est pas une nouveauté: les filtres Bloom sont optimisés pour la quantité de mémoire et non pour le nombre d'appels. Par exemple, voirarticle scientifique sur les filtres à coucou .

Une autre chose est les discussions sans fin sur les fonctions de hachage. Honnêtement, dans la plupart des cas, cela n'a pas d'importance. Le coût du comptage même des fonctions de hachage complexes semble siphash24faible par rapport au coût de l'accès aléatoire à la mémoire. Dans notre cas, la simplification de la fonction de hachage n'apportera qu'un petit avantage. Le temps CPU est simplement perdu ailleurs - en attente de mémoire!

Un collègue dit souvent: «On peut supposer que les processeurs modernes sont infiniment rapides. Ils travaillent à une vitesse infinie, jusqu'à ce qu'ils reposent contre le mur de la mémoire . "

Enfin, ne répétez pas mon erreur. Vous devez toujours effectuer le profilage avecperf stat -det regardez le compteur IPC (instructions par cycle). S'il est inférieur à un, cela signifie généralement que le programme est bloqué en attente de mémoire. Les valeurs optimales sont supérieures à deux. Cela signifie que la charge de travail est principalement sur le CPU. Malheureusement, dans mes tâches, l'IPC est encore faible ...

Mmuniq supérieur

Avec l'aide de collègues, j'ai écrit une version améliorée de l'outil mmuniq basée sur une table de hachage. Voici le code:

mmuniq.c

Il peut changer dynamiquement la taille de la table de hachage, prend en charge l'entrée avec un nombre cardinal arbitraire. Ensuite, il traite les données en paquets, en utilisant efficacement l'indice prefetchdans le processeur, ce qui accélère le programme de 35 à 40%. Soyez prudent, une utilisation abondante prefetchdans le code donne rarement effet. Pour utiliser cette fonction, j'ai spécialement réorganisé les algorithmes. Avec toutes les améliorations, le temps d'exécution a été réduit à 2,1 secondes:

la fin

La création d'un outil de base qui tente de surpasser la combinaison «tri / uniq» a révélé certaines caractéristiques cachées de l'informatique moderne. Après avoir un peu transpiré, nous avons accéléré le programme de plus de deux minutes à deux secondes. Au cours du développement, nous avons découvert le retard de l'accès aléatoire à la mémoire, ainsi que la puissance des structures de données compatibles avec le cache. Des structures de données bizarres attirent l'attention, mais dans la pratique, il est souvent plus efficace de réduire le nombre d'accès aléatoires à la mémoire.

Lorsque le filtre bloom ne rentre pas