Control de concurrencia basado en marcas de tiempo

En informática , un algoritmo de control de concurrencia basado en marcas de tiempo es un método de control de concurrencia optimista . Se utiliza en algunas bases de datos para gestionar de forma segura las transacciones mediante marcas de tiempo .

Operación

Supuestos

• Cada valor de marca de tiempo es único y representa con precisión un instante en el tiempo.
• Una marca de tiempo de mayor valor aparece más tarde en el tiempo que una marca de tiempo de menor valor.

Generando una marca de tiempo

Existen varios enfoques diferentes que pueden generar marcas de tiempo.

• Utilizando el valor del reloj del sistema al inicio de una transacción como marca de tiempo.
• Utilizando un contador compartido seguro para subprocesos que se incrementa al inicio de una transacción como marca de tiempo.
• Una combinación de los dos métodos anteriores.

Definición formal

Cada transacción ( ) es una lista ordenada de acciones ( ). Antes de que la transacción realice su primera acción ( ), se marca con la marca de tiempo actual , o cualquier otra secuencia estrictamente totalmente ordenada : . A cada transacción también se le asigna un conjunto inicialmente vacío de transacciones de las que depende, , y un conjunto inicialmente vacío de objetos antiguos que actualizó, . ${\displaystyle T_{i}}$ ${\displaystyle A_{ix}}$ ${\displaystyle A_{i1}}$ ${\displaystyle TS(T_{i})=NOW()}$ ${\displaystyle DEP(T_{i})=[]}$ ${\displaystyle OLD(T_{i})=[]}$

A cada objeto de la base de datos se le asignan dos campos de marca de tiempo que no se utilizan excepto para el control de concurrencia: ${\displaystyle (O_{j})}$

• ${\displaystyle RT(O_{j})}$es la marca de tiempo de la última transacción que leyó el valor del objeto ( , donde es la última transacción que leyó el valor del objeto). ${\displaystyle TS(T_{r})}$ ${\displaystyle T_{r}}$
• ${\displaystyle WT(O_{j})}$es la marca de tiempo de la última transacción que actualizó el valor del objeto ( , donde es la última transacción que actualizó el valor del objeto). ${\displaystyle TS(T_{w})}$ ${\displaystyle T_{w}}$

Para todos : ${\displaystyle T_{i}}$

Para cada acción : ${\displaystyle A_{ix}}$

Si desea leer el valor de : ${\displaystyle A_{ix}}$ ${\displaystyle O_{j}}$

Si luego se cancela (un hilo más reciente ha sobrescrito el valor), ${\displaystyle WT(O_{j})>TS(T_{i})}$

De lo contrario, actualice el conjunto de dependencias y establezca ; ${\displaystyle DEP(T_{i}).\mathrm {add} (WT(O_{j}))}$ ${\displaystyle RT(O_{j})=\max(RT(O_{j}),TS(T_{i}))}$

Si desea actualizar el valor de : ${\displaystyle A_{ix}}$ ${\displaystyle O_{j}}$

Si luego se aborta (un hilo más reciente ya depende del valor anterior), ${\displaystyle RT(O_{j})>TS(T_{i})}$

Si entonces se omite (la regla de escritura de Thomas ), ${\displaystyle WT(O_{j})>TS(T_{i})}$

De lo contrario, almacene los valores anteriores , establezca y actualice el valor de . ${\displaystyle OLD(T_{i}).\mathrm {add} (O_{j},WT(O_{j}))}$ ${\displaystyle WT(O_{j})=TS(T_{i})}$ ${\displaystyle O_{j}}$

Mientras haya una transacción que no haya finalizado: esperar ${\displaystyle DEP(T_{i})}$

Si hay una transacción que se abortó, entonces abortar ${\displaystyle DEP(T_{i})}$

De lo contrario: confirmar .

Para abortar :

Para cada uno en ${\displaystyle (\mathrm {old} O_{j},\mathrm {old} WT(O_{j}))}$ ${\displaystyle OLD(T_{i})}$

Si es igual entonces restaura y ${\displaystyle WT(O_{j})}$ ${\displaystyle TS(T_{i})}$ ${\displaystyle O_{j}=\mathrm {old} O_{j}}$ ${\displaystyle WT(O_{j})=\mathrm {old} WT(O_{j})}$

Definición informal

Cada vez que se inicia una transacción, recibe una marca de tiempo. La marca de tiempo de la transacción indica cuándo se inició la transacción. Estas marcas de tiempo garantizan que las transacciones afecten a cada objeto en la misma secuencia de sus respectivas marcas de tiempo. Por lo tanto, dadas dos operaciones que afectan al mismo objeto desde diferentes transacciones, la operación de la transacción con la marca de tiempo anterior debe ejecutarse antes de la operación de la transacción con la marca de tiempo posterior. Sin embargo, si la operación de la transacción incorrecta se presenta primero, entonces se cancela y la transacción debe reiniciarse.

Cada objeto en la base de datos tiene una marca de tiempo de lectura , que se actualiza cada vez que se leen los datos del objeto, y una marca de tiempo de escritura , que se actualiza cada vez que se modifican los datos del objeto.

Si una transacción desea leer un objeto,

• pero la transacción se inició antes de la marca de tiempo de escritura del objeto, significa que algo cambió los datos del objeto después de que se inició la transacción. En este caso, la transacción se cancela y debe reiniciarse.
• y la transacción se inició después de la marca de tiempo de escritura del objeto, significa que es seguro leer el objeto. En este caso, si la marca de tiempo de la transacción es posterior a la marca de tiempo de lectura del objeto, la marca de tiempo de lectura se establece en la marca de tiempo de la transacción.

Si una transacción desea escribir en un objeto,

• pero la transacción se inició antes de la marca de tiempo de lectura del objeto, lo que significa que algo ha echado un vistazo al objeto y suponemos que ha hecho una copia de los datos del objeto. Por lo tanto, no podemos escribir en el objeto, ya que eso invalidaría cualquier dato copiado, por lo que la transacción se cancela y debe reiniciarse.
• y la transacción se inició antes de la marca de tiempo de escritura del objeto, significa que algo ha cambiado en el objeto desde que comenzamos nuestra transacción. En este caso, usamos la regla de escritura de Thomas y simplemente omitimos nuestra operación de escritura y continuamos de manera normal; no es necesario abortar ni reiniciar la transacción
• de lo contrario, la transacción escribe en el objeto y la marca de tiempo de escritura del objeto se establece en la marca de tiempo de la transacción.

Físicamente irrealizable

El comportamiento es físicamente irrealizable si los resultados de las transacciones no podrían haberse producido si las transacciones fueran instantáneas. Las siguientes son las únicas dos situaciones que dan lugar a un comportamiento físicamente irrealizable:

1. La transacción T intenta leer X pero TS(T) < WT(X). Motivo: significa que otra transacción escribió en X después de que T comenzara.
2. La transacción T intenta escribir X pero TS(T) < RT(X). Razón: significa que una transacción posterior leyó X antes de que T lo escribiera.

Recuperabilidad

Tenga en cuenta que el orden de las marcas de tiempo en su forma básica no produce historiales recuperables. Considere, por ejemplo, el siguiente historial con transacciones y : ${\displaystyle T_{1}}$ ${\displaystyle T_{2}}$

${\displaystyle W_{1}(x)\;R_{2}(x)\;W_{2}(y)\;C_{2}\;R_{1}(z)\;C_{1}}$

Esto podría ser producido por un programador TO, pero no es recuperable, ya que se confirma incluso después de haber leído de una transacción no confirmada. Para asegurarse de que produce historiales recuperables, un programador puede mantener una lista de otras transacciones de las que cada transacción ha leído , y no permitir que una transacción se confirme antes de que esta lista consista solo en transacciones confirmadas. Para evitar abortos en cascada, el programador podría etiquetar los datos escritos por transacciones no confirmadas como sucios , y nunca permitir que una operación de lectura comience en ese elemento de datos antes de que se desetiquetara. Para obtener un historial estricto, el programador no debe permitir ninguna operación en elementos sucios. ${\displaystyle T_{2}}$

Problemas de implementación

Resolución de la marca de tiempo

Este es el tiempo mínimo transcurrido entre dos marcas de tiempo adyacentes. Si la resolución de la marca de tiempo es demasiado grande (aproximada), aumenta la posibilidad de que dos o más marcas de tiempo sean iguales y, por lo tanto, se permite que algunas transacciones se confirmen en un orden incorrecto. Por ejemplo, para un sistema que crea cien marcas de tiempo únicas por segundo, es posible que a dos eventos que ocurren con una diferencia de 2 milisegundos se les asigne la misma marca de tiempo aunque hayan ocurrido en momentos diferentes.

Bloqueo de marca de tiempo

Si bien esta técnica no implica bloqueo, en la medida en que el objeto no está bloqueado para el acceso simultáneo durante la duración de una transacción, el acto de registrar cada marca de tiempo contra el Objeto requiere un bloqueo de duración extremadamente corta en el Objeto o su proxy.

Véase también

• Control de concurrencia de múltiples versiones
• Sellado de tiempo (informática)