Tehnici DE Reorganizare A Bazelor DE Date

TEHNICI DE REORGANIZARE A BAZELOR

DE DATE

INTRODUCERE

Reorganizarea unei baze de date este o schimbare a unor aspecte ale aranjamentului fizic și/sau logic al bazei de date. Un exemplu de reorganizare este restaurarea de clustering, care este practica de stocare de instanțe aproape una de alta dacă îndeplinesc anumite criterii. Pe parcursul mai multor tipuri de reorganizare, datele din zona reorganizată sunt deconectate sau parțial disponibile; utilizatorii nu pot actualiza (de multe ori nu pot nici măcar interoga) datele din această zonă. Figura 1 prezintă o posibilă programare tradițională de activități pentru o bază de date. Linia orizontală reprezintă timpul. De obicei (pe parcursul perioadelor marcate ”OPERAȚII”), utilizatorii pot accesa baza de date. Pe parcursul perioadei marcate ”FEREASTRA DE ÎNTREȚINERE”, baza de date poate fi deconectată pentru proceduri ca reorganizarea offline.

Fig. 1. Programarea reorganizării offline în timpul unei ferestre de întreținere

Totuși, o bază de date extrem de disponibilă (o bază de date care ar trebui să fie disponibilă 24 de ore pe zi, 7 zile pe săptămână, ori de câte ori este posibil) nu ar trebui să poată fi deconectată pe perioade semnificative. Disponibilitatea ridicată poate micșora fereastra de întreținere sub timpul necesar pentru reorganizare, ca săgeata cu vârful în stânga din Figura 1. Chiar dacă o bază de date nu este extrem de disponibilă, reorganizarea unei baze de date foarte mari poate necesita mult mai mult decât o anumită perioadă deconectată maximă tolerabilă, care este, fereastra de întreținere, ca săgeata cu vârful spre dreapta din partea de jos. Perioada maximă tolerabilă de indisponibilitate este specifică aplicației. Conform unui grup de clienți de baze de date, perioada maximă tolerabilă poate varia între 0 și 5 ore. Aceste considerații apelează pentru capacitatea de a reorganiza o bază de date online (în același timp cu utilizarea, treptat în timpul activităților utilizatorilor, sau interpretativ), astfel încât utilizatorii pot interoga și actualiza baza de date în timpul celor mai multe sau tuturor fazelor reorganizării.

Reorganizarea în general se referă la subiecte care se aplică atât reorganizării offline, cât și reorganizării online. Se identifică 3 categorii generale de reorganizare (întreținere, redefinire fizică și redefinire logică), fiecare dintre acestea poate fi împărțită în mai multe categorii specifice.

Întreținerea înseamnă restaurarea aranjamentului fizic al instanțelor de date fără a schimba definiția bazei de date. Acest articol folosește, de obicei, instanța de date pentru a se referi la o înregistrare în stocarea persistentă, nu în stocarea principală după recuperare. În mai multe organizații de stocare, actualizările utilizatorilor pot provoca degradarea structurală, care este rearanjarea fizică a instanțelor de date într-un mod care provoacă degradarea performanței sau epuizarea alocării de stocare. Degradarea performanței înseamnă o creștere în timpul de răspuns al utilizatorilor și/sau o scădere în transfer. Exemple de întreținere: restaurarea de clustering și colectarea gunoiului pentru stocarea persistentă. Întreținerea apare în mod repetat (periodic sau la cerere).

Redefinirea fizică înseamnă schimbarea definiției fizice a bazei de date și în mod obișnuit, include eventuala schimbare a instanțelor de date pentru a se potrivi cu noua definiție. Exemplele de redefinire fizică includ: (1) construirea, eliminarea sau redenumirea unui indice non-unic și (2) conversia între indexare și hashing.

Dacă un tip de reorganizare păstrează definiția fizică inițială de bază, dar schimbă valorile parametrilor acestei definiții, atunci reorganizarea s-ar putea potrivi în oricare categorie de mai sus (întreținere sau redefinire fizică).

Redefinirea logică (uneori numită schema de evoluție sau restructurare) înseamnă schimbarea definiției logice a bazei de date. Schimbarea unei definiții logice, uneori, necesită, schimbarea instanțelor de date, definiției fizice, metodelor obiectelor și programelor aplicație. Exemple de redefinire logică: adăugarea, ștergerea, combinarea, divizarea sau redenumirea coloanelor (sau tabele), schimbarea reprezentării logice a unei coloane (ex. din inch în centimetri), adăugarea, ștergerea sau redenumirea unei metode, schimbarea ierarhiei moștenite a claselor obiect și schimbarea unei relații din unu-la-mulți în mulți-la-mulți. Acest articol folosește termeni și exemple din modele de date specifice (relațional, orientat-obiect, relație-entitate, ierarhic și CODASYL), dar conceptele prezentate se pot aplica la mai multe modele de date. Dacă o bază de date are nevoie de mai multe tipuri de reorganizare, se pot efectua împreună aceste tipuri, pentru a economisi timp. Pentru unele tipuri de redefinire, un sistem de management al bazei de date ar putea verifica imediat cererea redefinirii, dar amână reorganizarea instanțelor de date până la următoarea întreținere [Friske 2004b].

Se descriu tehnicile și se clasifică lucrarea despre reorganizarea online în două ramuri. O ramură implică categorii specifice de reorganizare, de exemplu: (1) restaurare de clustering și (2) conversie între indexare și hashing. O altă ramură implică probleme, de exemplu: (1) utilizarea partițiilor și (2) referințe la datele care s-au mutat, unde fiecare problemă se poate aplica la mai multe categorii specifice. Acest articol folosește ambele ramuri.

Capitolul I prezintă cerințe pentru reorganizarea online, adică aplicații care necesită reorganizare online și caracteristici necesare strategiilor și analizează problemele care apar în reorganizarea online. Problemele, dintre care cele mai multe implică compromisuri, includ utilizarea partițiilor, procesul care reorganizează, reorganizarea prin copiere la stocarea recent alocată, utilizarea de fișiere diferențiale, referințe la datele care s-au mutat, probleme generale în performanță și activarea întreținerii. Cerințele și problemele pot fi o listă de verificare parțială pentru designul strategiilor pentru reorganizarea online.

Următoarele două capitole descriu strategii online pentru categorii specifice de reorganizare în cadrul celor trei categorii mai generale (întreținere, redefinire fizică și redefinire logică). Discuțiile despre aceste strategii utilizează cerințele generice și problemele Capitolului I și mai puține probleme generice. Deoarece discuțiile includ implicit analizele și compromisurile pe care secțiunile anterioare le prezintă, problemele generice asigură o legătură între strategiile pentru diferite categorii ale reorganizării și problemele evită redundanța printre descrierile diferitelor strategii care împărtășesc o rezoluție a unei probleme. Capitolul II prezintă categoriile specifice în cadrul întreținerii, care includ: restaurarea de clustering, reorganizarea unui indice, reechilibrarea datelor paralele sau distribuite, colectarea gunoiului pentru stocarea persistentă și curățarea (recuperare de spațiu) într-un sistem de fișiere jurnal structurat. Capitolul III discută: (1) redefinirea fizică care include: construirea indicilor, conversia între arbore B+ și fișiere hash liniare și redefinirea partițiilor și (2) redefinirea logică, de exemplu, adăugarea coloanelor și schimbarea ierarhiei moștenite a claselor de obiecte. În cadrul redefinirii logice, discuțiile includ interpretarea și reorganizarea incrementală în timpul activităților utilizatorilor și utilizarea unui proces de fundal pentru reorganizare. Multe dintre strategiile pentru reorganizarea online au apărut în contexte de cercetare și în contexte comerciale. Pentru fiecare subiect individual, se vor prezenta tehnici pentru reorganizarea online.

CAPITOLUL I

CONDIDERAȚII PRIVIND REORGANIZAREA ONLINE A

BAZELOR DE DATE

CERINȚE PENTRU REORGANIZAREA ONLINE

Aplicații care necesită reorganizarea online

Pentru unele baze de date extrem de disponibile, deconectarea oricărei părți a bazei de date pe o perioadă semnificativă poate cauza o pierdere financiară semnificativă. Unele organizații, de exemplu, birourile de credit, pot evalua costul monetar de indisponibilitate al unei baze de date pe o perioadă, deoarece trasează activitățile concurenților în timpul perioadelor de indisponibilitate a propriilor baze de date. Dacă o bază de date care servește comerțului electronic este deconectată, un client nu va primi rapid, răspuns pozitiv dintr-un click de mouse. Clientul poate apela apoi la un concurent.

O altă consecință a indisponibilității este neplăcerea. De exemplu, baza de date pentru rezervarea unui hotel aglomerat a fost deconectată timp de 17 ore pentru recompilarea înregistrărilor la un nou format de bază de date [Radosevich 1993]. În timpul recompilării, clienții sunând la numărul de telefon central pentru rezervări, li se spune să sune hotelele individuale.

Detaliile cerințelor pentru disponibilitate sunt specifice fiecărei aplicații și indisponibilitatea unor facilități poate avea consecințe grave, altele decât pierdere financiară sau neplăcere. De exemplu, Centrul Național de Informare Infracțiuni este disponibil 24 ore pe zi. Acesta conține informații la zi despre infracțiuni, cum ar fi furt de mașini. Permiterea interogărilor este simplă, dar permiterea eliminărilor necesită un efort suplimentar in design. Justificarea pentru efortul suplimentar este prevenirea situațiilor de acest gen: o mașină furată este recuperată în timpul reorganizării, proprietarul conduce degajat, și la scurt timp după aceea poliția vede mașina și eronat, arestează proprietarul, deoarece înregistrarea mașinii furate nu a fost încă eliminată.

Utilitățile, procesul de control, spitalele și forțele armate pot avea propriile lor cerințe pentru disponibilitate, cu consecințe foarte serioase de indisponibilitate. Chiar pentru aplicații mai puțin esențiale, mulți administratori de baze de date preferă disponibilitatea de 24 ore. Chiar și fără o preferință pentru disponibilitate de 24 ore, reorganizarea unei baze de date foarte mari poate solicita mult mai mult decât perioada deconectată maximă tolerabilă.

Caracteristici necesare strategiilor

Pentru a servi aplicații care necesită reorganizarea online, există mai multe caracteristici necesare strategiilor care efectuează reorganizarea online, în zonele de corectitudine, performanță și toleranța eroriilor [Sockut și Goldberg 1976, Sockut 1977].

Utilizatorii trebuie să poată interoga și actualiza corect. În mod similar, acțiunile reorganizării trebuie să fie corecte. Operația corectă necesită control concurență. Corectitudinea implică, de asemenea, ca reorganizarea și tranzacțiile utilizatorilor să fie în măsură să urmărească stadiul acțiunilor celorlalți pe dată când este necesar, de exemplu, să corecteze referințe la acea dată. Această urmărire poate duce la complexitate. În timpul reorganizării online, o tranzacție utilizator ar putea efectua anumite acțiuni de nivel scăzut ca să nu efectueze într-o execuție în serie, de exemplu, urmărirea pointerilor la structuri care s-au mutat din cauza reorganizării [Goodman și Shasha 1985; Shasha și Goodman 1988]. Similar, reorganizarea online ar putea avea nevoie de acțiuni încât reorganizarea offline nu, de exemplu, citirea actualizărilor utilizatorilor dintr-un jurnal.

Progresul prin reorganizare este o altă cerință de performanță. Dacă un proces (separat de activitățile utilizatorilor) execută în fundal să reorganizeze toate instanțele de date, procesul trebuie, în cele din urmă, să își completeze lucrarea. Un exemplu, presupune că reorganizarea include citirea actualizărilor salvate ale utilizatorilor dintr-un jurnal și aplicarea acestora la o copie reorganizată a datelor. Citirea reorganizării actualizărilor trebuie să ajungă din urmă scrierea utilizatorilor lor.

Pentru redefinirea logică sau fizică, cerința de mai sus pentru progres și completarea reorganizării este auto-explicativă. Pentru întreținere, s-au idermărească stadiul acțiunilor celorlalți pe dată când este necesar, de exemplu, să corecteze referințe la acea dată. Această urmărire poate duce la complexitate. În timpul reorganizării online, o tranzacție utilizator ar putea efectua anumite acțiuni de nivel scăzut ca să nu efectueze într-o execuție în serie, de exemplu, urmărirea pointerilor la structuri care s-au mutat din cauza reorganizării [Goodman și Shasha 1985; Shasha și Goodman 1988]. Similar, reorganizarea online ar putea avea nevoie de acțiuni încât reorganizarea offline nu, de exemplu, citirea actualizărilor utilizatorilor dintr-un jurnal.

Progresul prin reorganizare este o altă cerință de performanță. Dacă un proces (separat de activitățile utilizatorilor) execută în fundal să reorganizeze toate instanțele de date, procesul trebuie, în cele din urmă, să își completeze lucrarea. Un exemplu, presupune că reorganizarea include citirea actualizărilor salvate ale utilizatorilor dintr-un jurnal și aplicarea acestora la o copie reorganizată a datelor. Citirea reorganizării actualizărilor trebuie să ajungă din urmă scrierea utilizatorilor lor.

Pentru redefinirea logică sau fizică, cerința de mai sus pentru progres și completarea reorganizării este auto-explicativă. Pentru întreținere, s-au identificat aceste îmbunătățiri la cerință:

Pentru termen lung (inclusiv perioadele de reorganizare și perioadele fără reorganizare), rata netă de scădere a reorganizării în degradarea structurală trebuie să se potrivească cu rata netă de creștere a utilizatorilor în degradarea structural [Soderlund 1980; 1981a; 1981b]. Fără această proprietate, degradarea structurală și astfel, degradarea performanței, ar crește și în cele din urmă, devin permanent inacceptabile;

Pentru un proces de fundal care reorganizează, se definește completarea ca o trecere completă prin zona reorganizată. Noua degradare structurală poate să apară (înainte de completare) în structuri încât reorganizarea a procesat deja. Următoarea trecere a reorganizării poate elimina această nouă degradare, deși chiar o degradare mai nouă poate să apară (și să rămână după) în timpul acestei treceri următoare.

Pentru toleranța erorilor, datele trebuie să fie recuperabile în timpul reorganizării online. Exemple de relații între recuperare și reorganizarea online:

Reorganizarea prin copiere poate crea o copie de rezervă a noului, copie reorganizată a datelor. Această copie de rezervă este o bază pentru recuperare.

Amsaleg et al. [1995; 1999] impune constrângeri cu privire la colectarea gunoiului pentru a evita posibilele probleme care ar putea rezulta din interacțiuni între colectarea gunoiului și recuperare.

Dacă o tranzacție utilizator omite o inserție redundantă într-un indice deoarece reorganizarea a efectuat deja inserarea, se poate scrie totuși, un jurnal de intrare pentru inserarea omisă. Jurnalul de intrare asigură corectitudinea posibilei reveniri ulterioare a tranzacției, dacă o problemă apare.

Erori, de asemenea, ar putea apărea în acțiunile de reorganizare. Deși cele mai multe execuții de reorganizare pot completa fără a fi nevoie de repornire, reorganizarea trebuie să fie repornită dacă apare o eroare. Repornirea de la începutul reorganizării este acceptată, dar poate implica refacerea unei cantități mari de lucrare.

PROBLEME ÎN REORGANIZAREA ONLINE

Problemele care apar în proiectarea reorganizării online implică compromisuri și politici care necesită decizii. Acestea includ: utilizarea partițiilor, procesul care reorganizează (un proces de fundal sau activitățile utilizatorilor), reorganizarea prin copiere la noua stocare alocată, utilizarea fișierelor diferențiale, referințe la datele care s-au mutat, probleme generale în performanță și activarea întreținerii.

Utilizarea partițiilor

Unele SGBD-uri permit divizarea unui tabel sau a unei baze de date în partiții, care pot exista chiar în timp ce nu apare reorganizarea. O partiție poate fi o unitate a reorganizării online. De asemenea, poate fi o unitate a reorganizării offline sau alte utilități, în timpul utilizării sau reorganizării offline a altor partiții [Strickland et al. 1982] ; [Mohan 1993b]. Dacă un scop al reorganizării este de a îmbunătăți performanța, reorganizarea unei partiții poate beneficia de utilizatori treptat, înainte de finalizarea reorganizării a întregii baze de date.

O decizie de design este de a stabili granularitatea de partiționare. Se poate considera lipsa de partiționare ca un caz degenerat de partiționare, a cărui granularitate este un tabel întreg sau bază de date. Cu o granularitate destul de fină de partiționare, reorganizarea offline a unei partiții ar putea fi, la un moment dat, suficient de rapidă pentru a aproxima 24 ore de disponibilitate. Totuși, această abordare are unele dezavantaje. În unele SGBD-uri, ceea ce face granularitatea fină poate încetini traseul de accese ale utilizatorilor în zonele corespunzătoare și, de asemenea, poate crește spațiul total necesar pentru descriptorii de stocare ai partițiilor și probabilitatea ca zonele de creștere și zonele de contractare să fie în partiții diferite. Această creștere a probabilității, crește variația probabilă printre ratele de creștere ale partițiilor, crescând astfel cantitatea totală recomandată de spațiu liber pentru a rezerva în baza de date. De asemenea, reorganizarea offline, similar cu unele strategii pentru reorganizarea online, are o perioadă necesară de invalidare a activităților utilizatorilor (blocarea noilor activități și așteptarea ca activitățile existente să termine). Reorganizarea offline a unei partiții greu accesate ar putea bloca cel mai mult activitatea utilizator. În final, în câteva cazuri, reorganizarea necesită schimbări corespunzătoare în indici (dintre care unele ar putea să nu fie partiționate) sau în referințe încrucișate din alte partiții.

Indicii parțiali se referă doar la înregistrările care îndeplinesc condiții specificate [Stonebraker 1989]. Utilizarea unui indice parțial pentru a diviza un indice și / sau o zonă de date în partiții, permite reorganizarea și prin urmare, blocarea unei singure partiții la un moment dat [Stonebrake et al. 1988].

Procesul care reorganizează

Dacă reorganizarea schimbă, creează sau șterge instanțe de date, proiectantul reorganizării trebuie să aleagă, de asemenea, procesul (locul de control) care efectuează

aceste activități.

Abordări. S-au identificat două abordări pentru procesul pentru reorganizarea online. De asemenea, o a treia abordare este o alternativă la schimbarea instanțelor în stocarea persistentă.

Prima abordare este de a utiliza un reorganizator, care este un proces care execută în fundal (sau pe un procesor separat) pentru a străbate printr-o zonă și schimbă instanțele. Utilizatorii și reorganizatorul folosesc orice control de concurență necesar. Un reorganizator poate reorganiza în loc sau prin copiere. Amânarea unor sarcini la un reorganizator poate îmbunătăți performanța utilizator [Moitra et. al 1988]. Utilizarea unui proces de fundal scutește activitățile utilizator de muncă în plus și evită irosirea timpului inactiv al unui processor [Lampson 1984] .

A doua abordare este reorganizarea incrementală în timpul activităților utilizatorilor (de obicei, doar activitățile care fac referire la instanțele care necesită schimbare). Această abordare pe care unii o numesc reorganizare leneșă, poate încetini unele activități. Totuși, poate evita blocarea suplimentară și accesul suplimentar de date pentru anumite tipuri de reorganizare. Aceste avantaje sunt mai puțin aplicabile la reorganizarea care necesită accesul la mai multe pagini decât doar la paginile care conțin instanțele referință. De asemenea, reorganizarea incrementală evită disputa între un utilizator și un reorganizator, deși ar putea crește disputa între doi utilizatori. Mai poate evita schimbarea la instanțele care vor fi șterse (sau vor fi subiectul unei alte redefiniri) fără a fi citit întâi; schimbarea unor astfel de instanțe ar putea fi un efort irosit. De obicei, reorganizarea incrementală execută ca parte a unei tranzacții utilizator. O alternativă este de a reorganiza într-o tranzacție de sistem separată și de a avea așteptarea de tranzacție utilizator pentru tranzacția de sistem [Sun et al. 2005; Sun 2005].

A treia abordare, spre deosebire de primele două, este o alternativă la reorganizarea efectivă de instanțe în stocarea persistentă. În schimb, se interpretează instanțele ca utilizatorii să le acceseze (ex. prin materializarea de noi coloane). Interpretarea oferă utilizatorului aspectul de schimbare a instanțelor în mod corespunzător și nu primește baza de date deconectată. Din perspectiva utilizatorului, interpretarea poate constitui una din strategiile pentru reorganizarea online, în ciuda lipsei sale de schimbare la instanțe în stocarea persistentă. Reorganizarea produce efecte imediat după specificarea noii definiții. Totuși, interpretarea are un cost, și câteodată costul motivează eventuala schimbare la instanțe în stocarea persistentă.

Considerații pentru întreținere. Întreținerea poate reduce discul de intrare/ ieșire și concurența poate realiza transfer ridicat. Efectuarea întreținerii treptate în timpul unei activități utilizator, poate reduce concurența prin creșterea lungimii activității (ex. cu intrare/ ieșire suplimentară) și prin impunerea mai multor blocări. Amânarea unor sarcini de întreținere la un reorganizator poate scurta o activitate utilizator și astfel îmbunătățește transferul, dar amânarea (ex. prin crearea de overflow) ar putea încetini activitățile ulterioare. Câteva sarcini posibile de a amâna sunt: (1) reclamarea spațiului care este eliminat logic și (2) restabilirea de clustering.

Reorganizarea prin copiere

Dacă reorganizarea unei zone a unei baze de date schimbă instanțele de date preexistente, o altă decizie presupune reorganizarea zonei în loc versus reorganizarea prin copierea zonei la stocarea recent alocată. Figura 2 prezintă două abordări pentru reorganizarea în loc (A și B) și o abordare pentru reorganizarea prin copiere (C). Dreptunghiurile mici reprezintă paginile și un set de patru pagini alăturate în această figură simplă reprezintă zona reorganizată. Literele r până la u reprezintă locațiile instanțelor de date înainte de reorganizare și săgețile reprezintă mutarea sau copierea instanțelor de date.

Fig.2. Reorganizarea în loc și reorganizarea prin copiere

Reorganizarea în loc scrie zona reorganizată, dar nu construiește o nouă copie a întregii zone reorganizate, de exemplu, un table întreg:

În abordarea A pentru reorganizarea în loc, reorganizarea nu mută nicio instanță de date între pagini.

În abordarea B pentru reorganizarea în loc, reorganizarea mută grupuri de una sau mai multe instanțe de date între pagini, dar nu mută în mod necesar toate instanțele. Aici, o pagină ar putea fi atât originea mutării unei instanțe de date, cât și destinația mutării unei alte instanțe de date.

Ca abordare, C descrie: reorganizarea prin copiere poate implica descărcarea tuturor instanțelor din zonă (în special, din vechea copie a zonei) și reîncărcarea tuturor instanțelor într-o nouă copie a zonei în stocarea recent alocată. Aici, fiecare pagină poate fi originea copierii sau destinația copierii, dar nu ambele, deși o reorganizare târzie ar putea copia în direcția opusă. Abordarea C include comutarea acceselor utilizator din vechea copie la cea nouă. Reorganizarea prin copiere scrie noua copie a zonei reorganizată, dar nu și pe cea veche.

Există compromisuri între reorganizarea în loc și reorganizarea prin copiere. Dacă reorganizarea mută datele și utilizatorii eliberează unele blocări înainte de sfârșitul unei tranzacții (astfel activând un reorganizator să opereze simultan pe datele blocate anterior), un avantaj al reorganizării prin copiere este simplu, asigurarea eficientă a corectitudinii. Acest avantaj este deosebit de important dacă reorganizarea include schimbarea atribuirii de înregistrări la pagini, ca în restaurarea de clustering.

Un alt avantaj al reorganizării prin copiere este că aceasta ar putea cauza o dispută mai mică cu utilizatorii și astfel, degradarea mai mică a performanței utilizatorilor în timpul copierii, dacă citește, dar nu scrie copia pe care utilizatorii o accesează. Controlul de concurență poate fi, de asemenea, mai simplu. Alt avantaj al reorganizării prin copierea unui table întreg (și reconstruirea tuturor indicilor) este evitarea necesității de a schimba referințe individuale în indicii preexistenți când datele au fost mutate.

Un dezavantaj al reorganizării prin copiere este că poate solicita mai mult spațiu pe disc pentru zona reorganizată. De asemenea, copierea poate solicita o tranziție între direcția acceselor utilizatorilor în vechea copie și direcția lor în noua copie. În multe implementări, un dezavantaj al copierii este o perioadă de acces limitat sau inexistent prin utilizatori în timpul tranziției. În unele cazuri, un alt dezavantaj al reorganizării prin copiere implică o întârziere în beneficiul utilizatorilor (o întârziere care le oferă acces la o zonă reorganizată). Reorganizarea în loc ar putea începe să beneficieze imediat de utilizatori, precum sistemul începe să reorganizeze zona la care accesează utilizatorii. În contrast, pentru reorganizarea prin copiere, beneficiul începe numai după tranziția menționată mai sus, care are loc aproape de sfârșitul reorganizării în unele strategii.

Tehnici pentru reorganizarea prin copiere.

Prima tehnică include două alternative, numite copiere simplă și descărcare și reîncărcare simplă:

Se copiază (în formă reorganizată) din copia inițială la o nouă copie. Ambele copii sunt în format normal al SGBD-ului, care este, un format potrivit pentru utilizatori să acceseze.

Se descarcă din copia inițială la o copie de descărcare; apoi se reîncarcă (în formă reorganizată) din copia de descărcare la o nouă copie. Datele din copia de descărcare nu sunt neapărat necesare în formatul normal al SGBD-ului. De asemenea, nu este necesar să fie reorganizate.

A doua tehnică presupune replicarea temporară a zonei de a fi reorganizată, pentru o bază de date care nu este replicată în mod obișnuit. Se copiază zona fără reorganizare; apoi, se reorganizează copia offline (în loc sau prin reorganizarea altei copi). Copia este în formatul normal al SGBD-ului, deși se va reorganiza copia înainte de a permite utilizatorilor să o acceseze. Lipsa de reorganizare a versiunii inițiale a copiei distinge această tehnică de prima tehnică.

A treia tehnică se aplică la o bază de date replicată permanent. Se reorganizează o copie la un moment dat offline (în loc sau prin reorganizarea altei copi). Permanența replicării distinge această tehnică de a doua tehnică.

Reorganizarea neclară. Această strategie permite interogări și actualizări aproape în timpul tuturor etapelor, inclusiv o etapă a aplicării jurnal. Etapele implică o perioadă de acces doar de interogare și o perioadă offline. Acestea sunt:

Se înregistrează poziția curentă a jurnalului. Utilizatorii pot interoga și actualiza în timpul acestui pas.

Se descarcă copia veche (inițială) a zonei reorganizate și se reîncarcă într-o nouă copie în formă reorganizată. Se poate copia direct în loc de descărcarea într-un fișier și reîncărcarea din acel fișier. În același timp, utilizatorii pot folosi facilitățile obișnuite ale SGBD-ului pentru a interoga și actualiza copia veche. În partea de sus a Figurii 3 se prezintă acest pas. Interogarea și actualizarea utilizatorilor constă în copierea datelor între baza de date (în special, copia veche) și variabilele din programele utilizatorilor (se arată în figură ca ”datele utilizatorilor”). În jurnal, facilitățile normale ale SGBD-ului adaugă, de asemenea, intrări jurnal care corespund actualizărilor utilizatorilor.

Se înregistrează din nou poziția curentă a jurnalului. Citește jurnalul (între cele două poziții înregistrate) și aplică intrările jurnal la noua copie. Această aplicație a jurnalului va reflecta actualizările utilizatorilor care au avut loc la pasul (2). Utilizatorii pot interoga și actualiza copia veche în timpul acestui pas.

Se invalidează actualizările copiei vechi, în timp ce continuă să se permită interogări ale copiei vechi.

Se înregistrează din nou poziția curentă a jurnalului, se citește și se aplică din nou jurnalul (între cele două poziții înregistrate mai recent). Este nevoie de acest pas suplimentar de aplicație doar să se ocupe de actualizări care au avut loc după ce a început Pasul 3. Utilizatorii pot interoga copia veche în timpul acestui pas.

Se invalidează interogările copiei vechi.

Se schimbă maparea logică-la-fizică, de exemplu, prin schimbul de nume al fișierelor care stau la baza vechilor și noilor copii ale zonei reorganizate. Zona este offline în timpul acestui pas. După ce s-a schimbat maparea, accesele viitoare ale utilizatorilor vor intra în noua copie, ca în figură.

Se creează o copie de rezervă a noii copi, ca o bază pentru recuperarea viitoare și se permite utilizatorilor să interogheze și să actualizeze noua copie.

Se șterge copia veche.

Un dezavantaj al reorganizării neclare este faptul că numărul de intrări jurnal, nu încă aplicate, va crește dacă se va suspenda reorganizarea, de exemplu, în timpul unei perioade de utilizare vârf. O altă preocupare cu utilizarea unui jurnal este că un jurnal ar putea omite în mod obișnuit, unele informații de care reorganizarea are nevoie. O alternativă la utilizarea jurnalului regulat este de a defini un declanșator care înregistrează actualizările zonei reorganizate. Reorganizarea neclară utilizează actualizările înregistrate.

Fig. 3. Câteva etape ale reorganizării neclare

Utilizarea de fișiere diferențiale

O altă decizie implică unde să se scrie actualizările utilizatorilor din zona reorganizată. O posibilitate este de a le scrie imediat în zona principal (primară) a bazei de date. O altă posibilitate este de a le salva într-un fișier diferențial în timpul reorganizării și de a le scrie mai târziu în zona principală. Folosind un fișier diferențial se poate simplifica și accelera prelucrarea reorganizatorului zonei principale. Totuși, se adaugă complexitate (în prelucrarea accesului utilizator), spațiu supraîncărcat și uneori timp supraîncărcat (pentru utilizatori). Un alt dezavantaj al fișierului diferențial este că, dacă se suspendă reorganizarea, de exemplu, în timpul unei perioade de utilizare vârf, fișierul diferențial crește.

Zona de date principală conține datele de un anumit timp și un fișier diferențial stochează orice actualizări care au loc mai târziu. O schemă de filtrare (pentru a localiza înregistrări) utilizează un set de funcții hashing care mapează identificatorii de înregistrare din adrese într-o serie de biți în stocarea principală (inițial toate 0). Un identificator de înregistrare (sau prescurtat, RID) este un număr care identifică o înregistrare într-o bază de date. La actualizarea unei înregistrări, sistemul setează toți biții mapați la 1 și actualizarea merge în fișierul diferențial (nu în zona principală). Pentru a citi o înregistrare, dată de un RID, sistemul își testează întâi biții trasați. Dacă toți acești biți sunt 1, înregistrarea este probabil în fișierul diferențial, care caută sistemul. Dacă această căutare este fără succes, apoi unirea hashing-ului a unuia sau mai multor RID-uri ale înregistrărilor ar trebui să se ciocnească cu hashing-ul acestui RID al înregistrării, astfel încât sistemul caută atunci zona principală. Dacă nu toți biții mapați sunt 1, sistemul caută doar zona principală, unde înregistrarea (dacă există) se află cu siguranță. Sistemul mută eventual conținutul fișierului diferențial în zona principală și resetează toți biții [Severance și Lohman 1976; Lohman 1977].

În contextul reorganizării, un jurnal și un fișier diferențial au mai multe asemănări. Fiecare dintre ele este un fișier care este separat de zona principală a bazei de date. Fiecare stochează actualizările utilizatorilor. După reorganizarea zonei principale, se pot aplica actualizările stocate la zona principală.

Totuși, un jurnal și un fișier diferențial au și câteva diferențe. Multe dintre diferențe rezultă din faptul că un jurnal este proiectat pentru recuperare, nu reorganizare, în timp ce un fișier diferențial poate fi proiectat pentru un scop specific diferit, de exemplu, un anumit tip de reorganizare. Aceste diferențe sunt:

O mare parte a datelor dintr-o intrare jurnal obișnuită este redundantă cu datele din zona principală a bazei de date (până la posibila actualizare ulterioară a acestor date în zona principală). În contrast, datele dntr-un fișier diferențial nu există încă în zona principal a bazei de date.

Un jurnal obișnuit conține atât anularea, cât și refacerea informației, dar un fișier diferențial conține de obicei doar echivalentul refacerii.

Activitățile utilizator interoghează, de obicei, un fișier diferențial (când este necesar), dar nu un jurnal. Prin urmare, un tratament al SGBD-ului unui jurnal diferă, de obicei, de tratamentul zonei principale. Tratamentul unui fișier diferențial este mult mai probabil să semene cu tratamentul zonei principale.

Un jurnal reflectă toate actualizările, nu doar cele care sunt relevante la reorganizare. Un fișier diferențial specializat nu trebuie să reflecte actualizări irelevante.

Un SGBD menține, de obicei, un jurnal chiar și fără reorganizare online. Totuși, SGBD menține un fișier diferențial doar dacă acest SGBD are un motiv special pentru asta.

Referințe la datele care s-au mutat

O altă problemă care apare în unele cazuri, este manipularea de referințe care indică înregistrărilor de date că reorganizarea online a mutat. De exemplu, referințele pot apărea în alte înregistrări de date, într-un indice, într-un jurnal sau în procesarea unei activități utilizator. Dacă reorganizarea mută o înregistrare de date, SGBD trebuie să asigure că referințele la înregistrarea de date, în final, merg la locația noii înregistrări. Acest subiect apare mai ales în timpul întreținerii, dar se poate aplica și la redefinire.

Unele SGBD-uri atribuie un RID pentru fiecare înregistrare. De exemplu, un RID ar putea fi alcătuit dintr-un număr de pagină și un identificator în cadrul paginii. Indicii și alte stucturi pot folosi RID-uri la înregistrările de referință. În timpul utilizării normale, când nu are loc nicio reorganizare, RID-ul unei înregistrări este stabil. În unele SGBD-uri, chiar compactarea unei pagini (prin mutarea înregistrărilor în cadrul paginii) nu schimbă niciun RID. Totuși, reorganizarea online poate elimina această stabilitate prin mutarea înregistrărilor între pagini și astfel, schimbându-le RID-urile; o referință neschimbată la o înregistrare mutată devine invalidă.

Utilizarea tabelelor de mapare. Tabelele de mapare sunt structuri care pot suporta schimbarea de referințe. Vor fi prezentate două tipuri de tabele de mapare (logic-la-fizic și fizic-la fizic) pentru schimbarea referințelor.

Un tabel de mapare logic-la fizic mapează de la identificatorii logici, care nu se schimbă în timpul reorganizării, la identificatorii fizici curenți, care se schimbă. Un identificator logic ar putea fi valoarea unei chei unice, un identificator obiect, un identificator al unui vas hash sau un număr de bloc logic. Un identificator fizic ar putea fi un RID, un număr de disc sau locația unui bloc fizic. Referințele din afara tabelului de mapare utilizează identificatorii logici. De obicei, un tabel de mapare logic-la-fizic conține o intrare pentru fiecare înregistrare, chiar dacă reorganizarea nu a mutat înregistrarea.

Pentru a obține efectul de schimbare al tuturor referințelor când o înregistrare se mută, sistemul schimbă pur și simplu identificatorul fizic în intrarea înregistrării în tabelul de mapare logic-la-fizic. Părțile A și B din Figura 4 arată parte a conținutului unui tabel de mapare logic-la-fizic. În acest exemplu, reorganizarea mută o înregistrare (care are identificator logic L9) dintr-o locație fizică veche (cu identificatorul fizic OP1) la o nouă locație fizică (cu identificatorul fizic NP2). Partea A a figurii reprezintă tabelul de mapare înainte de mutarea înregistrării și partea B, după mutare. Pentru reorganizarea prin copiere, o alternativă de a schimba identificatorul fizic este să se utilizeze două tabele de mapare (vechi și nou).

Un tabel de mapare logic-la-fizic are avantaje și dezavantaje. Un dezavantaj, mai ales atunci când un tabel nu se potrivește în stocarea principală, este un nivel de indirecție în acces. Un alt dezavantaj este spațiul, cu excepția cazului în care tabelul de mapare este un indice care ar exista pentru eficiență sau unicitate chiar fără reorganizare online. Aceste dezavantaje se aplică în orice moment, nu doar în timpul reorganizării. Totuși schimbarea de referințe este simplă și eficientă și McIver și King [1994] notează o serie de alte avantaje ale tabelului de mapare: (1) După ce reorganizarea și-a actualizat intrarea tabelului de mapare pentru o înregistrare mutată, sistemul poate întrerupe în siguranță reorganizarea fără schimbarea fizică de referințe în alte obiecte. (2) Reorganizarea evită accesarea paginilor (în alte obiecte) care conțin referințe. (3) Reorganizarea se poate concentra pe o regiune limitată a bazei de date.

Fig. 4. Utilizarea tabelelor de mapare

Multe sisteme nu utilizează tabelul de mapare logic-la-fizic. Ele pot utiliza tabelul de mapare fizic-la-fizic, care mapează de la identificatori fizici vechi la identificatori fizici noi. Din nou, o implementare poate utiliza RID-uri sau o varietate de alți identificatori ca identificatorii fizici. De obicei, un tabel de mapare fizic-la-fizic conține o intrare pentru o înregistrare numai dacă reorganizarea a mutat înregistrarea. Când se mută o înregistrare, sistemul inserează o intrare în tabelul de mapare fizic-la-fizic, pentru a sprijini eventuala schimbare de referințe. Partea C din Figura 4 reprezintă tabelul de mapare înainte de mutarea unei înregistrări dintr-o locație fizică veche OP1 la o locație fizică nouă NP2. Partea D reprezintă tabelul de mapare după mutare.

Probleme generale ale performanței

Multe dintre problemele de design afectează performanța. În continuare vor fi prezentate doar problemele generale, cum ar fi: subiecte de fundal privind performanța în timpul reorganizării online, politici referitoare la compromisuri între performanța utilizatorilor și performanța reorganizării, și criteriile pentru programarea de reorganizare online.

Fundal. De obicei, atât reorganizarea online, cât și tranzacțiile utilizator funcționează mai lent decât ar funcționa dacă s-ar fii executat separat. Câteva motive sunt:

Utilizatorii și reorganizarea concurează între ele pentru resurse, de exemplu, căi de intrare / ieșire, timp procesor, blocări și buffere (tampoane) în stocarea principală.

Reorganizarea ar putea muta unele date departe de prima locație pe care o activitate utilizator o caută.

Strategii care implică reorganizarea incrementală în timpul activităților utilizatorilor, cresc timpii scurși atât pentru aceste activități, cât și pentru finalizarea reorganizării.

Similar, strategii de reorganizare care implică interpretarea în timpul activităților utilizatorilor, cresc timpul de a executa aceste activități.

Unele strategii implică o etapă suplimentară de citire a reorganizării și prelucrare a actualizărilor utilizatorilor dintr-un jurnal sau un fișier diferențial.

Se presupune că se folosește o strategie de reorganizare în care reorganizarea produce structuri de date pentru a-și înregistra activitățile, de exemplu, mutarea datelor. Tranzacțiile utilizator sau un reorganizator consumă aceste structuri de date. Aici se pot suspenda activitățile de reorganizare care produc structurile, dacă alocarea depășește un prag și amenință să epuizeze stocarea. După consumarea structurilor sub un prag, se reia activitățile de reorganizare.

Compromisuri între utilizatori și reorganizare. Dacă un scop al reorganizării este de a beneficia de activități utilizator care se vor executa în viitorul apropiat, viteza reorganizării poate fi un element important, deoarece încetinind reorganizarea, se va întârzia beneficiul la aceste activități. Dacă reorganizarea este doar pentru a beneficia de activități utilizator care se vor executa în viitorul îndepărtat, orice moment al finalizării reorganizării poate fi acceptat dacă precede timpul dorit introducerii acestor activități. Încetinirea reorganizării nu numai că întârzie finalizarea reorganizării, dar de asemenea, poate prelungi perioada în care reorganizarea online degradează performanța utilizatorilor.

Pentru a reduce degradarea reorganizării performanței utilizatorilor, o politică posibilă este de a favoriza utilizatorii mai mult decât reorganizatorul, când se alocă resurse. Câteva considerații specifice care se ocupă cu favorizarea utilizatorilor sunt:

Un reorganizator poate pune pauză între etapele sale, pentru a reduce competiția cu utilizatorii.

Un reorganizator poate folosi o granularitate fină de transfer de date sau de control concurență. Această politică reduce cantitatea de date care nu este disponibilă utilizatorilor și astfel, poate reduce timpul de răspuns pentru utilizatori.

Similar, o blocare a reorganizatorului poate avea o durată scurtă sau poate fi lipsită de utilizatori. Dacă reorganizatorul execută la o prioritate scăzută, achiziționarea de blocări de către reorganizator ar putea conduce la un convoi de utilizatori așteptând pentru reorganizator. Posibilele soluții pentru această problemă includ lipsirea reorganizatorului și creșterea priorității.

O altă resursă importantă este bufferul (tampon) în stocarea principală.

Cu toate astea, o politică a favorizării utilizatorilor încetinește reorganizarea. Pentru unele cazuri de întreținere, încetinirea reorganizării ar putea afecta chiar performanța utilizatorilor:

Un avantaj de a da reorganizatorului o prioritate egală în loc de o prioritate mai mică este reducerea duratei de întreținere, care scurtează perioada de concurență cu utilizatorii și accelerează reducerea degradării structurale.

Pentru întreținerea care face mai multă stocare disponibilă utilizatorilor, s-ar putea favoriza reorganizatorul, pentru a evita epuizarea stocării [Seltzer et al. 1993].

Favorizarea utilizatorilor ar putea înfometa chiar reorganizarea, cauzând o creștere în degradarea structurală și astfel, o creștere în degradarea performanței utilizatorilor [Bastani et al. 1986]. Când degradarea depășește un prag, se poate da reorganizării o prioritate mai mare [Breitbart et al. 1996; Vingralek et al. 1998].

Programarea reorganizării online. Câteva criterii posibile pentru programare [Sockut et al. 1997] implică caracteristici așteptate de aplicații:

Dacă volumul de muncă utilizator variază, s-ar putea reorganiza mai ales în perioadele relativ deteriorate. S-ar putea suspenda reorganizarea în timpul perioadelor de utilizare vârf. Această politică nu se aplică dacă volumul de muncă utilizator nu are nicio variație semnificativă. Această politică reduce numărul de utilizatori pe care reorganizarea întârzie și evită schimbarea performanței utilizatorilor din rău în mai rău în timpul utilizării vârf. De asemenea, poate accelera etapele individuale ale reorganizării prin reducerea concurenței dintre utilizatori. Dacă reorganizarea poate finaliza în cadrul unei perioade deteriorate, această politică poate reduce, de asemenea, citirea reorganizării actualizărilor utilizatorilor din jurnal (pentru strategiile de reorganizare care utilizează jurnalul în acest fel). Totuși, dacă reorganizarea necesită mai mult de o perioadă deteriorată, suspendarea încetinește finalizarea reorganizării, și pentru strategiile care citesc jurnalul, suspendarea crește foarte mult citirea totală necesară reorganizării actualizărilor utilizatorilor din jurnal.

Dacă toleranța de întârziere variază printre aplicații, s-ar putea reorganiza în principal în timpul executării aplicațiilor de înaltă toleranță. S-ar putea suspenda reorganizarea în timpul aplicațiilor de toleranță scăzută, pentru a evita iritarea utilizatorilor acestor aplicații.

Executarea unei tranzacții utilizator de lungă durată poate crește timpul necesar pentru tranzacțiile inactive. Prin urmare, dacă reorganizarea implică inactivarea, atunci programarea reorganizării online, atunci când nu sunt așteptate tranzacții de lungă durată pentru a se executa, poate accelera reorganizarea online.

Activarea întreținerii

O problemă care se referă îndeaproape la performanță este activarea întreținerii. Întreținerea trebuie sa aibă loc în mod repetat, iar dacă SGBD nu activează automat întreținerea, administratorul bazei de date trebuie să decidă dacă să activeze întreținerea. Un administrator ar putea activa întreținerea când degradarea depășește un prag sau la ore fixe (ex. weekend-uri alternative) fără a măsura degradarea de fiecare dată.

Activarea, care se aplică la întreținere și, probabil, la unele tipuri de redefinire fizică, se ocupă cu decizia dacă să se reorganizeze. În contrast, programarea reorganizării, se aplică la fel de bine la redefinirea fizică și logică, nu doar la întreținere. După ce s-a decis să se reorganizeze, programarea se ocupă cu decizia când să execute reorganizarea, de exemplu, pe timp de noapte.

Fig. 5. Timpul de răspuns așteptat al tranzacțiilor utilizator versus timpul scurs

Activarea întreținerii offline. Graficul A din Figura 5 arată timpul de răspuns așteptat de tranzacțiile utilizator versus timpul scurs, pentru un SGBD care utilizează întreținerea offline. Pentru simplitate, graficele din figură sunt stilizate; ele nu reprezintă exact un SGBD specific, bază de date, volum de muncă, tip de degradare structurală sau tip de întreținere, și ignoră creșterea în baza de date. De-a lungul timpului, degradarea structurală degradează performanța utilizatorilor și alocarea de stocare. Prin urmare, timpul de răspuns reprezentat în graficul A are o pantă pozitivă în timpul utilizării bazei de date (în timpul perioadelor marcate cu “U”). Alternativ, am putea reprezenta transferul, care ar avea o pantă negativă în timpul utilizării. Spre deosebire de această figură simplă, degradarea timpului de răspuns într-o bază de dată reală nu trebuie să fie liniară. În graficul A, după îndeplinirea unui criteriu (ex. degradarea structurală care depășește un prag), se activează întreținerea offline, care se execută în timpul unei perioade marcate în paranteze. După întreținere, timpul de răspuns trebuie să revină la o valoare scăzută și se reia ciclul de utilizare și întreținere. Desigur, întreținerea frecventă cauzează perioade offline frecvente, iar întreținerea rară permite o creștere ridicată în timpul de răspuns și, probabil, în cerințele de stocare.

Pentru SGBD-urile comerciale, recomandările de obicei implică criterii simple pentru activarea întreținerii offline. Administratorul bazei de date examinează statistici care măsoară degradarea structurală sau degradarea performanței. Dacă degradarea depășește un prag, administratorul activează întreținerea [Bracht et al. 1991; Smith 1994]. Pragul poate varia în funcție de caracteristicile bazei de date și toleranța aplicațiilor de degradare. Pentru a decide care partiții ale unei baze de date ar trebui să fie supuse întreținerii, este posibil să se alinieze partițiile, de exemplu, după cantitatea de fragmentare sau cantitatea așteptată de îmbunătățire în performanță [Plow et al. 2008].

Considerații pentru activarea întreținerii online. Graficul B din Figura 5 arată comportamentul posibil al timpului de răspuns așteptat de tranzacțiile utilizator versus timpul scurs, pentru un SGBD care utilizează întreținerea online în loc. Aici, degradarea performanței utilizatorilor are două cauze:

Degradarea structurală degradează performanța și alocarea de stocare. Prin urmare, timpul de răspuns reprezentat are o pantă pozitivă, atunci când utilizarea, și nu întreținerea, are loc (în timpul perioadelor marcate cu „U” fără paranteze).

În timpul întreținerii online și utilizării (în timpul unei perioade marcate cu „U” cu paranteze), însăși întreținerea concurează cu utilizatorii și le degradează performanța. Desigur, întreținerea frecventă cauzează competiție frecventă. Se descrie degradarea printr-un salt în timpul de răspuns reprezentat când întreținerea online începe sau se termină. Dimensiunea saltului (care rezultă din competiția de la întreținere) nu este neapărat egală cu dimensiunea scăderii treptate în timpul de răspuns din timpul întreținerii (care rezultă din reducerea degradării structurale). De asemenea, schimbarea în timpul de răspuns când întreținerea online începe sau se termină ar putea fi treptată, nu un salt. Întreținerea online poate dura mai mult decât întreținerea offline, deoarece utilizatorii concurează cu reorganizarea.

Pentru ca întreținerea online să aibă succes, trebuie să scadă degradarea structurală pe termen lung la fel de repede cum actualizările utilizatorilor cresc degradarea structurală. Acest succes este descris prin întoarcerea timpului de răspuns reprezentat la o valoare scăzută.

Un exemplu de criteriu pentru întreținerea offline care poate activa întreținerea este degradarea structurală peste un prag. Degradarea maximă a performanței utilizatorilor are loc chiar înainte de activarea întreținerii offline în graficul A. Dacă întreținerea online utilizează aceeași valoare pentru un astfel de prag, atunci degradarea maximă a performanței utilizatorilor în timpul întreținerii online ar putea depăși degradarea maximă pentru cazul offline, pentru că însăși întreținerea online degradează performanța utilizatorilor. Pentru a preveni o degradare maximă mai ridicată a performanței utilizatorilor întreținerea online ar putea folosi o valoare mai mică pentru un prag (dacă un scop al întreținerii este de a îmbunătăți performanța), așa cum arată graficul B. Pentru întreținerea online pentru un SGBD comercial [Smith 1990], pragul nu este mai mic decât pragul pentru întreținerea offline. Totuși, clienții acestui SGBD, în principal, au fost reorganizați pentru a recupera spațiu, nu pentru a îmbunătăți performanța.

În timpul întreținerii online, actualizările utilizatorilor provoacă, de asemenea, degradarea structurală continuată și astfel, degradarea performanței în părți ale bazei de date pe care trecerea reorganizării prin baza de date a ajuns deja. Această degradare structurală va rămâne după finalizarea acestei treceri. Graficul B descrie această degradare printr-un timp de răspuns minim (după finalizarea întreținerii) care depășește oarecum minimul din graficul A.

Graficul C arată comportamentul posibil al timpului de răspuns așteptat pentru un SGBD care utilizează întreținerea online prin copiere. Actualizările utilizatorilor în timpul întreținerii online ar putea cauza degradarea structurală în copia nouă. De exemplu, în reorganizarea neclară, aplicarea jurnalului poate provoca surplus în copia nouă. Totuși, timpul de răspuns minim din graficul C depășește oarecum minimul din graficul A. Două diferențe între B și C sunt:

Dacă întreținerea prin copiere citește, dar nu scrie copia pe care utilizatorii o accesează, întreținerea însăși ar putea provoca degradarea mai puțină a performanței utilizatorilor, așa cum este descris printr-un salt mic în graficul C.

Întreținerea prin copiere beneficiază de utilizatori numai după ce încep să trimită accesele utilizatorilor în noua copie (care de multe ori înseamnă la sfârșitul întreținerii); întreținerea în loc poate începe să beneficieze de utilizatori imediat. Totuși, în timpul întreținerii online, panta este încă pozitivă în graficul C, dar negativă în graficul B. Desigur, în graficul C, cantitatea de creștere a timpului de răspuns în timpul întreținerii este proporțională cu durata de întreținere.

CAPITOLUL II

STRATEGII PENTRU ÎNTREȚINEREA ONLINE

Cele mai multe din secțiunile de până acum au implicat probleme care, în general, se pot aplica la o varietate de categorii de reorganizare, dar acum vor fii prezentate strategiile care se aplică la categorii specifice în cadrul întreținerii: restaurare de clustering, reorganizarea unui indice, reechilibrarea datelor paralele sau distribuite, colectarea gunoiului pentru stocarea persistentă și curățare (recuperare de spațiu) într-un sistem de fișiere jurnal structurat. Aceste categorii au unele suprapuneri. De exemplu, colectarea gunoiului recuperează spațiu, reorganizarea unui indice poate, de asemenea, recupera spațiu și recuperarea de spațiu, de asemenea, poate restaura clustering. Restaurarea de clustering și reorganizarea unui indice pot include îndepărtarea surplusului. Cu toatea astea, strategiile sunt clasificate în funcție de activitățile pe care pun accentul.

Restaurare de clustering

Prima categorie de întreținere este restaurarea de clustering, care înseamnă practica de a stoca instanțe aproape una de alta dacă îndeplinesc anumite cristerii. Criteriile populare pentru clustering includ: (1) legătură între instanțe și (2) valori consecutive ale unei chei. Un astfel de clustering ar trebui să reducă discul de intrare / ieșire pentru instanțele pe care utilizatorii de multe ori le accesează împreună. Desigur, actualizările utilizatorilor pot reduce cantitatea de clustering și astfel, degradează performanța. De asemenea, chiar dacă un anumit clustering a fost adecvat pentru modelele anterioare de acces ale utilizatorilor, poate deveni nepotrivit (și degrada performanța) când modelele de acces se schimbă [Bennet și Franaszek 1977; Soderlund 1980; McIver și King 1994; McIver 1994]. Vor fi prezentate strategii pentru: (1) restaurare incrementală de clustering în loc în timpul activităților utilizatorilor, (2) restaurare în loc prin intermediul unui reorganizator și (3) restaurare prin copiere prin intermediul unui reorganizator.

Restaurare incrementală în loc în timpul activităților utilizatorilor. Restaurarea de clustering poate să apară în loc în timpul activităților utilizatorilor. Strategiile reorganizează în loc cu mutarea între pagini.

Conceptele în strategia lui Bennet și Franaszek [1977] se pot aplica la orice ierarhie de stocare în care o unitate de transfer de date între două nivele din ierarhie conțin unități mai mici. Un bloc (care conține pagini) este o unitate de transfer din stocarea secundară în stocarea principală. După transferul unui bloc în stocarea principală, paginile blocului sunt apoi administrate individual. Strategia pentru clustering implică doar blocurile care sunt deja în stocarea principală. Fiecare proces are o sarcină de clustering asociată care execută o secvență de schimburi de atribuiri de pagini la blocuri. Fiecare schimb implică: (1) o pagină de referință și (2) o pagină într-un punct de cluster. Un punct de cluster este setul de pagini fără referință într-un bloc care conține o pagină de referință. Fiecare proces poate avea mai multe puncte de cluster.

Principalele caracteristici ale strategiei sunt:

Sistemul atribuie fiecare pagină la primul proces care face referire la pagina din timpul șederii sale actuale în stocarea principală. Această atribuire înseamnă că sarcina de clustering pentru acest proces este responsabilă pentru îmbunătățirea de clustering a acestei pagini.

Pentru fiecare proces, primul punct de cluster este setul de pagini fără referință în blocul care conține pagina care provoacă prima eroare de pagină pentru proces.

Când se atribuie pagina la un proces, sistemul își adaugă identificatorii la o listă asociată cu punctul de cluster curent.

După ce dimensiunea listei crește la dimensiunea punctului de cluster, următorul punct de cluster pentru proces este setul de pagini fără referință în blocul care conține pagina care provoacă următoarea eroare de pagină. Acest punct de cluster va avea propria listă de identificatori de pagini.

Când o pagină dintr-un punct de cluster este pe cale să fie dată afară, sistemul își schimbă atribuirea de bloc cu atribuirea de bloc a unei pagini în lista asociată. Astfel, blocul care conține punctul de cluster acumulează pagini de referință.

Când este dată afară ultima pagină dintr-un punct de cluster, sistemul șterge lista pentru punctul de cluster.

Pentru un SGBD orientat obiect, Chang și Katz [1989] utilizează moștenirea și structura semantică pentru a influența clustering-ul. Intrările la clustering pot fi sugestiile utilizatorilor, frecvențe de accese inter-obiect (care sunt definite atunci când este creat tipul obiect) și caracteristici ale atributelor moștenite. La crearea fiecărei instanțe de date, sistemul alege o plasare inițială bazată pe relația care este cel mai frecvent traversată.

Altă discuție de clustering pentru un SGBD orientat obiect [McAuliffe et al. 1998] include o descriere a două tehnici:

La crearea unui obiect, o aplicație poate specifica o sugestie apropiată (o cerere pentru plasarea pe aceeași pagină ca un obiect existent specificat). De obicei, un SGBD nu înregistrează sugestia persistent, astfel că utilitatea sa este limitată la plasarea inițială, nu mai târziu de întreținerea de clustering. Această tehnică, de asemenea, nu spune SGBD-ului că un anumit obiect va fi specificat într-o sugestie apropiată pentru o viitoare creare a altui obiect, astfel încât SGBD ar putea folosi spațiu apropiat pentru obiecte independente. Totuși, un SGBD poate permite programatorului aplicației să specifice cantitatea de spațiu liber pe care SGBD-ul ar trebui să o lase pe pagini până când va fi înlocuită de o sugestie apropiată.

Un cluster de dimensiune fixă reprezintă un număr integral de pagini care să rezerve pentru inserările viitoare; SGBD nu va amesteca două clustere pe o pagină. Această tehnică poate cauza fragmentare, iar dimensiunea unui cluster ar putea fi imposibil de prezis, ceea ce duce la un eventual surplus.

Restaurare în loc prin intermediul unui reorganizator. Mai multe strategii sunt disponibile pentru utilizarea unui reorganizator pentru a muta înregistrări între pagini, pentru a restaura clustering în loc. Diferite strategii subliniază diferite activități, de exemplu, următoarele link-uri, reducerea costurilor pentru a construi o pagină și clustering prin intermediul unui indice.

Pentru a realiza clustering, SGBD plasează o înregistrare inserată într-o pagină care conține o înregistrare logică relatată, dacă este posibil; în caz contrar, SGBD plasează înregistrarea într-o zonă de surplus. Diferite relații (reprezentate de diferite tipuri de set CODASYL) pot avea priorități diferite în clustering. Eliminarea unei înregistrări rezultă în marcarea înregistrării ca eliminată, dar nu dealocă imediat spațiu. Un reorganizator urmărește link-uri de seturi CODASYL și realizează întreținerea. Pentru ca această întreținere să fie posibilă, trebuie să se evite: (1) creșterea pe termen lung în degradarea structurală (și astfel, creșterea pe termen lung în timpii de răspuns ai utilizatorilor) și (2) o creștere inacceptabilă în timpii de răspuns ai utilizatorilor ca urmare a disputei cu reorganizatorul.

Strategia lui Omiecinski și Scheuermann [1984] și Omiecinski [1985b; 1996] implică restaurarea de clustering prin schimbul de înregistrări între pagini. Restaurarea se poate aplica la un fișier întreg sau la un subset al unui fișier, ex. pagini cel mai des accesate. În cadrul fișierului, reorganizatorul blochează doar paginile care sunt în prezent în buffere; utilizatorii pot accesa restul fișierului. Un tip de tabel de mapare logic-la-fizic mapează identificatori la numerele de pagină; reorganizarea datelor nu afectează indicii. Ordinea de construcție a noilor pagini afectează cantitatea de schimbare de pagină (intrare / ieșire) în timpul reorganizării, deoarece unele dintre înregistrările necesare pentru o pagină ar putea fi deja în buffer, datorită construcției de pagini anterioare noi. Pentru alegerea unui ordin și efectuarea reorganizării se prezintă doi algoritmi (reorganizarea costurilor statică și reorganizarea costurilor dinamică). O ipoteză este că pentru fiecare pagină nouă j, cardinalitatea de delta(j) nu va depăși dimensiunea bufferului, unde delta(j) este setul de pagini care conține înregistrările care vor locui în cele din urmă în noua pagină j.

În algoritmul reorganizarea costurilor statică, după construirea unei pagini (i), funcția cost pentru orice pagină nouă (j) nu încă construită este fracțiunea de pagini din delta(j), care nu sunt în delta(i). Următoare pagină nouă (j) va fi noua pagină care are valoarea minimă pentru funcția cost. Acest algoritm ia în considerare doar paginile care au fost aduse în bufferul pentru construirea paginii mai recente (i). Ordinea tuturor paginilor noi este determinată static (ex. înainte de construirea oricărei din aceste pagini noi). Pentru fiecare pagină nouă j, au loc următoarele etape: (1) Dacă este necesar, se schimbă unele pagini afară din buffer, folosind o privire înainte de k pagini noi pentru a determina care pagini nu sunt în deltele din următoarele câteva pagini noi. (2) Se aduc în paginile care sunt necesare pentru a construi pagina j și care nu sunt deja în buffer. (3) Se rearanjează înregistrările pentru a construi pagina j și se modifică tabelul de mapare. (4) Se scrie pagina j pe disc.

În algoritmul reorganizarea costurilor dinamică, acești pași se execută iterativ până au fost construite toate paginile noi: (1) Funcția cost pentru orice pagină nouă (j) nu încă construită este fracțiunea de pagini din delta(j) care nu sunt în buffer. Se alege noua pagină curentă (j) ca noua pagină care are valoarea minimă pentru funcția cost. Acest algoritm ia în considerare toate paginile care sunt acum în buffer, chiar și paginile care au fost aduse în buffer înainte de cea mai recentă construire a unei pagini noi. Ordinea noilor pagini este determinată dinamic (ex. în fiecare iterație, noua pagină curentă este determinată). (2) Dacă este necesar, se schimbă unele pagini afară din buffer, alegând paginile care conțin cele mai puține înregistrări necesare noii pagini. (3) Se aduc în paginile care sunt necesare pentru a construi pagina j și care nu sunt deja în buffer. (4) Se rearanjează înregistrările pentru a construi pagina j și se modifică tabelul de mapare. (5) Scrie pagina j pe disc. (6) Se rearanjează înregistrările din buffer în seturi în conformitate cu noile pagini în care vor locui înregistrările în cele din urmă; asta este construirea parțială a acestor noi pagini. Se ordonează paginile din buffer după dimensiunile acestor seturi de înregistrări. Se modifică tabelul de mapare. Ordinea în această etapă grăbește alegerea în etapa (2).

Restaurare prin copiere prin intermediul unui reorganizator. Un reorganizator ar putea restaura clustering prin copiere. Strategiile de clustering iau în considerare legăturile dintre obiecte sau valorile unei chei de clustering.

O strategie pentru restaurare de clustering [McIver și King 1994; McIver 1994] se aplică la obiectul bazelor de date. Strategia implică trei componente. Primele două își păstrează datele în afara bazei de date și, astfel, nu blochează baza de date.

Prima componentă se execută ca un proces de fundal. Pentru a urmări modelele de acces, această componentă colectează statistici, pe care tranzacțiile utilizator le trimit la angajament. O statistică este raportul dintre: totalul acceselor consecutive la obiecte pe diferite pagini și totalul acceselor de disc. Degradarea performanței activează a doua componentă.

A doua componentă se execută, de asemenea, ca un proces de fundal. Această componentă analizează clustering-ul prin utilizarea unui criteriu care implică accese consecutive ale obiectelor (nu neapărat pe diferite pagini). Analiza folosește un grafic ale cărui noduri reprezintă obiecte și ale cărui margini reprezintă link-uri. Produce o secvență a identificatorilor de obiecte; ordinea reflectă cantitățile relative de acces consecutiv și, astfel, sugerează un clustering dorit. Modelele de utilizare ar putea fi schimbate după clustering-ul precedent. Reducerea suficientă de clustering activează a treia componentă.

A treia componentă (reorganizarea) copiază obiectele la un nou set de pagini pentru a realiza clustering-ul dorit. Un tabel de mapare logic-la-fizic mapează din identificatorii de obiecte la adresele de pe pagini și reflectă mutarea. Acest tabel de mapare evită actualizarea de obiecte care au link-uri la înregistrările care au fost mutate și permite intercalarea acceselor utilizator și mutarea înregistrărilor prin reorganizare. Caracteristicile managerului de stocare de bază au fost necesare reorganizării pentru a bloca întreaga bază de date. Totuși, reorganizarea are loc în etape și utilizatorii pot executa tranzacții între etape.

Reorganizarea unui indice

O altă categorie de întreținere este reorganizarea unui indice. Aici, vor fi prezentate caracteristici ale indicilor (pentru a explica nevoia de reorganizare) și studiul lucrării în reorganizarea online a indicilor.

Fundal. Unele SGBD-uri susțin indicii care constă în ierarhii de noduri. Arborii B și variațiile acestora sunt forme comune pentru astfel de ierarhii. În continuare, vor fi prezentate operații de inserare și ștergere într-un indice.

La inserarea într-un indice, dacă nodul dorit este deja plin, și, prin urmare, nu poate stoca noua intrare, sistemul alocă alt nod și împarte intrările nodului inițial în două noduri. Inserarea necesară unei intrări în nodul părinte poate cauza divizarea de a propaga în sus, uneori chiar adăugând un nivel la indice. Alocarea de pagini, adăugarea de nivele și (în unele implementări) pierderea alăturării fizice a nodurilor frunză logice adiacente pot încetini accesele viitoare ale utilizatorilor la indice.

În unele implementări, la ștergerea dintr-un indice, dacă un nod devine mai puțin de jumătate plin și un nod vecin este mai mult de jumătate plin, atunci sistemul mută unele intrări între noduri pentru a echilibra nodurile. Dacă, în schimb, niciun nod vecin nu este mai mult de jumătate plin, atunci sistemul îmbină (concatenează) intrările din nod și un nod vecin într-un singur nod, și dealocă noul nod gol. Ștergerea necesară unei intrări dintr-un nod părinte poate cauza îmbinarea de a propaga în sus. Un SGBD care utilizează un indice poate împărți și îmbina noduri ale unui indice în timpul activităților utilizatorilor. În practică, implementările comerciale tipice nu echilibrează sau îmbină noduri; ele dealocă un nod doar la o ștergere a utilizatorului a ultimei intrări a nodului.

Unii implementatori recomandă reorganizarea ocazională a întregului indice. Reorganizarea poate reduce numărul de pagini alocate, numărul de nivele în ierarhie și face distribuirea spațiului liber cât mai uniformă posibilă peste nodurile indice. Aceste beneficii sunt deosebit de importante pentru implementările care nu echilibrează sau îmbină noduri în timpul eliminărilor. În unele implementări, reorganizarea poate, de asemenea, restaura alăturarea fizică a nodurilor frunză logice adiacente.

Reorganizarea în loc. Strategiile de aici reorganizează fără a copia un număr mare de noduri dintr-o locație veche într-o locație nouă, la un moment dat.

Kung și Lehman [1980] descriu concurența în arborii binari. Activitățile utilizator pot schimba structura părților indicelui pe care le accesează. Nodurile care nu vor mai fi în indice merg într-o coadă de gunoi, dar ele dobândesc înapoi pointerii, pentru a asigura corectitudinea căutărilor care sunt încă poziționate în aceste noduri. Periodic, un reorganizator blochează coada de gunoi, o copiază, resetează coada de gunoi inițială pentru a goli, o deblochează, așteaptă ca toate procesele de execuție curente să se finalizeze (și, astfel, să oprească utilizarea nodurilor de gunoi) și returnează nodurile de gunoi la lista de stocare disponibilă.

Strategia lui Manber și Ladner [1982; 1984] operează, de asemenea, pe arbori binari. O activitate utilizator poate șterge logic un nod și adăuga identificator la o listă de noduri șterse logic. Unul sau mai mulți reorganizatori pot opera. Aici un reorganizator, nu o activitate utilizator, reglează un pointer la un nod șters logic. O tranzacție utilizator blochează cel mult un nod și un reorganizator blochează cel mult trei.

În strategia lui Lomet și Salzberg [1992; 1977], activitățile utilizator împart frunzele (care conțin toate datele), dar un reorganizator împarte nodurile non-frunză. Un nod divizat primește un pointer la noul său frate. Îmbinarea (la orice nivel) nu trebuie să fie parte a unei activități utilizator. La divizare sau îmbinare, este solicitată o acțiune (și eventual executată) pentru a efectua actualizarea necesară de pointeri la următorul nivel superior. Desigur, această actualizare de pointeri ar putea duce la solicitarea unei alte divizări sau îmbinări. După executarea unei acțiuni, este eficient, dar nu esențial, pentru orice acțiuni relatate să se execute în curând. Discuțiile includ blocarea și recuperarea:

Divizarea unui nod non-frunză implică doar blocarea nodului divizat. După divizare, actualizarea de pointeri în părinte implică blocarea părintelui și copilul divizat. Îmbinarea blochează trei noduri (doi copii și părintele). Ordonarea blocării previne impasul.

Fiecare acțiune de reorganizare este atomică, înregistrată în jurnal și schimbă un singur nivel în ierarhie. Recuperarea dintr-un accident de sistem nu are nevoie de nicio măsură specială pentru a reflecta posibila incompletitudine a reorganizării. În schimb, dacă o tranzacție utilizator, în timpul traversării obișnuite întârziate a ierarhiei, constată că o divizare sau îmbinare a avut loc, dar pointerii părintelui nu au fost încă actualizați (probabil din cauza unui accident de sistem), acțiunea lipsă este solicitată.

Reorganizare prin copiere. Strategiile din această secțiune copiază un grup de noduri dintr-o locație veche într-o locație nouă. Această copiere include lăsarea cantității dorite de spațiu liber în fiecare pagină pentru inserările viitoare.

Zou și Salzberg [1996b; 1999c] descriu un reorganizator pentru un indice ale cărui noduri frunză conțin înregistrările de date. O tranzacție utilizator nu îmbină noduri slab populate. Autorii presupun că paginile frunză și paginile non-frunză locuiesc pe diferite discuri sau pe diferite părți ale discului. Logarea acțiunilor reorganizatorului permite dinainte recuperarea. Unele acțiuni reorganizează în loc; unele reorganizează prin copiere. Reorganizatorul face 3 treceri, pentru: (1) compactare de frunze, (2) reordonare de frunze și (3) reorganizare de noduri non-frunză:

Reorganizatorul scanează părinții nodurilor frunză, în ordine cheie. În fiecare set de noduri frunză frate, compactează nodurile frunză (prin mutarea datelor dintr-un nod în altul) și actualizează părintele. Construiește o nouă pagină frunză la un moment dat. Dacă o pagină goală de stocare este disponibilă după cea mai mare pagină cu cheie a cărei compactare este terminată și înainte de pagina frunză ale cărei date sunt în curs de reorganizare, atunci sistemul utilizează acea pagină goală ca destinație a mutării. În caz contrar, folosește o pagină parțial plină ca destinație.

Reorganizatorul scanează din nou părinții de noduri frunză. Mută nodurile astfel încât ordinea lor fizică se potrivește cu ordinea logică a cheilor lor. Această trecere are loc numai dacă performanța de interogare a fost degradată dincolo de un prag.

Pentru a reduce numărul de nivele într-un indice, sistemul reorganizează non-frunzele prin scanarea părinților de frunze și copierea la o nouă zonă. După fiecare construire a câtorva pagini ale indicelui, forțează noile pagini la disc, pentru durabilitate. Dacă o actualizare prin intermediul unui utilizator este pe o pagină pe care reorganizatorul nu a citit-o încă, actualizarea are loc doar în pagina veche; reorganizatorul o va găsi mai târziu. Dacă o actualizare este pe o pagină pe care reorganizatorul a citit-o deja, actualizarea are loc în pagina veche, dar sistemul, de asemenea, înregistrează actualizarea într-un fișier special. După copierea nodurilor (și construirea indicelui), sistemul scanează fișierul special și aplică actualizările la noua copie. Apoi scrie-blochează fișierul special (prevenind noile actualizări), comută utilizatorii din indicele vechi la cel nou prin schimbarea informațiilor stocate în jurul locației rădăcină, scrie-blochează indicele vechi (astfel așteptând ca interogările vechi să se finalizeze) și dealocă indicele vechi.

Reechilibrarea datelor paralele sau distribuite

Reechilibrarea se poate aplica la declustering sau striping, pentru care se folosesc următoarele definiții:

Declustering este practica de intercalare date printre discuri paralele, atribuind unități logice de date (ex. un rând al unui tabel) pe disc. Un SGBD este implicat și ar putea folosi o abordare round-robin sau o cheie. Dacă utilizează o cheie, s-ar putea încurca cheia sau fiecare disc ar putea primi o serie de valori-cheie.

Striping este practica de intercalare date printre discuri paralele, atribuind unități fizice de date (ex. n biți) pe disc. Nu este necesar ca un SGBD să fie implicat. Este folosită o abordare round-robin.

Declustering sau striping pot permite accesul paralel la piesele de date. Plasarea atentă a datelor poate echilibra nivelele de activitate printre discuri și astfel îmbunătățește performanța prin reducerea probabilității pe care cozile formează la unele discuri când alte discuri sunt inactive.

Alegerea de date care să migreze. Acest subiect presupune criterii pentru alegerea datelor care să migreze pentru a realiza reechilibrarea. Criteriile pot include frecvența de acces a datelor și dimensiunea datelor, cu un scop de a evita strâmtorile. De obicei, acest lucru nu pune accent pe creșterea în rețea.

Weikum et al. [1991] descriu caracteristici ale sistemului de fișiere. Un traseu este un set fizic alăturat de blocuri logice consecutive ale unui fișier; este granularitatea de striping. O extensie este un set fizic alăturat de unul sau mai multe trasee pe un disc. O regiune este un set de extensii diferite discuri. Creșterea unui fișier duce la alocarea de regiuni suplimentare. Un fișier este un set de regiuni. Un tabel de mapare logic-la-fizic mapează de la numere logice blocate la adrese de disc blocate. Căldura unui obiect (extensie sau disc) este frecvența de acces (implicând I / O, nu cache) pe o perioadă de timp. Temperatura unui obiect este căldura împărțită la dimensiune.

Obiectivele de performanță sunt pentru a minimiza timpul de acces la porțiuni consecutive ale unui fișier, pentru a echilibra încărcătura de disc și pentru a minimiza costul reorganizărilor. Aceste obiective pot intra în conflict unele cu altele. Când un fișier este creat, sistemul utilizează anumite formule pentru plasare. Dacă un disc are suficient spațiu pentru o cerere de alocare, dar nu are spațiu alăturat suficient, sistemul compactează discul.

Dacă un disc devine atât de fierbinte încât provoacă dezechilibru semnificativ în încărcătură, sistemul efectuează răcire de disc, care este migrarea datelor de la sursă (disc cald) la o destinație (disc răcitor). Granularitatea migrării este o extensie. Destinația este, de obicei, un disc care nu deține o extensie a aceeași regiuni. Temperatura reprezintă raportul dintre beneficiu (scăderea în căldură a discului prin eliminarea datelor accesate frecvent) și cost (cantitatea de date pentru a migra). Sistemul continuă răcirea unui disc până când căldura discului scade sub un prag sau până când discul destinație devine mai fierbinte decât sursa.

Într-o strategie bazată pe indice pentru reechilibrare [Lee et al. 2000], SGBD încarcă grămadă datele migrate într-un arbore (specific, un subset al indicelui primar) la destinație. Indicii secundari necesită inserări și ștergeri convenționale. SGBD menține echilibru înălțime al indicilor în noduri, chiar dacă unii indici sunt mai grași sau mai flexibili decât de obicei. Datele sunt partiționate după rândul valorilor de cheie primară. Nivelul de sus al unui indice cu 2 niveluri direcționează un acces la nodul care conține datele.

O etapă de migrare constă în mutarea datelor prin încărcarea grămadă și schimbarea indicilor. Fiecare migrare mută date pentru rândul precedent sau ulterior. Cantitatea de date pentru a muta este un subarbore al indicelui primar; această politică permite actualizarea eficientă a indicelui. Nivelul subarborelui în indice controlează cantitatea de date pentru a muta. O migrare necesită schimbarea indicelui de pe rândul de sus, această informație va traversa la alte noduri ca parte a oricăror mesaje viitoare care ar putea fi trimise chiar și fără această migrare.

SGBD activează migrarea când încărcătura, timpul de răspuns sau dimensiunea cozii la un nod depășește un prag. Un nod de control votează nodurile pentru stările lor și decide dacă să activeze migrarea. O alternativă este ca pentru fiecare nod să i se compare încărcătura cu încărcăturile vecinilor săi.

Creștere în rețea. Un alt subiect în reechilibrare se ocupă cu decizia dacă rețeaua trebuie să crească (bazată pe îndeplinirea obiectivelor de performanță și evitarea creșterii inutile) sau cu programarea migrării când rețeaua crește. Sistemul migrează unele date la noduri noi.

Pentru datele distribuite, Vingralek et al. [1994] are un scop de scalabilitate (specific, sprijin pentru creșterea datelor și / sau un volum de muncă în creștere printr-o creștere liniară a numărului de servere). Sistemul dobândește un nou server numai dacă utilizarea generală server din sistem depășește un prag. Vasele hash pot migra de la serverele puternic încărcate la servere mai ușor încărcate și, de asemenea, se pot împărți. Adevărata preocupare este performanța, nu utilizarea stocării, dar autorii folosesc capacitatea de date a unui server pentru a reprezenta capacitatea de performanță. Un tabel de mapare logic-la-fizic mapează de la vase hash la servere; o copie a tabelului există la fiecare client și fiecare server. Dacă un server primește o cerere pentru o cheie pe care alt sever o deține acum, transmite cererea la acest server și trimite propria copie a tabelului de mapare la clientul solicitant, care poate corecta apoi copia.

Colectarea gunoiului pentru stocarea persistentă

Următoarea categorie de întreținere este colectarea gunoiului. Mai multe limbi suportă structuri de date legate. Rădăcinile acestor lanțuri ar putea fi variabile globale, statice, variabile stivă și registre. În astfel de limbi, o sarcină recurentă este colectarea gunoiului, de exemplu, îmbunătățirea (eliberare) stocării care nu mai este în mod direct sau indirect accesibilă din rădăcini și, astfel, nu mai este utilizată. Termenul de mutator se folosește pentru a se refeli la un proces utilizator, care ar putea face stocarea inaccesibilă.

Unele strategii pentru colectarea gunoiului împart baza de date în partiții și colectează o partiție la un moment dat. Colectarea partiționată are mai multe avantaje:

Crește locul de referință al colectării. În particular, se poate recupera ceva spațiu fără scanarea întregii baze de date.

Se poate limita perturbarea utilizatorilor, chiar dacă o strategie blochează o partiție întreagă.

Pentru colectarea prin copiere, limitează spațiul suplimentar necesar pentru o unitate de copiere.

Colectarea partiționată are, de asemenea, și dezavantaje:

Este necesar spațiu și timp pentru a menține listele de referință de la obiecte într-o partiție la obiecte în altă partiție.

Dacă astfel de referințe de partiție încrucișată formează un ciclu de gunoi, colectarea doar a unei partiții nu revendică ciclul, deoarece fiecare obiect din ciclu pare accesibil.Dacă nu se completează colectarea de partiție cu colectarea de partiție încrucișată, un astfel de ciclu va rămâne necolectat.

Colectarea gunoiului în loc pentru stocarea volatilă. Se presupune că fiecare obiect include un contor de referință (un contor al obiectelor și rădăcinilor care se referă la obiect) [Collins 1960]. Când contorul scade la 0, se poate considera că obiectul este gunoi și se revendică stocarea obiectului. Această simplă strategie este online; adică, colectarea gunoiului evită, de obicei, o pauză lungă pentru utilizatori. Această strategie necesită spațiu pentru contor și actualizarea contorului ori de câte ori se adaugă sau se șterge o referință. Un dezavantaj mai important este că strategia eșuează revendicarea unui ciclu adresat obiectelor care sunt gunoi. Acest eșec se produce deoarece fiecare obiect din ciclu încă se referă la succesorul său, care astfel, are încă un contor pozitiv. Prin urmare, dacă ciclurile se pot forma, această strategie singură este inadecvată, dar unele sisteme o combină cu strategii mai scumpe, dar rareori executate care fac revendicare de cicluri.

O altă limitare a numerotării de referință se aplică în cazul în care contoarele de referință au o valoare maximă posibilă care este mai mică decât numărul maxim de referințe posibile. După ce un anumit contor de referință atinge valoarea maximă, nu se poate incrementa pentru a reprezenta referințe suplimentare, astfl încât singura ipoteza în condiții de siguranță este că numărul actual de referințe poate fi arbitrar mai mare decât valoarea maximă. Prin urmare, nu se poate decrementa în condiții de siguranță acest contor la 0.

În afară de numerotarea de referință, o altă strategie în loc este marchează și străbate [McCarthy 1960], care, de obicei, include aceste faze: (1) Pornind de la rădăcini, se urmăresc obiectele accesibile și se marchează ca accesibile. Într-o traversare în adâncime, dacă se găsește un obiect marcat deja, s-au urmărit deja succesorii săi, așa că nu se urmăresc din nou. (2) Se străbate prin stocare și se revendică obiectele nemarcate.

Colectarea gunoiului online nepartiționată în loc pentru stocarea persistentă. Aceste strategii nu impart baza de date în partiții.

Lucrarea lui Birell și Needham [1978] se ocupă cu un collector de gunoi pentru un sistem de fișiere. Un tabel central stochează fiecare contor de referință al obiectului și tipul de obiect (director sau segment). Contorul de referință este sufficient pentru recuperarea de segmente, care constituie cele mai multe obiecte și care nu au cicluri. Pentru a recupera directoarele, care pot avea cicluri, un reorganizator marchează și străbate. Colectarea gunoiului pentru directoare scanează inițial tabelul central și stabilește o structură de date cu o intrare pentru fiecare director.

Pentru un sistem de operare care accept programarea orientată obiect, Almes [1980] descrie colectarea gunoiului pentru obiectele persistente, care utilizează ambele strategii (numerotarea de referință și strategia care marchează și străbate). Un obiect poate fi atât activ (adică, în stocarea primară), cât și pasiv (adică, în stocarea secundară). Tabelul de simboluri active urmărește obiectele active; tabelul de simboluri passive urmărește obiectele pasive. Fiecare obiect active are două contoare de referință. Contorul de referință total reprezintă toate referințele; Contorul de referință activ reprezintă doar referințele active, adică acelea care au fost convertite la adrese fizice. Când contorul de referință total devine 0, obiectul poate fi recuperat. Când contorul de referință activ devine 0, obiectul devine doar pasiv și este eliminat din tabelul de simboluri active. De asemenea, un proces scanează tabelul de simboluri active pentru obiectele care nu au fost accesate recent. Procesul face fiecare astfel de date ale obiectelor pasive, convertește referințele active ale obiectelor la forma pasivă și recuperează stocarea pe care datele și pointerii au ocupat-o.

Într-un ciclu inaccesibil în tabelul de simboluri active, în cele din urmă, unele obiecte vor ajunge la o stare de a nu fi accesate recent. Acest lucru duce la decrementarea contoarelor de referință active pentru obiectele la care se indică. De asemenea, duce la eliminarea obiectelor din ciclu când contoarele de referință active devin 0. Astfel, un ciclu inaccesibil în tabelul de simboluri active va dispărea; obiectele devin doar pasive.

Colectarea gunoiului online partiționată în loc pentru stocarea persistent. Strategiile de aici impart baza de date în partiții și colectează o partiție la un moment dat.

Pentru un sistem client-server de bază de date orientată obiect, Amsaleg et al. [1995;1999] descriu colectarea gunoiului online bazată pe server. Paginile sunt transferate între clienți și server, un client trimite paginile scrise la server doar după trimiterea intrărilor jurnal și toate paginile scrise de client sunt copiate la server înainte de angajament. Colectarea gunoiului marchează și străbate execută pe server.

Cu partiționare, fiecare partiție are o listă de intrare referințe; această listă este o rădăcină a persistenței. Ciclurile de gunoi care traversează partițțile, nu sunt colectate. După colectarea unei partiții, colectorul elimină referințele care pleacă netrasate în listele de intrare referințe ale altor partiții.

Pentru o stocare de obiect persistent client-server, Maheshwari și Liskov [1997] colectează gunoi într-o partiție la un moment dat. Fiecare pereche de partiții i și j au o listă inter-partiție, care înregistrează referințele din obiecte în partiția i în obiecte în partiția j. Fiecare partiție are o listă de intrare referințe, care este un set de pointeri la listele inter-partiție pentru referințele în această partiție. Similar, fiecare partiție i are o listă de foste referințe, care este un set de pointeri la listele inter-partiție pentru referințele din partiția i. Fosta listă este esențială, dar accelerează tăierea listelor de intrare a altor partiții (prin evitarea scanării acestor liste de intrare) în timpul eliminării referințelor care nu sunt trasate în timpul colectării gunoiului partiției i.

Colectarea partiționată singură nu colectează ciclurile inter-partiție de gunoi, deci o marcare globală completează colectarea bazată pe partiție. Pentru fiecare partiție, marcarea globală are loc când colectarea de partiție are loc. În timpul urmăririi unei partiții, orice obiecte care nu au fost trasate la pasul precedent al colectării globale de gunoi sunt recuperate. Apoi, marcarea propagă din rădăcinile partiției la referințele fostei liste. Obiectele noi create sunt, de asemenea, marcate. Marcarea este completă când marcările au propagat prin toate partițiile.

Colectarea gunoiului prin copiere pentru stocarea volatilă. În acete strategii, se pocnește; adică, se schimbă rolurile zonei inițiale cu zona nouă, astfel încât accesele viitoare ale utilizatorilor se pot aplica la noua zonă. În strategiile online, flipping-ul (pocnirea) are loc când începe colectarea.

Într-o strategie tipică de copiere, se copiază toate obiectele accesibile, producând o nouă copie compactă a datelor [Cheney 1970]. Se începe prin copierea obiectelor la care indică rădăcinile. Se scanează apoi obiectele în noua zonă. Pentru fiecare astfel de obiect, se urmăresc pointerii (dacă este cazul) la obiecte în zona veche, se copiază aceste obiecte la zona nouă și se actualizează pointerii. De fiecare dată când se copiază un obiect, copia veche dobândește o expediere de pointer la noua copie. În cazul în care colectorul ajunge mai târziu copia veche din nou (prin urmărirea unui pointer din alt obiect), se va actualiza pointerul care s-a urmărit și se va evita copierea obiectului din nou. După copierea tuturor obiectelor accesibile, se revendică zona veche și se permite utilizatorilor să acceseze noua zonă. Această strategie offline poate produce o pauză lungă pentru utilizatori.

Baker [1978] descrie copierea incremental. În timpul fiecărei activități utilizator care alocă stocare, se copiază și compactează datele treptat (adică, se copiază câteva obiecte) înainte chiar de a se efectua alocarea (din noua zonă). În fiecare incrementare de colectare, se scanează obiectele în noua zonă. Pentru fiecare astfel de obiect, se urmăresc pointerii (dacă este cazul) la obiecte în zona veche, se copiază aceste obiecte la noua zonă, se inserează expedierea de pointeri în obiectele în zona veche și se actualizează pointerii în obiectul scanat în noua zonă. Se urmărește poziția scanării în noua zonă și următoarea incrementare se va relua la acea poziție. De asemenea, când un utilizator încearcă să acceseze un obiect în zona veche, se va captura încercarea, se copiază obiectul la noua zonă și se redirecționează accesul utilizatorului în noua copie. Din perspective utilizatorului, această redirecționare realizează efectul de flipping la începutul colectării gunoiului. Această captură și copierea provoacă pe collector să proceseze un astfel de obiect mai curând decât ar fi de obicei. După copierea tuturor obiectelor accesibile, se revendică zona veche. Această strategie produce, de obicei, o pauză scurtă pentru utilizatori.

Bartlett [1988] descrie o strategie de copiere mai ales. Aici, colectorul nu trebuie să fie în măsură să determine dacă o valoare în stiva de activare a utilizatorului (o rădăcina potențială) este un pointer. Se poate muta un posibil obiect de referință și actualiza posibilul pointer doar dacă se poate determina că este cu adevărat un pointer. Prin urmare, pentru orice pagină la care stiva de activare sau registrele ar putea indica, colectarea nu copiază pagina din zona veche la cea nouă, se marchează pagina ca fiind logică în zona nouă. Apoi se copiază (din zona veche la cea nouă) obiectele care sunt accesibile din paginile care au marcat ca fiind logice în zona nouă. Prin urmare, se copiază cele mai multe dintre paginile care conțin obiecte accesibile. Această strategie offline poate produce o pauză lungă pentru utilizatori.

Colectarea gunoiului online nepartiționată prin copiere pentru stocarea persistentă. Detlefs [1990] s-a bazat pe colectărul său, care execută ca un reorganizator. Sistemul oprește inițial utilizatorii, pocnește, scanează rădăcinile, găsește paginile la care rădăcinile ar putea indica, marchează paginile ca fiind logice în noua zonă și apoi permite utilizatorilor să reia. Utilizatorii interoghează, alocă și actualizează în noua zonă. Utilizarea metodei lui Appel [1988] capturează încercările utilizatorilor de a accesa paginile în noua zonă ale căror obiecte nu au fost încă scanate. Colectorul scanează paginile în noua zonă. Pentru fiecare astfel de pagină, sistemul prinde pagina în stocarea volatilă și scanează obiectele în pagină. După găsirea (în pagina scanată) unui pointer la un obiect în zona veche care nu a fost copiat încă, sistemul copiază obiectul la noua zonă, prinde pagina veche în stocarea volatilă, inserează o expediere de pointer în obiect în pagina veche și schimbă pointerul în pagina scanată (în zona nouă) care a indicat la obiect. După scanare, sistemul scrie o intrare de colectare a gunoiului în jurnal, și scrie aceste pagini la stocarea persistentă: (1) paginile (în zona nouă) care dețin obiectele copiate, (2) paginila (în zona veche) care au deținut obiectele copiate și (3) pagina scanată în noua zonă. Sistemul scrie apoi o intrare angajament (pentru scanare de pagină) în jurnal și elimină protecția pentru pagina scanată, astfel încât utilizatorii pot accesa pagina.

Colectarea gunoiului online partiționată pentru stocarea persistentă. În colectarea gunoiului pentru obiecte persistente distribuite [Ferreira și Shapiro 1994b; 1994a], un obiectiv de design este de a minimiza comunicarea din cauza colectării între noduri. Un alt obiectiv este conservarea semanticii de consistență a sistemului de stocare. Aici, un segment (set de pagini de stocare virtuale) conține obiecte și o bandă (partiție) este un grup logic de segmente. O partiție poate fi reprodusă pe mai multe noduri. În orice moment, un obiect poate avea un scriitor sau orice număr de cititori. Proprietarul unui obiect este nodul care are (sau a avut cel mai recent) acces de scriere la obiect. Cea mai mare parte a activității de colectare implică o partiție la un moment dat.

Pentru o stocare de obiect persistent, Moss et al. [1997] și Munro et al. [1999] descriu colectarea gunoiului prin copiere (și apoi recuperarea copiei vechi) pentru o mașină (partiție) la un moment dat. Partițiile sunt grupate în seturi de partiții. Seturile sunt ordonate după timpul de creare al seturilor și, într-un set, partițiile sunt ordonate după timpul de creare al partițiilor. Această colectare a gunoiului utilizează o tehnică de copiere, deci s-ar clasifica ca o colectarea a gunoiului prin copiere, dar nu copiază o zonă mare dacă partițiile au o granularitate fină. Ideea este de a copia obiectele accesibile dintr-un set de partiții la seturi tinere și apoi de a se debarasa cel mai vechi set când nu conține obiecte accesibile. Copierea poate compacta datele. Uneori, copierea dintr-o partiție la alta poate reutilize aceeași zonă pe disc. Ciclurile de gunoi inter-partiție pot fi recuperate dacă pot fi mutate în același set de partiții. Fiecare partiție are o listă de intrare referințe și fiecare set de partiții are un contor de intrare referințe din afara setului.

Curățare (recuperare de spațiu) într-un sistem de fișiere jurnal structurat

Autorii [Ousterhout și Douglis 1989; Rosenblum și Ousterhout 1992] și-au bazat designul unui sistem de fișiere jurnal structurat (LFS) pe următoarele ipoteze:

Fișierele pot fi memorate în cache în stocarea principală. Cu o memorie cache mare, multe dintre cererile de a citi fișiere își pot găsi datele în memoria cache fără a reaccesa discul.

Totuși, cel mai disc de intrare / ieșire va fi pentru scriere. Îmbunătățirea performanței de scriere este importantă.

Într-un LFS, scrierea de fișiere are loc prin tamponarea unei secvențe de a scrie în memoria cache și apoi scrierea fizică la o structură secvențială pe disc. Pentru modificarea logică a unui bloc preexistent de date, sistemul adaugă un nou bloc de date ca și în cazul în care s-a scris un jurnal, în loc de a suprascrie blocul preexistent. Această adăugare are ca efect invalidarea și dealocarea blocului preexistent. Sistemul adaugă, de asemenea, blocuri de o hartă care indică spre anumite structuri; structura pentru un fișier conține atributele fișierului și indică la datele fișierului. Un LFS poate înlocui mai multe scrieri mici.

În timpul utilizării, adăugarea și dealocarea sa de blocuri vechi pot fragmenta spațiul liber. O categorie de întreținere numită curățare restabilește diponibilitatea spațiul alăturat liber adecvat pentru scrierea viitoare. Această curățare îmbină datele active din unul sau mai multe segmente (seturi de blocuri alăturate) în unul sau mai multe alte segmente. Curățarea creează spațiu liber alăturat unde datele active au locuit anterior. Desigur, curățarea consumă lățime de bandă pe disc și astfel, degradează performanța sistemului. Segmentele sunt suficient de mari astfel încât citirea sau scrierea unui întreg segment durează mai mult decât căutarea. Un LFS nu servește în mod necesar într-un context de bază de date, dar curățarea are similarități evidente la colectarea gunoiului prin copiere și poate fi văzută ca o categorie de întreținere. Curățarea ar putea executa ca un reorganizator sau când stocarea este epuizată.

În LFS-ul lui Rosenblum și Ousterhout [1992], curățarea operează pe segmente puternic fragmentate. Fiecare execuție a curățării alege câteva segmente pentru curățare, citește segmentele în stocarea principală, identifică datele active, scrie compact aceste date într-un număr mai mic de segmente curate și marchează segmentele alese ca fiind curate. Curățarea începe când numărul de segmente curate scade sub un prag și se suspendă când numărul crește peste alt prag.

Pentru un indice, tehnicile jurnal structurate sunt aplicabile pentru înlocuirea unui bloc modificat [Singhal et al. 1992]. Deoarece înlocuirea unui bloc implică modificarea pointerului care provine din părinții săi, toți strămoșii blocului trebuie să fie înlocuiți. Aceste activități au loc în contextual unei stocări de obiecte persistente. Aici curățarea utilizează numerotarea de referință, nu copierea sau compactarea.

O altă implementare LFS [Seltzer et al. 1993] evită blocarea în cea mai mare parte a procedurii de curățare. În schimb, când reorganizatorul este gata să scrie segmentele înapoi pe disc, acesta verifică dacă orice date active au dispărut recent. În programare, sistemul acordă prioritate scrierii reorganizatorului mai multă decât scrierii utilizatorilor, pentru a evita epuizarea spațiului liber. De asemenea, scrierea normală de către utilizatori se suspendă când numărul de segmente curate scade la 2, pentru a se asigura că poate funcționa curățarea.

Un disc logic [de Jonge et al. 1993] gestionează un disc, nu fișiere. Un tip de tabel de mapare logic-la-fizic mapează adresele de bloc logice la adresele de disc fizice. Un sistem de fișiere, la un nivel mai ridicat de abstractizare, utilizează adresele logice și mutarea unui bloc de date nu necesită schimbarea referințelor pe care le indică blocul. Un sistem de fișiere poate specifica lista ordonată de blocuri, pe care discul logic o poate utiliza pentru a ghida clusteringul fizic. O implementare prototip este jurnal structurat. Când o activitate utilizator, găsețte că stocarea este epuizată, curățarea produce un segment gol, întârziind activitatea utilizator. Curățarea poate utiliza informații din listele menționate mai sus pentru a restaura clustering. Autorii, de asemenea, propun un reorganizator pentru a efectua curățarea și a îmbunătăți aspectul.

CAPITOLUL III

STRATEGII PENTRU REDEFINIREA ONLINE

STRATEGII PENTRU REDEFINIREA FIZICĂ ONLINE

Activitățile de întreținere prezentate mai sus nu schimbă definițiile fizice, dar în cele ce urmează, vor fii prezentate schimbările aduse definițiilor fizice. Acest sondaj de lucru în redefinirea fizică include: construirea de indici, conversia între arbore-B+ și fișiere hash liniare, și redefinire (ex. divizare) de partiții.

Construirea de indici

În timpul construirii de indici pentru un tabel, un SGBD tradițional permite utilizatorilor să interogheze, dar nu să actualizeze tabelul. Vor fi prezentați algoritmi care construiesc indici concomitent cu actualizările utilizatorilor și interogările din tabel.

Tabelul I compară algoritmii care vor fi prezentați. Titlurile coloanelor din dreapta reprezintă algoritmii. Cele două clase de diferențe în tabel sunt: (1) zona de salvare a actualizărilor utilizatorilor în timpul construirii și (2) principalele etape de a construi indice și de a procesa actualizările salvate, dacă este cazul.

Un asterisc într-o celulă indică faptul că algoritmul folosește zona sau setul de etape.

Un indice parțial [Stonebraker 1989] face referire doar la înregistrările care satisfac o anumită condiție. Un reorganizator pentru construirea unui indice (parțial sau complet) poate scana datele în ordinea paginii, blocarea doar a unei serii de una sau mai multe pagini la un moment dat și construirea indicelui treptat din acele pagini.

Dacă un indice parțial are o condiție logică, preexistența unui indice diferit pe coloanele în condiție poate, desigur, accelera mai mult construirea indicelui parțial [Olson 1993]. Utilizarea unui indice parțial poate accelera o interogare a cărei condiție este cel puțin la fel de restrictivă ca și condiția indicelui. De asemenea, dacă un indice parțial este construit treptat, SGBD poate face indicele parțial disponibil treptat pentru procesarea interogărilor relevante; acesta este un avantaj al indicilor parțiali.

Tabelul I. Compararea algoritmilor pentru construirea online de indici

În continuare, vor fi prezentați zece algoritmi pentru construirea unui indice printr-un reorganizator [Srinivasan și Carey 1991a; Srinivasan 1992]. În timpul unor pași ai fiecărui algoritm, SGBD utilizează o listă actualizată (în loc de indicele construit) pentru a salva inserările încercate ale utilizatorilor și ștergerile din indice. Fiecare algoritm include primele trei operații descrise mai jos, iar unii algoritmi includ ,de asemenea, a patra și/sau a cincea operație:

Reorganizatorul scanează datele. Mai exact, pentru fiecare pagina din tabel, dobândește o citire-blocare, adaugă perechi de valori cheie și RID-urile la un fișier heap și deblochează.

Reorganizatorul sortează datele în fișierul heap, după cheie și RID. Dacă fișierul conține două sau mai multe intrări pentru o pereche de valoare-cheie și RID, sortarea păstrează pe ultima și elimină pe celelalte.

Reorganizatorul construiește indicele, bazat pe una sau două surse. Prima sursă este întotdeauna fișierul heap sortat. Unii din cei zece algoritmi utilizează o a doua sursă (lista actualizată). Aceasta construcție include: (1) eliminarea perechilor duplicate de valori-cheie și RID-uri și (2) aruncarea perechilor de inserări și ștergeri care corespund între ele. Reorganizatorul produce paginile frunză ale indicelui și apoi creează nivelele superioare ale ierarhiei.

Reorganizatorul sortează intrările care sunt în lista actualizată. Dacă lista conține două sau mai multe intrări pentru o pereche de valoare-cheie și RID, sortarea păstrează pe ultima și elimină pe celelalte.

Reorganizatorul procesează intrările care sunt în lista actualizată. Mai precis, pentru fiecare intrare care este o ștergere, reorganizatorul șterge din indice dacă indicele conține perechea de valoare-cheie și RID. Pentru o inserare, acesta inserează în indice dacă indicele nu conține deja perechea.

Construirea offline citește-blochează tabelul, efectuează primele trei operații de mai sus (fără blocare la nivel de pagină), face indicele vizibil la tranzacțiile utilizator și deblochează tabelul.

Algoritmul LXB este cel mai simplu și cuprinde următoarele etape:

Reorganizatorul scanează datele din tabel, sortează datele și construiește indicele dintr-o singură sursă. Fiecare tranzacție utilizator care actualizează datele într-un mod care de obicei ar actualiza indicele (dacă a existat), în schimb scrie-blochează lista actualizată, adaugă un set de informații (valoare cheie, RID, și indicator pentru inserare sau ștergere) la lista actualizată și deblochează lista actualizată. Reorganizatorul scrie-blochează lista actualizată la sfârșitul acestei etape.

Reorganizatorul procesează intrările care se află în lista actualizată. Fiecare tranzacție utilizator care ar actualiza indicele așteaptă finalizarea acestei etape. Reorganizatorul face indicele disponibil utilizatorilor la sfârșitul acestei etape. Tranzacțiile utilizator pot stabili întotdeauna etapa actuală a reorganizatorului.

Toți cei zece algoritmi scanează și sortează datele în etapa 1.

Cei zece algoritmi diferă unul de celălalt prin trei moduri. Prima diferență este:

În timpul unor pași ai algoritmilor (scanarea datelor, sortarea datelor și construirea unui indice doar din date), toți algoritmii permit actualizările încercate de către utilizatori. În timpul altor pași (sortarea actualizărilor, procesarea actualizărilor și construirea unui indice din îmbinarea datelor și a listei actualizate), cei cinci algoritmi din Tabelul 1 interzic actualizări suplimentare ale utilizatorilor.

Cu toate astea, ceilalți cinci algoritmi (LCB, LCS, LCM, ICB și ICM) extind cinci din Tabelul 1 pentru a obține mai multă concurență, permițând astfel, actualizări suplimentare (în etapa 2) și inclusiv o etapă suplimentară (3) pentru a procesa aceste actualizări. ”X” în mijlocul numelui unui algoritm înseamnă ”exclusiv”, iar ”C” înseamnă ”concurent”. În algoritmii C, după blocarea listei actualizate în etapa 1, reorganizatorul copiază, golește și deblochează lista actualizată. Această deblocare permite actualizările suplimentare ale utilizatorilor în etapa 2; utilizatorii reia adăugarea lor la lista actualizată. Reorganizatorul folosește copia listei actualizate pentru procesarea actualizărilor sau pentru a doua sursă în construirea indicelui. Algoritmii C blochează din nou lista actualizată la sfârșitul etapei 2. Acești algoritmi au o a treia etapă, în timpul căreia reorganizatorul procesează lista actualizată (care acum conține actualizările făcute la etapa 2) și utilizatorii inserează și șterg direct în indice. În timpul etapei 3, pentru coordonare între utilizatori și reorganizator, utilizatorii trebuie să pună uneori inserare specială sau ștergere intrări în indice, sortarea reorganizatorului a listei actualizate se ocupă de duplicări într-un mod special și procesarea reorganizatorului de actualizări trebuie să ia în considerare intrările speciale ale utilizatorilor.

A doua diferență dintre algoritmi se ocupă cu lista care salvează actualizările utilizatorilor. Câțiva algoritmi (LXB, LXS, LXM, LCB, LCS și LCM) salvează actualizările utilizatorilor într-o listă secvențială, și câțiva (IXB, IXM, ICB și ICM) folosesc o listă sortată (adică, frunze ale unui indice temporar). ”L” la începutul numelui algoritmului înseamnă ”listă” (secvențială) și ”I” înseamnă ”indice” (sortat). În algoritmii I, pentru salvarea unei actualizări a utilizatorilor, dacă lista sortată conține deja o intrare pentru perechea de valoare-cheie și RID, sistemul șterge intrarea existentă înainte de a insera noua intrare.

A treia diferență implică procesarea actualizărilor salvate. LXB construiește indicele dintr-o sursă în etapa 1. Totuși, câțiva algoritmi (LXM, IXM, LCM și ICM) construiesc indicele în etapa 2 (utilizând actualizările salvate ca o a doua sursă în construire) după blocarea listei actualizate în etapa 1 și (pentru algoritmii L) sortarea listei actualizate în etapa 2. Unii algoritmii (LXS și LCS) sortează și procesează actualizările salvate în etapa 2 după construirea în etapa 1. Câțiva algoritmi (LXB, IXB, LCB și ICB) procesează actualizările salvate în etapa 2 (după construirea în etapa 1) fără sortare. ”M” la sfârșitul numelui unui algoritm înseamnă ”îmbinare” (două surse), ”S” înseamnă ”sortare” și ”B” înseamnă ”de bază” (nu sortare).

În continuare, vor fi prezentați alți doi algoritmi pentru construirea online a unui indice [Mohan și Narang 1992]: ”NSF” și ”SF”. Reorganizatorul scanează datele pentru valorile-cheie și RID-uri, sortează cheile și construiește indicele în timp ce, periodic, punctul de control cel mai mare a inserat cheia. Principala diferență între cei doi algoritmi constă în manipularea inserărilor și ștergerilor tranzacțiilor utilizator în indice în timpul construirii. Algoritmii includ logarea și sunt restartabili. Ei folosesc un algoritm de sortare restartabil, care înlătură rescanarea datelor dacă apare un eșec.

Într-un algoritm (numit NSF pentru ”niciun fișier lateral”), utilizatorii inserează și șterg direct în indice; algoritmul nu folosește o zonă separată pentru a salva inserările și ștergerile. NSF tolerează interferențe de către utilizatori. Atât reorganizatorul, cât și tranzacțiile utilizator scriu intrări jurnal pentru activități în indice. Atunci când apare problema inserării unei chei duplicate, oricare proces este al doilea (reorganizatorul sau un utilizator) se abține de la inserarea duplicatului. Chiar dacă o tranzacție utilizator se abține de la inserarea unei chei, această tranzacție scrie încă o intrare jurnal pentru inserarea omisă. Această înregistrare în jurnal permite corectitudinea unei posibile reveniri întârziate a tranzacției dacă apare o problemă. Pentru a rezolva problema ștergerii cheie, o tranzacție utilizator care încearcă, fără succes, să găsească o cheie pentru a șterge în indice, inserează în schimb, o falsă ștergere cheie și scrie o intrare jurnal. Reorganizatorul nu va introduce mai târziu o cheie acolo.

NSF începe prin actualizările inactive ale indicelui, pentru a asigura lipsa actualizărilor libere. NSF creează apoi un descriptor pentru indice, făcându-l vizibil utilizatorilor pentru inserare și ștergere. Apoi eliberează inactivarea. Fără inactivare, o revenire a unei tranzacții libere care a inserat o înregistrare, nu va șterge cheia înregistrării din indice. Indicele nu este disponibil încă utilizatorilor pentru interogări, deși este posibil să se optimizeze etapa de construcție întârziată prin facerea indicelui treptat disponibil pentru interogări. NSF extrage apoi cheile și RID-urile din date (posibil, inclusiv înregistrări libere) și sortează cheile. După această sortare, NFS inserează cheile în indice și periodic validează inserările. Poate periodic punctul de control cel mai mare a inserat cheia, pentru a evita repornirea de la început dacă a apărut o eroare. Tranzacțiile utilizator înregistrează în jurnal aceste inserări, chiar dacă acestea se abțin chiar de la inserarea datorită problemei de inserare a cheii duplicate. Reorganizatorul înregistrează în jurnal inserările numai când acestea au reușit. După inserarea tuturor cheilor, NSF face indicele disponibil pentru interogări.

Într-un alt algoritm (numit SF pentru fișier lateral), utilizatorii adaugă inserările și ștergerile la un fișier lateral dacă indicele este vizibil; adică, dacă reorganizatorul a scanat deja pagina datelor relevante. În caz contrar, ignoră indicele construit. Tranzacțiile utilizator nu interferează cu construirea indicelui. Reorganizatorul și tranzacțiile utilizator scriu intrări jurnal pentru fișierul lateral, nu pentru indice. Problema inserării cheii duplicate nu apare, deoarece o tranzacție utilizator adaugă o inserare la fișierul lateral doar dacă reorganizatorul a scanat deja pagina datelor relevante, care încă nu conține cheia inserată. Problema ștergerii cheii nu apare, deoarece reorganizatorul procesează fișierul lateral (care include ștergerea) după construirea inițială a indicelui (care include inserarea cheii). Când o tranzacție utilizator adaugă o ștergere la fișierul lateral, intrarea jurnal include numărul indicilor vizibili, pentru a asigura corectitudinea oricărei reveniri întârziate.

SF creează un descriptor pentru indice, scanează datele, sortează cheile, construiește indicele din date și efectuează inserările și ștergerile fișierului lateral în indice.

SF este mai eficient decât NSF, implică mai puțină înregistrare în jurnal, evită eliminările false, probabil se produce un indice mai adunat (deoarece tranzacțiile utilizator nu interferează) și nu are nevoie inițial de actualizări inactive. Totuși, NSF are înregistrarea în jurnal mai puțin sofisticată și anulează cerințele pentru tranzacțiile utilizator.

O altă strategie pentru construirea indicilor este similară cu reorganizarea neclară (coloana marcată ”Mai” în Tabelul 1). Strategia folosește următorii pașii:

Salvează poziția curentă în jurnal. Pentru fiecare rând din tabel, citește rândul și creează o intrare indice, în timp ce utilizatorii pot interoga și actualiza tabelul.

Citește intrările jurnal relevante, pornind din poziția salvată. Pentru fiecare intrare care ar trebui să schimbe indicele, creează una sau două intrări jurnal pentru modificarea indicelui corespunzător și efectuează operațiuni de ”refacere” pentru a aplica intrarea jurnal creată sau intrările la indice. Utilizatorii încă mai pot interoga și actualiza tabelul.

Blochează tabelul. Citește și procesează intrările jurnal ca în pasul anterior, începând după ultima intrare jurnal a pasului anterior.

Face indicele vizibil pentru utilizatori și deblochează tabelul.

Un exemplu de redefinire fizică [Ronstrom 2000], și anume construirea unui indice (coloana ”Ron” în Tabelul 1) creează indicele și scanează tabelul pentru a construi treptat intrări indice. În plus, un declanșator temporar (definit pe tabelul de bază) asigură că pentru oricare rând care include deja indicele, actualizările utilizatorilor rândului actualizează, de asemenea, indicele. Când indicele este complet, SGBD-ul face indicele vizibil la tranzacțiile utilizator.

O altă strategie [Friske et al. 2007] este asemănătoare cu reorganizarea neclară. Aceasta înregistrează poziția jurnal, scanează datele, extrage cheile indice, perechile de chei cu RID-uri, sortează după cheie și RID, construiește indicele, citește intrările jurnal și aplică intrările jurnal la indice (coloana marcată ”Fri” în Tabelul 1).

Conversie între arbore B+ și fișiere hash liniare

Un indice poate lua forma unui arbore B+ [Comer 1979]. Pentru interogări care utilizează indexarea sau cheie întreruptă, arborele B+ poate procesa mai eficient gama de interogări și un fișier hash liniar poate procesa mai eficient interogările potrivite.

Pentru conversia de la un arbore B+, un reorganizator scanează frunzele arborelui B+. Pentru fiecare pagină frunză, au loc următorii pași:

Se setează o blocare exclusivă pe pagina frunză.

Se citește pagina.

Se setează o blocare partajată pe variabilele de stare.

Se calculează adresele de pagini în fișierul hash liniar pentru toate cheile în pagina frunză.

Se inserează datele în fișierul hash liniar. Pentru această inserare, sistemul testează dacă numărul adreselor de pagini distincte depășește o fracție prag a numărului de chei.

Dacă un surplus a avut loc în fișierul hash, se efectuează apoi o divizare.

Se eliberează blocările.

Pentru conversia de la un fișier hash liniar, reorganizatorul continuă în secvența de adresă fizică în fișierul hash. Se citește și se blochează o pagină primară ca o unitate. Pentru fiecare pagină primară, se setează o blocare exclusivă, se citesc paginile, se sortează cheile, se inserează cheile în arborele B+ în ordine și se deblochează.

Redefinirea partițiilor

Pong [1990] menționează divizarea unei partiții în două partiții, permițând în același timp interogări concurente ale partiției.

Troisi [1994;1996] Englert [1994] și Maier et al. [1997] descriu o astfel de divizare, permițând în același timp actualizări concurente. Într-o reorganizare neclară, sistemul creează o nouă partiție, înregistrează poziția curentă a jurnalului, copiază a doua parte (ex. jumătate) a partiției originale în noua partiție, aplică jurnalul la noua partiție, blochează partiția originală, aplică orice intrări jurnal rămase la noua partiție, modifică descriptorii tabelului pentru rutarea acceselor utilizatorilor în partiții și deblochează. Apoi, fizic, sistemul șterge datele copiate din partiția originală, concomitent cu actualizările. Partiția divizată este recuperabilă. Recompilarea poate fi necesară pentru planurile de acces de interogare relevante. În acest SGBD, fiecare partiție include informații despre intervalele tuturor partițiilor. Prin urmare, după aplicarea finală a jurnalului, sistemul trebuie să blocheze scurt întregul tabel pentru a modifica gama de informații. Aceeași strategie de reorganizare neclară poate schimba limita (intervale de valori cheie) între două partiții adiacente sau poate muta o partiție de la o zonă de disc la alta.

Într-o altă strategie,când se adaugă o partiție goală inițial, noua partiție poate fi disponibilă imediat, cu nicio reorganizare a instanțelor necesară [Friske 2004a].

STRATEGII PENTRU REDEFINIREA LOGICĂ ONLINE

Redefinirea logică poate afecta, nu doar instanțele de date, dar și definiția fizică, definițiile vizate, metodele obiectelor și programele aplicație [Sockut 1985]. Cu toate astea, strategiile descrise mai jos pot reduce impactul. Pentru unele tipuri de redefinire logică, afișările pot apăra programele aplicație preexistente din modificări. Sistemul oferă un set neschimbat de interfețe pentru afișări pe perioada modificării definițiilor interne ale afișărilor pentru a se adapta schimbărilor.

Interpretarea și reorganizarea incrementală în timpul activităților utilizatorilor

Strategiile pentru redefinirea logică prin interpretarea și/sau reorganizare incrementală în timpul activităților utilizatorilor, permit executarea unui program aplicație a cărui versiune de schemă diferă de versiunea de schemă care utilizează, în prezent, instanțele de date accesate. Când proiectantul bazei de date specifică redefinirea, SGBD înregistrează schimbarea și nu trebuie să efectueze imediat orice schimbare fizică la instanțele de date preexistente.

Gerritsen și Morgan [1976] descriu o astfel de strategie. Un proiectant de bază de date folosește un limbaj de redefinire pentru a specifica schimbările, ex. mutarea unui element de date între tipuri de înregistrări. Când un program accesează o instanță, SGBD efectuează următorii pași:

Dacă instanța utilizează oricare din versiunile vechi ale schemei, traduce instanța la cea mai recentă versiune definită. Pentru o interogare, această traducere apare numai în stocarea volatilă; instanța continuă să utilizeze versiunea veche în stocarea persistentă. Pentru o actualizare, SGBD va stoca fiecare instanță actualizată în stocarea persistentă folosind versiunea definită cel mai recent. Asta obține reorganizarea incrementală în stocarea persistentă.

Dacă programul utilizează orice versiune veche, prezintă instanța (programului) în forma care utilizează vechile versiuni. Totuși, dacă un program încearcă să citească sau să modifice ceva ce nu mai există, abandonează programul.

Se utilizează strategia lui Clamen [1994] pentru a ilustra tehnici pentru interpretarea și reorganizarea incrementală în SGBD-uri orientate obiect. Va fii prezentat comportamentul logic al strategiei și apoi posibilele tehnici pentru a pune în aplicare comportamentul logic. În această strategie, fiecare instanță obiect este logic o instanță a fiecărei versiuni a clasei sale obiect și, astfel, conține logic toate atributele fiecărei versiuni. Când un utilizator modifică atributele unei versiuni, modificarea propagă logic imediat la orice atribute relevante ale oricărei alte versiuni.

Pentru fiecare versiune și relațiile sale cu alte versiuni, proiectantul bazei de date poate alege o implementare pentru fiecare din câteva aspecte ale redefinirii logice. Un aspect implică adăugarea și inițializarea atributelor unei noi versiuni. La specificarea unei noi versiuni a unei clase obiect, proiectantul are următoarele opțiuni:

Pentru fiecare instanță a acestei clase obiect, se adaugă și inițializează imediat atributele noii versiuni a clasei.

Pentru fiecare instanță a acestei clase obiect, se adaugă și inițializează atributele noii versiuni a clasei doar când un utilizator trimite târziu această instanță prin intermediul acestei versiuni. Această reorganizare incrementală salvează spațiu. Se salvează o cantitate mare de timp pe parcursul specificării versiunii, dar este nevoie de timp în decursul unor execuții întârziate.

Un al doilea aspect implică propagarea de modificări din atributele unei versiuni la atributele alteia (dacă versiunile ocupă spații distincte). Proiectantul are următoarele opțiuni:

Modificarea unei versiuni propagă fizic imediat la altă versiune.

Un indicator este asociat cu fiecare versiune în fiecare instanță pentru a indica dacă atributele acestei versiuni sunt la zi în raport cu cealaltă versiune. Când un utilizator modifică prima versiune, SGBD setează indicatorul pentru cealaltă versiune pentru a indica ”ieșirea datelor”, dar nu propagă valorile. Când un utilizator citește instanța prin intermediul celei de-a doua versiuni, SGBD propagă valorile din prima versiune la cea de-a doua și resetează indicatorul. Această alegere accelerează scrierea oricărei versiuni, dar încetinește citirea unei versiuni care este afară din date.

Al treilea aspect implică spațiul pentru atribute comune. De obicei, proiectantul alege pentru atributele comune să ocupe același spațiu; asta economisește spațiu și timp.

Al patrulea aspect implică spațiul pentru atribute derivate reciproc. Proiectantul poate alege între ocuparea aceluiași spațiu și ocuparea spațiilor separate. Dacă atributele ocupă același spațiu, o altă decizie este dacă acel spațiu stochează prima versiune, a doua versiune sau (pentru fiecare instanță) versiunea care a fost scrisă cel mai recent. Dacă spațiul stochează întotdeauna prima versiune (sau a doua), citirea sau scrierea acestei versiuni este rapidă și citirea sau scierea unei alte versiune necesită interpretare. Dacă spațiul stochează versiunea care a fost scrisă cel mai recent, orice scriere este rapidă, citirea unei versiune stocate mai recent este rapidă și citirea unei versiuni stocate mai puțin recent necesită interpretare. Dacă atributele ocupă spații separate, citirea și scrierea sunt lente dacă necesită propagare imediată; sunt rapide dacă nu necesită.

Utilizarea unui reorganizator

În continuare vor fii prezentate strategii care includ un reorganizator combinat cu activități care au loc în timpul activităților utilizatorilor.

Wilson [1980] prezintă o arhitectură care utilizează un reorganizator pentru a efectua redefinirea logică în loc și care utilizează modelul de date CODASYL. În această arhitectură, o schemă de tranziție (care include vechile și noile scheme și înrudirile lor) descrie baza de date în timpul reorganizării. De exemplu, mulțimea tipurilor CODASYL în schema de tranziție poate relata tipuri de înregistrări în schema veche și schema nouă, dacă valorile unei noi instanțe înregistrate sunt derivate din vechile instanțe înregistrate. Proiectantul bazei de date poate specifica procedurile pentru a deriva valorile. Pentru orice program aplicație, SGBD prezintă doar schema veche sau schema nouă.

În abordarea lui Ronstrom [2000], tranzacțiile preexistente utilizează schema veche și noile tranzacții utilizează schema nouă. Unele cazuri de redefinire nu necesită inactivare. Se sugerează schimbări separate de lungă durată în mai multe tranzacții mici pentru a evita tranzacțiile lungi de reorganizare. Această abordare implică cinci pași. Multe detalii ale primelor două etape depind de tipul specific de redefinire. Etapele sunt:

Reorganizatorul adaugă orice coloane necesare, tabele, indici, declanșatoare și chei străine. Unele declanșatoare adăugate și chei străine asigură că instanțele noilor coloane, tabele și indici vor fi la zi la sfârșitul etapei 2. Coloanele adăugate permit valorille nule, deși le interzic începând cu etapa 5 dacă schema nouă interzice valorile nule. Dacă schema nouă omite o coloană veche, tabel, indice sau cheie străină, atunci eliminarea efectivă are loc în etapa 5.

Reorganizatorul scanează datele vechi și efectuează orice acțiuni care sunt necesare pentru a face vechile și noile date compatibile.

Administratorul bazei de date poate efectua tranzacții de testare pe noua schemă. Dacă schimbările sunt grele, administratorul trebuie întâi să inactiveze tranzacțiile.

Dacă testările sunt de succes, noile tranzacții pot începe și utilizează noua schemă. Vechile tranzacții continuă pe schema veche.

După ce au fost terminate toate tranzacțiile vechi, reorganizatorul poate elimina orice declanșatoare și coloane pe care reorganizatorul le-a utilizat, și elimină orice coloane vechi, tabele, indici și chei străine pe care noua schemă le-a omis

Primul exemplu de redefinire este adăugarea coloanelor care sunt derivate din vechile coloane (și, dacă se dorește, eliminarea coloanelor vechi). Etapa 1 include adăugarea coloanelor, adăugarea unui declanșator pentru a actualiza noile coloane să reflecte actualizările cele vechi, și adăugarea unui declanșator pentru inversul primului declanșator. Etapa 2 scanează tabelul și actualizările noilor coloane, bazate pe cele vechi.

Un exemplu de redefinire fizică este construirea unui indice. În etapa 1, reorganizatorul creează indicele (care nu este încă disponibil tranzacțiilor utilizator) și creează (în tabelul de bază) o coloană a cărei prezență într-un rând indică faptul că indicele include o intrare pentru acel rând. Un declanșator asigură că o actualizare a unui rând, de asemenea, actualizează indicele dacă indicele include deja o intrare pentru acel rând sau dacă actualizarea inserează un rând în tabel. Etapa 2 așteaptă pentru finalizarea tuturor tranzacțiilor utilizator care au început înainte de crearea declanșatorului. Reorganizatorul apoi scanează tabelul și construiește intrări în indice pentru rândurile care nu au încă coloană. În etapa 3, după testarea cu succes, reorganizatorul face indicele disponibil tranzacțiilor utilizator.

Alte exemple de redefinire includ divizarea unui tabel (după rânduri sau coloane) și îmbinarea tabelelor. Aici, declanșatoarele asigură că noile tabele și indicii reflectă actualizări ale tabelelor inițiale și că tabelele inițiale și indicii reflectă actualizări ale noilor tabele. În plus, dacă vechile chei străine se referă la tabelele inițiale, declanșatoarele asigură că noile chei străine se referă eventual, în mod corect, la noile tabele.

O altă facilitate online [Friske 2004b] se aplică la câteva tipuri de redefinire logică (schimbarea tipurilor de date și lungimi) și câteva tipuri de redefinire fizică (ex. adăugarea coloanelor la indici și schimbarea indicilor între clustering și nonclustering). Redefinirea intră în vigoare imediat în catalogul bazei de date, dar SGBD nu schimbă imediat instanțele de date în stocare. Pentru interogare, SGBD materializează noul format interpretativ, și pentru actualizare, SGBD depozitează instanțele actualizate în noul format. În timpul următoarei întrețineri, care poate fi online (prin intermediul unui reorganizator) sau offline, SGBD depozitează toate instanțele în noul format.

În lucrarea lui Loland și Hvasshovd [2006], un reorganizator utilizează reorganizarea neclară (cu iterații de prelucrare jurnal) pentru a efectua oricare dintre cele două exemple specifice redefinirii logice:

O nouă tabelă este asocierea exterioară completă a celor două tabele vechi.

Două noi tabele sunt rezultatul divizării unui tabel vechi.

CAPITOLUL IV

APLICAȚIE

CONCLUZII

Reorganizarea unei baze de date este o schimbare a unor aspecte ale aranjamentului fizic și/sau logic al bazei de date. În această lucrare, au fost prezentate mai multe tipuri de reorganizare, și în practică, orice sistem de management de baze de date poate avea nevoie de un anumit tip. Pentru a evita luarea unei disponibilității ridicate sau bază de date foarte mare offline pentru reorganizare, o soluție este să se reorganizeze online (concomitent cu utilizarea, treptat în timpul activităților utilizatorilor sau interpretativ). S-au identificat cerințele pentru reorganizarea online. Designul reorganizării online implică compromisuri în rezolvarea anumitor probleme, inclusiv utilizarea partițiilor, procesul care reorganizează, reorganizarea prin copiere, utilizarea fișierelor diferențiale, referințe la datele care au fost mutate, performanța și activarea întreținerii.

Lucrarea a avut loc în întreținerea online, redefinirea fizică și redefinirea logică. O mare parte din această lucrare a apărut în contexte de cercetare și o parte a apărut în contexte comerciale. Lucrarea comercială în reorganizarea online și zonele relatate includ subiectele de reorganizare a unei partiții, reorganizatori, interpretare și reorganizare incrementală în timpul activităților utilizatorilor, reorganizare în loc, reorganizare prin copiere, reorganizare neclară, utilizarea tabelelor de mapare (și alte tehnici de corectare referințe), pauza între etapele reorganizării, activarea întreținerii, restaurarea de clustering, reorganizarea unui indice, curățarea într-un sistem de fișiere jurnal structurat, construirea unui indice, redefinirea partițiilor (divizare sau mutare), redefinirea logică în timpul activităților utilizatorilor și redefinirea logică prin intermediul unui reorganizator.

S-a arătat că unele subiecte implică complexitate sau au nevoie de mai multă cercetare. Aceste subiecte includ urmărirea reorganizării și utilizatorilor a stării acțiunilor celuilalt pe date, tranziții între accesarea vechilor și noilor copii într-o strategie de copiere, coordonarea acceselor concurent ale vechilor și noilor copii dacă două copii ale zonei reorganizate conțin uneori copii valide ale acelorași instanțe și activarea întreținerii online.

Nu toate bazele de date sunt extrem de disponibile și foarte mari. Totuși, ca dependența pe computere și cantitatea de informații în baza de date să crească, bazele de date extrem de disponibile sau foarte mari vor continua să devină mai frecvente și mai importante în economia mondială. Cu toate astea, importanța reorganizării online va continua să crească.