[DB] Disk, 파일구조, Hashing, 저장소 설계

DBs are stored physicaly as files of records stored on magnetic disks.

 

storage hierarchy

• primary storage : 주기억장치
  • operated on directly by the CPU
• Secondary storage : 보조기억장치, 온라인
• Tertiary storage : 오프라인 아카이브 (온라인으로 로드 필요)

Memory Hierarchies and storage devices

상위 저장소 : 빠름, 작음, 비쌈

하위 저장소 : 느림, 큼, 쌈

Storage of DBs

• 물리적 DB 설계
• files of records : locate them efficiently

Primary FIle organizations

1. heap file(unordered file) : 첨가 순서대로 저장 (삽입 쉬움)
2. sorted file (sequential file) : 키값에 따라 정렬
3. hashed file : 해시 함수로 저장위치 결정

Secondary File organizations

• auxiliary access structure (보조 접근 구조)
• 보조 필드의 효율적인 접근. 주 파일에서 사용된.

<secondary storage devices>

hardware description of disk

• fixed angle : 고정각, 간편하여 자주 사용됨
• uniform recording density : 일정한 density로 분리, 같은 각도지만 갯수가 다름

자기디스트 (magnetic disk) : 직접 접근 저장 장치 (DASD : direct access storage device)

• 트랙 수 만큼의 실린더가 존재.
• blocks / pages : 디스크 포맷 중 OS에 의해 설정된 트랙의 동일크기 분할
• 블록은 interblock gaps(블록 간격) 로 구분됨

디스크 주소법 : addressing

• random access addressable device
• transfer unit between main memory and disk

1. 실린더 주소법 : 각 트랙의 기억용량은 일정하고 기록 밀도가 다름
2. 섹터 방법 : 섹터번호를 주고 섹터 수의 증가에 따라 연속된 섹터(클러스터)를 단위로 입출력

buffer

cluster : 다수의 연속 섹터

extent : 연속된 클러스터, 한 구역. 분산도와 비례

Disk controller : SCSI, SATA, SAS

data transfer operation

• 연산 시간 = seek time + (head 활동시간 = 거의 0이라서 고려안함) + rd + btt

회전지연 (rd) ⇒ 최대:방금 지났을떄, 최소: 바로 다음일때

Bulk transfer : 대량 전송 = btr

• 연속된 블럭 전송 시 추가적인 btt만 소요.

Making Data access more efficient on disk : 효율성 향상

1. 데이터의 버퍼링
2. 디스크에 있는 데이터의 적절한 구성
3. 요청에 앞서서 데이터 읽기
4. I/O요청의 적절한 스케줄링
5. 로그 디스크를 사용하여 쓰기를 일시중지
6. 복구를 위한 SSD나 플래시 메모리 사용

Solid State Device (SSD) storage

• use flash memories as an intermediate layer between main memory and HDDs

HDD : 데이터 연속성이 중요, 업데이트 시 덮어쓰기 됨

SSD : 어떤 주소이든 접근시간이 동일, 읽고쓰는 횟수가 정해져있으므로 수명을 위해 골고루 업데이트 필요. 덮어쓰기 없고 새로운 장소에 writing

Magnetic Tape Storage devices

• disks : random access
• magnetic tape : sequential access, blocking

가로 : tracks, 세로 : frames

• IBG = inter block gap = inter record gap, IBG보다 record시간이 작아질수록 비효율적.

CD-ROM : 반사율에 따라 결정.

• 단일 나선형 트랙, 저장밀도 일정, 균일 선형 속도

DVD : cd보다 더 큰 용량 저장 (블루레이)

< Buffering of blocks > : 미리 사용할 블럭들을 알 때 미리 버퍼를 할당하면 빨리 처리 가능

• 버퍼를 갖다놓고 그 레코드를 처리하는 동안 다른 버퍼도 실행가능(병렬 시행)
• double buffering

Buffer Management

• buffer manager : a sw component of a DBMS
• buffer pool
• pin count
• dirty bit

Buffer replacements strategies : 버퍼 교체 전략

• Least recently used : LRU
• clock policy
• first in first out : FIFO
• most recently used : MRU

<Placing file records on disk>

records and record types

file, fixed length records, viriable length record

record blocking and spanned vs unspanned

신장 방식 : 레코드를 쪼개서 빈틈없이 / 비신장 방식 : 레코드 보존, 공간낭비 있음

고정길이 blocking factor : bfr = B/R 이하의 최대정수

가변길이 bfr : 블록에 있는 레코드 수의 평균

• 필요한 블록 수 b = 레코드 수 / bfr

allocating file blocks on disk : 블록 할당

• contiguous allocation
• linked allocation
• clusters
• indexed allocation

file headers / file descriptor

• 목표 : 최소의 전송시간을 위한 블록 배치

<Operations on files> : 파일 연산

• Retrieval : 검색
• Update : 갱신
• Open/close
• record at a time (한번에 한 레코드씩만 연산되는것) : reset,find,read,findnext,delete,modify,insert
• set at a time (한번에 여러개) : findall, find n, findOrdered, Reorganize
• Scan : find + findNext + read

<Files of unordered records (Heap files)>

heap or pile file : 삽입된 순서대로 저장. 선형탐색(블럭수/2)

• 삽입 : 버퍼에 블럭 복사, 삽입, 디스크에 다시 쓰기
• 삭제 : deletion marker 사용

To read all records in order → external sorting method (잘라서 부분정렬 후 merge)

Relative or direct file

• disk 실린더랑 비슷한 연산

<Files of ordered records (sorted files)>

Ordered or sequentail files : 순차파일

• 이진탐색 : log2 (블럭 수)
• 선형탐색 : 블럭수/2 (얘가 훨씬 큰 시간)

Searchign in ordered files

• 효율적, 순차기준 아닌걸로 검색하면 의미없음

Insertion and deletion in 순차파일

• ordering field 값 기반으로 삽입
• 공간부족 시 중간중간의 여분공간(reserved space)에 삽입하거나 새 공간에 임시보관
• 삭제 시 deletion marker, periodic reorganizaiton

Using a Transaction File

• unordered file : overflow of transaction file

수정내용을 보관함. 삽입은 효율적이지만 검색은 복잡

• 비정렬 필드 수정 : 레코드 변경후 덮어쓰기
• 정렬 필드 수정 : old 레코드를 지우고 new 레코드를 삽입

Reorganization

1. sort the records in the overflow file
2. merge them with the master file

< Average Access Times for a file of b Blocks under basic file organizations >

<Hashing Techniques>

키값 함수로 주소를 구함.

search for the record within the block can be carried out in a main memory buffer

neeed only a single block access

Internal Hashing

Collision → open addressing, chaining, multiple hashing

Collision Resolutions

• open addressing : 입력한 다음주소에 저장
• chaining : 별도의 블럭할당 후 연결리스트로 연결
• multiple hashing : applies a second hash function
• 저장을 적게할수록 충돌확률이 낮아지므로 여유공간을 남기기

External Hashing for Disk files

• hashing foir disk files is called external hashing
• buckets
• key → a relative bucket number
• use a variation of chaining in each bucket

상대버킷번호를 이용하여 디스크상의 실제 주소 찾기

operations on 외부 해싱

• 검색 : 비정렬 파일에는 비싼 연산. overflow 라인을 따라서 감
• 삭제 : 버킷에서 지우고 오버플로우 라인 다음값을 채워넣기

• 수정 : 검색 후 해시필드가 아니면 그냥 덮어쓰고, 해시필드일때는 삭제 후 삽입

Static hashing : a fixed number of buckets

reorganize : change the number of blocks and 새로운 해시함수를 사용 → 부담이 큰 연산

Hashing Techniques that allow dynamic file expansion

• extendible hashing
• linear hashing
• dynamic hashing

액세스 구조는 레코드의 해시 값의 이진 표현을 기반으로 합니다.

Extendible hashing

• 이진수 주소 사용
• d=global depth of the directory, d` = local depth (≤ d)

d = d` and overflow : 더블링

d > d` for all the buckets : 해블링

 

레코드의 모조키(pseudo key) : key값을 이진 정보로 바꿔줄때 사용

💡 확장형 해싱의 장단점

• 장점 : 성능저하가 없고, 미리 공간할당할 필요 없고, 성능에 미치는 영향이 적음
• 단점 : 정적 해싱에서는 한블럭 접근하면 되지만 확장형은 2블럭에 접근해야함 (h(K)→ 디렉토리→ 버킷)

 

Dynamic hashing

Linear hashing

• overflow : split into two buckets. 오버플로된 버킷의 레코드는 다른 해시 함수를 기반으로 두 버킷 사이에 분배.
• 실제 메모리가 2배가 되는것은 아님

< Parallelizing Disk access using RAID >

• RAID : redundant arrays of inexpensive/independent disks
• 작은 여러개의 디스크를 이어서 큰 하나의 저장소처럼 사용.
• Data striping : 디스크 성능을 개선. (여러 디스크에 분할저장)
  • bit level
  • block level

Improving Reliability with RAID : 신뢰도 높이기

• 디스크가 많을수록 고장율이 높다.
• MTBF (Mean time between failures) of a disk = 22.8 years
• MTBF of 100 disk drives = 83.8 day
• 솔루션 : 데이터를 중복시키면 됨. 근데 추가적 연산이 필요하고 비용이 많이 든다.

Improving Performance with RAID

• the technique of data striping achieves 더 높은 전송 속도(전송율, tr)

RAID organizations and levels

• the two factors of granularitiy of data interleaving(striping)
• 컴퓨터가 중복정보를 사용하는 패턴

 

RAID level 0~6