P3 · Motor: almacenamiento

Publicado: semana 9 · Entrega: semana 12 · En parejas

Desde esta entrega dejan de usar un motor y empiezan a construir uno: quipu, un motor de almacenamiento pequeño en Node.js. Al final de P3, quipu guarda la tabla de envíos de Chasqui en un archivo de páginas, la lee a través de un buffer pool y la indexa con un B+ tree. Cubre las semanas 9 a 11 (Silberschatz, caps. 13 y 14; notas 3, 4 y 5 de CS186).

quipu es síncrono: lee y escribe el archivo con fs.readSync y fs.writeSync, sin promesas. Así el código se parece al de un motor real y la concurrencia queda para P5, donde la simularemos de forma explícita.

Archivos

Esta carpeta trae el punto de partida. Se copia a la carpeta del proyecto, junto a lo de P0–P2:

Sus pruebas van en quipu/, con nombre *.test.mjs (por ejemplo, quipu/btree.test.mjs). node load.mjs deja sus archivos en data/, que no se entrega.

Reglas comunes

• Las pruebas públicas usan exactamente los nombres de este enunciado. Pueden agregar todo lo que quieran por dentro: más métodos, más módulos, clases auxiliares.
• Un RID es un objeto { pageId, slot } con dos enteros.
• Una fila es un objeto con una propiedad por columna del esquema, por ejemplo { shipment_id: 17, status: 'delivered', ... }; NULL es null.
• Cuando algo no se puede hacer (una página que no existe, un slot libre, un valor que no es del tipo de su columna), el método lanza un Error (o una subclase, como RangeError o TypeError) con un mensaje que diga qué pasó. Las pruebas solo revisan que lance; el mensaje es para quien depura.
• En todas las páginas que escribe quipu (de datos, de índice o de metadatos), los bytes 0 a 7 son del pageLSN de P5: un entero sin signo de 64 bits en little-endian. En P3 vale 0 y nadie lo toca.

Módulos y API

quipu/disk.mjs — DiskManager

Un archivo dividido en páginas de PAGE_SIZE = 4096 bytes. Es el único módulo que toca el archivo; todo lo demás pasa por aquí. Exporta PAGE_SIZE y DiskManager.

readPage y writePage lanzan un error si pageId no está entre 0 y numPages − 1 o si buf no mide 4096 bytes. allocatePage no cuenta en stats. Al volver a abrir un archivo, numPages es el de antes y stats empieza en cero.

quipu/record.mjs — formato de registros

encode(schema, row) devuelve un Buffer con el registro y decode(schema, bytes) devuelve la fila. Un esquema es un arreglo de columnas, cada una con name y type, que es 'int32', 'float64' o 'text':

[{ name: 'shipment_id', type: 'int32' }, { name: 'status', type: 'text' }]

El formato es el de largo variable de la sec. 13.2.2, en este orden y todo en little-endian:

Por ejemplo, con las columnas a int32, b text, c float64 y d text, la fila { a: -2, b: 'ñu', c: 1.5, d: null } ocupa 24 bytes: el bitmap 00001000, a en los bytes 1–4, el offset 21 y el largo 3 de b en los bytes 5–8, c en 9–16, ceros para d en 17–20 y los 3 bytes de 'ñu' en 21–23.

decode devuelve un objeto con todas las columnas, en el orden del esquema. encode lanza un error si una columna no está en la fila (undefined no es NULL), si un int32 no es un entero entre −2³¹ y 2³¹ − 1, si un float64 no es un number o si un text no es un string. -0, NaN e Infinity son float64 válidos y vuelven iguales.

quipu/page.mjs — SlottedPage

Una vista sobre un Buffer de 4096 bytes con el formato de página con slots de Silberschatz (sec. 13.2.2): encabezado, arreglo de slots que crece desde el inicio y registros que crecen desde el final. Todo el estado de la página vive en el Buffer: otra SlottedPage sobre una copia de los mismos bytes ve lo mismo. Un registro es un Buffer de al menos 1 byte.

Los RIDs no cambian nunca: ni compact, ni update, ni otro insert mueven un registro de slot. insert y update compactan solos cuando el espacio libre alcanza pero está repartido en huecos. update(slot, bytes) siempre funciona si bytes.length es a lo más el largo del registro actual más freeSpace(). delete y update de un slot libre lanzan un error.

El encabezado debe ser chico: una página vacía tiene un freeSpace() de al menos 4060 bytes y en una página entran al menos 400 registros de 6 bytes. El resto del formato (qué guarda el encabezado, cómo se marca un slot libre, de cuántos bytes es cada slot) lo deciden ustedes y lo documentan en su README.

El módulo exporta además getPageLSN(buf) y setPageLSN(buf, lsn), que leen y escriben el pageLSN de cualquier página de quipu (bytes 0 a 7, como number). Ningún método de SlottedPage cambia esos bytes.

quipu/buffer-pool.mjs — BufferPool

Las reglas, que las pruebas revisan con contadores:

• fetchPage de una página en memoria es un hit; si hay que leerla del disco, un miss. newPage no es hit ni miss. Cada página que sale de la memoria para hacer sitio (en fetchPage o en newPage) es una eviction.
• “Sucia” se acumula: después de un unpinPage(p, true), la página sigue sucia aunque los siguientes unpinPage digan false, hasta que se escriba. Una página limpia nunca se escribe.
• unpinPage de una página que no está en memoria, o con pin count 0, lanza un error: es un bug de quien llama.
• Si todos los frames tienen páginas fijadas, fetchPage y newPage lanzan un error con un mensaje claro, también un bug de quien llama. newPage no agrega la página al archivo si no tiene frame para ella.

Reemplazo con clock (sec. 13.5.2 y nota 5 de CS186), exactamente así, porque las pruebas revisan qué página sale:

1. Los frames van de 0 a capacity − 1 y cada uno tiene un bit de referencia. Mientras quede un frame vacío, la página va al frame vacío de número más bajo, sin mover la manecilla.
2. Cada vez que una página entra a un frame o se pide con un hit, su bit queda en 1.
3. Para elegir víctima, la manecilla (que empieza en el frame 0) avanza de a un frame, dando la vuelta al final: salta los frames con páginas fijadas; a un frame con bit en 1 le pone 0 y sigue; el primer frame sin fijar y con bit en 0 es la víctima. La página nueva ocupa ese frame y la manecilla queda en el frame siguiente.
4. Si en dos vueltas no encuentra víctima, todas las páginas están fijadas.

Por ejemplo, con 3 frames y las páginas pedidas en el orden 0, 1, 2, 3, 1, 4, 0, 5 (cada una se suelta antes de pedir la siguiente):

Al final, stats es { hits: 1, misses: 7, evictions: 4 } y el disco hizo 7 lecturas.

quipu/heap-file.mjs — HeapFile

Una tabla como heap file sobre el buffer pool. El archivo del DiskManager es todo del heap file y todas sus páginas son páginas con slots con filas de la tabla, sin página de metadatos: la página p del archivo es la página p de la tabla.

• Una fila que, codificada, no entra en una página vacía hace que insert y update lancen un error.
• El heap file lleva su propia lista de páginas con espacio libre, para no recorrer todo el archivo en cada insert. La lista puede vivir en memoria; como no hay página de metadatos, al abrir un archivo con datos se arma recorriéndolo una vez, la primera vez que haga falta. Con la lista armada, un insert lee a lo más una página del disco.
• scan lee cada página del archivo una sola vez: con un buffer pool frío, un scan completo hace exactamente numPages lecturas.
• Ninguna operación deja páginas fijadas al terminar, tampoco un scan que se corta a la mitad con break.
• Si update mueve una fila, los índices que apuntaban al RID viejo quedan desactualizados. En P3 eso es responsabilidad de quien llama.

quipu/btree.mjs — BPlusTree

Un índice B+ tree guardado en páginas del buffer pool (no en objetos de JavaScript), con claves int32 y valores RID. El archivo del DiskManager es todo del índice.

Para un índice sobre una columna con repetidos (como sender_id), la clave de búsqueda es el par (key, rid), como explica la sec. 14.3.5: las entradas se ordenan por key, luego por rid.pageId y luego por rid.slot, y ese es el orden de range. Así cada entrada es única aunque la clave se repita, y los separadores de los nodos internos son pares completos. Con unique: true, insert de una clave que ya está lanza un error. En cualquier índice, insert del mismo par (key, rid) dos veces lanza un error, y también una clave que no es un int32.

Requisitos que revisan las pruebas:

• Cada nodo es una página. Una hoja guarda al menos 200 entradas y un nodo interno al menos 200 hijos antes de partirse; al partir, cada mitad se queda con la mitad de las entradas.
• Todo el árbol vive en las páginas: lo que guarden en memoria entre llamadas (por ejemplo, el pageId de la raíz y la altura) tiene que estar también en el archivo, porque al volver a abrirlo el árbol es el mismo.
• Abrir un árbol existente lee a lo más una página (la de metadatos o la raíz, según dónde guarden la raíz). Abrir el árbol y hacer un search, empezando con el buffer pool vacío, leen entre height() y height() + 2 páginas: una por nivel, más la de metadatos y una hoja vecina si hacen falta.
• Ninguna operación deja páginas fijadas al terminar; el índice funciona con un buffer pool de 3 frames.

La eliminación es opcional (bono): delete(key, rid), que devuelve true o false, sin necesidad de fusionar nodos.

Lo que queda a su criterio

El formato del encabezado y de los slots de SlottedPage (fuera de los bytes 0 a 7), cómo recuerda el heap file sus páginas con espacio libre, el formato de los nodos del B+ tree, si usa una página de metadatos y dónde guarda la raíz. Todo eso va, con un diagrama de bytes, en su README.

Pensando en P4 y P5

P4 arma operadores sobre esta API: un sequential scan sobre scan(), un index scan sobre range(), y mide el costo de cada plan con disk.stats. P5 escribe un LSN en cada página que modifica (setPageLSN), usa beforeWrite para forzar el log antes de escribir una página (la regla WAL) y simula una caída cerrando el DiskManager sin flushAll. Lo que P5 necesite además para deshacer y rehacer cambios lo agrega P5.

Cargar Chasqui en quipu

node load.mjs [carpeta] lee la tabla shipment de PostgreSQL con pg (la conexión sale de las variables de entorno, como en P0) y deja en la carpeta (por defecto, data/ junto a load.mjs) tres archivos, cada uno con su DiskManager y su BufferPool:

Si los archivos ya existen, los reemplaza: cargar dos veces deja lo mismo que cargar una. En quipu, los integer son int32, los numeric son float64 (todos los de Chasqui tienen dos decimales) y los timestamptz son float64 con los milisegundos desde el 1 de enero de 1970 en UTC, lo que da Date.getTime() sobre el Date que devuelve pg. Las pruebas comparan, para muchas claves y rangos al azar, las filas que devuelve quipu con las que devuelve PostgreSQL.

README

El formato exacto de sus páginas (un diagrama con los bytes de una página de datos y de un nodo del B+ tree), cuántas páginas ocupa shipment en quipu y en PostgreSQL (pg_relation_size) y por qué no coinciden, y la altura de los dos índices comparada con la que predice el cálculo de la semana 10.

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 (y, cuando estén en la carpeta, p4.public.test.mjs y p5.public.test.mjs) y las pruebas de ustedes en quipu/. Son las pruebas de esta mitad del proyecto: las de P0 a P2 se quedan en la carpeta, pero este Makefile ya no las corre.

Las pruebas públicas tienen una sección por módulo (DiskManager, registros, SlottedPage, BufferPool, HeapFile, BPlusTree) y una de integración que corre node load.mjs en una carpeta temporal. Varias hacen miles de operaciones al azar y comparan a quipu con un modelo simple en JavaScript (un Map, un arreglo ordenado); el azar sale de un generador con semilla, y cuando una falla, el mensaje dice la semilla y el paso, para que puedan repetir exactamente esa secuencia. Las pruebas privadas son las mismas con otras semillas y con los datos de Chasqui generados con otra semilla (SEED=123 make test). Todas corren en pocos segundos; si las suyas tardan más de un minuto, algo está leyendo de más.