PROIECTAREA ALOCARII

PROIECTAREA ALOCARII

Fie un set de fragmente F = intr-o retea formata din siteurile S = si asupra carora se executa anumite aplicatii (interogari) Q = . Problema proiectarii alocarii se refera la distribuirea optima a fragmentelor F pe siturile S.

Potrivit lui Dowdy si Foster, "optimul"  se refera la:

• Cost minim. Functia cost - compusa din:
• costul plasarii fragmentului F_i pe site-ul S_j
• costul interogarii S_j de catre F_i
• costul actualizarii tuturor fragmentelor F_i plasate in toate siteurile
• costul comunicatiei.

Problema alocarii - gasirea unei scheme de minimizare a costurilor.

• Performanta. Strategia de proiectare - mentinerea unui nivel de performanta prin minimizarea timpului de raspuns si maximizarea capacitatilor sistemului ca masura a contributiei fiecarui site.[1]

Alocarea - neredundanta sau redundanta

• Alocarea neredundanta - mai ieftina ca efort de proiectare si mai usor de realizat. Alt avantaj - posibilitatea de actualizare a fragmentelor. Se bazeaza pe metoda celei mai bune alegeri - unei statii pe care deja a fost plasat un fragment, nu poate sa-i mai fie alocat un fragment "inrudit".
• Alocarea redundanta - mai complexa. Consultarile de date si actualizarile sunt problematice. Exista doua variante de abordare a proiectarii in acest caz:

a)        Metoda selectarii - identificarea siturilor pentru care beneficiul alocarii unei copii depaseste costul alocarii;

b)        Metoda alocarii progresive - se implementeaza initial o alocare neredundanta. Apoi, in functie de gradul de profitabilitate al statiilor se vor raspandi replici ale fragmentelor deja alocate, pana cand nu mai exista candidati la replicare.

Prima metoda (selectarea) este mai riguroasa si elimina posibilitatea de a inmagazina pe acelasi site si copia fragmentului deja stocat.

Replicarea progresiva - metoda euristica - bazata pe asertiunea ca profitabilitatea scade pe masura ce gradul de redundanta creste.[2]

Abordare mai eficienta, dar si mai selectiva - metoda celei mai bune alegeri si in etapa de proliferare a copiilor. Se incepe cu fragmentele considerate ca fiind cele mai importante, tinandu-se cont la fiecare alocare de relatia de "rudenie" a tuturor fragmentelor ce exista sau urmeaza a fi stocate intr-un site.

Formule de evaluare a costurilor si beneficiilor implicate de alocarea fragmentelor [Lungu 1995], paginile 308 - 310:

Conventii in utilizarea notatiilor:

i - indice fragment;

j - indice site;

k - indice aplicatie sau cerere;

f_kj - frecventa cererii k la site-ul j;

r_ki - numarul acceselor de regasire (citire, consultare) ale cererii k pentru fragmentul i;

w_ki - numarul acceselor de actualizare (scriere) ale cererii k pentru fragmentul i;

n_ki = r_ki + w_ki.

Alocarea fragmentelor orizontale

Metoda alocarii neredundanta. Se aloca fragmentul F_i la statia unde numarul de referiri la F_i este maxim. Calcularea numarului de referiri locale ale fragmentului F_i in situl S_j - → fragmentul F_i va fi alocat la statia pentru care B_ij este maxim.

Metoda statiilor profitabile. Fragmentul F_i va fi plasat in acele situri j, unde costul referintelor de regasire este mai mare decat costul referintelor de actualizare in alte situri. Beneficiul B_ij - o diferenta:

C - constanta ce cuantifica raportul dintre costul unei citiri si costul unei scrieri. In majoritatea cazurilor, C

→ Fi - alocat la statiile j pentru care B_ij este pozitiv. Daca B_ij ia numai valori negative, se va selecta maximul dintre acestea.

• Metoda replicarii progresive - beneficiul stocarii unei noi replici se masoara in functie de siguranta si disponibilitatea sistemului.

d_i - gradul de redundanta a lui F_i

P_i - beneficiul de a avea cate o copie a lui F_i in fiecare sit

Beneficiul: β(d_i) = (1 - 2^1-d_i) P_i

Alocarea fragmentelor verticale

• Partitionarea atributelor - masurarea beneficiului fragmentarii unui fragment F_i alocat la statia j, in doua fragmente F_s si F_t plasate in siturile s si t se considera si seturile de aplicatii ce acceseaza atributele din cele doua fragmente disparate vor fi q_s si q_t. Aceste cereri sunt cereri locale. Exista inca trei seturi de aplicatii: Q₁, Q₂ si Q₃, - Q₁ - local statiei r, care utilizeaza numai atribute ale fragmentelor F_s si F_t. Cererile Q₁ necesita un acces la distanta. Setul Q₂ - rezident in site-ul r si acceseaza atribute din ambele fragmente (q si t). Aici vom avea doua accese la distanta. Q₃ apartine altor situri decat r, s, sau t, dar utilizeaza si fragmentul F_s, cat si F_t. Beneficiul acestei partitionari se cuantifica astfel:

Formula - numara atat accesele locale, cat si cele la distanta. Se poate rescrie prin inlocuirea lui n_ki cu r_ki + C w_ki.

Pentru determinarea schemei de alocare a fragmentelor Fs si Ft se va calcula beneficiul pentru toate combinatiile posibile ale siturilor s si t, alegandu-se perechea pentru care se realizeaza beneficiu maxim.

• Gruparea atributelor - proiectarea fragmentelor - rezultat fragmente nedisjuncte. Problema descrisa in paragraful anterior - un set comun de atribute I. Gruparea verticala va prezenta particularitati si in ceea ce priveste cererile implicate.
• Q_s - setul de aplicatii locale site-ului s, care citesc sau actualizeaza orice atribut al fragmentului F_s, dar care nu se suprapun cu I.
• Q₂ - cererile de actualizare aflate pe statia r - actualizarea atributelor setului I si necesita acces atat la F_s, cat si la F_t.
• Q₃ - aplicatii din alte statii decat cele amintite, care actualizeaza atributele setului I si necesita acces atat la F_s, cat si la F_t.

→ Formula descrisa in cazul abordarii anterioare este valabila si in cazul gruparii → alocarea trebuie sa asigure regasirea facila a fragmentelor prin conferirea unui plasament optim, astfel ca sa se reduca pe cat posibil numarul de accese la distanta. In afara de componenta costului de comunicatie, alocarea trebuie sa tina cont si de celelalte aspect relative costului proiectarii alocarii.