Erase Coding 이란? What's the Erase coding in hadoop 3.x!!
Erase Coding 왜 사용?
- HDFS 기본 복제 체계는 스토리지 공간 및 기타 리소스에 200% 오버헤드가 있음.
- 기본적으로 1개의 원본과 2개의 복제본을 생성하기 때문임
- 따라서 동일한 수준의 내결함성을 제공하고 훨씬 적은 저장 공간을 사용하는 EC(Erase Coding)을 사용
Erase Coding Schema
아래는 하둡 문서에서 가져왔다.
The EC schema: This includes the numbers of data and parity blocks in an EC group (e.g., 6+3), as well as the codec algorithm (e.g., Reed-Solomon, XOR).
즉 Codec (인코딩/디코딩) 알고리즘으로 Reed-Solomon, XOR 이 존재하고 데이터/패리티 비트랑 알고리즘을 묶어서 EC 그룹이라고 한다.
1. XOR
- 다른 EC 알고리즘에 비해 상대적으로 간단
- 데이터 비트에 대해 비트별 XOR 연산을 수행해서 패리티 비트를 생성
XOR 연산은 다르면 1, 같으면 0을 출력하는 논리 연산
3개의 데이터 블록 (D1, D2, D3)을 가지고 패리티 블록(P1) 생성
- 원본 데이터를 D1, D2, D3의 3개의 동일한 크기의 데이터 블록으로 나눔
- 데이터 블록에 대해 블록(비트) 별 XOR을 수행해서 패리티 블록(비트) P1을 생성함
P1 = D1 ⊕ D2 ⊕ D3.
이제 데이터 블록 중 D2에 결함이 생긴 경우, 복구 과정은
D2 = D1 ⊕ D3 ⊕ P1.
끝이다.
장점은 간단하다.
하지만 너무 간단한 나머지 내결함성에서 제한적이다.
구현에 따라 하나 또는 두 개 블록에 대한 손실을 허용하는데 다중 오류를 허용해야 하는 HDFS에서는 적합하지 않다.
이런 제한적인 내결함성을 해결하기 위해서 사용하는 것이 바로
2. Reed-Solomon(RS)
GT(Generator Matrix, 생성행렬)를 사용하는 Reed- Solomon 방법은 선형 대수 연산을 통해 데이터/패리티 비트를 생성
가볍게 방법 론 보려고 한 건데 행렬 나오길래.. 너무 뇌절까지 왔나 싶기도 했다
데이터 벡터
- 원본 데이터를 K개의 동일한 크기의 데이터 블록으로 나누고 벡터 D로 나열
유한체(Galois Field)
- 일반적으로 GF(2^m) 선택
- m은 블록의 최대 수 (k+m)을 나타내는 데 필요한 비트 수
- 따라서 일반적으로는 GF(2^8), 256개 사용
Generative Matrix(생성기 행렬)
- 갈루아 필드 사용해서 (k*m) * k의 생성기 행렬 'G' 구성
- 행렬 'G'는 행렬 I와 행렬 V의 연결임
- G : k * k 크기의 항등 행렬 'l' , 대각선에는 1이 있고 다른 곳에는 0이 있음
- V : k * m 크기의 Vandermonde 행렬, 요소의 연속 거듭 제곱을 사용해 구성
Generative Matrix
G = | I | V |인코딩
- 행렬 G와 데이터 벡터 D 사이에 행렬 곱셈 수행하여 크기 (k+m) * 1의 새로운 벡토 'C' (CodeWord) 생성
- 벡터 C는 데이터/패리티 비트 모두 가지고 있음
C = G * D디코딩
- 원본 데이터를 디코딩해서 복구하기 위해 Berlekamp-Massey 알고리즘이나 Euclidean 알고리즘(유클리드 호제법)을 사용해 디코딩하거나 GT의 역행렬 사용
장점은
제한적인 XOR 방식과는 다르게 최대 'm' 개 패리티 블록 손실에 대응이 가능
3. 하지만
Erase Coding 방식은 데이터를 복구하는 기법 중 하나이지, 데이터 백업을 대체하는 방식은 아님
Reference
A performance evaluation and examination of open-source erasure coding libraries for storage | Proccedings of the 7th conference
ABSTRACT Over the past five years, large-scale storage installations have required fault-protection beyond RAID-5, leading to a flurry of research on and development of erasure codes for multiple disk failures. Numerous open-source implementations of vario
dl.acm.org
Apache Hadoop 3.3.5 – HDFS Erasure Coding
<!--- Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or a
hadoop.apache.org
'MLOps > Data' 카테고리의 다른 글
| 꼬리에 꼬리를 무는 Spark와 RDD, DataFrame, Dataset 이야기 (0) | 2023.04.15 |
|---|---|
| 아파치 하둡 입문 강좌 정리 (0) | 2023.03.27 |
| What's the Rack Awareness in HDFS (0) | 2023.03.03 |
| [데이따] 하둡, 스파크, 에어플로우.. 개고생 , Let's go (4) | 2023.01.25 |
