Cache efficiente per gruppi di utenti e sottogruppi, indipendentemente dal fatto che un utente appartenga a un gruppo

0

Considera un sistema con un numero finito di utenti e un numero finito di gruppi.

Ad ogni gruppo corrisponde un insieme di utenti. (Diciamo che gli utenti "appartengono direttamente" a un gruppo.)

Gruppi di utenti formano un grafico diretto senza cicli. Se A & rightarrow; B per i gruppi A e B, allora io dico che B è un sottogruppo diretto di A.

Le seguenti operazioni sono definite:

  • aggiungi un utente a un gruppo
  • rimuovi un utente da un gruppo
  • aggiungi un sottogruppo diretto a un gruppo
  • rimuovi un sottogruppo diretto da un gruppo

Si noti che il tentativo di creare un ciclo nel grafico diretto dovrebbe generare un'eccezione.

Potrebbero essere creati anche nuovi utenti e gruppi e utenti e gruppi esistenti potrebbero essere cancellati.

Ho bisogno di memorizzare in modo efficiente queste informazioni, in modo che verificare se un utente (direttamente o indirettamente) appartiene a un gruppo (o ai suoi sottogruppi diretti o indiretti) dovrebbe essere un'operazione veloce. Il caching è fatto da un motore di cache come memcached.

Per favore, riferiscimi ad un efficiente algoritmo di caching. Penso di non essere il primo a risolvere questo problema e c'è un algoritmo noto.

Si noti che scriviamo in linguaggio di programmazione Python.

    
posta porton 15.09.2016 - 22:26
fonte

3 risposte

0

Terzo (più efficiente) algoritmo.

Abbiamo lo stesso caching table come in altre due risposte.

Manteniamo (in memoria o nel DB) il set (diciamolo M) di tutti i gruppi per i quali dovremmo aggiungere o rimuovere utenti insieme agli elenchi di utenti da aggiungere e rimuovere.

Quindi lo facciamo (aggiungi e rimuovi utenti alla tabella di memorizzazione nella cache) nel thread di lavoro, utente uno alla volta o in piccole transazioni.

Tra i passaggi dell'algoritmo precedente, i gruppi di utenti da aggiungere o rimuovere possono essere modificati.

Per sapere quando rimuovere un utente anche da un gruppo genitore quando rimuoviamo l'utente da un gruppo figlio, possiamo usare il conteggio dei riferimenti nella tabella delle relazioni molti-a-molti tra gruppi e utenti.

Nell'insieme M dovremmo anche mantenere il conteggio dei riferimenti di quante volte è stato aggiunto o rimosso un utente. Quando viene rimosso, riduciamo il contatore di riferimento nella tabella della tabella di collegamento molti a molti e rimuoviamo solo se raggiunge lo zero. Quando lo aggiungiamo, incrementiamo il contatore di riferimento nella tabella di collegamento many-to-many.

Quanto sopra sono le mie considerazioni preliminari sull'algoritmo. Dovrebbero essere migliorati rendendo l'algoritmo più dettagliato (per essere degno del nome "algoritmo") e più comprensibile.

    
risposta data 20.09.2016 - 15:19
fonte
0

In primo luogo, la mia prima idea di usare memcached era sbagliata, perché se un utente non effettua il login per un po 'tutti i riferimenti a lui o lei vengono rimossi dalla cache. In questa situazione per verificare se l'utente appartiene a un gruppo di livello superiore tutti i gruppi devono essere controllati. Potrebbe non essere efficiente.

Invece, propongo di aggiungere una tabella DB relazionale con memorizzazione nella cache. Questa tabella conterrà per un determinato gruppo l'insieme di tutti i suoi utenti diretti e indiretti.

Quindi verificare se un utente appartiene a un gruppo diventa completamente semplice.

Anche aggiungere nuovi utenti a un gruppo e aggiungere nuovi sottogruppi è semplice.

Un pensiero più difficile è la rimozione di un utente da un gruppo. Per fare ciò, possiamo:

  1. ottieni il set di tutti i gruppi che contengono direttamente questo utente;

  2. calcola l'insieme di tutti i gruppi che contengono direttamente o indirettamente il primo set;

  3. sottrai questo ultimo set dal set di tutti i gruppi che contengono direttamente o indirettamente questo utente;

  4. rimuovi l'utente da ogni elemento dell'ultimo set.

Bene, non ho ancora deciso come comportarmi quando rimuovo un gruppo (piuttosto che un utente). I commenti sono ben accetti.

    
risposta data 17.09.2016 - 00:40
fonte
0

La precedente soluzione soffre di attacchi DoS (quando un grosso gruppo di utenti cambia il suo gruppo genitore molte volte, ciò può causare ritardi e persino un overflow di query. Quindi, qui propongo una soluzione alternativa.

Come nella soluzione precedente, aggiungiamo una tabella DB relazionale con memorizzazione nella cache. Questa tabella conterrà per un determinato gruppo l'insieme di tutti i suoi utenti diretti e indiretti.

Utilizzando un mutex globale (in effetti, un blocco di file consultivo) eseguo il processo di lavoro (quello che aggiorna il DB) in non più di un processo / thread simultaneamente.

Contrassegniamo (con un flag booleano) alcune tabelle come "ha bisogno di aggiornamento".

All'inizio del processo recuperiamo l'insieme di tabelle che necessitano di aggiornamento e costruiamo un grafo diretto aciclico delle dipendenze tra tali tabelle.

Iniziamo il processo di aggiornamento effettivo iniziando con i nodi foglia di questo grafico.

Questo processo legge in memoria il set di utenti per una determinata tabella e quindi uno a uno rimuove e aggiunge righe corrette.

Il processo sopra menzionato potrebbe essere interrotto da un mutex (probabilmente un valore nel database). In questo caso il gruppo viene contrassegnato come bisognoso di aggiornamento e il processo ricomincia dall'inizio.

Il processo viene interrotto se una nuova attività arriva in coda.

Quanto sopra sono le mie considerazioni preliminari sull'algoritmo. Dovrebbero essere migliorati rendendo l'algoritmo più dettagliato (per essere degno del nome "algoritmo") e più comprensibile.

    
risposta data 20.09.2016 - 14:47
fonte

Leggi altre domande sui tag