theory - resolucion - utilizacion de tablas hash
Explicación básica simple de una tabla hash distribuida(DHT) (5)
¿Podría alguien dar una explicación sobre cómo funciona un DHT?
Nada demasiado pesado, solo lo básico.
Echa un vistazo a http://en.wikipedia.org/wiki/Distributed_hash_table O a esta diapositiva de PowerPoint
Los DHT proporcionan el mismo tipo de interfaz para el usuario que una tabla hash normal (busca un valor por clave), pero los datos se distribuyen a través de una cantidad arbitraria de nodos conectados. Wikipedia tiene una buena introducción básica que estaría esencialmente regurgitando si escribo más:
Me gustaría agregar a la útil respuesta de HenryR ya que solo tuve 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.
Compare 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.
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 de los cuales se hace responsable 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, supongamos 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 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.
Hay muchas otras estructuras de superposición como esta que utilizan 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.
Lee la página de wikipedia, y si realmente quieres saber algo más, echa un vistazo a esta coursepage de Harvard que tiene una lista de lectura bastante completa.
echa un vistazo al Dynamo de Amazon, explica una implementación de DHT sencilla pero novedosa basada en hash consistente en círculos.