CH11-2 I/O Management and Disk Scheduling

RAID(Redundant Array of Independent Disks)

단일 디스크의 한계를 극복하기 위해서 여러 개의 독립적인 디스크들을 묶어 하나의 큰 저장 장치처럼 사용

예를 들어서, 하나의 디스크에 저장되는 양을 디스크 4개에 나누는 것이기 때문에 디스크의 큐의 길이가 1/4이 된다. 속도는 4배 빨라진다.

 

RAID 목적

1. 디스크 access 시간을 빠르게 하는 것

2. recovery가 가능한 디스크 시스템을 만드는 것

 

RAID 0 (non-redundant)

하나의 데이터를 strip이라는 작은 조각으로 나눈 뒤, 여러 개의 하드디스크에 순서대로 분산하여 저장한다. strip 0, strip 1, strip 2, strip 3이 각각 다른 4개의 디스크에 나뉘어 저장되는 것을 볼 수 있다. 여러 디스크에서 동시에 데이터를 읽고 쓸 수 있어서 입출력 성능이 매우 향상된다.

 

단점으로는 데이터를 백업하는 기능이 전혀 없어서 중요한 데이터를 저장하기에는 매우 위험한 방식이다.

 

RAID 1 (mirrored)

- 데이터를 읽을 때는 파란색 디스크에서 읽으면 된다.

- 데이터를 쓸 때는 파란색, 회색에 둘 다 써야 한다.

 

회색 디스크

- 파란색 디스크의 데이터를 그대로 복제하는 디스크

 

파란색 디스크가 고장 나더라도 회색 디스크에 원본 데이터가 그대로 남아있기 때문에 데이터를 안전하게 보존할 수 있다. 데이터 복구가 매우 용이하다.

 

RAID 2 (redundancy through Hamming code)

 

파란색 디스크: 데이터 디스크

원본 데이터를 비트 단위로 잘라서 각각의 디스크에 나누어 저장한다.

 

회색 디스크: 해밍 코드 디스크

 

전채 7개의 비트 위치 중 2^n 위치에는 체크 비트(c0, c1, c2)를 배치한다.

나머지 위치(3, 5, 6, 7)에는 데이터 비트(d0, d1, d2, d3)를 배치한다.

 

c0은 데이터 비트의 위치 번호를 이진수로 표현했을 때 가장 오른쪽 비트(2^0)가 1인 모든 데이터 비트를 XOR

c1은 데이터 비트의 위치 번호를 이진수로 표현했을 때 중간 비트(2^1)가 1인 모든 데이터 비트를 XOR

c2는 데이터 비트의 위치 번호를 이진수로 표현했을 때 가장 왼쪽 비트(2^2)가 1인 모든 데이터 비트를 XOR

 

 

RAID 3 (bit-interleaved parity)

RAID 2의 오버헤드가 큰 단점을 해결하기 위한 방식이 RAID 3이다.

데이터를 비트 단위로 여러 디스크에 나누어 저장하고 데이터 복구를 위해서 하나의 패리티 디스크를 사용하는 방식

 

짝수/홀수 패리티 개념을 이용한다.

 

[짝수 패리티를 사용할 때]

4개의 데이터 비트가 1, 1, 1, 1일 경우에 패리티 디스크에는 0을 저장

 

[홀수 패리티를 사용할 때]

4개의 데이터 비트가 1, 1, 1, 1일 경우에 패리티 디스크에는 1을 저장

 

RAID 2, RAID 3의 가장 큰 한계는 데이터를 비트 단위로 나누어 저장한다는 점이다.

데이터의 한 블록을 읽기 위해서 모든 데이터 디스크에 동시에 접근하여 각 비트를 조합해야 한다. 즉, 디스크 4개를 써도 속도가 4배가 되지 않는 문제가 발생한다.

 

RAID 4 (block-level parity)

RAID 4는 데이터를 비트가 아닌 블록 단위로 나누어 저장한다.

데이터를 읽을 때, 블록이 저장된 디스크 하나에만 접근하면 돼서 디스크 개수만큼의 읽기 성능 향상을 기대할 수 있다.

 

데이터 쓰기 과정 (write) 

- 데이터 디스크: 실제 데이터 블록을 새로 쓴다.

- 패리티 디스크: 변경된 데이터를 기반으로 새로 계산된 패리티 값을 쓴다.

 

쓰기 요청이 폭주하는 상황을 가정하면, 데이터 쓰기 요청은 여러 데이터 디스크로 분산되지만, 모든 쓰기 작업에 대한 패리티 업데이트는 단 하나의 패리 디스크로 집중된다. 따라서, 패리티 디스크가 심각한 병목 현상을 일으킨다.

 

RAID 5 (block-level distributer parity)

RAID5는 RAID 4의 패리티 병목 문제를 해결하기 위해 등장했다. 

전용 패리티 디스크를 없애고, 패리티 정보를 모든 디스크에 골고루 분산시켜 저장하는 방식

 

패리티 블록이 여러 디스크에 저장되므로, 여러 쓰기 작업이 발생하더라도 패리티 업데이트 부담이 특정 디스크 하나에 집중되지 않고 여러 디스크로 분산된다.

 

Disk Cache

: 디스크 sector의 데이터를 메인 메모리에 임시로 저장하는 버퍼

자주 사용되는 데이터를 메모리에 캐싱함으로써 느린 디스크 접근 없이도 빠르게 데이터에 접근할 수 있게 한다.

 

I/O 요청 발생 시, 먼저 디스크 캐시에 해당 sector가 있는지 확인

있다면 캐시에서 바로 데이터를 반환 (디스크 접근 불필요)

없다면 디스크에서 sector를 읽어오고 캐시에 저장한 후에 응답

 

디스크 캐시가 꽉 찬 상태에서 새로운 블록을 가져와야 할 경우 기존의 블록 중 하나를 버려야 한다.

이때 어떤 블록을 버릴지 결정하는 규칙 2가지에 대해서 알아보자.

 

1) Least Recently Used

가장 오래 전에 사용된 데이터를 제거하는 방식

최근 접근된 블록은 스택의 위쪽에 위치시키고 가장 아래에 있는 블록을 제거한다.

 

2) Least Frequently Used

접근 횟수가 가장 적은 블록을 제거하는 방식

각 블록에 카운터를 두고 접근 시마다 값을 증가시킨다.

 

디스크 캐시에 도착한 블록은 counter가 1이라 앞으로 사용될 수 있는데 counter 값이 작아서 버려질 수도 있다는 문제점이 있다.

 

Frequency-based Replacement

LRU, LFU 2가지 방식을 섞은 방식

New Section, Old Section 2개 섹션 모델

블록이 캐시에 올라오면 count = 1로 초기화되고 New Section의 top 위치에 저장된다.

 

블록 재참조 시 처리 방식

- New Section에 있을 때: count 값은 증가하지 않고 블록의 위치만 top으로 이동

- Old Section에 있을 때: count 값을 +1 증가시키고 블록의 위치를 top으로 이동

 

New Section에 있는 블록은 버리지 않는다.

Old Section에 있는 블록 중에 count가 가장 작은 블록을 버린다.

New Section에서만 자주 사용되던 블록이 처음으로 Old Section으로 밀려나는 순간에 count는 1이고 이때 교체가 필요하면 실제로는 매우 자주 사용하는 블록이 바로 버려지는 문제가 발생할 수 있다.

 

New Section, Middle Section, Old Section 3개 섹션 모델의 도입

Middel Section에 있을 때 재참조가 발생하면 count 값을 +1 증가시켜주고 블록의 위치를 top으로 이동

 

New Section, Middle Section에 있는 블록은 버리지 않는다.

Old Section에 있는 블록 중에 count가 가장 작은 블록을 버린다.