Idea centrale
Un database, al livello più basso, deve fare solo due cose: mettere via un dato quando glielo dai e ritrovarlo quando lo chiedi. Il capitolo parte da qui, dalla versione più stupida possibile di queste due operazioni, per far vedere dove si rompe e perché servono gli indici.
Il database più semplice del mondo
Kleppmann apre con un database scritto come due funzioni bash. Scrivere significa aggiungere una riga chiave,valore in fondo a un file; leggere significa cercare quella chiave nel file.
#!/bin/bash
db_set () {
echo "$1,$2" >> database
}
db_get () {
grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}
db_set 42 '...' aggiunge una riga in coda. db_get 42 cerca tutte le righe che iniziano con 42, e tiene l'ultima (tail -n 1): se una chiave è stata aggiornata più volte, le vecchie versioni restano nel file, non vengono sovrascritte.
Provalo qui sotto. Aggiungi righe con db_set, poi cerca una chiave con db_get e guarda come la lettura scorre il file dall'alto verso il basso e si tiene l'ultima occorrenza.
Perché la scrittura è veloce e la lettura no
db_set è difficile da battere: aggiungere in fondo a un file è l'operazione di scrittura più semplice che esista. Per questo molti database, sotto il cofano, usano un log: un file a sola aggiunta (append-only). Qui log non vuol dire i messaggi testuali di un'applicazione, ma il senso più generale: una sequenza di record aggiunti in coda su disco, anche binari.
db_get invece è terribile man mano che i dati crescono. Per ogni lettura deve scorrere tutto il file dall'inizio alla fine cercando la chiave. Il costo è O(n): raddoppi i record, raddoppia il tempo di ricerca. L'animazione qui sopra mostra proprio questo, le righe lette che salgono fino a coprire l'intero file.
Il trade-off di fondo dello storage. Scrittura e lettura tirano in direzioni opposte. Il log a sola aggiunta rende le scritture quasi gratis ma costringe ogni lettura a una scansione completa. Un indice ribalta il conto: rende le letture veloci, ma è una struttura in più da aggiornare a ogni scrittura, quindi rallenta le scritture e occupa spazio.
L'indice come struttura derivata
Per trovare in fretta il valore di una chiave serve una struttura dati diversa: un indice. L'idea generale è organizzare i dati in un certo modo (per esempio ordinati per chiave) così da localizzare in fretta quello che cerchi. Se vuoi cercare gli stessi dati in più modi, ti servono più indici su parti diverse del dato.
Tre proprietà da tenere a mente:
- Un indice è una struttura derivata dai dati primari: aggiungerlo o toglierlo non cambia il contenuto del database, cambia solo la performance delle query.
- Mantenerlo ha un costo sulle scritture: ogni volta che scrivi un dato, va aggiornato anche l'indice.
- Per questo i database non indicizzano tutto di default: scegli tu gli indici, in base ai pattern di query della tua applicazione.
Mappa mentale
Domande aperte
- Il log cresce all'infinito: come si recupera spazio senza fermare le scritture? (compaction, segmenti)
- Come si gestiscono le scritture concorrenti e i record scritti a metà durante un crash?
- Quando un indice ordinato conviene davvero rispetto a una hash table in memoria?
Sono i fili che il capitolo tira nelle sezioni successive (hash index, SSTable e LSM-tree, B-tree).