Un quórum es el número mínimo de votos que debe obtener una transacción distribuida para poder realizar una operación en un sistema distribuido . Se implementa una técnica basada en quórum para imponer un funcionamiento coherente en un sistema distribuido.
Técnicas basadas en quórum en sistemas de bases de datos distribuidas
La votación basada en quórum se puede utilizar como método de control de réplicas , [1] así como un método de confirmación para asegurar la atomicidad de la transacción en presencia de particiones de red . [1]
Votación basada en quórum en protocolos de compromiso
En un sistema de base de datos distribuida, una transacción podría ejecutar sus operaciones en varios sitios. Dado que la atomicidad requiere que cada transacción distribuida sea atómica, la transacción debe tener el mismo destino ( confirmar o abortar ) en todos los sitios. En el caso de la partición de la red, los sitios están particionados y es posible que las particiones no puedan comunicarse entre sí. Aquí es donde entra en juego una técnica basada en quórum. La idea fundamental es que una transacción se ejecuta si la mayoría de los sitios votan para ejecutarla.
A cada sitio del sistema se le asigna un voto V i . Supongamos que el número total de votos en el sistema es V y los quórumes de aborto y compromiso son V a y V c , respectivamente. Entonces se deben obedecer las siguientes reglas en la implementación del protocolo de confirmación:
- V a + V c > V, donde 0
c , V a V. - Antes de que una transacción se confirme, debe obtener un quórum de compromiso V c .
El total de al menos un sitio que está preparado para comprometerse y cero o más sitios en esperaV c . [2] - Antes de que una transacción se anule, debe obtener un quórum de anulación V a
El total de cero o más sitios que están preparados para abortar o cualquier sitio en esperaV a .
La primera regla asegura que una transacción no se pueda confirmar y abortar al mismo tiempo. Las siguientes dos reglas indican los votos que debe obtener una transacción antes de que pueda terminar de una forma u otra.
Votación basada en quórum para el control de réplicas
En las bases de datos replicadas, un objeto de datos tiene copias presentes en varios sitios. Para garantizar la serialización , no se debe permitir que dos transacciones lean o escriban un elemento de datos al mismo tiempo. En el caso de bases de datos replicadas, se puede utilizar un protocolo de control de réplicas basado en quórum para garantizar que dos transacciones no lean o escriban dos copias de un elemento de datos al mismo tiempo.
La votación basada en quórum para el control de réplicas se debe a [Gifford, 1979]. [3] A cada copia de un elemento de datos replicado se le asigna un voto. Luego, cada operación tiene que obtener un quórum de lectura (V r ) o un quórum de escritura (V w ) para leer o escribir un elemento de datos, respectivamente. Si un dato dado tiene un total de V votos, los quórumes deben obedecer las siguientes reglas:
- V r + V w > V
- V w > V / 2
La primera regla asegura que un elemento de datos no sea leído y escrito por dos transacciones al mismo tiempo. Además, garantiza que un quórum de lectura contenga al menos un sitio con la versión más reciente del elemento de datos. La segunda regla asegura que dos operaciones de escritura de dos transacciones no puedan ocurrir simultáneamente en el mismo elemento de datos. Las dos reglas garantizan que se mantenga la serialización de una copia.
Ver también
Referencias
- ^ a b Ozsu, Tamer M; Valduriez, Patrick (1991). "12". Principios de los sistemas de bases de datos distribuidos (2ª ed.). Upper Saddle River, Nueva Jersey: Prentice-Hall, Inc. ISBN 978-0-13-691643-7.
- ^ Skeen, Dale. "Un protocolo de compromiso basado en quórum" (PDF) . Biblioteca ECommons de la Universidad de Cornell . Consultado el 10 de febrero de 2013 .
- ^ Gifford, David K. (1979). Votación ponderada para datos replicados . SOSP '79: Actas del séptimo simposio de ACM sobre principios de sistemas operativos. Pacific Grove, California, Estados Unidos: ACM. págs. 150-162. doi : 10.1145 / 800215.806583 .