데이터베이스 시스템 7판을 읽으며 간략하게나마 정리하는 글입니다.
이전 글 에서는 자기 디스크와 SSD를 중심으로 물리적 저장 장치의 특성을 살펴보고, RAID에 대하여 살펴보았다.
이번에는 기반 저장 장치 매체에 저장되는 데이터의 구성과 그 데이터에 어떻게 접근하는지에 관해 설명한다.
1. 데이터베이스 저장 장치 구조
자기 디스크와 SSD는 block 구조를 이용하는 저장 장치이다. 즉 데이터를 블록 단위로 읽거나 쓴다.
이에 반해 데이터베이스는 일반적으로 블록보다 훨씬 작은 크기인 레코드를 처리한다.
대부분의 데이터베이스는 레코드를 저장하기 위한 중간 계층으로 OS 파일을 사용하여 하부 블록의 세부 정보를 추상화 한다.
그러나 효율적인 접근과 데이터의 복구를 위해 가능하면 블록 구조를 계속 사용해야 한다.
레코드 집합이 있다면, 파일 구성에서 이러한 레코드를 어떻게 조직할지를 결정할 수 있다.
예를 들어, 어떤 키에 대해 정렬한 순서, 생성한 순서, 또는 임의 순서대로 레코드를 저장할 수 있는 것이다.
특정 행의 모든 속성을 함께 저장하는 것이 아니라, 특정 열의 모든 값을 함께 저장하는 것에 기반을 둔 데이터 저장 방법은 분석 질의 처리에서 매우 잘 동작하는 것으로 밝혀졌는데, 이를 열 지향 저장소(Column-oriented storage)라 부른다.
2. 파일 구성
하나의 데이터베이스는 내부적으로 기반 OS가 관리하는 많은 다른 파일에 대응한다.
이 파일은 디스크 안에 영구적으로 저장된다. 파일(File)은 일련의 레코드로서 논리적으로 구성된다.
이러한 레코드는 디스크 블록상에 대응된다.
운영체제에 있는 기본적인 구조로 파일을 제공하는 파일 시스템(file system)이 있다고 가정한다.
블록(block)이라 불리는 고정 길이 저장 단위로 각 파일을 논리적으로 분할한다.
여기서 block은 저장 장소 할당과 데이터 전송의 단위이다. 대부분의 DB는 4~8KB의 블록 크기를 사용하지만, 많은 데이터베이스 인스턴스가 생성될 때 명시하는 것 또한 허용한다.
한개의 block은 여러 레코드를 포함한다. 여기서 block보다 더 큰 레코드는 없다고 가정한다.
추가로, 단일 블록은 각 레코드를 완전히 포함해야 한다. 즉 이는 어떤 레코드도 한 블록에 부분적으로 포함되거나, 또 다른 레코드에 부분적으로 포함되지 않는다는 것을 의미한다.
이는 데이터에 접근하는 것을 단순화 하고, 접근 속도를 향상시킨다.
관계형 DB에서 서로 다른 릴레이션의 튜플은 일반적으로 다른 크기를 가진다. 데이터베이스에 파일을 매핑하기 위한 한가지 방법은, 여러 파일을 사용하면서 주어진 파일 내에 고정 길이 레코드만 저장하는 것 이다.
대안으로 파일을 구조적으로 저장하여 가변 길이 레코드를 저장할 수 있도록 하는 것이다.
하지만, 고정 길이 레코드로 구성된 파일은 가변 길이 레코드 파일보다 구현하기 더 쉽다.
2 - 1) 고정 길이 레코드
다음과 같은 학교의 instructor 레코드 파일을 생각해보자.
위 레코에서, 각 문자는 1바이트, numeric(8, 2)는 8바이트를 차지한다고 하자.
ID, Name, dept_name과 같은 속성에 대한 다양한 크기의 바이트를 할당하는 대신에 각 속성을 저장할 수 있는 최대 크기의 바이트 수를 할당한다.
instructor 레코드의 길이는 53바이트 이다.
이러한 고정 길이 파일을 구성하는 간단한 방법은 첫번째 레코드를 위해 53바이트를 사용하고, 두번째 레코드에도 53바이트를 사용하면 된다.
하지만 이런 방식은 2가지 문제점이 있다!
1) 만약 블록의 크기가 53의 배수가 되지 않는다면, 몇몇 레코드는 블록 경계를 넘게 된다.
즉 레코드 일부분은 어떤 블록에 저장되고, 나머지 부분은 다른 블록에 저장된다. 이렇게 되면 읽고 쓰기 위해서 두 블록에 모두 접근해야 한다.
2) 구조에서 레코드를 삭제하기가 어렵다.
삭제할 레코드가 차지하는 공간은 그 파일의 다른 레코드로 채워야 한다. 아니면 그 공간을 무시할 수 있도록 레코드를 삭제했다는 표시를 해야 한다.
처번째 문제점은 해결하려면, 한 블록에 완전히 채울 수 있는 만큼만 레코드를 할당해야 한다.
이 수는 블록 크기를 레코드 크기로 나눠서 쉽계 계산할 수 있는데, 소수부분은 무시한다. 각 블록의 남은 바이트는 사용하지 않는다.
한 레코드를 삭제할 때, 해당 레코드 뒤에 있는 모든 레코드를 바로 전 레코드가 차지한 공간으로 이동시킨다.
이 방법에서 많은 수의 레코드가 이동해야 하는 문제가 있다.
삭제된 레코드의 빈 공간을 재우기 위해 레코드를 이동하게 되면 부차적인 블록 접근이 필요해서 바람직하지 않다.
레코드 삽입이 레코드 삭제보다 더 자주 일어나기 떄문에 삭제한 레코드가 있었던 공간을 비워두고, 재사용하기 전 다음에 삽입할 레코드를 기다리게 할 수 있다.
삭제한 레코드를 표시하는 것만으로는 충분하지 않을 것 이다.
왜냐하면 삽입할 레코드가 있을 때 이러한 이용 가능 공간을 찾기가 어렵기 때문이다. 따라서 추가적인 구조가 필요할수 있습니다.
파일 앞부분에 일부 바이트를 할당해 파일 헤더(file header)를 만든다.
여기에 삭제된 첫 번째 레코드의 주소를 저장해둔다. 이 첫번째 레코드를 사용해서 이용 가능한 두번째 레코드의 주소를 저장하고, 이런 식으로 계속 진행하면 된다.
직관적으로, 이렇게 저장한 레코드 주소는 레코드의 위치를 가리키므로 해당 주소를 포인터로 생각할수 있다.
그래서 이 삭제한 레코드는 연결 리스트를 형성하는데 종종 자유 리스트(free list)로 언급하기도 한다.
새로운 레코드를 삽입할때는 헤더가 가리키는 레코드를 사용한다. 그 다음 헤더의 포인터를 다음 이용 가능한 레코드를 가리키도록 바꾼다.
이용 가능한 공간이 없다면 파일의 끝에 레코드를 추가한다.
고정된 길이의 레코드를 저장한 파일의 삽입과 삭제는 구현이 간단하다.
하지만 가변길이의 레코드는 파일에서 삭제한다면, 새로 삽입하는 레코드의 크기가 삭제된 레코드의 빈 공간보다 커서 맞지 않을 수 있다.
또는 작아서 공간의 일부만 채울지도 모른다.
2 - 2) 가변 길이 레코드
가변길이 레코드(variable-length record)가 필요한 몇 가지 상황이 있다.
대표적으로 문자열과 같은 가변 길이 필드가 있기 때문이다.
또 다른 이유는 배열 혹은 다중 집합(multiset)과 같은 반복적인 필드를 포함하는 레코드 유형과 파일 내에 여러 레코드 유형의 존재가 있다는 점 입니다.
가변 길이 레코드는 다음 2가지 문제를 해결해야 한다.
1) 속성이 가변 길이인 경우에도 개별 속성을 쉽게 추출할 수 있는 방식으로 하나의 레코드를 표현하는 방법
2) 블록 내의 레코드를 쉽게 추출할 수 있도록 블록 내에 가변 길이 레코드를 저장하는 방법
가변 길이의 속성을 지닌 레코드는 일반적으로 두 부분으로 구성된다.
처음 부분은 고정된 길이의 정보를 갖는 부분, 그 다음 부분은 가변 길이 속성의 내용으로 구성되어있다.
varchar 타입과 같은 가변 길이의 속성은 레코드의 맨 처음 부분에서 [offset, length]의 쌍으로 표현된다.
따라서 레코드의 맨 처음 부분은 각 속성이 고정 길이인지? 가변 길이인지에 따라 다르게 저장한다.
레코드의 앞부분에 있는 고정 길이 부분 이후에 가변 속성값을 연속적으로 저장한다.
위 그림을 보면 첫 3개의 속석인 ID, name, dept_name은 가변 길이의 문자열이며, 레코드의 네번째 속성인 salary는 고정 길이 숫자이다.
offset, length을 4바이트를 사용하여 저장하고, 이어서 8바이트로 salary 속성을 짱한다.
이후 어떤 레코드의 속성이 Null값을 갖는지 표현하는 null bitmap의 사용을 나타낸다.
일한 특정한 레코드에서 값이 Null이면 비트맵의 4번째 비트는 1로 설정되고, 12 ~ 19 바이트 부분의 값이 무시된다.
블록의 가변 길이 레코드를 저장하는 문제점에 대하여 알아보자.
슬롯 페이지 구조(slotted-page structure)는 블록 내의 레코드를 구성하는 데 흔히 사용된다.
각 블록의 시작에는 다음의 정보를 포함하는 헤더가 있어야 한다.
- 헤더에 있는 레코드 엔트리의 총 수
- 블록에서 빈 곳의 끝
- 각 레코드의 위치와 크기를 포함하고 있는 엔트리 배열
실제 레코드는 블록의 끝에서부터 인접하게 할당된다. 블록에서 빈 곳은 헤더 배열에 있는 마지막 엔트리와 첫 번째 레코드 사이에서 연속적이다.
어떤 한 레코드를 삽입하면 빈곳 끝에 이 레코드를 위한 공간을 할당하고 이 레코드의 크기와 위치를 포함하는 엔트리를 헤더에 추가한다.
레코드를 삭제하면 해당 레코드의 공간을 비우고 관련 엔트리를 삭제한 상태(예를 들면 -1)를 명시한다.
추가로, 삭제한 레코드 앞쪽에 있는 레코드를 이동한다. 그래야 모든 빈곳이 헤더 배열의 마지막과 엔트리와 첫번째 레코드 사이에 있게된다.
또한 빈공간 끝을 가리키는 포인터를 헤더에서 상황에 맞게 갱신해야 한다.
(블록의 크기는 보통 4~8KB이다.)
슬롯페이지의 레코드 데이터를 직접 가리키는 포인터는 없도록 해야 한다.
그 대신 포인터는 레코드의 실제 위치를 포함하고 있는 헤더안에 있는 엔트리(레코드 슬롯)를 가리키도록 해야 한다.
이를 간접 접근(Indirect access)라고 합니다.
간접 접근을 하는 이유는, 레코드 데이터 삭제 시 레코드 데이터는 빈 자리를 메우기 위해 한칸씩 이동하는데, 이러면 외부에서(예: 인덱스 등) 레코드를 가리키는 포인터 주소를 전부 일일이 수정해줘야 하는 번거로움이 생깁니다.
반면 레코드 데이터 위치가 변경돼도 이를 레코드 슬롯에만 반영하면 레코드 데이터 위치가 변경되는 것에 상관없이 외부에서 레코드 데이터에 항상 정확하게 접근할 수 있어 일반적으로 DBMS는 간접 접근 방식을 사용합니다.
이러한 수준의 우회(redirection)는 레코드에 대한 간접 포인터를 지원하면서 블록의 공간을 단편화하는 것을 막기 위해 레코드를 이동할 수 있도록 해준다.
데이터베이스와 디스크 구조
저장 공간은 크게 휘발성 저장 공간과 비휘발성 저장공간으로 나뉩니다. 휘발성 저장 공간인 메모리는 전원 공급이 차단되면 가지고 있는 데이터가 모두 사라지기 때문에, 데이터베이스는 전원
velog.io
2 - 3) 대형 객체 저장 방법
엄청 큰 데이터를 종종 저장할 일이 있다. SQL은 따라서 blob, clob을 지원한다.
대부분의 RDBMS는 내부적으로 한 레코드의 크기가 한 Block의 크기를 넘지 않도록 제한한다.
따라서 대형 객체를 별도의 대형 객체로 저장한 후, 그 다음 해당 대형 객체에 대한 포인터를 해당 객체를 포함하는 레코드에 저장한다.
대형 객체(Large Object)를 데이터베이스가 관리하는 파일 시스템 영역에 파일로 저장하거나, 데이터베이스가 저장하고 관리하는 파일 구성으로 저장할 수 있다.
후자의 경우 데이터베이스 내 대형 객체를 B+ tree 파일 구성을 통해서 선택적으로 표현할 수 있다.
B+ tree는 그 객체 내의 임의 위치에 대한 효율적인 접근을 가능하게 한다.
하지만 데이터베이스에 매우 큰 객체를 저장하는 데서 오는 성능에 대한 몇가지 이슈가 있다.
1) 대형 객체를 데이터베이스 인터페이스를 통해서 접근하는것이 효율적인가?
2) 데이터베이스 백업의 크기 (따라서 일반적으로 외부의 파일시스템에 저장한다)
이런 경우 애플리케이션은 파일 이름을 데이터베이스 내 레코드의 속성에 저장하게 된다.
3. 파일에 레코드를 구성하는 방법
릴레이션은 레코드 들의 집합이다.
파일에 레코드를 구성하는 몇가지 가증한 방법은 다음과 같다.
▶ 힙 파일 구성(Heap file organization)
파일 안에 레코드를 위한 공간만 있다면 임의의 레코드는 어디든지 놓일 수 있다. 레코드의 순서는 없다.
일반적으로 각 릴레이션은 하나의 파일 또는 파일 집합으로 되어 있다.
▶ 순차 파일 구성(Sequential file organization)
레코드는 "검색 키(search key)"의 값에 따라 순차적 순서대로 저장된다.
▶ 다중 테이블 군집 파일 구성(Multitable clustering file organization)
일반적으로 각 릴레이션의 레코드를 저장하기 위해 독립된 파일이나 파일의 집합을 사용한다.
그러나 다중 테이블 군집 파일 구성에서 특정 조인 연산의 비용을 줄이기 위해 여러 다른 릴레이션의 레코드가 같은 파일에 저장되고, 실제로도 파일 내의 같은 블록에 저장된다.
▶ B+ - Tree 파일 구성(B+ - tree file organization)
전통적인 순차 파일 구성은 레코드의 순서를 변경할 수 있는 삽입, 삭제 및 갱신 작업이 있더라도 순차적인 접근만 제공한다.
따라서 삽입, 삭제, 갱신 드의 작업이 많을수록 정렬 접근의 호율성이 저하된다.
B+ - tree를 이용하면 삽입, 삭제 또는 갱신 작업이 많은 경우에도 레코드에 대한 매우 효율적인 접근을 지원한다.
▶ 해쉬 파일 구성(Hashing file organization)
해시 함수는 각 레코드의 일부 속성에 대해 계산된다. 해시 함수의 결과는 해당 레코드가 파일의 어느 블록에 놓일지를 나타낸다.
3 - 1) 힙 파일 구성 (free-space map)
힙 파일 구성에서 레코드는 릴레이션에 해당하는 파일의 어디에나 저장될 수 있다.
특정 위치에 있다면 해당 레코드를 일반적으로 이동하지 않는다.
레코드를 파일에 삽입할때 위치를 선택하는 한가지 옵션은, 항상 파일의 끝부분에 추가하는 것 이다.
그러나 레코드를 삭제하면서 만들어진 빈 곳을 사용하여 새 레코드를 저장하는 것이 좋다.
따라서 데이터베이스 시스템은 파일의 모든 블록을 순차적으로 검색하지 않고도 빈 곳이 있는 블록을 효율적으로 찾을 수 있어야 한다.
대부분의 데이터베이스 시스템은 free-space map 이라고 하는 공간을 효율적으로 사용하는 데이터 구조를 사용하여 레코드를 저장할 여유공간이 있는 Block을 찾는다.
free-space map은 일반적으로 릴레이션에서 각 블록에 대해 1개의 엔트리를 포함하는 배열로 표현된다.
각 엔트리는 비율 f로 표현하는데, 이는 최소 비율 f만큼이 해당 블록 공간에 비어있어야 한다는 것을 뜻한다.
레코드를 삽입, 삭제 또는 그 크기를 변경할 때마다 엔트리 값에 영향을 줄 만큼 점유 비율이 변경되면 free-space map에서 엔트리를 갱신한다.
16개의 블록이 있는 파일에 대한 free-space map 예시를 살펴보자.
예를 들어 7이라는 값은 해당 블록에서 최소 7/8의 공간이 비어있다는 것을 의미한다.
새로운 레코드를 저장할 블록을 찾기 위해, 데이터베이스는 여유 공간 맵을 스캔하여 해당 레코드를 저장할 충분한 여유 공간이 있는 블록을 찾을 수 있다.
만약 적당한 블록이 없다면, 릴레이션에 새로운 블록을 할당한다.
대용량 파일을 위해 2계층 이상의 free-space map 을 사용하기도 한다.
맵의 엔트리를 갱신할 때마다 free-space map 을 디스크에 쓰는 것은 비용이 많이드는 작업이다. 따라서 일정 주기를 두고 Write한다.
이로 인해 디스크의 free-space map 이 최신이 아닐수도 있으며, 여유 공간이 없는데 있다고 할 수 있다.
이러한 오류는 Block을 가져올때 감지되며, 다른 Block을 찾기 위해 여유 공간 맵에서 추가로 검색하여 이를 해결할 수 있다.
3 - 2) 순차 파일 구성 (sequential file)
레코드의 효율적인 처리를 위해 일부 검색 키를 기반으로 정렬한 sequential file을 설계한다.
검색 키(search key)는 특정 속성이나 속성들의 집합이다.
이때 검색키가 반드시 주키이거나 수퍼키일 필요는 없다.
검색 키 순서로 빠른 탐색을 위해 레코드를 포인터로 연결한다. 각 레코드는 다음 레코드를 가리키고 있다.
더욱이 순차 파일을 처리하는 동안 블록의 접근 수를 최소화 하기 위해 레코드를 검색 키 순서에 가깝도록 물리적으로 저장한다.
다음 예시를 보자.
instructor 레코드의 순차 파일을 보여준다. ID를 검색키로 정렬되어있다.
그러나 레코드를 삽입하고 삭제한 대로 물리적 순서를 유지하기는 어렵다. 왜냐하면 한번의 삽입이나 삭제 떄문에 많은 레코드를 이동하는 것은 비용이 많이 들기 때문이다.
따라서 삽입을 위해 다음 규칙을 적용한다.
1) 검색 키 순서로 볼때, 삽입할 레코드 바로 앞에 위치하는 레코드를 파일에서 찾는다.
2) 찾은 레코드와 같은 블록 내에 빈 레코드가 있다면 거기에 새로운 레코드를 삽입한다. 그렇지 않으면 overflow block에 새로운 레코드를 삽입한다. 어느 경우든 키 순서로 연결하기 위해 포인터를 조정한다.
다음 그림은 새로운 레코드인 (32222, Verdi, Music, 48000)의 삽입 이후 구조를 보여준다.
이러한 방법은 일반적으로 잘 동작하지만, 결국 검색 키 순서와 물리적 순서 사이의 일치를 시간이 지나면서 완전히 잃어버린다.
이런 경우 다시 물리적으로 순차적인 순서가 되도록 재구성(reorganized)해야 한다.
이러한 재구성은 작업량이 적을때 진행해야 한다.
3 - 3) 다중 테이블 군집 파일 구성 (multitable clustering file organization)
많은 RDBMS는 각 릴레이션을 독립된 파일, 또는 파일 집합에 저장한다.
이러한 설계에 따라 각 파일 및 결과적으로 각 블록에는 하나의 릴레이션의 레코드만 저장한다.
그러나 일부의 경우 단일 블록에 여러 릴레이션의 레코드를 저장하는것이 유용할 수 있다.
우선 다음 query를 살펴보지.
select dept_name, building, budget, ID, name, salary
from department natural join instructor위 쿼리는 department와 instructor 릴레이션의 join을 수행한다.
이상적으로 레코드를 인덱스를 통해 찾으며, 레코드는 디스크에서 메인메모리로 전달된다.
최악의 경우 레코드가 각각 다른 블록에 있어 질의에 필요한 각 레코드에 대해 블록 읽기를 매번 수행해야 할 수 있다.
예를 들어 다른 블록에 있는 department, instructor 릴레이션은 다음과 같다.
이를 효율적으로 실행하기 위한 다중 테이블 군집 파일은 다음과 같다.
특정 dept_name에 대한 모든 instructor 튜플을 해당 dept_name에 대한 department 튜플 가까이에 저장한다.
두 릴레이션을 dept_name 키에 대하여 군집한다고 말할 수 있다.
이러한 구조는 Join을 효율적으로 처리하도록 한다. department의 튜플을 읽을때, 해당 튜플이 포함된 블록 전체가 메로리에 복사된다.
필요한 instructor 튜플은 department 튜플 근처에 저장되기 때문에 효율적으로 처리가 가능하다.
만약 하나의 블록에 들어가지 못하게 된다면, 남아있는 레코드는 근처에 있는 추가적인 블록에 저장된다.
multitable clustering file organization은 각 블록에 두개 혹은 그 이상의 릴레이션에 관련되는 레코드를 저장하는 파일 구성이다.
군집 키(cluster key)는 함께 저장되는 레코드를 정의하는 속성이다.
다만 다중 군집 테이블 구성은 Join처리를 빠르게 수행하지만, 다른 형태의 쿼리는 느려지는 결과를 초래할 수 있다.
따라서 다중 군집 테이블 구성을 신중하게 사용하면 질의 처리를 할 때 상당한 성능 향상을 얻을 수 있다.
3 - 4) 분할
릴레이션의 레코드를 더 작은 릴레이션으로 분할하여 따로 저장할 수 있다.
이러한 테이블 분할(table partitioning)은 일반적으로 속성값을 기반으로 수행된다.
이러한 분할을 사용하면, 예를 들어 이전에는 단순히 transaction 릴레이션 전체를 대상으로 데이터를 select 했다면,
테이블을 연도 별로 나누어 19년도 대상의 릴레이션만을 조사하여 데이터를 찾아올 수 있다.
또한 주로 사용할 19년도는 SSD에 저장해두고, 이전 년도의 비교적 잘 사용하지 않는 18년도 데이터는 자기 디스크에 나누어 저장할 수 있게된다.
4. 데이터 사전 저장소
RDBMS는 릴레이션 스키마 같은 릴레이션에 대한 데이터 또한 유지해야 한다.
"데이터에 대한 데이터를" 메타데이터(metadata)라고 부른다.
관계형 스키마와 릴레이션에 대한 다른 메타데이터는 데이터 사전(data dictionary) 혹은 시스템 카탈로그(system catalog)라 부르는 구조에 저장된다.
시스템이 저장해야 하는 정보의 종류는 다음과 같다.
- 릴레이션 이름
- 각 리레이션 속성의 이름
- 속성의 도메인과 길이
- 데이터베이스에 대해 정의한 뷰의 이름과 이 뷰에 대한 정의
- 무결성 제약 조건
또한 사용자에 대한 정보도 유지한다.
더욱이 데이터베이스는 각 릴레이션의 튜플 수, 각 속성에 대해 서로 다른 속성값의 수와 같은 릴레이션 및 속성에 대한 통계 데이터를 저장한다.
데이터 사전은 릴레이션의 저장 구성(힙, 순차, 해시...)과 각 릴레이션이 저장된 위치도 기록할 수 있다.
- 릴레이션을 OS 파일에 저장한다면 사전은 각 릴레이션을 포함하고 있는 파일의 이름을 기록한다.
- 데이터베이스가 모든 릴레이션을 하나의 파일에 저장한다면, 사전은 각 릴레이션의 레코드를 포함하는 블록을 연결리스트 와 같은 자료 구조에 기록할 수 있다.
또한 인덱스에 대한 정보도 저장하게 된다.
시스템 메타데이터에 자주 접근하기 때문에 대부분의 데이터베이스는 매우 효율적으로 접근할 수 있는 인메모리 데이터 구조로 해당 메타데이터를 읽어온다.
이러한 메타데이터를 읽어오는 것은 데이터베이스가 질의처리를 시작하기 전에 먼저 수행된다.
5. 데이터베이스 버퍼
디스크에 있는 데이터에 접근하는 것은 메모리에서 가져오는것 보다 훨씬 느리다.
RDBMS은 디스크와 메모리 사이에 블록의 전송 수를 최소화하는 것이 된다.
디스크 접근을 줄이는 한가지 방법은 메인 메모리에 가능한 많은 블록을 유지하는 것 이다.
이러면 찾아올 데이터가 이미 메모리상에 있을 확률을 최대화 하여 디스크 접근을 할필요 없도록 하는 것 이다.
메인 메모리에 모든 블록을 유지하는 것은 불가능 하므로, 메인 메모리에서 블록을 저장하기 위해 이용할 수 있는 공간 할당을 관리할 필요가 있다.
Buffer는 디스크 블록의 복사본을 저장하기 위해 이용할 수 있는 메인 메모리의 일부분이다.
디스크 상의 복사본은 버퍼에 있는 버전보다 더 오래된 버전일 수 있다.
이러한 버퍼 공간의 할당을 관리하는 시스템을 버퍼 관리자(buffer manager)라고 한다.
5 - 1) 버퍼 관리자
RDBMS는 디스크로부터 block을 가져올때 버퍼 관리자를 호출한다.
버퍼 관리자는 해당 블록이 이미 있다면 메인 메모리의 블록 주소를 요청한 프로세스에 전달한다.
블록이 없다면 먼저 버퍼에 블록을 저장하기 위한 공간을 할당하는데, 공간을 만들기 위해 메모리에 있는 블록을 디스크로 보내기도 한다.
디스크로 보내진 블록은 디스크에 쓰인 가장 최근 것과 비교해서 변경된것이 있으면 다시 디스크에 write된다.
그다음 버퍼 관리자는 디스크로부터 요구된 블록을 버퍼에 읽어와서 메인 메모리의 블록 주소를 해당 process에 전달한다.
버퍼 관리자의 이런 내부 조치는 디스크 블록을 요청한 프로그램은 모르게 진행된다.
5 - 1 - 1) 버퍼 교체 전략
버퍼로 새로운 block을 읽어오기 전에 빈 공간이 없다면, 블록 하나를 버퍼에서 제거해야 한다.
대부분의 OS는 LRU(least recently used) 방식을 사용한다.
즉, 최근에 가장 적게 참조된 블록을 디스크에 다시 쓰고 제거한다.
5 - 1 - 2) 버퍼에 고정된 핀 블록
블록을 버퍼로 가져온 후 process는 버퍼에서 해당 블록의 내용을 읽을 수 있다.
어떤 process가 블록을 읽고 있는 동안, 동시 프로세스(concurrent process)가 그 블록을 제거하고 다른 블록으로 교체한다면 이전에 오래된 블록의 내용을 읽던 다른 프로세스는 부정확한 데이터를 보게된다.
따라서 process가 버퍼로부터 블록 데이터를 읽기 전에 block을 제거할 수 없도록 하는 것이 중요하다.
이를 위해 process는 block을 고정시키는 핀(pin) 연산을 실행한다.
데이터 읽기가 끝나면 process는 고정을 제거하는 언핀(unpin) 연산을 실행하여 필요할 때 블록을 제거할 수 있도록 해야 한다.
만약 버퍼의 모든 block이 pin된다면 블록을 제거할 수 없으며, 다른 블록을 버퍼로 가져올 수도 없다.
이 경우 데이터베이스는 더 이상의 처리를 수행할 수 없다.
5 - 1 - 3) 버퍼에 대한 공유 및 독점적 잠금
데이터베이스 버퍼 관리자는 process가 버퍼에 대한 공유 및 독점적 잠금을 얻을 수 있도록 해준다.
버퍼 관리자가 제공하는 잠금 시스템은 데이터베이스 프로세스가 블록에 접근하기 전에 공유 모드(shared mode) 또는 독점적 모드(exclusive mode)에서 버퍼 블록을 잠금하고 접근이 완료된 후 나중에 잠금 해제할 수 있도록 한다.
잠금 규칙은 다음과 같다.
1) 임의의 수의 process가 동시에 어떤 블록에 대한 shared lock을 가질 수 있다.
2) 한번에 하나의 process만 exclusive lock을 얻을 수 있으며, 더 나아가 process가 독점적 잠금을가질 때 다른 process는 블록에 대한 shared lock을 가질수 없다.
따라서 어떤 다른 프로세스도 버퍼 블록에 대한 잠금이 없을때만 exclusive lock을 얻을 수 있다.
3) 블록이 이미 공유, 독점적 모드의 Lock 상태일때, 다른 프로세스가 독점적 lock을 요청하면 이전의 모든 lock이 해제될 때까지 해당 블록에 대한 요청을 보유 상태로 유지한다.
4) 블록이 잠금 상태가 아니거나 이미 공유 잠금인 상태에서 프로세스가 해당 블록에 대한 공유 잠금을 요청하면 그 공유 잠금은 허용된다.
하지만 독점적 Lock을 가지는 경우, 해당 독점lock을 해제한 후에만 공유 잠금을 부여할 수 있다.
5) 블록에 대한 작업을 수행하기 전 process는 pin작업을 해야한다. Lock은 이후 획득되며 block을 unpin하기 전에 Lock을 해제해야 한다.
6) 버퍼 블록에서 데이터를 읽기 전에 process는 공유 lock을 얻어야 한다.
7) 버퍼 블록의 내용을 갱신하기 전에 프로세스는 블록에 대한 독점적 lock을 얻어야 한다. 갱신 완료 후 Lock을 해제한다.
이를 요약하면
다른 process가 블록을 읽는 동안 블록을 갱신할 수 없고, 반대로 다른 process가 블록을 갱신하는 동안 블록을 읽을 수 없도록 한다.
위 규칙은 안전한 버퍼 접근을 위해 필요하다.
5 - 2) 버퍼 교체 전략
버퍼에서 블록을 교체하는 방법의 목적은 디스크 접근을 최소화 하기 위해서이다.
이를 위해 OS는 앞으로 참조될 것을 예상하기 위해 과거의 참조된 패턴을 이용한다.
일반적으로 최근에 참조된 블록은 다시 참조될 가능성이 있다. 따라서 어떤 블록을 교체해야 한다면 최근에 가장 적게 참조된 블록을 교체한다. 이런 방식을 LRU 버퍼 교체 방법이라 부른다.
LRU는 OS에서는 받아들일만 한 교체 방식이다. 그러나 RDBMS는 향후 참조 패턴을 OS보다 좀더 정확하게 예상할 수 있다.
데이터베이스는 사용자 요구 연산을 수행하기 위해 필요한 각 절차를 확인함으로써 어느 블록을 앞으로 필요로 할지 종종 미리 결정할 수 있다. 이는 가까운 미래를 내다보는 느낌이다.
향후 접근할 블록에 대한 정보를 사용하여 LRU 방법을 어떻게 향상시키는지 알아보자.
다음의 SQL문의 처리를 생각해보자.
select *
from instructor natural join department;다음 의사코드가 위 쿼리를 처리하기 위한 전략을 선택했다고 가정하자.
별도의 파일에 각각 instructor, department 두 릴레이션을 저장해두었다고 가정하자.
이 예시에서는 instructor 튜플을 하나 처리하고 나면 다시 필요하지 않다는 것을 알 수 있다.
그러므로 일단 instructor 튜플의 전체 블록 처리가 완료되면 이것이 가장 최근에 사용되었더라도 더는 메인 메모리에 있을 필요가 없다.
버퍼 관리자는 instructor의 마지막 튜플이 처리되자마자 instructor 블록이 차지하고 있던 공간을 메모리에서 비우도록 지시해야 한다.
이런 버퍼 관리를 즉시 전달(toss-immediate) 방법이라 한다.
이제 instructor 릴레이션의 각 튜플에 대해 department 튜플의 모든 블록을 한번씩 조사해야 한다.
department 릴레이션의 한 블록에 대한 처리를 마치게 되면, 모든 다른 department 블록을 처리할 때 까지 그 블록에 다시 접근하지 않는다.
그러므로 최근에 가장 많이 사용된 department 블록은 재참조할 마지막 블록일 것이고, 최근에 가장 적게 사용된 department 블록은 다음에 참조할 블록일 것이다.
이는 LRU의 가정돠 반대된다. 실제로 블록 교체를 위한 최적의 전략은 MRU(most recently used) 방법이다.
department 블록을 버퍼로부터 제거해야 한다면, MRU 방법은 최근에 가장 많이 사용된 블록을 선택한다.
MRU 방식이 우리의 예에서 정확히 작동하려면, 시스템은 현재 처리하고 있는 department 블록을 Pin해야 한다.
마지막 department 튜플을 처리한 후 pin 블록을 unpin하면 해당 block이 최근 가장 많이 사용한 블록이 된다.
또한 버퍼 관리자는 데이터 사전이나, 인덱스를 사용하여 찾으려는 하는 대상 파일보다 종종 더 많이 접근하기 때문에 해당 블록을 메모리에서 제거하면 안된다.
5 - 3) 쓰기 및 복구의 재정렬
데이터베이스 버퍼를 사용하면 쓰기가 수행된 순서와 다른 순서로 메모리 내에서 쓰기를 수행한 후 나중에 디스크에 출력할 수 있다.
파일 시스템 또한 쓰기 작업을 정기적으로 재정렬한다.
이러한 재정렬은 시스템 충돌 발생 시 디스크에 있는 데이터가 비일관되게 만들수 있다.
이러한 손상을 방지하기 위해 예전 세대의 파일 시스템은 시스템 재시작시 file system consistency check를 수행하여 데이터의 일관성을 확인하였고, 일관되지 않은 경오 복구하였다.
최신 세대의 파일 시스템은 write 작업이 수행되는 순서로 로그를 저장하기 위한 디스크를 할당한다.
이를 Log Disk라고 부른다.
로그에는 각 write에 관해 그 쓰기를 수행했던 순서대로 사용한 block 번호와 사용한 데이터를 포함한다.
로그 디스크에 대한 모든 접근이 순차적이므로 기본적으로 탐색 시간이 필요 없으며, 연속된 여러 블록을 한꺼번에 쓸 수도 있다.
따라서 로그 디스크에 쓰는 것이 디스크에 임의 순서로 쓰는것보다 몇배나 빠르다.
이전과 같이 디스크의 실제 위치상에도 데이터를 기록해야 하지만 이것은 나중에 해도된다. 디스크 암의 이동을 최소화하기 위해 쓰기 순서를 변경할 수 있기 때문이다.
실제 디스크 위치로 일부 쓰기 작업을 완료하기 전에 시스템이 충돌하면, 시스템 백업 시 로그 디스크를 읽어 완료되지 않은 쓰기 작업을 찾아 수행한다. 쓰기 작업을 모두 마치면 로그 디스크에 해당 레코드를 삭제한다.
이러한 로그 디스크를 지원하는 파일 시스템을 저널링 파일 시스템(journaling file system)이라고 한다.
저널링 파일 시스템은 별도의 로그 디스크 없이도 구현되며, 데이터와 로그를 같은 디스크 보관할수도 있다.
그러나 일반적인 응용 프로그램에서 수행한 쓰기 작업은 로그 디스크에 기록되지 않는다.
대신 데이터베이스 시스템은 자체적 로깅 방법을 구현하며, 이는 쓰기 작업이 재정렬된 경우에도 오류 발생 시 데이터베이스의 내용을 안전하게 복구할 수 있도록 해준다.
6. 열 지향 저장소
DB는 전통적으로 한 레코드에 한 튜플의 모든 속성을 함께 저장하고, 앞에서 본것처럼 하나의 파일에 튜플을 저장한다.
이러한 방식을 행 기반 저장소(row-oriented storage) 라고 한다.
이와 반대로 열 지향 저장소(column-oriented storage)는 릴레이션의 각 속성별로 저장하게 된다.
다음과 같이 말이다.
가장 간단한 열 지향 저장소는 각 속성을 펼도의 파일에 저장하는 방식이다. 게다가 각 파일은 그 크기를 줄이기 위해 압축된다.
만약 query가 테이블의 i번째 행의 전체 내용에 접근한다면, 각 열의 i번째 위치에 있는 값을 검색하여 행을 재구성한다.
이처럼 열 지향 저장소는 단일 튜플의 여러 속성을 읽어 오기 위해 여러번의 I/O 연산을 요구하는 단점이 있다.
=> 릴레이션에 있는 적은 수의 튜플로부터 다수의 속성을 추출하는 쿼리에는 부적합하다.
열 지향 저장소는 릴레이션의 많은 수의 튜플에 접근하되, 일부 속성에만 자주 접근하는 데이터 분석 쿼리에 적합하다.
이유는 다음과 같다.
6 - 1) 장점
▶ 감소한 I/O
많은 수의 속성을 가진 릴레이션에서 아주 소수의 속성에만 질의가 접근할 필요가 있으면, 나머지는 메모리로 읽어올 필요가 없다.
이와 반대로, 행 지향 저장소는 관련 없는 속성까지 메모리로 읽어오게 된다.
▶ 향상된 CPU 캐시 성능
질의 처리기가 특정 속성의 내용을 읽어 올 때, 최신 CPU 구조를 사용하여 캐시 라인(cache line)이라고 하는 여러 연속된 바이트가 메모리에서 CPU 캐시로 읽힌다.
만약 이후에 이 바이트에 접근하는 경우가 있다면, 메인 메모리가 아닌 캐시에서 읽게되어 매우 빠르다.
이때 만약 질의에서 필요하지 않은 속성값이 포함된 인접한 바이트까지 캐시로 가져온다면, 다른 데이터를 저장하는 데 사용될 수 있는 캐시 공간과 메모리 대역폭이 낭비된다.
그러나 열 지향 저장소는 이러한 문제로 고민할 필요가 없다.
열 지향 저장소에서 인접한 바이트트 같은 열에 있으며, 데이터 분석 질의는 일반적으로 이러한 모든 값에 연속적으로 접근해야 하기 때문.
▶ 개선된 압축
행 단위로 데이터를 압축했던것과 비교했을때, 열 단위로 같은 타입의 속성만 압축하는것이 더 효율적이다.
행 단위의 인접한 속성은 타입이 달라서 압축 효율성이 낮다.
압축된 파일이 메모리에 저장되면 메모리 내 저장 공간도 그만큼 감소한다. 이는 메인 메모리가 디스크보다 훨씬 비싸다는 점에서 특히 중요하다.
▶ 벡터 처리
최신의 CPU들은 벡터 처리(vector processing)을 지원한다.
이는 배열의 여러 요소에 CPU연산을 병렬로 실행할 수 있는것을 말한다. 열 단위로 데이터를 저장하면 속성과 상수를 비교하는 것 과 같은 연산을 벡터 처리하게 되는데, 이는 릴레이션에 선택 조건을 적용하는데 중요하다.
또한 벡터 처리는 한번에 하나의 값을 집계하는 대신 병렬로 여러 값의 집계를 계산하는 데 사용되기도 한다.
이러한 이점으로 인해 데이터 분석 질의를 처리하는 데이터 웨어하우징(data-warehousing) 응용 프로그램에 열 지향 저장소를 많이 사용한다.
열 지향 저장소에 사용되는 데이터베이스는 열 저장소(column store)라고 불리며, 행 지향 저장소에 사용되는 데이터베이스는 행 저장소(row store)라고 불린다.
6 - 2) 단점
하지만 열 지향 저장소는 몇가지 단점이 있어 트랜잭션 처리에 적합하지 않다.
▶ 튜플 재구성 비용
개별 열로부터 튜플을 재구성 하는것은 비용이 많이 들기 때문에 많은 열을 재구성해야 하는 경우 열 기반 표현 방식의 장점이 사라진다.
튜플의 재구성은 트랜잭션 처리 응용 프로그램에서 흔하지만, 이와 달리 데이터 분석 응용 프로그램은 보통 데이터 웨어하우스 "fact table"에 저장된 많은 속성 중 소수의 속성만 출력한다.
▶ 튜플 삭제 및 갱신 비용
압축된 형식에서 단인 튜플을 삭제 또는 갱신하려면 하나의 단위로 압축된 튜플의 전체 순차(sequence)를 다시 write해야 한다.
트랜잭션 처리 응용 프로그램에서 튜플의 삭제와 갱신은 흔하므로, 열 지향 저장소에 많은 튜플이 하나의 단위로 압축된 경우 삭제, 갱신의 비용이 크게 든다.
▶ 압축 해제 비용
압축한 형식에서 데이터를 읽어오려면 압축 해제를 해야 하는데, 가장 간단한 압축 형식에서는 파일의 처음부터 끝까지 모든 데이터를 다 읽어야 한다.
하지만 트랜잭션 처리 쿼리의 경우 일반적으로 몇개의 레코드만 읽어오는 것이 필요하다.
이런경우 순차 접근의 비용이 매우큰데, 이는 몇개의 관련된 레코드에 접근하기 위해 관련 없는 많은 레코드의 압축을 해제해야 하기 때문이다.
데이터 분석 쿼리는 선택 조건에 일치하지 않는 레코드에 접근할 필요가 없으며, 디스크 I/O를 줄이기 위해 그러한 레코드 속성을 건너 뛰어야 한다.
이러한 레코드로부터 속성값을 건너뛰기 위해, 열 저장소의 압축 형식을 사용하면 파일의 이전 부분을 건너뛰고 파일의 여러 임의 지점에서 압축 해제를 시작할 수 있다.
예를 들어 10,000 개의 값마다 새로운 압축을 함으로써 이를 수행할 수 있다. 만약 파일의 i번째 값을 알고 싶다면, 파일에서 10,000개 값의 그룹마다 시작 위치를 찾고 lower(i/10000) 그룹의 시작 부분으로 이동하면 된다.
그런 다음, 그 위치에서부터 압축 해제를 시작하여 i번째 값에 쉽게 접근할 수 있다.
ORC와 Parquet은 많은 빅데이터 처리 응용 프로그램에서 사용되는 열 기반 파일 형식이다.
ORC는 다음과 같은 방식을 통해 행 지향 형식을 열 지향 형식으로 변환한다. 수백 메가바이트를 차지하는 튜플 순차는 스트라이프(stripe)라고 하는 열 기반 표현으로 나뉜다.
ORC 파일에는 여러 개의 스트라이프가 존재하며, 각 스트라이프의 크기는 250MB 정도다.
7. 메인 메모리 데이터베이스의 저장 구조
큰 메인 메모리는 데이터베이스 버퍼에 많은 양의 메모리를 할당하여 사용할수가 있다.
이렇게 하면 전체 데이터베이스를 버퍼에 적재할 수 있으므로 데이터를 읽기위한 디스크 I/O 연산을 피할 수 있다.
다만, 갱신한 블록은 영속적으로 저장되기 위해 여전히 디스크에 다시 쓰여져야 한다.
메인 메모리 데이터베이스(main-memory database)는 모든 데이터가 메모리에 상주하는 데이터베이스 이다.
일반적으로 이러한 사실을 활용하여 성능을 최적화하도록 설계되었다. 특히 버퍼 관리자를 완전히 없애버렸다.
디스크 기반 데이터베이스에서 레코드가 블록에 저장되고, 레코드에 대한 포인터는 블록 식별자와 블록 내의 offset 또는 slot번호로 구성된다. 이러한 레코드 포인터를 따라가려면 블록이 버퍼에 있는지 확인하고 블록이 존재하는 경우 버퍼에서 위치를 찾고, 버퍼에 없는 경우 가져와야 한다.
이러한 모든 작업은 상당한 수의 CPU 사이클이 필요하다.
반대로, 메인 메모리 데이터베이스는 레코드에 대한 직접 포인터(direct pointer)를 메모리에 가지고 있을 수 있는데, 레코드에 접근하는 것은 매우 효율적인 메모리 내 포인터 순회가 된다.
블록 내의 슬롯 페이지 구조에 레코드를 저장하면, 다른 레코드를 삭제하거나 크기를 조정할 때 레코드를 블록 내에서 이동시키게 된다.
이 경우 레코드에 대한 직접 포인터를 사용할수는 없지만, 슬롯 페이지 헤더에 있는 엔트리를 통해 우회하여 접근할 수 있다.
다른 Process가 데이터를 읽는 동안 레코드를 이동하지 않으려면 해당 block에 대한 잠금이 필요할 수 있다.
이러한 오버헤드를 피하고자 많은 메인 메모리 데이터베이스는 레코드를 할당하기 위한 슬롯 페이지 구조를 사용하지 않는다.
대신 메인 메모리에 레코드를 직접 할당하고 다른 레코드에 대한 갱신으로 인해 레코드를 이동하지 않도록 한다.
그러나 레코드를 직접 할당할 때 생기는 한가지 문제점은, 가변 크기의 레코드를 반복적으로 삽입하고 삭제하면 메모리가 단편화될 수 있다는 것이다.
따라서 메인 메모리를 주기적으로 압축을 수행하여, 시간이 지남에 따라 단편화되지 않도록 해야 한다.
메인 메모리에서 열 지향 저장소 방식을 사용할 경우, 열의 모든 값을 연속적인 메모리 위치에 저장할 수 있다.
그러나 릴레이션에 대한 데이터 추가가 있는 경우 연속적인 할당을 보장하려면 기존 데이터를 재할당해야 한다.
이러한 오버헤드 방지를 위해 열의 논리적 배열을 여러 물리적 배열로 나눌 수 있다.
간접 테이블(indirection table)은 모든 물리적 배열에 대한 포인터를 저장한다. 다음 그림을 보자.
논리적 배열의 i번째 요소를 찾기 위해, 간접 테이블을 사용하여 i번째 요소를 포함하는 물리적 배열을 찾은 다음 적절한 offset을 계산하고, 해당 물리적 배열 내에서 조회한다.
'CS > DB (2022-1)' 카테고리의 다른 글
| [DB] 인덱싱 (2) | 2022.10.21 |
|---|---|
| [DB] 물리적 저장 장치 시스템 (0) | 2022.10.09 |
| [DB] E-R 모델을 사용한 데이터베이스 설계 (0) | 2022.10.06 |
| [DB] 고급 SQL (1) | 2022.10.04 |
| [DB] 중급 SQL - 2 (1) | 2022.09.30 |
댓글