Format de fitxer

Escrit a partir de l'especificació de disseny del motor. El motor s'està implementant; això descriu el disseny, no una API publicada.

Capçalera

64 bytes a l'offset 0, amb la identitat i la geometria del fitxer. S'escriu una vegada, en la creació, i mai es reescriu — aquesta immutabilitat és la raó de mantenir-la separada de les pàgines meta: si el punter arrel visqués a la capçalera, cada commit la reescriuria, i un tall de corrent a mig escriure podria deixar un fitxer la geometria del qual ja no es pot llegir.

Offset	Bytes	Camp	Propòsit
0	8	`magic`	“INRO0DB1” — detecta a l’instant que un fitxer no és una base de dades inro, en lloc d’interpretar bytes arbitraris com a punters de pàgina.
8	2	`format_major`	Un binari que troba una versió major més alta que la seva es nega a obrir el fitxer. Sense aquest camp, una versió antiga corrompria un fitxer nou en aplicar regles obsoletes.
10	2	`format_minor`	Canvis compatibles amb versions anteriors.
12	1	`page_size_log2`	9 per a 512 B, 12 per a 4 KB. Un camp crític: sense la mida de pàgina no es pot llegir cap pàgina, per això viu en un offset fix i es llegeix amb una única lectura de 64 bytes.
13	1	`flags`	Trets fixats en la creació: checksums de pàgina, compressió de prefixos, xifratge. Fixats perquè canviar-los exigiria reescriure tot el fitxer.
14	2	—	Reservat.
16	16	`db_id`	L’identificador únic d’aquesta base de dades. Permet que els desplegaments multi-tenant detectin que un fitxer ha estat canviat, i evita que les eines de còpia de seguretat confonguin llinatges no relacionats.
32	8	`created_unix`	Marca de temps de creació, per a diagnòstic i anàlisi forense.
40	4	`meta_a_page`	La pàgina que conté el slot meta A.
44	4	`meta_b_page`	La pàgina del slot B. Explícita en lloc de fixa per convenió, perquè les dues es puguin col·locar en sectors físics diferents del dispositiu sense pujar la versió del format.
48	12	—	Reservat per créixer sense trencar el format.
60	4	`header_crc32`	La capçalera es valida a si mateixa. Si no quadra, la base de dades es nega a obrir i ho diu clarament, en lloc d’operar sobre una geometria corrupta.

Pàgines meta

Dos slots alterns, A i B. Cadascun conté:

txn_id (u64, monòton, mai es reutilitza)
un punter a l'arrel de l'arbre
el cap de la llista de pàgines lliures
n_pages: el nombre de pàgines que la transacció considerava assignades
una còpia dels camps de geometria de la capçalera, perquè es pugui recuperar si la capçalera es malmet
la clau de dades embolicada, quan el xifratge està activat
el seu propi CRC32, o una etiqueta d'autenticació si el xifratge està actiu

Un commit és: escriure les pàgines noves, fsync, escriure la meta inactiva, fsync. En obrir, es llegeixen els dos slots, es descarten els que fallen la validació, i es munta el que té el txn_id més alt. Si es produeix una fallada mentre s'escriu una meta, aquest slot falla la validació i es munta l'altre: es perd aquest commit, res no es corromp.

Disposició de les metes i sectors físics

Els discos actuals són de 4 KB físics fins i tot quan informen de sectors lògics de 512 B. Una escriptura interrompuda pot malmetre els 4 KB sencers. Si A i B compartissin un sector físic, un únic tall de corrent podria endur-se'ls tots dos, i la base de dades seria irrecuperable.

Disposició amb pàgines de 512 B:

pàgina 0      capçalera (64 B) + reservat
pàgina 1      meta A                        (sector físic 0)
pàgines 2-7   pàgines de l'arbre           (sector físic 0)
pàgina 8      meta B                        (sector físic 1)
pàgines 9+    pàgines de l'arbre

A i B cauen en sectors físics diferents per construcció. Que les pàgines de dades comparteixin sector amb la meta A no és un problema: són pàgines copy-on-write, i les que s'estan escrivint ja són lliures des del punt de vista de la meta supervivent, així que el dany que puguin patir és irrellevant.

Cost mínim fix per base de dades: 4,6 KB. En cinc mil tenants, 23 MB. La disposició ingènua amb pàgines de 4 KB pertot arreu costaria 60 MB.

Reubicació de la meta B. La capçalera emmagatzema meta_a_page i meta_b_page explícitament precisament perquè les metes es puguin moure. Això s'utilitza per baixar el terra: en un fitxer que encara no ha superat els 4 KB, la meta B viu a la pàgina 2, i es mou a l'offset 4096 quan el fitxer creix més enllà d'aquest punt. Durant aquesta finestra les dues metes comparteixen sector físic, però una base de dades per sota de 4 KB amb prou feines conté dades i recuperar-la vol dir recrear-la, així que el risc és acceptable a canvi de baixar el terra per base de dades de 4,6 KB a 1,5 KB. Cinc mil tenants inactius passen de 23 MB a 7,5 MB.

El trasllat passa dins d'una transacció ordinària: la meta B s'escriu a la seva nova posició, la capçalera s'actualitza, i se sincronitza. És l'única operació de tot el disseny que reescriu la capçalera, per això porta la còpia de geometria que les metes ja guarden.

Format de pàgina

Una pàgina amb slots i un directori. Capçalera lògica de 8 bytes més 4 per al CRC quan no hi ha xifratge:

0   1  tipus (0 fulla, 1 intern, 2 desbordament, 3 llista lliure)
1   1  flags
2   2  nombre de slots
4   2  final de l'array de slots
6   2  inici de les cel·les
8   4  crc32 de la resta de la pàgina      (absent si està xifrada)
12  .. array de slots (u16 per slot)
    .. espai lliure
    .. cel·les, creixent cap a l'inici de la pàgina

Els slots es mantenen ordenats per clau, cosa que permet la cerca binària sense moure cel·les en inserir. Amb una pàgina de 512 B, hi ha uns 500 bytes utilitzables.

Prefix compartit per pàgina, no per cel·la. El prefix comú a totes les claus d'una pàgina s'emmagatzema una vegada, entre la capçalera de la pàgina i l'array de slots; cada cel·la conserva només el seu sufix.

Emmagatzemar-lo per cel·la, relatiu a l'anterior, comprimiria una mica més però trencaria la cerca binària: la cel·la i no es podria descodificar sense descodificar abans de 0 a i−1, portant l'accés a la pàgina d'O(log n) a O(n). El prefix per pàgina conserva gairebé tot l'estalvi sense aquest cost.

Cel·la fulla: [suffix_len varint][suffix][value_len varint][value]. En claus de log, que comparteixen els bytes alts de la marca de temps, el prefix de pàgina elimina uns 5 de cada 11 bytes de clau.

Cel·la de node intern: [key_len varint][truncated separator][child_page u32]. El separador es trunca a la seqüència de bytes més curta que distingeix les dues fulles, en lloc de copiar la clau completa. Això eleva el factor de ramificació d'uns 35 a uns 50 amb pàgines de 512 B.

Valors grans: per sobre d'un quart de pàgina, els valors van a una cadena de pàgines de desbordament; la cel·la emmagatzema la longitud total i la primera pàgina de la cadena.

Varint i CRC32

Tots dos estan escrits a mà, juntament amb l'analitzador, el B+tree i la resta de les codificacions — els cobreix la política per defecte del projecte de zero depèndencies en temps d'execució.