1 Sistemas DistribuídosReplicación Sistemas Distribuídos

2 Objetivos Aumentar la disponibilidad Mejorar los tiempos de respuestaIncrementar la tolerancia a fallas

3 Candidatos a replicaciónDatos (por ejemplo, una base de datos críticos) Servicios: Comunicaciones Servicio de nombres Servicio de archivos Recursos en general

4 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)

5 Mejoras en la perfomanceMú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

6 Mejoras en la disponibilidadDatos 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

7 Mejoras en la disponibilidadSupongamos 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

8 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

9 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

10 Requerimientos Transparencia de replicación: Consistencia: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

11 Operaciones de acceso a objetosread: lectura del estado de un objeto (no lo modifica) write: cambio del estado de un objeto (lo modifica) también llamada update u overwrite

12 Operaciones de lecturaLeer uno (primario) lectura Leer uno Leer quorum

13 Operaciones de escrituraEscribir uno (primario) Sobreescribir Escribir todos Escritura Escribir todos los disponibles Escribir un quorum Leer y modificar Escribir Gossip

14 Modelos de ReplicaciónAsí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

15 Modelos de ReplicaciónSincró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

16 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.

17 Modelo Arquitectural Front Ends Servicio replicado AR cliente FE ARAdministradores de réplica Requerimientos y respuestas

18 Componentes del modeloClientes: 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

19 Implementación I: Gossipmensajes AR cliente FE AR cliente FE cliente AR FE 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

20 Implementación II: Réplica primariaPrimario En rojo: escrituras En verde: lecturas AR cliente FE AR cliente FE cliente AR FE 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.

21 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

22 Consistencia y ordenamiento de requerimientosAsumimos 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

23 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

24 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.

25 Ordenamiento SincrónicoPermite 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.

26 Diagramas de ordenamientoFE1 AR1 AR2 AR3 FE2 Totalmente Ordenado t1 t2 Ord. Causal (c1 y c2) Arbitrario (c3) c1 c3 c2

27 Ordenamiento SincrónicoFE1 AR1 AR2 AR3 FE2 S c1 t1 t2 c2 c1, c2: causal t1, t2: total s: sincrónico

28 Implementaciones del ordenamiento de mensajesHay 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)

29 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

30 Hold-Back: ArquitecturaProcesamiento de Requerimientos Cola de Procesamiento Cola de ‘Hold-Back’ requerimiento

31 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

32 Requerimientos para la implementaciónSeguridad: 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

33 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