To -fase låsing - Two-phase locking

Denne artikkelen handler om samtidighetskontroll . For forpliktelse av konsensus innen en distribuert transaksjon, se To-fase forpliktelsesprotokoll .

I databaser og transaksjonsbehandling , to-faselåsing ( 2PL ) er en samtidighetskontrollmetode som garanterer serialiserbarhet . Det er også navnet på resultatet av denne database transaksjonsplanene (historier). Protokollen bruker låser , brukt av en transaksjon på data, som kan blokkere (tolket som signaler for å stoppe) andre transaksjoner fra å få tilgang til de samme dataene i løpet av transaksjonens levetid.

Ved 2PL -protokollen brukes låser og fjernes i to faser:

  1. Utvidende fase: låser erverves og ingen låser frigjøres.
  2. Krympefase: låser frigjøres og ingen låser erverves.

To typer låser brukes av grunnprotokollen: Delte og eksklusive låser. Avgrensninger av grunnprotokollen kan bruke flere låsetyper. Ved å bruke låser som blokkerer prosesser, kan 2PL være utsatt for låsninger som skyldes gjensidig blokkering av to eller flere transaksjoner.

Datatilgangslåser

En lås er et systemobjekt assosiert med en delt ressurs, for eksempel et dataelement av en elementær type, en rad i en database eller en side med minne. I en database kan det hende at en lås på et databaseobjekt (en datatilgangslås) må anskaffes av en transaksjon før du får tilgang til objektet. Korrekt bruk av låser forhindrer uønskede, feilaktige eller inkonsekvente operasjoner på delte ressurser fra andre samtidige transaksjoner. Når et databaseobjekt med en eksisterende lås ervervet av en transaksjon må nås av en annen transaksjon, kontrolleres den eksisterende låsen for objektet og typen av den tiltenkte tilgangen av systemet. Hvis den eksisterende låsetypen ikke tillater denne spesifikke forsøkte samtidige tilgangstypen, blir transaksjonen som prøver å få tilgang blokkert (i henhold til en forhåndsdefinert avtale/ordning). I praksis blokkerer en lås på et objekt ikke direkte en transaksjons operasjon på objektet, men blokkerer den transaksjonen fra å anskaffe en annen lås på det samme objektet, som måtte holdes/eies av transaksjonen før denne operasjonen utføres. Med en låsemekanisme styres den nødvendige operasjonsblokkeringen av et skikkelig låseblokkeringsskjema, som indikerer hvilken låstype som blokkerer hvilken låsetype.

To hovedtyper låser brukes:

  • Skrivelås ( eksklusiv lås ) er knyttet til et databaseobjekt ved en transaksjon (Terminologi: "transaksjonen låser objektet," eller "anskaffer lås for det") før du skriver (setter inn/modifiserer/sletter) dette objektet.
  • Leselås ( delt lås ) er knyttet til et databaseobjekt ved en transaksjon før du leser (henter tilstanden til) dette objektet.

De vanlige interaksjonene mellom disse låsetypene er definert ved å blokkere atferd som følger:

  • En eksisterende skrivelås på et databaseobjekt blokkerer en tiltenkt skrive på det samme objektet (allerede forespurt/utstedt) av en annen transaksjon ved å blokkere en respektive skrivelås fra å bli anskaffet av den andre transaksjonen. Den andre skrivelåsen vil bli anskaffet og den forespurte skrivingen av objektet vil finne sted (materialisere) etter at den eksisterende skrivelåsen er frigitt.
  • En skrivelås blokkerer en tilsiktet (allerede forespurt/utstedt) lesning av en annen transaksjon ved å blokkere den respektive leselåsen .
  • En leselås blokkerer en tiltenkt skriving av en annen transaksjon ved å blokkere den respektive skrivelåsen .
  • En leselås blokkerer ikke en tilsiktet lesning av en annen transaksjon. Den respektive leselåsen for den tiltenkte lesingen blir anskaffet (delt med den forrige lesningen) umiddelbart etter at den tiltenkte lesningen er bedt om, og deretter finner den tiltenkte lesingen seg ut.

Det finnes flere varianter og forbedringer av disse store låsetypene, med respektive variasjoner av blokkeringsatferd. Hvis en første lås blokkerer en annen lås, kalles de to låsene inkompatible ; ellers er låsene kompatible . Ofte presenteres låsetyper som blokkerer interaksjoner i teknisk litteratur ved hjelp av en Lock -kompatibilitetstabell . Følgende er et eksempel på de vanlige, store låsetypene:

Lås kompatibilitetstabell
Låsetype leselås skrive-lås
leselås ✔ X
skrive-lås X X
✔ indikerer kompatibilitet
X indikerer inkompatibilitet, dvs. et tilfelle når en lås av den første typen (i venstre kolonne) på et objekt blokkerer en lås av den andre typen (i øverste rad) fra å bli anskaffet på det samme objektet (ved en annen transaksjon). Et objekt har vanligvis en kø med ventende forespørsel (ved transaksjoner) operasjoner med respektive låser. Den første blokkerte låsen for drift i køen erverves så snart den eksisterende blokkeringslåsen fjernes fra objektet, og deretter utføres den respektive operasjonen. Hvis en lås for operasjon i køen ikke er blokkert av noen eksisterende lås (eksistensen av flere kompatible låser på samme objekt er mulig samtidig), anskaffes den umiddelbart.
Kommentar: I noen publikasjoner er tabelloppføringene ganske enkelt merket "kompatible" eller "inkompatible", eller henholdsvis "ja" eller "nei".

To-faset låsing og spesialtilfeller

To-fase låsing

I henhold til to-faselåsing protokollen, håndterer en transaksjon sine sluser i to forskjellige, på hverandre følgende faser under transaksjonens gjennomføring:

  1. Utvidende fase (også kjent som voksende fase): låser erverves og ingen låser frigjøres (antallet låser kan bare øke).
  2. Krympefase (aka Kontraherende fase): låser frigjøres og ingen låser erverves.

De to faselåsingsreglene kan oppsummeres som: skaff deg aldri en lås etter at en lås er sluppet. Den serialiserbarhet Eiendommen er garantert for en tidsplan med transaksjoner som adlyder denne regelen.

Vanligvis, uten eksplisitt kunnskap om en transaksjon på slutten av fase 1, bestemmes det trygt bare når en transaksjon har fullført behandlingen og bedt om forpliktelse. I dette tilfellet kan alle låsene slippes samtidig (fase 2).

Konservativ tofaset låsing

Forskjellen mellom 2PL og C2PL er at C2PLs transaksjoner får alle låsene de trenger før transaksjonene begynner. Dette er for å sikre at en transaksjon som allerede inneholder noen låser ikke vil blokkere ventetiden på andre låser. Konservativ 2PL forhindrer fastlåsing .

Streng tofaset låsing

For å overholde S2PL -protokollen, må en transaksjon overholde 2PL, og slippe sine skrive (eksklusive) låser først etter at den er avsluttet, det vil si enten bli begått eller avbrutt . På den annen side frigjøres (delte) låser regelmessig under fase 2. Denne protokollen er ikke passende i B-trær fordi den forårsaker flaskehals (mens B-trær alltid begynner å søke fra den overordnede roten).

Sterk streng tofaset låsing

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

For å overholde sterk streng tofaset låsing (SS2PL) frigjør låseprotokollen både skrive (eksklusive) og lese (delte) låser som brukes av en transaksjon først etter at transaksjonen er avsluttet, det vil si bare etter at begge er ferdig med å utføre (være klar ) og blir enten engasjert eller avbrutt . Denne protokollen er også i samsvar med S2PL -reglene. En transaksjon som adlyder SS2PL kan ses som å ha fase 1 som varer hele transaksjonens varighet, og ingen fase 2 (eller en degenerert fase 2). Dermed er det bare en fase igjen, og "tofase" i navnet ser ut til å fortsatt bli brukt på grunn av den historiske utviklingen av konseptet fra 2PL, og 2PL er en superklasse. SS2PL -egenskapen til en tidsplan kalles også Rigorousness . Det er også navnet på klassen av tidsplaner som har denne egenskapen, og en SS2PL -plan kalles også en "streng tidsplan". Begrepet "Rigorousness" er fri for den unødvendige arven fra "to-fase", i tillegg til at den er uavhengig av hvilken som helst (låsemekanisme) (i prinsippet kan andre blokkeringsmekanismer brukes). Eiendommens respektive låsemekanisme kalles noen ganger Rigorous 2PL .

SS2PL er et spesielt tilfelle av S2PL, dvs. SS2PL -klassen av tidsplaner er en riktig underklasse av S2PL (hver SS2PL -plan er også en S2PL -plan, men det finnes S2PL -planer som ikke er SS2PL).

SS2PL har vært valgfri samtidighetskontrollprotokoll for de fleste databasesystemer og blitt brukt siden de var tidlige på 1970 -tallet . Det har vist seg å være en effektiv mekanisme i mange situasjoner, og gir dessuten serialiserbarhet også Strenghet (et spesielt tilfelle av cascadeless Gjenoppretting), som er medvirkende til effektiv database utvinning , og også engasjement bestilling (CO) for å delta i distribuerte miljøer hvor en CO baserte distribuerte serialiserbarhetsløsninger og globale serialiseringsløsninger brukes. Være en undergruppe av CO, en effektiv implementering av distribuert SS2PL eksisterer uten et distribuert lås leder (DLM), mens fordelt vranglåser (se nedenfor) blir løst automatisk. Det faktum at SS2PL ansatt i multidatabasesystemer sikrer global serialisering har vært kjent i mange år før oppdagelsen av CO, men først med CO kom forståelsen av rollen til en atomisk forpliktelsesprotokoll for å opprettholde global serialisering, samt observasjon av automatisk distribuert dødlåsoppløsning (se et detaljert eksempel på Distribuert SS2PL ). Faktisk er SS2PL -arvende egenskaper for gjenvinnbarhet og CO mer signifikant enn å være en undersett av 2PL, som i seg selv i sin generelle form, i tillegg til å omfatte en enkel serialiserbarhetsmekanisme (men serialiserbarhet er også underforstått av CO), ikke kjent å gi SS2PL andre viktige kvaliteter. 2PL i sin generelle form, så vel som når det kombineres med Strictness, dvs. Strict 2PL (S2PL), er ikke kjent for å bli brukt i praksis. Den populære SS2PL krever ikke merking av "slutten av fase 1" slik 2PL og S2PL gjør, og er dermed enklere å implementere. I motsetning til den generelle 2PL, gir SS2PL, som nevnt ovenfor, de nyttige bestillingsegenskapene for strenghet og forpliktelse .

Det finnes mange varianter av SS2PL som bruker forskjellige låsetyper med forskjellige semantikk i forskjellige situasjoner, inkludert tilfeller av endring av låsetype under en transaksjon. Bemerkelsesverdig er varianter som bruker Multiple granularity locking .

Kommentarer:

  1. SS2PL vs S2PL: Begge gir serialisering og strenghet. Siden S2PL er en superklasse av SS2PL, kan det i prinsippet gi mer samtidighet. Imidlertid oppdages vanligvis ingen samtidighetsfordel praktisk talt (nøyaktig samme låsing eksisterer for begge, med praktisk talt ikke mye tidligere låsemodus for S2PL), og overhead for å håndtere en slutt-på-fase-1-mekanisme i S2PL, atskilt fra transaksjonsenden , er ikke berettiget. Selv om SS2PL leverer forpliktelsesbestilling , gjør ikke S2PL det. Dette forklarer preferansen til SS2PL fremfor S2PL.
  2. Spesielt før 1990, men også etter, i mange artikler og bøker, f.eks. (Bernstein et al. 1987, s. 59), har begrepet "Strict 2PL" (S2PL) ofte blitt definert av låseprotokollen "Bare frigjør alle låser etter transaksjonens slutt, "som er protokollen til SS2PL. Dermed kan "Strict 2PL" ikke være navnet på krysset mellom Strictness og 2PL, som er større enn klassen generert av SS2PL -protokollen. Dette har skapt forvirring. Med en eksplisitt definisjon av S2PL som skjæringspunktet mellom Strictness og 2PL, et nytt navn for SS2PL og et eksplisitt skille mellom klassene S2PL og SS2PL, har artiklene (Breitbart et al. 1991) og (Raz 1992) hatt til hensikt å fjerne forvirring: den første som bruker navnet "strenghet" og den andre "SS2PL."
  3. Det finnes en mer generell egenskap enn SS2PL (en tidsplan superklasse), Strikt forpliktelsesbestilling (Strikt CO eller SCO), som i tillegg gir både serialisering, strenghet og CO, og har lignende låsingskostnader. I motsetning til SS2PL, blokkerer ikke SCO en lese-skrive-konflikt (en leselås blokkerer ikke anskaffelse av en skrivelås; både SCO og SS2PL har samme oppførsel for skrive-lese og skrive-skrive-konflikter) på bekostning av en mulig forsinkelse forplikte seg, og ved slik konflikttype har SCO kortere gjennomsnittlig transaksjonstid og bedre ytelse enn SS2PL. Mens SS2PL adlyder tabellen over kompatibilitet med lås ovenfor, har SCO følgende tabell:
Låsekompatibilitet for SCO
Låsetype leselås skrive-lås
leselås X
skrive-lås X X
Vær oppmerksom på at selv om SCO frigjør alle låser ved transaksjonens slutt og overholder 2PL -låsereglene, er SCO ikke et delsett av 2PL på grunn av den forskjellige låsekompatibilitetstabellen. SCO tillater materialiserte lese-skrive-konflikter mellom to transaksjoner i fasene 1, noe 2PL ikke tillater i fase 1 (se om materialiserte konflikter i serialiserbarhet ). På den annen side tillater 2PL andre materialiserte konflikttyper i fase 2 som SCO ikke tillater i det hele tatt. Til sammen innebærer dette at tidsplanklassene 2PL og SCO er uforlignelige (dvs. ingen klasse inneholder den andre klassen).

Oppsummering - Forhold mellom klasser

Image
Planlegg innhold av klasser: En pil fra klasse A til klasse B indikerer at klasse A strengt inneholder B; mangel på en rettet vei mellom klassene betyr at klassene er makeløse. En eiendom blokkerer iboende , hvis den bare kan håndheves ved å blokkere transaksjonens datatilgangsoperasjoner til visse hendelser oppstår i andre transaksjoner. ( Raz 1992 )

Mellom to planklasser (definert av sine tidsplaners respektive egenskaper) som har felles tidsplaner, inneholder enten den ene den andre ( inneholder strengt hvis de ikke er like), eller de er uforlignelige . Inneslutningsforholdet mellom 2PL -klassene og andre større timeplanklasser er oppsummert i diagrammet nedenfor. 2PL og dens underklasser blokkerer iboende , noe som betyr at det ikke finnes noen optimistiske implementeringer for dem (og når "Optimistisk 2PL" blir nevnt, refererer det til en annen mekanisme med en klasse som også inkluderer tidsplaner som ikke er i 2PL -klassen).

Dødlås i 2PL

Låser blokkerer tilgang til data. Gjensidig blokkering mellom transaksjoner resulterer i et dødfengsel , hvor utførelsen av disse transaksjonene stopper, og det ikke er mulig å fullføre. Dermed må dødelåser løses for å fullføre disse transaksjonenes henrettelser og frigjøre relaterte databehandlingsressurser. En fastlåsning er en refleksjon av en potensiell syklus i forranggrafen , som ville oppstå uten blokkering. Et dødvann løses ved å avbryte en transaksjon som er involvert i en slik potensiell syklus, og bryte syklusen. Det blir ofte oppdaget ved hjelp av en vent-på-graf (en graf over konflikter som er blokkert av låser fra å bli materialisert; konflikter som ikke materialiseres i databasen på grunn av blokkerte operasjoner gjenspeiles ikke i prioritetsgrafen og påvirker ikke serialiserbarheten ), som indikerer hvilken transaksjon "venter på" låsefrigjøring, ved hvilken transaksjon, og en syklus betyr en fastlåst posisjon. Å avbryte en transaksjon per syklus er tilstrekkelig for å bryte syklusen. Hvis en transaksjon har blitt avbrutt på grunn av en fastlåst løsning, er det opp til søknaden å bestemme hva de skal gjøre videre. Vanligvis vil en applikasjon starte transaksjonen på nytt fra begynnelsen, men kan forsinke denne handlingen til å gi andre transaksjoner tilstrekkelig tid til å fullføre for å unngå å forårsake et nytt dødfeng.

I et distribuert miljø en atom engasjement protokoll, typisk Tofaseiverksetting (2PC) protokoll, blir brukt for atomicity . Når gjenvinnbare data (data under transaksjonskontroll) som er delt mellom 2PC -deltakere (dvs. at hvert dataobjekt kontrolleres av en enkelt 2PC -deltaker), blir distribuerte (globale) dødelåser, dødelåser som involverer to eller flere deltakere i 2PC, løst automatisk som følger:

Når SS2PL effektivt brukes i et distribuert miljø, genererer globale dødelåser på grunn av låsing stemmelokeringer i 2PC, og løses automatisk av 2PC (se Engasjementsbestilling (CO), i Nøyaktig karakterisering av stemmesperre etter globale sykluser ; Ingen referanse bortsett fra at CO -artiklene er kjent for å legge merke til dette). I det generelle tilfellet med 2PL løses globale dødelåser på samme måte automatisk av synkroniseringspunktprotokollen for fase 1-enden i en distribuert transaksjon (synkroniseringspunkt oppnås ved å "stemme" (varsle lokal fase-1-ende) og videreformidles til deltakere i en distribuert transaksjon på samme måte som et beslutningspunkt i atomforpliktelse; analogt med beslutningspunkt i CO, kan en motstridende operasjon i 2PL ikke skje før fase 1-slutt-synkroniseringspunktet, med samme resulterende stemmebelegg i tilfelle av en global datatilgangsblokkering; stemmegivningen (som også er en låsebasert global dødelås) løses automatisk ved at protokollen avbryter en involvert transaksjon, med en manglende stemme, vanligvis ved bruk av en timeout ).

Kommentar :

Når data er partisjonert mellom atom engasjement protokollen (f.eks 2pc) deltakere, automatisk global vranglås har oppløsning vært oversett i databasen forskningslitteraturen, men vranglås i slike systemer har vært et ganske intensivt forskningsområde:
  • For CO og sin spesielle tilfelle SS2PL, automatisk vedtak i atom engasjement protokollen har blitt lagt merke bare i CO artikler. Imidlertid har det blitt lagt merke til i praksis at globale dødelåser i mange tilfeller svært sjelden blir oppdaget av de dedikerte oppløsningsmekanismene, mindre enn man kunne forvente ("Hvorfor ser vi så få globale dødelåser?"). Årsaken er sannsynligvis dødelåsene som automatisk løses og dermed ikke håndteres og telles ut av mekanismene;
  • For 2PL generelt har den automatiske oppløsningen ved (obligatorisk) ende-av-fase-en-synkroniseringspunkt-protokollen (som har samme stemmemekanisme som atomforpliktelsesprotokoll, og samme manglende stemmebehandling ved avstemning, som resulterer i global fastlåsning) ikke blitt nevnt før i dag (2009). Nesten bare spesialtilfellet SS2PL brukes, der det ikke er nødvendig med slutten av fase-en-synkronisering i tillegg til atomic commit-protokollen.
I et distribuert miljø hvor gjenvinnbare data ikke er delt mellom deltakere i protokolldeltakere, eksisterer ingen slik automatisk oppløsning, og distribuerte dødelås må løses med dedikerte teknikker.

Se også

Referanser