Содержание к диссертации
Введение
Глава 1 Аналитический обзор, классификация распределенных систем хранения данных 23
1.1 Анализ причин сбоев в распределенных системах хранения данных 26
1.2 Надежность вычислительных систем, распределенных систем хранения и ее количественные показатели 31
1.3 Алгебраические коды с обнаружением и исправлением ошибок 37
1.4 Основные модели модулярных вычислительных структур, используемые для разработки отказоустойчивых систем на основе системы остаточных классов 42
1.5 Краткая характеристика методов обнаружения, поиска и исправления ошибок 48
1.6 Постановка задачи исследования 56
1.7 Выводы по первой главе 59
Глава 2 Разработка распределенной системы хранения данных с повышенной отказоустойчивостью на основе системы остаточных классов 62
2.1 Разработка и анализ моделей хранения данных с обеспечением отказоустойчивости на основе регулируемого избыточного кодирования 62
2.2 Разработка численного метода выбора параметров избыточной системы остаточных классов для распределенного хранения данных 69
2.3 Разработка и модификация метода исправления ошибок, основанного на методе проекций с максимальным правдоподобием 73
2.4 Разработка численного метода расчета расстояния Хэмминга на основе приближенного метода и ранга числа для модификации метода проекций с максимальным правдоподобием 78
2.5 Разработка вероятностного подхода к оценке отказоустойчивости распределенных систем хранения данных 88
2.5.1 Разработка вероятностного подхода к оценке отказоустойчивости распределенных систем хранения данных на основе резервирования 88
2.5.2 Разработка базовой структуры распределенной системы хранения данных на основе избыточной системы остаточных классов 98
2.6 Выводы по второй главе 109
Глава 3 Разработка математических моделей и синтез базовых отказоустойчивых структур распределенных систем хранения данных 111
3.1 Разработка алгоритма и структурной схемы прямого преобразования данных в распределенных системах хранения 111
3.2 Разработка алгоритма и структурной схемы обратного преобразования данных в распределенных системах хранения 124
3.2.1 Разработка алгоритма и структурной схемы локализации ошибок и восстановления корректных данных на основе метода проекций 124
3.2.2 Разработка алгоритма и структурной схемы локализации ошибок и восстановления корректных данных на основе метода проекций с максимальным правдоподобием 140
3.3 Выводы по третьей главе 158
Глава 4 Экспериментальное исследование методов обеспечения отказоустойчивости, основанных на системе остаточных классов на базе программируемых логических интегральных схем архитектуры FPGA 160
4.1 Моделирование базовых вычислительных структур системы остаточных классов 160
4.2 Моделирование методов локализации ошибок и восстановления корректных данных на основе избыточной системы остаточных классов 165
4.3 Сравнительный анализ моделей распределенных систем хранения данных 175
4.4 Выводы по четвертой главе 182
Заключение 186
Обозначения и сокращения 192
Список литературы 194
Приложение 1 208
Приложение 2 216
Приложение 3 225
Приложение 4 237
Приложение 5 241
Приложение 6 245
Приложение 7 255
- Анализ причин сбоев в распределенных системах хранения данных
- Разработка и анализ моделей хранения данных с обеспечением отказоустойчивости на основе регулируемого избыточного кодирования
- Разработка алгоритма и структурной схемы локализации ошибок и восстановления корректных данных на основе метода проекций
- Сравнительный анализ моделей распределенных систем хранения данных
Анализ причин сбоев в распределенных системах хранения данных
Распределенное хранилище данных представляет собой систему с большим количеством запоминающих устройств, соединенных сетью, и инфраструктурой, обеспечивающей их функционирование. Увеличение размеров современных распределенных систем хранения, содержащих тысячи устройств хранения данных, приводит к увеличению частоты сбоев ее компонентов [96].
Основными причинами сбоев данных в распределенных системах хранения являются аппаратные, программные, сетевые сбои и сбои питания [86]. Vishwanath и Nagappan проанализировали надежность оборудования для крупной инфраструктуры распределенной системы хранения [97]. Как показано на рисунке 1.2, 78% всех сбоев сервера были связаны с жесткими дисками, 5% – с RAID-контроллерами (Rapid Array of Inexpensive Disk – RAID), 3% – с памятью, остальные 14% обусловлены другими факторами. Диски являются центральным элементом распределенных систем хранения [44] и наиболее распространенным компонентом отказа [70]. Поскольку распределенные системы строятся на обычных серверах и жестких дисках [64], они подвержены сбоям, которые могут поставить под угрозу работу приложений, зависящих от них. Разработчики распределенной системы хранения данных компании Google называют частые сбои работы компонентов системы одной из наиболее сложных проблем [65]. Например, в 2009 году Facebook временно потерял более 10% сохраненных фотографий из-за сбоя жестких дисков [67]. При отказе диска, хранимые на нем данные становятся недоступны, что неприемлемо в современных условиях.
Как показано на рисунке 1.3, сбои могут привести к временной или постоянной недоступности данных. Недоступность данных из-за перебоев в работе сети, сбоя узла (машины), перебоя в питании или автоматического процесса восстановления является временной и не приводит к постоянной потере данных [86]. Недоступность данных из-за сбоя жесткого диска или повреждения данных приводит к постоянной потере данных.
Надежность данных включает в себя максимальную целостность и достоверность данных. Повышение достоверности снижает влияние сбоев, приводящих к постоянной недоступности данных; а повышение целостности снижает влияние сбоев, приводящих к временной недоступности данных.
Как показано на рисунке 1.4, в облачных дата-центрах используются различные механизмы повышения надежности системы хранения. Влияние аппаратных сбоев снижается за счет использования RAID-массивов, взаимозаменяемых дисков и кодов исправления ошибок с памятью (Error Correction Code Memory – ECC RAM). RAID-массивы – это логическая единица, состоящая из нескольких дисков, в которых хранятся данные с чередованием, зеркалированием и проверкой четности. Взаимозаменяемые диски позволяют администраторам обмениваться дисками, которые выходят из строя или сбои которых прогнозируются, пока система остается в рабочем режиме. ECC RAM используются для обнаружения и исправления однобитовых ошибок, связывая бит четности с каждым двоичным кодом. При отказах сети и перебоях в подаче электроэнергии используются резервная сеть питания соответственно.
В случае сбоев, приводящих к временной недоступности данных, недоступные данные могут быть рассмотрены как потерянные. Тогда для восстановления доступа к ним можно применить методы борьбы со сбоями, приводящими к постоянной недоступности данных.
В общем виде структурная схема организации распределенного хранения представлена на рисунке 1.5.
Последствия любых сбоев, независимо от проблем их вызвавших, могут быть устранены с помощью различных методов введения избыточности данных [96]. Реализация блоков прямого и обратного преобразования данных (рис. 1.5) зависит от выбранных методов обеспечения отказоустойчивости. Коды стирания, репликация и отказоустойчивое разделение данных (Resilient Distributed Dataset – RDD) [102] являются наиболее важными методами обеспечения отказоустойчивости распределенных систем хранения данных.
Наиболее распространенными методами введения избыточности являются репликация [73] и коды стирания [69, 87]. Репликация – это простой механизм резервирования данных. Одни и те же данные копируются и хранятся в нескольких местах в системе хранения. Если запрошенные данные недоступны на одном диске, они подаются со следующего доступного диска [83]. Коды стирания являются более сложным механизмом введения избыточности данных. Наряду с исходными данными создаются и сохраняются данные о четности, так что если запрошенные данные недоступны, их можно восстановить из данных о четности. Расходы на хранение для кодов стирания намного меньше, чем для репликации, следовательно, это уменьшает потребность в оборудовании для хранения данных и обеспечивает значительную экономию затрат и энергии в центрах обработки данных [69]. Однако восстановление данных после сбоя связано с высокой стоимостью реконструкции и трафиком сети.
Повышение отказоустойчивости и снижение эксплуатационных расходов является основной причиной, по которой пользователи распределенных систем хранения заинтересованы в переходе к кодам стирания или отказоустойчивому разделению данных. Facebook увеличил эффективность хранения с 2.1 до 3.6, используя коды стирания, сэкономив при этом несколько петабайт [76]. Microsoft Azure сократил затраты на хранение с 3 до 1.33, используя коды стирания, что позволило снизить затраты более 50% [69].
Далее рассмотрим основные понятия и определения параметров надежности и основных ключевых показателей, определяющих надежность и отказоустойчивость вычислительных систем и систем хранения.
Разработка и анализ моделей хранения данных с обеспечением отказоустойчивости на основе регулируемого избыточного кодирования
В главе 1 рассмотрены различные принципы обеспечения надежности, отказоустойчивости и доступности, которые применяются при проектировании систем хранения и обработки данных. В связи с возрастанием объемов данных, которые необходимо хранить и обрабатывать в современных системах, особую роль приобретают принципы организации подобных систем на основе распределенной инфраструктуры. В данном случае, части системы могут находиться на различных компьютерах, связанных воедино высокоскоростной сетью. Иногда подобные системы могут быть распределены и географически, если это целесообразно с экономической точки зрения.
Это влечет необходимость разработки специальных моделей и методов, которые адаптированы под специфическую инфраструктуру распределенного центра обработки и хранения данных. В данном разделе исследуются вопросы выбора модели хранения данных, адаптированной для распределенной инфраструктуры и отвечающей вызовам, представленным в пункте 1.1. Проведенный анализ позволяет предложить новые модели хранения данных на основе разделения данных в системе остаточных классов. В данной главе рассматриваются различные подходы к моделированию систем хранения данных, предлагаются методы их анализа и производится анализ рассматриваемых и предлагаемых методов согласно критериям надежности, представленным в пункте 1.2. Если рассматривать общую схему функционирования систем распределенного хранения данных, то можно выделить несколько ключевых атрибутов, свойственных им. Методы хранения данных в каждом конкретном случае различаются, однако часть процедур необходимо обеспечивать при любой выбранной модели хранения данных. Выделим ключевые подсистемы системы распределенного хранения данных:
1. Подсистема разделения данных включает в себя алгоритмы и методы разделения подающейся на вход информации, представления ее в распределенной (возможно – избыточной) форме, пригодной для хранения на физически распределенных устройствах хранения данных.
2. Среда хранения данных состоит из пула носителей информации (жесткие диски, сервера), которые связаны в единую систему (возможно, логическую файловую систему), что определяет способы хранения и доступа к данным.
3. Подсистема восстановления данных предполагает обратное преобразование распределенной информации и может сочетать в себе некоторые из следующих механизмов:
a. Механизм сбора распределенных частей данных на основе хранящейся метаинформации о местах хранения распределенных данных и о доступности физических носителей.
b. Механизм обеспечения целостности данных, включающий оценку собранных данных на поврежденность и механизмы реагирования в случае обнаружения ошибок в блоках данных.
c. Механизм восстановления данных на основе полученных частей данных и информации о поврежденных блоках данных.
Подобная структура является обобщенной и предполагает различные способы обеспечения надежности хранения данных в такой форме. Каждая конкретная реализация может быть оценена по ряду критериев, включая описанные в главе 1:
- доступность данных, которая определятся вероятностью потери доступа к данным в ходе долгосрочного функционирования всей системы;
- избыточность хранения данных, которая может быть определена как отношение количества оборудования (измеряемое в условных единицах - денежный эквивалент или объем хранимых данных), необходимого для хранения исходного объема данных, к количеству оборудования, необходимого для обеспечения хранения исходной и избыточной информации;
- скорость сохранения данных и скорость доступа к данным, характеризуемая пропускной способностью каналов связи, по которым обеспечивается доступ к данным, и задержкой, вызываемой функционированием подсистем разделения и восстановления данных.
Оценка данных параметров важна и определят эффективность и надежность каждой конкретной системы. Каждый из критериев функционирования распределенных систем хранения данных определяет качество сервиса (Quality of Service, QoS) этой системы.
Подробное определение каждой из подсистем определяет конкретную систему хранения данных или принцип, на котором основывается семейство таких систем. Рассмотрим схему хранения данных, основанную на резервировании (рис. 2.1). Подсистема разделения данных предполагает копирование частей данных на распределенные носители. Принцип хранения данных подбирается таким образом, чтобы обеспечить максимально продолжительное хранение при условии выхода из строя части носителей. Подсистема восстановления данных сочетает в себе выбор одной из копий хранимых данных. В случае необходимости для обеспечения целостности данных может быть применен механизм, аналогичный механизму мажоритарного кодирования [8]. Такой подход активно используется на практике [65] и гарантирует высокую отказоустойчивость систем хранения данных, однако приводит к высокой избыточности [61, 83, 85], что является его главным недостатком. Безусловным плюсом такого подхода является простота организации и низкие накладные расходы на прямое и обратное преобразование.
Для снижения избыточности предлагается использование избыточной системы остаточных классов, введенной в пункте 1.4. На рисунке 2.2 представлена обобщенная модель распределенного хранения данных, основанная на представлении данных в ИСОК. Пусть подобрана некоторая система из n оснований СОК p1, p2,..., pk ,..., pn , в которой первые k оснований являются рабочими. Преобразование данных из позиционной системы счисления (ПСС) предполагает вычисление остатков от деления числового представления данных на основания избыточной СОК p1, p2,..., pk ,..., pn . Блок данных разделяется благодаря представлению в распределенной форме в виде остатков от деления на каждый из модулей введенной СОК. В связи с этим, схема хранения данных должна предусматривать распределенное хранение каждого из остатков на отдельном носителе независимо от остальных остатков того же самого числового блока данных. В свою очередь, процедура восстановления данных сочетает в себе процедуру определения и локализации ошибки в собранных из хранилища данных, что является основой отказоустойчивости рассматриваемой схемы. После локализации ошибки и ее исключения из кода СОК, полученное представление на основе некоторых безошибочных остатков p[,p 2,...,p к переводится одним из известных методов в позиционную форму.
Разработка алгоритма и структурной схемы локализации ошибок и восстановления корректных данных на основе метода проекций
Код избыточной СОК с к рабочими и п-к контрольными основаниями P1, …, pk, pk+1, …,Рп способен исправить а = — ошибок, согласно (1.7). Для локализации ошибок и восстановления корректных данных методом проекций достаточно рассчитать значения Сqn проекций и выбрать из них ту, которая меньше рабочего диапазона избыточной СОК. Восстановленные по выбранной проекции данные будут корректны. Однако, в зависимости от используемого подхода к вычислению значений проекций: метод ортогональных базисов, модифицированный метод перевода в ОПСС, КТО с дробными числами; схема локализации ошибок и восстановления корректных данных методом проекций будет изменяться.
Для локализации ошибок и восстановления корректных данных методом проекций с использованием КТО необходимо вычислить величину каждой из С проекций, используя метод ортогональных базисов. Вычисление проекций выполняется параллельно. Затем необходимо сравнить величину каждой из проекций с величиной рабочего диапазона Рк. Все сравнения так же выполняются параллельно. Проекция, величина которой окажется меньше рабочего диапазона и будет представлять собой корректные данные. На рисунке 3.7 изображена схема локализации ошибок и восстановления корректных данных методом проекций с использованием КТО (на примере двукратной ошибки q = 2). Логическая глубина схемы локализации ошибок и восстановления корректных данных методом проекций с использованием КТО равна
Схема локализации ошибки идентична для всех рассматриваемых методов: на входы подаются Г или 0 , в зависимости от результата сравнения конкретной проекции с величиной рабочего диапазона избыточной СОК, а на выход подается наибольший из номеров входов, на которые была подана единица. Схема локализации ошибки содержит Сqn -1 сравнений и максимум 2 операции присваивания, поэтому ее логическая глубина равна Сqn +1 операций: я(Лок.Ош.)=С+1.
Схема выбора корректной проекции содержит многовходовый мультиплексор: на входы подаются рассчитанные величины проекций, на управляющий вход - номер корректной проекции, на выход подается корректная проекция. Схема выбора корректной проекции содержит 1 сравнение, поэтому ее логическая глубина равна 1 операции:
Таким образом, логическая глубина схемы локализации ошибок и восстановления корректных данных методом проекций с использованием КТО (3.6) с учетом логической глубины ее подблоков равна:
Для локализации ошибок и восстановления корректных данных методом проекций с использованием ОПСС необходимо найти представление величин каждой из Сqn проекций в ОПСС, используя модифицированный перевод в ОПСС. Вычисление представления проекций в ОПСС выполняется параллельно. Затем необходимо сравнить старшие цифры ОПСС каждой из проекций с нулем. Все сравнения так же выполняются параллельно. Проекция, старшая цифра которой окажется равной нулю, и будет представлять собой корректные данные, представленные в ОПСС. После определения корректной проекции необходимо выполнить ее преобразование из ОПСС в позиционную систему счисления. На рисунке 3.9 изображена схема локализации ошибок и восстановления корректных данных методом проекций с использованием ОПСС (на примере двукратной ошибки q = 2). Логическая глубина схемы локализации ошибок и восстановления корректных данных методом проекций с использованием ОПСС равна:
Для вычисления представления проекций в ОПСС (рис. 3.10) необходимо каждый из (n – q) остатков умножить на соответствующие константы ОПСС заранее вычисленные для каждой из проекций. Все умножения выполняются параллельно. Далее необходимо сложить полученные значения произведений, соответствующие каждому из модулей проекции. Сложения, соответствующие разным модулям, выполняются параллельно. Далее, найденную сумму, соответствующую первому модулю, необходимо разделить на величину этого модуля, вычислив целую часть и остаток. Остаток будет равен цифре ОПСС по данному модулю, а целую часть от деления необходимо сложить с суммой соответствующей следующему модулю и т.д. для каждого из модулей кроме последнего. Для последнего модуля нет необходимости искать целую часть от деления, поэтому вместо деления используется операция нахождения остатка отделения на последний модуль. Логическая глубина схемы вычисления представления проекций в ОПСС равна:
Логическая глубина умножения на константу равна одной операции, т.к. все умножения на константы ОПСС выполняются параллельно:
Схема вычисления остатка от деления (Mod/?/) рассмотрена ранее в пункте 3.1, рисунок 3.3. Логическая глубина схемы вычисления остатка от деления равна количеству слоев в дереве сумматоров по модулю рп, т.е. [log2((L21og2pJ+l)/ )l, где s - разрядность констант, хранимых в LUT таблицах. Из ранее найденного, логическая глубина каждого из сумматоров по модулю равна 3 операциям. Тогда с учетом логической глубины подблоков, логическая глубина схемы вычисления остатка от деления равна
Таким образом, логическая глубина схемы вычисления представления проекций в ОПСС с учетом логической глубины ее подблоков равна:
Согласно схеме на входы сравнения подаются рассчитанная старшая цифра ОПСС проекции и ноль. Если старшая цифра ОПСС проекции равна нулю, на выход подается единица ( 1 ), иначе ноль ( 0 ). Схема сравнения с нулем содержит единственную операцию сравнения, поэтому ее логическая глубина равна 1 операции:
Схема выбора корректной проекции содержит n - q мультиплексоров с Cqn входами: на входы различных мультиплексоров подаются рассчитанные цифры ОПСС всех проекций по одному и тому же модулю (т.е. входами мультиплексора являются цифры ОПСС различных проекций по одному и тому же основанию), на управляющие входы мультиплексоров подается номер корректной проекции, на выход каждого из мультиплексоров подается по одной цифре ОПСС корректной проекции. Схема выбора корректной проекции содержит 1 сравнение, поэтому ее логическая глубина равна 1 операции:
Для перехода от представления в корректной проекции в ОПСС к представлению в позиционной системе счисления, необходимо цифры ОПСС a2, …, an –q умножить на заранее сохраненные константы, равные частичным произведениям модулей корректной проекции и сложить полученные произведения (рис. 3.11). Логическая глубина умножения на константу равна 1 операции, т.к. все умножения выполняются параллельно. Как уже было отмечено, логическая глубина схемы многооперандного сумматора равна количеству слоев в дереве сумматоров, т.е. l0g2 (/!f). Тогда логическая глубина схемы перехода от представления в ОПСС к представлению в позиционной системе счисления равна:
Сравнительный анализ моделей распределенных систем хранения данных
Методы повышения отказоустойчивости основаны на формировании дополнительной информации, позволяющей восстановить исходные данные в случае потери или порчи какой-то их части. В разделе 2.5 был предложен вероятностный подход к оценке отказоустойчивости распределенных систем хранения данных, основанных на резервировании и использовании схем разделения данных [28]. С одной стороны, использование схем разделения данных позволяет повысить отказоустойчивость распределенных систем хранения данных по сравнению с резервированием при одинаковом уровне избыточности, с другой стороны, позволяет снизить избыточность при одинаковом уровне отказоустойчивости.
Если приоритетом при проектировании распределенной системы хранения данных является снижение эксплуатационных затрат, то схемы разделения данных подбираются таким образом, чтобы максимально снизить избыточность с сохранением приемлемого уровня отказоустойчивости. В таблице 4.11 приведены данные отказоустойчивости и избыточности распределенных систем хранения данных с использованием репликации и схем разделения данных в зависимости от размера хранимых файлов и годового показателя AFR жестких дисков (T0 = 8766 часов), на которых строится распределенная система хранения данных. Вероятность искажения данных равна er = 0.001. Фактор репликации и схема разделения данных подобраны таким образом, чтобы обеспечить приемлемую отказоустойчивость распределенной системы хранения данных: PFD 10–2.
Если приоритетом при проектировании распределенной системы хранения данных является повышение отказоустойчивости, то схемы разделения данных подбираются таким образом, чтобы повысить отказоустойчивость с сохранением того же уровня избыточности, что и при резервировании. В таблице 4.12 приведены данные отказоустойчивости и избыточности распределенных систем хранения данных с использованием репликации и схем разделения данных в зависимости от размера хранимых файлов и годового показателя AFR жестких дисков (T0 = 8766), на которых строится распределенная система хранения данных. Вероятность искажения данных равна er = 0.001. Фактор репликации подобран таким образом, чтобы обеспечить приемлемую отказоустойчивость распределенной системы хранения данных: PFD 10–2. Схема разделения данных подбирается так, что бы ее избыточность была равна избыточности при резервировании, обеспечивающем необходимый уровень отказоустойчивость.
Полученные в ходе сравнительного анализа данные показали, что использование алгоритмов разделения данных для снижения избыточности позволяет в среднем в 3.36 раза уменьшить избыточность систем, построенных на жестких дисках с высоким годовым показателем вероятности выхода из строя AFR = 0.1; в среднем в 3.14 раза уменьшить избыточность систем, построенных на жестких дисках со средним годовым показателем вероятности выхода из строя AFR = 0.05; в среднем в 2.38 раза уменьшить избыточность систем, построенных на жестких дисках с низким годовым показателем вероятности выхода из строя AFR = 0.01 по сравнению с резервированием при одинаковом уровне отказоустойчивости сравниваемых распределенных систем хранения данных (табл. 4.11, рис. 4.5). При увеличении размеров хранимого файла, выигрыш в избыточности при использовании схем разделения данных по сравнению с резервированием возрастает. Отметим, что даже снижение избыточности в два раза позволяет существенно сократить эксплуатационные затраты в случае крупномасштабных распределенных систем хранения.
Использование алгоритмов разделения данных для повышения отказоустойчивости распределенных систем хранения данных позволяет снизить вероятность отказа системы при запросе (PFD) в течение года в среднем на 3 порядка, с 3.610–3 до 310–6 для систем, построенных на жестких дисках с высоким годовым показателем вероятности выхода из строя AFR = 0.1; более чем на 3 порядка, с 3.210–3 до 5.110–7, снизить вероятность отказа систем, построенных на жестких дисках со средним годовым показателем вероятности выхода из строя AFR = 0.05, по сравнению с резервированием. При использовании схем разделения данных в распределенных системах хранения, построенных на жестких дисках с годовым показателем вероятности выхода из строя AFR = 0.01 и ниже, вероятность отказа системы при запросе (PFD) в течение года стремится к нулю при одинаковом уровне избыточности сравниваемых распределенных систем хранения данных (табл. 4.12, рис. 4.6).
Предложенные методы расчета отказоустойчивости и избыточности и соответствующее разработанное программное обеспечение могут быть использованы для расчета параметров распределенной сети хранения данных, исходя из требований, предъявляемых к ее отказоустойчивости, общего объема памяти и объема хранимых полезных данных.