Tidsstämpelbaserad samtidighetskontroll

Inom datavetenskap är en tidsstämpelbaserad algoritm för samtidighetskontroll en icke-låst metod för samtidighetskontroll . Det används i vissa databaser för att säkert hantera transaktioner, med hjälp av tidsstämplar .

Drift

Antaganden

Varje tidsstämpelvärde är unikt och representerar exakt ett ögonblick i tiden.
En tidsstämpel med högre värde inträffar senare i tiden än en tidsstämpel med lägre värde.

Genererar en tidsstämpel

Ett antal olika sätt har använts för att skapa tidsstämpel

Använd värdet på systemets klocka i början av en transaktion som tidsstämpel.
Använd en trådsäker delad räknare som inkrementeras i början av en transaktion som tidsstämpel.
En kombination av ovanstående två metoder.

Formell

Varje transaktion ( $T_{i}$ ) är en ordnad lista över åtgärder ( ${\displaystyle A_{ix}})$ . Innan transaktionen utför sin första åtgärd ( $A_{i1}$ ), markeras den med den aktuella tidsstämpeln , eller någon annan strikt helt ordnad sekvens: $TS(T_{i})=NU()$ . Varje transaktion ges också en initialt tom uppsättning transaktioner som den beror på, $DEP(T_{i})=[]$ , och en initialt tom uppsättning gamla objekt som den uppdaterades, $OLD(T_{i})=[]$ .

Varje objekt $(O_{j})$ i databasen ges två tidsstämpelfält som inte används annat än för samtidighetskontroll: $RTS(O_{j} )$ är den tidpunkt då objektets värde senast användes av en transaktion, $WTS(O_{j})$ är den tidpunkt då objektets värde senast uppdaterades av en transaktion.

För alla $T_{i}$ :

För varje åtgärd

A_{ix}

:

Om

A_{ix}

vill använda värdet för

O_{j}

:

Om

WTS(O_{j})>TS(T_{i})

avbryt sedan (en nyare tråd har skrivit över värdet),

Uppdatera annars uppsättningen av beroenden

DEP(T_{i}).\mathrm {add} (WTS(O_{j}))

och ställ in

{\displaystyle RTS(O_{j})=\max(RTS(O_{j}),TS(T_{i})

;

Om

A_{ix}

vill uppdatera värdet för

O_{j}

:

Om

RTS(O_ {j})>TS(T_{i})

avbryt sedan (en nyare tråd förlitar sig redan på det gamla värdet),

Om

{\displaystyle WTS(O_ {j})>TS(T_{i})} hoppa

sedan över ( Thomas Write Rule ),

annars lagra de tidigare värdena,

{\displaystyle OLD(T_{i}).\mathrm {add} (O_{j},WTS(O_{j}))} ,

set

WTS(O_{j})=TS(T_{i})

uppdatera värdet på

O_{j}

.

Medan det finns en transaktion i

DEP(T_{i})

som inte har avslutats: vänta

Om det finns en transaktion i

DEP(T_{ i})

som avbröt och avbryt.

Annars: begå .

För att avbryta :

För varje

(\mathrm {old} O_{j},\mathrm {old} WTS(O_{j}))

i

OLD(T_{i})

Om

WTS(O_{j})

är lika med

TS(T_{ i})

återställ sedan

O_{j}=\mathrm {old} O_{j}

och

WTS(O_{j})=\mathrm {gammal} WTS(O_{j})

Informell

Närhelst en transaktion påbörjas får den en tidsstämpel. Denna tidsstämpel anger i vilken ordning transaktionen måste ske, i förhållande till de andra transaktionerna. Så, givet två transaktioner som påverkar samma objekt, måste operationen av transaktionen med den tidigare tidsstämpeln utföras före operationen av transaktionen med den senare tidsstämpeln. Men om operationen av fel transaktion faktiskt presenteras först, avbryts den och transaktionen måste startas om.

Varje objekt i databasen har en lästidsstämpel , som uppdateras när objektets data läses, och en skrivtidsstämpel , som uppdateras när objektets data ändras.

Om en transaktion vill läsa ett objekt,

men transaktionen startade före objektets skrivtidsstämpel betyder det att något ändrade objektets data efter att transaktionen startade. I det här fallet avbryts transaktionen och måste startas om.
och transaktionen startade efter objektets skrivtidsstämpel betyder det att det är säkert att läsa objektet. I det här fallet, om transaktionens tidsstämpel är efter objektets lästidsstämpel , sätts lästidsstämpeln till transaktionens tidsstämpel.

Om en transaktion vill skriva till ett objekt,

men transaktionen startade innan objektets lästidsstämpel betyder att något har tittat på objektet, och vi antar att det tog en kopia av objektets data. Så vi kan inte skriva till objektet eftersom det skulle göra all kopierad data ogiltig, så transaktionen avbryts och måste startas om.
och transaktionen startade före objektets skrivtidsstämpel betyder det att något har förändrat objektet sedan vi startade vår transaktion. I det här fallet använder vi Thomas skrivregel och hoppar helt enkelt över vår skrivoperation och fortsätter som vanligt; transaktionen behöver inte avbrytas eller startas om
annars skrivs transaktionen till objektet, och objektets skrivtidsstämpel ställs in på transaktionens tidsstämpel.

Återvinningsbarhet

Observera att tidsstämpelbeställning i dess grundläggande form inte ger återställningsbara historik. Betrakta till exempel följande historik med transaktioner $T_{1}$ och $T_{2}$ :

W_{1}(x)\;R_{2}(x)\;W_{2}( y)\;C_{2}\;R_{1}(z)\;C_{1}

Detta skulle kunna produceras av en TO-schemaläggare, men kan inte återställas, eftersom $T_{2}$ commits trots att den har läst från en icke-bekräftad transaktion. För att säkerställa att den producerar återvinningsbara historiker, kan en schemaläggare hålla en lista över andra transaktioner som varje transaktion har läst från och inte låta en transaktion begå innan denna lista endast bestod av begångna transaktioner. För att undvika kaskadavbrott kan schemaläggaren märka data som skrivits av icke-överförda transaktioner som smutsiga , och aldrig låta en läsoperation påbörjas på en sådan datapost innan den avtaggades. För att få en strikt historik bör schemaläggaren inte tillåta några operationer på smutsiga föremål.

Implementeringsfrågor

Tidsstämpelupplösning

Detta är den minsta tid som förflutit mellan två intilliggande tidsstämplar. Om upplösningen av tidsstämpeln är för stor (grov), ökas möjligheten att två eller flera tidsstämplar är lika och på så sätt gör det möjligt för vissa transaktioner att utföra ur korrekt ordning. Om man till exempel antar att vi har ett system som kan skapa hundra unika tidsstämplar per sekund, och med tanke på två händelser som inträffar med 2 millisekunders mellanrum, kommer de förmodligen att få samma tidsstämpel även om de faktiskt inträffade vid olika tidpunkter.

Tidsstämpellåsning

Även om denna teknik är en icke-låsande teknik, eftersom objektet inte är låst från samtidig åtkomst under en transaktions varaktighet, kräver handlingen att registrera varje tidsstämpel mot objektet en extremt kort varaktighetslåsning på objektet eller dess ombud.

Se även