Pastry es una red superpuesta y una red de enrutamiento para la implementación de una tabla hash distribuida (DHT) similar a Chord . Los pares clave-valor se almacenan en una red peer-to-peer redundante de hosts de Internet conectados . El protocolo se inicia proporcionándole la dirección IP de un par que ya está en la red y, a partir de ahí, a través de la tabla de enrutamiento que se construye y repara dinámicamente. Se afirma que, debido a su naturaleza redundante y descentralizada, no hay un único punto de falla y cualquier nodo puede abandonar la red en cualquier momento sin previo aviso y con poca o ninguna posibilidad de pérdida de datos. El protocolo también es capaz de utilizar una métrica de enrutamiento proporcionada por un programa externo, como ping o traceroute , para determinar las mejores rutas para almacenar en su tabla de enrutamiento.
Aunque la funcionalidad de tabla hash distribuida de Pastry es casi idéntica a la de otras DHT , lo que la distingue es la red de superposición de enrutamiento construida sobre el concepto de DHT . Esto permite a Pastry lograr la escalabilidad y la tolerancia a fallas de otras redes, al mismo tiempo que reduce el costo general de enrutar un paquete de un nodo a otro al evitar la necesidad de inundar los paquetes. Debido a que la métrica de enrutamiento es suministrada por un programa externo basado en la dirección IP del nodo de destino, la métrica se puede cambiar fácilmente a la cantidad de saltos más corta, la latencia más baja, el ancho de banda más alto o incluso una combinación general de métricas.
El espacio de claves de la tabla hash se considera circular, como el espacio de claves del sistema Chord , y los identificadores de nodo son números enteros sin signo de 128 bits que representan la posición en el espacio de claves circular. Los identificadores de nodo se eligen de forma aleatoria y uniforme, de modo que los pares adyacentes en el identificador de nodo sean geográficamente diversos. La red de superposición de enrutamiento se forma sobre la tabla hash cuando cada par descubre e intercambia información de estado que consiste en una lista de nodos hoja, una lista de vecindad y una tabla de enrutamiento. La lista de nodos hoja consta de los pares más cercanos L /2 por identificador de nodo en cada dirección alrededor del círculo.
Además de los nodos de hoja, también existe la lista de vecindad. Esta representa los M pares más cercanos en términos de la métrica de enrutamiento. Aunque no se utiliza directamente en el algoritmo de enrutamiento, la lista de vecindad se utiliza para mantener los principios de localidad en la tabla de enrutamiento.
Por último, está la tabla de enrutamiento propiamente dicha. Contiene una entrada para cada bloque de dirección que se le asigna. Para formar los bloques de direcciones, la clave de 128 bits se divide en dígitos, cada uno de los cuales tiene una longitud de b bits, lo que da como resultado un sistema de numeración con base 2 b . Esto divide las direcciones en distintos niveles desde el punto de vista del cliente, donde el nivel 0 representa un prefijo común de cero dígitos entre dos direcciones, el nivel 1 un prefijo común de un dígito, y así sucesivamente. La tabla de enrutamiento contiene la dirección del par conocido más cercano para cada dígito posible en cada nivel de dirección, excepto el dígito que pertenece al par en sí en ese nivel en particular. Esto da como resultado el almacenamiento de contactos por nivel, con un número de niveles que se escala como . Los valores de y representan valores operativos en una red típica.
Un paquete puede ser enrutado a cualquier dirección en el espacio de claves, ya sea que haya un par con ese ID de nodo o no. El paquete se enruta hacia su lugar apropiado en el anillo circular y el par cuyo ID de nodo esté más cerca del destino deseado recibirá el paquete. Siempre que un par recibe un paquete para enrutar o desea enviar un paquete, primero examina su conjunto de hojas y enruta directamente al nodo correcto si encuentra uno. Si esto falla, el par consulta su tabla de enrutamiento con el objetivo de encontrar la dirección de un nodo que comparte un prefijo más largo con la dirección de destino que el propio par. Si el par no tiene ningún contacto con un prefijo más largo o el contacto ha muerto, elegirá un par de su lista de contactos con el mismo prefijo de longitud cuyo ID de nodo esté numéricamente más cerca del destino y enviará el paquete a ese par. Dado que la cantidad de dígitos correctos en la dirección siempre aumenta o permanece igual (y si permanece igual, la distancia entre el paquete y su destino se hace más pequeña), el protocolo de enrutamiento converge.
Pastry especifica cómo se distribuyen las claves entre los nodos y cómo se puede encontrar el nodo responsable de almacenar una clave. Al utilizar esto como sustrato para un protocolo superior , Pastry puede implementar funciones como un sistema de archivos distribuido, un sistema de suscripción y publicación o cualquier otro sistema que pueda reducirse a almacenar valores y recuperarlos más tarde.
PAST es un sistema de archivos distribuido en capas sobre Pastry. Un archivo se almacena en el sistema calculando el hash de su nombre de archivo. Luego, Pastry envía el contenido del archivo al nodo en el espacio de claves circular más cercano al hash obtenido del nombre de archivo. Este nodo enviará copias del archivo a los k nodos más cercanos a la clave real, la mayoría de los cuales probablemente sean nodos hoja de este nodo y, por lo tanto, directamente accesibles. La recuperación de datos se logra rehaciendo el nombre del archivo y enviando una solicitud de datos a través de Pastry al lugar adecuado en el espacio de claves. La solicitud puede ser atendida por cualquiera de los k nodos que tienen copias de los datos. Esto logra tanto la redundancia de datos como la distribución de la carga. Dado que los nodos adyacentes en el espacio de claves son geográficamente diversos, las probabilidades de que todos ellos se desconecten al mismo tiempo son muy pequeñas. Más importante aún, dado que el protocolo de enrutamiento de Pastry busca minimizar la distancia recorrida, es probable que el nodo más cercano a la máquina que realizó la solicitud (según la métrica) sea el que responda con los datos.
SCRIBE es un sistema de publicación/suscripción descentralizado que utiliza Pastry para la gestión de rutas subyacente y la búsqueda de host. Los usuarios crean temas a los que otros usuarios pueden suscribirse. Una vez que se ha creado el tema, el propietario del tema puede publicar nuevas entradas bajo el tema que se distribuirán en un árbol de multidifusión a todos los nodos SCRIBE que se han suscrito al tema. El sistema funciona calculando el hash del nombre del tema concatenado con el nombre del usuario que posee el tema. Este hash se utiliza luego como una clave de Pastry y el editor enruta los paquetes al nodo más cercano a la clave utilizando el protocolo de enrutamiento de Pastry para crear el nodo raíz del tema en ese nodo. Las personas luego se suscriben al tema calculando la clave a partir del tema y el nombre del editor y luego utilizando Pastry para enrutar un mensaje de suscripción al tema hacia el nodo raíz. Cuando el nodo raíz recibe el mensaje de suscripción de otro nodo, agrega el ID del nodo a su lista de hijos y comienza a actuar como un reenvío del tema.
La descentralización se logra haciendo que todos los nodos de la red espíen los mensajes de suscripción que pasan por ellos en su camino hacia el nodo raíz del tema. Si el tema es uno al que el nodo actual está suscrito, dejará de reenviar el paquete hacia el nodo raíz y agregará el nodo que intenta suscribirse como uno de sus hijos. De esta manera, se forma una estructura en forma de árbol con el nodo raíz en la parte superior enviando a los primeros nodos suscriptores y luego cada uno de estos nodos reenvía los mensajes a sus hijos, y así sucesivamente. Debido a que los paquetes de nodos aleatorios en la red Pastry destinados al mismo nodo a menudo terminan viajando por el mismo camino muy pronto en su viaje, terminan adhiriéndose a cualquier parte del árbol que esté más cerca de ellos en la red Pastry. Dado que cada salto a lo largo de una ruta Pastry representa lo que es localmente la mejor ruta de acuerdo con la métrica de enrutamiento en uso, el mensaje de suscripción busca la parte más cercana del árbol y se adhiere allí.
Finalmente, la tolerancia a fallos entre los miembros del árbol de distribución se logra mediante el uso de tiempos de espera y de keepalives, con transmisiones de datos reales que se duplican como keepalives para minimizar el tráfico. Si un nodo secundario no recibe noticias de su padre durante un tiempo, envía un nuevo mensaje de suscripción hacia el nodo raíz del árbol, y se vuelve a conectar donde sea que se encuentre con el árbol para ese tema. Si un padre no recibe noticias de un hijo durante un período de tiempo de espera, elimina al hijo de su lista de hijos. (Si esta acción hace que su lista de hijos se vacíe, el padre deja de actuar como reenviador por completo). El único punto de falla restante es el del nodo raíz, y Pastry lo supera automáticamente. Debido a que Pastry duplica las claves entre los pocos nodos más cercanos al valor real de la clave, el nodo raíz ya tiene espejos configurados, que permanecen inactivos. Si el nodo raíz se desconecta, nuevamente detectado a través de tiempos de espera, el siguiente nodo Pastry más cercano comenzará a actuar como nodo raíz. Cuando el creador del tema intenta publicar material nuevo, el nodo raíz antiguo no se puede alcanzar. El editor recurrirá entonces a la red Pastry y la utilizará para enviar su mensaje de publicación al nuevo nodo raíz. Una vez hecho esto, el editor almacena en caché una copia de la dirección IP del nuevo nodo raíz para reducir el uso de la red Pastry para futuras transmisiones.
