Control de concurrencia basado en marcas de tiempo

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

Existen varios métodos diferentes para generar marcas de tiempo.

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

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

Cada objeto${\displaystyle (O_{j})}$En la base de datos se proporcionan dos campos de marca de tiempo que no se utilizan para nada más que para el control de concurrencia:

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

A pesar de${\displaystyle T_{i}}$:

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

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

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

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

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

Si${\displaystyle RT(O_{j})>TS(T_{i})}$entonces abortar (un hilo más reciente ya está dependiendo del valor anterior),

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

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

Si bien hay una transacción en${\displaystyle DEP(T_{i})}$Eso no ha terminado: espera

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

De lo contrario: confirmar .

Para abortar :

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

Si${\displaystyle WT(O_{j})}$igual${\displaystyle TS(T_{i})}$luego restaurar${\displaystyle O_{j}=\mathrm {antiguo} O_{j}}$y${\displaystyle WT(O_{j})=\mathrm {old} WT(O_{j})}$

Cada vez que se inicia una transacción, se le asigna una marca de tiempo. Esta marca indica cuándo se inició la transacción. Estas marcas de tiempo garantizan que las transacciones afecten a cada objeto en el orden en que aparecen sus respectivas marcas de tiempo. Por lo tanto, si dos operaciones de transacciones diferentes afectan al mismo objeto, la operación de la transacción con la marca de tiempo más antigua debe ejecutarse antes que la operación de la transacción con la marca de tiempo más reciente. Sin embargo, si la operación de la transacción incorrecta se ejecuta primero, 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 quiere leer un objeto,

• Pero si la transacción se inició antes de la marca de tiempo de escritura del objeto, significa que algo modificó los datos del objeto después de que se iniciara la transacción. En este caso, la transacción se cancela y debe reiniciarse.
• Si la transacción se inició después de la marca de tiempo de escritura del objeto, significa que es seguro leerlo. 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 a la marca de tiempo de la transacción.

Si una transacción quiere escribir en un objeto,

• Pero como la transacción se inició antes de la marca de tiempo de lectura del objeto, significa que alguien ha accedido a él y suponemos que ha copiado sus datos. Por lo tanto, no podemos escribir en el objeto, ya que eso invalidaría cualquier dato copiado; así que la transacción se cancela y debe reiniciarse.
• Si 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 iniciamos nuestra transacción. En este caso, utilizamos la regla de escritura de Thomas y simplemente omitimos nuestra operación de escritura y continuamos con normalidad; 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 con la marca de tiempo de la transacción.

Este es el tiempo mínimo transcurrido entre dos marcas de tiempo consecutivas. 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, lo que permite que algunas transacciones se confirmen en un orden incorrecto. Por ejemplo, en 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 distintos.

Si bien esta técnica no requiere bloqueo, ya que el objeto no se bloquea para evitar el acceso concurrente durante la duración de una transacción, el acto de registrar cada marca de tiempo en el objeto requiere un bloqueo de duración extremadamente corta en el objeto o en su proxy.