¿Cuál es la mejor manera de adaptar este sistema de seguridad para tratar la herencia múltiple?

Question

Ponte cómodo, esta es una pregunta difícil.

Tenemos un sistema que se ocupa de grandes conjuntos de datos. (millones a mil millones de registros por mesa grande). Todos los datos se manejan en una estructura en árbol de nodos.

Estamos utilizando Symfony2 y el sistema de seguridad Symfony2 (objetos de dominio, Acls, Ases, etc.). Nuestro árbol Acl refleja nuestro árbol de nodos.

acuñar un lenguaje:

• DP permiso definido, es decir, un registro as en este nodo acl
• EP permiso efectivo, no hay registro de la ECA, el permiso heredado de un padre con un DP

En lógica de negocios, asignamos 0 o 1 ace a un objeto por usuario, y confiamos en la herencia donde no hay ninguno. Root > lvl1 (DP: VIEW) > lvl2 > lvl3 (EP: VIEW)

Hasta ahora, muy bien. Todo esto funciona

Algunos nodos no solo tienen un elemento principal, sino que están asociados a otros nodos (muchos a muchos). Cuando un nodo está asociado a otro nodo, esto representa una ruta separada en el árbol para que las sigan. Es decir, tendríamos 1 o muchas rutas en el árbol para rootear para obtener As.

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

O lógica para la gestión de la votación de los ases está muy bien, lo que no estamos seguros de cómo es para representar los múltiples caminos hasta el árbol. Nuestro actual (es decir: las malas) ideas son:

• el comportamiento de los padres múltiple en el árbol acl
  • Pros
    • Parece más limpio?
  • Contras
    • Casi toda reescritura del sistema de seguridad para poner esto en.
    • ratsnesting potencial.
• identidades duplicados de objetos/ACL contra entidades, especificando diferentes padres.
  • Pros
    • Er ...
  • Contras
    • creará una cantidad muy grande de registros potencialmente acl.
    • Es difícil de administrar en el código.

Answer 1

En su caso los padres múltiples, que tienen efectivamente un recorrido de árbol inversa de su nodo inicial a cualquier nodo que contiene un as. Por lo tanto, si visualizamos las operaciones de desplazamiento hacia arriba y lateral como su propio árbol (bucles de poda), podría, potencialmente, buscar en toda su red de nodos antes de encontrar un as en el peor de los casos.

La manera más fácil de resolver esto sería garantizar algún tipo de heap property que asegure que cada nodo con un as tenga un valor grande o pequeño que pueda conducir el recorrido. Esto toma el tiempo de recorrido del peor de los casos O(n) (si buscó cada nodo en su índice de base de datos) a O(log n) a medida que avanza por la red.

El motivo por el cual obtener O(1) recorrido aquí es difícil es que su red de nodos garantice la posibilidad de bucles. Pero, si construyes un gráfico ACL manteniendo las propiedades de, por ejemplo, un montón mínimo, deberías estar bien.

La mejor de las suertes con su modelo de permisos.

Answer 2

Una vez más, como se señaló, este es un problema interesante, pero no trivial, ¡gracias! Ahora sé cómo tengo que pasar este fin de semana :-) También podría considerar la idea del montón, pero lo convertiría en un montón. Cada nodo en el montón contiene un puntero a un "índice" de ACL, si lo desea.

Supongamos que tengo solo tres nodos en el ejemplo (R (oot), P (are not) y N (ode)). Por lo tanto, el conjunto de ACL para N es ACL (R) + ACL (P) + ACL (N). Suponga que cuando se crea un nodo, ese nodo contiene un puntero X que apunta a un índice de nodo. Entonces R (X) = ACLIndex (R). Ningún nodo en sí contiene su ACL.

Ahora, para un nodo N dado, todavía tengo que perseguir desde la raíz en el peor de los casos, pero simplemente estoy saltando alrededor de un índice plano para hacerlo en lugar de rebotar por todo el árbol. Sería mejor si pudiera hacer la afirmación de que para un nodo dado N, solo hay una ruta a N, o, si hay varias rutas, N mantiene otra tabla de recorridos tales que, para N, Ruta (N) desde el nodo A se escucha en esa tabla. En efecto, debe dejar migas de pan en N cuando un nodo se adhiere a él.

Me pregunto si podemos tomar prestado un concepto de geolocalización. No es posible que su pequeño GPS de mano mantenga todas las rutas de ruta más cortas posibles desde cualquier punto a cualquier punto, y tenga en cuenta los tiempos de tráfico. Trucos y divide los mapas en "mosaicos". Como no puedes recorrer todo el mapa al mismo tiempo, sino que estás limitado a un mosaico en el que te encuentras actualmente, solo necesita calcular los caminos más cortos desde dentro. ese azulejo a su conocido existe. Una vez que tomas una salida, carga ese mosaico y se repite. En efecto, usamos el principio de localidad para reducir el alcance.

¿Qué pasa si utilizamos la misma idea? Para un nodo dado, si dividió el árbol de acceso en "fragmentos", puede precomputar los costos o al menos actualizarlos, y luego el costo de la ruta de R a N es simplemente la suma de los costos del fragmento más el costo de la ruta en tu fragmento local