La principal investigación en este artículo es el código de algoritmo consistente.
El MIT propuso el algoritmo de hash consistente en el MIT en 1997 (ver 0). El objetivo de diseño era resolver el problema de Hotpot en Internet, y su intención original era muy similar a la carpa. El hashing constante corrige el problema causado por el algoritmo de hashing simple utilizado por la carpa, de modo que DHT se puede aplicar realmente en entornos P2P.
El hashing consistente propone cuatro condiciones de adaptación que el algoritmo de hash debe cumplir en un entorno de caché que cambia dinámicamente:
El equilibrio significa que el resultado del hash se puede distribuir a todos los cachés tanto como sea posible, de modo que se pueda utilizar todo el espacio de caché. Muchos algoritmos hash pueden cumplir con esta condición.
La monotonidad se refiere a si se ha enviado algún contenido al caché correspondiente a través del hashing, y se agregan nuevos cachés al sistema. El resultado del hash debe garantizar que el contenido asignado original se pueda asignar al nuevo caché sin ser asignado a otros buffers en la colección de caché antiguo.
Los algoritmos de hashing simple a menudo no pueden cumplir con los requisitos de la monotonicidad, como el hash lineal más simple:
X → Ax + B Mod (P)
En la fórmula anterior, P representa el tamaño de todos los cachés. No es difícil ver que cuando el tamaño del caché cambie (de P1 a P2), todos los resultados del hash original cambiarán, por lo que no cumplirán los requisitos de la monotonicidad.
Los cambios en los resultados del hash significan que cuando cambia el espacio de caché, todas las relaciones de mapeo deben actualizarse en el sistema. En los sistemas P2P, los cambios de caché son equivalentes a unir o salir del sistema. Esta situación ocurre con frecuencia en los sistemas P2P, lo que traerá una gran carga de computación y transmisión. La monotonidad requiere que el algoritmo hash pueda evitar esta situación.
En un entorno distribuido, el terminal puede no ver todos los cachés, pero solo puede ver algunos de ellos. Cuando un terminal desea asignar contenido al caché a través del proceso de hashing, dado que el rango de caché visto por diferentes terminales puede ser diferente, el resultado del hash es inconsistente. El resultado final es que el mismo contenido se asigna a diferentes áreas de caché por diferentes terminales. Obviamente, esta situación debe evitarse porque hace que el mismo contenido se almacene en diferentes buffers, reduciendo la eficiencia del almacenamiento del sistema. La definición de dispersión es la gravedad de la situación anterior. Un buen algoritmo de hash debe poder evitar las inconsistencias tanto como sea posible, es decir, para minimizar la dispersión.
El problema de la carga en realidad está analizando el problema de la descentralización desde otra perspectiva. Dado que diferentes terminales pueden asignar el mismo contenido a diferentes buffers, para un búfer específico, también pueden mapearlo a diferentes contenidos por diferentes usuarios. Al igual que la dispersión, esta situación debe evitarse, por lo que un buen algoritmo de hashing debería poder minimizar la carga del búfer.
En la superficie, el hashing consistente está dirigido al problema del almacenamiento en búfer distribuido, pero si piensa en el búfer como un par en un sistema P2P y el contenido mapeado como varios recursos compartidos (datos, archivos, transmisiones de medios, etc.), encontrará que los dos realmente están describiendo el mismo problema.
En el algoritmo de hash consistente, cada nodo (correspondiente al par en el sistema P2P) tiene una ID asignada al azar. Al asignar contenido a un nodo, se realiza una operación de hash consistente utilizando la palabra clave del contenido y la identificación del nodo y obtiene el valor clave. El hashing consistente requiere que el valor clave y la ID del nodo estén en el mismo rango de valor. El valor de clave y la identificación de clave más simples pueden ser unidimensionales, como un conjunto de enteros de 0000 a 9999.
Al almacenar contenido en función del valor clave, el contenido se almacena en el nodo con la ID más cercana a su valor clave. Por ejemplo, si el valor clave es 1001, hay nodos con IDS 1000, 1010, 1100 en el sistema, y el contenido se asignará a 1000 nodos.
Para construir las rutas requeridas para la consulta, el hash de consistencia requiere que cada nodo almacene la información de ubicación (dirección IP) de su nodo de enlace ascendente (el valor de ID es mayor que el más pequeño entre sus propios nodos) y el nodo de enlace descendente (el valor de ID es menor que el más grande entre sus propios nodos). Cuando un nodo necesita encontrar contenido, puede decidir iniciar una solicitud de consulta al enlace ascendente o al nodo de enlace descendente en función del valor clave del contenido. Si un nodo que recibe la solicitud de consulta encuentra que tiene el objetivo solicitado, puede devolver directamente la confirmación al nodo que inicia la solicitud de consulta; Si encuentra que no pertenece a su propio alcance, puede reenviar la solicitud a su nodo de enlace ascendente/enlace descendente.
Para mantener la información de enrutamiento mencionada anteriormente, cuando un nodo se une/sale del sistema, los nodos adyacentes deben actualizar la información de enrutamiento de manera oportuna. Esto requiere que los nodos no solo almacenen información de ubicación del nodo de enlace descendente conectado directamente, sino que también conozcan información del nodo del enlace descendente indirecto a cierta profundidad (N-HOP) y mantengan dinámicamente la lista de nodos. Cuando un nodo sale del sistema, su nodo de enlace ascendente intentará conectarse directamente al nodo de enlace descendente más cercano. Después de que la conexión sea exitosa, obtendrá la lista de nodos de enlace descendente del nuevo nodo de enlace descendente y actualizará su propia lista de nodos. Del mismo modo, cuando se agrega un nuevo nodo al sistema, primero encuentre el nodo de enlace descendente de acuerdo con su propia ID y obtenga la lista del nodo de enlace descendente, y luego solicite al nodo de enlace ascendente que modifique su lista de nodos de enlace descendente, restaurando así la relación de enrutamiento.
conversar
El hash consistente básicamente resuelve el problema más crítico en un entorno P2P: cómo distribuir el almacenamiento y el enrutamiento en una topología de red dinámica. Cada nodo solo necesita mantener información de un pequeño número de nodos vecinos, y cuando el nodo se une/sale del sistema, solo un pequeño número de nodos relevantes participan en el mantenimiento de la topología. Todo esto hace que el hash consistente sea el primer algoritmo DHT práctico.
Sin embargo, el algoritmo de enrutamiento de hashing consistente todavía tiene deficiencias. Durante el proceso de consulta, el mensaje de consulta debe pasar por el paso O (N) (O (N) indica una relación proporcional con N, y N representa el número total de nodos en el sistema) antes de que pueda alcanzar el nodo de consulta. No es difícil imaginar que cuando el sistema sea muy grande, el número de nodos puede exceder un millón, y dicha eficiencia de consulta es obviamente difícil para satisfacer las necesidades de uso. Desde otra perspectiva, incluso si el usuario puede tolerar retrasos largos, la gran cantidad de mensajes generados durante el proceso de consulta traerá una carga innecesaria a la red.
paquete HeroTrix; import java.util.collection; import java.util.sortedmap; import java.util.treemap; clase pública consistente de consistencia <t> {// hash algoritmo privado final hashfunction hashfunction; // Número de nodos virtuales finales intiveresofricas; privado final de sortes de sortedmap <integer, t> t> treeMaP de treegurt, t> treeGerats, t/treeGugurent, t - treegurent, t/treegurent. T> (); público consistente (hashfunction hashfunction, int numberoFreplicas, colección <t> nodos) {this.hashfunction = hashfunction; this.numberOfReplicas = NumberOfReplicas; for (t nodo: nodos) {add (nodo);}} public void add (t node) {for (int i = 0; i <numberOfreplicas; i ++) {circle.put (hashfunction.hash (node.ToString ()+i), node);}} public r eliminar (t node) {for (inti = 0; i <i = 0; i); i ++) {circle.remove (hashfunction.hash (node.ToString ()+i));}} // Algoritmo clave public t get (clave de objeto) {if (circle.isEmpty ()) {return null;} // calcula el valor de hash int hash = hashfunction.hash (clave); // si este valor no se incluye if (! circle.containskey (hash)) {sortedmap <integer, t> tailmap = circle.tailmap (hash); hash = tailmap.isempty ()? circle.firstkey (): tailmap.firstkey ();} return circle.get (hash);}}Lo anterior es todo el contenido de este artículo sobre las notas de aprendizaje de algoritmo de hash del idioma Java (ejemplos de código). Espero que sea útil para todos. Los amigos interesados pueden continuar referiéndose a otros temas relacionados en este sitio. Si hay alguna deficiencia, deje un mensaje para señalarlo. ¡Gracias amigos por su apoyo para este sitio!