In this thesis, we study the index coding problems for repair problems of distributed storage systems with local hierarchical structures. In distributed storage systems, it is well known that the maximum distance separable (MDS) erasure codes is the optimal scheme in terms of redundancy-reliability tradeoff. However, in real storage systems such as Hadoop distriubted file system which is used by Facebook and Yahoo, only 8 percent of the data is MDS encoded though it is still the most efficient. It is because of the serious transmission cost in the repair process of MDS coded distributed storage system, hence reducing the cost is the most important and challenging problem of researches on the distributed storage systems.
We present that a repair problem of multiple failures in a distributed storage system with local hierarchy can be immediately reduced to an index coding problem. Consequently, numerous results in the field of index coding can be applied to the repair problems of distributed storage systems. Motivated by the fact, we proposed an efficient linear binary index coding algorithm named "The Extended LDG Algorithm". From the existing algorithm proposed by Birk and Kol (FOCS` 06), we develop 2 extensions which are "column merging" and "row addition and backward induction heuristic". Considering a transpose model of an index coding instance and cycles in the graph model of the index coding problem obtained by the existing algorithm, we improve performance of the algorithm and offer the lower number of transmitted blocks for a given index coding problem. In conclusion, we contribute to the repair problems of distributed storage systems with local hierarchical structures by developing an efficient index coding algorithm extended from the existing one.
본 논문에서는 지역 계층구조를 가지는 분산저장장치에서의 데이터 복구과정에 사용되는 인덱스코딩 기술과, 인덱스코딩에 사용될 수 있는 효율적인 선형 알고리즘에 대해 연구하였다. 최근 구글, 페이스북과 같은 IT기업의 발달과 스마트 폰의 보급으로 데이터 저장공간에 대한 요구가 빠르게 증가하고 있다. 급증하는 데이터 요구를 감당하기 위해 저비용의 저장장치를 주로 사용할 수 밖에 없고, 때문에 데이터의 안정성과 복구과정에 관한 연구의 필요성이 대두되고 있다. 데이터의 안정성을 높이기 위해 많은 시스템에서 여분의 복제 데이터를 생성하는데, 이때 단순한 복제 데이터가 아닌 MDS 코드를 이용하여 저장을 하면 같은 저장공간을 사용하였을 때 가장 높은 안정성을 얻을 수 있는 것으로 알려져 있다. 하지만 페이스북 등 많은 IT기업에서 사용되는 Hadoop 분산파일시스템 (HDFS) 같은 경우, 전체 데이터의 8퍼센트 정도만을 MDS 코드를 이용하여 저장하는데, 이는 MDS 코드를 사용하였을 때 발생하는 심각한 복구비용의 문제 때문이다. 이러한 점에서 보았을 때, 분산저장장치에의 연구에 있어 복구비용의 문제가 매우 중요한 핵심연구라 할 수 있다. 한편 최근 많은 연구결과에서 지역 계층구조를 가지는 분산 저장장치를 보편적으로 고려하는데, 이 때 다수의 데이터 소실이 동시에 일어난 상황에서의 네트워크 비용을 최소화하는 문제가 사전정보를 가지는 브로드캐스트 문제로 변형되어 인덱스코딩의 결과를 적용할 수 있음을 보일 수 있다.
이에 따라 본 논문에서는, 선형 인덱스코드의 효율적 설계를 위해 기존의 선형 인덱스코딩 알고리즘에 대해 연구하였다. 그 중 다른 알고리즘에 비해 효율적 성능을 보이는 것으로 알려진 체험적 선형 알고리즘인 `The Least Difference Greedy Clique Cover Algorithm`에 대해 집중적으로 연구하여 이를 확장한 `Extended LDG Algorithm`을 제안하였다. 기존 행간의 차이만을 이용하여 행렬의 위수를 줄이는 방법에서, 두가지 확장된 개념을 통해 알고리즘의 성능을 개선하였다는 것이 본 논문의 주요한 기여라고 할 수 있다. 첫째로 열간의 차이를 추가로 고려할 수 있는 전치행렬 모델을 이용하여 성능을 개선하였고, 둘째로 정해지지 않은 원소가 있는 행렬에서의 행간의 합과 차에 대한 개념을 도입하여 LDG 알고리즘 이후 추가로 행렬의 위수를 줄일 수 있는 방법을 제안하였다. 이러한 알고리즘의 확장을 통해 제안된 알고리즘은 거의 모든 영역에서 기존 알고리즘보다 좋은 성능을 나타내는 것을 볼 수 있고, 이를 통해 분산저장장치에서의 복구비용을 줄이는데 기여하였다고 할 수 있다.
