Control simultan multiversiune - Multiversion concurrency control

Controlul concurenței multiversiune ( MCC sau MVCC ), este o metodă de control al concurenței utilizată în mod obișnuit de sistemele de gestionare a bazelor de date pentru a oferi acces simultan la baza de date și în limbaje de programare pentru a implementa memoria tranzacțională .

Descriere

Fără control simultan, dacă cineva citește dintr-o bază de date în același timp în care altcineva îi scrie, este posibil ca cititorul să vadă o bucată de date pe jumătate scrisă sau inconsistentă . De exemplu, atunci când efectuați un transfer bancar între două conturi bancare dacă un cititor citește soldul la bancă atunci când banii au fost retrași din contul original și înainte de a fi depuși în contul de destinație, s-ar părea că banii au dispărut din bancă. Izolarea este proprietatea care oferă garanții în accesele simultane la date. Izolarea este implementată prin intermediul unui protocol de control al concurenței . Cea mai simplă modalitate este de a-i face pe toți cititorii să aștepte până la terminarea scriitorului, ceea ce este cunoscut sub numele de blocare de citire-scriere . Se știe că blocările creează controverse, în special între tranzacțiile cu citire lungă și tranzacțiile de actualizare. MVCC își propune să rezolve problema păstrând mai multe copii ale fiecărui element de date. În acest fel, fiecare utilizator conectat la baza de date vede un instantaneu al bazei de date la un moment dat. Orice modificare făcută de un scriitor nu va fi văzută de alți utilizatori ai bazei de date până când modificările nu vor fi finalizate (sau, în termenii bazei de date: până la efectuarea tranzacției .)

Când o bază de date MVCC trebuie să actualizeze o bucată de date, aceasta nu va suprascrie elementul de date original cu date noi, ci va crea o versiune mai nouă a elementului de date. Astfel, există mai multe versiuni stocate. Versiunea pe care o vede fiecare tranzacție depinde de nivelul de izolare implementat. Cel mai comun nivel de izolare implementat cu MVCC este izolarea instantanee . Cu izolarea instantanee, o tranzacție observă o stare a datelor ca atunci când tranzacția a început.

MVCC oferă vizualizări coerente punct-în-timp . Tranzacțiile de citire în cadrul MVCC utilizează de obicei un timestamp sau un ID de tranzacție pentru a determina ce stare a bazei de date să citească și să citească aceste versiuni ale datelor. Tranzacțiile de citire și scriere sunt astfel izolate unele de altele, fără a fi nevoie de blocare. Cu toate acestea, în ciuda blocărilor inutile, acestea sunt utilizate de unele baze de date MVCC, cum ar fi Oracle. Scrierile creează o versiune mai nouă, în timp ce citirile simultane accesează o versiune mai veche.

MVCC introduce provocarea de a elimina versiunile care devin învechite și care nu vor fi citite niciodată. În unele cazuri, este implementat un proces pentru a muta periodic și a șterge versiunile învechite. Acesta este adesea un proces stop-the-world care traversează un tabel întreg și îl rescrie cu ultima versiune a fiecărui element de date. PostgreSQL poate folosi această abordare cu procesul său de ÎNGELARE VACUUM . Alte baze de date împart blocurile de stocare în două părți: partea de date și un jurnal de anulare. Partea de date păstrează întotdeauna ultima versiune angajată. Jurnalul de anulare permite recreerea versiunilor mai vechi de date. Principala limitare inerentă a acestei din urmă abordări este că, atunci când există încărcări de lucru cu actualizare intensivă, partea de jurnal de anulare rămâne fără spațiu și apoi tranzacțiile sunt întrerupte deoarece nu li se poate da instantaneul. Pentru o bază de date orientată spre documente, acesta permite, de asemenea, sistemului să optimizeze documentele prin scrierea documentelor întregi pe secțiuni adiacente ale discului - când este actualizat, întregul document poate fi rescris mai degrabă decât biți și bucăți decupate sau menținute într-un link legat, non- structură de bază de date contiguă.

Implementare

MVCC folosește timestamps ( TS ) și ID-uri de tranzacție incrementale , pentru a obține consistența tranzacțională . MVCC asigură că o tranzacție ( T ) nu trebuie să aștepte niciodată să citească un obiect de bază de date ( P ) prin menținerea mai multor versiuni ale obiectului. Fiecare versiune a obiectului P are atât un timestamp de citire ( RTS ), cât și un timestamp de scriere ( WTS ), care permite unei anumite tranzacții T i să citească cea mai recentă versiune a obiectului care precede tranzacția de citire a timestampului RTS ( T i ).

Dacă tranzacția T i vrea să scrie la obiectul P și există, de asemenea, o altă tranzacție T k care se întâmplă cu același obiect, Read Timestamp RTS ( T i ) trebuie să preceadă Read Timestamp RTS ( T k ), adică RTS ( T i ) < RTS ( T k ) , pentru ca obiectul Operațiune de scriere ( WTS ) să aibă succes. O scriere nu se poate finaliza dacă există alte tranzacții restante cu un timp de citire anterioară ( RTS ) către același obiect. Ca și cum ați sta la coadă la magazin, nu vă puteți finaliza tranzacția de plată până când cei din fața dvs. nu le-au finalizat.

A reteta; fiecare obiect ( P ) are un Timestamp ( TS ), cu toate acestea, dacă tranzacția T i vrea să scrie pe un obiect, iar tranzacția are un Timestamp ( TS ) care este mai devreme decât actualul obiectului Read Timestamp, TS ( T i ) < RTS ( P ), atunci tranzacția este întreruptă și repornită. (Acest lucru se datorează faptului că o tranzacție ulterioară depinde deja de vechea valoare.) În caz contrar, T i creează o nouă versiune a obiectului P și setează marcajul temporar de citire / scriere TS al noii versiuni la marcajul de timp al tranzacției TS ← TS ( T i ).

Dezavantajul acestui sistem este costul stocării mai multor versiuni de obiecte în baza de date. Pe de altă parte, citirile nu sunt niciodată blocate, ceea ce poate fi important pentru sarcinile de lucru care implică în principal valorile citirii din baza de date. MVCC este deosebit de abil în implementarea adevăratei izolări instantanee , lucru pe care alte metode de control al concurenței îl fac frecvent fie incomplet, fie cu costuri ridicate de performanță.

Exemple

Citire-scriere simultană

La ora = 1, starea unei baze de date ar putea fi:

Timp Obiectul 1 Obiectul 2
0 „Foo” de T0 „Bar” de T0
1 „Bună ziua” de T1

T0 a scris Obiectul 1 = "Foo" și Obiectul 2 = "Bara". După aceea T1 a scris Obiectul 1 = „Bună ziua” lăsând Obiectul 2 la valoarea sa inițială. Noua valoare a obiectului 1 va înlocui valoarea la 0 pentru toate tranzacțiile care încep după ce T1 se angajează, moment în care versiunea 0 a obiectului 1 poate fi colectată la gunoi.

Dacă o tranzacție de lungă durată T2 pornește o operație de citire a obiectului 2 și a obiectului 1 după comiterea T1 și există o tranzacție de actualizare simultană T3 care șterge obiectul 2 și adaugă obiectul 3 = "Foo-Bar", starea bazei de date va arăta astfel la timpul 2:

Timp Obiectul 1 Obiectul 2 Obiectul 3
0 „Foo” de T0 „Bar” de T0
1 „Bună ziua” de T1
2 (șters) de T3 „Foo-Bar” de T3

Există o nouă versiune din momentul 2 al obiectului 2 care este marcată ca ștearsă și un nou obiect 3. Deoarece T2 și T3 rulează concomitent, T2 vede versiunea bazei de date înainte de 2, adică înainte ca T3 să se angajeze în scris, ca atare T2 citește obiectul 2 = "Bara" și Obiectul 1 = "Bună ziua". Acesta este modul în care controlul concurenței multiversiune permite citirea izolării instantanee fără blocări.

Istorie

Controlul concurenței cu mai multe versiuni este descris în detaliu în lucrarea din 1981 „Controlul concurenței în sisteme de baze de date distribuite” de Phil Bernstein și Nathan Goodman, atunci angajată de Computer Corporation of America . Lucrarea lui Bernstein și Goodman citează o disertație din 1978 a lui David P. Reed care descrie destul de clar MVCC și o susține ca o lucrare originală.

Primul produs software de transport comercial, bazat pe baze de date cu MVCC, a fost VAX Rdb / ELN , lansat în 1984 și creat la Digital Equipment Corporation de Jim Starkey . Starkey a continuat să creeze a doua bază de date MVCC cu succes comercial - InterBase .

Vezi si

Referințe

Lecturi suplimentare

  • Gerhard Weikum, Gottfried Vossen, Sisteme informaționale tranzacționale: teorie, algoritmi și practica controlului și recuperării concurenței , Morgan Kaufmann, 2002, ISBN  1-55860-508-8