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 manejar de forma segura transacciones utilizando marcas de tiempo .

Operación

Suposiciones

• 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 ocurre más tarde que una marca de tiempo de menor valor.

Generando una marca de tiempo

Varios enfoques diferentes pueden generar marcas de tiempo

• Usar el valor del reloj del sistema al inicio de una transacción como marca de tiempo.
• Usar 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.

Definicion 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 ordenada y totalmente : . Cada transacción también recibe 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 más que 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 está 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 está 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 cancela (un hilo más reciente ya se basa en el valor anterior), ${\displaystyle RT(O_{j})>TS(T_{i})}$

Si luego 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: espera ${\displaystyle DEP(T_{i})}$

Si hay una transacción en la que se canceló, entonces se cancela. ${\displaystyle DEP(T_{i})}$

De lo contrario: comprometerse .

Abortar :​

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

Si es igual entonces restaurar 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 que la operación de la transacción con la marca de tiempo posterior. Sin embargo, si primero se presenta la operación de la transacción incorrecta, se cancela y se debe reiniciar la transacción.

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 cambian los datos del objeto.

Si una transacción quiere leer un objeto,

• pero la transacción comenzó antes de la marca de tiempo de escritura del objeto, significa que algo cambió los datos del objeto después de que comenzó la transacción. En este caso, la transacción se cancela y debe reiniciarse.
• y la transacción comenzó 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 quiere escribir en un objeto,

• pero la transacción comenzó antes de la marca de tiempo de lectura del objeto, significa que algo ha echado un vistazo al objeto y asumimos que tomó una copia de los datos del objeto. Por lo tanto, no podemos escribir en el objeto, ya que eso invalidaría los datos copiados, por lo que la transacción se cancela y se debe reiniciar.
• y la transacción comenzó antes de la marca de tiempo de escritura del objeto, significa que algo ha cambiado 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 normalmente; la transacción no tiene que ser cancelada o reiniciada
• 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.

Fisicamente irrealizable

El comportamiento es físicamente irrealizable si los resultados de las transacciones no hubieran podido ocurrir si las transacciones hubieran sido instantáneas. Las siguientes son las dos únicas situaciones que resultan en un comportamiento físicamente irrealizable:

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

Recuperabilidad

Tenga en cuenta que el pedido de 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 aunque se haya 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 únicamente 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 comience una operación de lectura en dicho elemento de datos antes de que se desetiquete. Para obtener un historial estricto, el programador no debe permitir ninguna operación con elementos sucios. ${\displaystyle T_{2}}$

Problemas de implementación

Resolución de 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 (gruesa), aumenta la posibilidad de que dos o más marcas de tiempo sean iguales y, por lo tanto, permite que algunas transacciones se confirmen en un orden incorrecto. Por ejemplo, para un sistema que crea cien marcas de tiempo únicas por segundo, dos eventos que ocurren con 2 milisegundos de diferencia pueden recibir la misma marca de tiempo aunque hayan ocurrido en momentos diferentes.

Bloqueo de marca de tiempo

Aunque esta técnica no es de 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 apoderado.

Ver también

• Control de concurrencia multiversión
• Sellado de tiempo (informática)