Sistema de búsqueda distribuido sobre Pastry overlay p2p.

Enero 13, 2008 in Cube Platform, Grid Computing, p2p

Una de las necesidades más importantes en un sistema p2p puro, en el que todos los nodos desempeñan el mismo papel, es poder encontrar los que se necesita en el menor tiempo posible. Al fin y al cavo, no sirve de nada poseer datos distribuidos si no se puede acceder a ellos. En redes como Gnutella, que emplean el método de la inundación, la búsqueda es sencilla. Un nodo A necesita un contenido, por ejemplo un pdf que hable sobre sistemas linux. El usuario escribe un patrón de búsqueda: “sistemas Linux”. La cadena de búsqueda es enviada por el nodo A a todos sus contactos, y cada uno de estos la reenvia a los suyos… etc. Esto tiene que parar, pues la profundidad de un arbol de búsqueda de este tipo puede ser enorme y el tráfico que genera diréctamente proporcional. El número de saltos máximo para la búsqueda viene dado por el hops-to-lives. Cada nodo, al recibir la petición, realiza una exploración en su contenido y contestará al nodo A con los datos que concuerden con la cadena de búsqueda o parte de ella.

En el caso de una red tipo Pastry, como la empleada por Madagascar, es algo distinto. Para implmentar este mecansmo de búsqueda sería necesario realizar un broadcast a los nodos y eso sería muy costoso. Para realizarlo, lo más cómodo es emplear la aplicación Scribe que permite comunicaciones en grupo mediante Treecasting, es decir, los nodos se organizan a modo de árbol en el que cada elemento es responsable de comunicar el mensaje a sus hijos. Este sistema es muy efectivo para realizar streaming de video o audio, por ejemplo. Centrándonos en el tema de las búsquedas, lo mejor sería aprovechar la característica innata de una red como pastry: Los nodos se organizan en orden, de acuerdo a los 160 bits que designan a cada elemento.

Para entrar en contexto, una red pastry es una overlay p2p con estructura en anillo en el que los mensajes viajan del origen al destino saltando por nodos intermedios que están cada vez más cerca del nodo que debe recibir el mensaje. Sobre esta estructura se puede montar una tablas hash distribuida (DHT) que permite subir cualquier contenido y ser hubicado en el nodo que le corresponda. Esta es la forma en la que madagascar almacena los contenidos subidos por los usuarios.

El sistema de búsqueda lo describiré teniendo en cuenta la forma de trabajo de madagascar.

Bien, imaginemos que hemos subido un determinado contenido al anillo: una pelicula titulada “hora punta”. Entonces tenemos un fichero fs al que le pasamos SHA-1 y obtenemos su firma, a la que llamaremos fsSignature, que es única. El segundo paso es aplicar SHA-1 a cada uno de los elementos clave del título: hora , punta y obtenemos lo que se llaman token hash, uno por cada elemento clave. Ahora podemos crear una tupla con el siguiente formato:

[<token hash1>,<token hash2>, fsSignature]

De esta forma, este contenido lo podemos hubicar en el anillo mediante una DHT, como PAST, enviando la tupla a los nodos más cercanos a cada uno de los token hashs. A la tupla también le podemos añadir metadatos como, por ejemplo, el título original del contenido.

Ahora el Nodo A realiza la búsqued de “hora punta”: El sistema obtiene las palabras clave y les aplica SHA-1. Tras esto, le dice a la la DHT que recupere esas claves. Lo que hará el sistema es enviarle al nodo A todas las tuplas que contengan la palabra hora y la palabra punta. El usario selecciona la que le interese y recupera el fichero fs realizando la petición de nuevo a la DHT. Una vez tenga el fichero fs, puede obtener el contenido original.