[데이터베이스시스템#11~14]해싱과 특수 인덱스

1. 정적 해싱

해시 : 탐색키에 산술적인 연산을 통해 버킷의 주소를 계산하는 해시함수를 사용해 데이터 배분 및 접근

버킷 : 한 개 이상의 레코드를 저장할 수 있는 저장공간의 단위, 디스크 블록의 크기와 일치

 

특징

- 버킷의 개수가 고정된 해싱 기법

- 키 값이 K인 레코드 삽입

- 키 값이 K인 레코드 검색

 

충돌 : 서로 다른 두 레코드가 동일한 버킷에 대응

동거자 : 충돌에 의해 같은 버킷 주소를 갖는 레코드

 

오버플로

- 버킷에 레코드를 저장할 수 있는 여유 공간 X

- 추가적인 버킷을 할당 or 다음 버킷에 할당

- 접근 시간이 길어지고 해시 성능 저하

 

해시 인덱스

- 해시 파일 구조와 동작 방식을 레코드가 아닌 인덱스 엔트리에 적용한 인덱스

 

문제점

- DB의 크기가 커짐에 따른 성능 감소

- 미리 큰 공간을 잡을 경우 초기에 상당한 양의 공간이 낭비

- 재구성 시 새롭게 선택된 해시 함수를 사용해 모든 레코드에 대해 다시 계산하고 버킷에 할당

2. 동적 해싱

정의 : 버킷의 개수를 가변적으로 조절 가능, DB의 크기에 따라 비례

DB의 증대 or 축소에 따른 인덱스의 구조를 조절하기 위해 해시 함수를 동적 변경

 

확장성 해싱

- 모조키 : 레코드의 탐색키 값이 해시 함수에 의해 일정 길이의 비트 스트링으로 변환된 키

- 버킷 헤더 : 정수값이 저장되어있음을 표시

3. 비트맵 인덱스

탐색키의 중복 비율이 높은 컬럼을 대상으로 질의를 효율적으로 처리하기 위해 고안된 특수한 형태의 인덱스

비트맵 : 간단한 비트의 배열, 릴레이션에 있는 레코드의 수 n개만큼 n개의 비트로 표현

활용 : 컬럼에 대한 값의 범위가 유한, 비교적 개수가 적은 규모일 때 용이

크기 : 레코드의 크기가 수백 바이트 이상이 되어도 비트맵 인덱스에서는 하나의 비트로 표시

---

1. 트랜잭션의 이해

데이터 동시 접근의 문제

- 동일 데이터에 다수 사용자의 접근 허용 시 일관성이 훼손

 

트랜잭션의 개념

- DB 를 조작하기 위한 하나의 논리적 단위를 이루는 일련의 연산의 집합

- DB를 사용하여 처리하는 작업을 하늬 묶음으로 인식하여 묶음단위로 실행되도록 정의한 개념

 

트랜잭션의 특징

- 다수의 연산으로 구성된 트랜잭션이 사용자에게 단일작업처럼 다뤄지도록 ACID 특징을 준수

- ACID 특성 : 원자성, 일관성, 고립성, 지속성

 

트랜잭션의 연산

- Read(X) : DB에서 데이터 X를 읽고, 트랜잭션이 실행되는 메모리 변수 X에 값을 저장

- Write(X) : 트랜잭션이 실행되는 메모리에 있는 변수 X의 값을 DB에 저장

 

트랜잭션 실행의 연산

- Commit : 데이터 항목의 값을 DB에 반영, 지속성을 확보

- Rollback : 트랜잭션이 중단되기 이전까지 수행한 연산에 의해 갱신된 모든 데이터 항목의 값을 무효화하여 일관성 확보

2. 트랜잭션의 동시성

동시성 고려

- DBMS는 다수의 사용자가 DB를 공용으로 사용하기 위한 목적으로 도입

- 트랜잭션 동시 실행의 이점(트랜잭션 처리율 + 자원 이용률 향상, 대기 시간 감소)

- 다중 사용자 환경에서 트랜잭션의 동시 실행으로 데이터 갱신 시, 일관성 훼손 문제가 발생

- 동시성 제어

 

적용 트랜잭션

병렬 스케줄 : 비순차적 실행되는 스케줄, 일관성 훼손 발생 가능

직렬 가능 스케줄 : 복수개의 트랜잭션이 동시에 수행된 결과가 직렬 스케줄의 결과와 동일

충돌 동등 : 특정 스케줄에서 충돌이 일어나지 않는 연산의 순서를 바꿔 스케줄로 변환이 가능한 상태

3. 트랜잭션의 특성

회복 : 원자성을 보장하기 위해 트랜잭션 실패 시 실행된 모든 연산을 실행 이전 상태로 복원

비연쇄적 스케줄 : 연쇄적 롤백으로 발생할 수 있는 대량의 회복 연산을 방지

---

1. 락 기반 규약

- 트랜잭션 직렬화와 회복화는 스케줄이 데이터 일관성에 영향을 미치는 여부를 판별하고 유지되는 상태로 복원시키기 위해 정의

- 일관성 훼손을 발생시키는 트랜잭션에 대해 동시성 제어를 통해 일관성 유지에 개입

- 동시성 제어 규약 : 락 기반, 타임스탬프 기반, 검증 기반

 

락 기반 규약

개념 : 직렬 가능성을 보장하기 위해 락을 사용해 데이터 항목에 연산 적용 전 트랜잭션이 락을 획득하고 연산 후 반납하도록 하는 규약 (공유, 배타)

락 양립성 : 트랜잭션은 연산하고자 하는 데이터에 대한 락을 획득해야만 연산 진행 가능

확장 단계 : 락을 얻을 수 있으나 반납할 수 없는 단계

축소 단계 : 락을 반납할 수는 있지만 새로운 락을 얻을 수 없는 단계

 

2. 타임스탬프 기반 규약

개념 : 각 트랜잭션 실행의 순서를 판단하기 위해 타임스탬프 부여

시스템 클럭 값 :

논리적 계수기 :

 

토마스 기록 규칙

3. 교착상태

개념 : 특정 트랜잭션 집합 내에 속하는 모든 트랜잭션이 집합 내의 다른 트랜잭션을 기다리고 있는 상태

처리방법 : 교착상태 발생이 비교적 높은 시스템의 경우,

교착상태 방지 : 타임스탬프 이용,

교착상태 회복 : 희생자 선정, 희생자 롤백, 무한정 기다림 해결

---

1. 회복 시스템의 개념

예상치 못한 HW/SW 오류 발생

오류 발생 이전의 일관된 상태로 DB를 복원시키는 기법이 요구

DB는 데이터 복원 절차 내재화

 

시스템 실패의 유형

- 트랜잭션 실패 : 논리적, 시스템적

- 시스템 장애 : 시스템의 하드웨어 고장, 소프트웨어의 오류

- 디스크 실패 : 비휘발성 디스크 저장장치의 손상 및 고장으로 인한 데이터 손실

 

구성 : 백업, 로그

 

데이터 저장 구조

- 데이터는 디스크와 같은 비휘발성 저장장치에 저장되며, 전체 데이터의 일부만 주기억장치에 상주

- 데이터베이스는 데이터를 블럭 단위로 전송, 블럭 단위로 기억장소를 분할

- 트랜잭션은 디스크로부터 주기억장치로 데이터를 가져오며 변경된 데이터는 다시 디스크에 반영

 

데이터베이스 연산 : 메인 메모리와 디스크 사이의 연산

 

2. 로그 기반 회복

DB가 수행한 모든 수정 작업을 기록한 여러 종류의 로그를 사용하여 회복

WAL : 트랜잭션은 DB 수정 전, 로그 레코드를 생성

 

Redo : 수정된 새로운 값으로 DB의 데이터 항목값을 수정

Undo : 수정된 모든 데이터 항목을 이전 값으로 복귀, 완료 후 기록

 

DB 변경 : 트랜잭션의 일부 변경 사항이 버퍼 블록에만 반영

트랜잭션 커밋 : 로그 레코드가 안정된 저장장치에 기록 완료 시 커밋, 기록되기 전 장애가 있으면 롤백

 

회복의 유형 : 갱신 작업이 디스크에 반영되는 시점에 따라 구분

지연 갱신 회복 : 부분 커밋까지 디스크 반영을 지연시키고 로그만 기록

즉시 갱신 회복 : 갱신 요청을 곧바로 디스크에 반영

 

3. 회복 알고리즘

1. 로그를 역방향으로 탐색

2. 로그 레코드에 대해 기록

3. 로그 레코드를 찾아 역방향 탐색을 중단

 

시스템 장애 후 회복 알고리즘

- Redo : 순방향 로그

- Undo : 트랜잭션 롤백 알고리즘