Осуществление регенерационного кодирования на базе кодов-произведений с простой проверкой на четность

_ 05.13.00 ИНФОРМАТИКА, ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА И УПРАВЛЕНИЕ

05.13.18

УДК 004.75, 004.772, 004.62

ОСУЩЕСТВЛЕНИЕ РЕГЕНЕРАЦИОННОГО КОДИРОВАНИЯ НА БАЗЕ КОДОВ-ПРОИЗВЕДЕНИЙ С ПРОСТОЙ ПРОВЕРКОЙ НА ЧЕТНОСТЬ

© 2018

Роман Владимирович Климов, аспирант

Ульяновский государственный технический университет, Ульяновск

Аннотация

Введение: сформулирована проблема наращивания объема данных и его влияние на трафик передачи данных. Описаны основные подходы к организации надежного долгосрочного хранения данных. Обоснована необходимость разработки и развития распределенных систем хранения данных.

Материалы и методы: рассмотрены основные методы оценки вероятности отказа отдельных устройств хранения данных. Представлен аналитический метод прогнозирования выхода из строя критического числа устройств хранения данных. Произведен анализ методов организации избыточного хранения данных на базе массивов-накопителей. Описан общий принцип регенерационного кодирования данных на примере систем, базирующихся на применении кодов Рида-Соломона со сложной схемой перемежения между словами. Результаты: предложен метод организации регенерационного кодирования, базирующийся на применении кодов-произведений с простой проверкой на четность с регулярным смещением. Описана обобщенная процедура осуществления кодирования предложенного кода-произведения. Описан метод осуществления регенера-ционного декодирования кода-произведения с простой проверкой на четность в условиях выхода из строя накопителя систем хранения данных.

Обсуждение: произведен анализ эффективности применения кодов-произведений с простой проверкой на четность со смещением. Представлены аналитические выражения оценки объема внутрисетевой нагрузки. Показана пригодность предложенного решения к сокращению объема передаваемого трафика, генерируемого в процессе восстановления содержимого одного утраченного устройства хранения до 30 % в сравнении с системами без дополнительного сокращения нагрузки.

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

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

Для цитирования: Климов Р. В. Осуществление регенерационного кодирования на базе кодов-произведений с простой проверкой на четность // Вестник НГИЭИ.2018. № 3 (82). С. 28-37.

THE IMPLEMENTATION OF THE REGENERATION CODING ON THE BASIS OF THE CODES WORKS WITH A SIMPLE EVEN PARITY

© 2018

Roman Vladimirovich Klimov, the postgraduate

Ulyanovsk state technical university, Ulyanovsk

Abstract

Introduction: the author formulated the problem of increasing the volume of data and its impact on data traffic. The paper describes the main approaches to the organization of reliable long-term data storage. The article substantiates the necessity of development of distributed data storage systems.

Materials and methods: the paper discusses the main methods of assessing the probability of failure of individual storage devices. An analytical method for predicting the failure of a critical number of storage devices is presented. The author analyzes the methods of excessive data storage on the basis of storage arrays. The article describes the

General principle of regenerative coding of data on the example of systems based on the use of reed-Solomon codes with a complex scheme of alternation between words.

Results: the author proposes a method for the organization of regenerative coding, based on the use of codes-products with a simple test for parity with regular displacement. This paper describes a synthesis procedure of the proposed encoding code works. The method of implementation of regenerative decoding code-product with a simple parity test in the conditions of failure of the storage drive is described.

Discussion: the article analyzes the effectiveness of the use of codes-products with a simple test for honesty with bias. The author presents analytical expressions for estimating the volume of intra-network load. The article shows the feasibility of the proposed solution to reduce the amount of transmitted traffic generated during the recovery of the content of one lost storage device to 30 % compared to systems without additional load reduction.

Conclusion: the paper considers the method of data organization in the data storage system, based on the use of codes-products with a simple test for parity with regular displacement. The main advantages of the proposed approach are shown.

Key words: reliability of storage systems, distributed storage systems, noise-resistant coding, code-product with a simple check for parity, regenerative coding, reduction of the internal network load recovery.

For citation: Klimov R. V. The implementation of the regeneration coding on the basis of the codes works with a simple even parity // Bulletin NGIEI. 2018. № 3 (82). P. 28-37.

Введение

В настоящее время наблюдается устойчивая тенденция непрерывного и интенсивного увеличения объемов генерируемой и обрабатываемой информации [1; 2]. Подобный рост связан с наращиванием числа устройств, производящих цифровые данные, распространение их в различные области человеческой деятельности, развитие концепции Интернета вещей, увеличение доли медиаданных и постоянное повышение требований к их качеству. Из данных трендов вытекает острая необходимость организации долгосрочного надежного хранения данных. Для осуществления вышеописанной задачи применяется широкий спектр устройств хранения данных, отличающихся как по природе физических процессов, лежащих в основе способов организации хранения, так и по методам непосредственного применения данных процессов. Основными требованиями к хранилищам данных являются объем, пригодный для размещения пользовательских данных, стоимость реализации устройства, доступность данных и надежность хранения данных. В ходе разработки новых накопителей постоянно ищется компромисс между этими показателями. Для оценки надежности устройств хранения используются такие метрики, как: интенсивность отказов устройств хранения, среднее время наработки на отказ, и связанная с ними вероятность отказа [3].

Невозможность безграничного наращивания плотности записи данных при сохранении малых габаритов устройств хранения и высокой доступности данных для пользователя вынуждает объединять отдельные информационные накопителеи в системы хранения данных (СХД) и их частный слу-

чай распределенные СХД (РСХД). Показателем надежности СХД является вероятность полной утраты данных, вычисляемая на базе метрик надежности устройств хранения, входящих в систему.

Гарантированная надежность хранения в СХД достигается как развитием новых технологий построения накопителей, так и применением распределенного хранения данных с дополнительным использованием методов избыточного хранения, базирующихся на разнородных методах корректирующего кодирования. Наиболее широко распространены коды с повторением, коды с простой проверкой на четность, коды с максимальным кодовым расстоянием. Показателем надежности СХД является вероятность полной утраты данных, вычисляемая на базе метрик надежности устройств хранения, входящих в систему.

Масштабирование СХД приводит к развитию и усложнению сетевой инфраструктуры, объединяющей отдельные устройства хранения. Трафик, передаваемый в обозначенной сети, формируется из трафика записи данных, трафика чтения данных и внутрисетевого трафика, в том числе трафика восстановления. В рамках данной работы наибольший интерес представляет трафик восстановления, генерируемый в процессе восстановления содержимого отдельных устройств хранения, утраченных в ходе их эксплуатации. В случае применения традиционных подходов к кодированию данных (коды с проверкой на четность, коды Хемминга, коды Рида-Соломона) в системе осуществляется передача полного объема данных, содержащихся во всех оставшихся хранилищах, защищенных одним кодовым словом. Таким образом, на сеть передачи данных оказывается значительная нагрузка, что негативно

сказывается на ее быстродействии, скорости и надежности осуществления восстановления данных. В настоящее время можно выделить два концептуальных к организации избыточного кодирования в РСХД, позволяющих снизить нагрузку на сеть передачи данных: регенерационное кодирование и применение локально-декодируемых кодов [4].

Материалы и методы

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

A

где Aq > 0 - коэффициент масштаба, определяющий скорость изменения функции, а - коэффициент формы, определяющий поведение изменения функции. В зависимости от задаваемого параметра а определяется период эксплуатации устройства (период приработки, нормального функционирования, старения и износа).

Традиционно оценка вероятности безотказной работы устройств хранения данных в период времени (0, t] вычисляется как:

t

P

0

С ростом числа устройств хранения данных в системах без резервирования происходит увеличение вероятности утраты одного хранилища, которая может быть оценена как:

n

Q

i=1

где Q(t) - вероятность утраты устройства хранения данных, n - число устройств в системе.

Применение резервирования на базе избыточного кодирования позволяет осуществлять восстановление исходного массива данных в условиях выхода из строя l < dmn накопителей, где dmn - минимальное кодовое расстояние избыточного кода. Оценка вероятности подобных событий может быть произведена с использованием биноминального распределения:

Pdl =

где P - вероятность выхода из строя одного накопителя, Q = 1 - P - вероятность сохранения работо-

способности накопителя, n - общее число накопителей. В предельном случае событие утраты данных возможно при единовременном выходе из строя l > dmn устройств хранения.

Широкое распространение в СХД нашли коды с простым повторением, коды с единичной проверкой на четность, коды Хемминага и коды с максимальным декодируемым расстоянием, например коды Рида-Соломона. Перечисленные решения обладают как положительными, так и отрицательными сторонами. Коды с повторением обладают наибольшей надежностью и создают малое влияние на сеть передачи данных. В то же время данное решение требует наличия пространства для размещения избыточности пропорционально большего объема хранимой информации. Применение кодов с простой проверкой на четность позволяет восстанавливать целостность данных только в случаях выхода из строя не более одного устройства хранения данных и отсутствием устойчивости к некорректируемым ошибкам, но они отличаются минимальным объемом избыточности. Системы, базирующиеся на организации хранения с использованием кодов Рида-Соломона, обладают сравнимыми с кодами повторениями объемами избыточности при сравнительно малом объеме избыточности. Однако восстановление содержимого утраченных устройств хранения данных требует передачи большого объема информации через транспортную сеть, связывающую отдельные устройства хранения.

Одним из путей нахождения компромисса между показателями надежности СХД, ее избыточностью и объемом внутрисетевой нагрузки, возникающей в процессе восстановления содержимого отдельных устройств хранения, является применение методов регенерационного кодирования [5; 6; 7; 8; 9; 10; 11; 12; 13; 14]. Сущность этого метода заключается в использовании конструктивных особенностей корректирующих кодов со сложной процедурой кодирования. Ярким примером данной разновидности кодов является код Рида-Соломона с перемежением между словами. В подобном решении используется сложная система перемежения символов исходного кодового слова и формирование символов избыточности на базе привлечения различных их комбинаций. Отдельные символы кодового слова, полученные в результате подобных процедур, объединяются в группы, которые размещаются в разных хранилищах. При этом распределение производится таким образом, чтобы восстановление содержимого одного из хранилищ осуществлялось из малой части фрагментов данных, распределенных в области памяти СХД. Таким образом

достигается высокая надежность хранения, малый объем избыточности и малая нагрузка на сеть передачи данных в рамках восстановления содержимого вышедших из строя элементов СХД. Недостатками описанного подхода является сложность реализации схемы кодирования данных, отсутствие однотипных методов восстановления для всех устройств СХД, а также рост нагрузки на сеть передачи данных в случае наличия транзитных устройств хранения, содержащих элементы того же кодового слова.

Результаты Альтернативой применению регенеративному декодированию предлагается способ осуществления регенерационного кодирования данных на основе применения кодов-произведений с простой проверкой на четность с регулярным смещением проверочного символа хранилища. Подобный подход базируется на модификации СХД с простой проверкой на четность путем дополнения аппарата кодирования с одной контрольной суммой дополнительной проверкой на четность [16; 17; 18; 19; 20].

Для осуществления надежного хранения данных в системах с простой проверкой на четность множество накопителей 5 = ||51= п} разделяется на подмножество устройств хранения информационных фрагментов Б = {ё | ё е 5,| Б |= п -1} и подмножество устройств хранения избыточности р = {р | р е 5,| Р |= 1}. Одно из множеств контрольных сумм размещается в памяти отдельного избыточного хранилища р. Множество контрольных сумм, вычисленных в рамках дополнительной проверки на четность, размещается в каждом из хранилищ, как в информационных, так и к избыточном. Для организации регенерационного кодирования в рамках данного подхода применяется регулярный сдвиг символов одной из контрольных сумм, что является особенностью этого способа построения кодового слова, отличающей его от традиционного процесса формирования кодов-произведений. Схема организации кода-произведения с простой проверкой на четность с регулярным смещением представлена на рисунке 1.

Рис. 1. Схема организации кода-произведения с простой проверкой на четность с регулярным смещением Fig. 1. Diagram of the organization code-works with a simple even parity with regular offset

Процесс формирования кодового слова осуществляется в шесть этапов. На первом этапе источником информации формируется массив информационных данных размера М, передаваемых на вход контроллера массива устройств хранения данных:

vinf

= {.., vj, V2,...,Vkik2,..|

Для осуществления распределения данных между устройствами хранения контроллером массива производится разделение исходного картежа

на к1 • к2 фрагментов одинакового размера & =-.

кк2

Полученные фрагменты формируют информационную часть кодового слова кода-произведения, которая может быть представлена в форме матрицы к1 х к2 элементов:

V =

V1 Vk1 +1

v2 Vk1 +2

Vki V2k

V(ki +1)(k2 -1) V(ki + 2)(k2-1) : Vkik2

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

На втором этапе осуществляется формирование проверочных символов линий кода. Вычисление проверочных символов осуществляется как сумма по модулю двух фрагментов, входящих в линию информационной части кода-произведения:

к1

р = у У2 ©...©= £у

I =1

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

чего формируется кодовое слово первичного кода: С1 = УОк .

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

вое слово вычисляется как транспонированное произведение транспонированного первичного кодового слова на порождающую матрицу Ок :

С2 = (CÏOk2)T .

На четвертом этапе из полученного кодового слова производится выделение линии, содержащей контрольные суммы хранилищ:

01 =

где (х^ - операция выделения столбца матрицы номер х.

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

0 = 01 . (11) Окончательное кодовое слово кода-произведения (щп2 = (к +1)(к2 +1), кк, ^Шп = 4) формируется из кодового слова первичного кода С\ и линии контрольных сумм хранилищ со смещением 0 . Кодовое слово фрагментируется на щщ = (к\ +1)( к2 + 2) фрагментов, которые распределяются по зонам устройств хранения данных согласно схеме, представленной на рисунке 2.

V1 ^2 % -л Pi - TV (mod 2) ¡=1

vi1+l Vk, 1 2 • • V2k, Щ Pi = Хг'.1т,"'(12>

V

Ф. qf =У v,(mod2) t: % =Vi;i.;:](mod2) ï;-l Î2 = S%n-:(mod2) i-0 ^^ ft = Z%1+i(mod2> ^______i-Q ^__

Рис. 2. Схема распределения фрагментов данных в зонах накопителей Fig. 2. The allocation of data fragments in the storage areas

Наиболее вероятным событием для систем хранения данных является группировка стертых фрагментов в рамках памяти одного устройства хранения данных, вызванная его выходом из строя. Код-произведение размерности 2D позволяет вос-

станавливать 5 >> dшn -1 стертых фрагмента, при условии, что они не группируются в рамках одной кодовой линии или одного хранилища.

В случае выхода из строя одного отдельного устройства хранения данных происходит стирание

всех фрагментов, расположенных в его памяти. Пример схемы распределенной системы хранения

данных с единичным утраченным устройством хранения представлен в таблице 1.

Таблица 1. Схема распределения данных в системе хранения данных с одним утраченным накопителем Table 1. The distribution of data in the data storage system with a single lost drive

Накопитель 1/ Drive 1

Накопитель 2/ Drive 2

Накопитель k1 / Drive k

Накопитель избыточности/ Redundancy drive

Линия 1/ Line 1

Линия 2/ Line 2

vk1 +1

v2

vk1 +2

vki v2k1

k

2 vj (mod 2) i=1

2k,

2 vj

i=k1 +1

Линия _ 1 / Line &2 _ 1

Линия k 2 / Line k 2

Линия избыточности/ Redundancy line

v

v

vk1(k2 -1) vhk 2

k1k2

2 vi

k2 -1

i=1

i=1

^ vik1 + 2

i=0

2 vi

i=(k1 +1)(k2 -2) k1

2 vi

i=

k2 -1

2 vik1 +1(mod2) i=0

Реконструкция содержимого утраченных в ходе эксплуатации устройств хранения СХД, построенной на базе кодов-произведений с простой проверкой на четность с регулярным смещением, может осуществляться как с использованием традиционного метода декодирования кодов-произведений с простой проверкой на четность, так и с использованием регенерационного метода реконструкции.

В ходе выполнения тривиальной процедуры восстановления реконструкция производится с привлечением только горизонтального направления кода-произведения. В рамках этого подхода осуществляется сбор всех фрагментов, содержавшихся в памяти неповрежденных узлов системы, и формирование из них нового исходного кодового слова У,, состоящего из к1 на к2 + 1 фрагментов.

Реконструкция содержимого утраченного устройства хранения осуществляется путем умножения кодового слова Уь на проверочную матрицу Икх +1,1 , представляющую собой матрицу единиц соответствующего порядка, находимую как:

Б =

где Оь - реконструируемое содержимое утраченного устройства хранения.

Коренным отличием регенерационного метода реконструкции от традиционного является сниженный объем внутрисетевой нагрузки восстановления.

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

Процесс регенерационной реконструкции на этапе формирования исходного кодового слова требует получение по к2 -1 фрагментов из к1 оставшихся устройств хранения, при этом линия контрольных сумм устройств хранения данных не за-действуется. Из полученных фрагментов формируется сокращенное кодовое слово У^', состоящее из к[(к2 -1) фрагментов:

Vl =

v2

vk1 +2

vk

v2h

v

vk1

2 vi (mod2) i=1 2k1

2 vi(mod2) i=k1 +1

k '

2 vi(mod2) i=(k1 +1)(k2 -2) _

.

Из полученного сокращенного кодового слова путем умножения его на соответствующую проверочную матрицу реконструируются к2 - 1 фрагмен-

k

k

2

k

тов, содержащихся в зонах утраченного устройства хранения:

R = k1k2 _

kk

1k2

(

Dl ' = VL =

V,

•Vi

\

V К(к!+1Хкг-2) У

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

^ =

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

Обсуждение Относительная скорость кода-произведения с простой проверкой на четность вычисляется как:

.

«1«2

Из (16) видно, что кодовая скорость увеличивается с ростом числа фрагментов, размещаемых в каждом хранилище, и асимптотически приближается к относительной скорости кода с простой проверкой на четность, применяемая в СХД RAID-3 -RAID-5.

Применение тривиальной процедуры восстановления содержимого утраченного хранения данных приводит к увеличению нагрузки на сеть передачи данных за счет передачи дополнительной линии для каждого кодового слова:

X = (k2 +1)(k1)a = M + M > уraid-3 = k2^« = M, (17) k2

где Yraid-3 - нагрузка на сеть передачи данных в системах. построенных по технологии RAID-3. Таким образом, применение данного подхода к реконструкции данных не оптимально.

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

п п 14 -.ч а л, 2M M ,10Ч

Yreg =

k2 k1k2 k

Графики зависимости внутрисетевой нагрузки, возникающей в условиях восстановления содержимого утраченного накопителя, от числа фрагментов, располагаемых в каждом из устройств СХД при разном числе информационных накопителей, представлен на рисунке 3.

Рис. 3. Зависимость внутрисетевой нагрузки восстановления от числа фрагментов в накопителе Fig. 3. Recovery internal network load dependence on the number of fragments in the drive

Очевидно, что применение кода-произведения с простой проверкой на четность со смещением при использовании процедуры регенерационного декодирования позволяет сократить нагрузку на сеть передачи данных в условиях восстановления содержимого одного утраченного устройства хранения более чем на 30 % от нагрузки массива с одиночной проверкой на четность.

Заключение Рассмотрен метод организации данных в СХД, базирующийся на применении кодов-произведений с простой проверкой на четность с регулярным смещением. За счет конструктивных особенностей построения кодового слова и применения специаль-

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

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

СПИСОК ЛИТЕРАТУРЫ

1. Рост объема информации - реалии цифровой вселенной // Технологии и средства связи. 2013. № 1 (94). С. 24-25.

2. IDC digital universe 2014 Russia [Электронный ресурс]. Режим доступа: https://russia.emc.com/collateral/analyst-reports/idc-digital-universe-2014-russia.pdf (дата обращения: 25.05.2017).

3. Шарапов Р. В. Аппаратные средства хранения больших объёмов данных // Инженерный вестник Дона. 2012, Т. 24. № 4-2 (23). С. 67.

4. Andy Klein. Hard Drive Stats for Q1 2017 [Электронный ресурс]. Режим доступа: https://www.backblaze.com/blog/hard-drive-failure-rates-q1-2017/ (дата обращения: 27.06.2017).

5. Rashmi K. V., Nihar B. Shah, Vijay Kumar P. Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction // IEEE Transactions. 2011. Vol. 57, № 8. P. 5227-5239.

6. Dimakis A. G., Godfrey P. B., Wainwright M., Ramchandran K. Network Coding for distributed storage systems // Proc. 26th IEEE International Conference on Computer Communications (INFOCOM), Anchorage, May 2007, P. 2000-2008.

7. Dimakis A., Godfrey P., Wu Y., WainwrightM., and Ramchandran K. Network coding for distributed storage systems // IEEE Transactions on Information Theory/ 2010. Vol. 56. №. 9. P. 4539-4551.

8. Marwen Zorgui, Zhiying Wang. Centralized multi-node repair for minimum storage regenerating codes // IEEE International Symposium on Information Theory (ISIT). 2017. P. 2213-2217.

9. Гладких А. А., Климов Р. В., Сорокин И. А. Методы снижения внутрисетевой нагрузки в распределенных системах хранения данных // Автоматизация систем управления. Том 41. № 3. 2015. С. 34-41.

10. Климов Р. В. Методы снижения внутрисетевого трафика в процедуре восстановления данных // Радиотехника. 2016. № 9. С. 44-47.

11. Jy-yong Sohn, Beongjun Choi and Jaekyun Moon. A Class of MSR Codes for Clustered Distributed Storage [Электронный ресурс]. Режим доступа: https://arxiv.org/pdf/1801.02014.pdf (date of access: 26.02.2018).

12. Steve Jiekak, Anne-Marie Kermarrec, Nicolas Le Scouarnec, Gilles Straub, Alexandre Van Kempen. Regenerating Codes: A System Perspective // IEEE 31st Symposium on . Reliable Distributed Systems (SRDS), 2012.

13. Hanxu Hou, Patrick P. C. Lee, Kenneth W. Shum, Yuchong Hu. Rack-Aware Regenerating Codes for Data Centers [Электронный ресурс]. Режим доступа: https://arxiv.org/pdf/1802.04031.pdf (date of access: 26.02.2018).

14. Bing Zhu, Kenneth W. Shum, Hui Li, Hanxu Hou. General Fractional Repetition Codes for Distributed Storage Systems // IEEE Communications Letters, APRIL 2014. Vol. 18. №. 4. P. 660-663.

15. Гладких А. А. Основы теории мягкого декодирования избыточных кодов в стирающем канале связи. Ульяновск : УлГТУ. 2010. 379 с.

16. Скляр Б. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр. пер. с англ. М. : Издательский дом «Вильямс», 2003. 1104 с.

17. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М. : Техносфера, 2005. 320 с.

18. Кларк Дж., мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. Пер. с англ. М. : Радио и связь, 1987. 392 с.

19. Гладких А. А., Капустин Д. А., Климов Р. В., Солодовникова Д. Н. Адаптивный кодер гиперкода размерности 3D. Патент на изобретение № 2480918, опубликовано: 27.04.2013 Бюл. № 12.

Дата поступления статьи в редакцию 17.01.2018, принята к публикации 12.02.2018.

Информация об авторах: Климов Роман Владимирович, аспирант

Адрес: Ульяновский государственный технический университет, 432027, Россия, г. Ульяновск, ул. Северный Венец, 32 E-mail: chorrus@mail.ru Spin-код: 1496-9625

Автор прочитал и одобрил окончательный вариант рукописи.

REFERENCES

1. Rost ob"ema informacii - realii cifrovoj vselennoj [The growing volume of information - the realities of the digital universe], Tekhnologii i sredstva svyazi [Technologies and means of communication], 2013, No. 1 (94), pp.24-25.

2. IDC digital universe 2014 Russia [Elektronnyi resurs]. Available at: https://russia.emc.com/collateral/ analyst-reports/idc-digital-universe-2014-russia.pdf (Accessed: 25.05.2017).

3. Sharapov R. V. Apparatnye sredstva hraneniya bol'shih ob"yomov dannyh [Hardware store large amounts of data], Inzhenernyj vestnik Dona [Engineering Bulletin of Don], 2012, Vol. 24, No. 4-2 (23), pp. 67.

4. Andy Klein, Hard Drive Stats for Q1 2017 [Elektronnyi resurs]. Available at: https://www.backblaze.com/ blog/hard-drive-failure-rates-q1-2017/ (Accessed: 27.06.2017).

5. Rashmi K. V., Nihar B. Shah, Vijay Kumar P. Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction, IEEE Transactions, 2011, Vol. 57, No. 8, pp.5227-5239.

6. Dimakis A. G., Godfrey P. B., Wainwright M., and Ramchandran K. Network Coding for distributed storage systems, Proc. 26th IEEE International Conference on Computer Communications (INFOCOM), Anchorage, May 2007, pp. 2000-2008.

7. Dimakis A., Godfrey P., Wu Y., Wainwright M., and Ramchandran K. Network coding for distributed storage systems, IEEE Transactions on Information Theory, 2010, Vol. 56, No. 9, pp. 4539-4551.

8. Marwen Zorgui, Zhiying Wang, Centralized multi-node repair for minimum storage regenerating codes, IEEE International Symposium on Information Theory (ISIT), 2017, pp. 2213-2217.

9. Gladkih A. A., Klimov R. V., Sorokin I. A. Metody snizheniya vnutrisetevoj nagruzki v raspredelennyh sistemah hraneniya dannyh [Methods to reduce internal network load in distributed data storage systems], Avtomatiza-cija sistem upravlenija [Automation of control systems], 2015, Vol. 41, No. 3, pp. 34-41.

10. Klimov R. V. Metody snizhenija vnutrisetevogo trafika v procedure vosstanovlenija dannyh [Method of net traffic reducing in the data recovery procedure], Radiotehnika [Radioengineering], No. 9, 2016, pp. 44-48.

11. Jy-yong Sohn, Beongjun Choi and Jaekyun Moon, A Class of MSR Codes for Clustered Distributed Storage [Elektronnyi resurs]. Available at: https://arxiv.org/pdf/1801.02014.pdf (Accessed: 26.02.2018).

12. Steve Jiekak, Anne-Marie Kermarrec, Nicolas Le Scouarnec, Gilles Straub, Alexandre Van Kempen. Regenerating Codes: A System Perspective, IEEE 31st Symposium on, Reliable Distributed Systems (SRDS), 2012.

13. Hanxu Hou, Patrick P. C. Lee, Kenneth W. Shum, Yuchong Hu, Rack-Aware Regenerating Codes for Data Centers [Elektronnyi resurs]. Available at: https://arxiv.org/pdf/1802.04031.pdf (Accessed: 26.02.2018).

14. Bing Zhu, Kenneth W. Shum, Hui Li, Hanxu Hou, General Fractional Repetition Codes for Distributed Storage Systems, IEEE Communications Letters, April 2014, Vol. 18, No. 4, pp. 660-663.

15. Gladkih A. A. Osnovy teorii myagkogo dekodirovaniya izbytochnyh kodov v stirayushchem kanale svyazi [Fundamentals of the theory of soft decoding of redundant codes in the erase channel of communication], Ul'yanovsk : UlGTU, 2010, 379 p.

16. Sklyar, B. Cifrovaya svyaz'. Teoreticheskie osnovy i prakticheskoe primenenie [Digital Communications: Fundamentals and Applications], 2nd Edition, Moscow: Publ. «Vil'yams», 2003, 1104 p.

17. Morelos-Saragosa R. Iskusstvo pomekhoustojchivogo kodirovaniya. Metody, algoritmy, primenenie [The art of error-correcting coding. Methods, algorithms, application], Moscow: Tekhnosfera, 2005, 320 p.

18. Klark Dzh., ml., Kejn Dzh. Kodirovanie s ispravleniem oshibok v sistemah cifrovoj svyazi: Per. s angl. [Encoding with error correction in digital communication systems], Moscow: Radio i svyaz', 1987, 392 p.

19. Gladkih A. A., Kapustin D. A., Klimov R. V., Solodovnikova D. N. Adaptivnyj koder giperkoda razmer-nosti 3D [Adaptive coder of 3D dimension hypercode], Patent na izobretenie No. 2480918. Byulleten', No. 12, 2013.

Submitted 17.01.2018; revised 12.02.2018.

About the authors: Roman V. Klimov, the postgraduate student

Ulyanovsk State Technical University, 432027, Russia, Ulyanovsk, Severny Venetz str., 32 E-mail: chorrus@mail.ru Spin-Kog: 1496-9625

Author have read and approved the final manuscript.