Cómo almacenar y leer una jerarquía de manera eficiente desde el caché

Question

Mi situación es que actualmente estoy almacenando una jerarquía en una base de datos SQL que se acerca rápidamente a los 15000 nodos (5000 bordes). Esta jerarquía es la definición de mi modelo de seguridad basado en una posición de los usuarios en el árbol, otorgando acceso a los elementos a continuación. Entonces, cuando un usuario solicita una lista de todos los elementos asegurados, estoy usando CTE para recurse en el archivo db (y aplanar todos los elementos), que se inicia para mostrar su edad (lenta).

La jerarquía no cambia con frecuencia, así que he intentado moverla a la RAM (redis). Teniendo en cuenta que tengo muchos subsistemas que necesitan esto para llamadas de seguridad, y UI para construir el árbol para operaciones CRUD.

primer intento

Mi primer intento es almacenar las relaciones como un par de valores clave (esta es la forma de su almacenado en la base de datos)

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

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

Así que cuando quiero E y todos sus descendientes, recursivamente obtengo su hijo y su hijo usando las teclas, y me permite comenzar en cualquier nodo para bajar. Esta solución dio un buen aumento de velocidad pero con 15,000 nodos, fue aproximadamente 5000 visitas de caché para reconstruir mi árbol en código (peor escenario posible ... comenzando en E. el desempeño se basa en la ubicación de los nodos iniciales, lo que resulta en superusuarios que ven el peor rendimiento). Esto todavía era bastante rápido, pero parecía ser parlanchín. Me gusta el hecho de que puedo eliminar un nodo en cualquier momento saliéndolo de las listas de teclas sin reconstruir todo el caché. Esto también se estaba iluminando rápidamente para construir un árbol según demanda en una interfaz de usuario.

segundo intento

Mi otra idea es tomar la Jerarquía de la base de datos, construir el árbol y almacenar que en la memoria RAM (Redis) luego tire toda la cosa fuera de la memoria (que era aproximadamente 2 MB en tamaño, serializado). Esto me dio una sola llamada (no tan hablador) en redis para extraer todo el árbol, ubicar el nodo padre de los usuarios y descender para obtener todos los elementos secundarios. Estas llamadas son frecuentes y la transferencia de 2 MB en la capa de red parecía grande. Esto también significa que no puedo agregar/eliminar fácilmente y el elemento sin tirar hacia abajo del árbol y editarlo y empujarlo hacia atrás. Además, la creación de árboles a pedido a través de HTTP significaba que cada solicitud tenía que reducir 2 MB para obtener solo hijos directos (muy pequeños con la primera solución).

---

Entonces, ¿qué solución cree que es un mejor enfoque (a largo plazo, ya que sigue creciendo). Ambos son desafiantemente más rápidos y toman algo de carga de la base de datos. ¿O es una mejor manera de lograr esto que yo no haya pensado?

Gracias

Answer 1

Hacemos algo como esto. Leemos el árbol en la memoria, lo almacenamos en la memoria caché de la aplicación y accedemos a él desde la memoria. Dado que nuestros cambios casi nunca, y los cambios no tienen que reflejarse inmediatamente en la aplicación web, ni siquiera nos molestamos en detectarlos, simplemente dejemos que el caché envejezca y se actualice. Funciona realmente bien para nosotros.

Answer 2

Si la jerarquía no se cambia con frecuencia, puede calcular toda la lista de elementos a continuación para cada nodo (en lugar de solo los secundarios). De esta forma necesitará significativamente más RAM, pero funcionará a la velocidad del rayo para cualquier usuario, ya que podrá leer toda la lista de nodos descendientes en una sola lectura.

Para su ejemplo (utilizaré 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]} 

Bueno, para superusuarios que todavía tendrá que transferir una gran cantidad de datos por petición, pero no veo ninguna manera de hacerlo menor.

Answer 3

Permítanme ofrecer una idea ...

uso de versiones jerárquica. Cuando se modifica un nodo en el gráfico, incremente su versión (un campo int simple en la base de datos), pero también incrementa las versiones de todos sus antecesores.

• Al obtener un subárbol de la base de datos por primera vez, almacénelo en caché en la memoria RAM. (Probablemente pueda optimizar esto mediante CTE recursivo y hacerlo en una única base de datos de ida y vuelta.)
• Sin embargo, la próxima vez que necesite recuperar el mismo subárbol, recupere solo la raíz. Luego, compare la versión almacenada en caché con la versión que acaba de obtener de la base de datos.
  • Si coinciden, genial, puede detener la búsqueda y solo reutilizar la caché.
  • Si no lo hacen, busque a los niños y repita el proceso, actualizando la memoria caché sobre la marcha.

El resultado neto es que más a menudo que no, usted Cull el ir a buscar muy temprano, por lo general después de un solo nodo, y que ni siquiera tendrá que almacenar en caché todo el gráfico. Las modificaciones son costosas, pero esto no debería ser un problema ya que son raras.

Por cierto, un principio similar funcionaría en la dirección opuesta, es decir, cuando comienzas con una hoja y necesitas encontrar el camino a la raíz. Debería actualizar la jerarquía de versiones en la dirección opuesta, pero el resto debería funcionar de una manera muy similar. Incluso podría tener ambas direcciones en combinación.

--- --- EDITAR

Si su base de datos y ADO.NET soporte de controladores que, podría ser vale la pena analizar notificaciones del servidor, tales como MS SQL Server o SqlDependencyOracleDependency.

Esencialmente, le ordena al DBMS que supervise los cambios y le avise cuando ocurran. Esto es ideal para mantener su caché del lado del cliente actualizado de una manera eficiente.