Explicación básica simple de una Tabla Hash Distribuida (DHT)

Ok, son fundamentalmente una idea bastante simple. Un DHT le da una interfaz similar a un diccionario, pero los nodos se distribuyen a través de la red. El truco con DHTs es que el nodo que consigue almacenar una clave en particular se encuentra mediante el hashing de esa clave, por lo que en efecto sus cubos de tabla de hash ahora son nodos independientes en una red.

Esto da mucha tolerancia a fallas y confiabilidad, y posiblemente algún beneficio de rendimiento, pero también arroja muchos dolores de cabeza. Por ejemplo, lo que sucede cuando un nodo sale de la red, por error o de otra manera? Y cómo redistribuir claves cuando un nodo se une para que la carga esté aproximadamente equilibrada. Ahora que lo pienso, ¿cómo distribuir uniformemente las claves de todos modos? Y cuando un nodo se une, ¿cómo se evita repetir todo? (Recuerde que tendría que hacer esto en una tabla hash normal si aumenta el número de cubos).

Un ejemplo de DHT que aborda algunos de estos problemas es un anillo lógico de n nodos, cada uno asumiendo la responsabilidad de 1 / n del espacio de claves. Una vez que agrega un nodo a la red, encuentra un lugar en el anillo para sentarse entre otros dos nodos y asume la responsabilidad de algunas de las claves en sus nodos hermanos. La belleza de este enfoque es que ninguno de los otros nodos en el anillo se ven afectados; solo los dos nodos hermanos tienen que redistribuir las claves.

Por ejemplo, digamos que en un anillo de tres nodos el primer nodo tiene las claves 0-10, el segundo 11-20 y el tercero 21-30. Si aparece un cuarto nodo y se inserta entre nodos 3 y 0 (recuerde, están en un anillo), puede asumir la responsabilidad de decir la mitad del espacio clave de 3, por lo que ahora se ocupa de 26-30 y el nodo 3 se ocupa de 21-25.

Hay muchas otras estructuras superpuestas como esta que usan enrutamiento basado en contenido para encontrar el nodo correcto en el que almacenar una clave. Localizar una clave en un anillo requiere buscar alrededor del anillo un nodo a la vez(a menos que mantenga una tabla de búsqueda local, problemática en un DHT de miles de nodos), que es enrutamiento O (n)-hop. Otro las estructuras, incluidos los anillos aumentados, garantizan el enrutamiento de salto O(log n), y algunos afirman que el enrutamiento de salto O(1) cuesta más mantenimiento.

Lee la página de wikipedia, y si realmente quieres saberlo con un poco de profundidad, echa un vistazo a este página del curso en Harvard que tiene una lista de lectura bastante completa.