공부하는 개발 블로그

1. 데이터베이스의 필요성

1) 대량의 데이터에서 빠른 검색.

2) 대량의 데이터를 메모리 내에서 관리하기 어렵다

3) 장애 복구

4) 병렬성 제어(동시 작업)

5) 데이터 무결성 보장

2. 인덱스

- <id, 주소> 형태

원하는 정보가 어느 주소에 위치하는지 빠르게 찾기 위함.

레코드가 고정 길이인 경우, 고정길이 * id를 하면 주소를 알 수 있지만, 버려지는 정보가 많을 수 있다.

인덱스를 이용하면 가변 길이를 이용하면서도 주소를 빨리 구할 수 있다.

- B+ tree : root/branch.leaf 블록이 존재.

리프 블록만 데이터를 가짐.

리프 블록에서 리프 블록으로 이동 가능. ->  등호, 전방일치 등 범위 검색 가능

branch 노드도 데이터를 갖는 경우: B- tree

-인덱스 병합: 여러 개의 인덱스를 사용하는 경우, 각 인덱스로 검색 -> AND/OR

- 업데이트 속도를 향상시키기 위해: 데이터가 추가될때마다 업데이트(ranom write) 하지 않고, 메모리나 파일에 모아두었다가 한번에 업데이트한다.(sequential write.) 예: MySQL innoDB

- B+ 트리의 인덱스 값이 변경된 경우, 리프 블록의 내용도 변경해야하는 경우가 존재한다 : 리프 분할

동시에 여러 클라이언트에서 하는 경우 문제가 생길 수 있음. -> LOCK 사용

파티션 테이블 : 사용자에게는 테이블이 하나지만 내부로는 복수의 테이블로 관리, 인덱스도 복수로 구분 -> 병렬 갱신 가능.

3. 테이블과 릴레이션

◆ - 참조 무결성:

정규화 이론

1) 제1 정규화: 테이블 구성에서 중복/반복/복합값을 포함한 구조 제거

2) 제2 정규화: 일부 열에 의해 결정되는 열 제거

3) 제3 정규화: 모든 열은 기본키에 의해 값이 하나로 결정되어야한다.

4. 장애와 대응

1) RAID

하나의 서버를 여러 개의 HDD에 탑재하고 동일한 데이터를 두 개 이상의 HDD에 분산하는 기술

RAID 0: 복수의 HDD에 데이터 기록, 읽고 쓰기. 이용 가능 용량 - 디스크 개수

RAID 1: 두 대의 HDD에 동일한 데이터 작성. 이용 가능 용량 - 디스크 수의 반절

RAID 5: 오류 정정 부호인 패리티 데이터와 함께 분산하는 방식. 이용가능 용량 - 디스크 수-1개

2) 복제

-1) 단방향

마스터 -> 슬레이브 : 바이너리 로그 전송.

슬레이브는 바이너리 로그를 실행함으로써 마스터와 동일한 상태가 됨.

- 단방향/비동기(MySQL 채택)

슬레이브가 바이너리 로그를 받아서 실행을 완료하기 전까지는 동일하지 않음.

- 단방향/준동기화

슬레이브에 바이너리 로그가 도착할 때까지 마스터가 기다린 뒤 다시 실행 시작.

시간이 조금 더 걸림.

- 단방향/동기화

슬레이브에서 처리를 마칠때 까지 마스터가 기다림.

-2) 양방향

MySQL cluster : 데이터 노드라는 특수 서버에서 데이터를 가지고 있음.

여러 데이터 노드가 동일한 데이터 가짐.

한 데이터 노드 업데이트 -> 다른 데이터 노드에 동기화

3) 장애 대처: 현재는 슬레이브가 다운되면 새로 만들어 전체 복구하는 방법 채택

데이터양이 많을 수록 부하 증가.

5. 트랜잭션

1) 처리 중간에 멈춘 상태에서 데이터 복구

2) 무정지성 : 장애 발생 뒤에도 다시 정상가동을 도움(백업 이후의 처리에 대한 기록이 남음)

LSN(Log Sequence Number)가 증가하고 REDO 로그 생성.

commit마다 데이터를 변경하는 것이 아니라 redo 로그를 생성한뒤 한 번에 처리

sequential write은 처리가 빠르므로 부하 작음.

◆

샤딩:

같은 테이블 스키마를 가진 데이터를 다수의 데이터베이스에 분산하여 저장하는 방법

무결성

1. 영역 무결성

- 한 컬럼에 대해 NULL의 허용 여부와 타당한 데이터 값들을 지정합니다.

- 자료형(Data type), 규칙과 제약(Rules), 값 범위 등을 제한합니다.

2. 참조 무결성

- 기본 키와 참조 키 간의 관계가 항상 유지됨을 보장합니다.

- 참조되는 테이블의 행을 이를 참조하는 참조키가 존재하는 한 삭제될 수 없고, 기본키도 변경될 수 없습니다.

3. 개체 무결성

- 테이블에 있는 모든 행들이 유일한 식별자를 가질 것을 요구합니다.

출처: https://jwprogramming.tistory.com/53 [개발자를 꿈꾸는 프로그래머]

1. DB 구성

클라이언트 : SQL을 주는(요청을 하는) 프로그램

서버: SQL을 처리하는 프로그램

2. SQL

DDL : Data Definition Language: CREATE, DROP, ALTER

DML : Data Manipulation Language: SELECT, INSERT, DELETE

DCL : Data Control Language: COMMIT(실행 확정), ROLLBACK(실행 취소), GRANT(권한 부여), REVOKE(권한 제거)

3. SQL작성 규칙

- 마지막에 ;

- 대문자, 소문자 구분이 없다.

4. 이름 짓기 규칙

- 영문자, 숫자, 언더바(_)만 가능

- 첫글자는 영어

5. SQL 규칙

1) 집약과 정렬

- WHERE은 FROM 바로 뒤에 온다.

- GROUPBY 는 WHERE 뒤에 온다.

- FROM -> WHERE -> GROUP BY -> HAVING -> ORDER BY

: 실행 순서는 WHERE -> GROUP BY -> HAVING -> SELECT -> ORDER BY.

(따라서 GROUP BY에는 약칭 사용 불가)

(따라서 ORDER BY에는 약칭 사용 가능/ 집약 함수 사용 가능)

- 주석은 -- 와 /* */

- GROUP BY: 행에 대한 조건

- HAVING: 그룹에 대한 조건

6. 연산자

- =와 <>

- IS NULL ( NULL은 비교 연산시 -> 불명(UNKNOWN)

- AVG

7. transaction

세트로 실행해야할 하나 이상의 갱신 처리 집합

BEGIN TRANSACTION;

COMMIT;

ACID 특성

Atomic(원자성): 트랜잭션이 끝난 시점에 모든 갱신 처리가 실행된 상태/모두 실행되지 않은 상태로 종료되는 것을 보증

Consistency(일관성): 트랜잭션의 처리는 데이터베이스의 제약(NOT NULL 등)을 지킨다.

Isolation(독립성): 트랜잭션간에 서로 간섭하지 않는다.

Durability(지속성): 트랜젝션이 종료되면 해당 시점의 데이터 상태가 지속된다.

8. 뷰

- ORDER BY 사용 불가

- DISTINCT, GROUP BY, HAVING 사용 안하는 경우, FROM에 테이블이 하나인 경우, 갱신 가능

9. 서브쿼리

- 마지막에 AS로 이름을 붙인다.

- 스칼라 서브쿼리: 값이 하나인 서브쿼리 -> SELECT문이나 WHERE에 사용 가능

SELECT goods_id FROM Goods

WHERE sell_price > (SELECT AVG(sell_price) FROM Goods);

- 상품 분류별 평균 판매 가격을 비교하자.

SELECT goods_id, goods_name

FROM Goods AS S1

WHERE sell_price > (SELECT AVG(sell_price) FROM Goods AS S2

WHERE S1.goods_class = S2.goods_class 

GROUP BY goods_classs);

10. 함수

1) 함수

- || : 문자열 연결( 'abc' 'de -> 'abcde'

- LENGTH : 문자열 길이

- REPLACE(<col>, <from>, <to>)

- SUBSTRING(<col> FROM <start> TO <counts>)

- CURRENT_DATE, CURRENT_TIME, CURRENT_TIMESTAMP

- EXTRACT(<datetime type> FROM <date>) : 날짜 요소 추출

- CAST(<pre> AS <post>) : 형변환

- COALESCE(<data1> <data2> ...): 처음으로 NULL이 아닌 값 반환

2) 술어

 - LIKE , %

- BETWEEN:

SELECT * FROM <table> WHERE sell_price BETWEEN 10 AND 100;

- IN: 서브쿼리 사용 가능

SELECT * FROM <table> WHERE goods_id IN (1,2,3);

SELECT * FROM <table> WHERE goods_id IN (SELECT goods_id FROM Storegoods

WHERE sell_price > 500);

- EXIST: 조건을 만족하는 레코드가 존재하는가?

SELECT * FROM <table> WHERE EXISTS (SELECT goods_id FROM Storegoods AS TS

WHERE TS.sell_price > 500

AND TS.store_id = '00C');

3) CASE

검색 case문

SELECT goods_name, 

CASE WHEN goods_class  = '의류' THEN 'A:' || goods_class

 WHEN goods_class  = '사무용품' THEN 'B:' || goods_class

 WHEN goods_class  = '주방용품' THEN 'C:' || goods_class

 ELSE NULL

END AS abc_class

FROM Goods;

단순 case문

SELECT goods_name,

CASE goods_class  WHEN '의류' THEN 'A:' || goods_class

 goods_class WHEN '사무용품' THEN 'B:' || goods_class

 goods_class WHEN '주방용품' THEN 'C:' || goods_class

 ELSE NULL

END AS abc_class

FROM Goods;

4) 집합 연산

<SELECT문>

UNION

<SELECT문>

 - 열의 수와 데이터 타입이 동일할것

- UNION ALL은 중복 허용

- INTERSECT

- EXCEPT: 차집합

5) JOIN

INNER JOIN, OUTER JOIN

FROM 뒤에 온다. FROM과 한몸!

FROM -> JOIN -> WHERE

11. 윈도우 함수

<윈도우 함수> OVER (PARTITION BY <columns> ORDER BY <columns>)

PARTITION BY 생략 가능

1) RANK : 순위

SELECT goods_name, RANK() OVER (PARTITION BY goods_class ORDER BY sell_price)

FROM Goods;

2) DENSE_RANK: 중복이 있어도 후순위를 건너뛰지 않음.

3) ROW_NUMBER: 순위에 상관 없이 연속 번호

4) 집약 함수 사용

-1) SUM

SELECT goods_name, SUM(sell_price) OVER (ORDER BY goods_id) AS current_sum

FROM Goods;

누적 합계

-2) 이동평균

SELECT goods_name, SUM(sell_price) OVER (ORDER BY goods_id ROWS 2 PRECEDING) AS current_sum

FROM Goods;

앞의 2 행을 포함한 이동평균.

FOLLOWING 사용 가능

ROWS BETWEEN 1 PRECEDING AND 1 FOLLOWING

12. GROUPIN 함수

1) ROLLUP : 그룹별 값 -> 그룹을 통합한 값

2) GROUPIN

3) CUBE

4) SETS

CREATE DATABASE <>;

CREATE TABLE <>;

DROP TABLE <>;

◆ ALTER TABLE <> ADD COLUMN <column name> <datatype> <constraint>;

◆ ALTER TABLE <> DROP COLUMN <>;

◆ ALTER TABLE <> RENAME TO <>; RENAME TABLE <> TO <>;

◆ SELECT '상수' AS <sangsu column name> FROM <>;

◆ SELECT DISTINCT <> FROM <>;

◆ SELECT DISTINCT COUNT(goods_classify) FROM GOODS; 행수를 센 뒤에 중복 제거

◆ SELECT SUM(DISTINCT sell_price) FROM GOODS; 중복 제거 뒤 합.

◆

INSERT INTO <table name> (<column names>) VALUES (<values>);

INSERT INTO <table name> VALUES (<values>);

INSERT INTO <table name> (<column names>)

SELECT <columns> FROM <table name>;

DELETE <> FROM <> WHERE ;

UPDATE <table name> SET <column name> = <value> WHERE <>;

UPDATE <table name> SET sell_price = sell_price * 10;

CREATE VIEW <>  (<view colums>)

AS

<select 문>;

웹 캐슁은 캐슁의 대상이 되는 객체들의 크기와 인출 비용이 일정하지 않으므로 기존의 캐슁과 다른 성격을 가진다.

1)

1) LRU-K: 최근 K번째 참조를 이용

2) LRUF: 각 참조에 가중치를 주어서 계산. 오래될 수록 낮은 가중치를 가짐.

시간 지역성, 객체 인기도(참조 횟수)

노화 기법(aging) : 오래 전에 잉루어진 참조에 대해서 가중치를 줄여나가는 것

캐쉬 오염(cache pollution): 전혀 참조되지 않은 객체가 캐쉬에 유지되는 것.

3. 웹 캐쉬의 일관성 유지 기법

1) pollinv-every-time: 캐쉬 내에 존재하는 객체에 대한 요청이 있을 때마다 근원지 서버에 객체의 변경 여부를 확인하는 방법

2) invalidation: 근원지 서버가 자신의 객체를 캐슁하는 모든 프락시 서버를 기록하고 있다가 객체가 변경된 경우 해당 프락시 서버에 알려주는 방법

3) adaptive TTL(time-to-live): 캐쉬 내에 이미 존재하는 요청이 있을 때 해당 객체에 대한 최종 변경 시각과 최종 변경 확인 시각을 고려해서 변경되었을 가능성이 높다고 판단되는 경우에만 근원지서버에서 변경 여부를 확인한다. 상용 프락시 서버가 사용하는 방식.

변경 가능성 : LMF(Last Modified Facctor)

LMF = (C-V)/(V-M)

C: 현재 시각

V: 최종 확인 시각(validation), M: 최종 변경 시각(modified)

9.1 디스크 구조

디스크에는 데이터가 일정한 크기로 저장됨: 논리 블럭(logical block)

물리적 저장 위치: 섹터(sector)

sector - logical block: 일대일 매핑

디스크는 원판으로 구성.

원판은 트랙으로 구성.

트랙은 섹터로 구성.

섹터에 최소한의 단위 정보가 저장됨.

상대적 위치가 동일한 트랙들의 집합: 실린더.

9.2 디스크 스케줄링

◆디스크 접근 시간(access time) = 탐색 시간 + 회전 지연 시간 + 전송 시간

탐색 시간(seek time) : 디스크 헤드를 해당 실린더로 이동시키는데  걸리는 시간. 원판 안/밖 이동 시간

회전 지연 시간(rotational latency): 디스크가 회전해서 읽고 쓰려는 섹터가 헤드에 도달하는데 걸리는 시간

전송 시간(transfer time): 데이터를 실제로 섹터에 읽고 쓰는 데 소요되는 시간

탐색 시간을 줄이는 것이 핵심

◆

1) FCFS(Fist Come First Served)

2) SSTF(Shorted Seek Time First): 현재위치에서 가장 가까운 위치에 있는 요청. 기아(starvation)발생 가능

3) SCAN(=엘리베이터 스케줄링 알고리즘): 한쪽 끝에서 한쪽 끝으로. 기아, 이동거리에서 효율적이지만 바깥쪽이 안쪽보다 평균 대기 시간이 긺.

4) C-SCAN(Circular SCAN): SCAN과 비슷하나, 한쪽 끝에 도달하면 다시 시작점으로 돌아가서 처리. 돌아가는 길에는 처리 X. 이동거리는 길어지지만 탐색 시간의 편차는 줄일 수 있음..

5) LOOK: 헤드의 진행방향에 더 이상 요청이 없으면 turn.

   C-LOOK: 헤드의 진행방향에 더 이상 요청이 없으면 시작점으로 돌아감.

9.3 다중 디스크 환경에서의 스케줄링

여러 디스크에 데이터가 중복해서 저장된 경우.

어느 디스크에서 작업을 수행할지?에 대한 문제

탐색 시간을 줄이기

디스크간의 부하가 균형을 이루도록

저전력을 원하면 일부 디스크에 요청 집중. -> 디스크에서 요청을 수용할 수 있을 정도에만

9.4 디스크의 저전력 관리

1) 비활성화 기법

활동(active): 헤드가 데이터를 읽거나 쓰는 중

공회전(idle): 디스크가 회전중이지만 읽거나 쓰는 중이 아닌 경우

------ ^ 활성화. 아래: 비활성화

준비(standby): 디스크가 회전하지는 않지만 인터페이스가 활성화

휴면(sleep): 디스크 회전 X 인터페이스 비활성화

비활성 상태가 활성 상태보다 전력 소모가 적으나, 비활성 때 요청을 처리하는 경우 추가 에너지 소모가 든다.

언제 비활성화 할지 결정하는 알고리즘:

시간 기반 : 일정 시간동안 공회전 -> 정지

예측 기반 : 과거 요청을 보고 공회전 구간의 길이 예측

확률 기반: 마르코프 체인 등의 확률 모델 이용

2) 회전 속도 조절 기법

디스크 회전 속도(RPM)

3) 디스크 데이터 배치 기법

디스크 내의 복제본을 만듦. -> 헤드 위치에서 가까운 복제본 이용.

4) 버퍼 캐슁 및 사전 인출(prefetch) 기법

미래에 요청될 데이터를 알거나/예측 가능하다면 prefetch

디스크가 저전력일 때, 최대한 입출력 지연.

5) 쓰기 전략을 통한 저전력 디스크 기법

디스크가 비활성 상태일 때 쓰지 않고 기다렸다가, 활성상태가 되면 씀.

가상 메모리: 각 프로세스는 0번지에서 시작하는 고유의 주소 공간을 가짐.

8.1 요구 페이징

당장 사용할 페이지만 메모리에 올림.

입출력 시간이 단축 -> 응답시간 단축. 더 많은 프로세스 처리.

적은 메모리 필요.

페이지 부재(page fault): 페이지가 메모리에 없다.

1) page fault 처리

(1) MMU(Memory Management Unit)이 page fault trap 발생

(2) CPU으 제어권이 커널모드로 전환. page fault 처리 루틴 호출

(3) 페이지에 대한 접근이 적법한지 체크: 사용되지 않는 주소 영역? 접근 권한이 있는가?

(4) 물리 프레임에서 비어있는 프레임을 할당받아 메모리를 읽어옴

(5) 빈 프레임 없으면 swap out and swap in. 디스크 작업은 오래 걸리므로 page fault가 발생한 프로세스는 CPU를 빼앗기고 봉쇄 상태가 됨. PCB에 CPU 레지스터 상태 및 프로그램 카운터 값 저장.

(6) 디스크 입출력 완료 -> 인터럽트 -> 유효 비트로 설정 -> 봉쇄된 프로세스를 준비큐로 이동.

2) 요구 페이징의 성능

page fault의 발생 빈도에 따라 성능이 결정됨.

EAT(effective access time):

p는 page fulat rate

(1-p) * 메모리 접근 시간 + p*(page fualt 처리 오버헤드 + swap out 오버헤드 + swap in 오버헤드 + 프로세스 재시작 오버헤드)

8.2. 페이지 교체

page fault율을 최소화하는 알고리즘이 목표

1) 빌레디의 오프라인 최적 알고리즘

가장 먼 미래에 참조되는 페이지를 swap out.

페이지가 참조되는 순서를 알고 있다는 가정. 이론적. 알고리즘 성능의 상하선 제공.

2) FIFO

가장 먼저 올라왔던 페이지를 먼저 swap out.

FIFO 이상현상(FIFO anomal): 메모리를 증가시켰음에도 오히려 page fault 증가

3) LRU(Least Recently Used)

시간 지역성(temporal locality) 이용.

가장 오래 전에 참조가 이루어진 페이지를 swap out.

4) LFU(Least Frequently Used)

페이지 참조 횟수가 가장 적은 페이지 swap out.

Incache-LFU: 페이지가 물리 메모리에 올라온 순간부터 1. swap out-in 되면 1부터 다시 시작.

Perfect-LFU: 누적 참조 횟수.

참조 횟수를 저장하는 오버헤드

5) clock algorithm(=second chance algorithm, NUR, NRU: Not Used Recently)

LRU를 근사한 알고리즘.

오랫동안 참조되지 않은 페이지 중 하나 swap out.

하드웨어 지원으로 동작 -> 빠름. 대부분 사용

페이지가 참조될때마다 참조 비트 1로 set

참조비트가 1인 경우 0으로 set.(-> 한 바퀴 돌때까지 0인 페이지를 못 발견한 경우를 위함)

참조 비트가 0인 페이지를 발견하면 교체.

8.3 페이지 프레임의 할당

1)균등 할당

2) 비례 할당(proportional allocation): 프로세스의 크기에 비례하여 할당.

3) 우선순위 할당(priority allocation): 당장 CPU에서 실행될 프로세스에 더 많은 페이지 프레임 할당.

프로세스별로 최소한으로 필요한 메모리 양, 반복문 여부 등을 고려해야 더 효율적

8.4 전역 교체와 지역 교체

전역 교체: 교체 범위가 메모리 전체

지역 교체: 같은 프로세스 안의 페이지 중에서 교체

8.5 스레싱(thrashing)

page fault가 크게 상승해 CPU 이용률이 떨어지는 현상

MPD(Multi-Programming Degree): 메모리에 동시에 올라간 프로세스의 수

MPD가 낮은 경우 CPU는 더 많은 프로세스를 메모리에 올림.

그런데 너무 많은 프로세스가 올라가면, page fault 증가 -> 디스크 I/O : 시스템은 page fault 처리에 분주, CPU 이용률 감소.

=> 운영체제는 메모리 상의 프로세스가 적다고 판단하고 프로세스를 더 올림. -> page fault 더 증가. 악순환

1) 워킹셋 알고리즘(working-set algorithm)

지역성이 있는 집합(locality set)을 메모리에 동시에 올라갈 수 있도록 하는 알고리즘.

working-set: 프로세스가 일정 시간 동안 원할히 수행되기 위해 한꺼번에 메모리에 올라와 있어야하는 페이지들의 집합.

working-set의 모든 페이지가 메모리에 올라갈 수 있는 경우에만 적재. 아니면 swap out.

workng-set window: delta

working-set: 시각 t에서 시간간격 [t-delta, t] 사이에 참조된 서로 다른 페이지의 집합. 페이지가 참조된 시점으로부터 delta시간 동안은 메모리에 유지되고, 그 시점이 지나면 swap out.

working-set의 크기의 합이 메모리보다 크면 일부 swap out

working-set window의 크기가 중요.

너무 작으면: 지역성 집합 수용 X

너무 크면: MPD감소 -> CPU 이용률 낮아짐.

working-set의 크기는 시간의 흐름에 따라 변함. 동적 프레임 할당의 기능까지 수행.

2) 페이지 부재 빈도 알고리즘(page-fault frquency algorithm)

프로세스별 page fault 비율을 조사해서,

시스템에서 정한 상한보다 높은 경우, 추가 프레임 할당. 추가할 빈 프레임이 없으면 일부 프로세스 swap out

시스템에서 정한 하한보다 작은 경우, 프레임 수를 줄인다.