Способ организации хранения данных на базе кодов-произведений с простой проверкой на четность со смещением

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

 

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

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

Наиболее близким по технической сущности к заявленному способу является способ, представленный в патенте US 6269453 В1 от 31 июл 2001, когда массив из N₁=K₁+1 устройств хранения данных разделяется на множество K₁, собственно устройств хранения информационных данных и одно дополнительное устройство хранения избыточных данных, при этом область памяти каждого из N₁ устройств хранения данных, делиться на I равных зон хранения таким образом, что K₁ одноименных зон разных хранилищ информационных данных формируют в хранилище избыточных данных одноименную зону, что в совокупности по всем одноименным зонам составляет линию проверки на четность с номером i⊂I, в случае утраты одного из устройств хранения данных, входящих в массив производится опрос всех оставшихся устройств хранения данных с последовательной передачей в контроллер массива содержимого всех зон входящих в линии проверки на четность.

Недостатками прототипа являются:

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

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

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

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

Техническим результатом являются:

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

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

- повышение надежности хранения данных в системах хранения данных.

Для достижения указанного технического результата предлагается способ восстановления целостности данных в массиве устройств хранения данных, заключающийся в том, что массив из N_l=K_l+1 устройств хранения данных разделяется на множество K₁ собственно устройств хранения информационных данных и одно дополнительное устройство хранения избыточных данных, при этом область памяти каждого из N₁ устройств хранения данных, делиться на I равных зон хранения таким образом, что K₁ одноименных зон разных хранилищ информационных данных формируют в хранилище избыточных данных одноименную зону, что в совокупности по всем N₁ одноименным зонам составляет линию проверки на четность с номером i⊂I, при этом в случае утраты одного из хранилищ восстановление данных, хранившихся в нем, осуществляется путем последовательного выделения одноименных зон каждого из K₁ оставшихся устройств хранения данных, и за счет системы проверок четности данной линии восстанавливаются утраченные данные этой линии, при этом последовательно используются номера i⊂I линий.

Особенностью является то, что в каждом из N₁ устройств хранения данных множество I зон делятся на J=I/(K₂+1) групп, где K₂ число зон хранения информационных данных в хранилищах d⊂K₁ и соответствующих K₂ зон избыточных данных в устройстве хранения избыточных данных, совокупность которых в каждом хранилище формирует зону избыточных данных с номером j⊂J, при этом избыточные данные групп для каждого из N₁ устройств хранения данных не могут размещаться в устройствах хранения данных для которых они сформированы, а хранятся по принятой в системе схеме хранения избыточных данных групп, например с циклическим сдвигом номеров относительно истинных номеров групп, и при необходимости восстановления содержимого утраченного устройства хранения данных, выбираются любые J-2 линии для каждой из групп, с последующим восстановлением утраченных данных для этих линий, при этом в утраченную группу вводятся избыточные данные группы, находящееся в одном из K₁ оставшихся не утраченных устройств хранения данных, жестко закрепленных схемой хранения избыточных данных групп, при этом контроль соответствия содержимого в зонах хранения избыточности и зонах хранения информационных символов позволяет определять зону дислокации скрытых ошибок.

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

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

Пример организации хранения данных в массиве устройств хранения данных продемонстрирован на Фиг. 1.

Источник и потребитель данных (101), передает исходный массив данных в контроллер (102) массива устройств хранения данных (103).

Для осуществления организации хранения, исходный массив данных разделяется контроллером (102) на k₁*k₂ фрагментов одинакового размера, размещаемых в зоны (104) устройств хранения информационных данных (105-107), таким образом, что в каждом из них расположено k₂ фрагментов, размещенных в зонах, объединенных в группы (108). В случае если информационный массив делится на число фрагментов меньше k₁*k₂ оставшиеся заполняются значениями ноль. В ином случае, если информационный массив делится на число фрагментов больше k₁*k₂, он разделяется на несколько слов, обрабатываемых по отдельности. Последовательность зон с одинаковыми номерами, но находящихся на разных устройствах хранения данных образует линию проверки на четность (109).

Формирование избыточности, размещаемом в зонах (110) отдельного устройстве хранения данных (111), производится с использованием выражения:

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

Формирование избыточности, размещаемом в отдельной линии всех устройств хранения данных (112), производится с использованием выражения:

где i=1, …, k2 - номера фрагментов в каждом из устройств хранения данных, j=2, …, k1 - номер информационного устройства хранения данных, d_j,i - символы содержащиеся в зоне номер i устройства хранения данных j, r_i - фрагмент номер i устройства хранения избыточных данных.

В случае возникновения события утраты устройства хранения данных, содержимое зоны утраченного устройства хранения данных считается стертым. Массив устройств хранения данных становится безызбыточным до введение в массив устройств хранения данных новоприбывшего устройства хранения данных (113). Операции чтения данных осуществляется с проведением операции декодирования.

Восстановление содержимого утраченного устройства хранения информационных данных производится путем вычисления обратных контрольных сумм d'_i,утр для всех кроме одного информационного фрагмента с использованием выражения:

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

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

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

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

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

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

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

Способ восстановления целостности данных в массиве устройств хранения данных, заключающийся в том, что массив из N_l=K₁+1 устройств хранения данных разделяется на множество K₁ собственно устройств хранения информационных данных и одно дополнительное устройство хранения избыточных данных, при этом область памяти каждого из N₁ устройств хранения данных делится на I равных зон хранения таким образом, что K₁ одноименных зон разных хранилищ информационных данных формируют в хранилище избыточных данных одноименную зону, что в совокупности по всем N₁ одноименным зонам составляет линию проверки на четность с номером i⊂I, при этом в случае утраты одного из хранилищ восстановление данных, хранившихся в нем, осуществляют путем последовательного выделения одноименных зон каждого из K₁ оставшихся устройств хранения данных, и за счет системы проверок четности данной линии восстанавливают утраченные данные этой линии, при этом последовательно используют номера i⊂I линий, отличающийся тем, что в каждом из N₁ устройств хранения данных множество I зон делят на J=I/(K₂+1) групп, где K₂ число зон хранения информационных данных в хранилищах d⊂K₁ и соответствующих K₂ зон избыточных данных в устройстве хранения избыточных данных, совокупность которых в каждом хранилище формирует зону избыточных данных с номером j⊂J, при этом избыточные данные групп для каждого из N₁ устройств хранения данных не могут размещаться в устройствах хранения данных, для которых они сформированы, а хранятся по принятой в системе схеме хранения избыточных данных групп, например, с циклическим сдвигом номеров относительно истинных номеров групп, и при необходимости восстановления содержимого утраченного устройства хранения данных выбирают любые J - 2 линии для каждой из групп с последующим восстановлением утраченных данных для этих линий, при этом в утраченную группу вводят избыточные данные группы, находящиеся в одном из K₁ оставшихся неутраченных устройств хранения данных, жестко закрепленных схемой хранения избыточных данных групп, при этом контроль соответствия содержимого в зонах хранения избыточности и зонах хранения информационных символов позволяет определять зону дислокации скрытых ошибок.