Tecnologia di un Database Server

S. CostantiniDispensa 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 SistemaTransazione 1 Transazione N

DatabaseServer

Bot,SQL QueriesCommit, Abort

Ottimizzatore QueryEsecutore Query

SchedulerBuffer 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

trasferimento effettivo delle pagine

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 B-alberi

Hashing• L’hashing usa una funzione H:VB, 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

Ki Pi Ki+1K1 P1 Kn-1 Pn. . . . . .

K´i P´i K´i+1K´1 P´1 K´n-1 P´n. . . . . .

• 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

Esempio n=3127 496

14 83 221 352

127 145 189 221 245 320

521 690

352 353 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 17X

15 19

12 14

X

15 17

Per inserire la chiave 15• si spezza la foglia• nel padre, [0, 19)diventa [0, 15) e [15, 19)• se il padre e’ pieno, bisogna spezzarlo (in modo simile)• l’albero resta automaticamentebilanciato

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

19 --

12 14 17

P

CX

15 19

12 14

X

15 17

P

C´C

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?

• Il maggior problema e’ il software• Environment - incendi, terremoti, vandalismi,

mancanza di elettricita’, guasto al condizionatore• system management - manutenzione, configurazione

Tandem ‘89 Tandem ‘85 AT&T/ESS ‘85Environment 7% 14%Hardware 8% 18% Subtotal 15% 32% 20%system Mgmt 21% 42% 30%Software 64% 25% 50%

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

DatabaseLog

Read, Write

Fix, FlushUse, Unfix

Buffer Manager

Buffer

Read, Write

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

Presentation Manager

Workflow Control(gestisce le richieste)

Database Server

Front-End(Client)

Back-End(Server)

Utente finale

Transaction Program

richieste

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

Presentation Server

Controllore di Workflow

Transaction Server Transaction Server

Rete

Richieste

Messaggiodi richiesta

Architettura 3-Tierdi un TP Monitor

• Gli elementi dello schema possono essere distribuiti in rete

Code

Architettura 3-Tier

• La struttura dell’applicazione ricalca la struttura del sistema

• Elementi del TP Monitor in un’architettura 3-Tier:– 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 CostantiniBasi 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.

Webbrowser

Trad. URLWorkflowController

TP system

Web Server

TransactionServer

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)