En informática , Chord es un protocolo y algoritmo para una tabla hash distribuida de igual a igual . Una tabla hash distribuida almacena pares clave-valor asignando claves a diferentes computadoras (conocidas como "nodos"); un nodo almacenará los valores de todas las claves de las que es responsable. Chord especifica cómo se asignan las claves a los nodos y cómo un nodo puede descubrir el valor de una clave determinada localizando primero el nodo responsable de esa clave.
Chord es uno de los cuatro protocolos de tabla hash distribuidos originales , junto con CAN , Tapestry y Pastry . Fue introducido en 2001 por Ion Stoica , Robert Morris , David Karger , Frans Kaashoek y Hari Balakrishnan , y fue desarrollado en el MIT . [1]
Descripción general
A los nodos y las claves se les asigna un -identificador de bits que utiliza hash coherente . El algoritmo SHA-1 es la función de hash base para un hash consistente. El hash consistente es parte integral de la solidez y el rendimiento de Chord porque tanto las claves como los nodos (de hecho, sus direcciones IP ) se distribuyen uniformemente en el mismo espacio de identificador con una posibilidad insignificante de colisión. Por lo tanto, también permite que los nodos se unan y salgan de la red sin interrupciones. En el protocolo, el término nodo se utiliza para referirse tanto a un nodo en sí como a su identificador (ID) sin ambigüedad. También lo es el término clave .
Utilizando el protocolo de búsqueda de acordes, los nodos y las claves se organizan en un círculo identificador que tiene como máximo nodos, que van desde a . ( debe ser lo suficientemente grande para evitar colisiones). Algunos de estos nodos se asignarán a máquinas o claves, mientras que otros (la mayoría) estarán vacíos.
Cada nodo tiene un sucesor y un predecesor . El sucesor de un nodo es el siguiente nodo en el círculo identificador en el sentido de las agujas del reloj. El predecesor es en sentido antihorario. Si hay un nodo para cada posible ID, el sucesor del nodo 0 es el nodo 1 y el predecesor del nodo 0 es el nodo.; sin embargo, normalmente hay "huecos" en la secuencia. Por ejemplo, el sucesor del nodo 153 puede ser el nodo 167 (y los nodos del 154 al 166 no existen); en este caso, el predecesor del nodo 167 será el nodo 153.
El concepto de sucesor también se puede utilizar para las claves. El nodo sucesor de una clave es el primer nodo cuyo ID es igual a o sigue en el círculo de identificación, denotado por . Cada clave se asigna a (almacenada en) su nodo sucesor, por lo que buscar una clave es consultar .
Dado que el sucesor (o predecesor) de un nodo puede desaparecer de la red (debido a una falla o salida), cada nodo registra un segmento completo del círculo adyacente a él, es decir, el nodos que lo preceden y el nodos que lo siguen. Esta lista da como resultado una alta probabilidad de que un nodo pueda ubicar correctamente a su sucesor o predecesor, incluso si la red en cuestión sufre una alta tasa de fallas.
Detalles del protocolo
Consulta básica
El uso principal del protocolo Chord es consultar una clave de un cliente (generalmente también un nodo), es decir, encontrar . El enfoque básico es pasar la consulta al sucesor de un nodo, si no puede encontrar la clave localmente. Esto conducirá a una tiempo de consulta donde es el número de máquinas en el ring.
Mesa de dedos
Para evitar la búsqueda lineal anterior, Chord implementa un método de búsqueda más rápido al requerir que cada nodo mantenga una tabla de dedos que contenga hasta entradas, recuerda que es el número de bits en la clave hash. La entrada de nodo contendrá . La primera entrada de la tabla de dedos es en realidad el sucesor inmediato del nodo (y, por lo tanto, no se necesita un campo sucesor adicional). Cada vez que un nodo quiere buscar una clave, pasará la consulta al sucesor o predecesor más cercano (dependiendo de la tabla de dedos) de en su tabla de dedos (la "más grande" en el círculo cuyo ID es menor que ), hasta que un nodo descubre que la clave está almacenada en su sucesor inmediato.
Con una tabla de dedos de este tipo, el número de nodos que deben contactarse para encontrar un sucesor en una red de N nodos es. (Vea la prueba a continuación).
Unión de nodo
Siempre que se une un nuevo nodo, se deben mantener tres invariantes (los dos primeros garantizan la corrección y el último sigue consultando rápidamente):
- El sucesor de cada nodo apunta correctamente a su sucesor inmediato.
- Cada clave se almacena en .
- La tabla de dedos de cada nodo debe ser correcta.
Para satisfacer estos invariantes, se mantiene un campo predecesor para cada nodo. Como el sucesor es la primera entrada de la tabla de dedos, ya no necesitamos mantener este campo por separado. Las siguientes tareas deben realizarse para un nodo recién unido:
- Inicializar nodo (el predecesor y la tabla de dedos).
- Notifique a otros nodos para que actualicen sus predecesores y tablas de dedos.
- El nuevo nodo toma las claves responsables de su sucesor.
El predecesor de se puede obtener fácilmente del predecesor de (en el círculo anterior). En cuanto a su tabla de dedos, existen varios métodos de inicialización. La más simple es ejecutar consultas de búsqueda de sucesor para todos entradas, resultando en tiempo de inicialización. Un mejor método es comprobar si La entrada en la tabla de dedos sigue siendo correcta para el entrada. Esto conducirá a. El mejor método es inicializar la tabla de dedos de sus vecinos inmediatos y hacer algunas actualizaciones, que es.
Estabilización
Para garantizar búsquedas correctas, todos los punteros sucesores deben estar actualizados. Por lo tanto, se ejecuta periódicamente un protocolo de estabilización en segundo plano que actualiza las tablas de dedos y los punteros sucesores.
El protocolo de estabilización funciona de la siguiente manera:
- Stabilize (): n pregunta a su sucesor por su predecesor py decide si p debería ser el sucesor de n (este es el caso si p se unió recientemente al sistema).
- Notify (): notifica al sucesor de n de su existencia, por lo que puede cambiar su predecesor an
- Fix_fingers (): actualiza las tablas de dedos
Usos potenciales
- Duplicación cooperativa: mecanismo de equilibrio de carga mediante una red local que aloja información disponible para equipos fuera de la red local. Este esquema podría permitir a los desarrolladores equilibrar la carga entre muchas computadoras en lugar de un servidor central para garantizar la disponibilidad de su producto.
- Almacenamiento de tiempo compartido: en una red, una vez que una computadora se une a la red, sus datos disponibles se distribuyen a través de la red para su recuperación cuando esa computadora se desconecta de la red. Además, los datos de otras computadoras se envían a la computadora en cuestión para su recuperación fuera de línea cuando ya no están conectados a la red. Principalmente para nodos sin la capacidad de conectarse a tiempo completo a la red.
- Índices distribuidos: recuperación de archivos a través de la red dentro de una base de datos con capacidad de búsqueda. por ejemplo, clientes de transferencia de archivos P2P.
- Búsquedas combinatorias a gran escala: Las claves son soluciones candidatas a un problema y cada clave se asigna al nodo, o computadora, que se encarga de evaluarlas como solución o no. por ejemplo, ruptura de código
- También se utiliza en redes de sensores inalámbricos para mayor confiabilidad [2]
Bocetos de prueba
Con alta probabilidad, contactos de acordes nodos para encontrar un sucesor en un -red de nodos.
Suponga nodo desea encontrar el sucesor de key . Dejar ser el predecesor de . Deseamos encontrar un límite superior para el número de pasos necesarios para que un mensaje se enrute desde a . Nodo examinará su tabla de dedos y enrutará la solicitud al predecesor más cercano de que tiene. Llamar a este nodo. Si es el entrada en mesa de dedos, luego ambos y están a distancias entre y de a lo largo del círculo identificador. Por tanto, la distancia entre y a lo largo de este círculo es como máximo . Por lo tanto, la distancia desde a es menor que la distancia desde a : la nueva distancia a es como máximo la mitad de la distancia inicial.
Este proceso de reducir a la mitad la distancia restante se repite, así que después pasos, la distancia restante para es como máximo ; en particular, después de pasos, la distancia restante es como máximo . Debido a que los nodos se distribuyen uniformemente al azar a lo largo del círculo identificador, el número esperado de nodos que caen dentro de un intervalo de esta longitud es 1 y, con alta probabilidad, hay menos detales nodos. Debido a que el mensaje siempre avanza por al menos un nodo, toma como máximopasos para que un mensaje recorra esta distancia restante. El tiempo total de enrutamiento esperado es por lo tanto.
Si Chord realiza un seguimiento de predecesores / sucesores, entonces con alta probabilidad, si cada nodo tiene una probabilidad de 1/4 de fallar, find_successor (ver más abajo) y find_predecessor (ver abajo) devolverán los nodos correctos
Simplemente, la probabilidad de que todos los nodos fallan es , que es una probabilidad baja; por lo que es muy probable que al menos uno de ellos esté vivo y el nodo tenga el puntero correcto.
Pseudocódigo
- Definiciones de pseudocódigo
- dedo [k]
- primer nodo que tiene éxito
- sucesor
- el siguiente nodo del nodo en cuestión en el anillo de identificación
- predecesor
- el nodo anterior del nodo en cuestión en el anillo de identificación
El pseudocódigo para encontrar el nodo sucesor de una identificación se da a continuación:
// pide al nodo n que encuentre el sucesor de idn.find_successor (id) // Sí, debería ser un corchete de cierre para que coincida con el paréntesis de apertura. // Es un intervalo medio cerrado. si id ∈ (n, sucesor] entonces devuelve sucesor else // reenvía la consulta alrededor del círculo n0: = nodo_precedente_más cercano (id) return n0.find_successor (id)// busca en la tabla local el predecesor más alto de idn.nodo_precediendo_más_cercano (id) para i = m downto 1 do if (dedo [i] ∈ (n, id)) entonces devolver el dedo [i] volver n
El pseudocódigo para estabilizar el anillo / círculo de acordes después de las uniones y salidas de nodos es el siguiente:
// crea un nuevo anillo de acordes.n. crear () predecesor: = nulo sucesor: = n// unirse a un anillo de acordes que contenga el nodo n '.n. unirse (n ') predecesor: = nulo sucesor: = n'.find_successor (n)// llamado periódicamente. n pregunta al sucesor// sobre su predecesor, verifica si n es inmediato// el sucesor es consistente y le dice al sucesor acerca de nn. estabilizar () x = sucesor.predecesor si x ∈ (n, sucesor) entonces sucesor: = x sucesor.notify (n)// n 'piensa que podría ser nuestro predecesor.n. notificar (n ') si predecesor es nil o n'∈ (predecesor, n) entonces predecesor: = n '// llamado periódicamente. actualiza las entradas de la tabla de dedos.// siguiente almacena el índice del dedo para arreglarn.fix_fingers () siguiente: = siguiente + 1 si siguiente> m entonces siguiente: = 1 dedo [siguiente]: = find_successor (n +); // llamado periódicamente. comprueba si el predecesor ha fallado.n.check_predecessor () si el predecesor ha fallado entonces predecesor: = nulo
Ver también
Referencias
- ^ Stoica, I .; Morris, R .; Kaashoek, MF; Balakrishnan, H. (2001). "Chord: un servicio de búsqueda escalable de igual a igual para aplicaciones de Internet" (PDF) . Revisión de comunicación informática ACM SIGCOMM . 31 (4): 149. doi : 10.1145 / 964723.383071 .
- ^ Labbai, Peer Meera (otoño de 2016). "T2WSN: SUPERPOSICIÓN DE ACORDES DE DOS CANSADOS TITIVADOS QUE AYUDAN A LA ROBUSTEZ Y LA RELACIÓN DE ENTREGA PARA REDES DE SENSORES INALÁMBRICOS" (PDF) . Revista de Tecnología de la Información Teórica y Aplicada . 91 : 168-176.
enlaces externos
- The Chord Project (redireccionamiento desde: http://pdos.lcs.mit.edu/chord/ )
- Open Chord: una implementación de Java de código abierto
- Chordless: otra implementación de Java de código abierto
- jDHTUQ: una implementación de Java de código abierto. API para generalizar la implementación de sistemas DHT peer-to-peer. Contiene GUI en estructura de datos de modo