СПОСОБ ОРГАНИЗАЦИИ ХРАНЕНИЯ ДАННЫХ НА БАЗЕ КОДОВ-ПРОИЗВЕДЕНИЙ С ПРОСТОЙ ПРОВЕРКОЙ НА ЧЕТНОСТЬ СО СМЕЩЕНИЕМ
METHOD OF ORGANIZING STORAGE OF DATA BASED ON CODES OF PRODUCTS WITH SIMPLE PARITY CHECK WITH OFFSET

Изобретение относится к вычислительной технике, в частности системам хранения данных. Заявленный способ может быть использован для организации надежного хранения данных как в локально размещенных массивах устройств хранения данных, так и в распределенных системах хранения данных, позволяя снизить нагрузку на сеть передачи данных.
В условиях непрерывного роста объемов генерируемой и обрабатываемой информации, сопряженного с увеличением объемов трафика данных передаваемого через сети передачи данных, объединяющие различные устройства, остро стоит проблема организации надежного долгосрочного хранения данных. Для решения данной проблемы применяются различные аппаратные и программные средства, в частности системы хранения данных, состоящие из множества устройств хранения данных объединенных в массив. Надежность хранения данных в подобных системах гарантируется применением различных методов избыточного кодирования и резервирования.
1
1
1
1
1
Наиболее близким по технической сущности к заявленному способу является способ, представленный в патенте US 6269453 В1 от 31 июл 2001, когда массив из N=K+1 устройств хранения данных разделяется на множество K, собственно устройств хранения информационных данных и одно дополнительное устройство хранения избыточных данных, при этом область памяти каждого из N устройств хранения данных, делиться на I равных зон хранения таким образом, что K одноименных зон разных хранилищ информационных данных формируют в хранилище избыточных данных одноименную зону, что в совокупности по всем одноименным зонам составляет линию проверки на четность с номером i⊂I, в случае утраты одного из устройств хранения данных, входящих в массив производится опрос всех оставшихся устройств хранения данных с последовательной передачей в контроллер массива содержимого всех зон входящих в линии проверки на четность.
Недостатками прототипа являются:
- предложенное техническое решение позволяет обнаруживать линии проверки на четность, содержащую некорректируемую ошибку, не обнаруживаемую средствами устройств хранения данных, но не позволяет определить зону содержащую эту ошибку для дальнейшего ее исправления;
- в случае утраты одного из устройств хранения данных и осуществлении процедуры восстановления его содержимого, возникает необходимость передачи всего содержимого оставшихся не утраченными устройств хранения данных, что приводит к возрастанию нагрузки на сеть передачи данных, росту времени простоя системы в целом;
- в ходе восстановления данных, проводимого в случае утраты одного из устройств хранения данных, возрастает нагрузка на оставшиеся устройства хранения данных, что снижает их быстродействие и ресурс.
Задачей, на решение которой направлено изобретение, является разработка способа организации хранения данных в массиве устройств хранения данных, базирующемся на применении кодов-произведений с простой проверкой на четность.
Техническим результатом являются:
- снижение общей нагрузки на сеть передачи данных возникающая в ходе восстановления массива данных в случае утраты одного устройства хранения данных из массива устройств хранения данных;
- снижение нагрузки на устройства хранения данных, оставшиеся в массиве, возникающей в процессе восстановления данных;
- повышение надежности хранения данных в системах хранения данных.
l
l
1
1
1
1
1
Для достижения указанного технического результата предлагается способ восстановления целостности данных в массиве устройств хранения данных, заключающийся в том, что массив из N=K+1 устройств хранения данных разделяется на множество K собственно устройств хранения информационных данных и одно дополнительное устройство хранения избыточных данных, при этом область памяти каждого из N устройств хранения данных, делиться на I равных зон хранения таким образом, что K одноименных зон разных хранилищ информационных данных формируют в хранилище избыточных данных одноименную зону, что в совокупности по всем N одноименным зонам составляет линию проверки на четность с номером i⊂I, при этом в случае утраты одного из хранилищ восстановление данных, хранившихся в нем, осуществляется путем последовательного выделения одноименных зон каждого из K оставшихся устройств хранения данных, и за счет системы проверок четности данной линии восстанавливаются утраченные данные этой линии, при этом последовательно используются номера i⊂I линий.
1
2
2
1
2
1
1
Особенностью является то, что в каждом из N устройств хранения данных множество I зон делятся на J=I/(K+1) групп, где K число зон хранения информационных данных в хранилищах d⊂K и соответствующих K зон избыточных данных в устройстве хранения избыточных данных, совокупность которых в каждом хранилище формирует зону избыточных данных с номером j⊂J, при этом избыточные данные групп для каждого из N устройств хранения данных не могут размещаться в устройствах хранения данных для которых они сформированы, а хранятся по принятой в системе схеме хранения избыточных данных групп, например с циклическим сдвигом номеров относительно истинных номеров групп, и при необходимости восстановления содержимого утраченного устройства хранения данных, выбираются любые J-2 линии для каждой из групп, с последующим восстановлением утраченных данных для этих линий, при этом в утраченную группу вводятся избыточные данные группы, находящееся в одном из K оставшихся не утраченных устройств хранения данных, жестко закрепленных схемой хранения избыточных данных групп, при этом контроль соответствия содержимого в зонах хранения избыточности и зонах хранения информационных символов позволяет определять зону дислокации скрытых ошибок.
Предлагаемый способ к кодированию данных, размещаемых в памяти массива устройств хранения данных предназначен для повышения надежности функционирования массива, в условиях одиночных отказов отдельных узлов. Новизна этого способа заключается в уменьшении объема трафика передаваемых через сеть обмена данных, генерируемого в случае восстановления содержимого утраченного информационного накопителя, и в возможности обнаруживать и исправлять одиночные некорректируемые ошибки, возникающие в ходе генерации данных, осуществления операций кодирования и передачи данных в память устройств хранения данных.
Предлагаемый способ предполагает формирование и хранение в памяти накопителей двух контрольных сумм. Одна из контрольных сумм размещается в памяти отдельного устройства хранения данных. Вторая контрольная сумма размещается в каждом из устройств хранения данных, как в информационных, так и избыточном. Условием функционирования этого решения является то, что сформированный избыточный символ не должна находиться в том же устройств хранения, для которого оно рассчитан.
Пример организации хранения данных в массиве устройств хранения данных продемонстрирован на Фиг. 1.
Источник и потребитель данных (101), передает исходный массив данных в контроллер (102) массива устройств хранения данных (103).
1
2
2
1
2
1
2
Для осуществления организации хранения, исходный массив данных разделяется контроллером (102) на k*k фрагментов одинакового размера, размещаемых в зоны (104) устройств хранения информационных данных (105-107), таким образом, что в каждом из них расположено k фрагментов, размещенных в зонах, объединенных в группы (108). В случае если информационный массив делится на число фрагментов меньше k*k оставшиеся заполняются значениями ноль. В ином случае, если информационный массив делится на число фрагментов больше k*k, он разделяется на несколько слов, обрабатываемых по отдельности. Последовательность зон с одинаковыми номерами, но находящихся на разных устройствах хранения данных образует линию проверки на четность (109).
Формирование избыточности, размещаемом в зонах (110) отдельного устройстве хранения данных (111), производится с использованием выражения:
i,j
где i=1, …, k2 - номера зон в каждом из устройств хранения данных, j - номер информационного устройства хранения, d - символы содержащиеся в зоне номер i устройства хранения данных j,  - сумма элементов по модулю 2.
Формирование избыточности, размещаемом в отдельной линии всех устройств хранения данных (112), производится с использованием выражения:
j,i
i
где i=1, …, k2 - номера фрагментов в каждом из устройств хранения данных, j=2, …, k1 - номер информационного устройства хранения данных, d - символы содержащиеся в зоне номер i устройства хранения данных j, r - фрагмент номер i устройства хранения избыточных данных.
В случае возникновения события утраты устройства хранения данных, содержимое зоны утраченного устройства хранения данных считается стертым. Массив устройств хранения данных становится безызбыточным до введение в массив устройств хранения данных новоприбывшего устройства хранения данных (113). Операции чтения данных осуществляется с проведением операции декодирования.
i,утр
Восстановление содержимого утраченного устройства хранения информационных данных производится путем вычисления обратных контрольных сумм d' для всех кроме одного информационного фрагмента с использованием выражения:
утр
Последний фрагмент утраченного множества восстанавливается с использованием соответствующей контрольной суммы q, с использованием выражения:
Полученные символы передаются пользователю или при наличии новоприбывшего устройства хранения данных размещаются в соответствующих зонах этого устройства.
Выявление и коррекция одиночной некорректируемой ошибки, не выявляемой средствами устройства хранения данных, производится путем расчета всех контрольных сумм, как фрагментов, так и хранилищ, с последующим сравнением их с эталонными. Дислокация зоны с поврежденным символом определяется как зона линии с выявленным несоответствием значений вычисленной избыточности с эталонной избыточностью, размещенной в устройстве хранения избыточных данных, расположенная в группе устройства хранения данных для которой вычисленная избыточность не совпадает с эталонной избыточностью, расположенной в зоне хранения избыточности, вычисленной для этой группы зон.
Предлагаемый способ к организации хранения данных, размещаемых в памяти массива устройств хранения данных, позволяет повысить надежность обеспечения операций хранения и восстановления информации, в условиях одиночных отказов отдельных узлов. Применение этого способа позволяет:
- уменьшить объем трафика, передаваемый через сеть обмена данных, генерируемый в случае восстановления содержимого утраченного информационного накопителя;
- снизить эксплуатационную нагрузку, оказываемую на сохранившиеся в составе массива устройства хранения данных в процессе восстановления содержимого утраченного устройства хранения данных;
- повысить надежность обеспечения процедуры хранения, за счет аппарата обнаружения и исправления одиночных некорректируемых ошибок, возникающих в ходе генерации данных, осуществления операций кодирования и передачи данных в память устройств хранения данных по каналам сети передачи данных.