DBMS - Files

Tony·2023년 6월 8일
0

DBMS - Disks, Files and Buffers

DBMS 구조

DBMS architecture
SQL Client
Query Parsing & Optimization
Relational Operators
Files and Index Management
Buffer Management
Disk Space Management
Database
  • Query Parsing & Optimization : SQL을 파싱, 검증, 최적화합니다.
  • Relational Operators : 레코드와 파일에 연산을 수행합니다.
  • Files and Index Management: 테이블과 레코드를 관리합니다.
  • Buffer Management : 메모리를 관리합니다.
  • Disk Space Management: 페이지를 실제 바이트로 번역합니다.

Disk page에 접근하기 위한 시간

  1. Seek time : 디스크 헤드가 해당 디스크 페이지가 있는 트랙으로 도착할때까지의 시간
  2. rotational delay : 디스크 헤드가 해당 디스크 페이지가 위치한 트랙으로 도착할때 까지 걸리는 시간 (Spindle이 원판을 돌립니다.)
  3. transfer time : 데이터를 디스크에서 읽어서 데이터를 옮길때 걸리는 시간

각각 2-3ms, 0-4ms, ~0.25ms이 걸립니다. 따라서, seek time과 rotational delay를 줄이는 것이 관건입니다.

SSD

읽기는 2~3KB 단위로 가능하지만, 쓰기는 1~2MB 단위로 가능합니다. 또한, 쓰기 연산은 garbage collecting도 수반하기 때문에 그에 대한 오버헤드도 있습니다.

따라서, 읽기는 기존 하드디스크보다 10~1000배 정도의 성능 향상이 있습니다. 하지만, 쓰기 성능은 드라마틱하게 좋진 않습니다.

SSD의 특징은, sequential read와 random read의 성능이 비슷하다는 것입니다. 쓰기 연산의 경우 큰 단위로 쓰기 때문에 sequential write의 성능이 훨씬 좋습니다.

그러나, 전체적으로 SSD의 쓰기/읽기 성능은 하드디스크를 상회합니다.

Terminology

  • Block: unit of transfer for disk read/write

    64KB ~ 128KB

  • Page: common synonym for block, a block-sized chunk of RAM

  • "Next" block : 특정 블록으로부터 가장 가까운 블록(현재 블록으로부터 seek, rotational delay가 적은 블록)을 의미합니다. 다음과 같은 순으로 가깝다고 말할 수 있습니다.

    1. 같은 트랙에 있는 연속한 블록
    2. 같은 실린더에 있는 블록
    3. 근접한 실런더에 있는 블록

Disk Space Management

디스크 공간을 관리하며, 페이지를 읽고 쓸 수 있는 API를 제공합니다.

  • 페이지를 디스크의 물리적인 위치로 매핑합니다.
  • 디스크로부터 메모리로 페이지를 로드합니다.
  • 페이지를 디스크에 저장합니다.

페이지를 요청할 때, 상위 레이어들은 "Next" page가 빠르다고 추측합니다. 그래서 연속한 페이지를 스캔하는 것이 빠를 것이라고 기대합니다. 그러나, 실제 디스크의 세부사항은 상위 레이어들에게는 감춰져있고 Disk Space Manager가 관리합니다.

구현

DBMS 파일은 여러 개의 디스크에 있는 여러 개의 파일 시스템에 걸쳐서 작용할 수 있습니다.

image-20230524000953050

위의 그림과 같이, Disk Space Management 레이어는 상위 레이어가 각 Storage를 하나의 거대한 contiguous한 블록들이라고 인식할 수 있도록 해줍니다. 만약, Page5를 fetch한다면 Disk Space Manager는 BigFile2에서 Page5를 찾아 로드할 것입니다.

DB Files

DB 테이블은 파일들의 집합이고, 파일은 페이지의 집합입니다.

  • Unordered Heap Files : 레코드가 여러 페이지에 순서 없이 흝뿌려져 있습니다.
  • Clustered Heap Files : 레코드와 페이지가 그룹을 이루고 있습니다.
  • Sorted Files : 레코드와 페이지가 정렬되어 있습니다.
  • Index Files : 레코드의 빠른 검색을 도와주는 파일 구조입니다.

Unordered Heap Files

자료구조에 나오는 heap과는 다른 개념입니다. 특정한 순서가 없는 레코드의 집합을 heap file이라고 부릅니다.

Unordered Heap Files을 구현하기 위해서는 다음과 같은 메타데이터를 유지할 수 있도록 구현해야합니다.

  • 파일내에서 페이지의 위치
  • 파일내에서 레코드의 위치
  • 레코드가 추가될 수 있는 빈 공간

구현

  1. 파일의 메타데이터를 가지고 있는 헤더 페이지의 페이지 ID와 파일 이름은 데이터베이스 카탈로그에 저장됩니다.
  2. 헤더 페이지에 빈 공간에 대한 정보가 기입되어 있습니다. 1개의 헤더 페이지만 있는 것이 아니라, 여러 개의 헤더 페이지가 linked list 형태로 이어져있습니다. 자주 접근하므로, 메모리에 캐시되어 있을 확률이 높아 접근 비용이 저렴하다는 장점이 있습니다.
  3. 헤더 페이지에는 각 데이터 페이지를 가르키는 entry가 저장되어 있습니다. 해당 entry에는 참조하는 페이지의 free bytes도 트래킹합니다. 따라서, 파일 헤더페이지에서 데이터 페이지의 빈 공간을 알 수 있습니다.

DB Page

Page Header

다음과 같은 정보를 가집니다.

  • Number Of records
  • Free space
  • Maybe a next/last page pointer
  • Bitmaps, slot table

Page 구현시 고려사항

  • Record의 길이가 고정값인지/변수값인지
  • Record id(Page, Location in Page)로 레코드를 찾을 수 있는데, Record id를 어떻게 Stable하게 유지할 수 있는지
  • 레코드를 어떻게 추가하고 삭제하는지

Fixed Length Records, Packed

Packed란, 레코드들이 빈 공간 없이 앞에서부터 채워져있다는 의미입니다.

  • Record id는 현재 레코드 앞에 있는 레코드의 수 * 레코드 길이로 구할 수 있습니다.
  • 레코드의 추가는 맨 뒤에 추가하기만 하면 됩니다.
  • 레코드의 삭제가 일어나면, 해당 레코드를 삭제하고 빈공간이 없도록 앞으로 당겨야합니다. 이때, 이동한 레코드에 대한 Record id도 모두 변경시켜야합니다.

Fixed Length Records, Unpacked

페이지 헤더에 비트맵 자료구조를 지닙니다. 각 비트는 레코드의 유무를 나타냅니다.

  • 비트맵의 첫 번째 비트는 첫번째 공간에 있는 레코드, 두 번째 비트는 두 번째 공간에 있는 레코드를 각각 나타냅니다. 따라서, Record Id로서 사용할 수 있습니다.
  • 레코드의 추가는, 비트맵을 앞에서부터 스캔하면서 빈 공간이 있으면 거기에 추가합니다.
  • 삭제는, 비트맵을 끄면 됩니다.

Packed와 비교하여, Record Id를 변경하지 않아도 되므로 더 효율적인 방식이라고 말할 수 있습니다.

Variable Length Records (Slotted Pages)

  • 헤더를 푸터로 이동합니다.
  • 푸터에 slotted directory라는 자료구조를 유지합니다.

slotted directory

slotted directory는 포인터의 배열입니다. 초기값은 레코드의 마지막 위치, 즉 비어있는 공간이 시작하는 위치를 나타내는 포인터를 저장하는 슬롯과 슬롯의 개수를 기입하는 슬롯입니다. slotted directory는 페이지의 가장 뒤에서 시작해서 앞으로 커집니다.

  • 레코드가 추가되면, 비어있는 슬롯이 없을 시 slotted directory에 슬롯이 1개 추가됩니다. 이때, 슬롯이 추가되었다면 슬롯 개수를 1 증가시킵니다. 그리고 추가된 레코드의 가장 앞을 가리키는 포인터가 저장됩니다. 비어있는 공간이 시작하는 위치가 레코드의 마지막 부분으로 바뀌므로 이 부분도 업데이트합니다.
  • 레코드가 삭제될때는 해당 레코드에 대한 포인터를 저장한 슬롯을 null로 초기화합니다.

레코드 삭제에서 대두되는 문제가 empty space fragmentation입니다. 해당 문제를 해결하기 위해서는

  • 삭제할때마다 reorganization을 시행한다. (eager)
  • 빈 공간이 없을때 reorganization을 시행한다. (lazy)

와 같은 방법을 사용할 수 있습니다. reorganization은 레코드 사이의 빈공간이 없도록 레코드들을 앞으로 붙이는 작업을 의미합니다.

헤더를 푸터로 바꾼 이유

slotted directory의 존재만으로 유추할 수 있습니다. slotted directory는 slot이 증가하므로, 헤더에 있다면 모든 레코드의 위치가 그때마다 바뀝니다. 레코드의 위치가 바꾸면 포인터도 업데이트 시켜주어야하기 때문에 오버헤드가 상당합니다. 따라서 푸터로 바꾸어 데이터가 반대방향으로 자라도록 합니다.

결론

slotted page는 fixed length record에도 충분히 적용할 수 있는 general purpose한 자료구조입니다.

Record Layout

기본적으로 테이블 스키마는 데이터베이스 카탈로그에 저장되어 있습니다.

Fixed Length Field

필드 길이가 고정되어 있기 때문에, 스키마를 보고 각 필드의 위치를 계산할 수 있습니다.

Variable Length Field

필드 길이가 가변입니다. 따라서, Fixed Length Field의 경우와 같이 계산을 통해 필드의 위치를 구할 수는 없습니다.

따라서, 가변 길이 필드에 대한 메타정보를 지닌 레코드 헤더를 둡니다.

  • 고정 길이 필드들은 앞쪽에 위치시켜서 계산을 통해 접근할 수 있도록 합니다.
  • 가변 길이 필드들은 고정 길이 필드들의 뒷쪽에 위치합니다. 레코드 헤더에는 가변 길이 필드의 끝을 가리키는 포인터를 저장함으로써 레코드 필드의 위치와 길이를 알 수 있도록 합니다.

image-20230524113441864

하얀색 박스가 고정 길이 필드, 하늘색 박스가 가변 길이 필드입니다.

Heap File과 Sorted File 비교

가정

  • B : number of blocks in a file
  • R : number of records per block
  • D : average time to read/write disk block
  • 이외의 cost는 무시한다.
  • 레코드 값은 모두 unique하다.
Heap FileSorted File
Scan all recordsB*DB*D
Equality Search0.5BD(logB)*D
Range SearchB*D(logB + pages) * D
Insert2*D(logB + B) * D
Delete(0.5B + 1)D(logB + B) * D
profile
Tony
이전 포스트

WebSockets

다음 포스트

DBMS - Recovery Manager

0개의 댓글