[OS] 36. Data Integrity and Protection

Park Yeongseo·2024년 3월 12일

OS 운영체제

OS

목록 보기

45/54

Operating Systems : Three Easy Pieces를 보고 번역 및 정리한 내용들입니다.

(OSTEP의 44장 Flash-based SSDs는 스킵합니다)

이 장에서는 다시 데이터의 신뢰성에 대해, 구체적으로는 어떻게 파일 시스템이나 스토리지 시스템이 데이터가 안전하다는 것을 보장할 수 있는지에 대해 다룬다.

이러한 영역을 데이터 무결성(data integrity), 혹은 데이터 보호(data protection)라 부르는데, 여기서는 어떻게 스토리지 시스템에 넣는 데이터가 그로부터 꺼내는 것과 동일함을 보장할 수 있는지에 대해서 다룬다.

1. Disk Failure Modes

RAID 장에서 배웠던 것처럼, 디스크는 완벽하지 않고 때로는 오류를 일으킬 수 있다. 초기 RAID 시스템에서 오류 모델은 간단했는데, 전체 디스크가 작동하거나 완전히 작동하지 않는 것이었다. 이러한 디스크의 fail-stop 오류 모델은 RAID 제작을 상대적으로 간단하게 만들었다.

하지만 현대의 디스크들은 다른 종류의 오류 모델들을 보인다. 구체적으로 현대 디스크들은 가끔, 대체로 잘 작동하기는 하지만 하나, 혹은 그 이상의 블럭에 접근할 때에 말썽을 일으키곤 한다. 구체적으로 두 종류의 단일-블럭 오류들이 흔히 일어난다. 숨은 섹터 에러(latent sector error, LSE)와 블럭 손상(block corruption)이다.

LSE는 디스크 섹터, 혹은 섹터 그룹이 손상된 경우 일어난다. 예를 들어 디스크 헤드가 디스크 표면을 건드리는 경우, 디스크 표면에 손상이 일어날 수 있고 수 비트를 읽지 못하게 만들 수 있다. 이를 헤드 크래시(head crash)라 부른다. 방사선의 경우도 비트값을 바꿔 내용을 잘못되게 만들 수도 있다. 다행히 디스크 내에는 에러 정정 코드(error correcting code, ECC)가 있어 블럭 내의 비트가 고칠 만한 것인지 그렇지 않은지를 판단할 수 있다. 만약 해당 비트가 좋지 않고, 디스크에 그런 비트를 고치기 위한 충분한 정보가 없는 경우, 그에 대한 읽기 요청은 에러를 반환한다.

디스크 자체로 검출될 수 없는 방식으로 디스크 블럭이 손상되는 경우도 있다. 예를 들어, 버그가 있는 디스크 펌웨어는 블럭을 잘못된 위치에 쓸 수 있다. 그런 경우 디스크의 ECC는 블럭 내용이 괜찮다고 말하지만, 클라이언트의 입장에서는 잘못된 블럭을 반환받게 된다. 비슷하게 오류가 있는 버스를 통해 블럭이 전달되는 경우에도 문제가 일어날 수 있다. 디스크는 이러한 종류의 오류가 일어나도 어떤 문제도 일어났다고 알려주지 않는다.

이러한 디스크 오류 모델을 가리켜 fail-partial 모델이라 부른다. fail-stop 모델에서와 마찬가지로 디스크는 완전히 동작하지 않을 수도 있고, 그와 반대로 대체로는 동작하지만 몇 개의 블럭만 접근 불가능한 상태이거나, 혹은 잘못된 내용들을 가지고 있을 수도 있다. 그러므로 동작하는 것 같이 보이는 디스크에 접근할 때, 이는 에러를 반환하거나, 혹은 에러 없이 잘못된 데이터를 반환할 수도 있다.

2. Handling Latent Sector Errors

이런 두 부분적 디스크 오류 모델에 대해 어떤 일을 할 수 있을까? 우선은 숨은 섹터 에러에 대해서 알아보자.

숨은 섹터 에러의 경우 더 탐지하기 쉽기 때문에 처리하기도 쉽다. 스토리지 시스템이 블럭에 접근하려 할 때, 디스크는 에러를 반환하고, 스토리지 시스템은 이를 바탕으로 올바른 데이터를 반환하기 위한 중복 데이터 메커니즘을 사용한다. 예를 들어 미러링된 RAID에서 시스템은 다른 복제본에 접근하고, RAID-4나 RAID-5에서 시스템은 패리티 그룹 내 다른 블럭들을 이용해 해당 블럭을 재구성한다. 그러므로 LSE와 같이 쉽게 검출되는 문제들은 이를 복구하기 위한 표준 중복 메커니즘들도 마련해놓는다.

LSE가 점점 많아지면서 RAID 설계에도 영향을 줬다. RAID-4/5 시스템에서는 디스크 전체에서의 오류와 LSE가 함께 일어날 때 문제가 발생한다. 구체적으로 전체 디스크 오류가 일어나는 경우 RAID는 패리티 그룹 내 다른 모든 디스크를 읽고 손실된 값을 재계산함으로써 디스크를 재구성하려고 한다. 그런데 재구성 중에 LSE가 다른 디스크들 중 하나에서 일어나면 이러한 재구성이 제대로 완료되지 못한다.

이 이슈를 해결하기 위해 몇몇 시스템들은 추가적인 중복을 더한다. 예를 들어, NetApp의 RAID-DP는 하나가 아니라 두 개의 동등한 패리티 디스크를 가진다. 만약 재구성 도중 LSE가 발견되면, 패리티 그룹 내의 다른 한 쪽이 손실된 블럭을 재구성하는 데에 도움을 준다. 물론 그 대가도 있는데, 각 스트라이프에 대해 두 개의 패리티 블럭들을 유지하는 비용이 높다는 것이다. 하지만 NetApp WAFL 파일 시스템의 로그-기반성이 그런 비용을 줄인다. 다른 비용으로는 공간도 있다. 두 번째 패리티 블럭에 대해 추가적인 디스크 구성이 필요하기 때문이다.

3. Detecting Corruption: The Checksum

이제 데이터 손상을 통한 조용한 오류의 문제에 대해 알아보자. 어떻게 사용자가 손상된 데이터를 받는 일을 방지할 수 있을까?

숨은 섹터 에러와 달리, 손상 문제에서는 검출이 핵심 문제다. 어떻게 알 수 있을까? 일단 알기만 한다면 복구는 이전과 같이 이뤄질 수 있다. 해당 블럭의 다른 복제본을 어딘가에 저장해놓고 쓰는 것이다.

현대 스토리지 시스템에서 데이터 무결성을 지키기 위해 쓰는 주 메커니즘은 체크섬(checksum)이라 불리는 것이다. 체크섬은 데이터 청크를 입력으로, 해당 데이터의 내용의 작은 요약본을 출력하는 함수의 결과다. 이러한 계산의 목표는 데이터 체크섬을 저장해놨다가 나중에 해당 데이터에 대한 요청이 들어왔을 때 계산한 체크섬이 원래의 값과 일치하는지를 확인함으로써, 시스템이 데이터가 어떻게든 손상되거나 바뀌었는지를 확인하는 것이다.

Common Checksum Functions

체크섬 계산을 위해 쓰이는 함수에는 여러 가지가 있는데, 그 강도와 스피드에서 차이를 보인다. 보호성이 높으면 비용도 커지는, 시스템에서 흔히 보이는 트레이드 오프가 여기서도 나타난다.

한 가지 간단한 체크섬 함수로는 XOR을 사용하는 것이 있다. XOR 기반 체크섬에서, 체크섬은 데이터 블럭의 각 청크들을 XOR함으로써 하나의 값을 만들어 냄으로써 계산된다.

16바이트 블럭에 대해 4바이트 체크섬을 계산하려고 한다고 해보자. 16바이트의 데이터는 16진법으로 다음과 같다고 한다.

365e c4cd ba14 8a92 ecef 2c3a 40be f666

이진법으로 보면 다음과 같다.

0011 0110 0101 1110     1100 0100 1100 1101
1011 1010 0001 0100     1000 1010 1001 0010
1110 1100 1110 1111     0010 1100 0011 1010
0100 0000 1011 1110     1111 0110 0110 0110

각 열에 대해 XOR을 수행했을 때의 최종 체크섬 값은 다음과 같다.

0010 0000 0001 1011 1001 0100 0000 0011

16진법으로는 0x201b9403이다.

XOR은 쓸 만하지만 한계도 있다. 예를 들어 두 데이터 청크의 같은 위치에 있는 두 비트가 모두 바뀌는 경우, 체크섬을 통해서는 데이터 손상을 탐지할 수 없게 된다. 이러한 이유로 사람들은 다른 체크섬 함수들을 만들어냈다.

다른 기초적인 체크섬 함수에는 덧셈이 있다. 이 방식은 빠르다는 장점을 가지고 있다. 데이터의 각 청크에 대해, 오버플로를 무시하고 2의 보수 덧셈을 수행하면되기 때문이다. 이 기법은 많은 데이터 변경을 찾아낼 수 있지만, 데이터가 시프트된 경우에는 잘 검출해내지 못한다.

조금 더 복잡한 알고리즘은 Fletcher checksum이라 불리는 것이다. 계산은 간단한데, 체크 바이트 $s_1, s_2$ 를 이용한다. 구체적으로, 블럭 $D$ 가 바이트 $d_1, ..., d_n$ 으로 이루어져 있다고 하자. $s_1$ 과 $s_2$ 는 각각 다음과 같이 정의된다.

\begin{aligned} s_1 = (s_1 + d_i) \mod 255\\ s_2 = (s2 + s1) \mod 255 \end{aligned}

Fletcher checksum은 거의 CRC만큼이나 강력해서, 모든 단일 비트, 두 비트 에러들도 찾아내고 그 외의 많은 에러들도 찾아낸다.

마지막으로 자주 쓰이는 체크섬으로는 순환 중복 검사(cyclic redundancy check, CRC)가 있다. 데이터 블럭 $D$ 의 체크섬을 계산하려고 한다고 해보자. 이제 할 것은 그냥 $D$ 를 큰 이진수로 보고, 이를 합의된 값 $k$ 로 나누는 것이다. 이 나눗셈의 나머지가 CRC 값이 된다.

어떤 방법을 쓰든지 완벽한 체크섬은 없다. 서로 같지 않은 데이터 블럭들이 같은 체크섬을 가질 수도 있다(충돌, collision). 따라서 좋은 체크섬 함수를 정하려면, 이러한 충돌 가능성을 줄이면서도 계산하기 쉬운 방법을 찾아야 한다.

Checksum Layout

체크섬을 어떻게 계산하는지 알게 됐으니, 이제는 체크섬을 스토리지 시스템에서 어떻게 사용할지를 보자. 다뤄야 할 첫 번째 문제는 체크섬이 어떻게 디스크에 저장되어야 하는지에 대한 것이다.

가장 기본적인 방식은 체크섬을 각 디스크 섹터, 혹은 블럭에 저장하는 것이다. 데이터 블럭 $D$ 에 대해, 그 체크섬을 $C(D)$ 라 부르도록 하자. 체크섬이 없는 경우 디스크 레이아웃은 다음과 같다.

체크섬을 이용하면 다음과 같이 각 블럭에 하나의 체크섬이 추가된다.

다만 위와 같은 레이아웃을 만드는 데 문제가 하나 발생한다. 보통 체크섬은 작고(8바이트), 디스크는 섹터 사이즈(512바이트), 혹은 그 배수의 청크들에만 쓸 수 있기 때문이다. 한 가지 해결법은 드라이브 제조사에서 체크섬의 크기를 더한, 예를 들면 520바이트 섹터를 만드는 것이다.

그런 기능이 없는 디스크들의 경우에는 파일 시스템이 어떻게 체크섬을 저장할지를 결정해야 한다. 한 가지 가능한 방법은 다음과 같다.

이 방식에서 $n$ 개의 체크섬은 하나의 섹터에 함께 저장되고, 그 뒤에는 $n$ 개의 데이터 블럭들이 저장된다. 이 방법은 모든 종류의 디스크에 적용할 수 있지만, 조금 덜 효율적일 수 있다. 만약 파일 시스템이 블럭 $D1$ 을 덮어 쓰고 싶은 경우, $C(D1)$ 이 있는 섹터를 읽고, 그 안의 $C(D1)$ 을 갱신하고, 체크섬 섹터와 새 데이터 블럭 $D1$ 을 써야 한다. 이와 달리 각 섹터에 체크섬의 자리가 마련된 앞의 경우는 한 번만 쓰면 된다.

4. Using Checksums

위와 같이 체크섬 레이아웃이 정해졌다면, 어떻게 체크섬을 사용할지에 대해 알아보자. 블럭 $D$ 를 읽을 때, 클라이언트(파일 시스템, 혹은 스토리지 컨트롤러)는 저장된 해당 블럭의 체크섬 $C_s(D)$ 도 읽는다. 이후 클라이언트는 블럭 $D$ 의 체크섬( $C_c(D)$ )을 계산하고, 두 체크섬을 비교한다. 만약 그 둘이 같으면 데이터가 손상되지 않은 것이라 판단하고 사용자에게 해당 데이터를 반환하고, 그렇지 않다면 데이터가 저장된 시점 이후에 변경되었다는 말이다. 이 경우 데이터 손상이 일어나 것이라 할 수 있다.

그렇다면 손상이 일어난 경우에는 뭘 해야할까? 만약 스토리지 시스템이 중복 복제본이 있다면 나머지 복제본을 사용하면 된다. 만약 그런 복제본이 없다면? 에러를 반환한다. 어떤 경우든, 손상 여부를 검출했다고 해서 모든 일이 풀리는 것은 아니다. 손상되지 않은 데이터를 얻을 길이 없다면 운이 없다고 생각하자.

5. A New Problem: Misdirected Writes

일반적인 경우 위의 기본 방식은 손상된 블럭들에 대해 잘 작동하지만, 현대 디스크들은 다른 해결법이 필요한, 흔치 않은 오류 모델들도 가지고 있다.

첫 번째 오류 모델은 misdirected write라 불린다. 이는 디스크나 RAID 컨트롤러에서, 제대로 된 데이터를 다른 위치에 쓰는 경우 일어난다. 예를 들면 단일 디스크 시스템에서 주소 $x$ 에 쓰여야 하는 데이터 블럭 $D_x$ 를 주소 $y$ 에 쓰는 경우가 그렇다. 다중 디스크 시스템에서는 디스크 $i$ 의 주소 $x$ 에 써야하는 데이터를 디스크 $j$ 에 쓰는 경우도 있다. 그렇다면 어떻게 이런 문제를 검출할 수 있을까? 체크섬 이외로 필요한 것에는 무엇이 있을까?

놀랍게도 해결법은 간단하다. 각 체크섬에 약간의 추가 정보들을 더하는 것이다. 이 경우 물리 식별자(physical identifier)를 추가하는 게 도움이 된다. 예를 들어 저장된 정보가 체크섬과 더불어 디스크와 블럭의 섹터 번호도 가지고 있다면, 특정 위치에 제대로 된 정보가 들어있는지를 확인할 수 있다. 구체적으로 만약 클라이언트가 디스크 10의 블럭 4를 읽는 경우( $D10.4$ ), 저장된 정보는 디스크 번호와 섹터 오프셋도 포함한다. 만약 정보가 일치하지 않으면, 잘못된 위치에 쓴 것이 되므로 데이터 손상이 검출된다.

이제 디스크에 많은 중복 정보들이 포함되었음을 볼 수 있다. 각 블럭에 디스크 번호가 각 블럭에서 반복되고, 블럭의 오프셋도 해당 블럭에 들어있다. 이런 중복 정보들이 에러 검출과 복구의 핵심이다. 약간의 추가 정보들을 통해 일어날지도 모르는 문제적 상황들을 찾아낼 수 있게 된다.

6. One Last Problem: Lost Writes

또 다른 문제도 있다. 구체적으로 몇몇 현대 저장 장치들은 lost write라 불리는 문제도 가지고 있다. 이는 장치가 상위 계층에는 쓰기 작업이 완료되었다고 알리면서도, 사실은 아무 것도 저장되지 않았을 때 발생하는 문제다. 이 경우 디스크에는 갱신되지 않은, 오래된 내용의 블럭만이 남게 된다.

문제는 이 경우, 위와 같이 체크섬이나 물리 ID를 사용하는 방법으로는 위 이슈를 발견할 수 없다는 것이다. 그렇다면 이 문제는 어떻게 알아낼 수 있을까?

가능한 해결법에는 여러 가지가 있지만, 한 가지 고전적인 방식으로는 쓰기 검증(write verify), 혹은 쓴 후 읽기(read-after-write)를 수행하는 것이다. 쓰기가 끝나면 바로 해당 내용을 읽음으로써 시스템은 원하던 데이터가 디스크 표면까지 도달했는지를 확인하는 것이다. 하지만 이 방식은 상당히 느리다. 쓰기 작업을 완료하기 위해 필요한 I/O의 수를 두 배로 늘리기 때문이다.

어떤 시스템들은 lost write를 찾기 위한 체크섬을 시스템 어디엔가 추가하기도 한다. 예를 들어 Sun의 Zettabyte File System(ZFS)의 경우, 각 파일 시스템 아이노드 및 해당 파일에 포함된 모든 블럭의 간접 블럭에 체크섬을 추가한다. 이렇게 하면 데이터 블럭에의 쓰기 자체가 손실되더라도 아이노드 내의 체크섬이 오래된 데이터와 맞지 않게 될 것이기 때문에 위와 같은 문제를 알아낼 수 있다. 아이노드와 데이터로의 쓰기가 동시에 모두 실패하는 경우에는 마찬가지의 문제가 발생할 수 있지만, 흔치는 않다.

7. Scrubbing

그렇다면 이 체크섬들이 실제로 확인되는 건 언제일까? 물론 어느 정도는 애플리케이션이 데이터에 접근할 때 일어날 수도 있지만, 이 경우 대부분의 데이터는 거의 접근되지 않기 때문에 확인되지 않은 채로 남게 된다. 확인되지 않은 데이터는 신뢰성 있는 스토리지 시스템에 문제가 될 수 있다. 조금의 흠이 전체 데이터에 영향을 줄 수도 있기 때문이다.

이 문제를 해결하기 위해, 많은 시스템들은 디스크 스크러빙(disk scrubbing)을 이용한다. 주기적으로 시스템 내 모든 블럭을 읽고 체크섬이 여전히 유효한지 확인함으로써, 디스크 시스템은 특정 데이터 아이템의 모든 복사본들이 손상되는 경우를 줄일 수 있게 된다. 보통의 시스템들은 매일 밤, 혹은 매 주 이러한 작업을 스케줄링 해놓는다.

8. Overheads Of Checksumming

데이터 보호를 위한 체크섬 사용의 오버헤드에는 무엇이 있을까? 두 가지가 있다. 공간과 시간이다.

공간 오버헤드로도 두 가지가 있다. 첫 번째는 디스크 자체에 대한 것이다. 각 저장된 체크섬은 디스크 내 공간을 차지한다. 보통은 4KB 데이터 블럭에 대해 8바이트 체크섬을 사용하고, 0.19%의 디스크 공간 오버헤드가 발생한다.

다른 종류로는 시스템 메모리에서 발생한다. 데이터에 접근할 때, 이제는 데이터 뿐만 아니라 체크섬을 위한 공간도 필요하다. 하지만 만약 시스템이 단순히 체크섬을 확인하고 이후 버린다면, 이러한 오버헤드는 오랫동안 유지되지는 않기 때문에 크게 걱정할 일이 아니다. 오직 체크섬이 메모리에 남는 경우에만 이 작은 오버헤드는 영향을 주게 된다.

이렇듯 공간적 오버헤드는 작지만, 체크섬으로 인한 시간적 오버헤드는 상당하다. 적어도 CPU는 데이터를 쓰거나 읽을 때 각 블럭에 대한 체크섬을 계산해야 한다. 이런 CPU 오버헤드를 줄이기 위해 많은 시스템들이 사용하는 방법은 데이터 복사와 체크섬 계산을 한 번에 처리하는 것이다. 복사는 어쨌든 일어나야 하기 떄문에, 복사와 체크섬 계산을 함께 하는 것은 상당히 효과적이다.

CPU 오버헤드 외에도 체크섬 방식에 따라 추가적인 I/O 오버헤드가 발생할 수 있는데, 특히 체크섬이 데이터와 별개로 저장되는 경우, 그리고 백그라운드 스크러빙을 수행해야 하는 경우 등이 있다. 전자의 경우는 설계를 통해 오버헤드가 줄어들 수 있고, 후자의 경우는 언제 스크러빙이 일어날지를 조정하는 등을 통해 줄어들 수 있다.