J'ai besoin de stocker un grand groupe de hachage, capable de contenir jusqu'à environ 200 valeurs de 40 milliards de dollars. Le stocker en 200 millions de 64 bits serait acceptable (malgré la perte de 200 millions de dollars).
Les exigences sont:
Empreinte de mémoire minuscule (espace disque n'est pas un problème, la mémoire est)
fast incorporé
GRATUIT ET SANS NASTY LICENCES (NO BERKELEY DB). LGPL FINE.
pas de faux positif et non faux négatif, des choses comme des filtres de floraison à base de disque ne sont pas ce que je suis après
SQL est pas ce que je suis après ici.
Parce que je pense vraiment que je suis plus après quelque chose rapide comme ceci (remarquez comment la solution est beaucoup plus rapide qu'une solution SQL):
HASHTables à base de disque rapide?
Google a-t-il une API de Java?
serait une mise en œuvre de la paire de clé / de la paire de valeur basée sur un disque rapide où je n'utiliserais que la "touche" travail?
ou quelque chose d'autre?
Je préfère ne pas réinventer la weel. contient (long L) et ajouter (long L) méthodes (beaucoup plus vite que SQL)
3 Réponses :
Si vous pouvez vous permettre 128 Go de disque, vous pouvez stocker un bit par valeur de 40 bits. Vous pouvez ensuite utiliser un fichier d'accès aléatoire pour vérifier un bit est défini ou pour la modifier. Vous n'auriez pas besoin d'insérer des valeurs ni de maintenir un index.
@Peter Lawrey: Intéressant ... Fait intéressant, j'avais une autre question, avant cela, pour autre chose, où j'ai demandé quel était le moyen le plus rapide de Java pour obtenir une recherche aléatoire dans les grands fichiers :) Malheureusement, cela n'est pas possible dans mon cas: doit être installé sur plusieurs ordinateurs. Quelques gigaoctets vont bien, mais 128 est trop :( J'aime l'approche qui a dit ...
Vous pouvez également utiliser un filtre de floraison qu'il prend à peu près 6 bits pendant 1% de faux taux positif détecte si la clé est présente. Si c'est l'opération que vous recherchez. Si les données sont statiques, un arbre avec un ventilateur élevé est également possible.
Je pense que vous devrez utiliser un arbre B plutôt que d'une table de hachage. Les tables de hachage n'ont pas de bonne localité pour le stockage secondaire, vous perdrez donc trop de temps sur le disque I / O.
La plupart des bases de données - relationnelles ou non - implémentent leurs index en tant qu'ebre B. Vous parlez de sorte que vous parlez de l'équivalent de stocker un index avec aucune autre donnée jointe à celle-ci.
aurez-vous plusieurs processus mis à jour simultanément ce magasin de données?
Essayez SG-CDB (port étrange gizmo du CDB de DJB), puis échangez le randomAccessFile avec un bufferedrandomAccessfile (il y a un bon dans le code Jai-imageoo).
Je tiens à donner des performances en écriture. À travers le toit (Cuz, tout est tamponné, alors commis dans un swoop châpé). Les performances de lecture pour le raf en mémoire tampon ne sont pas modifiées, cependant.
Je pourrais prendre le temps de comparer avec H2 Bulk Import, pourrait être comparable mais pas sûr.
La base de données est simple: clé => valeur. Recherche uniquement prise en charge sur la clé. Les clés sont dans mon boîtier (base32 codé aléatoire INTS + base32 codé unique int) de sorte que la localité ne devrait pas vraiment aider beaucoup. Les valeurs sont des matrices de 120 octets aléatoires.
4 mai 2011 11:45:10 Test.TestH2Simple Main : Inserts effectués ajoutés dans: 101625 MS
Taille de la base de données: Environ 140 Mo
Taille du lot: 2000 : Inserts effectués ajoutés dans: 116875 MS
Taille du lot: 10000 : InsertFormé Ajouté en: 70234 MS
avec aléatoireAccessfile: Insérer sans affleurement: 21688 MS, Flush: 30359 ms, Total: 52047 MS Taille du fichier sur le disque: 66.1 MB (69 315 632 octets)
avec bufferedrandomAccessfile: environ 6,5 secondes
Bien sûr, ce n'est pas vraiment une comparaison juste, car H2 rinçage des données de manière continue pendant l'insert, alors que le SG-CDB n'est pas. Cela doit naître à l'esprit lors de la comparaison. Probablement juste serait de comparer l'insert SG-CDB avec H2 Bulk Insert
: recherché: 490000 Terminé sur: 1304544550439 A pris: 17547 MS, Compteur: 0
: Sélectionne effectué dans: 19579 MS
En ce qui concerne les fichiers mappés de mémoire: Ils ne semblent pas être ce que vous cherchez. La grande performance avec les fichiers MMAP est lorsque vous mappez environ 100 Mo ou plus dans la mémoire (mon expérience).
200 millions sont environ 28 bits.
@Thorbjorn: Je parle de stocker 200 millions de valeurs, chacune d'entre eux correspond à 40 bits. Je n'ai jamais parlé de stocker des valeurs pouvant contenir une valeur allant jusqu'à 200 millions :)
Hors de curiosité, avez-vous essayé avec SQLite, etc.? Je n'ai vu aucune preuve dans la question que vous avez liée à la journalisation OP désactivée, ou même créé des index ...
@Steven Huwig: non et j'ai spécifié SQL n'était pas ce que je ne faisais pas quoi après ... Quand je parlais de quelque chose rapide J'avais plus en tête des réponses comme la seule Peter Lawrey a fait :) pensez-vous honnêtement pensez-vous que dans la réponse liée au dépollution, le réglage SQLite viendrait n'importe où près de la réponse acceptée, qui indique spécifiquement qu'il fonctionne autour des cercles SQL? Nous ne nous soucions pas des propriétés relationnelles, ni des garanties d'acide, etc. SQL pour un problème aussi simple est un Massive Overbloat. Un marteau d'or en d'autres termes.
"Cercles en cours" (la phrase réelle dans le poteau est "incroyablement plus rapide") est à peine quantitative, ni la méthodologie de "réglage" tenté de la SQLite de manière adéquate de manière adéquate dans le poste. Ma question reste - avez-vous déjà mis en œuvre une solution trop lente, si oui, quelle est la solution et combien plus vite doit-il être? L'optimisation prématurée est la racine de tout Mal.
@Steven Huwig: Nous faisons l'informatique haute performance à l'aide de Java (et Java est bon à cela en fait). Le nom du jeu est l'optimisation. J'ai demandé à une question très spécifique, pas trop noobaine, question et expressément dit que SQL n'était pas ce que j'étais après. Je ne suis pas après "SQL" et "XML" Type de réponse. Je suis après des réponses comme la seule Peter Lawrey faite.
Vous pourriez exclure SQL pour les mauvaises raisons, en utilisant l'une des bases de données intégrées (qui disposent d'une interface SQL) n'est pas la pire idée. Surtout si vous avez besoin d'une certaine protection de cohérence.