Kademlia
Kademlia puede considerarse como un protocolo para la implementación de Tabla de hash distribuida, desarrollado en la universidad de Nueva York por David Mazières y Petar Maymounkov en el año 2002.[1]
Está destinado a sistemas P2P, ya que las Tablas Hash Distribuidas son un tipo de tablas hash cuyos rangos de registros clave-valor quedan dispuestos de una forma más o menos equitativa entre los nodos participantes en el sistema, sin necesidad de tener un servidor central.
De esta forma se produce una equiparación de responsabilidades entre todos los nodos participantes dentro del propio sistema, eliminando así, la dependencia de un nodo central que mantenga toda la responsabilidad y toda la información que pudieran requerir los nodos y por esto se elimina un cuello de botella del sistema, aumentando el rendimiento de este.
Actualmente, según David Mazières y Petar Maymounkov, la utilidad de Kademlia está en aplicaciones para compartir archivos, aunque esta podría no ser la única utilidad de Kademlia. En este tipo de sistemas de compartición de archivos, los datos que va a guardar cada nodo participante con relación a los archivos, suelen ser una clave conjunto a un valor buscado, este valor puede indicar en que nodo encontrar el archivo, ya que, el nodo que contiene esta referencia no tiene porque ser el que posea el archivo o la información. La clave suele ser el Hash del archivo, en concreto en Kademlia se utiliza un hash de 160 bits, como por ejemplo pudiera ser un SHA-1
Se han realizado múltiples implementaciones de Kademlia, siendo este protocolo DHT uno de las más extendidos hasta el momento, haciendo uso de Kademlia por ejemplo BitComet o eMule.
La característica innovadora por la que Kademlia es conocida, es por el tratamiento de la distancia entre claves y nodos mediante una métrica XOR, que dota al protocolo de un buen rendimiento en búsqueda de recursos y de otros nodos participantes.
¿Es Kademlia lo mismo que Overnet o Kad?
No, Kademlia es un protocolo y Overnet y Kad son redes. Overnet fue una variante del protocolo Kademlia y era la red nativa sin servidores del desaparecido programa eDonkey, mientras que Kad usa otra variante distinta y es la red nativa sin servidores de los clientes *Mule. Aun así, ambas redes usan esencialmente el mismo protocolo (Kademlia), pero diferentes variantes, incompatibles entre sí. El cliente MLDonkey es compatible con ambas. El protocolo Kademlia es un desarrollo abierto y público.[2]
Nociones básicas para el entendimiento de Kademlia
Cada nodo almacena dos tablas, una que será la tabla con los pares clave valor relacionados con la información a compartir, y otra que se considera una tabla de rutas o encaminamiento, que contendrá registros con información sobre otros nodos de la red.
En Kademlia, cada nodo participante, al entrar en el sistema, adquiere un identificador mediante un proceso pseudo-aleatorio, este identificador tiene una longitud total de 160 bits. El proceso debe de ser pseudo-aleatorio, ya que se debe de garantizar una distribución más o menos uniforme.
La forma en que Kademlia trata a su red es de árbol binario, siendo las hojas de este árbol los nodos participantes en el sistema. Cada hoja por tanto contendrá el identificador del nodo, tal y como se muestra en la Figura 1.
En la Figura 1, los identificadores han quedado reducidos a 3 bits, pero en la red de Kademlia, tendrían una longitud de 160 bits, a no ser que, se utilicen solo prefijos del identificador (dependiendo del número de participantes en la red).
En Kademlia, se hablan de dos parámetros básicos, ambos números:[3]
- K Cuantifica la cantidad de estructuras de datos Contacto que puede almacenar cada nodo en cada Bucket
- α Representa cuantas llamadas a procesos remotos puede realizar un nodo de forma paralela
Los nodos almacenan dos tipos de información: la relativa al resto de participantes (tabla de encaminamiento), con la que conocen parte de la red, y la relativa a los recursos (tabla de datos).
En cuanto a la información relativa a los recursos , cada nodo guarda una porción de una tabla Hash, las claves tienen una longitud de 160 bits, que usualmente son el hash del recurso o archivo, y el valor, el bloque de datos que apunta al nodo en el que reside el archivo deseado o el recurso buscado.
Los siguientes párrafos estarán mayormente dedicados a la información relativa a la red.
Los contactos en Kademlia son una estructura de datos compuesta por un ID, una IP y un puerto UDP de un nodo en concreto.
Bucket
Todos los contactos en Kademlia quedan estructurados en cubos, denominados Buckets. En cada Bucket se van a almacenar aquellos contactos cuyo identificador de nodo difiere en 1 bit (en cada Bucket uno distinto y menos significativo), empezando por el bit más significativo, el de la izquierda. Por lo tanto, cada nodo en Kademlia va a mantener un total de 160 Buckets.
El siguiente ejemplo muestra un conjunto de Buckets que tendría un nodo, si el espacio de Identificadores fuera de 3 bits, suponiendo que conoce todos y cada uno de los nodos con los identificadores correspondientes y los Buckets no tienen límite de almacenamiento de contactos. ver Figura 2
Como se puede observar, en el Bucket-1 , se encuentran los contactos cuyos identificadores de nodos difieren en el bit más significativo, a este Bucket, se le denomina Bucket de contactos más alejados, ya que, en él, se encuentran los nodos cuyo identificador está más alejado del nodo actual.
El último Bucket del espacio de identificadores, en este caso el Bucket-3, es el Bucket de los contactos más cercanos.
El concepto de lejanía o cercanía se define mediante la métrica de distancia XOR de Kademlia, y es por el cual quedan los Buckets organizados ( los contactos con una distancia “ d ” respecto del identificador del nodo van en un Bucket, y los contactos con una distancia “ d’ ” respecto del nodo van en otro Bucket)
Dada la imagen anterior, se ve claramente que la forma de organizar los contactos hace que la cantidad de contactos en los Buckets sea desproporcionada, ya que el Bucket más alejado contendrá muchos contactos y el Bucket que contiene los contactos más cercanos almacena solo uno.
Para evitar esta desproporción y a la vez descargar al nodo de almacenamiento de datos en esta tabla de encaminamiento, se limita el Bucket a K contactos.
En el almacenamiento de los contactos nos podemos encontrar frente a varias situaciones:
1. El contacto que descubrimos se debe de posicionar en un Bucket que está vacío o se encuentra en un Bucket en el que hay menos contactos que K, por lo tanto, se añade al final del Bucket.
2. El contacto que hemos descubierto, ya se encontraba dentro de un Bucket, por lo que se mueve al final del Bucket.
3. El contacto que hemos descubierto no se encontraba en ningún Bucket, y se debe de introducir en uno que ya existen K contactos, por lo que se procede a investigar sobre la alcanzabilidad del primer contacto del Bucket (cuyo descubrimiento es más antiguo).
i. El contacto cuya alcanzabilidad ha sido evaluada, no responde, por lo que pasado un tiempo este contacto se descarta del Bucket, y se añade el nuevo contacto al final del Bucket.
ii. El contacto ha respondido y por lo tanto se descarta el nuevo contacto descubierto.
Además, como ya se ha podido observar en el párrafo anterior, dentro de cada Bucket limitado a K contactos (K-Bucket) , se realiza una ordenación de estos, siendo los contactos posicionados en la cabeza, aquellos que, se descubrieron en un primer momento y siendo los últimos, los nuevos contactos descubiertos, por supuesto, estos contactos deben de estar en línea para estar dentro del K-Bucket.
De esta forma, se evitan ataques de DoS al inundar la red con contactos nuevos y se intenta garantizar el acceso a la información sobre la ubicación de los recursos, ya que probabilísticamente es más difícil que un contacto que ha estado activo vaya a desactivarse, que uno que acaba de ser descubierto.
XOR como medida de distancia entre nodos
Kademlia utiliza XOR (OR exclusivo), para calcular la distancia entre nodos y claves, esta característica permite tratar a la red de nodos participantes como un árbol binario.
La operación XOR se realiza entre la clave o identificador de nodo a buscar y otro nodo, bit a bit, y el resultado de la operación se convierte a decimal, indicándonos la distancia entre las claves.
Por ejemplo, si quisiéramos ver cual de los dos nodos con identificadores 010 y 110 respectivamente está más cerca del identificador 100, realizaríamos el XOR dos veces y compararíamos (Figura 3)
El XOR, tiene varias propiedades que deben de ser expuestas. Dado un identificador U , otro V y otro W:
- La distancia entre U y el mismo es igual a 0.
- La distancia entre U y V es mayor que 0 siempre que V sea distinto de U.
- La distancia entre U y V es igual que la distancia entre V y U.
- La distancia entre U y V más la distancia entre V y W es mayor o igual que la distancia entre U y W.
Los RPC
Kademlia define 4 tipos de llamadas a procedimientos remotos para la comunicación, cabe destacar que cada vez que se realiza una comunicación entre nodos, se almacenan contactos si fuese necesario, reduciéndose así también los mensajes de configuración que se tendrían que enviar entre nodos para conocer información sobre ellos.
RPC PING
En esta llamada se evalúa la alcanzabilidad de un nodo. Cuando se produce una llamada de este tipo hacia un nodo, el nodo que recibe la llamada, como ya hemos comentado en el párrafo anterior, introduce si cree necesario (viendo la existencia o no del nodo que envía el Ping dentro del Bucket y actuando en consecuencia teniendo en cuenta el número de K contactos ya almacenados), el contacto del nodo emisor de la llamada en el Bucket correspondiente. Cuando se produce la respuesta, el nodo que inició la llamada, también modifica el Bucket correspondiente con el contacto al que le hizo el PING.
RPC STORE
Esta llamada a procedimiento remoto está destinada al almacenamiento de la información relativa a los datos que pudiera requerir un emisor y no a los datos de configuración o conocimiento sobre la red.
El nodo que genera la llamada debe de incluir la clave y el valor, que el propio nodo que recibe la llamada, almacenará en su tabla de datos por si alguien preguntase por la clave, pudiera indicarle el valor correspondiente
RPC FIND_NODE
En esta llamada, el nodo que inicia la llamada debe de incluir en ella un identificador de 160 bits (que corresponderá con un identificador de un nodo, existente o no), el nodo receptor, buscará dentro de sus Buckets, los contactos con identificadores más cercanos a dicha clave, y devolverá un total de K contactos más cercanos que conoce, a menos que, conozca menos contactos que K, en ese caso devolvería todos los que conoce.
RPC FIND_VALUE
De igual manera que en el RPC FIND_NODE, el nodo que realiza la llamada debe de incluir un identificador de 160 bits (presumiblemente el SHA-1 de un recurso), que coincidirá en caso de existencia con la clave de la tabla de datos de algún nodo, que, en caso de coincidir, este será el nodo con el identificador más cercano a la clave.
El nodo destino, si tiene en su tabla esta clave, devolverá el valor asociado, en caso de que no contenga esa clave dentro de su tabla de información, devolverá K contactos cercanos a la clave.
Entrar en la red
Según el documento redactado por David Mazières y Petar Maymounkov, para entrar en la red, se debe de conocer algún contacto que esté presente en el sistema distribuido.
El nodo en primer lugar deberá de introducir el contacto o contactos que conoce dentro de los Buckets correspondientes.
De forma paralela, empieza a realizar llamadas RPC FIND_NODE a los nodos cercanos a su propio ID, con el objetivo de conocer los nodos más cercanos al nuevo nodo. El número de llamadas paralelas que se pueden realizar estarán determinadas por el parámetro Alfa.
Los contactos devueltos por los nodos a los que se ha realizado las llamadas son almacenados en los K-Buckets correspondientes. De los que se han devuelto cercanos al propio nodo , se escogen alfa contactos y se les realiza otra llamada FIND_NODE, y así sucesivamente hasta que no se devuelvan contactos más cercanos al nodo de los que hay ya almacenados.
Una vez se ha terminado está búsqueda de nodos cercanos, el nodo tiene un conocimiento básico de sus vecinos.
Veamos un ejemplo:
Existe un nodo en la red, en concreto el nodo con identificador 100, otro nodo lo conoce y se conecta a la red, en este caso el nodo con identificador es el 000.
Sucesivamente se van añadiendo otros dos nodos que conocen al nodo 000, a los cuales se les asigna los identificadores 001 y 011, si K fuese igual a 1, no se produciría una red desconectada, ya que, por ejemplo:
El nodo 001 conocería al nodo con identificador 011, el nodo 011 debería de conocer al menos al nodo 000 y el nodo 000 conocería al nodo 100.
En caso de que el nodo 000 quedara fuera de línea, estaríamos ante un caso de desconexión de la red, por ello se debe de garantizar que se conocen un número suficiente de contactos repartidos por los subárboles del árbol binario que representa la red, y por tanto K debe de ser un número tal que permita esto último, de esta forma se rellenaría también el Bucket con contactos más alejados.
Búsqueda de un nodo y almacenamiento de un valor
El nodo al tener un conocimiento básico de la red ya puede introducir un registro clave valor en un fragmento de la tabla hash en el host correspondiente.
Para ello, lo primero que tiene que realizar es un Hash del recurso, el cual servirá como clave para la búsqueda, y el valor asociado a este suele ser un valor que indique donde se puede encontrar el recurso.
Una vez realizado este paso, tiene que realizar una búsqueda, similar a la búsqueda del nodo que se realiza a la hora de entrar en la red, pero en este caso, va a buscar aquellos contactos cuyo identificador de nodo esté más cercano a la clave, el contacto más cercano será aquel que guardará el valor correspondiente.
La situación de la red actualmente es la de la Figura 4, siendo el ejemplo de nodo inicializador con su tabla de encaminamiento y los parámetros, referenciados en la Figura 5.
El nodo con ID 011, vería cuales de los existentes en su tabla están más cercanos a la clave que quiere posicionar, para ello utiliza la métrica XOR.
Una de las formas en las que se podría hacer, sería realizar el XOR entre su identificador y la clave, y ver en que bit más significativo difiere, e ir a su tabla de encaminamiento y elegir el Bucket en el que están almacenados aquellos que difieren en dicho bit.
En este caso, podemos ver un ejemplo en la Figura 6.
El bit más significativo en el cual difiere es el primero, por lo que iríamos al Bucket número 1.
En este Bucket, solo hay un contacto, aquel con identificador 111, ya que la búsqueda de dicho nodo se debe de realizar seleccionando al menos 2 contactos, ya que alfa es 2, por lo que se seleccionaría otro contacto de otro Bucket, por ejemplo, del Bucket en el que los contactos difieren en el segundo bit más significativo del nodo.
Por lo que el nodo 011, enviaría FIND_NODE al nodo 111 y al primero del Bucket-2, el nodo 001 de forma paralela y asíncrona. En este FIND_NODE, se deberá de incluir como identificador la clave, para buscar contactos más cercanos a esta.
El nodo 001 y el nodo 111 deberán de responder con K contactos cercanos a la clave. A continuación, se pueden ver las tablas de encaminamiento que tendrán los nodos 011 y 111 respectivamente las referenciadas en la Figura 7.
El nodo 001 responde con: {111, 88.107.1.35, 3444} , {010, 88.107.12.35, 3444}
El nodo 111 responde con: {100, 84.16.0.4, 3444} , {001, 88.107.1.35, 3444}
En este momento el nodo inicializador de la comunicación seleccionada alfa nodos más cercanos a la clave, en el caso del ejemplo:
{111, 88.107.1.35, 3444} , {100, 84.16.0.4, 3444}
Del conjunto de contactos recibidos, escogería alfa tales que no hayan sido preguntados, como el nodo 111 ya ha sido preguntado, solo quedaría preguntar al nodo 100. Siendo su tabla la referenciada en la Figura 8.
El nodo 100 devuelve como K contactos: {111, 88.107.1.36, 3444} , {001, 88.107.1.35, 3444} Ya que no ha devuelto nodos más cercanos, el nodo inicializador, preguntaría a los contactos que quedan por preguntar devueltos como los más cercanos, en este caso solo faltaría por preguntar al nodo 010, el cual o bien no respondería contactos más cercanos, o de entre los contactos, devolvería el 100, y como ya le ha peguntado a este nodo (el 100) terminaría la búsqueda.
En este momento enviará un STORE al nodo con identificador 100 que es del de los alfa más cercanos aquel que tiene un identificador más cercano a la clave, conjunto con la clave y el valor.
En este proceso de búsqueda del nodo con identificador más cercano a la clave, las tablas de rutas se han ido actualizando cuando se han ido recibiendo mensajes. Por lo que los nodos tendrán un conocimiento más amplio de la red.
Recuperación de un valor
Para obtener un valor, necesitaremos conocer la clave a buscar, en este momento se procederá como en el apartado anterior en cuanto a la búsqueda de un nodo, pero las llamadas serán de tipo FIND_VALUE, y la búsqueda terminará cuando se devuelva un valor en vez de K contactos, o no haya más K contactos cercanos a la clave y no se haya devuelto un valor con anterioridad.
Programas compatibles con el protocolo
Véase también
Referencias
- «Kademlia: A peer-to-peer information system based on the xor metric».
- «Kademlia: A Design Specification». 2003.