Replicación
Sistemas Distribuídos
Objetivos
Aumentar la disponibilidad
Mejorar los tiempos de respuesta
Incrementar la tolerancia a fallas
Candidatos a replicación
Datos (por ejemplo, una base de datos
críticos)
Servicios:
Comunicaciones
Servicio de nombres
Servicio de archivos
Recursos en general
Concepto
Replicación es el mantenimiento de copias
on-line de datos y otros recursos, a fin de
alcanzar mejor perfomance, alta
disponibilidad y tolerancia a fallas
Ejemplos de replicación en Internet:
El servicio DNS
El Servicio USENET (Internet News)
Mejoras en la perfomance
Múltiples clientes accediendo a un solo
servidor lo transforman en un cuello de
botella: por encima de un nro. máximo de
requerimientos por segundo, el tiempo
medio de respuesta cae significativamente
Múltiples servidores atendiendo a
subconjuntos de clientes permiten
mejorar el tiempo medio de respuesta
Mejoras en la disponibilidad
Datos replicados en dos servidores
independientes, conectados a la red por
vínculos independientes permiten
seleccionar al otro servidor ante la falla de
uno cualquiera de ellos o de su enlace
Mejoras en la disponibilidad
Supongamos n servidores replicados, cada
uno con una probabilidad p de falla
independiente. La disponibilidad de los
datos será:
d = 1 - (prob. todos los serv en falla) = 1 - pn
Tolerancia a Fallas
Tipos de falla cubiertos por la replicación:
Fallas bizantinas o arbitrarias (resultados
incorrectos)
Fallas de parada: un componente entra en
un estado de falla detectable
Tolerancia a Fallas
Una réplica cualquiera podrá seguir
prestando servicio ante la falla de otra
Un conjunto de réplicas puede producir
un dato correcto mediante una elección
por mayoría, frente a fallas aleatorias en
una cualquiera de las réplicas
Requerimientos
Transparencia de replicación:
Los clientes no deben tener percepción de la
existencia de múltiples copias físicas del
objeto referenciado  nombre único y
conjunto de resultados único
Consistencia:
Las mismas operaciones sobre los mismos
objetos hechas por distintos clientes deben
producir idénticos resultados
Operaciones de acceso a
objetos
read: lectura del estado de un objeto (no
lo modifica)
write: cambio del estado de un objeto (lo
modifica) también llamada update u
overwrite
Operaciones de lectura
Leer uno (primario)
lectura
Leer uno
Leer quorum
Operaciones de escritura
Escribir uno (primario)
Sobreescribir
Escribir todos
Escribir todos los disponibles
Escritura
Leer y modificar
Escribir un quorum
Escribir Gossip
Modelos de Replicación
Asíncrono:
Todos los requerimientos de un cliente son
atendidos por su servidor local (el mas
cercano en términos de red)
El ordenamiento de las operaciones puede
diferir entre réplicas.
Cuando un servidor procesa un update desde
un cliente local lo propaga al resto de los
servidores de réplica
Modelos de Replicación
Sincrónico total:
Todo requerimiento de update se procesa en
orden temporal
Sólo cuando todas las réplicas procesaron la
operación, el control retorna al cliente
Es un modelo de consistencia estricta, en el
cual los tiempos de respuesta son mayores al
asíncrono
Técnicas de diseño
Los esquemas reales utilizan un punto
intermedio entre el modelo asíncrono y el
sincrónico total:
Esquemas basados en quorum: requieren la
participación de un subconjunto de las
réplicas activas
Esquemas basados en causalidad: imponen
ordenamiento sólo a las operaciones que lo
requieren.
Modelo Arquitectural
Front Ends
cliente
FE
Servicio
replicado
AR
AR
cliente
FE
Requerimientos
y respuestas
AR
Administradores
de réplica
Componentes del modelo
Clientes: procesos usuarios del servicio
Front-Ends: responsable de la
comunicación con uno o mas AR’s,
abstraen al cliente de la implementación
del servicio
Administradores de réplica: procesos que
contienen las réplicas y efectúan
operaciones directamente sobre ellas
Implementación I: Gossip
mensajes
cliente
FE
AR
AR
cliente
FE
FE
cliente
AR
Cada FE se comunica con uno o mas AR’s para satisfacer el
requerimiento del cliente. Los AR intercambian mensajes
(gossip), propagando los cambios registrados
Implementación II: Réplica
primaria
Primario
cliente
FE
AR
AR
cliente
FE
En rojo: escrituras
En verde: lecturas
FE
cliente
AR
Secundarios
Cada FE se comunica con el AR designado primario cuando la
operación requerida es un update. El AR primario propaga los
cambios al resto de los AR’s.
Réplica primaria
Para las operaciones de lectura, los FE’s
pueden utilizar cualquier AR, dado que el
modelo garantiza que todos están
sincronizados.
En la eventualidad de falla del AR
primario, un algoritmo distribuido fuerza
una elección de otro AR para promoverlo
a primario
ordenamiento de
requerimientos
Asumimos que cada Administrador de
Réplica:
Procesa un requerimiento por vez (o, si es
multithreaded, suponemos equivalencia
serial)
Es una máquina de estados, es decir, los
datos administrados tienen valores en función
del valor inicial y de la secuencia de
operaciones aplicadas
Ordenamiento
Requerimientos totalmente ordenados:
Dados dos requerimientos {r1, r2}, se
asegura que:
r1 es procesado antes que r2 en todas los
AR, o
r2 es procesado antes que r1 en todas los AR
Ordenamiento causal
Establece una relación causal entre dos
eventos (requerimientos):
r1 sucedió antes que r2 si hubo un flujo de
información desde r1 hacia r2
Dada esta relación, r1 debe procesarse antes
que r2 en todos los AR
El ordenamiento total no necesariamente
es causal.
Ordenamiento Sincrónico
Permite establecer eventos de
sincronización, que imponen a todas las
réplicas respetar el ordenamiento
consistentemente, antes o después del
evento de sincronzación.
Diagramas de ordenamiento
FE1
t1
c1
c2
AR1
AR2
AR3
FE2
Totalmente
t2 Ordenado
Ord. Causal
(c1 y c2)
Arbitrario (c3)
c3
Ordenamiento Sincrónico
FE1
S
AR1
AR2
AR3
FE2
c1
t1
c2
t2
c1, c2: causal
t1, t2: total
s: sincrónico
Implementaciones del
ordenamiento de mensajes
Hay dos aproximaciones al problema:
Hold-Back: un requerimiento ri que arriba a
un AR no es procesado hasta que no se
satisfacen las condiciones de ordenamiento
requeridas
El problema guarda similitud con las
condiciones de comunicación en grupo (por
ej. Multicast Ordenado)
Hold-Back
Un requerimiento r es estable en un AR si
todos los requerimientos previos (según el
criterio de ordenamiento vigente) han sido
procesados
Todo requerimiento estable está en
condiciones de ser procesado por el AR
Hold-Back: Arquitectura
Procesamiento
de
Requerimientos
Cola de Procesamiento
Cola de ‘Hold-Back’
requerimiento
Funcionamiento
Al arribar un requerimiento al AR es
encolado en Hold-Back
Cuando este requerimiento está estable,
pasa a la cola de Procesamiento
La unidad de procesamiento extrae los
requerimientos uno a uno de esta cola
Requerimientos para la
implementación
Seguridad: la implementación debe
asegurar que una vez que se procesó un
requerimiento r es imposible que arribe un
requerimiento previo
Liveness: Ningún requerimiento debe
esperar indefinidamente en la cola de
Hold-Back
Implementaciones:
ISIS toolkit: es un software que corre
sobre Unix y brinda un entorno de
multicast ordenado para entregar los
requerimientos a los AR’s
Gossip: entrega los mensajes no
ordenados, basándose en la propagación
de updates entre AR’s
Descargar

Replicación, parte I - Departamento de Sistemas e Informática