なぜU-ロックはデッドロックを回避するのか

http://www.ccs.neu.edu/home/salzberg/transproc/jan20-99.psをPDF化




U-Locks

The most frequent reason for deadlocks 
is conversion from S-locks to X-locks.

Suppose T1 has an S-lock on A and T2 has an S-lock on A 
and T1 requests an Xlock on A and T2 requests an X-lock on A. 
You get a deadlock. U-locks solve this problem.


U-locks would be used in update statements where the system must read 
each record first to see if it satisfies a "where" clause. 
Would U-locks be used in a transaction where a record is read 
in an SQL Select statement first, 
and then later updated in an Update Statement?


最もよく起きるデッドロックの原因は
S-ロックからX-ロックへのコンバージョンである。

T1がS-ロックをAに対してかけて、T2がS-ロックをAにかける
T1がX-ロックをAに対して要求し、T2もX-ロックをAに対して要求すると
デッドロックになる。U-ロックはこの問題を解決する。

U-ロックはupdate文で
システムが「where」句の条件をみたすレコードを
まず一件づつ読まなければならないときに使われる。

U-ロックは、最初にSQLのselect文でレコードを一件ずつ読んで
あとでupdate文で更新するトランザクションで使えるだろうか？





U-Locks

Salzberg's U-locks:

Clearing up the discussion on U locks. 
Do not pay attention to what is in the text on U locks. 
It does not make sense. 
Here is the story: A U-lock is exactly the same as an S-lock 
in its compatibility. 
The only new information to remember is that 
two U-locks are not compatible with each other. 
U is compatible with S and IS.

When a U lock wants to convert to an X-lock, 
it must obtain the necessary new higher granularity locks first. 
And replace page 416 with the following:

SalzbergのU-ロック

U-ロックの議論を明確にするために、
U-ロックで何が行われるかに注目しないでほしい。
無意味なのだ。
こんな話：
U-ロックはS-ロックと互換性は全く同じである。
覚えておかなければならない新しい情報は
U-ロック自身はお互い互換性がないことである。






Partial Order on Locks 

ロックの部分的な順序

	o IS < S (or U) 
	o IS < IX 
	o IX < SIX 
	o S (or U) < SIX 
	o SIX < X

If A < B then any lock L which conflicts with A conflicts with B.

A < Bのとき、どんなロックもAと競合するものはBとも競合する。




Compatability Matrix for locks

Table 21. Lock Type Compatibility
State Being Requested＼State of Held Resource

     none  IN   IS   NS    S  IX   SIX    U    X    Z   NW    W
none yes  yes  yes  yes  yes  yes  yes  yes  yes  yes  yes  yes
IN   yes  yes  yes  yes  yes  yes  yes  yes  yes   no  yes  yes
IS   yes  yes  yes  yes  yes  yes  yes  yes   no   no   no   no
NS   yes  yes  yes  yes  yes   no   no  yes   no   no  yes   no
S    yes  yes  yes  yes  yes   no   no  yes   no   no   no   no
IX   yes  yes  yes   no   no  yes   no   no   no   no   no   no
SIX  yes  yes  yes   no   no   no   no   no   no   no   no   no
U    yes  yes  yes  yes  yes   no   no   no   no   no   no   no
X    yes  yes   no   no   no   no   no   no   no   no   no   no
Z    yes   no   no   no   no   no   no   no   no   no   no   no
NW   yes  yes   no  yes   no   no   no   no   no   no   no  yes
W    yes  yes   no   no   no   no   no   no   no   no  yes   no







Rules for requesting locks:

o Obtain an IS lock or stronger on all ancestors 
before obtaining an S or IS lock on descendents 
in the object hierarchy. 
Reason: IS prevents X.


o Obtain a IX lock or stronger on all ancestors 
before obtaining an X, IX or SIX or U lock on descendents 
in the object hierarchy. Reason: IX prevents S (or U). 
(This will prevent a deadlock if a lower granularity 
and higher granularity U are both requested.)


S and X locks create implicit locks on objects lower in the object hierarchy.
If a file is S-locked, it is the same as if every record in the file were S-locked. 
If a file is X-locked, it is the same as if every record were X-locked.


ロック要求のルール:

o オブジェクト階層のなかで、S-ロックまたはIS-ロックをすべての子孫に対して獲得する前に
  IS-ロックかそれ以上に強いロックをすべての先祖に対して獲得する。
  結果：ISはXを防ぐ

o オブジェクト階層のなかで、X、IX、SIX、U-ロックをすべての子孫に対して獲得する前に
  IX-ロックかそれ以上に強いロックをすべての先祖に対して獲得する。
  結果：IXはS(またはU)を防ぐ
 (これでデッドロックを防ぐことができる。下位の部品と上位の部品が両方U-ロックを要求する。)














Lock Conversion

Within any LUW a process can only have one lock on a data object.Locks are hierarchical!
Conversion occurs when lower lock is held and a higher lock is needed.
If I hold an S lock on a row and I request a U lock The S lock is converted to U
If I hold an U lock on a row and I request a X lock The U lock is converted to X











DAG locks 

A little on DAG locks. What if there are two indexes? 
(This part uses key-range locks also.)

Example: T1 wants to update E and Xlocks [E G) as before. 
T2 wants to read the record with socsecno = 333-33-3444. 
But this record has alphakey = E. 
If T2 does not also locking the alphakey, 
or T1 does not also lock the socsecno, 
there is a problem.









DAG locks continued

Answer: To update (or insert or delete), 
X-lock all paths through indexes and to read, 
set an S lock on one of the paths.

Problem: What about scanning the table without using an index? 
(ok if T1 IX-locks the table and the scanner tries to get an 
S-lock on the table.)

Another problem: suppose there are ten indexes 
and there are 100 records with alphakey = E. 
Answer: for each record updated, inserted or deleted, 
all indexes must be key-range locked.








Instead of DAG locks

you can lock a record ID (RID or primary key) when it is read or updated, 
even if you look it up by a secondary key. This will cause the correct conflicts. This is probably what systems do when they lock records. You still need the table lock or the key-range locks to prevent phantoms.









Locking Heuristics (sec 7.9, text) 

o lock conversion
T1 has an S-lock or a U-lock 
(compatible with S but not with X) and wants to convert to an Xlock. 
T1 keeps the S-lock and requests the X-lock. 
(We will see T1 goes to front of lock-wait queue for a lock conversion request)


o lock escalation 
When a transaction has requested hundreds of record-granularity locks 
on the same table, most systems will escalate the lock to a table-level lock, 
dropping all the record-level locks.


o lock de-escalation 
Some systems begin by making all locks table-granularity locks. 
Then if there is a conflicting request, the lock is de-escalated 
to recordlevel locks. 
Transactions must maintain lists of the locks they would have requested 
if record-level locks were used.






Nested Transaction Locks (sec 7.10) 

Studying how nested transaction locks work explains 
what nested transactions do. The semantics of nesting 
can be derived from the mechanics of locking.

Sequential nested transactions are implemented in many systems, 
such as DB2 and Sybase. Sybase has nested pairs of begin 
and commit transaction statements. Only the outermost commit commits 
the transaction. The inner pairs just keep track of the nesting level. 
This nesting has no effect on locks.

If you have savepoints and rollback to a savepoint, the locks acquired after the savepoint are released (after the updates made since the savepoint are UNDONE).




Parallel Nesting 

Parallel nested transactions allow any child to inherit a lock 
from a parent (but not from a sibling). If a child subtransaction rolls back, 
the inherited locks are returned to the parent and the acquired 
locks are dropped. If a child commits, both inherited and acquired locks 
go to the parent. If a sibling wants a lock another sibling has, 
it has to wait.
Most systems do not support parallel nesting.








Deadlocks

 The order transactions request locks cannot be predicted, 
so deadlocks are always possible. Most systems use timeout 
to resolve possible deadlocks. (If you have to wait a long time, 
you are aborted.)

An alternative is to construct a waits-for graph. Transactions 
which are waiting are nodes and there is an edge from T1 to T2 
if T1 is waiting for T2. If there is a cycle in the graph, 
there is a deadlock. 
The transaction with the shortest number of log records might 
be chosen to be aborted.

Deadlock is rare. 
Only timeout is used for distributed deadlock.







The Convoy Phenomenon 

Suppose T1 is running in a high-priority process and T2 has a low priority.
When doing process switches, T1 should be chosen more often than T2. 
But suppose T2 acquires a lock on object X. T1 will have to wait for X.

Suppose T3 and T4 are also high priority and wait for X. 
When T2 finally gets some time, (because higher priority processes are 
no longer ready to run because they are waiting) T2 may run, 
release the lock and get swapped out and then T1 runs, releases the lock 
and goes to the end of the queue. T1, T3, T4 cycle forever. 
(The lock in the text example is the endof-log lock, 
which must be acquired for each update.) Solution: don't use a queue 
for hot spots lock waiting, or spin rather than wait, or don't allow lock 
holders to be pre-empted.





Mixed Multiversion Concurrency 

Mixed multiversion concurrency: Readonly transactions read the most recent 
version valid before their begin time. Read/Write transactions keep locks. 
and put committime timestamps on the records they update (or the TID and 
system keeps table correlating TID and commit time).

DEC's Rdb used this. Most systems do not.

A new transaction copies a TID vector: TIDs increase monotonically, 
so all you need is the TID of the earliest non-committed transaction T1 
(All TIDs less than T1s are from committed transactions) and the TIDs of 
any transactions which have already committed and are greater than T1's TID.







Snapshot Isolation (from Berenson et al.)

o Readers can read data from the most
recent version committed before the begin time (start timestamp)

o Updating transactions: When T1 is ready to commit, if gets a commit 
timestamp. Success if no other transaction T2 with commit timestamp in T1's 
(start, commit) interval wrote data that T1 also wrote (first committer) 
Otherwise T1 is aborted.

No locks. But also it does not guarantee isolation.









Examples for SI

T1 moves $40 from x to y; T2 reads an earlier version

H1SI: r1[x0=50] w1[x1=10]
r2[x0=50] r2 [y0=50] c2
r1[y0=50] w1[y1=90] c1

Here, T2<<


2003/08/28
ugya@lycos.com