En el almacenamiento de datos distribuidos , un P-Grid es un sistema peer-to-peer estructurado y autoorganizado que puede admitir distribuciones de claves arbitrarias (y, por lo tanto, admitir el ordenamiento de claves lexicográficas y consultas de rango), y al mismo tiempo proporcionar equilibrio de carga de almacenamiento y búsqueda eficiente mediante enrutamiento aleatorio.
P-Grid abstrae un trie y resuelve consultas basándose en la coincidencia de prefijos. La topología real no tiene jerarquía. Las consultas se resuelven mediante la coincidencia de prefijos. Esto también determina la elección de las entradas de la tabla de enrutamiento. Cada par, para cada nivel del trie, mantiene de forma autónoma entradas de enrutamiento elegidas aleatoriamente de los subárboles complementarios. [2] De hecho, se mantienen múltiples entradas para cada nivel en cada par para proporcionar tolerancia a fallas (así como potencialmente para la gestión de la carga de consultas). Por diversas razones, incluida la tolerancia a fallas y el equilibrio de carga, varios pares son responsables de cada nodo de hoja en el árbol P-Grid. Estos se denominan réplicas. Los pares de réplica mantienen una subred de réplica independiente y utilizan una comunicación basada en chismes para mantener actualizado el grupo de réplicas. [3] La redundancia tanto en la replicación de particiones de espacio de claves como en la red de enrutamiento en conjunto se denomina replicación estructural. La figura anterior muestra cómo se resuelve una consulta al reenviarla en función de la coincidencia de prefijos. [ cita requerida ]
P-Grid divide el espacio de claves en una granularidad que se adapta a la carga en esa parte del espacio de claves. En consecuencia, es posible realizar una red superpuesta de P-Grid donde cada par tiene una carga de almacenamiento similar incluso para distribuciones de carga no uniformes. Esta red probablemente proporciona una búsqueda de claves tan eficiente como las tablas hash distribuidas (DHT) tradicionales. Tenga en cuenta que, a diferencia de P-Grid, las DHT funcionan de manera eficiente solo para distribuciones de carga uniformes. [4]
Por lo tanto, podemos utilizar una función de preservación del orden lexicográfico para generar las claves y, al mismo tiempo, lograr una red P-Grid con equilibrio de carga que admita la búsqueda eficiente de claves exactas. Además, debido a la preservación del orden lexicográfico, las consultas de rango se pueden realizar de manera eficiente y precisa en P-Grid. La estructura de trie de P-Grid permite diferentes estrategias de consulta de rango, procesadas en serie o en paralelo, compensando la sobrecarga de mensajes y la latencia de resolución de consultas. [5] Los marcos arquitectónicos de almacenamiento de datos simples basados en vectores también están sujetos a limitaciones de consultas variables dentro del entorno P-Grid. [6]