Tabla de Hash Distribuido

Las tablas de hash distribuidas (en inglés, Distributed Hash Tables, DHT) son una clase de sistemas distribuidos descentralizados que proveen un servicio de búsqueda similar al de las tablas de hash, donde pares (clave, valor) son almacenados en el DHT, y cualquier nodo participante puede recuperar de forma eficiente el valor asociado con una clave dada. La responsabilidad de mantener el mapeo de las claves a los valores está distribuida entre los nodos, de forma que un cambio en el conjunto de participantes causa una cantidad mínima de interrupción. Esto permite que las DHTs puedan escalar a cantidades de nodos extremadamente grandes, y que puedan manejar constantes errores, llegadas y caídas de nodos.

Las DHTs forman una infraestructura que puede ser usada para construir servicios más complejos, como sistemas de archivos distribuidos, compartición de archivos peer-to-peer, sistemas de distribución de contenido, caché web cooperativo, multicast, anycast, servicios de DNS, y mensajería instantánea. Redes distribuidas importantes que usan DHT incluyen los trackers distribuidos de BitTorrent, la red Kad, el Storm botnet, YaCy, y la Coral Content Distribution Network.

Historia

Las búsquedas por medio de DHTs fueron motivadas originalmente por los sistemas peer-to-peer como Napster, Gnutella, y Freenet, que aprovechaban recursos distribuidos en Internet para proveer una única aplicación. En particular aprovechaban el creciente ancho de banda y capacidad de disco, para brindar un servicio de compartición de archivos.

La diferencia entre estos sistemas estaba en como encontraban los datos que tenían sus pares:

• Napster tenía un servicio de indexado central donde cada vez que un nodo se incorporaba, mandaba al servidor una lista de los archivos que poseía a nivel local. El servidor era el encargado de realizar las búsquedas y direccionarlas a los nodos que contenían los resultados. La desventaja estaba en que éste componente central hacia al sistema vulnerable a ataques.
• Gnutella y redes similares usaban un modelo de inundaciones, donde cada búsqueda resultaba en un mensaje que se repetía a todas las maquinas en la red. Éste método evitaba el problema de tener un único punto de falla, pero era significativamente menos eficiente que Napster.
• Freenet también era totalmente distribuido, y empleaba una clave heurística de ruteo, en donde cada archivo estaba asociado a una clave. Los archivos con claves similares tendían a agruparse en conjuntos de nodos similares. De esta forma era probable que las búsquedas fueran ruteadas a esos conjuntos, sin tener que visitar muchos nodos. Sin embargo no se garantizaba que se iba a encontrar los datos.

Las DHTs usan un ruteo basado en claves que incorpora los beneficios de la descentralización de Gnutella y Freenet, y la eficiencia y resultados garantizados de Napster. Una desventaja es que las DHTs así como Freenet, solo soportan búsquedas de coincidencia exacta, no obstante es posible implementar una funcionalidad de búsquedas por palabra clave como una capa superior a las DHTs.

Las primeras cuatro DHTs - CAN, Chord, Pastry y Tapestry- surgieron en la misma época durante el 2001. Desde entonces esta forma de búsqueda ha sido muy usada, principalmente desde que BitTorrent las incorporó.

Estructura

La estructura de una DHT puede ser descompuesta en una gran cantidad de componentes. La base es un espacio de claves abstracto. Un esquema de particionamiento de espacio de claves divide entre los nodos este espacio de claves. Una red de overlay conecta los nodos, permitiendo encontrar al titular de cualquier llave en el espacio de claves.

Una vez que estos componentes están en su lugar, el DHT puede ser usado para almacenamiento y recuperación de la siguiente manera: supongamos que el espacio de claves es una serie de strings de 160 bits. Para almacenar un archivo con un nombre y datos en el DHT, se aplica el hash SHA1 sobre el nombre del archivo, obteniendo una llave “K” de 160 bits. Luego se envía un mensaje put(K,data) a los nodos participantes en la DHT. El mensaje es enviado de nodo en nodo a través de la red hasta que alcanza al nodo responsable de la llave “K”, especificado en el espacio de claves. En este nodo se almacena el par (K,data). Si cualquier cliente quiere obtener el contenido del archivo, debe hacer un hash del nombre del archivo, lo cual produce la llave “K”; con ésta se genera un mensaje get(K) que es enrutado hasta llegar al nodo responsable, el cual responderá con los datos almacenados. A continuación se describen los componentes del espacio de claves y de la red, con el objetivo de capturar la idea principal de las DHTs; muchos diseños difieren en detalles.

Particionamiento del espacio de claves

La mayoría de las DHTs utilizan alguna variante de dispersión hash para mapear las claves con los nodos. Esta técnica implementa una función δ(k1,k2) que define una noción abstracta de la distancia entre la clave k1 y k2, la cual no está relacionada con la distancia geográfica o la latencia de la red. A cada nodo se le asigna una única clave denominada ID. Un nodo con el ID “i” posee todas las claves para las cuales “i” es el ID más cercano, medido con la función δ.

Ejemplo: la DHT Chord trata las claves como puntos en un circulo y δ(k1,k2) es la distancia alrededor del circulo desde k1 a k2 en sentido horario. Así, el espacio de claves circular se divide en segmentos contiguos cuyos extremos son los identificadores del nodo. Si i1 e i2 son dos identificadores adyacentes, el nodo con ID i2 posee todas las llaves que se encuentren entre i1 e i2.

El hashing tiene la propiedad que la remoción o adición de un nodo cambia únicamente las claves de los nodos con IDs adyacentes, y los demás nodos no son afectados. En una tabla hash tradicional la adición o eliminación de un nodo implica que casi la totalidad del espacio de claves sea reasignada. Dado que cualquier cambio generalmente es debido a un intenso uso del ancho de banda ocasionado por el movimiento de un nodo a otro de objetos almacenados en el DHT, es necesario minimizar esa reorganización para soportar de forma eficiente altas tasas de llegada y falla de nodos.

Red de overlay

Cada nodo mantiene una serie de links a otros nodos (sus vecinos o tabla de enrutamiento). En conjunto, estos enlaces forman la red. Un nodo escoge sus vecinos de acuerdo a una estructura específica, llamada “topología de la red”. Todas las topologías DHT comparten alguna variante de la siguiente propiedad: para cualquier clave “k”, pasa que el nodo tiene un ID que posee “k” o tiene un link a un nodo cuyo ID es más cercano a “k”, en términos de la distancia definida en el espacio de claves. De esta forma es fácil enrutar un mensaje hacia el dueño de cualquier clave “k” usando un algoritmo “greedy” (algoritmo voraz), que no necesariamente es óptimo a nivel global. El algoritmo consiste en reenviar el mensaje al vecino cuyo ID es más cercano a “k” de forma sucesiva, y cuando no existe ese vecino, pasa que se llegó al nodo más cercano el cual posee “k”. Este estilo de enrutamiento se suele llamar “key based routing”. Más allá de la exactitud del enrutamiento básico, dos limitaciones importantes en la topología son garantizar que el número máximo de saltos en cualquier ruta (longitud de la ruta) sea bajo, de forma que las solicitudes se completen rápidamente; y que el número máximo de vecinos de cualquier nodo sea mínimo, de forma que la sobrecarga de mantenimiento no sea excesiva.

La longitud máxima de la red es el número de saltos del camino más largo, entre los caminos más cortos entre los nodos. La longitud de ruteo de la red es al menos tan grande como su diámetro y puede ser mayor dado que el algoritmo de enrutamiento codicioso puede no encontrar el camino más corto.

Algoritmos para redes de overlay

Además del enrutamiento, existen muchos algoritmos que aprovechan la estructura de la red de overlay para el envío de un mensaje a todos los nodos, o un subconjunto de los nodos, en una DHT. Estos algoritmos se utilizan en aplicaciones para hacer multicast, consultas, o para recoger estadísticas.

Propiedades

Las DHTs destacan las siguientes propiedades:

• Descentralización: los nodos en conjunto forman el sistema sin ningún tipo de coordinación central.
• Escalabilidad: el sistema debe funcionar de manera eficiente, incluso con miles o millones de nodos.
• Tolerancia a fallas: el sistema debe ser fiable (en cierto sentido), incluso con nodos continuamente uniéndose, yéndose y fallando.

Una técnica clave utilizada para lograr estos objetivos es que cualquier nodo debe coordinar con sólo unos pocos nodos en el sistema - la más común, O (log n) de los n participantes (ver abajo) - de manera que ante un cambio en la composición sólo es necesario una cantidad limitada de trabajo. Algunos diseños de DHT buscan ser seguros contra los participantes maliciosos [2] y permiten a los participantes permanecer en el anonimato, aunque esto es menos común que en muchos otros sistemas peer-to-peer (sobre todo para compartir archivos), ver peer-to-peer anónimo. Por último, las DHTs deben ocuparse de cuestiones más tradicionales de sistemas distribuidos, como sistemas de balanceo de carga, integridad de datos y rendimiento (en particular, garantizar que las operaciones como el enrutamiento y almacenamiento de datos o la recuperación de manera completa se haga de forma rápida).

Implementaciones de DHT

Las diferencias más destacables encontradas en casos prácticos de implementaciones de DHT incluyen las siguientes:

• El espacio de direcciones es un parámetro de DHT. Varias DHTs utilizan un espacio de direcciones de 128 o 160 bits.
• Algunas DHT utilizan funciones de hash distintas a SHA1.
• La clave k puede ser un hash del contenido de un archivo en lugar de un hash de su nombre. De esta forma el cambio de nombre del archivo no impide a los usuarios poder encontrarlo.
• Algunas DHTs también pueden publicar objetos de diferentes tipos. Por ejemplo, la clave k podría ser el ID del nodo y los datos asociados podrían describir cómo ponerse en contacto con este nodo. Esto permite la publicación de información de presencia frecuentemente usada en aplicaciones de mensajería instantánea. El caso más simple de identificación es un número aleatorio que se utiliza directamente como clave k (de esta manera en DHTs de 160 bits el ID será un número de 160 bits, usualmente elegido al azar). En algunas DHTs, la publicación de los IDs de los nodos también es usado para optimizar las operaciones de DHT.
• Un clave k podría ser almacenada en más de un nodo para mejorar la fiabilidad de DHT por medio de la redundancia. Por lo general, en lugar de seleccionar un solo nodo, los algoritmos DHT seleccionan los i nodos adecuados, siendo i un parámetro específico de implementación del DHT. En estos diseños de DHT, los nodos acuerdan manejar cierto espacio de claves, donde el tamaño del espacio debe ser elegido de forma dinámica.
• Algunas DHTs avanzadas como Kademlia realizan en primer lugar búsquedas iterativas de la DHT para seleccionar un conjunto de nodos adecuados y enviar mensajes put (k, data) únicamente a dichos nodos. Esto reduce drásticamente el tráfico inútil, ya que los mensajes publicados sólo se envían a los nodos adecuados para almacenar la clave k y las búsquedas iterativas cubren un conjunto pequeño de nodos en lugar de todo el DHT. En dicha transmisión, los mensajes put (k, data) pueden aparecer como parte de un algoritmo de auto-sanación: si un nodo de destino recibe un mensaje put (k, data), pero considera que k está fuera de su área y conoce un nodo más cercano (en términos del espacio de claves DHT), el mensaje se reenvía a ese nodo. De lo contrario, los datos se indizan a nivel local. Esto conduce a sí mismo a un auto-balanceo de comportamiento. Estos algoritmos requieren que los nodos publiquen sus datos de presencia en la DHT, de forma que se puedan realizar búsquedas iterativas.

Ejemplos

Protocolos DHT e implementaciones

• CAN (Content Addressable Network)
• Chord
• Kademlia
• Pastry
• P-Grid
• Tapestry

Aplicaciones que usan DHT

• BitTorrent: Distribución de archivos. BitTorrent usa DHT como un tracker distribuido para emparejar clientes que comparten un archivo particular.
• Codeen: Web caching
• Coral Content Distribution Network
• Freenet: Red anónima.
• Deluge: Cliente BitTorrent.
• Dijjer: Red distribuida similar a Freenet.
• eMule: Compartición de archivos.
• FAROO: Motor de búsqueda peer-to-peer.
• GNUnet: Red de distribución similar a Freenet.
• JXTA: Plataforma P2P Opensource.
• KTorrent: Cliente BitTorrent KDE.
• LimeWire: Compartición de archivos.
• NEOnet: Compartición de archivos.
• OneSwarm: Compartición de archivos. La DHT Kademlia es usada para almacenar direcciones IP cifradas.
• Overnet: Compartición de archivos.
• The Circle: Compartición de archivos y chat.
• Transmission: Cliente BitTorrent.
• µTorrent: Cliente BitTorrent.
• Vuze: Primer cliente BitTorrent en implementar DHT. Vuze en aquella época se llamaba Azureus.
• Warez P2P: Compartición de archivos.
• YaCy: Motor de búsqueda distribuido.
• Ares Galaxy: Programa Per To Per de descarga.