Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля

Скачать 59.23 Kb.

Название	Разработка модуля вычисления синдромов и восстановления утраченных дисков в raid-массиве с использованием арифметики поля
Тип	Документы

rykovodstvo.ru > Руководство эксплуатация > Документы

Разработка модуля вычисления синдромов
и восстановления утраченных дисков в RAID-массиве
с использованием арифметики поля

Быкова Ю.С., студентка кафедры системного программирования СПбГУ,
yulya_byk@mail.ru
Веселков И.Д., студент кафедры системного программирования СПбГУ,
veselkov.id@gmail.com

Научный руководитель:
Платонов С. М., руководитель исследовательской лаборатории RAIDIX,
platonov.s@raidixstorage.com

Введение.

В данной работе рассматривается подход к вычислениям в RAID с использованием арифметики конечных полей

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

Основные термины и технологии.

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

. Для организации вычислений буфера разбиваются на блоки (Blocks) одинакового размера. Размер блока является делителем размера буфера. Количество буферов

равно количеству дисков данных в массиве. В рамках одного страйпа буфера могут называться дисками. Для обеспечения отказоустойчивости в страйп вводятся дополнительные буфера (диски), предназначенные для хранения синдромов. Размер этих дополнительных буферов (дисков) равен размеру буферов (дисков) данных.

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

Цель данной работы.

С помощью кода Рида-Соломона эффективно реализовать вычисление синдромов и восстановление утраченных дисков с элементами в поле

, а также сравнить производительность с полями размера

.
Данная технология RAID при работе с элементами из поля

имеет несколько преимуществ:

* Эффективность операции умножения на x по сравнению с непараллельной реализацией
За счет эффективной реализации вычислений и использованию технологий SSE и AVX при одном умножении количество инструкций совпадает с количеством единиц в двоичном представлении образующего многочлена поля. В нашем случае, на умножение на x большого числа элементов расходуется всего три процессорных инструкции.
* Увеличение максимального количества дисков по сравнению с полем

.

Больший размер элемента поля позволяет работать с огромным количеством дисков, около 1.16*10^77, что примерно равно 0,12 процентам от количества всех атомов в обозримой Вселенной. Это дает нам возможность полностью пренебречь их количеством.

* Оптимальное использование процессорного кэша
Цифра 256 была выбрана не случайно. Длина страйпа имеет вполне определенное значение в 4 Кбайта. Если мы разобьем его на переменные по 16 байт, чтобы можно было их обрабатывать с помощью технологии SSE, то получим как раз 256 переменных. Будем представлять их совокупность как многочлен поля

.

Для вычисления контрольных сумм в RAID6 используются формулы вида

, где

это произвольнй элемент поля.

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

ней использовались только операции умножения на примитивный элемент поля и сложения.

Умножение на произвольный элемент поля так же сводится через факторизацию

к умножения на х и сложениям в зависимости от битов элемента на который

умножаешь

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

Проделанная работа и инструментарий.
Был написан генератор кода для создания отдельных функций для каждого количества дисков (от 5 до 128) с последующим объединением их в массив. Это вызвано тем, что условные переходы понижают производительность по сравнению с линейным. Генератор позволил автоматизировать написание большого количества похожих функций.

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

Результаты.

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

. [5]
Полученный результат.
Ниже приведены результаты замеров работы функций (Диаграмма 1 и Диаграмма 2) для 48, 78, 108 и 128 дисков. Для сравнения приведены результаты замеров работы тех же функций из модулей, работающих с полями

.

Диаграмма 1: Расчет двух синдромов
Диаграмма 2: Восстановление двух дисков.
Используемая конфигурация тестовой машины:

ОС: Debian 7.0
Тип ОС: х64
CPU: Intel® Xeon(R) CPU E5-2620 0 @ 2.00GHz × 18
Оперативная память: 39.4 Гб

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

Также планируется рассмотреть работу функций в полях GF(

) и GF(

).

Литература.

Питерсон У., Уэлдон Э. "Коды, исправляющие ошибки"
H. Peter Anvin "The mathematics of RAID-6"
Сайт Утешева Алексея Юрьевича http://pmpu.ru/vf4/users/au/index
Richard Gerber, Aart J.C. Bik, Kevin B. Smith, Xinmin Tian “The Software Optimization Cookbook High-Performance Recipes for IA-32 Platform” Second Edition.
Gadiel Seroussi "Table of Low-Weight Binary Irreducible Polynomials"

Похожие:

	Разработка модуля вычисления синдромов и восстановления утраченных... Демьяненко И. И., студент кафедры системного программирования спбГУ, dii6@yandex ru		Разработка по для вычисления Федеральное государственное бюджетное образовательное учреждение высшего образования
	Инструкция по подготовке респондентом статистической отчетности с... Порядок действий сотрудника организации (Респондента), отчитывающейся в территориальный орган Федеральной службы государственной...		В тексте дипломной работы представлена разработка модуля генерирующего... В тексте дипломной работы представлена разработка модуля генерирующего qr-код и разработка информационно – справочной системы выставки...
	Конкурсная документация для проведения открытого одноэтапного конкурса... «Гольф-поля на 18 лунок (поля №№01-18 + тренировочное поле), инв. Н0000220106681» на территории филиала ГлавУпдк при мид россии мзк...		1. 2 Эволюционные вычисления Генетический алгоритм — это алгоритм, который позволяет найти удовлетворительное решение к аналитически неразрешимым или сложнорешаемым...
	Программа профессионального модуля пм. 02 Разработка, внедрение и адаптация Программа профессионального модуля составлена на основе Федерального государственного образовательного стандарта по профессии спо...		Задачи кабинета физики: Обеспечение качественного выполнения программы по физике Организация фронтальной учебной деятельности с использованием мультимедиапроектора и компакт-дисков учебного назначения, а также...
	С разделением на разделы и возможностью планирования Приводятся две формы программирования. Одна из них содержит все поля программирования, а другая содержит поля специфичных разделов....		Кафедра системного программирования Разработка технологии взаимодействия... Разработка технологии взаимодействия гетерогенных систем с использованием метапрограммирования
	Инструкция по подготовке респондентом статистической отчетности с... Инструкция по подготовке респондентом статистической отчетности с использованием off-line модуля подготовки отчетов		Антисептики Обработки опер поля, рук хирургов, обозначения опер поля, перед катетеризацией и пункцией суставов
	Инструкция по эксплуатации Наденьте необходимое количество дисков на втулку грифа симметрично с двух сторон. Закрепите положение дисков, для этого наденьте...		Облачные вычисления. Как создать облако от Oracle Термин “облачные... Почти каждую неделю появляются новые статьи, книги, презентации об облачных вычислениях – новой сервисной модели предоставления вычислительных...
	Гнц РФ ао «Концерн «цнии «Электроприбор», с-петербург Разработка цифровой части asic Разработка цифровой части asic с использованием программных продуктов компании Cadence		Разработка элементарного индуктора для системы магнитотерапии локального... Ключевые слова: динамическое магнитное поле, магнитотерапия, система индукторов, индуктор-электромагнит, магнитная индукция, математическое...

Руководство, инструкция по применению

rykovodstvo.ru