[Database] Concurrency Control

Concurrency control

 

Concurrency control의 목표는 DBMS가 Serializable하고 Recoverable하며 가급적이면 Cascadeless인 스케줄을 생성하도록 스케줄링 결정을 내리는 것입니다.

2025.05.25 - [[학교 수업]/[학교 수업] Database] - [Database] Transaction

[Database] Transaction

 

DBMS Scheduler는 높은 수준의 concurrency level을 제공해야 합니다. 한 번에 하나의 Transaction만 실행되도록 하는 정책은 serializable한 schedule을 생성하지만 concurrency level이 낮습니다. 다양한 concurrency control schemes들은 가능한 concurrency amount와 overhead사이에서 절충하는 방법을 사용합니다.

 

Weak levels on consistency

 

OLAP(On Line Analytic Processing)는 성능을 위해 non serializable한 schedule을 허용하는 weak level consistency를 허용합니다. 즉 workload의 종류에 따라 요구되는 consistency의 수준이 달라질 수 있습니다:

• On Line Transaction Processing(OLTP)는 현실 세계 기업의 정확한 모델인 데이터베이스를 유지합니다. 짧고 단순한 transaction들을 처리하며 데이터베이스의 작은 부분만을 접근합니다.
• On Line Analytic Processing(OLAP)는 데이터베이스를 사용하여 전략적 의사결정을 안내합니다. 복잡한 쿼리를 처리하며 데이터베이스의 많은 부분을 접근합니다. 이때 데이터는 항상 최신일 필요는 없습니다(예: 은행 CEO가 모든 고객 계좌의 대략적인 총 잔액을 얻는 경우). 즉 OLAP는 OLTP Transaction과 달리 serializable할 필요는 없습니다. *아마도 read-intensity workload?

 

Phenomena caused by Concurrent Transactions

 

동시에 Transaction들을 실행하면 발생할 수 있는 네 가지 현상이 있습니다:

• Dirty read: 완료되지 않은(uncommited) concurrent transaction이 작성한 데이터를 다른 transaction이 읽는 현상입니다.
• Nonrepeatable read: 한 transaction이 같은 쿼리를 두 번 실행했을 때 다른 transaction에 의해 데이터가 수정된 것을 발견하는 현상입니다.
• Phantom Read: 한 transaction이 같은 쿼리를 두 번 실행했을 때 최근 완료된 다른 transaction으로 인해 결과 집합에 새 record가 추가된 것을 발견하는 현상입니다.
• Serialization Anomaly: Transaction group을 성공적으로 commit한 결과가 해당 transactions들을 하나씩 실행하는 가능한 모든 순서와 일관되지 않는 현상입니다. 즉, 가능한 모든 serialize schedule의 결과에 해당하지 않는 결과가 commit된 경우를 말합니다.

 

Phentom Phenomenon

 

Phentom Read의 예시입니다:

ex

 

Transaction Isolation in SQL-92

 

SQL-92의 transaction isolation 수준을 정의합니다:

• Serializable: 가장 기본적인 isolation 수준입니다. serialized 실행 결과와 동일한 결과를 보장하며, Dirty read, Nonreapteable read, Phantom read, Serializable anomaly 모두 발생하지 않습니다.
• Repeatable read: commit된 record만 읽습니다. 같은 record를 반복해서 읽어도 동일한 값을 반환합니다. 그러나 transaction은 serializable하지 않을 수 있으며, 다른 transaction이 삽입한 일부 record는 찾지 못할 수 있습니다.
• Read Commited: commit된 record만을 읽으며, record를 연속해서 읽으면 다른(하지만 commit된) record값이 반환될 수 있습니다. Dirty read는 불가능하지만, 나머지 현상들은 발생할 수 있습니다.
• Read uncommited: commit되지 않은 record들을 읽을 수 있습니다.

Transaction Isolation in SQL-92

 

Transaction Definition in SQL

 

SQL에서 Transaction은 implicit하게 실행되며 다음을 통해 종료됩니다:

• Commit work: 현재 transaction을 commit하고 새로운 transaction을 시작합니다.
• Rollback work: 현재 transaction을 abort합니다.

거의 모든 데이터베이스 시스템에서는 기본적으로 모든 SQL문이 성공적으로 실행되면 implicit하게 commit됩니다. 이 implicit commit은 데이터베이스 지시문을 통해 끌 수도 있습니다. *(in JDBC) -- connection.setAutoCommit(false);

 

isolation level은 데이터베이스에서 설정하거나, transaction시작 시 변경할 수 있습니다. *(In SQL) set transaction isolation level serializable // (in JDBC) -- connection.setTransactionIsolation(Connection.TRANSACTION_SERIALIZABLE)

 

Implementation of Isolation Levels

 

isolation level은 다음 기법들을 이용해서 구현됩니다:

• Locking: 데이터베이스 전체에 대한 잠금 vs. 개별 항목에 대한 잠금(Lock on whole database vs lock on items), 얼마나 locking을 유지해야하며, shared vs. exclusive lock중 어떤걸 선택해야하는지에 대한 고려가 필요합니다.
• Timestamp: transaction 시작 시 timestamp를 할당하고, 데이터 항목은 write timestamp와 read timestamp를 저장합니다. timestamp는 순서에 어긋나는 접근을 감지하는 데 사용됩니다.
• Multiple versions of each data item: transaction이 데이터베이스의 version을 읽을 수 있도록 허용합니다(@homework4)

 

Lock-Based Protocols

 

locking은 data item에 대한 동시 접근을 제어하는 매커니즘입니다. data item은 두 가지 모드로 lock을 걸 수 있습니다:

• exclusive (X) mode: data item을 읽거나 쓸 수 있습니다. X-lock은 lock-X instruction을 사용하여 요청됩니다.
• shated (S) mode: data itme을 읽을 수만 있습니다. S-lock을 lock-S instruction을 사용하여 요청됩니다.

lock request는 concurrency-control manager에게 전달되며, transaction은 요청이 승인된 후에만 진행할 수 있습니다. transaction이 item에 대한 잠금을 요청할 때, 해당 lcok이 다른 transaction이 이미 보유하고 있는 lock과 호환되는 경우에만 승인될 수 있고 이를 나타내는 행렬이 Lock-compatibility matrix입니다:

Lock-compatibility matrix

 

(1) 어떤 transaction이든 item에 대해 shared lock은 보유할 수 있습니다.

(2) 그러나 어떤 transaction이 item에 대해 exclusive lock을 보유하고 있다면, 다른 어떤 transaction도 해당 item에 대해 어떤 lock도 보유할 수 없습니다.

 

locking의 예시입니다:

ex

 

위 예시는 item수준의 lock을 이용했지만 serializablility는 보장하지 않습니다. 만약 예를 들어 unlock(A)와 lock-S(B) 사이에 T3가 lock-X(B); write(B); unlock(B) 를 수행했다면 직렬성이 보장되지 않습니다. 이는 item 수준에서의 locking은 serializability를 보장하기에는 부족함을 보여줍니다.

 

Schedule with lock grants

 

다음의 예시는 non-serializable shedule입니다:

ex

 

즉 item 수준의 lock만으로는 serializability를 보장할 수 없고, 더 체계적인 locking protocol이 필요합니다.

 

Deadlock

 

deadlock은 transaction 집합이 존재하며, 집합 내의 모든 transaction들이 다른 transaction들을 기다리는 상황입니다. 이는 deadlock의 예시입니다:

ex

 

T3는 A에 대한 lock을 얻기 위해, T4는 B에 대한 lock을 얻기 위해 서로 대기중인 상황입니다. 이러한 상황을 deadlock이라고 하며, deadlock을 해결하기 위해 T3 또는 T4 중 하나가 rollback되어 lock을 해제해야합니다.

 

대부분의 locking protocol은 deadlokc의 가능성이 있습니다. 또한 concurrency control manager가 제대로 설계되어있지 않으면 Stravation도 발생할 수 있습니다. 예를 들어 (1) transaction이 한 item에 대한 X-lock을 기다리는 동안, 일련의 다른 transaction이 동일한 item에 대한 S-lock을 요청하고 승인받는 경우(X-lock을 기다리는 transaction이 starvation에 빠짐), (2) 같은 transaction이 deadlock의 해결을 위해 반복적으로 rollback되는 경우가 있습니다.

 

그래서 concurrency control manager는 starvation을 방지하기 위해 디자인되어야합니다.

 

The Two Phase Locking protocol

 

2PL protocol은 conflic serializable schedule을 보장하는 방법입니다. 이는 두 단계로 나뉩니다:

• Phase 1: Growing Phase - transaction은 lock을 획득할 수 있으며, lock을 해제할 수는 없습니다.
• Phase 2: Shrinking Phase - transaction은 lock을 해제할 수 있으며, lock을 획득할 수는 없습니다.

2PL

 

이 프로토콜은 serializability를 보장합니다. 하지만 2PL은 conflict serializable schedule을 위한 필요조건은 아닙니다. transaction은 lock point(transaction이 최종 잠금을 얻는 시점) 순서로 serializable할 수 있음이 증명되었습니다.

 

기본적인 2PL protocol에서 recoverability와 freedom from cascading roll-back을 보장하기 위해서는 확장기능이 필요합니다:

• Strict two-phase locking: Transaction은 모든 exclusive lock을 commit/abort까지 보유해야합니다.
• Rigorous two-phase locking: Transaction은 모든 lock을 commit/abort까지 보유해야합니다.

transaction들은 commit되는 순서로 serializable될 수 있습니다. 또한 recoverability와 freedom from cascading roll-back을 보장합니다. 대부분의 DB는 S2PL을 구현합니다. 하지만 2PL은 deadlock으로부터의 자유는 보장하지 않습니다.

 

Lock Conversion

 

lock conversion이 포함되는 2PL도 있습니다:

• Growing phase: item에 대한 S-lock을 획득하거나, X-lock을 획득하거나, S-lock을 X-lock으로 upgrade할 수 있습니다.
• Shrinking phase: item에 대한 S-lock을 해제하거나, X-lock을 해제하거나, X-lock을 S-lock으로 downgrade할 수 있습니다.

이 프로토콜 또한 serializability를 보장합니다. *recoverability나 non-cascasding roll-back은 아닐듯

 

Automatic Acquisition of Locks

 

Transaction Ti는 명시적인 lock request없이 표준 read/write instruction을 실행할 수 있습니다. read(D) instruction은 다음과 같습니다:

Automatic Acquisition of Locks

 

write(D) instruction은 다음과 같습니다:

Automatic Acquisition of Locks

 

이 두 instruction에서의 모든 lock은 commit/abort이후에 해제됩니다. *아마도 serializability 뿐만 아니라 recoverability, freedom of cascading rollback도 보장하지 않을까?

 

Implementation of Locking

 

lock manager는 별도의 프로세스로 구현될 수 있으며, transaction은 manager에게 lock/unlock request를 보냅니다. lock manager는 lock grant message나, 만약 deadlock이 발생한 경우 transaction에게 rollback하라는 message를 보냅니다. lock manager는 승인된 lock과 대기 중인 request를 기록하기 위해 lock table이라는 in-memory 구조를 유지합니다:

Lock table

 

새로운 요청은 데이터 항목에 대한 요청 대기열의 끝에 추가되며, 이전 잠금들과 호환되는 경우(with lock compatibility matrix)에만 승인됩니다. transaction이 abort되면 해당 transaction의 대기 중이거나 승인된 모든 요청이 삭제됩니다.

 

Graph-Based Protocols

 

그래프 기반 protocol은 2PL에 대한 대안입니다. 모든 data item 집합 D = {d1, d2, ..., dh}에 대해 partial ordering을 부여합니다. 만약 di -> dj라면 di와 dj에 접근하는 모든 transaction은 반드시 dj를 접근하기 전에 di를 접근해야 합니다.

 

이는 집합 D가 database graph라는 DAG(directed acyclic graph)로 나타낼 수 있음을 의미합니다. 이 중 tree protocol은 간단한 종류의 graph protocol입니다.

 

Tree protocol

 

tree protocol의 규칙은 다음과 같습니다:

• exclusive lock만 허용합니다.
• Ti의 첫 번째 잠금은 어떤 데이터 항목에 대해서든 가능합니다. 즉, 잠금을 시작하는 item은 어떤 것이든 상관없습니다.
• 이후, Ti가 데이터 항목 Q를 잠글 수 있는 경우는 Q의 부모가 현재 Ti에 의해 잠겨있는 경우 뿐입니다. 즉, tree의 ordering에 따라 lock을 진행해야합니다.
• 데이터 항목은 언제든지 해제될 수 있습니다.
• Ti에 의해 잠겼다가 해제된 데이터 항목은 그 후 Ti에 의해 다시 잠글 수 없습니다.

 

Tree protocol은 conflict serializability와 deadlock으로부터 자유롭습니다. 또한 unlook이 2PL보다 더 빠를 수 있습니다. *규칙 4번. 이는 대기시간을 단축하고 동시성을 높일 수 있습니다. 이 프로토콜을 deadlock이 없으므로 rollback이 필요하지 않습니다.

 

하지만, tree protocol은 recoverability와 cascade freedom을 보장하지 않습니다. recoverability를 보장하기 위해서는 commit dependency를 추가해야합니다. 부모의 lock을 잡아야 자식의 lock을 잡을 수 있기 때문에 transaction이 직접 접근하지 않는 item에 대해서도 lock을 해야할 수 있습니다. 이는 locking overhead를 증가시키며 추가 대기 시간을 발생시키며 잠재적으로 동시성을 감소시킬 수도 있습니다.