Qual è il modo migliore di adattare questo sistema di sicurezza per gestire l'ereditarietà multipla?

Question

Cinghia, questa è una domanda complicata.

Abbiamo un sistema che si occupa di grandi set di dati. (da milioni a miliardi di dischi per tavolo grande). Tutti i dati sono gestiti in una struttura ad albero di nodi.

Utilizziamo Symfony2 e il sistema di sicurezza Symfony2 (Oggetti dominio, Acl, Aces ecc.). Il nostro albero Acl rispecchia il nostro albero dei nodi.

a coniare una lingua:

• DP permesso definito, vale a dire un record di ace su questo nodo ACL
• EP permessi efficace, nessun record asso, autorizzazione ereditata da un genitore con un DP

Per logica aziendale, assegniamo 0 o 1 asso a un oggetto per utente e ci affidiamo all'ereditarietà dove non ce n'è. Root > lvl1 (DP: VIEW) > lvl2 > lvl3 (EP: VIEW)

Finora, tutto bene. Tutto funziona.

Alcuni nodi non solo hanno un genitore, ma sono associati ad altri nodi (molti a molti). Quando un nodo è associato a un altro nodo, questo rappresenta un percorso separato nell'albero da seguire per gli ACL. IE avremmo 1 o più percorsi sull'albero da radicare per raccogliere gli assi.

Leaf < Parent < GrandParent < Root 
Leaf < AssociatedNode < AssociatedNodeParent < AssociatedNodeGrandParent < Root 
... 

o la logica per gestire la votazione degli assi va bene, ciò che siamo sicuri di è come rappresentare i percorsi multipli contro l'albero. La nostra attuale (leggi: cattivo) le idee sono:

• comportamento genitore multipla nella struttura di ACL
  • Pro
    • Sembra più pulito?
  • Contro
    • Quasi tutta la riscrittura del sistema di sicurezza per mettere questo in.
    • ratsnesting potenziale.
• identità duplicate degli oggetti/ACL contro entità, specificando genitori diversi.
  • Pro
    • Er ...
  • Contro
    • creerà una grande quantità di record ACL potenzialmente.
    • Difficile da gestire nel codice.

Answer 1

Nel tuo caso genitore multipla, si sono effettivamente un albero di attraversamento inversa dal nodo iniziale a qualsiasi nodo che contiene un asso. Quindi, se visualizziamo le operazioni di spostamento verso l'alto e laterale come il proprio albero (loop di potatura), potresti, potenzialmente, cercare l'intera rete di nodi prima di trovare un asso nel peggiore dei casi.

Il modo più semplice per risolvere questo problema è garantire una forma di heap property che assicuri che ciascun nodo con un asso abbia un valore grande o piccolo che possa guidare l'attraversamento. Questo riduce il tempo di attraversamento dal caso peggiore O(n) (se hai cercato ogni nodo nell'indice del database) a O(log n) mentre esegui il backpath attraverso la rete.

Il motivo per cui il passaggio da O(1) qui è difficile è che la rete del nodo garantisce la possibilità di loop. Ma se si costruisce un grafico ACL mantenendo le proprietà di, ad esempio, un heap minimo, si dovrebbe essere a posto.

Buona fortuna con il modello di autorizzazioni.

Answer 2

Ancora una volta, come notato, questo è un problema interessante, ma non banale - grazie! Ora so come devo passare questo fine settimana :-) Potrei prendere in considerazione anche l'idea dell'heap, ma lo renderei un heap a thread. Ogni nodo nell'heap contiene un puntatore a un "indice" ACL, se lo si desidera.

Presupposto Ho solo tre nodi nell'esempio (R (oot), P (non lo sono) e N (ode)). Pertanto, l'ACL impostato per N è ACL (R) + ACL (P) + ACL (N). Supponiamo che quando viene creato un nodo, quel nodo contenga un puntatore X che punta a un indice del nodo. Quindi R (X) = ACLIndex (R). Nessun nodo vero contiene il suo ACL.

Ora, per un dato nodo N, devo ancora inseguire dalla radice nel peggiore dei casi, ma sto semplicemente saltellando attorno a un indice piatto per farlo piuttosto che rimbalzare su tutto l'albero. Sarebbe meglio se si potesse fare l'asserzione che per un dato nodo N, c'è solo un percorso per N, o, se ci sono più percorsi, N mantiene un'altra tabella di attraversamenti tale che, per N, Percorso (N) da il nodo A è ascoltato in quella tabella. In effetti, devi lasciare i breadcrumb in N quando un nodo si collega ad esso.

Mi chiedo se possiamo prendere in prestito un concetto dalla geolocalizzazione. Non è possibile per il tuo piccolo GPS portatile mantenere tutti i possibili percorsi di percorso più breve da qualsiasi punto a qualsiasi punto e tenere a mente i tempi del traffico. Truffa e divide le mappe in "tessere" Dato che non puoi essere in tutto la mappa allo stesso tempo, ma piuttosto sei limitato a una tessera in cui sei attualmente, deve solo calcolare i percorsi più brevi dall'interno esiste una tessera alla sua conosciuta. Una volta presa un'uscita, carica quella tessera e si ripete. In effetti, usiamo il principio di località per ridurre l'ambito.

E se usassimo la stessa idea? Per un dato nodo, se hai diviso l'albero di accesso in "shard", potresti pre-calcolare i costi o almeno aggiornarli, e quindi il costo del percorso da R a N è semplicemente la somma dei costi di shard più il costo del percorso nel tuo frammento locale.