Простейшие практические реализации
Хорошим примером воплощения кодера/декодера Рида-Соломона являются "древние" модели жестких дисков, разработанных в недрах фирмы IBM. Модель IBM 3370
имела простой и наглядный кодер/декодер Рида-Соломона типа (174,171) в поле Галуа GF(256). Другими словами, он оперировал 8-битными ячейками (28 = 256), и на 171 информационный байт приходилось 3 байта суммы четности, что в результате давало кодовое слово с размером 174 байт, причем, как мы увидим далее, все три байта контрольной суммы рассчитывались совершенно независимо друг от друга, поэтому фактически кодер/декодер Рида-Соломона оперировал одним байтом, что значительно упрощало его архитектуру.
В современных же винчестерах кодер/декодер Рида-Соломона стал слишком "навороченным", а количество контрольных байтов многократно возросло, в результате чего пришлось работать с числами противоестественных разрядностей (порядка 1408 бит и более). Как следствие — программный код "ощетинился" толстым слоем дополнительных проверок, циклов и функций, чрезвычайно затрудняющих его понимание (к тому же большинство производителей железа в последнее время перешли на аппаратные кодеры/декодеры Рида-Соломона, полностьюцеликом реализованные в одной микросхеме). В общем, прогресс — прогрессом, а для изучения базовых принципов работы лучше использовать "древние" модели.
Ниже (листинг 21.17 и 21.18) приведены два фрагмента оригинальной прошивки жесткого диска IBM 3370 (только не спрашивайте: откуда они у меня взялисья).:
Листинг 21.17. Ключевой фрагмент кодера Рида-Соломона, вырванный из прошивки IBM 3370
for (s0 = s1 = sm1 = i = 0; i < BLOCK_SIZE; ++i)
{
s0 = s0 ^ input[i];
s1 = GF_mult_by_alpha[ s1 ^ input[i] ];
sm1 = GF_mult_by_alpha_inverse[sm1 ^ input[i] ];
};
Листинг 21.18. Ключевой фрагмент декодера Рида-Соломона, вырванный из IBM 3370
err_i = GF_log_base_alpha[ GF_divide[s1][s0] ]; // вычисляем синдром ошибки
input[err_i] ^= s0; // исправляем сбойный байт
Ну, что, слабо нам разобраться: как он работает? Что касательно переменной s0 — с ней все предельно ясно: она хранит контрольную сумму, рассчитанную по тривиальному алгоритму. Как вывы, наверноенаверное, помните, сложение в полях Галуа осуществляется логической операцией XOR (исключающее ИЛИ) и потому: s0 += input[i[Y68] [n2k69] ].
Назначение переменной s1 выяснить сложнее и чтобы понять суть разворачивающегося вокруг нее "метаболизма", мы должны знать содержимое таблицы GF_mult_by_alpha. Несмотря на то, что по соображениям экономии бумажного пространства она здесь не приводится, ее имя говорит само за себя: содержимое переменной s1 суммируется с очередным байтом контролируемого потока данных и умножается на так называемый примитивный член, обозначаемый как alpha, и равный двум. Другими словами: s1 = 2 * (s1 + input[i]).
Допустим, один из байтов потока данных в последствии будет искажен (обозначим его позицию как err_i), тогда индекс искаженного байта можно определить тривиальным делением переменной s1 на s0. Почему? Так ведь выражение s1 = 2 * (s1 + input[i]) по своей сути есть ни что иное, как завуалированное умножение информационного слова на порожденный полином, динамически генерируемый на основе своего примитивного члена alpha. А контрольная сумма информационного слова, хранящаяся в переменной s0, фактически представляет собой то же самое информационное слово, только представленное в более "компактной" форме. И, как уже говорилось в предыдущей главе: если ошибка произошла в позиции x, то остаток от деления кодового слова на порожденный полином будет равен k = 2x. Остается лишь по известному значению k
вычислить x, что в данном случае осуществляется путем обращения к таблице GF_log_base_alpha, хранящей пары соответствий между k и 2x. Коль скоро позиция сбойного байта найдена, его можно исправить путем выполнения операции XOR (исключающее ИЛИ)'а с рассчитанной контрольной суммой s0 (input[err_i] ^= s0).
Конечно, сказанное справедливо только для одиночных ошибок, а искажения двух и более байт на один блокблок, данный алгоритм исправить не в силах. Собственно, для этого и присутствует третий байт контрольной суммы — sm1, — защищающий декодер от "политнекорректных" попыток исправления ошибок, когда их больше одной. Если выражение s1/s0 == sm1 * s0
становится ложным, — контроллер винчестера может засвидетельствовать факт наличия множественных ошибок, констатируя невозможность их исправления.
Однако, как хорошо известно, дефекты магнитной поверхности имеют тенденцию образовывать не одиночные, а групповые ошибки. И, чтобы хоть как-то компенсировать слабость корректирующего алгоритма, парни из фирмы IBM прибегли к чередованию байт. Винчестер IBM 3370 имел чередование 3:1, означающее то, чтото есть сначала шел первый байт первого блока, за ним первый байт второго блока, за ним — первый байт третьего и только потом — второй байт первого блока. Такой трюк усиливал корректирующую способность винчестера с одной одиночной ошибки, до трех последовательно искаженных байт.. Однако, если разрушению подвергались не соседние байты, то корректирующая способность вновь уменьшаласьопускалась до значений в один искаженный байт на блок, но вероятность такого события была несравненно меньше.
Естественно, что данный алгоритм может быть реализован не только в самом жестком диске, но и вне его. Варьируя размер блоков и степень чередования, вы обеспечите себе лучшую или худшую защищенность при большей или меньшей избыточности информации. Действительно, пусть у нас есть N
секторов на диске. Тогда, разбив их на блоки по 174 сектора в каждом и выделив 3 сектора для хранения контрольной суммы, мы сможем восстановить по меньшей мере N/174 секторов диска. Исходя из средней емкости диска в 100 Гбайт (что соответствует 209 .715 .200 секторам), мы сможем восстановить до 1 .205 .259 секторов даже при их полном физическом разрушении, затратив всего лишь 2% дискового пространства для хранения контрольных сумм.
Согласитесь, что очень редко, когдаая процесс "осыпанияка" винчестера проходит столь стремительно, чтобы корректирующих способностей кода Рида-Соломона оказалась недостаточно для егое воскрешения. (конечноКонечно, если этоу "осыпаниеку" вовремя заметить и, если коэффициент чередования выбран правильно: так, что сектора, принадлежащие одному дисковому блину, обслуживались бы разными корректирующими блоками, в противном случае при повреждении поверхности одного из блинов возникнет групповая ошибка, уже неисправимаянеисправляемая данной программой).
А как быть, если выйдет из строя"навернется" весь жесткий диск целиком? Наиболее разумный выход — создать массив из нескольких дисков, хранящих полезную информацию вперемешку с корректирующими кодами. Главный минус такого подхода — его неэффективность на массивах, состоящих из небольшого количества жестких дисков. Разумный минимум — это: четыре информационных диска и один контрольный, тогдакогда потеря любого из информационных дисков компенсируется оставшихсяоставшимся "в живых" контрольным. Ну, а потерянный контрольный диск элементарным образом заменяется на новый, с последующим пересчетом всех контрольныхе кодов. Правда, одновременный выход двух дисков из строя — это "кранты". Массив из пятнадцати дисков RAID (Redundant Array of Independent Disks, матрица независимых дисковых накопителей с избыточностью), двенадцать из которых — информационные, а оставшиеся три — контрольные, намного более отказоустойчив и допускает одновременный крах двух любых дисков, а при благоприятном стечении обстоятельств — и трех.
Собственно, во всем этом ничего нового нет, и соответствующие RAID-контроллеры можно купить буквально в любом магазине. Однако… мне трудно представить себесебе, сколько будет стоить RAID-контроллер уровня 15 и удастся ли его вообще заставить работать (по личному опыту могу сказать, что RAID-контроллеры даже начальных уровней — вещь крайне "глючная", капризная и требовательная как к "железу", так и к операционному окружению).
Наконец, практически все RAID- контроллеры требуют наличия абсолютно идентичных, ну или близких по своим характеристикам и/или интерфейсам дисков. А коли таковых нет?
Программный RAID, активно пропагандируемый настоящим автором, всех этих недостатков лишен. Вы можете использовать диски различной геометрии и даже различной емкости, причем никто не обязывает вас сосредотачивать их в одном месте — доступ к дискам может осуществляться и по сети, причем совершенно необязательно отводить под RAID-хранилище весь диск целиком! Вы вольны произвольным образом выделять ту или иную часть дискового пространства.
Как это можно реально использовать на практике? Первое, что приходит на ум, использовать часть емкости жестких дисков под хранение избыточной информации, помогающей восстановить их в случае аварии. Если несколько компьютеров объединить в сеть (что уже давным-давно сделано и без нас), то при относительно небольших накладных расходах мы сможем восстановить любой из жестких дисков членов сети даже при полном его разрушении лишь за счет одной избыточной информации, распределенной между остальными компьютерами. Более надежного хранилища для ваших данных нельзя и придумать! Подобная схема была реализована автором в локальных сетях нескольких фирм и доказала свою высокую живучесть, гибкость и функциональность. Необходимость в постоянном резервировании содержимого жестких дисков автоматически отпала, что в условиях одно-ранговой сети с отсутствующим выделенным сервером более, чем актуально! А ведь такие локальные сети — не редкость (нет, я не утверждаю, что такие сети хороши, просто я констатирую факт, что они существуют в природе и в обозримом будущем "вымирать" не собираются).
Единственный минус программного RAID'а'а — его невысокая производительность. В частности, поставив программный RAID на сервер, обрабатывающий тысячи запросов ежесекундно и интенсивно модифицирующий большое количество файлов, вы не выиграете ничего, но… ведь само понятие "производительности" очень относительно и при достаточно быстром процессоре кодирование/декодирование информации вполне реально осуществлять и "на лету" безо всяких потерь в пропускной способности! С другой стороны, если операции чтения доминируют над операциями записи, то ставить программный RAID сам "Крестный Отец" велел, поскольку контроль целостности считываемой информации осуществляется на "железном" уровне самим приводом и при использовании систематического кодирования (т. е.информационные слова — отдельно, байты четности — отдельно), декодеру Рида-Соломона нет никакой нужды как-то вмешиваться в этот процесс и его помощь требуется лишь тогда, когда часть информации оказывается безнадежно разрушена, что случается прямо-таки скажем не часто. Так что, право же, не стоит "перекармливать" фирмы, специализирующие на выпуске RAID'ов, тем более, что на домашний и мелко-офисный рынок они все равно не обращают внимания.
