Consistencia y

Replicación

Capítulo 6
Sistemas Distribuidos
Andrew Tanenbaum
¿Por qué replicar?
 Confiabilidad
 Continuidad de trabajo ante fallas
 Mayor cantidad de copias  mejor protección
contra corrupción de datos
 Rendimiento
 Escalabilidad en número
 Escalabilidad en área geográfica (menor tiempo
de acceso a copias cercanas)
 Consulta simultánea de datos
Javier Bustos Jiménez, Sistemas Distribuidos 2
Replicación de objetos
 ¿Cómo proteger el objeto contra el acceso
simultáneo de múltiples clientes?

Javier Bustos Jiménez, Sistemas Distribuidos 3

… acceso simultaneo
 Básicamente hay dos soluciones:
 El mismo objeto maneja las invocaciones
concurrentes (a).
 El objeto está desprotegido y el entorno se
preocupa del control de concurrencia (b).

En ambos casos, la réplica siempre debe

permanecer actualizada

Javier Bustos Jiménez, Sistemas Distribuidos 4

… en otras palabras:

Javier Bustos Jiménez, Sistemas Distribuidos 5

Objetos replicados:

a) La inteligencia de la replicación va en el objeto

b) La inteligencia de la replicación va en el sistema distribuido

Javier Bustos Jiménez, Sistemas Distribuidos 6

¿ReplicaciónEscalabilidad?
+ escala  - rendimiento
 Por 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

Javier Bustos Jiménez, Sistemas Distribuidos 7

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

Javier Bustos Jiménez, Sistemas Distribuidos 8

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.

Javier Bustos Jiménez, Sistemas Distribuidos 9

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)
Javier Bustos Jiménez, Sistemas Distribuidos 10
 Consistencia Secuencial
Las escrituras fueron vistas en
otro orden, pero por todos igual

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 Javier
programa.
Bustos Jiménez, Sistemas Distribuidos 11
Linealidad
 Más débil que la consistencia estricta pero más
fuerte que la consistencia secuencial.
 Se utiliza una marca generada por algún reloj
global:
 Sea tsOP(x) la marca de tiempo asignada a la operación OP
realizada sobre el dato x, donde OP puede ser lectura (R)
o escritura (W)
 Una operación es linealizable si y sólo si:
 Es consistencia secuencial

 ts
OP1(x) < tsOP2(x) si OP1 precede a OP2 en esa secuencia.

Javier Bustos Jiménez, Sistemas Distribuidos 12

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

Proceso P1 Proceso P2 Proceso P3

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

 ¿Cuáles secuencias de ejecución serán válidas?

Javier Bustos Jiménez, Sistemas Distribuidos 13

… secuencias válidas
 Cuatro secuencias válidas, el eje vertical es el tiempo.
 Signature = concatenación de la salida en orden P1 P2 P3
 Notar que la linealidad (orden en un mismo color) se mantiene.
x = 1; x = 1; y = 1; y = 1;
print (y, z); y = 1; z = 1; x = 1;
y = 1; print (x,z); print (x, y); z = 1;
print (x, z); print(y, z); print (x, z); print (x, z);
z = 1; z = 1; x = 1; print (y, z);
print (x, y); print (x, y); print (y, z); print (x, y);

Prints: 001011 Prints: 101011 Prints: 010111 Prints: 111111

Signature: Signature: Signature: Signature:

001011 101011 110101 111111
Javier Bustos Jiménez, Sistemas Distribuidos 14
(a) (b) (c) (d)
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.
 Los datos son causalmente consistentes si:
 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.
Javier Bustos Jiménez, Sistemas Distribuidos 15
… ejemplo

 Esta secuencia es permitida con un almacenamiento

causalmente consistente, pero no con uno del tipo
secuencialmente consistente o superior.

Javier Bustos Jiménez, Sistemas Distribuidos 16

… ejemplo 2
Posible dependencia

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

Javier Bustos Jiménez, Sistemas Distribuidos 17

Consistencia FIFO

 Toda escritura realizada por un proceso

deben ser vistas por los otros procesos
en el orden que fueron realizadas.

 Escrituras desde diferentes procesos

pueden ser vistas en orden distinto por
diferentes procesos.

Javier Bustos Jiménez, Sistemas Distribuidos 18

Ejemplo de consistencia FIFO

Javier Bustos Jiménez, Sistemas Distribuidos 19

¿Qué procesos mueren?

Process P1 Process P2
x = 1; y = 1;
if (y == 0) kill (P2); if (x == 0) kill (P1);
 Intuitivamente: P1, o P2, o ninguno.
 Con consistencia FIFO pueden morir ambos:

 P1 hace R1(y)0 antes de ver el W2(y)1

 P2 hace R2(x)0 antes de ver el W1(x)1

 ¿Por qué? Porque sólo las escrituras de un mismo proceso se ven en orden

Javier Bustos Jiménez, Sistemas Distribuidos 20

… pero!
 Este esquema es muy restrictivo: no todos
los procesos quieren ver todas las escrituras
(puede que no estén relacionados).
 Lo mejor es una vez que se tenga un

resultado final, propagarlo. Pero ¿Cómo

saber cuando se tiene un resultado final?
  Secciones críticas

  Variables de sincronización (S)

Javier Bustos Jiménez, Sistemas Distribuidos 21

Consistencia Débil
 Propiedades:
 Los accesos a variables de sincronización
asociadas a los datos almacenados son
secuencialmente consistentes.

 No se permite operación sobre una variable de

sincronización hasta que todas las escrituras
previas se hayan completado.

 No se permite operaciones de escritura o lectura

sobre items de datos hasta que no se hayan
completado todas las operaciones previas sobre las
variables de sincronización.
Javier Bustos Jiménez, Sistemas Distribuidos 22
Consistencia Débil
 La sincronización fuerza a que todos los procesos
vean la última actualización (escritura) sobre una
variable.

 La consistencia débil asegura consistencia sobre un

grupo de operaciones, no sobre lecturas o
escrituras aisladas.

 Útil, por ejemplo, en transacciones distribuidas.

Javier Bustos Jiménez, Sistemas Distribuidos 23

Ejemplo de consistencia débil

Como P2 y P3 no han
sincronizado, pueden ver las
escrituras en cualquier orden

Javier Bustos Jiménez, Sistemas Distribuidos 24

… pero
 Cuando uno accede a la variable de
sincronización ¿cómo saber si es para
finalizar una escritura o para comenzar una
lectura?
 Se necesitan entonces dos variables de
sincronización en vez de una (¿?)
 O dos tipos de operaciones sobre la variable de
sincronización (¿?)

Javier Bustos Jiménez, Sistemas Distribuidos 25

Consistencia relajada
 Se utilizan dos operaciones:
 Acquire: avisa la entrada a la sección crítica
 Release: avisa la salida de la sección crítica

 También reemplazable por barreras: ningún

proceso puede seguir hasta que todos hayan
alcanzado el punto de sincronización.

Javier Bustos Jiménez, Sistemas Distribuidos 26

Ejemplo de consistencia
relajada

P3 no hizo uso de la variable de sincronización, por lo

tanto puede leer cualquiera de sus valores en el tiempo

Javier Bustos Jiménez, Sistemas Distribuidos 27

Consistencia relajada
 Reglas:

 Antes que una operación de lectura o escritura

sobre variables compartidas sea realizada, todos
los acquire previos deben haber sido completados.

 Antes de permitir una liberación, todas las lecturas

o escrituras previas por el proceso deben
completarse.

 Los accesos a las variables de sincronización son

FIFO consistentes.
Javier Bustos Jiménez, Sistemas Distribuidos 28
… por lo tanto
 La consistencia relajada garantiza que:
 Al hacer un acquire, las copias de los datos
protegidos estarán actualizadas.
 Al hacer un release, las actualizaciones se
propagarán a las otras copias.

 Pero:
 Hacer un acquire no garantiza que los cambios
locales serán propagados inmediatamente.
 Hacer un release no garantiza que se
actualizarán datos desde otras copias
inmediatamente.
Javier Bustos Jiménez, Sistemas Distribuidos 29
Consistencia Entry
 Modelo de consistencia del tipo relajada

 Cada ítem de dato compartido debe estar

asociado a una variable de sincronización

 Cuando un acquire es hecho sobre una

variable de sincronización, sólo los datos
asociados a esa variable serán consistentes.
Javier Bustos Jiménez, Sistemas Distribuidos 30
Consistencia Entry
 Condiciones a cumplir:
1. No se permite realizar un acceso para adquirir una variable
de sincronización respecto a un proceso hasta que todas las
actualizaciones sobre los datos compartidos han sido
realizadas con respecto a ese proceso.
2. Antes de que sea permitido realizar un modo exclusivo de
acceso a variables de sincronización por un proceso, otros
procesos no pueden retener la variable de sincronización. Ni
siquiera en el modo exclusivo.
3. Después que un modo exclusivo de acceso a la variable de
sincronización sea realizado, cualquier otro modo acceso no
exclusivo de un proceso posterior a la variable de
sincronización no se puede realizar hasta que lo haya
realizado sobreJavier
lasBustos
propias variables.
Jiménez, Sistemas Distribuidos 31
Condición 1 quiere decir…
 Cuando un proceso hace un acquire, éste no
será completo hasta que todos los datos
compartidos sean actualizados. Es decir,
todos los cambios a datos remotos deben ser
visibles.

Javier Bustos Jiménez, Sistemas Distribuidos 32

Condición 2 quiere decir…
 Antes de actualizar un dato compartido, un
proceso debe entrar a la región crítica en
modo exclusivo para estar seguro que no hay
otros procesos tratando de modificar los
datos.

Javier Bustos Jiménez, Sistemas Distribuidos 33

Condición 3 quiere decir…
 Si un proceso quiere entrar a una sección
crítica en un modo no exclusivo, primero
debe chequear la última actualización de la
variable con el dueño de la sección crítica.

Javier Bustos Jiménez, Sistemas Distribuidos 34

… ejemplo

Este pudo llegar

antes que el Acq(Ly)

Javier Bustos Jiménez, Sistemas Distribuidos 35

 En resumen:
Consistency Description
Estricta Ordenamiento en tiempo absoluto de todos los accesos compartidos.
Todos los procesos deben ver todos todos los accesos compartidos en el mismo orden. Los
Linealizada
accesos son ordenados de acuerdo a una marca de tiempo global.

Todos los procesos ven todos los accesos compartidos en el mismo orden. Los accesos no
Secuencial
están ordenados en el tiempo.
Todos los procesos ven los accesos compartidos causalmente relacionados en el mismo
Causal
orden.
Todos los procesos ven las escrituras de un proceso en el orden que éste las efectuó.
FIFO
Escrituras de diferentes procesos pueden no ser vistas en el mismo orden.
(a) Modelos de consistencia que no usan variables de sincronización
Consistency Description
Débil Los datos compartidos pueden ser considerados consistentes luego de que se haya hecho la
sincronización.
relajada Los datos compartidos son hechos consistentes cuando la región crítica es abandonada.
Entry Los datos compartidos pertenecientes a una región crítica son hechos consistentes cuando se
entra a la región crítica.
Javier Bustos Jiménez, Sistemas Distribuidos 36
(b) Modelos de consistencia con operaciones de sincronización
Modelos de Consistencia
Centrados en el Cliente
 Bajo número de actualizaciones simultáneas
 Fácil resolución entre actualizaciones
concurrentes.
 Generalmente son operaciones de lectura.
 Modelo de consistencia bastante débil
(consistencia eventual, o de eventos).
 Consistencia garantizada para un único
cliente, por lo tanto muchas inconsistencias
son ocultadas fácilmente.
Javier Bustos Jiménez, Sistemas Distribuidos 37
Consistencia eventual
 The principle of a mobile user accessing
different replicas of a distributed database.

Javier Bustos Jiménez, Sistemas Distribuidos 38

Notación:
 Sea xi[t] la versión del ítem 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 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.
Javier Bustos Jiménez, Sistemas Distribuidos 39
Lecturas Monotónicas
 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.

Javier Bustos Jiménez, Sistemas Distribuidos 40

 Ejemplo de lectura
monotónica:

Si leí R(x1) desde L1

me debo asegurar que
leeré R(x1) en L2.

t t

Operaciones de lectura realizadas por un único proceso P sobre

dos copias locales (L1 y L2) del almacenamiento de datos.
Javier Bustos Jiménez, Sistemas Distribuidos 41
Escrituras 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 ítem de dato x es completada antes de
cualquier otra operación de escritura sobre x por
el mismo proceso.
Javier Bustos Jiménez, Sistemas Distribuidos 42
… ejemplo

Operaciones de escritura realizadas por un proceso P en

dos copias locales del mismo almacen de datos.
Javier Bustos Jiménez, Sistemas Distribuidos 43
Lea sus escrituras
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 ítem de dato x será siempre
visto por las sucesivas operaciones de lectura
sobre x por el mismo proceso.

Javier Bustos Jiménez, Sistemas Distribuidos 44

 … ejemplo

Si escribí x1 en L1 me
debo asegurar que lo
lea desde L2.

Similar a lecturas monotónicas, sólo que esta vez la

consistencia está garantizada por la última operación de
escritura de P, en vez de la última operación de lectura.
Javier Bustos Jiménez, Sistemas Distribuidos 45
Escrituras siguen a Lecturas
 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 ítem de dato x realizada luego de leer ese
dato x, se realizó garantizadamente sobre el valor
más reciente de x.
Javier Bustos Jiménez, Sistemas Distribuidos 46
… ejemplo

Si leí x1 en L1 me debo
asegurar que toda escritura
posterior al menos lleve x1
en cualquier copia.

Operaciones de escritura realizadas por un proceso P en

dos copias locales del mismo almacen de datos.
Javier Bustos Jiménez, Sistemas Distribuidos 47
Ubicación de réplicas

 Organización lógica de diferentes clases de copias

de datos almacenados en tres anillos concéntricas
Javier Bustos Jiménez, Sistemas Distribuidos 48
Replicas permanentes
 Es el primer subconjunto de réplicas.
 Comúnmente son un número pequeño de

réplicas.
 Ejemplos:
 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).
Javier Bustos Jiménez, Sistemas Distribuidos 49
Replicas iniciadas por el
servidor
 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?

Javier Bustos Jiménez, Sistemas Distribuidos 50

… una solución
 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.
Javier Bustos Jiménez, Sistemas Distribuidos 51
… reevaluación de réplicas
 Si Q determina que el
número de pedidos de
F es menor a un cierto
límite, se borra F de
esa réplica (a menos
que sea la última).
 Si P tiene más de la
mitad de los accesos a
F, entonces se lleva F
de Q a P.

Javier Bustos Jiménez, Sistemas Distribuidos 52

… pero
 Si P no puede recibir F
(por ejemplo, no tiene
espacio de disco
suficiente), y el número
de accesos es mayor
que un cierto límite, F
se replica a otros
servidores: el más
lejano que supere un
cierto % de accesos a
F.
Javier Bustos Jiménez, Sistemas Distribuidos 53
Réplicas 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 cercanos.
Javier Bustos Jiménez, Sistemas Distribuidos 54
Propagación de
actualizaciones
 ¿Qué propagar? Básicamente hay 3 opciones:

 Propagar sólo la notificación de actualización (protocolos

de invalidación)

 Transferir datos completos de una copia a otra (útil cuando

hay más lecturas que escrituras)

 Propagar la operación de actualización (también conocido

como active replication), parte de la base que cada
almacén es capaz de actualizar sus datos mediante
operaciones, lo cual implica mayor procesamiento en las
réplicas.

Javier Bustos Jiménez, Sistemas Distribuidos 55

 Protocolos tipo Pull v/s Push

Asunto Basado en Push Basado en Pull

En el servidor Lista de réplicas de clientes y cachés Ninguna

Actualización (y posiblemente búsqueda

Mensajes enviados Pull y actualización
de la actualización después)
Tiempo de
Tiempo de Inmediato (o tiempo de búsqueda y
búsqueda y
respuesta al cliente actualización)
actualización

 Comparación entre protocolos basados en push (del

servidor a los clientes) y pull (de los clietnes al servidor)

Javier Bustos Jiménez, Sistemas Distribuidos 56

Protocolos de Consistencia
 Un protocolo de consistencia describe una
implementación de un modelo específico de
consistencia.
 Los modelos de consistencia en los cuales las
operaciones están globalmente serializadas son los
modelos más importantes; y los más ampliamente
aplicados incluyen: consistencia secuencial,
consistencia débil con variables de sincronización y
transacciones atómicas.
 Los protocolos pueden ser:
 Basados en el primario
 De escritura replicada.

Javier Bustos Jiménez, Sistemas Distribuidos 57

Protocolos Basados en el
Primario
 Cada ítem de dato x tiene en el
almacenamiento de datos un primario
asociado, el cual es responsable de
coordinar las operaciones de escritura sobre
x.
 El primario:
 O bien está fijo en un servidor remoto;
 O bien se trae el primario a la copia local y las
operaciones de escritura se ejecutan localmente.
Javier Bustos Jiménez, Sistemas Distribuidos 58
Servidor fijo y reenvio de
requerimientos

Javier Bustos Jiménez, Sistemas Distribuidos 59

Protocolo de respaldo primario

Javier Bustos Jiménez, Sistemas Distribuidos 60

… ¿problema?
 Quienhizo el update (W1) puede demorar
mucho en recibir la autorización de continuar
(W5), porque usualmente actualizar es
bloqueante ¿Soluciones?:
 Usar un esquema no bloqueante… lo cual genera
problemas de tolerancia a fallas (¿cómo saber
que hizo lo que dijo que haría?)
 ¿Mover el primario?

Javier Bustos Jiménez, Sistemas Distribuidos 61

Escrituras Locales: el primario
se mueve entre los procesos

Javier Bustos Jiménez, Sistemas Distribuidos 62

… pero
 ¿Cómo saber donde se encuentra el dato
actualmente?
 Exceso de movimientos del dato (se mueve
para read y writes)… mejor moverlo sólo
para las escrituras.
 Ventajas: Múltiples escrituras locales mientras los
otros leen sus copias locales.
 Desventajas: Funciona sólo si las actualizaciones
son no bloqueantes y propagadas a las réplicas
después de actualizar el primario.
Javier Bustos Jiménez, Sistemas Distribuidos 63
Escrituras locales moviendo el
primario sólo para actualizar.

Javier Bustos Jiménez, Sistemas Distribuidos 64

Protocolos de Escritura
Replicada
 En los protocolos de escritura replicada, las
operaciones de escritura pueden ser
ejecutadas en múltiples réplicas en vez de
sólo una.
 Se dividen en:
 Replicación activa: una operación es llevada a
todas las réplicas.
 Protocolos basados en votación (quorum)

Javier Bustos Jiménez, Sistemas Distribuidos 65

Replicación Activa
 Cada replica tiene asociado un proceso que
se encarga de las actualizaciones, enviando
a las otras réplicas la operación que produjo
la actualización, no el valor del dato.
 Pro: Reducción de ancho de banda para datos
grandes
 Contras: Se debe mantener el orden de las
operaciones.
 ¿Qué
pasa si cada réplica debía operar
además sobre otra réplica?
Javier Bustos Jiménez, Sistemas Distribuidos 66
Invocaciones replicadas

Javier Bustos Jiménez, Sistemas Distribuidos 67

… pero
 Imaginen que la operación sobre C es
transferir $1.000.000. Alguien va a pagar por
ese error, y mucho.
 Solución: replication-awareness: la

invocación es asignada a una única réplica

mediante la elección de un coordinador. El
mismo mecanismo se usa para la respuesta
desde las réplicas.

Javier Bustos Jiménez, Sistemas Distribuidos 68

Replication awareness

Javier Bustos Jiménez, Sistemas Distribuidos 69

Protocolos basados en votos
 La idea es obtener el permiso de múltiples
servidores antes de leer o escribir un dato
replicado.
 Por ejemplo: para actualizar, hay que hacerlo

en la mitad más uno de los servidores. Para

leer, hay que tener al menos la mitad más
uno de los datos en la misma versión.

Javier Bustos Jiménez, Sistemas Distribuidos 70

Algoritmo de Gifford
 Sean N réplicas
 NR = Quórum de lectura
 NW = Quórum de escritura
 Se debe cumplir que:
 NR + NW > N (previene conflictos de lectura /
escritura)
 NW > N/2 (previene conflictos de escritura)

Javier Bustos Jiménez, Sistemas Distribuidos 71

… ejemplos

Si un cliente elige {A,B,C,D,F,G} Todos pueden leer

y el otro {D,H,I,J,K,L} para cualquier réplica, el
escribir, ambas serán aceptadas problema es que se
y hay conflicto en D. Esto debe actualizar
porque NW <= N/2 todas siempre.
Javier Bustos Jiménez, Sistemas Distribuidos 72
Aplicación: memoria
compartida distribuida
 La memoria se parte en “bloques” fijos

 El “caching” evita la latencia de acceso

 Puede soportar: migración y/o replicación

Javier Bustos Jiménez, Sistemas Distribuidos 73

… aspectos a considerar:
 Granularidad (¿false sharing?)
 Estructura del espacio de memoria
compartida
 Coherencia de memoria y sincronización de
acceso
 Localización de datos y accesos
 Estrategias de reemplazo
 Trashing
 Heterogeneidad

Javier Bustos Jiménez, Sistemas Distribuidos 74

Estructura
 No estructurada: es un arreglo de palabras.

 Por tipos de datos: colección de objetos (sistemas

Clouds y Orca) o colección de variables en lenguaje
fuente (sistemas Munin y Midway). Granularidad al
nivel de variable u objeto.

 Como base de datos: implica una memoria

asociativa.

Javier Bustos Jiménez, Sistemas Distribuidos 75

Implementación
 Lamás común: modelo de consistencia
secuencial, porque:
 Es realizable
 Soporta semántica más intuitiva para la
coherencia de memoria.
 No impone nada extra al programador
 Pero:
 Posee bajo nivel de concurrencia

Javier Bustos Jiménez, Sistemas Distribuidos 76

Estrategias para consistencia
secuencial:
 El protocolo dependerá de la estrategia elegida.
 Estrategias:
 No réplica, no migratoria (NRNMB): cliente – servidor.

 No réplica, migratoria (NRMB): lleva bloques a quien lo

usa.

 Réplica, migratoria (RMB): lleva la réplica más cercana a

quien lo usa.

 Réplica, no migratoria (RNMB): acceso a la réplica más

cercana.
Javier Bustos Jiménez, Sistemas Distribuidos 77
Protocolos:
 Escritura invalidante: El nodo con la última
actualización se encarga de invalidar las
otras.
 Escritura actualizada: ordenamiento total de

las operaciones de escritura para lograr la

consistencia secuencial. Utiliza un
secuenciador global.

Javier Bustos Jiménez, Sistemas Distribuidos 78

Localización:
 Broadcasting: produce cuello de botella y problemas
de latencia.
 Servidor centralizado: reduce el paralelismo y una
falla mata el sistema.
 Servidor distribuido fijo: Cada nodo posee un
subconjunto fijo de los datos, ante falla esa
información se pierde.
 Servidor distribuido dinámico: Cada nodo tiene su
propia tabla sobre la ubicación de los bloques, pero
no siempre está actualizada.
 En RNMB las localizaciones no cambian y siempre
al escribir se actualiza.
Javier Bustos Jiménez, Sistemas Distribuidos 79
Estrategias de reemplazo
 ¿Qué bloque debe ser reemplazado?
 Usado v/s no usado (LRU)
 En algunos sistemas un bloque es clasificado como: no
usado, Nil (invalidado), Read-only (RO), Read-owned (RO
y el nodo es dueño), Escribible. Y la prioridad de
reemplazo es:
1. No usado y Nil
2. Read-only
3. Read-owned
4. Escribible
 ¿Donde?
 Almacenamiento secundario
 Memoria de otros nodos
Javier Bustos Jiménez, Sistemas Distribuidos 80
¿Trashing?
 Si hay mirgación y se produce que:

 Hay datos entrelazados entre distintos nodos

 Bloques con permiso RO son repetidamente

invalidados inmediatamente luego que son
replicados

… es decir: hay baja localidad de datos

Javier Bustos Jiménez, Sistemas Distribuidos 81
¿Solución?
 Proveer locks de aplicación controlada: fija el
bloque por un tiempo.
 No permitir que quiten, por un tiempo t, un

bloque de nodo (t generado por estadística o

accesos)
 Ajustar el algoritmo de coherencia para usar

modelos de datos compartidos.

Javier Bustos Jiménez, Sistemas Distribuidos 82

FIN

Javier Bustos Jiménez, Sistemas Distribuidos 83