struttura su disco per memorizzare una grande serie di numeri interi 128 bit?

Question

Ho circa 500 milioni di numeri interi a 128 bit, l'aggiunta di circa 100M all'anno. Nulla è mai cancellato. I numeri vengono ad una distribuzione uniforme, scala-saggio e tempo-saggio.

In sostanza, tutti bisogno I è un'operazione di aggiunta che anche restituisce se il numero esiste già nel DB. Inoltre, non voglio usare troppa RAM per questo sistema, quindi basta immagazzinando tutto in memoria non è quello che sto cercando.

Finora siamo stati utilizzando diverse tabelle MyISAM su MySQL, utilizzando due bigints come una chiave primaria. Questo ci dà prestazioni OK, ma ho il sospetto che non è lo strumento giusto per questo lavoro. Abbiamo avuto alcuni problemi di prestazioni prima di tavoli di scissione, e abbiamo avuto corruzioni su interruzioni di corrente. Inoltre, un DB ci dà molti più caratteristica che non abbiamo bisogno.

sto usando Python su Linux, ma sono aperto a suggerimenti.

domanda simile in C ++ .

UPDATE: il commento di Marcelo menzionato Bloom Filter , che sembra promettere davvero a me. Dal momento che sto lavorando con hash, ho già rinunciato a una precisione assoluta, quindi questo potrebbe essere un grande commercio di precisione / prestazioni off.

Answer 1

Inserisci ogni intero in uno di un pool di 2 ⁿ SQLite database (2 ⁸ è probabilmente un buon numero) scelti calcolando un n hash bit del numero intero. Fare quella colonna della una tabella una chiave primaria, in modo che il tentativo di inserire un numero esistente non riesce.

Supponendo che gli interi sono già abbastanza casuale, probabilmente si può semplicemente prendere, per esempio, il byte meno significativo come "hash".

EDIT: Ho fatto alcuni test. Ho inserito 25 milioni di voci in circa due ore, ma ha inghiottito oltre 1 GB nel processo. Questo viene fatto generazione di numeri casuali e di distribuirli a 32 sottoprocessi, ciascuno con il database SQLite uno sotto il suo controllo e si impegna una volta ogni 100.000 inserti. Inserimenti sono attualmente chugging lungo a circa 1350 Hz, ben oltre i 3 Hz vostre esigenze problema, ma l'intero database ancora si inserisce nella cache (ho 8 GB di RAM). Non voglio conoscere le prestazioni in regime stazionario a meno che non mi avvicino alle dimensioni del database corrente. A quel punto, ogni inserimento indurrà almeno quattro movimenti del disco a testa (leggere e scrivere l'indice e la tabella, probabilmente più di drill-down in B + tree), e allora saprete quanto dolore siete veramente dentro per .

sto iniziando a pensare che questo è un problema veramente interessante che potrebbe essere risolto in modo più efficiente con una soluzione su misura. Tuttavia, ho il sospetto che ci vorrà una quantità ragionevole di sforzo per sovraperformare in modo significativo un motore di database.

Answer 2

Hash tuoi hash?