1. No category

Universidad Católica Andrés Bello
Replicación
(parte 2)
Dictado por David Hernández
[email protected]
Agenda
● Tolerancia a Fallas
○ Requerimientos útiles para los S.D
○ Clasificación
● Modelo de Fallas
● Disfrazado de fallas por redundancia
○ Redundancia física
■ Técnicas
■ Replica activa vs. primaria
○ Redundancia modular triple
● Temas de Diseño
● Fallas bizantinas
Tolerancia a Fallas
“Una falla es un desperfecto, causado tal vez por un
error de diseño, un error de fabricación, un error de
programación, un daño físico, el deterioro con el
curso del tiempo, condiciones ambientales
adversas, entradas inesperadas, un error del
operador, roedores comiendo parte del sistema y
muchas otras causas” – Tanenbaum, 1996
Tolerancia a Fallas
Requerimientos útiles para los sistemas distribuidos
● Disponibilidad: se define como la propiedad de que un
sistema está listo para ser utilizado de inmediato.
● Confiabilidad: se refiere a la propiedad de que un
sistema sea capaz de funcionar de manera continua sin
fallar.
● Seguridad: situación en que no acontece nada
catastrófico cuando un sistema deja de funcionar
correctamente durante un tiempo.
● Mantenimiento: se refiere a cuan fácil puede ser
reparado un sistema que falló.
Ing. Francisco Gómez
[email protected]
Sistemas Distribuidos. Segunda Edición
Andrew S. Tanenbaum, Maarten Van Steen
Tolerancia a Fallas
Clasificación
● Fallas transitorias: ocurren una vez y luego
desaparecen.
● Fallas intermitentes: ocurre, luego desaparece por sí
sola, después reaparece, y así sucesivamente.
● Fallas permanentes: es una que continúa existiendo
hasta que el componente defectuoso es reemplazado.
Ing. Francisco Gómez
[email protected]
Sistemas Distribuidos. Segunda Edición
Andrew S. Tanenbaum, Maarten Van Steen
Modelo de Fallas
Ing. Francisco Gómez
[email protected]
Sistemas Distribuidos. Segunda Edición
Andrew S. Tanenbaum, Maarten Van Steen
Disfrazado de fallas por redundancia
Para que un sistema sea tolerante a fallas, lo mejor que
puede hacer es tratar de ocultar ante otros procesos la
ocurrencia de fallas.
● Redundancia de información: se agregan bits
●
●
adicionales para recuperar los bits mutilados.
Redundancia de tiempo: se realiza una acción y luego
si es necesario se vuelve a realizar. Esta redundancia
es útil con fallas transitorias e intermitentes.
Redundancia física: se agrega equipo o procesos
adicionales para que el sistema en su conjunto tolere la
pérdida o el mal funcionamiento de algunos
componentes.
Ing. Francisco Gómez
[email protected]
Sistemas Distribuidos. Segunda Edición
Andrew S. Tanenbaum, Maarten Van Steen
Disfrazado de fallas por redundancia
Redundancia física - Técnicas
● Réplica activa (maestro-maestro): en esta técnica
todas las replicas manejan la misma información. La
lectura de solicitudes no altera el estado de los
servidores, pero la escritura de solicitudes si lo hace.
En este esquema es necesario un tiempo global
(problema de transacción atómica).
● Réplica primaria (maestro-esclavo): en está técnica
un servidor es primario y realiza todo el trabajo,
mientras que el otro se mantiene idéntico y en caso de
fallas toma el control.
Prof. Rodolfo Campos
[email protected]
Disfrazado de fallas por redundancia
Redundancia física - Replica activa vs. primaria
● La replica primaria es más sencilla que la activa durante
la operación normal ya que todos los mensajes van a
un servidor y no a un grupo.
● La replica primaria no tiene problemas de ordenamiento
de los mensajes ya que todos van a la misma máquina.
● La replica primaria necesita menos máquinas que la
activa.
● La replica activa puede trabajar correctamente en
presencia de fallas bizantinas, mientras que la primaria
no.
● En la replica primaria es difícil conocer cuando el
servidor primario ha muerto.
Prof. Rodolfo Campos
[email protected]
Disfrazado de fallas por redundancia
Redundancia modular triple
Circuito "perfecto"
Redundancia modular triple
Ing. Francisco Gómez
[email protected]
Sistemas Distribuidos. Segunda Edición
Andrew S. Tanenbaum, Maarten Van Steen
Temas de Diseño
La forma clave de afrontar la tolerancia a un proceso
defectuoso es organizar varios procesos idénticos en
grupos.
La propiedad fundamental de un grupo es que cuando un
mensaje es enviado al grupo, todos los miembros de este
los reciben.
Comunicación en grupo simple
Ing. Francisco Gómez
[email protected]
Comunicación en grupo jerárquico simple
Sistemas Distribuidos. Segunda Edición
Andrew S. Tanenbaum, Maarten Van Steen
Acuerdo en sistemas defectuosos
Fallas bizantinas
En general, las cosas se complican cuando se demanda
que un grupo de procesos llegue a un acuerdo, lo cual se
requiere en muchos casos. Algunos ejemplos son:
● La elección de un coordinador
● La decisión de realizar o no una transacción.
● La división de tareas entre los trabajadores y la
sincronización.
Ing. Francisco Gómez
[email protected]
Sistemas Distribuidos. Segunda Edición
Andrew S. Tanenbaum, Maarten Van Steen
Acuerdo en sistemas defectuosos
Fallas bizantinas (cont.)
Algunos sistemas deben acordar decisiones comunes
contando con la posible existencia de errores ocasionados
por:
● La entrega de mensajes de manera no confiable
(Problema de los dos ejércitos – límite en el envío de
ACKs)
● La falla de procesadores, silentes o bizantinas
(Problema de los Generales Bizantinos)
● La naturaleza del sistema ¿síncrona o asíncrona?.
Fischer et al (1985) demostró que un sistema
distribuido con procesadores asíncronos y retrasos no
acotados en la transmisión, no puede llegar a un
acuerdo aunque sólo un procesador este fallando – no
se pueden distinguir los procesadores lentos de los
muertos.
Prof. Rodolfo Campos
[email protected]
Acuerdo en sistemas defectuosos
Fallas bizantinas (cont. 2)
Solución de Lamport al problema de los Generales
Bizantinos:
El acuerdo se puede lograr sólo si están presentes 2K+1
procesos que estén funcionando correctamente. Dicho de
otra manera más de dos tercios de los procesos están
funcionando correctamente.
Ing. Francisco Gómez
[email protected]
Sistemas Distribuidos. Segunda Edición
Andrew S. Tanenbaum, Maarten Van Steen
Acuerdo en sistemas defectuosos
Fallas bizantinas (cont. 3)
Pasos:
1. Cada proceso i no defectuoso envía Vi a todos los
demás procesos mediante unitransmisión confiables.
2. Los resultados de los anuncios del paso 1 se reúnen en
forma de vectores.
3. Cada proceso transfiere su vector (Completo) a todos los
demás procesos.
4. Cada proceso examina el elemento i-ésimo de cada uno
de los vectores recién recibidos.
Finalmente si ningún valor tiene mayoría, el elemento
correspondiente del vector resultado se marca mediante
UNKNOWN
Ing. Francisco Gómez
[email protected]
Sistemas Distribuidos. Segunda Edición
Andrew S. Tanenbaum, Maarten Van Steen
Acuerdo en sistemas defectuosos
Fallas bizantinas (cont. 4)
1 Obtuvo (1,2,x,4)
2 Obtuvo (1,2,y,4)
3 Obtuvo (1,2,3,4)
4 Obtuvo (1,2,z,4)
2
1
2
1
x
3
2
1
4
1
y
4
2
4
4
Luego...
1 Obtuvo
(1,2,y,4)
(a,b,c,d)
(1,2,z,4)
2 Obtuvo
(1,2,x,4)
(e,f,g,h)
(1,2,z,4)
4 Obtuvo
(1,2,x,4)
(1,2,y,4)
(i, j, k, l)
z
Sistemas Distribuidos. Segunda Edición
Andrew S. Tanenbaum, Maarten Van Steen
(modificado)