Consistencia y Replicación

Consistencia y Replicación

Martínez González GerardoCruz Casas Hernando

Tapia Contreras José Antonio

¿Por qué replicar?

Confiabilidad◦Continuidad de trabajo ante fallas◦Mayor cantidad de copias mejor protección

contra corrupción de datosRendimiento

◦Escalabilidad en número◦Escalabilidad en área geográfica (menor tiempo

de acceso a copias cercanas)◦Consulta simultánea de datos

ReplicaciónTécnica Escalabilidad

+ escala - rendimientoPor lo tanto se usa replicación (caching)

para reducir el tiempo de acceso en alta escala.

Problemas: ◦Actualizar las réplicas consume ancho de

banda◦Mantener la consistencia en las copias es un

problema de escalabilidad (¿?)◦Sincronizar las réplicas

Modelos de Consistencia.

Contrato entre los procesos y el almacenamiento de datos:◦Si los procesos acuerdan obedecer ciertas

reglas, el almacenamiento promete trabajar correctamente.

◦Normalmente una operación de lectura debiese retornar la última actualización del dato.

◦Los modelos pueden ser: Centrados en los datos Centrados en el cliente

Modelos de Consistencia centrados en los datos.

Organización general de un almacenamiento lógico de datos, físicamente distribuidos y replicados a través de múltiples procesos.

Consistencia Estricta.

El más restrictivo de todos. Cualquier lectura sobre un ítem de dato

x retorna un valor correspondiente con la más reciente escritura sobre x (en términos de un hipotético reloj de tiempo global)

Consistencia Secuencial.

La consistencia secuencial satisface:

El resultado de una ejecución es el mismo si todas las operaciones (lectura y escritura) de todos los procesos sobre el dato fueran ejecutadas en algún orden secuencial y las operaciones de cada proceso individual aparecen en esta secuencia en el orden especificado por su programa.

Proceso P1 Proceso P2 Proceso P3

x = 1;print ( y, z);

y = 1;print (x, z);

z = 1;print (x, y);

Se tienen tres procesos que se ejecutan concurrentemente, todos ellos inicializaron sus variables en 0.

x = 1;print (y, z);y = 1;print (x, z);z = 1;print (x, y);

Prints: 001011

(a)

x = 1;y = 1;print (x,z);print(y, z);z = 1;print (x, y);

Prints: 101011

(b)

y = 1;z = 1;print (x, y);print (x, z);x = 1;print (y, z);

Prints: 010111

(c)

y = 1;x = 1;z = 1;print (x, z);print (y, z);print (x, y);

Prints: 111111

(d)

Cuatro secuencias válidas, el eje vertical es el tiempo. Signature = concatenación de la salida en orden P1 P2 P3Notar que la linealidad (orden en un mismo color) se mantiene.

Consistencia Secuencial.

a) Almacén de datos secuencialmente consistente

Consistencia Causal.

Debilitamiento de la consistencia secuencial

Se diferencian eventos que están potencialmente relacionados en forma causal y otros que no, los no relacionados se dicen concurrentes.

Consistencia Causal.

Todas las escrituras que están parcialmente relacionadas en forma causal son vistas por todos los procesos en el mismo orden. Las concurrentes pueden ser vistas en distinto orden sobre diferentes máquinas.

Posible dependencia

Si son dependientes, todos deben ver las escrituras en el mismo orden.

MODELOS DE CONSISTENCIA CENTRADA EN EL CLIENTE

•Este tipo de modelos trata una clase especial de almacenamientode datos distribuidos.

•Los almacenamiento de datos referidos están caracterizadospor una falta de actualizaciones simultáneas, o cuandodichas actualizaciones ocurren, pueden ser fácilmenteresueltas.

•La mayoría de las operaciones son de lectura.

•La introducción de modelos de consistencia centrados en elcliente permiten esconder muchas inconsistencias demanera relativamente fácil.

En esencia la consistencia centrada en el cliente provee garantías para un único cliente concerniente a la consistencia de accesos a los datos de ese cliente.

MODELOS DE CONSISTENCIA CENTRADA EN EL CLIENTE

Consistencia momentánea

Sistema de bases de datos, difícilmente realizan actualización, en su mayoría leen los datos

DNS, está dividido en dominios, cada dominio es asignado a una autoridad de asignación, que actúa como propietario del dominio, y sólo se le permite actualizar a esta autoridad, no se necesita manejar conflictos escritura-escritura, solamente lectura-escritura, se tolera una actualización lenta

World Wide Web, las páginas web son actualizadas por una sola autoridad. Inconsistencia en la caché.

Se tolera cierto grado de inconsistencia.

Todas las réplicas convergen en copias idénticas

Consistencia momentánea

Solo requiere la garantía de que todas las actualizaciones se propaguen a todas las réplicas.

La implementación es barata

Existen problemas cuando en tiempo corto se accede a réplicas diferentes

Consistencia momentánea

Sea xi[t] la versión del elemento de dato x en la copia local Li al tiempo t.

La versión xi[t] es es el resultado de una serie de operaciones de escritura sobre Li desde la inicialización, denotada WS(xi[t]).

Si WS(xi[t1]) fue además realizada sobre lo copia local Lj al tiempo posterior t2 entonces la serie se escribirá WS(xi[t1];xj[t2]).

Si el orden de las operaciones o el tiempo son claros por el contexto, el índice del tiempo se omite.

Notación:

Se dice que un dato ofrece consistencia de lecturas monotónicas si y sólo si la siguiente condición se cumple:

◦Si un proceso lee el valor de un ítem de dato x, cualquier operación de lectura sucesiva sobre x por el mismo proceso siempre retornará el mismo valor o un valor más reciente.

Lectura monotónicas

Garantiza que si un proceso ha visto un valor de x al tiempo t, nunca verá una version más vieja de x en un tiempo posterior.

Ejemplo; base de datos correo electrónico

Lectura monotónicas

Las escrituras deben ser propagadas en el orden correcto a todas las copias del almacenamiento de datos.

Se debe cumplir que:

◦Una operación de escritura por un proceso sobre un elemento de datos x es completada antes que cualquier otra operación sucesiva de escritura sobre x por el mismo proceso.

Escrituras monotónicas

Es decir, una operación de escritura sobre una copia del elemento x se realiza sólo si esa copia se ha actualizado mediante cualquier operación de escritura previa.

Si es necesario, la nueva escritura debe esperar a que terminen otras escrituras anteriores.

Escrituras monotónicas

Ejemplo: biblioteca de software; al actualizar, se actualizará de version.

Escrituras monotónicas

A veces es más importante garantizar que si yo escribo un dato, yo siempre vea el valor actualizado no importa de donde haga la siguiente lectura, por lo tanto, un almacén de datos provee consistencia lea sus escrituras si se cumple que:◦El efecto de una operación de escritura por un

proceso sobre un elemento de datos x será siempre visto por las sucesivas operaciones de lectura sobre x por el mismo proceso.

Lea sus Escrituras

Una operación de escritura siempre se completa antes de una operación de lectura sucesiva del mismo proceso, independiente del lugar.

Ejemplo, Cache de un documento. Si el editor y el navegador se integran en un solo programa el caché se invalida cuando la página es actualizada

Lea sus Escrituras

Lea sus Escrituras

La idea de este esquema de consistencia es garantizar que si alguien va a modificar el valor de un dato, antes haya leído la última actualización de éste.

Un almacén de datos provee consistencia de escrituras siguen lecturas si se cumple que:◦Una operación de escritura de un proceso sobre

un elemento de datos x realizada luego de leer ese dato x, se realizó garantizadamente sobre el valor más reciente de x.

Las escrituras siguen a las lecturas

Las escrituras siguen a las lecturas

Cualquier operación sucesiva de un proceso sobre un elemento de datos x se realizará sobre una copia de x actualizada con el valor más reciente leído por el proceso.

Ejemplo; una red de un grupo de noticias, garantiza que los usuarios vean el anuncio de una respuesta a un artículo, después de haber visto el artíiculo original.

Las escrituras siguen a las lecturas

Un punto clave para un sistema distribuido que soporta replicación es decidir donde, cuando y por quien ubicar las réplicas.

Se divide en 2:◦Ubicación de servidores de réplicas (encontrar

los mejores lugares para colocar un servidor)◦Ubicación del contenido (encontrar los mejores

servidores para colocar el contenido)

Administración de las Replicas

No es un problema muy estudiado

Qiu y colaboradores toman en cuenta la distancia entre clientes y un punto de partida

La distancia puede medirse por la latencia o el ancho de banda

Seleccionan a un servidor cuyo distancia promedio entre el servidor y sus clientes sea minimo

Ubicación del servidor de réplicas

Radoslavov y colaboradores no toman en cuenta la posición de los clientes, solo toman en cuenta la topología y al que tenga el mayor número de interfaces de red.

Metodos con alto costo de procesamiento

Szymaniak y colaboradores toman en cuenta regiones con más demanda y uno de sus nodos es la réplica

Ubicación del servidor de réplicas

Ubicación y replicación del contenido

Replicas permanentes

Es el primer conjunto de réplicas.Comúnmente son un número pequeño de réplicas.

Ejemplos:

Página web. Múltiples copias cercanas y los requerimientos son dirigidos a cada una a la vez mediante algún esquema (por ejemplo round-robin).Múltiples copias lejanas a las cuales se elige entrar (mirror).

Replicas iniciadas por servidores

Copias del almacén de datos para mejorar la performance.Réplicas creadas y actualizadas bajo la iniciativa del dueño del almacén de datos (servidor)Problema principal: ¿Dónde poner las réplicas? (cerca/lejos) ¿Cuándo actualizarlas?

Replicas iniciadas por servidores

Replicas iniciadas por servidores

Cada servidor cuenta el número de accesos.

Cada cliente accede al servidor más cercano.

Si C1 y C2 comparten el servidor más cercano (P), y éste no tiene réplica, se toma como si P fuese quien realiza la consulta.

Replicas iniciadas por el cliente

Más conocidas como caché de cliente.Copia temporal de datos para el uso del cliente.Mejora el tiempo de acceso a datos.Útil si la mayoría de las operaciones son de lectura.Caché puede ser compartido entre un grupo de clientes cercanosTiempo limitadoUso de servidores cachéSe está volviendo más efectivo la replicación iniciada por el servidor debido a las mejoras en la red y al desempeño de los servidores.

Distribución de Contenido

Estado vs. Operaciones

Propagar notificaciones.◦ Usan protocolos de invalidación.◦ Indica que parte del almacén de datos es invalido.◦ Se necesita actualizar el almacén de datos.

Transferir datos entre copias◦ La relación de escritura-lectura es grande.◦ Se propagan los datos modificados y se registran cambios.◦ Varias modificaciones en un solo mensaje.

Propagar la operación a todas las copias◦ Se indica a cada replica la operación de actualización a realizar.◦ Se llama también: Replicación activa.◦ Similar al proceso efectuado en un Raid 1.

Protocolos Push y Pull.

Push◦Protocolo basado en servidor.◦Las actualizaciones se propagan a otras replicas sin

que estas las soliciten.◦Actualizan los cachés de los clientes.◦Hay datos consistentes al momento de solicitarlos.

Pull◦Protocolo basado en el cliente.◦El cliente solicita a otro servidor que le envíe

cualquier actualización que tenga al momento.◦Estrategia aplicada en los cachés Web.

Difusión simple vs. Multidifusion.

Difusión simple.◦Se envía la actualización a N servidores.◦Se envían N mensajes de actualización.

Multidifusion.◦La red subyacente se encarga de enviar un

mensaje a varios destinatarios.◦Suele ser eficiente combinada con una red

pequeña y utilizando el método push.

Protocolos de escritura

Escritura remota.◦ La primaria realiza la actualización en su copia local.◦ Posteriormente se remite la actualización a los servidores

de respaldo.◦ Se envía un acuse a quien inicio el proceso de

actualización.

Escritura local.◦ Se pueden realizar varios procesos de escritura local.◦ Se envían las actualizaciones a los servidores de

respaldo una vez terminados los procesos.◦ Se aplica a computadoras móviles capaces de operar

desconectadas, al terminar todo se vuelve al servidor primario.

Protocolos de escritura replicados.

Replicación activa.◦Cada replica con un proceso asociado que realiza

operaciones de actualización.◦Las operaciones deben realizarse en el mismo orden

en cualquier parte.◦Debe existir un cronometro llamado secuenciador.

Protocolo basado en quórum.◦Se utiliza votación.◦Requiere que los clientes adquieran permiso de

varios servidores para leer o escribir elementos de datos replicados.