Structure sur disque pour stocker un grand nombre d'entiers 128 bits?

Question

J'ai environ 500 millions d'entiers de 128 bits, ajoutant environ 100M par an. Rien n'est jamais effacé. Les chiffres sont distribués uniformément, à l'échelle et dans le temps.

Fondamentalement, tout ce dont j'ai besoin est une opération d'ajout qui retourne également si le numéro existe déjà dans le DB. De plus, je ne veux pas utiliser trop de RAM pour ce système, donc stocker tout en mémoire n'est pas ce que je cherche.

Jusqu'à présent, nous utilisions plusieurs tables MyISAM sur MySQL, en utilisant deux bigints comme clé primaire. Cela nous donne une bonne performance, mais je suppose que ce n'est pas le bon outil pour ce travail. Nous avons eu quelques problèmes de performance avant de diviser les tables, et nous avons eu des corruptions sur les pannes de courant. En outre, une base de données nous donne beaucoup plus de fonctionnalités dont nous n'avons pas besoin. J'utilise Python sous Linux, mais je suis ouvert aux suggestions.

Similar question in C++. MISE À JOUR: Le commentaire de Marcelo mentionne Bloom Filter, ce qui me semble très prometteur. Puisque je travaille avec des hachages, j'ai déjà renoncé à une précision complète, donc cela pourrait être un grand compromis précision/performance.

Answer 1

Insérer chaque entier dans une d'un groupe de 2 n bases de données SQLite (2 est probablement un bon nombre) choisi par le calcul d'un hachage n de bits de l'entier. Faites de la colonne d'une table une clé primaire, de sorte que la tentative d'insertion d'un nombre existant échoue.

En supposant que les nombres entiers sont déjà suffisamment aléatoires, vous pouvez probablement choisir, disons, l'octet le moins significatif comme "hash".

EDIT: J'ai effectué quelques tests. J'ai inséré 25 millions d'entrées en deux heures environ, mais il a englouti plus de 1 Go dans le processus. Ceci est fait en générant des nombres aléatoires et en les distribuant à 32 sous-processus, chacun avec une base de données SQLite sous son contrôle et valide une fois tous les 100 000 insertions. Les insertions sont actuellement en cours à environ 1350 Hz, bien au-delà des 3 Hz exigés par votre problème, mais la base de données entière tient toujours dans le cache (j'ai 8 Go de RAM). Je ne connaîtrai pas les performances en régime permanent à moins que je ne me rapproche de la taille de la base de données actuelle. À ce stade, chaque insertion induira au moins quatre mouvements de la tête de disque (lire et écrire l'index et la table, probablement plus pour descendre dans l'arbre B +), et vous saurez alors à quel point vous êtes vraiment mal à l'aise. . Je commence à penser que c'est un problème vraiment intéressant qui pourrait être résolu beaucoup plus efficacement avec une solution personnalisée. Cependant, je soupçonne qu'il faudra un effort raisonnable pour surpasser considérablement un moteur de base de données.

Answer 2

Vous pouvez hacher vos hachages?