Korean Institute of Information Technology

Current Issue

The Journal of Korean Institute of Information Technology - Vol. 19, No. 9

[ Article ]
The Journal of Korean Institute of Information Technology - Vol. 19, No. 9, pp.11-21
Abbreviation: Journal of KIIT
ISSN: 1598-8619 (Print) 2093-7571 (Online)
Print publication date 30 Sep 2021
Received 07 Jul 2021 Revised 13 Aug 2021 Accepted 16 Aug 2021
DOI: https://doi.org/10.14801/jkiit.2021.19.9.11

압축을 적용한 Erasure Coding의 성능 측정 및 분석
김은경* ; 심봉걸* ; 임승호**
*한국외국어대학교 컴퓨터공학부 학부생
**한국외국어대학교 컴퓨터공학부 교수(교신저자)

Measurement and Analysis of the Performance of Erasure Coding with Compression
Eun-Kyung Kim* ; Bong-Geol Sim* ; Seung-Ho Lim**
Correspondence to : Seung-Ho Lim Division of Computer Engineering, Hankuk University of Foreign Studies, Korea Tel.: +82-31-330-4704, Email: lim.seungho@gmail.com

Funding Information ▼

초록

클라우드 스토리지 및 데이터센터에서는 저장되는 데이터의 안정성을 높이기 위해서 패리티 관리 기법인 이레이저 코딩(Erasure Coding)이 널리 사용되고 있다. 이레이저 코딩은 기존 데이터 패리티 관리 기법보다 안정성과 공간 효율성이 높지만, 여전히 데이터 인코딩 및 디코딩 오버헤드로 인해서 연산 시간이 많이 든다. 또한, 확률적으로 패리티 블록 개수 이상의 데이터 오류 발생 시 데이터를 복구하지 못한다. 본 논문에서는 이레이저 코딩 기법과 데이터 압축 기법을 혼용하여 데이터 인코딩 효율성을 높이고, 패리티 블록 개수 이상의 데이터 오류가 발생하더라도 오류가 복구가 가능한 방법을 설계하고 구현하였다. 데이터센터의 이레이저 코딩 시뮬레이션 도구인 SimEDC를 확장하여 데이터의 압축 기법을 적용하고 이레이저 코딩 성능을 측정하였다. 이레이저 코딩에 압축 기법을 혼용하였을 경우, 기존보다 데이터 복구 성능이 높아짐을 확인할 수 있었다.

Abstract

A parity management scheme called Erasure Coding is widely used in cloud storage and data centers to increase the stability of stored data. Erasure Coding provides high stability and space efficiency compared to the other data parity management system, however, it still takes a lot of computation time due to data encoding and decoding overhead. In addition, data cannot be recovered when a data error of more than the number of parity blocks occurs. In this paper, the data encoding efficiency is improved by mixing the erasure coding and compression. In the proposed method, the error can be recovered even if a data error greater than the number of parity blocks occurs. The compression is added to SimEDC, which is an erasure coding simulation tool developed for data center. When the compression technique was mixed with the erasure coding, it was confirmed that the data recovery performance was improved compared to the existing one.


Keywords: erasure coding, data compression, data center, PDL, NOMDL

I. 서 론

나날이 증가하는 IT 기술로 인해 빅데이터 시대에 들어선 우리는 수많은 데이터와 함께 살고 있다. 유튜브에는 1분마다 400시간 분량의 동영상이 업로드되고, 페이스북에는 매일 수 억장의 이미지가 등록된다. 시장조사업체 IDC에 따르면 전 세계 데이터의 양은 매년 30%씩 증가해 2025년에는 163ZB에 이를 전망이다. 데이터의 생성되는 양이 증가하고 수집 주기가 짧아지는 만큼, 이러한 데이터의 효율적이고 안전한 보관 역시 더욱 중요해지고 있다[1][2]. 특히, 데이터센터에서는 이렇게 폭발적으로 증가하는 데이터에 대한 저장 관리를 위한 저장장치 시스템이 주요 부분 중 하나이며, 데이터센터는 저장장치의 데이터 오류로 인한 손실을 낮추기 위한 다양한 연구 분야가 있다[3][4].

데이터에 손실이 발생했을 때 이를 복구하는 데이터 복구 기법의 하나인 이레이저 코딩(Erasure coding) 기법은 손실로부터 데이터 스토리지를 보호하기 위해 널리 채택되었다[5]-[9]. 이레이저 코딩은 이레이저 코드를 이용하여 데이터를 인코딩하고, 데이터 손실이 발생했을 때 데이터 디코딩 과정을 거쳐 원본 데이터를 복구하는 기법이다. 일반적으로 이레이저 코딩은 데이터의 원본을 포함해서 n개 블록으로 하나의 클러스터를 구성한다. 해당 클러스터에서 n개 중 k개의 데이터를 인코딩하여 (n-k) 개의 패리티를 생성하여 저장한다. 데이터 읽기 시에 (n-k) 개 이하의 데이터 손실이 발생하면, 해당 클러스터를 구성하는 n개의 영역 중에서 손실이 발생한 영역을 제외한 나머지 개의 데이터로 디코딩을 통해 원본 데이터를 복구한다.

이레이저 코드 기법은 기존의 RAID나 단순 패리티 관리 기법보다 공간 효율성이 상대적으로 높으며, 상대적으로 적은 패리티로 높은 복구율을 달성한다[10]. 그러나 이레이저 코드 기법의 데이터 인코딩 및 디코딩 알고리즘은 계산의 복잡도로 인해서 연산 시간의 오버헤드가 발생한다. 또한, 패리티 데이터 블록 이상의 데이터 오류가 발생하면 복구하지 못하는 복구율에도 향상이 필요하다.

본 논문에서는 이레이저 코드의 인코딩 효율성의 향상과 패리티 블록 개수 이상의 데이터 오류가 발생했을 때의 복구율을 높이기 위해서 기존 이레이저 코드 기법에 데이터 압축 기법을 추가하여 적용한 데이터 패리티 관리 방법을 설계하고 구현하였다. 압축 기법은 데이터 블록에 대해서 압축을 적용하고, 압축으로 인해서 남는 공간은 1 또는 0으로 채우고 나머지 압축된 데이터에 대해서만 이레이저 코드 기법을 적용한다. 이렇게 할 경우, 압축으로 인해서 남은 영역은 데이터 오류 시 복구 영역으로 활용할 수 있다. 우리는 압축기반 이레이저 코드 기법을 적용한 방법을 데이터센터의 이레이저 코딩 시뮬레이션 도구인 SimEDC[11]에 적용하였다. 이레이저 코딩에 압축 기법을 혼용하였을 경우, 기존과 비교하여 데이터 복구 성능이 높아짐을 확인할 수 있었다.


Ⅱ. 배 경

배경에서는 이레이저 코딩의 기본 개념에 관해서 설명하고, SimEDC 내부의 시뮬레이터 구현 방식에 관해서 설명한다.

2.1 이레이저 코딩 및 데이터센터의 Failure

이레이저 코딩은 단순 데이터 복제하여 저장하는 것보다 데이터 저장소의 구성에 효율적 방법이다. 이를 통해 운영 비용, 전력, 설치 공간을 절감할 수 있다. 데이터센터와 같은 스토리지 시스템에서 데이터를 저장할 때 일반적으로 데이터를 청크라고 하는 고정 크기의 단위로 나누어 이레이저 코딩을 적용한다. 이때, 하나의 인코딩 단위가 되는 그룹을 n개의 청크로 묶어서 스트라이프라고 하며 n개 중에 (n-k) 개의 패리티 청크를 가진다. 이레이저 코드는 k개의 데이터 청크에 대해서 (n-k) 개의 패리티 청크를 인코딩 연산을 통해서 생성한다. 즉, n, k 코드의 경우 k개의 청크는 직접 접근할 수 있는 원본 데이터 청크이고, n-k개의 청크는 패리티 청크이며 패리티 청크의 개수만큼 failure를 허용한다.

기본적으로 이레이저 코드는 패리티를 생성하는 방식에 따라서 GF(Galios Field)를 기반으로 한 RS(Reed Solomon) 방식과 패리티의 XOR 연산에 따른 XOR-base 방식이 존재한다[12]-[14]. 이러한 RS 또는 XOR 알고리즘을 적용함에 있어 코딩 알고리즘의 효율성을 높이기 위한 다양한 연구 방법이 진행되었다[15]-[19].

한편, 이레이저 코드는 데이터센터와 같은 대규모 스토리지 시스템에서 데이터 복구와 재구성에 많은 대역폭과 연산량을 요구한다. 이러한 연산량을 줄이기 위해서 이레이저 코딩을 적용하는 다양한 하이브리드 이레이저 코딩 구성(Construction) 방식이 연구되어 왔다. 하이브리드 기반의 이레이저 코드 구성 방식은 기본적으로 RS만 적용하여 배치 구상하는 방식[12]에 더해서 LRC(Local Reconstruction Codes) 방식[4], DRC(Double Regenerating Codes) 방식[20][21], HeART[22], EC-Fusion[23] 방식 등 수많은 방식이 제안되었다.

데이터센터는 수천 개의 디스크 장치와 수백에서 수천 개의 노드가 rack으로 구성되는 분산 저장 시스템이다. 이러한 분산 저장 시스템에서 이레이저 코드 방식에 따라서 클러스터링 된 청크의 배치는 다양한 토폴러지가 존재할 수 있다. 가장 대표적인 청크의 배치는 평판 배치(Flat placement)와 계층적 배치(Hierarchical placement)가 있다.

그림 1과 같이 평판 배치는 n개의 랙에 각각의 Rack마다 사용 가능한 같은 노드에 청크를 1개씩 배치하는 것이고, 계층적 배치의 경우 r개의 랙을 선택하여 각 랙에 r개의 노드를 선택하여 각각의 노드에 n/r개의 청크를 배치하는 방법이다. 예를 들어 n=6, k=3인 경우 평판 배치는 6개의 rack에 하나의 노드에 청크를 넣는 것이고, 계층적 배치의 경우 3개의 rack에 2개 노드에 각각의 청크를 넣는 것이다.


Fig. 1. 
Flat placement and hierarchical placement

이러한 데이터센터의 배치 방식과 시스템의 레벨에 따라서 발생할 수 있는 failure model에는 disk failure, node failure, rack failure, correlated failure가 있다. 이 중에서 failure가 독립적으로 발생한 failure에 대하여 주로 고려하고, 데이터 손실이 발생하는 failure에 대하여 고려한다.

본 논문은 기존 압축한 데이터에 기존 이레이저 코딩의 구성 방식을 적용할 경우에 대한 효율성을 분석하기 위한 논문으로 기존의 이레이저 코딩 구성 방식과 혼용하여 적용할 수 있을 것으로 기대한다. 본 논문에서는 기존의 기본 RS 방식에 압축 기법을 적용하였으며, 이에 대한 효율성을 분석하여 보았다. 이러한 압축 기법은 LRC, DRC 방식 등 다양한 하이브리드 이레이저 코디 구성 방식과 함께 혼용 가능할 것이다.

2.2 SimEDC : 데이터센터 기반 이레이저 코드 시뮬레이터

SimEDC[9]는 시뮬레이션을 통해 이레이저 코딩된 데이터센터의 신뢰성을 측정하는 시뮬레이터이다. 데이터센터의 위상 배치 입력, 이레이저 코드 및 중복 배치 등이 이레이저 코딩된 데이터센터의 안정성에 미치는 영향을 특성화하는 것이 중요하지만 탐구되지 않았다는 점에 주목하여 여러 패턴을 기반으로 이레이저 코딩된 데이터센터의 신뢰성을 분석하도록 SimEDC는 설계되어 있다.

SimEDC를 실행시키기 위해서는 파이선 라이브러리인 mpmath, numpy, scipy를 설치해야 하며, python 2.7 버전을 설치하여 실행해야 한다. 그리고 “python simedc.py -n <code_n> -k <code_k>”와 같이 입력하여 시뮬레이터를 실행시킬 수 있으며 자세한 configuration은 “python simedc.py -h”를 통해 확인할 수 있다.

SimEDC에서는 설정한 시스템의 배치와 디스크 failure model에 따라서 PDL(Probability of Data Loss), NOMDL(Normalized Magnitude of Data Loss), BR(Blocked Ratio)[24]과 같은 여러 가지 신뢰성 매트릭스와 성능지표를 추출할 수 있다. PDL은 데이터 손실 확률로써 실행 중 데이터센터에서 청크의 손실(스트라이프 내 failure가 발생한 청크의 수가 허용 한도를 초과한 경우)이 발생한 가능성을 측정한 값이다. NOMDL은 표준화된 데이터 손실 규모로, 복구할 수 없는 청크의 수를 전체의 청크 수로 나눈 값으로 데이터 손실의 정상화된 규모를 측정한 값이다. BR은 차단 비율로 모든 청크의 평균 미션 시간 동안 정상인 상태에 있는 시간의 비율로, 청크에 발생한 failure로 청크에 직접 액세스할 수 없는 시간의 비율을 측정한 값이다. SimEDC 시뮬레이터는 이러한 성능 메트릭을 통해서 이레이저 코드 및 배치 방식에 따른 모델링된 데이터센터의 신뢰성을 평가할 수 있다.

SimEDC의 시뮬레이션 과정에는 적용될 수 있는 이레이저 코드의 종류로는 RS방식, LRC방식, DRC방식을 적용할 수 있고, 각각의 방식에 대해 n개의 데이터와 k개의 패리티를 생성하고, 가상의 오류를 발생했다고 가정한 뒤 신뢰성을 측정하게 된다.


Ⅲ. 압축을 적용한 이레이저 코딩의 성능 분석 프로그램 설계 및 구현

이번 장에서는 SimEDC를 활용하여 압축기반 이레이저 코딩을 설계하고 구현한 내용을 기술하도록 한다.

3.1 Overview

압축을 활용한 이레이저 코드 적용 기법의 전체적인 동작 방식은 그림 2와 같이 나타낼 수 있다. 그림은 (n, k)가 (9, 6)인 이레이저 코딩 방식을 예로 나타낸 것이다. 그림에서와같이 6개의 데이터 청크와 3개의 패리티 청크로 구성되는 스트라이프에 대해서 6개의 데이터 청크에 대한 이레이저 코딩 인코딩을 수행하기 전에 데이터 압축한다. 압축을 수행하고 나면, 기존 데이터 청크의 개수는 압축으로 인해서 줄어들며 데이터 저장이 필요하지 않은 프리 청크가 생성된다. 우리는 프리 청크에 데이터를 저장하지 않고 단순히 0으로 값을 채워준다. 그 후, 패리티 청크는 나머지 압축된 데이터를 이용해서 생성한다.


Fig. 2. 
System diagram of compression-based erasure coding

그림 2에서와같이 (9, 6)인 스트라이프에서 압축에 의해서 4개의 압축 데이터 청크로 줄어든 경우, 4개의 압축 데이터에 대해서 이레이저 코딩 인코딩을 수행하여 3개의 패리티 청크를 생성한다. 이렇게 생성된 패리티 청크와 기존의 데이터 청크 및 프리 청크는 하나의 스트라이프를 구성하게 된다. 이러한 이레이저 코딩 방식은 비록 압축 연산이 추가되기는 하지만, 인코딩에 적용되는 데이터 청크의 개수가 줄어들기 때문에 인코딩 연산량이 줄어들 수 있다.

스트라이프의 데이터를 읽는 도중 스트라이프의 특정 청크에 대한 오류가 발생할 경우, 해당 스트라이프틑 최대 5개의 청크가 오류가 나더라도 해당 스프라이프틑 이레이저 코딩의 디코딩 방식에 의해서 복구할 수 있게 된다. 이는 기존 방식인 3개의 오류까지 복구가 가능한 것보다 높은 오류 복구율을 달성할 수 있다.

3.2 압축기반 이레이저 코딩 구현 세부사항

본 논문은 SimEDC 이레이저 코딩 시뮬레이터에 압축을 적용하는 설계 및 구현을 진행하였다. 여기에는 SimEDC에 압축을 적용한 구체적인 구현내용을 설명하도록 한다.

SimEDC는 메인 함수 부분인 simedc.py와 객체 생성 부분인 모듈들이 존재한다. 그림 3은 기본적인 SimEDC 시뮬레이터를 구성하는 있는 모듈들과 객체를 나타낸 것이다.


Fig. 3. 
SimEDC diagram

SimEDC는 python으로 구현되어 있으며 메인 함수 부분인 simedc.py 파일, 시뮬레이션 객체 생성 부분인 simulation.py, is_simulation.py, regular_simulation,py 파일, 데이터의 배치 부분인 placement.py 파일들로 구성되어 있으며 이 부분이 주요 모듈 부분이다.

본 논문에서 압축을 적용하기 위해서 기본 SimEDC 모듈에 데이터 변수와 함수들을 추가하였다. 압축을 적용하고 압축된 빈 공간을 표시하기 위하여 free라는 변수를 simedc.py에서 입력받을 수 있도록 하였다. free의 기본값은 0이며, configuration을 통해 개수를 지정해주면 시뮬레이션 객체를 생성해주는 부분으로 전달되고, 시뮬레이션 객체 내부에서 초기화되는 placement까지 free 값이 전달되도록 하였다.

압축을 적용하여 청크들을 배치하는 부분에 대한 구현은 다음과 같다. Placement에서는 전달받은 변숫값들을 바탕으로 데이터를 배치한다. 본 연구에서는 3가지 인코딩 알고리즘 방식 중 RS방식에 관하여 압축을 적용하였다. 기존 코드에서는 전체 청크의 개수인 n과 데이터 청크의 개수인 k를 통해 패리티 청크의 수를 m(=n-k)으로 계산하고, n개의 청크를 앞에서부터 차례대로 k개는 데이터 청크, 나머지는 패리티 청크로 설정을 한다. 데이터 청크를 할당하기 전에 압축을 통하여 필요한 데이터 청크의 개수와 free 청크의 개수를 구분한다.

그 후, free 청크를 적용하여 k를 k-free개로 하여 앞에서부터 k-free개의 청크를 데이터 청크, 다음 free개의 청크를 프리 청크, 나머지 m개의 청크를 패리티 청크로 하여 배치를 하도록 하였다.

generate_placement_ec() 함수에서는 스트라이프마다 n개의 랙 리스트를 랜덤으로 만들고, 랙 아이디마다 디스크 리스트도 랜덤으로 생성하고 stripes_location에 디스크 리스트를 추가하여 n개의 랜덤 디스크 위치를 스트라이프의 위치로 저장하게 된다. 압축괴 erasure coding을 적용하여 생성된 stripe는 위의 함수를 통해서 생성된 stripes_location에 저장한다. 이를 generate_num_data_chunks_per_disk() 함수에서 n개씩 반복문을 돌며 k번째 청크까지는 데이터 청크의 디스크 리스트 (num_data_chunks_per_disk)에 저장한다. 이 부분을 k-free개 까지는 데이터 청크의 디스크 리스트에 저장되게 하고, 이후 free개의 디스크 아이디는 프리 청크의 디스크 리스트(num_free_chunks_per_disk)에 저장되도록 하였다.

그리고 디스크별로 데이터와 패리티 청크에 해당되는 stripe_id를 저장하는 stripes_per_disk 리스트와 디스크별로 청크의 개수를 관리하는 num_chunks_per_disk 리스트에는 해당하는 stripe_id를 전부 저장하는 것이 아닌, 프리 청크가 아닌 데이터 청크 또는 패리티 청크일 경우에만 개수와 아이디를 관리하도록 수정하여 이 리스트들에 접근하는 함수들이 free 영역이 적용된 값을 반환할 수 있도록 하였다.

3.3 데이터 복구 과정

SimEDC의 is_simulation.py 모듈은 기본 형태인 UnifBFBSimulation 클래스가 정의되어 있고 초기화 함수, 노드와 디스크의 실패율을 반환하는 함수, 고장 난 구성 요소의 복구 시간을 계산하는 함수, 디스크 또는 노드에 대한 다음 복구 시간을 설정하는 함수 등이 구현되어 있고, 이 함수들을 통해 복구를 가상으로 가정하고 진행한다. 남아있는 이벤트들을 힙으로 관리하여 시간이 가장 적게 걸리는 이벤트들부터 처리하며 복구를 진행하는 것으로 구현하였다.

그림 4는 SimEDC에 전체적으로 적용된 구현사항을 간략하게 클래스로 도식화한 것이다.


Fig. 4. 
Simplified connection between classes

클래스의 마지막에 정의된 함수인 run_iteration이 전체 프로세스의 연결 역할을 하는데, placement.py 파일에 정의된 get_num_failed_status 함수를 통해 데이터 손실이 발생한 디스크에 대한 failed stripe 수와 lost chunk 수를 반환하게 된다. simedc.py에서 입력된 조건에 따라 생성된 클래스의 run_iteration() 함수를 simedc.py 파일의 run_simulation() 함수에서 입력된 반복 횟수만큼 호출하게 되고, 반환된 청크와 스트라이프 개수를 do_it() 함수에서 반환하게 된다. 이 do_it 함수가 메인 함수에서 호출되며 반환된 리스트를 get_output에서 계산하여 평균값을 통해 복구 성능 평가항목인 PDL, NOMDL을 구하게 된다.

마지막으로, 다양한 데이터의 압축률에 대한 효과를 보기 위해서 다양한 압축률을 적용할 수 있는 인터페이스를 넣었다. 압축률을 적용하여 실험하기 위해 free 영역을 한 종류로만 지정해주는 것이 아니라, 전체 실행 횟수 중 비율에 따라 다양하게 지정해줄 수 있도록 simedc.py 내에 free 개수가 다른 시뮬레이션 객체를 여러 개 생성하고, 각 객체마다 run_iteration 횟수를 실행할 때마다 하드 코딩으로 적용하여 실험을 진행할 수 있도록 하였다.


Ⅳ. 성능 평가
4.1 실험환경 구성

본 논문에서 실험한 SimEDC 시뮬레이터를 이용한 이레이저 코딩의 압축에 따른 성능을 평가하기 위해 SimEDC 시뮬레이터의 압축률에 따른 데이터 청크의 변화에 따른 실험환경을 구성하였다.

그림 5는 SimEDC 시뮬레이터의 실행 방식을 도식화하여 나타낸 그림이다. simedc.py에서 각각의 실행을 위한 configuration을 다음과 같은 방법으로 설정한다(./simedc.py –n 9 –k 6 –i 1024). 입력을 통해 simedc.py는 실행을 위해 하위 simulation.py, placement.py, smp_data_ structures 모듈을 불러와 실행한다.


Fig. 5. 
SimEDC operation system

simulation.py 모듈은 설정에 따라 is_sumulation과 regular_simulation 둘 중 하나의 설정으로 실행된다. placement.py 모듈은 설정에 따른 랙, 노드, 청크의 배치를 설정하는 모듈이다. smp_data_structures.py 모듈은 랙, 노드 디스크의 상태를 변경, 저장하고 Weibull 분포에 따라 고장률과 실패율을 계산하는 모듈이다.

다양한 데이터 형식에 대한 압축을 통한 실험을 진행하기 위해 텍스트(Text) 파일, DB(Database) 파일, 이미지(Image) 파일에 대하여 각각의 압축률을 구하고, 압축률에 대한 비율을 데이터 청크에 적용하여 시뮬레이션을 실행하였다. 각각의 파일에 대하여 시뮬레이션을 진행하고, 텍스트 파일, DB 파일, 이미지 파일을 1:1:1 비율로 혼합한 시뮬레이션과 1:1:3 비율로 혼합하여 진행한 결과를 원본 데이터의 시뮬레이션 결과와 비교 및 분석했다.

이미지 파일의 비율을 1:1:1로 섞어서 실험한 이유는 각각의 파일의 특징에 따라서 압축률이 다른 다양한 데이터가 혼합되어 있을 때 압축 기법을 적용한 경우의 실험 결과를 분석하기 위해서이다. 특히 이미지 파일과 같은 멀티미디어 데이터의 경우 데이터 크기가 다른 텍스트 기반 파일보다 크기 때문에 저장장치에서 차지하는 용량이 크므로 저장 용량의 비율을 높이는 것이 더욱 일반적인 사용성일 수 있기 때문에 1:1:3과 같이 이미지 파일에 대한 비율을 높이는 분포를 추가 적용하였다.

먼저, 압축률에 따른 시뮬레이션의 결과를 비교하기 위해 기존의 원본 파일, 텍스트 파일, DB 파일, 이미지 파일을 비교하였다. 그림 6은 텍스트, DB, 이미지 파일의 압축률과 압축률 비율에 따른 파일의 개수를 나타낸 그래프이다. 이미지 파일 1058개를 zlib를 통해 압축한 평균적으로 41.9%의 압축률을 보였다. DB 파일의 경우 기존의 파일보다 용량이 커진 파일은 존재하지 않았으며, 39.97%의 압축률을 보였다. 마지막으로 이미지 파일의 경우 1027개의 파일을 압축한 결과 압축 후 기존의 파일보다 용량이 커진 파일이 70개 존재했으며, 97.01%의 압축률을 보였다.


Fig. 6. 
Text, DB, Image file compression rate

각각의 파일의 압축률을 비율에 따라 몇 퍼센트 압축되었는지 구간을 나누어 SimEDC 실험환경에서 압축 비율에 맞도록 스트라이프를 생성할 시 압축률에 따라서 프리 청크 영역을 생성하도록 구성하고 실행하였다. 예를 들어 텍스트 파일의 경우 n=9, k=6으로 1024회 반복하도록 하였으며, 파일의 압축률 비율 구간에 따라서 프리 청크가 생성되도록 시뮬레이터를 구성하여 데이터 압축 및 이레이저 코딩을 통한 스트라이프 생성작업을 수행하였다.

두 번째 실험의 경우 텍스트와 데이터베이스, 멀티미디어(이미지)를 혼합한 압축을 진행하였을 때의 성능을 분석하도록 하였고, 텍스트, 데이터베이스, 멀티미디어의 비율을 1:1:1, 1:1:3으로 했을 때의 시뮬레이션을 실행하기 위해 반복 횟수를 위와 같이 계산하였다.

이미지의 압축 결과 대부분이 90% 이상으로만 압축이 된 점을 통해 압축을 적용하지 않은 original과 유사하다고 볼 수 있다.

실험은 앞에서 적용한 프리 청크 개수 별 반복 횟수와 3장에서 설명한 클래스 객체를 여러 개 생성하여 실행하고 결과를 합치는 방식을 사용하여 실험을 진행하였고, SimEDC 시뮬레이터 실행 시 설정해주는 옵션에 따라서 total_iteration 횟수는 1024회(-i), 프로세스 개수는 1개(-p), 실험 종류에 따라 n과 k 개수를 지정해주었다.

original의 경우는 프리 청크를 0개로 설정한 1024개의 반복을 수행하는 시뮬레이터를 실행하였고, 나머지 조건인 프로세스의 개수와 총 반복 횟수는 1개, 1024개로 똑같이 실행하였다. 이레이저 코딩의 (n, k)에 따른 성능 변화를 관찰하기 위해서 (n, k)의 비율을 각각 (6, 4), (9, 6), (12, 8)로 변화시켜 가면서 실험을 진행하였다. 실험 측정지표로는 PDL과 NOMDL을 활용하였다. PDL은 총 읽은 데이터에 대해서 손실이 발생한 확률을 나타낸 지표이며, 해당 스트라이프 내에서 오류가 발생한 청크의 개수가 복구 불가능한 확률에 대한 지표로 볼 수 있다. NOMDL은 진행한 실험 셋에서 오류로 인해서 디코딩을 수행해도 복구할 수 없는 청크의 개수를 전체의 청크의 개수로 나눈 값으로써 전체 데이터 손실의 규모를 측정하는 지표로 볼 수 있다.

4.2 실험 결과

먼저, 첫 번째 실험은 텍스트 및 데이터베이스 개별 타입의 데이터에 대한 압축 비율에 따라 프리 청크를 적용하여 PDL과 NOMDL 값을 측정하여 나타내었다. 그림 7은 (n, k)가 (6, 4), (9, 6), (12, 8)인 경우에 대해서 기존 이레이저 코딩 방식과, 텍스트 데이터와 DB에 데이터에 압축기반 이레이저 코딩을 적용한 시스템의 시뮬레이션 수행 결과 PDL과 NOMDL값의 결과를 도식화한 것이다. 그림에서 Original은 기존 이레이저 코딩 방식이 적용된 결과를 나타내며 Text는 텍스트 파일에 대해서 압축 기법을 적용한 것이고 database는 DB 파일에 대한 압축 기법을 적용한 것이다. PDL값이나 NOMDL값은 값이 낮을수록 복구 불가능한 경우가 낮다는 의미이기 때문에 값이 낮을수록 성능이 높다는 것을 나타낸다. 결과에서 알 수 있듯이 압축을 적용한 이레이저 코딩 기법이 압축을 적용하지 않은 것보다 복구 불가능한 데이터의 발생 확률이 낮은 것을 확인할 수 있다. 즉, 복구 성능이 높다는 것을 알 수 있다. 압축을 적용하여 Free 영역을 적용함에 따라 실질적 에러의 발생 비율에 변화가 생겼으며, 이 변화에 따라 PDL 값이 반비례하여 낮아지는 것을 확인할 수 있었다.


Fig. 7. 
Experimental results of PDL and NOMDL measured by applying compression-based erasure coding technique to text and database data

NOMDL 값은 failed_stripe과 lost_chunk의 평균값을 의미하는데, 압축을 적용하지 않은 original의 경우보다 압축을 적용했을 때 감소하는 것을 확인할 수 있으며, 이를 통해 복구 성능이 더 좋아졌음을 확인할 수 있다.

(n, k)의 비율에 따른 성능 변화를 살펴보면, (n, k)가 (6, 4)에 비해서 (9, 6) 및 (12, 8)로 갈수록 전반적으로 복구 성능은 높아진다. 이는 당연히 데이터 청크에 비해서 패리티 청크의 비율이 높아지므로 오류 청크의 비율에 비해서 데이터 복구 비율이 높아지기 때문이다. 특히 압축 기법을 적용할 경우 이 비율은 더 높아질 수 있으므로 (n, k)이 비율이 높아질수록 성능 향상 정도는 더 높아짐을 확인할 수 있다. 텍스트 파일과 DB 파일을 비교할 경우 비슷한 성능 결과가 나옴을 확인할 수 있는데, 이는 둘의 압축 비율이 비슷하므로 비슷한 Free 영역의 활용도를 보임을 나타낸다. 이미지 파일의 경우 압축 비율이 현저히 떨어져서 압축의 효과를 볼 수 없다.

텍스트, DB, 이미지 파일의 혼합 비율을 적용하여 압축기반 이레이저 코딩 기법의 복구 성능 실험을 진행한 실험 결과를 그림 8에 나타내었다. 혼합 적용하여 실험한 경우 “텍스트:DB:이미지”의 비율을 각각 1:1:1 비율로 적용한 경우와 1:1:3 비율로 적용한 경우인 두 가지에 대한 실험을 진행하였으며, 그 결과를 각각 나타내었다. 일반적으로 멀티미디어 파일의 경우 압축된 데이터임에도 불구하고 데이터 유형 상 데이터 크기가 크기 때문에 스토리지 시스템의 많은 공간을 차지하게 된다. 그래서 이미지 파일과 같은 멀티미디어의 비율을 높게 하여 실질적으로 압축 기법이 적용될 경우의 성능 향상 정도를 파악할 필요가 있다.


Fig. 8. 
Experimental results of PDL and NOMDL measured by applying compression-based erasure coding technique for mixed dataset

실험 결과에서도 확인할 수 있듯이 멀티미디어 파일이 섞여 있는 경우에도 압축을 적용하지 않은 경우보다 압축을 적용하는 경우가 데이터 복구율 성능이 좋아짐을 확인할 수 있다. 그러나 당연히 이미지 파일의 비중이 높은 1:1:3의 경우에는 성능 향상 정도가 1:1:1에 비해서 낮아짐을 확인할 수 있다. 실험을 통해 각각 데이터의 손실과 그에 따른 복구 과정에서 데이터의 압축 비율에 따라 데이터 손실에 따른 복구 성능이 좋아지는 것을 확인할 수 있다.

그러나 일반적으로 데이터 압축을 통해서 실질적으로 이레이저 코딩이 적용되는 데이터 영역을 줄이고, Free 영역을 활용해서 손실이 발생한 부분에 대한 복구 영역을 줄여줄 경우, 전체 데이터 저장 시스템의 에러 복구율은 향상됨을 확인할 수 있다.


Ⅴ. 결론 및 향후 과제

전 세계적으로 데이터의 사용량과 보관량은 점점 늘어나고 있다. 이러한 과정에서 이레이저 코딩은 데이터의 저장과 복구에 효율적인 방식이다. 이레이저 코딩은 인코딩 및 디코딩 연산의 복잡도와 패리티 크기 이상의 데이터 오류에 대한 복구율이 낮은 한계점이 있다. 본 논문에서는 압축 기법을 적용하여 이레이저 코딩의 연산 복잡도를 낮추고 에러 복구율을 높이는 방법을 설계하고 구현하였으며, 이를 SimEDC 시뮬레이터에 적용하고 실험하여 그 성능을 평가하여 보았다. 이레이저 코딩 알고리즘 방식에 대한 압축 적용 결과 압축률이 높은 텍스트 파일과 DB 파일에 대한 PDL이 현저히 감소하는 것을 확인할 수 있었고, NOMDL은 대략 4%~7% 정도 향상됨을 실험을 통해 알 수 있었고, 이를 통해 압축한 데이터의 저장 및 복구 방식의 성능이 향상되었음을 도출할 수 있었다.

향후 압축 기법의 발전을 통해 압축률을 더 높일 수 있다면 보다 나은 성능 향상을 가져올 수 있을 것으로 기대하며, RS 방식만 아니라 DRC 알고리즘과 LRC 알고리즘에도 압축한 데이터를 넣었을 때의 복구 성능 향상 역시 기대할 수 있을 것이다. 이를 향후 과제로 남겨 다른 알고리즘 기법 역시 압축을 적용한 실험을 진행하여 구체적인 성능 향상 정도를 확인할 수 있을 것이다. 같은 압축 비율을 적용하더라도 알고리즘 방식에 따라 성능 향상 정도가 다를 것이고, 알고리즘별 정도 비교를 통해 압축한 데이터를 저장했을 때 가장 효과적인 이레이저 코딩 방식 또한 도출해낼 수 있을 것으로 기대한다.


Acknowledgments

This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government (MSIP) (NRF-2019R1F1A1057503, NRF-2021R1F1A1048026).

이 연구는 한국외국어대학교 교원연구지원사업비 지원에 의하여 이루어진 것임


References
1. B. Schroeder and G. A. Gibson, "Disk Failures in the Real World: What does an MTTF of 1,000,000 Hours Mean to You?", In Proceedings of USENIX FAST, San Jose CA, Feb. 2007.
2. K. Rao, J. L. Hafner, and R. A. Golding, "Reliability for Networked Storage Nodes", IEEE Transactions on Dependable and Secure Computing, Vol. 8, No. 3, pp. 404–418, May-Jun. 2011.
3. S. Maneas, K. Mahdaviani, T. Emami, and B. Schroeder, "A study of SSD reliability in large scale enterprise storage deployments", In Proceedings of USENIX FAST, Santa Clara, CA, USA, pp. 137-150, Feb. 2020.
4. S. Han, P. P. C. Lee, F. Xu, Y. Liu, C. He, and J. Liu, "An In-Depth Study of Correlated Failures in Production SSD-Based Data Centers", In Proceedings of USENIX FAST, pp. 417-429, Feb. 2021.
5. D. Ford, F. Labelle, F. I. Popovici, M. Stokely, V.-A. Truong, L. Barroso, C. Grimes, and S. Quinlan. "Availability in Globally Distributed Storage Systems", In Proceedings of USENIX OSDI, Vancouver BC Canada, pp. 61-74, Oct. 2010.
6. C. Huang, H. Simitci, Y. Xu, A. Ogus, B. Calder, P. Gopalan, J. Li, and S. Yekhanin, "Erasure Coding in Windows Azure Storage", In Proceedings of USENIX ATC, Boston, MA, Jun. 2012.
7. K. Rashmi, N. B. Shah, D. Gu, H. Kuang, D. Borthakur, and K. Ramchandran. "A Solution to the Network Challenges of Data Recovery in Erasure-coded Distributed Storage Systems: A Study on the Facebook Warehouse Cluster", In Proceedings of USENIX HotStorage, San Jose CA, pp. 8, Jun. 2013.
8. S. Park and H. Kim, "Design and Implementation of a Secure Data Storage System for Corporations using Multi-clouds", Journal of KIIT, Vol. 11, No. 3, pp. 151-157, Mar. 2013.
9. Goo Yeon Lee. "Delay Improvement of Expedited Data from Erasure Coding", Journal of KIIT, Vol. 15, No. 4, pp. 95-103, Apr. 2017.
10. H. Weatherspoon and J. D. Kubiatowicz. "Erasure Coding Vs. Replication: A Quantitative Comparison", In Proceedings of International Workshop on Peer-to-Peer Systems, Cambridge, MA, USA, pp. 328-338, Mar. 2002.
11. M. Zhang, S. Han, and P. P. Lee. "SimEDC: A simulator for the reliability analysis of erasure-coded data centers", IEEE Transactions on Parallel and Distributed Systems, Vol. 30, No. 12, pp. 2836–2848, Dec. 2019.
12. I. S. Reed and G. Solomon, "Polynomial Codes over Certain Finite Fields", Journal of the Society for Industrial and AppliedMathematics, Vol. 8, No. 2, pp. 300–304, Jun. 1960.
13. Y. Zhang, C. Wu, J. Li, and M. Guo, "PCM: A Parity-Check Matrix Based Approach to Improve Decoding Performance of XOR-based Erasure Codes", IEEE 34th Symposium on Reliable Distributed Systems, pp. 182-191, Sep. 2015.
14. J. Gu, C. Wu, X. Xie, H. Qiu, J. Li, M. Guo, X. He, Y. Dong, and Y. Zhao, "Optimizing the Parity Check Matrix for Efficient Decoding of RS-Based Cloud Storage Systems", IEEE International Parallel and Distributed Processing Symposium, pp. 533-544, Sep. 2019.
15. M. Vajha, V. Ramkumar, B. Puranik, G. Kini, E. Lobo, B. Sasidharan, and P. V. Kumar, "Clay codes: Moulding mds codes to yield an msr code", in Proceedings of the USENIX FAST, Oakland, CA, USA, pp. 139-153, Feb. 2018.
16. M. Xia, M. Saxena, M. Blaum, and D. A. Pease, "A tale of two erasure codes in hdfs", in Proceedings of the FAST, Santa Clara, CA, USA, pp. 213-226, Feb. 2015.
17. M. Blaum, J. Brady, J. Bruck, and Jai Menon, "EVENODD: An efficient scheme for tolerating double disk failures in RAID architectures", IEEE Transactions on Computers, Vol. 44, No. 2, pp. 192–202, Feb. 1995.
18. C. Huang and L. Xu, "STAR: An efficient coding scheme for correcting triple storage node failures", IEEE Transactions on Computers, Vol. 57, No. 7, pp. 889–901, Jul. 2008.
19. Y. Zhang, C. Wu, J. Li, and M. Guo, "TIP-Code: A Three Independent Parity Code to Tolerate Triple Disk Failures with Optimal Update Complextiy", 45th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, pp. 136-147, Jun. 2015.
20. Y. Hu, P. P. C. Lee, and X. Zhang, "Double Regenerating Codes for Hierarchical Data Centers", IEEE International Symposium on Information Theory, pp. 245-249, Jul. 2016.
21. Z. Shen, J. Shu, and P. P. C. Lee. "Reconsidering Single Failure Recovery in Clustered File Systems", 46th IEEE International Conference on Dependable Systems and Networks, Jun. 2016.
22. S. Kadekodi, K. V. Rashmi, and Gregory R. Ganger, "Cluster storage systems gotta have heart: improving storage efficiency by exploiting disk-reliability heterogeneity", in Proceedings. of the USENIX FAST, Boston MA, USA, pp. 345–358, Feb. 2019.
23. H. Qiu, C. Wu, J. Li, M. Guo, T. Liu, X. He, Y. Dong, and Y. Zhao, "EC-Fusion: An Efficient Hybrid Erasure Coding Framework to Improve Both Application and Recovery Performance in Cloud Storage Systems", IEEE International Parallel and Distributed Processing Symposium, New Orleans, LA, USA, pp. 191-201, May 2020.
24. K. M. Greenan, J. S. Plank, and J. J. Wylie. "Mean Time to Meaningless: MTTDL, Markov Models, and Storage System Reliability", 2nd USENIX Workshop on Hot Topics in Cloud Computing, Boston, MA, Jun. 2010.

저자소개
김 은 경 (Eun-Kyung Kim)

2018년 3월 ~ 현재 : 한국외국어대학교 컴퓨터공학부

관심분야 : 빅데이터, 분산처리시스템, HDFS

심 봉 걸 (Bong-Geol Sim)

2016년 3월 ~ 현재 : 한국외국어대학교 컴퓨터공학부

관심분야 : 빅데이터, 분산처리시스템, HDFS

임 승 호 (Seung-Ho Lim)

2001년 2월 : 한국과학기술원 전기 및 전자 전공(공학사)

2003년 2월 : 한국과학기술원 전기 및 전자 전공(공학석사)

2008년 2월 : 한국과학기술원 전기 및 전자 전공(공학박사)

2008년 3월 ~ 2010년 2월 : 삼성전자 메모리 사업부 책임 연구원

2010년 3월 ~ 현재 : 한국외국어대학교 컴퓨터공학부 교수

관심분야 : 운영체제, 파일 시스템, 임베디드 시스템, 비휘발성 메모리 시스템, 빅데이터 처리, Hadoop, HDFS