이것이 중복의 모습입니다

중복 코드*는 데이터 저장의 신뢰성을 높이기 위해 컴퓨터 시스템에서 널리 사용됩니다. Yandex에서는 많은 프로젝트에서 사용됩니다. 예를 들어, 내부 객체 스토리지에서 복제 대신 중복 코드를 사용하면 안정성을 희생하지 않고도 수백만 달러를 절약할 수 있습니다. 그러나 널리 사용됨에도 불구하고 중복 코드의 작동 방식에 대한 명확한 설명은 매우 드뭅니다. 이해하고 싶은 사람들은 대략 다음과 같은 상황에 직면합니다. 위키피디아):

제 이름은 Vadim이고 Yandex에서 내부 객체 스토리지 MDS를 개발하고 있습니다. 이 기사에서는 중복 코드(Reed-Solomon 및 LRC 코드)의 이론적 기초를 간단한 단어로 설명합니다. 복잡한 수학과 희귀 용어 없이 어떻게 작동하는지 알려드리겠습니다. 마지막에는 Yandex에서 중복 코드를 사용하는 예를 제시하겠습니다.

나는 많은 수학적 세부 사항을 자세히 고려하지 않을 것이지만 더 깊이 들어가고 싶은 사람들을 위해 링크를 제공할 것입니다. 또한 이 기사는 수학자를 대상으로 한 것이 아니라 문제의 본질을 이해하려는 엔지니어를 대상으로 했기 때문에 일부 수학적 정의는 엄격하지 않을 수도 있다는 점에 유의하겠습니다.

* 영어 문헌에서는 중복 코드를 삭제 코드라고도 합니다.

1. 중복코드의 본질

모든 중복 코드의 본질은 매우 간단합니다. 오류(디스크 오류, 데이터 전송 오류 등)가 발생해도 데이터가 손실되지 않도록 데이터를 저장(또는 전송)하는 것입니다.

대부분*의 중복 코드에서는 데이터를 n개의 데이터 블록으로 나누고, 이에 대해 m개의 중복 코드 블록을 계산하여 총 n+m개의 블록이 됩니다. 중복 코드는 n + m 블록 중 일부만을 사용하여 n 블록의 데이터를 복구할 수 있도록 구성됩니다. 다음으로, 블록 중복 코드, 즉 데이터가 블록으로 나누어진 코드만을 살펴보겠습니다.

n개의 데이터 블록을 모두 복구하려면 n + m개 블록 중 n개 이상이 필요합니다. n-1개 블록만 있으면 n개 블록을 얻을 수 없기 때문입니다. 이 경우 얇은 블록에서 1개 블록을 가져와야 합니다. 공기"). n + m 블록의 n 무작위 블록이 모든 데이터를 복구하기에 충분합니까? 이는 중복 코드 유형에 따라 다릅니다. 예를 들어 Reed-Solomon 코드를 사용하면 임의의 n 블록을 사용하여 모든 데이터를 복구할 수 있지만 LRC 중복 코드가 항상 그런 것은 아닙니다.

데이터 저장

데이터 저장 시스템에서는 원칙적으로 각 데이터 블록과 중복 코드 블록이 별도의 디스크에 기록됩니다. 그런 다음 임의의 디스크에 오류가 발생하더라도 원본 데이터를 계속 복원하고 읽을 수 있습니다. 여러 디스크에 동시에 장애가 발생하더라도 데이터를 복구할 수 있습니다.

데이터 전송

중복 코드를 사용하면 신뢰할 수 없는 네트워크를 통해 데이터를 안정적으로 전송할 수 있습니다. 전송된 데이터는 블록으로 나누어지고, 이에 대한 중복 코드가 계산됩니다. 데이터 블록과 중복 코드 블록은 모두 네트워크를 통해 전송됩니다. 임의의 블록(특정 블록 수까지)에서 오류가 발생하더라도 오류 없이 네트워크를 통해 데이터를 전송할 수 있습니다. 예를 들어 리드 솔로몬 코드는 광통신 회선과 위성 통신을 통해 데이터를 전송하는 데 사용됩니다.

* 이더넷 네트워크에서 데이터 전송에 널리 사용되는 해밍 코드, CRC 코드 등 데이터가 블록으로 구분되지 않는 중복 코드도 있습니다. 이는 오류 수정 코딩을 위한 코드로, 오류를 수정하는 것이 아니라 오류를 감지하도록 설계되었습니다(Hamming 코드는 오류의 부분 수정도 허용함).

2. 리드 솔로몬 코드

리드 솔로몬 코드는 가장 널리 사용되는 중복 코드 중 하나로 1960년대에 발명되었으며 1980년대에 컴팩트 디스크 대량 생산을 위해 처음으로 널리 사용되었습니다.

리드 솔로몬 코드를 이해하기 위한 두 가지 주요 질문이 있습니다. 1) 중복 코드 블록을 생성하는 방법; 2) 중복 코드 블록을 사용하여 데이터를 복구하는 방법. 그들에 대한 답을 찾아보자.
단순화를 위해 n=6, m=4라고 더 가정하겠습니다. 다른 계획도 유사하게 고려됩니다.

중복 코드 블록을 만드는 방법

중복 코드의 각 블록은 다른 블록과 독립적으로 계산됩니다. 모든 n개의 데이터 블록은 각 블록을 계산하는 데 사용됩니다. 아래 다이어그램에서 X1-X6은 데이터 블록이고, P1-P4는 중복 코드 블록입니다.

모든 데이터 블록은 크기가 동일해야 하며 정렬에는 16비트를 사용할 수 있습니다. 결과적인 중복 코드 블록은 데이터 블록과 동일한 크기가 됩니다. 모든 데이터 블록은 워드(예: XNUMX비트)로 구분됩니다. 데이터 블록을 k 단어로 분할한다고 가정해 보겠습니다. 그러면 중복 코드의 모든 블록도 k 단어로 분할됩니다.

각 중복 블록의 i번째 워드를 계산하려면 모든 데이터 블록의 i번째 워드가 사용됩니다. 다음 공식에 따라 계산됩니다.

여기서 x 값은 데이터 블록의 단어, p는 중복 코드 블록의 단어, 모든 알파, 베타, 감마 및 델타는 모든 i에 대해 동일한 특별히 선택된 숫자입니다. 이 모든 값은 일반 숫자가 아니라 갈루아 필드의 요소이며 +, -, *, / 연산은 우리 모두에게 친숙한 연산이 아니라 갈루아 요소에 도입된 특수 연산입니다. 필드.

갈루아 필드가 필요한 이유는 무엇입니까?

모든 것이 단순해 보입니다. 데이터를 블록으로, 블록을 단어로 나누고, 데이터 블록의 단어를 사용하여 중복 코드 블록의 단어를 계산하여 중복 코드 블록을 얻습니다. 일반적으로 작동 방식은 다음과 같습니다. 하지만 문제는 세부 사항에 있습니다.

1. 위에서 설명한 대로 단어 크기는 고정되어 있습니다(예제에서는 16비트). 리드-솔로몬 코드에 대한 위의 공식은 일반 정수를 사용할 때 p 계산 결과가 유효한 크기의 단어를 사용하여 표현되지 않을 수 있다는 것과 같습니다.
2. 데이터를 복구할 때 위의 공식은 데이터를 복구하기 위해 풀어야 하는 방정식 시스템으로 간주됩니다. 풀이 과정에서 정수를 서로 나누어야 하는 경우가 있는데, 이로 인해 컴퓨터 메모리에서 정확하게 표현할 수 없는 실수가 생성됩니다.

이러한 문제로 인해 리드 솔로몬 코드에 정수를 사용할 수 없습니다. 문제에 대한 해결책은 독창적이며 다음과 같이 설명할 수 있습니다. 필요한 길이(예: 16비트)의 단어를 사용하여 표현할 수 있는 특수 숫자와 이에 대한 모든 연산을 수행한 결과(추가) , 뺄셈, 곱셈, 나눗셈)도 필요한 길이의 단어를 사용하여 컴퓨터 메모리에 표시됩니다.

이러한 "특수" 숫자는 수학에서 오랫동안 연구되어 왔으며 이를 필드라고 합니다. 필드는 덧셈, 뺄셈, 곱셈, 나눗셈 연산이 정의된 요소 집합입니다.

갈루아* 필드는 필드의 두 요소에 대한 각 연산(+, -, *, /)의 고유한 결과가 있는 필드입니다. 갈루아장은 2, 2, 4, 8 등의 거듭제곱인 숫자에 대해 구성될 수 있습니다. (실제로는 모든 소수 p의 거듭제곱이지만 실제로는 16의 거듭제곱에만 관심이 있습니다.) 예를 들어, 2비트 단어의 경우 이는 16개의 요소를 포함하는 필드이며 각 쌍에 대해 모든 연산(+, -, *, /)의 결과를 찾을 수 있습니다. 위 방정식의 x, p, 알파, 베타, 감마, 델타 값은 계산 시 갈루아 필드의 요소로 간주됩니다.

따라서 우리는 적절한 컴퓨터 프로그램을 작성하여 중복 코드 블록을 구성할 수 있는 방정식 시스템을 갖게 되었습니다. 동일한 방정식 시스템을 사용하여 데이터 복구를 수행할 수 있습니다.

* 이는 엄밀한 정의가 아니라 설명입니다.

데이터를 복구하는 방법

n + m 블록 중 일부가 누락된 경우 복원이 필요합니다. 이는 데이터 블록과 중복 코드 블록이 될 수 있습니다. 데이터 블록 및/또는 중복 코드 블록이 없다는 것은 해당 x 및/또는 p 변수가 위 방정식에서 알 수 없음을 의미합니다.

리드 솔로몬 코드에 대한 방정식은 모든 알파, 베타, 감마, 델타 값이 상수이고 사용 가능한 블록에 해당하는 모든 x와 p는 알려진 변수이고 나머지 x와 p는 방정식 시스템으로 볼 수 있습니다. 알려지지 않았습니다.

예를 들어 데이터 블록 1, 2, 3과 중복 코드 블록 2를 사용할 수 없으면 i번째 단어 그룹에 대해 다음과 같은 방정식 시스템이 사용됩니다(알 수 없는 항목은 빨간색으로 표시됨).

우리는 4개의 미지수가 있는 4개의 방정식으로 구성된 시스템을 가지고 있습니다. 즉, 이 문제를 풀고 데이터를 복원할 수 있습니다!

이 방정식 시스템에서 리드 솔로몬 코드(n 데이터 블록, m 중복 코드 블록)의 데이터 복구에 대한 여러 가지 결론을 얻을 수 있습니다.

• m개 이하의 블록이 손실되면 데이터를 복구할 수 있습니다. m+1개 이상의 블록이 손실되면 데이터를 복원할 수 없습니다. 즉, m + 1개의 미지수로 m 방정식 시스템을 풀 수 없습니다.
• 하나의 데이터 블록이라도 복구하려면 나머지 블록 중 n개를 사용해야 하며 중복 코드 중 하나를 사용할 수 있습니다.

그 밖에 당신이 알아야 할 것

위의 설명에서는 고려해야 할 수학에 대한 더 깊은 탐구가 필요한 여러 가지 중요한 문제를 피했습니다. 특히 다음 사항에 대해서는 아무 말도 하지 않습니다.

• 리드-솔로몬 코드에 대한 방정식 시스템은 미지수의 모든 조합(m개 이하의 미지수)에 대해 (고유한) 해를 가져야 합니다. 이 요구 사항에 따라 알파, 베타, 감마 및 델타 값이 선택됩니다.
• 방정식 시스템은 자동으로 구성되고(사용할 수 없는 블록에 따라) 풀 수 있어야 합니다.
• 우리는 Galois 필드를 구축해야 합니다. 주어진 단어 크기에 대해 두 요소에 대한 연산(+, -, *, /)의 결과를 찾을 수 있습니다.

기사 끝에는 이러한 중요한 문제에 관한 문헌에 대한 참고 자료가 있습니다.

n과 m의 선택

실제로 n과 m을 선택하는 방법은 무엇입니까? 실제로 데이터 저장 시스템에서는 공간을 절약하기 위해 중복 코드가 사용되므로 m은 항상 n보다 작은 값으로 선택됩니다. 특정 값은 다음을 포함한 여러 요인에 따라 달라집니다.

• 데이터 저장의 신뢰성. m이 클수록 살아남을 수 있는 디스크 장애 횟수, 즉 신뢰성이 높아집니다.
• 중복 스토리지. m/n 비율이 높을수록 스토리지 중복성이 높아지고 시스템 비용이 높아집니다.
• 요청 처리 시간. n + m의 합이 클수록 요청에 대한 응답 시간이 길어집니다. 복구 중 데이터를 읽으려면 n개의 서로 다른 디스크에 저장된 n개의 블록을 읽어야 하므로 읽기 시간은 가장 느린 디스크에 따라 결정됩니다.

또한 여러 DC에 데이터를 저장하면 n과 m 선택에 추가 제한이 적용됩니다. 즉, 1개의 DC가 꺼진 경우에도 데이터를 계속 읽을 수 있어야 합니다. 예를 들어 3개의 DC에 데이터를 저장하는 경우 다음 조건이 충족되어야 합니다: m >= n/2, 그렇지 않으면 1개의 DC가 꺼지면 데이터를 읽을 수 없는 상황이 발생할 수 있습니다.

3. LRC - 지역 재건 코드

리드 솔로몬 코드를 사용하여 데이터를 복구하려면 n개의 임의 데이터 블록을 사용해야 합니다. 이는 분산 데이터 스토리지 시스템의 매우 중요한 단점입니다. 하나의 손상된 디스크에서 데이터를 복원하려면 대부분의 다른 디스크에서 데이터를 읽어야 하므로 디스크와 네트워크에 큰 추가 부하가 발생하기 때문입니다.

가장 일반적인 오류는 한 디스크의 오류 또는 과부하로 인해 한 데이터 블록에 액세스할 수 없는 것입니다. 이(가장 일반적인) 경우에 데이터 복구에 대한 초과 로드를 줄이는 것이 가능합니까? 이 목적을 위해 특별히 LRC 중복 코드가 있습니다.

LRC(Local Reconstruction Codes)는 Windows Azure Storage에서 사용하기 위해 Microsoft가 개발한 중복 코드입니다. LRC의 아이디어는 최대한 간단합니다. 모든 데이터 블록을 두 개(또는 그 이상) 그룹으로 나누고 각 그룹에 대한 중복 코드 블록의 일부를 별도로 읽는 것입니다. 그런 다음 일부 중복 코드 블록은 모든 데이터 블록(LRC에서는 글로벌 중복 코드라고 함)을 사용하여 계산되고 일부는 두 데이터 블록 그룹 중 하나를 사용하여 계산됩니다(로컬 중복 코드라고 함).

LRC는 세 개의 숫자로 표시됩니다: nrl, 여기서 n은 데이터 블록의 수, r은 글로벌 중복 코드 블록의 수, l은 로컬 중복 코드 블록의 수입니다. 하나의 데이터 블록을 사용할 수 없을 때 데이터를 읽으려면 n/l 블록만 읽어야 합니다. 이는 리드 솔로몬 코드보다 l배 적습니다.

예를 들어, LRC 6-2-2 방식을 고려해 보세요. X1–X6 — 데이터 블록 6개, P1, P2 — 전역 중복 블록 2개, P3, P4 — 로컬 중복 블록 2개.

중복 코드 블록 P1, P2는 모든 데이터 블록을 사용하여 계산됩니다. 중복 코드 블록 P3 - 데이터 블록 X1-X3을 사용하고, 중복 코드 블록 P4 - 데이터 블록 X4-X6을 사용합니다.

나머지는 Reed-Solomon 코드와 유사하게 LRC에서 수행됩니다. 중복 코드 블록의 단어 수를 계산하는 방정식은 다음과 같습니다.

숫자 알파, 베타, 감마, 델타를 선택하려면 데이터 복구 가능성(즉, 방정식 시스템 풀기)을 보장하기 위해 여러 조건을 충족해야 합니다. 이에 대한 자세한 내용은 다음에서 확인할 수 있습니다. 기사.
또한 실제로 XOR 연산은 로컬 중복 코드 P3, P4를 계산하는 데 사용됩니다.

LRC의 방정식 시스템에서 여러 가지 결론을 얻을 수 있습니다.

• 1개의 데이터 블록을 복구하려면 n/l 블록(이 예에서는 n/2)을 읽는 것으로 충분합니다.
• r + l 블록을 사용할 수 없고 모든 블록이 하나의 그룹에 포함되어 있으면 데이터를 복원할 수 없습니다. 이는 예를 들어 설명하기 쉽습니다. 블록 X1–X3 및 P3을 사용할 수 없게 하십시오. 이는 동일한 그룹의 r + l 블록(이 경우 4)입니다. 그렇다면 우리는 풀 수 없는 3개의 미지수를 가진 4개의 방정식으로 구성된 시스템을 갖게 됩니다.
• r + l 블록을 사용할 수 없는 다른 모든 경우(각 그룹에서 하나 이상의 블록을 사용할 수 있는 경우)에는 LRC의 데이터를 복원할 수 있습니다.

따라서 LRC는 단일 오류 이후 데이터를 복구하는 데 리드 솔로몬 코드보다 성능이 뛰어납니다. Reed-Solomon 코드에서는 한 블록의 데이터를 복구하려면 n 블록을 사용해야 하며, LRC에서는 한 블록의 데이터를 복구하려면 n/l 블록(예에서는 n/2)만 사용하면 충분합니다. 반면 LRC는 최대 허용 오류 수 측면에서 Reed-Solomon 코드보다 열등합니다. 위의 예에서 Reed-Solomon 코드는 임의의 4개 오류에 대해 데이터를 복구할 수 있으며, LRC의 경우 데이터를 복구할 수 없는 경우 2개 오류의 4가지 조합이 있습니다.

더 중요한 것은 특정 상황에 따라 다르지만 종종 LRC가 제공하는 초과 로드 절감 효과가 약간 덜 안정적인 스토리지보다 중요합니다.

4. 기타 중복 코드

Reed-Solomon 및 LRC 코드 외에도 다른 중복 코드가 많이 있습니다. 다른 중복 코드는 다른 수학을 사용합니다. 다음은 기타 중복 코드입니다.

• XOR 연산자를 사용한 중복 코드입니다. n개의 데이터 블록에 대해 XOR 연산을 수행하여 1블록의 중복 코드, 즉 n+1 방식(n개의 데이터 블록, 1개의 중복 코드)을 얻는다. 다음에서 사용됨 RAID 5, 데이터 블록과 중복 코드가 어레이의 모든 디스크에 주기적으로 기록됩니다.
• XOR 연산을 기반으로 하는 짝수-홀수 알고리즘입니다. 2개의 중복 코드 블록, 즉 n+2 체계를 구축할 수 있습니다.
• XOR 연산을 기반으로 하는 STAR 알고리즘입니다. 3개의 중복 코드 블록, 즉 n+3 체계를 구축할 수 있습니다.
• 피라미드 코드는 Microsoft의 또 다른 중복 코드입니다.

5. Yandex에서 사용

다수의 Yandex 인프라 프로젝트에서는 안정적인 데이터 저장을 위해 중복 코드를 사용합니다. 여기 몇 가지 예가 있어요.

• 기사 시작 부분에 쓴 MDS 내부 개체 저장소입니다.
• YT — Yandex의 MapReduce 시스템.
• YDB (Yandex 데이터베이스) - 새로운SQL 분산 데이터베이스.

MDS는 LRC 중복 코드, 8-2-2 체계를 사용합니다. 중복 코드가 있는 데이터는 12개의 서로 다른 DC(각 DC에 3개의 서버)의 서로 다른 서버에 있는 4개의 서로 다른 디스크에 기록됩니다. 이에 대해 자세히 알아보세요. 기사.

YT는 최초로 구현한 Reed-Solomon 코드(Scheme 6-3)와 LRC 중복 코드(Scheme 12-2-2)를 모두 사용하며 LRC가 선호되는 저장 방법입니다.

YDB는 짝수-홀수 기반 중복 코드를 사용합니다(그림 4-2). 이미 YDB의 중복 코드에 대해 하이로드에서 말했어요.

서로 다른 중복 코드 구성표를 사용하는 것은 시스템 요구 사항이 다르기 때문입니다. 예를 들어 MDS에서는 LRC를 사용하여 저장된 데이터가 한 번에 3개의 DC에 배치됩니다. DC 중 하나가 실패하더라도 데이터를 읽을 수 있는 상태로 유지하는 것이 중요합니다. 따라서 DC를 사용할 수 없는 경우 액세스할 수 없는 블록의 수가 허용 가능한 수준을 넘지 않도록 DC 간에 블록을 분산해야 합니다. 1-8-2 방식에서는 각 DC에 2개의 블록을 배치할 수 있으며, DC가 꺼지면 4개의 블록을 사용할 수 없으며 데이터를 읽을 수 있습니다. 4개의 DC에 배치할 때 어떤 방식을 선택하든 어쨌든 (r + l) / n >= 3가 되어야 합니다. 즉, 스토리지 중복성은 최소 0,5%가 됩니다.

YT에서는 상황이 다릅니다. 각 YT 클러스터는 완전히 1 DC(다른 DC의 다른 클러스터)에 위치하므로 그러한 제한이 없습니다. 12-2-2 방식은 33%의 중복성을 제공합니다. 즉, 데이터를 저장하는 것이 더 저렴하고 MDS 방식과 마찬가지로 최대 4개의 동시 디스크 중단에도 견딜 수 있습니다.

데이터 저장 및 처리 시스템에서 중복 코드를 사용하는 데에는 데이터 복구의 뉘앙스, 쿼리 실행 시간에 대한 복구의 영향, 데이터 기록 기능 등 더 많은 기능이 있습니다. 이러한 기능과 기타 기능에 대해 별도로 이야기하겠습니다. 주제가 흥미로울 경우 실제 중복 코드 사용에 대해 설명합니다.

6. 링크

1. Reed-Solomon 코드와 Galois 필드에 관한 일련의 기사: https://habr.com/ru/company/yadro/blog/336286/
   https://habr.com/ru/company/yadro/blog/341506/
   접근 가능한 언어로 수학을 더 깊이 살펴봅니다.
2. LRC에 관한 Microsoft 기사: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/LRC12-cheng20webpage.pdf
   섹션 2에서는 이론을 간략하게 설명하고 실제 LRC 경험을 논의합니다.
3. 짝수-홀수 방식: https://people.eecs.berkeley.edu/~kubitron/courses/cs262a-F12/handouts/papers/p245-blaum.pdf
4. STAR 방식: https://www.usenix.org/legacy/event/fast05/tech/full_papers/huang/huang.pdf
5. 피라미드 코드: https://www.microsoft.com/en-us/research/publication/pyramid-codes-flexible-schemes-to-trade-space-for-access-efficiency-in-reliable-data-storage-systems/
6. MDS의 중복 코드: https://habr.com/ru/company/yandex/blog/311806
7. YT의 중복 코드: https://habr.com/ru/company/yandex/blog/311104/
8. YDB의 중복 코드: https://www.youtube.com/watch?v=dCpfGJ35kK8

출처 : habr.com