close

Вход

Забыли?

вход по аккаунту

?

Исследование методов оптимизации нагрузки восстановления распределенных систем хранения данных на базе корректирующих кодов

код для вставкиСкачать
На правах рукописи
Климов Роман Владимирович
ИССЛЕДОВАНИЕ МЕТОДОВ ОПТИМИЗАЦИИ НАГРУЗКИ
ВОССТАНОВЛЕНИЯ РАСПРЕДЕЛЕННЫХ СИСТЕМ ХРАНЕНИЯ
ДАННЫХ НА БАЗЕ КОРРЕКТИРУЮЩИХ КОДОВ
Специальность 05.12.13 – Системы, сети и устройства телекоммуникаций
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата технических наук
Ульяновск – 2018
Работа выполнена в федеральном
образовательном
учреждении
высшего
государственный технический университет»
государственном бюджетном
образования
«Ульяновский
Научный руководитель:
Гладких Анатолий Афанасьевич,
технических наук, профессор
доктор
Официальные оппоненты:
Смагин
Алексей
Аркадьевич,
доктор
технических наук, профессор, заведующий
кафедрой телекоммуникационных систем и сетей
ФГБОУ ВО «Ульяновский государственный
университет», г. Ульяновск.
Башкиров Алексей Викторович, кандидат
технических наук, доцент, доцент кафедры
конструирования и производства радиоаппаратуры
ФГБОУ ВО «Воронежский государственный
технический университет», г. Воронеж
Ведущая организация:
Федеральное
государственное
бюджетное
образовательное
учреждение
высшего
образования «Нижегородский государственный
технический университет им. Р. Е. Алексеева», г.
Нижний Новгород.
Защита состоится 21 сентября 2018г. в 12-00 на заседании
диссертационного совета Д219.003.02 при Федеральном государственном
образовательном бюджетном учреждении высшего образования «Поволжский
государственный университет телекоммуникаций и информатики» (ФГОБУ ВО
ПГУТИ) по адресу: 443010, г. Самара, ул. Льва Толстого д. 23, конференц-зал.
С диссертацией можно ознакомиться в библиотеке Федерального
государственного образовательного бюджетного учреждения высшего
образования «Поволжский государственный университет телекоммуникаций и
информатики» на сайте www.psuti.ru/science/diss-ob.
Автореферат разослан «____» __________2018 г.
Отзывы и замечания по автореферату в двух экземплярах, заверенных
печатью учреждения, просим направлять по вышеуказанному адресу на имя
ученого секретаря диссертационного совета.
Ученый секретарь
диссертационного совета Д219.003.02,
доктор технических наук, профессор
А.И. Тяжев
Актуальность темы
Наблюдаемая тенденция непрерывного и интенсивного роста объемов
генерируемой и обрабатываемой информации диктует необходимость
организации ее долгосрочного хранения. Для осуществления указанной задачи
применяются различные устройства хранения данных (УХД). К основным
требованиям к хранилищам данных относятся объем, пригодный для
размещения пользовательских данных, доступность данных и надежность их
хранения.
Объективное наращивание востребованного для хранения данных объема,
а также повышение их доступности для конечного пользователя достигается
путем объединения отдельных информационных накопителей в системы
хранения данных (СХД) и, в частности, распределенные систем хранения
данных (РСХД). Для обеспечения гарантированной надежности процедуры
хранения, наряду с развитием новых технологий построения накопителей, в
СХД применяются различные методы избыточного хранения, которые все чаще
базируются на механизмах избыточного кодирования. Наиболее широкое
применение нашли системы, основанные на использование кодов с
повторением, кодов с простой проверкой на четность и кодов с максимальным
кодовым расстоянием.
Для оценки надежности УХД используются такие метрики как:
интенсивность отказов УХД, среднее время наработки на отказ и связанная с
ними вероятность отказа. Показателем надежности СХД является вероятность
утраты данных, вычисляемая на базе метрик надежности УХД, входящих в
систему.
В условиях непрерывного роста масштабов СХД остро встает вопрос
транспортировки больших информационных массивов, расположенных в
хранилищах, разнесенных топологически. Подобная необходимость возникает
в случаях частичного повреждения или полной утраты целых УХД, с
последующим восстановлением их содержимого в памяти новоприбывших
накопителей. Наибольшую актуальность данная проблема приобретает в РСХД,
со значительным разнесением узлов.
Становится ясным, что применение традиционных подходов к
организации избыточности для СХД и особенно для РСХД, в совокупных
условиях роста объемов данных и загруженности транспортной сети, теряют
свою эффективность. В связи с этим актуализируется проблема поиска и
применение новых подходов к задаче вычисления и распределения
избыточности, позволяющих осуществлять надежное восстановление
утраченных фрагментов массивов данных, сопряженное с уменьшением
объемов передаваемых данных.
Степень разработанности темы исследования
Методы регенерационного кодирования, применяемого в целях снижения
нагрузки на сеть хранения данных, разрабатывались Alexandros G. Dimakis,
Kannan R. В работах эти авторов описаны концептуальные основы построения
регенерационных кодов. Вместе с этим описанные решения базируются на
3
применении кодов Рида-Соломона (РС) со сложными схемами перемежения
между кодовыми словами, что повышает сложность реализации СХД.
Задачи локального декодирования кодов решались Сергеем Еханиным,
Parikshit Gopalan, Cheng Huang, Uuseyin Simitci. Авторами описывались
основные подходы к осуществлению построения локально-декодируемых
кодов для систем РСХД.
Вопросы надежности РСХД решались Рахманом П.А., Иваничкиной Л.В.,
Непорада А.П., Kevin M, James S. Plank, Jay J. Wyle, K.Gopinath. В работах этих
авторов описаны методы определения вероятностей отказов УХД, входящих в
состав СХД, и полной утраты размещенного в СХД информационного массива.
Недостатком описанных подходов является использование замкнутых цепей
Маркова, не позволяющих прогнозировать состояния структурных элементов в
системах с динамически изменяемыми интенсивностями отказов УХД.
Цель работы: исследование систем хранения данных с гарантированной
надежностью, позволяющих оптимизировать их в смысле снижения
внутрисетевой нагрузки восстановления содержимого утраченных накопителей
на базе аппарата помехоустойчивого кодирования.
Для достижения поставленной цели в диссертационной работе решаются
основные задачи:
1. Выполняется анализ существующих подходов к организации СХД,
базирующихся на методах помехоустойчивого кодирования, выявляются их
достоинства и недостатки.
2. Разрабатывается аналитическая модель надежности СХД,
функционирующих в условиях отказов отдельных накопителей и их замены
накопителями с трансформацией общих показателей надежности системы.
3. Разрабатывается способ регенерационного кодирования, основанного
на применении произведения кодов с простой проверкой четности,
позволяющий осуществлять эффективное снижение объемов внутрисетевого
трафика в процедуре восстановления содержимого утраченных хранилищ.
4. Разрабатываются и исследуются способы организации хранения
данных и их восстановления на основе применения локально декодируемых
кодов, организованных как произведение кодов заданной размерности на базе
простой проверки на четность, позволяющие снизить внутрисетевую нагрузку
путем локализации УХД, участвующих в процедуре реконструкции.
5. Предлагается и исследуется новый способ квазилокального
декодирования
недвоичных
кодов
с
максимальным
расстоянием,
оптимизирующий нагрузку восстановления за счет участия в реконструкции
топологически ближайших хранилищ СХД и применения аппарата
перестановочного декодирования.
Объект исследования: системы хранения данных, включая
распределенные системы их хранения.
Предмет исследования: системы хранения данных и методы их
восстановления с использованием аппарата избыточных кодов.
4
Результат исследования соответствует пункту 2, 3, 9 и 12 паспорта
научной специальности 05.12.13 – Системы, сети и устройства
телекоммуникаций.
Основные положения диссертации, выносимые на защиту
1. Аналитическая модель оценки надежности СХД, учитывающая
изменения показателей надежности СХД в условиях замены утраченных
накопителей новыми.
2. Способ организации регенерационного кодирования кодовпроизведений с простой проверкой на четность со смещением,
предполагающий снижение нижней границы внутрисетевой нагрузки,
генерируемой при восстановлении содержимого утраченного хранилища.
3. Аналитическая модель оценки вероятности утраты данных в СХД на
базе многомерных произведений кодов с проверкой на четность, учитывающая
вероятностные характеристики возникновения замкнутых циклов в
проверочном соотношении.
4. Способ организации локально-декодируемого кода, основанный на
использовании многомерных произведений кодов с проверкой на четность,
предполагающий адаптивный подход к процедуре кодирования-декодирования
в целях оптимизации СХД.
5. Метод квазилокального декодирования МДР-кодов с использованием
аппарата
перестановочного
декодирования,
предполагающий
учет
топологического расположения накопителей в сети СХД.
Научная новизна диссертационного исследования
1. Предложена аналитическая модель оценки показателей надежности
СХД, позволяющая осуществлять моделирование функционирования СХД в
условиях динамического изменения показателей надежности отдельных УХД,
отличающаяся применением незамкнутых цепей Маркова.
2. Описан новый метод регенерационного кодирования данных,
основанный на применении произведения кодов с простой проверкой на
четность, позволяющий снизить нагрузку на сеть передачи данных в ходе
восстановления содержимого утраченного хранилища, отличающийся тем, что
все операции осуществляются над конечными полями Галуа порядка два, что
снижает сложность реализации кодеков.
3. Получен новый метод организации локально декодируемого кода на
базе кода-произведения с простой проверкой на четность произвольной
размерности,
позволяющий локализовать группу УХД, участвующих в
восстановлении содержимого утраченного накопителя, отличающийся
устойчивостью к возникновению критического числа выходов из строя
накопителей, не образующих замкнутые циклы в структуре кодового слова.
4. Описан новый подход к осуществлению квазилокального
декодирования максимально декодируемых кодов, позволяющий снизить
нагрузку на сеть передачи данных, отличающийся от существующих аналогов
применением процедуры перестановочного декодирования символов.
5
Теоретическая и практическая значимость работы
Представленные в диссертационной работе методы могут быть
применены для восстановления целостности массива данных, в условиях
возникновения одиночных или групповых событий выходов из строя УХД,
входящих в состав СХД. Важной особенностью предложенных методов
является возможность восстановления содержимого утраченных узлов с
минимизаций нагрузки на сеть передачи данных. Разработанные подходы
являются гибкими для масштабирования СХД, и могут обеспечивать требуемое
соотношение надежности системы, объема избыточности и объема трафика.
Достоверность и обоснованность научных результатов работы
определяется корректностью используемого математического аппарата,
основанного на методах теории вероятностей и математической статистики,
теории надежности, теории оценивания, алгебраической теории групп, колец и
полей. Аналитическое и имитационное моделирование проводилось с
использованием языков программирования высокого уровня лицензионных
версий Mathcad.
Внедрение результатов работы
Результаты исследования внедрены в организации ФНПЦ АО «НПО
«Марс» г. Ульяновск при выполнении НИР «Разработка комплексных методов
оценки динамически изменяющихся параметров корабельной компьютерной
сети и алгоритма работы коммутатора Ethernet» Шифр – «СЕТЬ -1Е УлГТУ»
завершенной в 2016 году и составной части ОКР «Создание
телекоммуникационной сети ИСБУ» Шифр – «УлГТУ – ТКС», проведенной
ФНПЦ АО «НПО «Марс»» совместно с Ульяновским государственным
техническим университетом и завершенной в 2017 году, а также в учебный
процесс УлГТУ, что подтверждается соответствующими актами.
Личный вклад
Все выносимые на защиту научные результаты получены соискателем
лично. Автор принимал непосредственное участие в планировании и
проведении работ, обработке и анализе полученных результатов, подготовке
публикаций. Сотрудники, работавшие совместно с автором по научным
направлениям, имеющим отношение к теме диссертации, поименно
представлены в качестве соавторов публикаций.
Апробация работы
Результаты диссертации докладывались и обсуждались на следующих
конференциях: Научная сессия РНТОРЭС им. Попова, посвященная Дню
Радио, г. Москва (2013, 2014); Международная конференция «Цифровая
обработка сигналов и ее применение» – DSPA, г. Москва (2014, 2015);
Международная научно-техническая конференция «Радиолокация, навигация,
связь» – RLNC, г. Воронеж (2013, 2014, 2016, 2017); Международная научнотехническая
конференция
«Проблемы
техники
и
технологий
6
телекоммуникаций» – ПТиТТ, г. Казань (2014, 2017); Международная научнотехническая
конференция
«Проблемы
техники
и
технологий
телекоммуникаций» – ПТиТТ, г. Самара (2016); Всероссийская научнопрактическая конференция «Современные проблемы создания и эксплуатации
радиотехнических систем», г. Ульяновск (2014, 2015, 2017).
Публикации
По теме диссертации опубликованы двадцать две работы, шесть из
которых в изданиях, рекомендованных ВАК Минобрнауки России. Получен
один патент на изобретение. Опубликована одна монография. Восемь работ в
материалах и трудах Международных и Всероссийских конференций.
Структура и объем диссертации
Диссертация состоит из введения, четырех глав, заключения, списка
литературы и одного приложения. Работа изложена на 125 страницах
машинного текста, содержащих 40 рисунков и 4 таблицы. Список
использованных источников составляет 89 наименований.
КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ
Во введении показана актуальность выбранной темы диссертации,
определены цель и задачи работы, методы исследования, изложены научная
новизна и практическая значимость полученных результатов, сформулированы
основные положения, выносимые на защиту.
Первая глава посвящена описанию основных концептуальных подходов
к обработке данных, предназначенных для дальнейшего размещения в памяти
УХД, входящих в состав СХД. Представлены основные концепции
осуществления
помехоустойчивого
кодирования,
применяемого
для
обеспечения надежности хранения данных в СХД. Показаны достоинства и
недостатки существующих СХД, определяются цели исследования,
формулируется постановка ряда научных задач.
Во второй главе описана обобщенная схема оценки эффективности
использования кодовых схем на базе решения задачи многокритериальной
оптимизации. Представлены три основных критерия оптимальности,
используемые в работе: применяемые ресурсы памяти, внутрисетевая нагрузка
восстановления и надежность системы.
Критерий используемых ресурсов памяти определяет общий объем
данных, распределяемый в УХД системы. Данный объем формируется как из
объема исходного массива данных, генерируемого и передаваемого в СХД
пользователем, так и объемом избыточности, формируемой непосредственной
системой в целях обеспечения безотказности работы СХД.
7
Критерий используемых ресурсов памяти может быть оценен как
относительная скорость кода R = k / n, где k - число информационных
символов кодового слова, n - общее число символов кодового слова.
Применение подобного подхода позволяет осуществлять оценку
параметра используемых ресурсов памяти безотносительно к размеру СХД и
объемам размещаемой информации.
Вторым показателем эффективности функционирования СХД является
объем внутрисетевой нагрузки восстановления  , возникающий в процессе
реконструкции содержимого УХД, утраченного в процессе эксплуатации.
Необходимо учитывать, что данный параметр СХД является комплексным и
может оцениваться с учетом как объема данных, передаваемым одним или
группой УХД в процессе реконструкции, так и числом транзитных узлов,
осуществляющих передачу как содержимого своей памяти, так и транслируя
данные из других УХД.
В случае простых СХД, строящихся по топологии звезды с контроллером
в центре, транзитные устройства передачи данных отсутствуют. В зависимости
от кодовой схемы нагрузка на сеть передачи данных будет различна, что
связанно с особенностями осуществления реконструкции содержимого
утраченного УХД.
Третьим критерием оценки оптимальности СХД является ее надежность,
выражаемая в устойчивости системы к выходам из строя отдельных устройств.
Традиционно вероятность безотказной работы УХД в период времени (0, t]
оценивается с помощью выражения:
t n
P (t ) = exp(− ∫ ∑ i (t )dt );
(1)
0 i =1
n
n
 (t ) = ∑  (t ) = ∑ i 0t  −1,
i =1
(2)
i =1
где  0 > 0 - коэффициент масштаба, определяющий скорость изменения
функции,  - коэффициент формы, определяющий поведение изменения
функции. В зависимости от задаваемого параметра  определяется период
эксплуатации устройства (период приработки, нормального функционирования,
старения и износа). При увеличении числа УХД происходит рост вероятности
утраты одного хранилища, оцениваемая как:
n
Q(t ) = 1 − ∏ Pi (t ) ,
i =1
(3)
где Q(t ) – вероятность утраты УХД, n – число устройств в системе.
Применение избыточного кодирования позволяет производить
восстановление исходного массива данных при утрате l < d min накопителей, где
d min - минимальное кодовое расстояние избыточного кода. Оценка вероятность
событий может быть произведена с использованием биноминального
распределения:
8
n
(4)
PDL =   P l Q n − l ,
l 
где P - вероятность выхода из строя одного накопителя, Q ≡ 1 − P - вероятность
сохранения работоспособности накопителя, n - общее число накопителей. В
предельном случае событие утраты данных возможно при единовременном
выходе из строя l ≥ d min УХД.
Зависимость вероятности возникновения критического числа событий
отказов от времени для кодов [25,16,4] и [125,64,8] представлена на рисунке 1.
а
б
Рисунок 1. Вероятность возникновения критического числа событий отказа для: (а) для кода
[25,16,4]; (б) для кода [125,64,8].
В целях оценки надежности СХД используются модели, базирующиеся на
применении Марковских цепей. Граф состояний классической модели "гибели
и размножения" представлен на рисунке 2.
Рисунок 2. Граф состояний модели возникновения событий утраты аутентичности.
Применение предложенной модели позволяет производить оценку
показателей надежности функционирования СХД в условиях обратимых
изменений, таких как возникновение скрытых ошибок, не выявляемых
внутренними средствами накопителей. Вероятность возникновения подобных
событий оценивается с использованием системы уравнений Колмогорова:
9
 dp0
 dt = cp1 +  + cperror − nap0 ;

 dp1 = nap − ((n − 1)a + c) p ;
0
1
 dt


 dp
 m = (n − m)apm −1 − ((n − m − 1)a + c) pm ;
 dt
 dp DL
= (n − m − 1)apm ,

 dt
(5)
DL
∑ pi = 1.
i =0
(6)
где p0 , p1..., pm , pDL - предельные вероятности состояний без ошибок, с одной
ошибкой, с m ошибками и события утраты исходных данных соответственно,
a - интенсивность возникновения некорректируемых битовых ошибок, c интенсивность
реконструкции
некорректируемых
битовых
ошибок,
m = (d min − 1) / 2 - предельное число некорректируемых битовых ошибок, при
которых возможна реконструкция.
Для решения задачи оценки состояния системы в условиях необратимого
процесса выхода из строя отдельных устройств предлагается использовать
модель на базе незамкнутой цепи Маркова. Граф состояний предложенной
модели представлен на рисунке 3.
Рисунок 3. Граф состояний для распределенной СХД
10
Для оценки вероятности состояний в подобной цепи система уравнений
Колмогорова принимает вид:
n
n
t =1
n
t =1
n
∑  't p '0 (t ) = (( ∑ t − e ) p0 (t ) + new p0 (t −  1 )) ,
(7)
d min −1
d min −1
∑  ' 't p ' '0 (t ) = (( ∑ t − ∑ ei ) p0 (t ) + ∑ newi p0 (t −  l ))
t =1
t =1
i =1
i =1
(8)
n
 dp0 (t )
=
−
t p0 (t );
∑
 dt
t =1

n
 dp1 (t ) n
= ∑ t p0 (t ) − (( ∑ t − e +  ) p1 (t );

t =1
t =1
 dt


d min −1
d min
n
n
 dpl (t )
=
(

−

)
p
(
t
)
−
(

−
∑
∑
∑
∑ ei +  ) p l (t );

t
ei l −1
t
dt
t =1
i =1
t =1
i =1

 dp (t )
d min
n
 DL = ( ∑ t − ∑ ei ) pl (t );
 dt
t =1
i =1

n
 dp '0 (t )
=

p
(
t
)
−
 't p'0 (t );
∑

1
dt
t =1

 dp ' (t ) n
n
 1 = ∑  't p '0 (t ) − ( ∑  't −  'e +  ) p '1 (t );
 dt
t =1
t =1


d min
n
 dp ' DL (t )
=
(

'
−
∑
∑  'ei ) p 'l (t );

t
dt
t =1
i =1

(9)
 dp ' ' (t )
n
0

= p l (t ) − ∑  ' 't p ' '0 (t );
 dt
t =1



где p0 , p1... p DL , p0 '... p DL ' , p0 ' '... p DL ' ' ... - предельные вероятности состояний
утраты накопителей, e - интенсивность выхода из строя накопителя, new интенсивность отказа новоприбывшего узла,  - интенсивность реконструкции
содержимого утраченных накопителей, 1... l ... - момент времени выхода из
строя накопителя, l = d min − 1 - предельное число накопителей, единовременно
находящихся в неисправном состоянии, при которых возможна реконструкция.
11
В третьей главе описываются концептуальные основы построения
регенерационных кодов.
За счет конструктивных особенностей регенерационного кода
восстановление содержимого утраченного узла хранения данных возможно при
сборе только части фрагментов, размещенных в памяти всех оставшихся УХД.
Традиционно для осуществления данного подхода используются коды РС
с перемежением между словами. Исходный информационный массив D
размера M разделяется на множество Dc = {d | d ∈ D, D = d1 || d 2 ... || d c ,}
фрагментов, размера  = M / c . Формирование исходного кодового слова
осуществляется путем формирования k 2 подмножеств D'i , j = {d '| d ' ⊆ Dc } ,
включающего в себя k1 фрагментов, и образующего исходные подслова кода.
Полученные в результате подслова подвергаются кодированию с
использованием кода РС (n, k1 , d ) , при этом каждый символ избыточности для
каждого кодового подслова формируется на основе информационных символов
из k 2 разных исходных подслов. В УХД записываются одноименные символы
из разных кодовых подслов. В результате формируется кодовое слово-массив
(n ⋅ k 2 , k1 ⋅ k 2 , d min , M ,  ,  min ) , создающее при восстановлении содержимого
одного утраченного накопителя нагрузку  min , вычисляемую как:
(n − 1) , приk 2 < n − 1;
(10)
 min = K = 
(
k
+

−
1
)

,
приk
≥
n
−
1
.

2
Недостатком данного подхода является относительная сложность
реализации устройства кодирования, обусловленная необходимостью
проведения операций над конечными полями.
Предлагается реализация метода регенерационного кодирования на
основе применения произведения кодов с проверкой четности с регулярным
смещением проверочного символа хранилищ в иное УХД, относительно
проверяемого.
Предлагаемый подход предполагает формирование и хранение в памяти
накопителей двух контрольных сумм. Одна из них размещается в памяти
отдельного хранилища. Вторая контрольная сумма размещается в каждом из
хранилищ, как в информационных, так и к избыточном. Источник и
потребитель данных, передает исходный массив данных в контроллер массива
УХД.
Для осуществления организации хранения исходный массив данных
разделяется контроллером на k1 * k2 фрагментов одинакового размера,
размещаемых в зоны УХД информационных данных таким образом, что в
каждом из них расположено k 2 фрагментов, размещенных в зонах,
объединенных в группы. В случае если информационный массив делится на
число фрагментов меньше k1 * k2 , оставшиеся заполняются значениями ноль. В
ином случае, если информационный массив делится на число фрагментов
больше k1 * k2 , он разделяется на несколько слов, обрабатываемых по
12
отдельности. Последовательность зон с одинаковыми номерами, но
находящихся на разных УХД, образует линию проверки на четность.
Формирование избыточности, размещаемом в зонах отдельного УХД,
производится с использованием выражения:
k1
ri = ∑ d j ,i (mod 2) ,
(11)
j =1
где i = 1,..., k 2 - номера зон в каждом из УХД, j – номер информационного
n
УХД, d i, j – символы содержащиеся в зоне номер i УХД j , ∑ x(mod 2) –
1
сумма элементов по модулю 2.
Формирование избыточности, размещаемом в отдельной линии всех УХД,
производится с использованием выражения:
k2

q
=
 D1 ∑ ri (mod 2);
i =1

k2

(12)
q Dj = ∑ d Dj , i (mod 2);
i
=
1


k2
q R = ∑ d k1, j (mod 2),

i =1
где i = 1,..., k 2 - номера фрагментов в каждом из УХД, j = 2,..., k1 – номер
информационного УХД, d j ,i – символы содержащиеся в зоне номер i УХД j ,
ri – фрагмент номер i устройства хранения избыточных данных.
Визуализация описанного способа представлена на рисунке 4.
Рисунок 4. Схема организации произведения кодов с проверкой четности с
регулярным смещением проверочного символа.
13
В случае возникновения события утраты УХД содержимое зоны
утраченного УХД считается стертым. Массив УХД становится безызбыточным
до введения в массив новоприбывшего накопителя. Операции чтения данных
осуществляется с проведением операции декодирования.
Восстановление содержимого утраченного устройства хранения
информационных данных производится путем вычисления обратных
контрольных сумм d 'i, утр для всех, кроме одного информационного фрагмента,
с использованием выражения
k1−1
d 'i = ( ∑ d j ,i (mod 2)) ⊕ ri
j =1
(13)
Последний фрагмент утраченного множества восстанавливается с
использованием соответствующей контрольной суммы q утр на основе
выражения
k 2 −1
d 'k 2 = ( ∑ d ' j (mod 2)) ⊕ q утр
(14)
j
Формирование избыточности, размещаемой в отдельном хранилище,
производится с использованием выражения
k1
ri = ∑ d j , i (mod 2) ,
j =1
(15)
где i = 1,..., k 2 - номера фрагментов в каждом из хранилищ, j – номер
информационного хранилища, d i, j – информационный фрагмент номер i
n
хранилища j , ∑ x(mod 2) – сумма элементов по модулю 2.
1
Объем генерируемого трафика при восстановлении содержимого одного
устройства может быть вычислен как:
(16)
 = (k1 (k 2 − 1) + 2)l ,
где k1 – число хранилищ, k 2 – число фрагментов входящих в один страйп, l –
размер одного фрагмента.
При условии k1 = k 2 скорость кода будет сопоставима с таковой в
системах на базе RAID-6, при этом ожидается сокращение объема
передаваемого трафика при восстановлении данных до 30%.
В четвертой главе дано описание подхода к организации локальнодекодируемых кодов.
Если дан код C – линейный блоковый (n, k , d ) код, то при кодировании
информационного полинома
vinf ∈ Fqk
с использованием данного кода
получают кодовое слово
C (vinf ) = (c1vinf , c2 vinf ,, cn vinf ) ∈ Fqn .
14
(17)
Степень локальности Loc (ci ) символа ci ∈ C - это наименьшее целое число
r , для которого существует R ⊆ C мощности r , такое, что
(18)
ci = ∑  j c j .
j∈R
Полная локальность кода в этом случае будет определяться как
Loc(C ) = max i∈[n ] Loc(ci ).
(19)
Из выражения (19) очевидно, что при реконструкции символов кода,
обладающие наименьшей локальностью, требуется передача наименьшего
числа других символов.
Предлагается реализация локальных кодов на основе многомерного
произведения кодов с проверкой четности. Данный подход базируется на идее
формирования кодового слова с одной контрольной суммой, вычисляемой для
k1 фрагментов исходного слова как:
k1
R = ∑ Di (mod 2) ,
i =1
(20)
где ∑ x(mod 2) – сумма по модулю 2, R - значение контрольной суммы
кодового слова, Di - информационный фрагмент исходного массива данных,
i = 1,..., k1 - номер фрагмента массива.
Для обеспечения повышенной надежности СХД k 2 кодовых слов,
полученных на первом этапе, объединяются и для них формируются
дополнительные k1 + 1 контрольных сумм, как
k2
Qi = ∑ Di, j (mod 2) ,
j =1
(21)
где Qi - значение i -й контрольной суммы i = 1,..., k 1 + 1 , j = 1,..., k 2 - номер
кодового слова, полученного на первом этапе.
Повышение надежности кода при масштабировании достигается путем
перехода к конструкциям большей размерности. Геометрическое представление
кодовых конструкций размерности 2D и 3D представлены на рисунке 5.
Рисунок 5. Кодовые конструкции размерности 2D и 3D
15
С учетом того, что минимальное кодовое расстояние кода с проверкой на
четность d min = 2 , кодовое расстояние получаемого кода может быть
вычислена как:
D
d 'min = ∏ d min i = 2 D ,
i =1
(22)
где D – принятая размерность кода.
Из выражения (19) видно, что для многомерных произведений кодов с
проверкой четности локальность будет вычисляться как:
(23)
Loc (C ) = min(k1...k D ) ,
Полученная конструкция позволяет реконструировать содержимое
утраченного хранилища, при этом требуется передача не более чем k1
фрагментов кода. Таким образом, применение предложенного кода позволяет
снизить нагрузку на сеть передачи данных до 50% в сравнении с системами на
базе кодов РС.
Важной особенностью данной разновидности кодов является их
уязвимость к структурируемым ошибкам. Данная особенность заключается в
том, что при возникновении e = d min стираний, код не может их исправить
тогда и только тогда, когда они дислоцируются в вершинах многомерных
параллелепипедов размерности кода. Таким образом, данный код способен
восстанавливать целостность исходного массива данных в том числе при
выходе из строя e ≥ d min узлов, за исключением некоторых случаев
группировки утраченных УХД с дислокацией в вершинах многомерного
параллелепипеда размерности кода, а также случаев e >> d min . Общее число
запрещенных комбинаций стираний, формирующих обозначенные структуры,
может быть вычислено с использованием выражения
(24)
N = ∑ (k1 − t1 )(k 2 − t1 )...(k n − t n ) ,
t1 ,t 2 ,...t n
где k1 , k 2 ...k n – размер многомерного кодового куба по соответствующим
измерениям, t1 = [1, k1 − 1] , t 2 = [1, k 2 − 1] , t n = [1, k n − 1] .
Из выражения (4) путем замены биноминального коэффициента на число
сочетаний, вычисляемого по (24), получаем выражение для определения
вероятности единовременного отказа распределенной системы на базе
многомерного произведения кодов с проверкой четности:
P ' DL = NP d min Q n − d min .
(25)
Из
выражения (25)
видно, что
вероятность
возникновения
группирующихся ошибок на порядок ниже таковой для ошибок, возникающих
16
случайным образом. Из этого следует, что утрата данных, содержащихся в
памяти систем, организованных на базе многомерного произведения кодов с
проверкой четности, до 10 раз ниже таковой у систем, базирующихся на кодах,
уязвимых к случайно группирующимся ошибкам. Зависимость вероятности
утраты работоспособности при всех возможных событиях и в случае
группировки представлена на рисунке 6.
Рисунок 6. Зависимость вероятности отказа системы от времени
Для получения дополнительного выигрыша с точки зрения нагрузки на
сеть передачи данных возможно комплексное использование предложенного
локально-декодируемого кода и регенерационных кодов для применения в
локальных группах хранилищ.
Из особенностей построения кодов с максимальным расстоянием
вытекает невозможность организации истинно-локальных кодов на их базе. Для
снижения нагрузки на сеть передачи данных, возникающей в процессе
восстановления содержимого утраченных накопителей, предлагается
организация квазилокального декодирования МДР-кода. Данное решение
базируется на идее применения перестановочного декодирования МДР-кодов с
формированием максимального числа стираний в кодовом слове.
Важнейшим свойством МДР-кодов является максимальное соотношение
кодового расстояния и скорости кода d min = n − k + 1 . Из этого следует, что в
случает утраты менее d min − 1 УХД, требуется и достаточна передача
n − d min + 1 любых из оставшихся символов, при этом все символы, не
принимающие участия в реконструкции, считаются стертыми. При
формировании максимального числа стираний на длине кодового слова всегда
приходят к условию вида
∆
Ps ∑ Pст Pош +
i =0
d
∑ Pош > PC s ,
(26)
i = ∆ +1
где Pош – вероятность появления ошибок при регистрации в комбинации i
стираний, а Pст – вероятность появления ошибок в этой же кодовой
комбинации, PC s – вероятность ошибочного декодирования комбинации в
17
условиях, когда на длине такой комбинации формируется всегда константное
число стираний, ∆ – символизирует произвольное число стираний на длине
декодируемого вектора. Следовательно, P∆s > PCs . В случае предельных
значений i необходимо выполнение условия: в отобранную часть символов
для формирования процедуры ПД не должно попасть ни одного фрагмента,
содержащего скрытую ошибку, что достаточно просто достигается при
выявлении поврежденного накопителя данных.
В соответствии с классическим алгоритмом для описания ошибок
используются многочлен локаторов ошибок
n−k
L( x) = ∏ (1 − xX i ) = Ln − k x n − k + Ln − k −1 x n − k −1 +  + L1 x + L0 ,
(27)
i =1
имеющий корни X i−1 , i = 1,  , n − k , взаимные к локаторам ошибок. Причем
величина при ПД всегда остается постоянной. Также необходимо знать
многочлен значений ошибок T (x)
T ( x) = S ( x) L( x)(mod x 2t ) ,
где
2t
2t n − k
j =1
j =1 i =1
(28)
S ( x ) = ∑ S j x j = ∑ ∑ Yi X i j x j – синдромный многочлен бесконечной
степени, для которого известны только
n−k
2t коэффициентов
( )
для поступившей
комбинации кода РС. Здесь S j = ∑ Yi X i j = e  j – элемент синдрома,  j –
i =1
корень порождающего многочлена кода РС. Значение
требуется
S (x)
n−k
вычислять для каждой кодовой комбинации, но
L ′( x) = − ∑ X i ∏ (1 − xX j ) .
i =1
j ≠i
Тогда для l -й позиции получают
L ′( X l−1 ) = − X l ∏ (1 − X j X l−1 ) .
(29)
j ≠l
С учетом последнего выражения Yl значение ошибки на позиции
l принимает вид
T ( X l−1 )
Yl =
.
(30)
L ′( X l−1 )
При восстановлении данных утраченного хранилища значение l всегда
имеет единственное значение, что существенно упрощает вычисление именно
l -го разряда комбинации.
В диссертационном исследовании решены поставленные задачи и
получены следующие основные результаты:
1. Приведен анализ существующих подходов к организации СХД с
гарантированной надежностью. Показана необходимость применения в данной
18
предметной области новых подходов, основанных на методах избыточного
кодирования.
2. Разработан и предложен метод регенерационного кодирования данных,
основанный на применении произведений кодов с проверкой на четность со
смещением, позволяющий сократить объем передаваемого трафика,
генерируемого в процессе восстановления содержимого одного утраченного
УХД до 30% в сравнении с системами без дополнительного сокращения
нагрузки.
3. Получен новый метод организации локально декодируемого кода на
базе многомерного произведений кодов с проверкой на четность, позволяющий
локализовать одну из групп УХД, объединенных одним кодовым словом, за
счет чего снизить внутрисетевую нагрузку восстановления в объеме одного
УХД по сравнению с известной СХД на базе произведения укороченных кодов
РС.
4. Предложенный метод организации локально декодируемого кода на базе
многомерного произведения кодов с проверкой на четность позволяет снизить
вероятность событий утраты данных, размещенных в СХД до одного порядка,
по сравнению с системой, не учитывающей природу группирования ошибок.
5. Предложен подход к организации квазилокально декодируемых кодов
на базе перестановочного декодирования МДР-кодов, позволяющих снизить
внутрисетевую нагрузку до 50% по сравнению с нагрузкой, возникающей при
традиционном восстановлении данных, при относительной скорости кода до 0,5
за счет топологической локализации избыточных символов.
6. Предложена аналитическая модель оценки вероятности возникновения
событий выхода из строя критического числа УХД.
Дальнейшие перспективы исследования видятся в развитии аппарата
локально-декодируемых кодов с дополнением его механизмами когнитивного
распределения ресурсов памяти УХД, связанных одной сетевой
инфраструктурой. Достижение поставленной цели оптимизации внутрисетевой
нагрузки восстановления требует решения задач раскраски графов и
эффективного замощения пространства.
ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ:
Список трудов, опубликованных в изданиях, рекомендованных ВАК
1. Климов Р.В. Методы снижения внутрисетевого трафика в процедуре
восстановления данных/ Р.В. Климов // Радиотехника №9 - 2016 г. - 44-47
2 Гладких А.А. Методы снижения внутрисетевой нагрузки в
распределенных системах хранения / А.А. Гладких, Р.В. Климов, И.А. Сорокин
// Автоматизация процессов управления. 2015. № 3 (41). С. 34-40.
3. Климов Р.В. Модель формирования индексов мягких решений символов
на основе модификации параметров канала со стираниями / Р.В. Климов,
Д.Н.Солодовникова / Радиотехника. 2014. № 11. С. 90-93.
19
4. Гладких А.А. Численное моделирование обобщенной процедуры
формирования индексов мягких решений / А.А. Гладких, Р.В. Климов //
Инфокоммуникационные технологии. 2013. Т. 11. № 2. С. 22-28.
5. Ганин Д.В. Особенности моделирования надежности распределенных
систем хранения данных / Д.В. Ганин, Р.В. Климов // Вестник НГИЭИ. 2017. №
7 (74). С. 18-25.
6. Климов Р.В. Осуществление регенерационного кодирования на базе
кодов-произведений с простой проверкой на четность / Р.В. Климов // Вестник
НГИЭИ. 2018. № 3 (82). С. 28-37.
Список патентов
7. Адаптивный кодер гиперкода размерности 3D. : патент №2480918 Рос.
Федерация: МПК H04L 1/16 (2006.01) H03M 13/00 (2006.01)/ Гладких А.А.,
Капустин Д.А., Климов Р.В., Солодовникова Д.Н.; заявитель и
патентообладатель ФГБОУ ВПО УлГТУ (RU) - № 2011146949/08 заявл.
18.11.2011; опубл. 27.04.2013 Бюл. № 12.
Список трудов, опубликованных в других изданиях
8. Гладких А.А. Методы эффективного декодирования избыточных кодов и
их приложения / А.А. Гладких, Р.В. Климов, Н.Ю. Чилихин // Ульяновск:
УлГТУ, 2016. - 258 с.
9. Климов Р.В. Исследование процесса формирования индексов мягких
решений со сниженным числом ложных стираний / Р.В. Климов // REDS:
Телекоммуникационные устройства и системы. 2014. Т. 4. № 2. С. 101-105.
10. Климов Р.В. Совместное применение сетевого и помехоустойчивого
кодирования в системах распределенного хранения данных / Р.В. Климов //
Современные проблемы проектирования, производства и эксплуатации
радиотехнических систем. 2014. № 1 (9). С. 82-85.
11. Климов Р.В. Применение комплекса сетевого и помехоустойчивого
кодирования в системах распределенного хранения / Р.В. Климов // В сборнике:
Проблемы техники и технологий телекоммуникаций ПТиТТ-2014; Оптические
технологии в телекоммуникациях ОТТ-2014 Материалы Международных
научно-технических конференций. 2014. С. 105-107.
12. Климов Р.В. Применение дополненного аппарата регенерационного
кодирования для оптимизации внутрисетевого трафика / Р.В. Климов, Н.А.
Пчелин, Г.М. Тамразян //: REDS Телекоммуникационные устройства и
системы. 2015. Т. 5. № 1. С. 115-118.
13. Климов Р.В. Обзор программных методов обеспечения надежности
хранения информации в распределенных системах хранения информации / Р.В.
Климов // Современные проблемы проектирования, производства и
эксплуатации радиотехнических систем. 2015. № 1-2 (9). С. 148-150.
14. Гладких А.А. Унификация процедуры обработки данных в
информационно-управляющих комплексах на базе полярных кодов / А.А.
Гладких, Р.В. Климов, Н.Ю. Чилихин // В сборнике: Радиолокация, навигация,
связь XХI Международная научно-техническая конференция. 2015. С. 10211031.
20
15. Климов Р.В. Оптимизация трафика восстановления узлов
распределенных систем хранения данных / Р.В. Климов, Н.Ю. Чилихин // В
сборнике: радиолокация, навигация, связь XXII Международная научнотехническая конференция. Воронеж, 2016. С. 671-681.
16. Гладких А.А. / Метод формирования индексов мягких решений в
системе с квадратурно-амплитудной модуляцией // А.А. Гладких, Р. В. Климов,
И.С. Линьков // DSPA-2013. Международная конференция Цифровая обработка
сигналов и ее применение. 2013.
17. Климов Р.В. / Разработка процедуры формирования индексов мягких
решений принятых символов с расширенной зоной стираний / Р.В. Климов //
16-я Международная конференция Цифровая обработка сигналов и ее
применение. 2014.
18. Климов Р.В. / Обобщенная процедура сокращения внутрисетевого
трафика в системах распределенного хранения на основе регенерационных
кодов / Р.В. Климов // 17-я Международная конференция Цифровая обработка
сигналов и ее применение. 2015.
19. Климов Р.В. Модель надежности систем хранения данных в условиях
утраты и восстановления хранилищ / Р.В. Климов // Современные проблемы
проектирования, производства и эксплуатации радиотехнических систем. 2017.
№ 1-2 (10). С. 195-198.
20. Климов Р.В. Особенности моделирования процессов отказов устройств
хранения в распределенных системах хранения данных / Р.В. Климов, М.С.
Соловьева // В сборнике: радиолокация, навигация, связь XXII Международная
научно-техническая конференция. Воронеж, 2017. С. 179-184.
21. Климов Р.В. Методы оценки надежности систем хранения данных /
Р.В. Климов // материалы XVIII Международной научно-технической
конференции. Казань, 20 –24 ноября 2017 года. – Казань: КНИТУ-КАИ, 2017. –
Т. 1. – С. 219 -220.
22. Климов Р.В. Подход к модификации модели оценки надежности
распределенных систем хранения данных / Р.В. Климов // материалы XVII
Международной научно-технической конференции. 22 –24 ноября 2016 года. –
Самара: ПГУТИ 2016. – Т. 1. – С. 199 -200.
21
Климов Роман Владимирович
ИССЛЕДОВАНИЕ МЕТОДОВ ОПТИМИЗАЦИИ НАГРУЗКИ
ВОССТАНОВЛЕНИЯ РАСПРЕДЕЛЕННЫХ СИСТЕМ ХРАНЕНИЯ
ДАННЫХ НА БАЗЕ КОРРЕКТИРУЮЩИХ КОДОВ
Подписано в печать 02. 07.2018. Формат 60×84/16.
Усл. печ. л. 1,00. Тираж 100 экз. Заказ. №542
ИПК «Венец» УлГТУ, 432027, г. Ульяновск, Северный Венец, 32
22
1/--страниц
Пожаловаться на содержимое документа