Coordinación

Coordinación #

En un sistema centralizado x = timestamp(); y = timestamp() da como resultado \( x \leq y \).

En un sistema distribuido, acordar en un valor temporal no es trivial.

¿Es posible sincronizar los relojes de los nodos de un sistema distribuido? La respuesta es sorprendentemente complicada.

Entonces… ¿Cómo coordinan sus actividades los procesos de un sistema distribuido?

Relojes físicos #

  • Existen situaciones donde es necesario que todos los nodos en un sistema acuerden en un valor de tiempo determinado.

  • Un reloj físico presenta deriva

  • Problemas:

    1. ¿Cómo sincronizamos el reloj interno con un reloj externo?
    2. ¿Cómo sincronizamos los relojes internos entre sí?

  • UTC:

    • Coordinated Universal Time
    • Estándar internacional
    • 40 emisoras de onda corta difunden una señal al comienzo de cada segundo UTC
      • Precisión $\pm 1$ ms a $\pm 10$ ms
    • Uso de satelites, por ejemplo GPS y relojes atómicos
      • Precisión $\pm 0,5$ ms

  • Sincronización de relojes:

    • Suponer un conjunto de nodos:
      • Desafio 1: que esten sincronizados con una referencia externa, por ejemplo UTC.
      • Desafio 2: que los relojes de los nodos difieran lo menos posible.
    • Exactitud: mantener la desviación con respecto a una fuente externa dentro de un rango específico.
    • Precisión: mantener la desviación entre dos relojes dentro de un rango específico.
    • Sincronización externa: mantener los relojes exactos.
    • Sincronización interna: mantener los relojes precisos.
    • Problema:
      • Los relojes fisicos no son exactos, presentan deriva
      • El reloj por software se basa en el reloj hardware
      • Segun la deriva un reloj puede ser más rapido o más lento en referencia a un reloj ideal
    • Fun facts:
      • Dos relojes exactos pueden ser precisos con una cota $2 \delta$
      • Sin embargo, ser precisos no indica nada acerca de la exactitud.

  • Servidor de tiempo:

    • Obtener un valor actualizado desde un servidor central (por ejemplo, que tenga un reloj UTC)
    • Implementación mediante una arquitectura cliente/servidor:
      • Servidor retorna al cliente respuesta con timestamp.
      • Cliente debe compensar el offset y delay.

  • NTP

    • Network Time Protocol

  • Ambientes inalambricos:

    • Requieren algoritmos diferentes
    • Ejemplo: Reference Broadcast Synchronization

Relojes lógicos #

  • Generalmente lo que importa es que los nodos esten de acuerdo en el orden de los eventos.

  • Relación happened-before:

    • $a$ y $b$ son eventos
    • Si $a$ ocurre antes que $b$ en un mismo proceso, entonces $a \rightarrow b$
    • Si $a$ es el envío de un mensaje y $b$ la recepción, entonces $a \rightarrow b$
    • Transitivo: si $a \rightarrow b$ y $b \rightarrow c$, entonces $a \rightarrow c$
    • Introduce un ordenamiento parcial sobre los eventos.

  • Diseño:

    • Cada evento $e$ tiene asociado un timestamp $C(e)$
    • Propiedad 1: si $a$ y $b$ son eventos en un mismo proceso y $a \rightarrow b$ entonces $C(a) < C(b)$
    • Propiedad 2: si $a$ y $b$ son envío y recepción de un mensaje respectivamente, entonces $C(a) < C(b)$

  • Implementación:

    • Cada proceso $P_i$ mantiene un reloj lógico $C_i$
    • Por cada evento en $P_i$, $C_i = C_i + 1$
    • Cada mensaje enviado por Pi tiene un timestamp ts(m) = C(i)
    • Cuando Pj recibe un mensaje m:
      • Ajusta su contador Cj con el máximo valor entre Cj y ts(m)
      • Antes de pasar el mensaje a la aplicación, incrementa Cj en uno.

  • El servicio de relojes lógicos es implementado en un middleware, idealmente la aplicación no tiene por que ocuparse.

  • Ejemplo de uso: multicast totalmente ordenado

Relojes vectoriales #

Al usar relojes lógicos si $C(a) < C(b)$ no implica que $a$ ocurra antes que $b$

Solución: relojes vectoriales

  • Cada nodo mantiene su propio reloj lógico
  • Mantiene información de los relojes lógicos del resto de los nodos
  • Se organizan como un vector o arreglo
    • $V[i]$ es el reloj lógico del nodo $i$
    • $V[j]$ es el reloj lógico del nodo $j$

Ahora el timestamp asociado a cada mensaje es un vector: ts(m) = VC

Para comparar dos relojes vectoriales, VCa < VCb si y solo si:

  • VCa[k] <= VCb[k] para cualquier k
  • existe al menos un k’ tal que VCa[k’] < VCb[k’]

Si se cumple VCa < VCb entonces un evento precede causalmente a otro.

Implementación: similar al reloj lógico

Ejemplo de uso: multicast totalmente ordenado.

Exclusión mutua #

  • Coordinar el acceso exclusivo a un recurso.

  • Estrategias:

    • Mediante permisos: acuerdo entre los procesos.
    • Utilizando un token: quien tiene el token, accede al recurso.

Centralizado #

  • Uso de un coordinador que otorga el acceso al recurso
  • Facil de implementar, sencillo de mantener.
  • Posibles problemas para escalar.

Descentralizado #

  • Recurso con N replicas, cada una con un coordinador asignado.
  • Acceder al recurso requiere votos positivos de al menos m > N/2 coordinadores.

Distribuido #

  • Uso de multicast totalmente ordenado para coordinar el acceso.
  • Requiere poder contactar a todos los procesos interesados en el mismo recurso.

Token ring #

  • Procesos organizados en un anillo lógico.
  • Token circula por el anillo.
  • Quien tiene el token puede acceder al recurso.

Comparación: #

  • Centralizado:
    • Requiere 3 mensajes para acceder/liberar el recurso (petición, recepción del ok, liberación).
  • Distribuido:
    • Si existen N nodos, debo envíar mensajes a cada uno y esperar confirmación de ok: 2(N-1) mensajes.
  • Token-ring:
    • El token puede recorrer indefinidamente el anillo hasta ser retenido para el acceso al recurso.
    • En el peor caso un nodo debe esperar N-1 mensajes hasta que le llegue el token (suponiendo un anillo de N nodos)

Ejemplo: exclusion mutua con Zookeeper #

  • En la práctica muchos sistemas distribuidos utilizan un coordinador centralizado

  • Zookeeper ofrece servicios para:

    • exclusion mutua
    • elección de lider
    • monitoreo
    • etc

  • Diseñado para ofrecer confiabilidad, tolerancia a fallas y escalabilidad

    • Aunque es logicamente un servicio centralizado, su implementación es un sistema distribuido

  • Usar zookeeper o servicios similares: ¡no hay que reinventar la rueda! (sobre todo una rueda complicada)

  • Zookeeper 101:

    • No hay primitivas bloqueantes
      • Las peticiones de un cliente siempre reciben una respuesta.
    • Ofrece un espacio de nombres, similar a un sistema de archivos.
    • Operaciones:
      • crear y eliminar nodos
      • leer y actualizar datos en nodos (las actualizaciones son completas, no parciales)
      • verificar si existe un nodo en particular
    • Tipos de nodos:
      • persistentes: deben ser creados y eliminados explicitamente
      • efímeros: son eliminados cuando la conexión del proceso que los creo se pierde
    • Servicio de notificaciones
      • Evita polling por parte de los clientes.

  • Ejemplo: obtener acceso exclusivo

    • Un proceso crea un nodo, por ejemplo con nombre /lock
    • Si existe, la operación falla indicando que ya existe
    • El proceso debe repetir la operación para obtenerlo
    • En caso de crearlo, para liberar el acceso elimina el nodo /lock
    • Problemas:
      • ¿que sucede cuando un cliente crea /lock y desaparece?
      • Proceso p2 puede solicitar notificaciones por /lock mientras /lock es eliminado
      • Estas sutilezas y muchas más son manejadas por zookeeper.

Algoritmos de elección #

  • Muchos algoritmos distribuidos requieren que un nodo actue como coordinador.

  • No importa en general cual nodo en particular sea el coordinador… pero alguien tiene que hacerlo.

  • Mediante un algoritmo de elección se escoje un nodo para que actue como coordinador.

  • En general se asume:

    • Cada proceso P cuenta con un identificador único id(P).
    • Cada proceso conoce a todo el conjunto de procesos (aunque no cuales estan funcionando).

  • El objetivo de estos algoritmos es que cuando finalice la elección todos los procesos hayan acordado el mismo lider.

Algoritmo del matón (bully) #

  • Considerar N procesos, cada uno con un identificador k, con k entre 0 y n-1.
  • Cuando un proceso k se da cuenta que el lider no responde:
    • Envía un mensaje ELECTION a todos los nodos con identificador > k.
    • Si ninguno responde, el nodo k asume el papel de líder.
    • Si alguno responde con OK, toma el control del proceso de elección y k desiste.
    • Eventualmente, sólo un proceso tomará el control, enviando el mensaje COORDINATOR.
  • Si un proceso caído retoma su ejecución, inicia una elección.
  • Como el proceso con mayor ID es el que gana, se lo conoce por el nombre de “bully algorithm”.

Elección en un anillo #

  • Suponer que cada nodo conoce su sucesor, y al siguiente a este, y al proximo, y así.

  • Cuando un nodo detecta que el coordinador no responde:

    • Envía un mensaje ELECTION a su sucesor (o al siguiente si este no responde), con su ID.
    • El receptor reenvia el mensaje ELECTION, agregando su propio ID.
    • Eventualmente, el mensaje retorna al emisor original.
    • En ese momento, el mensaje circula nuevamente ahora con el tipo COORDINATOR.
    • El mensaje contiene ahora: el nuevo coordinador (el ID mas alto) y que nodos estan activos en el anillo.

  • ¿Importa que dos o más procesos inicien una elección?

    • No, únicamente habrá mayor recarga en la red.

Elecciones en sistemas de gran escala #

Muchos algoritmos de elección suponen un número pequeño de nodos.

Las cosas se vuelven complicadas a medida que el número de nodos aumenta.

Un ejemplo es una red blockchain.

Proof of work #

Consiste en que los nodos compitan en base a su poder de cómputo

Para esto, compiten para ver quien es el primero en resolver un problema complejo pero soluble.

El ganador es el nodo que primero difunde una solución.

El nodo ganador se convierte en el líder: es quien añade la transacción a la cadena de bloques.

Multiples problemas:

  • Principalmente, consumo de energía.
  • ¿Cómo regular la complejidad del problema?

Proof of stake #

Elecciones en redes inalambricas #

En una red inalambrica, la transmisión no es necesariamente confiable, ni la topología permanece estática.

El algoritmo presentado por Vasudevan escoge el mejor líder.

Para elegir un líder un nodo difunde un mensaje ELECTION a sus vecinos.

Si un nodo vecino hubiera recibido ya un mensaje ELECTION, simplemente retorna un ACK.

Caso contrario, si recibe un mensaje ELECTION por primera vez recuerda al nodo emisor y retrasmite el mensaje.

En cuanto todos los nodos vecinos responda a esta retransmisión de ELECTION, el nodo responde al emisor original.

Coordinación basada en rumores #

Se puede utilizar rumores para recolectar información.

Consensuar un mismo valor:

  • Cada nodo $P_i$ escoge un valor arbitrario $v_i$
  • Cuando dos nodos $P_i$ y $P_j$ intercambian datos: $v_i, v_j \leftarrow (v_i + v_j)/2$
  • Eventualmente todos los nodos tendran el mismo valor (media de los valores iniciales)

Estimar el número de nodos:

  • El nodo $P_1$ escoge $v_1=1$, el resto de los nodos $v_i=0$
  • Si hay $N$ nodos, eventualmente todos tendran $v_i=1/N$
  • Se puede estimar el tamaño de la red como $1/v_i$

Seleccionar un nodo al azar:

  • Cada nodo $P_i$ seleccionar un valor $m_i$ al azar y setea $v_i=m_i$
  • Al intercambiar datos $P_i$ y $P_j$ realizan $v_i, v_j \leftarrow max{v_i, v_j}$
  • Si luego $m_i < v_i$, entonces el nodo $P_i$ pierde la competencia.
  • Eventualmente un único nodo será el ganador.

Aplicacion

  • Un nodo al azar inicia el proceso de estimación de números de nodos.
  • Si el numero de nodos es estable, se puede designar un nodo fijo para que realice el conteo.
  • Caso contrario, se pueden utilizar epocas o bien un nodo al azar cada tanto realiza un conteo.

Peer-sampling #

¿Cómo elegir un nodo al azar cuando no se conoce la totalidad de los nodos en el sistema?

Un nodo podría tener toda la información, pero no es una solución escalable.

Una solución es el uso de vistas parciales:

  • Cada nodo mantiene una lista de c nodos vecinos.
  • Los nodos intercambian parte de sus listas parciales con otros nodos (en su vista parcial).
  • Cada nodo actualiza su vista parcial, pero siempre manteniendo c nodos en la misma.

Si esto se repite regularmente, escoger un nodo al azar de la vista parcial es estadisticamente indistinguible de hacerlo de la totalidad de los nodos.

Construccion de redes superpuestas #

Es posible utilizar las vistas parciales para generar topologías estructuradas.

Un posible protocolo para lograrlo estaría dividido en dos capas:

  • Una capa inferior que mantiene la vista parcial y opera sobre la red no-estructurada.
  • Una capa superior que genera una topología estructurada en base a la vista parcial.

Rumores seguros #

La velocidad de propagación de datos puede generar problemas de seguridad/confiabilidad.

Por ejemplo, $c$ nodos pueden cooperar maliciosamente para cooptar la red:

  • Al intercambiar las vistas parciales, estos nodos envian $c/2$ entradas que sólo referencian a alguno de estos $c$ nodos.
  • Gradualmente, las vistas parciales de todos los nodos solo contienen referencias a un conjunto de estos $c$ nodos.

Se busca tratar de detectar y prevenir comportamiento malicioso

Los nodos maliciosos pueden ser detectados por el elevado número de referencias desde otros nodos (indegree)

Sin embargo, al detectarlos ya puede ser demasiado tarde

Una manera de mitigar es requerir que los nodos generen estadísticas:

  • Al intercambiar vistas parciales se puede realizar también estadísticas
  • Es importante que no se sepa cuando se utilizan para actualizar la vista parcial o para generar estadísticas
  • Un nodo malicioso no puede devolver siempre enlaces a otros nodos maliciosos, sería rápidamente descubierto
  • No queda otra que, de vez en cuando, “jugar con las reglas” de los nodos benignos