¿Alguien podría dar una explicación sobre cómo funciona un DHT?
Nada demasiado pesado, solo lo básico.
177
Ok, son fundamentalmente una idea bastante simple. Un DHT le brinda una interfaz similar a un diccionario, pero los nodos se distribuyen a través de la red. El truco con los DHT es que el nodo que puede almacenar una clave en particular se encuentra al cifrar esa clave, por lo que, en efecto, los cubos de la tabla hash ahora son nodos independientes en una red.
Esto brinda mucha tolerancia a fallas y confiabilidad, y posiblemente algunos beneficios de rendimiento, pero también genera muchos dolores de cabeza. Por ejemplo, ¿qué sucede cuando un nodo abandona la red, si falla o no? ¿Y cómo redistribuye las claves cuando un nodo se une para que la carga esté más o menos equilibrada? Ahora que lo pienso, ¿cómo distribuyes las llaves de manera uniforme? Y cuando un nodo se une, ¿cómo evitas 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 responsable de 1 / n del espacio de teclas. 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 está afectado; 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 teclas 0-10, el segundo 11-20 y el tercero 21-30. Si aparece un cuarto nodo y se inserta entre los nodos 3 y 0 (recuerde, están en un anillo), puede asumir la responsabilidad de decir la mitad del espacio de teclas de 3, por lo que ahora se ocupa de 26-30 y el nodo 3 se ocupa de 21 -25.
Hay muchas otras estructuras de superposición como esta que usan enrutamiento basado en contenido para encontrar el nodo correcto en el que almacenar una clave. La localización de 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 el enrutamiento O (n) -hop. Otras estructuras, incluidos los anillos aumentados, garantizan el enrutamiento de O (log n) -hop, y algunos reclaman el enrutamiento de O (1) -hop a costa de un mayor mantenimiento.
Lea la página de wikipedia, y si realmente quiere saber un poco más, consulte esta página del curso en Harvard que tiene una lista de lectura bastante completa.
Los DHT proporcionan el mismo tipo de interfaz para el usuario que una tabla hash normal (busque un valor por clave), pero los datos se distribuyen en un número arbitrario de nodos conectados. Wikipedia tiene una buena introducción básica que esencialmente estaría regurgitando si escribiera más:
http://en.wikipedia.org/wiki/Distributed_hash_table
fuente
Me gustaría agregar a la útil respuesta de HenryR ya que solo tenía una idea del hashing consistente. Una búsqueda hash normal / ingenua es una función de dos variables, una de las cuales es el número de cubos. La belleza del hashing consistente es que eliminamos el número de cubos "n" de la ecuación.
En el hash ingenuo, la primera variable es la clave del objeto que se almacenará en la tabla. Llamaremos a la tecla "x". La segunda variable es el número de cubos, "n". Entonces, para determinar en qué cubo / máquina se almacena el objeto, debe calcular: hash (x) mod (n). Por lo tanto, cuando cambia el número de depósitos, también cambia la dirección en la que se almacena casi todos los objetos.
Compare esto con el hashing consistente. Definamos "R" como el rango de una función hash. R es solo una constante. En hashing consistente, la dirección de un objeto se encuentra en hash (x) / R. Dado que nuestra búsqueda ya no es una función del número de cubos, terminamos con menos reasignación cuando cambiamos el número de cubos.
http://michaelnielsen.org/blog/consistent-hashing/
fuente
hash(x)/Rle da 34500. Todavía necesita hacer 34500% 3 .