Explicación básica simple de una tabla hash distribuida (DHT)

Question

¿Podría alguien dar una explicación sobre cómo funciona una DHT?

Nada demasiado pesado, solo lo básico.

Answer 1

Ok, son fundamentalmente una idea bastante simple. Un DHT le proporciona una interfaz tipo diccionario, pero los nodos se distribuyen a través de la red. El truco con los DHT es que el nodo que obtiene almacenar una clave en particular se encuentra mezclando esa clave, por lo que sus depósitos de tablas hash ahora son nodos independientes en una red.

Esto proporciona mucha tolerancia a fallas y confiabilidad, y posiblemente algún beneficio de rendimiento, pero también genera muchos dolores de cabeza. Por ejemplo, ¿qué sucede cuando un nodo sale de la red, por fallas o de otra manera? ¿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 forma pareja? Y cuando un nodo se une, ¿cómo evitas reacomodar todo? (Recuerde que debe hacer esto en una tabla hash normal si aumenta la cantidad de cubos).

Un ejemplo de DHT que aborda algunos de estos problemas es un anillo lógico de n nodos, cada uno con 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, 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 que están en un anillo), puede asumir la responsabilidad de decir la mitad del espacio de teclas de 3, por lo que ahora trata de 26-30 y el nodo 3 trata con 21 -25.

Existen muchas otras estructuras de superposición como esta que utilizan el enrutamiento basado en contenido para encontrar el nodo correcto en el que almacenar una clave. Ubicar una llave 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 O (log n) -hop, y algunos afirman que el enrutamiento O (1) -hop a costa de más mantenimiento.

Lea la página de la wikipedia, y si realmente quiere saberlo con profundidad, mire este coursepage en Harvard que tiene una lista de lectura bastante completa.

Answer 2

DHT proporcionan el mismo tipo de interfaz para el usuario como una tabla hash normal (buscar un valor por clave), pero los datos se distribuyen en una cantidad arbitraria de nodos conectados. Wikipedia tiene una buena introducción básica que estaría esencialmente regurgitando si escribo más -

http://en.wikipedia.org/wiki/Distributed_hash_table

Answer 3

Salida this Wikipedia article O esto powerpoint slide

Answer 4

echa un vistazo a Amazon's Dynamo, explica una implementación de DHT sencilla pero novedosa basada en hash consistente en círculos.

Answer 5

Me gustaría agregar a la útil respuesta de HenryR, ya que acabo de tener una idea del hash consistente. Una búsqueda de hash normal/ingenua es una función de dos variables, una de las cuales es el número de cubetas. La belleza del hashing consistente es que eliminamos la cantidad de cubetas "n" de la ecuación.

En el hashing 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 segmentos, "n". Entonces, para determinar en qué cubo/máquina está almacenado 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.

Comparar esto con el hash consistente. Vamos a definir "R" como el rango de una función hash. R es solo una constante. En hash consistente, la dirección de un objeto se encuentra en hash (x)/R. Como nuestra búsqueda ya no es una función de la cantidad de depósitos, terminamos con menos reasignaciones cuando cambiamos el número de segmentos.

http://michaelnielsen.org/blog/consistent-hashing/