Kademlia: la tabla hash distribuida que usan BitTorrent e IPFS

⏱️ Lectura: 15 min

BitTorrent encuentra el nodo que tiene un archivo entre millones de pares sin preguntarle a ningún servidor central. La respuesta llega en pocos saltos gracias a Kademlia, un algoritmo de 2002 que también sostiene la red de IPFS y el descubrimiento de nodos en Ethereum.

📑 En este artículo

1. TL;DR
2. Qué es Kademlia y por qué importa
3. Cómo funciona: distancia XOR y k-buckets
   1. La métrica XOR
   2. k-buckets: la tabla de ruteo
   3. Los cuatro mensajes RPC del protocolo
   4. Cómo se busca un nodo: FIND_NODE iterativo
4. Ejemplos prácticos: implementar Kademlia en miniatura
   1. Paso 1: la distancia y el orden de cercanía
   2. Paso 2: insertar en un k-bucket
   3. Paso 3: búsqueda iterativa completa (simulación)
5. Cómo empezar: correr un nodo Kademlia real
6. Casos de uso reales
7. Errores comunes y buenas prácticas
8. Comparativa: Kademlia frente a otras DHT
9. Profundizando: por qué la métrica XOR es la pieza clave
10. Preguntas frecuentes
    1. ¿Kademlia necesita un servidor central para arrancar?
    2. ¿Qué pasa si el nodo que busco ya no está conectado?
    3. ¿Por qué IDs de 160 bits y no menos?
    4. ¿Kademlia es lo mismo que blockchain?
    5. ¿Se puede usar Kademlia para una aplicación privada, no P2P pública?
11. Referencias

Kademlia resuelve un problema clásico de sistemas distribuidos: cómo ubicar un dato, o un nodo, en una red sin coordinador central y con participantes que aparecen y desaparecen todo el tiempo. Su truco es una métrica de distancia basada en XOR que reduce el ruteo a una tabla binaria simple.

TL;DR

• Vas a entender qué es una tabla hash distribuida (DHT) y por qué reemplaza a un servidor central de índice.
• Vas a calcular la distancia XOR entre dos IDs de nodo, la base de todo el ruteo en Kademlia.
• Vas a ver cómo se arma una tabla de k-buckets y por qué el valor k=20 no es arbitrario.
• Vas a simular una búsqueda iterativa de nodos en Python, paso a paso.
• Vas a identificar los ataques Sybil y eclipse, y cómo Kademlia se defiende de ellos.
• Vas a comparar Kademlia contra Chord y Pastry para elegir la DHT correcta según tu caso de uso.

Qué es Kademlia y por qué importa

Una tabla hash distribuida (DHT) es un diccionario clave-valor repartido entre miles de computadoras, sin que ningún nodo conozca el mapa completo. Cada nodo guarda una porción de las claves y sabe a quién preguntarle por el resto.

Kademlia, descrito en 2002 por Petar Maymounkov y David Mazières, es el diseño de DHT más usado en la práctica. BitTorrent lo adoptó en 2005 como DHT Protocol (BEP 5) para eliminar la dependencia de un tracker central: si el tracker de un torrent caía, la red seguía encontrando pares por sí sola.

El mismo diseño, con variaciones, corre hoy dentro de libp2p, la capa de red de IPFS y Filecoin, y en el protocolo de descubrimiento de nodos de Ethereum. La razón de su éxito es simple: la lógica de ruteo cabe en una operación aritmética, XOR, y eso la hace fácil de implementar y de razonar.

Cómo funciona: distancia XOR y k-buckets

La métrica XOR

Cada nodo y cada clave en Kademlia tienen un identificador de 160 bits, tomado de SHA-1 en el diseño original. La distancia entre dos identificadores no es geográfica ni de saltos de red: es el resultado de aplicar XOR bit a bit entre ambos números.

# distancia XOR entre dos IDs de nodo (IDs de 8 bits para el ejemplo)
node_a = 0b10110010
node_b = 0b10100001

distancia = node_a ^ node_b
print(bin(distancia))   # 0b00010011 -> 19 en decimal

Esta operación tiene una propiedad clave: es una métrica matemática válida (cumple simetría y desigualdad triangular) y además es unidireccional. Para cualquier ID dado existe exactamente un nodo a cada distancia posible, así que no hay ambigüedad sobre quién está más cerca.

k-buckets: la tabla de ruteo

Cada nodo organiza a sus vecinos conocidos en una lista de k-buckets. El bucket i guarda hasta k nodos cuya distancia XOR al nodo local cae en el rango [2^i, 2^(i+1)). Con IDs de 160 bits hay 160 buckets posibles, aunque casi ninguno se llena en la práctica.

El valor k que proponen Maymounkov y Mazières en el paper original es 20. No es arbitrario: modela cuántas fallas simultáneas de nodos puede tolerar un bucket antes de perder contacto con esa región del espacio de IDs.

flowchart TD
    Root["Nodo local"] --> B0["Bucket 0: distancia [1,2)"]
    Root --> B1["Bucket 1: distancia [2,4)"]
    Root --> B2["Bucket 2: distancia [4,8)"]
    Root --> B3["Bucket ...159: distancia lejana"]
    B0 --> N1["hasta k=20 nodos"]
    B1 --> N2["hasta k=20 nodos"]
    B2 --> N3["hasta k=20 nodos"]

Los cuatro mensajes RPC del protocolo

Kademlia define solo cuatro tipos de mensaje entre nodos. PING comprueba que un nodo sigue vivo. STORE le pide a un nodo que guarde un par clave-valor. FIND_NODE pide los k nodos más cercanos a un ID dado. FIND_VALUE es igual a FIND_NODE, pero si el nodo consultado ya tiene guardado el valor buscado, lo devuelve directamente en lugar de una lista de vecinos.

Este conjunto mínimo de mensajes es otra razón de la popularidad del diseño: implementar Kademlia completo no requiere más que cuatro handlers de red y la lógica de k-buckets que ya vimos.

Cómo se busca un nodo: FIND_NODE iterativo

Para localizar un nodo, o una clave, Kademlia no reenvía la petición en cadena como un protocolo recursivo. El nodo que busca consulta en paralelo a los α (alpha) nodos más cercanos que conoce, típicamente α = 3, y les pide sus propios vecinos más cercanos al objetivo.

Con cada respuesta, el buscador arma una lista cada vez más precisa y repite el proceso contra los nuevos candidatos, hasta que ninguna ronda produce un nodo más cercano que el mejor ya conocido. Esto converge en O(log n) saltos para una red de n nodos.

sequenceDiagram
    participant A as Nodo buscador
    participant B as Nodo cercano 1
    participant C as Nodo cercano 2
    A->>B: FIND_NODE(objetivo)
    B-->>A: lista de vecinos mas cercanos
    A->>C: FIND_NODE(objetivo)
    C-->>A: lista de vecinos mas cercanos
    Note over A: repite con los nuevos candidatos hasta converger

Ejemplos prácticos: implementar Kademlia en miniatura

Vamos a construir, en Python simplificado, las piezas mínimas de un nodo Kademlia: la distancia XOR, la inserción en un k-bucket y una búsqueda iterativa de juguete sobre una red simulada en memoria.

Paso 1: la distancia y el orden de cercanía

def distancia_xor(id_a, id_b):
    return id_a ^ id_b

def mas_cercanos(id_objetivo, candidatos, k=20):
    return sorted(candidatos, key=lambda nid: distancia_xor(id_objetivo, nid))[:k]

# ejemplo con IDs de 8 bits para simplificar
objetivo = 0b01100110
red = [0b01100000, 0b11111111, 0b01100111, 0b10000000]
print(mas_cercanos(objetivo, red, k=2))
# devuelve los 2 IDs con distancia XOR menor al objetivo

Esta función es el corazón de todo el algoritmo: cualquier nodo puede ordenar a cualquier conjunto de candidatos por cercanía sin coordinarse con nadie más.

Paso 2: insertar en un k-bucket

class KBucket:
    def __init__(self, k=20):
        self.k = k
        self.nodos = []  # lista ordenada: mas reciente al final

    def insertar(self, nodo_id):
        if nodo_id in self.nodos:
            self.nodos.remove(nodo_id)
            self.nodos.append(nodo_id)  # se mueve al final: sigue vivo
        elif len(self.nodos) < self.k:
            self.nodos.append(nodo_id)
        else:
            # bucket lleno: se hace ping al mas antiguo (self.nodos[0])
            # si no responde, se descarta y entra el nuevo nodo
            pass

La regla de reemplazo es deliberada: Kademlia prefiere nodos antiguos sobre nodos nuevos, porque un nodo que lleva tiempo conectado es estadísticamente más confiable que uno recién visto. Esto hace que la red sea más resistente a un atacante que inunda con nodos efímeros.

Paso 3: búsqueda iterativa completa (simulación)

def buscar(id_objetivo, mi_bucket, red_simulada, alpha=3, k=20):
    consultados = set()
    mejores = mas_cercanos(id_objetivo, mi_bucket.nodos, k)
    while True:
        candidatos = [n for n in mejores if n not in consultados][:alpha]
        if not candidatos:
            break
        nuevos = []
        for nodo in candidatos:
            consultados.add(nodo)
            nuevos.extend(red_simulada.get(nodo, []))
        combinados = list(set(mejores + nuevos))
        actualizados = mas_cercanos(id_objetivo, combinados, k)
        if actualizados == mejores:
            break  # ninguna ronda mejoro: converge
        mejores = actualizados
    return mejores

El ciclo se detiene cuando una ronda completa no acerca más al objetivo, la condición de convergencia del algoritmo real. En una red de miles de nodos esto toma pocas iteraciones, porque cada ronda reduce la distancia XOR de forma significativa.

Cómo empezar: correr un nodo Kademlia real

Para experimentar sin escribir el protocolo desde cero, la librería kademlia de Python implementa el algoritmo completo sobre asyncio.

pip install kademlia

import asyncio
from kademlia.network import Server

async def main():
    servidor = Server()
    await servidor.listen(8468)
    await servidor.bootstrap([("127.0.0.1", 8469)])  # nodo semilla de la red

    await servidor.set("clave-ejemplo", "valor-guardado-en-la-dht")
    resultado = await servidor.get("clave-ejemplo")
    print(resultado)  # "valor-guardado-en-la-dht"

    servidor.stop()

asyncio.run(main())

El método bootstrap() es la única dependencia externa real: un nodo nuevo necesita conocer al menos un nodo ya conectado a la red para empezar a poblar su tabla de ruteo. A partir de ahí, set() y get() reparten la lectura y escritura entre los nodos más cercanos a la clave, calculados con la misma distancia XOR del ejemplo anterior.

💡 Tip: para probar con más de un nodo en tu máquina, levantá varios procesos con puertos distintos y usá 127.0.0.1 como dirección de bootstrap de cada uno.

Casos de uso reales

BitTorrent fue el primer despliegue masivo. Antes de 2005, cada torrent dependía de un tracker HTTP central que listaba quién tenía el archivo. Si el tracker caía, el torrent quedaba huérfano aunque miles de pares siguieran conectados. La Mainline DHT (BEP 5) resolvió eso: hoy cualquier cliente BitTorrent participa en una única DHT global compartida entre todos los torrents.

IPFS y Filecoin usan la implementación de Kademlia dentro de libp2p para dos cosas distintas: encontrar qué nodo tiene el contenido de un hash de contenido (content routing) y descubrir la dirección de red de otro nodo (peer routing).

Ethereum usa una variante de Kademlia en su protocolo discv5 para que los nodos se encuentren entre sí en la red P2P, antes incluso de empezar a sincronizar bloques o transacciones.

Errores comunes y buenas prácticas

El problema más citado contra las DHT tipo Kademlia es el ataque Sybil: un atacante crea miles de identidades falsas para rodear una clave específica y censurar o interceptar el tráfico hacia ella. Kademlia no lo resuelve por diseño; mitigarlo requiere capas externas, como IDs de nodo derivados de una prueba costosa de generar en cantidad.

Un segundo riesgo es el ataque eclipse: rodear a un nodo específico, no a una clave, con nodos maliciosos para aislarlo de la red real y mostrarle una vista falsa. La defensa práctica es diversificar las fuentes de bootstrap y refrescar buckets periódicamente en vez de confiar en una sola tabla de ruteo estática.

También es común subestimar el churn: en una red pública, buena parte de los nodos se desconecta en minutos. Por eso el algoritmo hace ping periódico a los buckets inactivos y prioriza nodos antiguos sobre nuevos, como vimos en el paso 2 del ejemplo. Ignorar el refresco de buckets es el error de implementación más frecuente: una tabla de ruteo que no se actualiza queda ciega a buena parte de la red en cuestión de horas.

Un detalle que sorprende a quien implementa Kademlia por primera vez: los pares clave-valor guardados con STORE expiran solos, típicamente a las 24 horas. El nodo original debe volver a publicarlos antes de que caduquen, o el valor desaparece de la red aunque el nodo que lo originó siga conectado.

Comparativa: Kademlia frente a otras DHT

Antes de elegir un diseño de DHT conviene mirar el contexto de uso: no es lo mismo una red pública con miles de participantes anónimos que un clúster interno controlado por un solo operador.

Diseño	Cuándo usarlo	Ventaja	Limitación
Kademlia	Redes P2P públicas con alto churn (BitTorrent, IPFS)	Ruteo O(log n) simple, tolera fallas sin coordinación	Vulnerable a Sybil/eclipse sin capas extra
Chord	Sistemas académicos o con topología de anillo controlada	Prueba formal de convergencia, diseño muy simple	Peor tolerancia a fallas simultáneas que Kademlia
Pastry	Redes que necesitan ruteo consciente de proximidad de red real	Optimiza la latencia física, no solo la lógica	Más compleja de implementar y depurar
Tracker centralizado	Redes pequeñas o controladas por un solo operador	Simplicidad total, consultas instantáneas	Punto único de falla y de censura

Profundizando: por qué la métrica XOR es la pieza clave

La elección de XOR como métrica de distancia no es cosmética. XOR es simétrica (d(a,b) = d(b,a)), cumple la desigualdad triangular y, a diferencia de otras métricas posibles, es unidireccional: para cualquier punto de referencia y cualquier distancia, existe un único punto a esa distancia exacta.

Esa unidireccionalidad permite que la información aprendida durante una búsqueda sea siempre útil en la siguiente: cuando un nodo A aprende sobre un nodo C mientras busca a B, esa información sirve tanto si A vuelve a buscar a B como si busca cualquier otro objetivo cercano a C. Con métricas ambiguas, como la distancia en anillo modular de Chord, esa reutilización de información es más limitada.

💭 Clave: la propiedad unidireccional de XOR significa que dos nodos nunca están a la misma distancia de un tercero salvo que sean el mismo nodo, así que la tabla de ruteo nunca tiene ambigüedad sobre a quién preguntar primero.

El otro detalle fino es la diferencia entre búsqueda iterativa, la que implementamos arriba, donde el nodo buscador controla cada ronda, y búsqueda recursiva, donde cada nodo reenvía la petición al siguiente. Kademlia usa iterativa porque le da al buscador control total sobre el paralelismo y el timeout de cada salto, a costa de más mensajes por la red que una cadena recursiva. El valor típico α=3 equilibra latencia y tráfico de red: subirlo acelera la convergencia pero multiplica los mensajes en paralelo; bajarlo ahorra ancho de banda a costa de más rondas.

flowchart LR
    subgraph Centralizado["Modelo con tracker central"]
    T["Tracker"] --- P1["Par 1"]
    T --- P2["Par 2"]
    T --- P3["Par 3"]
    end
    subgraph DHT["Modelo Kademlia"]
    N1["Nodo 1"] --- N2["Nodo 2"]
    N2 --- N3["Nodo 3"]
    N1 --- N3
    end

📖 Resumen en Telegram: Ver resumen

Tu próximo paso: instalá la librería kademlia con pip install kademlia y levantá dos nodos locales en puertos distintos para ver el bootstrap() y el set()/get() funcionando entre ellos.

Preguntas frecuentes

¿Kademlia necesita un servidor central para arrancar?

No necesita un servidor permanente, pero sí un nodo semilla (bootstrap) al que conectarse la primera vez. Ese nodo puede ser cualquier otro miembro activo de la red, no un servidor con privilegios especiales.

¿Qué pasa si el nodo que busco ya no está conectado?

La búsqueda iterativa converge igual: devuelve los nodos vivos más cercanos al ID objetivo, que en una DHT de almacenamiento clave-valor son los responsables de guardar esa clave según la distancia XOR.

¿Por qué IDs de 160 bits y no menos?

160 bits corresponden al tamaño de un hash SHA-1, que es lo que usa el diseño original para generar identificadores con probabilidad prácticamente nula de colisión entre nodos.

¿Kademlia es lo mismo que blockchain?

No. Kademlia es una estructura de ruteo y almacenamiento distribuido, sin consenso ni orden total de eventos. Una blockchain puede usar Kademlia, como discv5 en Ethereum, solo para que los nodos se encuentren, no para ponerse de acuerdo sobre el estado.

¿Se puede usar Kademlia para una aplicación privada, no P2P pública?

Sí. Cualquier sistema que necesite ubicar datos entre muchos nodos sin un índice central puede adoptar el diseño, aunque en redes pequeñas y confiables el costo de resolver Sybil o eclipse suele no justificarse frente a un directorio centralizado simple.

Referencias

• Kademlia: A Peer-to-peer Information System Based on the XOR Metric: el paper original de Maymounkov y Mazières, 2002.
• BEP 5: DHT Protocol: la especificación de la Mainline DHT que usa BitTorrent.
• Kademlia DHT en libp2p: documentación oficial de la implementación que usan IPFS y Filecoin.
• bmuller/kademlia: implementación de referencia en Python sobre asyncio, usada en los ejemplos de este artículo.
• Kademlia en Wikipedia: resumen general del algoritmo y su historia.

📱 ¿Te gusta este contenido? Únete a nuestro canal de Telegram @programacion donde publicamos a diario lo más relevante de tecnología, IA y desarrollo. Resúmenes rápidos, contenido fresco todos los días.

Imagen destacada: Foto de GuerrillaBuzz en Unsplash