PDF de programación - Tolerancia a Fallas y Recuperación - Sistemas de Operación II

Sistemas de Operación II

Tolerancia a Fallas y Recuperación

Prof. Carlos Figueira

Basado en material de
Yudith Cardinale (USB)

Andrew Tanembaum y Marteen van Steen

Contenido

● Conceptos Básicos de Tolerancia a Fallas
● Redundancia

● Réplicas

● Recuperación de transacciones

● Listas de Intención

● Mecanismos de recuperación

● Uso de bitácoras
● Versiones Sombras

● Acuerdos en sistemas que fallan

Carlos Figueira/USB

2

Tolerancia a Fallas

● Es la capacidad de que un sistema siga
operando en presencia de fallas de uno o más
componentes

● En un Sistema Distribuido, pueden ocurrir fallas

parciales: las fallas totales son muy raras

● Falla de un componente puede afectar a otros
● Objetivo:

recuperarse automáticamente de

fallas parciales sin afectar rendimiento global

Carlos Figueira/USB

3

Conceptos básicos

● Disponibilidad: propiedad del sistema de estar listo para

ser usado en cualquier momento

● Confiabilidad: propiedad del sistema de ejecutar

servicios de manera continua, sin fallas

● Seguridad: si sistema falla temporalmente, nada

catastrófico sucederá

● Facilidad de Mantenimiento (maintainability): qué tan fácil

se repara sistema cuando falla

● Notas:

● Alta disponibilidad no implica alta confiabilidad
● ¡La recuperación automática no es tan fácil!

Carlos Figueira/USB

4

Conceptos básicos

● Falla del Sistema <= Error <= Falla externa

1.Sistema falla cuando no cumple con objetivos, no

satisface a sus usuarios

2.Un error es un estado del sistema que produce una

falla

3.La causa de un error es llamada “falla externa”

● Determinar la falla externa es importante, pero

no siempre ayuda.

● Cambiar las condiciones del momento para

prevenir un error no funciona

Carlos Figueira/USB

5

Conceptos básicos

● Sistemas Tolerantes a Fallas no las previenen,

sino que las controlan (anulan o mitigan sus
efectos)

● Los Sistemas Tolerantes a Fallas proveen los

servicios en presencia de fallas
● Clasificación de fallas externas:

● Transitorias: ocurren una vez y desaparecen
● Intermitentes: ocurren, desaparecen, ocurren

nuevamente, y así sucesivamente

● Permanentes: la falla ocurre y no desaparece

Carlos Figueira/USB

6

Modelos de fallas del sistema

● Fallas por muerte (crash): el servidor se para,
pero trabaja correctamente hasta ese momento

● Fallas por omisión: servidor falla (deja de

responder) a solicitudes entrantes
● De recepción: falla recibiendo mensajes
● De envío: falla enviando mensajes

● Fallas de temporización: la respuesta del
servidor cae fuera del intervalo de tiempo
especificado

Carlos Figueira/USB

7

Modelos de fallas del sistema

● Fallas de respuesta: la respuesta del servidor

es incorrecta
● De valor: el valor de la respuesta es incorrecto
● De transición de estados: el servidor se desvía del

flujo correcto de control

● Fallas Arbitrarias (bizantinas): un servidor
puede producir respuestas arbitrarias en
momentos arbitrarios

Carlos Figueira/USB

8

Modelos de fallas del sistema

● Fallo-detención (fail-stop): caída detectable, se

obtiene notificación

● Silenciosas: falla se produce sin anuncios. Puede

confundirse con servidores lentos

● Seguras (fail-safe): servidor produce salidas que

se reconocen como fallas

● Bizantinas: servidor produce salida errónea que

se confunde con salida correcta.
● Opciones: tratar de precisar mediante sondeo, o parar

y volver a arrancar el sistema
Carlos Figueira/USB

9

Redundancia

Carlos Figueira/USB

10

Enmascaramiento de fallas

● Redundancia permite ocultar fallas. Hay tres

tipos
● Información: se agrega información adicional para
detectar/corregir fallas (código de Hamming, bits de
paridad, etc.)

● Tiempo: una acción se puede repetir si es
operaciones

(transacciones

necesario
idempotentes)

u

● Física: se agregan equipos o procesos extras para

sustituirlos por el componente que falle

Carlos Figueira/USB

11

Redundancia Física

● La más usada en biología, aviones, deportes y

circuitos electrónicos

● El modelo TMR (Redundancia Modular Triple) de

los circuitos electrónicos se puede aplicar a SD

Carlos Figueira/USB

12

Redundancia

● Pueden usarse grupos de procesos y

comunicación en grupo

● ¿Cuánta replicación es necesaria si se usan

grupos de procesos?
● Un sistema es k-tolerante a fallas si continúa

funcionando aunque fallen k componentes
● La redundancia con grupo de procesos

requiere multicast atómico

Carlos Figueira/USB

13

Enfoques de replicación por grupos

1.Protocolo basado en respaldo primario

(replicación pasiva).
● Se implementa con grupos jerárquicos

2.Protocolo de escritura replicada:

● Se implementa con grupos planos (como TMR)

Carlos Figueira/USB

14

Replicación pasiva

C

C

Prin

Resp

Resp

Resp

El cliente interactúa con Principal/Primario, que
se encarga de actualizar servidores de respaldo

Carlos Figueira/USB

15

Replicación pasiva

1.Petición: va del cliente al principal (lleva id de

petición)

2.Coordinación: principal acepta peticiones en

forma atómica y en orden

3.Ejecución: principal ejecuta petición y guarda

respuesta

4.Acuerdo: para actualizar, se envían cambios a

todos los respaldos (atómicamente)

5.Respuesta: principal responde al cliente

Carlos Figueira/USB

16

Replicación pasiva

● Requiere algoritmos de elección de coordinador

cuando falla principal

● Es necesario identificar requerimientos de manera

que nuevo principal detecte retransmisiones

● Desventaja: sobrecarga relativamente grande para

principal
● Para descargar a principal, lecturas pueden ser

satisfechas por respaldos

● ¿Puede soportar fallas silenciosas y bizantinas?

Carlos Figueira/USB

17

Replicación activa

C

Proxy

Serv

Serv

Serv

Proxy

C

La interacción se hace directamente con
todos los servidores simultáneamente

Carlos Figueira/USB

18

Replicación activa (escrituras

replicadas)

● Petición: cliente/proxy envía requerimiento a

grupo (multicast)

● Coordinación: sistema de com. en grupo

reparte petición (multicast atómico y ordenado)

● Ejecución: todos ejecutan petición
● Acuerdo: no es necesario, debido a

comunicación atómica y ordenada

● Respuesta: todos envían respuesta a

cliente/proxy

Carlos Figueira/USB

19

Replicación activa (escrituras

replicadas)

● Cliente/proxy puede obtener la primera

respuesta y obviar las demás, o puede decidir
en base a respuesta más común de las que
recibe

● Provee consistencia secuencial
● ¿Puede soportar fallas silenciosas y

bizantinas?

Carlos Figueira/USB

20

Recuperación de transacciones

Carlos Figueira/USB

21

Recuperación de transacciones

● Consiste en asegurar la atomicidad de las

transacciones en presencia de fallas del
servidor

● Implica permanencia (durabilidad): los datos

son salvados en almacenamiento permanente
y no pueden revertirse

● Interviene Administrador de Recuperación

Carlos Figueira/USB

22

Administrador de recuperación

● Salva datos en archivo de recuperación

(permanente) de transacciones comprometidas
● Restaura datos del servidor después de caída
● Reorganiza archivo de recuperación para

mejorar desempeño en recuperación

● Recobra espacio de almacenamiento (archivo

de recuperación)

Carlos Figueira/USB

23

Listas de intención

● Usadas para que cada servidor mantenga

registro de datos accedidos por transacciones
● Durante progreso de transacción, operaciones

se aplican a conjunto privado de versiones
tentativas

● Cada servidor registra lista de intención (write-

ahead log) de cada transacción activa
● Contiene lista de nombres y valores de datos

modificados por la transacción

Carlos Figueira/USB

24

Listas de intención

● Cuando una transacción se compromete

(commit), el servidor usa lista de intención para
identificar datos afectados
● versión comprometida previamente de cada dato es

reemplazada por versión tentativa de la
transacción;

● el nuevo valor es escrito en archivo de

recuperación del servidor

● Cuando aborta transacción, servidor usa lista

de intención para borrar versiones tentativas

Carlos Figueira/USB

25

Contenido de Lista de Intención

Tipo de entrada

Descripción

Dato

Valor

Estado de transacción

Lista de intención

Tid, estado (lista, espera,
comprometida, abortar),
otros valores

Tid y secuencia de
intenciones que consisten
de: <id dato>, <posición de
valor del dato en archivo de
recuperación>

Carlos Figueira/USB

26

Mecanismos de Recuperación

Carlos Figueira/USB

27

Mecanismos de recuperación:

bitácoras (logging)

● Archivo de recuperación representa una bitácora o

registro histórico, con todas las transacciones
realizadas por el servidor

● Contiene valores de datos, registros de estados de

transacciones y listas de intención

● Orden de las entrada en la bitácora refleja orden en

el cual transacciones han sido preparadas,
comprometidas o abortadas en servidor

● Archivo de recuperación contendrá foto de valores de

datos en servidor, seguida por historia de
transacciones posteriores a la foto (punto de control)

Carlos Figueira/USB

28

Ejemplo del mecanismo de

bitácoras

Transacción T

Transacción U

retirar(A,4)
depositar(B,4)
balance=A.leer()
A.escribir(balance-4)

balance=B.leer
B.escribir(balance+4)

100
96

200
204

retirar(C,3)
depositar(B,3)

balance=C.leer()
C.escribir(balance-3)

balance=B.leer
B.escribir(balance+3)

300
297

204
207

Carlos Figueira/USB

29

Ejemplo del mecanismo de

bitácoras

Antes de T y U T y U comenzaron
P0

P1

Dato

A
100

Dato

B
200

Dato

C
300

Dato

A
96

Dato

B
204

P2

P3
Trans T
preparada
<A,P1>
<B,P2>

P0

Punto de control

Apuntadores a la posición del
estado previo de la transacción

Pi: posición i en bitácora

P4

P5

P6

Trans T
completa

P3

Dato

C
297

Dato

B
207

P7
Trans U
preparada
<C,P5>
<B,P6>

P4

Fin de registro
de bitácora

Carlos Figueira/USB

30

Proceso de recuperación usando

registro de bitác