덜 읽고 복구하는 소거 코드 LRC (Erasure Coding in WAS, USENIX ATC 2012)

출처

참고 이 페이지는 원문 번역이 아니라 한국어 해설이에요. 정확한 표현과 수치는 원문을 확인하세요.

한눈에

• Azure Storage 는 봉인된 확장(extent)을 3중 복제에서 소거 코딩으로 바꿔 저장 비용을 줄입니다. 목표 오버헤드는 원본의 1.33배입니다.
• 표준 Reed-Solomon (12,4) 로도 1.33배는 되지만, 조각 하나를 복구할 때마다 12개 조각을 읽어야 합니다.
• 저자들은 데이터 조각을 지역 그룹으로 나누고 그룹마다 지역 패리티를 두는 Local Reconstruction Codes(LRC)를 제안합니다. LRC (12,2,2) 는 같은 1.33배 오버헤드에서 복구 때 6개 조각만 읽습니다.
• 3중 복제보다 높은 내구성을 유지하면서 복구 I/O 와 대역폭을 줄였고, 큰 읽기의 지연도 Reed-Solomon 보다 짧았습니다.

왜 나왔나

Windows Azure Storage 논문에서 본 것처럼 스트림 계층은 데이터를 확장 단위로 3중 복제합니다. 확장이 약 1GB 가 되어 봉인되면 더 이상 바뀌지 않으므로, 이때 소거 코딩으로 바꿔 저장하고 원래의 3개 복제본을 지울 수 있습니다. 저자들은 소거 코딩이 저장 비용을 50% 넘게 줄이고 데이터 센터 면적을 절반으로 줄인다고 적습니다.

문제는 복구 비용입니다. 클라우드에서 조각을 읽지 못하는 상황은 디스크가 영구히 고장난 경우보다, 업그레이드나 일시적인 노드 장애로 잠깐 응답하지 않는 경우가 훨씬 흔합니다. 이때 사용자의 읽기 요청은 남은 조각들로 원본을 즉석에서 재구성해야 합니다. Reed-Solomon (12,4) 에서는 조각 하나를 되살리려면 12개 조각을 모두 읽어야 하므로, 복구 읽기가 많아질수록 네트워크와 디스크 I/O 가 크게 늘고 지연도 길어집니다. 저자들의 목표는 두 가지였습니다. 복구에 필요한 최소 조각 수를 줄이는 것, 그리고 1.33배 오버헤드에서 3중 복제보다 높은 내구성을 유지하는 것입니다.

핵심 아이디어

LRC 의 정의

(k, l, r) LRC 는 k 개의 데이터 조각을 l 개의 지역 그룹으로 나누고, 그룹마다 지역 패리티 하나를, 전체에 대해 전역 패리티 r 개를 둡니다. 전체 조각 수는 n = k + l + r 이고 저장 오버헤드는 n/k 입니다. 논문의 그림 1은 (6,2,2) LRC 를 예로 듭니다. 데이터 6개를 3개씩 두 그룹으로 나누고, 그룹별 지역 패리티 2개와 전역 패리티 2개를 둡니다. 데이터 조각 하나가 사라지면 같은 그룹의 나머지 2개와 지역 패리티 1개, 즉 3개만 읽으면 됩니다. 같은 오버헤드의 Reed-Solomon (6,3) 은 6개를 읽어야 합니다.

최대 복구 가능 성질

LRC 는 모든 조합의 장애를 견디는 MDS 코드가 아닙니다. 대신 저자들은 "최대 복구 가능(Maximally Recoverable)" 성질을 정의하고, 이 성질을 만족하도록 GF(2^4) 위에서 계수를 고르는 조건을 식으로 제시합니다(2.2절). 그 결과 (6,2,2) LRC 는 임의의 3개 장애를 견디고, 4개 장애 패턴 중 86% 를 복구할 수 있습니다. 2.3절의 정리 1은 이 수준의 복구 성질을 가지려면 패리티가 최소 l + r 개 필요하다는 하한을 보이고, LRC 가 그 하한을 정확히 맞춘다는 점을 증명합니다.

신뢰성 모델과 매개변수 선택

3장은 마르코프 모델로 평균 데이터 손실 시간(MTTF)을 계산합니다. 노드 400대, 노드당 16TB, 1Gbps 대역폭, 장애 감지 30분이라는 가정에서 표 1의 결과는 3중 복제 3.5 × 10^9 년, Reed-Solomon (6,3) 6.1 × 10^11 년, LRC (6,2,2) 2.6 × 10^12 년입니다. 즉 LRC 는 3중 복제보다 훨씬 안전합니다.

그림 4와 그림 5는 저장 오버헤드와 복구 비용을 두 축으로 놓고 여러 코드를 비교합니다. 같은 1.5배 오버헤드에서는 Reed-Solomon (6,3) 의 복구 비용 6이 LRC (12,4,2) 의 3으로 절반이 되고, 같은 복구 비용 6에서는 오버헤드가 1.5배(RS (6,3))에서 1.33배(LRC (12,2,2))로 내려갑니다. Azure 는 후자를 택했습니다. 저장 용량이 아주 큰 서비스에서는 1.5배와 1.33배의 차이가 그대로 큰 하드웨어 비용 차이가 됩니다.

Azure Storage 안의 구현

소거 코딩은 스트림 계층 안에서 일어납니다. 스트림 매니저가 봉인된 확장을 찾아 작업을 예약하면, 조정 역할의 확장 노드가 확장을 추가 블록 경계에 맞춰 잘라 조각을 대상 노드들에 보냅니다. 진행 상황을 기록해 두므로 중간에 노드가 죽어도 다른 노드가 이어받습니다. LRC (12,2,2) 는 조각이 16개이고, 이 조각들은 서로 다른 장애 도메인(랙)에 놓여야 합니다. 스탬프는 랙 20개로 이루어져 있어 이 조건을 만족할 수 있습니다. 업그레이드 도메인은 9개를 쓰는데, 데이터 조각에 6개, 지역 패리티와 전역 패리티에 각각 1개씩을 배정합니다. 두 지역 그룹의 같은 번호 조각이 같은 업그레이드 도메인을 나눠 쓰는 배치입니다.

운영 측면의 세부도 있습니다. 복구 읽기는 최대 5MB 단위로 미리 읽고 최대 256MB 를 캐시하며, 모든 읽기에서 CRC 를 확인하고, 소거 코딩을 마치기 전에 복호화가 실제로 되는지 검증한 뒤에야 원래 복제본을 지웁니다.

실험과 결과

5장은 실제 클러스터(노드당 1Gbps NIC)에서 같은 1.33배 오버헤드인 LRC (12,2,2) 와 Reed-Solomon (12,4) 를 비교합니다.

• 작은 읽기(4KB, 그림 9): 부하가 큰 조건에서 복구 없는 직접 읽기는 91ms, RS 가 12개 조각을 읽으면 305ms 였습니다. RS 가 조각을 13개 읽으면 151ms, LRC 는 6개를 읽고 166ms 였습니다. 지연은 비슷하지만 LRC 의 I/O 가 훨씬 적습니다.
• 큰 읽기(4MB, 그림 10): 직접 읽기 99ms, RS 893ms, LRC 418ms 였습니다. 1Gbps NIC 가 병목이라 읽는 조각 수가 지연을 그대로 결정했고, LRC 가 절반 이하의 시간으로 끝났습니다.
• 복호화 계산: 4KB 기준 RS 13.2마이크로초, LRC 7.12마이크로초로 둘 다 전송 시간에 비해 무시할 만했습니다.

결론적으로 LRC (12,2,2) 는 RS (12,4) 와 같은 1.33배 오버헤드에서 복구 I/O 와 대역폭이 적고, 작은 읽기의 지연은 비슷하며, 큰 읽기의 지연은 더 짧고, 3중 복제보다 내구성이 높습니다.

지금 Azure 에서는

LRC 는 Azure Storage 의 봉인된 데이터 저장 방식으로 쓰였고, 같은 기법은 Windows Server 와 Azure Local 의 저장소 공간 다이렉트(Storage Spaces Direct)에서도 쓰입니다. 공식 문서는 규모가 큰 이중 패리티(dual parity) 볼륨이 Microsoft Research 가 개발한 Local Reconstruction Codes 로 인코딩을 작은 그룹으로 나눈다고 설명합니다. 고객이 LRC 를 직접 고르는 설정은 없고, 저장 비용을 낮추는 내부 메커니즘으로 동작합니다.

함께 읽기

• 스토리지 계정: 이 사이트의 기능 문서
• Windows Azure Storage: 스트림 계층과 봉인된 확장의 배경
• USENIX ATC 2012 발표 자료
• Microsoft Research 논문 페이지
• Storage Spaces Direct 의 장애 허용과 저장 효율 (공식 문서)