Метод резервирования и восстановления данных в распределенных системах их хранения



Стаття | Article    

Download

В работе предложен способ резервирования и восстановления данных, хранящихся на разнесенных удаленных носителях при постоянной или временной потере доступа к любым n из них.Высокая эффективность предложенного способа достигается за счет использования теоретически минимального числа резервных носителей, равного количеству носителей, доступ к которым утрачен, а также предельно простых вычислительных процедур, обеспечивающих высокую скорость реконструкции утраченных данных.Приведен теоретическое обоснование, изложена методика формирования резервных кодов и их использования для восстановления информации.

Ключевые слова: распределенные системы удаленного хранения информации, восстановление данных, восстанавливающие коды, доступ к удаленно хранящимся данным, надежность удаленного хранения данных.

ст. преп. Виноградов Ю. Н.

студ. Иванов В.Г.

НТУУ “КПИ им. Игоря Сикорского”

Method to reservation and restore data in distributed data storage systems

In this work, a method for backup and restoring data is proposed. The data is stored on different remote disks and temporary orpermanent loss of access to any n of them appears. The high efficiency of the proposed method is achieved by using a theoretically proved minimum number of backup copies of the data, which is equal to the number of the disks to which access has been lost. Additionally, an extremely simple computational procedure to ensure high-speed reconstruction of lost data is employed. The theoretical justification with a methodology of backup codes and their use for data recovery.

Keywords: remote distributed information storage systems, data recon­struction, erasures codes, remove data access, reliability of remote data storage.

sr. lect. Vinogradov Y. N.

stud. Ivanov V. G

NTUU “Igor Sikorsky KPI” FICT

Быстрый прогресс средств телекоммуникаций и средств передачи данных привели к расширяющему использованию распределенных систем обработки и хранения информации. Такие системы позволяют гибко реализовать прогрессивные концепции обмена и концен­трации вычислительных ресурсов и информации для решения прикладных задач.

Для обеспечения высокой надежности хранения информации в распределенных системах необходимы эффективные средства резервирования и восстановления данных при утрате доступа к одному или нескольким узлам хранения.

Таким образом, научная задача разработки эффективных методов резервирования и восстановления информации в распределенных системах ее хранения является важной и актуальной.

Целью исследований является разработка метода и средств восстановления данных в распределенных системах, который бы обеспечивал решение этой задачи при потере доступа к относительно большому числу узлов хранения информации с использованием минимального числа резервных узлов.

3.4. С использованием фрагмента r3,j+u третьего резервного носителя восстанавливается фрагмент au,j лежащий на (j+u)-той диагонали, проходящей в матрице под углом -45°.

3.5. Поскольку все j-тые фрагменты блоков Bv, Bw, Bu и Bz уже восстановлены, с использованием фрагмента r1,j первого резервного носителя восстанавливается фрагмент ay,j лежащий в j-том столбце матрицы.

Таким образом, описанный способ позволяет последовательно восстанавливать данные, хранящиеся на любых 5-ти узлах, к которым утрачен доступ. Предложенный способ может быть использован для восстановления данных с большего числа узлов хранения информации путем формирования и использования резервных кодов, формируемых как суммы элементов матрицы, лежащих на диагоналях под углом 11.25°, -11.25°, 5.625°, -5.625° и так далее.

Из приведенного описания очевидно, что на первом резервном узле хранится n фрагментов,на втором и третьем - по n+m-1, на четвертом и пятом - n+2∙(m-2), на пятом и шестом по n+3∙(m-1) и так далее. На практике, число m узлов хранения информации распределенной системы составляет десятки и сотни, в то время, как количество фрагментов - n данных на каждом из узлов составляет миллионы, то есть n>>m. Поэтому, можно говорить о том, что на каждом резервном узле хранится примерно n фрагментов, то есть столько же, как и на любом из основных.

Из сказанного следует, что для восстановления данных, хранящихся на любых k узлах системы предложенный способ использует только k резервных узлов, что составляет теоретический минимум избыточности.

При потере доступа к резервным узлам снижается способность восстанавливать данные из основных узлов хранения. Так при потере доступа к q из k резервных узлов хранения можно восстановить данных только k-q основных узлов.

Таким образом, по критериям отсутствия ограничений на количество узлов хранения, доступ к которым утрачен и числу используемых резервных узлов хранения предложенный метод превосходит все известные методы решения рассматриваемой задачи.

Доказано, что предложенный метод позволяет решать задачу восстановления данных при потере доступа к любым узлам хранения информации распределенной системы при использовании минимального числа резервных узлов хранения.

Предложенный метод предельно прост и легко может быть реализован программно на любых вычислительных платформах, а также аппаратно с использованием технологий FPGA.

Перечень ссылок

$1.$ Blaum M., Hafner J.I., Hetzler S.Partial MDS Codes and Their Application to RAID Type of Architectures / IEEE Transaction on Information Theory.- Vol.59.- No.7.- 2013.- PP. 4510-4519.

$2.$ W Weslay Peterson and E.J. Weldon Jr. Error-Correcting Codes.- New York: MIT Press, 1984.

$3.$ Abdel-Ghaffar K.A.S., Weber J.H. Parity-check matrices separating erasures from errors. / IEEE Transaction on Information Theory.- Vol.59.-No.6.- 2013.- PP. 3332-3346.

$4.$ Alexandros G. Dimakis, Vinod Prabhakaran, and Kannan Ramchandran. Decentralized Erasure Codes for Distributed Networked Storage. - Berkeley: University of California. - 2006. - 176 P.

$5.$ P. Corbett , B. English, A. Goel, T. Grcanac, S. Kleiman, J. Leong, and S. Sankar. Row-diagonal parity for double disk failure. In Proceedings of _the Third USENIX Conference on File and Storage_Technologies, - 2004 - PP.1-14.

Jun 16, 2017