Thomas’ Write Rule
Modified version of the timestamp-ordering protocol in which
obsolete write operations may be ignored under certain circumstances.
– When Ti attempts to write data item Q, if TS(Ti ) <
W-timestamp(Q), then Ti is attempting to write an obsolete value of Q. Hence, rather than rolling back Ti as the timestamp ordering protocol would have done, this write
operation can be ignored.
– Otherwise, this protocol is the same as the timestamp
ordering protocol.
Thomas’ Write Rule allows for greater potential concurrency.
Unlike previous protocols, it allows some view-serializable
schedules that are not conflict-serializable.
Database Systems Concepts 14.22 Silberschatz
Validation-Based Protocol
Execution of transaction Ti is done in three phases.
1. Read and execution phase: Transaction Ti writes only to
temporary local variables
2. Validation phase: Transaction Ti performs a “validation
test” to determine if local variables can be written without violating serializability.
3. Write phase: If Ti is validated, the updates are applied to
the database; otherwise, Ti is rolled back.
The three phases of concurrently executing transactions can
be interleaved, but each transaction must go through the three
phases in that order
– Start(Ti): the time when Ti started its execution
– Validation(Ti ): the time when Ti entered its validation
phase
– Finish(Ti ): the time when Ti finished its write phase
Serializability order is determined by timestamp given at
validation time, to increase concurrency. Thus TS(Ti ) is given
the value of Validation(Ti ).
This protocol is useful and gives a greater degree of concurrency
if the probability of conflicts is low. That is because the
serializability order is not pre-decided and relatively fewer
transactions will have to be rolled back
Validation Test for Transaction Tj
If for all Ti with TS (Ti ) < TS (Tj ) either one of the followingcondition holds:
– finish(Ti ) < start(Tj )
– start(Tj ) < finish(Ti ) < validation(Tj ) and the set of data
items written by Ti does not intersect with the set of data
items read by Tj .
then validation succeeds and Tj can be committed. Otherwise,
validation fails and Tj is aborted.
Justification: Either the first condition is satisfied, and there is no
overlapped execution or second condition is satisfied and
1. the writes of Tj do not affect reads of Ti since they occur
after Ti has finished its reads.
2. the writes of Ti do not affect reads of Tj since Tj does not
read any item written by Ti .
Schedule Produced by Validation
Example of schedule produced using validation
Multiple Granularity
Allow data items to be of various sizes and define a hierarchy
of data granularities, where the small granularities are nested
within larger ones
Can be represented graphically as a tree (but don’t confuse
with tree-locking protocol)
when a transaction locks a node in the tree explicitly, it
implicitly locks all the node’s descendants in the same mode.
Granularity of locking (level in tree where locking is done):
– fine granularity (lower in tree): high concurrency, high
locking overhead
– coarse granularity (higher in tree): low locking overhead,
low concurrency
Example of Granularity Hierarchy
Intention Lock Modes
In addition to S and X lock modes, there are three additional
lock modes with multiple granularities:
– intention-shared (IS): indicates explicit locking at a lower
level of the tree but only with shared locks.
– intention-exclusive (IX): indicates explicit locking at a lower
level with exclusive or shared locks
– shared and intention-exclusive (SIX): the subtree rooted by
that node is locked explicitly in shared mode and explicit
locking is being done at a lower level with exclusive-mode
locks.
intention locks allow a higher level node to be locked in S or X
mode without having to check all descendant nodes.
Database
Compatibility Matrix with Intention Lock Modes
The compatibility matrix for all lock modes is:
Multiple Granularity Locking Scheme
Transaction Ti can lock a node Q, using the following rules:
1. The lock compatibility matrix must be observed.
item root of the tree must be locked first, and maybe locked in any mode.
2. A node Q can be locked by Ti in S or IS mode only if the
parent of Q is currently locked by Ti in either IX or IS mode.
3. A node Q can be locked by Ti in X, SIX, or IX mode only if
the parent of Q is currently locked by Ti in either IX or SIX
mode.
4. Ti can lock a node only if it has not previously unlocked any
node (that is, Ti is two-phase).
5. Ti can unlock a node Q only if none of the children of Q are
currently locked by Ti .
Observe that locks are acquired in root-to-leaf order, whereas
they are released in leaf-to-root order.
Multiversion Schemes
Multiversion schemes keep old versions of data items to
increase concurrency.
– Multiversion Timestamp Ordering
– Multiversion Two-Phase Locking
Each successful write results in the creation of a new version
of the data item written.
Use timestamps to label versions.
When a read(Q) operation is issued, select an appropriate
version of Q based on the timestamp of the transaction, and return the value of the selected version.
reads never have to wait as an appropriate version is returned
immediately.
Multiversion Timestamp Ordering
Each data item Q has a sequence of versions
< Q1,Q2, . . .,Qm >. Each version Qk contains three data
fields:
– Content – the value of version Qk .
– W-timestamp(Qk ) – timestamp of the transaction that
created (wrote) version Qk
– R-timestamp(Qk ) – largest timestamp of a transaction that
successfully read version Qk
when a transaction Ti creates a new version Qk of Q, Qk ’s
W-timestamp and R-timestamp are initialized to TS(Ti ).
R-timestamp of Qk is updated whenever a transaction Tj reads
Qk , and TS(Tj ) > R-timestamp(Qk ).
Suppose that transaction Ti issues a read(Q) or write(Q)
operation. Let Qk denote the version of Q whose write
timestamp is the largest write timestamp less than or equal to
TS(Ti ).
1. If transaction Ti issues a read(Q), then the value returned is
the content of version Qk .
2. If transaction Ti issues a write(Q), and if TS(Ti ) <
R-timestamp(Qk ), then transaction Ti is rolled back.
Otherwise, if TS(Ti ) = W-timestamp(Qk ), the contents of Qk
are overwritten, otherwise, a new version of Q is created.
Reads always succeed; a write by Ti is rejected if some other
transaction Tj that (in the serialization order defined by the
timestamp values) should read Ti ’s write, has already read a
version created by a transaction older than Ti .
Multiversion Two-Phase Locking
Differentiates between read-only transactions and update
transactions
Update transactions acquire read and write locks and hold all
locks up to the end of the transaction. That is, update
transactions follow rigorous two-phase locking.
– Each successful write results in the creation of a new
version of the data item written.
– each version of a data item has a single timestamp whose
value is obtained from a counter ts counter that is
incremented during commit processing.
Read-only transactions are assigned a timestamp by reading
the current value of ts counter before they start execution;
they follow the multi-version timestamp-ordering protocol for
performing reads.
Deadlock Handling
Consider the following two transactions:
T1: write(X) T2: write(Y)
write(Y) write(X)
Schedule with deadlock
The system is deadlocked if there is a set of transactions such that
every transaction in the set is waiting for another transaction in
the set.
Deadlock prevention protocols ensure that the system will
never enter into a deadlock state. Some prevention strategies :
– Require that each transaction locks all its data items before
it begins execution (pre declaration).
– Impose partial ordering of all data items and require that a
transaction can lock data items only in the order specified
by the partial order (graph-based protocol).
More Deadlock Prevention Strategies
The following schemes use transaction timestamps for the sake of
deadlock prevention alone.
wait-die scheme — non-preemptive
– the older transactions may wait for the younger ones to release data
items. Younger transactions never wait for older ones; they
are rolled back instead.
– a transaction may die several times before acquiring
needed data item
wound-wait scheme — preemptive
– older transaction wounds (forces rollback) of younger
transaction instead of waiting for it. Younger transactions
may wait for older ones.
– maybe fewer rollbacks than wait-die scheme.
Both in wait-die and in wound-wait schemes, a rolled-back
transaction is restarted with its original timestamp. Older
transactions thus have precedence over newer ones, and
starvation is hence avoided.
Timeout-Based Schemes :
– a transaction waits for a lock only for a specified amount of
time. After that, the wait times out and the transaction is
rolled back.
– thus deadlocks are not possible
– simple to implement, but starvation is possible. Also difficult
to determine the good value of the timeout interval.
Deadlock Detection
Deadlocks can be described as a wait-for graph, which
consists of a pair G = (V,E),
– V is a set of vertices (all the transactions in the system)
– E is a set of edges; each element is an ordered pair
Ti ! Tj .
If Ti ! Tj is in E, then there is a directed edge from Ti to Tj ,
implying that Ti is waiting for Tj to release a data item.
When Ti requests a data item currently being held by Tj , then
the edge Ti ! Tj is inserted in the wait-for graph. This edge
is removed only when Tj is no longer holding a data item
needed by Ti .
The system is in a deadlock state if and only if the wait-for
graph has a cycle. Must invoke a deadlock-detection algorithm
periodically to look for cycles.
Deadlock Recovery
When a deadlock is detected :
– Some transactions will have to roll back (made a victim) to
break the deadlock. Select that transaction as a victim that will
incur the minimum cost.
– Rollback – determine how far to rollback transaction
Total rollback: Abort the transaction and then restart it.
More effective to roll back transactions only as far as
necessary to break the deadlock.
– Starvation happens if the same transaction is always chosen as
a victim. Include the number of rollbacks in the cost factor to
avoid starvation.
Insert and Delete Operations
If two-phase locking is used :
– A delete operation may be performed only if the transaction
deleting the tuple has an exclusive lock on the tuple to be
deleted.
– A transaction that inserts a new tuple into the database is
given an X-mode lock on the tuple
Insertions and deletions can lead to the phantom
phenomenon.
– A transaction that scans a relation (eg., find all accounts in
Perryridge) and a transaction that inserts a tuple in the
relation (eg., insert a new account at Perryridge) may
conflict in spite of not accessing any tuple in common.
Actually, the transaction scanning the relation is reading
information that indicates what tuples the relation contains,
while a transaction inserting a tuple updates the same
information. The information should be locked.
One solution: associate a data item with the relation, to
represent the information about what tuples the relation
contains. Transactions scanning the relation acquire a shared
lock in the data item, while transactions inserting or deleting a
tuple acquire an exclusive lock on the data item.
(Note: locks on the data item do not conflict with locks on
individual tuples.)
The above protocol provides very low concurrency for
insertions/deletions. Index locking protocols provide higher
concurrency.
– If only tuple locks are used, non-serializable schedules can
result: the scan transaction may not see the new account,
yet maybe serialized before the insert transaction.
Index Locking Protocol
Every relation must have at least one index. Access to a
relation must be made only through one of the indices on the
relation.
A transaction Ti that performs a lookup must lock all the index
buckets that it accesses, in S-mode.
A transaction Ti may not insert a tuple ti into a relation r
without updating all indices to r. Ti must perform a lookup on
every index to find all index buckets that could have possibly
contained a pointer to tuple ti, had it existed already, and
obtain locks in X-mode on all these index buckets. Ti must also
obtain locks in X-mode on all index buckets that it modifies.
The rules of the two-phase locking protocol must be observed
Concurrency in Index Structures
Indices are unlike other database items in that their only job is
to help in accessing data.
Index-structures are typically accessed very often, much more
than other database items.
Treating index-structures like other database items leads to low
concurrency. Two-phase locking on an index may result in
transactions executing practically one-at-a-time.
It is acceptable to have non-serializable concurrent access to
an index as long as the accuracy of the index is maintained. In
particular, the exact values read in an internal node of a B+-tree
are irrelevant so long as we land up in the correct leaf node.
There are index concurrency protocols where locks on internal
nodes are released early, and not in a two-phase fashion.
Example of index concurrency protocol:
Use crabbing instead of two-phase locking on the nodes of the
B+-tree, as follows. During search/insertion/deletion:
– First, lock the root node in shared mode.
– After locking all required children of a node in shared mode,
release the lock on the node.
– During insertion/deletion, upgrade leaf node locks to
exclusive mode.
– When splitting or coalescing requires changes to a parent,
lock the parent in exclusive mode.
The above protocol can cause excessive deadlocks. Better
protocols are available; see Section 14.8 for one such protocol,
the B-link tree protocol
No comments:
Post a Comment