En el almacenamiento de datos distribuidos , un P-Grid es un sistema peer-to-peer estructurado y autoorganizado , que puede acomodar distribuciones de claves arbitrarias (y por lo tanto admitir pedidos de claves lexicográficas y consultas de rango), aún proporcionando equilibrio de carga de almacenamiento y búsqueda eficiente utilizando enrutamiento aleatorio.
Características sobresalientes
- Buen equilibrio de carga de almacenamiento a pesar de la distribución de carga arbitraria en el espacio de claves. [1]
- Las consultas de rango se pueden respaldar de forma natural y procesar de manera eficiente en P-Grid porque P-Grid abstrae una estructura trie y admite (más bien) una distribución arbitraria de claves, como se observa en escenarios realistas. [1]
- Se crea un directorio autorreferencial para proporcionar persistencia de la identidad de los pares en varias sesiones. [1]
- Un mecanismo de actualización basado en chismes primitivos para mantener actualizado el contenido replicado. [1]
- Fusión sencilla de múltiples P-Grids y, por tanto, arranque descentralizado de la red P-Grid. [1]
- El almacenamiento en caché adaptable a consultas es fácil de realizar en P-Grid para proporcionar equilibrio de carga de consultas donde los pares tienen capacidad restringida. [1]
Descripción general
P-Grid abstrae un trie y resuelve consultas basadas 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 manera autónoma entradas de enrutamiento elegidas al azar 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 carga de consultas). Por diversas razones, incluida la tolerancia a fallas y el equilibrio de carga, varios pares son responsables de cada nodo hoja en el árbol P-Grid. Estos se llaman réplicas. Los pares de réplicas mantienen una subred de réplicas independiente y utilizan la 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 juntas se denomina replicación estructural. La figura anterior muestra cómo se resuelve una consulta reenviéndola en función de la coincidencia de prefijos. [ cita requerida ]
Consultas de rango en P-Grid
P-Grid divide el espacio clave en una granularidad que se adapta a la carga en esa parte del espacio clave. En consecuencia, es posible realizar una red superpuesta 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 lo hacen las tablas hash distribuidas (DHT) tradicionales . Tenga en cuenta que, a diferencia de P-Grid, los DHT funcionan de manera eficiente solo para distribuciones de carga uniformes. [4]
Por lo tanto, podemos usar una función de preservación de orden lexicográfico para generar las claves, y aún así realizar una red P-Grid con carga equilibrada que admite 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 trie de P-Grid permite diferentes estrategias de consulta de rango, procesadas en serie o en paralelo, compensando los gastos generales de los mensajes y la latencia de resolución de consultas. [5] Los marcos arquitectónicos simples de almacenamiento de datos basados en vectores también están sujetos a limitaciones de consulta de variables dentro del entorno P-Grid. [6]
Referencias
- ↑ a b c d e f Antonopoulos, Nick (2010). Manual de Investigación en Sistemas P2P y Grid para Computación Orientada a Servicios: Modelos, Metodologías y Aplicaciones: Modelos, Metodologías y Aplicaciones . IGI Global. págs. 323–892.
- ^ Ray, Chhanda (2009). Sistemas de bases de datos distribuidas . Pearson Education India. págs. 87-121.
- ^ Jepsen, Thomas (2013). Redes de almacenamiento distribuidas: arquitectura, protocolos y gestión . John Wiley e hijos. págs. 37–79.
- ^ Pitoura, Pitoura; Ntarmos, Nikos; Triantafillou, Peter (2006). Replicación, equilibrio de carga y procesamiento eficiente de consultas de rango en DHT . Conferencia internacional sobre la ampliación de la tecnología de bases de datos. págs. 131-148. doi : 10.1007 / 11687238_11 .
- ^ Datta, A .; Hauswirth, M .; John, R .; Schmidt, R .; Aberer, K. (2005). Consultas de rango en superposiciones estructuradas en trie . Quinta Conferencia Internacional IEEE sobre Computación Peer-to-Peer. págs. 57–66. doi : 10.1109 / P2P.2005.31 . ISBN 0-7695-2376-5.
- ^ Oliker, Leonid; Canning, Andrew; Carter, Jonathan; Shalf, John; Ethier, Stéphane (2008). "Rendimiento de aplicaciones científicas en las principales plataformas de supercomputación escalares y vectoriales". Revista internacional de aplicaciones informáticas de alto rendimiento . 22 : 5-20. doi : 10.1177 / 1094342006085020 . S2CID 5347699 .