Skip to content

3. Lock Layer Design

Jump to bottom
김영서 edited this page Oct 7, 2021 · 2 revisions

Concurrency Control의 필요성

데이터베이스는 다수의 사용자들이 동시에 접근하는 경우가 빈번하게 발생합니다. 다수의 사용자들이 동시에 데이터베이스를 사용하는 경우, 적절한 통제가 이루어지지 않는다면 데이터베이스의 무결성이 깨지고 의도하지 않은 결과를 반환할 수도 있습니다.

이러한 문제점을 해결하기 위해 DBMS는 병행 제어 기능을 통해 데이터베이스를 보호해야 합니다.


Concurrency Execution

Concurrency Execution은 동시에 여러 사용자의 트랜잭션을 수행하는 것입니다.

병행 수행을 통해 Throughput과 Latency가 좋아진다는 장점이 있지만, 병행 수행에서 발생할 수 있는 문제점을 통제하기 위한 과정이 까다롭다는 단점도 있습니다.

병행 수행이 어려운 이유는 아래와 같은 문제점이 발생할 수 있기 때문입니다.

  1. Lost Update (Write-Write Conflict)

    1

    대상이 되는 레코드에 동시에 접근하는 트랜잭션의 동작이 모두 Write인 경우 발생하는 문제입니다.

  2. Inconsistent Read (Read-Write Conflict)

    2

    하나의 레코드에 서로 다른 사용자가 각각 Read, Write를 하는 경우 발생하는 문제입니다.

  3. Dirty Read (Read-Write Conflict)

    3

    Abort 될 값을 읽는 경우 발생하는 문제입니다.


Concurrency Control

Concurrency Control이란 여러 명의 사용자가 동시에 데이터베이스를 사용하더라도, 마치 한 명의 사용자가 사용하는 것 처럼 데이터베이스의 상태를 Consistent 하게 유지하는 것을 말합니다. 따라서 병행 제어는 Isolation을 제공해야 합니다.

실제로 Serial Execution을 통해 매우 안전하게 Isolation을 제공할 수 있지만, 해당 방법은 매우 느리기 때문에 Interleave를 통해 Throughput과 Latency를 늘리는 방법을 사용하겠습니다.

본 프로젝트에서 병행 제어의 최종 목표는 CPU에 최대한 많은 트랜잭션을 올려 결과가 Serial하게 동작한 것의 결과와 동일하게 하는 것입니다.


PCC vs OCC

Pessimistic Concurrency Control

PCC는 Conflict가 발생할 것 같다는 것을 가정하여 선검사 후접근을 수행하는 병행 제어 방법입니다.

대표적으로 2PL, S2PL 기법이 있습니다.

Optimistic Concurrency Control

OCC는 Conflict가 발생하지 않을 것 같다는 것을 가정하여 선접근 후검사를 수행하는 방법입ㄴ니다.

대표적으로 BOCC, FOCC 기법이 있습니다.

For more details about OCC

PCC is used in this project

하나의 레코드에 접근이 많은 경우 PCC가 OCC 보다 유리하고, Uniform하게 레코드에 접근하는 경우 OCC가 PCC 보다 유리합니다. Hot Spot이 존재하면 그만큼 Conflict가 발생할 확률이 증가하기 때문입니다.

본 DBMS는 Dependency Graph를 통한 Deadlock Detection을 구현하기 위해 PCC 방법을 채택하겠습니다.


Strict Two-Phase Locking

본 프로젝트에서는 Conflict Serializability를 구현하기 위해 PCC의 일종인 S2PL 기법을 사용합니다.

Two-Phase Locking

4

5

2PL 기법은 아래와 같은 규칙을 따릅니다.

  1. 트랜잭션은 Read 전에는 S Lock을, Write 전에는 X Lock을 획득해야 한다.
  2. Lock을 한 번 Release 하기 시작한 이후부터는 Lock을 획득할 수 없다. (Conflict Serializability를 보장하기 위해)

위 방법은 먼저 Lock을 획득한 트랜잭션의 모든 Operation이 종료된 이후 Release를 수행하기 때문에, 만약 나와 Conflict 관계가 있는 트랜잭션이 존재하더라도 Conflict Serializability를 보장할 수 있습니다.

즉, 나와 Conflict관계에 있는 Operation은 나 이전에 이미 끝났거나 나 이후에 실행되는 것이 보장됩니다.

Cascading Aborts

6

하지만 2PL에는 Cascading Aborts라는 치명적인 문제점이 있습니다.

만약 트랜잭션이 Abort 된다면, Abort 된 값을 읽어 작업을 수행한 모든 트랜잭션들 역시 Abort 되어야 하는데, 이를 Cascading Aborts라고 합니다.

Strict Two-Phase Locking

7

이를 해결하기 위한 방법이 바로 S2PL입니다.

S2PL은 2PL의 Cascading Aborts를 해결하기 위해, 트랜잭션이 완전히 종료된 후 모든 Lock을 Release 합니다.

따라서 본 프로젝트에서는 S2PL 기법을 이용하여 병행 제어를 수행하겠습니다.


Deadlock

데드락은 서로가 서로를 기다리는 교착상태로써 더 이상 Progress를 만들 수 없는 상태를 의미합니다.

해결 방법으로는 Prevention/Aviodence와 Detection and Resolution이 있습니다.

1. Deadlock Avoidance

Deadlock Avoidence는 Wait를 Priority 기준으로 한 방향으로만 형성하여 Cycle을 방지하는 기법입니다.

안전한 Wait를 통해 No Deadlock을 보장하지만, 너무 선제적으로 Abort 한다는 단점이 있습니다.

2. Deadlock Detection

Wait-for Graph를 통해 주기적으로 그래프의 Cycle 유무를 확인하는 방법입니다. Cycle이 존재한다면 Log의 양이 제일 적은 것을 Abort 하는 방법을 사용합니다.

Detection은 Mutex로 Lock Table을 막아두고 Cycle을 확인해야 하기 때문에, 너무 자주 수행하면 병목 현상이 발생할 수 있습니다.


Lock Layout

1. Lock

struct lock_t {
	int trx_id;                 // Transaction id of lock object
	int lock_mode;              // 0(shared lock) or 1(exclusive lock)
	int is_waiting;             // 0(working lock) or 1(waiting lock)
	lock_table_entry* sentinel; // Points hash table entry which lock tries to acquire
	lock_t* prev;               // Previous lock of lock list 
	lock_t* next;               // Next lock of lock list
	lock_t* trx_prev;           // Previous lock of transaction list
	lock_t* trx_next;           // Next lock of transaction list
	pthread_cond_t cond;        // Condition variable
};

2. Lock Table Entry

struct lock_table_entry {
	int table_id; // Table id of hash table entry
	int64_t key;  // Key of hash table entry
	lock_t* head; // First lock which tries to acquire this entry
	lock_t* tail; // Last lock which tries to acquire this entry
};

Lock Mode

Shared Lock

특정 Opeartion이 Shared Lock Mode로 데이터를 점유하고 있는 경우, 다른 Shared Lock Mode Operation과 함께 데이터를 사용할 수 있습니다.

Exclusive Lock

특정 Opeartion이 Exclusive Lock Mode로 데이터를 점유하고 있는 경우, 본인을 제외한 어떠한 Opeartion도 데이터에 접근할 수 없습니다.


Lock Acquire

데이터베이스의 Isolation 보장과 데이터 간의 경합 제거를 위해, 모든 Operation은 수행 전에 접근해야하는 데이터의 Lock을 획득해야 합니다. 이를 Lock Acquire라고 합니다.

All possible cases

Lock을 얻기 위해 시도할 때에는 많은 선행 경우들이 존재합니다. 아래 그림은 발생할 수 있는 모든 상황을 트리구조로 도식화한 것이며, 총 16가지의 경우가 존재합니다.

아래에서 모든 경우에 대한 예시를 살펴보겠습니다.

1

1. Lock List에 트랜잭션이 없는 경우

2

  1. S Lock을 얻어야 하는 경우 → 바로 Lock을 획득합니다
  2. X Lock을 얻어야 하는 경우 → 바로 Lock을 획득합니다

2. Lock List에 트랜잭션이 존재하고, 자신의 트랜잭션이 있는 경우

2-1. 자신의 트랜잭션이 S Working Lock Object를 갖고 있는 경우

  1. S Lock을 얻으려고 하는 경우 → 바로 Lock을 획득합니다

    3

  2. X Lock을 얻으려고 하는 경우

    1. Lock List의 Working Lock이 자신의 트랜잭션 혼자인 경우 → X Mode Upgrade 후, 바로 Lock을 획득합니다

      4

      5

    2. Lock List의 Working Lock이 자신의 트랜색션과 다른 트랜잭션과 함께 존재하는 경우

      1. Waiting Lock Object가 있는 경우 → Deadlock

      2. Waiting Lock Object가 없는 경우 → 트랜잭션은 데드락이 없다면 대기상태로 전환되고, 있다면 중단됩니다

        6

2-2. 자신의 트랜잭션이 X Working Lock Object를 갖고 있는 경우

7

  1. X Lock을 얻으려고 하는 경우 → 바로 Lock을 획득합니다
  2. S Lock을 얻으려고 하는 경우 → 바로 Lock을 획득합니다

2-3. 자신의 트랜잭션이 Waiting Lock Object를 갖고 있는 경우

8

현재 상황은 일어날 수 없는 경우입니다.

TRX2는 Lock을 잡기 위해 Waiting 상태에 진입하였기 때문에, 더이상 Progress를 만들어 낼 수 없습니다. 따라서 위 그림과 같이 TRX2가 새로운 요청을 하는 일은 일어날 수 없습니다.

3. Lock List에 트랜잭션이 존재하지만, 자신의 트랜잭션이 없는 경우

3-1. Lock List의 Tail이 S Working Lock Object인 경우

  1. S Lock을 얻어야 하는 경우 → 바로 Lock을 획득합니다

    9

  2. X Lock을 얻어야 하는 경우 → 트랜잭션은 데드락이 없다면 대기상태로 전환되고, 있다면 중단됩니다

    10

3-2. Lock List의 Tail이 X Working Lock Object인 경우

11

  1. S Lock을 얻어야 하는 경우 → 트랜잭션은 데드락이 없다면 대기상태로 전환되고, 있다면 중단됩니다
  2. X Lock을 얻어야 하는 경우 → 트랜잭션은 데드락이 없다면 대기상태로 전환되고, 있다면 중단됩니다

3-3. Lock List의 Tail이 S Waiting Lock Object인 경우

12

  1. S Lock을 얻어야 하는 경우 → 트랜잭션은 데드락이 없다면 대기상태로 전환되고, 있다면 중단됩니다
  2. X Lock을 얻어야 하는 경우 → 트랜잭션은 데드락이 없다면 대기상태로 전환되고, 있다면 중단됩니다

3-4. Lock List의 Tail이 X Waiting Lock Object인 경우

13

  1. S Lock을 얻어야 하는 경우 → 트랜잭션은 데드락이 없다면 대기상태로 전환되고, 있다면 중단됩니다
  2. X Lock을 얻어야 하는 경우 → 트랜잭션은 데드락이 없다면 대기상태로 전환되고, 있다면 중단됩니다

Lock Release

Lock Release는 S2PL 정책에 따라 수행됩니다.

Release 요청이 들어온 Lock Object를 Lock List에서 제거하고, 대기하고 있는 Lock Object에게 알맞게 Signal을 보내 대기 중인 다른 Transcation이 일을 할 수 있게 합니다.

아래는 상황 따른 Signal 전송 방법 중 주요 상황에 대한 그림입니다.

1. Lock List에 자신의 Lock Object 밖에 없는 경우

14

2. 자신의 Lock Object 외에 다른 Working Lock Object가 존재하는 경우

15

3. 자신의 Lock Object 다음의 Lock Object들이 S Waiting Lock인 경우

16

4. 자신의 Lock Object 다음의 Lock Object가 X Waiting Lock인 경우

17

5. 자신이 Abort되어야 하고 Waiting Lock Object인 경우 (자신의 앞은 S Working Lock, 뒤는 S Waiting Lock인 경우)

18

6. S Lock을 보유한 트랜잭션이 X Lock을 얻기위해 대기하는 경우

19

위 그림은 TRX1은 S Lock을 획득한 상태지만, TRX2 때문에 X Lock을 바로 얻지 못하고 TRX2의 종료를 대기하고 있는 상태입니다.

이 경우 TRX2는 자신이 Lock을 Release하는 경우 fig 3가 될 수 있도록 TRX1에게 Signal을 보내줘야 합니다.

Clone this wiki locally