Обзоры Обзоры 20.06.2007 в 08:55 comment

Неизбыточно о RAID

author avatar
https://secure.gravatar.com/avatar/2f8d57cddfeb455ba418faa11ee01bb0?s=96&r=g&d=https://itc.ua/wp-content/uploads/2023/06/no-avatar.png *** https://secure.gravatar.com/avatar/2f8d57cddfeb455ba418faa11ee01bb0?s=96&r=g&d=https://itc.ua/wp-content/uploads/2023/06/no-avatar.png *** https://itc.ua/wp-content/themes/ITC_6.0/images/no-avatar.svg

ITC.UA

автор

«Это изобретение относится к системам хранения данных и, в частности, к усовершенствованным механизмам для восстановления информации, хранящейся в вышедшем из строя устройстве памяти», – так начинается описательная часть патента США № 4,092,732, которым изобретатель Норман Кен Учи (Norman Ken Ouchi) защитил свою интеллектуальную собственность в далеком 1978 г.

Неизбыточно о RAID
Дэвид Паттерсон, автор термина «RAID»

О технологиях, объединяемых общим термином «избыточный массив дешевых дисков» (Redundant Array of Inexpensive Disks), написано так много, что автор просто не может позволить себе что-то, для чего просится аббревиатура YARAIDA (Yet Another RAID Article, «еще одна статья о RAID»). И все равно мы будем говорить только о RAID, хотя и несколько необычно.

Давайте для начала вернемся к патенту № 4,092,732 – для выяснения задачи, которую решал Кен Учи почти 30 лет назад: «…в типовой системе обработки данных обычно используется одно или несколько устройств памяти, соединенных с центральным процессором. Функцией этих устройств является хранение данных и программ, с помощью которых центральный процессор выполняет задачи обработки данных… если одно из них выходит из строя, система утрачивает доступ к хранящейся в нем информации. Обычно это приводит к серьезному сбою и выходу из строя всей системы обработки данных». За прошедшие годы в высокоуровневой архитектуре массово-доступных и даже просто реально (а не на уровне проектов или прожектов) существующих и работоспособных вычислительных машин ничего существенно не изменилось, поэтому никаких усилий для доказательства актуальности задачи, поставленной Кеном Учи, мы прилагать не будем. Напротив, мы подчеркнем возросшую важность этой задачи, обратившись ко второму ключевому документу в RAID-истории – к ставшей уже классической статье Дэвида Паттерсона, Гарта Гибсона и Рэнди Каца, авторов термина RAID. Эта работа под названием «Доводы в пользу избыточного массива дешевых дисков» была опубликована через десять лет после патентования Учи своей тогда еще безымянной технологии и начинается кратким описанием проблемы, с которой, по мнению авторов, непременно столкнутся пользователи вычислительных систем в ближайшие (к 1988 г., конечно же) годы: «…Гордон Белл утверждает, что в период с 1974 г. по 1984 г. возможности однокристальных компьютеров увеличивались на 40% в год, в два раза обгоняя рост возможностей мини-ЭВМ.

В последующие годы Билл Джой предсказал еще более высокую скорость роста (MIPS – миллионы инструкций в секунду, Year – год прогноза):

MIPS = 2Year–1984

…а в соответствии с правилом Амдала повышение быстродействия центрального процессора на одну операцию в секунду сопровождается увеличением емкости основной памяти на один байт… Для поддержания баланса стоимости вычислительных систем долговременная энергонезависимая память должна соответствовать возможностям всей системы в целом… что вызовет потребность существенного увеличения емкостей основной памяти для буферирования операций ввода-вывода… но все равно производительность приложений, характеризующихся громадной интенсивностью обмена небольшими количествами данных с дисковой подсистемой (например, приложения обработки транзакций), будет сильно ограничена…».

К слову, этот фрагмент статьи дает нам возможность проверить и пророческие способности Джоя и Амдала, и (используя штампы примерно той же тридцатилетней давности) то, как промышленность выполняет заветы классиков: ни предсказанная производительность порядка миллионов MIPS, ни объемы оперативной памяти на уровне мегабайт не соответствуют реалиям наших дней. Справедливости ради следует отметить, что на наблюдаемом из 1988 г. историческом участ-ке эти эмпирические правила казались вполне работоспособными. Но эти детали уже не принципиальны – сегодня, когда мы оперируем гигафлопами, гигабайтами ОЗУ и терабайтами дисковых систем, две задачи, для которых искали решения Кен Учи и команда Дэвида Паттерсона, – снижение зависимости сохранности информации от работоспособности накопителей и повышение производительности дисковой подсистемы – становятся исключительно важными.

Онлайн-курс Pyton від Powercode academy.
Опануйте PYTHON з нуля та майте проект у своєму портфоліо вже через 4 місяця.
Приєднатися

XOR

Предшествующие отступления были, если так можно сказать, историко-логическими и касались предпосылок возникновения RAID-технологии. Теперь же пора, не стесняясь, отступить к самым основам… к алгебре. Точнее, к функции, на программистском сленге часто называемой «ксор» (xor). Без ее знания все рассказы о RAID-технологии превратятся в невнятные объяснения на пальцах. Более того, повторение xor даст нам возможность так незаметно перейти к точному описанию механизма функционирования «самого RAID из всех RAID», что игра стоит свеч.

Этой функции не очень повезло – она крайне проста и стала популярной из-за всевозможных трюковых приемов, непременно появляющихся в арсенале практикующего программиста. В результате уже мало кто задумывается о том, с чем имеет дело. А ведь «тонкости» xor начинаются сразу с ее названия. Дело в том, что для функции xor, обычно описываемой в учебниках языков программирования следующей таблицей истинности… есть несколько названий:

X1 X2 Y = xor(X1, X2)
0 0 0
0 1 1
1 0 1
1 1 0

Ее называют «исключающее или», «сложение по модулю 2» и, наконец, «несовпадение». И пока речь идет о функции от двух переменных (в приведенной выше таблице – X1 и X2), все эти названия допустимы. Так, «сложение по модулю 2» описывает арифметический способ реализации такой функции – остаток от деления суммы на 2. «Исключающее или» – логический способ ее построения. Но давайте взглянем на таблицы истинности функций с теми же названиями, но от трех переменных:

X1 X2 X3 Сложение по мод. 2 Исключающее или Несовпадение
0 0 0 0 0 0
0 0 1 1 1 1
0 1 0 1 1 1
0 1 1 0 0 1
1 0 0 1 1 1
1 0 1 0 0 1
1 1 0 0 0 1
1 1 1 1 0 0

Как видите, все они действительно разные. О какой же из них принято говорить в контексте языков программирования и какая реализована, например, в языке C оператором «^»? Для ответа на этот вопрос прибегнем к практическому приему – большинство C-программистов, специализирующихся на разработке программного обеспечения встраиваемых систем (где каждый байт на счету), знают трюк, позволяющий изящно обменять содержимое двух регистров без использования дополнительных ячеек памяти:

void xorSwap(int *x, int *y)
{
 *x ^= *y;
 *y ^= *x;
 *x ^= *y;
}

О каком свойстве функции xor нам говорит этот код? Очевидно, о том, что повторное ее применение возвращает к исходному значению аргумента, иначе говоря, что если с = xor(a, b), то b = xor(c, a) и a = xor(c, b). Менее очевидно, но проще, то же самое можно сказать следующим образом – функция такова, что при равенстве двух аргументов ее результат равен третьему аргументу. Это свойство функции в алгебре принято называть инволютивностью, и в общем случае (при числе переменных больше двух) им обладает только сложение по модулю 2. К слову, авторам русского перевода статьи википедии об алгоритме обмена содержимым регистров с помощью функции xor следует исправить неточность – речь идет о сложении по модулю 2, а не об исключающем или.

Онлайн-курс Pyton від Powercode academy.
Опануйте PYTHON з нуля та майте проект у своєму портфоліо вже через 4 місяця.
Приєднатися

Теперь давайте опишем свойство инволютивности функции xor (сложение по модулю 2) с числом аргументов, большим двух, например с четырьмя аргументами, в следующей форме:

если P=xor(X1, X2, X3, X4), то 
X1=xor(P, X2, X3, X4), 
X2=xor(P, X1, X3, X4), 
X3=xor(P, X1, X2, X4) и 
X4=xor(P, X1, X2, X3). 

Для повторного самостоятельного «открытия» главной идеи RAID-технологии нам остается только уточнить еще одно важное свойство функции xor – это сложение, не порождающее переносов, т. е. при любых числе и комбинациях значений однобитовых аргументов всегда получается однобитовый результат. Иными словами, приведенное выше описание свойства инволютивности «работает» как теоретически, на бумаге, с «однобитовыми» логическими переменными, так и с реализациями xor на реальных процессорах, вне зависимости от разрядности переменных X1-X4 и P (естественно, если все они одинаковой разрядности).

Собственно говоря, настала пора назвать вещи своими именами. Если в приведенной выше записи принять в качестве X1-X4 и P блоки данных, являющиеся множествами битов с одинаковой мощностью (числом битов в блоке), мы получили не что иное, как… модель RAID 5 – представителя некогда многочисленного списка технологических приемов, объединяемых термином RAID и единственного в этом списке, в какой-то мере направленного на решение задач, поставленных Кеном Учи и Дэвидом Паттерсоном. Последнее утверждение неочевидно и требует некоторых пояснений.

Снижение зависимости сохранности информации от работоспособности накопителей (задача, поставленная Кеном Учи) с помощью такой модели решается при следующем уточнении: если блоки X1–X4 и P хранятся на пяти разных физических дисках, выход из строя любого из них (X1-X4) не приведет к утрате информации, потому что каждый блок данных вышедшего из строя накопителя может быть восстановлен посредством функции xor с соответствующими аргументами. Задача увеличения производительности дисковой подсистемы, поставленная командой Дэвида Паттерсона, потенциально может быть решена в рамках приведенной выше модели, если блоки данных X1–X4 и P не просто хранятся на разных физических накопителях, но и записываются-считываются с них одновременно. Естественно, такое решение может потребовать (и практически всегда требует, но, заметьте, не без исключений из правила, о них – позже) дополнительных аппаратных средств.

Теперь давайте вернемся к патенту Кена Учи: «…иным решением является использование "контрольных сумм". В этом решении информацию, сохранность которой надо обеспечить, записанную на одном накопителе, мы обрабатываем функцией xor с информацией со второго накопителя и результирующую "контрольную сумму" сохраняем на третьем накопителе… Этот принцип может использоваться и при числе накопителей, большем трех…» (примечательно, насколько сильно въелось неверное утверждение «xor – исключающее или»: в патенте Учи называет xor именно «исключающим или», но результат, полученный с помощью этой операции, – все-таки «контрольной суммой»).

Нюансы реальности

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

Современные диски более чем недороги и привлекательны для RAID-систем. Но, как обычно, все дело в нюансах. Точнее, в одном нюансе – в кэшировании с отложенной записью (write-back cache). Суть его в том, что интеллектуальный накопитель очень быстро получает блок данных от хост-машины в быструю кэш-память и тут же сообщает хосту о завершении процедуры записи. Когда же данные из кэш-памяти будут перенесены физически на энергонезависимую память (поверхность диска) накопителя – это хост-машины ни в коем случае не касается, а становится заботой контроллера диска. Такой подход дает возможность прозрачно для высокоуровневого системного ПО оптимизировать операции записи и добиться весьма высокой средней производительности накопителя. Кэширование – механизм, бесспорно, очень эффективный и полезный. Вот только в инженерии не бывает механизмов «эффективных и полезных вообще» – как только вы согласитесь с возможностью их существования, сразу соглашайтесь и с неистребимыми создателями вечных двигателей. В инженерии же есть понятие «при соблюдении определенных условий». И пока дисковый накопитель с большим объемом встроенной кэш-памяти и механизмом отложенной записи используется в качестве единственного и основного устройства долговременной памяти, все просто прекрасно. Но давайте восстановим только что выстроенную модель RAID 5 – пять накопителей, четыре из которых хранят непосредственно данные, пятый – «контрольные суммы», операции чтения-записи выполняются параллельно, при этом каждый накопитель имеет встроенный кэш и механизм отложенной записи. Предположим, что операционная система «забросала» накопители запросами на запись большого количества блоков данных, и тут ей на помощь пришла наша доблестная энергетика – пропало питание. Так как кэш-память жестких дисков не имеет собственных резервных источников, ее содержимое пропадает. Что же тогда сохраняется долговременной энергонезависимой памятью накопителей? В общем случае на этот вопрос ответа нет. Понятно только одно – в такой ситуации после включения системы и попытки восстановления RAID-массива вполне возможно, что восстановленные с помощью xor данные окажутся полной галиматьей. Для этого достаточно, чтобы содержимое кэш-памяти с контрольными суммами не было перенесено на диск – ведь нет никакой гарантии, что в восстанавливающих выражениях типа Xi = xor(P, Xj, Xk…Xn) все блоки данных будут теми же, которые участвовали в формировании P.

Естественно, у накопителей, оснащенных кэш-памятью с механизмом отложенной записи, есть возможности и полностью отключать этот механизм, и принудительно, по команде хост-машины, переносить данные из кэш-памяти на поверхность диска. Но все дело в том, что полное отключение механизма отложенной записи категорически не рекомендуется производителями накопителей – оно сильно снижает ресурс их работы (объяснения этому вполне очевидны), а использованию принудительной записи содержимого кэш-памяти разработчики системного ПО уделяли на удивление мало внимания. Достаточно сказать, что только в ОС семейства Windows и Solaris используется механизм принудительной инициации переноса содержимого кэш-памяти на диски (обсуждение деталей можно без труда отыскать в тематических форумах по ядру ОС Linux и NetBSD).

RAID-Z

Об упомянутом инженерном правиле «справедливо в определенных условиях» прекрасно знала команда разработчиков файловой системы ZFS (Sun, проект операционной системы Solaris) под руководством Джеффа Бонвика. Неудовлетворенные этими самыми «определенными условиями»программисты Sun решили пойти своим путем и умудрились создать технологию RAID-Z всего 599 строками кода! RAID-Z не только устраняет невозможность невосстанавливаемого сбоя из-за некогерентности перенесения содержимого дисковых кэшей на энергонезависимую память, но и не требует на это существенных расходов. В отличие от известного приема – использования аппаратного энергонезависимого сверхбыстродействующего буфера большой емкости, позволяющего применять аппаратно-программный RAID-контроллер с любой операционной и файловой системой, подход команды Бонвика основывался на уникальных возможностях файловой системы ZFS. Во-первых, в отличие от RAID, несвязанных с файловой системой, RAID-Z позволяет формировать блоки X1–X4 и P произвольного и переменного размера. Во-вторых, RAID-Z хранит для каждого блока 256-битовую контрольную сумму, позволяющую идентифицировать содержимое блока и проверять его на пригодность к использованию в xor-операции восстановления данных (такой функции принципиально не существует в традиционных RAID-контроллерах). В-третьих, RAID-Z обладает не только способностью восстанавливать весь вышедший из строя накопитель, но и отдельный блок данных – как только его вычисленная контрольная сумма не совпадет с хранимой, RAID-Z автоматически прочитает блок P, вычисленный для данного блока, и с помощью xor рассчитает правильное значение. В-четвертых, RAID-Z использует механизм принудительной записи содержимого кэш-памяти накопителей, что позволяет избежать проблем «некогерентности». И наконец, RAID-Z не требует никакого дополнительного аппаратного обеспечения.

RAID ли тот RAID, который не RAID 5?

Читатель, знакомый с технологией RAID, просто обязан задать автору статьи очевидный вопрос – почему не упомянуты другие уровни RAID, которых некогда было немало, но от которых в сегодняшнем перечне реально «выживших» остались разве что RAID 0 и RAID 1? Вопрос совершенно законный. И хотя ответ на него в неявном виде присутствует в статье, попробуем все-таки окончательно определиться со смыслом используемых терминов.

Если мы попытаемся «вычеркнуть» из истории RAID-технологии заслуги Кена Учи только на том основании, что запатентованная им система обеспечения сохранности абстрактной (совершенной, «чистой») информации в мире несовершенных реальных накопителей не получила в свое время название RAID – мы не просто обидим талантливого изобретателя (которого, по большому счету, нам и не обидеть даже при огромном желании). Мы поступим намного хуже – выбросим из списка требований к технологии и ее овеществлениям ключевой элемент.

С другой стороны, если мы согласимся со сторонниками кое-где модной позиции «аббревиатуры ничего не значат», то вычеркнем второй ключевой элемент списка требований к технологии RAID – результаты работы команды Дэвида Паттерсона.

Но если мы принимаем требования и Учи, и Паттерсона одновременно и утверждаем, что система, обеспечивающая долговременное хранение и доступ к информации, должна удовлетворять этим требованиям, чтобы стать настоящим «избыточным массивом дешевых дисков», – то должны согласиться и с псевдопарадоксом: младшие уровни RAID по-настоящему не являются RAID ввиду несоответствия критериям Учи и Паттерсона. Например, резервирование накопителя (RAID 1, на сленге – «зеркалирование») ни в коей мере не способствует повышению производительности всей вычислительной системы в целом. Еще забавнее обстоит дело с известным уровнем RAID 0 – он вообще чуть ли не официально называется «избыточным массивом» (потому что RAID), но без избыточности (потому что RAID 0).

Именно по этим причинам под термином RAID в статье понимается исключительно полноценный избыточный массив жестких дисков – RAID 5 и его производные. Увы, случай массово-распространенной путаницы «сложение по модулю 2 – исключающее или» не может претендовать на исключительность – RAID 0 и RAID 1 на самом деле не являются представителями технологии Redundant Array of Inexpensive Disks.

Продолжается конкурс авторов ИТС. Напиши статью о развитии игр, гейминг и игровые девайсы и выигрывай профессиональный игровой руль Logitech G923 Racing Wheel, или одну из низкопрофильных игровых клавиатур Logitech G815 LIGHTSYNC RGB Mechanical Gaming Keyboard!


Loading comments...

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: