Control de Concurrencia - Prep Segundo Parcial

¡Hola! Estudiemos Concurrencia y Recuperación 🚀

Esta aplicación interactiva te ayudará a practicar y dominar los ejercicios del segundo parcial de Base de Datos de la FIUBA.

Tu Progreso Global

0 de 12 ejercicios resueltos con éxito.

0 intentos totales registrados.

SGBD favoritos: SQLite & FastAPI backend.

Temario del Segundo Parcial

Los temas claves evaluados en la sección de Concurrencia y Recuperación son:

Serializabilidad: Construcción de Grafos de Precedencia (Conflictos RW, WR, WW) y equivalencias seriales.
Recuperabilidad y Cascada: Determinar si un solapamiento es recuperable y si evita rollbacks en cascada (ACR).
Log de Recuperación (REDO/UNDO): Algoritmos con checkpoint activo, determinación de qué transacciones rehacer/deshacer y la línea de retroceso.
Timestamps: Reglas básicas del planificador de timestamps, abortar lecturas tardías, y la Regla de Escritura de Thomas (Thomas's Write Rule).

Estatus de Ejercicios del Parcial

PARCIAL 2024 1C

Ejercicio de Concurrencia

Sin Empezar

Enunciado

Resolución Interactiva

Analiza el log secuencialmente. Haz clic en una línea para marcarla como la Línea de Retroceso (donde se empieza a leer / punto más lejano en UNDO/REDO).

Línea	Operación	Marca

Preguntas del Ejercicio

Mis Notas de Estudio

Usa este espacio para apuntar tus razonamientos sobre este ejercicio. Se guarda automáticamente.

Historial de Intentos

No has realizado intentos todavía.

📚 Resumen de Teoría de Concurrencia y Recuperación

Fórmulas rápidas, reglas y resúmenes de los conceptos evaluados en el examen.

Serializabilidad por Conflictos

Dos instrucciones en un solapamiento están en conflicto si y solo si:

Pertenecen a diferentes transacciones.
Operan sobre el mismo recurso (ej: $X$).
Al menos una de las operaciones es una escritura ($W(X)$).

Hay 3 tipos de conflictos:

Conflicto	Descripción	Relación de Precedencia
RW (Read-Write)	$R_{T_i}(X)$ precede a $W_{T_j}(X)$	$T_i \to T_j$
WR (Write-Read)	$W_{T_i}(X)$ precede a $R_{T_j}(X)$	$T_i \to T_j$
WW (Write-Write)	$W_{T_i}(X)$ precede a $W_{T_j}(X)$	$T_i \to T_j$

📌 Teorema fundamental: Un solapamiento es serializable por conflictos si y solo si su grafo de precedencias es acíclico. El orden equivalente es cualquier ordenamiento topológico del grafo.

Recuperabilidad (Recoverable Schedule)

Un solapamiento es recuperable si, para cada par de transacciones $T_i$ y $T_j$ tal que $T_j$ lee un ítem escrito previamente por $T_i$ ($T_j$ lee de $T_i$), el commit de $T_i$ ocurre antes que el commit de $T_j$.

$$(W_{T_i}(X), R_{T_j}(X)) \implies Commit(T_i) < Commit(T_j)$$

Evitar Rollback en Cascada (Avoid Cascading Aborts - ACR)

Un solapamiento **evita rollbacks en cascada** si, para cada par de transacciones $T_i$ y $T_j$ tal que $T_j$ lee un ítem escrito previamente por $T_i$, el commit de $T_i$ ocurre **antes de que $T_j$ realice la lectura**.

$$(W_{T_i}(X), R_{T_j}(X)) \implies Commit(T_i) < Read_{T_j}(X)$$

Si un solapamiento no cumple con esto, se dice que permite rollbacks en cascada porque si $T_i$ aborta, todas las transacciones que leyeron sus datos no guardados ($T_j$, etc.) también deberán abortar forzosamente.

Control de Concurrencia por Timestamps

Es un protocolo optimista (no usa locks, por ende no produce deadlocks). Cada transacción $T_i$ recibe un identificador único $TS(T_i)$ al iniciar. Cada ítem $X$ almacena:

$read\_TS(X)$: Timestamp de la transacción más nueva que ha leído $X$.
$write\_TS(X)$: Timestamp de la transacción más nueva que ha escrito $X$.

Reglas de Operación

Operación	Condición	Acción del Planificador
Leer $R(X)$	$TS(T_i) < write\_TS(X)$	Abortar y reiniciar $T_i$ (Lectura tardía)
Leer $R(X)$	$TS(T_i) \ge write\_TS(X)$	Permitir. Actualiza $read\_TS(X) = \max(read\_TS(X), TS(T_i))$
Escribir $W(X)$	$TS(T_i) < read\_TS(X)$	Abortar y reiniciar $T_i$ (Escritura tardía)
Escribir $W(X)$	$TS(T_i) < write\_TS(X)$	Abortar (Básico) o Ignorar (Regla de Escritura de Thomas)
Escribir $W(X)$	$TS(T_i) \ge \max(read\_TS(X), write\_TS(X))$	Permitir. Actualiza $write\_TS(X) = TS(T_i)$

Regla de Escritura de Thomas (Thomas's Write Rule)

Si $T_i$ quiere escribir $X$ y $TS(T_i) < write\_TS(X)$ pero $TS(T_i) \ge read\_TS(X)$, la escritura es obsoleta pero no causa problemas. Simplemente se descarta (no se escribe en la base de datos) y $T_i$ continúa sin abortar. Garantiza serializabilidad por **vistas**, pero no por **conflictos**.

Algoritmos de Recuperación (Log)

Algoritmo REDO (No-Steal/Force)

Las modificaciones se escriben a la BD solo tras el COMMIT. Si falla, las transacciones confirmadas deben rehacerse.

REDO Set: Transacciones con COMMIT en el log.
UNDO Set: Transacciones activas (no se deshacen físicamente porque no llegaron a disco en No-Steal, solo se marcan abortadas).
Procedimiento: Retroceder hasta la más antigua de las activas en el BEGIN CKPT del último checkpoint completo. Rehacer (escribir NewValue) de REDO Set hacia adelante.

Algoritmo UNDO (Steal/No-Force)

Las modificaciones pueden ir a disco antes del COMMIT. Si falla, los cambios de transacciones no confirmadas deben deshacerse.

REDO Set: Vacío (no se rehace nada).
UNDO Set: Transacciones con BEGIN pero sin COMMIT.
Procedimiento: Retroceder deshaciendo (escribiendo OldValue) las de UNDO Set hasta alcanzar sus respectivos BEGIN. Escribir ABORT en el log.

Algoritmo UNDO/REDO (Steal/No-Force)

Permite escribir datos antes del COMMIT (steal) y no obliga a flushearlos inmediatamente al commitear (no-force).

REDO Set: Transacciones con COMMIT.
UNDO Set: Transacciones con BEGIN pero sin COMMIT.
Procedimiento: Escanear hacia atrás deshaciendo (escribiendo OldValue) el UNDO Set hasta su BEGIN. Luego escanear hacia adelante desde el CKPT rehaciendo (NewValue) el REDO Set.

Reglas del Gestor de Recuperación

WAL (Write-Ahead Logging)

El registro de log correspondiente a una escritura (WRITE) debe ser volcado persistentemente a disco antes de que el propio dato modificado sea guardado en disco.

FLC (Force Log at Commit)

El registro de log correspondiente al COMMIT de una transacción debe ser volcado a disco de forma síncrona antes de considerar confirmada la transacción.

⚠️ Checkpoints Incompletos: Si no hay un registro END CKPT para el último BEGIN CKPT antes de la falla, dicho checkpoint se ignora por estar incompleto y se debe buscar el checkpoint completo anterior (o ir al inicio del archivo si no hay otro).

Políticas y Motores Reales

Los tres algoritmos de clase modelan combinaciones de dos políticas de buffer independientes:

STEAL vs NO-STEAL

STEAL: una página sucia de una transacción no confirmada puede escribirse a disco (para liberar buffer). Requiere UNDO si la transacción luego aborta.

NO-STEAL: páginas uncommitted nunca van a disco. No hace falta UNDO, pero exige buffer grande.

FORCE vs NO-FORCE

FORCE: al hacer COMMIT, todos los datos modificados se flushean síncronamente a disco. Committed = en disco. No hace falta REDO, pero los commits son lentos.

NO-FORCE: el COMMIT solo garantiza que el registro de COMMIT llegó al log. Los datos van a disco de forma diferida → hace falta REDO tras un crash.

Política	Necesita UNDO	Necesita REDO	Algoritmo
`STEAL + FORCE`	✓	✗	UNDO
`NO-STEAL + NO-FORCE`	✗	✓	REDO
`STEAL + NO-FORCE`	✓	✓	UNDO/REDO — todos los motores reales
`NO-STEAL + FORCE`	✗	✗	Sin log (impráctical)

En producción: todos los motores usan STEAL + NO-FORCE (UNDO/REDO) porque maximiza el rendimiento — permite buffer pequeño (STEAL evita que páginas uncommitted bloqueen el buffer) y commits rápidos (NO-FORCE evita el flush síncrono de datos en cada commit). El log WAL garantiza durabilidad y recuperabilidad. Ejemplos: InnoDB (MySQL) con undo log + redo log; PostgreSQL con WAL; SQLite con WAL mode.