En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos




descargar 0.75 Mb.
títuloEn años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos
página36/36
fecha de publicación02.02.2016
tamaño0.75 Mb.
tipoDocumentos
b.se-todo.com > Economía > Documentos
1   ...   28   29   30   31   32   33   34   35   36

7.4 Protocolos distribuidos



Como con los protocolos de recuperación local, las versiones distribuidas ayudan a mantener la atomicidad y durabilidad de las transacciones. La ejecución de los comandos begin_transaction, read y write no provoca ningún cambio significativo. Sin embargo, la ejecución de las operaciones commit, abort y recover requieren del desarrollo de un protocolo especial para cada una de ellas en el cual participan todos los nodos de la red que intervienen en una transacción. De manera breve, a continuación se presentan algunos problemas que aparecen en sistemas distribuidos y que no se presentan en sistemas centralizados.
¿Cómo ejecutar un comando commit para transacciones distribuidas? ¿Cómo asegurar la atomicidad y durabilidad de las transacciones distribuidas?
Si ocurre una falla, ¿cómo pueden, los nodos que permanecen funcionando, seguir operando normalmente? Idealmente, la ocurrencia de la falla en un nodo no debe forzar a los otros nodos a tener que esperar a que se repare la falla en el nodo para terminar una transacción. A esta propiedad se le conoce como no-bloqueante.
De manera similar, cuando ocurre una falla ¿cómo terminar una transacción que se estaba ejecutando al momento de la falla? Idealmente un nodo con falla debería poder terminar una transacción sin tener que consultar a los otros nodos. Esta es una propiedad de independencia del nodo con falla con respecto a los nodos sin falla. Una recuperación independiente supone que existe una estrategia no-bloqueante en el manejo de fallas.
Para facilitar la descripción de los protocolos de confiabilidad distribuida se supondrá que en el nodo que se origina una transacción hay un proceso, llamado el coordinador, que ejecuta las operaciones de la transacción. El coordinador se comunica con procesos participantes en los otros nodos los cuales lo ayudan en las operaciones de la transacción.

7.4.1 Compromisos de dos fases



El compromiso de dos fases (two-phase commit) es un protocolo muy simple y elegante que asegura la atomicidad de las transacciones distribuidas. Extiende los efectos de una operación local de commit a transacciones distribuidas poniendo de acuerdo a todos los nodos involucrados en la ejecución de una transacción antes de que los cambios hechas por la transacción sean permanentes.
Las fases del protocolo son las siguientes:


  • Fase 1: el coordinador hace que todos los participantes estén listos para escribir los resultados en la base de datos.

  • Fase 2: Todos escriben los resultados en la base de datos.


La terminación de una transacción se hace mediante la regla del compromiso global:


  1. El coordinador aborta una transacción si y solamente si al menos un participante vota por que se aborte.

  2. El coordinador hace un commit de la transacción si y solo si todos los participantes votan por que se haga el commit.


La operación del compromiso de dos fases entre un coordinador y un participante en ausencia de fallas se presenta en la Figura 7.9, en donde los círculos indican los estados y las líneas entrecortadas indican mensajes entre el coordinador y los participantes. Las etiquetas en las líneas entrecortadas especifican la naturaleza del mensaje.
En la Figura 7.10 se presentan las dos fases de comunicación para realizar un commit en sistemas distribuidos. El esquema presentado en la figura se conoce como centralizado ya que la comunicación es solo entre el coordinador y los participantes; los participantes no se comunican entre ellos.


Figura 7.9. Acciones del compromiso de dos fases.
Otra alternativa es una comunicación lineal, en donde los participantes se pueden comunicar unos con otros. Existe un ordenamiento entre los nodos del sistema. La estructura se presenta en la Figura 7.11. Un participante, P, recibe un mensaje vote-abort o vote-commit de otro participante, Q. Si P no está listo para hacer un commit, envía un vote-abort al siguiente participante, R, y la transacción se aborta en este punto. Si P el participante está de acuerdo en hacer un commit, envía un vote-commit a R y entra al estado de LISTO. Este proceso continúa hasta el último participante poniendo fin a la primera fase. En la segunda fase, si el último participante está de acuerdo en hacer un commit envía un global-commit al participante anterior. En caso contrario, envía un global-abort. Así en la segunda fase, P recibe un mensaje de R informándole si se hace un global-commit o un global-abort. Este mensaje se propaga a Q y así hasta alcanzar al coordinador.


Figura 7.10. Estructura centralizada de comunicaciones para el compromiso de dos fases.



Figura 7.11. Estructura lineal de comunicaciones para el compromiso de dos fases.
Otra estructura de comunicación usual para implementar los compromisos de dos fases involucra la comunicación entre todos los participantes durante la primera fase del protocolo de manera que todos ellos alcanzan su punto de terminación en forma independiente. Esta versión, llamada la estructura distribuida, no requiere la segunda fase. En la Figura 7.12 se presenta la estructura distribuida en la cual el coordinador envía el mensaje de preparación a todos los participantes. Cada participante, entonces, envía su decisión a todos los otros participantes y al coordinador indicándola como un vote-commit o vote-abort. Cada participante espera los mensajes de todos los otros participantes y toma su decisión de acuerdo a la regla de compromiso global.


Figura 7.12. Estructura distribuida de comunicaciones para el compromiso de dos fases.
Independientemente de la forma en que se implemente el compromiso de dos fases, éste puede ser modelado por medio de un diagrama de transición de estados. En la Figura 7.13 se presentan los diagramas de transición para el coordinador y los participantes.


Figura 7.13. Diagrama de transición de estados para el compromiso de dos fases del coordinador y de un participante.

7.4.2 Fallas de nodos



En esta sección se considera cuando un nodo falla en la red. El objetivo es desarrollar un protocolo de terminación no-bloqueante que permita desarrollar protocolos de recuperación independiente. En una red puede haber muchas fallas de comunicación debido a colisiones, comunicación intermitente por interferencia, sobrecarga de trabajo, etc. La única forma de suponer que existe una falla de nodo es cuando después de un cierto periodo de tiempo (timeout) no se obtiene respuesta del mismo. Así, la discusión de los protocolos de terminación y recuperación considera el caso en que las fallas de nodo se manifiestan por ausencia de comunicación con éste durante intervalos de tiempo.

Protocolos de terminación



Las fallas de nodo se pueden manifestar tanto en el coordinador como en los participantes.


  • Timeouts del coordinador




  1. Timeout en el estado WAIT. El coordinador está esperando por las decisiones locales de los participantes. El coordinador no puede de manera unilateral realizar un commit. Sin embargo, él puede decidir abortar globalmente la transacción. En este caso, escribe un comando abort en el registro de la base de datos y envía un mensaje global-abort a todos los participantes.

  2. Timeout en los estados COMMIT o ABORT. En este caso el coordinador no esta seguro que los procedimientos de commit o abort se han terminado por los administradores de recuperación local en todos los nodos participantes. Así, el coordinador envía mensajes global-commit o global-abort de manera repetida a todos los nodos que no han respondido y espera por su reconocimiento.




  • Timeouts de los participantes




  1. Timeout en el estado INITIAL. En este estado el participante está esperando por un mensaje prepare. El coordinador pudo haber fallado en el estado INITIAL por lo que el participante puede abortar de manera unilateral la transacción. Si el mensaje prepare llega en un tiempo posterior al participante, esto se puede manejar de dos formas. Puede responder con un vote-abort o simplemente ignorar el mensaje y dejar que ocurra el timeout en el lado del coordinador.

  2. Timeout en el estado READY. En este estado el participante ha votado por realizar un commit pero desconoce la decisión global del coordinador. No se puede de manera unilateral ni hacer un commit ni hacer un abort. Así permanecerá bloqueado hasta que pueda conocer de alguien, el coordinador u otro participante, cual fue la decisión final sobre la transacción.


Protocolos de recuperación
En la parte anterior se discutió como implementar los compromisos de dos fases cuando se presentan fallas en nodos pero desde la perspectiva de los nodos que se mantienen trabajando. En esta parte, se examinará el otro punto de vista, esto es, como un coordinador o participante se pueden recuperar cuando sus nodos fallas y tienen que reiniciar su trabajo.


  • Fallas del coordinador




  1. El coordinador falla en el estado INITIAL. Esto es antes de que el coordinador ha iniciado el procedimiento para hacer un commit. Por lo tanto, cuando el coordinador reinicia tiene que empezar el proceso para hacer el commit.

  2. El coordinador falla en el estado de WAIT. En este caso el coordinador ha enviado el comando prepare y después falla. Para recuperarse de una falla, tendrá que reiniciar el proceso de commit para la transacción desde el envío nuevamente del mensaje prepare.

  3. El coordinador falla en los estados COMMIT o ABORT. En este caso el coordinador ha tomado una decisión y la ha informado a los participantes. Así, si todos los reconocimientos se han recibido cuando se trata de recuperar, entonces no se hace nada. De otra manera, se invoca al protocolo de terminación.




  • Fallas de los participantes




  1. Un participante falla en el estado INICIAL. En este caso se aborta la transacción de manera unilateral cuando se trata de recuperar. Lo anterior es aceptable ya que el coordinador de la transacción debe estar en el estado INITIAL o WAIT. Si está en el primero, enviará un mensaje prepare y pasará al estado de WAIT en donde no recibirá respuesta del participante que ha fallado y eventualmente abortará globalmente la transacción.

  2. Un participante falla en el estado READY. En este caso el participante ha informado su decisión al coordinador. Cuando se recupere, el participante en el nodo fallido puede tratar esto como un timeout en el estado de READY y manejar la transacción incompleta sobre su protocolo de terminación.

  3. Un participante falla en el estado ABORT o COMMIT. Esos estados representan las condiciones de terminación, de manera que, cuando se recupere, el participante no necesita tomar acciones especiales.


Casos adicionales
Consideremos ahora los casos cuando se relajan las condiciones de atomicidad del registro y las acciones del envío de mensajes. En particular, se supone que una falla de nodo puede ocurrir después de que el coordinador o un participante ha escrito información en el registro de la base de datos pero puede enviar un mensaje. Para esta discusión es útil consultar la Figura 7.8.


  1. El coordinador falla después que un begin_commit ha sido escrito en el registro pero antes de que se envíe el mensaje prepare. El coordinador puede considerar esto como una falla en el estado WAIT y enviar el comando prepare cuando se recupera.

  2. Un particiapante falla después de escribir un comando ready en el registro pero antes de enviar un mensaje vote-commit. El participante ve a este caso como una falla en el estado de WAIT y procede conforme lo discutido antes.

  3. Un particiapante falla después de escribir un comando ready en el registro pero antes de enviar un mensaje vote-abort. El participante no tiene que hacer nada cuando se recupere. El coordinador está en el estado de WAIT y no obtendrá respuesta del participante fallido lo que llevará a invocar el protocolo de terminación en donde se abortará de forma global la transacción.

  4. El coordinador falla después de registrar su decisión final (abort o commit) en el registro de la base de datos pero antes de enviar su mensaje global-abort o global-commit a los participantes. El coordinador trata a éste como el caso 3, mientras que los participantes lo tratan con un timeout en el estado de READY.


Un participante falla después de registrar un abort o commit pero antes de enviar un mensaje de reconocimiento al coordinador. El participante trata a éste como en el caso 3, mientras que el coordinar lo maneja como un timeout en el estado COMMIT o ABORT.


REFERENCIAS
[Ozsu 98] Öszu, Tamar and Valduriez, P. Principles of Distributed Database Systems 2nd Ed. Prentice Hall, 1998. Libro de texto.
[Bell 92] Bell, D. A. and Grimson, J. B. Distributed Database Systems. Addisson-Wesley, 1992.
[Ceri 84] Ceri, S. and Pelagatti, G. Distributed Databes - Principles and Systems. McGraw Hill, 1984.
[DeWitt 92] DeWitt, D. and Gray, J. "Parallel Database Systems: The Future of High-Performance Database Systems," Communications of the ACM, June 1992, 35(6).

[Elmagarmid 90] Elmagarmid, A. K. and Pu, C. (guest eds.) ACM Computing Surveys. Special issue on heterogeneous databases, September 1990, 22(3).
[Grey 93] Gray, J. and Reuter, A. Transaction Processing -Concepts and Techniques. Morgan Kaufmann, 1993.
[Jarke 84] Jarke, M. and Koch, J. "Query optimization in database systems," ACM Computing Surveys, June 1984, 16(2): 227-269.
[Ozsu 91] Öszu, Tamar and Valduriez, P. "Distributed Database Systems: where are we now?", IEEE Computer, August 1991, 24(8).
[Ozsu 94] Öszu, Tamar and Valduriez, P. "Distributed Database Systems: unsolved problems and new issues," In Readings in Distributed Computing Systems, T. L. Casavant and M. Singhal eds. IEEE Press, 1994.
[Ram 91] Ram, S. (guest editor). IEEE Computer. Special issue on heterogeneous distributed database systems, December 1991, 24(12).



Ing. Pedro Tamayo Gomez Página de

1   ...   28   29   30   31   32   33   34   35   36

similar:

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconBases de datos de secuencias de adn y proteínas

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconUna red de comunicaciones es la combinación de hardware, software...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconResumen a lo largo de los años, la agricultura se ha mantenido como...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconResumen El presente trabajo de investigación bibliográfica trata...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconCientífico británico que sentó las bases de la moderna teoría evolutiva,...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconRecibimos de las distintas sucursales de la empresa los datos correspondientes a las ventas en

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconEntre las herramientas utilizadas en la minería de datos (Data Mining)...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconMinería de Datos aplicados a las ventas con Tarjeta de Crédito realizados...

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconBases moleculares de las acciones de la insulina

En años recientes, la disponibilidad de las bases de datos y de las redes de computadoras ha promovido el desarrollo de un nuevo campo denominado bases de datos iconBases moleculares de las acciones de la insulina




Todos los derechos reservados. Copyright © 2015
contactos
b.se-todo.com