Pedido de marca de tiempo multiversión

En la técnica de ordenamiento por sello de tiempo Multiversión, para cada transacción en el sistema, se asigna un sello de tiempo único antes del inicio de la ejecución de la transacción. La marca de tiempo de una transacción T se denota por TS(T). Para cada dato X se asocia una secuencia de versiones <X ₁ , X ₂ , X ₃ ,……X _K >.

Para cada versión X _i de un elemento de datos (X), el sistema mantiene los siguientes tres campos:

• El valor de la versión.
• Read_TS (X _i ): la marca de tiempo de lectura de X _i es la marca de tiempo más grande de cualquier transacción que lea con éxito la versión X _i.
• Write_TS (X _i ): la marca de tiempo de escritura de X _i es la marca de tiempo más grande de cualquier transacción que escribe con éxito la versión X _i.

Para garantizar la serialización, se utilizan las dos reglas siguientes:

Supongamos que una transacción T emite una solicitud de lectura y una solicitud escrita para un elemento de datos X. Sea X _i la versión que tiene el Write_TS(X _i ) más grande de todas las versiones de X, que también es menor o igual que TS(T) .

• Regla 1: supongamos que la transacción T emite una solicitud de lectura (X), si Read_TS (X _i ) <TS (T), el sistema devuelve el valor de Xi a la transacción T y actualiza el valor de Read_TS ( _{X i} ) a TS(T)
• Regla 2:  Supongamos que la transacción T emite una solicitud Write(X) TS(T) < Read_TS(X), entonces el sistema aborta la transacción T. Por otro lado, si TS(T) = Write_TS(X), el el sistema sobrescribe el contenido de X; si TS(T)>Write_TS(X) crea una nueva versión de X.

Ejemplo:

Considere el siguiente horario

Deje que las marcas de tiempo de la Transacción T1 y T2 sean 5 y 10 respectivamente. Estas transacciones realizan operaciones de lectura y escritura en un elemento de datos X.

• Suponga inicialmente que el estado del elemento de datos X es X ₀ y Read_TS(X ₀ )=Write_TS(X ₀ )=0
• T1 realiza Read(X), como Read_TS(X ₀ )<TS(T1) por lo que T1 leerá el valor de X ₀ y establecerá Read_TS(X ₀ )=TS(T1)=5,
• T1 realiza Write(X), como Write_TS(X ₀ )<TS(T1) esto crea una nueva versión de X, es decir, X ₁ y establece Read_TS(X ₁ )=Write_TS(X ₁ )=TS(T1)=5.
• T2 realiza Read(X), como Read_TS(X ₁ )<TS(T2) por lo que T2 leerá el valor de X ₁ y establecerá Read_TS(X ₁ )=TS(T2)=10.
• T2 realiza Write(X), como Write_TS(X ₁ )<TS(T2) esto crea una nueva versión de X, es decir, X ₂ y establece Read_TS(X ₂ )=Write_TS(X ₂ )=TS(T2)=10.
• T1 realiza la lectura (X). En el orden normal de la marca de tiempo, esto abortaría T1 (y posteriormente T2) porque T2 ya había sobrescrito X. Dado que mantuvimos las versiones anteriores, leemos X ₁ en lugar de X ₂ y la lectura es exitosa.
• T1 realiza Write(X), As TS(T1)<Read_TS(X ₁ ) (es decir, T2 ya ha leído una versión de X que T1 aún no ha producido). El sistema cancela T1.
• Dado que T2 había leído X ₁ cuando T1 abortó, cayó en cascada en T2 y T2 abortó.

ventajas:

• Las requests de lectura de la transacción nunca fallan y nunca se hacen esperar.
• Encuentra su aplicación en sistemas de bases de datos donde las requests de lectura son más frecuentes que las requests de escritura.

Desventajas:

• La lectura de un elemento de datos requiere la actualización del campo de marca de tiempo de lectura, lo que da como resultado dos posibles accesos al disco, en lugar de uno.
• Los conflictos entre transacciones se resuelven mediante reversiones, en lugar de esperas. Esta alternativa puede ser costosa.
• El esquema de ordenación de marcas de tiempo de múltiples versiones no garantiza la capacidad de recuperación y la falta de cascada.