CS 스터디 1주차 정리

학습 주제

1. Disk Space Management
2. Buffer Management
3. 트랜잭션, 트랜잭션 격리 레벨, 2 Phase Lock

디스크 관리(Disk Space Management)

Physical formatting(Low-level formatting)

포맷팅(formatting) : 디스크를 처음 만들게 되면 디스크를 디스크 컨트롤러가 읽고 쓸 수 있도록 디스크를 섹터단위로 나눠놓는데 이런 과정을 포맷팅이라고 하고 Physical formatting 이라고 부른다.

예전에는 포맷을 하게 되면(지금은 하드디스크를 구매하면 Physical formatting이 되서 나옴) 디스크를 Sector(섹터)단위로 나누는 과정이 필요하였다. 단, 용량이 클수록 Physical formatting 과정이 오래걸린다.

섹터는 앞뒤로 헤더(header)와 트레일러(trailer)가 각각 붙는다 즉, 섹터는 header + 실제 데이터(512byte) + trailer로 구성된다.

파티셔닝(Partitioning)

파티셔닝 : Physical formatting이 끝난 다음에 섹터 영역들을 묶어서 하나의 독립적인 디스크로 만드는 과정을 파티셔닝이라고 한다.

예를들어 C드라이브와 D드라이브로 파티션을 나누면 C와 D드라이브는 서로 다른 논리적인 디스크가 되는것이다. OS는 하드디스크가 1개만 있음에도 불구하고 파티셔닝된 논리적인 디스크를 바라보고 접근한다.

Logical formatting

Logical formatting : 파티셔닝이 끝난 각각의 파티션은 가상메모리를 위한 Swap Area 용도와 파일 시스템 용도로 사용할 수 있지만, 파일 시스템 용도로 사용하기 위해 파일 시스템을 설치하면 Logical formatting 이라고 부른다.

디스크 스케줄링(Disk Scheduling)

디스크를 접근하는 시간은 크게 3가지로 구분된다.

1. Seek time
   디스크 헤드(그림에서 read-write head)가 찾고자 하는 데이터가 있는 실린더로 움직이는데 걸리는 시간을 의미한다.

   Seek time이 I/O작업에서 가장 많은 시간소요가 발생한다.

2. Rotational latency
   디스크 헤드가 실린더로 이동하고 난 후에 찾고자 하는 섹터(Sector)위치가 디스크 헤더로 가는데 걸리는 시간을 의미한다.

3. Transfer time
   디스크 헤드가 섹터에서 데이터를 읽고 쓰고 하는 시간을 의미한다.

   Transfer time은 굉장히 빠르다.

결국, I/O 작업이 느린 이유는 Seek time 때문에 느린것이다. 즉, 헤더가 실린더로 한번만 이동해서 많은양의 데이터를 읽을 수만 있다면 I/O 시간을 단축할 수 있다. 이를 위해 적절한 디스크 스케줄링 알고리즘을 적용해야 한다.

디스크 스케줄링 알고리즘(Disk Scheduling Algorithm)

실린더 번호가 들어온 순서(Queue) : 98, 183, 37, 122, 14, 124, 65, 67

1. FCFS(First Come First Service)
   단순히 들어온 순서대로 처리해주는 방법, 굉장히 비효율적인 방법이다.

2. SSTF(Shortest Seek Time First)
   큐에 들어와 있는 요청중에서 디스크 헤드에서 제일 가까운 요청을 먼저 처리하는 방법이다.
   단, 기아(Starvation) 문제가 발생할 수 있다.(먼 거리에 있는 요청이 평생 처리되지 않을 수 있다.)

3. SCAN(==엘리베이터 스케줄링)
   큐에 어떤 요청이 들어왔는지 상관없이 디스크 헤드는 가장 안쪽에서 바깥쪽으로 이동하면서 가는 도중 요청이 있으면 처리하고 지나가는 방식이다. 엘레베이터가 동작하는 것과 비슷하기 때문에 엘리베이터 스케줄링이라고도 부른다.
   단, 대기시간의 편차가 생기는 문제점이 있다.
   
   다음 그림이 있을 때 가운데 부분은 최악의 경우 반바퀴만 돌면 처리가 되지만 양 끝에 있는 부분은 최악의 경우 왕복까지 기다려야 한다.

4. C-SCAN
   SCAN의 대기시간 편차 문제를 해결한 알고리즘, 디스크 헤드가 안쪽에서 바깥쪽으로 이동할때는 요청을 처리하지 않고 되돌아 올때는 요청을 처리하는 방법이다.

5. N-SCAN
   디스크 헤드가 이동할 때 이미 큐에 들어와 있던 요청은 지나가면서 처리하고 디스크 헤드가 움직이는 동안 들어온 요청들은 당장 처리하지 않다가 다시 되돌아올때 처리하는 방법이다.

6. LOOK and C-LOOK
   SCAN방식의 비효율적인 측면을 개선한 알고리즘이다. 사실 끝쪽에 요청이 없으면 더이상 갈 필요가 없는데 결국 LOOK과 C-LOOK은 어떤 방향으로 요청을 처리하면서 지나가다가 그쪽 방향에 더 이상 요청이 없으면 거기서부터 방향을 바꾸는 방법이다.
   LOOK은 SCAN을 사용, C-LOOK은 C-SCAN을 사용한다.

버퍼 관리(Buffer Management)

버퍼 관리자

DBMS는 데이터를 디스크에 저장하고 일부분을 메인메모리에 유지하는데 메인 메모리에 유지하는 데이터를 관리하는 모듈을 버퍼 관리자라고 부른다.

DBMS는 크게 질의 처리기(Query Processor)와 저장 시스템(Storage System)으로 나눠볼 수 있다. 메인 메모리에 올리는 데이터를 저장 시스템안에 있는 페이지 버퍼에 저장하게 되는데 이 페이지 버퍼를 관리하는게 버퍼 관리자이고, 페이지 버퍼를 어떻게 관리하느냐에 따라서(버퍼 관리 정책에 따라서) UNDO 복구와 REDO 복구의 과정이 달라지게 된다.

UNDO

트랜잭션이 수행되다가 어떤 문제가 발생해서 Rollback 작업이 필요할 때 트랜잭션을 실행하기 전 상태로 복구하는 과정이 UNDO이다.

UNDO는 어떤 STEAL 정책을 사용하는지에 따라서 과정이 달라지게 된다.

STEAL 정책

STEAL : 수정된 데이터를 언제든지 디스크에 쓸 수 있는 정책을 말한다. 즉, 트랜잭션이 수행되다가 수정된 내용들을 트랜잭션이 종료되지도 않았는데 페이지 버퍼의 공간 부족 등의 이유로 메인메모리에 올라와 있던 데이터를 디스크에 써야할 수도 있는데 이것이 가능하면 STEAL 정책이라고 한다.

NO STEAL : 수정된 데이터들을 최소한 트랜잭션 종료 시점까지는 페이지 버퍼에 그 내용을 유지하는 정책을 의미힌다. 결국 트랜잭션이 종료되지 않으면 디스크에 쓸 수 없는 정책이며, 트랜잭션이 길어지면 저장해야 하는 데이터의 양이 많아지고, 그만큼 메인 메모리를 많이 사용하게 되기 때문에 사용하지 않는다.

즉, 거의 모든 DBMS가 채택하는 버퍼 관리 정책은 STEAL이다.

REDO

REDO는 이미 커밋한 트랜잭션의 수정을 재반영하는 복구 작업을 말한다. Commit이 이루어진다고 해서 실제 디스크에 반영되지 않았을 수 있기 때문에 이를 디스크에 확실하게 반영하는 작업을 REDO라고 생각하면 된다.

FORCE 정책

FORCE : 수정했던 모든 페이지를 트랜잭션 커밋 시점에 디스크에 반영하는 정책을 의미한다. 여기서는 Commit이 수행완료가 되면 반드시 디스크에 변경사항이 반영되는것을 보장하는 정책이기 때문에 REDO연산이 필요하지 않게 된다.

NO FORCE : 수정했던 페이지를 트랜잭션 커밋 시점에 디스크에 반영하지 않는 정책을 의미한다. 정확하게는 무조건 반영하지 않는다기 보다는 반영되지 않을 수도 있다. NO FORCE 정책에서는 디스크에 변경사항을 즉시 반영하지 않을 순 있지만 변경사항을 기록한 로그는 반드시 기록하게 된다.

즉, 거의 모든 DBMS는 NO FORCE 정책을 채택한다.

트랜잭션

트랜잭션이란?

데이터베이스의 상태를 변화시키는 하나의 논리적인 단위를 의미한다. 하나의 트랜잭션 안에는 여러개의 연산들이 존재할 수 있다.

예를들어, A계좌에서 B계좌로 일정 금액을 이체한다고 가정한다면
1. A계좌 잔액확인(SELECT)
2. A계좌에서 B계좌로 이체할 금액을 뺀다(UPDATE)
3. B계좌 잔액확인(SELECT)
4. B계좌로 이체할 금액을 더한다(UPDATE)
다음과 같은 4가지의 연산들이 합쳐져서 하나의 논리적인 작업을 수행하는 트랜잭션을 구성한다.

만약에 계좌이체를 하다가 전체작업이 정상적으로 완료되면 해당 내용을 Commit을 통해 디스크에 반영해야하고, 무언가의 오류로 인해 일부분만 적용되는 등 정상적으로 처리할 수 없는 경우에는 Rollback을 통해 트랜잭션을 수행하기 전 상태로 되돌려야 한다.

트랜잭션의 성질(ACID)

• Atomicity(원자성) : "all or nothing"특성으로 설명된다. 전체가 다 수행되거나, 그게 아니라면 아무것도 수행되지 않아야 한다는 성질이다. 즉, 트랜잭션은 여러 연산들의 집합으로 구성되어 있는데 각각의 연산을 차례로 수행할 때 디스크에는 실제로 값이 반영될 수도 있다. 하지만, 이 상태에서 트랜잭션이 중지가 되면 디스크에는 일부분만 반영되어 있는 결과가 나타나기 때문에 중간 상태를 데이터베이스에 반영해서는 안된다.

• Consistency(일관성) : 트랜잭션의 수행이 데이터베이스의 일관성을 보존해야 한다는 성질이다. 즉, 트랜잭션이 완료 후에도 데이터베이스가 일관된 상태로 유지되어야 한다. 트랜잭션 수행 전후의 데이터베이스의 상태는 각각 일관성이 보장되는 서로 다른 상태가 된다.

트랜잭션 수행이 보존해야 할 일관성은
1. 기본키, 외래 키 제약과 같은 명시적인 무결성 제약 조건
2. 자금 이체 예에서 두 계좌 잔고의 합은 이체 전후가 같아야 한다는 사항 같은 비명시적인 일관성 조건들

• Isolation(독립성) : 각각의 트랜잭션들은 서로 다른 트랜잭션의 영향을 받아서는 안되는 성질이다. 즉, 여러 트랜잭션이 동시에 수행되더라도 각각의 트랜잭션은 다른 트랜잭션의 수행에 영향을 받지 않고 독립적으로 수행되어야 한다. 독립성을 위해 트랜잭션의 격리 수준을 두고 있다.

• Durability(지속성) : 트랜잭션이 완료되어 커밋되고 나면, 해당 트랜잭션에 의한 변경사항은 무슨일이 있어도 데이터베이스에 영구적으로 저장되어야 한다는 성질이다.

트랜잭션의 격리 수준

트랜잭션 격리수준(isolation level)은 동시에 여러 트랜잭션이 수행될 때, 트랜잭션끼리 얼마나 서로 고립되어 있는지를 나타내는 것이다.

트랜잭션 격리수준은 크게 4가지로 나뉜다.
1. READ UNCOMMITED
2. READ COMMITED
3. REPEATABLE READ
4. SERIALIZABLE
아래로 내려갈수록 트랜잭션간 고립수준이 높이지며, 성능이 떨어지는 것이 일반적이다.
(MYSQL의 기본 격리수준은 REPEATABLE READ이다.)

• READ UNCOMMITED : 다른 트랜잭션에서 커밋되지 않은 내용을 참조할 수 있다.

단, 더티 리드(Dirty Read)가 발생할 수 있다.
1. A 트랜잭션에서 10번 사원의 나이를 27살에서 28살로 바꿈
2. 아직 커밋하지 않음
3. B 트랜잭션에서 10번 사원의 나이를 조회함
4. 28살이 조회됨

A트랜잭션에서 변경한 내용을 커밋, 롤백과 무관하게 다른 트랜잭션(B)에서 확인할 수 있는 격리수준을 의미하며, 이 상황을 더티 리드(Dirty Read)라고 한다.

즉, 더티 리드가 발생하기 때문에 잘 사용하지 않는 가장 낮은 격리수준이다.

• READ COMMITED : 다른 트랜잭션에서 커밋된 내용만 참조할 수 있다.(오라클에서 기본으로 사용하는 격리수준이다.) UNDO영역에 백업된 레코드에서 값을 가져오기 때문에 커밋된 내용만 참조할 수 있는것이다.

단, NON REPETABLE READ 부정합 문제가 발생할 수 있다.
1. B트랜잭션에서 10번 사원의 나이를 조회
2. 27살이 조회됨
3. A 트랜잭션에서 10번 사원의 나이를 27살에서 28살로 바꾸고 커밋
4. B 트랜잭션에서 10번 사원의 나이를 다시 조회
5. 28살이 조회됨

B트랜잭션에서 처음 SELECT한 결과로 27살이 조회되면 그 이후에도 동일하게 27살이 조회가 되어야 하는데 그 사이에 A트랜잭션에서 해당 데이터를 수정하고 커밋해서 다른 결과가 나오게 되면 NON REPETABLE READ 부정합 문제가 발생했다고 한다.

• REPETABLE READ : 해당 트랜잭션이 수행되기 전에 커밋된 내용만 참조할 수 있다.(MYSQL에서 기본으로 사용하는 격리수준이다.)

1. A 트랜잭션이 10번 사원의 나이를 조회
2. 27살이 조회됨
3. B 트랜잭션이 10번 사원의 나이를 28로 변경하고 커밋
4. A 트랜잭션이 10번 사원의 나이를 다시 조회
5. 27살이 그대로 조회됨
   즉, NON REPETABLE READ 부정합 문제가 해결된다. 이것이 가능한 이유는 자신의 트랜잭션 번호보다 낮은 트랜잭션 번호에서 변경된(커밋된) 내용만 보게 되는 것이다.
   (모든 InnoDB의 트랜잭션은 순차적으로 증가하는 고유한 트랜잭션 번호를 가지고 있다.)

단, Phantom Read 현상이 발생할 수 있다.(InnoDB 스토리지 엔진은 넥스트 키 락을 이용해서 Phantom Read 문제를 해결한다)
Phantom Read는 다른 트랜잭션에서 수행한 변경 작업에 의해 레코드가 보였다가 안보였다가 하는 현상을 말한다.
--> (추가 조사 필요)

• SERIALIZABLE : 트랜잭션이 수행될 때 접근하는 데이터에 락을 걸어서 다른 트랜잭션에서 해당 데이터에 접근하지 못하도록 한다. 즉, 한번에 하나의 트랜잭션만 수행되어 상당히 성능이 떨어지는 격리수준이다.

로킹(Locking)

로킹은 하나의 트랜잭션이 실행하는 동안 특정 데이터 항목에 대해서 다른 트랜잭션이 동시에 접근하지 못하도록 상호배제(Mutual Exclusive) 기능을 제공하는 기법이다. 하나의 트랜잭션이 데이터 항목에 대해서 잠금(lock)을 설정하면, 잠금을 설정한 트랜잭션이 해제(unlock)할 때 까지 데이터를 독점적으로 사용할 수 있다.

잠금에 사용되는 연산은 lock연산과 unlock연산을 사용한다.

S-lock(공유잠금), X-lock(배타잠금)

S-lock : 어떤 데이터에 읽기연산을 수행할 때 사용하는 연산이다. 하나의 데이터 항목에 여러 개의 S-lock이 가능하며, 읽기연산만 가능하다.

X-lock : 어떤 데이터 항목에 대해서 읽기 연산과 쓰기 연산 모두 가능하고, 하나의 데이터 항목에 대해서는 하나의 X-lock만 가능하다.

트랜잭션이 read(x) 연산을 실행하기 전에 S-lock(x)이나 X-lock(x)을 실행해야 하며, 연산 종료 후에는 unlock(x) 연산을 실행해야 한다.

2단계 잠금 규약(2Phase Lock, 2PL)

단순 잠금 연산만으로는 병렬적으로 동작하는 트랜잭션이 순차적으로 실행되는 것과 같은 직렬 가능한 스케줄을 보장하지 못하기 때문에 2PL을 사용한다.
또 단순 잠금 연산으로는 교착상태(Dead lock)이 발생할 수 있다.

2PL은 잠금을 설정하는 단계와 해제하는 단계로 나누어 수행한다.

• 확장단계(growing phase) : 트랜잭션이 lock 연산만 수행할 수 있고 unlock연산은 수행할 수 없는 단계
• 축소단계(shrinking phase) : 트랜잭션이 unlock 연산만 수행할 수 있고 lock연산은 수행할 수 없는 단계

하지만, 2PL도 여전히 교착상태가 발생할 수 있고, 연쇄 복귀 문제도 발생할 수 있다.

엄격한 2단계 잠금 규약(strict 2PL)

모든 X-lock에 대한 unlock 연산을 트랜잭션이 완전히 완료된 후에 실행하는 것이다.

strict 2PL을 통해 교착상태와 연쇄 복귀 문제도 해결할 수 있으며, 현재 대부분의 DBMS에서 엄격한 2PL 규약을 사용한다.