СПОСОБ ВОССТАНОВЛЕНИЯ ЗАПИСЕЙ В ЗАПОМИНАЮЩЕМ УСТРОЙСТВЕ И СИСТЕМА ДЛЯ ЕГО ОСУЩЕСТВЛЕНИЯ Российский патент 2013 года по МПК G06F11/08 G11C29/52 

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

Ключевой технологией для обеспечения надежности хранения данных в запоминающих устройствах является возможность восстановления данных при выходе из строя одной или нескольких зон запоминающего устройства. Так как в настоящее время наиболее часто для хранения больших объемов информации используются запоминающие устройства, представляющие собой дисковые массивы, можно говорить о возможности восстановления данных при выходе из строя одного или нескольких жестких дисков. Для этого используются различные методы коррекции кода - так называемые избыточные дисковые массивы RAID (redundant array of independent disks). Восстановление происходит за счет вычисления и хранения некоторой избыточной информации (контрольных сумм), которая позволяет восстановить потерянные данные, но требует дополнительного дискового пространства. (См., например, Anvin, Н.Р. (последнее обновление 20 декабря 2011). Получено 25 августа 2012 года по адресу http://ftp.kernel.org/pub/linux/kernel/people/ripa/raid6.pdf).

Способы и системы восстановления записей в запоминающих устройствах с использованием массивов RAID описаны в многочисленных патентных документах, например, патенты США №№7392458 (публ. 24.06.2008), 7437658 (публ. 14.10.2008), 7600176 (публ. 06.10.2009); в заявках на патент США №№2009/0132851 (публ. 21.05.2009), 20100229033, (публ. 09.09.2010), 201101145677 (публ. 16.06.2011), 20110167294 (публ. 07.07.2011), 20110264949 (публ. 27.10.2011).

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

Однако для больших массивов запоминаемой информации известные способы не могут обеспечить достаточной надежности работы, это связано с параметрами надежности современных запоминающих устройств. Так для жестких дисков, объединенных по технологии RAID-6, на текущем уровне развития техники достаточная надежность достигается на массивах не более 24 ТБ. Когда используется большое количество дисков, возникает реальная опасность выхода из строя одновременно двух и более дисков. На практике данное затруднение преодолевают за счет разбиения больших массивов на маленькие, что влечет дополнительные расходы на использование больших объемов памяти для хранения контрольных сумм. Поэтому существует потребность в новых способах восстановления записей при хранении больших массивов информации в запоминающих устройствах.

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

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

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

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

где D_i - i-я информационная зона, в которую записаны кодовые слова d_i,1, d_i,2,…, d_i,s-1

i=0,…, n-1, кодовые слова являются элементами поля Галуа;

n - число информационных зон;

s - число кодовых слов в одной информационной зоне;

a - примитивный элемент поля Галуа.

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

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

Способ по изобретению дает возможность обойти технические ограничения надежности носителей и создавать массивы записей в запоминающих устройствах значительно большего объема. При этом способ позволяет восстановить данные при возникновении до трех одновременно возникших отказов или повреждений. Отказы могут происходить и в той части запоминающего устройства, где хранятся контрольные суммы. Кроме того, способ позволяет также восстанавливать ошибки чтения и записи, не регистрируемые аппаратными средствами. Эти результаты достигаются всеми признаками способа, в том числе за счет формирования трех контрольных сумм, хранящихся в различных частях запоминающего устройства. При этом важно, что контрольные суммы рассчитаны на основе трех формул, приведенных выше, и восстановление данных с использованием эталонных и текущих контрольных сумм производят путем решения систем уравнений, полученных из формул расчета контрольных сумм.

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

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

- вычислительный блок.

Каждая из n информационных зон запоминающего устройства выполнена с возможностью записи в нее группы подлежащих запоминанию данных в виде набора кодовых слов;

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

упомянутый вычислительный блок выполнен с возможностью:

нахождения эталонных контрольных сумм, каждую по соответствующей заранее установленной формуле, для каждого i-го набора кодовых слов, где i=0,…, n-1, во всех упомянутых n информационных зонах при каждой записи подлежащих запоминанию данных в упомянутое запоминающее устройство.

При этом для расчета контрольных сумм S₀, S₁, S₂ применяются следующие формулы:

где D_i - i-я информационная зона, в которую записаны кодовые слова d_i,1, d_i,2,…, d_i,s-1;

i=0,…,n-1, кодовые слова являются элементами поля Галуа;

n - число информационных зон;

s - число кодовых слов в одной информационной зоне;

a - примитивный элемент поля Галуа.

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

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

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

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

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

Настоящее изобретение иллюстрируется рисунками.

На Фиг.1 показано разбиение дисков на блоки, которые составляют страйп.

На Фиг.2 приведено разбиение информационных зон на зоны хранения кодовых слов и кодовые зоны на зоны хранения кодовых слов.

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

В случае применения в качестве запоминающего устройства массива жестких дисков они разбиваются на блоки одинаковой длины. Последовательность блоков с одинаковыми номерами, но находящихся на разных дисках образует страйп (фиг.1). Информационные зоны и контрольные зоны - это блоки одного страйпа, которые хранятся на разных дисках. Разбиение информационных зон производится на зоны хранения кодовых слов и кодовые зоны - на зоны хранения кодовых слов (Фиг.2).

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

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

где D_i - i-я информационная зона, в которую записаны кодовые слова d_i,1, d_i,2,…, d_i,s-1; i=0,…, n-1, кодовые слова являются элементами поля Галуа;

n - число информационных зон;

s - число кодовых слов в одной информационной зоне;

a - примитивный элемент поля Галуа;

производится расчет синдромов S₀, S₁, S₂ с помощью вычислительного блока. Под умножением информационной зоны D_i на примитивный элемент поля а или его степени понимается умножение по модулю неприводимого многочлена всех кодовых слов информационной зоны на примитивный элемент поля или его степени. Сложение понимается как сложение по модулю 2 (логическая операция XOR). Полученные значения синдромов записываются на диски в тот же страйп, что и блоки данных.

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

Коэффициенты aⁱ в формулах выбирались, чтобы система уравнений всегда имела решение. Выбор в качестве коэффициентов степеней примитивного элемента обеспечивает выполнение этого условия.

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

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

Если поврежден блок D_j, являющийся информационной зоной, где j - номер поврежденного блока в страйпе, он нам известен, так как отказ регистрируется аппаратными средствами. Тогда с помощью вычислительного блока производится расчет текущей контрольной суммы . При этом при расчете текущей контрольной суммы пропускается значение отказавшего блока страйпа. Для увеличения производительности, при практической реализации, расчет контрольных сумм производится по схеме Хорнера (см. формулы расчета контрольных сумм). Тогда для расчета контрольных сумм используются операции: умножение на примитивный элемент и сложение. При расчете текущей контрольной суммы с пропуском значения отказавшей информационной зоны, для повышения производительности, вместо значения поврежденного блока D_j, который пропускается, можно положить D_j=0 и расчет текущей контрольной суммы также делать по схеме Хорнера.

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

Используя значения хранящейся эталонной контрольной суммы S₀ и значение текущей контрольной суммы , вычислительный блок по формуле

вычисляет значение отказавшей информационной зоны. Полученное значение записывается вместо поврежденного.

В случае повреждения одной информационной зоны данные могут быть восстановлены за счет контрольной суммы S₁. Этот вариант восстановления требует больше вычислительных ресурсов, но он необходим, если кроме информационной зоны в страйпе поврежден блок контрольной суммы S₀. Также данный способ восстановления может быть применен в режиме упреждающего восстановления. Режим упреждающего восстановления - это режим чтения данных, который позволяет ускорить процесс получение информации, когда падает скорость чтения с какого-либо диска. Система может не дожидаться окончания чтения данных с медленного диска, а восстановить их. Например, если в процессе чтения блоков с дисков непрочитанными остались контрольные суммы S₀, S₂ и одна информационная зона, то можно, не дожидаясь окончания процесса чтения, восстановить значение информационной зоны, а контрольные суммы S₀, S₂ посчитать. Использование упреждающего восстановления ускоряет процесс чтения, если какие-то диски начинают медленно работать.

В этом случае, если поврежден блок D_j, являющийся информационной зоной, где j - номер поврежденного блока в страйпе, он нам известен, так как отказ регистрируется аппаратными средствами. Тогда с помощью вычислительного блока производится расчет текущей контрольной суммы . При этом при расчете текущей контрольной суммы пропускается значение отказавшего блока страйпа.

Значение текущей контрольной суммы рассчитывается вычислительным блоком по формуле:

Используя значения хранящейся эталонной контрольной суммы S₁ и значение текущей контрольной суммы , вычислительный блок по формуле

вычисляет значение отказавшей информационной зоны. Полученное значение записывается вместо поврежденного.

Отрицательная степень означает обратный элемент поля Галуа. Умножение на обратный элемент соответствует делению в алгебре. Вычисление обратного элемента поля требует много вычислительных ресурсов. При практической реализации значения обратных элементов удобнее всего брать из заранее рассчитанных таблиц.

В случае повреждения одной информационной зоны данные могут быть восстановлены за счет контрольной суммы S₂. Этот вариант восстановления требует больше вычислительных ресурсов, но он необходим, если кроме информационной зоны в страйпе поврежден блок контрольной суммы S₀. Также данный способ восстановления может быть применен в режиме упреждающего восстановления. В этом случае, если поврежден блок D_j, являющийся информационной зоной, где j - номер поврежденного блока в страйпе, он нам известен, так как отказ регистрируется аппаратными средствами. Тогда с помощью вычислительного блока производится расчет текущей контрольной суммы S₂. При этом при расчете текущей контрольной суммы пропускается значение отказавшего блока страйпа.

Значение текущей контрольной суммы рассчитывается вычислительным блоком по формуле:

Используя значения хранящейся эталонной контрольной суммы S₂ и значение текущей контрольной суммы , вычислительный блок по формуле

вычисляет значение поврежденной информационной зоны. Полученное значение записывается вместо поврежденного.

Рассмотрим случай, когда в страйпе повреждены два блока, что соответствует отказу двух дисков массива. Также этот способ восстановления применяется, если во время реконструкции одного отказавшего диска возникает невосстановимая ошибка (UER) чтения, и, следовательно, поврежденными являются два блока. Если повреждены блоки, являющиеся контрольными зонами, тогда с помощью формул расчета контрольных сумм вычислительный блок рассчитывает текущие контрольные суммы, соответствующие поврежденным контрольным зонам. Полученные значения контрольных сумм записываются вместо поврежденных. Если из двух поврежденных блоков один является блоком информационной зоны, а другой контрольной зоны, в этом случае данные восстанавливаются по схеме, описанной выше, для одного отказавшего блока, а значение поврежденной контрольной зоны рассчитывается по формулам расчета контрольных сумм.

Если повреждены блок D_j и D_k, являющиеся информационными зонами, где j, k - номера поврежденных блоков в страйпе, они нам известны, так как отказ регистрируется аппаратными средствами. Тогда с помощью вычислительного блока производится расчет текущих контрольных сумм , . При этом при расчете текущих контрольных сумм пропускаются значения отказавших блоков страйпа.

Значения текущих контрольных сумм рассчитываются вычислительным блоком по формулам:

Используя значения хранящихся эталонных контрольных сумм S₀, S₁ и значения текущих контрольных сумм , , вычислительный блок по формулам

вычисляет значения поврежденных информационных зон. Полученные значения записываются вместо поврежденных.

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

В случае повреждения двух информационных зон данные могут быть восстановлены за счет контрольных сумм S₀, S₂. Этот вариант восстановления требует больше вычислительных ресурсов, но он необходим, если кроме информационных зон в страйпе поврежден блок контрольной суммы S₁. Также данный способ восстановления может быть применен в режиме упреждающего восстановления. В этом случае, если повреждены блоки D_j и D_k, являющиеся информационными зонами, где j, k - номера поврежденных блоков в страйпе, они нам известны, так как отказ регистрируется аппаратными средствами. Тогда с помощью вычислительного блока производится расчет текущих контрольных сумм , . При этом при расчете текущих контрольных сумм пропускаются значения отказавших блоков страйпа.

Значения текущих контрольных сумм рассчитываются вычислительным блоком по формулам:

Используя значения хранящихся эталонных контрольных сумм S₀, S₂ и значения текущих контрольных сумм , , вычислительный блок по формулам:

вычисляет значения поврежденных информационных зон. Полученные значения записываются вместо поврежденных.

В случае повреждения двух информационных зон данные могут быть восстановлены за счет контрольных сумм S₁, S₂. Этот вариант восстановления требует больше вычислительных ресурсов, но он необходим, если кроме информационных зон в страйпе поврежден блок контрольной суммы S₀. Также данный способ восстановления может быть применен в режиме упреждающего восстановления. В этом случае, если повреждены блоки D_j и D_k, являющиеся информационными зонами, где j, k - номера поврежденных блоков в страйпе, они нам известны, так как отказ регистрируется аппаратными средствами. Тогда с помощью вычислительного блока производится расчет текущих контрольных сумм , . При этом при расчете текущих контрольных сумм пропускаются значения отказавших блоков страйпа.

Значения текущих контрольных сумм рассчитываются вычислительным блоком по формулам:

Используя значения хранящихся эталонных контрольных сумм S₁, S₂ и значения текущих контрольных сумм , , вычислительный блок по формулам:

вычисляет значения поврежденных информационных зон. Полученные значения записываются вместо поврежденных.

Рассмотрим случай, когда в страйпе повреждены три блока, что соответствует отказу трех дисков массива. Также этот способ восстановления применяется, если во время реконструкции двух отказавших дисков возникает невосстановимая ошибка (UER) чтения, и, следовательно, поврежденными являются три блока. Если повреждены блоки, являющиеся контрольными зонами, тогда с помощью формул расчета контрольных сумм вычислительный блок рассчитывает текущие контрольные суммы, соответствующие поврежденным контрольным зонам. Полученные значения контрольных сумм записываются вместо поврежденных. Если из трех поврежденных блоков один или два являются блоками информационных зон, а остальные контрольные зоны, в этом случае данные восстанавливаются по схемам, описанным выше, для одного или двух отказавших блоков соответственно, а значения поврежденных контрольных зоны рассчитываются по формулам расчета контрольных сумм.

Если повреждены блоки D_j, D_k, D_l, являющиеся информационными зонами, где j, k, l - номера поврежденных блоков в страйпе, они нам известны, так как отказ регистрируется аппаратными средствами. Тогда с помощью вычислительного блока производится расчет текущих контрольных сумм , , . При этом при расчете текущих контрольных сумм пропускаются значения отказавших блоков страйпа.

Значения текущих контрольных сумм рассчитываются вычислительным блоком по формулам:

Для восстановления блоков D_j, D_k, D_l вычислительный блок должен решить систему:

Матрица этой системы является матрицей Вандермонда, ее определитель не равен 0, а значит, система уравнений всегда разрешима.

Введя обозначение:

. b_jkl является определителем матрицы системы.

И используя значения хранящихся эталонных контрольных сумм S₀, S₁, S₂ и значения текущих контрольных сумм , , , вычислительный блок по формулам:

вычисляет значения поврежденных информационных зон. Полученные значения записываются вместо поврежденных.

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

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

Вычислительный блок сравнивает друг с другом соответствующие текущие контрольные суммы , , и хранящиеся эталонные контрольные суммы S₀, S₁, S₂.

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

Если , то искажение данных произошло в блоке страйпа, соответствующем контрольной сумме S_0.

Если , то искажение данных произошло в блоке страйпа, соответствующем контрольной сумме S_1.

Если , то искажение данных произошло в блоке страйпа, соответствующем контрольной сумме S_2.

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

Когда определен номер испорченного блока, вычислительный блок восстанавливает значение этого блока, как это описано выше для одного отказавшего блока страйпа.

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

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

Вычислительный блок сравнивает друг с другом соответствующие текущие контрольные суммы , и хранящиеся эталонные контрольные суммы S₀, S₁.

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

Если , то искажение данных произошло в блоке страйпа, соответствующем контрольной сумме S_0.

Если , то искажение данных произошло в блоке страйпа, соответствующем контрольной сумме S_1.

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

Когда определен номер испорченного блока, вычислительный блок восстанавливает значения всех отказавших блоков, как это описано выше для двух отказавших блоков страйпа.

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

Вычислительный блок сравнивает друг с другом соответствующие текущие контрольные суммы , и хранящиеся эталонные контрольные суммы S₀, S₂.

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

Если , то искажение данных произошло в блоке страйпа, соответствующем контрольной сумме S_0.

Если , то искажение данных произошло в блоке страйпа, соответствующем контрольной сумме S_1.

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

Когда определен номер испорченного блока, вычислительный блок восстанавливает значения всех отказавших блоков, как это описано выше для двух отказавших блоков страйпа.

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

Вычислительный блок сравнивает друг с другом соответствующие текущие контрольные суммы , и хранящиеся эталонные контрольные суммы S₁, S₂.

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

Если , то искажение данных произошло в блоке страйпа, соответствующем контрольной сумме S_1.

Если , то искажение данных произошло в блоке страйпа, соответствующем контрольной сумме S_2.

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

Когда определен номер испорченного блока, вычислительный блок восстанавливает значения всех отказавших блоков, как это описано выше для двух отказавших блоков страйпа.

Если отказавшим блоком страйпа является блок, соответствующий информационной зоне D_j, где j - номер отказавшего блока в страйпе, он известен, так как отказ регистрируется аппаратными средствами. Тогда для обнаружения факта искажения с помощью вычислительного блока рассчитываются текущие контрольные суммы , , по формулам:

Введем вспомогательные обозначения:

Вычислительный блок проверяет следующее условия для обнаружения факта повреждения:

Если (U₁=0 и U₂=0), то искажения данных не обнаружены, и можно восстанавливать отказавший блок, как это описано выше для одного отказавшего блока страйпа. Если это условие не выполнено, тогда с помощью вычислительного блока производится определение номера блока страйпа, в котором произошло искажение данных. Для этого с помощью вычислительного блока проверяются следующие условия:

Если (U₁≠0 и U₂≠0 и u₃≠0), то искажение данных произошло в блоке страйпа, соответствующем контрольной сумме S_0.

Если (U₁≠0 и U₂=0 и u₃≠0), то искажение данных произошло в блоке страйпа, соответствующем контрольной сумме S_1.

Если (U₁=0 и U₂≠0 и u₃≠0), то искажение данных произошло в блоке страйпа, соответствующем контрольной сумме S_2.

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

Когда определен номер испорченного блока, вычислительный блок восстанавливает значения всех отказавших блоков, как это описано выше для двух отказавших блоков страйпа.

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

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

Изобретение относится к вычислительной технике. Технический результат заключается в восстановлении большого числа одновременно отказавших частей запоминающего устройства. Способ восстановления записей в запоминающем устройстве при отказе или повреждении части запоминающего устройства или при искажении данных на запоминающем устройстве, в котором разделяют область памяти запоминающего устройства на информационные зоны одинакового размера и контрольные зоны, выбранные из разных частей запоминающего устройства. Записывают каждую группу подлежащих запоминанию данных в виде набора кодовых слов в соответствующую информационную зону. Находят при каждой записи данных с помощью соответствующего вычислительного блока три эталонных контрольных суммы каждую по заранее установленной формуле. Далее записывают каждую из найденных эталонных контрольных сумм в виде кодового слова с тем же номером в соответствующую контрольную зону, при этом каждая из трех контрольных сумм хранится в отдельной зоне запоминающего устройства. При отказе или повреждении части запоминающего устройства вычисляют с помощью вычислительного блока текущие контрольные суммы по формулам для каждого набора кодовых слов с одинаковыми номерами во всех информационных зонах. Используют значения хранящихся эталонных контрольных сумм и значения текущих контрольных сумм для восстановления утраченных данных путем решения систем уравнений. 2 н. и 8 з.п. ф-лы, 2 ил.

1. Способ восстановления записей в запоминающем устройстве при отказе или повреждении части запоминающего устройства или при искажении данных на запоминающем устройстве, заключающийся в том, что:
разделяют область памяти упомянутого запоминающего устройства на информационные зоны одинакового размера, выбранные из разных частей запоминающего устройства, и контрольные зоны, также выбранные из различных частей запоминающего устройства; записывают каждую группу подлежащих запоминанию данных в виде набора кодовых слов в соответствующую информационную зону;
находят при каждой записи подлежащих запоминанию данных в упомянутое запоминающее устройство с помощью соответствующего вычислительного блока три эталонных контрольных суммы S₀, S₁, S₂, каждую по соответствующей заранее установленной формуле:



где D_i - i-я информационная зона, в которую записаны кодовые слова d_i,1, d_i,2, …, d_i,s-1 i=0, …, n-1, кодовые слова являются элементами поля Галуа;
n - число информационных зон;
s - число кодовых слов в одной информационной зоне;
a - примитивный элемент поля Галуа;
далее записывают каждую из найденных эталонных контрольных сумм в виде кодового слова с тем же номером в соответствующую контрольную зону, при этом каждая из трех контрольных сумм хранится в отдельной зоне запоминающего устройства, в процессе использования упомянутого запоминающего устройства при отказе или повреждении части запоминающего устройства и при выявлении искажений данных вычисляют с помощью упомянутого вычислительного блока текущие контрольные суммы по упомянутым формулам для каждого набора кодовых слов с одинаковыми номерами во всех информационных зонах;
используют значения хранящихся эталонных контрольных сумм и значения текущих контрольных сумм для восстановления утраченных данных;
при этом восстановление утраченных данных с использованием эталонных и текущих контрольных сумм производят путем решения систем уравнений, полученных из формул расчета контрольных сумм, а число уравнений в системе зависит от количества отказавших или поврежденных зон запоминающего устройства.

2. Способ по п.1, отличающийся тем, что дополнительно используют значения хранящихся эталонных контрольных сумм и значения текущих контрольных сумм для обнаружения и поиска искажения данных.

3. Способ по п.1 или п.2, отличающийся тем, что перед восстановлением утраченных данных определяют факт наличия искажения данных сравнением эталонных и текущих контрольных сумм и определяют место искажения данных с помощью систем уравнений, полученных из формул расчета контрольных сумм.

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

5. Способ по п.1, отличающийся тем, что упомянутый вычислительный блок является внешним по отношению к упомянутому запоминающему устройству.

6. Система для восстановления записей в запоминающем устройстве при отказе или повреждении части запоминающего устройства или при искажении данных на нем, содержащая упомянутое запоминающее устройство, включающее в себя n одинакового размера информационных зон, выбранных из разных частей запоминающего устройства, и три контрольные зоны, также выбранные из разных частей запоминающего устройства, и вычислительный блок, при этом:
каждая из упомянутых n информационных зон запоминающего устройства выполнена с возможностью записи в нее группы подлежащих запоминанию данных в виде набора кодовых слов;
каждая из упомянутых трех контрольных зон запоминающего устройства выполнена с возможностью записи в нее соответствующей контрольной суммы;
упомянутый вычислительный блок выполнен с возможностью:
нахождения эталонных контрольных сумм, каждую по соответствующей заранее установленной формуле, для каждого i-го набора кодовых слов, где i=0, …, n-1, во всех упомянутых n информационных зонах при каждой записи подлежащих запоминанию данных в упомянутое запоминающее устройство,
при этом для расчета контрольных сумм S₀, S₁, S₂ применяются следующие формулы:



где D_i - i-я информационная зона, в которую записаны кодовые слова d_i,1, d_i,2, …, d_i,s-1; i=0, …, n-1, кодовые слова являются элементами поля Галуа;
n - число информационных зон;
s - число кодовых слов в одной информационной зоне;
a - примитивный элемент поля Галуа;
при этом вычислительный блок в процессе использования упомянутого запоминающего устройства при отказе или повреждении части запоминающего устройства и при выявлении искажений данных выполнен с возможностью определения текущих контрольных сумм по упомянутым формулам для каждого набора кодовых слов с одинаковыми номерами во всех информационных зонах и использования значений хранящихся эталонных контрольных сумм и значения текущих контрольных сумм для восстановления утраченных данных, а восстановление утраченных данных с использованием эталонных и текущих контрольных сумм производится путем решения систем уравнений, полученных из формул расчета контрольных сумм, число уравнений в системе зависит от количества отказавших или поврежденных зон запоминающего устройства.

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

8. Система по п.6 или 7, отличающаяся тем, что вычислительный блок выполнен с возможностью перед восстановлением утраченных данных определения факта наличия искажения данных путем сравнения эталонных и текущих контрольных сумм и определения места искажения данных с помощью систем уравнений, полученных из формул расчета контрольных сумм.

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

10. Система по п.6, отличающаяся тем, что упомянутый вычислительный блок является внешним по отношению к упомянутому запоминающему устройству.