PDF de programación - Sincronización, tolerancia a fallos y replicación

Sincronización,
tolerancia a fallos
y replicación

Leandro Navarro Moldes
Joan Manuel Marquès i Puig

P07/M2106/02840

© FUOC • P07/M2106/02840

Índice

Sincronización, tolerancia a fallos y replicación

Introducción .............................................................................................. 5

Objetivos ..................................................................................................... 7

1. La observación de un sistema distribuido .................................... 9
1.1. Observación y relatividad ................................................................. 9

2. Tiempos y relojes ................................................................................. 11
2.1. La medida del tiempo ....................................................................... 11
2.2. ¿Cómo ajustar el reloj? ..................................................................... 12
2.3. Relojes lógicos ................................................................................... 15
2.4. Relojes vectoriales ............................................................................. 17

3. Exclusión mutua ................................................................................. 19
3.1. Algoritmo centralizado ..................................................................... 19
3.2. Algoritmo descentralizado ................................................................ 19
3.3. Algoritmo basado en un anillo ......................................................... 20
3.4. Algoritmo distribuido ....................................................................... 21
3.5. Comparación de algoritmos ............................................................. 22

4. Algoritmos de elección ...................................................................... 24
4.1. El algoritmo de Bully ......................................................................... 24
4.2. Algoritmo anillo ............................................................................... 24
4.3. Elección en entornos sin hilo ........................................................... 25

5. Tolerancia a fallos ............................................................................... 27
5.1. Comunicación fiable en grupo ......................................................... 30
5.2. Entrega de mensajes ......................................................................... 32
5.3. Transacciones en presencia de fallos ................................................ 34

6. Consenso ................................................................................................ 36
6.1. Algoritmo de Paxos ........................................................................... 37

7. Conceptos básicos de replicación .................................................... 40
7.1. Single frente a multi-masters .............................................................. 40
7.2. Sistemas síncronos frente a sistemas asíncronos .............................. 41
7.2.1. Síncronos ................................................................................ 41
7.2.2. Asíncronos............................................................................... 42
7.3. Modelos de replicación síncronos .................................................... 42
7.3.1. Replicación pasiva................................................................... 42
7.3.2. Replicación activa .................................................................. 43
7.3.3. Basados en quórums ............................................................... 44

© FUOC • P07/M2106/02840

Sincronización, tolerancia a fallos y replicación

7.4. Algoritmos para replicación síncrona .............................................. 45
7.4.1. Reserva en dos fases ................................................................ 45
7.4.2. Confirmación distribuida........................................................ 45
7.4.3. Confirmación en dos fases ..................................................... 46
7.4.4. Confirmación en tres fases ..................................................... 48
7.5. Replicación optimista ........................................................................ 50

7.5.1. Pasos seguidos por un sistema optimista para llegar

a un estado consistente .......................................................... 50
7.5.2. Algunos ejemplos de sistemas optimistas .............................. 52

Resumen ...................................................................................................... 54

Actividades ................................................................................................. 57

Ejercicios de autoevaluación ................................................................. 57

Solucionario ............................................................................................... 58

Glosario ....................................................................................................... 59

Bibliografía ................................................................................................ 60

© FUOC • P07/M2106/02840

Introducción

5

Sincronización, tolerancia a fallos y replicación

En este módulo didáctico se describen los problemas que presenta y las ventajas
que ofrece un sistema informático distribuido formado por procesos y/o máqui-
nas que trabajan de manera independiente, y que tan sólo se comunican me-
diante el intercambio de mensajes por una red que puede retardar, desordenar,
duplicar o perder los mensajes.

Un sistema distribuido está formado por multitud de componentes que interac-
cionan entre sí. El objetivo del software intermediario (middleware) es tratar con la
red y presentar un modelo abstracto de programación a las aplicaciones sencillo
y completo, ocultando los inconvenientes y ofreciendo servicios para aprovechar
las ventajas. Aunque su complejidad es mayor que la suma de la complejidad de
cada componente, es deseable que el sistema no falle cuando falla cualquier com-
ponente (fragilidad), sino que funcione mientras algún componente funcione
(robustez o tolerancia a fallos).

Un sistema distribuido formado por varias máquinas puede funcionar de ma-
nera coordinada como si tuviera una capacidad de proceso suma de la capaci-
dad de cada componente.

El coste de un sistema de capacidad N veces superior a la capacidad de una sola
máquina de capacidad media puede costar N veces el coste de la máquina me-
dia, mientras que una sola máquina de capacidad N puede ser imposible de
construir o puede costar demasiado (CN).

En realidad, el razonamiento anterior puede aplicarse tanto a la capacidad de
procesar peticiones como a la capacidad de tolerar fallos: con sistemas distri-
buidos diseñados adecuadamente, se pueden construir sistemas más rápidos y
que funcionan durante más tiempo que cada uno de sus componentes.

El primer problema que existe en un sistema distribuido es que no nos es po-
sible hacer una foto “instantánea” o una película “global” de todo el sistema
para conocer su estado o sacar conclusiones de cómo ha ocurrido algo. El ob-
servador es también un proceso y recibe mensajes como cualquier otro com-
ponente de un sistema distribuido. Se verá que ocurren fenómenos similares
a los que describe la teoría de la relatividad.

El segundo problema es que el tiempo se mide localmente en cada lugar, no
está sincronizado globalmente y puede derivar (acelerarse o retrasarse respecto
a otros): no hay un reloj global. Se podrían recibir mensajes con marcas de
tiempo que parecen venir del futuro o secuencias de mensajes que parecen te-
ner un orden extraño a la vista de las marcas de tiempo que traen de su origen.

© FUOC • P07/M2106/02840

6

Sincronización, tolerancia a fallos y replicación

Hay protocolos para sincronizar mutuamente los relojes de cada computador
de un sistema distribuido mediante el intercambio de mensajes y garantizar
que con “relojes lógicos” se puede certificar que los mensajes se entregan a las
aplicaciones respetando las relaciones de causalidad (los mensajes llegan en el
orden en el que han ocurrido si uno ha podido influir en el otro).

El tercer problema está en cómo caracterizar y tratar un sistema en el que al-
gún componente pueda fallar o algún mensaje pueda perderse, o en el que la
demanda de un servicio pueda requerir el trabajo de varios componentes de
manera coordinada. Se presentan las formas en las que un sistema puede com-
portarse en presencia de fallos.

El cuarto problema es cómo garantizar que la compartimentación de recursos
se realice de manera coordinada. Se presentarán unos cuantos algoritmos que
permiten gestionar este acceso.

Otro aspecto que trataremos son los algoritmos de elección, que son muy im-
portantes en sistemas distribuidos. Muchos algoritmos necesitan que un pro-
ceso actúe como coordinador, iniciador o desarrolle un papel especial. En
estos casos da igual quién lo haga, pero es necesario que alguien lo haga.

El quinto problema consiste en pensar un modelo de programación que per-
mita diseñar aplicaciones en las que diferentes componentes cooperan para
proveer un servicio más rápidamente, con una disponibilidad mayor. Éste es
el modelo de comunicación en grupo.

En el módulo también se presentan los conceptos básicos relacionados con la
replicación en sistemas distribuidos. La replicación permite aumentar la dis-
ponibilidad y el rendimiento de los sistemas distribuidos. También contribuye
a mejorar la escalabilidad. Esta replicación puede ser síncrona –las actualizaci-
ones se aplican a todas las copias del objeto como parte de la operación de ac-
tualización– o asíncrona –como parte de la operación de actualización no hace
falta que se actualicen todas las copias del objeto. Posteriormente, se hace lle-
gar la actualización al resto de réplicas.

© FUOC • P07/M2106/02840

7

Sincronización, tolerancia a fallos y replicac