Cos'è un modo scalabile e pratico per cercare l'esistenza di un gruppo di stringhe in un file enorme

Naviga le tue risposte
3

Contesto : ho creato un'app che genera intorno a 1000 nomi di dominio in base all'input dell'utente. Devo controllare se sono disponibili o meno confrontando un enorme file di zona con nomi di dominio analizzati che si trova intorno a 2 GB .

Ho un'istanza micro di Amazon e non posso memorizzare il file di testo lì a causa di vincoli di spazio. Mi aspetto circa 100k - 200k e più in query di ricerca al mese.

Approccio ingenuo (Potenzialmente): 1. Archivia il file di testo in dropbox. Quindi recupera il contenuto del file e cerca le stringhe e sputa i nomi di dominio disponibili nell'istanza EC2.

Ho solo bisogno di controllare se i domini esistono o meno. Devo memorizzarlo in un database?

Alcune informazioni: attualmente sono registrati 100 milioni di nomi di punti com in base a Verisign. E i miei nomi di dominio analizzati sono uno su ogni riga. Come:

  • GOOGLE
  • APPLE
  • FACEBOOK
  • STACKOVERFLOW ecc.

Qual è il modo migliore e pratico per affrontare il problema? Idealmente il controllo dovrebbe richiedere solo pochi secondi. Ma sto bene con tutto ciò che funziona a questo punto.

    
posta endrendum 15.03.2014 - 01:08
fonte

2 risposte

3

a) un motore di indicizzazione, come Lucene

b) Filtro Bloom link

c) È possibile utilizzare uno schema di hashing della chiave semplice e dividere i domini con un semplice "modulo hash N" per suddividere il lavoro su più datastore (semplici).

  • BTW 2GB è piccolo. Si potrebbe facilmente fare tutto in memoria.

  • Inoltre, poiché hai già normalizzato le tue stringhe in un formato standard, mi concentrerei sull'archiviazione e sulla ricerca degli hash delle stringhe piuttosto che delle stringhe stesse.

...

Full disclosure: probabilmente li conserverei in un database.

    
risposta data 15.03.2014 - 02:03
fonte
0

Should I have to store it in a database?

Questa sarebbe la soluzione più semplice. Cerca una libreria di database leggera (non transazionale)

Un'altra idea sarebbe quella di convertire il file di zona in un elenco di parole compresse, trattando ogni nome di dominio come una "parola". Questo ti darà una compressione migliore e, se scegli lo schema giusto, dovresti essere in grado di ottenere una ricerca rapida e accurata senza conservare l'intero "file" in memoria.

Una variazione su quanto sopra sarebbe di trattare i componenti del nome come parole e trattarli come un problema di ricerca di testo libero. Costruire un indice inverso e trattare la ricerca di un nome di dominio come ricerca di un insieme di parole; per esempio. "www.example.com" è una ricerca per "www" AND "example" AND "com". Questo è molto più complicato, ma potrebbe dare una compressione migliore in generale, e ti permetterebbe di fare altre domande.

C'è molta letteratura sul tema della ricerca del testo ...

Mettere il file (originale) in un servizio file esterno e recuperarlo / cercarlo è una cattiva idea. Ci vuole una notevole quantità di tempo per lo streaming di un file da 2 GB da una macchina all'altra su Internet ... e probabilmente finirai per pagare la larghezza di banda I / O che stai utilizzando. Sarebbe meglio pagare in anticipo per l'archiviazione sull'infrastruttura Amazon.

    
risposta data 15.03.2014 - 01:35
fonte

Leggi altre domande sui tag

Dove devo mettere i binding per l'iniezione di dipendenza? Interfacce segreganti / preoccupazioni per un albero