In der Informatik ist ein Zeitstempel-basierter Parallelitätskontrollalgorithmus eine Nichtschloss-Parallelitätskontrollmethode. Es wird in einigen Datenbanken verwendet, um Transaktionen mit Zeitstempeln sicher zu behandeln.

Operation

Annahmen

• Jeder Zeitstempel-Wert ist einzigartig und vertritt genau einen Moment rechtzeitig.
• Keine zwei Zeitstempel können dasselbe sein.
• Ein höher geschätzter Zeitstempel kommt später rechtzeitig vor als ein tiefer geschätzter Zeitstempel.

Das Erzeugen eines Zeitstempels

Mehrere verschiedene Wege sind verwendet worden, um Zeitstempel zu erzeugen

• Verwenden Sie den Wert der Uhr des Systems am Anfang einer Transaktion als der Zeitstempel.
• Verwenden Sie einen vor dem Faden sicheren geteilten Schalter, der am Anfang einer Transaktion als der Zeitstempel zusätzlich ist.
• Eine Kombination der obengenannten zwei Methoden.

Formell

Jede Transaktion ist eine geordnete Liste von Handlungen . Bevor die Transaktion seine erste Handlung durchführt , wird sie mit dem aktuellen Zeitstempel oder jeder anderen ausschließlich völlig bestellten Folge gekennzeichnet:. Jede Transaktion wird auch ein am Anfang leerer Satz von Transaktionen gegeben, auf die sie abhängt, und ein am Anfang leerer Satz von alten Gegenständen, die sie aktualisiert hat.

Jeder Gegenstand in der Datenbank wird zwei Zeitstempel-Felder gegeben, die anders nicht verwendet werden als für die Parallelitätskontrolle: Ist die Zeit, in der der Wert des Gegenstands verwendet durch eine Transaktion letzt war, ist die Zeit, in der der Wert des Gegenstands aktualisiert durch eine Transaktion letzt war.

Für alle:

:For jede Handlung:

:: Wenn Wünsche, den Wert zu verwenden:

::: Wenn dann abbrechen (ein neuerer Faden hat den Wert überschrieben),

::: Aktualisieren Sie sonst den Satz von Abhängigkeiten und gehen Sie unter;

:: Wenn Wünsche, den Wert zu aktualisieren:

::: Wenn dann abbrechen (ein neuerer Faden verlässt sich bereits auf den alten Wert),

::: Wenn dann (die Regierung von Thomas Write), hüpfen

::: Versorgen Sie sonst die vorherigen Werte, den Satz, und aktualisieren Sie den Wert dessen.

:While dort ist eine Transaktion darin hat nicht geendet: Warten Sie

auf

:If dort ist eine Transaktion darin abgebrochen dann brechen ab

:Otherwise: Begehen.

Abzubrechen:

:For jeder in

:: Wenn gleich ist, dann stellen wieder her und

Informell

Wann auch immer eine Transaktion anfängt, wird sie ein Zeitstempel gegeben. Das ist so wir können erzählen, welche Ordnung, in der die Transaktionen angewandt werden sollen. So gegeben zwei Transaktionen, die denselben Gegenstand betreffen, wird die Transaktion, die den früheren Zeitstempel hat, gemeint, um vor der anderen angewandt zu werden. Jedoch, wenn die falsche Transaktion wirklich zuerst präsentiert wird, wird sie abgebrochen und muss wiederangefangen werden.

Jeder Gegenstand in der Datenbank hat einen gelesenen Zeitstempel, der aktualisiert wird, wann auch immer die Daten des Gegenstands, und ein schreiben Zeitstempel gelesen werden, der aktualisiert wird, wann auch immer die Daten des Gegenstands geändert wird.

Wenn eine Transaktion einen Gegenstand, lesen

will

• aber die Transaktion hat angefangen vor dem Gegenstand schreiben Zeitstempel es bedeutet, dass etwas die Daten des Gegenstands geändert hat, nachdem die Transaktion angefangen hat. In diesem Fall wird die Transaktion annulliert und muss wiederangefangen werden.
• und die Transaktion hat angefangen nach dem Gegenstand schreiben Zeitstempel, es bedeutet, dass es sicher ist, den Gegenstand zu lesen. In diesem Fall, wenn der Transaktionszeitstempel ist, nach dem gelesenen Zeitstempel des Gegenstands wird der gelesene Zeitstempel auf den Transaktionszeitstempel gesetzt.

Wenn eine Transaktion einem Gegenstand, schreiben

will

• aber die Transaktion hat angefangen vor dem gelesenen Zeitstempel des Gegenstands bedeutet es, dass etwas auf den Gegenstand einen Blick geworfen hat, und wir annehmen, dass es eine Kopie der Daten des Gegenstands genommen hat. So können wir nicht dem Gegenstand schreiben, weil das jeden kopierten Dateninvaliden machen würde, so wird die Transaktion abgebrochen und muss wiederangefangen werden.
• und die Transaktion hat angefangen vor dem Gegenstand schreiben Zeitstempel es bedeutet, dass etwas den Gegenstand geändert hat, seitdem wir unsere Transaktion angefangen haben. In diesem Fall verwenden wir die Regierung von Thomas Write und lassen einfach unseren aus, Operation geschrieben, und machen als normal weiter; die Transaktion muss nicht abgebrochen oder wiederangefangen werden
• sonst schreibt die Transaktion dem Gegenstand, und der Gegenstand schreibt, dass Zeitstempel auf den Zeitstempel der Transaktion gesetzt wird.

Werthaltigkeit

Für eine Erklärung der Begriffe wiedergutzumachend (FERNSTEUERUNG) sehen vermeidet, Abbrüche wellig zu fallen (ACA) und streng (ST) Liste (Informatik).

Bemerken Sie, dass die Zeitstempel-Einrichtung in seiner grundlegenden Form wiedergutzumachende Geschichten nicht erzeugt. Denken Sie zum Beispiel die folgende Geschichte mit Transaktionen und:

:

Das konnte durch zum PLANER erzeugt werden, aber ist nicht wiedergutzumachend, wie wenn auch begeht, von einer uncomitted Transaktion lesen. Um sich zu überzeugen, erzeugt es wiedergutzumachende Geschichten, ein Planer kann eine Liste anderer Transaktionen behalten, die jede Transaktion davon gelesen hat, und eine Transaktion hat nicht begehen lassen, bevor diese Liste aus nur begangenen Transaktionen bestanden hat. Um zu vermeiden, Abbrüche wellig zu fallen, konnte der Planer Daten markieren, die durch neutrale Transaktionen als geschrieben sind, schmutzig, und nie eine gelesene Operation auf solch einem Datenartikel anfangen lassen, bevor es unmarkiert war. Um eine strenge Geschichte zu bekommen, sollte der Planer keine Operationen auf schmutzigen Sachen erlauben.

Durchführungsprobleme

Zeitstempel-Entschlossenheit

Das ist die minimale zwischen zwei angrenzenden Zeitstempeln vergangene Zeit. Wenn die Entschlossenheit des Zeitstempels (rau) zu groß ist, wird die Möglichkeit von zwei oder mehr Zeitstempeln, die gleich sind, vergrößert und so einige Transaktionen ermöglichend, aus der richtigen Ordnung zu begehen. Zum Beispiel das Annehmen, dass wir ein System haben, das hundert einzigartige Zeitstempel pro Sekunde, und gegeben zwei Ereignisse schaffen kann, die 2 Millisekunden entfernt vorkommen, wird ihnen wahrscheinlich derselbe Zeitstempel gegeben, wenn auch sie wirklich zu verschiedenen Zeiten vorgekommen sind.

Zeitstempel-Blockierung

Wenn auch diese Technik eine nicht verriegelnde, in so viel ist, wie der Gegenstand vom gleichzeitigen Zugang für die Dauer einer Transaktion nicht geschlossen wird, verlangt die Tat, jeden Zeitstempel gegen den Gegenstand zu registrieren, ein äußerst kurzes Dauer-Schloss auf dem Gegenstand oder seiner Vertretung.

Siehe auch

• Mehrversionsparallelität kontrolliert
• Timestamping, (rechnend)