stoccaggio ottimale di struttura dati per la ricerca veloce e persistenza

Question

Scenario

Ho i seguenti metodi:

public void AddItemSecurity(int itemId, int[] userIds)
public int[] GetValidItemIds(int userId)

Inizialmente Sto pensando di archiviazione sul modulo:

itemId -> userId, userId, userId

e

userId -> itemId, itemId, itemId

AddItemSecurity si basa su come ottenere i dati da una terza parte API, GetValidItemIds è come voglio usarlo in fase di esecuzione.

Ci sono potenzialmente 2000 utenti e 10 milioni di pezzi. iD articolo è nel modulo:. 2.007.123,456 mila, 2010001234 (10 cifre in cui primi quattro rappresentano l'anno)

AddItemSecurity non ha per eseguire super veloce, ma ha bisogno GetValidIds essere inferiore al secondo. Inoltre, se v'è un aggiornamento su un itemId esistente ho bisogno di rimuovere quel itemId per gli utenti non è più nella lista.

Sto cercando di pensare a come devo conservare questo in modo ottimale. Preferibilmente su disco (con la cache), ma voglio il codice mantenibile e pulita.

Se la voce id avevano cominciato a 0, ho pensato di creare un array di byte la lunghezza del MaxItemId / 8 per ogni utente, e impostare un vero falso bit / se l'oggetto fosse presente o meno. Ciò limitare la lunghezza della matrice di poco più di 1 MB per utente e invia ricerche veloci e anche un modo semplice per aggiornare l'elenco per utente. Persistendo questo come memoria mappata Dello .Net 4 quadro penso che avrei avuto il caching decente come bene (se la macchina ha abbastanza RAM) senza implementare la logica di caching me stesso. Analisi del id, escludendo l'anno, e memorizzare una matrice all'anno potrebbe essere una soluzione.

L'ItemId -> UserId [] lista può essere serializzato direttamente su disco e lettura / scrittura con un FileStream normale al fine di persistere lista e diff quando ci sono modifiche

.

Ogni volta che si aggiunge un nuovo utente tutte le liste devono aggiornati pure, ma questo può essere fatto ogni notte.

Domanda

Devo continuare a provare questo approccio, o ci sono altre strade che dovrebbero essere esplorati come bene? Sto pensando di SQL Server non eseguirà abbastanza veloce, e darei un overhead (almeno se è ospitato su un server diverso), ma la mia ipotesi potrebbe essere sbagliata. Ogni pensiero o approfondimenti sulla questione è apprezzato. E voglio cercare di risolverlo senza aggiungere troppo hardware:)

[Update 2010-03-31]

Ora ho provato con SQL Server 2008 nelle seguenti condizioni.

• Tabella con due colonne (ID utente, itemid) entrambe sono Int
• indice cluster su due colonne
• aggiunta ~ 800.000 articoli per 180 utenti - totale di 144 milioni di righe
• RAM assegnata 4GB per SQL Server
• Dual Core a 2,66 GHz portatile
• disco SSD
• Usa uno SqlDataReader per leggere tutte le itemid di in un List
• Loop su tutti gli utenti

Se corro uno medie filo IT su 0,2 secondi. Quando aggiungo un secondo filo che va fino a 0,4 secondi, che è ancora ok. Da lì i risultati diminuiscono. Aggiungere un terzo filo porta un sacco di query fino a 2 seonds. Una via filo, fino a 4 secondi, un quinto picchi alcune delle domande rivolte fino a 50 secondi.

La CPU è copertura, mentre questo è in corso, anche su un thread. La mia applicazione di test richiede un po 'a causa del ciclo veloce, e SQL il resto.

Il che mi porta alla conclusione che non scala molto bene. Almeno non sul mio hardware testato. ci sono modi per ottimizzare il database, dire la memorizzazione di un array di int di per utente invece di un record per ciascun elemento. Ma questo rende più difficile rimuovere elementi.

[Update 2010-03-31 # 2]

Ho fatto un rapido test con gli stessi dati di metterlo come bit in file di memoria mappata. Si rende molto di più. Sei le discussioni rendimenti tempi di accesso tra 0.02s e 0.06s. Puramente di memoria legato. I file mappati sono stati mappati da un processo, e accessibili da altri sei contemporaneamente. E come la base sql ha 4gb, i file sul disco ha preso 23MB.

Answer 1

Dopo molte prove ho finito per usare file mappati in memoria, contrassegnandoli con il po 'scarsa (NTFS), utilizzando il codice da NTFS Sparse file con C # .

Wikipedia contiene una spiegazione di ciò che un sparse il file è.

I vantaggi di utilizzare un file sparse è che non ho a cura di ciò che vanno i miei ID sono. Se scrivo solo id tra il 2006 milioni e 2.010.999,999 mila, il file verrà allocare solo 625.000 byte da compensare 250.750.000 nel file . Tutto lo spazio fino a quel offset è allocato nel file system. Ogni ID viene memorizzato come un po 'insieme nel file. Sorta di trattato come un array bit. E se la sequenza id cambia improvvisamente, allora assegnerà in un'altra parte del file.

Al fine di recuperare i cui ID sono impostato, posso effettuare una chiamata sistema operativo per ottenere le parti assegnate del file sparse, e poi controllare ogni bit in quelle sequenze. Anche controllare se un particolare id è impostato è molto veloce. Se non rientra nei blocchi allocati, allora non c'è, se cade all'interno, è solo un byte leggere e una maschera di bit di controllo per vedere se è impostato il bit corretto.

Così, per il particolare scenario in cui si dispone di molte id cui si desidera controllare con la massima velocità possibile, questo è il modo più ottimale io ho trovato finora.

E la parte buona è che i file mappati in memoria possono essere condivisi con Java come pure (che si è rivelato essere qualcosa di necessario). Java ha anche il supporto per la memoria mappata file su Windows, e l'implementazione della logica di lettura / scrittura è abbastanza banale.

Answer 2

Credo davvero che si dovrebbe provare un bel database prima di prendere la decisione. Qualcosa di simile sarà una sfida per mantenere nel lungo periodo. Il tuo base di utenti è in realtà abbastanza piccola. SQL Server dovrebbe essere in grado di gestire quello che ti serve senza problemi.

Answer 3

2000 utenti non è male, ma con 10 elementi correlati mil davvero dovrebbe valutare l'ipotesi di questo in un database. DB fare tutto lo stoccaggio, la persistenza, l'indicizzazione, la memorizzazione nella cache, ecc che avete bisogno e si comportano molto bene.

Inoltre, consentono una migliore scalabilità verso il futuro. Se improvvisamente necessario trattare con due milioni di utenti e miliardi di impostazioni che hanno un buon db in atto farà scalare un non-problema.