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. 500px|right|thumb|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 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 autoorganizadas, 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. es el número de nodos de la DHT, usando la notación Big-O:
Grado Longitud de ruta Nota más común pero no la óptima
La opción más común es longitud de grado/ruta , 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 .
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.