Chord

Chord es un protocolo y algoritmo para la implementación de tablas de hash distribuidas. A la tablas de hash construidas según esta forma se las llama tablas hash distribuidas de Chord o DHT Chord. El sistema es sencillo, escalable y está diseñado para funcionar en redes descentralizadas P2P (sin nodos privilegiados).

Un problema fundamental al que se enfrentan las aplicaciones P2P es el de localizar de manera eficiente el nodo que almacena un elemento de datos en particular. Para ello existen diferentes mecanismos como Chord, un protocolo de búsqueda distribuida que aborda este problema. Chord proporciona soporte para una sola operación: dado una clave, asigna la clave a un nodo. La ubicación de los datos puede ser fácilmente implementada sobre Chord asociando una clave para cada elemento, y almacenar el par de clave / elemento en cada nodo. Chord se adapta de manera eficiente a medida que los nodos se unen y dejan el sistema, y puede responder consultas incluso si el sistema está continuamente cambiando.

Introducción

Este protocolo permite tener un conjunto de nodos identificados con un conjunto de bits. Por ejemplo, si usamos un conjunto de 6 bits como identificador, pues podemos identificar hasta 64 nodos en nuestra red P2P, porque 2^6 es 64. Los identificadores irían desde 000000 (0) hasta 111111 (63). Para identificar al nodo 49 por ejemplo sería: 110001 (49)

Cada nodo, además, puede tener asociado a una o varias claves o llaves. Estas claves, se representan con el mismo número de bits que el identificador de los nodos. En nuestro caso, las llaves se identificarían también con un conjunto de 6 bits. Un nodo no puede tener asociado claves cuya representación o id sea mayor que la del propio nodo. Por ejemplo, el nodo con identificador 34 no puede tener asociada una clave con id 35, pero si una con id 34. La regla general es que cada nodo tiene asignadas las claves con id menor o igual que su identificador de nodo, de forma que no haya otro nodo cuyo identificador esté más cerca del id de la clave. Por ejemplo, si tenemos los nodos 20 y 34, la clave con id 15 iría asociada al nodo 20, porque 15 está más cerca de 20 que de 34, pero la clave con id 21, iría asociada al nodo 34, porque 21 es mayor que 20 y no puede ir asociada a él.

El nodo con menor id del conjunto de nodos, puede tener claves asociadas con id mayor que él. Para explicarlo, lo haremos con un ejemplo. Imaginemos que tenemos un conjunto de nodos y que el nodo con mayor id es 54 de los 63 posibles identificadores. La clave 56, no puede ir asociada al nodo 54, por lo que pasa al siguiente nodo empezando por el principio de nuevo, que sería el nodo con id más bajo. Es decir, las claves que no puede recoger un nodo, se las pasa a su sucesor, que es el que tiene el siguiente id más alto que él. Si esta clave llega al nodo con id más bajo, se la asigna a él.

Funcionamiento general

Se considera una red formada por $2^{m}$ nodos, que pueden estar activos o ausentes de la red. Dado un conjunto de claves en esa red, el protocolo Chord se encarga de asignar las claves existentes a los nodos activos y mantener esas asignaciones dinámicamente, es decir, a medida que los nodos van entrando y saliendo de la red. El resto de tareas vinculadas a la red -autenticación, almacenamiento de datos, interfaz, etc.- son responsabilidad de los niveles superiores de la arquitectura.

La asignación de identificadores a nodos y claves se realiza mediante una función de hash consistente. En efecto, cuando un nodo o una clave entran en la red, reciben una identificación (id) que se obtiene calculando el hash (SHA-1) de la IP del nodo o del valor de la clave. Con este hashing se aleatorizan los accesos al sistema, de forma que para un atacante resulte difícil encontrar nodos o claves consecutivas o de posición estratégica en la red.

Una clave de id k se asigna al nodo de id k si éste está activo en la red. Si k no está, se busca el primer nodo posterior a k que esté activo y se le asigna a la clave: este nodo sustitutivo se denomina sucesor de k (successor(k)).

Cuando k se conecte a la red, su nodo sucesor le transferirá las claves que estuvieran destinadas a él. Cuando un nodo abandona la red, transfiere las claves de las que se hacía cargo a su sucesor, es decir, al nodo con id siguiente a la suya. Con estos mecanismos, se garantiza la autorregulación de la red y el mantenimiento de las claves aun en un contexto de movilidad de los nodos participantes.

Procedimiento de búsqueda

El correcto mantenimiento de los nodos sucesores ya garantiza que las búsquedas se procesan de forma exhaustiva. Sin embargo, cada nodo almacena una cierta información adicional sobre la red que permite acelerar las búsquedas.

Esta información adicional se reduce a unos pocos nodos activos de la red, y se refleja en una tabla de rutas (finger table) interna. En la i-ésima fila de esta tabla consta el sucesor del nodo situado a distancia $2^{(i-1)}$ del nodo correspondiente (en dirección negativa en el círculo). De esta forma, cada nodo tiene un conocimiento más exhaustivo de sus homólogos más cercanos (aproximadamente, si N es el número de nodos totales, almacena información sobre $O(log(N))$ ).

Cuando un nodo solicita una clave j, examina su propia tabla de rutas; si encuentra el nodo responsable de j, envía la petición directamente al nodo afectado. En caso contrario, pregunta al nodo cuya id sea más cercana (menor) a j, que devolverá la id del nodo más cercano a j (menor) que encuentre en su tabla de rutas. De esta manera, el nodo remitente obtiene en cada nueva iteración un nodo más cercano a k, hasta llegar a k o a su sucesor. Todo este mantenimiento requiere el desarrollo de una señalización (mensajes entre nodos para mantener actualizadas las tablas de rutas) del orden de $(log(N))^{2}$ .

Búsqueda secuencial

Este problema de búsqueda consiste en cómo encontrar una llave que posee un nodo.

Supongamos el siguiente caso. El nodo con id 12 quiere encontrar la llave con id 52. Entonces el nodo 12 sabe que no tiene la llave porque tiene un id menor que el id de la llave. Lo que hace pues, es preguntar a su sucesor, el nodo 20. Este nodo también sabe que no tiene la llave, pues tiene un id mayor que su identificador de nodo. Entonces, pregunta a su sucesor, el nodo 34, que tampoco tiene la llave. El nodo 34 pregunta al nodo 49, que es su sucesor, y este como tampoco la tiene, pregunta a su sucesor, que es el nodo 50. El nodo 50 tampoco tiene la llave, y pregunta al nodo 51, que sigue sin tener la llave. Entonces pregunta al nodo 53, su sucesor, y este sí que contiene la llave buscada. Es entonces, a partir de la séptima iteración es cuando se le puede decir al nodo 12 que el nodo 53 tiene la llave con id 52.

Se han necesitado 7 saltos. En el peor de los casos, si todos los identificadores de nodo estuviesen asignados a nodos, tendríamos que haber hecho 63 saltos en nuestro caso. Si los identificadores fuesen de más bits, el número de saltos máximo, en el peor de los casos sería 2^m saltos, siendo m el número de bits que forman el identificador de nodo.

Ejemplo usando finger tables

La búsqueda secuencial puede ser costosa. Entonces lo que se propone, es que cada nodo tenga una tabla con tantas filas como número de bits tiene el identificador de un nodo o una clave. En nuestro caso, la tabla tendría seis filas. Esta tabla se conoce como fingertable.

Cada fila almacena un valor, que es el nodo que contiene la clave con identificador igual al identificador del propio nodo más dos elevado a la posición de la fila en la tabla, empezando por cero. Por ejemplo:

Para el nodo 3, su fingertable es la que se representa en el dibujo. La primera fila corresponde con la llave de id 4, y el nodo que la tendría es el 12. Para la fila segunda, la llave es 5, y el nodo que la poseería es el nodo 12. Para la fila 6, tenemos el nodo 38, que es el que guardaría la llave 35.

Supongamos que el nodo 3 quiere buscar ahora la llave con id 52. El nodo 3 lo que hace es buscar en su tabla el nodo cuya llave más se aproxima a 52 por debajo. En este caso es el nodo 38, que tendría la llave 35, así que le pregunta a él directamente. Ya no pregunta a su sucesor.

Ahora pues, el nodo con id 38, mira también en su fingertable. El siguiente nodo al que tiene que preguntar es el nodo con id 49, pues la llave 54 ya es mayor que 52 y no puede preguntar al nodo 54.

El nodo 49, mira su fingertable, y el siguiente nodo cuya llave es menor que 52, es el nodo 51, así que le pregunta a este otro.

Así, ya en el nodo 51, este ve en su tabla que la clave con id 52, la tiene el nodo con id 53, así que le pregunta a él. Y el nodo 53, como ya sí contiene la clave 52, puede contestar al nodo 3.

Hemos necesitado, por tanto, cuatro saltos o iteraciones, mientras que, en una búsqueda secuencial, habríamos necesitado ocho iteraciones.

Inserción y eliminación de nodos

Cuando un nodo nuevo entra, averigua quién es su sucesor, y le pide las claves que le corresponden. Esto implica que los nodos con menor id que el nodo que acaba de entrar tienen que actualizar sus fingertables.

Cuando un nodo sale, le pasa sus claves a su sucesor. Esto también implica que los nodos con id menor que el que sale, deben actualizar sus tablas.

Cada vez que un nodo entra o sale, se necesitan $log^{2}n$ mensajes para actualizar las tablas de los nodos, siendo n el número de nodos.

Eficiencia y escalabilidad

Chord está diseñado para ser altamente escalable, es decir, para que los cambios en las dimensiones de la red no afecten significativamente a su rendimiento. En particular, si N es el número de nodos de la red, su coste es proporcional a log(N).

Es escalable porque solo depende del número de bits del que se compone un identificador. Si queremos más nodos, simplemente asignamos identificadores más largos.

Es eficiente, porque hace búsquedas en un orden $log(n)$ , siendo n el número de nodos en la red, ya que en cada salto, se puede reducir a la mitad el número de saltos que quedan por hacer.