2019-04-14

Chapter 15 데이터베이스 파일 조직: 레코드들의 비순서, 순서 및 해시된 파일 2019-04-14 Chapter 15 데이터베이스 파일 조직: 레코드들의 비순서, 순서 및 해시된 파일 Copyright © 2004 Pearson Education, Inc.

Chapter Outline 보조기억장치, 블록, 버퍼링 디스크 상에 파일의 레코드들 배치 파일에 대한 연산 비순서 파일 (히프 파일) 순서 파일 (정렬된 파일) 해싱 기법/해시 파일 동적이고 확장 가능한 해싱 기술 RAID 기술을 이용한 병렬 디스크 접근

디스크 기억 장치(1) 자기 디스크는 적은 비용으로 방대한 양의 데이타를 저장하기 위하여 사용된다. 디스크 기억 장치(1) 자기 디스크는 적은 비용으로 방대한 양의 데이타를 저장하기 위하여 사용된다. 디스크에 저장하는 가장 기본적인 데이타의 단위는 비트이며, 특정 방법으로 디스크상의 한 영역을 자기화함으로써 0 또는 1의 비트값을 표현 디스크 팩은 여러 장의 자기 디스크를 묶어서 구성 디스크는 디스크 표면상의 동심원인 트랙으로 나누어지며 각 트랙은 4 ~ 50 Kbytes를 기록할 수 있음. 트랙은 블록으로 나누어지며 블록 크기는 한 시스템 내에서 고정되어 있으며 일반적인 블록 크기는 512byte 에서 4096byte 이다. 주기억장치와 디스크간의 데이터 이동은 블록 단위로 수행

그림 15.2 디스크 상의 여러 섹터 구조 : (a) 일정각으로 분할된 섹터, (b) 동일한 기록 밀도를 유지하는 섹터

11.2 보조 기억 장치(2) 판독/기록 헤드가 전송할 블록이 있는 트랙으로 이동하고 자기 디스크면이 회전하여 원하는 블록이 판독/기록 헤드 아래에 위치하면 그 블록을 읽거나 쓴다. 디스크 접근 시간 = 탐색시간 + 회전 지연시간( 또는 지연시간 ) + 블록 전송 시간 물리적 디스크 블록 주소는 표면번호, 표면내 트랙번호, 트랙내 블록번호로 구성 디스크 블록의 읽기나 쓰기에서 탐구시간과 회전 지연 시간이 대부분의 시간을 차지 연속된 디스크 블록을 전송하는 시간을 줄이기 위해 이중 버퍼링을 사용할 수 있다.

그림 15.1 (a) 판독/기록 하드웨어를 장착한 단일면 디스크 (b) 판독/기록 하드웨어를 장착한 디스크

표 15.1 Seagate의 전형적인 고급 Cheetah의 디스크 명세

레코드와 레코드 타입 데이터는 일반적으로 레코드 형태로 저장되며, 각 레코드는 연관된 데이터 값이나 항목들로 구성된다. 각 값은 하나 이상의 바이트로 구성되며 레코드의 특정 필드에 해당된다. 레코드는 엔티티와 엔티티의 애트리뷰트들을 기술한다. 한 필드의 데이터 타입은 프로그래밍에서 사용되는 표준 데이터 타입들 중의 하나이다. 표준 데이터 타입에는 수치, 문자열, 부울(0과 1 또는 TRUE와 FALSE) 데이터 타입이 있고, 때로는 특별하게 코드화된 날짜, 시간 데이터 타입들도 사용된다. 이미지, 비디오, 오디오, 긴 텍스트를 나타내는 방대한 양의 비구조적인 객체들은 BLOB(Binary Large Object)라고 하며, 대개 별도의 디스크 블럭들의 풀(pool)에 저장되고 레코드에는 그 포인터만 저장한다.

블로킹 디스크와 주기억 장치 사이의 데이터 전송 단위는 하나의 블록이므로 한 화일의 레코드들을 디스크 블록들에 할당하여야 한다. 블록 크기가 레코드 크기보다 크다면 각 블록에 여러 개의 레코드를 저장한다. 블록크기가 B바이트이라 하고 크기가 R바이트인 고정 길이 레코드들로 구성된 화일에 대하여 B ≥ R인 경우에 블록당 bfr= └B/R┘ 개의 레코드를 저장할 수 있다. 일반적으로 B를 R로 정확히 나눌 수 없으므로 각 블록마다 B - (bfr * R)바이트만큼의 사용되지 않는 공간이 있다. 비사용 공간을 사용하기 위하여 레코드의 일부분을 한 블록에 저장하고 나머지 부분을 다른 블록에 저장할 수 있다.

레코드와 화일 화일은 데이터 값이나 항목들로 구성된 레코드의 집합 화일 내의 레코드들이 모두 같을 때 이 화일이 고정 길이 레코드들로 구성되어 있다고 말한다. 화일 내의 레코드들의 크기가 서로 다를 때 이 화일은 가변 길이 레코드들로 구성되어 있다고 말한다. 가변 길이 레코드 화일에서는 가변 길이 필드의 바이트 수를 결정하기 위해 분리 문자를 사용하거나, 필드값 앞에 가변 길이 필드의 바이트 길이를 기록한다.

레코드와 화일(계속) 레코드를 하나 이상의 블록에 걸쳐서 저장하는 방식을 신장(spanned)조직이라 한다 레코드 하나의 크기가 한 블록의 크기보다 클 경우 신장조직을 사용하여야 한다. 레코드가 블록 경계를 넘지 않도록 저장하는 방식을 비신장(unspanned) 조직이라 한다. 가변길이 레코드의 경우에는 신장 또는 비신장 조직을 사용할 수 있다. 평균 레코드 크기가 클 경우에는 각 블록내의 손실 공간을 줄이기 위하여 신장조직을 사용하는 것이 유리하다.

그림 15.6 레코드 조직의 유형 : (a) 비신장 조직, (b) 신장 조직 P 레코드 1 레코드 2 레코드 3 레코드 4 레코드 5 레코드 6 레코드 4(나머지) 레코드 7 (a) 블록 i 블록 i+1 (b) 그림 15.6 레코드 조직의 유형 : (a) 비신장 조직, (b) 신장 조직

화일에 대한 연산 한 번에 한 레코드 연산 Delete : 현재 레코드를 삭제하고, 화일을 갱신한다. Open : 판독과 기록을 위해 화일을 개방하고, 디스크로부터 화일 블록들을 유지하기 위해 적절한 버퍼들을 할당한 후 화일 헤더를 검색한다. 화일 포인터를 화일의 시작 위치로 설정한다. Reset : open된 화일의 화일 포인터를 화일의 시작 위치로 설정한다. Find : 조건을 만족하는 첫 번째 레코드를 탐색하고, 탐색된 레코드를 현재 레코드로 지정한다. FINDNEXT : 현재 레코드로부터 조건을 만족하는 다음 레코드를 탐색하고, 탐색된 레코드를 현재 레코드로 지정한다. READ : 현재 레코드를 프로그램 변수로 복사한다. Delete : 현재 레코드를 삭제하고, 화일을 갱신한다. Modify : 현재 레코드의 필드값을 수정하고, 화일을 갱신한다. Insert : 새로운 레코드를 화일에 삽입한다. Close : 버퍼 해제와 기타 필요한 제거 연산을 수행하여 화일 접근을 완료한다.

화일에 대한 연산(계속) 한 번에 레코드들의 집합 연산 : 데이터베이스 시스템에서 사용하는 고수준의 연산 FindAll : 탐색 조건을 만족하는 화일 내의 모든 레코드를 찾는다. Find n : 검색 조건을 만족하는 첫 번째 레코드를 검색한 후 동일한 조건을 만족하는 나머지 n-1개의 레코드를 연속해서 찾는다. FindOrdered : 특정 순서대로 화일 내의 모든 레코드를 검색한다. Reorganize : 화일을 재조직한다. 화일 조직은 기억 장치 매체상에 레코드와 블록들을 저장하고 서로 연결시키는 방법. 접근 방법은 화일에 적용할 수 있는 연산들의 그룹을 제공 화일에 자주 사용되는 연산들을 가능한 한 효율적으로 수행해야 성능이 우수한 화일 조직이라 하겠다.

비순서 화일 heap file이나 pile file로 불리기도 한다. 새로운 레코드는 화일의 마지막에 삽입하므로 삽입은 매우 효율적이다. 레코드를 탐색하기 위해서는 선형 탐색 기법을 사용해야 한다. 이 기법은 평균 화일 블록의 반을 탐색하기 때문에 비효율적이다. 어떤 필드값의 순서대로 레코드를 판독하기 위해서는 해당 화일의 레코드들을 정렬시켜야 한다. 비신장 블록과 연속할당 방식을 사용하는 비순서 고정길이 레코드들로 구성된 화일에서는 레코드의 위치(순번)을 이용하여 레코드를 접근할 수 있다. 이런 방식으로 접근할 수 있는 화일을 상대 화일이라고 한다.

순서 화일 순차화일(sequential file)로 불리우기도 한다. 화일 내의 레코드들을 순서 필드의 값에 따라 정렬된다. 레코드들이 정렬된 형태로 추가되어야 하기 때문에 삽입 비용이 비싸다. 더욱 효율적으로 작업하기 위해 오버플로 화일 또는 트랜잭션 화일을 사용한다. 단, 이 방식은 정기적으로 주 화일에 합병시켜야 한다. 이진 탐색은 레코드의 순서 필드값에 따른 탐색의 경우 사용된다. 평균적으로 Log2b개의 블록을 접근하는 이진 탐색은 선형 탐색보다 더 좋은 성능을 보인다.(b는 블록의 총 개수). 정렬된 키 값의 순서대로 판독하는 연산이 매우 효율적이다. 레코드 삽입과 삭제는 레코드를 물리적으로 정돈된 상태를 유지해야 하므로 비용이 매우 크다.

순서 화일(계속) 순서 화일 방식에서 비순서 필드 값을 기반으로 레코드들을 임의 접근하거나 순서 접근하기 어렵다. 이 경우 임의 접근은 선형 탐색을 사용하고, 순서 접근은 화일을 정렬한 복사본을 사용해야 한다. 삽입을 효율적으로 수행하기 위해 오버플로 화일 또는 트랜잭션 화일이라는 임시 비순서 화일에 기록한 후 주 화일 또는 마스터 화일과 정기적으로 합병 레코드 삭제시 빈 공간을 메우기 위해 레코드들을 이동하거나 삭제 표시자를 사용할 수 있다. 순서 필드 값을 수정하는 연산은 그 레코드를 삭제하고 새로운 순서 필드 값을 갖는 레코드를 삽입한다. 기본 인덱스라고 부르는 부가적인 접근 경로를 화일과 함께 사용하는 경우가 아니면 데이타베이스 응용에서 순서 화일을 거의 사용하지 않는다.

그림 15.7 NAME 필드를 순서키로 갖는 EMPLOYEE 레코드들로 구성된 순서 화일의 일부 목록

표 15.2 기본 화일 구조에 대한 평균 접근 시간

해싱 화일 해싱을 기반으로 조직된 화일을 해시 화일 또는 직접 화일이라고 한다. 해시 함수 또는 난수화 함수라고 하는 함수 h를 레코드의 해시 필드값에 적용하여 레코드를 저장하고 있는 디스크 블록의 주소를 산출한다. 대부분의 레코드에 대해 한 번의 블록 접근으로 원하는 레코드를 검색하는 매우 효율적인 방식이다. 화일의 키 필드로 해시 필드를 사용할 경우 이를 해시키라고 한다. 프로그램에서 어떤 필드값을 사용하여 레코드들의 그룹을 배타적으로 접근하고자 할 때 내부 탐색 구조로 해싱을 사용한다.

해싱 화일(계속) 내부 화일에서 해싱은 일반적으로 레코드들의 배열을 이용하여 해시 테이블로 구현한다. 해시 필드 공간이 주소 공간보다 매우 크기 때문에 대부분의 해시 함수는 서로 다른 해시 필드값을 항상 서로 다른 주소로 사상하지는 못하는 문제점이 있다. 삽입하려는 새로운 레코드의 해시 필드 값이 다른 레코드가 이미 점유하고 있는 주소로 해싱될 때 충돌이 발생. 이 경우 새로운 레코드를 삽입할 다른 위치를 찾아야 하는데 이를 충돌 해결이라 함. 해시 테이블을 70%에서 90% 정도 사용하도록 유지할 때 충돌 횟수도 줄이고, 공간 낭비도 줄일 수 있다.

해싱 화일(계속) 충돌 해결 기법 개방 주소 지정(Open addressing): 해시 주소가 가리키고 있는 위치부터 시작하여 빈 위치를 찾을 때까지 순차적으로 그 이후의 위치들을 조사한다. 체인(Chaining): 오버플로 영역에 새로운 레코드를 저장하고 다른 레코드가 이미 점유하고 있는 해시 주소 영역의 포인터에 오버플로 영역의 주소를 지정하여 충돌을 해결한다. 다중 해싱(Multiple hashing): 충돌이 발생하지 않을 때까지 여러 개의 해시 함수를 적용한다. 충돌시 필요하면 개방 주소 지정 방법을 사용한다.

그림 15.9 버켓 번호들을 디스크 블록 주소들로 사상

해싱 화일(계속) 목표 주소 공간을 같은 크기의 버켓들로 구성하고, 각 버켓에는 다수의 레코드들을 유지함. 버켓은 디스크 블록 한 개나 연속적인 블록인 클러스터 한 개의 크기를 갖는다. 해시 키가 K 인 레코드는 해시 함수 i = h(K)에 의해 결정된 버켓 i 에 저장 가득 찬 버켓으로 새로운 레코드가 해시 될 경우 충돌이 발생되며 충돌된 레코드는 오버플로 버켓에 저장, 각 버켓에서 오버플로된 레코드들은 연결 리스트로 구성 단점 버켓의 수가 고정되어 있기 때문에 화일의 레코드수가 버켓 공간에 비해 너무 적거나(공간 낭비 초래) 너무 많으면(빈번한 충돌 발생) 문제가 발생한다. 해시 키에 따른 순차적 접근은 매우 비효율적이며 레코드의 정렬이 요구된다.

그림 15.10 체인 방법을 사용한 버켓 오버플로 처리

동적 및 확장 해싱 화일 정적 해싱은 해시 주소 공간이 고정되어 화일을 동적으로 확장하고 축소하는 것이 어렵다. 이 문제를 해결하기 위한 기법으로는 확장가능 해싱, 선형 해싱이 있다. 이런 해싱 기법들은 해시 함수 결과를 이진수로 표현할 수 있고, 이진수 표현을 기반으로 접근 구조를 구성한다. 이런 이진수 표현을 레코드에 대한 해시값이라 한다. 이진수 표현은 비트열로 구성된다. 레코드 해시값에서 선행하는 비트들의 값을 기반으로 레코드들을 버켓들에 분배한다.

동적 및 확장 해싱 화일(계속) 확장가능 해싱 디렉토리는 2d 개의 버켓 주소를 갖는 배열이다. 이때 d는 전역 깊이라 하며, 해시 값의 처음 d개 비트를 디렉토리 배열의 인덱스 값을 결정하는데 사용한다. 2d 개 디렉토리 엔트리들은 서로 다른 버켓 주소를 유지할 필요는 없다. 처음 d'개의 비트 값이 갖는 레코드가 하나의 버켓에 저장될 수 있으면 여러 디렉토리 엔트리가 같은 버켓 주소를 유지한다. 각 버켓내의 레코드가 기반으로 하는 비트 수 d'을 지역 깊이라고 한다. 지역 깊이 d'과 전역 깊이 d가 같은 버켓에서 오버플로가 발생할 경우 디렉토리 배열 내의 엔트리 수는 2배가 된다. 어떤 레코드를 삭제한 후, 모든 버켓에 대해 d > d' 인 경우 디렉토리 배열내의 엔트리 수는 절반이 된다. 대부분의 레코드 검색은 두 개의 블록 접근(디렉토리에 대한 블록 접근, 버켓에 대한 블록 접근)을 필요로 한다.

그림 15.11 확장가능 해싱 기법의 구조

정적 해싱 예제 h(John) = 000 h(Franklin) = 000 h(Alicia) = 010 h(Jennifer) = 001 h(Ramesh) = 111 h(Joyce) = 101 h(Ahmad) = 100 h(James) = 011 Jonhn B ………. 000 Franklin T ………. Jennifer S ………. 001 Alicia J 010 Franklin T ………. 011 James E………. Ramesh K………. 111

확장성 해싱 예제(1) h(John) = 000 h(Franklin) = 000 h(Alicia) = 010 Jonhn B ………. Franklin T ………. h(John) = 000 h(Franklin) = 000 h(Alicia) = 010 h(Jennifer) = 001 h(Ramesh) = 111 h(Joyce) = 101 h(Ahmad) = 100 h(James) = 011 1 1 1 2 Jonhn B ………. Franklin T ………. 00 2 01 10 1 11 Alicia J ………. 2 2 Jonhn B ………. Franklin T ………. 00 1 01 Jennifer S …….... Ramesh K ……… 10 2 11 Alicia J ………. 2

확장성 해싱 예제(2) h(John) = 000 h(Franklin) = 000 h(Alicia) = 010 Jonhn B ………. Franklin T ………. h(John) = 000 h(Franklin) = 000 h(Alicia) = 010 h(Jennifer) = 001 h(Ramesh) = 111 h(Joyce) = 101 h(Ahmad) = 100 h(James) = 011 00 01 2 Jennifer S …….... Joyce A ……… 10 11 2 Alicia J ………. 2 2 Ramesh K ………. 3 Jonhn B ………. Franklin T ………. 000 001 2 Jennifer S …….... Joyce A ……… 010 011 2 Alicia J ………. 100 101 2 Ramesh K ………. 110 111 3 Ahmad V ………. 3

RAID 기술을 이용한 병렬 디스크 접근 보조 기억 장치 기술의 성능과 신뢰도를 프로세서 기술의 수준으로 올려야 한다. 보조 기억 장치 기술의 주요한 발전은 RAID (Redundant Arrays of Inexpensive Disks)의 개발로 대표된다. RAID의 주요 목표는 메모리와 마이크로프로세서의 성능 향상과 균형을 맞출 수 있도록 디스크의 성능을 획기적인 비율로 향상시키는 데 있다.

RAID 기술(계속) 자연스러운 해결책은 여러 개의 작고 독립적인 디스크를 배열로 구성하여 하나의 고성능 디스크처럼 동작하도록 하는 것이다. 여기에는 디스크의 성능 향상을 위해 병렬성을 사용하는데, 이 개념을 데이터 스트라이핑이라 한다. 데이터 스트라이핑은 여러 개의 디스크가 하나의 크고 빠른 디스크처럼 보이도록 데이터를 다중 디스크로 투명하게 분산시킨다.

그림 15.12 데이터 스트라이핑. 화일 A가 네 개의 디스크에 스트라이핑 표 15.3 디스크 기술 동향

RAID 기술(계속) 신뢰성을 향상시키는 첫 번째 방법은 데이터를 두 개의 동일한 물리적 디스크에 중복해서 기록하는 반사(또는 그림자) 기법을 사용하는 것이다. 두 번째 방법은 디스크 오류 발생시 손실된 정보를 재구축하는 데 사용할 부가 정보를 저장하는 것이다. 여분의 정보를 계산하기 위해 패리티 비트나 해밍 코드 같은 특별한 코드를 포함한 에러 검출 코드를 사용한다. 중복된 정보를 디스크 배열상에 분산시키기 위해 몇 개의 디스크에 여분의 정보를 저장하는 방식과, 모든 디스크에 균등하게 여분의 정보를 저장하는 방식이 있다. 두 번째 방식이 더 좋은 부하 균등을 제공한다.

RAID 기술(계속) 비트 레벨 데이터 스트라이핑 : 데이터의 각 바이트를 비트들로 분할하여 비트들이 서로 다른 디스크에 분산함으로 더 작은 단위를 데이터 전송에 사용하는 방식이다. 블록 레벨 데이터 스트라이핑 : 데이터를 분산하는 단위로 화일의 블록을 사용하는 방식이다. 하나의 블록에 다수의 요청을 각 디스크에 의해 병렬로 처리할 수 있어서, I/O 요청 대기 시간이 줄어든다.

RAID 기술(계속) RAID의 구조는 데이터 분산(스트라이핑)의 단위와 여분의 정보를 계산하는 데 사용되는 패턴의 두 가지 요인의 조합 방법에 따라 서로 구별된다. RAID 레벨 0은 여분의 데이터를 갖지 않아서 데이터의 갱신이 중복되지 않으므로 가장 좋은 쓰기 성능을 가진다. RAID 레벨 1은 디스크들을 복사한다. RAID 레벨 2는 해밍 코드를 이용하여 메모리 형태의 여분 정보를 사용한다. 해밍 코드는 데이터의 구성 비트들의 서로 상이한 부분집합들에 대한 패리티 비트들을 포함한다. 레벨 2에서는 에러 검출과 교정이 가능하다. RAID 레벨 3은 어느 디스크에 오류가 발생했는지 파악할 수 있는 디스크 제어기를 사용함으로써 한 개의 패리티 디스크만을 사용한다. RAID 레벨 4와 5는 블록 레벨 데이터 스트라이핑을 이용하며, 레벨 5는 데이터와 패리티 정보를 모든 디스크에 분산시킨다. RAID 레벨 6은 두 개의 여분 디스크를 사용하여 두 개의 디스크까지의 오류에 대비하기 위해 Reed-Soloman 코드를 사용하는 소위 P + Q라는 여분 기법을 활용한다.

11.10.3 RAID의 구조와 레벨(2) 상황 조건에 따라 사용하는 RAID 구조는 다르다. 레벨 1은 로그 저장 같은 중요한 응용을 위해 사용한다. RAID 레벨 2 해밍 코드를 이용하여 메모리 형태의 여분 정보를 사용한다. 해밍 코드는 데이터의 구성 비트들의 서로 상이한 부분집합들에 대한 패리티 비트들을 포함한다. 레벨 2에서는 에러 검출과 교정이 가능하다. RAID 레벨 3과 5는 대용량의 데이터 저장을 위해 주로 사용되며, 그 중에서 레벨 3은 더 높은 전송률을 제공한다. 현재 가장 널리 사용되고 있는 RAID 기술은 스트라이핑을 지원하는 레벨 0, 반사 기능을 가진 레벨 1, 패리티를 위한 추가적인 디스크를 가진 레벨 5이다. 주어진 여러 응용을 위한 RAID 설정을 설계하기 위해서는 RAID의 레벨, 디스크의 수, 패리티 기법의 선택, 블록 레벨 스트라이핑을 위한 디스크 그룹핑 방법 등 여러 가지 사항을 고려해야 한다.

그림 15.13 여러 RAID의 레벨. Chen, Lee, Gibson, and Katz, Patterson(1994) ACM Computing Survey, Vol.26, No.2(June 1994)에서 인용

저장 영역 네트워크 현재 예전의 저장 장치보다 더욱 고성능인 저장 장치에 대한 요구가 매우 늘어나고 있다. 정적이고 고정된 데이터 센터 중심에서부터 더 유연하고 동적인 구조로의 전환이 필요하다. 따라서 대규모 조직체들은 저장 영역 네트워크 (Storage Area Networks :SANs)라고 부르는 개념으로 많이 옮겨가고 있다. SANs에서는 온라인 저장 주변장치들이 초고속 네트워크에 노드들로 구성되어 있고, 매우 유연한 방법으로 서버들에 연결되거나 분리될 수 있다. 이것은 저장 시스템들이 서버로부터 더 먼 거리에 위치할 수 있도록 해 주고, 서로 다른 성능과 연결 옵션들을 제공한다.

저장 영역 네트워크(계속) SANs의 장점: 광섬유 채널 허브들과 스위치들을 사용하여 서버들과 저장 장치들간의 유연한 다대다 연결 적절한 광섬유 케이블을 사용하여 서버와 저장 시스템 사이에 10km까지 거리가 떨어지는 것이 가능 새로운 주변장치와 서버들을 파열 없이 추가할 수 있도록 하는 더 우수한 분리 기능 SANs는 여러 업체들의 저장 옵션을 조합하고 저장 관리 소프트웨어와 하드웨어들의 진보된 표준을 취급해야 하는 등의 문제점을 가지고 있다.