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.
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 los 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.FAQ eD2k-Kademlia-es
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. centro|miniaturadeimagen|339x339px|Figura 1.- Árbol binario red Kademlia
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:
- 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 centro|miniaturadeimagen|516x516px|Figura 2.- Tabla de encaminamiento nodo 011 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) izquierda|miniaturadeimagen|265x265px|Figura 3.- Ejemplo XOR entre nodos 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.