(관심 논문) Practical Design Considerations for Wide Locally Recoverable Codes (LRCs)

Saurabh Kadekodi∗ , Shashwat Silas∗ , David Clausen, Arif Merchant Google

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

USENIX Association

21st USENIX Conference on File and Storage Technologies

 

 

---

Abstract

---

 

 

  Large-scale storage clusters의 대부분 data는 # erasure coding이 사용된다. # Exascale에서는 # low storage overhead, efficient reconstruction, and easy deployment를 위해 erasure code를 최적화하는 것이 중요하다. (+참고 1) Locally Recoverable Codes (LRCs)는 이 분야에서 중요성을 띄며, 이는 많은 requirements (요구사항)을 균형잡을 수 있다. 본 논문의 연구에서는 wide LRC를 연구하였다. 이것은 stripe당 block 수가 많고 storage overhead가 적은 LRC이다. 이 codes는 실무자들이 더 높은 storage saving을 활용하기 위해 자연스럽게 흘러가는 다음 단계이지만, 자체적인 도전 과제가 있다. 특히, 더 넓은 stripe는 동시에 많은 장애 (failures)를 발생시키기 때문에 그 reliability가 중요하다.

  저자들은 몇 가지 인기 있고 새로운 LRC를 실질적인 측면에서 분석한다. 저자들은 wide LRC에 대한 reliability가 여러 design choices에 민감하게 영향을 받는 것으로 밝혀졌다는 것을 알아냈다. 일부 design choices는 이론가들에게 간과되었고, 다른 design choices는 실무자들에게 간과되었다. 이러한 통찰을 바탕으로, 저자들은 Uniform Cauchy LRCs라는 새로운 LRCs를 구성했다. 이 코드들은 simulation에서 우수한 성능을 보이며, Google storage cluster에 배치된 wide LRC에서 관찰된 # unavailability events에 대한 reliability가 33% 향상되었다. 또한, 이러한 code들이 일반적인 maintenance events (유지 보수 상황)에서의 robustness (견고성)을 향상시키는 방식으로 쉽게 배치할 수 있음을 보여준다. 그리고 이 과정에서 theory-minded(이론 중심) readers에게 흥미로운 distance optimal LRCs의 매우 간단하고 새로운 구성을 제공한다 ( 다른 constructions도 알려져 있다) .

 

 

 

---

Conclusion

---

 

 

  본 연구에서는 real world scenario에서 LRC reliability에 영향을 미치는 다양한 세부 요인들이 있다는 것을 보여준다 : coefficients in the generator matrix (생성 매트릭스의 계수), design of local repair groups (로컬 복원 그룹의 설계), 그리고 maintenance-robust-deployment (유지보수 강력한 배치) 등이 그 예이다. 본 논문에서는 reliability에 대한 실험 기반의 이해의 가치를 보여준다. 이것은 reliability에 의미있는 영향을 미치는 design choices에 대한 새로운 통찰력을 제공한다. 실제로, Uniform Cauchy LRCs의 구성이 인기있는 코드(provably distance optimal, 증명된 거리 최적 코드)를 능가하는 더 나은 performance를 보인다.

 

 

 

 

 

 

 

 

---

 

---

 

+ 참고 설명

---

    

 

(+참고 1) Locally Recoverable Codes (LRCs)

  "Locally Recoverable Codes (LRCs)는 data storage system에서 사용되는 효율적인 오류 정정 기술 중 하나이다. 기본 아이디어는 데이터를 조각으로 나누고 각 조각에 대한 부분 parity를 계산하여 저장하는 것이다. 이러한 부분 parity를 사용하여 데이터 손상 시 손상된 조각의 parity를 기반으로 데이터를 복구할 수 있다.

  LRC는 이러한 다른 코드보다 더 많은 부분 parity를 사용한다. 예를 들어, 한 개의 조각이 손상된 경우에도, LRC는 해당 조각과 함께 다른 조각들의 부분 parity를 사용하여 해당 조각을 복구할 수 잇다. 이러한 기능은 전체 data를 복구할 때 필요한 비용을 크게 줄여준다.

  LRC는 대규모 data storage system에서 매우 중요하다. 이는 대량의 data loss가 발생할 가능성이 있는 시스템에서도 reliability를 보장하기 때문이다. 또한, LRC를 사용하면 더 효율적으로 storage space를 활용할 수 있다.

+

 

 

 

---

# 용어 정리

---

 

 

# Erasure coding

  "Erasure coding"이란 데이터 손실을 방지하기 위한 기술 중 하나이다. 일반적으로 RAID(Redundant Array of Inexpensive Disks)에서 많이 사용되는 기술이다. Data를 여러 조각으로 나누고, 이 중 일부 조각으로 추가하여 오류에 대한 복구가 가능하게 하는 기술이다. 이렇게 조각을 나누고 추가함으로써, 데이터를 여러 곳에 저장하므로 데이터 손실에 대한 security를 높일 수 있다.

  Erasure coding에는 여러 종류가 있으며, 주로 Reed-Solomon, Cauchy-Reed-Solomon, Fountain Codes 등이 있다. 이 중에서 Reed-Solomon이 가장 널리 사용되며, bit error, block error, 전체 disk failure 등 다양한 오류를 복구할 수 있다. Erasure coding은 일반적으로 비용이 더 드는 것이 단점이다. 하지만, 대규모 datacenter에서 사용되는 경우, data failure를 방지하기 위해 필수적인 기술 중 하나이다.

#

 

# Exascale

  kilo (K) → mega (M) → giga (G) → tera (T) → peta (P) → exa (E) → zetta (Z) → yotta (Y)

10^3 (천)  10^6 (백만)  10^9 (십억) 10^12 (조)    10^15       10^18        10^21          10^24

  exascale은 초대규모 데이터를 처리하기 위한 computing performance unit을 말한다. 이를 위해서는 초당 10^18회 이상의 연산을 수행할 수 있어야 하며, 이를 위해 대규모 distributed computing cluster, 강력한 processor, 대용량 memory 등이 필요하다. 이러한 technical requirement을 충족시켜 대규모 데이터 처리를 가능하게 하는 것이 exascale이다.

#

 

# low storage overhead

  "low storage overhead (저 저장 용량 오버헤드)"는 data storage system or method의 속성을 나타내는 데, 이는 원래 data 이외에 최소한의 additional storage space를 사용하여 redundancy(불완전성), fault tolerance(장애 허용성), 또는 기타 원하는 기능을 달성할 수 있는 것을 말한다. 즉, physical

 

# unavailability events

  "event"는 일종의 사건이나 상황을 의미한다. "unavailability events"는 어떤 이유로 인해 데이터가 사용 불가능한 상황이 발생하는 사건을 의미한다. 예를 들어, hardware failure, network failure, power failure (전력 공급 장애) 등이 그 예시가 될 수 있다.

#