научная статья по теме К ВОПРОСУ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ СОЗДАНИЯ КОНТРОЛЬНОЙ ТОЧКИ ДЛЯ ВЫЧИСЛИТЕЛЬНОГО ПРИЛОЖЕНИЯ, ОСНОВАННЫХ НА ПРИМЕНЕНИИ КОДА РИДА-СОЛОМОНА Математика

Текст научной статьи на тему «К ВОПРОСУ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ СОЗДАНИЯ КОНТРОЛЬНОЙ ТОЧКИ ДЛЯ ВЫЧИСЛИТЕЛЬНОГО ПРИЛОЖЕНИЯ, ОСНОВАННЫХ НА ПРИМЕНЕНИИ КОДА РИДА-СОЛОМОНА»

ПРОГРАММИРОВАНИЕ, 2008, Ml, с. 75-78

— ОПЕРАЦИОННЫЕ СИСТЕМЫ

УДК 681.3.06

К ВОПРОСУ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ АЛГОРИТМОВ СОЗДАНИЯ КОНТРОЛЬНОЙ точки ДЛЯ ВЫЧИСЛИТЕЛЬНОГО ПРИЛОЖЕНИЯ, ОСНОВАННЫХ НА ПРИМЕНЕНИИ КОДА РИДА-СОЛОМОНА

© 2008 г. А. В. Инюхин

Московский государственный университет им. М.В. Ломоносова, механико-математический факультет 119992 Москва, Воробьевы горы

E-mail: avi@imec.msu.ru Поступила в редакцию 01.06.2005 г.

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

1. ВВЕДЕНИЕ

Код Рида-Соломона является эффективным средством восстановления информации о состоянии вычислительного процесса при многократных сбоях. Простота реализации и минимальные накладные расходы на хранение кода коррекции делают его одним из наиболее привлекательных способов восстановления вычислительного процесса при сбоях из-за программных и аппаратных ошибок.

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

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

ца в исправленной версии статьи [3] пригодна для построения кода Рида-Соломона, однако не обладает рядом других свойств и не удовлетворяет приведенным в [2] оценкам количества операций.

Цель настоящей публикации - отметить упомянутые неточности на исследуемом направлении и предложить способы их устранения.

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

2. ИСПОЛЬЗОВАНИЕ КОДА РИДА-СОЛОМОНА ДЛЯ ОБЕСПЕЧЕНИЯ ВОЗМОЖНОСТИ ВОССТАНОВЛЕНИЯ ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА ПРИ МНОГОКРАТНЫХ СБОЯХ

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

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

Различные подходы к решению сформулированной задачи рассмотрены в [1]. В контексте данной работы интерес представляют только два из рассмотренных в публикации методов: подсчет контрольных сумм на основе кода Рида-Соломона и на основе операции "исключающее или" .

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

Общим подходом к решению задачи является вычисление контрольных сумм с помощью кода Рида-Соломона, которые представляют собой линейные комбинации векторов данных над некоторым конечным полем К, где N + М ^ ^ \К*\ = \К\ — 1, К* - мультипликативная подгруппа К.

Пусть 6 К, где 1 ^ г ^ N - данные, а Cj £ К, где 1 ^ ] М, - контрольные суммы. Тогда должны существовать коэффициенты такие, что выполнено соотношение

N

С3 = fj,i(^i■ г = 1

(1)

В матричном виде, обозначая Ьп;т(К) группу линейных отображений из Кп в Кт, приведенные выражения можно записать в виде:

^ = ш е о =(<*!,..., е кн,

с = (С1,...,СМ)Т е км,F_D = с.

Определим матрицу А £ следую-

щим образом:

А =

I

/ 1

О

/1,1

0 \

1

Л, N

(2)

V /м, 1 • • • /м,ЛГ /

где I - матрица тождественного преобразования. Тогда

АВ =

I

Б =

Ю

FJD

В

С

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

кое, что Р((х1,.. .,хм+м)Т) = {х1,...,хм)т, о £ 5* (./V + М) - некоторая перестановка, а 11 а £ Ь^+м,н+м{К) ~ преобразование, задаваемое соотношением 11а ((жь..., ждг+м)Т) = = (ж^!),..., Ж(7(Лг+М))Т- Таким образом, выполнено следующее соотношение

.1а{{х1, • • • , ЖдГ+м)Т) = (Ж(т(1), • • • , Ха(М))Т

и информация Я для восстановления данных задается выражением

К — <Лт

Б

С

= .1а{АР) = {.1аА)Р.

Для возможности восстановления необходимо, чтобы было выполнено свойство

V£7 е ^(ЛГ + М) : 3(.1аА)

-1

(3)

а именно: чтобы существовало (/^А)-1, тогда И = {.]аА)~1 Я. Выражение ,7аА является набором из N строк матрицы А, следовательно, для возможности восстановления по любому набору из N элементов необходимо, чтобы каждый минор размера N матрицы А имел полный ранг. Это условие является необходимым и достаточным для возможности восстановления полного набора данных. Достаточность непосредственно следует из приведенных выше выкладок, необходимость доказывается от противного.

Введем класс линейных преобразований <3, обладающих свойством (3):

(2 = {Ае1М1М+м(К) : У<7 £ 5(ЛГ + М), 3(.^А)-1}.

Отметим, что этот класс непуст, так как ему принадлежит матрица В = Улг,лг+мУдг дг £ гДе

Уи^+М = / 1

О1 I1

\ (ЛГ+М-1)0 (ЛГ+М-1)1 ... (А^+М —/

Матрица В является матрицей Вандермонда У/у,Лг+М) приведенной а виду (2) с помощью элементарных преобразований столбцов. Она также совпадает с матрицей В, упоминавшейся в [3].

N-1

N-1

К ВОПРОСУ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ... СОЗДАНИЯ КОНТРОЛЬНОЙ ТОЧКИ 77

ВМ = (с^(/м, . . . , /1,дг, /1,1/1,1 , /1,1/2,1 > • • ч /1,1 /м,1))^(с11аё(Л,1 > • • ч Л,м))

1, .. . , /1,лг) . / .

(¿^(ЛдЛд , /1,1/2,1 > • • • > /1,1 /мд))^

/

Вм =

/ 1 о

Вм =

/1,1/1,1/1,1/1,1 /1,1/2,1/2,1/1,1

/1,1/1,1/1,2/1,2 /1,1/2,1/2,2/1,2

Вм =

/ 1 О

0

1

0

1

0

1 -1

1 /1,1/2,1 /2,2/1,2

/1,1/1,1/1,л/1,ДГ /1,1/2,1 /2, л/1,дг

V / д/м,1/^,1/1,1 Лд/м,1/^,2/1,2 • • • /1,1 /м, 1 /м,ТУ/1,дг /

О

0

1 1

/1,1/2,1/2,л/1, дг

-1

V 1 /1,1/мд/м,2Л,2 • • • /1д/мд/м,л/1> /

с-1

-1

с-1

Процесс построения матрицы Вм-

3. ПОСТРОЕНИЕ МАТРИЦЫ Таким образом, матрицу Ам можно предста-

С ДОПОЛНИТЕЛЬНЫМИ СВОЙСТВАМИ вить в виде:

Пусть матрица А 6 <5 имеет вид (2), а ее строка с номером А + 1 имеет вид (/1,1,..., /1,лг)> причем /1,3' ф 0, 1 ^ I N.

Определим Ам следующим соотношением

Ам = (с^(/м,.. .,/1,лг, 1, • •., 1))х

где diag(Al,..., Хп) - диагональная матрица с элементами Х\,..., Хп на диагонали, а

Ам =

/ 1 О

/

(Наесд-!1,...,/-^))

о \

/1,1/1,1

V /м, 1/1,1

1

/1,^/1,

-1

я

/м,л//

Получившаяся в результате матрица Ам также имеет вид (2) и обладает свойством (3) линейной независимости любого набора из А

строк (умножения на невырожденные диагональные матрицы справа и слева не меняют этого свойства), Ам £ аее А + 1-ая строка равна (1,...,1).

Далее, построим матрицу Вм £ <3, такую, что = 1 и /¿^ = 1. Процесс ее построения представлен на рисунке.

Матрица Вм, также как и Ам, имеет вид (2) и обладает свойством (3). Единичные коэффициенты в первой позиции строк с номерами N + 2,...,N + М могут позволить сократить сложность вычисления контрольных сумм по сравнению с матрицей Ам-

4. ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ

Для практического применения в качестве К используется поле Галуа СЕ(2ги), где т - разрядность машинного слова (чаще всего 8 или 16). В данном поле операция сложения совпадает с операцией "исключающее или", а значит, при использовании матриц Ам и Вм, построенных в предыдущем разделе, с\ из (1) совпадает с контрольной суммой,используемой в алгоритме 11АГО-4. Отметим, что в публикации [1] этот метод упоминается как 11АГО-5, однако, несмотря на общую схему вычисления контрольной суммы, 11АГО-5 предполагает чередование блоков данных, которое при создании контрольных точек производить затруднительно и нецелесообразно.

Таким образом, при использовании вышеуказанных матриц отсутствует необходимость независимого рассмотрения алгоритмов вычисления контрольной суммы с помощью операции "исключающее или" и кода Рида-Соломона, а также появляется возможность расширения существующей контрольной суммы, обеспечивающей восстановление при однократном сбое, до некоторого значения (Ат-\-М < 2Ш) без перевычисления.

В отличие от схем, полученных с помощью алгоритма 11АГО-6, основанного на использовании кода Рида-Соломона для реализации аппаратных контроллеров [4], представленный выше метод является несимметричным, то есть затраты на восстановление разных файлов контрольных сумм могут отличаться. Такая асимметрия обусловлена спецификой задачи управления фай-

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

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

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

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком