Timestamp-based concurrency control - Revision history

Eddard69: /* Formal definition */ Corrected the definitions of RT(Oj) and WT(Oj).

2024-03-22T12:32:00Z

Formal definition: Corrected the definitions of RT(Oj) and WT(Oj).

← Previous revision		Revision as of 12:32, 22 March 2024
Line 16:		Line 16:
	Each transaction (<math>T_i</math>) is an ordered list of actions (<math>A_{ix}</math>). Before the transaction performs its first action (<math>A_{i1}</math>), it is marked with the current [[timestamp]], or any other [[total order\|strictly totally ordered]] sequence: <math>TS(T_i) = NOW()</math>. Every transaction is also given an initially empty set of transactions upon which it depends, <math>DEP(T_i) = []</math>, and an initially empty set of old objects which it updated, <math>OLD(T_i) = []</math>.		Each transaction (<math>T_i</math>) is an ordered list of actions (<math>A_{ix}</math>). Before the transaction performs its first action (<math>A_{i1}</math>), it is marked with the current [[timestamp]], or any other [[total order\|strictly totally ordered]] sequence: <math>TS(T_i) = NOW()</math>. Every transaction is also given an initially empty set of transactions upon which it depends, <math>DEP(T_i) = []</math>, and an initially empty set of old objects which it updated, <math>OLD(T_i) = []</math>.

	Each [[Object (computer science)\|object]] <math>(O_j)</math> in the database is given two timestamp fields which are not used other than for concurrency control: <math> RT(O_j)</math> is the ~~time~~ ~~at which~~ the ~~value~~ of ~~object~~ ~~was~~ ~~last~~ ~~read~~ by a ~~transaction,~~ <math>WT(~~O_j~~)</math> is the ~~time~~ at ~~which~~ the value of the object ~~was last updated by a transaction~~.		Each [[Object (computer science)\|object]] <math>(O_j)</math> in the database is given two timestamp fields which are not used other than for concurrency control:

			* <math> RT(O_j)</math> is the timestamp of the last transaction that read the value of the object ( <math>TS(T_r)</math>, where <math>T_r</math> is the last transaction that read the value of the object).
			* <math>WT(O_j)</math> is the timestamp of the last transaction that updated the value of the object ( <math>TS(T_w)</math>, where <math>T_w</math> is the last transaction that updated the value of the object).

	For all <math>T_i</math>:		For all <math>T_i</math>:

PetraMagna: minor changes to wording and punctuation

2024-02-05T03:25:17Z

minor changes to wording and punctuation

← Previous revision		Revision as of 03:25, 5 February 2024
Line 1:		Line 1:
	In [[computer science]], a '''timestamp-based concurrency control''' algorithm is a [[optimistic concurrency control]] method. It is used in some [[database]]s to safely handle transactions, using [[~~timestamp~~]]s.		In [[computer science]], a '''timestamp-based concurrency control''' algorithm is a [[optimistic concurrency control]] method. It is used in some [[database]]s to safely handle transactions using [[timestamps]].

	==Operation==		==Operation==
Line 8:		Line 8:

	===Generating a timestamp===		===Generating a timestamp===
	A number of different ~~ways~~ ~~have been used to~~ generate ~~timestamp~~		A number of different approaches can generate timestamps
	* ~~Use~~ the value of the system's clock at the start of a transaction as the timestamp.		* Using 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.		* Using a thread-safe shared counter that is incremented at the start of a transaction as the timestamp.
	* A combination of the above two methods.		* A combination of the above two methods.

	===Formal===		===Formal definition===
	Each transaction (<math>T_i</math>) is an ordered list of actions (<math>A_{ix}</math>). Before the transaction performs its first action (<math>A_{i1}</math>), it is marked with the current [[timestamp]], or any other [[total order\|strictly totally ordered]] sequence: <math>TS(T_i) = NOW()</math>. Every transaction is also given an initially empty set of transactions upon which it depends, <math>DEP(T_i) = []</math>, and an initially empty set of old objects which it updated, <math>OLD(T_i) = []</math>.		Each transaction (<math>T_i</math>) is an ordered list of actions (<math>A_{ix}</math>). Before the transaction performs its first action (<math>A_{i1}</math>), it is marked with the current [[timestamp]], or any other [[total order\|strictly totally ordered]] sequence: <math>TS(T_i) = NOW()</math>. Every transaction is also given an initially empty set of transactions upon which it depends, <math>DEP(T_i) = []</math>, and an initially empty set of old objects which it updated, <math>OLD(T_i) = []</math>.

Line 35:		Line 35:
	::If <math>WT(O_j)</math> equals <math>TS(T_i)</math> then restore <math>O_j = \mathrm{old}O_j</math> and <math>WT(O_j) = \mathrm{old}WT(O_j)</math>		::If <math>WT(O_j)</math> equals <math>TS(T_i)</math> then restore <math>O_j = \mathrm{old}O_j</math> and <math>WT(O_j) = \mathrm{old}WT(O_j)</math>

	===Informal===		===Informal definition===
	Whenever a transaction initiated, it receives a timestamp. The '''transaction's timestamp''' indicates when the transaction was initiated. These timestamps ensure that transactions affect each object in the same sequence of their respective timestamps. Thus, given two operations that affect the same object from different transactions, the operation of the transaction with the earlier timestamp must execute before the operation of the transaction with the later timestamp. However, if the operation of the wrong transaction is actually presented first, then it is aborted and the transaction must be restarted.		Whenever a transaction initiated, it receives a timestamp. The '''transaction's timestamp''' indicates when the transaction was initiated. These timestamps ensure that transactions affect each object in the same sequence of their respective timestamps. Thus, given two operations that affect the same object from different transactions, the operation of the transaction with the earlier timestamp must execute before the operation of the transaction with the later timestamp. However, if the operation of the wrong transaction is actually presented first, then it is aborted and the transaction must be restarted.

Line 67:		Line 67:

	===Timestamp resolution===		===Timestamp resolution===
	This is the minimum time elapsed between two adjacent timestamps. If the resolution of the timestamp is too large (coarse), the possibility of two or more timestamps being equal is increased and thus enabling some transactions to commit out of correct order. For example, ~~assuming that we have~~ a system that ~~can create~~ one hundred unique timestamps per second, ~~and given~~ two events that occur 2 milliseconds apart~~, they will~~ ~~probably~~ be given the same timestamp even though they ~~actually~~ occurred at different times.		This is the minimum time elapsed between two adjacent timestamps. If the resolution of the timestamp is too large (coarse), the possibility of two or more timestamps being equal is increased and thus enabling some transactions to commit out of correct order. For example, for a system that creates one hundred unique timestamps per second, two events that occur 2 milliseconds apart may be given the same timestamp even though they occurred at different times.

	===Timestamp locking===		===Timestamp locking===
	Even though this technique is a non-locking one, in as much as the ~~Object~~ is not locked from concurrent access for the duration of a transaction, the act of recording each timestamp against the Object requires an extremely short duration lock on the Object or its proxy.		Even though this technique is a non-locking one, in as much as the object is not locked from concurrent access for the duration of a transaction, the act of recording each timestamp against the Object requires an extremely short duration lock on the Object or its proxy.

	==See also==		==See also==

Guy Harris: Avoid redirect.

2023-12-22T21:55:00Z

Avoid redirect.

← Previous revision		Revision as of 21:55, 22 December 2023
Line 56:		Line 56:

	==Recoverability==		==Recoverability==
	{{for\|an explanation of the terms ''recoverable'' (''RC''), ''avoids cascading aborts'' (''ACA'') and ''strict'' (''ST'')\|Database transaction ~~scheduling~~}}		{{for\|an explanation of the terms ''recoverable'' (''RC''), ''avoids cascading aborts'' (''ACA'') and ''strict'' (''ST'')\|Database transaction schedule}}

	Note that timestamp ordering in its basic form does not produce recoverable histories. Consider for example the following history with transactions <math>T_1</math> and <math>T_2</math>:		Note that timestamp ordering in its basic form does not produce recoverable histories. Consider for example the following history with transactions <math>T_1</math> and <math>T_2</math>:

Guy Harris: Avoid redirect; the page is Database transaction scheduling, not Schedule (computer science) - the latter is a redirect to the former.

2023-12-22T21:00:45Z

Avoid redirect; the page is Database transaction scheduling, not Schedule (computer science) - the latter is a redirect to the former.

← Previous revision		Revision as of 21:00, 22 December 2023
Line 56:		Line 56:

	==Recoverability==		==Recoverability==
	{{for\|an explanation of the terms ''recoverable'' (''RC''), ''avoids cascading aborts'' (''ACA'') and ''strict'' (''ST'')\|~~Schedule~~ ~~(computer~~ ~~science)~~}}		{{for\|an explanation of the terms ''recoverable'' (''RC''), ''avoids cascading aborts'' (''ACA'') and ''strict'' (''ST'')\|Database transaction scheduling}}

	Note that timestamp ordering in its basic form does not produce recoverable histories. Consider for example the following history with transactions <math>T_1</math> and <math>T_2</math>:		Note that timestamp ordering in its basic form does not produce recoverable histories. Consider for example the following history with transactions <math>T_1</math> and <math>T_2</math>:

Jarfuls of Tweed: /* Informal */ only kept the first definition/mention of a timestamp as bolded

2023-12-11T22:35:15Z

Informal: only kept the first definition/mention of a timestamp as bolded

← Previous revision		Revision as of 22:35, 11 December 2023
Line 41:		Line 41:

	If a transaction wants to read an object,		If a transaction wants to read an object,
	* but the transaction started ''before'' the object's ~~'''~~write timestamp~~'''~~ it means that something changed the object's data after the transaction started. In this case, the transaction is canceled and must be restarted.		* but the transaction started ''before'' the object's write timestamp it means that something changed the object's data after the transaction started. In this case, the transaction is canceled and must be restarted.
	* and the transaction started ''after'' the object's ~~'''~~write timestamp~~'''~~, it means that it is ''safe'' to read the object. In this case, if the transaction's timestamp is after the object's ~~'''~~read timestamp~~'''~~, the read timestamp is set to the transaction's timestamp.		* and the transaction started ''after'' the object's write timestamp, it means that it is ''safe'' to read the object. In this case, if the transaction's timestamp is after the object's read timestamp, the read timestamp is set to the transaction's timestamp.

	If a transaction wants to write to an object,		If a transaction wants to write to an object,
	* but the transaction started ''before'' the object's ~~'''~~read timestamp~~'''~~ it means that something has had a look at the object, and we assume it took a copy of the object's data. So we can't write to the object as that would make any copied data invalid, so the transaction is aborted and must be restarted.		* but the transaction started ''before'' the object's read timestamp it means that something has had a look at the object, and we assume it took a copy of the object's data. So we can't write to the object as that would make any copied data invalid, so the transaction is aborted and must be restarted.
	* and the transaction started ''before'' the object's ~~'''~~write timestamp~~'''~~ it means that something has changed the object since we started our transaction. In this case we use the [[Thomas write rule]] and simply skip our write operation and continue as normal; the transaction does not have to be aborted or restarted		* and the transaction started ''before'' the object's write timestamp it means that something has changed the object since we started our transaction. In this case we use the [[Thomas write rule]] and simply skip our write operation and continue as normal; the transaction does not have to be aborted or restarted
	* otherwise, the transaction writes to the object, and the object's ~~'''~~write timestamp~~'''~~ is set to the transaction's timestamp.		* otherwise, the transaction writes to the object, and the object's write timestamp is set to the transaction's timestamp.

	== Physically unrealizable ==		== Physically unrealizable ==

Jarfuls of Tweed: /* Informal */ made the phrasing more precise

2023-12-11T22:25:59Z

Informal: made the phrasing more precise

← Previous revision		Revision as of 22:25, 11 December 2023
Line 36:		Line 36:

	===Informal===		===Informal===
	Whenever a transaction initiated, it receives a timestamp. The '''transaction's timestamp''' indicates when the transaction was initiated. These timestamps ~~are~~ ~~used~~ to ~~preserve~~ ~~the~~ ~~order~~ in ~~which~~ the ~~transactions~~ ~~must~~ be ~~started,~~ ~~relative~~ ~~to all the other transactions~~. So, given two ~~transactions~~ that affect the same object, the operation of the transaction with the earlier timestamp must execute before the operation of the transaction with the later timestamp. However, if the operation of the wrong transaction is actually presented first, then it is aborted and the transaction must be restarted.		Whenever a transaction initiated, it receives a timestamp. The '''transaction's timestamp''' indicates when the transaction was initiated. These timestamps ensure that transactions affect each object in the same sequence of their respective timestamps. Thus, given two operations that affect the same object from different transactions, the operation of the transaction with the earlier timestamp must execute before the operation of the transaction with the later timestamp. However, if the operation of the wrong transaction is actually presented first, then it is aborted and the transaction must be restarted.

	Every object in the database has a '''read timestamp''', which is updated whenever the object's data is read, and a '''write timestamp''', which is updated whenever the object's data is changed.		Every object in the database has a '''read timestamp''', which is updated whenever the object's data is read, and a '''write timestamp''', which is updated whenever the object's data is changed.

Jarfuls of Tweed: /* Recoverability */ defined physically unrealizable

2023-12-11T21:36:58Z

Recoverability: defined physically unrealizable

← Previous revision		Revision as of 21:36, 11 December 2023
Line 48:		Line 48:
	* and the transaction started ''before'' the object's '''write timestamp''' it means that something has changed the object since we started our transaction. In this case we use the [[Thomas write rule]] and simply skip our write operation and continue as normal; the transaction does not have to be aborted or restarted		* and the transaction started ''before'' the object's '''write timestamp''' it means that something has changed the object since we started our transaction. In this case we use the [[Thomas write rule]] and simply skip our write operation and continue as normal; the transaction does not have to be aborted or restarted
	* otherwise, the transaction writes to the object, and the object's '''write timestamp''' is set to the transaction's timestamp.		* otherwise, the transaction writes to the object, and the object's '''write timestamp''' is set to the transaction's timestamp.

			== Physically unrealizable ==
			The behavior is '''physically unrealizable''' if the results of transactions could not have occurred if transactions were instantaneous. The following are the only two situations that result in physically unrealizable behavior:

			# Transaction T tries to read X but TS(T) < WT(X). Reason: It means that X has been written to by another transaction after T began.
			# Transaction T tries to write X but TS(T) < RT(X). Reason: It means that a later transaction read X before it was written by T.

	==Recoverability==		==Recoverability==

Jarfuls of Tweed: /* Formal */ "RTS" --> "RT" and "WTS" --> "WT"

2023-12-11T21:16:48Z

Formal: "RTS" --> "RT" and "WTS" --> "WT"

Jarfuls of Tweed: /* Formal */ replaced some instances of "used" --> "read"

2023-12-11T21:10:42Z

Formal: replaced some instances of "used" --> "read"

← Previous revision		Revision as of 21:10, 11 December 2023
Line 16:		Line 16:
	Each transaction (<math>T_i</math>) is an ordered list of actions (<math>A_{ix}</math>). Before the transaction performs its first action (<math>A_{i1}</math>), it is marked with the current [[timestamp]], or any other [[total order\|strictly totally ordered]] sequence: <math>TS(T_i) = NOW()</math>. Every transaction is also given an initially empty set of transactions upon which it depends, <math>DEP(T_i) = []</math>, and an initially empty set of old objects which it updated, <math>OLD(T_i) = []</math>.		Each transaction (<math>T_i</math>) is an ordered list of actions (<math>A_{ix}</math>). Before the transaction performs its first action (<math>A_{i1}</math>), it is marked with the current [[timestamp]], or any other [[total order\|strictly totally ordered]] sequence: <math>TS(T_i) = NOW()</math>. Every transaction is also given an initially empty set of transactions upon which it depends, <math>DEP(T_i) = []</math>, and an initially empty set of old objects which it updated, <math>OLD(T_i) = []</math>.

	Each [[Object (computer science)\|object]] <math>(O_j)</math> in the database is given two timestamp fields which are not used other than for concurrency control: <math>RTS(O_j)</math> is the time at which the value of object was last ~~used~~ by a transaction, <math>WTS(O_j)</math> is the time at which the value of the object was last updated by a transaction.		Each [[Object (computer science)\|object]] <math>(O_j)</math> in the database is given two timestamp fields which are not used other than for concurrency control: <math>RTS(O_j)</math> is the time at which the value of object was last read by a transaction, <math>WTS(O_j)</math> is the time at which the value of the object was last updated by a transaction.

	For all <math>T_i</math>:		For all <math>T_i</math>:
	:For each action <math>A_{ix}</math>:		:For each action <math>A_{ix}</math>:
	::If <math>A_{ix}</math> wishes to ~~use~~ the value of <math>O_j</math>:		::If <math>A_{ix}</math> wishes to read the value of <math>O_j</math>:
	:::If <math>WTS(O_j) > TS(T_i)</math> then '''abort''' (a more recent thread has overwritten the value),		:::If <math>WTS(O_j) > TS(T_i)</math> then '''abort''' (a more recent thread has overwritten the value),
	:::Otherwise update the set of dependencies <math>DEP(T_i).\mathrm{add}(WTS(O_j))</math> and set <math>RTS(O_j) = \max(RTS(O_j), TS(T_i))</math>;		:::Otherwise update the set of dependencies <math>DEP(T_i).\mathrm{add}(WTS(O_j))</math> and set <math>RTS(O_j) = \max(RTS(O_j), TS(T_i))</math>;

Jarfuls of Tweed: /* Informal */ used consistent wording in the definition of a transaction's timestamp, and its references to improve clarity. Improved some other wording to be more precise.

2023-12-11T21:01:58Z

Informal: used consistent wording in the definition of a transaction's timestamp, and its references to improve clarity. Improved some other wording to be more precise.

← Previous revision		Revision as of 21:01, 11 December 2023
Line 36:		Line 36:

	===Informal===		===Informal===
	Whenever a transaction ~~begins~~, it receives a timestamp. ~~This~~ timestamp indicates the order in which the ~~transaction~~ must ~~occur~~, relative to the other transactions. So, given two transactions that affect the same object, the operation of the transaction with the earlier timestamp must execute before the operation of the transaction with the later timestamp. However, if the operation of the wrong transaction is actually presented first, then it is aborted and the transaction must be restarted.		Whenever a transaction initiated, it receives a timestamp. The '''transaction's timestamp''' indicates when the transaction was initiated. These timestamps are used to preserve the order in which the transactions must be started, relative to all the other transactions. So, given two transactions that affect the same object, the operation of the transaction with the earlier timestamp must execute before the operation of the transaction with the later timestamp. However, if the operation of the wrong transaction is actually presented first, then it is aborted and the transaction must be restarted.

	Every object in the database has a '''read timestamp''', which is updated whenever the object's data is read, and a '''write timestamp''', which is updated whenever the object's data is changed.		Every object in the database has a '''read timestamp''', which is updated whenever the object's data is read, and a '''write timestamp''', which is updated whenever the object's data is changed.
Line 42:		Line 42:
	If a transaction wants to read an object,		If a transaction wants to read an object,
	* but the transaction started ''before'' the object's '''write timestamp''' it means that something changed the object's data after the transaction started. In this case, the transaction is canceled and must be restarted.		* but the transaction started ''before'' the object's '''write timestamp''' it means that something changed the object's data after the transaction started. In this case, the transaction is canceled and must be restarted.
	* and the transaction started ''after'' the object's '''write timestamp''', it means that it is ''safe'' to read the object. In this case, if the transaction timestamp is after the object's '''read timestamp''', the read timestamp is set to the transaction timestamp.		* and the transaction started ''after'' the object's '''write timestamp''', it means that it is ''safe'' to read the object. In this case, if the transaction's timestamp is after the object's '''read timestamp''', the read timestamp is set to the transaction's timestamp.

	If a transaction wants to write to an object,		If a transaction wants to write to an object,

← Previous revision		Revision as of 21:16, 11 December 2023
Line 16:		Line 16:
	Each transaction (<math>T_i</math>) is an ordered list of actions (<math>A_{ix}</math>). Before the transaction performs its first action (<math>A_{i1}</math>), it is marked with the current [[timestamp]], or any other [[total order\|strictly totally ordered]] sequence: <math>TS(T_i) = NOW()</math>. Every transaction is also given an initially empty set of transactions upon which it depends, <math>DEP(T_i) = []</math>, and an initially empty set of old objects which it updated, <math>OLD(T_i) = []</math>.		Each transaction (<math>T_i</math>) is an ordered list of actions (<math>A_{ix}</math>). Before the transaction performs its first action (<math>A_{i1}</math>), it is marked with the current [[timestamp]], or any other [[total order\|strictly totally ordered]] sequence: <math>TS(T_i) = NOW()</math>. Every transaction is also given an initially empty set of transactions upon which it depends, <math>DEP(T_i) = []</math>, and an initially empty set of old objects which it updated, <math>OLD(T_i) = []</math>.

	Each [[Object (computer science)\|object]] <math>(O_j)</math> in the database is given two timestamp fields which are not used other than for concurrency control: <math>~~RTS~~(O_j)</math> is the time at which the value of object was last read by a transaction, <math>~~WTS~~(O_j)</math> is the time at which the value of the object was last updated by a transaction.		Each [[Object (computer science)\|object]] <math>(O_j)</math> in the database is given two timestamp fields which are not used other than for concurrency control: <math> RT(O_j)</math> is the time at which the value of object was last read by a transaction, <math>WT(O_j)</math> is the time at which the value of the object was last updated by a transaction.

	For all <math>T_i</math>:		For all <math>T_i</math>:
	:For each action <math>A_{ix}</math>:		:For each action <math>A_{ix}</math>:
	::If <math>A_{ix}</math> wishes to read the value of <math>O_j</math>:		::If <math>A_{ix}</math> wishes to read the value of <math>O_j</math>:
	:::If <math>~~WTS~~(O_j) > TS(T_i)</math> then '''abort''' (a more recent thread has overwritten the value),		:::If <math>WT(O_j) > TS(T_i)</math> then '''abort''' (a more recent thread has overwritten the value),
	:::Otherwise update the set of dependencies <math>DEP(T_i).\mathrm{add}(~~WTS~~(O_j))</math> and set <math>~~RTS~~(O_j) = \max(~~RTS~~(O_j), TS(T_i))</math>;		:::Otherwise update the set of dependencies <math>DEP(T_i).\mathrm{add}(WT(O_j)) </math> and set <math>RT(O_j) = \max(RT(O_j), TS(T_i))</math>;
	::If <math>A_{ix}</math> wishes to update the value of <math>O_j</math>:		::If <math>A_{ix}</math> wishes to update the value of <math>O_j</math>:
	:::If <math>~~RTS~~(O_j) > TS(T_i)</math> then '''abort''' (a more recent thread is already relying on the old value),		:::If <math>RT(O_j) > TS(T_i)</math> then '''abort''' (a more recent thread is already relying on the old value),
	:::If <math>~~WTS~~(O_j) > TS(T_i)</math> then '''skip''' (the [[Thomas Write Rule]]),		:::If <math>WT(O_j) > TS(T_i)</math> then '''skip''' (the [[Thomas Write Rule]]),
	:::Otherwise store the previous values, <math>OLD(T_i).\mathrm{add}(O_j, ~~WTS~~(O_j))</math>, set <math>~~WTS~~(O_j) = TS(T_i)</math>, and update the value of <math>O_j</math>.		:::Otherwise store the previous values, <math>OLD(T_i).\mathrm{add}(O_j, WT(O_j))</math>, set <math>WT(O_j) = TS(T_i)</math>, and update the value of <math>O_j</math>.
	:While there is a transaction in <math>DEP(T_i)</math> that has not ended: '''wait'''		:While there is a transaction in <math>DEP(T_i)</math> that has not ended: '''wait'''
	:If there is a transaction in <math>DEP(T_i)</math> that aborted then '''abort'''		:If there is a transaction in <math>DEP(T_i)</math> that aborted then '''abort'''
Line 32:		Line 32:

	To '''abort''':		To '''abort''':
	:For each <math>(\mathrm{old}O_j, \mathrm{old}~~WTS~~(O_j))</math> in <math>OLD(T_i)</math>		:For each <math>(\mathrm{old}O_j, \mathrm{old}WT(O_j)) </math> in <math>OLD(T_i)</math>
	::If <math>~~WTS~~(O_j)</math> equals <math>TS(T_i)</math> then restore <math>O_j = \mathrm{old}O_j</math> and <math>~~WTS~~(O_j) = \mathrm{old}~~WTS~~(O_j)</math>		::If <math>WT(O_j)</math> equals <math>TS(T_i)</math> then restore <math>O_j = \mathrm{old}O_j</math> and <math>WT(O_j) = \mathrm{old}WT(O_j)</math>

	===Informal===		===Informal===