Timestamp-Based Protocol 편집하기

'''Timestamp-Based Protocol''' is a concurrency control mechanism in database systems that uses timestamps to order transactions, ensuring serializability. Each transaction is assigned a unique timestamp when it begins, and the protocol uses these timestamps to determine the execution order of conflicting operations.
==Key Concepts==
*'''Timestamp:''' A unique identifier (usually based on the system clock or a counter) assigned to each transaction when it starts.
*'''Read and Write Timestamps:'''
**Each data item is associated with:
***'''Read Timestamp (RT):''' The largest timestamp of any transaction that successfully read the data item.
***'''Write Timestamp (WT):''' The largest timestamp of any transaction that successfully wrote the data item.
==Rules for Timestamp-Based Protocol==
The protocol enforces the following rules to maintain serializability:
#'''Write Operation:'''
#*If a transaction T1 attempts to write to a data item:
#**If T1's timestamp is less than the read timestamp of the data item, the write is rejected, and T1 is aborted.
#**If T1's timestamp is less than the write timestamp of the data item, the write is rejected, and T1 is aborted.
#**Otherwise, the write is allowed, and the write timestamp is updated.
#'''Read Operation:'''
#*If a transaction T1 attempts to read a data item:
#**If T1's timestamp is less than the write timestamp of the data item, the read is rejected, and T1 is aborted.
#**Otherwise, the read is allowed, and the read timestamp is updated.
==Example of Timestamp-Based Protocol==
Consider two transactions T1 and T2 accessing a shared data item A:
{| class="wikitable"
!Step!!Transaction T1!!Transaction T2!!Explanation
|-
|1||BEGIN TRANSACTION (TS=1)||BEGIN TRANSACTION (TS=2)||T1 and T2 are assigned timestamps 1 and 2, respectively.
|-
|2||READ(A)||-||T1 reads A. RT(A) is updated to 1.
|-
|3||-||WRITE(A)||T2 attempts to write to A. WT(A) is updated to 2.
|-
|4||WRITE(A)||-||T1 attempts to write to A but is aborted because TS(T1) < WT(A).
|}In this example, T1 is aborted because it attempts to write to A after a newer transaction (T2) has already written to it.
==Advantages==
*'''Deadlock-Free:''' Timestamp-based protocols avoid deadlocks because transactions are never required to wait.
*'''Simple Implementation:''' The protocol relies only on timestamps, reducing complexity.
*'''Ensures Serializability:''' Transactions are executed in timestamp order, guaranteeing a serializable schedule.
==Limitations==
*'''Cascading Aborts:''' Transactions may be frequently aborted due to timestamp conflicts, leading to performance degradation.
*'''Overhead:''' Maintaining timestamps and metadata for each data item can be resource-intensive.
*'''Starvation:''' Older transactions may be aborted repeatedly in favor of newer transactions.
==Applications==
Timestamp-based protocols are commonly used in:
*'''Distributed Databases:''' Ensuring consistency across nodes by assigning global timestamps.
*'''Real-Time Systems:''' Prioritizing transactions based on their timestamps.
*'''Optimistic Concurrency Control:''' Validating transactions at commit time using timestamp-based techniques.
==Variants==
The basic timestamp-based protocol has several extensions to handle specific scenarios:
*'''Thomas' Write Rule:'''
**Allows a transaction to ignore certain outdated writes, reducing unnecessary aborts.
*'''Multiversion Timestamp Ordering (MVTO):'''
**Maintains multiple versions of data to improve concurrency and reduce conflicts.
==See Also==
*[[Concurrency Control]]
*[[Two-Phase Locking]]
*[[Thomas' Write Rule]]
*[[Multiversion Concurrency Control]]
*[[Transaction Management]]
*[[Serializability]]
[[Category:Database]]