Tabla de hash distribuida

Las tablas de hash distribuidas, conocidas por las siglas DHT (del inglés, Distributed Hash Tables), son un tipo de tablas de hash que almacenan pares de clave-valor y permiten consultar el valor asociado a una clave, en las que los datos se almacenan de forma distribuida en una serie de nodos (sistemas distribuidos) y proveen un servicio eficiente de búsqueda que permite encontrar el valor asociado a una clave. Para esto último usan un sistema de enrutado que permite encontrar de forma eficiente el nodo en el cual está almacenada la información que se necesita.

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 del protocolo BitTorrent, la red Kad, el Storm botnet, YaCy, la Coral Content Distribution Network, Retroshare, etc...

Tabla de hash distribuida.

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 proporcionar un servicio de compartición de archivos.

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

• Napster fue el primer sistema de distribución de contenido P2P a gran escala. 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, además de demandas legales.
• Gnutella y redes similares usaban un modelo de consultas por inundación, donde cada búsqueda resultaba en un mensaje que se repetía a todas las máquinas en la red. Este método evitaba el problema de tener un único punto de fallo (el servidor centralizado), 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ó.

Propiedades

Las DHTs destacan las siguientes propiedades:

• Autonomía y 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 se debe coordinar con solo 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 solamente 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 equilibrado 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).

Las redes DHT son buenas para:

• Almacenamiento distribuido de cosas con nombre conocido.
• Muy escalables pues automáticamente distribuyen la carga a los nuevos nodos que se unen a la red.
• Robustez contra fallos de nodos, los datos automáticamente migran fuera de los nodos que fallan.
• Son auto organizadas, no necesitan de un servidor central. La parte centralizada es únicamente para localizar los nodos que siguen dependiendo de los DNS.

son malas para:

• Búsquedas; consecuencia del algoritmo hash pues "abc" y "abcd" corresponden a nodos totalmente diferentes (aunque el valor buscado es muy similar)
• Problemas de seguridad; es complicado verificar la integridad de los datos almacenados

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 cadenas 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 una circunferencia y δ(k1,k2) es la distancia alrededor de dicha circunferencia 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. La localidad del hashing trata de asegurar que a claves similares se asignen objetos familiares. Esto puede permitir una ejecución más eficiente en la búsqueda, permitiendo búsquedas por rangos en tiempo logarítmico.

Red de overlay

Cada nodo mantiene una serie de enlaces 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 enlace 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, es porque 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.

Algunas opciones comunes para evaluar la eficiencia de las DHT son el grado/longitud de la ruta hasta el nodo que contiene la información búscada. $n$ es el número de nodos de la DHT, usando la notación Big-O:

Grado	Longitud de ruta	Nota
$O(1)$	$O(n)$
$O(\log n)$	$O(\log n/\log(\log n))$
$O(\log n)$	$O(\log n)$	más común pero no la óptima
$O(1)$	$O(\log n)$
$O({\sqrt {n}})$	$O(1)$

La opción más común es longitud de grado/ruta $O(\log n)$, no es la óptima en términos de longitud, pero permite una mayor flexibilidad en la elección de los vecinos. Varias DHT utilizan la flexibilidad de elegir a los vecinos que están cerca en términos de la latencia de red subyacente.

La longitud máxima de la red está muy relacionado con su diámetro, es el número de saltos del camino más largo, entre los caminos más cortos entre los nodos. En el peor de los casos 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 greedy 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.

Enrutamiento en una dimensión

Las implementaciones de DHT se diferencian, entre otras cosas, en la estructura de datos que usan para las búsquedas en $O(\log n)$.

Chord, por ejemplo, utiliza una estructura similar a una lista por saltos (skip-list). Las referencias a algunos de nodos son mantenidas de tal manera que un nodo está a la mitad de la distancia, uno a un cuarto, y así sucesivamente siguiendo potencias de 2. Así, el nodo que recibe la solicitud, la reenvía al nodo con el ID más alto y más pequeño que la clave.

Un nuevo nodo entra en el sistema haciendo una búsqueda de su ID (puede ser elegido al azar en el espacio de claves), para encontrar el nodo responsable de su ID, actualiza su sucesor y antecesor para que apunte al nuevo nodo. Así, el nodo se une a la red. Kademlia, Pastry y Tapestry utiliza una estructura similar de enlaces.

Una variación del Chord desde el año 2013 utiliza secuencias de Bruijn, según la cual solamente requiere que cada nodo sepa de otros dos, manteniendo así la búsqueda en $O(\log n)$.

Enrutamiento en múltiples dimensiones

Por otra parte, la CAN, por ejemplo, utilizando un espacio cartesiano n-dimensional. El espacio se divide en hiper-rectángulos llamados zonas y cada nodo es responsable de las llaves que pertenecen a una zona. Como la tabla enrutamiento, cada nodo tiene referencias a sus vecinos en el plano cartesiano. Un nuevo nodo para unirse a la DHT, elige al azar un punto en el espacio y utiliza la búsqueda para saber quien es el nodo responsable de la zona de particionamiento y el nodo se anuncia a los vecinos que actualizan sus tablas de enrutamiento.

Implementaciones de DHT en el mundo real y sus diferencias y mejoras sobre el modelo básico

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 nodo 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 nodo adecuados, siendo i un parámetro específico de implementación del DHT. En estos diseños de DHT, los nodo 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 nodo adecuados y enviar mensajes put (k, data) únicamente a dichos nodo. Esto reduce drásticamente el tráfico inútil, ya que los mensajes publicados solamente se envían a los nodo adecuados para almacenar la clave k y las búsquedas iterativas cubren un conjunto pequeño de nodo 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 nodo publiquen sus datos de presencia en la DHT, de forma que se puedan realizar búsquedas iterativas.

Ejemplos

Protocolos DHT e implementaciones

• Apache Cassandra
• BATON Overlay
• Mainline DHT - DHT estándar usado por BitTorrent (basado en Kademlia
• CAN (Content Addressable Network)
• Chord
• Kademlia
• Pastry
• P-Grid
• Tapestry
• TomP2P

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.
• Twister: Peer-to-peer microblogging.
• GNU Ring: Software de Mensajería y VoIP

• Datos: Q863506