PAC2 solucio - PAC2 solució candidata PDF

Preview

Summary

PEC2 SD2021-22/Estudios de Informática, Multimedia y TelecomunicaciónSistemas Distribuidos (Aula2)PEC2 – Segunda Prueba de Evaluación ContinuaPreguntas1. ReplicaciónLa replicación es una forma de conseguir la alta disponibilidad1a) Replicación activa y pasivaLa Replicación pasiva es un servicio tole...

Description

Sistemas Distribuidos (Aula2) PEC2 SD 2021-22/1

Estudios de Informática, Multimedia y Telecomunicación

Sistemas Distribuidos (Aula2) PEC2 – Segunda Prueba de Evaluación Continua

Preguntas 1. Replicación La replicación es una forma de conseguir la alta disponibilidad 1a) Replicación activa y pasiva La Replicación pasiva es un servicio tolerante a fallos, que emplea un gestor de réplicas primario (podrá hacer de cuello de botella) y uno o más gestores secundarios. Los frontales (poco funcionales) sólo se comunican con el gestor primario, el cual mantiene la consistencia secuencial, y si falla se hace que uno de los respaldos se promocione a primario. En este modelo, hay un servidor principal que es el responsable de administrar las réplicas. Los clientes simplemente le enviarán las solicitudes. Cuando el servidor primario recibe las solicitudes, actualizará la solicitud de réplica en otros servidores secundarios de respaldo. La replicación pasiva es tolerante a fallas, si el servidor primario falla, un servidor secundario cambiará su función y actuará como servidor primario. Otra ventaja es que el administrador de réplicas principal no actúa de forma determinista, por lo que es compatible con el servidor que utiliza tecnología multiproceso. La replicación pasiva es la más utilizada y menos costosa. Sin embargo, este modelo no tolera fallas bizantinas. Además, los servidores de respaldo pueden almacenar copias obsoletas. Otra desventaja es que solo hay un administrador de réplicas, por lo que el rendimiento podría disminuir si recibe una gran cantidad de solicitudes.

Este tipo de replicación pasa por las siguientes fases: - Petición: El frontal envía la petición al gestor primario - Coordinación: Dicho gestor primario emplea ordenación por cola FIFO - Ejecución: Ejecuta la petición y almacena la respuesta - Acuerdo: Para una petición de actualización, el gestor primario la envía a todos los respaldos, los cuales confirmarán la recepción - Respuesta: El gestor primario responde al frontal

Sistemas Distribuidos (Aula2) PEC2 SD 2021-22/1

La Replicación activa (o primario-backup) es un servicio tolerante a fallos, lo cual consigue fundamentalmente mediante la multidifusión fiable y totalmente ordenada, equivalente a un algoritmo de consenso. Todo encargado de la replicación ostenta el mismo papel, procesando las peticiones de manera independiente pero idéntica. Los frontales multi-difunden las peticiones a todos los gestores. En el modelo de replicación activa, cada solicitud realizada por un cliente se envía a todos los gerentes de réplica y lo procesan al mismo tiempo. El cliente hace una operación de sincronización con el primer administrador de réplicas que responde y rechaza los demás. Si uno de los administradores de réplicas deja de funcionar, no afecta al sistema, porque hay más. La principal ventaja de este modelo es que es muy apropiado en sistemas de tiempo real. que necesitan una respuesta rápida incluso cuando hay fallas en el sistema. En el otro Por otro lado, tolera fallas bizantinas, porque los clientes pueden comparar las respuestas de los administradores de réplicas. Sin embargo, la replicación activa requiere una comunicación síncrona y tiene un costo computacional elevado. Como dijimos anteriormente, los administradores de réplicas procesan cada solicitud al mismo tiempo, como resultado, será un uso elevado de ancho de banda de red y CPU. Además, otra desventaja es que en la replicación activa, la los gestores de réplicas deben actuar de forma determinista y, en la actualidad, la mayoría de los servidores son multiproceso, lo que hace complicado implementar este tipo de réplica.

Este tipo de replicación pasa por las siguientes fases (la anterior fase de ACUERDO comentada no es necesaria ahora debido a la multidifusión) - Petición: Usa multidifusión fiable. No envía otra petición hasta terminar. - Coordinación: Usa ordenación total. - Ejecución: La realizan los gestores. - Respuesta: Los gestores mandan la respuesta al frontal.

Sistemas Distribuidos (Aula2) PEC2 SD 2021-22/1

Diferencias entre replicación activa y pasiva: Ya podemos apreciar las diferencias en lo comentado anteriormente, y en los dos gráficos de funcionamiento anteriores. No obstante, resumo para hacer una comparativa entre ambos. REPLICACIÓN Petición

Coordinación Ejecución Acuerdo Respuesta Latencia Tolera fallos bizantinos Lineabilidad

ACTIVA Multidifusión a todos, se tratan de manera concurrente Ordenación total En todos los gestores ----El cliente recoge las mismas La reduce SI NO

PASIVA Solo se mandan al gestor

Cola FIFO Solo en el primario Se envía a todas las réplicas para actualizar Si es necesaria tras la actualización --NO SI

1b) Replicación master-master, una mejora frente a la master-slave La replicación es el proceso de copiar y mantener actualizados los datos en varios modos de bases de datos ya sean estos persistentes o no. Éste usa un concepto donde existe normalmente un nodo amo o maestro (master) y otros sirvientes o esclavos (slaves). No obstante, pueden existir varios máster, por lo que la replicación puede ser master-master o master-slave. La replicación master-master como ya se ha comentado es cuando hay dos o más maestros en un sistema, cada uno de ellos proporciona servicios de lectura y escritura, sincronizándose normalmente de forma asíncrona entre ellos, por lo que siempre es coherente. El posible problema de este modelo es cuando varios maestros modifican los mismos datos, ya que no es fácil fusionar conflictos entre los datos. Si estudiamos el diseño del reloj vectorial de DynamoDB vemos que esto no es tan simple y este diseño puede ser responsable de los conflictos de datos. DynamoDB y DBMS son ejemplos de uso. Diferencia con el modelo Master-Slave: El modelo Master-Master es una versión mejorada de Master-Slave. Una ventaja clara del maestro-maestro es que si un maestro cae, otros maestros podrán realizar los servicios de lectura y escritura, sin embargo, en el modelo maestro-esclavo, como los datos no se copian a otros maestros, los datos se perderían. MySQL y MariaDB DBMS son ejemplos de uso.

[Veamos unos gráficos comparativos]

Sistemas Distribuidos (Aula2) PEC2 SD 2021-22/1

Master-Slave replication

2. Apache Zookeeper Apache ZooKeeper es un proyecto de software libre, que ofrece un servicio para la coordinación distribuida y es altamente confiable, dando soluciones a varios problemas de coordinación en grandes sistemas distribuidos. Ofrece alta disponibilidad por redundancia, y se basa en un consenso distribuido, gestión de grupos, protocolos de presencia y los más importante para este trabajo, el proceso para la elección del líder, ya que siempre tiene que existir uno. Además, posee espacio de nombres jerárquico. 2a) Elección de líder Antes que nada, veamos un resumen del video propuesto (5 transparencias).

Sistemas Distribuidos (Aula2) PEC2 SD 2021-22/1

La parte más importante para el inicio de un clúster es la elección de Líder, ya que es la clave para garantizar la coherencia de los datos distribuidos. Al arrancar el clúster el proceso puede tener varias rondas de votación. Primero cada servidor crea una secuencia consigo mismo, mandado su id para intentar promocionar a líder, como todos reciben los id de los demás se crea una nueva ronda con el valor más alto, y en este caso del video queda elegido como líder el N80. Pero… ¿Qué pasa si el líder cae? Va en rueda de turnos. Cada proceso monitor intenta obtener el máximo id entre el suyo y su nodo sucesor, eligiendo a un nuevo líder en anillo hasta que se quede fijo el mayor id ya que el id se va propagando si es mayor que el anterior. Si no lo consigue llega el timeout y lo reintenta más tarde. En este caso saldrá N32. Veamos un ejemplo gráficamente de funcionamiento: Imaginemos que el proceso 1 detecta que el 28 ha caído y resulta que era el líder.

Sistemas Distribuidos (Aula2) PEC2 SD 2021-22/1

Pero… ¿Qué pasa si hay conflictos de id? Para solucionarlo, Zookeeper usa un sistema en dos fases. Se manda el comando NEW-LIDER al resto, el resto responde con ACK (confirmación ok) pero con el id mayor, el que recibe la mayoría de ACK’s responde con COMMIT, los que lo reciben actualizan su variable local que indica quien es el líder. Veamos un esquema explicativo Zookeeper.

Sistemas Distribuidos (Aula2) PEC2 SD 2021-22/1

2b) Comparativa Zookeeper no es el único algoritmo de elección automática de líder, por ejemplo, existe el algoritmo Abusón o las Concesiones (usado en Amazon). Para compararlos hay que hablar de dichos algoritmos primero. Las concesiones son relativamente fáciles de entender e implementar, y ofrecen tolerancia a errores integrada. También funcionan con una base de datos única que almacena al líder actual. Luego, la concesión necesita que el líder se muestre activo de forma periódica para indicar que todavía es el líder. Si no se muestra activo después de un tiempo, otros candidatos a líderes pueden tratar de quedar a cargo. Evita depender del tiempo, ya que es difícil asegurarse de que los relojes del sistema en un clúster estén sincronizados lo suficiente como para depender de esa sincronización para ordenar o coordinar las operaciones distribuidas. Durante los errores puede llegar a tener líderes dos o ninguno. Lo usa Amazon. El algoritmo abusón (o bully) funciona resumidamente de la siguiente manera. El convocante envía mensajes ELECCIÓN a los procesos que tengan un mayor id, si no responde nadie se queda el como COORDINADOR y lo anuncia al resto mandando tal mensaje, si alguien responde mediante un mensaje de RESPUESTA el convocante original se espera y deja tiempo al resto para que inicien un nuevo proceso de elección entre ellos. Se llama abusón ya que si un proceso ya sabe que tiene el id más alto se

Sistemas Distribuidos (Aula2) PEC2 SD 2021-22/1

queda como COORDINADOR y manda directamente tal mensaje al resto. Veamos un ejemplo gráfico.

ALGORITMO Cantidad de mensajes requeridos para la transacción Caída intermedia Seguridad Pervivencia Conocimiento de escritura

ZOOKEEPER 3*N-1

ABUSON N^2

NO SI SI Proceso siguiente

SI NO SI Todos los procesos

Como vemos en la comparativa, tengo que decir que la más importante diferencia es la cantidad de mensajes que se requieren para completar una elección, por otro lado, el algoritmo abusón no escala bien en casos de caídas y recuperaciones intermedias o bien en caso de fallos de timeout. No obstante, el abusón tiene la ventaja de que el conocimiento de escritura es total (por parte de todos), y de que actúa mejor ante caídas intermedias.

3. NTP El NTP es el Network Time Protocol, o de hora por Internet. Por ejemplo, el propio Windows se puede poner en otra con él o Unix por medio de su correspondiente demonio. Se emplea para sincronizar los relojes de los sistemas informáticos a través del enrutamiento de paquetes en redes con latencia variable. NTP utiliza UDP como su capa de transporte, usando el puerto 123. Está diseñado para resistir los efectos de la latencia variable, pero evidentemente al ser UDP no es confiable ni tiene acuse de recibo ni los datagramas tiene porque usar el mismo camino. 3a) Funcionamiento, como consigue escalar y se tolerante a fallos. NTP emplea el algoritmo conocido como Marzullo, con tiempo UTC (tiempo universal coordinado). La v4 del protocolo tiene una precisión de sincronización de 10

Sistemas Distribuidos (Aula2) PEC2 SD 2021-22/1

milisegundos a través de Internet y de 200 microsegundos en red local. Emplea un sistema de jerarquía de estratos de reloj, donde los sistemas de estrato 1 (servidores de tiempo primarios o Primary Time Servers) están sincronizados por medio de un dispositivo externo tal como un reloj GPS o algún reloj atómico. Los sistemas de estrato 2 de NTP derivan su tiempo de uno o más de los sistemas de estrato 1, y así consecutivamente. Todos los dispositivos técnicos que obtienen la hora de un servidor de tiempo primario o de un sistema de navegación por satélite se clasifican en la categoría estrato 0.

NTP v4.2 utiliza un reloj de referencia que actúa como punto fijo para todos los procesos de sincronización. Por lo tanto, todos los relojes están sincronizados respecto a ese reloj de referencia. Busca automáticamente las mejores fuentes de tiempo para realizar la sincronización. Es altamente escalable. Cada nodo de la red es capaz de transmitir información horaria en una estructura jerárquica bidireccional (punto a punto) o unidireccional (en una dirección). Es muy preciso. Puede solucionar los fallos de conexión. El protocolo NTP tiene problemas de seguridad, ya que envía toda la información en texto plano, no tiene ningún tipo de cifrado, autenticidad ni se comprueba la integridad de los datos. Para evitar esto, se ha diseñado el protocolo Network Time Security (NTS) que es la versión segura de NTP utilizando TLS y AEAD para proteger la comunicación. El timestamp es un número de 128 bits (versión 4 de NTP), de estos bits, los 32 o 64 primeros bits los usamos como potencia de 2 para indicar el tiempo en segundos transcurridos desde las 0:00 del 1 de Enero de 1900. Los segundos 32 o 64 bits se utilizan para indicar la fracción del segundo actual. Como se ha dicho ya, NTP es altamente escalable, ya que en cada red de sincronización es posible encontrar varios relojes de referencia. Por si fuera poco, cada nodo de la red es capaz de transmitir información horaria en una estructura jerárquica bidireccional o unidireccional. Un mismo equipo o nodo de la red puede actuar como cliente y servidor al mismo tiempo, como servidor atiende las peticiones NTP de los equipos inferiores y como cliente solicita el tiempo con mayor precisión a los equipos superiores, también algunos equipos pueden funcionar en modo ‘peer’ obteniendo el reloj de otro servidor pero pudiendo, a su vez, entregar el reloj a dicho servidor si así éste lo solicita. Como se ha dicho ya, NTP es tolerante a los fallos, como los problemas temporales de conexión de red, utilizando la información almacenada para determinar la hora actual o las desviaciones, en cuanto a la fiabilidad siempre busca la mejor fuente para sincronizarse, es decir, que puede utilizar mediciones del pasado para estimar el

Sistemas Distribuidos (Aula2) PEC2 SD 2021-22/1

tiempo actual y el error. Para minimizar los fallos acumulados, es capaz de seleccionar y combinar varias fuentes. Cuando es posible, el protocolo de tiempo de red detecta e ignora las fuentes de tiempo que proporcionan valores desviados de manera temporal o permanente. Candidatos múltiples pueden combinarse para reducir al mínimo el error acumulado. La próxima versión de NTP proporcionará nuevas características con respecto a la configuración automática (por ejemplo, el modo manycast), la fiabilidad, la reducción del tráfico de Internet y la autenticación (usando criptografía de clave pública). Un modelo kernel nuevo reloj puede mantener el tiempo con una precisión de hasta un nanosegundo. 3b) Ejemplo de comunicación entre nodos Hasta ahora hemos hablado de los servidores, toca el turno a los clientes, los equipos que deben sincronizarse actúan como clientes lanzando peticiones de sincronismo (NTP request) a otro u otros dispositivos que actúan como servidor y que entregan la fecha y hora exacta (NTP reply). El intercambio de mensajes, así como un resumen del cálculo del offset o retardo entre envío de petición y recepción de respuesta es como sigue: T1=Origin Timestamp (on client) T2=Receive Timestamp (on server) T3=TransmitTimestamp (on server) T4=DestinationTimestamp = ReceiveTimestamp (on client) offset = [ (T2-T1) + (T3-T4) ] / 2 Como se ve, en los paquetes NTP incluimos timestamps que utilizamos para calcular el offset o variación respecto a la medición anterior.

En el cálculo del offset asumimos un retardo en la red simétrico al dividir el RTD (Round Trip Delay) por 2. Este offset puede ser especialmente relevante cuando el servidor se encuentra en Internet o usamos un medio de transmisión de baja velocidad. Todo esto puede verse mejor en la siguiente figura.

Sistemas Distribuidos (Aula2) PEC2 SD 2021-22/1

4. CAP twelve Years Later a) Teorema CAP (Conjetura de Brewer) y evolución En un SSDD es imposible garantizar el uso continuado de las redes, es decir, que en ocasiones fallarán, aunque sea temporalmente, es por ello que estos sistemas se tienen que diseñar para soportar estas fallas. Es por ello que aparece CAP. Este teorema dice que todo sistema de datos compartidos en red puede tener solo dos de las tres propiedades deseables. No obstante, al manejar explícitamente las particiones (falla de la red), los diseñadores pueden optimizar la consistencia y la disponibilidad, logrando así algunas compensaciones de las tres. La formulación "2 de 3" siempre fue engañosa porque tendía a simplificar demasiado las tensiones entre las propiedades. Aunque los diseñadores aún deben elegir entre la coherencia y la disponibilidad cuando hay particiones, existe una increíble variedad de flexibilidad para manejar las particiones y recuperarse de ellas. La forma más fácil de entender CAP es pensar en dos nodos en lados opuestos de una partición. Permitir que al menos un nodo actualice el estado hará que los nodos se vuelvan inconsistentes, perdiendo así C. De igual manera, si la opción es preservar la consistencia, un lado de la partición debe actuar como si no estuviera disponible, perdiendo así A. Solo cuando los nodos se comunican normalmente y sin problemas es posible preservar tanto la consistencia como la disponibilidad, perdiendo así P. Las tres propiedades posibles son: • Consistencia (C de consistency) equivalente a tener una única copia actualizada de los datos • Disponibilidad (A de availability) de esos datos (para actualizaciones) • Tolerancia al particionado (P de partition tolerance).

Veamos un gráfico:

Sistemas Distribuidos (Aula2) PEC2 SD 2021-22/1

Un error común, es pensar que en CAP tenemos de renunciar a una de las tres garantías en todo momento, pero eso no es así, la elección es solamente entre la consistencia y la disponibilidad y exclusivamente cuando hay una falla de red que la parte. Evidentemente en ausencia de falla de red las propiedades se satisfacen plenamente. Generalmente, las bases de datos tradicionales eligen la consistencia frente a la disponibilidad, y las bases de datos NoSQL eligen la disponibilidad sobre la consistencia. Todavía falta hablar de dos cosas más de CAP, la CAP-Latency y la Managíng partitions, ampliamente comentas en el artículo. Relación CAP-Latency: La definición anterior de CAP es la clásica, ignorando la latencia. Pero es evidente, de que la latencia y las particiones de red tienen mucha relación en las transacciones. Como ya sabemos, si hay una falla hay que decidir, o bien se cancela disminuyendo la disponibilidad o bien se procede corriendo el riesgo de inconsistencias. Gestión de particiones: Como es lógico, se pretende con ella mitigar los efectos de una partición de red que tienen en cuanto a la coherencia y la disponibilidad. La gestión incluye la detección y la recuperación, además de otras cuestiones que se podrían mermar precisamente como consecuencia de realizar las acciones para intentar recuperar la falla. Esto se realiza en tres pasos: Detección de la partición de red. Entrar en modo de partición explícito (que puede limitar otras operaciones). Iniciar la recuperación cuando sea posible.

Sistemas Distribuidos (Aula2) PEC2 SD 2021-22/1

NOTA FINAL: Algunos autores critican CAP. Alternativas son las siguientes:

En cuanto a la evolución el teorema CAP apareció por primera vez en el otoño de 1998 (siendo por entonces una conjetura). Fue publicado en 1999 y en el discurso de apertura del Simposio de 2000 sobre principios de computación distribuida, donde se llevó a prueba. No obstante, es el 2002 cuando debido se demostró en el MIT formalmente y se co...