Acorde (de igual a igual)

Protocolo para tabla hash distribuida

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 dada ubicando primero el nodo responsable de esa clave.

Chord es uno de los cuatro protocolos originales de tablas hash distribuidas , junto con CAN , Tapestry y Pastry . Fue presentado en 2001 por Ion Stoica , Robert Morris , David Karger , Frans Kaashoek y Hari Balakrishnan , y fue desarrollado en el MIT . ^[1] El artículo de Chord de 2001 ^[1] ganó un premio ACM SIGCOMM Test of Time en 2011. ^[2]

Investigaciones posteriores de Pamela Zave han demostrado que el algoritmo Chord original (tal como se especifica en el artículo SIGCOMM de 2001, ^[1] el informe técnico de 2001, ^[3] el artículo PODC de 2002, ^[4] y el artículo TON de 2003 ^[5] ) puede ordenar incorrectamente el anillo, producir varios anillos y romper el anillo. ^[6]

Descripción general

A los nodos y las claves se les asigna un identificador de 16 bits mediante un algoritmo hash consistente . El algoritmo SHA-1 es la función hash base para el algoritmo hash consistente. El algoritmo hash consistente es fundamental para la robustez 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 identificadores con una posibilidad insignificante de colisión . Por lo tanto, también permite que los nodos se unan y abandonen la red sin interrupciones. En el protocolo, el término nodo se utiliza para referirse tanto al propio nodo como a su identificador (ID) sin ambigüedad. Lo mismo ocurre con el término clave . ${\displaystyle m}$

Al utilizar 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 hasta ( 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. ${\displaystyle 2^{m}}$ ${\displaystyle 0}$ ${\displaystyle 2^{m}-1}$ ${\displaystyle m}$

Cada nodo tiene un sucesor y un predecesor . El sucesor de un nodo es el siguiente nodo en el círculo de identificadores en el sentido de las agujas del reloj. El predecesor es en el sentido contrario a las agujas del reloj. Si hay un nodo para cada ID posible, 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. ${\displaystyle 2^{m}-1}$

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 identificadores, denotado por . Cada clave se asigna a (se almacena en) su nodo sucesor, por lo que buscar una clave es consultar . ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle successor(k)}$ ${\displaystyle k}$ ${\displaystyle successor(k)}$

Dado que el sucesor (o predecesor) de un nodo puede desaparecer de la red (por fallo o por marcharse), cada nodo registra un arco de nodos en medio del cual se sitúa, es decir, la lista de nodos que le preceden y de nodos que le siguen. Esta lista da como resultado una alta probabilidad de que un nodo sea capaz de localizar correctamente a su sucesor o predecesor, incluso si la red en cuestión sufre una alta tasa de fallos. ${\displaystyle 2r+1}$ ${\displaystyle r}$ ${\displaystyle r}$

Detalles del protocolo

Red de acordes de 16 nodos. Los "dedos" de uno de los nodos están resaltados.

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 dará lugar a un tiempo de consulta donde es la cantidad de máquinas en el anillo. ${\displaystyle successor(k)}$ ${\displaystyle O(N)}$ ${\displaystyle N}$

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, recuerde que es el número de bits en la clave hash. La entrada del 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 desea 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 (el "más grande" en el círculo cuyo ID es menor que ), hasta que un nodo descubra que la clave está almacenada en su sucesor inmediato. ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle i^{th}}$ ${\displaystyle n}$ ${\displaystyle successor((n+2^{i-1})\,{\bmod {\,}}2^{m})}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

Con una tabla de dedos de este tipo, la cantidad de nodos que se deben contactar para encontrar un sucesor en una red de N nodos es . (Vea la prueba a continuación). ${\displaystyle O(\log N)}$

Unión de nodos

Cada vez que se une un nuevo nodo, se deben mantener tres invariantes (las dos primeras garantizan la corrección y la última mantiene la velocidad de las consultas):

1. El sucesor de cada nodo apunta correctamente a su sucesor inmediato.
2. Cada clave se almacena en . ${\displaystyle successor(k)}$
3. La tabla de dedos de cada nodo debe ser correcta.

Para satisfacer estas 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. Se deben realizar las siguientes tareas para un nodo recién incorporado : ${\displaystyle n}$

1. Inicializar el nodo (el predecesor y la tabla de dedos). ${\displaystyle n}$
2. Notificar a otros nodos para actualizar sus predecesores y tablas de dedos.
3. El nuevo nodo adquiere las claves responsables de su sucesor.

El predecesor de se puede obtener fácilmente a partir del predecesor de (en el círculo anterior). En cuanto a su tabla de dedos, existen varios métodos de inicialización. El más simple es ejecutar consultas de búsqueda de sucesor para todas las entradas, lo que da como resultado un tiempo de inicialización. Un mejor método es verificar si la entrada en la tabla de dedos aún es correcta para la entrada. Esto conducirá a . El mejor método es inicializar la tabla de dedos a partir de sus vecinos inmediatos y realizar algunas actualizaciones, que es . ${\displaystyle n}$ ${\displaystyle successor(n)}$ ${\displaystyle m}$ ${\displaystyle O(M\log N)}$ ${\displaystyle i^{th}}$ ${\displaystyle (i+1)^{th}}$ ${\displaystyle O(\log ^{2}N)}$ ${\displaystyle O(\log N)}$

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:

• Estabilizar(): n pregunta a su sucesor por su predecesor p y decide si p debe ser el sucesor de n en su lugar (este es el caso si p se unió recientemente al sistema).
• Notificar(): notifica al sucesor de n de su existencia, para que pueda cambiar su predecesor a n
• Fix_fingers(): actualiza las tablas de dedos

Usos potenciales

• Duplicación cooperativa: mecanismo de equilibrio de carga mediante el cual una red local aloja información disponible para computadoras 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 compartido en tiempo: en una red, una vez que una computadora se une a la red, sus datos disponibles se distribuyen por toda la red para su recuperación cuando esa computadora se desconecta de la red. Así como 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 conectadas 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 es responsable de evaluarlas como una solución o no, por ejemplo, descifrado de códigos.
• También se utiliza en redes de sensores inalámbricos para mayor confiabilidad ^[7]

Bocetos de prueba

La ruta de enrutamiento entre los nodos A y B. Cada salto reduce la distancia restante a la mitad (o menos).

Con alta probabilidad, Chord contacta a los nodos para encontrar un sucesor en una red de nodos. ${\displaystyle O(\log N)}$ ${\displaystyle N}$

Supongamos que el nodo desea encontrar el sucesor de la clave . Sea el predecesor de . Deseamos encontrar un límite superior para la cantidad de pasos que se necesitan para que un mensaje se enrute desde a . El nodo examinará su tabla de dedos y enrutará la solicitud al predecesor más cercano de que tenga. Llame a este nodo . Si es la entrada en la tabla de dedos de , entonces tanto y están a distancias entre y desde a lo largo del círculo del identificador. Por lo 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. ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle i^{th}}$ ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle p}$ ${\displaystyle 2^{i-1}}$ ${\displaystyle 2^{i}}$ ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle p}$ ${\displaystyle 2^{i-1}}$ ${\displaystyle f}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle p}$

Este proceso de dividir a la mitad la distancia restante se repite, por lo que después de pasos, la distancia restante hasta es como máximo ; en particular, después de pasos, la distancia restante es como máximo . Debido a que los nodos se distribuyen de manera uniforme 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 de tales nodos. Debido a que el mensaje siempre avanza al menos un nodo, se necesitan como máximo pasos para que un mensaje atraviese esta distancia restante. El tiempo total de enrutamiento esperado es, por lo tanto , . ${\displaystyle t}$ ${\displaystyle p}$ ${\displaystyle 2^{m}/2^{t}}$ ${\displaystyle \log N}$ ${\displaystyle 2^{m}/N}$ ${\displaystyle \log N}$ ${\displaystyle \log N}$ ${\displaystyle O(\log N)}$

Si Chord realiza un seguimiento de los predecesores/sucesores, entonces, con alta probabilidad, si cada nodo tiene una probabilidad de 1/4 de fallar, find_successor (ver a continuación) y find_predecessor (ver a continuación) devolverán los nodos correctos. ${\displaystyle r=O(\log N)}$

Simplemente, la probabilidad de que todos los nodos fallen es , lo cual es una probabilidad baja; por lo que con alta probabilidad al menos uno de ellos está vivo y el nodo tendrá el puntero correcto. ${\displaystyle r}$ ${\displaystyle \left({{1} \over {4}}\right)^{r}=O\left({{1} \over {N}}\right)}$

Pseudocódigo

Definiciones de pseudocódigo

dedo[k]

primer nodo que tiene éxito ${\displaystyle (n+2^{k-1}){\mbox{ mod }}2^{m},1\leq k\leq m}$

sucesor

El siguiente nodo desde el nodo en cuestión en el anillo identificador

predecesor

El nodo anterior al nodo en cuestión en el anillo identificador

El pseudocódigo para encontrar el nodo sucesor de un id se proporciona a continuación:

// pedirle al nodo n que encuentre el sucesor de id n.find_successor(id)  // Sí, debería ser un corchete de cierre para que coincida con el paréntesis de apertura.  // Es un intervalo semicerrado.  si id ∈ (n, successor] entonces  devuelve successor de lo contrario // reenvía la consulta alrededor del círculo n0 := nodo anterior más cercano (id) devuelve n0.find_successor(id)// busca en la tabla local el predecesor más alto de id n.closest_preceding_node(id)  para i = m hasta 1 hacer  if (finger[i] ∈ (n, id)) then devolver el dedo[i] volver n

El pseudocódigo para estabilizar el anillo/círculo de cuerda después de las uniones y salidas de los nodos es el siguiente:

// crea un nuevo anillo de acordes. n.create() predecesor := nil sucesor := n// Unir un anillo de acordes que contiene el nodo n'. n.join(n') predecesor := nil sucesor := n'.find_successor(n)// llamado periódicamente. n pregunta al sucesor // sobre su predecesor, verifica si el sucesor inmediato de n es consistente y le informa al sucesor sobre n n.stabilize() x = sucesor.predecesor si x ∈ (n, sucesor) entonces sucesor := x sucesor.notificar(n)// n' piensa que podría ser nuestro predecesor. n.notify(n')  si predecesor es nulo o n'∈(predecesor, n) entonces predecesor := n'// se llama periódicamente. refresca las entradas de la tabla de dedos. // luego almacena el índice del dedo a corregir n.fix_fingers() siguiente := siguiente + 1 Si siguiente > m entonces siguiente := 1 dedo[siguiente] := buscar_sucesor(n+2 siguiente-1 );// se llama periódicamente. verifica si el predecesor ha fallado. n.check_predecessor()  si el predecesor ha fallado entonces predecesor := nil

Véase también

• Kademlia
• Coro
• OverSim : el marco de simulación de superposición
• SimGrid : un conjunto de herramientas para la simulación de aplicaciones distribuidas -

Referencias

1. Stoica, I. ; Morris, R.; Kaashoek, MF; Balakrishnan, H. (2001). "Chord: un servicio de búsqueda escalable entre pares para aplicaciones de Internet" (PDF) . ACM SIGCOMM Computer Communication Review . 31 (4): 149. doi :10.1145/964723.383071.
2. "Premio ACM SIGCOMM Test of Time Paper Award" . Consultado el 16 de enero de 2022 .
3. Stoica, I. ; Morris, R.; Liben-Nowell, D.; Karger, D.; Kaashoek, MF; Dabek, F.; Balakrishnan, H. (2001). Chord: Un servicio de búsqueda escalable entre pares para aplicaciones de Internet (PDF) (Informe técnico). MIT LCS. MIT. 819. Archivado desde el original (PDF) el 22 de julio de 2012.
4. Liben-Nowell, David; Balakrishnan, Hari; Karger, David (julio de 2002). Análisis de la evolución de los sistemas peer-to-peer (PDF) . PODC '02: Actas del vigésimo primer simposio anual sobre Principios de computación distribuida. págs. 233–242. doi :10.1145/571825.571863.
5. Stoica, I. ; Morris, R.; Liben-Nowell, D.; Karger, D.; Kaashoek, MF; Dabek, F.; Balakrishnan, H. (25 de febrero de 2003). "Chord: un protocolo de búsqueda escalable entre pares para aplicaciones de Internet". Transacciones IEEE/ACM sobre redes . 11 (1): 17–32. doi :10.1109/TNET.2002.808407. S2CID  221276912.
6. Zave, Pamela (2012). "Uso de modelado ligero para comprender los acordes" (PDF) . ACM SIGCOMM Computer Communication Review . 42 (2): 49–57. doi :10.1145/2185376.2185383. S2CID  11727788.
7. Labbai, Peer Meera (otoño de 2016). "T2WSN: SUPERPOSICIÓN DE CUERDAS DE DOS NIVELES ACTIVADA QUE MEJORA LA ROBUSTEZ Y LA RELACIÓN DE ENTREGA DE REDES DE SENSORES INALÁMBRICOS" (PDF) . Revista de tecnología de la información teórica y aplicada . 91 : 168–176.

Enlaces externos

• El Proyecto Acorde (redirección desde: http://pdos.lcs.mit.edu/chord/)
• Open Chord: una implementación de Java de código abierto
• Chordless: otra implementación de código abierto de Java
• jDHTUQ: una implementación de código abierto de Java. API para generalizar la implementación de sistemas DHT peer-to-peer. Contiene una interfaz gráfica de usuario en la estructura de datos de modo