데이터베이스 시스템 - File Organization

데이터 저장 장치 구조

데이터베이스의 영속 데이터는 비휘발성 저장 장치에 저장됩니다. 일반적으로 자기 디스크나 SSD가 사용되며, 이들은 모두 블록 단위 장치block-structured device입니다. 즉 데이터의 읽기와 쓰기는 모두 블록이라는 단위를 기준으로 일어납니다. 반면 데이터베이스가 다루는 단위는 레코드record이며, 레코드는 블록보다 훨씬 작은 것이 일반적입니다.

대부분의 데이터베이스는 운영체제가 제공하는 파일 시스템을 중간 계층으로 활용하여 레코드를 저장합니다. 파일 시스템이 디스크 블록의 세부 사항을 어느 정도 추상화해주기 때문입니다. 그럼에도 불구하고 데이터베이스는 여전히 블록의 존재를 인식해야 하는데, 그 이유는 두 가지입니다. 첫 번째는 효율적인 접근을 위해서입니다. 블록 단위 입출력의 비용을 고려하지 않고 레코드를 배치하면, 단순한 조회조차 불필요한 디스크 접근으로 이어지기 쉽습니다. 두 번째는 장애 복구를 위해서입니다. 데이터베이스는 장애 발생 후 일관성 있는 상태로 회복할 수 있어야 하는데, 이를 위해서는 디스크 위에 데이터가 어떤 모양으로 놓여 있는지를 직접 통제할 수 있어야 합니다.

따라서 데이터베이스는 운영체제가 제공하는 파일 추상화을 사용하면서도, 그 안에서 레코드가 블록에 어떻게 배치되는지를 스스로 결정해야 합니다. 이번 글에서는 그 첫 번째 주제로 파일 구조file organization을 다루며, 레코드를 블록 위에 표현하는 여러 방식을 살펴보겠습니다.

파일 구조(File Organization)

데이터베이스는 운영체제가 관리하는 여러 개의 파일로 매핑되며, 이 파일들은 디스크에 영구적으로 저장됩니다. 파일은 일련의 레코드로 구성되며, 이 레코드들은 다시 디스크 블록 위에 배치됩니다. 운영체제가 파일이라는 추상을 기본 구성 요소로 제공하기 때문에, 데이터베이스 시스템은 그 위에 논리적인 데이터 모델을 어떻게 표현할지에만 집중합니다.

각 파일은 다시 블록block이라 불리는 고정 크기의 저장 단위로 분할됩니다. 블록은 저장 공간의 할당 단위이자 데이터 전송의 단위입니다. 대부분의 데이터베이스에서는 4KB에서 8KB 사이의 블록 크기가 기본값으로 사용되며, 데이터베이스 인스턴스를 생성할 때 다른 값을 지정할 수 있는 시스템도 많습니다.

하나의 블록에는 보통 여러 개의 레코드가 들어갑니다. 정확히 어떤 레코드들이 한 블록에 함께 저장되는지는 사용 중인 물리적 데이터 구성 방식에 따라 결정됩니다.

이 글에서는 레코드의 크기가 블록보다 크지 않다고 가정합니다. 대부분의 데이터 처리 응용에서는 이 가정이 현실적입니다. 이미지나 영상처럼 블록보다 훨씬 큰 데이터 항목 또한 존재하지만, 이런 큰 객체는 별도로 저장하고 레코드에는 포인터만 남기는 방식으로 우회합니다. 또한 하나의 레코드는 단일 블록 내부에 온전히 담겨야 한다는 제약을 둡니다. 한 레코드가 여러 블록에 걸쳐 저장되는 것을 허용하면 접근 비용이 두 배로 늘어나기 때문에, 이를 금지함으로써 구현과 성능 양쪽을 단순하게 유지합니다.

관계형 데이터베이스에서 서로 다른 릴레이션의 튜플은 일반적으로 크기가 다릅니다. 데이터베이스를 파일에 매핑하는 한 가지 방법은 여러 개의 파일을 사용하되, 각각의 파일에는 동일한 고정 길이의 레코드만 저장하는 것입니다. 또 다른 방법은 하나의 파일이 여러 길이의 레코드를 수용할 수 있도록 구조를 잡는 것입니다. 후자가 더 유연하지만 구현은 전자가 훨씬 쉽고, 전자에서 사용된 기법 상당수는 후자에도 그대로 응용됩니다. 이런 이유로 먼저 고정 길이 레코드를 살펴본 뒤, 가변 길이 레코드로 확장해보겠습니다.

고정 길이 레코드(Fixed-Length Records)

대학 데이터베이스의 instructor 릴레이션을 예로 들어보겠습니다. 각 레코드는 다음과 같이 정의됩니다.

type instructor = record
    ID         varchar(5);
    name       varchar(20);
    dept_name  varchar(20);
    salary     numeric(8,2);
end

각 문자가 1바이트를 차지하고 numeric(8,2)가 8바이트를 차지한다고 가정합니다. 그리고 가변 길이 속성에 실제 사용량만큼만 바이트를 할당하는 대신, 각 속성이 가질 수 있는 최대 바이트 수를 항상 할당한다고 해봅시다. 그러면 instructor 레코드의 길이는 항상 53바이트로 고정됩니다. 가장 단순한 접근은 파일의 처음 53바이트를 첫 레코드로, 그다음 53바이트를 두 번째 레코드로 사용하는 식으로 빈틈없이 이어 붙이는 것입니다.

이 단순한 방식에는 두 가지 문제가 있습니다.

1. 일부 레코드가 블록 경계를 가로지르게 됩니다.

블록 크기가 53의 배수가 아닌 한, 어떤 레코드는 일부가 한 블록에, 나머지가 다음 블록에 걸쳐 저장됩니다. 이런 레코드를 한 번 읽거나 쓰려면 두 번의 블록 입출력이 필요해집니다. 이 문제를 피하기 위해서는, 한 블록에 온전히 들어갈 수 있는 만큼의 레코드만 배치하고 남는 바이트는 그대로 두는 방식이 사용됩니다. 블록 크기를 레코드 크기로 나눈 몫이 한 블록에 담을 수 있는 레코드의 수가 됩니다.

2. 레코드 삭제가 까다롭습니다.

삭제된 레코드가 차지하던 공간은 다른 레코드로 채우거나, 삭제 표시를 남겨 무시되도록 해야 합니다. 그렇지 않으면 파일이 점점 비어 있는 슬롯으로 가득 차게 됩니다.

삭제된 자리를 메우는 가장 직관적인 방법은, 그 뒤의 모든 레코드를 한 칸씩 앞으로 당기는 것입니다. 그러나 이 방식은 삭제 한 번에 수많은 레코드를 옮겨야 하므로 비용이 큽니다. 차라리 파일의 마지막 레코드를 삭제된 자리에 옮겨놓는 편이 훨씬 저렴합니다. 마지막 레코드는 어차피 어딘가로 옮길 수 있는 레코드이고, 한 번의 이동으로 빈 자리를 메울 수 있기 때문입니다.

그러나 이런 이동조차 결국 추가적인 블록 접근을 요구합니다. 삽입은 일반적으로 삭제보다 빈번하므로, 삭제된 공간을 일단 비워둔 채로 두었다가 다음 삽입 시 재사용하는 편이 더 유리합니다. 다만 단순히 "삭제됨" 표시만 남기는 것으로는 충분하지 않습니다. 삽입 시점에 빈 자리를 어떻게 빨리 찾을지가 또 다른 문제가 되기 때문입니다.

이 문제를 해결하기 위해 파일 헤더file header라 불리는 영역을 파일의 맨 앞에 두고, 여기에 첫 번째 빈 레코드의 주소를 저장합니다. 그리고 그 빈 레코드에는 다음 빈 레코드의 주소를, 그 레코드에는 또 다음 빈 레코드의 주소를 저장합니다. 이렇게 하면 삭제된 레코드들이 하나의 연결 리스트 형태로 묶이게 되고, 우리는 이를 자유 리스트free list라고 부릅니다. 헤더는 자유 리스트의 시작점만 알면 됩니다.

새로운 레코드를 삽입할 때는 헤더가 가리키는 자리를 사용하고, 헤더의 포인터를 그 다음 빈 레코드로 옮겨주면 됩니다. 빈 자리가 더 이상 없다면 파일의 끝에 새 레코드를 추가합니다. 고정 길이 레코드에서 삽입과 삭제가 단순한 이유는, 삭제로 비워진 공간의 크기가 새로 삽입할 레코드의 크기와 정확히 일치하기 때문입니다. 가변 길이 레코드를 다루는 순간 이 등식이 깨지면서 문제는 한 단계 더 복잡해집니다.

가변 길이 레코드(Variable-Length Records)

가변 길이 레코드는 여러 이유로 자연스럽게 등장합니다. 가장 흔한 원인은 가변 길이 필드, 즉 문자열의 존재입니다. 그 외에도 배열이나 멀티셋과 같은 반복 필드를 포함하는 레코드 타입, 한 파일 안에 여러 종류의 레코드 타입이 함께 저장되는 경우 등이 있습니다.

가변 길이 레코드를 구현할 때는 두 가지 문제를 동시에 풀어야 합니다.

1. 레코드 안에서 개별 속성을 어떻게 빠르게 추출할 것인가

2. 한 블록 안에 가변 길이 레코드를 어떻게 배치할 것인가

레코드 표현(Record Representation)

가변 길이 속성을 포함하는 레코드는 보통 두 부분으로 나뉘어 표현됩니다. 앞쪽에는 모든 레코드가 동일한 구조로 갖는 고정 길이 부분이 오고, 그 뒤에 가변 길이 속성의 실제 내용이 이어집니다. 숫자나 날짜, 고정 길이 문자열처럼 크기가 정해진 속성은 필요한 만큼의 바이트를 그대로 사용합니다. 반면 varchar처럼 크기가 정해지지 않은 속성은 고정 길이 부분에 (오프셋, 길이)라는 한 쌍의 값으로 표현됩니다. 오프셋은 해당 속성의 데이터가 레코드 내 어디서부터 시작하는지를, 길이는 그 데이터가 몇 바이트인지를 나타냅니다. 가변 길이 속성의 실제 값들은 고정 길이 부분 뒤에 차례대로 이어 붙입니다.

이런 구성 덕분에 레코드의 앞쪽만 봐도 모든 속성의 위치와 크기를 즉시 알 수 있습니다. ID, name, dept_name이 가변 길이 문자열이고 salary가 8바이트의 고정 길이 숫자인 instructor 레코드를 가정하면, 레코드 앞부분에는 각 속성마다 4바이트씩(오프셋 2바이트 + 길이 2바이트)이 자리를 잡고, 그 뒤에 salary 8바이트, 그리고 마지막에 가변 길이 문자열들이 이어집니다.

고정 길이 부분에는 보통 널 비트맵null bitmap이 함께 들어갑니다. 어떤 속성이 NULL인지를 비트 단위로 표시하는 작은 영역입니다. 만약 salary가 NULL이라면 비트맵의 해당 비트를 1로 두고, salary 자리에 저장된 8바이트는 무시하면 됩니다. 속성이 4개인 레코드라면 비트맵은 1바이트면 충분합니다. 어떤 구현에서는 NULL인 속성에 대해 값뿐만 아니라 오프셋과 길이조차 저장하지 않습니다. 저장 공간을 더 아낄 수 있지만, 속성을 추출할 때 약간의 추가 작업이 따라옵니다. 속성 수가 매우 많고 그중 대부분이 NULL인 응용에서는 이런 표현이 특히 유리합니다.

NULL 속성의 동작

NULL 처리는 INSERT 시점인지 이미 저장된 레코드를 UPDATE하는 시점인지에 따라 데이터 영역의 모양이 미묘하게 달라집니다.

INSERT 시 어떤 가변 길이 속성이 NULL이라면, 비트맵의 해당 비트가 1로 켜지고 가변 데이터 영역에는 그 속성의 자리를 아예 비워둡니다. 그 결과 그 다음 가변 속성의 데이터가 한 칸 앞당겨진 위치에서 시작합니다. 예를 들어 instructor 레코드에서 name이 NULL인 채로 들어온다면, dept_name의 데이터는 byte 36이 아니라 byte 26에서 시작합니다. 헤더의 (offset, length) 자리에 무엇을 적는지는 구현마다 다른데, Silberschatz 교과서의 표준 표현은 length 필드에 -1 같은 sentinel을 적어 NULL을 표시하고 offset 값은 어떤 값이든 무방하게 두며, MySQL InnoDB처럼 더 적극적으로 공간을 아끼는 구현은 NULL인 가변 속성에 대한 length 정보 자체를 record 헤더에서 빼버리기도 합니다.

여기서 가변 길이 속성과 고정 길이 속성의 비대칭이 드러납니다. salary가 NULL이어도 byte 12부터 19까지의 위치는 스키마에 의해 고정되어 있어 줄일 수 없습니다. 8바이트가 그대로 자리를 차지하고 비트맵 비트로 무시 표시될 뿐입니다. 공간만 보면 낭비처럼 보이지만, 위치가 고정되어 있다는 점은 NULL ↔ non-NULL 전환 시 다른 속성을 건드리지 않고 in-place로 갱신할 수 있는 장점이기도 합니다. 가변 길이 속성은 데이터 영역에서 자연스럽게 자리를 비우는 만큼 공간 효율은 좋지만, 그 대가로 NULL 여부가 바뀔 때 구조가 변경되어야 합니다.

이미 저장된 레코드에서 가변 길이 속성이 UPDATE로 NULL이 되는 경우는 조금 더 까다롭습니다. 데이터 영역에 이미 다른 속성들의 값이 빈틈없이 이어져 있기 때문에, 그 한 속성을 통째로 빼버리면 뒤 속성들의 위치가 어긋납니다. 처리 방식은 보통 두 가지로 갈립니다.

첫 번째는 데이터 영역을 다시 채워 넣는repacking 방식입니다. NULL이 된 속성이 차지하던 byte를 비우고 그 뒤의 모든 속성을 앞으로 끌어오며, 헤더의 (offset, length) 쌍들도 그에 맞춰 다시 계산합니다. 공간은 회수되지만 레코드의 상당 부분을 다시 써야 하는 비용이 따릅니다.

두 번째는 비트맵 비트만 1로 켜고 데이터 영역과 헤더는 손대지 않는 in-place 방식입니다. 추출 로직이 어차피 비트맵을 먼저 확인하기 때문에 (offset, length)를 갱신하지 않아도 무방합니다. 비워진 영역의 바이트는 의미 없는 garbage로 남지만 다른 부분을 전혀 건드리지 않아 비용이 가장 적습니다. 업데이트가 잦은 워크로드에서는 이 방식이 일반적이며, 누적된 빈 영역은 주기적인 재구성reorganization으로 회수됩니다.

슬롯 페이지 구조(Slotted-Page Structure)

가변 길이 레코드를 한 블록 안에 어떻게 배치할까요? 표준적으로 사용되는 방식은 슬롯 페이지 구조slotted-page structure입니다.

블록의 맨 앞에는 헤더가 자리잡으며, 다음 정보를 담습니다.

• 블록에 들어 있는 레코드 엔트리의 수
• 블록 내 자유 공간의 끝 위치
• 각 레코드의 위치와 크기를 담은 엔트리의 배열

그리고 실제 레코드들은 블록의 반대편 끝, 즉 블록의 끝에서부터 거꾸로 채워집니다. 헤더의 마지막 엔트리와 첫 번째 레코드 사이의 영역이 자유 공간입니다.

새로운 레코드를 삽입할 때는, 자유 공간의 끝에서 그만큼의 공간을 잘라 레코드를 채우고, 헤더에 위치와 크기를 담은 새로운 엔트리를 추가합니다. 레코드를 삭제할 때는 해당 엔트리를 삭제 표시(예를 들어 크기를 −1로 설정)하고, 그 레코드보다 앞쪽에 있던 레코드들을 한꺼번에 옆으로 밀어 빈 공간을 메웁니다. 이렇게 하면 자유 공간이 다시 헤더 끝과 첫 레코드 사이에 한 덩어리로 모이게 됩니다. 자유 공간 끝을 가리키는 포인터도 그에 맞춰 갱신됩니다. 레코드의 크기를 늘리거나 줄이는 것 역시 동일한 방식으로 처리할 수 있습니다.

이 "옆으로 미는" 작업이 비용처럼 보일 수 있지만 실제로는 거의 무시할 만합니다. 블록은 이미 메인 메모리에 올라와 있는 상태에서 수정되므로 압축도 메모리 위의 byte 복사로 끝나고, 블록 크기가 4~8KB로 제한되어 있어 그 복사 자체도 마이크로초 단위로 끝납니다. 디스크 I/O는 어차피 블록 단위로 한 번에 일어나기 때문에 블록 안에서 byte를 어떻게 옮겨놓든 I/O 횟수에는 영향을 주지 않습니다.

슬롯 페이지 구조의 한 가지 중요한 규칙은, 레코드를 직접 가리키는 포인터를 외부에서 사용하지 않는다는 점입니다. 외부의 모든 포인터는 레코드가 아니라 헤더의 엔트리를 가리킵니다. 한 단계의 간접 참조가 추가되긴 하지만, 이 덕분에 블록 안에서 레코드를 자유롭게 이동시키더라도 외부 포인터는 그대로 유효하게 유지됩니다. 블록 내부의 단편화를 손쉽게 정리할 수 있게 해주는 핵심적인 설계 결정입니다.

대형 객체 저장 방법(Storing Large Objects)

데이터베이스가 다뤄야 하는 데이터 중에는 디스크 블록보다 훨씬 큰 것이 종종 있습니다. 이미지나 오디오는 수 메가바이트, 영상은 수 기가바이트에 이를 수도 있습니다. SQL은 이런 데이터를 위해 blob(이진 대형 객체)과 clob(문자 대형 객체) 타입을 제공합니다.

많은 데이터베이스는 내부적으로 레코드의 크기가 블록을 넘지 못하도록 제한합니다. 그러면서도 레코드가 논리적으로는 큰 객체를 포함할 수 있도록, 실제 데이터는 레코드 바깥에 따로 저장하고 레코드에는 그 객체에 대한 포인터만 두는 방식을 사용합니다.

이렇게 분리된 큰 객체를 저장하는 방법은 다시 두 갈래로 나뉩니다. 둘 다 "DB가 관리하는 영역 안"이라는 점은 같지만, OS의 파일 시스템 추상을 어디까지 빌리느냐에서 갈립니다.

첫 번째는 큰 객체를 OS 파일 시스템 위의 일반 파일로 두는 방식입니다. DB는 자기 영역으로 잡아둔 디렉토리를 갖고, 큰 객체 하나마다 OS 파일을 하나 만들어 저장합니다. 파일 자체는 OS가 보기에 평범한 파일이지만 그 파일의 생성·삭제·접근 제어는 DB가 책임집니다.

두 번째는 큰 객체를 DB의 블록 시스템 안에서 직접 관리하는 방식입니다. OS 파일 시스템 추상을 빌리지 않고, DB가 다른 일반 레코드를 저장할 때 쓰는 페이지 할당기 위에 객체를 여러 블록으로 펼쳐 저장합니다. 이 경우 buffer pool, 트랜잭션, 잠금 같은 DB의 일반 기능이 큰 객체에도 그대로 적용됩니다. 또 객체를 B+-tree 파일 구조 위에 올려두면 객체 전체를 읽는 것뿐 아니라 임의의 바이트 범위를 읽거나, 객체의 일부를 삽입·삭제하는 연산까지 효율적으로 지원할 수 있습니다 — OS 파일 한 덩어리로 두는 첫 번째 방식이 부분 갱신을 다루기 어려운 것과 대비되는 큰 장점입니다.

다만 매우 큰 객체를 데이터베이스 안에 두는 것에는 몇 가지 성능 부담이 따릅니다. 데이터베이스의 인터페이스를 통해 큰 객체에 접근하는 비용이 첫 번째이고, 두 번째는 백업 크기입니다. 많은 조직에서 주기적으로 데이터베이스 덤프를 만드는데, 큰 객체가 데이터베이스 안에 저장되어 있으면 덤프 크기가 무시할 수 없을 정도로 불어납니다.

이런 이유로 영상과 같은 매우 큰 객체는 데이터베이스 외부의 파일 시스템에 저장하고, 데이터베이스에는 그 파일의 경로만 속성으로 보관하는 방식을 채택하는 응용이 많습니다. 다만 이 방식에는 별도의 위험이 따라옵니다. 데이터베이스가 가리키는 파일이 외부에서 삭제되면 일종의 외래 키 제약 위반과 비슷한 상황이 발생하며, 데이터베이스의 권한 제어 역시 외부 파일 시스템에는 적용되지 않습니다. 일부 데이터베이스는 파일 시스템과의 통합 기능을 제공하여 이러한 제약과 권한이 일관되게 유지되도록 합니다. 예를 들어 Oracle의 SecureFiles와 Database File System은 이러한 통합을 제공합니다.

마무리

지금까지 레코드를 어떻게 바이트로 표현하는지와, 한 블록 안에 여러 레코드를 어떻게 배치할 지, 그리고 블록보다 큰 객체를 어떻게 다룰지까지 살펴보았습니다. 모두 한 블록 안의 byte를 어떻게 다룰지에 관한 방법론이었습니다.

다음 글에서는 한 단계 더 나아가 같은 릴레이션에 속한 수많은 레코드들을 파일 안에 어떤 순서로, 어느 블록에 묶어 둘 것인지를 다뤄보겠습니다.