소거 부호

부호 이론에서 **소거 부호** 또는 **이레이저 코드**(erasure code)는 비트 오류(비트 에러) 대신 비트 소거를 가정하는 전방 오류 정정(FEC) 부호로, k개의 심볼로 이루어진 메시지를 n개의 심볼로 이루어진 더 긴 메시지(코드워드)로 변환하여 원래 메시지를 n개의 심볼 중 일부로 복구할 수 있게 한다. r = k/n 비율을 부호율이라고 한다. k’/k 비율(여기서 k’는 복구에 필요한 심볼 수를 나타냄)을 수신 효율이라고 한다. 복구 알고리즘은 n개의 심볼 중 어느 심볼이 손실되었는지 알고 있다고 가정한다.
# 역사
소거 부호화는 1960년에 어빙 리드와 구스타프 솔로몬이 발명했다. language=en 다양한 소거 부호화 방식이 있다. 가장 널리 사용되는 소거 부호는 리드-솔로몬 부호, 저밀도 패리티 검사 부호(LDPC 부호), 터보 코드이다. 2023년 현재, 최신 데이터 저장 시스템은 세 가지 접근 방식 중 하나를 사용하여 데이터 손실 없이 몇 개의 디스크가 완전히 고장 나는 것을 허용하도록 설계될 수 있다. language=en language=en-US language=en * 복제 * RAID * 소거 부호화 기술적으로 RAID는 일종의 소거 부호로 볼 수 있지만, Dimitri Pertin, Alexandre van Kempen, Benoît Parrein, Nicolas Normand. "Comparison of RAID-6 Erasure Codes". The third Sino-French Workshop on Information and Communication Technologies, SIFWICT 2015, Jun 2015, Nantes, France. ffhal-01162047f "RAID"는 일반적으로 단일 호스트 컴퓨터(단일 실패 지점)에 연결된 배열에 적용되는 반면, "소거 부호화"는 일반적으로 여러 호스트를 의미하며, 때로는 저가 서버의 중복 배열(RAIS)이라고도 한다. 소거 부호는 해당 호스트 중 하나라도 작동을 멈출 때 작업이 계속될 수 있도록 한다. language=en-us 블록 수준 RAID 시스템과 비교할 때, 객체 저장소 소거 부호화는 더 높은 탄력성을 제공하는 몇 가지 중요한 차이점이 있다. language=en language=en archive-date=2023-10-04 language=en archive-date=August 7, 2020
# 최적 소거 부호
최적 소거 부호는 n개의 코드워드 심볼 중 k개만으로도 원래 메시지를 복구할 수 있는 속성을 가진다(즉, 최적의 수신 효율을 가짐). 최적 소거 부호는 최대 거리 분리 부호(MDS 부호)이다.
## 패리티 검사
패리티 검사는 n = k + 1인 특수한 경우이다. k개의 값 \\{v_i\\}_{1\leq i \leq k}에서 체크섬이 계산되고 k개의 원본 값에 추가된다. :v_{k+1}= - \sum_{i=1}^k v_i. 이제 k + 1개의 값 \\{v_i\\}_{1\leq i \leq k+1}은 체크섬에 대해 일관성이 있다. 이 값들 중 하나인 v_e가 지워지면, 나머지 변수들을 합하여 쉽게 복구할 수 있다. :v_{e}= - \sum_{i=1 ,i \neq e }^{k+1}v_i. RAID 5는 XOR를 사용하는 패리티 검사 소거 부호의 널리 사용되는 응용이다.
## 다항식 과표본화
==== 예: 오류 메일(k = 2) ==== k = 2인 간단한 경우, 두 원래 심볼 사이의 선을 따라 다른 지점을 샘플링하여 중복 심볼을 만들 수 있다. 이는 오류 메일이라는 간단한 예로 설명된다. 앨리스는 오류 메일을 사용하여 자신의 전화번호(555629)를 밥에게 보내고 싶어 한다. 오류 메일은 이메일과 거의 동일하게 작동하지만, 다음과 같은 차이가 있다. #메일의 약 절반이 손실된다. #5자보다 긴 메시지는 허용되지 않는다. #매우 비싸다(항공 우편과 비슷). 앨리스는 밥에게 보낸 메시지의 확인을 요청하는 대신 다음 방식을 고안한다. #전화번호를 두 부분으로 나눈다: a = 555, b = 629. 그리고 "A=555"와 "B=629" 두 메시지를 밥에게 보낸다. #선형 함수 f(i) = a + (b-a)(i-1), 이 경우 f(i) = 555 + 74(i-1)를 구성하여 f(1) = 555이고 f(2) = 629가 되도록 한다. 파일:Code d'effacement optimal #f(3), f(4), f(5) 값을 계산한 다음, "C=703", "D=777", "E=851" 세 개의 중복 메시지를 전송한다. 밥은 f(k)의 형태가 f(i) = a + (b-a)(i-1)이며, 여기서 a와 b는 전화번호의 두 부분이라는 것을 알고 있다. 이제 밥이 "D=777"과 "E=851"을 받았다고 가정해 보자. 파일:Code d'effacement optimal 밥은 받은 값(f(4)와 f(5))으로부터 a와 b의 값을 계산하여 앨리스의 전화번호를 재구성할 수 있다. 밥은 어떤 두 오류 메일을 사용해서도 이 절차를 수행할 수 있으므로, 이 예의 소거 부호는 40%의 부호율을 가진다. 앨리스는 전화번호를 하나의 오류 메일로 인코딩할 수 없다는 점에 유의해야 한다. 전화번호는 여섯 자를 포함하고, 하나의 오류 메일 메시지의 최대 길이는 다섯 자이기 때문이다. 만약 그녀가 전화번호를 조각으로 보내 각 조각의 수신 확인을 밥에게 요청했다면, 어쨌든 최소 네 개의 메시지(앨리스로부터 두 개, 밥으로부터 두 개의 확인)가 전송되어야 했을 것이다. 따라서 다섯 개의 메시지를 요구하는 이 예의 소거 부호는 매우 경제적이다. 이 예가 약간 인위적이라는 점에 주목해야 한다. 진정으로 일반적인 소거 부호가 어떤 데이터 집합에서도 작동하려면 주어진 f(i) 외의 다른 것이 필요하다.
### 일반적인 경우
위의 선형 구성은 다항식 보간법으로 일반화될 수 있다. 또한, 이제 점들은 유한체를 통해 계산된다. 먼저 순서가 최소 n 이상인 유한체 F를 선택하지만, 보통 2의 거듭제곱을 사용한다. 송신자는 데이터 심볼에 0부터 k − 1까지 번호를 매기고 보낸다. 그런 다음 p(i)가 데이터 심볼 i와 같도록 k차수의 라그랑주 다항식 p(x)를 구성한다. 그리고 p(k), ..., p(n − 1)을 보낸다. 수신자는 이제 k개의 심볼을 성공적으로 수신한 경우, 다항식 보간법을 사용하여 손실된 패킷을 복구할 수 있다. F의 순서가 2b(여기서 b는 심볼의 비트 수)보다 작으면 여러 다항식을 사용할 수 있다. 송신자는 심볼 k부터 n − 1을 '즉석에서' 구성할 수 있다. 즉, 심볼 전송 간에 작업 부하를 균등하게 분배할 수 있다. 수신자가 계산을 '즉석에서' 수행하려면, 새로운 다항식 q를 구성할 수 있다. q(i) = p(i)는 심볼 i 0). ε를 줄이는 것은 CPU 시간을 희생해야 한다. 거의 최적의 소거 부호는 보정 능력과 계산 복잡성을 교환한다. 실용적인 알고리즘은 선형 시간 복잡도로 인코딩 및 디코딩할 수 있다. 분수 코드(무율 소거 부호라고도 함)는 거의 최적의 소거 부호의 주목할 만한 예이다. 이들은 k개의 심볼 메시지를 거의 무한한 인코딩 형태로 변환할 수 있다. 즉, 오류 수정에 사용될 수 있는 임의의 양의 중복 심볼을 생성할 수 있다. 수신자는 k개보다 약간 더 많은 인코딩된 심볼을 받은 후 디코딩을 시작할 수 있다. 재생 코드는 기존 인코딩된 조각에서 손실된 인코딩된 조각을 재구성(복구라고도 함)하는 문제를 다룬다. 이 문제는 인코딩된 중복성을 유지하기 위한 통신이 문제가 되는 분산 저장 시스템에서 발생한다.
# 저장 시스템에서의 소거 부호화 적용
소거 부호화는 이제 신뢰할 수 있는 데이터 저장을 위한 표준 관행이다. "Erasure Encoding—Practice and Principles". 2016\. Matt Sarrel. "Erasure Coding 101". 2022\. Brian Beach. "Backblaze Open-sources Reed-Solomon Erasure Coding Source Code". 2015\. 특히, 아파치 하둡, Linux에 내장된 RAID-6, Microsoft Azure, Facebook 콜드 스토리지, Backblaze Vaults에서 리드 솔로몬 부호의 다양한 구현이 사용된다. Rashmi Vinayak. "Erasure Coding for Big-data Systems: Theory and Practice". 2016\. p. 2: section "Abstract". p. 9: section "Systematic codes". p. 12: section "Regenerating codes". 저장 시스템에서 오류로부터 복구하는 고전적인 방법은 복제를 사용하는 것이었다. 그러나 복제는 낭비되는 바이트 측면에서 상당한 오버헤드를 발생시킨다. 따라서 데이터 센터에서 사용되는 것과 같은 점점 더 큰 저장 시스템은 소거 부호화된 저장을 사용한다. 저장 시스템에서 사용되는 가장 일반적인 형태의 소거 부호화는 리드 솔로몬 부호이다. 이는 패리티 블록이라고 불리는 알려진 데이터 조각으로부터 누락된 데이터를 재생할 수 있도록 하는 고급 수학 공식이다. (k, r) RS 코드에서 "청크"라고 불리는 주어진 **k** 데이터 블록은 (*k* + *r*) 청크로 인코딩된다. 총 청크 집합은 "스트라이프"를 구성한다. 인코딩은 (*k* + *r*) 청크 중 최소 *k*개가 사용 가능한 한 전체 데이터를 복구할 수 있도록 수행된다. 이는 (*k*, *mr*) RS 인코딩된 저장이 최대 *m*개의 오류를 허용할 수 있음을 의미한다. (이는 표준 RS(*n*, *k*) 표기법과 다르며, *n* = *k* + *r*이다.)
## RS(10,4)
**예:** Facebook에서 HDFS(현재 아파치 하둡의 일부)에 사용되는 RS(10, 4) 코드에서는 10MB의 사용자 데이터가 10개의 1MB 블록으로 나뉜다. 그런 다음 중복성을 제공하기 위해 4개의 추가 1MB 패리티 블록이 생성된다. 이는 최대 4개의 동시 오류를 허용할 수 있다. 여기서 저장 오버헤드는 14/10 = 1.4배이다.conference=FAST '15 완전히 복제된 시스템의 경우, 10MB의 사용자 데이터는 최대 4개의 동시 오류를 허용하기 위해 4번 복제되어야 한다. 이 경우 저장 오버헤드는 50/10 = 5배가 된다. 이는 전체 복제에 비해 소거 부호화된 저장의 낮은 저장 오버헤드와 오늘날 저장 시스템에서 그 매력을 보여준다. Hitchhiker scheme은 RS 코딩과 결합되어 데이터 블록 재구성에 필요한 계산 및 데이터 전송량을 줄일 수 있다. 또한 HDFS 코덱으로도 구현되어 있지만, 사용하려면 정책을 수동으로 정의해야 한다.
## 핫 데이터
처음에는 소거 코드가 "콜드"(드물게 액세스되는) 데이터를 효율적으로 저장하는 비용을 줄이는 데 사용되었지만, 소거 코드는 더 간단한 중복 방식(미러링)에 비해 "핫"(더 자주 액세스되는) 데이터를 서비스하는 성능을 향상시키는 데도 사용될 수 있다. 성능을 향상시키는 소거 부호화의 고전적인 예는 RAID 5이다. 이는 RAID 1에 비해 더 적은 하드 드라이브를 필요로 하면서 동일한 단일 드라이브 고장 보호를 제공한다. 추가 하드 드라이브는 더 많은 데이터를 저장하고 RAID 5의 향상된 읽기/쓰기 속도 배율을 활용하는 데 사용될 수 있다. 이는 처리 능력이 충분하다고 가정할 경우 RAID 6(이중 중복: 패리티 하나와 소거 코드 하나)에도 적용된다. 일반화된 RAID는 어떤 수의 중복 드라이브와도 작동할 수 있다. 일반화된 RAID에는 두 가지 표기법이 있다. RAID7.x는 x개의 중복 드라이브를 가진 시스템을 의미하며, 최대 x개의 드라이브가 고장 났을 때 복구를 허용한다.doi=10.1145/1661785.1670144 또는 RAID N+M은 N개의 일반 데이터 드라이브와 M개의 중복 드라이브를 의미하며, M개의 드라이브가 고장 났을 때 모든 데이터를 복구할 수 있다. 더 진보된 예는 클러스터 캐시인 EC-캐시이다. 즉, 여러 노드에 분산된 캐시이다. 이러한 시스템은 한 노드가 더 인기 있는 항목을 호스팅할 때 부하 불균형을 겪을 수 있으며, 이 문제를 해결하는 일반적인 방법은 선택적 복제, 즉 더 인기 있는 객체에 대해 더 많은 복제본을 생성하는 것이다. 그러나 이 방법은 사용 가능한 메모리 양에 의해 제한된다. 각 객체를 개별적으로 k개의 분할과 r개의 중복 단위로 나누면, 최소한의 메모리 낭비로 완벽한 부하 분산을 달성할 수 있다.
# 예시
다양한 코드의 구현 예는 다음과 같다.
## 거의 최적의 소거 부호
* 토네이도 코드 * 저밀도 패리티 검사 코드
## 거의 최적의 분수(무율 소거) 코드
* 분수 코드 * 온라인 코드 * LT 코드 * 랩터 코드 * 네트워크 코드 * 삼각 코드
## 최적 소거 부호
* XOR 패리티, 하나의 소거 가능한 심볼 추가. RAID4, RAID5에 사용된다. * 리드 솔로몬 부호. 소거 모드에서 사용될 때 최적이며, k개의 추가 심볼에 대해 k개의 소거를 허용한다. 오류 수정 모드에서 사용될 때도 최적이며, floor(k''/2)개의 오류를 허용한다. ** Parchive 파일 형식 1.0, 2.0 및 (오픈) 3.0은 RS를 사용한다. 3.0은 다른 선형 코드도 지원한다. ** RAID6은 다양한 최적 소거 코드를 사용하지만, RS가 일반적인 선택이다. ** Tahoe-LAFS에는 클래식 RS의 구현인 zfec가 포함되어 있다. * 소거 복원력 있는 체계적 코드, 동일한 심볼 크기에서 리드-솔로몬보다 더 많은 중복 패킷을 허용하는 MDS 코드, 2비트 RS(4,2) 또는 3비트 RS(9,2) 참조 * 재생 코드s2cid=260559901archive-date=2017-07-31 *다른 모든 최대 거리 분리 부호