En informática , un algoritmo de control de concurrencia basado en marcas de tiempo es un método de control de concurrencia sin bloqueo . Se utiliza en algunas bases de datos para manejar transacciones de forma segura, utilizando marcas de tiempo .
Operación
Supuestos
- Cada valor de marca de tiempo es único y representa con precisión un instante en el tiempo.
- No hay dos marcas de tiempo iguales.
- Una marca de tiempo de valor más alto ocurre más tarde en el tiempo que una marca de tiempo de valor más bajo.
Generando una marca de tiempo
Se han utilizado varias formas diferentes para generar la marca de tiempo
- Utilice el valor del reloj del sistema al inicio de una transacción como marca de tiempo.
- Utilice 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.
Formal
Cada transacción () es una lista ordenada de acciones (). Antes de que la transacción realice su primera acción (), está marcado con la marca de tiempo actual , o cualquier otra secuencia estrictamente ordenada :. A cada transacción también se le da un conjunto inicialmente vacío de transacciones de las que depende,, y un conjunto inicialmente vacío de objetos antiguos que actualizó, .
Cada objeto en la base de datos se le dan dos campos de marca de tiempo que no se utilizan más que para el control de concurrencia: es el momento en el que el valor del objeto fue utilizado por última vez por una transacción, es el momento en el que el valor del objeto se actualizó por última vez mediante una transacción.
Para todos :
- Para cada acción :
- Si desea utilizar el valor de :
- Si luego abortar (un hilo más reciente ha sobrescrito el valor),
- De lo contrario, actualice el conjunto de dependencias y establecer ;
- Si desea actualizar el valor de :
- Si luego abortar (un hilo más reciente ya se basa en el valor anterior),
- Si luego omita (la regla de escritura de Thomas ),
- De lo contrario, almacene los valores anteriores, , colocar y actualice el valor de .
- Si desea utilizar el valor de :
- Mientras haya una transacción en que no ha terminado: espera
- Si hay una transacción en que abortó luego de abortar
- De lo contrario: cometer .
Para abortar :
- Para cada en
- Si es igual a luego restaurar y
Informal
Siempre que comienza una transacción, recibe una marca de tiempo. Esta marca de tiempo indica el orden en el que debe ocurrir la transacción, en relación con las otras transacciones. Por lo tanto, dadas dos transacciones que afectan al mismo objeto, 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 de 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 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 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 debe reiniciarse.
- 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 saltamos 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.
Recuperabilidad
Tenga en cuenta que el orden de la marca de tiempo en su forma básica no produce historiales recuperables. Considere, por ejemplo, el siguiente historial con transacciones y :
Esto podría ser producido por un programador TO, pero no es recuperable, ya que se compromete a pesar 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 ha leído cada transacción y no permitir que una transacción se confirme antes de que esta lista solo consista en transacciones comprometidas. 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 un elemento de datos de este tipo antes de que no se etiquete. Para obtener un historial estricto, el programador no debe permitir ninguna operación en elementos sucios.
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 (aproximada), la posibilidad de que dos o más marcas de tiempo sean iguales aumenta y, por lo tanto, permite que algunas transacciones se comprometan fuera del orden correcto. Por ejemplo, asumiendo que tenemos un sistema que puede crear cien marcas de tiempo únicas por segundo, y dados dos eventos que ocurren con 2 milisegundos de diferencia, probablemente recibirán la misma marca de tiempo aunque en realidad ocurrieron 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 breve en el Objeto o su apoderado.