13. Data Storage Structures

File Organization

• 데이터베이스는 파일(file)의 집합으로 저장
• 파일은 논리적으로 레코드(record)의 시퀀스로 구성
• 각 파일은 블록(block)이라는 고정 길이 저장 단위로 논리적으로 분할되며, 이는 저장 할당 및 데이터 전송의 단위
• 블록은 레코드 크기와 사용 중인 물리적 레코드 구성 형태에 따라 여러 레코드를 포함 가능
• 레코드는 필드(field)(속성을 위한)의 시퀀스
• 가능한 가정들
  • 어떤 레코드도 블록보다 크지 않음 (대부분의 DB 시스템에서 현실적)
  • 블록보다 큰 레코드는 메모리 버퍼로 비연속적으로 가져올 수 있음
  • 각 레코드는 단일 블록에 완전히 포함됨; 블록 경계를 넘지 않음
  • 두 블록에 걸친 레코드는 메모리 버퍼로 비연속적으로 가져올 수 있음
  • 각 파일은 특정 유형의 레코드만 가짐
  • 다른 관계(relation)에 대해 다른 파일 사용

Fixed-Length Records

• 단순한 접근 방식:
  • 레코드 $i (\ge 0)$를 바이트 $n \times i$부터 저장. 여기서 $n$은 각 레코드의 크기
  • 레코드 접근은 간단하지만 레코드가 블록을 교차할 수 있음
• 수정: 레코드가 블록 경계를 넘지 않도록 허용
• 레코드 $i$의 삭제: 대안들
  • 대안 1: 레코드 $i+1, \dots, n$을 $i, \dots, n-1$로 이동
  • 대안 2: 레코드 $n$을 $i$로 이동
  • 대안 3: 레코드를 이동하지 않고, 모든 빈 레코드를 free list에 연결

Variable-Length Records

• 가변 길이 레코드는 여러 방식으로 데이터베이스 시스템에서 발생:
  • 파일 내에 여러 레코드 타입 저장
  • 문자열(varchar)과 같이 하나 이상의 필드에 가변 길이를 허용하는 레코드 타입
  • 배열과 같이 반복되는 필드를 허용하는 레코드 타입 (일부 구형 데이터 모델에서 사용)
• 해결해야 할 두 가지 문제
  1. 개별 속성이 가변 길이일지라도 쉽게 추출할 수 있도록 단일 레코드를 표현하는 방법
  2. 블록 내의 레코드를 쉽게 추출할 수 있도록 블록 내에 가변 길이 레코드를 저장하는 방법
• 단일 가변 길이 레코드 표현 방법
  • 레코드 구조는 두 부분으로 구성
    • 고정 길이 부분 (초기 부분)
      • 각 가변 길이 필드에 대한 고정 크기 (오프셋, 길이) 정보
      • 고정 길이 필드의 값과 Null 비트맵
    • 가변 길이 부분: 가변 길이 필드의 값
• 블록 내 다중 가변 길이 레코드 저장 방법
  • 슬롯 페이지(slotted-page) 구조는 블록 내 레코드를 구성하는 데 일반적으로 사용
  • 슬롯 페이지 헤더(header) 포함 내용:
    • 헤더의 레코드 엔트리(entry) 수
    • 블록 내 여유 공간의 끝
    • 각 레코드의 위치와 크기를 포함하는 항목들의 배열
  • 레코드는 삭제 또는 크기 변경 시 페이지 내에서 이동하여 레코드 사이에 빈 공간 없이 연속적으로 유지될 수 있음; 헤더의 항목은 그에 따라 업데이트되어야 함
  • 외부 레코드 포인터는 레코드를 직접 가리켜서는 안 됨; 대신 헤더에 있는 해당 레코드의 항목을 가리켜야 함

Organization of Records in Files

• Heap 파일 조직
  • 레코드는 공간이 있는 파일 어디에나 위치 가능
  • 레코드의 순서 없음
• Sequential 파일 조직
  • 검색 키(search key) 값에 따라 레코드를 순차적으로 저장
• Multitable clustering 파일 조직
  • 여러 다른 관계의 레코드를 동일한 파일에 저장 가능
  • 동기: 특정 조인(join) 연산에 대한 I/O를 최소화하기 위해 관련 레코드를 동일한 블록에 저장
• B+-tree 파일 조직
  • 많은 수의 삽입, 삭제, 업데이트 연산에도 정렬된 저장 유지
  • 자세한 내용은 14장
• Hashing 파일 조직
  • 검색 키에 대해 계산된 해시 함수(hash function); 결과는 레코드가 위치해야 할 파일의 블록을 지정
  • 자세한 내용은 14장

Heap File Organization

• 레코드는 여유 공간이 있는 파일 어디에나 위치 가능
• 레코드는 일단 할당되면 보통 이동하지 않음 (레코드 순서 유지 불필요)
• 파일 내 여유 공간이 있는 블록을 효율적으로 찾는 것이 중요
• Free-space map
  • 레코드를 저장할 여유 공간이 있는 블록을 추적하기 위한 공간 효율적인 데이터 구조
  • 블록 당 1개의 항목을 가진 배열: 각 항목은 몇 비트에서 바이트 크기이며, 블록의 여유 공간 비율을 기록
  • 아래 예시에서 블록 당 3비트, 값을 8로 나눈 값이 해당 비율을 나타냄
  • 큰 파일에서 속도 향상을 위해 2차 수준의 free-space map을 가질 수 있음
  • 아래 예시에서 각 항목은 1차 수준 free-space map의 4개 항목 중 최대값을 저장
• Free space map은 주기적으로 디스크에 기록됨: 디스크 상의 맵은 오래된 정보일 수 있음
• 일부 항목에 대해 잘못된 (오래된) 값을 가져도 괜찮음 (탐지되고 수정될 것)

Sequential File Organization

• 전체 파일을 순차적으로 처리해야 하는 애플리케이션에 적합
• 파일의 레코드는 반드시 기본 키(primary key)나 슈퍼키(superkey)가 아닌 검색 키에 의해 정렬됨
• 순차 파일 처리에서 블록 접근 수를 최소화하기 위해 레코드를 검색 키 순서로, 또는 가능한 한 그 순서에 가깝게 물리적으로 저장
• 포인터(pointer)를 사용하여 레코드 체인을 만듦
• 문제점: 레코드가 삽입되고 삭제될 때 물리적 순차 순서를 어떻게 유지하는가?
• 삭제: 포인터 체인 사용
• 삽입: 레코드가 삽입될 위치를 찾음
  • 여유 공간이 있으면 그곳에 삽입
  • 여유 공간이 없으면 오버플로 블록(overflow block)에 레코드 삽입
• 두 경우 모두 포인터 체인은 업데이트되어야 함
• 오버플로 블록에 많은 수의 레코드가 있으면 레코드의 물리적 순차 순서가 저하됨
• 물리적 순차성을 복원하기 위해 파일을 재구성해야 하며, 이는 비용이 많이 드는 작업
• B+-tree 파일 조직이 이 문제를 해결

Multitable Clustering File Organization

• Multitable clustering 파일 조직을 사용하여 하나의 파일에 여러 관계 저장
• $\text{department} \Join \text{instructor}$를 포함하는 쿼리와 단일 department 및 그 소속 instructor들을 포함하는 쿼리에 좋음
• department 또는 instructor만 포함하는 쿼리에는 좋지 않음
• 가변 크기 레코드를 초래
• 특정 관계의 레코드를 연결하기 위해 포인터 체인을 추가할 수 있음
• Cluster key: 어떤 레코드가 함께 저장될지 정의하는 속성
• 예시에서는 dept_name

Partitioning

• 테이블 파티셔닝(Table partitioning)
• 관계 내 레코드는 별도로 저장되는 더 작은 관계로 분할될 수 있으며, 이는 일반적으로 속성 값을 기반으로 수행됨
• 예: transaction 관계는 transaction_2018, transaction_2019 등으로 분할될 수 있음
• transaction에 대해 작성된 쿼리는 연도별 관계에 대한 쿼리로 변환됨: 모든 파티션의 레코드에 접근해야 함
• 쿼리 최적화기(Query optimizer)는 year=2019와 같은 선택 조건이 있는 쿼리를 재작성(또는 변환)하여 해당 파티션에만 접근하도록 할 수 있음
• 파티셔닝은 여유 공간 관리와 같은 일부 작업의 비용을 감소시킴
• 이러한 작업의 비용은 관계 크기에 따라 증가함
• 파티셔닝은 다른 파티션을 다른 저장 장치에 저장할 수 있게 함
• 예: (자주 접근하는) 현재 연도의 transaction 파티션은 SSD에, (드물게 접근하는) 이전 연도는 자기 디스크에 저장

Data Dictionary Storage

• 관계형 데이터베이스 시스템은 관계의 스키마(schema)와 같이 관계에 대한 데이터를 유지해야 함
• 일반적으로 이러한 "데이터에 대한 데이터"를 metadata(메타데이터)라고 함
• Data dictionary(데이터 사전) (또는 system catalog(시스템 카탈로그))는 다음과 같은 메타데이터를 저장:
  • 관계에 대한 정보
    • 관계의 이름
    • 각 관계의 속성 이름, 타입(도메인), 길이
    • 뷰(view)의 이름과 정의
  • 무결성 제약조건(Integrity constraint)
  • 사용자 및 계정 정보, 포함 내용:
    • 인증을 위한 사용자 이름, 비밀번호 및 기타 정보
    • 각 사용자에 대한 권한 정보
  • 통계 및 기술 데이터, 포함 내용:
    • 각 관계의 튜플(tuple) 수
    • 각 속성에 대한 고유 값의 수
  • 물리적 파일 조직 정보
    • 관계 저장 방식 (heap/sequential/hash/…)
    • 관계의 물리적 위치
  • 인덱스(index)에 대한 정보 (14장)
• 디스크 상의 관계형 표현
  • 메타데이터를 데이터베이스 자체의 관계로 저장
  • 시스템의 전체 구조를 단순화
  • 시스템 데이터에 대한 빠른 접근을 위해 데이터베이스의 모든 기능을 활용
• 데이터베이스 시작 시, 시스템 메타데이터는 빠른 접근을 위해 메모리 내 데이터 구조로 로드됨
• 일부 데이터베이스 시스템은 위의 관계형 표현 대신 메타데이터를 위해 특화된 데이터 구조를 사용

Storage Access and Database Buffer

Storage Access

• 순차 접근(Sequential access) 패턴
  • 연속적인 요청이 연속적인 디스크 블록에 대한 것
  • 디스크 탐색(seek)은 첫 번째 블록에 대해서만 필요
• 임의 접근(Random access) 패턴
  • 연속적인 요청이 디스크 어디에나 있을 수 있는 블록에 대한 것
  • 각 접근마다 탐색 필요
  • 탐색에 많은 시간이 낭비되므로 전송률이 낮음
• 초당 I/O 연산 (IOPS)
  • 디스크가 초당 지원할 수 있는 임의 블록 읽기 수
  • 현재 세대 자기 디스크에서 50 ~ 200 IOPS
• Solid-State Drives (SSD)
  • (비휘발성) NAND 메모리 칩 기반의 저장 장치
  • 표준 블록 지향 디스크 인터페이스도 사용
  • HDD보다 훨씬 작은 접근 시간과 더 큰 전송률 및 IOPS
  • 임의 읽기와 순차 읽기 간에 큰 차이 없음
  • 그러나 임의 쓰기는 여전히 중요
• 데이터베이스 시스템은 디스크와 메모리 간의 블록 전송 수를 최소화하고자 함
• 매우 느린 스토리지 접근 수를 최소화하기 위함
• 가능한 한 많은 블록을 주 메모리에 유지함으로써 디스크 접근 수를 줄일 수 있음
• Buffer(버퍼)
  • 모든 디스크 블록을 메모리에 저장할 수 없음
  • 디스크 블록에 대한 메모리 공간 할당 관리 필요
  • 주 메모리의 관리되는 부분으로 디스크 블록의 복사본을 저장하는 데 사용 가능
  • 디스크 블록은 버퍼 블록 (또는 페이지)에 저장됨
  • 디스크 블록의 데이터는 버퍼의 데이터보다 오래될 수 있음
  • 데이터베이스 시스템이 버퍼에서 삽입/삭제/업데이트 작업을 수행했지만 아직 결과를 디스크 블록에 출력하지 않았을 수 있기 때문
• Buffer manager(버퍼 관리자)
  • 주 메모리에 버퍼 공간을 할당하는 책임을 지는 하위 시스템

Buffer Manager

• 프로그램은 디스크에서 블록이 필요할 때 버퍼 관리자를 호출
• 블록이 이미 버퍼에 있으면, 버퍼 관리자는 주 메모리 내 블록의 주소를 반환
• 블록이 버퍼에 없으면, 버퍼 관리자는
  • 블록을 위한 공간을 버퍼에 할당
  • 필요한 경우, 다른 블록을 교체하여 새 블록을 위한 공간 확보: 버퍼 교체(buffer replacement)
  • 교체된 블록은 가장 최근에 디스크에 쓰여지거나 디스크에서 가져온 이후 수정된 경우에만 디스크에 다시 쓰여짐
  • 디스크에서 버퍼로 블록을 읽고, 주 메모리 내 블록의 주소를 요청자에게 반환
• Pinned block(고정된 블록): 디스크에 다시 쓰여지는 것이 허용되지 않는 메모리 블록
  • 버퍼 블록을 읽거나 쓰는 동안 교체되면 문제가 발생 → 버퍼 블록에 접근하기 전에 해당 블록이 제거되지 않도록 해야 함
  • Pin은 블록에서 데이터를 읽거나 쓰기 전에 수행됨
  • Unpin은 읽기/쓰기가 완료될 때 수행됨
  • 다중 동시 pin/unpin 연산 (동시 트랜잭션을 위해) 가능
  • pin count를 유지하며, pin count가 0일 때만 버퍼 블록을 제거할 수 있음
• 버퍼에 대한 공유 및 배타적 잠금(lock)
• 동시성 제어(Concurrency Control)
  • 여러 프로세스(또는 스레드)에 의한 데이터 항목에 대한 동시 접근은 데이터 불일치를 유발할 수 있음
  • 예) 버퍼 페이지에서 튜플을 추가하거나 삭제하는 프로세스는 페이지 내용을 이동시켜야 할 수 있음 → 이 시간 동안 페이지를 읽는 다른 프로세스는 부정확한 데이터를 얻을 수 있음
• 동시성 제어
  • 여러 프로세스의 전체적인 동시 실행 제어: 18장
• 잠금(Locking): 데이터베이스 시스템의 원시적인 동시성 제어 방식
  • 버퍼 관리자는 위와 같은 경우를 방지해야 함
  • 읽기 작업자는 공유 잠금(shared lock)을 얻고, 블록 업데이트는 배타적 잠금(exclusive lock)을 요구
• 잠금 규칙:

  	No lock	Shared lock	Exclusive lock
  No lock	O	O	O
  Shared lock	O	O	X
  Exclusive lock	O	X	X

  • 블록에 대해 다수의 프로세스가 동시에 공유 잠금(shared lock)을 가질 수 있음
  • 한 번에 하나의 프로세스만 배타적 잠금(exclusive lock)을 획득할 수 있음
  • 또한, 프로세스가 블록에 대해 배타적 잠금을 가지고 있을 때 다른 어떤 프로세스도 해당 블록에 대해 공유 잠금을 가질 수 없음
  • 따라서, 배타적 잠금은 다른 어떤 프로세스도 블록에 대한 잠금을 가지고 있지 않을 때만 부여될 수 있음
  • 프로세스가 이미 잠긴 (공유 또는 배타적) 블록에 대해 배타적 잠금을 요청하면, 이전의 모든 잠금이 해제될 때까지 요청은 보류됨
  • 프로세스가 배타적으로 잠긴 블록에 대해 공유 잠금을 요청하면, 공유 잠금은 배타적 잠금이 해제된 후에만 부여됨
• 잠금 획득 및 해제
  • 블록에 대한 연산 수행: 블록 Pin → 잠금 획득 → 연산 수행 → 잠금 해제 → 블록 Unpin
  • 읽기 연산: 블록에 대한 공유 잠금 획득 필요
  • 업데이트 연산: 블록에 대한 배타적 잠금 획득 필요

Output of Blocks

• 기본 블록 출력 정책
  • 버퍼 블록이 다른 블록으로 교체될 때 디스크로 출력(쓰기): 두 가지 경우
    • 사례 1: 버퍼로 로드된 후 업데이트되지 않음 → 출력하지 않음
    • 사례 2: 업데이트됨 → 디스크로 출력 필요
• 가능한 대안 정책
  • 업데이트된 블록을 교체 전에 미리 쓰기
  • 향후 교체 시, 이미 쓰여진 블록은 출력 없이 제거 가능
  • 그러나, 복구(recovery) 목적(19장)을 위해 출력 제한 필요
  • 대부분의 데이터베이스 시스템은 블록에 대한 업데이트가 진행 중인 동안 해당 블록이 디스크에 쓰여지지 않도록 요구: 여러 프로세스(트랜잭션)가 블록을 업데이트할 수 있음에 유의
  • 이러한 요구사항을 강제하기 위해, 블록을 출력하고자 하는 프로세스는 해당 블록에 대한 공유 잠금을 획득해야 함
• 블록의 강제 출력(Forced output)
  • 디스크의 데이터 일관성을 보장하기 위해 블록을 출력해야 하는 상황 → 블록의 강제 출력
  • 커밋된 데이터의 복구 가능성을 보장하기 위해 로깅(logging) 메커니즘과 함께 사용 (19장에서 상세히)

Buffer-Replacement Policies

• 대부분의 운영 체제는 가장 최근에 사용되지 않은(Least Recently Used, LRU) 블록을 교체 (LRU 전략)
• 최적의 정책: 가까운 미래에 사용되지 않을 버퍼 블록을 제거
• 블록에 대한 미래의 접근을 어떻게 알 수 있는가? → 최근 접근 기록이 통찰을 제공 → LRU
• LRU는 일부 쿼리에 대해 좋지 않을 수 있음
• LRU에 대한 나쁜 접근 패턴의 예: 중첩 루프(nested loop)를 사용하여 두 관계 $r$과 $s$의 조인을 계산할 때 for each tuple tr of r do for each tuple ts of s do if the tuples tr and ts match …
• 쿼리는 잘 정의된 접근 패턴(예: 순차 스캔)을 가짐
• 데이터베이스 시스템은 사용자의 쿼리 정보를 사용하여 미래의 참조를 예측할 수 있음
• 쿼리 최적화기(query optimizer)가 제공하는 교체 전략에 대한 힌트(hint)와 혼합된 전략이 바람직함
• Toss-immediate 전략
  • 블록의 마지막 튜플이 처리되는 즉시 해당 블록이 차지하는 공간을 해제 → 해당 블록은 다시 참조되지 않기 때문
  • 이전 예시에서 관계 $r$의 블록에 좋음
• 가장 최근에 사용된(Most Recently Used, MRU) 전략
  • LRU 전략과 반대
  • 이전 예시에서 관계 $s$의 블록에 좋음
  • 고정된 블록의 마지막 튜플이 처리된 후, 블록은 unpin되고 가장 최근에 사용된 블록이 됨
• 버퍼 관리자는 요청이 특정 관계를 참조할 확률에 대한 통계 정보를 사용할 수 있음
• 예: 데이터 사전은 자주 접근됨
• 휴리스틱(Heuristic): 데이터 사전 블록을 주 메모리 버퍼에 유지

Reordering of Writes and Recovery

• 운영 체제 또는 버퍼 관리자가 쓰기 순서를 재정렬할 수 있음
• 시스템 충돌 시 디스크의 데이터 구조 손상으로 이어질 수 있음
• 예: 디스크에 누락된 블록이 있는 블록의 연결 리스트(Linked list)
• 파일 시스템은 재시작 시 이러한 상황을 감지하기 위해 일관성 검사(consistency check)를 수행
• 신중한 쓰기 순서 지정은 이러한 많은 문제를 피할 수 있음
• 디스크 스케줄링(disk scheduling)과 같은 I/O 최적화 기술을 희생하여 업데이트 효율성에 영향을 미침
• 비휘발성 쓰기 버퍼(Nonvolatile write buffer)는 블록을 비휘발성 RAM 또는 플래시 메모리 버퍼에 즉시 기록하여 디스크 쓰기 속도를 높임
• 디스크 암(disk arm) 움직임을 최소화하기 위해 쓰기 순서를 재정렬할 수 있음
• Log disk: 블록 업데이트의 순차적 로그를 수행된 순서대로 기록하는 데 전용으로 사용되는 디스크
• Log disk에 대한 쓰기는 탐색이 필요 없으므로(즉, 순차적 쓰기) 매우 빠름
• Data disk의 데이터를 복구하기 위해 log disk의 로그를 사용
• 저널링 파일 시스템(Journaling file system)은 별도의 log disk 없이도 이러한 로깅을 지원하는 파일 시스템
• 저널링 없는 재정렬: 파일 시스템 데이터 손상 위험

Column-Oriented Storage

• 컬럼 기반 스토리지(columnar storage)라고도 알려짐
• 관계의 각 속성을 별도로 저장
• 연속적인 튜플의 속성 값을 파일의 연속적인 위치에 저장
• 쿼리가 테이블의 i번째 행의 전체 내용에 접근해야 하는 경우, 각 컬럼의 i번째 위치에 있는 값을 검색하여 행을 재구성
• 가장 간단한 형태: 각 속성은 별도의 파일에 저장되고, 각 파일은 압축됨

Columnar Representation

• 컬럼 기반 스토리지의 단점
  • 컬럼 표현에서 튜플 재구성 비용
  • 특히 압축된 경우 튜플 삭제 및 업데이트 비용
  • 압축 해제 비용
• 컬럼 표현은 관계의 많은 행을 처리하지만 종종 일부 속성에만 접근하는 데이터 분석(OLAP) 쿼리에 적합
• (많은 수의) 속성 중 일부만 접근하는 경우
  • I/O 감소
  • CPU 캐시 성능 향상
  • 동일한 타입의 값을 함께 저장하면 압축 효과 증가
  • 최신 CPU 아키텍처에서 벡터 처리(vector processing) 허용
  • CPU 연산이 배열의 여러 요소에 병렬로 적용됨
• 트랜잭션 처리(OLTP)에는 행 기반(row-oriented) 표현이 더 바람직함
• 일부 데이터베이스는 두 표현을 모두 지원
• 하이브리드 행/컬럼 스토어(hybrid row/column store)라고 불림

Columnar File Representation

• ORC 및 Parquet: 파일 내에 컬럼 기반 스토리지를 갖는 파일 형식
• 빅데이터 애플리케이션에서 매우 인기 있음
• ORC 파일 형식:
  • 수백 MB를 차지하는 튜플 시퀀스는 스트라이프(stripe)라고 불리는 컬럼 표현으로 분할됨
  • ORC 파일은 여러 스트라이프를 포함하며, 각 스트라이프는 약 250MB를 차지
  • Row data 영역은 첫 번째 컬럼의 값 시퀀스, 이어서 두 번째 컬럼 등의 압축된 표현을 저장
• 스트라이프의 Index data 영역은 각 속성에 대해 해당 속성 값의 각 그룹(예: 10,000개)에 대한 스트라이프 내 시작점을 저장