2011-11-15 11 views
8

La mia situazione è che attualmente sto memorizzando una gerarchia in un database SQL che si avvicina rapidamente a 15000 nodi (5000 spigoli). Questa gerarchia sta definendo il mio modello di sicurezza basato sulla posizione di un utente nell'albero, garantendo l'accesso agli elementi sottostanti. Quindi, quando un utente richiede un elenco di tutti gli articoli protetti, sto usando CTE per reclamarlo nel db (e appiattire tutti gli elementi), che viene avviato per mostrare la sua età (lento).Come archiviare e leggere in modo efficiente una gerarchia dalla cache

La gerarchia non cambia spesso, quindi ho tentato di spostarlo nella RAM (redis). Tenendo presente che ho molti sottosistemi che hanno bisogno di questo per le chiamate di sicurezza e UI per costruire l'albero per le operazioni CRUD.

primo tentativo

Il mio primo tentativo è quello di memorizzare i rapporti come una coppia di valori chiave (questo è come la sua memorizzati nel database)

 
     E 
    / \ 
    F  G 
/\ /\ 
    H I J K 

mapped to: 
    E - [F, G] 
    F - [H, I] 
    G - [J, K] 

Così quando voglio E e tutti i suoi discendenti, in modo ricorsivo, i suoi figli e i loro figli usano i tasti, e mi permette di iniziare da qualsiasi nodo a scendere. Questa soluzione ha dato un buon aumento di velocità ma con 15.000 nodi, è stato circa 5000 colpi di cache per ricostruire il mio albero nel codice (scenario caso peggiore ... partendo da E. prestazioni si basa sulla posizione dei nodi iniziali, con conseguente super utenti che vedono il peggiore prestazione). Questo era ancora piuttosto veloce ma sembrava loquace. Mi piace il fatto che riesco a rimuovere un nodo in qualsiasi momento saltando fuori dall'elenco delle chiavi senza ricostruire l'intera cache. Questo si stava anche rapidamente accendendo per costruire un albero su richiesta visivamente su un'interfaccia utente.

secondo tentativo

altra mia idea è quella di prendere la Gerarchia dal database, costruire l'albero e memorizzare che nella RAM (Redis) poi tirare l'intera cosa di memoria (era circa 2 MB di dimensioni, serializzato). Questo mi ha dato una chiamata singola (non così chatty) in redis per estrarre l'intero albero, individuare il nodo padre degli utenti e discendere per ottenere tutti gli elementi figlio. Queste chiamate sono frequenti e il passaggio di 2 MB a livello di rete sembrava ampio. Ciò significa anche che non posso aggiungere/rimuovere e aggiungere facilmente elementi senza abbattere l'albero e modificarlo e rimandarlo indietro. Inoltre, su richiesta, la creazione di alberi tramite HTTP significava che ciascuna richiesta doveva abbattere 2 MB per ottenere solo figli diretti (molto piccoli utilizzando la prima soluzione).


Quindi quale soluzione ritiene sia un approccio migliore (a lungo termine mentre continua a crescere). Entrambi sono provocatoriamente più veloci e caricano il database. O è il loro un modo migliore per realizzare ciò a cui non ho pensato?

Grazie

+0

Come hai risolto questo problema? – vishal

risposta

0

Facciamo qualcosa del genere. Leggiamo l'albero in memoria, lo memorizziamo nella cache dell'applicazione e accediamo dalla memoria. Dato che i nostri cambiamenti non sono mai stati quasi mai e le modifiche non devono essere immediatamente riflesse nell'app Web, non ci preoccupiamo nemmeno di rilevarle, ma lasciamo che la cache invecchi e venga aggiornata. Funziona davvero bene per noi.

1

Se la gerarchia non viene modificata spesso, è possibile calcolare l'intero elenco di elementi di seguito per ciascun nodo (anziché solo i bambini diretti). In questo modo avrai bisogno di molto più RAM, ma funzionerà in modo fulmineo per tutti gli utenti, perché sarai in grado di leggere l'intero elenco di nodi discendenti in lettura singola.

Per esempio (userò formato JSON):

E - {"direct" : [F, G], "all" : [F, G, H, I, J, K]} 
F - {"direct" : [H, I], "all" : [H, I]} 
G - {"direct" : [J, K], "all" : [J, K]} 

Beh, per superuser sarà ancora bisogno di trasferire un sacco di dati per ogni richiesta, ma non vedo alcun modo per farlo minore.

+0

- Se la RAM è un problema, è possibile impostare le chiavi con un TTL breve, che svuota gli utenti inattivi subito dopo la disconnessione. – Hristo

+0

- E se si utilizzano i set redis in contrapposizione a JSON o qualche altra stringa per rappresentare i sottonodi, molte operazioni potrebbero essere ottimizzate per controlli semplici come SISMEMBER, ecc., Per mantenere basso il traffico di rete. http://redis.io/commands#set – Hristo

3

Permettetemi di offrire un'idea ...

Usa delle versioni gerarchica. Quando viene modificato un nodo nel grafico, incrementare la sua versione (un campo int semplice nel database), ma anche le versioni di incremento di tutti i relativi antenati..

  • Quando si recupera un sottoalbero dal database per la prima volta, inserirlo nella RAM. (Probabilmente è possibile ottimizzarlo tramite CTE ricorsivo e farlo in un unico round-trip del database.)
  • Tuttavia, la volta successiva che è necessario recuperare lo stesso sottoalbero, recuperare solo la radice. Quindi confronta la versione memorizzata nella cache con la versione appena scaricata dal database.
    • Se corrispondono, ottimo, è possibile interrompere il recupero e riutilizzare solo il cache.
    • In caso contrario, recuperare i bambini e ripetere la procedura, aggiornando la cache man mano che si procede.

Il risultato netto è che il più delle volte, si abbattere il recupero molto presto, di solito dopo un solo nodo, e non sarà nemmeno bisogno di memorizzare nella cache l'intero grafico. Le modifiche sono costose, ma questo non dovrebbe essere un problema poiché sono rari.

BTW, un principio simile funzionerebbe nella direzione opposta, vale a dire quando si inizia con una foglia e occorre trovare il percorso alla radice. Dovresti aggiornare la gerarchia delle versioni nella direzione opposta, ma il resto dovrebbe funzionare in modo molto simile. Potresti anche avere entrambe le direzioni in combinazione.

--- EDIT ---

Se il database e il supporto driver ADO.NET esso, forse vale la pena guardare in notifiche server, ad esempio MS SQL Server SqlDependency o OracleDependency.

In sostanza, si istruisce il DBMS per monitorare le modifiche e avvisare quando si verificano. Questo è l'ideale per mantenere aggiornata la cache lato client in modo efficiente.

+0

Rispetto al mio metodo, questo richiede meno lavoro quando aggiorniamo il nodo e più lavoro quando leggiamo il nodo dalla cache. Penso che dipenda da quando vuoi mostrare un impatto sulle prestazioni agli utenti. Penso che sia più logico rendere più lunghe le richieste di aggiornamento degli alberi per rendere più veloci le seguenti richieste di lettura, piuttosto che diffondere ulteriore lavoro tra le seguenti letture. – mephisto123

+0

@ mephisto123 Non necessariamente.La query iniziale è più costosa nel mio approccio, ma le query successive tenderanno ad essere estremamente economiche, di solito solo una riga. Nel tuo approccio, le query successive dovranno comunque recuperare l'intero sottoalbero, anche se nulla è cambiato. Quindi, il mio approccio è migliore se ci sono più letture ripetute. A proposito, esplodi le dimensioni del database - questo non può essere buono per la memorizzazione nella cache a livello di database, quindi anche le prestazioni di questa prima query sono in questione - un CTE ricorsivo su un piccolo database ben memorizzato potrebbe essere più veloce di un recupero di un BLOB non memorizzato nella cache. –

+0

No, non intendevo salvare intere sottostrutture nel database. Intendevo memorizzare nella cache l'elenco di tutti i nodi discendenti (solo array semplici) poiché la struttura ad albero effettiva non è richiesta spesso, la maggior parte delle volte abbiamo solo bisogno di conoscere l'elenco dei nodi sotto un nodo selezionato e nient'altro. Quindi, se le informazioni per il nodo selezionato sono già memorizzate nella cache, faremo solo una semplice richiesta dalla cache e il gioco è fatto. – mephisto123