Kaksivaiheinen lukitus

Kaksivaiheinen lukitusEdit

Kaksivaiheisen lukitusprotokollan mukaan transaktio käsittelee lukituksiaan kahdessa erillisessä, peräkkäisessä vaiheessa transaktion suorituksen aikana:

1. Laajentumisvaihe (alias kasvuvaihe): lukituksia hankitaan eikä lukituksia vapauteta (lukkojen määrä voi vain kasvaa).
2. Kutistumisvaihe (alias supistumisvaihe): lukot vapautetaan eikä lukituksia hankita.

Kahden vaiheen lukitussäännöt voidaan tiivistää seuraavasti: Älä koskaan hanki lukitusta sen jälkeen, kun lukko on vapautettu. Sarjallistettavuusominaisuus on taattu aikataululle, jonka transaktiot noudattavat tätä sääntöä.

Tyypillisesti ilman eksplisiittistä tietoa transaktiossa vaiheen 1 päättymisestä, se todetaan turvallisesti vasta, kun transaktio on suorittanut käsittelyn loppuun ja pyytänyt sitoutumista. Tällöin kaikki lukot voidaan vapauttaa kerralla (vaihe 2).

Konservatiivinen kaksivaiheinen lukitusEdit

Ero 2PL:n ja C2PL:n välillä on se, että C2PL:n transaktiot saavat kaikki tarvitsemansa lukot ennen transaktioiden aloittamista. Tämän tarkoituksena on varmistaa, että transaktio, jolla on jo joitakin lukituksia, ei esty odottamaan muita lukituksia. Konservatiivinen 2PL estää lukkiutumiset.

Tiukka kaksivaiheinen lukitusEdit

S2PL-protokollan noudattamiseksi transaktion on noudatettava 2PL:ää ja vapautettava kirjoituslukkonsa (yksinoikeuslukot) vasta sen jälkeen, kun se on päättynyt eli joko sitoutunut tai keskeytetty. Toisaalta lukulukot (jaetut) vapautetaan säännöllisesti vaiheen 2 aikana. Tämä protokolla ei sovellu B-puihin, koska se aiheuttaa pullonkaulaa (kun taas B-puut aloittavat haun aina vanhemmasta juuresta).

Strong strict two-phase lockingEdit

or Rigorousness, tai Rigorous scheduling, tai Rigorous two-phase locking

Turvallista tiukkaa kaksivaiheista lukitusta (strong strict two-phase locking, SS2PL) noudattaen lukitusprotokolla vapauttaa transaktion käyttämät kirjoituslukitukset (eksklusiiviset lukituslukitukset (yksinoikeuslukituslukituslukituslukituslukituslukituslukituslukituslukituslukit (lukemislukituslukituslukituslukitus) vasta transaktion loputtua, eli, vasta sen jälkeen, kun molemmat ovat suorittaneet suorituksen loppuun (ovat valmiita) ja joko sitoutuneet tai keskeytyneet. Tämä protokolla on myös S2PL-sääntöjen mukainen. SS2PL-sääntöjä noudattavassa transaktiossa voidaan katsoa olevan vaihe 1, joka kestää koko transaktion suorituksen ajan, ja vaihe 2 puuttuu (tai vaihe 2 on degeneroitunut). Näin ollen jäljelle jää oikeastaan vain yksi vaihe, ja ”kaksivaiheisuus” nimessä näyttää edelleen olevan käytössä, koska käsite on kehittynyt historiallisesti 2PL:stä ja koska 2PL on superluokka. Aikataulun SS2PL-ominaisuutta kutsutaan myös nimellä Rigorousness. Se on myös tämän ominaisuuden omaavien aikataulujen luokan nimi, ja SS2PL-aikataulua kutsutaan myös ”tiukaksi aikatauluksi”. Termi ”Rigorousness” on vapaa tarpeettomasta ”kaksivaiheisuuden” perinnöstä sekä riippumaton mistä tahansa (lukitus)mekanismista (periaatteessa muitakin lukitusmekanismeja voidaan hyödyntää). Ominaisuutta vastaavaan lukitusmekanismiin viitataan joskus nimellä Rigorous 2PL.

SS2PL on S2PL:n erikoistapaus, eli aikataulujen SS2PL-luokka on S2PL:n oikea alaluokka (jokainen SS2PL-aikataulu on myös S2PL-aikataulu, mutta on olemassa S2PL-aikatauluja, jotka eivät ole SS2PL:iä).

SS2PL on ollut useimpien tietokantajärjestelmien rinnakkaisuudenhallintaprotokolla, ja sitä on myös hyödynnetty jo niiden alkuvaiheista lähtien 1970-luvulla. Se on osoittautunut tehokkaaksi mekanismiksi monissa tilanteissa, ja se tarjoaa sarjallistettavuuden lisäksi myös tiukkuuden (kaskadittoman palautettavuuden erikoistapaus), joka on tärkeää tietokannan tehokkaan palautuksen kannalta, ja myös sitoutumisjärjestyksen (Commitment ordering, CO) osallistumista varten hajautetuissa ympäristöissä, joissa käytetään CO-pohjaista hajautettua sarjallistettavuutta ja globaalia sarjallistettavuusratkaisua. Koska se on CO:n osajoukko, hajautetun SS2PL:n tehokas toteutus on mahdollista ilman hajautettua lukitushallintaa (DLM), ja hajautetut lukkiutumiset (ks. jäljempänä) ratkaistaan automaattisesti. Se, että monitietokantajärjestelmissä käytetty SS2PL takaa globaalin sarjallistettavuuden, on ollut tiedossa jo vuosia ennen CO:n keksimistä, mutta vasta CO:n myötä ymmärrettiin atomisen sitoutumisprotokollan rooli globaalin sarjallistettavuuden ylläpitämisessä sekä havaittiin automaattinen hajautettu umpisolmujen ratkaisu (ks. yksityiskohtainen esimerkki hajautetusta SS2PL:stä). Itse asiassa SS2PL:n perimät Recoverability- ja CO-ominaisuudet ovat merkittävämpiä kuin se, että se on osajoukko 2PL:stä, joka itsessään yleisessä muodossaan sisältää yksinkertaisen sarjallistettavuusmekanismin (sarjallistettavuus sisältyy kuitenkin myös CO:hon), mutta jonka ei tiedetä antavan SS2PL:lle muita merkittäviä ominaisuuksia. Käytännössä ei tiedetä käytettävän 2PL:ää sen yleisessä muodossa eikä myöskään yhdistettynä Strictnessiin eli Strict 2PL:ään (S2PL). Suosittu SS2PL ei edellytä ”vaiheen 1 lopun” merkitsemistä, kuten 2PL ja S2PL, ja on siten yksinkertaisempi toteuttaa. Lisäksi, toisin kuin yleinen 2PL, SS2PL tarjoaa, kuten edellä mainittiin, hyödylliset Strictness- ja Commitment ordering -ominaisuudet.

S SS2PL:stä on olemassa monia muunnelmia, jotka käyttävät erilaisia lukitustyyppejä erilaisilla semantiikoilla eri tilanteissa, mukaan lukien tapaukset, joissa lukitustyyppi vaihtuu transaktion aikana. Huomionarvoisia ovat variantit, jotka käyttävät Multiple granularity locking.

1. SS2PL vs. S2PL: Molemmat tarjoavat Serializability ja Strictness. Koska S2PL on SS2PL:n yläluokka, se voi periaatteessa tarjota enemmän samanaikaisuutta. Mitään samanaikaisuusetua ei kuitenkaan tyypillisesti käytännössä havaita (molemmissa on täsmälleen sama lukitus, eikä S2PL:ssä lukituksen vapautuminen käytännössä tapahdu paljon aikaisemmin), eikä S2PL:ssä tapahtuman päättymisestä erillään olevan vaiheen 1 lopetusmekanismin käsittelystä aiheutuva yleiskustannus ole perusteltu. Lisäksi SS2PL tarjoaa Commitment ordering -toiminnon, mutta S2PL ei. Tämä selittää SS2PL:n suosimisen S2PL:n kustannuksella.
2. Etenkin ennen vuotta 1990, mutta myös sen jälkeen, monissa artikkeleissa ja kirjoissa, esimerkiksi (Bernstein et al. 1987, s. 59), termi ”Strict 2PL” (S2PL) on usein määritelty lukitusprotokollan ”Release all locks only after transaction end” (Vapauta kaikki lukot vasta transaktion päättymisen jälkeen) kautta, joka on SS2PL:n protokolla. Näin ollen ”Strict 2PL” ei voisi olla siellä Strictnessin ja 2PL:n leikkauspisteen nimi, joka on suurempi kuin SS2PL-protokollan tuottama luokka. Tämä on aiheuttanut sekaannusta. Kun S2PL on nimenomaisesti määritelty Strictnessin ja 2PL:n leikkauspisteeksi, SS2PL:lle on annettu uusi nimi ja S2PL- ja SS2PL-luokat on selvästi erotettu toisistaan, artikkeleissa (Breitbart et al. 1991) ja (Raz 1992) on pyritty poistamaan sekaannus: ensimmäisessä on käytetty nimeä ”rigorousness” ja toisessa ”SS2PL”.”
3. S SS2PL:ää yleisempi ominaisuus on olemassa (aikataulun yläluokka), Strict commitment ordering (Strict CO, tai SCO), joka niin ikään tarjoaa sekä sarjallistettavuuden, tiukkuuden että CO:n, ja jolla on samanlainen lukituksen yleiskustannus. Toisin kuin SS2PL, SCO ei luku- ja kirjoitusristiriidassa (lukulukko ei estä kirjoituslukon hankkimista; sekä SCO:lla että SS2PL:llä on sama käyttäytyminen kirjoitus-luku- ja kirjoitus-kirjoitusristiriitojen osalta), mutta se aiheuttaa mahdollisen viivästyneen sitoutumisen, ja tällaisessa konfliktityypissä SCO:lla on lyhyempi keskimääräinen transaktion loppuunsaattamiseen kuluva aika ja parempi suorituskyky kuin SS2PL:llä. SS2PL noudattaa edellä esitettyä lukitusten yhteensopivuustaulukkoa, kun taas SCO noudattaa seuraavaa taulukkoa:

Huomaa, että vaikkakin SCO vapauttaa kaikki lukot transaktion päättyessä ja noudattaa 2PL-lukituksen sääntöjä, SCO ei ole 2PL:n osajoukko, koska sen lukitusten yhteensopivuustaulukko on erilainen. SCO sallii kahden transaktion väliset materialisoidut luku- ja kirjoitusristiriidat niiden vaiheessa 1, mitä 2PL ei salli vaiheessa 1 (ks. materialisoiduista ristiriidoista kohdasta Serializability). Toisaalta 2PL sallii muita materialisoituja konfliktityyppejä vaiheessa 2, joita SCO ei salli lainkaan. Yhdessä tämä tarkoittaa, että aikataululuokat 2PL ja SCO ovat vertailukelvottomia (eli mikään luokka ei sisällä toista luokkaa).

Yhteenveto – Luokkien väliset suhteetEdit

Aikataululuokkien sisältyminen: Nuoli luokasta A luokkaan B osoittaa, että luokka A sisältää tiukasti B:n; suunnatun polun puuttuminen luokkien väliltä tarkoittaa, että luokat ovat vertailukelvottomia. Ominaisuus on luonnostaan estävä, jos se voidaan panna täytäntöön vain estämällä transaktion tiedonkäyttöoperaatiot, kunnes tietyt tapahtumat tapahtuvat muissa transaktioissa. (Raz 1992)

Kahdessa aikataululuokassa (jotka määritellään niiden aikataulujen ominaisuuksien perusteella), joilla on yhteiset aikataulut, joko toinen sisältää toisen (sisältää tiukasti, jos ne eivät ole yhtäläisiä) tai ne ovat vertailukelvottomia. 2PL-luokkien ja muiden tärkeimpien aikataululuokkien väliset sisältösuhteet on esitetty seuraavassa kaaviossa. 2PL ja sen alaluokat ovat luonnostaan estäviä, mikä tarkoittaa, että niille ei ole olemassa optimistisia toteutuksia (ja aina kun ”Optimistinen 2PL” mainitaan, sillä viitataan eri mekanismiin, jonka luokka sisältää myös aikatauluja, jotka eivät kuulu 2PL-luokkaan).