P5 · Motor: transacciones

Publicado: semana 14 · Entrega: semana 16 · En parejas

La última pieza de quipu: varias transacciones a la vez y una caída en el peor momento. Cubre las semanas 13 a 15 (Silberschatz, caps. 17 a 19; notas 11, 12 y 14 de CS186). Se presenta en el laboratorio de la semana 16.

Al final de P5, quipu tiene una tabla con transacciones: un lock manager con strict 2PL que decide quién sigue y quién espera, un log write-ahead en un archivo aparte y una recuperación al estilo de ARIES que, después de una caída, deja exactamente los efectos de las transacciones que hicieron commit.

Node.js ejecuta un solo hilo y quipu es síncrono, así que la concurrencia se simula: las pruebas intercalan las operaciones de varias transacciones paso a paso, como los schedules de clase. Cuando una transacción tiene que esperar un lock, su operación no se ejecuta: devuelve WAIT y la prueba la vuelve a intentar más tarde, cuando el lock se liberó.

Archivos

Esta carpeta trae el punto de partida. Se copia a la carpeta del proyecto, encima de lo de P3 y P4; no trae ningún archivo de P3, así que no pisa nada de lo que ya hicieron:

Además, agregan un método a su quipu/page.mjs de P3 (sección 1). P5 usa DiskManager, BufferPool, SlottedPage, encode y decode de P3; no usa HeapFile ni el B+ tree, ni nada de P4.

Reglas comunes

• Las mismas de P3: las pruebas usan exactamente los nombres de este enunciado, pueden agregar todo lo que quieran por dentro, y cuando algo no se puede hacer el método lanza un Error (o una subclase).
• Las pruebas de P3 tienen que seguir pasando: lo que agreguen a los módulos de P3 no cambia nada de lo que ya hacían.
• Una transacción se identifica con un entero que da begin(): 1, 2, 3, … Una transacción es más joven que otra si su número es más grande.
• Un RID es { pageId, slot }, como en P3. El recurso que se bloquea por una fila es el string shipment:<pageId>:<slot>, por ejemplo shipment:3:17.

1. SlottedPage.put (en quipu/page.mjs)

Para rehacer y deshacer un cambio hay que poder dejar un slot dado exactamente como estaba: volver a poner una fila borrada en su slot, o rehacer un insert en el slot que anotó el log. insert no sirve, porque elige el slot. Agreguen a su SlottedPage:

• Si slot ≥ numSlots, el arreglo de slots crece hasta slot + 1 y los slots nuevos del medio quedan libres.
• Al liberar, los slots libres que quedan al final del arreglo salen de él: numSlots baja hasta el último slot ocupado más uno (0 si no queda ninguno). Así, liberar con put devuelve todo el espacio que ocupó el put que llenó ese slot, también el de los slots nuevos, y deshacer nunca se queda corto.
• Como insert y update en P3, put compacta sola cuando hace falta: que el registro entre depende solo del espacio libre total de la página, no de cómo estén repartidos los huecos.
• put no cambia los otros slots ni los bytes 0 a 7. Liberar un slot que ya está libre no hace nada y devuelve true.

2. Lock manager (quipu/lock-manager.mjs)

LockManager no sabe nada de páginas ni de filas: un recurso es un string y una transacción, un entero. Exporta LockManager.

Las reglas, que las pruebas revisan una por una:

• Compatibilidad. S es compatible con S; X no es compatible con nada.
• Pedir lo que ya se tiene. Si la transacción ya tiene el lock en ese modo o en uno más fuerte (X cubre a S), acquire devuelve 'granted' sin cambiar nada.
• Cola FIFO (sec. 18.1.4). Un pedido nuevo se concede si es compatible con todos los locks concedidos y la cola del recurso está vacía. Si no, va al final de la cola. Un S no se adelanta a un X que espera, aunque sea compatible con lo concedido: si no, un flujo de lectores dejaría esperando para siempre al escritor.
• Upgrade. Si la transacción tiene S y pide X: si es la única que tiene un lock sobre el recurso, se le concede de inmediato. Si no, espera al principio de la cola, delante de todos los pedidos que no son upgrades (detrás de otros upgrades, si hay). No suelta su S mientras espera.
• Una espera a la vez. Una transacción espera a lo más un pedido. Si una transacción que espera repite ese mismo pedido, acquire devuelve 'waiting' sin duplicarlo; si pide otra cosa, lanza un error.
• Al liberar. releaseAll revisa los recursos que la transacción tenía, en el orden de locksOf, y al final el recurso donde esperaba. En cada uno, concede los pedidos desde el principio de la cola mientras sean compatibles con lo concedido (un upgrade, con lo concedido a las demás) y se detiene en el primero que no lo es. Así, varios S seguidos se conceden juntos.
• Waits-for graph. Hay una arista Ti → Tj si Ti espera un recurso y Tj tiene ahí un lock incompatible con el pedido de Ti, o Tj está antes que Ti en la cola de ese recurso con un pedido incompatible (con FIFO, Ti también espera a Tj). detectDeadlock devuelve un ciclo: cada transacción de la lista espera a la siguiente, y la última a la primera. Si hay varios ciclos, cualquiera.

Por ejemplo, T3 tiene X sobre b y T1 tiene S sobre a. T2 pide X sobre a y espera. T3 pide S sobre a: es compatible con el S de T1, pero espera detrás de T2. T1 pide S sobre b y espera a T3. El ciclo es T1 → T3 → T2 → T1, y solo se ve con las aristas de la cola.

3. Log (quipu/log.mjs)

Un log write-ahead en un archivo aparte. Exporta LogManager.

Los LSN son 1, 2, 3, … sin huecos. Un registro que vuelve de get o de records tiene todos los campos con los que se agregó, más lsn, y los Buffer vuelven como Buffer. El formato del archivo lo deciden ustedes (una línea de JSON por registro está bien). Después de un crash(), los LSN que se perdieron se vuelven a usar: no es un problema, porque por la regla WAL ninguna página en disco tiene un pageLSN que no esté en el archivo.

Los registros que escribe quipu, todos con type, txn y prevLSN (el LSN del registro anterior de la misma transacción; 0 en el begin):

Pueden agregar campos (por ejemplo, el próximo número de transacción en el checkpoint). Es la versión de quipu de los registros de la sec. 19.9 y de la semana 15: logging fisiológico, físico por página (pageId) y lógico dentro de ella (el slot, no un offset).

4. Transacciones (quipu/database.mjs)

Database junta todo: una tabla en páginas con slots sobre un BufferPool, un LockManager y un LogManager. Exporta Database y WAIT, un valor único (un Symbol) que devuelven las operaciones que tienen que esperar.

Locks y strict 2PL

• get pide S y update y delete piden X sobre shipment:<pageId>:<slot> antes de leer o cambiar nada. Si el lock queda en espera, la operación no hace nada (ni lee, ni cambia la página, ni escribe en el log) y devuelve WAIT. La prueba la repite, con los mismos argumentos, cuando el lock se concedió (status vuelve a 'active'); la repetición encuentra el lock ya concedido y sigue.
• Una transacción que espera no puede hacer otra cosa que repetir esa operación o abortar: cualquier otra operación lanza un error. Tampoco puede hacer commit. Una transacción que terminó no puede hacer nada.
• Strict 2PL: ninguna operación suelta locks; todos se sueltan juntos en commit o abort. Un get que encuentra el slot libre se queda igual con su S.
• insert elige una página y, en ella, el slot libre de número más bajo sobre el que ninguna otra transacción tiene ni espera un lock (puede ser un slot nuevo al final). Pone la fila con put y toma X sobre ese RID, que se concede de inmediato. Por eso insert nunca espera.
• Un update que mueve la fila a otra página anota dos cambios en el log (el delete en la página vieja y el insert en la nueva) y toma X también sobre el RID nuevo.
• Cuando todas las transacciones que quedan esperan, la prueba llama a resolveDeadlocks(). La víctima queda 'aborted', con sus cambios deshechos, y lo que soltó se concede a las que esperaban.

Espacio reservado para el undo

Si T1 borra la fila del slot 3 de una página, T2 inserta en esa misma página y recibe el slot 3, y después T1 aborta, el undo de T1 ya no tiene dónde volver a poner su fila. Lo mismo pasa con los bytes: si T1 achica una fila y T2 usa el espacio que quedó, el undo de T1 no entra. Por eso:

Mientras una transacción esté activa, lo que liberó en una página (con un delete, un update que achica una fila o un update que la movió) queda reservado para ella: ninguna otra transacción ocupa espacio en esa página. Sus inserts van a otra página y sus updates que agrandan una fila de esa página la mueven a otra. Puede, en cambio, liberar espacio ahí (borrar o achicar). La reserva termina con el commit o el abort.

La misma transacción sí puede reusar lo que liberó: su undo va en el orden inverso y deshace primero lo que reusó. Con esta regla y la de insert (no usar slots con locks de otras), el undo siempre encuentra su slot libre y su espacio. La reserva vive en memoria: después de una caída no hace falta, porque durante la recuperación no hay transacciones nuevas.

Páginas de ceros

allocatePage escribe la página nueva en ceros en el disco en el momento, antes de que llegue su primer cambio y su registro en el log. Después de una caída, la tabla puede tener al final páginas de ceros que el log no menciona, o que menciona en registros que hay que rehacer. Regla:

Una página con sus 4096 bytes en cero es una página vacía. Antes de leerla o cambiarla, Database le da formato en memoria con SlottedPage.init.

Su pageLSN es 0, menor que cualquier LSN, así que el redo le aplica todo lo que el log tenga para ella. Ninguna página que Database haya cambiado queda en ceros, porque su pageLSN es al menos 1.

Database usa las páginas directamente (fetchPage, SlottedPage, put, unpinPage), no HeapFile. Como en P3, lleva en memoria una lista de páginas con espacio libre que arma la primera vez que hace falta (en el primer insert o en el primer update que mueve una fila), no al abrir ni en recover().

5. Log y recuperación (quipu/recovery.mjs)

Cada cambio de una fila se hace así: fetchPage, put sobre el slot, append del registro update (con la imagen anterior y la nueva), el LSN del registro en el pageLSN de la página (setPageLSN) y unpinPage sucia. Como quipu es síncrono, nadie escribe la página entre el put y el setPageLSN. El buffer pool es steal (puede escribir una página con cambios sin commit cuando la saca de memoria) y no-force (el commit no escribe páginas de datos), así que hace falta undo y redo.

• La regla WAL. El buffer pool no escribe una página sin antes forzar el log hasta el pageLSN de esa página. Se implementa con pool.beforeWrite (P3): log.flush(getPageLSN(buf)). Las pruebas lo revisan desde afuera: en cada escritura de una página al disco, su pageLSN tiene que ser a lo más log.flushedLSN.
• Commit. Fuerza el log hasta su registro commit; no escribe páginas de datos.
• Dirty page table. Database lleva en memoria la DPT: cada página cambiada que todavía no llegó al disco, con su recLSN (el LSN del primer cambio que la ensució). Una página entra con su primer cambio y sale cuando el buffer pool la escribe (beforeWrite también sirve para eso).
• Abort (sec. 19.4.2). Escribe abort y recorre los registros de la transacción hacia atrás por prevLSN. Por cada update escribe un clr con la imagen anterior y la aplica a la página (con el LSN del clr como pageLSN); un clr se salta hasta su undoNextLSN; al llegar al begin escribe end. Es el mismo undo de la recuperación.

recover({ redoLimit, undoLimit }) sigue ARIES (sec. 19.9) en versión simplificada, sobre una Database recién abierta:

1. Analysis. Empieza en el último checkpoint (o en el LSN 1 si no hay), con su transaction table y su DPT, y lee el log hacia adelante. Un update o clr actualiza el lastLSN de su transacción y agrega su página a la DPT si no estaba, con recLSN igual a su LSN; un begin agrega la transacción; un commit la marca; un end la saca. Al final, las perdedoras son las que quedaron sin commit.
2. Redo. Desde el menor recLSN de la DPT, cada update y cada clr se rehace (dejando el slot con su after y la página con su LSN como pageLSN) salvo que su página no esté en la DPT, que su LSN sea menor que el recLSN de la página, o que el pageLSN de la página ya sea mayor o igual que su LSN. Los dos primeros casos se deciden sin leer la página. Se rehace también lo de las perdedoras: se repite la historia.
3. Undo. Un conjunto con el lastLSN de cada perdedora. Se toma siempre el LSN más grande: si es un update, se escribe su clr, se aplica y se sigue con su prevLSN; si es un clr, se sigue con su undoNextLSN; si es un abort, con su prevLSN. Cuando una perdedora llega a su begin, se escribe su end.

recover() no escribe páginas ni fuerza el log al terminar: lo que hizo queda en el buffer pool y en la cola del log, como cualquier otro cambio, y si hay otra caída se vuelve a hacer. Por eso tiene que ser idempotente: caer en medio de la recuperación (o justo después) y recuperar de nuevo deja lo mismo, y gracias a los CLRs ningún update se deshace dos veces. Para simular esa caída, redoLimit detiene la recuperación en cuanto rehízo ese número de registros, sin llegar al undo, y undoLimit la detiene en cuanto escribió ese número de CLRs (con 0, antes del primero). Si el redo o el undo tienen menos trabajo que eso, la recuperación es completa. Sin opciones, también. Después de recover(), las transacciones nuevas siguen con begin().

Lo que las pruebas revisan de la recuperación:

• Después de crash() y recover() quedan exactamente las filas de las transacciones con commit, en los mismos RIDs, también si las páginas con cambios sin commit llegaron al disco y si hubo caídas en medio de recover().
• En el log final, cada update de una transacción que terminó sin commit tiene exactamente un clr (por su campo undone) y los de las que hicieron commit, ninguno. Una transacción que abortó antes de la caída no recibe más CLRs.
• Abrir una Database no lee páginas. recover() solo lee las páginas que tiene que rehacer o deshacer: después de un checkpoint con todas las páginas ya escritas, una caída cuesta tantas lecturas como páginas tocó lo que vino después.

Lo que queda a su criterio

El formato del archivo del log, cómo guardan la lock table, cómo arman el waits-for graph y buscan el ciclo, cómo llevan la transaction table y la DPT, y cómo reparten el código entre database.mjs y recovery.mjs (por ejemplo, recovery.mjs con las tres fases y el undo que también usa abort()). La prueba solo usa los métodos de este enunciado.

Bono. Locks de granularidad múltiple (IS e IX sobre la tabla, sec. 18.3) y prevención de deadlocks con wait-die, en módulos u opciones aparte: con las opciones por defecto, quipu se comporta como pide este enunciado.

README y presentación

En su README: un schedule de ejemplo con deadlock y cómo lo resolvió quipu (qué aristas tenía el waits-for graph y por qué esa víctima), y la traza de una recuperación: qué encontró el analysis (perdedoras y DPT), qué rehízo el redo y qué saltó, y qué CLRs escribió el undo, con los LSN de verdad de una corrida.

La presentación de la semana 16 dura 10 minutos y es una demostración por línea de comandos de cuatro escenarios (un script suyo sobre Database):

1. Dos transacciones comparten un S y una tercera pide X y queda en la cola.
2. Un upgrade de S a X, sin y con otra transacción que también tiene S.
3. Un deadlock que el waits-for graph detecta, la víctima que se elige y por qué.
4. Una caída con una transacción confirmada y otra en curso, y la recuperación con redo y undo que deja solo la confirmada.

Pruebas

make test                  # carga Chasqui en chasqui_test y corre las pruebas de quipu
QUIPU_SEED=7 make test     # lo mismo, con otras secuencias al azar

make test corre p3.public.test.mjs, p4.public.test.mjs y p5.public.test.mjs (los que estén en la carpeta) y las pruebas de ustedes en quipu/, con nombre *.test.mjs. Las de P3 y P4 tienen que seguir pasando. Las de P5 no usan PostgreSQL y dejan sus archivos en una carpeta temporal que se borra al final.

Las pruebas públicas de P5 tienen una sección por pieza: SlottedPage.put, LockManager, LogManager, las transacciones de Database (locks, strict 2PL, deadlocks, espacio reservado) y la recuperación (regla WAL, commit, steal, CLRs, caídas en medio de recover(), páginas de ceros, checkpoint). Las últimas pruebas de cada sección hacen miles de operaciones al azar: la del lock manager revisa sus invariantes después de cada paso, y la de recuperación ejecuta schedules de varias transacciones con caídas (también en medio de recover()) y compara la tabla con un modelo de lo que se confirmó. El azar sale de un generador con semilla, y cuando una falla, el mensaje dice la semilla y el paso. Las pruebas privadas son las mismas con otras semillas. Todas corren en pocos segundos.