바이너리 리드-솔로몬 인코딩

이 기사에는 여러 가지 문제가 있습니다.이를 개선하거나 토크 페이지에서 이러한 문제를 논의할 수 있도록 도와주시기 바랍니다.(이러한 템플릿 메시지를 제거하는 방법 및 시기에 대해 알아보십시오.) 이 기사는 고아입니다. 다른 기사는 연결되어 있지 않습니다.관련 기사에서 이 페이지에 대한 링크를 소개하십시오. 제안을 보려면 링크 찾기 도구를 사용하십시오. (2016년 8월) 이 문서는 위키백과의 품질 기준을 충족하기 위해 정리가 필요할 수 있습니다.구체적인 문제는: 깨진 테이블, 영어가 아닌 다이어그램, 불분명한 텍스트입니다. 가능하다면 이 기사를 개선할 수 있도록 도와주세요.(2018년 6월) (이 템플릿 메시지를 제거하는 방법 및 시기에 대해 알아보기) (이 템플릿 메시지를 제거하는 방법 및 시기에 대해 알아보십시오.)

RS 코드에 속하는 BRS(Binary Reed-Solomon Coding)는 분산 스토리지 환경에서 노드 데이터 손실을 해결할 수 있는 인코딩 방법입니다.MDS(Maximum Distance Separable) 인코딩 속성이 있습니다.인코딩 및 디코딩 속도는 기존 RS 코딩과 최적의 CRS 코딩을 능가합니다.

배경

RS 코딩은 분산 스토리지 환경을 위한 내결함성 인코딩 방법입니다.예를 들어 하드웨어 RAID 설정과 같이 스토리지 용량 또는 대역폭을 개선하기 위해 k개의 개별 장치에 데이터를 분산한다고 가정합니다.이러한 구성은 장치 장애 발생 시 상당한 데이터 손실 위험이 있습니다.리드-솔로몬 인코딩은 m 노드의 모든 하위 집합의 동시 실패에 강한 스토리지 코딩 시스템을 생성합니다.이를 위해 총 n = k + m 스토리지 노드에 대해 m개의 노드를 시스템에 추가합니다.

전통적인 RS 인코딩 방법은 Vandermonde 행렬을 코딩 행렬로 사용하고 그 역행렬을 디코딩 행렬로 사용합니다.기존의 RS 인코딩 및 디코딩 작업은 모두 대규모 유한 도메인에서 수행됩니다.

BRS 인코딩 및 디코딩은 시프트 및 XOR 작업만 사용하기 때문에 기존 RS 코딩보다 훨씬 빠릅니다.BRS 코딩 알고리즘은 베이징 대학의 첨단 네트워크 기술 연구소에서 제안하고 BRS 코딩의 오픈 소스 구현도 공개했습니다.실제 환경 테스트에서 BRS의 인코딩 및 디코딩 속도는 CRS보다 빠릅니다.분산 스토리지 시스템의 설계 및 구현에서 BRS 코딩을 사용하면 시스템이 내결함성 재생의 특성을 가질 수 있습니다.

원리

BRS 인코딩 원리

전통적인 리드-솔로몬 코드의 구조는 유한 필드를 기반으로 하며, BRS 코드는 시프트와 XOR 연산을 기반으로 하며, BRS 인코딩은 반데르몽드 행렬을 기반으로 하며, 구체적인 인코딩 단계는 다음과 같습니다.

1、원래 데이터 블록을 k개의 블록으로 균등하게 분할하고, 각 데이터 블록에는 L-bit 데이터가 있으며, 다음과 같이 기록됩니다.

${\displaystyle S=(s_{0},s_{1},...,s_{k-1}} 표시}$

여기서 ${\displaystyle {}_{}}$ $=$, ${\displaystyle {}_{}{}_{}}$ ${\displaystyle {si,}_{}{1}_{}}$.${\displaystyle }$. ${\displaystyle {si,L}_{}}$ -$$ {{$displaystyle s_{i$}=$s_{i,0}s_{i,1}...$$s_{i,L-1}},$ i $=$ ${\displaystyle 0,}$ ${\displaystyle 1,}$ ${\displaystyle 2,}$ ${\displaystyle .,}$k - ${\displaystyle 1}${{$displaystyle$ i=$0, 1$, $2,$ ..., $k-1}.$

2$、$보정 데이터 블록 M${displaystyle$M} ， ${displaystyle$ $M}$에는 총${\displaystyle }$n -$$의 $블록$이 있습니다.

${\displaystyle M=(m_{0},m_{1},...,m_{n-k-1})}$

여기서 ${\displaystyle {mi}_{}}$${\displaystyle =}$ ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle \underset{}{\overset{}{j}}}$ = ${\displaystyle \underset{}{\overset{}{}}}$k - ${\displaystyle \underset{}{\overset{}{1}}}$ ${\displaystyle s_{}}$j (${\displaystyle r_{}^{}}$ ${\displaystyle {}_{}^{}}$ {\$displaystyle m_{i}=\sum$ _{$j$=0}^{$k-1}s_{j$}($r_{j}^{i})},$ i = ${\displaystyle 0,1,.,n}$ -${\displaystyle k}$ -$$ {$displaystyle$ i=$0, ..., n-k-1}.$

여기에 추가된 모든 XOR 연산은 $({$가 원래 데이터 ${\displaystyle {블록}_{}}$ j$({$ 앞에 추가된 "0"의 비트 수를 나타냅니다$$.따라서 패리티 데이터 $블록{\displaystyle {}_{}}$ ${{$ ${$는 다음과 같은 방식으로 제공됩니다.

${\displaystyle(r_{0}^{a},r_{1}^{a},r_{k-1}^{a})=(0,a,2a,...(k-1)a)}$

$여기$서 a $=$ ${\displaystyle 0,}$ ${\displaystyle 1,}$.${\displaystyle n}$ ${\displaystyle -k}$ - ${\displaystyle 1}$ ${\displaystyle$a = $0,$ 1, ...$n-k-1}.$

3、각 노드는 데이터를 저장하고 노드 ${\displaystyle {Ni}_{}i}$ $=$ ${\displaystyle 0}$${\displaystyle {}_{}}$ ${\displaystyle 1,}$. ${\displaystyle .,n}$ - $)$ {{displaystyle $N_{i}(i$=$0$$,$ $1,$ ..., $n-1)$ {\$displaystyle s_. .,$ -${\displaystyle {}_{}{1}_{}}$, $,$ m${\displaystyle }$- ${\displaystyle k_{}}$- ${\displaystyle {1,}_{}}$ m - k - 1$,$ $..., s_k$- 1, {$k$ - 1},$$ $m$- k - 1, m - 1, m - 1,$$m - 1, m - 1, m - 1, m - 1, m - 1, m - 1${\displaystyle {}_{}}$ m - 1, ${\displaystyle {}_{}}$ - 1$,$ m -

BRS 인코딩 예제

$이제{\displaystyle }$ ${\displaystyle \mathrm{n}=}$ ${\displaystyle 6}$, ${\displaystyle \mathrm{k}}$ $=$ 3 {\$displaystyle$n ${\displaystyle {}_{}}$ 6, k $$$=$ $3$이면 ${\displaystyle {ID\mathrm{}}_{}}$ 0${\displaystyle }$${\displaystyle {}_{}}$${\displaystyle }$($0$ 0${\displaystyle ,}$ 0$)$ $$\$displaystyle ID_${0}$$${\displaystyle {}_{}}$${\displaystyle }$(${\displaystyle 0,}$${\displaystyle {}_{}}$${\displaystyle 1}$, 2$) \displaystyle$ $ID_${0} $$$=$$$(${\displaystyle 0,}$ ${\displaystyle 2}$, 4$)$ ${\displaystyle {ID\mathrm{}}_{}}$ ${\displaystyle {}_{}}$${\displaystyle {}_{}}$${\displaystyle =}$ (${\displaystyle {0\mathrm{}}_{}}$$,$ s, $0,$${\displaystyle {}_{}}$$)$ 원본 ${\displaystyle {}_{}}$입니다${\displaystyle .}$${\displaystyle s_{}}$L -$$({$i}$${\displaystyle =}$$s_{0},s_{1},...,s_{L-1}},$ $여기$서 i ${\displaystyle {}_{}}$ $1$ ${\displaystyle .,k}$ -$$({$displaystyle$ i$=$$,$ 1, ..., ${\displaystyle {...,}_{}}$ $$$k-1$}), 각 블록에 대한 보정 ${\displaystyle {데이터}_{}}$는 m ${\displaystyle {=}_{}}$ ${\displaystyle {}_{}{}_{,}}$ ${\displaystyle 0_{}}$ ${\displaystyle \mathrm{mi},}$ 1${\displaystyle {}_{}{m}_{}}$ x${\displaystyle {,L}_{}}$ + i${\displaystyle {}_{}}$($k$ - ${\displaystyle {1)}_{}}$ - $1(\$ ={i_${i},$ {$m+1,$ i_1$},$ i_m_1, $i_1$, i_m_1, $i_$${\displaystyle ,k}$ - ${displaystyle$ i$=0,1,...,k-1}.$

보정 데이터 블록의 계산은 다음과 같습니다. 추가 작업은 비트 XOR 작업을 나타냅니다.

${\displaystyle {m\mathrm{}}_{}}$ 0${\displaystyle {}_{}}$${\displaystyle {}_{}}$ ${\displaystyle {s\mathrm{}}_{}}$0 (${\displaystyle 0)}$ ${\displaystyle \oplus }$ ${\displaystyle {s\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$(${\displaystyle 0)}$ ⊕ ${\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$($)$ \$displaystyle m_{0$}=$s_{0}(0)\oplus s_{1}(0)\$oplus $s_{2}(0$$$${\displaystyle {som\mathrm{}}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ $=$ (${\displaystyle {}_{}{}_{}}$ 0, $0$ 1${\displaystyle .{0\mathrm{}}_{}}$ ${\displaystyle {\mathrm{m}}_{}}$,${\displaystyle {}_{}}$5$)$ \$displaystyle m_{0}$ =($0,$ 0, 0$,$ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,$m_{0,5}}$

${\displaystyle {m\mathrm{}}_{}}$ 1 ${\displaystyle {}_{}}$ ${\displaystyle {s\mathrm{}}_{}}$0 (${\displaystyle 0)}$ ${\displaystyle \oplus }$ ${\displaystyle {}_{}{1\mathrm{}}_{}}$ (${\displaystyle 1)}$ ⊕ ${\displaystyle {}_{}{2\mathrm{}}_{}}$ ($)$ \$displaystyle m_{1$}=$s_{0}(0)\oplus s_{1}(1)\oplus s_{2}(2$ ${\displaystyle {som\mathrm{}}_{}}$ 1 $=$ ($m1$ ${\displaystyle {}_{}{}_{m1\mathrm{}},}$ $.0$ m1${\displaystyle {,}_{}}$ $)$ \$displaystylease m_{$1} = ($m1,$ 1, 1, 0 $m1},$ 7$)$

${\displaystyle {m2\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {s\mathrm{}}_{}}$0 (${\displaystyle 0)}$ ${\displaystyle \oplus }$ ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$(${\displaystyle 2)}$ ⊕ ${\displaystyle {}_{}{2\mathrm{}}_{}}$ ($)$ \$displaystyle m_{2$}=$s_{0}(0)\oplus s_{1$$}($$2)\oplus s_{2}(4$ ${\displaystyle {som\mathrm{}}_{}}$ 2 $=$ ($m2,$ ${\displaystyle {0m2\mathrm{},}_{}}$ ${\displaystyle 1_{}.{m2\mathrm{},}_{}}$ $9)$ \$displaystyle m_{2}$=($m2,$ 0m2, 0m2, $0m2$, 0m2, $0m2)$

BRS 디코딩 원리

BRS 코드의 구조에서 원래 데이터 블록을$$k{$displaystyle$k}개의$$ $블록$으로 나눕니다.$S{\displaystyle }$ $=$ (${\displaystyle {s\mathrm{}}_{}}$ 0${\displaystyle {}_{}}$ ${\displaystyle {}_{}{1\mathrm{}}_{}}$,${\displaystyle }$. , ${\displaystyle s_{}}$- ${\displaystyle 1_{}}$ )$${$displaystyle$ S=($s_{0}, s_${1$}, ..., s_${k-1$\}\}$입니다. 인코딩은$n개의 displaystyle$n 블록$$ 보정 데이터 블록이며, ${\displaystyle M_{}}$ ${\displaystyle =({m0\mathrm{}}_{}}$m1${\displaystyle ,}$.,${\displaystyle {}_{}}$- ${\displaystyle {\mathrm{k}}_{}}$ -${\displaystyle {}_{}}$1 ) {$m$- k - k -$$1$}개의 displaystyle$ M =($m_{m_0},$ .$m-k$ -1)입니다.

디코딩 프로세스 중에 다음과 같은 조건이 필요합니다.손상되지 않은 교정 데이터 블록의 수는 누락된 원래 데이터 블록의 수보다 크거나 같아야 합니다. 누락되지 않은 경우 복구할 수 없습니다.

다음은 디코딩 프로세스 분석입니다.

n $=$ ${\displaystyle 6}${$displaystyle$ n $=$$$$6{\displaystyle }$ $$}, ${\displaystyle \mathrm{k}}$= 3 {$displaystyle k$= 3}으로 만드는 $것$이 좋습니다. 그러면

${\displaystyle m_{0}=s_{0}+s_{1}+s_{2}}}$

${\displaystyle m_{1}=s_{0}+{1}+x^{2}s_{2}}$

${\displaystyle m_{1}=s_{0}+x^{2}s_{1}+x^{4}s_{2}}$

$({$이(가) 손상되지 $않은{\displaystyle {}_{}}$ 것으로 ${\displaystyle {가정}_{}}$합니다${\displaystyle {}_{}}$$$s $,$ s 2({$1}, s_{2$}} 누락, m$$1({$displaystyle m_{1$ ${\displaystyle {m\mathrm{}}_{}}$2({$displaystyle m_{2})$를 $선택$하여 복구합니다.

${\displaystyle m_{1}^{*}=m_{1}+s_{0}}$

${\displaystyle m_{2}^{*}=m_{2}+s_{0}}$

$({$ $m_{$$1}}$ $$，$$ $({$ ${\displaystyle {}_{}^{}}$ ${\displaystyle {s\mathrm{}}_{}}$0({{$0}})$이 ${\displaystyle {}_{}^{}}$ ${\displaystyle {있으므로\mathrm{}}_{}^{}}$$m1$({{$displaystyle m_$${$1}^{*}) ${\displaystyle {}_{}^{}}$$m2$({{2$}^{*})$가 알려져 $있습니다{\displaystyle {}_{}^{}}$.하도록

${\displaystyle s_{1,i-2}=m_{2,i}^{*}+s_{2,i-4}}$

${\displaystyle s_{2,i-2}=m_{1,i}^{*}+s_{1,i-1}}$

위의 반복 공식에 따르면, 각 사이클은 두 개의 비트 값(${\displaystyle {s\mathrm{}}_{}}$ $1$ s 2 {{$1},$을 알아낼 수$$ 있습니다.각각의 원래 데이터 블록 길이$(${$displaystyle$ L$$$}$비트)를 L${displaystyle$ L$}$회$$ $반복$하면 원래 데이터 블록에서 알 수 없는 모든 비트를 해결할 수 있습니다. 추론의 패리티로 데이터 디코딩을 완료할 수 있습니다.

성능

일부 실험에 따르면 인코딩 속도를 고려할 때 단일 코어 프로세서에서 BRS 인코딩 속도는 RS 인코딩 속도의 약 6배, CRS 인코딩 속도의 약 1.5배로 RS 인코딩과 비교할 때 200% 이상으로 인코딩 속도가 업그레이드됩니다.

동일한 조건에서 삭제 횟수가 다른 경우 BRS 디코딩 속도는 RS 인코딩 속도의 약 4배, CRS 디코딩 속도의 약 1.3배로 RS 인코딩에 비해 디코딩 속도가 100% 향상됩니다.

적용들

현재 상황에서는 분산 시스템의 적용이 일반적으로 사용됩니다.삭제 코드를 사용하여 분산 스토리지 시스템의 하단에 데이터를 저장하면 시스템의 내결함성을 높일 수 있습니다.동시에 기존 복제 전략에 비해 소거 코드 기술은 동일한 중복성에 대한 시스템의 안정성을 기하급수적으로 향상시킬 수 있습니다.

BRS 인코딩은 분산 스토리지 시스템에 적용할 수 있습니다. 예를 들어 HDFS를 사용하는 동안 BRS 인코딩을 기본 데이터 인코딩으로 사용할 수 있습니다.성능의 이점과 인코딩 방법의 유사성으로 인해 BRS 인코딩을 사용하여 분산 시스템의 CRS 인코딩을 대체할 수 있습니다.

사용.

C로 작성된 BRS 인코딩을 구현하기 위한 오픈 소스 코드가 있으며 GitHub에서 사용할 수 있습니다.분산 스토리지 시스템의 설계 및 구현에서는 BRS 인코딩을 사용하여 데이터를 저장하고 시스템 자체의 내결함성을 달성할 수 있습니다.

레퍼런스

• H. Hou, K. W. Shum, M.Chen과 H. Li, BASIC Regeneration Code: 정확한 수리를 위한 이진 추가 및 이동, IEEE ISIT 2013.
• Jun Chen, Hui Li, Hanxu Hou, Bing Zhu, Tai Zhou, Lijia Lu, Yumeng Zhang, 최적의 인코딩과 효율적인 디코딩을 갖춘 새로운 지그재그 MDS 코드 [C]//Big Data (Big Data), 2014 IEEE International Conference on.IEEE, 2014.