(관심 논문) ParaRC: Embracing Sub-Packetization for RepairParallelization in MSR-Coded Storage

Xiaolu Li† , Keyun Cheng‡ , Kaicheng Tang‡ , Patrick P. C. Lee‡ , Yuchong Hu† , Dan Feng† , Jie Li∗ , and Ting-Yi Wu∗ †Huazhong University of Science and Technology ‡The Chinese University of Hong Kong ∗Huawei Technologies Co., Ltd., Hong Kong

February 21–23, 2023 • Santa Clara, CA, USA

USENIX Association

21st USENIX Conference on File and Storage Technologies

 

 

 

 

---

Abstract

---

 

 

  Minimum-storage regenerating(MSR) code는 distributed storage system(분산 저장 시스템)에서 최소한의 # storage redundancy 와 함께 # repair bandwidth (i.e., the amount of traffic being transferred during a repair operation)를 최소화하는 provably(증명된) optimal # erasure code(손상 복구 코드)이다. 그러나 MSR code의 repair performance는 여전히 개선해야할 것이 있다. 이것은 MSR code의 mathematical structure 때문에 repair operation을 병렬화(parallelize)하기 여렵기 때문이다. ParaRC는 MSR code를 위한 parallel repair # framework로, (+참고 1) MSR code의 sub-packetization 성격을 이용하여 sub-block의 복구를 병렬화하고 사용 가능한 # node간에 repair load(i.e., the amount of traffic sent or received by a node, 복구 부하)를 균형있게 분산시킨다. repair bandwidth와 maximum repair load 사이에 trade-off가 존재하며, 대형 coding parameter의 경우 제한된 검색 시간 내에서 maximum repair load를 대략적으로 최소화하는 빠른 # heuristic을 제안한다. 저자들은 ParaRC에서 이 heuristic을 prototype으로 제안하고, MSR code에서 일반적인 중앙 집중식 복구 접근(conventional centralized repair approach)과 비교하여, ParaRC가 degraded read(손상된 읽기)와 full-node recovery times(전체 노드 복구 시간)을 최대 59.3% 와 39.2% 줄일 수 있다는 것을 보여준다.

 

 

 

---

Conclusion and Future Work

---

 

 

  ParaRC는 MSR-coded distributed storage systems(MSR code가 사용된 분산 저장 시스템)에서 MSR code의 sub-packetization 특성을 활용해서 parallel한 복구를 수행해서 repair performance를 개선하는 parallel repair framework이다. (+참고 2) 저자들은 repair bandwidth와 maximum repair load 간에는 trade-off 관계가 있음을 보여준다. ParaRC는 maximum repair load를 최소화하면서 low repair bandwidth를 유지하는 것을 목표로 하는 fast heuristic에 기반해서 구현되었다. 저자들은 HDFS 상에서 동작하는 middleware로 ParaRC를 구현하였다. 그리고, Alibaba Cloud에서 수행한 evaluation results는 Clay codes 와 Butterfly code의 conventional centralized repair approach 뿐만 아니라 (+참고 3) RS codes의 경우 repair pipelining approach 보다도 ParaRC가 degraded reads(하향된 reads)와 full-node recovery(전체 노드의 복구)의 repair performance를 개선하는 것으로 나타났다.

  저자들은 본 연구의 limitation을 논의하고, 다음과 같은 issue들을 future work를 위한 주제로 제시한다.

  현재까지, ParaRC의 performance 향상만 실험적으로 보여주었으나, ParaRC design의 theoretical analysis(이론적 분석)은 아직 다루지 않은 문제들이 있다. 몇가지 이론적으로 다루지 않은 문제는 다음과 같다 :

1. repair bandwidth와 maximum repair load를 모두 최소화하는 multi-objective optimization problem(다목적 최적화 문제)의 공식화
2. 제안된 heuristic과 MLP의 차이
3. 제안된 heuristic의 수렴성
4. 더 빠르고 효율적인 heuristics

  등이 있다.

  현재, ParaRC는 single # stripe(i.e., intra-stripe parallelism, 하나의 stripe)내에서 repair parallelism에 초점을 두고 있다. ParaRC를 multiple stripes(i.e., inter-stripe parallelism, 다중 stripe) 복구 병렬성으로 확장하여 더 나은 performance 향상을 위한 최적화가 가능하다. 특히, stripe가 많은 node에 걸쳐 분산되는 declustered 환경에서 더 유용하다. 또한, ParaRC의 fullnode recovery는 현재 모든 reconstructed block을 failed node를 대체하는 new node에 저장한다. reconstructed block들을 여러 node에 분산하여 bottleneck phenomenon을 방지학 수 있도록 확장할 수 있다.

  ParaRC는 현재 대형 block들과 moderate parameters n과 k에 대해 설계되어 있다. 향후 작업에서는 small block들과 wide stripes(wide stripes encode data with large parameters n and k for ultra-low redundancy)를 고려한다.

 

 

---

 

 

 

---

+ 참고 설명

---

 

 

 

(+참고 1) MSR code의 sub-packetization 성격을 이용하여 sub-block의 복구를 병렬화한다.

  "Sub-packetization"은 erasure coding에서 사용되는 하나의 개념으로, 원본 데이터를 일정 크기의 작은 조각들로 분리하는 것을 말한다. 예를 들어, 1GB 파일을 1MB 크기의 sub-packet으로 분리할 경우, 1000개의 sub-packet으로 분리된다.

  ParaRC는 MSR code에서 sub-packetization을 활용하여 repair operation을 parallelize한다. # sub-blocks는 sub-packet으로부터 생성되고, 각 sub-block은 repair unit(복구 단위)이 된다. ParaRC는 sub-block의 repair를 병렬화하여 사용 가능한 # node간에 repair load를 균등하게 분배한다. 이렇게 하면 전체 repair time을 단축시킬 수 있으며, 기존의 MSR code에서 발생하는 repair bottleneck phenomenon을 해소할 수 있다.

+

  

(+참고 2) 저자들은 repair bandwidth와 maximum repair load 간에는 trade-off 관계가 있음

  "repair bandwidth"와 "maximum repair load" 사이에는 trade-off 관계가 있다. 이는 MSR code에서 data fragment를 복구할 때 발생하는 amount of data transmission와 각 node에서 처리할 수 있는 최대 데이터 양 사이에 균형이 맞는 부분을 찾아야 한다는 것을 의미한다.

  만약, data repair에 대한 priority를 repair bandwidth에 두게 되면, 더 많은 데이터가 한번에 전송되어 network bandwidth를 많이 사용하게 된다. 반대로, priority를 maximum repair load에 두면, 비교적 적은 데이터가 전송되지만, 더 많은 node가 repair operation에 참여해야 하기 때문에 각 node의 processing load가 높아질 수 있다. 이런 이유로 이 두 가지는 trade-off 관계라 말할 수 있다.

+

 

(+참고 3) RS codes의  repair pipelining approach

  본 논문인 ParaRS의 reference에 추가되어 있던 논문인 "Repair pipelining for erasure-coded storage: Algorithms and evaluation"  에서는 distributed storage system에서 data repair를 위한 RS codes의 Repair pipelining approach를 제안하고 그 성능을 평가하는 방법에 대해 소개한다.

  "Repair pipelining for erasure-coded storage: Algorithms and evaluation"에서는 기존의 복원 방식에서 bottleneck phenomenon이 발생하는 문제점을 해결하기 위해 parallel repair algorithm을 제안한다. 이를 위해 repair operation을 # pipeline으로 나누어 처리하고, repair operation간에 서로 다른 node를 사용하여 bottlenect phenomenon을 최소화한다.

  이 논문에서는 proposed repair pipelining approach가 기존의 repair 방식보다 더 나은 복구 속도와 processing throughput을 제공한다는 것을 실험적으로 입증하였다. 또한 이러한 방식은 다양한 환경에서 적용 가능하고, 비교적 낮은 overhead로 구현할 수 있어서 실용적이라고 말한다.

 

  추가로, "PipeRS: Pipeline-Based Partial Stripe Repair in Distributed Storage Systems" 논문에서는 이 방법은 repair process를 일련의 단계로 분할하여 parallelize하고, 이를 통해 repair bandwidth를 감소시키고 system recovery time을 단축시켰다. 조금더 자세히로는, repair operation을 첫 번째 단계와 두 번째 단계로 분할하고, 이러한 단계 사이에 데이터를 임시 저장하는 buffer를 사용하여 repair bandwidth를 줄인다.

+

 

 

---

 

 

 

---

# 용어 정리

---

 

 

# regenerating

  "Regenerating"의 사전적인 의미는 "새로 만들어내는 것"이다. 하지만 computer science에서 "regenerating"은 data recovery and restoration(복원)을 의미하는 용어로 사용된다. 예를 들어, regenerating codes는 data storage system에서 degraded data fragment을 복구하고 시스템 전체를 복원하는 데 사용된다.

#

 

# storage redundancy

  "storage redundancy"는 data storage system에서 data의 backup, 복제 또는  # parity 정보 등의 추가 정보를 사용해서 data loss를 방지하는 데 사용되는 개념이다. 즉, data를 안정적으로 보호하기 위해 원본 데이터 외에 추가적인 데이터를 저장하는 것을 말한다. 이렇게 저장된 데이터는 system의 다른 장치에서 사용 가능하며, data loss가 발생했을 때 복구하는 데 사용될 수 있다. 이러한 방식으로 데이터를 안전하게 보호하면, system failure나 data loss 등의 문제에 대응할 수 있다.

#

 

# parity

  "parity"는 data protection을 위해 추가된 bit 정보이다. 일반적으로 RAID와 같은 data repair technique에서 사용된다. 이러한 기술에서는 여러 개의 hard drive를 조합해서 하나의 logical disk로 사용한다. 이때 추가된 비트(additional bit)는 각 disk에 저장된 데이터의 subset의 XOR 결과로 계산된다. 이렇게 계산된 비트를 parity bit 또는 parity block이라고 한다. 이러한 parity 정보를 사용하여 single disk나 multiple disk 중 일부가 손상된 경우에도 데이터를 복구할 수 있다.

#

 

# repair bandwidth (i.e., the amount of traffic being transferred during a repair operation)

  "Repair bandwidth"는 distributed storage system에서 data recovery를 위해 전송되는 data의 양을 의미한다. data repair operation은 보통 손상된 block을 다른 block에서 복구하기 위해 수행되며, 이 과정에서 복구에 필요한 데이터의 양이 전송되어야 한다. repair bandwidth가 낮을수록 data transmission cost가 적게 들어가므로, distributed storage system에서는 repair bandwidth를 최소화하는 알고리즘 및 방법을 사용하여 system performance를 향상시켜주는 데 주력한다.

#

 

# erasure code(손상 복구 코드)

  이름만 들으면 삭제 코드로 오해할 수 있는데 erasure code란 HDFS, RAID 외의 storage에서 data storage space의 efficiency를 높이려고 설계된 data 복제 방식이다.

  "Erasure code(이제이저 코드)는 data를 분산 저장하는 방식 중 하나로, 데이터를 여러 조각으로 쪼개어 각각 다른 위치에 저장함으로써 data loss 시에 일부 조각을 이용해 원본 데이터를 복원하는 방식이다. 이 방식은 전통적인 # backup 방식과 달리, 데이터를 여러 장소에 저장함으로써 failure나 error가 발생하더라도 data loss를 최소화할 수 있는 장점이 있다. 또한, data distribution processing을 통해 data processing speed를 높일 수 있으며, 대용량 데이터를 안전하게 보관할 수 있는 방법 중 하나이다. 이러한 adventage 덕에, cloud storage 등에도 적용되고 있다.

#

 

# backup

  "전통적인 backup" 방식은 data를 일정한 주기로 backup server or storage device에 복사하여 보관하는 것이다. 이 방식은 data 복원 시간이 오래 걸리고, backup server나 storage device가 고장 날 경우 data repair(데이터 복구)가 어렵다는 단점이 있다. 또한, backup용 storage device를 별도로 구성해야 하므로 비용이 더 많이 들 수도 있다. 반면, erasure coding 방식은 데이터를 조각 내어 분산된 형태로 저장하므로, 하나 이상의 storage device나 node가 고장 날 경우에도 data repair(복구)가 가능하며, 비교적 적은 공간으로 많은 양의 데이터를 저장할 수 있다는 장점이 있다.

#

 

# framework

  "Framework"는 software development에서 code 작성을 위한 기본 구조를 제공하는 것이다. 일반적으로 framework는 여러 component, library, layer 및 service 등을 제공한다.

  Framework는 다음과 같은 위치와 역할을 한다.

1. Front-end Framework : User Interface (UI)와 관련된 logic을 처리한다. 대표적으로 React, Vue.js 등이 있다.
2. Back-end Framework : Web Application의 business logic을 처리한다. 대표적으로 Django, Flask 등이 있다.
3. Full-stack Framework : Front-end와 Back-end를 모두 지원하는 framework이다. 대표적으로 MEAN, MERN 등이 있다.
4. Mobile Framework : Mobile App Development에 사용되는 framework이다. 대표적으로 React Native, Flutter 등이 있다.

  Framework는 software development를 더욱 효율적으로 만들어주고, developer(개발자)들이 보다 적은 노력으로 안정적인 software를 만들 수 있도록 해준다.

  그렇다면 ParaRC는 어떤 framework인지 궁금할 수 있는 데, ParaRC는 distributed storage system에서 error repair 기능을 제공하는 # middleware이기 때문에, framework의 일부분으로 볼 수 있다. 구체적으로 MSR-coded distributed storage system에서 parallel repair operation을 수행하도록 하는 기능을 제공한다. 이러한 기능은 distributed storage system의 framework 내에서 data repair 기능을 담당하는 부분에 해당된다.

#

 

# middleware

  "Middleware"는 operating system(OS)와 application 사이에 위치하고 서로 다른 application, database 또는 기술 사이의 통합을 지원하는 software이다. 이러한 software는 특정 기능을 수행하기 위해 필요한 library, API, protocol 및 도구를 제공한다.

  system storage stack은 data storage를 관리하는 전체 시스템의 hierarchical structure를 의미한다. 일반적으로 다음과 같은 hierarchy로 구성된다 :

1. Application Level : Application(응용 프로그램)에서 data에 직접 access하는 것을 의미한다.
2. File system Level : file system에서 file을 관리하고 data를 read/write하는 것을 의미한다.
3. Block storage Level : Block storage에서 disk의 block에 직접 access하여 data를 Read/write하는 것을 의미한다.
4. Physical storage Level : disk나 block storage와 같은 physical storage device에서 data를 read/write하는 것을 의미한다.

  Middleware는 일반적으로 application level과 file system level 사이에 위치하며, data storage를 관리하기 위한 도구와 interface를 제공한다. 따라서, ParaRC도 middleware의 일종으로, system storage stack에서 application과 file system level 사이에 존재한다.

#

 

# sub-blocks과 sub-packet의 의미 차이

  sub-packetization은 하나의 data block을 작은 sub-packet으로 분할하는 과정을 의미한다. sub-packet은 data block의 작은 조각으로, erasure coding에서는 sub-packet을 이용하여 error correction(오류 정정 기능)을 수행한다. sub-packetization은 일반적으로 erasure coding에서 사용되며, 작은 sub-packet을 사용함으로써 더 나은 error correction을 제공할 수 있다.

  반면, sub-block은 distributed storage system에서 data block을 여러 개의 작은 sub-block으로 분할하는 것을 의미한다. 이렇게 분할된 sub-block들은 distributed storage system에서 여러 개의 node에 저장된다. sub-block을 이용하여 data를 parallelize하고, storage system의 scalability와 robustness를 향상시킬 수 있다.

  따라서, sub-packet과 sub-block은 서로 다른 의미의 용어이다. 다시 한번 정리해서, sub-packet은 erasure coding에서 error correction을 수행하는 과정에서 사용되는 작은 data 조각이고, sub-block은 distributed storage system에서 data를 작은 조각으로 분할하여 저장하는 것을 의미한다.

#

 

# node

  "Node"는 일반적으로 computer network에서 사용되는 용어로, network에 연결된 computer를 의미한다. node는 server, client, router, switch 등 다양한 장치가 될 수 있고, network 내에서 data를 전송하거나 받는 등의 역할을 한다. 이 때, node는 각각의 고유한 주소를 가지고 있고, 이를 이용하여 data가 정확히 전송되고 수신되도록 한다. node는 network 상에서 중요한 역할을 담당하므로, 안정적인 동작과 성능이 요구된다.

  그러나 본 논문에서 사용된 "Node"의 의미는 distributed storage system에서 사용되는 개별적인 storage device or server를 나타내는 용어이다. 이러한 node들은 data를 저장하고 필요에 따라 data를 복제하거나 복구하기 위해 서로 communicate한다. ParaRC는 이러한 node들 간의 통신을 최적화하여 parallelized repair operation을 수행하여 전체 system의 repair performance를 향상시킨다.

#

 

# heuristic (발견적, 발견적 방법)

  "Heuristic"은 문제 해결을 위한 경험적인 지식이나 경험에 의해 발견된 규칙을 이용하여 문제를 해결하거나 결정하는 방법을 의미한다. 일반적으로 정확한 optimal solution(최적해)을 찾을 수는 없지만, 제한된 검색 시간 내에서 optimal solution에 근접하는 approximate solution(근사해)을 찾거나 문제를 해결할 수 있는 근사적인 방법으로 사용된다. ParaRC에서 제안하는 빠른 heuristic은 대형 coding parameter의 경우 search time(검색 시간)을 제한하면서 maximum repair load를 최소화하기 위한 근사적인 방법을 사용한다.

#

 

# prototype

  "Prototype"은 개발 단계에서 최초의 작동 가능한 제품 또는 모델을 의미한다. 이는 일종의 샘플 제품으로, 제품의 전체 생산 또는 출시 전에 테스트 및 수정을 거쳐 제품의 최종 버전을 완성하는 데 중요한 역할을 한다. prototype은 developer 및 designer가 product concept(idea) or design을 구체화하고 테스트할 수 있는 유용한 도구이다.

#

 

# pipeline

  "pipeline"은 데이터 복원 과정을 일련의 단계로 나누어 병렬화하는 기술을 의미한다. 복원할 data가 손상된 경우, 복원을 위해 data fragment를 수집하고 처리하는 과정이 필요하다. 이 과정에서 복원할 데이터의 크기가 매우 크다면 한 번에 복원하는 것은 매우 시간이 오래 걸릴 수 있다. 이 때, 복원 과정을 일련의 단계로 분할해서 각각의 단계를 병렬로 처리함으로써 복원 시간을 단축시키는 방법이 제안되었다. 이러한 방식을 repair pipelining approach라고 한다.

  사전적인 의미로 연결을 지어보자면 Earnest 본인은 복구 작업을 여러 단계로 분할하여 각 단계를 병렬화하고, 각 단계가 연결되어 전체 복구 작업을 수행하는 과정에서 pipeline이 형성된다는 점에서 pipeline이 쓰인 것 같다. 작업을 일련의 단계로 split해서 연결한 구조가 pipeline과 유사하다는 점 때문이 아닐까? 생각한다.

#

 

# stripe

  "Stripe"는 distributed storage system에서 data fragment를 조합하여 만든 logical unit(논리적 단위)으로, 하나의 파일이나 객체를 나타낸다. 일반적으로 stripe는 fixed size를 가지고, 해당 크기는 system에서 사전에 정의된 parameter에 따라 결정된다. 각 stripe는 다수의 node에 걸쳐서 분산되어 저장되며, distributed storage system에서 data 복원이 필요한 경우 해당 stripe의 모든 node를 참조하여 복원이 수행된다. stripe의 크기와 node의 수는 system design 및 performance 목표에 따라 조정될 수 있다.

#