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 sin bloqueo. Se usa en algunas bases de datos para manejar transacciones de manera segura, usando marcas de tiempo.

Operación

Supuestos

• Cada valor de los tiempos es único y representa con precisión un instante en el tiempo.
• Un timetamp de mayor valor ocurre más adelante en el tiempo que un timetamp de menor valor.

Generar 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 el timetamp.
• Utilice un contador compartido seguro de rosca que se aumenta al comienzo de una transacción como el timetamp.
• Una combinación de los dos métodos anteriores.

Formales

Cada transacción (Ti{displaystyle T_{i}) es una lista ordenada de acciones (Aix{displaystyle A_{ix}). Antes de que la transacción realice su primera acción (Ai1{displaystyle A_{i1}), está marcado con el timetamp actual, o cualquier otra secuencia estrictamente ordenada: TS()Ti)=NOW()){displaystyle TS(T_{i})=NOW()}. Cada transacción también recibe un conjunto inicialmente vacío de transacciones en las que depende, DEP()Ti)=[]{displaystyle DEP(T_{i}=[], y un conjunto inicialmente vacío de objetos antiguos que actualizó, OLD()Ti)=[]{displaystyle OLD(T_{i})=[].

Cada objeto ()Oj){displaystyle (O_{j})} en la base de datos se administran dos campos de temporizador que no se utilizan más que para el control de concurrencia: RTS()Oj){displaystyle RTS(O_{j})} es el momento en que el valor del objeto fue utilizado por última vez por una transacción, WTS()Oj){displaystyle WTS(O_{j})} es el momento en que el valor del objeto fue actualizado por última vez por una transacción.

Para todos Ti{displaystyle T_{i}:

Para cada acción Aix{displaystyle A_{ix}:

Si Aix{displaystyle A_{ix} desea utilizar el valor de Oj{displaystyle O_{j}:

Si TS(T_{i})}" xmlns="http://www.w3.org/1998/Math/MathML">WTS()Oj)■TS()Ti){displaystyle WTS(O_{j})]TS(T_{i})" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7dd86b4734c7debd73cc7282a288370bbf12aa7f" style="vertical-align: -1.005ex; width:20.264ex; height:3.009ex;"/> entonces Aborto (un hilo más reciente ha sobrescrito el valor),

De lo contrario, actualice el conjunto de dependencias DEP()Ti).add()WTS()Oj)){displaystyle DEP(T_{i}).mathrm {add} (WTS(O_{j})} y conjunto RTS()Oj)=max()RTS()Oj),TS()Ti)){displaystyle RTS(O_{j})=max(RTS(O_{j}),TS(T_{i})};

Si Aix{displaystyle A_{ix} desea actualizar el valor de Oj{displaystyle O_{j}:

Si TS(T_{i})}" xmlns="http://www.w3.org/1998/Math/MathML">RTS()Oj)■TS()Ti){displaystyle RTS(O_{j})TS(T_{i})" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e3ca62e084d3da2ea4742faa82cbd46bb142fa30" style="vertical-align: -1.005ex; width:19.592ex; height:3.009ex;"/> entonces Aborto (un hilo más reciente ya está dependiendo del valor antiguo),

Si TS(T_{i})}" xmlns="http://www.w3.org/1998/Math/MathML">WTS()Oj)■TS()Ti){displaystyle WTS(O_{j})]TS(T_{i})" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7dd86b4734c7debd73cc7282a288370bbf12aa7f" style="vertical-align: -1.005ex; width:20.264ex; height:3.009ex;"/> entonces Patrón (la Regla de escritura de Thomas),

De lo contrario almacenar los valores anteriores, OLD()Ti).add()Oj,WTS()Oj)){displaystyle OLD(T_{i}).mathrm {add} (O_{j},WTS(O_{j})}, set WTS()Oj)=TS()Ti){displaystyle WTS(O_{j})=TS(T_{i}, y actualizar el valor de Oj{displaystyle O_{j}.

Mientras que hay una transacción en DEP()Ti){displaystyle DEP(T_{i})} que no ha terminado: Espera.

Si hay una transacción en DEP()Ti){displaystyle DEP(T_{i})} que abortó entonces Aborto

De lo contrario: commit.

Para cancelar:

Para cada uno ()oldOj,oldWTS()Oj)){displaystyle (mathrm {old} O_{j},mathrm {old} WTS(O_{j})} dentro OLD()Ti){displaystyle OLD(T_{i})}

Si WTS()Oj){displaystyle WTS(O_{j})} iguales TS()Ti){displaystyle TS(T_{i}} entonces restaurar Oj=oldOj{displaystyle O_{j}=mathrm {old} O_{j} y WTS()Oj)=oldWTS()Oj){displaystyle WTS(O_{j})=mathrm {old} WTS(O_{j})}

Informal

Cada vez que comienza una transacción, recibe una marca de tiempo. Esta marca de tiempo indica el orden en que debe ocurrir la transacción, en relación con las demás transacciones. Entonces, dadas dos transacciones que afectan al mismo objeto, 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 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 quiere leer un objeto,

• pero la transacción comenzó antes el objeto escribir timetamp significa que algo cambió los datos del objeto después de que la transacción comenzó. En este caso, la transacción es cancelada y debe ser reiniciada.
• y la transacción comenzó después el objeto escribir timetamp, significa que es seguro para leer el objeto. En este caso, si el timetamp de transacción es después del objeto read timestamp, el timetamp de lectura se establece en el timetamp de transacción.

Si una transacción quiere escribir en un objeto,

• pero la transacción comenzó antes el objeto read timestamp significa que algo ha visto el objeto, y suponemos que tomó una copia de los datos del objeto. Así que no podemos escribir al objeto como eso haría inválidos los datos copiados, por lo que la transacción es abortada y debe ser reiniciada.
• y la transacción comenzó antes el objeto escribir timetamp significa que algo ha cambiado el objeto desde que empezamos nuestra transacción. En este caso utilizamos la regla de escritura de Thomas y simplemente saltamos nuestra operación de escritura y continuamos como normales; la transacción no tiene que ser abortada o reiniciada
• de lo contrario, la transacción escribe al objeto, y el objeto escribir timetamp está fijado en el timetamp de la transacción.

Recuperabilidad

Tenga en cuenta que el orden de tiempos en su forma básica no produce historias recuperables. Considerar por ejemplo la historia siguiente con las transacciones T1{displaystyle T_{1} y T2{displaystyle T_{2}:

W1()x)R2()x)W2()Sí.)C2R1()z)C1[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, como T2{displaystyle T_{2} se compromete a pesar de haber leído de una transacción no comprometida. Para asegurarse de que produce historias recuperables, un programador puede mantener una lista de otras transacciones que cada transacción tiene leído en, y no permitir que una transacción se comprometa antes de esta lista consistía en sólo transacciones comprometidas. Para evitar los abortos en cascada, el programador podría etiquetar los datos escritos por transacciones no comprometidas como sucio, y nunca dejar que se inicie una operación de lectura sobre tal elemento de datos antes de que no fuera etiquetado. Para obtener una historia estricta, el programador no debe permitir ninguna operación en artículos 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 (gruesa), aumenta la posibilidad de que dos o más marcas de tiempo sean iguales y, por lo tanto, permite que algunas transacciones se comprometan fuera del orden correcto. Por ejemplo, suponiendo 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 se les dará 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 en el Objeto requiere un bloqueo de duración extremadamente breve en el Objeto o su proxy.