Puede que se de el caso de que encuentres alguna incompatibilidad con tu código o proyecto, recuerda probar siempre en un entorno de testing antes añadir el código al trabajo final.
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 llega a almacenar un determinado key se encuentra haciendo hash que keypor lo que, en efecto, sus cubos de tablas hash ahora son nodos independientes en una red.
Esto brinda 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 falla o de otra manera? ¿Y cómo se redistribuye? keys cuando un nodo se une para que la carga se equilibre aproximadamente. Ahora que lo pienso, ¿cómo distribuye uniformemente keys ¿de todos modos? 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 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 asume 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 algunos de los keys en sus nodos hermanos. La belleza de este enfoque es que ninguno de los otros nodos del anillo se ve afectado; solo los dos nodos hermanos tienen que redistribuir keys.
Por ejemplo, supongamos que en un anillo de tres nodos el primer nodo tiene keys 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, digamos, la mitad del espacio de claves 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 un key. Localizando un key 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 saltos O (log n) y algunos reclaman enrutamiento de saltos O (1) a costa de más mantenimiento.
Lea la página de wikipedia, y si realmente quiere saber un poco más, consulte esta página de cursos 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 key), 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 escribo más:
http://en.wikipedia.org/wiki/Distributed_hash_table
Me gustaría agregar a la respuesta útil de HenryR, ya que acabo de tener una idea del hashing consistente. Una búsqueda hash normal/ingenua es una función de dos variables, una de las cuales es la cantidad de cubos. La belleza del hashing consistente es que eliminamos el número de cubos “n” de la ecuación.
En hashing ingenuo, la primera variable es el key del objeto a almacenar en la tabla. Llamaremos al key “X”. La segunda variable es el número de cubos, “n”. Entonces, para determinar en qué depósito/máquina está almacenado el objeto, debe calcular: hash(x) mod(n). Por lo tanto, cuando cambia la cantidad de cubos, también cambia la dirección en la que se almacenan casi todos los objetos.
Compare esto con hash consistente. Definamos “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. Dado que nuestra búsqueda ya no es una función de la cantidad de depósitos, terminamos con menos reasignaciones cuando cambiamos la cantidad de depósitos.
http://michaelnielsen.org/blog/hashing-consistente/
Comentarios y calificaciones
Si estás contento con lo expuesto, puedes dejar una división acerca de qué te ha impresionado de esta reseña.