Des hashtables rapides sur disque?

Question

J'ai des ensembles de hachages (les 64 premiers bits de MD5, donc ils sont distribués de manière très aléatoire) et je veux être en mesure de voir si un nouveau hachage est dans un ensemble et de l'ajouter à un ensemble.

Les ensembles ne sont pas trop grands, le plus grand contient des millions d'éléments, mais il en existe des centaines, je ne peux donc pas les garder tous en mémoire.

Quelques idées que j'ai eues jusqu'à présent:

• J'ai essayé de tout garder dans une table sqlite, mais cela devient vraiment très lent une fois que tout ne peut pas être enregistré dans la mémoire.
• Les filtres Bloom sonnent comme s'ils avaient un taux d'erreur très élevé. Le taux d’erreur ne me dérange pas (un hachage de 64 bits donne déjà 1 collision sur un ensemble d’éléments 4G), mais des taux d’erreur tels que 1% sont beaucoup trop élevés.
• Conservez la liste triée des hachages avec des espaces dans un fichier et redimensionnez-la lorsque je ne dispose pas d'assez d'espaces. Les hachages sont répartis uniformément, donc même un schéma très simple comme celui-ci devrait fonctionner.

Est-ce que je manque quelque chose de vraiment évident? Des astuces pour mettre en oeuvre une bonne table de hachage sur disque?

Answer 1

Voici la solution que j'ai finalement utilisée:

• Un fichier par jeu
• Le fichier contient 2 ^ k compartiments de 256 octets ou 32 entrées de 8 octets chacun
• Les entrées vides sont simplement mises à zéro (000 ... est un hachage valide, mais je me moque de 2 chances sur 2 de collision, si tout peut déjà entrer en collision, par la nature du hachage).
• Chaque hachage réside dans un seau deviné via ses k premiers bits
• Si un compartiment déborde, doublez la taille du fichier et divisez chaque compartiment
• Tout est accessible via mmap (), pas read () / write ()

C’est incroyablement plus rapide que sqlite, même s’il s’agit d’un code Perl de bas niveau, et Perl n’est vraiment pas conçu pour les bases de données hautes performances. Cela ne fonctionnera pas avec tout ce qui est moins uniformément distribué que MD5, en supposant que tout sera extrêmement uniforme pour garder la mise en œuvre simple.

Je l'ai essayé avec seek () / sysread () / syswrite () au début, et c'était très lent, la version de mmap () est vraiment beaucoup plus rapide.

Answer 2

J'ai eu du mal à comprendre votre problème / besoin exact, mais cela m'a tout de même fait penser à Git et à la façon dont il stocke les références SHA1 sur disque:

Prenez la représentation hexadécimale sous forme de chaîne d'un hachage donné, par exemple, & "; abfab0da6f4ebc23cb15e04ff500ed54 &". Coupez les deux premiers caractères du hachage (& Quot; ab & Quot ;, dans notre cas) et faites-en un répertoire. Ensuite, utilisez le reste (& Quot; fab0da6f4ebc23cb15e04ff500ed54 & Quot;), créez le fichier et placez-y des éléments.

De cette manière, vous obtenez des performances assez correctes sur disque (en fonction de votre système de stockage, naturellement) avec une indexation automatique. De plus, vous obtenez un accès direct à tout hachage connu, simplement en calant un délimiteur de répertoire après les deux premiers caractères (& Quot; ./ab/fab0da [..] & Quot;)

Je suis désolé si j'ai complètement manqué le ballon, mais avec un peu de chance, cela pourrait vous donner une idée.

Answer 3

Cela ressemble à un travail pour la base de données Berkeley .

Answer 4

Les autres structures de hachage algo / données basées sur le disque incluent le hachage linéaire et le hachage extensible.

Answer 5

Deux algorithmes me viennent à l’esprit:

• Utilisez un arbre b .
• Séparez les chaînes de hachage en procédant comme si les 10 premiers bits de votre hachage étaient indexés dans l'un des 1024 fichiers individuels, chacun contenant une liste triée de tous les hachages commençant par ces 10 bits. Cela vous donne un saut en temps constant dans un bloc qui doit tenir dans la mémoire, et une recherche de journal (n) une fois que vous avez chargé ce bloc. (ou vous pouvez utiliser 8 bits pour hacher 256 fichiers, etc.)

Answer 6

Etant donné que pour un hachage, vous devez utiliser un accès aléatoire, je doute qu'une base de données vous fournisse des performances décentes. La meilleure solution consiste probablement à augmenter la mémoire cache du disque (plus de RAM) et à obtenir des disques durs avec une vitesse d’accès aléatoire très élevée (peut-être des disques à semi-conducteurs).