• Author / Uploaded
• Guillermo Muñoz

Citation preview

Página

1

Contenido Introducción .............................................................................................................................................. 3 Administración de replicas ................................................................................................................... 4 Replicación mediante primario y respaldos ................................................................................. 6 Comunicación en grupos ................................................................................................................... 7 Compromiso distribuido .................................................................................................................... 9 Transacciones....................................................................................................................................... 9 Sincronización y coordinación distribuida ..................................................................................... 11 Mecanismos de sincronización entre procesos ........................................................................ 11 Mecanismos de sincronización distribuida ............................................................................ 12

Página

2

Conclusión ............................................................................................................................................... 13

Introducción Un sistema distribuido es una colección de nodos autónomos de computación que se pueden comunicar unos con otros y que colaboran en un objetivo o tarea común. Cuando un nodo falla o cuando el subsistema de comunicaciones que permite que los nodos se comuniquen falla, los nodos se han de adaptar a las nuevas condiciones, para que puedan seguir cooperando. En los sistemas tolerantes a fallo, los fallos que se pueden tolerar son aquéllos que está previsto que pueden ocurrir. El primer paso necesario para que un sistema pueda recuperarse de un fallo, es detectarlo. El siguiente paso es llevar al sistema a un estado consistente, para ello, es necesario que las acciones realizadas antes del fallo mantengan la consistencia. La clave para tolerar fallos es la replicación, es decir, que

Página

3

varios elementos del sistema puedan dar el mismo servicio.

Administración de replicas La replicación activa (conocida también como replicación mediante máquina de estados) es un método general para construir un sistema tolerante a fallos mediante la replicación de sus elementos y la coordinación de las comunicaciones entre ellos. Una máquina de estados está compuesta por un conjunto de variables (estado) y un conjunto de operaciones que modifican o consultan el valor de esas variables. Cada operación se realiza mediante un programa determinista, y su funcionamiento es atómico respecto al de otras. Las operaciones también producir resultados de salida. Cuando un cliente quiere ejecutar un servicio de la máquina de estados, le hace una petición, indicando qué operación debe ejecutar. El resultado puede ser la activación de un actuador o la respuesta a algún cliente que la estaba esperando. Es necesario también que las peticiones que recibe una máquina de estados sean atendidas de una en una, en un orden que ha de ser consistente con la causalidad potencial entre ellas. La propiedad fundamental que caracteriza una máquina de estados es que los resultados de salida que produce están completamente determinados por la secuencia de peticiones que recibe, con independencia del momento en que las recibe y de cualquier otra actividad del sistema. Una gran ventaja de este enfoque consiste en que casi cualquier sistema puede descomponerse en clientes y máquinas de estados, por lo que puede ser utilizado en gran parte de los casos. Para conseguir una versión tolerante a t fallos de una máquina de estados podemos replicarla, colocando cada réplica en un nodo diferente de la red. Si todas las réplicas comienzan en el mismo estado, y reciben la misma secuencia de peticiones, todas harán lo mismo, y producirán los mismos resultados. El número de réplicas que son necesarias

Página

hacen falta como mínimo 2t + 1, y para obtener resultados correctos basta con tomar los

4

para tolerar t fallos depende del modelo de fallo que se considere. Si son fallos bizantinos,

que producen la mayoría de las réplicas. Si se considera que sólo puede haber falloparada, basta con t + 1 réplicas. En otras palabras, la clave para conseguir máquinas de estados replicadas tolerantes a fallos está en garantizar la coordinación entre las réplicas (todas reciben y procesan la misma secuencia de peticiones). Este requisito puede a su vez descomponerse en dos: concenso (todas las réplicas correctas reciben el mismo conjunto de peticiones) y orden (todas las réplicas correctas procesan las peticiones que reciben en el mismo orden). Los algoritmos de comunicación que satisfacen el requisito de acuerdo (concenso) deben conseguir que un emisor pueda enviar un mensaje a los receptores cumpliendo dos condiciones: todos los receptores correctos están de acuerdo en el mensaje que reciben y, si el emisor es correcto, lo que cada receptor correcto recibe es lo que envió el emisor. Los que garantizan estas dos condiciones se llaman protocolos de radiado fiables, protocolos de acuerdo bizantino o, simplemente, protocolos de concenso. El requisito de orden suele satisfacerse añadiendo información de orden a los mensajes. Esta información puede ser añadida por uno de los receptores (que luego la distribuye a los demás), o por los emisores, mediante el uso de algún tipo de reloj lógico (generalmente, combinado con cierto acuerdo entre los receptores).

Consideremos un objeto x, y la invocación de la operación [x op(arg)

] por parte del cliente

La petición se envía a todas las réplicas de x.

1. Cada réplica procesa la petición, actualiza su estado, y envía la respuesta [x ok(res)

] al cliente

.

las respuestas. Si las réplicas no se comportan de manera maliciosa (es decir, no

5

se producen fallos bizantinos), entonces el proceso cliente espera sólo por la

Página

2. El cliente espera hasta que recibe la primera respuesta, o hasta que recibe todas

primera respuesta. En caso contrario, será necesario disponer al menos de 2f + 1 réplicas para tolerar hasta f posibles fallos. En esta situación, el cliente espera a recibir sólo f + 1 respuestas idénticas.

Replicación mediante primario y respaldos En los sistemas que usan este enfoque para lograr tolerancia a fallos, los emisores envían mensajes sólo al proceso marcado como primario. Si éste falla, uno de los respaldos toma su lugar. Los clientes deben darse cuenta de estas caídas y actualizar el primario para poder enviar sus mensajes al proceso adecuado. Más formalmente, para que un protocolo pueda ser considerado del tipo primariorespaldos, deben cumplir las siguientes condiciones: Existe un predicado que se puede aplicar al estado de cada servidor. En cualquier momento, como mucho un servidor satisface ese predicado. El que lo satisface es denominado

primario.

Todo cliente mantiene información sobre la identidad de un servidor, al que realiza sus peticiones. Este servidor, si es el primario, encola las peticiones y las atiende de una en una.

casos, no responde durante un número limitado de períodos finitos de tiempo.

Página

El servicio replicado aparece, en su conjunto, como un servidor que, en el peor de los

6

Si una petición llega a un servidor que no es el primario, se descarta.

Las tres primeras propiedades definen cómo debe ser el protocolo entre los clientes y el servicio y la cuarta indica en qué condiciones el servicio debe satisfacer las peticiones.

Comunicación en grupos La comunicación en grupo asume un papel importantísimo a la hora de crear sistemas distribuidos tolerantes a fallos. Ello es así puesto que, para poder ofrecer tolerancia a fallos a una aplicación determinada, no es suficiente con replicar dicha aplicación, sino que además es necesario disponer de un sistema que facilite la comunicación entre tales réplicas. En un modelo de comunicación con grupos dinámicos, los procesos podrán unirse o abandonar el grupo cuando lo deseen, haciendo que la membresía pueda cambiar a lo largo del tiempo. Al conjunto de procesos que forman parte de un grupo se le conoce con el nombre de vista. Existirá por tanto un servicio de membresía que se ocupará de mantener actualizada la vista en cada uno de los miembros del grupo. Las herramientas software para comunicación con grupos utilizan una arquitectura conocida con el nombre de 3T (three-tier). En este modelo los clientes (client-tier) interactúan con una capa intermedia (middle-tier) que se encarga de enviar las peticiones

Página

7

a los servidores replicados (end-tier), manteniendo en todo momento la consistencia.

Para lograrlo, la capa intermedia anida dos componentes básicos, el secuenciador y el manejador de replicación activa, que se encargan de garantizar que todas las réplicas reciben y ejecutan las peticiones de los clientes en el mismo orden en que fueron enviadas. Las herramientas para comunicación con grupos proporcionan un conjunto de servicios y primitivas que ayudan a los desarrolladores a construir sistemas de alta disponibilidad utilizando replicación software. En un sistema de este tipo se distinguen dos bloques fundamentales, (i) la API y (ii) el núcleo del sistema.

El primer bloque lo constituye un conjunto de interfaces que permiten a la aplicación utilizar los servicios ofrecidos por la herramienta para comunicación de grupo; el segundo bloque implementa tales servicios. Ambos bloques pueden ser implementados usando diferentes lenguajes de programación. En caso de considerar herramientas de comunicación con grupos escritas en Java, es importante tener en cuenta cómo puede afectar al rendimiento la localización de la Máquina Virtual (JVM). Si sólo la API está escrita en Java, entonces la JVM estará ubicada bajo este bloque, permitiendo al núcleo intercambiar mensajes a través de la red utilizando llamadas nativas al sistema. Por el contrario, si el núcleo también está escrito en Java, la comunicación con la red habrá de realizarse a través de la JVM, lo cual puede

es su capacidad para adaptarse a las necesidades del usuario, pudiendo tener sistemas

Página

Otro factor importante a la hora de elegir una herramienta de comunicación con grupos

8

afectar negativamente al rendimiento.

monolíticos y sistemas modulares. En un sistema monolítico no se permite al usuario adaptar el sistema, sin embargo, en un sistema modular el usuario es libre para adaptar el sistema a sus necesidades configurando la pila de protocolos de la forma que considere más oportuna.

Compromiso distribuido Transacciones para agrupar un conjunto de peticiones efectuadas sobre un conjunto de elementos. – O todas tienen éxito: commit - Si alguna falla: rollback de todas las operaciones. Cada operación debe estar preparada a que se le ordene deshacer los cambios: No es posible en general si algún elemento no colabora (por ejemplo: una impresora) Protocolos de compromiso: Un proceso coordina la transacción y los demás participan con sus votos: Compromiso en dos fases: el coordinador envía PREPARAR y los demás responden OK o NOK. Si alguno respondió NOK, el coordinador envía ABORT. Si todos respondieron OK, el coordinador envía COMMIT. – Problema si el coordinador y un participante fallan antes de que el coordinador envíe COMMIT/ABORT. Se bloquea a los demás participantes, que no saben qué dijo el elemento que falló. Solución: compromiso en 3 fases: Preparar, precommit y commit.

Transacciones Los sistemas distribuidos son potencialmente muy fiables debido a la posibilidad de proveer redundancia y autonomía de recursos en diferentes nodos, esto permite detectar y localizar fallas, sin embargo, comúnmente tenemos varios aspectos que representan

Página

transacciones:

9

problemas para la integridad de los recursos y que a su vez motivan el uso de

Las transacciones son un mecanismo que ayuda a simplificar la construcción de sistemas confiables a través de procesos que proveen soporte uniforme para invocar y sincronizar operaciones como: Operaciones de compartición de datos. Aseguramiento de la sociabilidad de las transacciones con otras. Atomicidad en su comportamiento. Recuperación de fallas provocadas en red y nodos. El término transacción describe una secuencia de operaciones con uno o más recursos (por ejemplo, una base de datos) que transforman su estado actual en un nuevo estado de consistencia. El manejo de transacciones fue desarrollado en el campo de las operaciones financieras donde se tenía 3 reglas básicas: 1.Consistencia: Obedecer ciertas reglas. 2 Atomicidad: Debe ocurrir completo o abortar. 3 Durabilidad: Una vez iniciada una transacción y terminada completamente no puede ser abortada. La teoría de las transacciones consiste en una serie de modificaciones(transacciones) a un determinado recurso del sistema (por ejemplo, una base de datos) y en donde se define un punto de inicio (Begin Tran) y un punto determinación que define un bloque entre el conjunto de operaciones que son realizadas. Dentro de este proceso en bloque los demás usuarios no pueden modificar nada hasta que no se presente un estado

Página

10

estable de los datos, esto ocasiona inconsistencia temporal y conflictos.

Sincronización y coordinación distribuida Estos son los mecanismos que se basan en la existencia de una unidad de sincronización centralizada, la cual debe tener un nombre Técnico conocido para todos los procesos que requieren ser sincronizados. Se designa un nodo como nodo de control y su tarea es administrar el acceso a los recursos compartidos. Este nodo también almacena información relevante sobre todos los procesos que realizan alguna petición.

Mecanismos de sincronización entre procesos Reloj físico. La idea es proveer de un único bloque de tiempo para el sistema. Los procesos pueden usar la marca física del tiempo (timestamp) provista o leída de un reloj central para expresar algún orden en el conjunto de acciones que inician. La principal ventaja de este mecanismo es la simplicidad, aunque existen varios inconvenientes: el correcto registro del tiempo depende en la posibilidad de recibir correctamente y en todo momento, el tiempo actual desplegado por el reloj físico; los errores de transmisión se convierten en un impedimento para el orden deseado, el grado de exactitud depende de las constantes puestas en el sistema. Proceso central. Este mecanismo se basa en un proceso que recibe todas las peticiones de los procesos que serán sincronizados. La sincronización se logra por la exclusión mutua ejecutada por este proceso central. La ventaja principal de este mecanismo es que se asegura totalmente de la exclusión mutua. Como desventajas tiene: Requiere tres mensajes por sección critica. Si el proceso tiene que tomar su lugar y ejecutar los siguientes pasos: 1) detección de una falla, i el coordinador falla, un nuevo 2) elección de un único y nuevo coordinador y

procesos controlar directamente el orden de los eventos, en lugar de usar la exclusión mutua. En otras palabras, es un entero que no se decrementar y cuyo valor inicial es

Página

Contador de eventos. Un contador de eventos es un objeto abstracto que permite a los

11

3) reconstrucción de la cola de peticiones.

cero. Existen tres primitivas que definen a un contador de eventos: avance(E). Incrementa el valor del entero E por 1. Se utiliza esta primitiva para serializar la ocurrencia de un evento asociado directamente con un contador. read(E). Regresa el valor actual de E. await (E,v). Suspende la llamada al proceso hasta que el valor de E sea igual a v (no debe cambiar mientras que se suspende el proceso). Puede ser muy útil cuando se desea que un proceso no se ejecute hasta que ocurra algún evento. Mecanismos de sincronización distribuida El tomar decisiones en un ambiente distribuido implica que los problemas de sincronización son mucho más complicados, y el problema está en cómo extender un orden parcial a un ordenamiento total y arbitrario, usándolo en la resolución de problemas

Página

12

de sincronización.

Conclusión La administración de réplicas es de suma importancia debido a que de esta depende la fiabilidad de la información, el contar con información actualizada y a la mano siempre

Página

13

que se requiera.