Tecnologia di un
Database Server
S. Costantini
Dispensa per il Corso di Basi di dati e Sistemi
Informativi
Premessa
• Questa dispensa integra i contenuti della
seconda parte del Capitolo 9 del Libro di
Testo del Corso
– Atzeni, Ceri, et al., Basi di Dati: concetti, linguaggi e architetture,
McGraw-Hill editore.
• Questa dispensa non sostituisce questo
capitolo, che va comunque studiato.
Modello di un Sistema
Transazione 1
Transazione N
Bot,
SQL Queries
Commit, Abort
Database
Server
Ottimizzatore Query
Esecutore Query
Scheduler
Buffer Manager
Recovery manager
Database
Gestore degli accessi
• E’ il modulo di piu’ basso livello del data
manager
• Nei DBMS relazionali viene chiamato RSS
(Relational Storage System)
• Effettua in pratica gli accessi alla BD
• Conosce l’organizzazione fisica delle pagine
• Conosce la disposizione delle tuple nelle
pagine
• Usa un buffer manager per la gestione del
Indici
• Come si implementano Read e Write?
• Bisogna reperire i dati in Memoria di Massa
• A partire dal valore della chiave di una tupla,
occorre trovare il record id
– Record id = [pagina-id, offset-nella-pagina]
• Un indice collega i valori delle chiavi ai record
id.
– Le strutture indice piu’ comuni: tabelle hash e Balberi
Hashing
• L’hashing usa una funzione H:VB, dalle chiavi
al numero del blocco (pagina) dove si trova il
dato
– V = matricola
B = {1 .. 1000}
H(v) = v mod 1000
– se una pagina va in overflow, allora si deve
aggiungere una lista di pagine extra
– Al 90% di carico delle pagine, 1.2 accessi per
richiesta!
– ma, va male per accessi su intervalli (10 < v < 75)
B-albero
•
•
•
•
•
•
Ogni nodo e' un sequence di coppie [puntatore, chiave]
K1 < K2 < … < Kn-2 < Kn-1
P1 punta a un nodo contenente chiavi < K1
Pi punta a un nodo contenente chiavi in intervallo [Ki-1, Ki)
Pn punta a un nodo contenente chiavi > Kn-1
Dunque, K ´1 < K ´2 < … < K ´n-2 < K ´n-1
K1
P1
...
K´1 P´1 . . .
Ki
Pi Ki+1 . . . Kn-1 Pn
K´i P´i K´i+1 . . . K´n-1 P´n
Esempio n=3
127
14
83
127 145 189
221
496
352
221 245 320
521
352 353
690
487
• Notare che le foglie sono ordinate per chiave, da
sinistra a destra
• Importante: per ogni chiave, la foglia contiene il
Record id della tupla, o la tupla stessa
Inserzione
• Per inserire la chiave v, si cerca la foglia dove v
dovrebbe trovarsi: se c’e’ spazio, si inserisce
• Se no, si spezza la foglia in due, e si modifica il
padre per prevedere i puntatori alle due foglie
19
12
--
14 17
15
12 14
19
15 17
Per inserire la chiave 15
• si spezza la foglia
X
• nel padre, [0, 19)
diventa [0, 15) e [15, 19)
• se il padre e’ pieno, bisogna
spezzarlo (in modo simile)
X • l’albero resta automaticamente
bilanciato
B-albero: Osservazioni
• L’algoritmo di cancellazione riunisce nodi
adiacenti con riempimento < 50%
• La radice ed i nodi di livello uno sono mantenuti
in una cache, per ridurre gli accessi a
• Indice secondario: le foglie contengono in
realta’ coppie [chiave, record id]
• Indice primario: le foglie contengono i record
B+Alberi
• Ogni nodo foglia ha un puntatore al successivo
• facilita la ricerca su intervalli: trovata la prima chiave
dell’intervallo, basta scorrere le foglie adiacenti
mediante i puntatori
P
C
12
19
P
-X
14
17
15
C
12 14
19
C´
15 17
X
B+Albero: ottimizzazione
• B+albero - ciascuna foglia ha un puntatore alla
prossima, nell’ordine dato dalle chiavi
• Obbiettivo: ottimizzare interrogazioni il cui predicato di
selezione definisce un intervallo di valori ammissibili
• Trovato il primo valore della chiave, si scandiscono
sequenzialmente i nodi foglia
Database system
Recovery
Controllore dell’Affidabilita’
S. Costantini
Introduzione
• Un database puo’ divenire inconsistente a
causa di:
– fallimento di una transazione(abort)
– errore di sistema (a volte causato da un OS crash)
– media crash (disco corrotto)
• Il sistema di recovery assicura che il database
contenga esattamente gli aggiornamenti
prodotti dalle transazioni committed (cioe’
assicura atomicita’ e persistenza, nonostante i
guasti )
Terminologia
• Affidabilita’ - il grado di certezza con il quale un
sistema fornisce i risultati attesi su prove
ripetute
• L’affidabilita’ si misura come
mean-time-between-failures (MTBF)
• Disponibilita’ - frazione di tempo nel quale il
sistema fornisce i risultati attesi.
• La disponibilita’ e’ ridotta anche dai tempi di
riparazione e manutenzione preventiva
• Disponibilita’ = MTBF/(MTBF+MTTR), where
MTTR is mean-time-to-repair
Terminologia (cont.)
• Failure (fallimento) - un evento dove il sistema
dia risultati inattesi (sbagliati o mancanti)
• Fault (guasto) - causa identificata o ipotizzata di
fallimento
– Es. Un guasto nella scheda di memoria che causa
un malfunzionamento del software
• Transient fault - e’ occasionale, e non avviene
nuovamente se si ritenta l’operazione
• Permanent fault - non-transient fault
Quali sono le cause di guasto?
Environment
Hardware
Subtotal
system Mgmt
Software
Tandem ‘89 Tandem ‘85 AT&T/ESS ‘85
7%
14%
8%
18%
15%
32%
20%
21%
42%
30%
64%
25%
50%
• Il maggior problema e’ il software
• Environment - incendi, terremoti, vandalismi,
mancanza di elettricita’, guasto al condizionatore
• system management - manutenzione, configurazione
Assunzioni
• Ogni transazione mantiene i write locks fino a
dopo il commit. Questo assicura
– no aborti a catena
– strictness (non si utilizzano mai dati non
committed)
• Gestione a livello di pagine
– il database e’ un insieme di pagine
– le read e write operano su pagine
Modello della Memoria
• Memoria Stabile - resiste ai fallimenti di
sistema
• Buffer (volatile) - contiene copie di alcune
pagine, che vanno perse in caso di fallimenti
Fix, Flush
Use, Unfix
Read, Write
Database
Log
Buffer Manager
Read, Write
Buffer
Buffer Manager
• Fornisce primitive per accedere al buffer
• Fix carica una pagina nel buffer (la
pagina diventa valida)
• Politica no-steal = mai deallocare
pagine attive
• Use accede ad una pagina valida
Buffer Manager
• Unfix rende una pagina non piu’ valida
• Politica no-force = non riscrivere nel
DB tutte le pagine attive al commit
• Flush periodicamente riscrive nel DB le
pagine non piu’ valide
• Force trasferisce in modo sincrono una
pagina dal buffer al DB (transazione
sospesa fino a fine trasferimento)
Il LOG
• LOG: file sequenziale del gestore
dell’affidabilità
 scritto in memoria stabile
 e’ una registrazione delle attivita’ del
sistema
Checkpoint
• operazione periodica coordinata con
buffer-manager
 flush di tutte le pagine di transazioni terminate
 registrazione identificatori transazioni in corso
 non si accettano commit durante il
checkpoint
 si scrive in modo sincrono (force) l’elenco
transazioni attive nel LOG
 formato del record CKPT(T1,...,Tn)
DUMP
• copia completa del DB, fatta quando il
sistema non è operativo (non ci sono
transazioni attive)
 copia memorizzata su memoria stabile
(backup )
 record di dump nel LOG
 formato record DUMP(C) dove C è il
dispositivo di backup
Organizzazione del LOG
• Record del LOG
 di transazione
 di sistema (checkpoint, DUMP)
• Record di TRANSAZIONE:
 le transazioni registrano nel LOG le operazioni,
nell’ordine in cui le effettuano
 begin: record
B(T)
 commit/abort
C(T), A(T)
 T e’ l’identificatore della transazione
Organizzazione del LOG
Record di UPDATE
 identificatore transazione T
 identificatore oggetto O
 valore di O prima della modifica, before state
 valore di O dopo la modifica, after state
 U(T,O,BS,AS)
Organizzazione del LOG
Record di DELETE
 identificatore transazione T
 identificatore oggetto O
 valore di O prima della cancellazione, before state
 D(T,O,BS)
Organizzazione del LOG
Record di INSERT
 identificatore transazione T
 identificatore oggetto O
 valore di O dopo l’inserzione, after state
 I(T,O,AS)
UNDO e REDO
 UNDO : si ricopia BS su O,
–INSERT: si cancella O
 REDO : si ricopia AS su O
–DELETE: si cancella O
 UNDO e REDO sono idempotenti
 UNDO(UNDO(A)) = UNDO(A)
 REDO(REDO(A)) = REDO(A)
• Utile se errori durante il ripristino
Gestione delle Transazioni
 Regola WAL: Write Ahed Log
• BS scritta nel LOG prima di operare nella BD
>>> permette UNDO operazioni se no commit
 Regola Commit-Precedenza
• AS nel LOG prima del COMMIT
>>> permette REDO operazioni se problema dopo
commit (in no force)
Gestione dei Guasti
Guasto transitorio:
perso il contenuto del buffer
 resta il LOG
– RIPRESA A CALDO (warm restart)
Guasto permanente ad un disco:
 resta il LOG (assunzione memoria stabile)
– RIPRESA A FREDDO (cold restart)
Ripresa a caldo
 Si cerca ultimo checkpoint nel LOG
 Si decidono transazioni da rifare (insieme di
REDO) e disfare (insieme di UNDO)
 UNDO: transazioni attive al checkpoint
 REDO: inizialmente vuoto
 Si scorre il LOG:
 B(T) => T in UNDO
 C(T) => T in REDO
 Si applicano UNDO e REDO
Ripresa a Freddo
 Si usa l’ultimo DUMP per ripristinare uno stato
stabile della BD
 si ripercorre il LOG rifacendo tutte le azioni
successive al DUMP
 si fa ripresa a caldo dall’ultimo checkpoint
Ottimizzazioni User-Level
• Se la frequenza dei checkpoint si puo’
variare, regolarla mediante esperimenti
• Partitionare il DB su piu’ dischi per ridurre
il tempo di restart
Media Failures
• Un media failure e’ la perdita di parte della
memoria stabile
• La maggior parte dei dischi ha MTBF a piu’ di
10 anni, ma su 10 dischi...
• E’ importante avere dischi “shadow”, ossia un
disco duplicato che faccia da copia “ombra’
della memoria stabile
– Le Write vanno su entrambe le copie.
– Le Read vanno su una sola copia (in alternanza,
per efficienza)
RAID
• RAID - redundant array of inexpensive disks
– Array ridondante di dischi di basso costo
– Si basa su un array di N dischi in parallelo
– Soluzione ancora piu’ sicura rispetto al disco ombra
...
M blocchi dati
...
N-M blocchi di
correzione errore
Dove Usare Dischi Ridondanti?
• Preferibilmente sia per il DB che per il LOG
• Ma almeno per il LOG
– in un algoritmo di UNDO, e’ l’unico modo di
avere before images sicure
– in un algoritmo di REDO, e’ l’unico modo di
avere after images sicure
• Se non si ha almeno un disco ombra per il LOG,
il sistema ha un grosso punto debole
TP Monitors
(Transaction Processing Monitors)
Stefania Costantini
Architettura Client-Server
Utente finale
Presentation Manager
Front-End
(Client)
richieste
Workflow Control
(gestisce le richieste)
Transaction Program
Database Server
Back-End
(Server)
Cosa fa un TP Monitor
• TP Monitor = Transaction Processing Monitor =
Controllore dell’elaborazione delle Transazioni
• Una richiesta e’ un messaggio che descrive una unita’
di lavoro che il sistema deve eseguire.
• Un TP monitor coordina il flusso di richieste di
esecuzione di transazioni provenienti da varie fonti
(terminali e programmi applicativi)
Cosa fa un TP Monitor
• Struttura fondamentale:
– Traduce l’input (proveniente da form/menu, o da
un’istruzione in qualche linguaggio) in forma
standard
– Determina il tipo di transazione
– Fa partire la transazione
– Restituisce in forma opportuna l’output della
transazione
Architettura 3-Tier
di un TP Monitor
• Gli elementi dello schema possono essere distribuiti in
rete
Messaggio
Presentation Server
di richiesta
Code
Controllore di Workflow
Transaction Server
Rete
Transaction Server
Architettura 3-Tier
• La struttura dell’applicazione ricalca la struttura
del sistema
• Elementi del TP Monitor in un’architettura 3Tier:
– Presentation server : forms/menus, validazione
degli input (password, connessione sicura)
– Workflow controller : data una richiesta, produce la
chiamata al programma corretto
– Transaction server : esegue le richieste
Presentation Server
• Presentation independence - l’applicazione e’
indipendente dal tipo di dispositivo di i/o
– terminale, ma anche telefono cellulare o lettore di
codici a barre, o di carte di credito
• Il Presentation server ha due livelli:
– Raccogliere gli input
– Costruire le richieste
Autenticazione
• Autenticazione : determinare l’identita’
dell’utente e/o del dispositivo
– Il sistema client puo’ effettuare l’autenticazione, che
comunque il server effettua nuovamente (non si
fida dei client)
– Encryption della comunicazione client/server
opportuno
• Occorrono funzioni di sistema per creare
accounts, initializzare passwords, assegnare
ore di accesso
• E’ una parte importante dello sviluppo di
applicazioni TP
Workflow Controller
• Routing - Mappa il tipo di richiesta nel network
id del server che potra’ elaborarla, e invia la
risposta al client
• Gestisce errori ed eccezioni
Transaction Server
• Transaction server - programma applicativo
che effettua il “real work” dell’elaborazione
delle richieste
• Per portabilita’, e’ opportuno che sia scritto in
un linguaggio di programmazione standard (C,
C++, Java, COBOL) interfacciato con un Data
Manipulation Language standard (SQL)
Basi di Dati e Web
Stefania Costantini
Basi di dati e Sistemi Informativi
Transazioni su Internet
• Web browser = presentation manager
• Messaggio dal web browser al server = richiesta di
transazione su sistema (Transaction server) di cui si
da’ l’URL
• http = protocollo di comunicazione client/server
• Web server = include il workflow controller
• 3-Tier su Web:
– Presentation manager su client
– Workflow controller su server
– Transaction server molteplici, distribuiti su Internet
TP Monitor per Internet
• Il web server deve operare da workflow
controller. I transaction server sono in generale
remoti.
TP system
Web
browser
Trad. URL
Workflow
Controller
Web Server
Transaction
Server
DB Server
• TP monitors and DB servers attualmente sono
sempre piu’ spesso integrati nei Web server
Architettura tradizionale
• Sistema/Programma dove si vuole
eseguire la transazione : gateway
• CGI (Common gateway Interface):
programma chiamato dal server
• CGI fornisce richiesta e parametri al
gateway (nel nostro caso al TP system)