Ch15. 파일 구조

1. 블록 버퍼링

• 모든 블록 주소를 알고 있는 몇 개의 블록을 디스크에서 주기억 장치로 전송할 때, 전송 속도를 빠르게 하기 위하여 주기억 장치 내의 몇 개의 버퍼를 예약하여 사용할 수 있다.
• 하나의 버퍼를 판동하거나 기록하는 동안 CPU는 다른 버퍼 내의 데이터를 처리할 수 있다.
• 일반적으로 독립적인 디스크 입출력 처리기(제어기)가 존재하여 CPU처리와 병렬로 주기억 장치와 디스크 간에 데이터 블록을 독립적으로 전송할 수 있기 때문이다.

왼쪽 그림은 프로그램이 교대로 수행되지만, 사용자는 동시에 수행된다고 느낌(Interleaved concurrency)

오른쪽 그림은 정말로 병렬처리함

 

CPU가 하나의 버퍼를 사용하고 있는 동안에 입출력 공간에서 다른 블록을 읽어옴(효과: CPU의 대기시간을 줄여줌, 최대한 빠르게 다음 일을 할 수 있게 함)

 

버퍼가 하나 있으면 Single Buffering, 버퍼가 두 개 있으면 Double Buffering

 

 

2. 버퍼 관리

버퍼 관리자(Buffer Manager)는 DBMS의 소프트웨어 구성 요소

버퍼 관리자의 목표

1) 요청된 페이지가 주기억 장치에서 발견될 확률을 최대화

2) 디스크에서 새 디스크 블록을 읽을 경우, 금방 다시 요구하지 않을 것이란 의미에서 가장 적은 피해를 야기할 페이지를 교체 대상으로 찾음

 

버퍼 풀(buffer pool) :DBA가 제어하는 DBMS의 매개변수의 크기

 

버퍼 관리자는 버퍼 풀의 각 페이지에 대해 두 가지 종류의 정보를 유지함

1) 핀 수(pin-count)

• 페이지가 요청된 횟수 또는 그 페이지의 현재 사용자 수
• 고정 해제(unpinned): pin-count가 0이 될 때
• 고정(pinning): pin-count를 증가시키는 것

2) 오손 비트(dirty bit)

• 응용 프로그램에 의해 페이지가 갱신될 때마다 오손 비트가 1로 설정됨

 

3. 버퍼 교체 전략

1. LRU(Least recently used)
2. 시계 정책(Clock policy)
3. FIFO(First-in-first-out)
4. MRU(most recently used)

 

 

4.디스크 상에 파일의 레코드들 배치

레코드중에서는 고정 길이 레코드(Fixd-length record)와 가변 길이 레코드(Variable-length record)가 있음

 

가변 길이 레코드의 구성

• 가변 길이 필드
• 반복 필드 or 반복 그룹
• 선택적 필드
• 혼합 필드(다른 레코드 타입들이 섞인 것)

 

 

5. 레코드 블로킹과 신장/비신장 레코드

블록 = 데이터 전송의 최소 단위(= 하나의 블록)

블로킹(blocking) - 한 블록의 수많은 기록들

 

1) 고정 길이일 때

블로킹 인수(blocking factor)

• 블록 크기가 B바이트라고 가정함
• 크기가 R바이트인 고정 길이 레코드들로 구성된 파일에서 B >= R인 경우에
• Blocking factor: 블록마다 bfr = B/R(버림)개의 레코드를 저장할 수 있음
• 일반적으로 R을 B로 정확히 나눌 수 없으므로 B - (brf * R) 바이트는 사용하지 않음

ex) B = 512, R = 100일 때

블록마다 bfr = 512/100 (버림) = 5개의 레코드 저장

B - (brf * R) = 512 - 500 = 12 bytes를 사용하지 않음

 

2) 가변 길이일 때

• bfr = 블록당 레코드의 평균 개수
• r개의 레코드로 구성되는 파일이 필요로하는 블록 수 b = ( r / bfr ) 개임(올림)
• bfr이 정해지고, r을 가정했을 때의 b를 구하는게 대부분임

 

비신장 방식(Unspanned) = 블록에 남은 공간이 있어도 레코드들을 저장하지 않은 것(단점: 데이터 공간 낭비)

신장 방식(Spanned) = 블록에 남은 공간이 있으면 레코드의 일부를 저장하고, 나머지는 다음 블록에 저장함(단점: 레코드를 검색할 때 두 개의 블럭을 검색할 수도 있음)

 

 

6. 디스크에 파일 블록 할당

연속 할당(Contiguous allocation) : 파일의 블록들을 연속적인 디스크 블록들에 할당(전체 파일을 읽으면 빠르지만, 파일 확장은 어려움)

연결 할당(Linked allocation) : 각 파일 블록마다 다음 블록에 대한 포인터를 유지하는 방법(느리게 읽지만, 확장이 쉬움)

 

두가지 할당을 합쳐서 혼합하면 파일의 블록들을 클러스터라고 하는 연속적인 디스크 블록들에 할당하고(연속할당방식), 이 클러스터들은 서로 연결되게 한다.(연결할당방식) (클러스터는 파일 세그먼트나 영역extent라고 부름)

 

인덱스 할당(Index allocation) : 하나 이상의 인덱스 블록이 실제 파일의 블록의 위치 값을 포인터로 가지고 있는 것

 

 

7. 파일 헤더

좋은 파일 조직의 목표 : 레코드를 찾을 때, 최소 수의 블록 전송으로 원하는 블록을 찾아 레코드를 찾는 것

 

 

8. 파일 연산

검색 연산과 갱신 연산을 지원함

 

파일 연산의 분류

• Open, Close
• Record-at-a-time 
  • Reset, Find, Read, Findnext, Delete, Modify, Insert
  • 한 번에 한 레코드만 처리할 수 있음
• Set-at-a-time
  • FindAll, Find n, FindOrdered, Reoraganize
  • 여러 개의 레코드를 처리할 수 있음
• Scan : 연속적으로 처리하게 해주는 연산

 

 

9. 비순서 파일(Heap Files)

• Heap File 혹은 Pile File이라고도 부름
• 레코드가 삽입되는 순서대로 저장하는 방법
• 파일의 마지막에 새로운 레코드를 삽입함
• 향후 사용할 목적으로 데이터 레코드들을 수집하고 저장하기 위하여 사용됨

1. 탐색 : 블럭의 수가 b개로 구성된 파일이면 평균 b/2개의 블록을 탐색해야함, 탐색 조건에 만족하는 레코드가 없거나 여러개 존재하면 b개의 블록을 탐색해야함
2. 삽입의 경우 : 마지막 블록을 버퍼에 복사함 -> 새로운 레코드를 기록함 -> 디스크에 블록을 저장함
3. 삭제의 경우 :  삭제할 블록을 찾고 -> 블록을 버퍼에 복사하고 -> 버퍼에서 레코드를 삭제하고 -> 버퍼에 있는 블록을 파일에 다시 저장함(빈 레코드는 계속 사용 안함 -> 공간 낭비)
   삭제의 경우엔 너무 많은 공간 낭비가 일어날 수 있으므로 주기적으로 재구성해서 공간을 사용할 수 있도록 함
4. 수정의 경우
   고정 길이 : 파일에서 수정할 블록을 찾고 -> 레코드를 지워서 재기록을 하고 -> 수정된 레코드를 마지막 블럭에 첨가함
   가변 길이 : 기존 레코드를 지우고, 새로운 레코드를 삽입함. 왜냐하면 수정한 레코드가 이전의 레코드의 크기가 같지 않을 수도 있기 때문에
5. 특정 필드에 따라 순서대로 다 읽어야 할 때
   • 힙은 정렬이 안되어있는 상태라서 찾는데 오래 걸림
   • 그래서 외부 정렬(external sorting)을 사용하여 그걸 차례대로 읽는게 빠름

외부 정렬(External Sorting)

내부 정렬(internal sorting)은 메인 메모리에 값들이 다 들어갈 때 사용함. 이건 자료구조 시간에 많이 봄

메인 메모리에 정렬된 값들이 다 들어가지 못하는 경우엔 외부 정렬을 사용함

• 메인 메모리에 가져올 수 있는 크기만큼 파일을 자름
• 정렬한 결과를 파일에 저장함 - run (sorted sub file)
• 이 과정을 반복하면 여러 개의 run이 생기는데, 다시 읽어서 합병함(2개씩 합침 -> 2개씩 합침 -> ...)

 

 

상대 파일(Relative File) 또는 직접 파일(Direct File)

• 파일의 레코드를 주소로 검색하는게 아니라 상대 번호를 할당해줌(0부터 r-1까지)
• bfr(block factor)을 알고 있으면 그 레코드가 몇 번째 블록에 있는지( = i / bfr (내림)), 해당 블록 안에 몇 번째에 위치해 있는지(= i mod bfr)를 알 수 있음

ex) bfr = 4일 때 110번째 레코드는? (컴퓨터는 109번째)

블록의 위치 = 110 / 4 (내림) = 27번째 블록에 위치

해당 블록에서의 레코드의 위치 = 110 % 4 = 27번째 블록의 두 번째 레코드가 110번째 레코드임

 

 

 

10. 정렬 파일(Sorted Files)

순서 파일(Ordered File), 순차 파일(Sequential File)라고 부름

• 만약 정렬된 필드가 key라면 해당 값은 ordering key라고 부르고, 이것들은 unique하다는 것을 알 수 있음
• 비정렬 파일은 순차 탐색(linear search)만 가능한데, 정렬 파일은 이진 탐색(binary search)를 사용하여 빠르게 탐색할 수 있음(log2(b)개의 파일을 탐색)
• 정렬 파일은 부등호(>, <, >=, <=)로 검색할 때 매우 효율적임
• 순서 파일 방식에서는 다른 비순서 필드의 값을 기반으로 레코드들을 임의 접근하거나 순서 접근하지 못함(이름순으로 정렬했는데, 학번순으로 검색을 하라고 하면 순차 탐색을 해야함) -> 이런 경우 그냥 검색에서 찾는 파일을 정렬한 사본을 만들어서 찾는게 더 빠름

 

삽입과 삭제는 굉장히 효율이 낮음

• 삽입 : 끼워넣으면 나머지는 뒤로 밀어놔야함(중간중간에 빈 칸을 만드는 경우도 있음)
• 삭제 : 삭제대신 마킹만 해두다가 나중에 주기적으로 한 번에 삭제하고 다시 정렬하는 방식을 사용(재조직)

 

수정하는 방법 -> 트랜잭션 파일 사용

• 일시적인 비정렬 파일을 사용 : 오버플로우 파일 혹은 트랜잭션 파일이라고 부름(원래 정렬된 파일은 메인 파일 혹은 마스터 파일이라고 부름)
• 일단 트랜잭션 파일에 저장해뒀다가 나중에 메인 파일과 합체하는 방식
• 새로운 레코드는 오버플로우 파일의 끝에 넣음
• 나중에 마스터 파일과 오버플로우 파일은 서로 병합해주는 재조직 작업을 해야함
• 어떤 파일을 검색할 때 메인 파일에서 검색해보고, 없으면 트랜잭션 파일에서도 검색해야함(검색이 복잡해짐)
• 최신정보가 필요하지 않은 경우라면, 검색할 때 오버플로우 파일은 무시하고 메인 파일에서만 검색함

 

재조직(Reorganization)

파일을 재조직하는 방법은 오버플로우 파일(트랜잭션 파일)을 먼저 정렬하고, 마스터 파일(메인 파일)을 병합함(투포인터처럼 새로운 마스터 파일에 삽입함)

 

정렬된 트랜잭션 파일과 마스터 파일은 백업 파일이 될 수도 있음

 

 

 

 

 

정리

 

정렬/비정렬 -> 스캔 형태 -> 확인해야할 블록의 개수

Heap(unordered) -> Sequential scan(linear search) -> b/2

Ordered -> Sequential scan -> b/2

Ordered -> Binary search -> log2(b)

 

정렬된 파일은 primary index를 제공함 -> indexed-sequential file이라고 부름(17장)

정렬할 때 key가 아닌 필드로 정렬하면 clustered file이라고 부름

 

 

 

 

 

11. 해싱 기법

어떤 해시 키 값이 주어지면, 해시 함수를 사용하여 디스크 블록의 주소가 나옴

 

해싱을 쓰는 파일을 해시 파일, Direct 파일이라고 부름

• Primary file organization로, 기록에 검색하는 것을 매우 빠른 접근으로 제공해줌
• 해시 함수는 randomizaing function h라고 부름

 

내부 해싱(Internal Hashing)

내부파일에서 해싱은 일반적으로 레코드들의 배열을 이용하여 해시 테이블로 구현함

해시함수 : 해시 필드 값을 0 ~ M-1사이의 정수로 변환해줌(필드의 개수가 M개일 때)

h(K) = K mod M (만약 K의 값이 정수가 아니라면 숫자로 매핑을 해줌)

 

충돌(해싱 기법에서 가장 큰 문제. 해시 충돌)

해시 충돌 문제를 해결할 수 있는 방법 - 충돌 해결 기법: 다른 위치를 찾는 과정

충돌 해결 기법 종류

1. 개방 주소 법(open addressing)
2. 체인(chaining)
3. 다중 해싱(multiple hashing)

 

개방주소법: 충돌이 일어나면 다음 빈 자리에 저장하는 것(만약 어떤 값을 찾을 때, 해싱된 값부터 원하는 값이 나올 때까지 혹은 빈자리가 나올 때까지 값을 찾음)

체인: 별도의 블록을 할당해서 연결리스트로 연결하는 것(오버플로우 포인터를 만들어서 만약 충돌이 된다면 오버플로우 포인터를 따라가서 원하는 값을 찾음, 주소공간과 오버플로우 공간이 분리되어 있음 -> closed addressing이라고도 부름)

다중 해싱: 해시 충돌이 일어나면 또다른 해시 함수를 사용하여 새로운 주소를 할당하여 저장하도록 만드는 방법

 

위 세가지 충돌 해결 기법중 어떤 걸 사용하든지 간에 검색, 삽입, 삭제를 위한 별도의 알고리즘이 필요함

 

 

좋은 해싱 함수의 목표

• 전체 기억 공간에 70% ~ 90% 차도록 관리하기(작으면 작을수록 충돌이 일어날 확률이 적음, 밀도가 90%가 넘게되면 충돌이 급증하게 되고, 70% 아래로 내려가면 충돌이 일어날 확률은 비슷비슷하지 줄지는 않음)
• K mod M을 사용할 때 M은 소수를 사용함

 

 

 

외부 해싱(디스크 파일을 위한 해싱)

목표 주소 공간을 버켓(buckets)이라고 부르는데, 이 버켓은 하나의 디스크 블록을 뜻하거나 여러 연속된 블럭의 클러스터를 말함

해싱 함수: key -> 상대 버켓 번호(a relative bucket number)

충돌 해결 비법 -> 체인(chaining) 방법을 사용함

 

 

외부 해싱 연산

검색: 원하는 값을 한 번에 못 찾으면 오버플로우 체인을 따라가서 검색을 함

삭제: 해당되는 레코드를 찾아서 지우면 됨(만약 오버플로우 영역에 레코드가 있으면 삭제할 값을 없애고, 남은 값들을 포인터로 연결해줌. 123 -> 168 -> 987이 있으면 168을 삭제하고 싶을 때 123 -> 987로 연결해주면 댐. 123을 삭제하고 싶으면 168 -> 987로 앞으로 땡겨줌)

수정: 수정해야할 값을 찾고 -> 해시 필드가 아니라면 그냥 바꿔줌. 해시 필드면 삭제해주고, 수정 값을 새로 삽입해줌

 

 

 

정적 해싱(static hashing)과 동적 해싱(dynamic hashing)

지금까지 배운 내용은 정해진 수의 버켓을 할당하여 값을 저장하는 방식으로 이것을 정적 해싱이라고 부름

하지만 값이 몇 개가 들어올지 모르는 동적인 파일(dynamic file)이라면 재구성(reorganize)하는 방법밖에 없음 -> 하지만 재구성은 시간이 너무 오래 걸림

 

그래서 동적 파일을 위해 저장공간을 줄였다 늘였다할 수 있는 해싱을 정적 해싱과 반대인 동적 해싱라고도 부름

Entendible hashing(확장성 해싱)

Linear hashing(선형 해싱)

Dynamic hashing(동적 해싱)

 

접근 구조는 레코드의 해시 값은 이진 표현을 사용하여 처리하는 방법

 

확장성 해싱(entendible hashing)

키 값을 이진수로 표현하고, 버켓도 2^d의 이진수 주소로 만듦

Global depth: d = 3이면 비트를 3개만 쓰겠다는 말임(000 버켓에서 111버켓이 있는데 000버켓은 처음 세 비트가 000으로 시작하는 레코드들이 모여있음)

d'의 값이 다른 경우도 있는데, 이 값을 local depth라고 부르고 위의 예시에서 d'=2라면 010과 011은 앞 2개의 비트가 01로 같기 때문에 같은 버켓을 가르키게 댐

 

directory: 2^d개의 버켓 주소를 포함하고 있는 배열

d = directory의 global depth(첫 d비트를 이용함. 인덱스 역할. 주소를 포함함)

d' = local depth는 첫 d'개의 비트가 동일한 값을 갖는 레코드들을 모아둔 버켓(버켓과 같이 저장되어 있음)

 

d = 3일 때, 데이터가 늘어나면 d = 3으로 부족할 때가 있어서 그때는 d = 4로 만들어서 공간을 두 배로 늘림. 이런 행위를 doubling이라고 부르고, 반대로 데이터가 줄어들면 쓸모없는 공간이 생기므로 d = 2로 만들어서 공간을 1/2배로 줄이는데, 이것을 halving이라고 부름

 

동적 해싱의 장점

• 파일이 아무리 커져도 성능 저하가 일어나지 않음
• 앞으로를 대비할 파일을 위해 미리 공간을 만들어둘 필요가 없음(그때그때 만들면 되므로)(directory의 저장공간은 무시)
• doubling이나 halving하는 것은 reorganization에 비해 성능이 미미함

동적 해싱의 단점

해싱 함수를 통해 값을 바꾸고 -> 디렉토리를 찾고 -> 버켓에 진입하므로 총 두 번 접근해야하는 단점이 있음(대신 크기가 작으면 디렉토리를 메인 메모리에 둬서 한 번만 접근할 수 있게 할 수도 있음)

 

 

 

동적 해싱(dynamic hashing)

확장성 해싱이랑 비슷한데, directory를 트리로 유지함

필요에 따라 버켓을 늘렸다 줄일 수 있는 장점이 있음

 

 

선형 해싱(linear hashing)

K mod M에서 M의 값을 늘렸다 줄였다하는 방식의 해싱

h_i(K) = K mod M

오버플로우가 일어나면 h_(i+1)(K) = K mod 2M을 통해 나눠줌(실제 메모리가 두 배로 늘어나는 것은 아님, 논리적으로는 두 배가 늘어나지만 물리적으로는 한 개가 추가되는 방식)

 

 

 

12. RAID 기술

Redundant Arrays of Inexpensive Disks 또는

Redundant Arrays of Independent Disks의 약자

 

작은 용량의 디스크를 병렬적으로 연결해서 하나의 큰 디스크인 것처럼 사용하는 것

RAID level은 0 ~ 6까지 있음

 

Data striping: 디스크 퍼포먼스를 높이기 위해 데이터를 흩어지게 저장하는데, bit-level로 저장하는 방법(bit-level striping)과 block-level로 저장하는 방법(block-level striping)이 있음

 

 

RAID를 통해 신뢰도를 향상시킬 수 있음

n개의 디스크를 갖는 배열을 사용한다면, 디스크가 고장날 확률도 n배만큼 늘어남

(디스크 회사들이 고장나지 않는다는 것을 보장하는 시간 MTBF = 약 200,000시간은 고장 없이 사용할 수 있음, 그런데 만약 100개의 디스크를 사용한다면 200,000 / 100으로 2,000만큼 고장 없이 사용할 수 있게 댐)

=> 해결하는 방법: 데이터 중복성(redundancy of data)을 사용하면 동시에 고장날 확률이 줄어들음(단점: 두 군데를 사용해야하니까 작성을 위한 추가적인 입출력 연산이 필요, 중복성을 유지하거나 회복하는데 비용이 많이 들음, 중복성을 관리하기 위한 추가 공간이 필요)  => 그래서 RAID 방식을 사용함

 

가장 안전하게하는 방법은 Mirroring 혹은 Shadowing이라고 함(똑같은 디스크를 두 개나 쓰는 것)

그외 방법은 parity bits를 사용하거나, error-crrecting codes를 사용하는 것

 

Mirroring이나 Shadowing을 사용하면 동시에 두 개의 디스크가 고장나지 않는 이상 데이터가 그대로 유지될 수 있음

 

RAID를 사용하면 퍼포먼스에서도 이득을 볼 수 있음

mirroring은 중복성을 얻어서 안정적이지만,

data striping에서는 속도면에서 장점을 얻을 수 있음

디스크가 2개 있으면 동시에 2개를 읽어서 같은 시간에 두 배를 더 읽을 수 있음. 8개면 동시에 8개를 읽어서 같은 시간에 8배를 더 읽을 수 있음

 

RAID 조직방법

mirroring과 data striping을 잘 섞어서 데이터를 얼마나 흩어놓는지(striping), 중복 정보를 얼마나 관리할 것인지(redundant)

 

RAID Level 0: redundancy가 없고, striping만 있는 것 - block level striping(2개의 디스크면 전송률이 두 배)

RAID Level 1: mirrored disk 방식(mirroring 사용, striping 사용 안 함)

RAID Level 2: memory-style redundancy라고 부름.  Hamming code를 사용함(error-correcting), 특정 에러를 잡기 위해 3개의 추가 디스크를 할당함 + bit-level striping (어떤 디스크가 고장나면 Hamming code를 이용해 값을 살려내게 됨)

-> 최근 디스크에는 디스크 스스로 어디가 고장났는지 알 수 있어서 Hamming code가 1개의 추가 디스크만 사용함(RAID Level 3) 

RAID Level 3: byte-level striping. 특정 디스크가 고장나도 1개 값으로 복구가 가능함

RAID Level 4: block-level striping. 이것도 마찬가지로 1개의 값으로 복구가 가능함

-> Level 3, 4 떄문에 Level 2는 사용하지 않음 -> 이것도 level 5때문에 거의 사용하지 않음

RAID Level 5: block-level striping, 레벨 2, 3, 4는 디스크 하나에 Hamming code를 전부 할당하는데, 그러면 모든 디스크가 해밍 코드가 있는 디스크에 접근하려고 하므로 성능에 심각한 영향이 생기니까, 해밍 코드를 각 디스크에 흩어둠

-> RAID Level 0, 1, 5가 많이 쓰임

RAID Level 6: P+Q redundancy. 중복 디스크를 두 개나 쓰는 대신에 동시에 두 개의 디스크가 고장나도 데이터를 살려낼 수 있음(가장 안정적이긴 함)

 

 

Hybird RAID Levels

RAID Level을 섞어서 사용함(

RAID 0+1: 먼저 데이터를 2개의 디스크에 분산 시키고, 이것을 mirroring 함(총 4개의 디스크)

RAID 1+0: 먼저 미러링을 하고, 다른 2개의 디스크엔 새로운 값을 할당함 -> RAID 10이라고 함

 

A+B이면 밑에가 RAID Level A가 되고, 위에가 RAID Level B가 되는 방식