Algoritmi distribuiti in baze de date NoSql - stst.elia.pub. Tehnicile de coordonare, cum ar fi...

download Algoritmi distribuiti in baze de date NoSql - stst.elia.pub. Tehnicile de coordonare, cum ar fi alegerea

of 22

  • date post

    31-Aug-2019
  • Category

    Documents

  • view

    3
  • download

    0

Embed Size (px)

Transcript of Algoritmi distribuiti in baze de date NoSql - stst.elia.pub. Tehnicile de coordonare, cum ar fi...

  • ALGORITMI DISTRIBUITI

    IN BAZE DE DATE NOSQL

    Reele de calculatoare n internet

    Student: Alexandru Nicolae ION

  • Contents Algoritmi distribuii n baze de date NoSql .................................................................................... 1

    Consistena datelor .......................................................................................................................... 2

    Replicarea ................................................................................................................................... 2

    Obiectivele replicrii ................................................................................................................... 3

    Plasarea datelor ............................................................................................................................. 10

    Rebalansarea ............................................................................................................................. 10

    Sharding si replicarea n medii dinamice .................................................................................. 12

    Sharding pentru mai multe atribute........................................................................................... 14

    Coordonarea sistemului ................................................................................................................ 16

    Detectarea defectelor ................................................................................................................ 16

    Alegerea coordonatorului.......................................................................................................... 17

    Concluzii ....................................................................................................................................... 19

    Bibliografie ................................................................................................................................... 20

  • 1

    Algoritmi distribuii n baze de date NoSql

    Scalabilitatea este unul dintre motoare principalele ale micrii NoSQL. Ca atare, aceasta

    cuprinde un sistem de coordonare distribuit, tolerana la defecte, managementul resurselor i

    multe alte capaciti. Sun ca o umbrel mare i chiar este. Dei poate fi spus cu greu c micarea

    NoSQL a adus noi tehnici fundamental diferite de prelucrare a datelor distribuite, aceasta a

    declanat o avalan de studii practice i studii reale cu diferite combinaii de protocoale i

    algoritmi. Aceste dezvoltri au evideniat treptat un sistem de blocuri de construcie de baze de

    date relevante cu eficien dovedit practic. Acest proiect ncerc s furnizez o descriere mai

    mult sau mai puin sistematic de tehnici legate de operaiuni n baze de date NoSQL

    distribuite.[1]

    Vom studia o serie de activiti, cum ar fi replicarea, detectarea eecului, care ar putea

    aprea ntr-o baz de date. Aceste activiti, evideniate mai jos cu caractere ingroate, sunt

    grupate n trei seciuni principale:

    Consistena datelor. Din punct de vedere istoric, NoSQL i-a ndreptat atenia ctre

    compromisuri ntre consisten, toleran la erori i performan, pentru a servi sisteme

    distribuite geografic, laten mic sau aplicaii extrem de disponibile. Fundamental, aceste

    compromisuri se nvrt n jurul consistenei datelor, astfel nct aceast seciune este dedicat

    replicarii datelor i reparaiilor de date.

    Plasarea datelor. O baz de date ar trebui s se acomodeze la distribuii de date diferite,

    topologii de grup i configuraii hardware. n aceast seciune vom discuta despre cum s

    distribuim sau reechilibra datele n aa fel nct eecurile sunt tratate rapid, garaniile de

    persistenta sunt meninute, interogrile sunt eficiente, i resursele de sistem cum ar fi RAM sau

    spaiu pe disc sunt folosite n mod egal de-a lungul clusterului.

    Coordonarea sistemului. Tehnicile de coordonare, cum ar fi alegerea liderului sunt

    folosite n multe baze de date pentru pune n aplicare tolerana la erori i o puternic coeren a

    datelor. Cu toate acestea, chiar bazele de date descentralizate i urmresc de obicei starea lor

    global, detecteaz defeciuni i modificri de topologie. Aceast seciune descrie mai multe

    tehnici importante care sunt folosite pentru a menine sistemul ntr-o stare coerent.[1]

  • 2

    Consistena datelor

    Este bine cunoscut i destul de evident c, n sistemele distribuite geografic sau alte medii

    cu partiii de reea sau ntrzieri, n general nu este posibil s se menin o disponibilitate

    ridicat, fr a sacrifica consistena, din cauza prilor izolate ale bazei de date care trebuie s

    funcioneze independent n cazul de partiiilor de reea. Acest fapt este adesea menionat ca

    teorema CAP. Cu toate acestea, consistena este un lucru foarte scump n sistemele distribuite,

    nct poate fi negociat nu numai cu disponibilitatea. Acesta este adesea implicat n mai multe

    compromisuri. Pentru a studia aceste compromisuri, observm n primul rnd c problemele de

    coeren n sistemele distribuite sunt induse de replicare i de separarea spaial a datelor cuplate,

    aa c trebuie s ncepem cu obiectivele i proprietiile dorite ale replicrii.[1]

    Replicarea

    Unele din principalele cerinte ale sistemelor distribuite sunt fiabilitatea si disponibilitatea.

    In conformitate cu acestea defectarea unuia dintre nodurile sistemului nu va paraliza functionarea

    sistemului si nici nu va afecta disponibilitatea datelor care au fost nmagazinate la nodul

    respectiv. De cele mai multe ori sunt pstrate mai multe copii ale acelorai date n mai multe

    locaii cu scopul realizarii autonomiei locale cerute i a creterii disponibilitii. Pentru a se

    asigura consistena bazei de date este obligatorie replicarea fragmentelor ntre locaii n scopul

    reflectrii modificrilor asupra acestora. Aducerea la zi a datelor pstrate n mai multe copii ca

    fragmente distribuite poart denumirea de replicare.[2]

    Replicarea este un proces care const n realizarea i distribuirea unor copii a datelor,

    numite i replici n scopul asigurrii posibilitii de procesare local a acestora, oferind astfel un

    nivel ct mai ridicat de autonomie pentru bazele de date locale. Un nivel ridicat de autonomie i

    implicit de disponibilitate, implic o serie de concesii privind actualitatea informatiei utilizate.[2]

    Replicarea este o tehnologie care permite ca informaii ce provin de la una sau mai multe

    surse s poat fi distribuite catre una sau mai multe inte, cu propagarea consistent a

    modificrilor intervenite la surse catre intele corespunzatoare.[2]

    Este logic s considerm c procesul de replicare nu se refer la replicarea ntreagii baze

    de date, care ar ncrca foarte mult sistemul de comunicaie, ci doar un set de date, element care

    complic suplimentar procesul de replicare. Un alt termen des ntlnit n tehnologia replicrii

    este cel de sincronizare, ca fiind procesul prin care se asigur capturarea, propagarea i

    reproducerea la inte a actualizarilor de la surse.[2]

  • 3

    Obiectivele replicrii

    Disponibilitatea. Pri izolate ale bazei de date pot servi cereri de citire/scriere n caz de

    partiionare de reea.

    Latena la scrire/citire. Cererile de scrire/citire sunt procesate cu laten minim.

    Scalabilitatea la citire/scrire. Cererile de citire/scriere pot fi mprite pe mai multe

    noduri.

    Tolerana la defecte. Abilitatea de a deservi cereri de citire/scriere nu depinde de

    disponibilitatea unui nod particular.

    Persistenta datelor. Defectul nodurilor n masura unor limite nu duce la pierderea datelor.

    Consistena. Consistena este o proprietate mult mai complicat dect cele precedente.[1]

    Consistena la citire-scrire. Din perspectiva citire/scriere, scopul cel mai de baz al unei baze

    de date este de a minimiza timpul de convergen al unei replici, adic timpul necesar pentru a

    propaga o actualizare la toate replicile i eventual s garanteze i consistena. Pe lng aceste

    garanii slabe, putem fi interesai de garanii de consisten mai puternice:

    Consistena citire dup scriere. Efectul unei operaii de scriere pe un item X, va fi vzut

    ntotdeauna ca o operaie de citire succesiv pe X.

    Consistena citire dupa citire. Daca unii clieni citesc valoarea unui item X, orice citire

    succesiv pe X va returna ntotdeauna aceeai valoare sau o valoare mai recent.

    Consistena la scriere-scriere. Conflictele de tip scriere-scriere apar n cazul partiionrii

    bazei de date, deci o baza de date ar trebui ori s gestioneze aceste conflicte ntr-un mod anume,

    ori s garanteze ca scrierile concurente nu vor fi procesate de diferite partiii. Din aceast

    perspectiv, o baz de date poate oferi 2 modele de consisten:

    Operaii de scriere atomice. n cazul n care o baz de date ofer un API n care o cerere de

    scriere nu poate fi dect o asignare atomic i independent de o valoare, un mod posibil mod de

    a evita conflictele scrie-scriere este de a alege "cea mai recent" versiune a fiecrei entiti. Acest

    lucru garanteaz c toate nodurile vor avea aceeai versiune a datelor, indiferent de ordinea de

    actualizri care pot fi afectate de erori i ntrzieri de reea. Versiunea datelelor pot fi specificat

    prin intermediul amprentelor de timp, numite i timestamp, sau folosind metrici specifice

    aplicaiei. Aceast abordare este folosit, de exemplu, n Cassandra.[1]

    Operaii de citire-modificare-scriere atomice. Aplicaiile realizeaz n mod obinuit secvene

    de citire-modificare-scriere n loc de scrieri atomice independente. n