Comprender la tecnología distribuida no es difícil porque no es profunda, pero su diseño suele ser ingenioso.
Este artículo presenta un algoritmo de tecnología distribuida inteligente y común: Kademlia.
El algoritmo Kademlia es un algoritmo de enrutamiento y almacenamiento distribuido. ¿Qué es el almacenamiento distribuido? Imaginemos una escuela con 65.438.000 estudiantes. Ahora, de repente, la escuela decidió desmantelar la biblioteca (sin configurar un servidor centralizado) y distribuir todos los libros de la biblioteca a cada estudiante (todos los archivos se almacenan en cada nodo). Es decir, todos los estudiantes * * * juntos forman una biblioteca distribuida.
En este caso, hay varias preguntas clave que es necesario responder.
A continuación, echemos un vistazo a cómo el algoritmo Kademlia resuelve inteligentemente estos problemas.
Primero, echemos un vistazo a qué atributos tiene cada compañero (nodo):
Cada compañero mantendrá el siguiente contenido:
De acuerdo con la analogía anterior , puedes echar un vistazo a esta tabla:
(Para obtener una explicación del concepto de hash, consulta la Enciclopedia Baidu - Algoritmo Hash)
¿Por qué no todos los estudiantes tienen una tabla completa? comunicación (Cada nodo mantiene información de enrutamiento completa): primero, los nodos en el sistema distribuido entran y salen con mucha frecuencia. Cada vez que hay un cambio, se actualizará toda la libreta de direcciones de la red y el volumen de comunicación será muy grande; en segundo lugar, una vez que un compañero de clase es atacado por una mala persona, secuestro (el nodo es pirateado), los malos obtendrán inmediatamente el número de teléfono móvil de todos, lo cual no es seguro.
¿Cómo se distribuyen a los estudiantes los libros recopilados en la biblioteca después de haberlos indexado cuidadosamente? Los principios generales incluyen: 1) Los libros se pueden distribuir de manera relativamente uniforme en manos de los estudiantes, de modo que algunos estudiantes no tengan demasiados libros y la mayoría de los estudiantes ni siquiera tengan un libro 2) Cuando los estudiantes quieran encontrar un libro específico, que se puede buscar utilizando un método de índice relativamente simple.
Kademriya hizo los siguientes arreglos:
Suponiendo que el valor hash del título "Algoritmos distribuidos" es 00010000, este libro deberá guardarse con el ID de estudiante de 00010000 en las manos de los estudiantes. (Esto requiere que el rango del algoritmo hash sea consistente con el rango del ID del nodo. El ID del nodo de Kademlia es un binario de 160 bits. El ejemplo aquí se abrevia como ID del nodo)
Pero debemos tomar en cuenta que algunos estudiantes estarán ausentes. Si 00010000 no viene a la escuela hoy (el nodo no está en línea o completamente desconectado), ¿nadie recibirá el libro "Algoritmo distribuido"? El algoritmo requiere que este libro no solo exista en manos de un estudiante, sino que también exista en manos de K estudiantes cuyos números de estudiantes sean más cercanos a 00010000, es decir, 00010001, 00010010065438.
De manera similar, cuando necesites encontrar el libro Algoritmos distribuidos, aplica hash al título y obtén 00010000. Este es el número de llamada para que sepa a qué estudiante llamar. El problema restante es encontrar los números de teléfono móvil de estos estudiantes.
Como solo tienes la libreta de direcciones de algunos compañeros de clase, probablemente no tengas el número de teléfono móvil (dirección IP) de 00010000. Entonces, ¿cómo llega a sus estudiantes objetivo?
Una idea factible es encontrar un compañero de clase en su libreta de direcciones que tenga la información de contacto del compañero de clase objetivo. Como se mencionó anteriormente, la libreta de direcciones de cada estudiante está estratificada por distancia. El diseño del algoritmo es que cuanto más cerca esté un compañero de clase de usted, mayor será la probabilidad de que su número de teléfono móvil esté en su libreta de direcciones.
La idea central del algoritmo puede ser: cuando conoces la distancia entre tu compañero objetivo Z y tú, primero puedes encontrar un compañero B en tu libreta de direcciones que creas que es el más cercano al compañero Z y pedirle al compañero B que avance. y encuentra el número de teléfono móvil del compañero Z.
La distancia mencionada anteriormente es la distancia XOR (ID de nodo) entre los números de estudiantes. XOR se utiliza para operaciones binarias o de sí/no.
Da dos ejemplos:
La distancia entre 01010000 y 01010010 (es decir, el valor XOR de los dos ID) es 00000010 (convertido a decimal es 2);
La distancia entre 010000000 y 0000001 es 0100001 (convertida a decimal, que es 2^6 1, que es 65);
Y así sucesivamente.
¿Cómo se estratifica la libreta de direcciones por distancia? El siguiente ejemplo le indicará que la estratificación por distancia XOR puede entenderse básicamente como estratificación por número. Imagine el siguiente escenario:
Basado en 0000110, si un nodo tiene el mismo ID, excepto el último 1, dicho nodo solo tiene 1-000111 y el valor XOR con el nodo base es 065438. Para 0000110, dicho nodo se clasifica como "k-bucket 1";
Si el ID de un nodo es el mismo que el de todos los números anteriores pero diferente del penúltimo número, solo hay dos de esos nodos. nodos:0000101, 0000100, los valores XOR con el nodo base son 000011 y 0000010. Para 0000110, dichos nodos se clasifican como "k-bucket 2";
...
Si el ID de un nodo es el mismo que todos los números anteriores, pero diferente del enésimo desde abajo, entonces solo hay 2 de estos nodos (I-1), y la distancia desde el nodo base es [2 (i-1), 2i); para 0000110, dichos nodos se clasifican como "k cubo I";
Otra forma de entender la descripción anterior: si los nodos de toda la red se clasifican en un árbol binario ordenado por ID de nodo, cada hoja al final del árbol es un nodo. La siguiente figura es más intuitiva. Muestra la relación entre los nodos.
Volvamos a nuestra analogía. Cada estudiante solo mantiene una parte de la libreta de direcciones, que está estratificada según la distancia (se puede entender que la libreta de direcciones está estratificada según el número de estudiante y su propio número de estudiante), es decir, k-bucket1, k-bucket2 , K-Bucket3... Aunque cada uno El número real de estudiantes en K depósitos aumenta gradualmente, pero cada estudiante solo registra los números de teléfono móvil de K estudiantes en cada K depósito.
Debido a que la identificación del estudiante (ID del nodo) tiene 160 dígitos, la libreta de direcciones de cada estudiante se divide en 160 capas (el nodo * * tiene 160 k depósitos). Toda la red puede acomodar hasta dos compañeros de clase (nodos) de 160, pero cada compañero de clase (nodo) solo mantiene una libreta de direcciones de hasta 160 * k líneas (direcciones y puertos de otros nodos).
Ahora permítanos explicarle un proceso completo de solicitud de libros.
Un compañero de clase (estudiante número 0000110) quiere encontrar algoritmos distribuidos. a necesita calcular primero el valor hash del título, hash (algoritmo distribuido) = 00010000. Entonces A sabe que necesita encontrar un compañero de clase 00010000 (llamado compañero de clase Z) o un compañero de clase con un número de estudiante cercano a Z.
La distancia XOR entre el estudiante número 00010000 de Z y el suyo es 00010110, y el rango de distancia es [2^4, 2^5], por lo que este estudiante Z puede estar en k grupo 5 (en otras palabras , El número de estudiante de Z es diferente del quinto estudiante, por lo que el estudiante Z puede estar en k depósito 5. Luego, el estudiante A verificará si hay un estudiante Z 5 en su k depósito:
El mecanismo de consulta de Kademlia es un Es un poco como doblar constantemente una hoja de papel por la mitad para reducir el rango de búsqueda, asegurando así que para n estudiantes, solo necesite consultar el registro 2 (n) veces como máximo para encontrar la información de contacto del estudiante objetivo (es decir , para cualquier red A con [2 (n? 1), 2 n) un nodo requiere solo n pasos de búsqueda como máximo para encontrar el nodo objetivo).
Lo anterior es el principio básico del algoritmo Kademlia. Los detalles técnicos del protocolo se describen brevemente a continuación.
En el algoritmo de Kademlia, cada nodo tiene sólo cuatro instrucciones.
Este mecanismo garantiza que la entrada y salida de cualquier nodo no afectará a toda la red.
Kademlia es una tabla hash distribuida (DHT). DHT es un sistema distribuido descentralizado. En este tipo de sistema, cada nodo mantiene una parte del contenido de almacenamiento y el enrutamiento/dirección de otros nodos, de modo que cuando cualquier participante (nodo) en la red cambia (entra/sale), el impacto en toda la red es mínimo. . DHT se puede utilizar para crear aplicaciones más complejas, incluidos sistemas de archivos distribuidos, sistemas de intercambio de archivos entre pares, almacenamiento en caché web colaborativo, sistemas de nombres de dominio y comunicaciones en tiempo real.
El algoritmo Kademlia fue diseñado por Petar Maymounkov y David Mazières en 2002. Se caracteriza por superponer tablas hash con distancia XOR. Posteriormente, Kademlia fue adoptado como algoritmo subyacente por software peer-to-peer como eMule y BitTorrent. Kademlia puede servir como una de las bases de la tecnología de seguridad de la información.
Las ventajas de Kademlia son:
Referencia
Tabla Hash Distribuida de Wikipedia
Wikipedia-Kademlia
Kademlia : Un sistema de información peer-to-peer basado en la métrica XOR
Notas de Kademlia Prince Hall
Han Feng. Inteligencia artificial de cadena de bloques. Notas de traducción de "Guía y plan económico nuevo de Blockchain" de Xinxing Publishing House.