Explicación básica simple de una tabla de hash distribuida (DHT)
https://stackoverflow.com/questions/144360
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Podría alguien dar una explicación sobre cómo funciona un DHT?
Nada demasiado pesado, solo lo básico.
Solución
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 almacena una clave en particular se encuentra mediante el hashing de esa clave, por lo que, en efecto, sus grupos de tablas de hash ahora son nodos independientes en una red.
Esto proporciona mucha tolerancia a fallos y confiabilidad, y posiblemente algún beneficio de rendimiento, pero también provoca muchos dolores de cabeza. Por ejemplo, ¿qué sucede cuando un nodo abandona la red, si falla o no? Y, ¿cómo redistribuir las claves cuando un nodo se une para que la carga esté más o menos equilibrada? Ahora que lo pienso, ¿cómo distribuyes uniformemente las claves de todos modos? Y cuando un nodo se une, ¿cómo evitar rehacer todo? (Recuerda que tendrías que hacer esto en una tabla hash normal si aumentas el número de depósitos).
Un ejemplo de DHT que aborda algunos de estos problemas es un anillo lógico de n nodos, cada uno de los cuales es 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 del anillo están 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 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, por ejemplo, la mitad del espacio clave de 3, por lo que ahora se trata 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 ubicación de una clave en un anillo requiere buscar alrededor del nodo un nodo a la vez (a menos que mantenga una tabla de consulta 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), y algunos reclaman el enrutamiento O (1), a costa de un mayor mantenimiento.
Lea la página de wikipedia, y si realmente desea conocer un poco más a fondo, eche un vistazo a este coursepage en Harvard, que tiene una lista de lectura bastante completa.
Otros consejos
Los DHT proporcionan el mismo tipo de interfaz al usuario que una tabla hash normal (buscar un valor por clave), pero los datos se distribuyen sobre un número arbitrario de nodos conectados. Wikipedia tiene una buena introducción básica que esencialmente regurgitaría si escribiera más -
Me gustaría agregar a la útil respuesta de HenryR ya que acabo de tener una idea del hashing consistente. Una búsqueda de hash normal / ingenua es una función de dos variables, una de las cuales es el número de cubos. La belleza del hashing constante es que eliminamos el número de cubos " 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 grupos, " n " ;. Entonces, para determinar en qué grupo / 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.
Compara esto con hashing consistente. Definamos " R " como el rango de una función hash. R es solo una constante. En el hashing consistente, la dirección de un objeto se encuentra en hash (x) / R. Debido a que nuestra búsqueda ya no es una función del número de grupos, terminamos con menos reasignación cuando cambiamos el número de grupos.
Consulte este artículo de Wikipedia O este diapositiva de powerpoint
compruebe el Dynamo de Amazon, explica una implementación DHT sencilla pero novedosa basada en hashing de círculo consistente.
