Week 11 - Data Storage Structure

File Organization

MySQL → InnoDB : Function calls
InnoDB → Linux : System call
Linux → File System : Ext4_file_Write_iter
File System → HDD : SATA_commands

Database 는 파일 collection 으로 저장
각 파일은 레코드들의 sequence
각 File 은 하나 이상의 Page 로 구성
각 Page 는 하나 이상의 Record 로 구성
Record 는 Field 의 sequence

[!note] Data Size
일반적으로 레코드 - 페이지 - 파일 순으로 크기가 커집니다.
레코드는 데이터베이스에서 가장 작은 단위
레코드는 데이터베이스 테이블의 한 행

페이지는 레코드가 저장되는 블록
일반적으로 4KB 또는 8KB 크기

파일은 데이터베이스 테이블의 모든 레코드가 저장되는 논리적 단위

• 레코드 크기는 Fixed
• 각 파일에는 특정 유형의 레코드만 있음
• 다른 파일에는 다른 Relation
• Records 는 disk block 보다 작음

Fixed-Length Records

n : size of each record
i : record
Record Access 는 간단하지만 block 을 교차할 수 있음
레코드가 블록 경게를 넘지 않도록 변경할 수 있음

Deletion of record i

i 번째 데이터를 지우면 레코드를 i+1, , n 에서 i , , n-1 로 옮겨야함
n 번째 데이터를 i 로 옮김
많은 레코드를 옮기고 싶지 않기 때문에 사용되지 않는 free record 를 연결하여 free list 를 구성

Variable-Length Records

데이터베이스 시스템에서 여러가지 방식으로 발생

• 여러 레코드 유형의 저장 문자열 (varchar) 과 같이 하나 이상의 필드에 가변 길이를 허용하는 유형
  

Slotted Page Structure

레코드에 대한 정보를 Block Header 에 저장 : Slotted Block Header Contains

• Number of record entries
• End of free space in the block
• Location and size of each record
  레코드를 페이지 내에서 이동하여 레코드 사이에 빈 공간 없이 연속성을 유지
  헤더의 항목은 업데이트

Organization of Records in Files

Heap

Organization 의 가장 기본적이고 범용성 있는 type
레코드는 파일 끝에 삽입
레코드 삽입 시 순서 지정이 필요하지 않음
빈 공간이 있는 파일의 어느 위치에나 레코드 저장 가능

Sequential

각 레코드의 search key 의 value 를 기준으로 순차적으로 저장
전체 파일의 순차적인 처리가 필요한 응용 프로그램에 적합
파일 내의 레코드는 검색 키 순서대로 정렬

따라서, 전체 파일을 순차적으로 처리하고 검색 키 순서가 중요한 경우에 적합한 파일 조직 유형

Deletion

Use Pointer Chains

Insertion

삽입 위치 탐색 : 빈공간이 있으면 삽입
빈 공간 탐색 : 빈 공간이 없으면 Overflow block 에 삽입
오버플로 블록은 순차 파일의 마지막에 위치하며 삽입할 수 없는 레코드를 저장하는 데 사용

• 시간이 지남에 따라 삽입과 삭제가 이루어지면 파일이 조각화되어 순차적인 순서가 깨질 수 있습니다. 이러한 경우 파일의 순차적인 순서를 복원하기 위해 파일 재구성이 필요합니다. 파일 재구성은 모든 레코드를 읽고 정렬하고 순차적으로 빈 공간 없는 새 파일에 다시 삽입하는 작업입니다.

Multitable clustering file organization

여러 다른 관계의 레코드를 같은 파일에 저장
동일한 블록에 관련 레코드를 저장하여 I/O 를 최소화
다중 클러스터링 파일을 구성을 사용해서 하나의 파일에 여러 관계를 저장

Join 을 포함하는 쿼리 & department 와 그 instructor 를 포함하는 쿼리 에 적합
단일 테이블 (departmen) 에 대한 쿼리는 부적합
특정 relation 의 record 를 연결하기 위해 Pointer chain 을 추가할 수 있음

B±tree file organization

삽입/삭제가 발생하더라도 정렬된 저장이 유지

Hashing

검색 키를 기준으로 해시 함수를 계산
해시 함수의 결과는 파일의 어느 블록에 레코드를 배치해야하는지 지정

Data Dictionary Storage

Data dictionary 는 메타데이터를 저장 (Data about data)
Metadata 가 relation 에 대해 갖는 정보

• Name of relations(database)
• Names types and lengths of Attributes of each relation
• Names and definitions of views
• Integrity Contraints
• 유저 및 계정 정보
• 통계 데이터
• 물리적 파일 구성 정보
  • 어떤 Relation 이 저장되는지 (Sequential/ hash )
  • Relation 의 물리적 저장위치
• Index 에 대한 정보

Storage Access

Block 은 스토리지 할당 및 데이터 전송의 단위
데이터베이스는 디스크와 메모리 사이의 블록 전송 횟수를 최소화하고자 함
메인메모리에 가능한 많은 블록을 보관하면 디스크 액세스 횟수를 줄일 수 있음

Buffer

디스크 블록의 사본을 저장하는 데 사용할 수 있는 메인 메모리의 파티션
Partition of main memory available to store copies of disk blocks

Buffer Manager

Subsystem responsible for allocating buffer space in main memory

역할 : 디스크에서 블록이 필요할때 호출

• 블록이 이미 버퍼에 있을 경우
  • Returns the address of the block in main memory
• 블록이 버퍼에 없을 경우
  • If there is free space
    • Allocate new block in the buffer (새로운 블록 할당)
  • If there is no free space
    • Replacing (throwing out) some other block (새로운 블록을 위한 공간을 만들기 위해)
    • !블록은 디스크에서 읽고 쓸 수 있는 최소 단위이고, 페이지는 낸드 플래시 메모리의 기본 단위
    • 교체된 블록은 최근 디스크에 쓰거나/읽은 후 수정된 경우에만 다시 디스크에서 사용
  • 디스크에서 블록을 버퍼로 읽고 Requester 에게 메인 메모리에서 블록의 주소를 반환

Buffer Replacement Strategy

: 버퍼 관리자가 메모리 공간을 효율적으로 사용하기 위해 사용하는 알고리즘

고정 블록 (Pinned block)

• 디스크에 다시 쓰여서는 안 되는 메모리 블록

[!note]
버퍼의 크기와 블록의 크기를 미리 정해 놓고, 버퍼의 모든 블록을 항상 사용 가능한 상태로 유지하는 방식

• 디스크의 데이터를 메인 메모리에 복사하는 것은 시간이 많이 걸리는 작업입니다. 디스크의 데이터를 디스크에 다시 쓰면, 이 작업을 다시 해야 합니다.
• 디스크의 데이터를 디스크에 다시 쓰면, 디스크의 쓰기 작업이 발생합니다. 디스크의 쓰기 작업은 디스크의 수명을 단축시킬 수 있습니다.
• 따라서 고정 블록 버퍼는 디스크의 데이터를 메인 메모리에 임시로 저장하는 용도로만 사용해야 합니다.

공유 및 독점 잠금 버퍼 (Shared and exclusive locks buffer)

• 동시 작업이 이동/재정렬되는 페이지 내용을 읽고 한 번에 하나씩 이동/재정렬 하기 위해 필요
• Readers get shared lock, update to a block require
  (독자는 공유 잠금을 얻고, 블록 업데이트에는 독점 잠금이 필요)

Locking rules

• 한 번에 하나의 프로세스만 Exclusive Lock
• Shared Lock 은 Exclusive Lock 과 동시에 사용할 수 없음
• 여러 프로세스에 동시에 Shared Lock을 부여 가능

[!note]
공유 잠금의 예

• 여러 사용자가 동시에 같은 테이블에서 레코드를 읽는 경우, 각 사용자는 해당 레코드에 대해 공유 잠금을 얻습니다. 이렇게 하면 모든 사용자가 해당 레코드를 읽을 수 있지만 수정할 수는 없습니다.

독점 잠금의 예

• 한 사용자가 테이블에서 레코드를 수정하는 경우, 해당 사용자는 해당 레코드에 대해 독점 잠금을 얻습니다. 이렇게 하면 다른 사용자는 해당 레코드를 읽거나 수정할 수 없습니다.

Buffer-Replacement Polices

대부분의 OS 는 가장 최근에 사용한 블록을 대체하는 LRU Strategy 사용

• Use Past pattern of block references as a predictor of future references
  

• LRU : 캐시가 가득 차서 캐시에 없는 새로운 페이지가 참조될 떄 가장 마지막에 사용한 페이지를 제거
  

Column-Oriented Storage

Store each column of a relation separately


장점 : Reduced I/O if only some columns are accessed (열이 적으면 좋음)
단점 :

1. Cost of record reconstruction from columnar representation
   (열 바탕으로 레코드를 재구성하는 데 비용 소모)
2. Cost of record deletion and update

Tradition (레코드가 행으로 이루어진) 표현이 Transaction processing 에 더 적합
몇몇 데이터베이스는 두 표현을 모두 지원 : Hybrid row/column stores

---

“이 글은 Obsidian 에서 작성되어 업로드 되었습니다”