04. 데이터베이스 - Disk Space Management

다양한 저장장치

간단하게 저장장치들을 살펴보는데, 중요한 것은 각 저장장치의 속도 차이입니다. 

Register

L1 Cache

L2 Cache

RAM

SSD

Disk

위와 같은 저장장치들이 있는데, 위로 갈수록 빠르고 가격이 높아집니다. 따라서 낮은 가격으로 큰 용량을 사용할 수 있는 디스크가 데이터베이스에서 많이 사용됩니다. 

Disk

왼쪽 사진에 원판 하나를 Platter라고 하고, 이 Platter들은 빠르게 회전할 수 있습니다. 

 

왼쪽부분에 헤드는 앞뒤로(트랙과 수직하게) 움직일 수 있고, 따라서 특정 트랙에 위치할 수 있습니다. 

그리고 헤더가 위치한 트랙들을 '실린더' 라고 합니다.

 

한번에 하나의 헤드만이 디스크에 읽거나 쓸 수 있습니다. 

 

 

플래터는 여러 Sector로 나뉘는데, Page의 사이즈는 섹터 사이즈의 배수여야 합니다.

 

디스크에서 특정 블록에 접근할 때 다음과 같은 시간이 걸립니다.

1. Seek time : 디스크의 head가 접근할 track에 위치하도록 움직이는데 걸리는 시간

2. Rotational delay : 원하는 블록이 헤드의 아래에 오도록 플래터를 돌리는 시간

3. Transfer time : 실제로 디스크의 표면에 데이터를 저장하거나, 가져오는데 걸리는 시간

 

Disk Space Management

Disk Space Management는 DBMS 구조에서 가장 하위에 존재하는 레이어로, 페이지를 물리적인 주소로 변환하여 실제 디스크에서 Block 단위로 입출력 작업(디스크에서 메모리로 페이지를 load 혹은 메모리의 페이지를 디스크에 Save) 을 수행합니다. 

 

Block : Disk에서 Read/Write를 수행하는 단위 (일반적으로 64KB~128KB)

File Manager에서 취급하는 Page는 일반적으로 디스크의 Block과 같은 사이즈를 사용합니다.

 

디스크에서 인접한 블록은 같은 트랙 👉 같은 실린더 👉 인접한 실린더 순으로 배치되어, 인접한 블록들을 가져올 때 seek time과 rotational delay를 줄일 수 있습니다.

 

Disk Manager가 상위 레이어에 제공해야할 인터페이스는 다음과 같습니다.

1. 페이지를 디스크에 Read/Write 할 수 있는 인터페이스

2. 새로운 페이지를 할당받거나, 빈 페이지를 할당 해제할 수 있는 인터페이스

 

상위 레이어 (ex. Buffer manager) 는 Disk Manager가 어떻게 물리적으로 페이지를 디스크에서 가져오고 저장하는지는 신경쓸 필요 없이, 제공되는 인터페이스를 사용하면 됩니다.

 

Database Files

데이터베이스 테이블은 File로 인코딩되는데, 이 파일은 여러 개의 Page로 이루어집니다.

그리고 파일을 구성하는 방법에는 다양한 방식이 있습니다.

 

1. Unordered Heap Files

레코드들이 임의의 순서로 페이지들에 들어가는 방식입니다. 

여기서 Heap은 자료구조의 heap을 의미하는게 아니라 그냥 쌓여있다는 의미입니다.

따라서 빠르게 Insert, Delete를 할 수 있지만, 원하는 레코드를 탐색하는 것은 다른 방식에 비해 느립니다.

이러한 파일구조에서 레코드에 대한 연산을 수행하기 위해서는

1) 파일 내의 페이지들의 위치를 관리, 2)페이지 내의 레코드들의 위치를 관리, 3) 페이지 내의 빈 공간을 관리 해야합니다.

 

👉리스트로 Heap File 구현

• 페이지들을 링크드리스트로 잇는데, 헤더페이지에서 두 뭉치로 갈라지게 합니다. 한쪽 리스트는 꽉 찬 페이지들을 잇고, 다른 쪽 리스트는 아직 공간이 남아있는 페이지들을 잇습니다. 
• 여기서 문제점은 특정 레코드를 넣을 수 있을만큼의 남는 공간이 있는 페이지를 찾기 위해 여러 개의 페이지를 하나하나씩 뒤져가며 찾아야한다는 점입니다.

👉Page Directory 사용하여 Heap File 구현

헤더페이지에 각 페이지들에 남아있는 빈 공간의 크기를 담아두는 방식입니다.

이렇게되면 각 페이지들을 직접 가져와 빈 공간의 크기를 확인할 필요 없이, 헤더 페이지만을 가지고 새로운 레코드를 넣을 페이지를 찾을 수 있기 때문에 훨씬 효율적입니다.

Heap File로 데이터베이스를 구성하면, Page number와 페이지내에서 레코드의 위치 (offset)을 통해 레코드를 찾을 수 있습니다. 

하지만 만약 gpa가 4 이상인 레코드를 모두 찾는 것과 같이 레코드 내의 값을 기준으로 레코드를 찾고자 한다면 쉽게 찾을 수 없습니다.

이런 상황을 효율적으로 해결할 수 있는 파일 구조가 Index입니다.

2. Index Files

B+ Tree와 같은 자료구조로 이루어진 파일로, 자세한 내용은 이후 더 공부해보겠습니다. 

3. Hash Files

레코드의 일부 필드를 해시 함수에 넣으면 레코드가 디스크에서 배치될 위치가 출력되도록 하는 방식입니다.

4. Sorted Files

레코드와 페이지들이 정렬되어 저장되는 파일 구조입니다.

따라서 Heap File보다 Insert, Delete는 느리지만, 빠르게 탐색할 수 있습니다.

 

Database Pages

Page Header

페이지의 정보를 요약해놓은 부분으로, 페이지의 맨 앞에 부가적인 정보 (= Meta data)를 저장해놓은 것입니다.

예를 들어, 레코드의 총 개수나 각 페이지에 남은 공간의 크기 등을 모아 저장해둡니다.

 

Page Layout

페이지를 구성할 수 있는 방법에는 다양한 방식이 있는데, 다음의 기준에 따라 나눌 수 있습니다.

1. 레코드의 길이가 고정되어있는지 가변적인지

2. 레코드가 중간중간 삭제되어 페이지 중간에 빈 공간이 생길 때, 이 빈 공간들을 그냥 놔둘지 (Unpacked) 혹은 레코드들을 모아서 빈공간을 메울지 (Packed)

 

1. 고정된 길이의 레코드와 Packed 방식을 사용하는 경우

이 경우, 레코드를 찾기 위해서는 페이지의 id와 페이지 내에서 레코드의 인덱스를 알면 됩니다.

레코드의 길이가 고정되어 있으므로, 찾고자하는 레코드가 몇번째 레코드인지만 안다면 레코드의 위치(byte offset)를 알 수 있습니다. 

따라서 이 경우 Record Id = (Page Id, record #) 로 나타낼 수 있습니다.

 

새로운 레코드가 Insert되는 경우, 레코드가 Packing되어있으므로 (총 레코드의 개수 * 레코드의 size)를 이용해 Free space 의 시작점을 바로 알아내어 삽입할 수 있습니다. 

 

여기서 중간에 있는 레코드가 Delete 된다면, Packed상태를 유지하기 위해 삭제된 레코드 이후의 레코드들을 모두 재배열해주어야합니다. 그런데 이렇게 레코드들의 위치를 당기면 재배열된 레코드들의 Record id를 모두 변경해주어야합니다.

 

그런데 Packed 방식의 장점은 레코드들의 길이가 다를 때, 중간중간 비어있는 공간들의 총 합은 충분히 크지만 각각은 너무 작아서 새로운 레코드를 빈 공간에 삽입할 수 없을 때, 효율적으로 Free space를 관리할 수 있다는 점입니다.

따라서 레코드의 길이가 고정되어있다면 Unpacked 방식을 사용하는게 더 나을 수 있습니다.

2. 고정된 길이의 레코드와 Unpacked 방식을 사용하는 경우

레코드를 패킹하지 않으면 빈 공간이 페이지의 여기저기에 퍼져있기 때문에, 페이지에서 빈 공간을 관리하기 위해 Bitmap에 각 레코드가 비어있는지 아닌지를 표시해두어야합니다.

이때, 레코드 size가 너무 작다면 bitmap이 차지하는 공간이 너무 커져서 오버헤드가 커질 수 있습니다.

새로운 레코드가 Insert되면 비트맵에서 빈공간을 찾아 삽입합니다.

중간 레코드가 delete되면, 페이지를 재배열할 필요 없이 그냥 삭제하면됩니다.

3. 가변 길이의 레코드

레코드의 길이가 가변이 되면 페이지에 몇 개의 레코드가 들어갈 지 알 수 없게됩니다.

따라서 메타데이터, 즉 페이지 헤더의 크기도 가변이 됩니다. 따라서 이 경우에는 페이지 Header가 아닌 Footer를 사용해야합니다.

그러면 레코드가 저장되는 방향과 메타데이터가 저장되는 방향이 반대가 되어 둘 다 가변이 되어도 상관없기 때문입니다.

이렇게 가변 길이의 레코드를 저장하는 방식을 Slotted Page라고 합니다.

Slotted Page

Slotted Page는 Footer에 메타데이터를 저장해둡니다. 

Footer에 들어가는 한 slot은 위 그림의 오른쪽과 같이 구성되며, 레코드의 길이와 레코드 시작점을 가리키는 포인터를 담고 있습니다. 그리고 푸터는 새로운 레코드가 생길 때마다 거꾸로된 방향으로 늘어납니다. 

이 방식에서 Record id는 푸터의 슬롯테이블에서 레코드의 위치로 나타낼 수 있습니다. (오른쪽부터 시작, 예를 들어 12번 위치에 있는 레코드는 4번째 레코드)

그리고 슬롯테이블의 첫번째에는 Free space의 시작위치를 가리키는 포인터가 들어갑니다.

 

그리고 여기서 중간에 레코드가 삭제되면 다른 것을 고칠필요 없이 그냥 삭제만하면 됩니다. 

위에서 언급했듯 12번 위치에 있는 레코드는 record id로 4를 갖는데 (페이지#은 편의상 생략), 만약 3번째에 있던 레코드가 삭제되어도 해당 레코드의 id는 3으로 바뀔 필요가 없습니다.

왜냐하면 푸터의 슬롯테이블에서 4번째 위치에는 여전히 시작점의 주소로 12가 저장되어 있고, 이는 올바른 위치이기 때문입니다. 

 

새로운 레코드에 대한 Insert는 다음과 같이 이루어집니다.

1. Free space에 레코드를 넣습니다.

2. 슬롯테이블의 빈 슬롯에 해당 레코드의 길이와 시작 포인터를 넣습니다.

3. Free space를 가리키는 포인터를 업데이트합니다.

 

그리고 너무 중간중간 빈 공간이 많아지면 레코드들을 재배열해주는 작업이 필요한데, 이 경우에도 슬롯 내의 포인터 값만 변경하면 될 뿐 Record id는 달라지지 않습니다.

즉 데이터가 저장된 곳과 데이터를 찾기위해 사용하는 곳(헤더/푸터)을 분리하는 Address Indirection방식을 사용하여, 데이터의 위치가 아무리 변경되어도 데이터의 고유한 id는 변경되지 않아도 되는 것입니다.

이것이 Slotted Page의 큰 장점입니다.

 

또 푸터의 맨 앞에 슬롯의 개수를 저장해두어서, 슬롯테이블의 새로운 슬롯이 추가할 때 사용할 수 있습니다.

 

Database Records

레코드의 구조는 레코드 내에 가변길이의 변수가 있는지 없는지에 따라 달라집니다.

고정길이의 변수만 존재하는 레코드 형식

레코드에 고정된 길이의 변수만 존재하면 메모리와 디스크에 저장되는 레코드의 형식이 동일하게됩니다.

그리고 레코드 내의 특정 변수의 위치는 고정되어있습니다.

가변길이의 변수가 존재하는 레코드 형식

1. 각 필드의 공간을 충분히 크게 잡아놓고, 잡아놓은 공간보다 작은 값이 들어오면 남는 부분은 패딩으로 사용하는 방법이 있습니다. 그러면 각 필드의 위치가 정해져있으므로 빠르게 필드에 접근할 수 있습니다.

하지만 이 방법은 만약 처음 예상한 최대 크기보다 더 큰 값이 들어오는 경우 문제가 발생할 수 있습니다.

 

2. 각 필드마다 공간을 미리 잡아놓는 것이 아니라, 필드를 특정 식별자 (예를 들면 콤마같은) 를 이용해 구분하는 방법이 있습니다. 이 경우 해당 식별자를 찾기 위해 레코드를 훑어야하고, 필드 내의 값에 식별자가 포함되어있을 경우 문제가 발생할 수 있습니다.

3. 각 필드 앞에 필드의 길이를 저장해두는 방법이 있습니다. 이렇게하면 " 필드 내의 값에 식별자가 포함되어있을 경우" 발생하는 문제가 사라집니다. 하지만 여전히 사이즈를 하나하나 살피면서 필드를 찾아가야합니다.

이 문제를 최대한 해결하기 위해 가변길이의 변수들은 레코드의 맨 뒤로 모아버리는 방법이 있습니다. 

그리고 이를 더 효율적으로 만들면, 위에서 페이지에 헤더를 둔 것처럼 레코드 헤더를 두어 가변길이의 변수의 위치를 관리할 수 있습니다. 이렇게하면 필드 사이즈를 하나하나 따라가서 필드를 찾을 필요 없이, 헤더만을 보고 빠르게 필드의 위치를 찾을 수 있습니다.