Twee-fasen-locking

Twee-fasen-lockingEdit

Volgens het twee-fasen-lockingprotocol behandelt een transactie zijn locks in twee afzonderlijke, opeenvolgende fasen tijdens de uitvoering van de transactie:

1. Uitbreidingsfase (ook wel Groeifase genoemd): locks worden verworven en geen locks worden vrijgegeven (het aantal locks kan alleen maar toenemen).
2. Krimpende fase (ook wel Contracterende fase genoemd): sloten worden vrijgegeven en er worden geen sloten verworven.

De twee fase locking regels kunnen worden samengevat als: verkrijg nooit een slot nadat een slot is vrijgegeven. De serializability eigenschap is gegarandeerd voor een schema met transacties die zich aan deze regel houden.

Typisch is dat zonder expliciete kennis in een transactie over het einde van fase 1, dit pas veilig wordt vastgesteld als een transactie de verwerking heeft voltooid en commit heeft aangevraagd. In dat geval kunnen alle locks in één keer worden vrijgegeven (fase 2).

Conservative two-phase lockingEdit

Het verschil tussen 2PL en C2PL is dat C2PL’s transacties alle locks verkrijgen die ze nodig hebben voordat de transacties beginnen. Dit is om ervoor te zorgen dat een transactie die al een aantal “locks” heeft, niet blokkeert door op andere “locks” te wachten. Conservatieve 2PL voorkomt deadlocks.

Strict two-phase lockingEdit

Om aan het S2PL-protocol te voldoen, moet een transactie voldoen aan 2PL, en zijn schrijf (exclusieve) locks pas vrijgeven nadat hij is geëindigd, d.w.z. dat hij ofwel gecommit ofwel afgebroken is. Daarentegen worden lees- (gedeelde) “locks” tijdens fase 2 regelmatig vrijgegeven. Dit protocol is niet geschikt voor B-trees, omdat het een flessenhals veroorzaakt (terwijl B-trees altijd vanaf de parent root beginnen te zoeken).

Strong strict two-phase lockingEdit

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

Om te voldoen aan strong strict two-phase locking (SS2PL) geeft het locking protocol zowel de schrijf- (exclusieve) als de lees- (gedeelde) locks die door een transactie zijn toegepast pas vrij nadat de transactie is geëindigd, d.w.z, pas nadat zowel de uitvoering is voltooid (gereed is) als vastgelegd of afgebroken. Dit protocol voldoet ook aan de S2PL-regels. Een transactie die aan SS2PL voldoet, kan worden gezien als een transactie met fase 1, die de gehele uitvoeringsduur van de transactie duurt, en geen fase 2 (of een ontaarde fase 2). Er blijft dus eigenlijk maar één fase over, en “two-phase” in de naam lijkt nog steeds gebruikt te worden vanwege de historische ontwikkeling van het concept vanuit 2PL, en omdat 2PL een superklasse is. De SS2PL eigenschap van een schema wordt ook Rigoureusheid genoemd. Het is ook de naam van de klasse van schema’s die deze eigenschap hebben, en een SS2PL schema wordt ook wel een “rigoureus schema” genoemd. De term “rigoreusheid” is vrij van de onnodige erfenis van “tweefasigheid”, en is ook onafhankelijk van enig (blokkerings)mechanisme (in principe kunnen andere blokkeringsmechanismen worden gebruikt). Het respectieve vergrendelingsmechanisme van de eigenschap wordt soms aangeduid als Rigorous 2PL.

SS2PL is een speciaal geval van S2PL, d.w.z., de SS2PL klasse van schema’s is een eigen subklasse van S2PL (elk SS2PL schema is ook een S2PL schema, maar er bestaan S2PL schema’s die geen SS2PL zijn).

SS2PL is het concurrency control protocol bij uitstek voor de meeste databasesystemen en wordt al gebruikt sinds hun begindagen in de jaren zeventig. Het is in vele situaties een doeltreffend mechanisme gebleken, en biedt naast serializability ook Strictness (een speciaal geval van cascadeless Recoverability), dat van nut is voor efficiënt databaseherstel, en ook Commitment ordering (CO) voor deelname in gedistribueerde omgevingen waar een op CO gebaseerde gedistribueerde serializability en globale serializability-oplossingen worden toegepast. Omdat het een subset van CO is, bestaat een efficiënte implementatie van gedistribueerde SS2PL zonder een gedistribueerde lock manager (DLM), terwijl gedistribueerde deadlocks (zie hieronder) automatisch worden opgelost. Het feit dat SS2PL in multidatabasesystemen de globale serializeerbaarheid garandeert, was al jaren bekend vóór de ontdekking van CO, maar pas met CO kwam het inzicht in de rol van een atomair commitment protocol bij het handhaven van de globale serializeerbaarheid, alsmede de observatie van automatische gedistribueerde deadlock resolution (zie een gedetailleerd voorbeeld van gedistribueerde SS2PL). In feite is het feit dat SS2PL de eigenschappen van Herstelbaarheid en CO erft belangrijker dan het feit dat het een subset is van 2PL, dat op zichzelf in zijn algemene vorm, naast een eenvoudig serializatiemechanisme (serializatie wordt echter ook geïmpliceerd door CO), geen andere belangrijke kwaliteiten aan SS2PL kan geven. Van 2PL in zijn algemene vorm, alsook in combinatie met Strictness, d.w.z. Strict 2PL (S2PL), is niet bekend dat het in de praktijk wordt gebruikt. De populaire SS2PL vereist geen markering “einde van fase 1” zoals 2PL en S2PL dat doen, en is dus eenvoudiger te implementeren. Ook biedt SS2PL, in tegenstelling tot de algemene 2PL, zoals hierboven vermeld, de nuttige eigenschappen Strictness en Commitment ordering.

Er bestaan vele varianten van SS2PL die gebruik maken van verschillende locktypen met verschillende semantiek in verschillende situaties, waaronder gevallen van locktypeverandering tijdens een transactie. Opmerkelijk zijn varianten die gebruik maken van vergrendeling met meervoudige granulariteit.

1. SS2PL vs. S2PL: Beide bieden Serializability en Strictness. Aangezien S2PL een superklasse van SS2PL is, kan deze in principe meer “concurrency” bieden. In de praktijk wordt echter geen concurrency voordeel waargenomen (exact dezelfde locking bestaat voor beide, met praktisch niet veel eerdere lock-release voor S2PL), en de overhead van het omgaan met een einde-fase-1 mechanisme in S2PL, los van transactie-einde, is niet gerechtvaardigd. Ook biedt SS2PL Commitment ordering, terwijl S2PL dat niet doet. Dit verklaart de voorkeur van SS2PL boven S2PL.
2. Vóór 1990, maar ook daarna, is in veel artikelen en boeken, bijvoorbeeld (Bernstein et al. 1987, p. 59), de term “Strict 2PL” (S2PL) vaak gedefinieerd aan de hand van het sluitprotocol “Release all locks only after transaction end,” wat het protocol van SS2PL is. Strict 2PL” zou dus niet de naam kunnen zijn van de intersectie van Strictness en 2PL, die groter is dan de klasse die door het SS2PL protocol wordt gegenereerd. Dit heeft tot verwarring geleid. Met een expliciete definitie van S2PL als de doorsnijding van Strengheid en 2PL, een nieuwe naam voor SS2PL, en een expliciet onderscheid tussen de klassen S2PL en SS2PL, hebben de artikelen (Breitbart et al. 1991) en (Raz 1992) de verwarring willen opheffen: het eerste met de naam “strengheid,” en het tweede “SS2PL.”
3. Er bestaat een algemenere eigenschap dan SS2PL (een schema-superklasse), Strict commitment ordering (Strict CO, of SCO), die eveneens zowel serializability, strictness, als CO biedt, en een vergelijkbare locking-overhead heeft. In tegenstelling tot SS2PL blokkeert SCO niet bij een lees-schrijf conflict (een lees-lock blokkeert niet het verkrijgen van een schrijf-lock; zowel SCO als SS2PL hebben hetzelfde gedrag voor schrijf-lees en schrijf-schrijf conflicten) ten koste van een mogelijk vertraagde commit, en bij zo’n conflict type heeft SCO een kortere gemiddelde transactie voltooiingstijd en betere prestaties dan SS2PL. Terwijl SS2PL zich aan de bovenstaande slotcompatibiliteitstabel houdt, heeft SCO de volgende tabel:

Merk op dat hoewel SCO alle locks vrijgeeft aan het einde van de transactie en voldoet aan de 2PL-lockingregels, SCO is geen subset van 2PL vanwege de afwijkende lockcompatibiliteitstabel. SCO staat gematerialiseerde lees-schrijf conflicten toe tussen twee transacties in hun fase 1, wat 2PL niet toestaat in fase 1 (zie over gematerialiseerde conflicten in Serializability). Aan de andere kant staat 2PL andere gematerialiseerde conflicttypes toe in fase 2 die SCO helemaal niet toestaat. Samen impliceert dit dat de schema klassen 2PL en SCO onvergelijkbaar zijn (d.w.z. dat geen enkele klasse de andere klasse bevat).

Samenvatting – Relaties tussen klassenEdit

Schema klassen containment: Een pijl van klasse A naar klasse B geeft aan dat klasse A strikt B bevat; het ontbreken van een gericht pad tussen klassen betekent dat de klassen onvergelijkbaar zijn. Een eigenschap is inherent blokkerend, als zij alleen kan worden afgedwongen door de datatoegangsoperaties van transacties te blokkeren totdat zich bepaalde gebeurtenissen in andere transacties voordoen. (Raz 1992)

Tussen twee schema-klassen (gedefinieerd door de respectieve eigenschappen van hun schema’s) die gemeenschappelijke schema’s hebben, bevat ofwel de ene de andere (bevat strikt als ze niet gelijk zijn), of ze zijn onvergelijkbaar. De insluitingsrelaties tussen de 2PL klassen en andere grote schema klassen zijn samengevat in het volgende diagram. 2PL en zijn subklassen zijn inherent blokkerend, hetgeen betekent dat er geen optimistische implementaties voor bestaan (en wanneer “Optimistic 2PL” wordt genoemd refereert dat aan een ander mechanisme met een klasse die ook schema’s bevat die niet in de 2PL klasse zitten).