Repositorio Institucional de Documentos

Proyecto Finalde Carrera Ingenier´ıa Inform´atica Curso 2011-2012 Dise˜no eimplementaci´on de una capa de red P2P jer´arquica, escalable ytolerante afallos V´ıctor Miguel Catal´an S´anchez Septiembre de 2012 Director: Javier CelayaAlastru´e Departamento de Inform´atica eIngenier´ıa de Sistemas Escuela de Ingenier´ıa yArquitectura Universidad de Zaragoza Ami tutor, por su respaldo ydedicaci´on durante este tiempo. Ami madre, por su apoyo incondicional, ysu entrega de toda una vida Ami familia, por apoyarme en todo momento. Amis amigos ycompa˜neros por todas las ayudas recibidas. Yami novia, por ser como eres yestar siempreami lado. Dise˜no eimplementaci´on de una capa de red P2P jer´arquica, escalable ytolerante afallos. Resumen Durante este proyectose ha dise˜nado eimplementado una capa de red peer-to-peer jer´arquica, escalable ytolerante afallos. Dicha capa es un medio que nos permite la distribuci´on de la informaci´on yla localizaci´on de recursos aemplear por otras plataformas. Esta capa est´aenmarcada en el desarrollo de una plataforma escalable para la ejecuci´on distribuida de tareas. Se ha utilizado una estructura principal en forma de ´arbol binario balanceado oAVL. Las b´usquedas en este tipo de ´arboles tienen una complejidad que se mantiene siempre en orden logar´ıtmico O(log n), por lo que es perfecta para cumplir el requisito de la escalabilidad. Otro punto fundamental es la tolerancia afallos, en cuyocaso se resuelve utilizando una DHT como estructura paralela, donde se almacenar´ala informaci´on actualizada de todos los nodos de la red. En caso de fallo de un nodo, cualquier participante puede obtener la informaci´on relativa a dicho nodo einiciar el proceso de reconstrucci´on que permite devolver ala red aun estado correcto. Entre las distintas opciones de DHT, se ha elegido Apache Cassandra ym´as en concreto la librer´ıa libQtCassandra, que es un cliente que proporciona una API para interaccionar con los nodos de Cassandra. En definitiva, se ha desarrollado un protocolo de comunicaci´on totalmente distribuido, que permite trabajar de maneraconjunta ala estructura en forma de ´arbol yla DHT. El lenguaje utilizado es C++ por ser el lenguaje que se usa en la plataforma en la que este proyecto est´aenmarcado. Para comprobar el buen funcionamiento, se ha utilizado un simulador de eventos discretos. Con el objetivo de comprobar la escalabilidad, se han simulado redes de tama˜nos desde 10 nodos hasta 500.000 nodos. Posteriormente, se vuelven a simular losmismos tama˜nos yadem´as se introducen fallos de nodos f´ısicos aleatorios para comprobar la tolerancia afallos. Una vez concluyela simulaci´on, se comprueba el resultado por medio de pruebas de validaci´on del estado de los participantes de la red. El resultado obtenido tras la realizaci´on de todas las pruebas con el simulador es el correcto, con lo que se puede afirmar que la red se adapta perfectamente acualquier tama˜no de red yadem´as detecta los fallos que se producen para posteriormente reconstruir la red. Adem´as se han obtenido medidas del consumo del ancho de banda de entrada yde salida obteniendo valores muy buenos ycasi despreciables. Tambi´en se ha medido el tiempo de inserci´on de un nodo en la red yse puede concluir que para redes grandes de 100.000 nodos en adelante, el tiempo se estabiliza alrededorde 2,25 segundos, siendo un valor que se considera aceptable. Asimismo se ha ejecutado la aplicaci´onen un grupodeordenadores del laboratorio y se ha conseguido interconectarlos. La red se ha creado yfunciona correctamente, por lo que la prueba en un escenarioreal tambi´en es un ´exito. ´ Indice 1. Introducci´on 1 1.1. Objetivos .................................... 2 1.2. Organizaci´on de este documento . . . . . . . . . . . . . . . . . . . . . . . . 2 2. An´alisis del problema 3 2.1. Arquitectura de la red ............................. 3 2.2. Tolerancia afallos ................................ 4 2.3. Interfaz externa ................................. 4 3. Dise˜no de la soluci´on 6 3.1. Arquitectura de la red ............................. 6 3.2. Operaciones de la red .............................. 8 3.2.1. Concurrencia .............................. 8 3.2.2. Inserci´on ................................. 9 3.2.3. Rotaciones ................................ 10 3.2.4. Otras Operaciones ........................... 13 3.3. Tolerancia afallos ................................ 14 3.3.1. Tiempos de espera de las operaciones ................. 15 3.3.2. Detecci´on de fallos ........................... 15 3.3.3. Elecci´on del coordinador . . . . . . . . . . . . . . . . . . . . . . . . 16 3.3.4. Reconstrucci´on de la red . . . . . . . . . . . . . . . . . . . . . . . . 16 4. Implementaci´on de la soluci´on 19 4.1. Entorno de programaci´on ............................ 19 4.2. Detalles de laimplementaci´on ......................... 19 vi 4.3. Simulador .................................... 20 4.4. Medidas del c´odigo fuente ........................... 20 5. Simulaci´on yprueba real 21 5.1. Pruebas con el simulador ............................ 21 5.1.1. Escenario ................................ 21 5.1.2. Comprobaci´on del resultado . . . . . . . . . . . . . . . . . . . . . . 22 5.1.3. Validaciones b´asicas .......................... 22 5.1.4. Validaci´on en caso de churn . . . . . . . . . . . . . . . . . . . . . . 23 5.1.5. Consumo de Ancho de Banda ..................... 24 5.1.6. Tiempomedio de inserci´on . . . . . . . . . . . . . . . . . . . . . . . 25 5.2. Prueba escenario real .............................. 26 6. Conclusiones 27 6.1. Trabajo futuro ................................. 27 6.2. Valoraci´on Personal ............................... 28 Bibliograf´ıa 29 A. Despliegue Apache Cassandra 31 A.1. Nodo de Apache Cassandra . . . . . . . . . . . . . . . . . . . . . . . . . . 31 A.2. LibQtCassandra ................................. 33 B. C´odigo Fuente 34 B.1. Mensajes ..................................... 34 B.2. N´ucleo de la Estructura ............................ 45 B.3. Simulador ....................................133 C. GNU General Public License 149 vii ´ Indice de figuras 2.1. Visi´on global de todo el proyecto por capas .................. 5 3.1. Diagrama de clases de los nodos de estructura, de recurso yde la descripci´on de zona ..................................... 7 3.2. Esquema diferencial entre un ´arbol AVL ysu correspondiente nuevo ´arbol dise˜nado. ..................................... 7 3.3. Diagrama de secuencia de la inserci´on. Caso general ............. 9 3.4. Representaci´on del antes ydespu´es de la inserci´on .............. 10 3.5. Representaci´on del antes ydespu´es de la rotaci´on LL yRR ......... 11 3.6. Diagrama de secuencia de la rotaci´on LL yRR ................ 12 3.7. Representaci´on del antes ydespu´es de la rotaci´on LR yRL ......... 13 3.8. Antes ydespu´es de reconstrucci´on de un nodo de recurso .......... 16 3.9. Reconstrucci´on siendo padre ehijo . . . . . . . . . . . . . . . . . . . . . . 17 3.10. Reconstrucci´on sin ninguna relaci´on . . . . . . . . . . . . . . . . . . . . . . 18 5.1. Misma situaci´on resaltando los nodos involucrados en la reconstrucci´on del nodo 92 y38 de manera independiente. .................... 24 5.2. Medidas del uso delancho de banda de salida respecto al n´umero de nodos de la red. .................................... 25 5.3. Medidas del uso del ancho de banda de entrada respecto al n´umero de nodos dela red. ................................. 25 5.4. Medida del tiempo de inserci´on del ´ultimonodo que accedealared respecto del n´umero de nodos de la red ......................... 26 viii 3. Dise˜no de la soluci´on Apartir de las decisiones que se han tomado enel cap´ıtulo de an´alisis, se va a detallar la estructura jer´arquica, el mantenimiento de dicha estructura yla conectividad entre los nodos participantes enla red. 3.1. Arquitectura de la red La estructura yla gesti´on del ´arbol que conforma la arquitectura de la red se deriva del trabajo sobre ´arboles binarios balanceados, tambi´en llamados ´arboles AVL[2] aunque con ciertas modificaciones. En primer lugar, el par de la direcci´on IP-Puerto ser´ael valor identificativoque represente a cada nodo f´ısico de forma un´ıvoca en la red. Este par identificativose utiliza tambi´en como clavepara acceder alos datos de la DHT. En la estructura jer´arquica cada nodo f´ısico interpreta dos roles, un nodo con rol de estructura (Structure Node) yun nodo con rol de recurso (Resource Node). Cada rol que interpreta un nodo f´ısico est´alocalizado en una posici´on dentro del ´arbol, destacando que dichas posiciones no guardan ninguna relaci´on entre s´ı. Los nodos con rol de estructura tienen un enlace con su padre yun enlacecon cada uno de sus hijos, izquierdo yderecho. Adem´as guarda la descripci´onde zona de cada hijo, es decir, la informaci´on relativa a cada sub´arbol, que permitir´aencaminar losmensajes. La descripci´on de zona contiene la direcci´on m´ınima ym´axima, la altura yqu´erama es la m´as alta para cada sub´arbol. Por otra parte, los nodos de recurso tienen un ´unico enlace con su padre. Existe un cambio importante yaque los hijos de los nodos de estructura no se sit´uanala izquierda o a la derecha de un valor. Cada nodo de estructura guarda el intervalo de direcciones de sus sub´arboles que representan las tablas de encaminamiento para las operaciones de la red.En la figura 3.1 se puede observar m´as claramente los detalles. Los nodos con rol de estructura ser´an los nodos internos en el ´arbol ylos que nos permitir´an ir recorriendo el ´arbol hasta encontrar el recurso que se est´ebuscando. Siempre tendr´an hijos yasean dos nodosde estructura, dos nodos de recurso oun nodo de estructura yotro de recurso. Los nodos con rol de recurso siempre se encontrar´an en las 6 3. Dise˜no de la soluci´on 3.1 Arquitectura dela red Nodo de Recurso (RN) +padre +descripZona +recibirMensaje() +enviarMensaje() +notificarZonaPadre() +commit() +rollback() Nodo de Estructura(SN) +padre +hijoIzquierdo +descrIzquierdo +hijoDerecho +descrDerecho +estado +recibirMensaje() +enviarMensaje() +notificarZonaPadre() +recomputeZone() +reconstruir() +commit() +rollback() Descripción de Zona +minima +maxima +altura +hijoMaximo +operador==() +operador<() +getMinima() +getMaxima() +getAltura() +getHijoMaximo() Figura 3.1: Diagramade clases de los nodos de estructura, de recurso yde la descripci´on de zona hojas inferiores del ´arbol ysu padre siempre ser´aun nodo interno de estructura. Esta divisi´on en roles permite separar el mantenimiento de la estructura, que seproduce en los nodos de estructura, del uso del recurso perteneciente a cada nodo. En la figura 3.2 se puedenver las diferencias entre un ´arbol AVL yel dise˜nado, teniendo en cuenta que los rect´angulos representan los nodos de estructura ylos c´ırculos los nodos de recurso, as´ıcomo la DHT que almacena la informaci´on. En el ´arbol dise˜nado siempre se 1 2 3 4 5 6 7 8 D H T 1 6 2 6 1 28 4 35 7 3 23 47 67 8 8 5 45 Nodo de Recurso Nodo de Estructura Leyenda Figura 3.2: Esquema diferencial entre un ´arbol AVL ysu correspondiente nuevo ´arbol dise˜nado. cumplir´aque el n´umero de nodos totales (suma de los que interpretan el rolde estructura yde recurso) es el doble de nodos f´ısicos menos uno. Esto es debido aque por cada nodo 7 3. Dise˜no de la soluci´on 3.2 Operaciones de la red f´ısico siempre se introduce un nodo interpretando el rol de estructura yotro nodo con el rol de recurso salvoel primer nodo que solo introduce un nodo con el rol de recurso, ya que la red es el propio nodo de recurso. 3.2. Operaciones de la red Existen tres operaciones relacionadas con la estructura de la red: La inserci´on, que permite a˜nadir nuevos nodos ala red. Las rotaciones, que permiten cambiar la estructura del ´arbol sin interferir en el orden de los elementos modificados haciendo que los nodos est´en balanceados. La gesti´on de fallos, que nos permite reconstruir la estructura de la red ante fallos. Existen otras operaciones m´as simples que ayudan amantener la estructura como son las actualizaciones de zona yla comprobaci´on de la diferencia de altura. 3.2.1. Concurrencia En entornos distribuidos, poder realizar m´ultiples operaciones al mismo tiempoes vital. Sin embargo, cuando varias operaciones utilizan los mismos recursos hayque organizar c´omo se llevan a cabo todas las operaciones sin interferir en las dem´as. Esta organizaci´on permite mantener la consistencia de la red yes lo que se denomina concurrencia de las operaciones. La concurrencia en ´arboles AVL se ha estudiado ampliamente en [7] [14]. Para resolver la concurrencia dela capa de red se toma la decisi´on de usar transacciones[11]. Las transacciones nos permiten llevar a cabo una tarea independientemente del resto. Esto nos asegura que la tarea se realice de una sola vez ysin quese altere en medio de una modificaci´on. Cada tarea generaun identificador de transacci´on ´unico que se env´ıa alos recursos involucrados. Existe un identificador de transacci´on nulo que representa que un recurso est´alibre. Por este motivo, antes de empezar una tarea es necesario comprobar si el recurso este libre yal finalizar una tarea hayque liberar el recurso asignando el identificador nulo. El uso de las transacciones se implementa con el protocolo de commit en dos fases (Two-Phase-Commit)[13]. Es un algoritmo distribuido que permite atodos los nodos participantes ponerse de acuerdo paratomar una decisi´on. En este algoritmo hayun coordinador que es el que inicia la transacci´on. Las dos fases del algoritmo son la fase de petici´on de commit, en la cual el coordinador intenta preparar atodos los dem´as participantes, yla fase de commit, en la cual el coordinador completa las transacciones atodos los dem´as. El resultado del protocolo es que todos los nodos realizan el cambio 8 3. Dise˜no de la soluci´on 3.2 Operaciones de la red (Commit) o abortan (Rollback) la transacci´on. Se ha elegido este protocolo por su sencillez yreducido n´umero de mensajes. Aparte de lo comentado anteriormente ala hora de tomar las decisiones si un nodo est´ainvolucrado en dos transacciones se establece que las inserciones tienen preferencia frente alas rotaciones. Si un nodo est´arotando yrecibeun mensajede inserci´on toma la decisi´on de abortar la rotaci´on einiciar la inserci´on. Esta decisi´on se debeaque la inserci´on se realiza en las hojas del ´arbol, por lo que cuando ´esta finalice yse actualicen los nodos afectados ysucesivos hacia arriba, en caso de que sea necesario se iniciar´anuevamente la rotaci´on. Las inserciones entre s´ıno tienen preferencia yse realiza la que llega en primer lugar, retrasando una que llegue m´as tarde. En cuanto alas rotaciones tiene preferencia una rotaci´on que se inicie m´as abajo en el ´arbol. Al finalizar la rotaci´on yse realicen las actualizaciones de los implicados se volver´a a iniciar la rotaci´on en caso de ser necesario. En elcaso de una reconstrucci´on, ´esta siempre tendr´apreferencia sobre el resto, yaque al haber un nodo ca´ıdo involucrado no se puede llevar abuen t´ermino la transacci´on. En este caso para el correcto funcionamiento ymantenimiento de la consistencia de la estructura, se abortanlas transacciones involucradas yse inicia la reconstrucci´on. 3.2.2. Inserci´on La inserci´on es la operaci´on que permite a˜nadir nuevos nodos ala red. La secuencia de acciones arealizar est´adescrita en eldiagrama de secuencia de la figura 3.3.En el Nuevo NodoA: SN Nuevo NodoA: RN NodoB Red: RN Padre NodoB: SN Nuevo Driver: RNNodos Red: SN Padre Driver: SN InsertCommandMsg() InsertMsg(A) InsertMsg(A) InsertMsg(A) InsertMsg(A) InsertMsg(A) Flag Final True InsertFinalMsg(idT,A) InsertFinalMsg(idT) InsertFinalMsg(idT,PadreDriver) AckMsg(idT) AckMsg(idT) AckMsg(idT) CommitMsg(idT) CommitMsg(idT) CommitMsg(idT) UpdateZoneMsg() UpdateZoneMsg() UpdateZoneMsg() Figura 3.3: Diagrama de secuencia de la inserci´on. Caso general caso general, el nuevonodo (nodo A) que se quiere insertar en la red debecontactar con 9 3. Dise˜no de la soluci´on 3.2 Operaciones de la red alg´un nodo (nodo B) conocido que yaest´eformando parte de la red. El nodo Aenv´ıa un mensaje de inserci´on (InsertMsg) al nodo B. Este mensaje lo recibir´aun nodo de recurso que lo retransmite hacia arriba, asu padre. El nodo de estructura compara la direcci´on del nodo Acon su descripci´on de zona. Si la direcci´on est´acomprendida en su intervalo de direcciones retransmite el mensaje por la rama que corresponda, izquierda oderecha, o de lo contrario el mensaje es retransmitido al padre. El mensaje vasubiendo por los nodos de estructura repitiendo el proceso hasta que la direcci´on est´ecomprendida en el intervalo de direcciones ollegue al nodo ra´ız. Llegados aeste punto, el mensaje desciende atrav´es de las ramas adecuadas hasta llegar ala hoja que ser´aun nodo de recurso, que se convierte en el coordinador de la transacci´on. El coordinador env´ıa mensajes (InsertFinalMsg) alos nodos implicados para informarles de cu´al ser´asu siguiente estado. Los nodos implicados son el coordinador, el padre del coordinador, yel nuevonodo (nodo A) de estructura yde recurso. Una vez todos se ponen de acuerdo yse realiza la inserci´on, el coordinador yel nuevonodo de recurso son hermanos ytienen como padre al nuevonodo de estructura. Asu vez, el nuevonodo de estructura tiene como padre el que era padre del coordinador, como se puede ver en la figura 3.4 aclaratoria. A A B CB B CA AB Figura 3.4: Representaci´on del antes ydespu´es de la inserci´on Tras realizar la inserci´on, cada nodoinvolucrado en ella debeactualizar su descripci´on de zona, ypara ello se utilizan los mensajes UpdateZoneMsg. Estos mensajes recorren el ´arbol desde las hojas hacia arriba seg´un se explica en la secci´on 3.2.4. 3.2.3. Rotaciones La rotaci´on es la operaci´on que permite cambiar la estructura del ´arbol sin interferir en el orden delos elementos modificados. Esta operaci´on se inicia siempre en un nodo de estructura con el objetivo de mantener balanceado dicho nodo. El objetivoes equilibrar la altura de las ramas izquierda yderecha, permitiendo una diferencia m´axima de una unidad. El resultado de una rotaci´on es la reestructuraci´on del ´arbol. Se equilibran las 10 3. Dise˜no de la soluci´on 3.2 Operaciones de la red alturas moviendo los sub´arboles m´as peque˜nos hacia abajo ylos sub´arboles m´as altos hacia arriba. Existen cuatro posibles rotaciones que se pueden aplicar. En este apartado se explica c´omo se llevan a cabo cada una de las rotaciones, yposteriormente se analiza cuando hay que realizar cada una. Debido aalgunas inconsistencias en la definici´on de las direcciones de las rotaciones, se ha tomado la decisi´on de definirlas indicando que direcci´on, derecha oizquierda, de los sub´arboles es la m´as alta. Debido ala simetr´ıa que existe se pueden dividir en dos grupos. a) Rotaci´on Derecha-Derecha (RR) yRotaci´on Izquierda-Izquierda (LL) Las rotaciones RR yLL son sim´etricas.La rotaci´on RR se usa cuando el sub´arbol derecho sea dos unidades m´as alto que el izquierdo, yasu vez el sub´arbol derecho del hijo derecho sea una unidad m´as alto que el izquierdo. Llegados aeste punto se procede del siguiente modo: Pasamos el sub´arbol izquierdo del hijo derecho como sub´arbol derecho del nodo ra´ız de la rotaci´on. Esto mantiene el ´arbol ordenado, yaque todos los valores del sub´arbol movido siguen siendo mayores que los queten´ıamos en el sub´arbol derecho. El nodo ra´ız de la rotaci´on pasa aser el sub´arbol izquierdo del hijo derecho. Con estas dos simples modificaciones el nuevo ´arbol queda equilibrado en cuanto a la altura se refiere. De manerasim´etrica se realiza la rotaci´on LL. Las situaciones iniciales yfinales de las dos rotaciones se pueden ver de manera gr´afica en la siguiente figura 3.5. 5 6 7 1 23 4 0 2 56 1 7 3 4 0 3 2 4 0 1 6 75 3 1 6 0 5 4 72 Figura 3.5: Representaci´on del antes ydespu´es de la rotaci´on LL yRR La secuencia de acciones arealizar hasta completar la rotaci´on descrita es la que se puede ver en la figura 3.6. El nodo 1, ra´ız de la rotaci´on, env´ıa el mensaje RotateMsg con la nuevainformaci´on asu padre nodo 0yasu hijo nodo 3. Posteriormente, cuando estos reciben el mensaje, devuelven el mensaje de AckMsg al coordinador como 11 3. Dise˜no de la soluci´on 3.2 Operaciones de la red que han recibido la informaci´on nuevayen el caso del nodo 3nos devuelveadem´as el enlace del hijo que va a formar parte de la rotaci´on, el nodo 4. El coordinador manda un mensaje RotateMsg al nodo 4 con su informaci´on ya continuaci´on este nodo 4 contesta con el AckMsg. En el momento en el que el coordinador recibe este mensaje env´ıa los CommitMsg atodos los participantes. Una vez recibido el mensaje se modifica el nodo ypasa aestar en un nuevoestado. Todos los nodos involucrados actualizan su zona desde abajo hacia arriba. Nodo 1 : SNNodo 0 : SNNodo 3: SNNodo 4: RN UpdateZoneMsg() RotateMsg(idT,type) RotateMsg(idT,type) AckMsg(idT) AckMsg(idT) AckMsg(idT) RotateMsg(idT,type) CommitMsg(idT) CommitMsg(idT) CommitMsg(idT) UpdateZoneMsg() UpdateZoneMsg() UpdateZoneMsg() Figura 3.6: Diagrama de secuencia de la rotaci´on LL yRR b) Rotaci´on Derecha-Izquierda (RL) yRotaci´on Izquierda-Derecha (LR) Las rotaciones RL yLR son sim´etricas. La rotaci´on RL se usa cuando el sub´arbol derecho de un nodo es dos unidades m´as alto que el izquierdo yasu vez el sub´arbol izquierdo del hijo derecho es una unidad m´as alto que el derecho. Para llevar a cabo estas rotaciones se subdividen en dos pasos. En primer lugar se modifica el ´arbol realizando una rotaci´on simple del sub´arbolizquierdo del hijo. Con esta modificaci´on se deja preparado para efectuar posteriormente una rotaci´on de las explicadas anteriormente, en este caso RR. Seguimos los siguientes pasos: Pasamos el sub´arbol derecho del hijo izquierdo del sub´arbol derecho de la rotaci´on, como sub´arbol izquierdo del sub´arbol derecho. El hijo izquierdo del sub´arbol derecho subeun nivel ypasa aser el hijo del nodo ra´ız de la rotaci´on ypadre del que antes era el sub´arbol derecho. Con estas dos simples modificaciones se ha conseguido transformar el ´arbol ala situaci´on anterior en la que se puede realizar la rotaci´on RR. Las situaciones iniciales 12 3. Dise˜no de la soluci´on 3.2 Operaciones de la red yfinales de las dos rotaciones se pueden ver de manera gr´afica en la siguiente figura 3.7. 1 23 0 1 7 2 0 2 35 1 7 4 6 0 3 6 7 1 24 5 0 34 56 7 4 5 6 Figura 3.7: Representaci´on del antes ydespu´es de la rotaci´on LR yRL 3.2.4. Otras Operaciones a) Actualizaciones de zona Las actualizaciones de zona son muy importantes, yaque ´estas permiten dar a conocer los cambios que se han realizado en cualquier punto del ´arbol asus nodos superiores. Se realiza atrav´es del mensaje UpdateZoneMsg, en el quese manda la descripci´on de zona del propio nodo a su padre. Tras realizar cualquier cambio, ya sea tras inserci´on, rotaci´on oreconstrucci´on, todos los nodos que hayan cambiado est´an obligados aemitir un mensaje de actualizaci´on de zona. Un nodo que recibeuna actualizaci´on de cualquiera de sus hijos comprueba, ysi es necesario, actualiza sus valores de la descripci´on de zona. Las actualizaciones se seguir´an produciendo en orden ascendente hasta llegar al nodo ra´ız ollegar aun nodo enel que su descripci´on de zona no se hayamodificado. Los nodos de recurso no tienen ninguna restricci´on, yuna vez hayan cambiado de padre env´ıan el mensaje de actualizaci´on instant´aneamente. Sin embargo los nodos de estructura tienen restricciones, yaque tras realizar alg´un cambio es posible que no tengan toda la informaci´on. Un nodo de estructura tiene que tener la descripci´on de zona de sus dos hijos, yhasta que esto no ocurra no puede mandar su mensaje de actualizaci´on hacia arriba. 13 3. Dise˜no de la soluci´on 3.3 Tolerancia afallos Diferencia de Altura Sub´arbol m´as Alto Tipode Rotaci´on -2 omenor 0 ´o PositivoRightRight -2 omenor NegativoRightLeft 2 o mayor PositivoLeft Right 2 o mayor 0 ´o NegativoLeft Left Tabla 3.1: Valores para tomar decisi´on de rotaci´on b) Comprobaci´on diferencia de altura Esta operaci´on es fundamental en el correcto funcionamiento de la estructura, ya que es la que permite comprobar que los nodos est´en equilibrados. Esta operaci´on es la que determina si es necesario realizar una rotaci´on, yen ese caso qu´etipo de rotaci´on. La comprobaci´on se realiza en los nodos de estructura ´unicamente, yse lleva a cabo en dos ocasiones: tras cualquier cambio producido por una inserci´on, rotaci´on oreconstrucci´on ytras recibir un mensaje de actualizaci´on. La diferencia de altura es computada en cada nodo yes definida como la diferencia entre las alturas del sub´arbol izquierdo menos el derecho. Dada la definici´on, si la diferencia de altura tiene los valores (-1,0,1), el nodo est´aequilibrado ypor lo tanto no hayque realizar ninguna rotaci´on. Sin embargo si la diferencia de altura es menor oigual a -2 omayor oigual a 2 hayque realizar una rotaci´on. Llegados aeste punto, hemos decidido si hayque realizar una rotaci´on ono. En caso positivo, hayque determinar qu´etipo de rotaci´on ypara ello seusar´ael valor de qu´esub´arbol es el m´as alto. Este valor si es negativoindica que el sub´arbol izquierdo es m´as alto; si es positivoindica que el sub´arbol derecho es m´as alto;ysi es 0indica que tienen la misma altura. Definidos los valores, las decisiones sobrequ´erotaci´on se va a realizar aparece en la tabla 3.1. 3.3. Tolerancia afallos La DHT act´ua de almac´en donde se replica toda la informaci´on correspondiente a cada nodo. Cada vez que un nodo recibeun mensaje, y´este modifica cualquier informaci´on del nodo, la informaci´on se actualiza simult´aneamente en la DHT. En el momento enque se desconecta ofalla un nodo, se rompela conectividad en una parte de la red. En primer lugar se explican los mecanismos de desbloqueo de nodos involucrados en una operaci´on con un nodo que ha fallado, yposteriormente, c´omose detectayc´omo se reconstruyela red. 14 3. Dise˜no de la soluci´on 3.3 Tolerancia afallos 3.3.1. Tiempos de espera de las operaciones Los tiempos de espera nos van apermitir desbloquear los nodos que se queden bloqueados debido al fallo de otro nodo involucrado en la misma transacci´on. Al realizar cualquier operaci´on,si se supera el tiempo de espera, se considera que ha habido alg´un problema por lo que se decide abortar la transacci´on. Los casos son lossiguientes: Un nodo que intenta acceder ala red manda un mensaje de entrada (InsertCommandMsg). Se activauna alarma al mandar el mensaje. Si se cumple el tiempo de espera de la alarma,dicho mensaje se reenv´ıa para permitir atodos los nodos acceder ala red. Esta alarma tiene una vida activadesde el momento de env´ıo delprimer mensaje hasta que el coordinador inicia la inserci´on. Si se produce alg´un fallo en la inserci´on el timer se reactiva. Todos los nodos involucrados en una inserci´on ouna rotaci´on en el momento que reciben el mensaje de inicio de transacci´on activan una alarma para la transacci´on. Si se cumple el tiempo de espera, la transacci´on se aborta yse desbloquean los nodos, mientras que en caso de completarse la transacci´on se desactivala alarma. Para asegurar elcorrecto balanceo de todos los nodos de la red haydos situaciones especiales. La primera se produce cuando un nodo de estructura aborta una transacci´on, yla segunda en el nodo hijo del coordinador de las rotaciones RL yLR. En estas dos situaciones se necesita crear una alarma para asegurarnos que se comprueba el balanceo posteriormente. Si se cumple el tiempo de espera se comprueba si es necesario balancear. La alarma tiene vigencia hasta que se compruebeel balanceo, yasea por dicha alarma opor el desarrollo normal de la estructura. 3.3.2. Detecci´on de fallos Todos los nodos cada cierto tiempo, que es fijo, env´ıan un mensaje (AliveMsg) asus vecinos. Un nodo de estructura env´ıa el mensaje asu padre yasus dos hijos, mientras que un nodo de recurso s´olo env´ıa el mensaje asu padre. Este mensaje (AliveMsg) permite conocer alos nodos que sus vecinos son quienes deben ser yest´an en la red yno se han desconectado. Cuando un nodo falla deja de enviar los mensajes de AliveMsg. Todo nodo de la red tiene que recibir este mensaje dentro de un tiemporazonable, que se ha definido como tres veces el intervalo con que se manda el mensaje AliveMsg. Cada vez que un nodo recibeel mensaje de su vecino reinicia el tiempom´aximo deespera. Si un nodo no recibeeste mensaje de su vecino dentro del tiempodefinido, se considera que ese nodo ha fallado. 15 5. Simulaci´on yprueba real 5.1 Pruebas con el simulador 5.1.2. Comprobaci´on del resultado Para comprobar el resultado tras la simulaci´on se han realizado pruebas de validaci´on. Estas pruebas son el proceso de revisi´on en el que se comprueba si el resultado obtenido cumple ono los requisitos especificados, es decir, nos indica si el resultado es correcto o no. Al finalizar la simulaci´on se comprueban los siguientes par´ametros: Todos los nodos tienen la misma ra´ız del ´arbol. Esto comprueba que no hayaramas del ´arbol independientes. Todos los nodos con rol de estructura est´an en el estado ONLINE ysu identificador de transacci´on es nulo. Esto nos indica que el nodo no est´a en mitad de ninguna transacci´on. Todos los nodos con rol de estructura est´an equilibrados, es decir, la diferencia de la altura de los sub´arboles izquierdo yderecho es m´aximo una unidad. Esto comprueba que el ´arbol esta balanceado. Se recorren todos los nodos del ´arbol en preorden yel n´umero de nodos recorridos tieneque coincidir con el doble de nodos f´ısicos menos uno (Por la propiedad comentada en la secci´on 3.1). Si todo lo anterior se cumple, el resultado obtenido es correcto, de lo contrario algo falla. 5.1.3. Validaciones b´asicas Presentado el escenario yla forma de comprobar el resultado se realizan diversas pruebas. Siendo Nel valor que representa al n´umero de nodos f´ısicos que van aformar parte de la red, Ntoma los siguientes valores: 10, 50, 100, 500, 1000, 5000, 10000, 50000, 100000 y500000. En primer lugar se simula la red paralos valores de Ndefinidos anteriormente sin ning´un nodo que vaya a fallar. Para todos los valores el resultado obtenido bas´andonos en las comprobaciones anteriores es el correcto. Por lo tanto la escalabilidad se haconseguido. Posteriormente se simula la red para los valores de Ndefinidos anteriormente yprogramando el fallo de un nodo aleatorio en un tiempoaleatorio. Para todos los valores la red ha detectado el nodo que ha fallado, se ha reconstruido la estructura, yposteriormente se ha vuelto aintroducir el nodo quehab´ıa fallado. Acontinuaci´on, se realizan las mismas pruebas pero esta vez programando varios fallos durante la simulaci´on. Siempre ycuando un nodo que ha fallado no est´einvolucrado en la reconstrucci´on de otro nodo, la red consigue detectar todos los fallos, reconstruir la estructura y volver aintroducir los nodos en la red. 22 5. Simulaci´on yprueba real 5.1 Pruebas con el simulador Sin embargo, existe una limitaci´on en el protocolo, que se producesi uno om´as nodos ca´ıdos est´an involucrados en un proceso de reconstrucci´on de otro nodo, en la que la recuperaci´onde la estructura no puede llevarse a cabo.Esto se produce porque el coordinador de la reconstrucci´on env´ıa mensajes anodos que han fallado ypermanece ala espera de las respuestas de estos, que nunca van allegar por lo quetodos los nodos involucrados quedan bloqueados. Por lo que se puede asegurar que la estructura se recupera correctamente tras un fallo, siempre ycuando no hayaning´un nodo ca´ıdo involucrado en la reconstrucci´on de otro nodo. 5.1.4. Validaci´on en caso de churn Las redes P2P tienen un gran dinamismo, es decir, que la red est´acambiando continuamente debido alas conexiones ydesconexiones de los participantes.El proceso que involucra la entrada ysalida de los participantes de la red de manera arbitraria se denomina churn. En este apartado, se profundiza en la tolerancia afallos sometiendo ala red P2P aun permanente cambio. Se programan inserciones de nodos exactamente igual que en el apartado anterior, yasu vez se programan continuamente fallos aleatorios de nodos f´ısicos con un proceso de Poisson de media 10 segundos. Por la limitaci´on de esteproyecto, que s´olo permite reconstruir fallos en los que no intervengan otros nodos ca´ıdos, en el momento de programar el fallo de un nodo f´ısico se comprueba que todos los nodos vecinos est´en dentro de la red yno se hayaprogramado ning´un fallo para esos nodos. Con esta configuraci´on, se ha conseguido crear un escenario en el cual haycontinuas entradas ysalidas de participantes de la red. Durante un tiempoconsiderable de simulaci´on, la capa de red se comporta perfectamente detectando los fallos, yposteriormente, procediendo ala reconstrucci´on devolviendo la red aun estado correcto. Con lo que se puede afirmar que la red responde bien frente aun churn elevado. Sin embargo, debido ala limitaci´on ala hora de reconstruir nodos con otros nodos ca´ıdos, eventualmente aparecen casosde error m´as complejos. M´as concretamente en nuestro caso, se produce porque en el momento de programar el fallo de un nodo todos sus vecinos est´an en la red,sin embargo, en el momento que se inicia la reconstrucci´on alguno est´aca´ıdo ya´un no se ha realizado su reconstrucci´on. En este caso, todos los nodos quedan bloqueados imposibilitando el correcto funcionamiento de la red. Un ejemplo de la situaci´on descrita es la que podemos ver en la figura 5.1, donde se pueden observar todos los nodos que se usar´ıan en una reconstrucci´on del nodo 92 y38 respectivamente. Si se programa el fallo del nodo f´ısico 92 yposteriormente del nodo f´ısico 38 ylas reconstrucciones se realizan en este orden no hayningn problema. Sin embargo, si por alg´un motivose inicializa la reconstrucci´on del nodo 38 en primerlugar la reconstrucci´on no 23 5. Simulaci´on yprueba real 5.1 Pruebas con el simulador 92 29 3829 38 15 54 26 67 98 99 92 92 29 3829 38 15 54 26 67 98 99 92 Nodos reconstrucción 92 Nodos reconstrucción 38 Figura 5.1: Misma situaci´on resaltando los nodos involucrados en la reconstrucci´on del nodo 92 y38 de manera independiente. puede finalizar por involucrar al nodo 92 quedando bloqueados todos los nodos coloreados en la figura 5.1. Es por ello que esta limitaci´on en el funcionamiento se solucionar´a en el futuro. 5.1.5. Consumo de Ancho de Banda Adem´as de la validaci´on se ha realizado una medida del consumo de ancho de banda de salida yde entrada de los nodos de la red. Se han obtenido dos valores: la media de uso de ancho de banda de todos los nodos yel pico de m´aximo uso de ancho de banda en periodos de diez segundos. En las figuras 5.2 y5.3 se pueden observar lasmedidas obtenidas para el ancho de banda de salida yde entrada respectivamente. Para realizar las pruebas se realizan varias simulaciones. Siendo Nel valor que representa al n´umero de nodos que van aformar parte de la red, Ntoma los siguientes valores: 10, 100, 1000, 10000, 100000. Adem´as para cada valor de Nse han realizado siete simulaciones distintas. De los siete resultados obtenidos se eliminan las muestras m´as extremas yse realiza la media de las restantes. Las l´ıneas azules representan el m´aximo uso de ancho de banda en un per´ıodo de diez segundos ylas l´ıneas rojas describen la media de uso de ancho de banda de todos los nodos. Hayque destacar que el m´aximo uso del ancho de banda de salida se situa en tan solo el 3,32 KBps yel m´aximo uso del ancho de banda deentrada es solamente el 1,09 KBps. Por otra parte la media de uso de ancho de banda de entrada yde salida se sit´ua 24 5. Simulaci´on yprueba real 5.1 Pruebas con el simulador                Figura 5.2: Medidas del uso del ancho de banda de salida respecto al n´umero de nodos dela red.                Figura 5.3: Medidas del uso del ancho de banda de entrada respecto al n´umero de nodos de la red. ´unicamente en 0,31 KBps. Ante los resultados obtenidos en ambos casos hayque concluir que frente aun crecimiento exponencial del tama˜no de la red el aumento del uso del ancho de banda es practicamente despreciable. 5.1.6. Tiempomedio de inserci´on Tambi´en se ha realizado una medida del tiempo de inserci´on de los nodos en la red. Para realizar las pruebas se realizan varias simulaciones. Siendo Nel valor que representa al n´umero de nodos que van aformar parte de la red, Ntoma los siguientes valores: 10, 100, 1000, 10000, 100000. Adem´as para cada valor de Nse han realizado siete simulaciones distintas. Se obtiene el tiempoque tarda en insertarse en la red el ´ultimo nodo. El tiempo se determina desde que dicho nodo env´ıa el mensaje de inserci´on InsertCommandMsg hasta que losdos roles que interpreta cada nodo realizan el commit ypasan aformar parte de la red. De los siete resultados obtenidos se eliminan las muestras m´as extremas yse realiza la media de las restantes. En la figura 5.4, representado con la l´ınea azul, se puede ver el tiempo de inserci´on del ´ultimo nodo de la red. Como se puede observar, frente aun crecimiento exponencial del tama˜no de la red el aumento del tiempo de inserci´on es m´ınimo, situ´andose el tiempo medio de inserci´on entorno 2,25 segundospara redes de100.000 nodos. Lo anteriormente expuesto es otra evidencia de que la capa de redes escalable en cuanto al n´umero de participantes en la misma, yaque atendiendo ala gr´afica para redes m´as grandes, no afecta al rendimiento de la misma. 25 5. Simulaci´on yprueba real 5.2 Prueba escenario real                Figura 5.4: Medida del tiempode inserci´on del ´ultimo nodo que accede ala red respecto deln´umero de nodos de la red 5.2. Prueba escenario real Esta prueba trata de validar ycomprobarel correcto funcionamiento de la capa de red en un escenarioreal. Para ello se usan 6ordenadores del laboratorio 1.3b. En cada uno de ellos se lanzar´an 3instancias de la capa de red, por lo que se crear´aun red de un total de 18 nodos f´ısicos. Ala hora de crear la red, cada instancia tiene que recibir dos par´ametros el puerto propio donde se ejecuta (-p N´umero )yel punto de entrada atrav´es del cual se va a conectar ala red (-e IP:Puerto ). Salvola excepci´on del primernodoque solo necesita el par´ametro del puerto. Recordando que el identificador de cada nodo es el par direcci´on IP -Puerto, hayque destacar que cada instancia en un mismo ordenador es obligatorio que tenga un puerto distinto. Tras lanzar los 18 nodos f´ısicos, se comprueba que se han introducido correctamente todos los nodos en la red. Acontinuaci´on, para comprobar la tolerancia afallos se detiene la ejecuci´on de un nodo. En el momento que se detecta el fallo, se inicia el proceso de reconstrucci´on de la red ytras completarse dicho proceso, la estructura contin´ua ejecut´andose correctamente. De esta forma se harealizado la prueba en una escenario real yse puede asegurar que ha sido un ´exito, yaque se ha creado la red yse ha reconstruido tras un fallo. 26 6. Conclusiones En este proyecto fin decarrera se ha conseguido dise˜nar eimplementar una capa de red jer´arquica, escalable ytolerante afallos. Se ha conseguido obtener una estructura totalmente distribuida, sin memoria compartida ycreando un protocolo de intercambio de mensajes. Se ha validado el correctofuncionamiento de la capa de red atrav´es de un simulador, yposteriormente en una prueba real en el laboratorio. En la primera parte de simulaci´on, se ha comprobado que la capa de red se adapta acualquier tama˜no de red. Se han realizado pruebas de simulaci´on de la red desde un ´unico nodo f´ısico, hasta 500.000 nodos f´ısicos. En toda la bater´ıa de pruebas realizadas, el resultado ha sido el correcto. Adem´as, las medidas de tiempo de inserci´on yla medida del uso del ancho de banda de entrada ysalida han arrojado resultados muy adecuados alo que se buscaba. Por este motivopodemos asegurar que se ha conseguido el objetivobuscado de la escalabilidad. En las pruebas se han introducido fallos de nodos f´ısicos aleatorios, yen todas ellas la red ha detectado dicho fallo. Posteriormente se inicia el proceso de recuperaci´on, teniendo en cuenta que en este proceso no est´einvolucrado otro nodo ca´ıdo, yse reconstruyen los enlaces rotos devolviendo la estructura aun estado correcto. El resto de nodos no involucrados no se ven afectados ysiguen funcionando correctamente. Con estos datos se concluyeque se ha conseguido el objetivo de tolerancia afallos para las situaciones m´as corrientes. Se ha desarrollado una capa de red que servir´acomo medio para la distribuci´on de la informaci´on yla localizaci´on de recursos aemplear por otras plataformas. Todo lo expuesto demuestra que todos los objetivos de este proyecto se han cumplido. 6.1. Trabajo futuro Una vez que se ha visto que las decisiones tomadas han sido acertadas, el siguiente paso es profundizar en la tolerancia afallos. Se debeestudiar de forma m´as detallada el tratamiento yrecuperaci´on de errores de varios nodos pr´oximos entre s´ı. Es decir, nodos ca´ıdos que intervienen en el proceso de reconstrucci´on de otro nodo ca´ıdo. Otra mejora futura es la optimizaci´on del protocolo de intercambio de mensajes para 27 6. Conclusiones 6.2 Valoraci´on Personal reducir el tr´afico de mensajes. Por un lado, agrupar varios mensajes dirigidos aun mismo destino desde una misma fuente, ypor otra parte, mejorar el protocolo de detecci´on de nodos fallidos yde esta forma conseguir una reconstrucci´on en el menor tiempoposible. Con el objetivo de evitar usuarios malintencionados habr´ıa que implementar mecanismos de seguridad en laDHT para proteger los datos yque s´olo el propietario pueda modificarlos. 6.2. Valoraci´on Personal Este ha sido sin duda el trabajo m´as importante ydif´ıcil al que me he tenido que enfrentar. Afrontar los problemas en el desarrollo de un proyecto de esta envergadura, me ha aportado numerosos conocimientost´ecnicos que ser´an de mucha utilidad durante el desarrollo de mi vida profesional. He aprendido las pautas aseguir en la realizaci´on de un proyecto de investigaci´on, desde la fase de recopilaci´on de informaci´on yb´usqueda de art´ıculos similares hasta la obtenci´on de las conclusiones, as´ıcomoel an´alisis del problema, el dise˜no de una soluci´on yla realizaci´on de las pruebas para comprobar la validez del resultado. Este proyecto me ha permitido profundizar mucho en el lenguaje orientado a objetos C++. Por un lado al escribir numerosas l´ıneas de c´odigo desde cero, ypor otro al leer ycomprender c´odigo fuente desarrollado por otros programadores para adaptarlo e integrarlo todo en un mismo proyecto. Tambi´en me ha permitido poder adentrarme en el paradigma de la programaci´on distribuida, conoceryposteriormente poder dar una soluci´on alos numerosos problemas que ella entra˜na. Considero que la programaci´on distribuida es una tecnolog´ıa muy extendida por el auge que han tenido las redes P2P,y conocerla puede serme de gran utilidad. Amodo personal, este proyecto ha hecho que desarrolle una visi´on global que me permita anticipar los inconvenientes futuros que siempre aparecen en el transcurso de un proyecto real de desarrollo de software, yde esta forma poder resolver estos problemas de manera m´as eficiente. As´ımismo ha sido enriquecedor el hecho de haber conseguido los objetivos marcados al principio, ypor ello quiero agredecer ami director todo el tiempo ydedicaci´on que me ha brindado alolargo de este tiempo. 28 Bibliograf´ıa [1] The apache cassandra project. http://cassandra.apache.org/. [2] Avl tree. http://xlinux.nist.gov/dads//HTML/avltree.html. [3] Maidsafe. kademlia dhtwith nat traversal. http://code.google.com/p/maidsafe-dht/. [4] Apache. The apache project. http://www.apache.org/. [5] Apache. Libqtcassandra. http://snapwebsites.org/project/libqtcassandra. [6] J. Celaya. Ahighly scalable decentralized scheduler of tasks with deadlines. Grid Computing (GRID), 2011 12th IEEE/ACM International Conference,Septiembre 2011. [7] C.S.Ellis. Concurrentsearchand insertion in avl trees. Computers, IEEE Transactions,C-29(Issue: 9):811 –817, Sept 1980. [8] H.V. Jagadish, B.C. Ooi, and Q.H. Vu. Baton: abalanced tree structure for peer-to- peer networks. VLDB ’05,2005. [9] H.V. Jagadish, B.C. Ooi, Q.H. Vu, R. Zhang, and A. Zhou. Vbi-tree:Apeer-to-peer framework for supporting multi-dimensional indexing schemes. ICDE ’06.,Abril 2006. [10] A. Kaluszka. Distributed hash tables. http://courses.ischool.berkeley.edu/i250/s10/report/, April 2010. [11] B.W. Lampson. Atomic transactions. DistributedSystems:Architectureand Implementation,Vol. 105:246–265, 1981. [12] P.Maymounkovand D. Mazi`eres. Kademlia: Apeer-to-peer information system based on the xor metric. In Peer-to-Peer Systems,vol. 2429(Lecture Notes in Computer Science):53–65, Springer Berlin /Heidelberg 2002. [13] C. Mohan and B. Lindsay.Efficientcommit protocols forthe tree of processes model of distributed transactions. ACM SIGOPSOperating Systems Review,Volume 19(Issue 2):40 –52, April 1985. 29 [14] O. NURMI, E. SOISALON-SOININEN, and D. WOOD. Concurrentbalancing and updating of avltrees. http://www.csa.com,1992. [15] S. Ratnasamy,P.Francis, M. Handley,R. M. Karp, and S. Shenker. Ascalable content-addressable network. SIG-COMM Comput. Commun. Rev.,31(4),pages 161– 172, August 2001. [16] A. Rowstron and P.Druschel. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. IFIP/ACM International Conferenceon DistributedSystems Platforms Heidelberg,pages 329–350, Springer-Verlag 2001. [17] F. Ruiz and M.A. Moraga de la Rubia. El modelo de datos jerarquicos. Universidad de Castilla-LaMancha,Abril 2001. [18] I. Stoica, R. Morris, D. Karger, M. Frans Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup protocol for internet applications. SIGCOMM 01,pages 149–160, August 2001. [19] RVan Renesse, K.P.Birman, and Werner Vogels. Astrolabe: Arobust and scalable technology for distributed system monitoring, management, and data mining. ACM Trans. Comput. Syst.,21(2):164–206, 2003. [20] P.Yalagandula and M. Dahlin. Ascalable distributedinformation management system. ACM, 2004. [21] B.Y. Zhao, J.D. Kubiatowicz, and A.D Joseph. Tapestry: An infrastructure for fault tolerantwide-area locationand routing. Technical Report UCB/CSD-01-1141. UC Berkeley,April 2001. 30