Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Timestamp-based concurrency control
Résumé
In computer science, a timestamp-based concurrency control algorithm is a non-lock concurrency control method. It is used in some databases to safely handle transactions, using timestamps.
Every timestamp value is unique and accurately represents an instant in time.
A higher-valued timestamp occurs later in time than a lower-valued timestamp.
A number of different ways have been used to generate timestamp
Use the value of the system's clock at the start of a transaction as the timestamp.
Use a thread-safe shared counter that is incremented at the start of a transaction as the timestamp.
A combination of the above two methods.
Each transaction () is an ordered list of actions (). Before the transaction performs its first action (), it is marked with the current timestamp, or any other strictly totally ordered sequence: . Every transaction is also given an initially empty set of transactions upon which it depends, , and an initially empty set of old objects which it updated, .
Each object in the database is given two timestamp fields which are not used other than for concurrency control: is the time at which the value of object was last used by a transaction, is the time at which the value of the object was last updated by a transaction.
For all :
For each action :
If wishes to use the value of :
If then abort (a more recent thread has overwritten the value),
Otherwise update the set of dependencies and set ;
If wishes to update the value of :
If then abort (a more recent thread is already relying on the old value),
If then skip (the Thomas Write Rule),
Otherwise store the previous values, , set , and update the value of .
While there is a transaction in that has not ended: wait
If there is a transaction in that aborted then abort
Otherwise: commit.
To abort:
For each in
If equals then restore and
Whenever a transaction begins, it receives a timestamp. This timestamp indicates the order in which the transaction must occur, relative to the other transactions.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.