Universidad Nacional del Sur – Departamento de Ciencias e Ingeniería de la Computación Elementos de Bases de Datos – 2do. Cuatrimestre de 2004

Protocolo de Bloqueo de Dos Fases Planificación 1 T1.1

Elementos de Bases de Datos

T1.2

T2.2 Wlock A2 Unlock A2

Wlock A1 Wlock A2 Unlock A1 Unlock A2

Dpto.Ciencias e Ingeniería de la Computación Universidad Nacional del Sur

En S1

Lic. María Mercedes Vitturini [[email protected]]

Clase 23

T2.1

Wlock A1 Unlock A1

En S2

• Los elementos que aparecen en una misma línea podrían ocurrir simultáneamente, o en cierto orden. • Según el sitio S1, T1.1 debe preceder a T2.1 (T1 antes que T2). • Según el sitio S2, T2.2 debe preceder a T1.2 (T2 antes que T1). • Por lo tanto, esta planificación no es serializable.

1er. Cuatrimestre de 2004

Elementos de Bases de Datos Clase 23

Serializabilidad en Bases de Datos Distribuidas

Protocolo de Compromiso Distribuido

Š En el protocolo de bloqueo de dos fases estricto cada

subtransacción debe informar a las otras subtransacciones de que ha requerido todos los bloqueos. Š Luego de que todas las transacciones completaron su fase 1 (de bloqueo) pueden continuar con las lecturas y escrituras para luego liberar los bloqueos (unlock). Š El problema de completar la fase 1 se conoce como problema de concordancia distribuida. Š Para ello las subtransacciones deben llevar adelante el protocolos de compromiso (PC's). Elementos de Bases de Datos Clase 23

Inicial

Recibe Dispuesta "commit T"

a Cometer

Envía o Recibe "no T" "abort T"

Recibe "abort T"

en varias subtransacciones ejecutandose en diferentes sitios. La subtransacción del sitio S se denomina coordinador y las otras participantes. Š Cada subtransacción Ti decide si cometer o abortar, y envía al coordinador un mensaje “ready T” o “No T”. El coordinador toma la decisión final en función de las votaciones de todos los participantes. Š Cuando se presentan fallas en la red, este protocolo puede llevar a estados de bloqueo, esto es, una subtransacción en un sitio que no falló no puede cometer ni abortar hasta que se repare la falla en el sitio de origen. Elementos de Bases de Datos Clase 23

4

Protocolo de Compromiso de 2 Fases Š Mejora: cada subtransacción mide el tiempo máximo de

Cometida

espera por una respuesta (timeout).

Š Un participante que alcanza el timeout pasa al estado de

Participante

intentar recuperse.

Abortada

Inicial

Š Una transacción T que fue iniciada en un sitio S y dividida

3

Protocolo de Compromiso Distribuido Envía "ready T"

2

Š Para ello envía un mensaje de ayuda “help me” a los otros Recibe todos "ready T"

Debe Cometer

Envía "commit T"

participantes. Ante el pedido de ayuda, otros participantes según su estado constestan:

Cometida

„

Recibe al menos un "no T"

Debe Abortar

Envía ”abort T"

„

Abortada

„

Coordinador

„ Elementos de Bases de Datos Clase 23

5

Si está en estado cometida, le envía un mensaje “commit”. Si está en estado abortado, le envía un mensaje “abort”. Si está en estado decidiendo (no votó aún) decide abortar y envía “abort T” al coordinador. Si está en estado dispuesta a comenter, no puede ayudar. Elementos de Bases de Datos Clase 23

6

1

Universidad Nacional del Sur – Departamento de Ciencias e Ingeniería de la Computación Elementos de Bases de Datos – 2do. Cuatrimestre de 2004

Protocolo de Compromiso de 2 Fases

Protocolo de Compromiso de 2 Fases Coordinador

Participante Inicial

Recibe "prepare T"

Timeout

Decidiendo

Envía "no T"

Envía "ready T"

Dispuesta a Cometer

Recibe "abort T"

Bloqueada

Inicial Envía "prepare T"

Timeout Recuperar

Abortada Recibe "abort T"

Recibe "commit T"

Esperando

Recibe todos "ready T"

Debe Cometer

Envía "commit T"

Cometida

Envía "help-me T" Recibe "commit T"

Timeout o Recibe al menos un "no T"

Cometida

Elementos de Bases de Datos Clase 23

7

Un protocolo libre de bloqueos

Envía ”abort T"

Abortada

Elementos de Bases de Datos Clase 23

8

Ejemplo Š Un ejemplo de bloqueo en C2F:

Š El protocolo de C2F no está libre de bloqueo de

transacciones. Š Ningún protocolo está puede asegurar que esta totalmente libre de bloqueos. Š Intuitivamente, el protocolo de C2F permite a un participantee cometer tan pronto como sabe que todos los participantes votaron “ready commit”. El protocolo de C3F un participante no cometerá hasta no saber que todos los participantes saben (o pueden saber) que todos están dispuestos a comenter. Elementos de Bases de Datos Clase 23

Debe Abortar

„

„

„

„ „

„

9

Protocolo de Compromiso de 3 Fases

Todos los participantes están en el estado “Dispuesta a Cometer”. Un participante Ti envio “ready T” y perdió conexión con el coordinador. El coordinador recibió todos los votos y envió un mensaje “commit” a Tj. Tj y el coordinador fallan (o quedan desconectados). Ahora Ti y los otros participantes activos están bloqueados, (no saben sobre la decisión de Tj) Tj por su parte comete antes de saber que Ti sabe que están todas dispuestas a cometer. Elementos de Bases de Datos Clase 23

10

Protocolo de Compromiso de 3 Fases

ŠEl protocolo de compromiso de 3 fases evita la

posibilidad de bloqueos en para un subconjunto restringido de posibles fallos. ŠEl protocolo de compromiso de 3 fases exige que: No ocurran particiones de la red (para que en caso de fallos, se pueda elegir un nuevo coordinador). „ A lo sumo k sitios participantes pueden fallar mientras se ejecuta el protocolo. k es un parámetro que mide la tolerancia a los fallos. „ En cualquier momento, debe haber al menos k+1 sitios funcionando correctamente. „

Fase 1: (de Votación igual al Protocolo de C2F): ŠCi agrega el registro a la bitácora y lo graba en memoria estable. ŠCi envía un mensaje “prepare T” a todos los sitios donde se ejecutó T. ŠCada gestor que recibe el mensaje determina si puede o no cometer su porción de T.

ŠPara evitar bloqueos, se agrega una fase en la cual se

Respuesta Si: agrega a la bitácora, la graba en memoria estable y envía el mensaje “ready T” a Ci. „ Respuesta No: agrega a la bitácora, la graba en memoria estable y envía el mensaje “abort T” a Ci.

Elementos de Bases de Datos Clase 23

Elementos de Bases de Datos Clase 23

alcanza una decisión preliminar sobre el destino de T.

11

„

12

2

Universidad Nacional del Sur – Departamento de Ciencias e Ingeniería de la Computación Elementos de Bases de Datos – 2do. Cuatrimestre de 2004

Protocolo de Compromiso de 3 Fases Fase 2: Š Si Ci recibe un mensaje "no T" de un participante o si no recibe respuesta (en cierto período), decide abortar T y envía el mensaje "abort T" a todos los participantes. Š Si Ci recibe un mensaje "ready T" de cada sitio participante, toma la decisión preliminar de precompromiso, grabando en bitácora y envía el mensaje "precommit T" a todos los participantes. Š Cuando un participante recibe el mensaje de aborto o precompromiso graba en bitácora dicho mensaje ( o ) y envía el mensaje "acknowledge T" al coordinador. Elementos de Bases de Datos Clase 23

Protocolo de Compromiso de 3 Fases Fase 3: Esta fase se ejecuta solamente si la decisión de la Fase 2 fue de precompromiso.

ŠDespués de que se enviaron los respectivos mensajes

"precommit T" a todos los participantes, debe esperar que al menos k sitios envíen el mensaje "acknowledge T". ŠRecien en ese momento, el coordinador decide cometer grabando en bitácora y enviando un mensaje "commit T" a cada uno de los participantes. ŠCuando cada participante recibe ese mensaje, lo graba en su respectiva bitácora.

13

Protocolo de Compromiso de 3 Fases

Elementos de Bases de Datos Clase 23

Protocolo de Compromiso de 3 Fases Participante

ŠComo en el C2F, un sitio que puede decidir abortar T

enviando un mensaje "abort T" antes del "ready T". ŠMientras que en el C2F el coordinador puede incondicionalmente abortar T antes de enviar el mensaje "commit T", el mensaje "precommit T" es una promesa del coordinador de que eventualmente se cometerá T. ŠLa fase 3 de este protocolo lleva a una decisión de commit por lo que parece de poca utilidad práctica. ŠEl rol de la fase 3 se justifica en caso de fallos. Elementos de Bases de Datos Clase 23

Coordinador

Esperando

Envía "commit T"

Recibe todos "ready T"

Recibe al menos un "no T"

Debería Cometer

Debe Abortar

Envía"precommit T"

Envía ”abort T"

Elementos de Bases de Datos Clase 23

Recibe "prepare T"

Timeout

Decidiendo

Envía "no T"

Envía "ready T"

Dispuesta a Cometer

Recibe "abort T"

Abortada

Recibe "precommit T"

Timeout Recuperar Timeout

Cometida

Recibe "commit T" Lista para

Cometer

Elementos de Bases de Datos Clase 23

16

Protocolo de Compromiso de 3 Fases ŠEl protocolo de compromiso de 3 fases evita la posibilidad

Cometida

Envía "prepare T"

Inicial

15

Protocolo de Compromiso de 3 Fases Inicial

14

de bloqueos siempre que se restrinja el número de fallas posibles (algo muy difícil de garantizar). ŠEl protocolo de compromiso de 3 fases exige que:

No ocurran particiones de la red (para que en caso de fallos, se pueda elegir un nuevo coordinador). „ A lo sumo k sitios participantes pueden fallar mientras se ejecuta el protocolo. k es un parámetro que mide la tolerancia a los fallos. „ En cualquier momento, debe haber al menos k+1 sitios funcionando correctamente. „

Cometerá

ŠPara evitar bloqueos, se agrega una fase en la cual se

Abortada

alcanza una decisión preliminar sobre el destino de T.

17

Elementos de Bases de Datos Clase 23

18

3

Universidad Nacional del Sur – Departamento de Ciencias e Ingeniería de la Computación Elementos de Bases de Datos – 2do. Cuatrimestre de 2004

Manejo de Fallos en C3F

C3F - Fallo de un Participante Š Qué hace el coordinador cuando detecta el

Š Fallo de un participante „

„

fallo de un participante.

Tareas del coordinador cuando detecta el fallo de un participante. Tareas del participante como parte del proceso de recuperación.

„

„

Š Fallo del coordinador „

„

Selección de un nuevo coordinador entre los participantes. Tareas del coordinador como parte del proceso de recuperación. Elementos de Bases de Datos Clase 23

19

C3F - Fallo de un participante

„

„

de recuperación si ....

Si contiene un en su bitácora, ejecutar Redo(T). Si contiene un en su bitácora, ejecutar Undo(T). Si contiene un pero no un ni un consulta con Ci y ejecuta Undo(T) si recibe el mensaje "abort T" y Redo(T) si recibe un "commit T". Si contiene un pero no un ni un consulta con Ci Continua ... Elementos de Bases de Datos Clase 23

20

Š Qué hace un participante como parte del proceso

proceso de recuperación.

„

Elementos de Bases de Datos Clase 23

C3F - Fallo de un participante

Š Qué hace un participante como parte del „

Si Ti falla antes de enviar al coordinador un mensaje Ready T, el coordinador alcanza su timeout y aborta T. Si Ti falla después de enviar al coordinador un mensaje Ready T, el coordinador ignora la falla de Ti

21

C3F - Fallo del coordinador

„

Si contiene un pero no un ni un consulta con Ci. Š Si Ci responde que "abort T", ejecuta Undo(T). Š Si Ci responde que "commit T", ejecuta Redo(T). Š Si Ci responde que "precommit T", graba el registro en su bitácora y envía un mensaje "acknowledge T" al Ci. Š Si Ci no responde se ejecuta el protocolo de fallo del Ci. Elementos de Bases de Datos Clase 23

22

C3F - Fallo del Coordinador

Š Si un participante, por cualquier motivo no

recibe respuesta del coordinador, dispara el protocolo de fallo de coordinador. Š El resultado será la selección de un nuevo coordinador. Š Cuando el coordinador fallado se recupera, seguirá actuando como participante, acatando las decisiones del nuevo coordinador.

1. Los sitios participantes activos seleccionan un nuevo coordinador. 2. El nuevo coordinador Cnew envía un mensaje a cada sitio participante requiriendo el estado local de T. 3. Cada sitio participante (incluyendo Cnew) determina el estado local de T (cometida, abortada, lista, precometida, no lista). 4. Dependiendo de las respuestas recibidas, Cnew decide si cometerá o abortará T. Esta secuencia de pasos se conoce como Protocolo de Fallo del Coordinador.

Elementos de Bases de Datos Clase 23

23

Elementos de Bases de Datos Clase 23

24

4

Universidad Nacional del Sur – Departamento de Ciencias e Ingeniería de la Computación Elementos de Bases de Datos – 2do. Cuatrimestre de 2004

C3F - Estado de T ¿Cómo detectar el estado de T en cada sitio? Š Cometida: la bitácora contiene un registro . Š Abortada: la bitácora contiene un registro . Š Lista: la bitácora contiene un pero no contiene un ni un . Š Precometida: la bitácora contiene un registro pero no contiene un registro ni un registro . Š No Lista: la bitácora no contiene un ni un . Elementos de Bases de Datos Clase 23

Elementos de Bases de Datos Clase 23

26

C3F - La decisión de Cnew

Š ¿Qué pasa si ningún sitio activo recibió el mensaje de pre-

Š El nuevo coordinador Cnew puede llegar a conocer el

estado del coordinador fallado Ci. Š Si un sitio activo tiene un en su bitácora, entonces Ci tiene que haber decidido cometer T. Š Si un sitio activo tiene un en su bitácora, entonces Ci alcanzó un estado de precompromiso, lo que implica que todos los sitios alcanzaron el estado de listos. Š A diferencia del PC de 2 Fases, Cnew no comete T unilateralmente ya que puede producir un bloqueo si Cnew falla. 27

compromiso de Ci?

Ci ha decidido cometer antes de fallar. Ci ha decidio abortar antes de fallar. „ Ci no ha decidido sobre la suerte de T. „ „

Š La primera alternativa no es posible y, por lo tanto, veremos que es seguro abortar.

Š Si Ci decidió cometer, entonces al menos k sitios decidieron precometer T y enviaron un reconocimiento (acknowledge) a Ci.

Š Por lo tanto, existen al menos k sitios activos y al menos uno de

ellos debe informar a Cnew que recibió un mensaje de precompromiso. Š Si ningun sitio activo recibió un mensaje de pre-compromiso, no es posible que Ci haya decidido cometer. Elementos de Bases de Datos Clase 23

28

PC de 2 Fases vs. PC de 3 Fases

Comparando C2F y C3F Š Ambos protocolos buscan satisfacer el principio de atomicidad:

una transacción se ejecuta en su totalidad o no se ejecuta por completo. Š Ambos asumen ciertas condiciones en la red: que no se pierden mensajes y que los mensajes llegan en el mismo orden en que fueron enviados. Š El PC de 3 Fases exige condiciones adicionales como por ejemplo, que la red no pueda particionarse en dos o más grupos que no se pueden comunicar entre si. Š El Protocolo de Compromiso de 2 Fases puede dejar bloqueada a una transacción, ya que el destino de una transacción no se conoce hasta que el sitio fallado (coordinador) no se recupera. Š El Protocolo de Compromiso de 3 Fases evita situaciones de bloqueo pero requiere un mayor tráfico de mensajes. Elementos de Bases de Datos Clase 23

¿Qué decide hacer el nuevo coordinador Cnew? Š Si al menos un sitio tiene el estado cometido, entonces Cnew decide cometer T. Š Si al menos un sitio tiene el estado abortado, entonces Cnew decide abortar T. Š Si ningún sitio está cometido o abortado pero existe al menos un sitio en estado precometido, Cnew reanuda el protocolo enviando un nuevo mensaje de precompromiso. Š En otro caso, Cnew aborta T.

25

C3F - La decisión de Cnew

Elementos de Bases de Datos Clase 23

C3F - La decisión de Cnew

29

Š Intuitivamente, el PC de 2 Fases permite que un

participante cometa T ni bien descubre que los participantes votaron . Š En cambio, en el PC de 3 Fases un participante comete T no sólo cuando sabe que los participantes han votado , sino también cuando conozca que todos los participantes saben eso (si alguno falla, lo deberá saber cuando se recupere). Š Más allá de eso, el PC de 2 Fases es más comúnmente usado a pesar de sus bloqueos potenciales ya que la probabilidad de que éstos ocurran es suficientemente baja con respecto al costo extra que insume la tercera fase en el PC de 3 Fases. Elementos de Bases de Datos Clase 23

30

5

Universidad Nacional del Sur – Departamento de Ciencias e Ingeniería de la Computación Elementos de Bases de Datos – 2do. Cuatrimestre de 2004

Equivalencias de Mensajes Semejanzas de mensajes en Protocolos de Compromiso: Š Principles of Database and Knowledge-Base Systems. Jeffrey D. Ullman. Š Database System Concept. Abraham Silberschatz, Henry F. Korth, S. Sudarshan.

Ullman

Silberschatz

begin-vote vote-commit vote-abort abort commit help-me prepare-commit

"prepare T" "ready T" "no T" "abort T" "commit T"

Estampillas de Tiempo ŠEn un sistema distribuido, cada transacción debe tener una estampilla de tiempo única para usar en la decisión del orden de serializabilidad. ŠGeneración de estampillas únicas: –

–

Modelo Centralizado: un único sitio es encargado de generar y distribuir las estampillas de tiempo. Modelo Distribuido: cada transacción tiene una estampilla de tiempo que surge de concatenar la estampilla de tiempo local con el identificador de sitio.

"precommit T"

Elementos de Bases de Datos Clase 23

31

Estampillas de Tiempo ŠEl problema del modelo distribuido es que un sitio podría generar estampillas de tiempo a mayor velocidad que otros sitios. ŠEn ese caso, las estampillas de tiempo generadas por el sitio más rápido serán mayores que las generadas por otros sitios. ŠEsto se evita si cada sitio utiliza un reloj lógico, implementado mediante un contador que se incrementa cada vez que se genera una nueva estampilla de tiempo local. ŠPara sincronizar los relojes lógicos, se requiere que cada sitio Si avance su reloj lógico cuando arriba una nueva transacción a ese sitio. Elementos de Bases de Datos Clase 23

Elementos de Bases de Datos Clase 23

Tratamiento de Deadlocks ŠAl igual que en los sistemas centralizados, tenemos dos formas de tratar deadlocks: „ Prevención. „ Detección y Recuperación. ŠUna simple técnica de prevención usando la estrategia write-locks-all es la siguiente:

Asumimos un ordenamiento lexicográfico de los items de datos. „ Si A id(T2) por lo que S1 no envía un mensaje de detección de deadlocks a S2. • S2 detecta (simultáneamente con el posible deadlock S1) Tex→T3→T4→T2→Tex. • Aquí sucede que id(T2) < id(T3) por lo que S2 si envía un mensaje de detección de deadlocks a S1. • De este modo, se evitan envíos de mensajes innecesarios.

Elementos de Bases de Datos Clase 23

47

Temas de la clase de hoy Š Protocolos de compromiso „

Protocolo de Compromiso de 3 Fases.

Š Protocolos de estampilla de tiempo. Š Tratamiento de deadlock en entorno distribuido Š Bibliografía „

„

“Principles of Database and Knowledge Base System” - J. Ullman. Capítulo 10. “Fundamentos de Bases de Datos” – A. Silberschatz. Capítulo 18.

Elementos de Bases de Datos Clase 23

48

8