분산 저장에서 다중 노드 손실을 고려한 부분접속수와 가용도에 대한 연구

Abstract

최근 여러 시스템에서 다루는 데이터의 양이 방대해지면서 분산 저장 시스템의 중요성이 커지고 있다. 분산 저장 시스템에서는 네트워크 상의 문제 혹은 장비의 문제로 인해 노드 손실이라는 결함이 생긴다. 이 경우 손실되지 않은 노드를 통해 손실된 노드를 원상태로 복구하는 것이 중요하다. 이 때 분산 저장에 사용된 부호가 복구의 성능을 결정짓게 된다. 시스템의 용도에 따라 분산 저장에 사용되는 부호의 성능을 결정하는 요소가 다르다. 그 중 부분접속수(locality)는 어떤 손실된 노드를 복구하기 위해 필요한 노드의 수를 의미하고 가용도는 어떤 손실된 노드를 복구할 수 있는 서로소(disjoint)인 복구집합의 수를 의미한다. 실용적인 측면에서 가용도 개념을 도입할 경우 다수의 사용자가 동시에 여러 데이터에 병렬적으로 접근함으로써 동시에 데이터를 읽을 수 있다는 장점이 있다. 따라서 가용도를 고려한 부분접속복구 부호는 핫 데이터가 주로 저장된 분산 저장 시스템에 매우 유용하다. 본 논문에서는 분산 저장 시스템에서 다중 노드 손실과 가용도를 함께 고려한 부분접속복구 부호를 새롭게 제안하고 그 부호에 대한 최소 거리의 상계를 구한다. 그리고 새롭게 제안한 부호의 최소 거리의 상계의 achievability를 보이기 위해 최소 거리 상계에 대한 등식을 만족하는 부호를 설계한다. 특히 본 논문에서는 정보 심볼들에 대한 복구집합들의 노드 손실까지 고려했기 때문에 기존의 가용도만을 고려한 부분접속복구 부호에 비해 손실에 대한 tolerance가 더 크다. 따라서 본 논문에서 제안하는 (n,k,r,t,δ)-부분접속복구 부호는 손실이 자주 일어나며 동시에 접속할 필요가 있는 핫 데이터 사용에 더욱 적합하다.

Recently, as the amount of data to be handled by various systems has increased, the importance of distributed storage systems has increased. In a distributed storage system, there is a flaw in the node loss due to network problems or equipment problems. In this case, it is important to reconstruct the lost node through the non-lost node. At this time, the code used for distributed storage determines the performance of recovery. Depending on the use of the system, the factors that determine the performance of the codes used for distributed storage are different. Among them, 'locality' means the number of nodes needed to recover a lost node, and availability means the number of disjoint recovery sets that can recover a lost node.

In practical terms, when the availability is introduced, it is advantageous that a plurality of users simultaneously access data at the same time and simultaneously read data. Therefore, locally repairable code considering availability is very useful for distributed storage systems where hot data is mainly stored.

In this paper, we propose a locally repairable code considering multi - node loss and availability in a distributed storage system. Moreover, we find the upper bound of minimum distance for the code. In order to show the achievability of the upper bound of the minimum distance of the newly proposed code, a code satisfying the equation for the bound is designed.

In particular, since we consider multiple node loss of recovery sets, we have more tolerance for loss than locally repairable code considering only the availability. Therefore, the (n, k, r, t, δ) – locally repairable code proposed in this paper is more suitable for using hot data which has frequent loss and frequent connection.