Chap. 16 Concurrency and Serializability - Isolation

*Textbook: Chapter 15(6판), Chapter 18(7판)

Concurrent Executions (동시 실행)

• Allows multiple transactions to update data concurrently ensuring consistency.

① 처리율과 자원(CPU & Disk) 이용률 향상

⇒ Concurrency increases the 'throughput': the no. of transactions/sec.

⇒ the CPU and disk 'utilization' increases.

Ex) T1, T2, T3: Read (A)

CPU operation

Write (B)

② 대기시간 감소: 순차적으로 실행된다면 짧은 transaction이 긴 transaction이 끝날 때까지 오래 기다려야 함

CPU         Table A    Table B

DBMS

T2

T3

T1

T1

A

B

A

cpu

B

A

cpu

B

A

cpu

B

t

T2

T3

- But, concurrent access anomalies (i.e., inconsistency) can happen.

⇒ DB의 비일관성

Ex)	- Balance: Accnt. A - $1000, Accnt. B - $2000

- T1: Transfer $50 from accnt. A to accnt B

T2: Transfer 10% of the balance from accnt. A to accnt B

T1:	Read(A);	T2:	Read(A);

A = A - 50;	temp = A * 0.1;

Write(A);	A = A - temp;

Read(B);	Write(A);

B = B + 50;	Read(B);

Write(B);	B = B + temp;

Write(B);

<순차적 스케쥴>

① Serial Schedule 1: p.587 Fig.15-3,

Accnt. A - $855, Accnt. B - $2145

⇒ Consistency is preserved.

② Serial Schedule 2: p.587 Fig.15-4,

Accnt. A - $850, Accnt. B - $2150

⇒ Consistency is preserved.

- For a set of n trans., there exists n! different valid 'serial' schedules.

- The schedule no longer needs to be ‘serial’.

⇒ A time-sharing OS performs a context switch.

⇒ Operations can be interleaved.

⇒ ‘Much larger different valid’ schedules than n!

⇒ ‘Serializable' schedule

<동시 스케쥴>

③ Concurrent Schedule 3: p.588 Fig.15-5,

Equivalent to Schedule 1

⇒ Consistency is preserved.

- Are all concurrent schedules valid?

④ Concurrent Schedule 4: p.589 Fig.15-6,

Accnt. A - $950, accnt. B - $2100

⇒ Inconsistency.

- If concurrent execution of trans. is left entirely to the OS, many 'invalid' schedules are possible.

⇒ The DBMS needs the Concurrency Control scheme.

⇒ All 'valid concurrent' schedules must be equivalent to a 'serial' schedule

<Ti, Tj, …>.

Serializability

• Concurrency Control schemes (동시성 제어 기법)

- Provide a high degree of concurrency.

- 직렬성: All schemes are based on the ‘serializability’ property.

⇒ Ensuring that all schedules generated are 'conflict/view serializable' and 'cascadeless'.

- Which schedules will ensure consistency, and which schedules will not?

⇒ Different forms of 'schedule equivalence'

⇒ Conflict & View serializability (충돌 직렬성/뷰 직렬성)

- The only significant operations are Read(A) and Write(A).

⇒ A transaction may perform an arbitrary seq. of operations on the copy of A in the ‘local buffer’.

Ex) p.590 Fig.15-7,

Schedule 3: read와 write만을 나타낸 스케쥴

1. Conflict Serializability (충돌 직렬성)

- There are two consecutive instructions Ii and Ij of trans. Ti and Tj, respectively.

⇒ If Ii and Ij refer to the 'same' data item Q, the order may matter.

- There are four possible cases.

① Case 1:	Ii = Read(Q), Ij = Read(Q)

⇒ The same value of Q is read by Ti and Tj.

⇒ The order does NOT matter.

② Case 2:	Ii = Read(Q), Ij = Write(Q)

⇒ Ii → Ij : Ti reads the value of Q before Tj writes.

Ij → Ii : Ti reads the value of Q written by Tj.

⇒ The order matters.

③ Case 3:	Ii = Write(Q), Ij = Read(Q)

⇒ Ii → Ij : Tj reads the value of Q written by Ti.

Ij → Ii : Tj reads the value of Q before Ti writes.

⇒ The order matters.

④ Case 4:	Ii = Write(Q), Ij = Write(Q)

⇒ Ii → Ij : The value of Q written by Tj is preserved in the DB.

Ij → Ii : The value of Q written by Ti is preserved in the DB.

⇒ The order matters.

⇒ Only when both Ii and Ij are Read(Q), the relative order does NOT matter.

- We say that Ii and Ij are 'conflict',

① IF they are instructions of different transactions on the same data, and

② at least one of instructions is Write(Q).

⇒ 같은 항목을 접근하는 Ii 와 Ij 중 최소 하나는 ‘Write’일 때 서로 충돌(conflict)

Ex) p.590 Fig.15-7, p.591 Fig.15-8

Schedule 3	Schedule 5: Equivalent to 3

T1	T2		T1	T2
Read(A)			Read(A)
Write(A)			Write(A)
	Read(A)			Read(A)
	Write(A)	←‘Not 충돌’→	Read(B)
Read(B)		(다른 항목)		Write(A)
Write(B)			Write(B)
	Read(B)			Read(B)
	Write(B)			Write(B)

⇒ We can swap the order of Ii and Ij to produce a new schedule, IF Ii and Ij do NOT conflict.

: 서로 충돌하지 않는다면 두 명령어(instruction)의 순서를 바꿀 수 있다.

⇒ Schedule 3 and 5 produce the 'same' final state.

Schedule 5	Serial Schedule 6

T1	T2		T1	T2
Read(A)			Read(A)
Write(A)			Write(A)
	Read(A)		Read(B)
Read(B)			Write(B)
	Write(A)			Read(A)
Write(B)				Write(A)
	Read(B)			Read(B)
	Write(B)			Write(B)

⇒ Schedule 5로부터 순차적인(serial) Schedule 6을 얻을 수 있다

- 충돌 동등: S' and S" are 'conflict equivalent', IF S' can be transformed into S" by a series of swaps of 'nonconflicting' instructions.

Ex)	Schdule 3 (p.588 Fig.15-5) is conflict equivalent to Schedule 1.

Schdule 2 (p.587 Fig.15-4) is NOT conflict equivalent to Schedule 1.

- 충돌 직렬적: We say that S' is conflict 'serializable' IF it is conflict equivalent to a 'serial' schedule S.

Ex)	Schdule 3 is conflict serializable.

⇒ Schedule 3로부터 순차적인(serial) Schedule 1을 얻을 수 있다

Ex)	Schedule 7 (p.592 Fig.15-10) is NOT conflict serializable.

⇒ It is NOT equivalent to either the serial schedule <T3,T4> or <T4,T3>

⇒ conflict한 instruction의 순서가 serial schedule과 동일하지 않다.

serial schedule <T3,T4>	Schedule 7	serial schedule <T4,T3>

T3	T4		T3	T4		T3	T4
Read(Q)			Read(Q)				Write(Q)
Write(Q)				Write(Q)		Read(Q)
	Write(Q)		Write(Q)			Write(Q)

- But, it is possible for two non-equivalent schedules to produce the 'same' outcome.

Ex)	□ Transfers $10 from accnt. A to accnt. B.

□ Schedule 8 (p.593 Fig.15-11) is NOT conflict equivalent to the serial schedule <T1,T5>.

□ Final outcome of Schedule 8    : accnt. A - $960, accnt. B - $2040

Final outcome of serial schedule: accnt. A - $960, accnt. B - $2040

⇒ There are less stringent definitions of schedule equivalence than that of ‘conflict equivalence’.

2. View Serializability (뷰 직렬성)

- A form of 'less stringent' definitions of schedule equivalence than that of conflict equivalence.

⇒ 충돌 동등보다 덜 엄격한 정의가 있을 수 있다.

- S' and S" with the same set of transactions are said to be 'view equivalent',

IF the following three conditions are met;

① For each data item Q, if Ti reads the initial value of Q in S', then Ti in S" must also read the initial value of Q.

② For each data item Q, if the value of Q is produced by Tj (if any) and Ti  in S' execute Read(Q), then Ti in S" must also read the value of Q that was produced by Tj.

③ For each data item Q, the trans. (if any) that performs the final Write(Q) in S' must also perform the final Write(Q) in S".

"Ensures that each trans. reads the same values in both schedules"

(두 스케쥴이 같은 값을 읽는 것을 보장)

"Ensures that both schedules result in the same final system state"

(두 스케쥴이 같은 최종 상태를 가지는 것을 보장함)

① Ti가 S'에서 데이터 Q의 초기값을 읽는다면, S"에서도 Q의 초기값을 읽어야 한다.

② Ti가 S'에서 Tj가 기록한 Q의 값을 읽는다면, S"에서도 Tj가 기록한 Q의 값을 읽어야 한다.

③ 어떠한 데이터 Q에 대해서도 S'에서 Q에 대해 마지막으로 기록한 트랜잭션이 S"에서도 Q에 대해 마지막으로 기록하여야 한다.

Strong condition: 모든 R-W, W-R, W-W conflict를 금지

Conflict Serializability

View Serializability

Weak condition

Ex)	Schedule 1 (p.587 Fig.15-3) ↔  Schedule 2 (p.587 Fig.15-4)

⇒ Violation of Condition 2: Schedule 1에서 T2가 읽은 계좌 A의 값은 T1이 기록한 값인데, Schedule 2에서는 반대임

⇒ NOT view serializable

Schedule 1 ↔ Schedule 3 (p.588 Fig.15-5)

⇒ View serializable

- 뷰 직렬성: We say that S' is 'view serializable' IF it is view equivalent to a 'serial' schedule S.

Ex)	Schedule 9 (p.594 Fig.15-12) is view serializable.

T4, T6: blind write - read(Q)하지 않고 바로 write(Q) 실행

⇒ It is view equivalent to serial schedule <T3,T4,T6>.

T3의 read(Q)가 양쪽 스케쥴 모두에서 Q의 초기값을 읽고,

또한 양쪽 스케쥴에서 T6의 write(Q)가 Q에 마지막 기록하기 때문임

⇒ But, it is NOT conflict serializable.

• Precedence Graph of S'

- 선행그래프(precedence graph)를 사용하면 어느 스케쥴 내에 속한 트랜잭션간의 있을 수 있는 ‘모든 충돌(conflict)’들을 파악할 수 있음.

- Let {T0,T1, … ,Tn} be a set of transactions in S'.

We say that Ti 'precedes' Tj, written Ti→Tj, if there exist Q such that Ti has held a lock on Q, and Tj has held a incompatible lock on Q later.

⇒ 노드: S'에 속한 트랜잭션마다 하나의 노드

간선: Ti의 어떤 단위작업이 Tj의 단위 작업보다 선행하면서 서로 충돌 관계(R-W, W-R, W-W)이면 Ti→Tj

Ex) p.598 Fig.15-15, Fig.15-16,

p.599 Fig.15-17

Ex) Concurrent Schedule 4: p.589 Fig.15-6,

Accnt. A - $950, accnt. B - $2100

⇒ Inconsistency.

T1

T2

- A schedule S' is 'legal' under a given locking protocol IF S' is a possible schedule following the rules.

⇒ A locking protocol ensures ‘conflict serializability’ iff, for all legal schedules, the precedence graph is 'acyclic'.

⇒ 즉, 선행그래프에 사이클이 없으면 그 스케쥴은 충돌 직렬가능(conflict serializable)이며, 그 역도 성립.

- Why? The precedence graph of a 'serial' schedule S is always 'acyclic'.

⇒ 즉, cycle이 있다면 conflict operation(R-W, W-R, W-W)들이 serial하지 않음.

Recoverability (복구성)

• 동시 실행 중에 트랜잭션의 실패가 어떠한 영향을 미치는가.

- If Ti fails, it is necessary that Tj that is dependent on Ti (i.e, Tj has read data written by Ti) must be also aborted.

Ti가 실패하면 그에 ‘종속적인’ 트랜잭션 Tj(Ti가 기록한 데이터를 읽는 경우) 또한 중단되어야 한다.

• What schedules are acceptable in case of trans. 'failures' during concurrent execution.

- 트랜잭션 실패로부터 '복구'하는 관점으로 볼 때 어떠한 스케쥴이 받아들여질 수 있는가?

⇒ We need to place 'further' restrictions on acceptable schedules.

⇒ 'Recoverable' and 'Cascadeless' schedules

• 복구가능 스케쥴: The DBMS requires that all schedules be 'recoverable'.

Ex) Schedule 11 (p.595 Fig.15-13)

T9 commits before T8 does, and suppose that T8 fails before it commits.

⇒ It is impossible to recover correctly from the failure of T8.

⇒ 'Nonrecoverable' schedule (복구 불가능 스케쥴)

- Recoverable Schedules: For each pair of transactions Ti and Tj such that Tj reads a data previously written by Ti, the commit of Ti appears 'before' the commit of Tj.

⇒ Ti가 Write한 데이터 Q를 Read하는 Tj의 각 쌍에 대하여 Tj의 연산이 완료되기 전에 Ti의 연산이 먼저 완료하는 스케쥴

• Cascading rollback (연쇄적 복귀)

- Even if a schedule is recoverable, to recover 'correctly' from the failure of a Ti, 'several' transactions must roll back.

⇒ 복구 ‘가능’하더라도 Write한 Q값을 ‘Read’하는 서로 종속적인 여러 트랜잭션들을 모두 복귀시켜야 한다.

Ex) T10 fails: T10 'rollbacks' → T11 'rollbacks'  → T12 'rollbacks'

- A single trans. failure leads to a 'series' of trans. rollbacks.

⇒ 'Undesirable' since it leads to ‘undoing’ of a significant amount of work.

- 비연쇄적 스케쥴 (Cascadeless Schedules)

For each pair of transactions Ti and Tj such that Tj reads a data previously written by Ti, the commit of Ti appears before the 'read' operation of Tj.

⇒ Ti가 Write한 데이터 Q를 Read하는 Tj의 각 쌍에 대하여 Tj의 ‘Read’ 연산이 완료되기 전에 Ti의 완료가 먼저 실행되는 스케쥴

- Restrict the schedules to those where cascading rollbacks CANNOT occur.

⇒ Commit된 트랜잭션이 Write한 데이터만 다른 트랜잭션이 Read하는 스케쥴은 ‘복구가능(recoverable)’ 스케쥴일뿐만 아니라, ‘연쇄철회 회피(cascadeless)’ 스케쥴임.

Cascadeless

Recoverable

Concurrency Control Schemes

• Concurrency-control schemes: 동시성 제어 기법

- Provide a high degree of concurrency.

- All schemes are based on the serializability property.

⇒ Ensuring that all schedules generated are ‘conflict/view serializable’, AND are 'cascadeless'.

- DBMS에서 어떻게 구현할 것인가?

⇒ 'Lock-based' + '2 Phase' + 'Strict'

Strong condition: 모든 R-W, W-R, W-W conflict를 금지

⇒ Pessimistic

Conflict Serializable

View Serializable

Weak condition

⇒ Optimistic

Serializable Schedules,

Nonserializable Schedules

1. Lock-Based Protocols

∙ Access a data item Q ONLY IF it is currently holding a 'lock' on that item.

⇒ 데이터 항목 Q에 락을 가진 트랜잭션만이 액세스할 수 있음

⇒ Mutual Exclusion (상호배제)

∙ Two modes

① 'Shared' Lock-S(Q) : Ti can read, but CANNOT write Q.

⇒ Ti가 데이터 Q에 대해 ‘공유락’을 얻으면 Read할 수 있으나 Write할 수는 없다.

② 'Exclusive' Lock-X(Q): Ti can both read and write Q.

⇒ Ti가 데이터 Q에 대해 ‘전용락’을 얻으면 Read하기도 하고 Write할 수도 있다.

∙ 모든 트랜잭션은 데이터 항목 Q에 대해 적절한 모드의 락을 동시성 제어 모듈에게 요청해야 함

⇒ 동시성 제어 모듈은 해당 트랜잭션에게 요청한 락을 허용한 다음, 트랜잭션은 자신의 연산을 계속하여 진행할 수 있음

∙ Lock(Q) and Unlock(Q)

① 'Every' trans. 'request' a lock on Q depending on the types of operations.

⇒ Lock-S(Q) for Read(Q) or Lock-X(Q) for Write(Q)

⇒ 호환성: Shared mode is ‘compatible’ with Shared mode, but not with Exclusive mode.

Ex) p.605 Fig.16-1

Q

①Ti: Write(Q)

② Tj: Read(Q)

Lock-X(Q)

Lock-S(Q): 'wait until released'

③Tk: Write(Q)

Lock-X(Q): 'wait until released'

② The trans. can proceed only after the concurrency-control manager 'grants' the lock.

③ The trans. may 'unlock' Q after its access on Q.

⇒ Unlock(Q)

∙ Problem: ‘언제’ Unlock할 것인가

⇒ It is NOT always desirable that a trans. unlocks Q 'immediately' after its final access on Q.

⇒ 트랜잭션이 데이터 항목을 마지막으로 엑세스한 다음 ‘곧바로’ Unlock하는 것이 바람직하지 못한 경우가 있는데, 직렬성이 보장되지 않기 때문.

Ex) Accnt A - $100, Accnt B - $200

T1 and T2 (p.607 Fig.16-4)

⇒ T2 displays $250, which is incorrect.

⇒ T1 release a Lock-X(B) 'too early'.

T1	T2	Concurrency Control Manager
Lock-X(B)
		Grant-X(B,T1)
Read(B)
B=B-50
Write(B)
→ Unlock(B)
	Lock-S(A)
		Grant-S(A,T2)
	Read(A)
	Unlock(A)
	Lock-S(B)
		Grant-S(B,T2)
	Read(B)
	Unlock(B)
	Display(A+B)
Lock-X(A)
		Grant-X(A,T1)
Read(A)
A=A+50
Write(A)
Unlock(A)

∙ Unlocking must be 'delayed' to the 'end phase' of the trans.

⇒ 2PL(Two Phase Locking) Protocol

⇒ Growing/Shrinking phase of locks

Ex) p.607, 608, T3 and T4

⇒ 락을 맨 나중에 해제

T4 displays $300, which is correct.

⇒ But, 'deadlock' can happen (p.608 Fig.16-7, Schedule 2)

T1	T2
Lock-X(B)
Read(B)
B=B-50
Write(B)
	Lock-S(A)
	Read(A)
	Lock-S(B)
Lock-X(A)

∙ 교착 상태: Wherever a lock is used, there is always a deadlock problem.

⇒ 'Necessary Evil' if we want to avoid inconsistency.

⇒ The system must roll back 'one' of the transactions when deadlock occurs.

∙ Locking Protocol(규약): A set of ‘rules’ for each trans. to follow.

⇒ The CC(concurrency-control) manager must use a locking protocol.

⇒ Several locking protocols generate only 'conflict-serializable' schedules.

∙ Starvation: 기아 상태

Q

Ti: Read(Q)

Tj: Write(Q)

Tk: Read(Q)

Lock-S(Q): 'granted immediately'

Lock-S(Q)

Lock-X(Q): 'wait' until Tk, Tl, … ← 'Starved'

Tl: Read(Q)

- We can avoid starvation by granting locks as follows.

When Ti requests a lock on Q, the lock is granted provided that there is NO other trans. that is waiting for a lock on Q 'before' Ti.

Lock-S(Q): 'granted immediately'

Lock-S(Q): 'wait' until Tk releases

Q

Ti: Read(Q)

Tj: Write(Q)

Tk: Read(Q)

Lock-S(Q): 'wait' until Tj releases

Lock-S(Q)

Lock-X(Q): 'wait' until Ti releases

Tl: Read(Q)

• Two Phase Locking Protocol (2PL)

- Each trans. issue lock and unlock requests in 'two' phases.

① Growing Phase: 증가 단계

A trans. may 'obtain' locks, but may NOT release any lock.

② Shrinking Phase: 감소 단계

A trans. may 'release' locks, but may NOT obtain any new locks.

⇒ Once a trans. release a lock, it enters the shrinking phase and CANNOT issue more lock requests.

Ex) T1, T2 (p.607 Fig.16-4): Not 2PL - Unlock 다음에 다시 Lock을 요청

T5, T6, T7: 2PL - 일단 Unlock하면 다시 Lock을 요청하지 않음(p.611 Fig.16-8)

growing phase

'lock point': final lock

(마지막 락을 얻는 지점)

shrinking phase

lock-X(B)		lock-X(B)
…		…
lock-X(A)		lock-X(A)
…	← 2PL →	unlock(B)
…		…
unlock(B)		…
unlock(A)		unlock(A)

① 2PL ensures 'conflict serializability'

⇒ The precedence graph for all legal schedules under 2PL is 'acyclic'.

② But, 2PL is NOT a deadlock-free protocol.

T1	T2
Lock-X(B)
Read(B)
B=B-50
Write(B)
	Lock-S(A)
	Read(A)
	Lock-S(B)
Lock-X(A)

③ 2PL is also NOT a 'cascadeless' protocol.

⇒ Cascading rollback may occur under 2PL.

Ex) The failure of T6 after the Read(A) of T7 leads to cascading rollback of T6 and T7.

(T7이 ‘A'에 대해 Shared-Lock을 가졌기 때문에 T6와 동시에 실행되고 있음)

- Most commercial DBMSs implement either 'strict' or 'rigorous' 2PL WITH lock conversions.

⇒ 두 종류의 2PL과 락변환 사용

1. Strict 2PL

- 2PL + All 'exclusive' locks must be held UNTIL a trans. 'commits'.

⇒ 트랜잭션이 정상적으로 완료될 때까지 자신이 가진 '배타적' 락들을 그대로 유지한다.

- Any data written by an uncommitted trans. are locked in exclusive mode until the trans. commits.

⇒ Prevents any other trans. from reading that data.

⇒ 아직 완료되지 않은 트랜잭션에 의해 갱신된 데이터는 그 트랜잭션이 완료될 때까지 배타적 락이 걸려있으므로 다른 트랜잭션이 그 데이터를 읽을 수도 없다.

⇒ Prevents cascading rollback.

2. Rigorous 2PL

- 2PL + ALL locks must be held UNTIL a trans. commits.

⇒ 트랜잭션이 정상적으로 완료될 때까지 자신이 가진 ‘모든’ 락들을 그대로 유지한다.

⇒ Stronger than Strict 2PL.

- Transactions can be 'serialized' in the order of their commits under rigorous 2PL.

• Lock Conversions:

- Concurrency를 높이기 위한 방법

① Upgrade   : Lock-S(A) → Lock-X(A), Permitted only in 'growing' phase.

② Downgrade: Lock-X(A) → Lock-S(A), Permitted only in 'shrinking' phase.

Ex)	T8: read(a1)	T9: read(a1)

read(a2)	read(a2)

…	display(a1+a2)

read(an)

write(a1)

T8 needs lock-X(a1) & T9 needs lock-S(a1)

⇒ Serial execution.

But, T8 needs lock-X(a1) only at the 'end' of its execution, when it writes a1.

⇒ T8 do lock-S(a1), and later UPGRADE it to lock-X(a1).

⇒ T8 and T9 can access a1 and a2 simultaneously.

⇒ More concurrency.

- Enforced Wait: 대기상태

⇒ A trans. attempting to 'upgrade' a lock on Q may be 'forced to wait'

IF Q is currently locked by another trans. in shared mode.

⇒ 데이터 항목 Q의 락을 배타락으로 높이려 할 때 그 트랜잭션은 대기상태에 있을 수 있다. (다른 트랜잭션의 Unlock(Q)가 실행될 때까지)

⇒ 이러한 대기상태는 Q가 다른 트랜잭션에 의해 공유락이 걸려있는 경우 발생함.

- Protocol: Used extensively in commercial DBMSs.

① When Ti issues Read(Q), a CC manager (lock manager) issues Lock-S(Q) and Read(Q).

⇒ Ti가 Read(Q)를 실행하려 하면 락모듈은 Read(Q) 전에 Lock-S(Q)를 실행

② When Ti issues Write(Q), a CC manager checks to see whether Ti already issues Lock-S(Q).

IF it holds Lock-S(Q), the CC manager issues Upgrade(Q).

Otherwise, the CC manager issues Lock-X(Q) and Write(Q).

⇒ Ti가 Write(Q)를 실행하려 하면 락모듈은 Q에 대해 Lock-S를 가지고 있는지 검사한다.

만약 Ti가 공유락을 가지고 있다면, 락모듈은 Upgrade(Q)를 실행.

그렇지 않다면, 락모듈은 Write(Q) 전에 Lock-X(Q)를 실행

③ All locks obtained by a trans. are unlocked after that trans. 'commits' or 'aborts'.

⇒ 트랜잭션에 의해 획득된 모든 락들은 그 트랜잭션이 완료되거나 중단된 뒤에 전부 해제된다.

2. Graph-Based Protocols

3. Timestamp-Based Protocols

4. Validation-Based Protocols

5. Multiversion Schemes

Implementation Issues

• Lock Manager(락 관리기)

- 트랜잭션들에게 발부해 준 락들을 추적하는 DBMS 모듈.

- 락테이블: 데이터 객체(페이지/레코드 단위) 식별자를 키로 하는 Hash table.

⇒ 이 객체에 대해 락을 소지하고 있는 트랜잭션의 수 (공용 락의 경우 복수), 현재 락의 종류(공용/전용), 이 객체에 대해 대기하고 있는 락 요청들의 큐에 대한 포인터 등의 정보가 들어 있음

…
p-1	Lock-X(Ti)
p	Lock-S(Tj), Lock-S(Tk)
p+1
…

Lock-S(Tm)

Lock-X(Tn), Lock-S(Tp)

- 트랜잭션이 어떤 데이터에 대한 락을 필요로 하게 되면 락 관리기에게 락요청을 함.

⇒ 락을 얻으면 2PL 규약에 따라 commit되거나 abort될 때까지 락을 계속 소지하고 있어야 함.

- 락 관리기는 아래와 같이 락을 허용

① 공용 락을 요청시: 요청 큐는 비어 있으며 (즉, 전용 락이 앞에 대기하고 있지 않음 - starvation 방지), 해당 객체가 현재 전용 모드로 락되어 있지 않는 경우에는, 락을 허가하고 해당 객체에 대한 락 테이블 엔트리를 갱신함.

⇒ 즉, 그 객체가 공용 모드로 락되어 있다고 표시하고, 락 소지 트랜잭션의 수를 하나 증가시킴.

② 전용 락을 요청시: 현재 그 객체에 대한 락을 소지하고 있는 트랜잭션이 없는 경우에는 락을 허가하고 해당 객체에 대한 락 테이블 엔트리를 갱신함.

③ 그 밖의 경우에는 요청된 락이 바로 허가될 수 없으며, 해당 객체에 대한 락 요청 큐에 이 요청을 추가함.

⇒ 락을 요청한 트랜잭션은 sleep.

④ 트랜잭션이 commit되거나 abort되면 해당 락들을 모두 해제시킴.

⇒ 어떤 객체에 대한 락이 해제되면, 그 객체에 대한 락 테이블 엔트리를 갱신하고, 그 객체에 대한 큐의 앞머리에 있는 락 요청을 허가함.

⇒ 큐의 앞에 여러 개의 공용 락이 있는 경우, 이들 모두를 허가해 줌.

⑤ 락 승급(upgrade) 요청: 트랜잭션이 이미 ‘공용’ 락을 가지고 있는 객체에 대해 다시 ‘전용’ 락을 얻어야 하는 경우.

⇒ 이 객체에 대해서 공용 락을 소지하고 있는 다른 트랜잭션이 없으면, 전용 락을 바로 허가해 주고, 그렇지 않으면 큐의 앞머리에 ‘특별히’ 삽입.

⇒ Why? 이미 그 객체에 대해 공용 락을 소지하고 있기 때문에, 동일한 객체에 대해 전용 락을 요청하고 있는 다른 트랜잭션의 뒤에 넣게 되면 Deadlock이 발생.

Ex) Processes of Oracle

D000    Dispatcher

① user process

□application processes such as sqlplus.

② server process

□user process의 request를 받아 DB 작업을 수행하는 process.

③ listener

□service를 요청하는 client에 dispatcher를 할당함.

□dispatcher는 client를 SGA에 할당하고, client와 multi-threaded server간의 연결을 담당.

④ lock process (LCKn)

□OPS (Oracle Parallel Server) 환경하에서 instance 사이에 요구되는 lock들을 관리.

□OPS하에서는 여러 instance들이 ‘하나의’ DB를 동시에 관리하므로 이들 사이에 lock의 관리가 필요함.

'Client'

'Server'

sqlplus

Ora

Listnr

Tn

T1

Port# 1521

Redo

Log

Buffer

Dbw

DB

Buffer

Cache

Write(X')

Read(X)

X

X'

X

Lock-S(X)

Lock-X(X)

fork() & exec()

Result/Error Msg

X

X'

X

Lgwr

X'

Tn:

sqlplus

fork() & exec()

Ex) Lock in Oracle

Lock Type	설명
DML Lock	table/block/row (data)에 관한 lock
DDL Lock	table/view의 definition (data dictionary) 변경시에 필요한 lock
Internal Lock (latch: 빗장)	datafile/tablespace같은 DB 내부자원들에 관한 lock - Oracle에서 자동으로 수행됨.
Distr. Lock	distr. DB 환경에서 사용되는 lock - lock의 소요자는 trans.이 아니라 instance임.
PCM Lock	OPS 환경에서 분산되어 있는 data buffer cache에 있는 data block에 관한 lock

Lock Mode	설명
Exclusive	다른 Trans.과 공유되지 않음.
Shared	다른 Trans.의 read는 허용되나 write는 공유되지 않음.

Deadlock Handling

∙ Wherever a lock is used, there is a deadlock problem.

① Deadlock Prevention

② Deadlock Detection and Recovery

∙ Methods

① 'Wait-for' graph:

⇒ 주기적으로 대기그래프에 사이클이 생기는지를 점검.

⇒ 사이클을 형성하는 트랜잭션 중 하나를 abort시키고 그 트랜잭션이 가지고 있던 락을 해제.

⇒ Precise, but expensive

Ex) p.496 Fig.14-13, Fig.14-14

② 'Timeout-based' deadlock detection: In the absence of a general analysis which determines the trade-off of various deadlock avoidance methods, as well as the lack of understanding of complex inter-relationships of deadlock among protocol levels, the commercial systems and real life applications are mainly based in the most experience method.

⇒ 어떤 트랜잭션이 락을 너무 오랫동안 기다리고 있었다면, deadlock 사이클에 이 트랜잭션이 들어 있다고 ‘비관적으로’ 가정하여 이 트랜잭션을 abort 시킴.

⇒ 2-Phase Locking with 'time-out'-based deadlock detection.

Ex) Processes of Oracle

D000    Dispatcher

④ system monitor (SMON)

□‘instance 시작 시’와 다중 instance 시스템에서 장애가 발생한 instance 복구 시에 실행됨.

□사용되지 않는 segment를 회수하고, instance 복구 시에 완료되지 못한 trans.들을 복구함.

⑤ process monitor (PMON)

□user process가 실패했을 때 process 처리를 수행.

□실패한 user process가 점유하고 있던 자원을 회수하고, cache를 정리함.

Ex) Deadlock in Oracle

UDATE member

SET location=‘LA’

WHERE name=‘David'

UDATE member

SET location=‘NY’

WHERE name=‘Diane'

UDATE member

SET location=‘LA’

WHERE name=‘David'

UDATE member

SET location=‘NY’

WHERE name=‘Diane'

‘Diane' 'Chicago'

…

‘David' 'Houston'

…

Trans. A

Trans. B

Block 1001

Block 1005

Lock-X(1005)

Lock-X(1001)

Lock-X(1001)

Lock-X(1005)

- Oracle은 deadlock 발생시 error msg.를 내보냄.

- Deadlock을 풀기위해 하나의 trans.을 abort 시킴.

⇒ 그 trans.은 rollback되므로, user는 그 trans.을 다시 수행.

- Application 개발 시 발생할 소지를 최소화하고, 발생할 경우에 대비하여 예외처리 routine을 작성하여 두는 것이 바람직함.

⇒ Undo/Redo

Concurrency in Index Structures

∙ Observation

- 'Index blocks' are accessed more frequently than 'data blocks'.

⇒ 트리탐색은 항상 root node로부터 시작해서 leaf node까지 아래로 내려오며 진행.

⇒ More lock contentions: 특히 트리의 윗 부분에서는 lock 경쟁이 극심함.

- It is 'acceptable'

to have 'nonserializable' concurrent access to an index,

AS LONG AS the 'accuracy' of the index is maintained.

⇒ A 'higher' degree of concurrency is needed.

- 탐색시 root부터 원하는 leaf까지의 경로에 있는 모든 node들에게 S-Lock을 걸어야 함.

⇒ 자식 node에 대한 lock을 얻는 순간 바로 위의 부모 lock은 Unlock해도 됨.

⇒ NOT 2PL protocol

∙ Technique for Concurrent Access to B+-Trees

- Based on 'locking', but not 2PL.

- Every node (tree and leaf nodes) maintains a pointer to its 'right' sibling.

⇒ B-link trees

- A lookup may hold a pointer to an 'incorrect' node, when a split/coalesce occurs in the lower-level node.

⇒ A lookup that occurs while the lower-level node is being split may have to search that 'node's right sibling' (if one exist) as well as 'that node'.

⇒ Then, by following right sibling pointers, the lookup must 'eventually' reach the correct node.

Ex) p.502 Fig.14-15

T2: Lookup  'Downtown'

T1: Insert 'Clearview'

"Shared lock" and waiting for the lower-level node

"Exclusive lock" and spliting the node

	Mianus

	Brighton		Downtown

T1 splits the node.

⇒ T2 holds a pointer to an incorrect node.

T2: Lookup  'Downtown'

T1: Insert 'Clearview'

Pointing a 'wrong' node

"Exclusive lock" and spliting the node

	Mianus

	Brighton		Clearview

	Downtown

T1 updates the parent node, and T2 access the right sibling node.

T2: Lookup  'Downtown'

T1: Insert 'Clearview'

Follows the pointer to the right sibling node

"Exclusive lock" and updates the node

	Downtown

	Brighton		Clearview

	Downtown

- Algorithms

① Lookup (탐색)

□Each node must be locked in S-Lock before it is accessed.

□This lock is 'released' before S-Lock on the 'next' lower-level node is requested.

□If a 'split' occurs 'concurrently' with a lookup, the search key value is located by following the pointer to the 'right sibling'.

② Insertion/Deletion (삽입/삭제)

□Locate the node into which the insertion/deletion is to be made.

□The S-Lock on this node is 'upgraded' to X-Lock, and then, the insertion/deletion is performed.

③ Split (분할 - 삽입시)

□If a node is split, the right-sibling pointers of both the 'original' node and the 'new' node are set.

T1: Insert 'Clearview'

"X-Lock" and splits the node

	Daton		Mianus

	Brighton		Clearview

	Daton

	Mianus		Clearview

□After this, the X-Lock on the original node is released, and an X-Lock is requested on the parent, so that a pointer to the new node can be inserted.

④ Coalescence (결합 - 삭제시)

□The node with which it will be coalesced must be locked in X-Lock.

T1: Delete 'Clearview'

"X-Lock" and coalesce the node

	Daton		Mianus

	Brighton		Clearview

	Daton

	Mianus

□Once these two nodes have been coalesced, the X-Lock is requested on the 'parent' so that the deleted node can be removed.

⇒ The lock on the coalesced node is released.

□Unless the parent node must also be coalesced, its lock is released.

- Deadlock can happen.

□Concurrent 'lookup' can NOT lead to deadlock.

□'Insertion/Deletion' can lead deadlock IF a lookup has locked the 'parent' of nodes being splited/coalesced.

T2: Lookup  'Brighton'

T1: Delete 'Clearview'

S-Lock

X-Lock

'Waits' X-Lock

'Waits' S-Lock

	Daton		Mianus

	Brighton		Clearview

	Daton

	Mianus

□Solution: Leave nodes 'uncoalesced'

⇒ Violates the B+-tree property.

⇒ In most DBs, 'insertions' are more frequent than 'deletions'.

⇒ It is likely that nodes that have 'too few' search key values (<⌈(n-1)/2⌉) will gain additional values 'relatively quickly'.

SQL92 Standard on Transactions

∙ The DBMS must ensure both 'serializability' (i.e., conflict- and view-) and freedom from 'cascading rollback'.

∙ A trans. begins 'implicitly', but are ended by one of the followings.

COMMIT: Commits the current trans. and begins a new one.

ROLLBACK: Causes the current trans. to abort.

⇒ 트랜잭션을 생성할 필요가 있는 경우, 트랜잭션의 끝에 COMMIT/ROLLBACK (error인 경우) 명시.

Ex) Pro*C/C++ in Oracle

char username[10]	= "tykim";

char password[10]	= "tykim";

char db_string[20]	= "comedudb";

EXEC SQL DECLARE db_name1 DATABASE;

EXEC SQL CONNECT :username IDENTIFIED BY :password

AT db_name1	USING :db_string;

EXEC SQL SET TRANSACTION READ ONLY;	// 접근모드(access mode)

EXEC SQL AT db_name1	SELECT * FROM … ;

… …

if (error)	EXEC SQL ROLLBACK;

EXEC SQL COMMIT;

∙The isolation-level and access-mode specified by SQL-92

Ex) SET TRANSACTION ISOLATION LEVEL SERIALIZABLE READ ONLY

⇒ Trans.이 DB를 수정할 수 없음.

⇒ INSERT, DELETE, UPDATE, CREATE는 수행 불가.

⇒ S-Lock만 얻을 수 있으므로 concurrency는 향상.

Ex) SET TRANSACTION ISOLATION LEVEL SERIALIZABLE READ WRITE

⇒ default

∙ 격리등급(Isolation level): 동시에 실행되고 있는 다른 트랜잭션들의 작업(operation)들에 대해 주어진 트랜잭션이 '노출되는 정도'를 제어.

⇒ 이 중 하나를 선택함으로써 사용자는 다른 트랜잭션들의 미완결 변경에 대해 현행 트랜잭션의 노출도를 높이는 대신 더 '높은 병행성'(higher concurrency)을 얻을 수 있음.

① SERIALIZABLE: The default

- 가장 보수적, Lower concurrency

- Rigorous 2PL 사용: 2PL + All locks must be held until a trans. commits.

⇒ Only 'committed' records to be read.

⇒ 이 mode로 설정한 트랜잭션 T는 완결된 trans.들이 만들어 놓은 변경만 판독하며, T가 판독하거나 기록한 값은 T가 종료된 후에야 다른 트랜잭션들이 변경할 수 있음.

- Further restriction: 또한, 어떤 탐색 조건에 따라 ‘값의 집합’을 판독한 경우, T가 완료될 때까지 이 ‘집합’을 다른 트랜잭션이 변경할 수 없음.

⇒ Phantom 현상이 일어나지 않음.

(Trans.이 tuple의 집단을 한번 읽고나서, 이 중에 어떠한 tuple도 스스로 수정하지 않았는데, 다시 한 번 읽을 때 결과가 달라지는 현상)

② REPEATABLE READ

- Only 'committed' records to be read: SERIALIZABLE과 같음.

- Further restriction on update: Between 'two reads' of a record by a trans., NO other trans. is allowed to 'update' the record.

⇒ SERIALIZABLE과는 달리 ‘개별적인’ tuple들만 locking하며 tuple들의 ‘집합’에 대해서는 locking하지 않음.

⇒ Phantom 현상이 가능.

Ex) T가 등급=1인 회원을 조사하고 있을 때, 다른 트랜잭션이 이에 해당하는 다른 회원을 '추가'할 수 있음.

③ READ COMMITTED

- Only committed records to be read.

- NO restriction on update: Between two reads of a record by a trans., other transactions may update the record.

④ READ UNCOMMITTED

- Allows even 'uncommitted' records to be read by other transactions.

⇒ The lowest level of consistency

- 이 mode의 트랜잭션은 access-mode를 READ ONLY로 하여야 함.

Ex) Statistics application where approximated values are sufficient.

회원들의 평균나이를 구하는 질의.

⇒ Long transactions whose results do not need to be 'precise'.

⇒ 회원 수가 많을 경우 몇 개의 값이 누락되거나 잘못되어도 큰 영향을 받지 않음.