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...
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:
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ó.
Las DHTs destacan las siguientes propiedades:
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:
son malas para:
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.
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.
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:
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.
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.
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.
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 .
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.
Las diferencias más destacables encontradas en casos prácticos de implementaciones de DHT incluyen las siguientes: